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.

At eight arcs back the arc conductance leaves the band altogether. λ₂ = 0.1161 there, so Cheeger’s interval is [0.0581, 0.4819], the circulation conductance of the returned cut is 0.1458 and sits inside it as the theorem requires — and the arc conductance of the same cut is 0.5385, above the upper end.

Nothing is violated: the inequality is a statement about the circulation and the circulation obeys it. What the reading shows is that the substitution is not a matter of degree. A quantity that can sit outside the band the theorem draws is not a slightly different version of the quantity inside it, and a reader checking the theorem by computing conductances the undirected way would here conclude the theorem is false.

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 twenty-five configurations of one family say no. A hundred and twelve, across two families and four seeds, say yes.

The circulation conductance is the smaller of the two four times out of five, by a median factor of about 1.4. So the substitution does have a direction — and the graph at the top of this essay is one of the eighteen per cent where it runs the other way, and the most extreme of them: at 0.1235 against 0.0400 it is the largest ratio anywhere in the sample.

That inverts what the hero illustrates. It is drawn to show the walk finding the cut worse than the arcs suggest, and the typical case is the walk finding it better — which makes sense of the numerator once it is read: an arc out of a rarely visited vertex contributes almost nothing to Σ φᵢPᵢⱼ, and most cuts have some such arcs crossing them, so the walk’s opinion of a cut is usually kinder than the arc count’s.

The ratio still passes through one, and at twenty vertices with four arcs back the two agree to five per cent. What it does not do is sit around one.

That matters for how the finding is stated, and the wider sample changes which half of it is doing the work. A bias could in principle be corrected by a constant; what cannot be corrected is the spread, which runs from 0.118 to 3.392 — a factor of twenty-nine — around a median of 0.72. Multiplying the arc conductance by 1.4 would put the median right and leave the individual answers wrong by up to a factor of five in either direction.

So the conclusion stands and its reason changes. The arc conductance is not a usable proxy for the circulation one, not because the substitution has no direction — it has one, and a clear one — but because knowing the direction does not narrow the answer. They are two different quantities whose ratio has a typical value and no useful precision, which is a worse position than two quantities with no relationship at all, because the typical value invites a correction that does not work.

There is a lesson about the figure in that, and it is the second time this essay has had to learn it. The hero was chosen because it shows the substitution clearly, and clearly meant largely — the graph with the biggest gap between the two quantities. A configuration chosen for the size of an effect is, by construction, a draw from the tail of that effect’s distribution, and the tail is where the sign can differ from the body. So the figure that makes a phenomenon visible is systematically the one least representative of it.

The repair is not to draw a duller graph. It is to say, beside the striking one, what the distribution looks like — which is what the table above is for, and what turns a factor of three into a factor of three in the minority direction, out of a range of twenty-nine. The striking case and the typical case are both worth drawing, and only one of them was.

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.

The slider is where the mechanism is visible, because it moves the one thing the two quantities disagree about: how many arcs run back across the cut.

Across one, two, three, four, six and eight arcs back the two read 0.1235, 0.0816, 0.0768, 0.1078, 0.1369, 0.1458 for the circulation and 0.0400, 0.1538, 0.1481, 0.1429, 0.3750, 0.5385 for the arcs. The mechanism is in the two ranges rather than in the ratio: adding arcs back multiplies the arc conductance by 13.5 and the circulation by 1.18.

That is the substitution stated causally rather than statistically. An arc added back across the cut adds its full weight to the numerator the arc count uses, and adds to the numerator the walk uses only as much as the walk visits its tail — and the vertices these arcs leave from are exactly the ones the walk reaches last. So the two quantities do not merely differ; one of them is nearly insensitive to the thing the other one is measuring, which is why no constant relates them and why the ratio’s spread over the wider sample is a factor of twenty-nine.

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.