Motivation
A cluster can follow a curved shape that no single centroid represents well. A graph offers a different description: nearby observations are joined by strong edges, and a useful partition should cut relatively little edge weight. The graph does not remove modeling choices. It moves those choices into the meaning of distance, the neighborhood rule and the scale at which similarity is measured.
Minimizing the total weight cut by a partition can isolate a single weakly connected observation. Normalized cut addresses this tendency by dividing each outgoing cut by its cluster's total weighted degree. The resulting discrete problem remains difficult. Spectral clustering replaces indicator vectors by real coordinates, solves the relaxed problem exactly with eigenvectors, and then converts the coordinates back to labels. Each of these steps answers a different mathematical question.
This unit develops the multiway version, including the graph checks needed before matrix normalization is meaningful. The main lesson is that a complete algorithm needs both a spectral calculation and an explicit rounding rule. Proving the former does not silently prove optimality of the latter.
Definitions
Definition 5.1.1
(Affinity, degree, volume and normalized cut)
Let be symmetric with and . Define , and . For disjoint vertex sets , put , and . A partition into nonempty sets with positive volumes has objective
For two groups the edge weight between them occurs in both summands with different denominators. This is intentional. Volume counts incident weights, including internal edges twice because each has two endpoints; it is not the number of vertices. The objective therefore balances graph volume rather than forcing equally many observations into each cluster.
When every , define the symmetric normalized Laplacian and random-walk matrix by
The normalized random-walk Laplacian is . It is similar to , but its right eigenvectors are times the symmetric eigenvectors. Orthogonality for those vectors uses the inner product, not the ordinary Euclidean one. Distinguishing the matrices prevents a common normalization error.
There is a probabilistic meaning to the volume denominator. The random walk moves from vertex to vertex with probability . Its degree-proportional distribution is stationary because symmetry makes the incoming probability at a vertex equal its degree divided by total volume. Condition that distribution on a set . The probability that the next step exits is exactly its outgoing cut divided by its volume. Normalized cut sums these conditional escape probabilities across groups. This interpretation does not require aperiodicity; convergence of arbitrary initial distributions to stationarity would require further assumptions.
Definition 5.1.2
(Graph construction is part of the model)
One possible affinity is for , with fixed . A sparse alternative retains edges within a radius or between nearest neighbors. A directed nearest-neighbor relation must be symmetrized: an edge can be retained when either direction exists, or only when both do. These choices define different graphs and can give different partitions.
Coordinates measured in incompatible units should be scaled according to a declared metric before distances are computed. A Gaussian graph with a very small bandwidth can become numerically indistinguishable from a disconnected graph; a very large bandwidth makes almost all similarities equal. A sparse mutual-neighbor graph can create isolated observations. No eigensolver can determine whether these effects reflect meaningful structure or a poor similarity model.
Theorem/Proposition
Theorem 5.1.3
(Normalized cut is a constrained trace)
Suppose all degrees are positive. For a partition define if , and zero otherwise. Then and
With , this is under , together with the special discrete indicator structure of .
Theorem 5.1.4
(The multiway spectral relaxation)
Suppose every degree is positive and . Let be the eigenvalues of . Among all real matrices satisfying ,
An orthonormal basis of a bottom- eigenspace attains the minimum. Consequently the eigenvalue sum is a lower bound for every discrete normalized cut. If the graph has exactly connected components and no isolated vertices, row normalization of any orthonormal nullspace basis maps vertices in each component to one common unit vector, with different components mapped to orthogonal vectors.
The last assertion is an exact ideal-case result. It does not say that every graph with a small eigenvalue has a unique meaningful partition, or that an arbitrary perturbation preserves all labels. When the th and th eigenvalues are close, even the selected subspace can be sensitive. A label assignment can be unstable for additional reasons, such as nearly tied distances in the final clustering step.
Proof sketch or proof idea
Proof
(From edge energies to a trace objective)
Symmetry gives . Taking leaves only crossing edges, giving . Distinct indicator columns have disjoint supports, so . Summing their normalized quadratic forms proves the trace identity. Substitution proves the normalized version. In particular, the trace relaxation discards the indicator restriction; it does not derive labels directly.
Diagonalize and write . Then . Let be the squared norm of row of . Because is an orthogonal projector, , and . Therefore
Indeed, the two nonnegative masses and are equal. Bounding the first group's eigenvalues below by and the second group's above by proves the inequality. Choosing the first eigenvectors realizes equality.
Proof
(Why row normalization recovers disconnected components)
The edge-energy identity implies that the kernel of consists of vectors constant on each connected component. Hence a convenient orthonormal basis for has columns . With exactly components, any other orthonormal basis has form for an orthogonal matrix . For , row is the positive scalar times row of . Dividing by its norm removes that scalar. All vertices in a component therefore become identical, and rows from different components have inner product zero. Their mutual squared distance is two, so the ideal groups are separated.
Proof X-ray
Two relaxations should not be confused
Replacing indicator matrices by all orthonormal matrices gives an exact eigenvalue problem and a lower bound. Renormalizing rows and applying k-means is an additional rounding procedure. The rounded matrix generally fails to be an orthonormal minimizer of the same trace problem. A guarantee for a particular rounding rule requires its own hypotheses and proof; the Rayleigh argument alone supplies none.
A usable algorithm begins by constructing and inspecting the symmetric graph. Separate isolated vertices because their volumes are zero and is undefined there. Assigning each isolate a singleton label, marking it unassigned, or rebuilding the graph are explicit modeling policies. Adding a tiny number to every degree changes the operator and must not be described as exact normalization of the original graph.
On the remaining positive-degree graph, count connected components . If , several disconnected components must be merged, and the graph contains no edges supporting a preferred merge. Record that ambiguity or supply additional information. For the following algorithm take . Compute the bottom orthonormal eigenvectors of , including its complete nullspace, and place them in columns of . The squared norm of row restricted to the complete nullspace columns equals for its component , the corresponding diagonal entry of the nullspace projector. Hence the full row is nonzero. Normalize each row to obtain . Run k-means on the rows of using a stated initialization and restart policy, then assign the original vertices the resulting labels. Evaluate the original graph cut and inspect sensitivity to the graph and restarts. This returns labels; it does not certify the global discrete optimum.
Worked examples
Worked example 5.1.5
(Two components with very different edge weights)
Let vertices one and two have one edge of weight one, and vertices three and four have one edge of weight one hundred, with no other edges. Degrees are . Normalized adjacency has two identical blocks . An orthonormal kernel basis of has rows for the first component and for the second. Row normalization gives and , recovering the two components despite the large difference in volume. Arbitrary rotation of the two columns preserves all pairwise distances and the same clustering.
Worked example 5.1.6
(A three-vertex path and a genuine relaxation gap)
For the unit-weight path , degrees are and normalized eigenvalues are . Orthonormal eigenvectors for zero and one are and . The relaxed two-group minimum is one. The partition has cut one and volumes one and three, hence normalized cut . The mirrored partition has the same value; isolating the center gives two. Thus the relaxed optimum is strictly lower than every discrete optimum. After row normalization the embedding is , , and . Symmetry permits either endpoint to join the center in the rounding step.
Worked example 5.1.7
(An isolate is a missing definition, not a tiny cluster volume)
Add a fifth isolated vertex to the two-edge graph. Its degree is exactly zero. The expression is , which is undefined. We can remove it, cluster the other four into two groups, and report vertex five as unassigned. Alternatively we can declare it a singleton under a separately extended objective. What we cannot do is insert zero into the ratio and claim the original normalized-cut definition assigned its label. A self-loop creates a different graph and still supplies no similarity to the other observations.
Common mistakes
Counterexample mode
Uniformly rescaling similarities changes no normalized cut
Replace every edge by with . Cuts and volumes both multiply by , so every normalized cut is unchanged. Also . The normalized embedding is therefore unchanged up to eigenspace conventions. A claim that simply multiplying all affinities by a large number makes this algorithm discover stronger clusters is false. Changing the Gaussian bandwidth is different: it generally changes relative edge weights, not merely their common scale.
Common mistake
(Top and bottom depend on the chosen matrix)
The bottom eigenvectors of equal the top eigenvectors, ordered by algebraic value, of normalized adjacency. Selecting eigenvectors with the largest absolute eigenvalues is different. A two-vertex component has adjacency eigenvalues one and minus one; the negative eigenvector encodes alternating signs, not another connected component. Record the operator and eigenvalue ordering explicitly.
History of an idea
A multiway embedding with a separate normalization step
Ng, Jordan and Weiss's 2001 primary paper specifies normalized affinity eigenvectors, row normalization and clustering in the resulting coordinates. It treats the simultaneous use of several eigenvectors, rather than only recursive bisection. Its matrix called is normalized adjacency; this page reserves for the normalized Laplacian.
Summary
Normalized cut compares outgoing weight with graph volume. Its indicator trace becomes a solvable spectral problem when discrete restrictions are removed. A complete nullspace basis identifies disconnected components exactly after row normalization. For general graphs, affinity construction, isolates, the requested number of groups and rounding all require explicit decisions; the eigenvalue lower bound remains distinct from the quality of the final labels.
Exercises
Quick check
(For the unit-weight three-vertex path, compute normalized cut for the partition containing both endpoints together and the center separately. Compare it with an endpoint split and the spectral lower bound.)
Use degree volumes, not set sizes.
Solution · Answer
The endpoint set has volume two, as does the center. Both incident edges cross, so its cut is two. The normalized cut is . An endpoint split has value , while the sum of the bottom two eigenvalues is one. The strict sequence separates the relaxed lower bound, the optimal discrete value and a worse discrete partition.
Quick check
(Show directly that a normalized Laplacian has eigenvector with entries square root of degree and eigenvalue zero. Explain why this vector is generally not constant.)
Multiply normalized adjacency by that vector.
Solution · Answer
Let . Then . Hence . Its entries equal , so they are constant only on equal-degree vertices. A unit normalization divides by . In the random-walk coordinates , explaining why the two operators have different-looking trivial eigenvectors.
Quick check
(Replace an orthonormal spectral embedding U by UR for an orthogonal matrix R. Prove that row normalization and all pairwise embedded distances are unchanged up to the same rotation.)
Orthogonal maps preserve Euclidean norms and inner products.
Solution · Answer
For each nonzero row , . Thus its normalized row becomes . Pairwise differences obey . The k-means objective for any partition is likewise preserved because each mean rotates with the data. The coordinate labels can change; the geometric clustering problem does not.
Quick check
(A graph has three positive-degree connected components but two clusters are requested. Why can two bottom eigenvectors produce zero rows? What information is missing for a unique merge?)
Choose two component-supported nullspace vectors.
Solution · Answer
The nullspace is three dimensional. Choose normalized component indicators supported only on the first two components as the two eigenvector columns. Every row in the third component is zero and cannot be normalized. Other choices can avoid zero rows but are equally arbitrary minimizers. All cross-component weights vanish, so the graph provides no preference among possible merges. Additional distances, a domain rule or an explicitly acknowledged arbitrary policy is needed. Treating a numerical eigensolver's basis choice as substantive evidence would be misleading.