The vector that has to be rounded

Asked to cut a graph into two well-connected pieces, the spectral method returns a real vector of length n with entries like −0.3117 and 0.0842. Asked for a partition, a caller wants a set of vertices. Between those two sentences is a step that is not linear algebra, and it is where every guarantee the linear algebra provides has to be re-established or given up.

What the relaxation actually solved #

The problem anybody wants solved is combinatorial. Over all subsets S of the vertices, minimise the conductance

φ(S) = (weight of edges leaving S) ÷ (total degree of the smaller side)

which is NP-hard, and for which the number of candidates is 2ⁿ⁻¹ − 1.

The spectral method solves a different problem. Write the cut as a vector — one value on S, another off it — and the numerator becomes the quadratic form xᵀLx. Then drop the requirement that x take only two values, keeping only that it be orthogonal to the constant vector and of unit length. The minimum of the Rayleigh quotient over that set is λ₂, attained at the second eigenvector.

That is a relaxation in the exact sense: the feasible set has been enlarged, so the minimum can only have gone down, and λ₂ is a lower bound on something related to the combinatorial optimum. What it is not is an answer to the original question, because the vector it returns is almost never one of the two-valued vectors the original question was about.

The rounding step, and why it is a sweep #

The standard repair is the sweep. Sort the vertices by their entry in the eigenvector; consider the n − 1 prefixes of that order; compute the conductance of each; keep the best.

It is a good heuristic for a specific reason. The eigenvector’s ordering carries the information the relaxation found — vertices the graph keeps close have similar entries — while its actual values, which are the part the relaxation invented, are discarded. Only the order survives, and only n − 1 of the 2ⁿ⁻¹ − 1 candidate subsets are ever examined.

The figure above draws both halves at once: the pale dashed curve is the sorted eigenvector, and the solid curve is the conductance of the prefix ending at each position. The minimum of the second is the answer returned, and where it falls is decided by the ordering of the first.

How flat is the minimum #

The first thing to measure is whether the minimum is a minimum or a plateau, because a plateau means the position of the answer is decided by something small.

graph          best φ      at k    cuts within 5% of best
barbell 10     0.010989     10       1 of 19
two blocks 60  0.089820     30       1 of 59
grid 6×7       0.098592     21       3 of 41
path 30        0.034483     15       1 of 29
preferential   0.232143     29       2 of 59

On four of the five, exactly one prefix is within five per cent of the best, and the curve either side of it rises steeply. The grid has three, and they are the three cuts across the middle of a rectangle, which are genuinely almost equally good.

So on graphs with a real bottleneck the sweep’s minimum is sharp, and a small perturbation of the eigenvector does not move it. That is the encouraging half, and it is worth having before the discouraging one.

How far the answer is from the best answer #

The second thing to measure is the gap between what the sweep returns and the actual combinatorial optimum — which can only be done on graphs small enough to enumerate.

Thirteen vertices gives 8,190 non-trivial subsets, which is a fraction of a second. Over forty random graphs at edge probability 0.28, of which thirty came out connected:

suboptimal                13 of 30
median ratio               1.0000
mean ratio                 1.0691
worst ratio                1.4773

Thirteen of thirty times the sweep returns a cut that is not the best one. The median is exactly one — most of the time it finds the optimum — and the worst case returns 0.4545 where the best possible is 0.3077, a factor of 1.48.

Both halves of that are the result. The method is right much more often than a bound would suggest, and when it is wrong it is wrong by tens of per cent rather than by a rounding, because the answer is a different subset rather than a perturbed one.

On the structured families this field builds — the barbell, the two-block graph, the grid, the path — the sweep is supposed to find the exact optimum every time, because those graphs have one obvious cut and the relaxation finds it. That is checkable at several sizes rather than asserted.

The cut lands on the bridge at every size and the conductance falls faster than λ₂. At 10, 16 and 36 vertices the sweep cuts at k = 5, 8 and 18 — exactly half, the bridge, every time — while λ₂ runs 0.2984, 0.2042 and 0.1005 and the conductance runs 0.0476, 0.0175 and 0.00326.

λ₂ falls by three and the conductance by fifteen across the same sweep, which is the Cheeger bracket opening exactly as a bound with a square root in it measures it doing. The rounding step is untroubled by any of that: the eigenvector’s ordering puts the bridge at the halfway point on a graph of ten vertices and on one of thirty-six, and the sweep finds it in both. So the thirteen-of-thirty failures on random graphs are not a size effect — they are what happens when there is no single obvious cut for the ordering to expose, and a family with one exposes it at every size tested. The random graphs at thirteen vertices have no obvious cut, several nearly equally good ones, and that is where the ordering of the eigenvector stops being enough information.

Which is true except on the most symmetric ones #

Those families are drawn at sizes too large to enumerate, so the claim about them was never checked. Building them small enough to enumerate:

Two of twelve miss, both by exactly a factor of one and a half, and the two that miss are exactly the graphs whose second eigenvalue is degenerate. Every graph in the list with a simple λ₂ finds the optimum; neither of the two with a repeated one does.

The reason is that on a degenerate λ₂ there is no such thing as the second eigenvector. The minimiser of the Rayleigh quotient is a whole subspace, the solver returns an arbitrary member of it, and the sweep is a sweep of whatever came back. The 4×4 grid has two directions of equal claim and the four-cube has four — one per coordinate — and the optimal cut is along a coordinate, which an arbitrary rotation of the eigenspace does not order for.

That also explains why the rectangular grids succeed. A 3 × 5 grid has no symmetry exchanging its two axes, so its λ₂ is simple and points along the long one. Make it square and the symmetry appears and the answer stops being defined.

The obvious repair does not work. Sweeping every vector of the eigenbasis the solver returns gives 0.2500 for both of the grid’s and 0.3750 for all four of the cube’s: an eigensolver hands back one rotation of the eigenspace, and every member of that particular basis is equally bad.

Random directions inside the eigenspace do. Two hundred random unit combinations of the λ₂ eigenvectors find the true optimum on 100 of 200 draws for the grid and 61 of 200 for the cube — two or three draws on average, against a symmetry that is otherwise costing half the answer again.

So the rule the structured families actually support is one line longer than the essay’s: check λ₂’s multiplicity, and if it is greater than one, sweep a handful of random directions in the eigenspace rather than the vector that came back. A degenerate second eigenvalue is not a rare pathology on the graphs this field draws — it is what a symmetric graph has.

The cheaper rounding, and what it costs #

There is an even simpler rule than the sweep, and it is the one most people reach for first: split at zero. The second eigenvector is orthogonal to the constant, so it has entries of both signs, and the sign pattern is a partition without any further work.

It is free, and on the structured families it is the same answer:

graph          sweep φ     sign φ    ratio
barbell 10     0.010989   0.010989   1.000
two blocks 60  0.089820   0.089820   1.000
grid 6×7       0.098592   0.098592   1.000
hypercube 5    0.300000   0.300000   1.000
preferential   0.238938   0.268817   1.125

On five of six the sign cut lands exactly on the sweep’s answer, because on a graph with one obvious cut the eigenvector changes sign exactly where the cut is. On the preferential-attachment graph it is twelve per cent worse.

Over the thirty random graphs the difference is larger and more systematic: the sign cut is worse than the sweep on sixteen of thirty, its mean ratio against the true optimum is 1.152 against the sweep’s 1.069, and its worst case is 1.55 against 1.48.

The reason is what the two rules use. The sign cut reads one number from the eigenvector — where it crosses zero — and that number is a property of the values, which are the part of the eigenvector the relaxation invented. The sweep reads only the ordering, which is the part that carries information about the graph, and then chooses among n − 1 candidates by evaluating the objective directly. It costs one sort and one pass, which against the cost of computing the eigenvector is nothing, and it never returns a worse cut than the sign rule because the sign cut is one of the prefixes it considered.

What λ₂ is worth as a number #

It is tempting to report λ₂ as the quality of the partition, and it is not that. It is a lower bound on a relaxed objective, and the two are related through the inequality rather than through equality.

On the barbell, λ₂ of the normalised Laplacian is 0.01864 and the conductance achieved is 0.01099 — the conductance is below λ₂, which is possible and is not a contradiction, because the inequality bounds φ below by λ₂/2 rather than by λ₂. On the two-block graph λ₂ is 0.15383 and φ is 0.08982. On the grid λ₂ is 0.06297 and φ is 0.09859, the other way round.

So λ₂ is neither an upper nor a lower bound on the answer; the bounds are λ₂/2 and √(2λ₂), and the answer moves around inside them. Quoting λ₂ as “the quality of the cut” is quoting a number that happens to be nearby, and how nearby is what the next essay measures.

What λ₂ is good for is a comparison between graphs, or between the same graph at two moments — a falling λ₂ means the graph is becoming easier to cut, and the statement is exact rather than heuristic. It is a property of the object, computed to fourteen digits, and it is the right thing to report as long as it is not labelled as the answer.

The guarantee that survives the rounding #

The reason the sweep is not merely a plausible heuristic is that Cheeger’s inequality is a statement about it rather than about the relaxation.

The upper half, φ ≤ √(2λ₂), is proved by exhibiting a cut, and the cut exhibited is a sweep cut of the normalised eigenvector. So the theorem does not say “a good cut exists”; it says “this algorithm’s output is at most √(2λ₂)”, and the algorithm is the one above.

That is unusual and worth appreciating. Most rounding steps in numerical work are justified after the fact by a measurement. Here the rounding is inside the theorem, and what the theorem costs is a square root — which the next essay measures, and which turns out to be loosest exactly where it is quoted.

One caveat, and the field earns it the hard way: the theorem is about the normalised Laplacian’s eigenvector, swept after dividing each entry by the square root of its degree. Sweeping the combinatorial eigenvector is a different algorithm with no such guarantee, and on the graphs here it sometimes returns a better cut and sometimes a worse one. Two Laplacians of one graph is about the difference between the two objectives; this is what it costs at the last step.

What the rounding has in common with the rest of the site #

A real quantity turned into a discrete verdict by a rule applied afterwards is not a new shape here.

Rank is a decision makes it with a threshold on singular values: the singular values are computed accurately, and how many count as non-zero is a rule applied to them. Deciding that a zero has arrived makes it with a breakdown test. A rank that depends on the thread count makes it with the same threshold and a different summation order, and gets three different integers.

What is different here is where the discreteness comes from. In the rank essays the underlying quantity is genuinely continuous and the integer is imposed on it by a caller who wants one. Here the question was discrete before anybody wrote a matrix down: the caller wants a set of vertices, and the continuous object is the thing that was invented, as a means of getting at it.

That reversal changes what “accuracy” means. An eigenvector computed to fourteen digits rather than seven does not produce a better partition; it produces the same partition, because the sweep only reads the order. Computing the eigenvector more accurately buys nothing at all past the point where the ordering is settled — and the essay after next is about the graphs where the ordering is never settled, however accurate the eigenvector.

More than two pieces #

Almost nothing in practice wants two pieces, and the extension is where the honesty of the method is most easily lost.

Two routes are used. Recursive bisection cuts in two, then cuts each half in two, and so on: it reuses everything above unchanged, and its defect is that a cut made at the first level cannot be undone at the second, so a three-way structure gets a first cut through the middle of one of its parts. Multiple eigenvectors takes the first k non-trivial eigenvectors, treats each vertex as a point in k dimensions, and clusters those points — which is the standard spectral clustering algorithm, and which replaces one rounding step with a different and larger one, since the clustering in k dimensions is itself an NP-hard problem attacked by a heuristic.

Neither inherits Cheeger’s inequality. There are higher-order analogues, and they are weaker in a specific way: the bound involves λₖ and a factor polynomial in k, so it degrades as more pieces are asked for, and at k of any practical size it is not a useful number.

That is worth saying plainly because the two-piece case is unusually well served and the good fortune does not extend. The bisection theorem is tight enough to be worth quoting; nothing about the k-way case is. The measurements in this field therefore stay with two pieces, where a claim can be checked against an enumeration, rather than reporting a clustering nobody can score.

How accurate does the eigenvector have to be #

If the sweep reads only the ordering, then the accuracy the eigenvector needs is whatever settles the ordering, and nothing more. That is a measurable claim rather than a plausible one.

Perturbing the Fiedler vector by a relative ε and re-sweeping, twelve times at each level, and counting how often the partition changes:

graph            10⁻¹⁴   10⁻¹⁰   10⁻⁶   10⁻³   10⁻¹
barbell 10         0       0       0      0      0
two blocks 60      0       0       0      0      0
path 30            0       0       0      0      2
preferential 60    0       0       0      2     12
grid 6×7          10      10      10     10     10

Four of the five are unmoved by a perturbation of ten per cent. An eigensolver stopped at 10⁻⁶ and one stopped at 10⁻¹⁴ return the identical partition on all of them, and the second costs perhaps three times as much. On this evidence a spectral partitioner asking its eigensolver for fourteen digits is buying nothing.

The grid is the exception and it is not a small one: its partition changes on ten runs in twelve at every level tested, including 10⁻¹⁴. Nothing about the perturbation is doing that. A 6 × 7 grid has a symmetry that exchanges its two long halves, its second eigenvector has entries that are equal in exact arithmetic, and the sort therefore has ties in it whose order is decided by whatever the last bits happened to be. Ten of twelve runs return a partition of the same quality — the conductance is 0.098592 every time — and a different set.

That is the situation the essay after next is entirely about, and it is worth noticing here that it arrived while measuring something else: the question “how accurate must the eigenvector be” has no answer on a graph where accuracy is not what decides.

What to compute, and what to report #

Three practical consequences, each of which follows from something measured above.

Report the conductance, not the eigenvalue. λ₂ is a lower bound on a related quantity and is not the quality of the cut returned. The conductance costs one pass over the edge list once the partition is known, and it is the number a caller can act on.

Report where the minimum sat. A sweep whose best prefix is at k = 30 of 59, with the next-best five per cent worse, is a different situation from one whose best twelve prefixes are within a per cent of each other. The first is a partition; the second is a suggestion.

Do not spend accuracy on the eigenvector. Past the point where the ordering is settled, more digits change nothing. An iterative eigensolver stopped at 10⁻⁶ and one stopped at 10⁻¹⁴ return the same partition on every graph in this essay, and the second costs three times as much.