1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – smapers
    Commented Jan 14, 2020 at 15:36
  • $\begingroup$ @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. $\endgroup$
    – madman_with_a_box
    Commented Jan 14, 2020 at 16:04
  • $\begingroup$ 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. $\endgroup$
    – smapers
    Commented Jan 14, 2020 at 16:17
  • $\begingroup$ 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). $\endgroup$
    – Jason Gaitonde
    Commented Jan 14, 2020 at 22:46
  • $\begingroup$ @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. $\endgroup$
    – madman_with_a_box
    Commented Jan 15, 2020 at 10:56

1 Answer 1

Reset to default
1
$\begingroup$

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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.