A partition decided in the last digit

Everything in this anchor so far has assumed there is a Fiedler vector. There often is not.

The sweep assumes there is a vector to sort. An eigenvector belonging to a repeated eigenvalue is not determined. What is determined is the subspace, and any unit vector in it is as exact an eigenvector as any other. A graph whose second Laplacian eigenvalue is repeated therefore has no second eigenvector; it has an eigenplane, and the spectral partitioner picks a direction in that plane by a mechanism that has nothing to do with the graph.

That is not a pathology of contrived examples. It is what a symmetry does, and graphs with symmetries are the ordinary case rather than the exception: a cycle, a hypercube, a grid, a mesh with a repeated motif, any structure assembled from identical parts.

Why a symmetry forces a repeated eigenvalue #

If a permutation of the vertices maps the graph to itself, the corresponding permutation matrix commutes with the Laplacian. Commuting matrices share eigenspaces, so each Laplacian eigenspace is invariant under the whole automorphism group — and a group with a representation of dimension greater than one forces an eigenspace of that dimension.

The matrices involved are the ones the second essay in this field distinguishes, and the degeneracy is a property of both. Concretely: a cycle of n has a rotation group, whose two-dimensional representations are the sine and cosine modes at each frequency, so every non-zero eigenvalue of a cycle is double. A hypercube of dimension d has an automorphism group that permutes coordinates, so its eigenvalue 2 has multiplicity d. Three identical cliques joined in a triangle have a three-fold rotation, and λ₂ is double.

The last of those is worth contrasting with the case that does not work. Three identical cliques joined in a chain also look symmetric — the two ends are exchangeable — but the group has order two and has no two-dimensional representation, so λ₂ and λ₃ come out at 0.1125 and 0.3467 and are comfortably apart. Degeneracy is a property of the group rather than of how symmetric a picture looks, and guessing from the picture gets it wrong.

What that does to the answer #

The measurement is straightforward: nudge every edge weight by a relative 10⁻¹², which is four orders above the unit roundoff and far below anything anybody would call a difference in the data, recompute the Fiedler vector, sweep, and count how many distinct partitions come back over twenty-four runs.

graph              λ₂           λ₃           gap        partitions   conductances found
cycle 24           0.068148     0.068148    4.0·10⁻¹⁶       10        0.083333
triangle cliques   0.346688     0.346688    1.7·10⁻¹⁵        4        0.045455
hypercube 4        2.000000     2.000000    1.8·10⁻¹⁵        8        0.250000, 0.375000
grid 6×7           0.198062     0.267949    7.0·10⁻²         4        0.098592, 0.100000
barbell 10         0.169048    10.000000    9.8              1        0.010989
two blocks 60      2.553807     9.551710    7.0              1        0.089820

The two rows at the bottom are the reassuring case: a graph with a real gap returns one partition every time, and the perturbation does nothing. The four above them do not.

The cycle returns ten different partitions out of twenty-four runs. That is exactly right and should not be alarming on its own: a cycle has no distinguished place to cut, every cut across two antipodal edges is as good as every other, and the ten answers all have conductance 0.083333. The method is reporting the truth, which is that there are twelve equally good answers and it has no grounds to prefer one.

The case where the quality differs too #

The hypercube’s row is the one that is not benign.

Eight distinct partitions came back, and their conductances are 0.25 or 0.375 — a difference of fifty per cent in the quality of the answer, decided by a perturbation of 10⁻¹².

The natural cut of a four-dimensional hypercube is along one coordinate: eight edges cross, each half has volume 32, and the conductance is 0.25. That cut is one of the four directions in the eigenspace of λ₂ = 2. The other directions in that eigenspace are combinations of coordinates, and sweeping one of those produces a set that is not a coordinate half-space and cuts twelve edges instead of eight.

So on this graph the degeneracy is not “several equally good answers”; it is “several answers, some of which are half again as bad”, and which one a run returns is decided by where the eigensolver’s starting vector happened to land inside a four-dimensional space. Nothing in the output distinguishes the two cases. Both are exact eigenvectors, both sweeps are correct sweeps, and both conductances are inside Cheeger’s bracket.

The second mechanism, which is not degeneracy at all #

The grid’s row is the strange one. Its λ₂ and λ₃ are 0.198 and 0.268 — a gap of seven per cent, which is enormous by the standards of this table — and it still returns four different partitions.

The eigenvalue is simple, so the eigenvector is determined up to sign, and the perturbation moves it by about 10⁻¹². What is not determined is the sort order, because a 6 × 7 grid’s second eigenvector is constant along the short axis: six vertices share each value, exactly, in exact arithmetic. The sweep sorts by that vector, and ties in a sort are broken by whatever the last bits were.

That is a genuinely different failure. The eigenvalue problem is well posed, the eigenvector is accurate to fourteen digits, and the rounding step downstream of it is the thing that is underdetermined. Two of the four partitions returned have conductance 0.098592 and two have 0.100000, so here too the quality is not the same across the answers.

It is worth naming the distinction because a diagnostic that checks for repeated eigenvalues will miss it entirely. A tie in the spectrum is visible in the eigenvalues. A tie in the entries of an eigenvector is visible nowhere except in the sort, and a symmetric graph will usually have both.

Nothing is wrong with the arithmetic #

It is worth closing off the reading that this is an accuracy problem, because it is the reading a numerical analyst reaches for first and it is wrong in every case above.

Each of the eigenvectors involved is exact to the level the eigensolver delivers. Feeding one back through the matrix gives a residual ‖Lx − λx‖ of about 10⁻¹⁴ relative to ‖L‖, which is what a Jacobi sweep on a matrix of that norm produces and is as good as binary64 allows. The eigenvalues agree with their closed forms — the cycle’s to 2.6·10⁻¹⁴, the hypercube’s exactly, since 2 is representable — so nothing about the spectrum is being computed badly.

The perturbation is not doing damage either. Nudging the edge weights by a relative 10⁻¹² changes λ₂ by at most 2·10⁻¹² by Weyl’s inequality, which is nothing. It changes the direction the solver picks inside the eigenplane by an amount of order one, because that direction is not a continuous function of the matrix when the eigenvalue is repeated — and that discontinuity is a property of the eigenvalue problem, not of the solver.

So the correct summary is that a well-conditioned computation has been performed on a problem whose answer is not unique, and the non-uniqueness has been resolved by whatever was smallest. Improving the arithmetic improves nothing. Running in higher precision would move the crossover in the skew table by however many digits were added and would leave the exactly symmetric case exactly as it is, because the eigenvalues there are equal in every precision.

What this is, in the site’s existing vocabulary #

The first mechanism is the one the plane survives what its vectors do not is about, arriving here with a discrete consequence. There, a cluster of eigenvalues means the individual eigenvectors are meaningless while the invariant subspace they span is computed to full accuracy — and the repair is to report the subspace rather than the vectors. That repair is available here as a diagnosis and not as a fix: the eigenplane is well conditioned and is exactly what the graph determines, and a caller who wanted a partition cannot be handed a plane.

The second mechanism is closer to a rank that depends on the thread count — a comparison of two nearly equal floating-point numbers deciding a discrete outcome, with no last digits for the disagreement to hide in. There the comparison was against a threshold; here it is between two entries of one vector.

And both are instances of the machine field’s general statement, which is that a verdict has no continuum for an error to be small in. What is new here is that the underdetermination is a property of the object rather than of the implementation. A hypercube genuinely does not have one best bisection direction. No amount of care in the arithmetic changes that, and an implementation that returned the same answer every time would be concealing it.

Why this does not show up in the literature #

The effect is easy to reproduce and hard to find written down, and the reason is worth a paragraph because it explains what kind of graphs a method gets tested on.

Almost every empirical study of spectral partitioning runs on graphs from applications: finite element meshes, road networks, social graphs, matrices from sparse-matrix collections. Every one of those has irregular local structure, so its automorphism group is trivial, so no eigenvalue is repeated for a structural reason and the whole phenomenon is absent. A study of a hundred such graphs would report perfect run-to-run agreement and would be right about the graphs it looked at.

The graphs that do have symmetry are the ones used for illustration — the cycle, the grid, the hypercube, the ring of cliques — and those are precisely the ones nobody runs a determinism study on, because they are the pictures rather than the data.

That is a familiar shape on this site. The vector that hides it makes the same observation about parallel summation: the effect is invisible on positive data, positive data is what a synthetic benchmark generates, and so a real phenomenon acquired a reputation for being a curiosity. The mechanism here is the same one — the demonstration set and the difficult set are disjoint — and the consequence is that a partitioner which has never been observed to disagree with itself may simply never have been shown a symmetric graph.

How much of a gap is enough #

The perturbation and the gap compete, and the crossover is measurable. Skewing one of the three joins in the triangle of cliques opens the gap linearly:

skew        λ₃ − λ₂        distinct partitions
0           1.7·10⁻¹⁵            3
0.001       1.9·10⁻⁴             1
0.01        1.9·10⁻³             1
0.05        9.2·10⁻³             1

A skew of one part in a thousand — a gap of 1.9·10⁻⁴, which is twelve orders above the perturbation — is already enough to settle the answer completely. There is no delicate regime in between: either the gap dominates the perturbation and the partition is a function of the graph, or it does not and the partition is a function of the afternoon.

That table has three empty decades in it, and where the transition actually sits is worth knowing, because the advice below is a threshold. Thirty-two runs at each skew:

The answer settles at a gap of 5.6·10⁻¹³, which is about half the perturbation — nine decades below the skew the four-row table can resolve. The “no delicate regime” reading is confirmed: three distinct partitions at a gap of 1.9·10⁻¹³ and one at 5.6·10⁻¹³, so the transition takes about half a decade.

Which sharpens the criterion rather than changing it. The gap has to beat the perturbation, and beating it by a factor of a few is enough. Twelve orders of margin is twelve orders of margin — the useful number to check against is not the quoted 1.9·10⁻⁴ but the uncertainty in the graph itself.

That is the practically useful form of the result. The number to check is not whether λ₂ and λ₃ are “close” in some absolute sense; it is whether λ₃ − λ₂ is large compared with the uncertainty in the graph — which for a graph built from measurements is the measurement error, and for a graph built exactly is the eigensolver’s own accuracy, around 10⁻¹⁴ times the norm.

And raising the skew fifty times further changes nothing that can be seen. That is worth drawing rather than asserting, because it is what “no delicate regime” looks like from the outside: the settled picture at a thousandth and the settled picture at a twentieth are the same picture, and everything interesting happened nine decades below both of them.

The consequence for anybody choosing a tolerance is that the choice is not delicate either. There is no value of the gap at which the answer is partly settled, so a threshold does not have to be placed carefully — it has to be placed above the perturbation, and anywhere above it will do.

A note on which vertex ends up where #

One consequence is easy to overlook and bites in practice: on a degenerate graph the labels of the two sides are arbitrary as well as the sides themselves.

A partition is a set and its complement, and nothing in the eigenvector says which is which — the eigenvector’s sign is undetermined even when the eigenvector is. Downstream code that treats “side A” as meaningful, or that assigns the two sides to two machines and expects the assignment to be stable, is relying on a sign that was never determined.

The natural next sentence — so half the runs return the set and half return the complement — is where the claim needs care, and the measurement says it is not that. The Fiedler vector’s sign comes back identical in thirty-two runs of thirty-two at every skew above, and fiedler, laplacianEig and the normalised variant all agree with each other on the same graph. The indeterminacy is mathematical, and any one eigensolver resolves it deterministically.

So the irreproducibility it causes is between codes, not between runs of one, and that changes what a test can catch: a suite that runs the same routine twice will never see it, and the disagreement surfaces the first time somebody’s pipeline is rebuilt against a different library. The convention is still the right fix, and it is worth applying for a reason the sentence above does not give — not because the sign wanders, but because it does not wander and there is no guarantee it is the same fixed sign anywhere else.

This is separate from everything else in the essay and it applies to every graph, symmetric or not. The cheap repair is a convention that is about the problem — the side containing the lowest-numbered vertex, or the larger side, or the side containing a named vertex — applied after the sweep. It costs one comparison and it removes an entire class of irreproducibility that has nothing to do with eigenvalues.

What an implementation should do about it #

Three things, in order of how much they cost.

Report the gap. λ₃ − λ₂ is already computed by any solver that produced λ₂, or is one more iteration away. A partition returned without it is a partition whose determinacy the caller cannot check, and the check is a single comparison.

Report the conductance rather than trusting the partition, which is also the number Cheeger’s bracket is about. The hypercube’s eight answers differ by fifty per cent in quality and the difference is visible in one pass over the edge list. A caller given the conductance can tell a 0.25 answer from a 0.375 one; a caller given only the vertex sets cannot.

Do not chase determinism, which the machine field’s reproducible summation already prices. It is tempting, on discovering that runs disagree, to fix the eigensolver’s starting vector and declare the problem solved. That produces the same answer every time and it is the wrong answer as often as before — it has replaced an honest report of an underdetermined problem with a reproducible arbitrary choice. The machine field makes the general version of this argument about reproducible summation: agreement and accuracy are different properties, and buying the first does not buy the second.

If a single partition is genuinely needed, the honest way to get one is to break the tie with something that is about the problem — a vertex ordering with a meaning, a secondary objective, a preference for balance — rather than with something that is about the arithmetic.

What is worth carrying out of this #

A symmetric graph has an underdetermined spectral partition, and symmetry is common. Cycles, hypercubes, meshes and anything assembled from repeated parts all have repeated Laplacian eigenvalues, and every one of them has more than one equally exact answer.

Sometimes the answers are equally good and sometimes they are not. The cycle’s ten partitions all have conductance 0.083333. The hypercube’s eight have 0.25 or 0.375. Nothing in the eigenvalue problem distinguishes the two situations, and only measuring the conductance does.

A repeated eigenvalue is not the only way to get there. The grid has a comfortable spectral gap and still returns four partitions, because its eigenvector has exactly tied entries and the sweep sorts them. A check for degenerate eigenvalues will not see it.

And the fix is a measurement, not a determinism. Print the gap, print the conductance, and let the caller see that the problem has several answers — which it does.