Spectral Clustering and Graph Cuts

Spectral methods gain flexibility by moving the structural assumption into the affinity graph. Each of the three approaches below buys that flexibility at a different price. For the third, the price has been measured.

Modularity-based community detection has a proven blind spot. It can hide well-defined substructure inside a module whose internal links number about sqrt(2L) or fewer, where L is the network's total number of links. Fortunato and Barthelemy proved that in PNAS in 2007, and their abstract does not hedge: “We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined.”

A different research group revisited the same limit in 2010 and added a second problem to the first. The modularity function typically admits an exponential number of distinct high-scoring solutions. So a high score does not identify a partition.

Zachary's karate club is not a demonstration built to be separable. It is a real friendship network of 34 nodes — 77 or 78 edges, depending on an ambiguous typo in the 1977 study — whose members split into two factions. Zachary published it in 1977, and the Netzschleuder network catalogue has carried it, with its faction metadata, ever since. The ground truth is not a label the analyst assigned. It is the split that actually happened.

In June 2002 Girvan and Newman ran their community-detection algorithm on that graph and compared the top-level split it produced against the real division. The result is a countable error: “Only one node, node 3, is classified incorrectly.” One node out of 34.

That number is the whole point of the example, and it exists only because a real answer was there to check against. A graph-space method transformed the affinity structure it was given, and someone counted how far the result sat from the truth. Where no such answer exists — which is most of the time — the method still produces a clean-looking partition. Nothing in the output tells you whether it was right in 33 places out of 34 or wrong everywhere.

Spectral clustering converts local affinity into a new coordinate system before applying a conventional partition. Two of these five steps are not computations but choices. The two most widely used implementations disclose them in their own documentation.

scikit-learn's user guide states the constraint at step 5 before the reader has reached it: “The present version of SpectralClustering requires the number of clusters to be specified in advance. It works well for a small number of clusters, but is not advised for many clusters.” The same chapter documents SpectralClustering as solving a convex relaxation of the normalized-cuts problem, and lists its scalability as “Medium n_samples, small n_clusters”.

MATLAB exposes the same switches in spectralcluster, in its Statistics and Machine Learning Toolbox. k is a required positive integer. LaplacianNormalization takes 'none', 'randomwalk' (the default) or 'symmetric' — that is step 2, with its three options named. Each row of the eigenvector matrix V is then clustered by k-means, the default, or by k-medoids, which is step 5. Two vendors, independently, made the same two decisions the user's responsibility.

Several apparently technical choices can change the partition qualitatively. One of them has a theorem behind it rather than a caution.

The graph-derived distance most often invoked to justify affinity graphs degenerates at scale. In large random neighborhood graphs — epsilon-graphs, kNN graphs and Gaussian similarity graphs alike — the rescaled hitting time converges to 1/d_v and the rescaled commute time to 1/d_u + 1/d_v. That is the vertex degrees, and nothing else. Von Luxburg and two colleagues proved it in 2014, in the Journal of Machine Learning Research, and their abstract draws the consequence for practice: “In these cases, hitting and commute times do not provide information about the structure of the graph, and their use is discouraged in many machine learning applications.” Rupchin and Mucha restated the same collapse for dense random geometric graphs in 2026, writing that in dense settings “the role of the geometry disappears and commute times degenerate to a sum of inverse degrees”.

The graph, the spectrum, and the final partition each need independent checks. The last of those includes checking that the clusters you produced are connected, which scoring well does not imply.

The Louvain algorithm may yield arbitrarily badly connected communities. A 2019 paper in Scientific Reports demonstrated the gap: “In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected.” On the Amazon, DBLP and Web UK networks the averages were 23%, 16% and 14% badly connected. The same authors then introduced the Leiden algorithm and proved that it returns communities guaranteed to be connected. Scanpy's own documentation now tells users to “Cluster cells using the Leiden algorithm, an improved version of the Louvain algorithm”, citing that paper.

So step 1 inspects the components of the graph you built, and step 4 inspects the components of the partition you produced. They are different audits. A widely used method failed the second one on a quarter of its output before anyone measured it.

Shapes that centroid geometry misses become representable once the data is embedded, but only if the graph is meaningful. Choosing the affinity becomes the central modeling decision. Every result in this lesson attaches to that decision rather than to the eigenvectors: the commute times that stop carrying structure in large neighborhood graphs, the hubs a kNN rule creates in high dimensions, the ladders on which the second eigenvector cuts on the order of n edges instead of a constant number.

Use spectral clustering when connectivity is the right notion of structure and the graph can be defended. Where a ground truth exists, count the errors against it, as was done on 34 nodes and one misclassification. Otherwise the extra mathematics may only conceal an arbitrary neighborhood choice.