Behaviour of eigenspaces of adjacency matrices after a single change to the graph

Question

Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra edge (changing a single 0 in the matrix into a 1)? or the opposite (change a single 1 to a 0)? I am looking for a bound on the change to the eigenvectors and eigenvalues in the general case, but any answer which is restricted only to symmetric matrices (bidirectional graph) would be also great. In this case the change made to the matrix can be symmetric (e.g if I changed element $A_{ij}$ from 1 to 0 I will also change element $A_{ji}$ from 1 to 0).

The only information I found so far involved perturbation theory, but I'm not sure if any of that is applicable in my case because from what I understand it is relevant only for very small perturbations (orders of magnitude smaller than the values in the matrix) and in my case I'm making quite a big change to the matrix.

EDIT:

I am also interested to know if there is an algorithm for accounting for small changes in the matrix by changing only a subset of eigenvectors: Say I have $n$ independent eigenvectors of a matrix $A$, and I make a small change in $A$ as explained above. I want to hold $k$ eigenvectors fixed, and to account for the change only with changing the $n-k$ other eigenvectors.

So if I denote the change matrix (in the example above it's a matrix with 1 in the element I'm going to change in A and zeros everywhere else) by $\epsilon$ , and the original eigendecomposition of $A$ as $A=Q\lambda Q^{-1}$ where $\lambda$ is a diagonal matrix with the eigenvalues on the diagonal and $Q$ a matrix with the corresponding eigenvectors as columns, can I express (or approximate) $A + \epsilon$ in terms of $Q*$ and $\lambda*$ where the latter two are matrices with $k$ columns which are the same as as $Q$ and $\lambda$ respectively and $n-k$ columns that have changed (maybe it's possible to express the change in terms of $\epsilon$? that would be awesome).

Answer 1

What I'm about to say applies to the eigenvalues (at least). Here's what comes to my mind - it sprung from memory of some results of Batson, Spielman and Srivastava, mostly the paper "Twice Ramanujan sparsifiers" (http://arxiv.org/pdf/0808.0163.pdf).

In this paper they try to construct a sparse weighted graph that spectrally approximates a given weighted graph. They do it by greedily choosing the next edge to add. A key observation is that if you pass to the Laplacian matrix $L$ of a graph, the effect of adding an edge $e=(x,y)$ on the Laplacian is that $$L_{new} = L_{old} + vv^T$$ where $v$ is a column vector with say $1$ in the $x$-th position and $-1$ in the $y$-th. From Cauchy's interlacing theorem, it follows that the eigenvalues of $L_{new}$ are interlaced by the eigenvalues of $L_{old}$, meaning that if $\lambda_1\geq\ldots\geq \lambda_n$ are the eigenvalues of $L_{old}$ and $\lambda_1'\geq\ldots\geq\lambda_n'$ are the eigenvalues of $L_{new}$, we have

$$ \lambda_1'\geq \lambda_1\geq\lambda_2'\geq\lambda_2\geq\ldots\geq \lambda_n'\geq\lambda_n$$

(I could find a proof here http://orion.math.iastate.edu/lhogben/research/LaplacianTalkHall.pdf). The Batson-Spielman-Srivastava paper goes on to make this relationship more quantitative, by providing expressions for the new eigenvalues and intuition for their positions between the old ones via a physical model. I think section 3 of their paper would be of interest to you.