<p>Answer to Q1:</p>

<p>In [1], it is argued at the end of section 1 that the first k eigenvectors can be approximated in time roughly <span class="math-container">$O(mk)$</span> (up to log-factors), with <span class="math-container">$m$</span> 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.</p>

<p>Answer to Q2:</p>

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

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

CC BY-SA 4.0
2020-02-05T08:15:09.673Z
2020-02-05T08:15:09.673Z
smapers
<p>I'm looking for references for the following; Given the unnormalized Laplacian matrix of a graph <span class="math-container">$L = D - A, ~ L \in \mathbb{R}^{n\times n}$</span></p>

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

<p>Edit 1: Based on helpful comments, I've corrected Q2 to hopefully something more accurate.</p>

CC BY-SA 4.0
2020-01-14T15:36:37.323Z
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, so let's hope for a better reference. I don't see how these eigenvectors can help for your second question.

[1] Koutis et al. "Faster spectral sparsification and numerical algorithms for sdd matrices." (2015)
smapers
CC BY-SA 4.0
2020-01-14T16:04:06.273Z
@smapers: Thanks for the reference. In the penultimate paragraph of Section 1 in [1], they write "The algorithm consists of two steps...  spectral sparsification preserves the eigenvalues of G within $(1 ± \epsilon/2)$". Do you know if they mean that this holds for all eigenvalues of G? Consequently, would it hold that a $(1 + \epsilon/3)$-approximate eigenvector of $\tilde{G}$ is a $(1 + \epsilon/2)$-approximate eigenvector of G for all eigenvectors?

My motivation for the second question, approximating distance, comes from similar results in constructing sketches of high-dim points.
madman_with_a_box
CC BY-SA 4.0
2020-01-14T16:17:41.283Z
Yes, this statement holds simultaneously for all eigenvalues of $G$ (this is in contrast to sketching). Your second question depends on how you define a $(1+\epsilon)$-approximate eigenvector.
smapers
CC BY-SA 4.0
2020-01-14T22:46:09.930Z
Sorry if I'm misunderstanding, but I don't really get 2. First, "high probability" over what? Also, are you sure you want $U$ to be the smallest $k$ eigenvalue/eigenvector pairs? These are provably the least informative eigenvectors as far as forming a good approximation of $L$, so I don't see how $U$ helps in your problem (which is perhaps what @smapers was alluding to). If you had the top $k$ eigenvectors, you could find the best rank $k$ approximation $L'$ and estimate what you want from $L'$ using the triangle inequality (so the error will depend on how good the approximation is).
Jason Gaitonde
CC BY-SA 4.0
2020-01-15T10:56:24.877Z
@J.G - your comment and what smapers also mentioned helped me realize the issue. I've updated the question. Please let me know if this sounds more sensible. My apologies for the mistake. To answer your other question, I guess I'm wondering if I can pick some $k = \mathcal{O}(\log n)$ eigenvectors such that the "spectral" distance is well estimated. And I think you're right. Perhaps the top-k would be more useful. If you could point me to a reference for this, that would be great.
madman_with_a_box
<reference-request><graph-theory><spectral-graph-theory>
Fast Computation of First k Eigenvectors of Graph Laplacian
madman_with_a_box
# Fast Computation of First k Eigenvectors of Graph Laplacian

(Asked by: username_0 on 2020-01-14)

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}$

1. 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} $.
2. 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.

**Tags:** reference-request, graph-theory, spectral-graph-theory
> **Comments:**
> **username_1**: 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, so let's hope for a better reference. I don't see how these eigenvectors can help for your second question.  [1] Koutis et al. "Faster spectral sparsification and numerical algorithms for sdd matrices." (2015)  
> **username_0**: @smapers: Thanks for the reference. In the penultimate paragraph of Section 1 in [1], they write "The algorithm consists of two steps...  spectral sparsification preserves the eigenvalues of G within $(1 ± \epsilon/2)$". Do you know if they mean that this holds for all eigenvalues of G? Consequently, would it hold that a $(1 + \epsilon/3)$-approximate eigenvector of $\tilde{G}$ is a $(1 + \epsilon/2)$-approximate eigenvector of G for all eigenvectors?  My motivation for the second question, approximating distance, comes from similar results in constructing sketches of high-dim points.  
> **username_1**: Yes, this statement holds simultaneously for all eigenvalues of $G$ (this is in contrast to sketching). Your second question depends on how you define a $(1+\epsilon)$-approximate eigenvector.  
> **username_2**: Sorry if I'm misunderstanding, but I don't really get 2. First, "high probability" over what? Also, are you sure you want $U$ to be the smallest $k$ eigenvalue/eigenvector pairs? These are provably the least informative eigenvectors as far as forming a good approximation of $L$, so I don't see how $U$ helps in your problem (which is perhaps what @smapers was alluding to). If you had the top $k$ eigenvectors, you could find the best rank $k$ approximation $L'$ and estimate what you want from $L'$ using the triangle inequality (so the error will depend on how good the approximation is).  
> **username_0**: @J.G - your comment and what smapers also mentioned helped me realize the issue. I've updated the question. Please let me know if this sounds more sensible. My apologies for the mistake. To answer your other question, I guess I'm wondering if I can pick some $k = \mathcal{O}(\log n)$ eigenvectors such that the "spectral" distance is well estimated. And I think you're right. Perhaps the top-k would be more useful. If you could point me to a reference for this, that would be great.  

---

## 1 answers

### Answer by username_1 on 2020-02-05. Score: 1 | Accepted answer

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)


---

