Two Laplacians of one graph

A graph does not determine a matrix. It determines several, and the two that matter are built from the same degrees and the same edges by rules that differ in one diagonal scaling.

The combinatorial Laplacian is L = D − A. The normalised Laplacian is $\mathcal{L} = D^{-1/2} L D^{-1/2}$, which is the same matrix conjugated by the square roots of the degrees. Written entry by entry, 𝓛 has ones on the diagonal and −1/√(dᵢdⱼ) where there is an edge.

The scaling is small enough to look like bookkeeping and it is not. A conjugation by a diagonal matrix is a similarity only when the same matrix appears on both sides in inverse pairs, and it does not here: $D^{-1/2}LD^{-1/2}$ is a congruence, not a similarity. Congruences preserve the number of positive, negative and zero eigenvalues — inertia — and preserve nothing else about the spectrum. So the two matrices have the same rank and the same number of components, and no relationship at all between their eigenvalues beyond that.

The two sides of that inequality do not behave alike, and the slider is what shows it. Drawn at forty vertices the picture is one graph family among nine; drawn across the whole range it is two different statements about a bound.

One side of Cheeger’s inequality is attained and the other degrades linearly in n. The lower bound reads exactly 1 at every stop on the slider: there is a graph at each size for which λ₂/2 is the conductance, so no better constant is available and the inequality is sharp. The upper bound is a different kind of object:

The last column is the reading. Looseness against n has a slope of exactly one — 15.7 over 16, 19.8 over 20, 12.0 over 12 between consecutive stops — and an intercept converging on about −2.8. So the upper bound is loose by roughly n − 3 on the barbell, which is not a constant factor to be absorbed into a rule of thumb; it is an over-estimate that grows without limit as the graph does.

Which is worth carrying because the inequality is usually quoted as a two-sided statement, and it is two statements of very different strength. λ₂/2 ≤ φ is an equality on a graph that can be named. The √(2λ₂) side is a guarantee that a good cut exists and is not a prediction of how good, and on this family the gap between the guarantee and the cut is the size of the graph.

The obvious guess, and what it costs #

The guess everybody makes on meeting 𝓛 is that it is L divided by a degree — that on a graph whose degrees are all d, 𝓛 is exactly L/d, so on a graph whose degrees vary, 𝓛 must be L divided by something between the smallest and the largest.

The first half is true. On a d-regular graph $D^{-1/2}$ is $d^{-1/2}$ times the identity, the conjugation commutes with everything, and the spectra are proportional with constant d exactly. Every cycle, every hypercube and every complete graph in this field satisfies it.

The second half is false, and it is worth having the numbers.

graph            λ₂(L)     λ₂(𝓛)     ratio    degrees
grid 6×7         0.19806   0.06297    3.15     2 to 4
preferential 60  0.58610   0.19664    2.98     2 to 17
barbell 10       0.16905   0.01864    9.07     9 to 10
two blocks 60    2.55381   0.15383   16.60    10 to 22

The barbell is the clearest refutation. Its degrees are nine and ten — as close to regular as an irregular graph gets — and the ratio between the two second eigenvalues is 9.07, which is outside that range and not by a little. The two-block graph has degrees from ten to twenty-two and a ratio of 16.6, above every degree it has.

The reason is that λ₂ is not a function of any one vertex. It is a minimum of a Rayleigh quotient over a subspace, and the conjugation changes both the numerator and the constraint the minimisation runs under, in different ways at different vertices. There is no scalar to divide by because the two minimisations are not the same minimisation.

There are three names and two matrices #

A third object is in circulation and it is worth placing, because it is the one a probabilist writes down and it is not a third matrix.

The random-walk Laplacian is D⁻¹L = I − D⁻¹A, whose second factor is the transition matrix of a walk that steps to a uniformly chosen neighbour. It is not symmetric, so it has no business in an essay about eigenvalues of real symmetric matrices — except that

$$D^{1/2}(D^{-1}L)D^{-1/2} \;=\; D^{-1/2} L D^{-1/2} \;=\; \mathcal{L}$$

which is a similarity, not a congruence. So D⁻¹L and 𝓛 have exactly the same eigenvalues, real, in [0, 2], and the two differ only in whether the eigenvectors carry a factor of $D^{1/2}$.

That is the whole relationship between the three, and it is asymmetric in a way worth stating plainly. The normalised Laplacian and the random-walk Laplacian are the same operator seen in two bases. The combinatorial Laplacian is a different operator. Naming all three “the Laplacian” is how a statement proved about one comes to be quoted about another, and the essays about the walk rely on the similarity above at every step: they compute a symmetric matrix’s spectrum with the site’s own symmetric eigensolver and read the answer as a property of a non-symmetric one.

There is a practical consequence too. A walk on a graph with a degree-one vertex has a transition matrix with an entry of 1 in it, and a walk on a graph with a degree-thirty vertex has entries of 1/30 — a range of thirty in a matrix whose symmetric cousin has every diagonal entry equal to one. The symmetric form is the better conditioned object to compute with and the non-symmetric one is the better object to think with, which is an ordinary situation and is why the change of basis is worth knowing rather than worth avoiding.

Which cut each of them is looking for #

The useful way to tell them apart is to ask what each one’s second eigenvector is trying to do.

For the combinatorial Laplacian, minimising xᵀLx over vectors orthogonal to the constant and of unit length is a relaxation of the ratio cut: minimise the number of edges crossed, divided by the number of vertices on the smaller side. The denominator counts vertices.

For the normalised Laplacian the same minimisation, after the change of variable $y = D^{1/2}x$, is a relaxation of the conductance: minimise the weight crossed, divided by the total degree on the smaller side. The denominator counts edge endpoints.

Those are different objectives, and which is wanted depends entirely on what the vertices are. If they are machines to be given equal amounts of work, the count is right. If they are pages in a link graph and the question is how likely a random surfer is to cross, the volume is right. Neither is the correct one; they are answers to two questions that happen to have the same shape.

On a graph with equal degrees the two objectives coincide, which is why the distinction can be carried for a long time without ever being made. On the preferential-attachment graph here, the two sweeps return different partitions — one cuts after 29 vertices and the other after 30 — and the conductances they reach are 0.2321 and 0.2389. The combinatorial one wins on conductance, which is not what it was minimising, and there is no contradiction: a relaxation optimises its own objective and the sweep afterwards is a heuristic in both cases.

How often the choice changes the cut #

One graph is an anecdote, and the general picture is different in a way that matters more than the anecdote. Forty graphs — twenty preferential-attachment at n = 50, twenty two-block at n = 40:

• 23 of the 40 return exactly the same cut. The same vertex set, from eigenvectors of two matrices whose second eigenvalues differ by up to an order of magnitude. More than half the time there is nothing to choose at all.
• Of the seventeen that differ, the normalised sweep reaches the smaller conductance eleven times and the combinatorial four, with two ties. So the relaxation does, on balance, do better at its own objective, and the example above is the minority case rather than the pattern.
• And in three of the seventeen the two objectives disagree outright about which cut is better — one wins on conductance and loses on ratio cut — with several more where one of them ties.

That last is what answers to two questions looks like when it is measured, and where it appears is the interesting part. It appears at the level of the cut, and hardly at all. At the level of the eigenvalue the two matrices are wildly different: 16.6× apart on the two-block graph, and the table above shows no scalar relating them. At the level of the answer they usually agree exactly, and where they disagree the objectives usually agree about which is better.

So the two Laplacians are, as objects, as different as the congruence argument says. As partitioners they are nearly the same partitioner, and the distinction that is worth carrying is about which theorem applies rather than about which cut comes back. The next section is that theorem, and it is the place where the choice is not a matter of a vertex or two.

There is a practical reading of the 23 that is worth extracting, because it is the opposite of what the eigenvalue table suggests. A code that has already computed one Fiedler vector and is wondering whether the other Laplacian would have given a better answer can be told: usually not, and when it does the improvement is a few per cent of a conductance. The measured differences on the seventeen have a median of 4.6% and a worst case of 20%, both relative to the smaller conductance. That is a smaller effect than the choice of sweep rule, and very much smaller than the gap between either sweep and the best cut the graph has.

Which puts the two Laplacians in their place relative to the rest of the pipeline. Choosing between them is a decision about what the theorem in the next section is a theorem about; it is not a knob that buys a better partition. A reader who has been given the eigenvalue table and no cut table would conclude the opposite, and that is exactly why the cut table is here.

The inequality is about one of them, and only one #

The result that makes spectral partitioning more than a heuristic is Cheeger’s inequality: for the normalised Laplacian’s second eigenvalue and the graph’s conductance φ,

λ₂/2  ≤  φ  ≤  √(2λ₂)

Both halves are theorems. The left one says a small eigenvalue is evidence that a good cut exists; the right one says a good cut cannot exist without a small eigenvalue. Together they say that the relaxation is not merely suggestive — it is within a square root of the truth.

Substitute the combinatorial eigenvalue and the left half is false, spectacularly:

graph            λ₂(L)/2    φ measured    out by
complete 20      10.00      0.5263        19.0×
two blocks 60     1.2769    0.08982       14.2×
grid 6×7          0.09903   0.09859        1.0×
star 30           0.5       1.0           holds

On the complete graph the bound claims the conductance is at least ten, and every cut of a complete graph has conductance about a half. The bound is out by nineteen and the failure is not marginal.

This is not a subtlety about which convention a textbook uses. It is a statement about which matrix the theorem is a theorem for, and the site has a name for this shape: a condition number scaling cannot move makes the same point about a diagonal rescaling that changes a computed quantity while changing nothing about the problem. The difference here is that both matrices are legitimate objects and both are used, so the mistake is not applying a bound to a badly scaled matrix — it is applying a bound to the wrong matrix.

The upper half is the more interesting one and the next essay in this anchor’s neighbour is about how loose it is, which is loosest exactly where it is quoted.

What the two share, and it is not much #

They agree about the kernel. Both are positive semidefinite, both have rank n minus the number of components, and both have the component indicators — scaled, in the normalised case — spanning the kernel. That is the inertia, and it is what a congruence preserves.

They agree about nothing else. The combinatorial spectrum has no upper bound beyond twice the maximum degree; the normalised one is contained in [0, 2] for every graph, with 2 attained exactly when the graph is bipartite. That last fact is a genuine capability the combinatorial matrix does not have: a bipartite graph’s normalised spectrum is symmetric about 1 and its largest eigenvalue is exactly 2, so the normalised Laplacian detects bipartiteness and the combinatorial one does not. The cospectral pair at the end of this field is the sharpest instance: two graphs with identical combinatorial spectra, one of which contains a triangle and one of which is bipartite, separated at once by the other matrix.

The bounded spectrum is also why every account of random walks uses the normalised one. The walk matrix D⁻¹A is not symmetric, but $D^{1/2}(D^{-1}A)D^{-1/2} = D^{-1/2}AD^{-1/2}$ = I − 𝓛 is, so the walk’s eigenvalues are one minus the normalised Laplacian’s, are real, and lie in [−1, 1] where a probabilist expects them. The rate is the second eigenvalue is that substitution used in earnest.

A third question neither of them answers #

It is worth saying what the choice between these two does not settle, because the framing above can make it look as though picking the right Laplacian picks the right cut.

Both objects hand back a real vector, and both leave the rounding of that vector into a subset entirely open. The sweep — sort the entries, take every prefix, keep the best — is a heuristic applied afterwards, and it is the same heuristic in both cases. Cheeger’s inequality bounds what the best prefix of the normalised eigenvector’s sweep achieves, so it covers the heuristic as well as the relaxation; nothing analogous is available for the combinatorial one, and the ratio cut it relaxes is NP-hard to optimise exactly.

So the two matrices differ in which objective they relax and in how much is known about what happens next, and they do not differ at all in the step where a continuous answer becomes a discrete one. The vector that has to be rounded is about that step, and it applies to both.

The exactness is not shared either #

The previous essay made a point of the combinatorial Laplacian’s null vector: L·1 is exactly the zero vector, because each row is a cancellation of integers, and the measurement returns 0 with no exponent.

The normalised Laplacian’s null vector is $D^{1/2}\mathbf{1}$, and it is not exact. Building it costs n square roots, each correctly rounded and none of them exact; the matrix entries carry two more square roots apiece. Measured on four graphs, $\|\mathcal{L} D^{1/2}\mathbf{1}\|_\infty$ comes to between 2.2·10⁻¹⁶ and 3.8·10⁻¹⁵ — which is the rounding level and is not zero.

Nothing in these essays fails because of that, and the point of the measurement is not that something breaks. It is that a property the first Laplacian has structurally becomes, in the second, a property that holds to the rounding level — and those are different kinds of statement. An algorithm that deflates a known null vector out of every iterate is exact in one case and leaky in the other, at a rate that is tiny and nonzero, and whether the difference matters is a question about how long the iteration runs rather than a question about the graph.

What the two cost to solve with #

The scaling changes the conditioning as well as the spectrum, and not always in the direction the word “normalised” suggests.

Taking κ⁺ to be the largest eigenvalue over the smallest non-zero one — the condition number of the matrix restricted to the subspace anything is actually solved on:

graph          κ⁺(L)    κ⁺(𝓛)    λmax(L)   λmax(𝓛)
star 30        30.0      2.00      30.00     2.000
preferential   31.9      9.14      18.69     1.797
grid 6×7       38.0     31.8        7.53     2.000
barbell 10     70.0     64.0       11.83     1.192
path 30       364       341         3.99     2.000
hypercube 5     5.0      5.00      10.00     2.000

The normalised matrix is never worse conditioned here and is sometimes far better: on the star it is fifteen times better, because the whole of the combinatorial matrix’s condition number is the ratio between the hub’s degree and a leaf’s, and the scaling removes exactly that. On the regular graph the two are identical, as they must be. On the path — the worst-conditioned graph in the table by an order of magnitude — the improvement is seven per cent, because a path is nearly regular and its conditioning comes from its length rather than from its degrees.

So the scaling is doing what a diagonal equilibration does anywhere on this site: it removes the part of the conditioning that is about the units and leaves the part that is about the problem. On a graph whose degrees are all similar there is nothing to remove. The scaling essays make the general version of that argument, and the graph case is the cleanest instance the site has, because here the “units” are a degree and are therefore known exactly rather than guessed at.

The upper bound of 2 is the other half of it, and it is not an empirical observation: every normalised Laplacian on every graph has its spectrum inside [0, 2]. So κ⁺(𝓛) is always at most 2/λ₂(𝓛), and the entire conditioning of the normalised object is carried by one number — the same number Cheeger’s inequality is about. That does not happen for the combinatorial one, whose largest eigenvalue is somewhere between the maximum degree and twice it and therefore grows with the graph.

Which to use #

The honest summary is short, and it is a modelling question rather than a numerical one.

If the vertices are the units and they should be balanced by count, the combinatorial Laplacian is the right object. Load balancing across processors, partitioning a mesh so each piece has the same number of elements, any application where a vertex is a thing that costs the same as any other vertex.

If the edges are the units and the question is about flow, the normalised one is right. Random walks, clustering where a high-degree vertex is genuinely more important, anything where Cheeger’s inequality is going to be quoted.

And if the graph is regular the question does not arise, which is why so much of the literature can be read without noticing that there was one.

What is not defensible is computing one and quoting a result about the other, and the reason that happens is that the two objects have the same name, the same picture, and second eigenvalues that look interchangeable until somebody measures both on the same graph.