Graph Spectra | Population Algorithms by Petar Maymounkov

Cryo-EM structure determination – No Comments

Under Computer Science, FA: Functional Analysis, Graph spectra, Mathematics, Spontaneous, Talk

The crazy title up there means “recovering a 3D model of a molecule, using multiple 2D images/projections”. This was a talk at MIT by Yoel Shkolnisky. The talk was really neat, but the bottom line is this. From a CS point of view he was solving the following question. We have n points that (we know) come from some finite metric. We are given the pairwise distances (+ noise) between points that are within each other’s vicinity (in that metric). The goal is to reconstruct the metric. I’ve phrased this problem a little more generally then the form in which it is addressed in Yoel’s work.

The cool thing is that Yoel et al. solve this problem using a very natural appeal to graph Laplacians. This is found in a technical report on his page. Amit Singer (a collaborator) additionally has a paper on using these techniques to recover the global metric of sensor networks, based on local distance information. This is found in the form of a paper on Amit’s webpage.

There might be an opportunity for a new paper lurking in there. In particular, it is interesting to ask under what noise conditions (and noise can be correlated in real-world examples) is the recovery good. Having heard the talk, I believe that the answer to this question will also depend on the type of metric being recovered, i.e. it may depend on its doubling dimension e.g.

Oh, I should also mention that Yoel seems to have some cool papers involving the discrete Radon transform. This is probably a good place to read about it, while avoiding the continuous lingo.

L1 bounds for Laplacians – No Comments

Under Computer Science, Graph spectra, Question, Spontaneous

Spectral Graph theory has various methods of bounding the Laplacian eigenvalues of a graph G (say by embedding another graph H into G and computing the congestion). Usually we look at the ordered eigenvalues $0=\lambda_1<\lambda_2\le \cdots \le \lambda_n$ , and usually we simplify things a little by assuming a bounded-degree graph, which gives us $\lambda_n\le D_{\max}=O(1)$ for free, where $D_{\max}$ is the maximum vertex degree. So really, it is mostly just interesting to bound $\lambda_2$ from below. When this is done, it is very often used as $\|L^{-1}x\|_2 \le \lambda_2^{-1} \|x\|_2$ (when bounding energy of electrical flows in G) or as $\|(I-L)^kx\|_2\le (1-\lambda_2)^k \|x\|_2$ (when bounding mixing times of random walks on G).

We are interested in a new type of Laplacian bounds. It turns out that L1 bounds of the sort $\min_{x\bot\vi,\|x\|_1=1}\|Lx\|_1\ge \eta$ relate directly to how good electrical flow is when used for oblivious routing on G. Note that it is required here that $x\bot\vi$ since $\vi$ is the kernel of the Laplacian of any connected graph. This sort of bound is atypical in two ways. First, it is an L1 bound, and second, it is a lower-bound.

It is trivial to see that $\|L_{K_n}x\|_1=n$ where $L_{K_n}$ is the Laplacian of the n-clique. What we are after is proving that

$\|L_H x\|_1\ge (\log n)^{-1}$ where H is an expander and $\|x\|_1=1$ and $x\bot\vi$ .

This statement holds true in experiments with random bounded-degree expanders, and in particular it has natural interpretations in terms of electrical flow (which I am going to omit here). One can even give a pseudo-proof of this fact by simply observing that $L_H \approx L_{K_n} / n\log n$ .

I am curious if someone has come across similar types of inequalities and/or has an interesting proof idea.

Note that the above conjecture was recently proven and its proof will soon appear in a publication. I will post a link to it here when this happens. At this stage will be happy to hear of applications of this (now) theorem if you come across any.

Resistance vs. density – No Comments

Under Computer Science, Graph spectra

In a recent paper “Graph sparsification by effective resistances”, Spielman, Srivastava (STOC’08) show that one can sparsify a graph by essentially randomly getting rid of edges with very low effective resistance. Here we discuss an interesting corollary of one of the lemmas in this paper, which is not explicitly mentioned in the paper. In particular, we show a direct connection between the edge density of a graph and the smallest effective resistance.

For a graph $G$ define $\Pi=W^{1/2}BL^{-1}B^* W^{1/2}\in\mathds{R}^{E\times E}$ . This is all standard notation: $W$ is the diagonal edge-weights matrix, $B\in\mathds{R}^{E\times V}$ is the edge orientation matrix, and $L$ is the Laplacian. (Note we have that $L=B^*WB$ .)

The matrix $\Pi$ has the property that $\Pi_{e,e}=w_eR_e$ , where $R_e$ is the effective resistance of edge $e$ , and $w_e$ is its weight. We’ll focus on the case when all $w_e=1$ for simplicity. We prove the following statement:

If graph $G$ has $n$ vertices and $m$ edges, then there is an edge of effective resistance at most $(n-1)/m$ .

To see this, we use Lemma 3 in the paper which states that $\Pi$ has eigenvalue $1$ of multiplicity $n-1$ , and eigenvalue 0 of multiplicity $m-n+1$ . The sum of the eigenvalues thus equals $n-1$ . On the other hand, the trace of $\Pi$ equals $\sum_e w_eR_e$ . Equating the two (and using $w_e=1$ ) we get $\sum_e R_e = n-1$ . Therefore $\E\cdot R_e = (n-1)/m$ . Thus, there must exist at least one edge with effective resistance at most $(n-1)/m$ .

This inequality is tight in various small-graph cases that one could think of. And it is asymptotically tight in others (a long cycle with a shortcut in the middle). It is interesting to find out whether it is tight for large graphs of intermediate density (more than linear, less than quadratic).

Let’s see how this equality relates (directly) to sparsification. A close inspection of Lemma 4 in the paper asserts the following statement:

If we remove an edge $e$ from a graph, then the Laplacian of the new and the old graph are related by $(1-w_e R_e)L\preccurlyeq\tilde{L}\preccurlyeq L$ . This inequality is tight on both sides.

On the left equality is attained when considering the vector of potentials corresponding to a unit electric flow between the endpoints of $e$ . On the right equality is attained by considering any vector that equals 0 over the endpoints of $e$ .

The last statement combined with the inequality (that relates effective resistance to density) beg the question whether one can sparsify a graph by removing one edge at a time (and re-weighting the rest appropriately). If this is indeed a possibility, it would also have to be true that any sequence of removed edges $e_1,\dots,e_k$ that leads to a best sparsification must contain the edge of smallest effective resistance in the original graph.

The questions mentioned here are important since they relate to the conjecture that all graphs have linear-size sparsifiers. It is also a possibility that a one-edge-at-a-time procedure may lead to a more practical sparsification (in the Laplacian sense) algorithm than the currently available alternatives.