There are some themes that you hear about here and there for years. You know it’s cool, you know it’s probably profound, but you’ve never really taken it seriously. Then, one day, you decide to take a deeper look at it, and you find yourself sucked in a black hole of mathematical revelations. To me, this is spectral graph theory.
When I first heard about the whole notion of “effective resistance” I thought, cool, complicated algebra tricks and something cute in return. But actually, it turns out that viewing undirected graphs as a resistor network, and thinking about its effective resistance between pairs of nodes, arises in a number of applications, such as sparsification, or centrality measures. So, it’s worth buckling down, looking long and hard at the equations, and finally making them make sense.
The main paper I am using as a reference is
[1] Daniel A. Spielman, Nikhil Srivastava. Graph sparsification by effective resistances, 2009.
However, truthfully, a solid elementary circuits textbook will be likely more detailed.
What is effective resistance?
There are probably multiple answers to this question.
- Effective resistance is a way of summarizing a graph’s “inverse flow rate”. For example, consider a network of water pipes connecting various houses. Then, the flow of water coming from a source to my house is not only dependent on the size of a single pipe, but the size of all the pipes in all the paths from the source to my house. So, it doesn’t make sense to only look at the size of the pipe connecting the source directly to my house, but a “summary of pipe sizes”, over all the other pipes. This is one intuitive way to think of it.
- Effective resistance is a metric for spectrally-optimal matrix sparsification. This is the main idea behind [1], where the effective resistance is used as the sampling weights to produce a sparser matrix approximation of a graph Laplacian. Specifically, an approximation $L’$ computed this way satisfies
$$
(1-\epsilon) x^TL’x \leq x^TLx \leq (1+\epsilon)x^TL’x
$$
for optimal $\epsilon$. - Finally, most formally, the effective resistance $R_{i,j}$ is the actual resistance, in ohms, that represents the action of a resistor network with two exposing heads, at nodes $i$ and $j$. The rest of the nodes represent internal junctions, and in between each pair of junction $i,j$ where $A_{i,j} > 0$, lies a resistor of resistance $1/A_{i,j}$.
- Effective resistance has close connections with other graph concepts, like mean hitting times, and Kemeny constants. However, whether we chose to interpret this close connection as some cool electrical phenomenon, or merely that they are all closely related to $L^\dagger$ is… as the saying goes, six in one, half a dozen in the other.
I’ll guess there are even more answers to this question, but I’ll leave it up to the comments section. Now let’s do some math.
Don’t drink and derive, but do derive some effective resistances
Problem setup
Suppose I have an undirected graph, with $n$ nodes, and an edge set $\mathcal E$ containing pairs of nodes $(i,j)$, where $i,j \in \{1,…,n\}$. The weight of the edges are stored in a symmetric adjacency matrix
$$ A_{i,j} \geq 0, \quad i\neq j, \qquad A_{ii} = 0.$$
Moreover, $A_{i,j}\neq 0$ only if $(i,j) \in \mathcal E$. Also, we have the degree matrix $D = \mathrm{diag}(A\mathbf 1)$ and Laplacian matrix $L = D-A$ is symmetric and positive semidefinite.
Electrical networks setup
Now suppose that this graph actually models an electrical network, where nodes indicate junctions (e.g. where wires cross) and the weight $A_{i,j} = 1/r_{i,j}$ where $r_{i,j}$ is the resistance (in Ohms) of a physical resistor placed connecting junctions $i$ and $j$. Assume that at most one resistor appears for each pair $(i,j)$.
Now, pick any two nodes, say $k$ and $l$. We will ground the junction at $k$ and put a 1-volt power source on junction $l$. This will cause current to flow in the graph, from a source node $l$ and a terminus $k$. The effective resistance $R_{k,l}$ is defined as the resistance that summarizes this entire network into one resistor, with ends $k$ and $l$.
Specifically, from Kirchoff’s current law, for every node not $k$ or $l$, the sum of the currents (a signed quantity) going into each node should be 0; flow is conserved. For nodes $k$ and $l$, the cumulative current going into $k$ is the same as that coming out of $l$. Call this last quantity $\bar I_{k,l}$, in amps. Then, using Ohm’s law, $R_{k,l} = \frac{1}{\bar I_{k,l}}$.
The main claim
A (now well known, and frequently used) fact:
$$
R_{i,j} = L^\dagger_{ii} + L^\dagger_{jj} \,-\, 2L^\dagger_{i,j}\tag{$\star$}
$$
where $L^\dagger$ is the Moore-Penrose pseudoinverse of this graph.
Example. Consider the following circuit.
Now, what is the effective resistance $R_{1,2}$? Using elementary circuit knowledge, we would see it involves two resistors ($r_{1,3}$, $r_{2,3}$) in series and then $r_{1,2}$ in parallel, so
\[
R_{1,2} = \frac{1}{\frac{1}{r_{13} + r_{23}} + \frac{1}{r_{12}}} = \frac{r_{12}(r_{13}+r_{23})}{r_{12} + r_{13} + r_{23}}
\]
Meanwhile, in matrix form,
\[
A = \begin{bmatrix} 0 & \frac{1}{r_{12}} & \frac{1}{r_{13}}\\ \frac{1}{r_{12}} & 0 & \frac{1}{r_{23}}\\ \frac{1}{r_{13}} & \frac{1}{r_{23}} & 0 \end{bmatrix}, \qquad L = \begin{bmatrix} \frac{1}{r_{12}} + \frac{1}{r_{13}} & -\frac{1}{r_{12}} & -\frac{1}{r_{13}}\\ -\frac{1}{r_{12}} &\frac{1}{r_{12}} + \frac{1}{r_{23}} & -\frac{1}{r_{23}}\\ -\frac{1}{r_{13}} & -\frac{1}{r_{23}} & \frac{1}{r_{13}} +\frac{1}{r_{23}} \end{bmatrix}.
\]
Using MATLAB’s handy dandy symbolic toolbox,
\[
L^\dagger =
\frac{1}{9(r_{12} + r_{13} + r_{23})}
\begin{bmatrix}
4r_{12}r_{13} + r_{12}r_{23} + r_{13}r_{23} & -2r_{12}(r_{13}+r_{23}) +r_{13}r_{23} & -2r_{13}(r_{12}+r_{23}) + r_{12}r_{23}\\
-2r_{12}(r_{13}+r_{23}) +r_{13}r_{23} & r_{12}r_{13} + 4r_{12}r_{23} + r_{13}r_{23} & -2r_{23}(r_{12}+r_{13}) + r_{12}r_{13} \\
-2r_{13}(r_{12}+r_{23}) + r_{12}r_{23} & -2r_{23}(r_{12}+r_{13}) + r_{12}r_{13} & r_{12}r_{13} + r_{12}r_{23} + 4r_{13}r_{23}
\end{bmatrix}
\]
and one can manually check that, for $k\neq l \neq j$,
\[
(e_k-e_l)^T L^\dagger (e_k-e_l)=
\frac{ r_{k,l} ( r_{k,j} + r_{l,j} )}{r_{k,l} + r_{k,j} + r_{l,j}}.
\]
Interpretation as a Euclidean distance matrix. Note that since $L$ is symmetric positive semidefinite, so is $L^\dagger$. Therefore, we can think of $L^\dagger$ as the Gram matrix of points $p_1,…,p_n$ where $L^\dagger_{i,j} = p_i^Tp_j$. Moreover, since by construnction, the mean row or column sum of $L$, then $L\mathbf 1 = 0$ and therefore $L^\dagger \mathbf 1 = 0$. That is to say, the points are centered; e.g. $\sum_{i=1}^n p_i = 0$. Then, the Euclidean distance matrix corresponding to these points $p_1,…,p_n$ is exactly $R$, e.g. $R_{i,j} = \|p_i-p_j\|_2^2$.
The main proof
Now, let’s go back and prove ($\star$).
First, we should interpret $A_{i,j} = \frac{1}{r_{i,j}}$ as the edge conductance, and write Ohm’s law as
\[
\text{current from $i$ to $j$ } = I_{i,j} = \frac{v_i-v_j}{r_{i,j}} = v^T(e_i-e_j)A_{i,j}.
\]
Next, we apply 1V to node $k$ and ground node $l$. Then, by KCL, the cumulative current flowing out of node $j$ is
\[
\bar I_j = \sum_{i}I_{i,j} = \begin{cases}
0 & j \not\in \{k,l\}\\
\frac{1}{R_{k,l}} & j= k\\
-\frac{1}{R_{k,l}} &j =l\\
\end{cases}
\]
so we may write succinctly
\[
I^T\mathbf 1 \,-\, \frac{1}{R_{k,l}} (e_k-e_l) = 0.
\]
Filling in the terms for $I$, this means
\begin{eqnarray*}
0 &=& \sum_j v^T(e_i-e_j)A_{i,j}- \frac{1}{R_{k,l}} (e_k-e_l)_i \\
\Rightarrow 0 &=& (D-A)v\, -\,\frac{1}{R_{k,l}} (e_k-e_l)\\
\iff R_{k,l}L v &=& e_k-e_j
\end{eqnarray*}
Applying $(e_k-e_l)L^\dagger$ to both sizes gives
\[
R_{k,l}(e_k-e_l)^TL^\dagger L v = (e_k-e_l)^TL^\dagger(e_k-e_l)
\]
Next, I claim that $L^\dagger L = I – \frac{1}{n}\mathbf 1 \mathbf 1^T$. To see this, note that $\mathbf 1$ is orthogonal to all the nontrivial eigenvectors in $L$. So, given the eigenvalue decomposition
\[
L = \sum_{i=2}^n \lambda_i u_iu_i^T,
\]
then
$$
L+\frac{1}{n}\mathbf 1\mathbf 1^T = \sum_{i=2}^n \lambda_i u_iu_i^T+\frac{1}{n}\mathbf 1\mathbf 1^T,\qquad (L+\frac{1}{n}\mathbf 1\mathbf 1^T)^{-1} = \sum_{i=2}^n \frac{1}{\lambda_i} u_iu_i^T + \frac{1}{n} \mathbf 1 \mathbf 1^T
$$
so
\[
(L+\frac{1}{n}\mathbf 1\mathbf 1^T)^{-1} = L^\dagger + \frac{1}{n} \mathbf 1 \mathbf 1^T
\]
and
\[
I = (L+\frac{1}{n}\mathbf 1\mathbf 1^T)(L+\frac{1}{n}\mathbf 1\mathbf 1^T)^{-1} = (L+\frac{1}{n}\mathbf 1\mathbf 1^T) (L^\dagger + \frac{1}{n}\mathbf 1\mathbf 1^T) = LL^\dagger + \frac{1}{n} \mathbf 1\mathbf 1^T.
\]
Therefore, since recall $v_k = 1$ and $v_l = 0$,
\[
(e_k-e_l)^TL^\dagger(e_k-e_l) = R_{k,l}(e_k-e_l)^T (I \,-\, \frac{1}{n}\mathbf 1 \mathbf 1^T) v = R_{k,l}(v_k-v_l) = R_{k,l}.
\]
Actually, there isn’t much needed in terms of minimizing energies or anything fancy, just good old fashioned Kirchoff’s laws!
Finally, here is a summarizing image created by DALLE via ChatGPT4. The spelling could be improved, but otherwise, hopefully it gets the message across!
