A bound with a square root in it

A relaxation gives a lower bound. That is all a relaxation ever gives, and on its own it is not much: knowing that the best cut is at least this good does not tell anybody whether the cut in hand is any good.

What makes spectral partitioning a method rather than a heuristic is that the bound goes both ways. For the normalised Laplacian’s second eigenvalue and the graph’s conductance φ,

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

and the right-hand half is proved by exhibiting a cut — specifically, by exhibiting a sweep cut of the eigenvector, which is the thing an implementation actually returns. So the theorem covers the algorithm and not merely the idea behind it.

The two halves are not equally good, and the difference between them is the subject of this essay.

What the census measures #

Nine families, each with about forty vertices, each swept and each measured:

graph          λ₂(𝓛)      λ₂/2       φ         √(2λ₂)     φ ÷ lower   upper ÷ φ
complete 20    1.05263    0.52632   0.52632    1.45095      1.00        2.76
two blocks     0.15383    0.07691   0.08982    0.55467      1.17        6.18
barbell 8      0.02882    0.01441   0.01754    0.24010      1.22        13.69
hypercube 4    0.50000    0.25000   0.37500    1.00000      1.50        2.67
star 20        1.00000    0.50000   1.00000    1.41421      2.00        1.41
preferential   0.19664    0.09832   0.23894    0.62712      2.43        2.62
grid           0.06298    0.03149   0.09859    0.35490      3.13        3.60
cycle 40       0.01231    0.00616   0.05000    0.15692      8.12        3.14
path 40        0.00324    0.00162   0.02564    0.08053     15.81        3.14

The two rightmost columns are the whole result: how much slack there is at the bottom of the bracket, and how much at the top. Every λ₂ in the table is the normalised Laplacian’s, for the reason the second essay in this field gives.

The lower bound is attained #

The complete graph’s row reads 1.00. Not approximately — the conductance of the best cut of K₂₀ is 0.52632 and half its normalised λ₂ is 0.52632, to every digit the eigensolver produces.

That is not a coincidence of this size. For the complete graph on n vertices the normalised λ₂ is n/(n − 1), so λ₂/2 is n/(2n − 2); and the best cut is the balanced one, with (n/2)² edges crossing and a volume of (n/2)(n − 1) on each side, giving n/(2n − 2) as well. The bound is an equality on this family at every n.

So the left half is not a weak statement dressed up as a theorem. There is a graph on which it cannot be improved by any constant, and that graph is one of the most ordinary objects in the subject. A tighter version of the lower bound does not exist.

The upper bound is loose where it is used #

The barbell’s row reads 13.69. Its conductance is 0.01754 and the bound says only that it is at most 0.24010.

The barbell is two cliques joined by a single edge. It is the graph a reader imagines when told that a graph has a bottleneck, and it is the case spectral partitioning is recommended for. On exactly that case, the guarantee is out by a factor of fourteen.

Nor is that an accident of the barbell. The pattern down the column is systematic: the graphs where the upper bound is loosest — barbell at 13.69, two blocks at 6.18 — are the graphs with a small conductance, and the graphs where it is tightest — star at 1.41, hypercube at 2.67 — are the graphs with no meaningful cut at all. The square root is the reason. When λ₂ is small, √(2λ₂) is much larger than λ₂ relative to it, so the bracket is wide precisely when the numbers are small, which is precisely when a partition is worth looking for.

This is the shape of a bound that is never attained, arriving in a different field. There, the growth factor’s bound of 2ⁿ⁻¹ is correct, attained on one constructed matrix and unreachable on any matrix anybody has. Here the upper bound is attained too — in the limit, on a specific family — and the family is not the one anyone cares about.

Where the upper bound is tight, and it is π #

The cycle and the path both report 3.14, and that is not a rounded coincidence.

For a cycle of n vertices, the normalised second eigenvalue is 1 − cos(2π/n), which for large n is 2π²/n². The best cut removes two edges from a graph whose halves have volume n each, so the conductance is 2/n. Then

√(2λ₂) ÷ φ  →  (2π/n) ÷ (2/n)  =  π

exactly, in the limit. At n = 40 the measured ratio is 3.14 and the limit is 3.14159…, so the convergence is fast.

That is the sharpest available statement about how loose the square root is: on the family where the answer is known in closed form, the bound overstates the conductance by π and by nothing more. A constant of π is not the same kind of gap as a constant of fourteen, and the difference is that a cycle’s cut is unique — there is one way to cut it well, and every eigenvector of the relaxation points at it — while a barbell has a cut so much better than every alternative that the relaxation’s smooth answer is a poor description of it.

Where the square root comes from #

The constant is not an artefact of a lazy proof, and it is worth seeing why, because it explains which graphs the bound is loose on.

The upper half is proved by taking the eigenvector, sweeping it, and bounding the best prefix’s conductance. The step that costs the square root is a Cauchy–Schwarz inequality. Writing the eigenvector’s entries as x and the sweep cuts as level sets, one has to compare a sum of |xᵢ² − xⱼ²| over edges — which is what the level-set decomposition produces — with the sum of (xᵢ − xⱼ)², which is what λ₂ bounds. The bridge between them is

|xᵢ² − xⱼ²|  =  |xᵢ − xⱼ| · |xᵢ + xⱼ|

and then Cauchy–Schwarz over the edges, which turns a sum of products into the product of two square roots. One of those roots is √λ₂ and the other is a norm that is bounded by a constant. The square root is that step and there is no way round it in this argument.

What it means in practice is that the bound is tight when the eigenvector’s entries are spread out smoothly and loose when they are concentrated. On a cycle the entries are a sine wave and the Cauchy–Schwarz step is nearly an equality — hence the constant of π rather than of fourteen. On a barbell the entries are two nearly-constant plateaux joined by a step, |xᵢ + xⱼ| is far from proportional to |xᵢ − xⱼ| across the bridge, and the inequality is loose by an order.

So the loose cases are exactly the ones where the eigenvector is nearly two-valued — which is to say, exactly the ones where the relaxation was hardly a relaxation at all and the cut is obvious. The bound is worst where the problem is easiest, which is an unusual and slightly comic way for a guarantee to behave, and it is a direct consequence of the one line above.

Improving it is a research programme, not an exercise #

The gap between λ₂/2 and √(2λ₂) has been attacked from several directions and the results are worth knowing, mostly for what they do not deliver.

Higher eigenvalues sharpen it. There is an improved inequality of the form φ ≲ λ₂/√(λ_k), for any k, which is strictly better than √(2λ₂) whenever λ_k is not small. On a graph with one bottleneck λ₃ is already substantial, so this is a real improvement on the barbell — but it costs k eigenvalues rather than one, and the constant hidden in the ≲ is not small.

Many pieces cost more. The k-way analogues bound the k-way expansion by a polynomial in k times √(λ_k), and at any k worth using the polynomial dominates. The two-piece case is the well-served one and the good fortune does not extend, which is why the measurements in this field stay with two.

The square root cannot be removed. There are graphs — the cycle above is essentially one — where φ really is of order √λ₂ and not of order λ₂. So no proof technique can do better in general; the looseness on the barbell is a looseness of the worst case, not of the argument.

That last point is the one that makes the measurement worth taking. A bound that is tight in the worst case and loose by fourteen on the case in hand is a bound whose value is entirely in the certificate and not at all in the estimate, and telling those two uses apart is the whole of the section below.

Which λ₂, and what happens if it is the wrong one #

Everything above is about the normalised Laplacian’s second eigenvalue. Substituting the combinatorial one does not weaken the result; it makes it false.

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

On the complete graph the lower bound claims the conductance is at least ten. Every cut of a complete graph has conductance about a half. The claim is not slightly wrong.

The reason is the one the previous anchor is about: the two matrices are related by a congruence rather than a similarity, their eigenvalues are not proportional to any degree, and a theorem about one is not a theorem about the other. The two objects share a name and a picture, and a bound quoted for the wrong one fails by an order of magnitude on a graph everybody has met.

What the bracket is actually for #

Given how wide it is, it is worth asking what a bracket that spans a factor of fourteen is good for. Two things, and neither of them is estimating φ.

It certifies that no better cut exists. The lower bound is the useful half: if λ₂/2 is 0.0769 then no subset of the vertices, of any size, has conductance below that. Nothing else in this field provides such a statement, and it costs one eigenvalue rather than an enumeration of 2ⁿ⁻¹ subsets. When the sweep returns 0.0898 against a lower bound of 0.0769, the answer in hand is within 17% of the best there is, and that is a certificate rather than a hope.

It certifies that the method has not failed — including on the graphs where the partition itself is undetermined, since the bracket holds for every answer such a graph returns. The upper bound guarantees that the sweep will find something below √(2λ₂), so a run returning a conductance far above that has a bug rather than a hard graph. It is a weak test and it is a test, and this site’s habit is that a test that could fail is worth more than a description that could not.

What the bracket is not for is reporting. The number to report is the conductance, which is a measured property of the partition returned and costs one pass over the edge list.

The ratio between the two halves #

The bracket’s width in ratio is √(2λ₂) ÷ (λ₂/2) = 2√2 ÷ √λ₂, which grows without bound as λ₂ falls. At λ₂ = 1 it is 2.83; at λ₂ = 0.01 it is 28.3; at λ₂ = 10⁻⁴ it is 283.

So the certificate gets weaker exactly as the graph gets more interesting. On a graph that barely holds together — a network with a genuine bottleneck, which is what somebody partitioning a graph is usually looking at — the two halves of the guarantee are two orders of magnitude apart, and the measurement is the only thing that says where in that range the answer sits.

The measured ratios in the census bear this out from the other side. The graphs with λ₂ near one (complete, star, hypercube) have both halves tight, at 1.00–2.00 below and 1.41–2.76 above. The graphs with λ₂ near 0.01 (barbell, cycle, path) have one half or the other loose by an order.

Both halves are stable, which the answer is not #

One more property is worth measuring, because it separates this bracket from the partition it brackets.

λ₂ is an eigenvalue of a symmetric matrix built from the graph by a rule with exactly zero row sums, so it moves by at most the norm of a perturbation — Weyl’s inequality, which is the site’s sharpest statement about eigenvalue stability and applies here without qualification. Change one edge weight by δ and every eigenvalue moves by at most 2δ. Both ends of the bracket are continuous functions of λ₂, so both ends move by a comparable amount.

The conductance is not like that. It is a minimum over subsets, so it is continuous in the edge weights — but the subset achieving it is not, and a perturbation that moves φ by 10⁻¹⁶ can move the partition to a completely different set of vertices. The measurement in the previous essay found exactly that on a grid: ten runs in twelve return a different partition at a perturbation of 10⁻¹⁴, and all of them return the same conductance of 0.098592.

So the bracket is a stable statement about an unstable object. Everything the theorem asserts — that no cut is better than λ₂/2, that some cut is at least as good as √(2λ₂) — survives a perturbation of the graph, and the identity of the cut does not. That is worth stating because it tells a caller which of the two things they were handed is worth carrying forward: the number is robust and the set of vertices may not be.

What is genuinely surprising here #

Two things, and both are the opposite of what the shape of the theorem suggests.

The lower bound, which sounds like the weak half, is exact on an ordinary graph. A relaxation’s bound being attained is unusual; a relaxation’s bound being attained on the complete graph, at every size, is the kind of thing that suggests the relaxation is not merely a bound but the right object.

The upper bound, which is the half that makes the method a method, is loose by a factor that grows as the problem becomes the one the method is for. It is still enough to make the method sound — it rules out arbitrarily bad answers, and that is what a guarantee is — but it is not enough to predict what the answer will be, and quoting it as though it were is the mistake this essay exists to prevent.

Both of those are measurements over nine graphs rather than statements about a theorem, and both would have been invisible in a treatment that stated the inequality and moved on. The habit that produces them is the one this site runs on: compare a bound to the thing it bounds, on more than one object, and print the ratio.

At other settings #