Resistance vs. density | Population Algorithms by Petar Maymounkov

Resistance vs. density - 0

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.

Resistance vs. density - 0

Desire to speak? ↓