A conductance the arcs do not measure

The previous essay left the directed case with almost nothing: a matrix with an exact null vector on one side, complex unordered eigenvalues, non-orthogonal eigenvectors, and no quadratic form to build a cut argument on.

There is a construction that gives all of it back. It is Chung’s, it is short, and the price it charges is not accuracy or cost — it is that the quantity at the end of the argument is not the one that went in.

The construction #

Let P be the transition matrix of the random walk and φ its stationary distribution — the left null vector the previous essay had to compute. Write Φ for the diagonal matrix of φ. Then

$$\mathcal{L} \;=\; I \;-\; \tfrac{1}{2}\bigl(\Phi^{1/2} P \Phi^{-1/2} \;+\; \Phi^{-1/2} P^{\mathsf T} \Phi^{1/2}\bigr)$$

is symmetric by construction. So it has real eigenvalues, they lie in [0, 2], they can be ordered, there is a second-smallest one, there is a quadratic form to minimise, and there is a Cheeger inequality relating that eigenvalue to a best cut.

Everything the arrows took, returned. And the whole of the debt is in the two occurrences of Φ.

The form is worth reading slowly, because it is doing two things at once. $\Phi^{1/2} P \Phi^{-1/2}$ is a similarity transform of P, so it has P’s eigenvalues — nothing about the spectrum has been changed by it. Adding its transpose and halving is what makes the result symmetric, and that is a genuine change: the symmetric part of a matrix does not have the matrix’s eigenvalues, and 𝓛’s spectrum is not a reordering of the directed Laplacian’s. So the construction is not a rewriting of the same object in better coordinates. It is a different matrix, chosen so that a theorem applies to it.

The second route, which is a closed form #

A construction this convenient needs checking against something that is not itself, and the directed case supplies one.

If a digraph is balanced — every vertex’s in-degree equal to its out-degree — then its stationary distribution is proportional to the degree, exactly. Substituting that into the definition above collapses it: 𝓛 becomes the ordinary undirected normalised Laplacian of the graph with its arrows removed.

So the check is that on a balanced digraph the two matrices agree entry for entry. They do, to 10⁻¹⁴ at every size from eight to forty-eight, which is the rounding level for a power iteration and a pair of square roots. One matrix comes from an 824-step walk and the other from a formula in the degrees, and they share no arithmetic.

That is also this essay’s refusal. The natural thing to believe about symmetrising a digraph is that it amounts to ignoring the arrows, and on the two-block family the two matrices differ by 0.163 — which is not a rounding, is not small relative to a matrix whose entries are at most 1, and is what the direction is worth.

What the inequality is about #

Cheeger’s inequality for 𝓛 reads

λ₂/2  ≤  Φ(G)  ≤  √(2λ₂)

with Φ(G) the best conductance over all cuts. In the undirected case the conductance of a set S is the weight of the edges leaving it over the volume of the smaller side, and everybody knows what it means: how hard it is to cut the graph there.

Here Φ(S) is

Σ over i in S, j not in S of  φᵢ Pᵢⱼ    divided by    min(φ(S), φ(S̄))

The numerator is the probability that one step of the stationary walk crosses the cut. It is not the weight of the arcs crossing it. It is those arcs weighted by how often the walk is standing at their tail, and on a digraph those two are different numbers.

On the hero’s graph they are 0.1235 and 0.0400 — a factor of three, with the circulation conductance the larger. Read the band as a statement about the arc count and it says the cut is three times better than the walk finds it.

The band itself is wide, which is worth noting before it is read too closely. λ₂ = 0.0662 puts the lower end at 0.0331 and the upper at 0.364, a factor of eleven between them — so Cheeger’s inequality locates the conductance within an order of magnitude and no better. That is the undirected situation too and the essay that measured it says why: the square root on the upper half is not slack, it is attained on a cycle. A factor of three inside a band of eleven is not a violation of anything. It is a substitution the band is too wide to notice, which is the reason it has to be found by naming the quantities rather than by checking the inequality.

What Φ actually weights, in one paragraph #

The substitution is easier to hold with a concrete reading of the numerator.

Σ φᵢ Pᵢⱼ over arcs crossing the cut is a sum over those arcs of how much probability mass sits at the tail times what fraction of it leaves along this arc. An arc out of a vertex the walk almost never visits contributes almost nothing, however heavy the arc is; an arc out of a vertex the walk sits on contributes a great deal, however light. So the circulation conductance is the arc weight re-weighted by the walk’s own opinion of where it spends its time.

On an undirected graph that re-weighting is the identity, because φᵢ is the degree share and Pᵢⱼ is the arc weight over the degree, so the product is the arc weight over the total. That cancellation is the entire reason the undirected case never has to make this distinction — and it is a coincidence of undirected graphs rather than a general fact.

Which is bigger is not a fixed answer #

The natural next question is whether the substitution has a direction, and the measurement says no.

Across sizes from twenty to thirty-six and one to eight arcs running back across the cut, the ratio between the two quantities runs from 0.25 to 3.09, and passes through 1 on the way. At twenty vertices with four arcs back they agree to five per cent.

That matters for how the finding is stated. A bias could be corrected by a constant and would make the arc conductance a usable proxy with a caveat. A ratio that crosses one, in both directions, depending on the graph, cannot: they are two different quantities that happen to coincide sometimes, and the coincidence is not informative.

It also cost the figure an assertion. The first version asserted that the two differ substantially at every setting, which is false and which its own drag range refused — so what is asserted now is Cheeger’s inequality for the circulation, at every setting, and a factor of three on one fixed reference graph built independently of what the slider is showing.

Why it has to be the walk #

It is reasonable to ask why the symmetrisation is not done with something simpler — the degrees, or the arc weights symmetrised directly — and the answer is that neither gives a theorem.

Symmetrising the adjacency matrix and taking the undirected normalised Laplacian of the result is a perfectly well-defined operation. It produces a matrix, it has a Cheeger inequality, and the inequality is about the undirected graph rather than about the digraph: the sweep it justifies finds a good cut of a graph that was not the one asked about. On the two-block family that graph is a different object by 0.163 in the worst entry, and the cut it prefers is a different cut.

The distinction is worth labouring because both operations are called symmetrising and they are not the same operation. One symmetrises the graph and then builds a Laplacian; the other builds the Laplacian and symmetrises it, with respect to a measure the graph supplies. The first throws the arrows away. The second keeps them, in the only place they can be kept once the matrix has to be symmetric — in the weights.

The walk is what makes the inequality a statement about the arrows. It is also the reason two conditions are needed that the undirected case never had:

• Strong connectivity. A walk on a digraph that is not strongly connected has more than one closed communicating class and therefore more than one stationary distribution, and there is no canonical Φ to symmetrise by. The essay on a chain with no stationary vector is that failure from the Markov side, and the PageRank essays repair it the way everybody does, by adding a teleport — which changes the walk and therefore changes the conductance the inequality is about.
• Aperiodicity, or a teleport instead. A directed cycle’s walk never converges: the distribution rotates for ever. The construction here uses a teleport of exactly zero on the families that are aperiodic and reports which walk it is using, because the answer is a property of the walk rather than of the graph.

What this leaves the field with #

Three statements, and the third is the one worth carrying.

The apparatus is recoverable. A directed graph has a symmetric normalised Laplacian, a real spectrum in [0, 2], a spectral partitioning algorithm and a Cheeger inequality, and all of them reduce to the undirected versions exactly when the graph is balanced. Nothing here is a heuristic, which is worth contrasting with the rest of this field: the sweep cut itself is a heuristic — it searches n − 1 of the 2ⁿ possible cuts — and the essay measuring what that costs is about the gap between the cut it finds and the best one. That gap is unchanged here. What has been recovered is the theorem around the heuristic, not a better heuristic.

The cost is a global computation. Where the undirected case read a degree — an integer, local, free — this one computes a stationary distribution, which is an iteration to a tolerance and depends on the whole graph. So the matrix being partitioned carries an error before its eigenvalues are computed, and the sensitivity of that first step is not something the undirected essays ever had to price.

And the quantity has been substituted. This is the part that survives outside the mathematics. Somebody asking for a good cut of a directed graph usually means few arcs cross it, and what the theorem delivers is the walk rarely crosses it. On the graph in the hero those differ by a factor of three, and on others by a factor of four the other way. A method that answers a question adjacent to the one asked is the harder kind of wrong to notice, because everything about it is correct.

It is also, in a smaller way, the shape of a spanning-tree preconditioner making a grid worse: a theorem that holds exactly, applied to an object it is genuinely about, delivering something the person who invoked it did not want. The remedy in both cases is to read what quantity is on which side of the inequality, and that is the whole content of this essay.

That is the same shape as the two undirected Laplacians, where one minimises a cut counting vertices and the other a cut counting edge endpoints, and quoting Cheeger’s inequality about the wrong one is out by 19× on the complete graph. The directed case adds a third object to the pair, and the arithmetic that decides between them is a walk.

Where the construction’s own error comes from #

The undirected essays in this field can treat the matrix as exact. This one cannot, and it is worth locating the error rather than waving at it.

Three roundings enter before an eigenvalue is computed. The stationary distribution is the fixed point of a power iteration, stopped at a tolerance — 824 steps to 10⁻¹⁴ on the hero’s graph. The square roots of its entries are correctly rounded and are not exact, which is exactly the situation the normalised Laplacian’s inexact null vector describes in the undirected case. And the entries of 𝓛 are then quotients of those square roots.

The consequence is a matrix that is symmetric only to the rounding level, which the routine checks rather than assumes: the measured relative asymmetry is below 10⁻¹² on every family drawn, and the figure fails rather than symmetrising by hand if it is not. A matrix that is nearly symmetric fed to a symmetric eigensolver is a small perturbation of a symmetric problem, and symmetric eigenvalues are perfectly conditioned, so the eigenvalues inherit the perturbation and not an amplification of it.

Which is a mild answer, and it is worth saying so: the construction is not numerically delicate. What it is, is dependent on a computation that the undirected case got for free, and the difference shows up as a tolerance and an iteration count rather than as an inaccuracy.

The teleport, which changes the question #

One detail in the construction has to be reported rather than buried, because it changes what the answer is about.

A walk on a graph that is not strongly connected has no unique stationary distribution, and the universal repair is a teleport: with probability 1 − α the walk jumps to a uniformly chosen vertex. That makes the chain irreducible and aperiodic whatever the graph is, so φ exists and is unique.

It also makes φ the stationary distribution of a different walk. The conductance the Cheeger inequality then bounds is the conductance of that walk, which includes the teleport’s own crossings of the cut — and at α = 0.85, the value everybody uses, a substantial part of the circulation across any cut is teleportation rather than the graph.

The figures here use α = 1 on the families that are strongly connected and aperiodic, so the walk is the graph’s own and the numbers mean what they say. That is a choice the families make available and a real digraph often does not, which is why the readout names the walk rather than only the graph.

At other settings #