Fast Computation of First k Eigenvectors of Graph Laplacian I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph $L = D - A, ~ L \in \mathbb{R}^{n\times n}$


Algorithm(s) to efficiently estimate the first $k$ (smallest in magnitude) eigenvectors of $L$ -- and, the time complexity of such an algorithm. Denote these eigenvectors by $U_{:,1:k} \in \mathbb{R}^{n\times k} $. 
For $1 \leq i, j \leq n$ and $p \in \{1,2\}$, can we determine whether or not $||U_{i,1:k} - U_{j,1:k}||_p$ is a close estimate of $||U_{i,:} - U_{j,:}||_p$ up to small multiplicative error, with high probability?


Edit 1: Based on helpful comments, I've corrected Q2 to hopefully something more accurate.
Answer to Q1:

In [1], it is argued at the end of section 1 that the first k eigenvectors can be approximated in time roughly $O(mk)$ (up to log-factors), with $m$ the number of edges. They are not very precise in their statement however, but I'm not aware of a better reference explictly stating this.

Answer to Q2:

No, this will not hold in general. You are describing a $k$-dimensional embedding of the nodes $[n] \to \mathbb{R}^k; i \mapsto U_{i,1:k}$, as is used in for instance spectral clustering. For nodes $i, j$ which lie in the same cluster (e.g., in the same clique of a dumbbell graph), the quantity $\|U_{i,1:k} - U_{j,1:k}\|_2$ will be small for sufficiently small $k$. On the other hand, if $i \neq j$ then $U_{i,:}$ is orthogonal to $U_{j,:}$ and hence $\|U_{i,:}-U_{j,:}\| = \sqrt{2}$.

[1] Koutis et al. "Faster spectral sparsification and numerical algorithms for sdd matrices." (2015)