Upper bound on the difference between two elements of an eigenvector

Question

Let $W$ be the non-negative, symmetric adjacency/affinity matrix for some connected graph. If $W_{ij}$ is large, then vertex $i$ and vertex $j$ have a heavily weighted edge between them. If $W_{ij} = 0$, then no edge connects vertex $i$ to vertex $j$.

Now $L = \mathrm{diag}(W\mathbf{1})-W$ is the (unnormalized) graph Laplacian. Let $v$ be the Fiedler vector of $L$, that is, a unit eigenvector corresponding to the second smallest eigenvalue of $L$. As $W_{ij}$ increases, all else equal, $|v_i - v_j|$ tends to decrease---at least this is the idea behind spectral clustering. What is an upper bound on $|v_i - v_j|$, given quantities that don't require computing $v$, like $W_{ij}$ and $\|W\|$?

Any suggestions or thoughts would be greatly appreciated.

Answer 1

Let me at least point out a trivial bound.

If $L$ is a Laplacian, then $x^TLx=\sum_{i,j}L_{i,j}(x_i-x_j)^2$. Let $\lambda$ be the eigenvalue for the Fiedler vector. Then $$\lambda = x^TLx = \sum_{i,j} w_{i,j}(x_i-x_j)^2,$$ whence $|x_i-x_j| \le (\lambda/w_{i,j})^{1/2}$.

Answer 2

I've seen peopl use Davis and Kahan (1970), "The Rotation of Eigenvectors by a Perturbation". It's sometimes a bit tough going, but incredibly useful for problems like this.

More info would also be useful. Is $W$ stochastic? Are there underlying latent classes that control the distribution of $W_{ij}$, e.g., with $E(W_{ij})$ larger if $i$ and $j$ possess the same class? If so, then I suggest first considering $E(W_{ij})$ with the latent classes given. Reorder the rows and columns according to latent class. You'll end up with a block matrix with entries constant on each block. It's not that difficult to then compute eigenvalues and eigenvectors of this block matrix. You'll find the eigenvector entries for the same latent class are the same. Now perturb the matrix from $E(W)$ back to the original $W$ and use Davis and Kahan to bound differences in the eigenvector entries.