On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector. Twenty-four runs with the edge weights nudged by 10⁻¹² return ten different partitions of a cycle and, on a hypercube, two different qualities of answer.
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.
Fig. 1 Three seven-vertex cliques joined in a triangle. λ₂ and λ₃ agree to 1.7·10⁻¹⁵, and eight runs with
the edge weights nudged at the rounding level return three different partitions.
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.
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.
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.
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 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.
Fig. 2 A hypercube, whose second eigenvalue has multiplicity equal to its dimension.
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.
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.
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.
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.
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:
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 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.
Fig. 3 The same graph with one join raised by a thousandth. The gap is 1.9·10⁻⁴ and every run returns the
same partition.
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, so half the runs return the set and
half return the complement. Downstream code that treats “side A” as meaningful, or that assigns the
two sides to two machines and expects the assignment to be stable across runs, is relying on a sign
that was never determined.
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.
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.
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.
Fig. 4 A skew of one per cent, where the gap is 1.9·10⁻³ and the answer is settled.Fig. 5 Five per cent, where the two eigenvalues are visibly apart on the plot.Fig. 6 Twenty per cent, where nothing about the graph is symmetric any more.Fig. 7 And forty, where the third clique is attached quite differently from the other two.Fig. 8 The cycle, whose every non-zero eigenvalue is double and whose cuts are all equally good.Fig. 9 The grid, whose eigenvector has tied entries and whose sweep therefore has ties in its sort.Fig. 10 A cycle laid out at its own eigenvectors, which recovers the circle because they are the sine modes.Fig. 11 The grid, whose second eigenvector is constant along its short axis.Fig. 12 The extreme case: every non-zero eigenvalue equal, so the whole orthogonal complement is one
eigenspace.Fig. 13 The bracket, which holds for every one of the answers a degenerate graph returns.Fig. 14 An eigenvector with no gap to define it, in the field that measured that first.Fig. 15 How a gap decides an eigenvector, which is the continuous version of this essay.Fig. 16 How far an eigenvalue moves when the matrix does, which sets the scale a gap is measured against.Fig. 17 One matrix with three numerical ranks, which is the same shape with a threshold instead of a plane.Fig. 18 One solve with thirteen different bills, in the field about answers that are not unique.Fig. 19 Twenty-one answers from one program, which is the machine field’s version of this.Fig. 20 A threshold turning a spectrum into an integer.Fig. 21 A cluster of eigenvalues, which is what a symmetry produces exactly rather than approximately.Fig. 22 Orthogonality lost in a Krylov space, which is how a degenerate pair is usually first noticed.Fig. 23 A residual that cannot see the error, which an eigenvector residual here also cannot.Fig. 24 A discrete choice inside a solve, on a graph whose spectral gap is large.Fig. 25 The spectrum whose second and third entries this essay is about the distance between.Fig. 26 An estimate reported as a spread, which is what a degenerate partition should be.Fig. 27 The two errors, neither of which is what goes wrong here.Fig. 28 The precision knob, which does not settle any of the partitions in this essay.Fig. 29 An answer that is known, which a degenerate partition problem does not have one of.