Clustering and Unsupervised Evaluation

Modularity is a score a network clustering algorithm can maximise while handing back communities whose members are not connected to one another at all. Louvain is one of the most widely used clustering methods for networks. It can return communities that are internally disconnected. The objective it is optimising cannot see the defect. Traag and colleagues put a size on it in Scientific Reports in 2019: “In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected.”

Leiden, their replacement algorithm, was built to guarantee well-connected communities. Even that does not close the hole. Subhajit Sahu, working independently, measured what is left in 2024: “we observe that up to 1.3 x 10^-4 fraction of the communities are internally disconnected when using the original Leiden implementation”.

In every one of those runs the geometry is real. The modularity score is genuinely high. The artifact is the interpretation — that each returned community is a group.

Unsupervised evaluation needs several forms of evidence. There is no task label defining correctness.

Internal scores reward particular cluster shapes. The external scores have a subtler defect. Some of them have no fixed baseline. A partition carrying no information at all can score well simply by containing more clusters.

A 2010 study measured that. Vinh and colleagues generated 10,000 random clusterings for each value of K and compared them against a fixed random reference partition of 100 points. The data had no structure in it whatsoever. Mutual information, NMI and the Rand index still rise monotonically with K. The adjusted Rand index stays near zero. For two random 10-cluster partitions of 100 items the expected mutual information works out at 0.4618, against a maximum of only log(10) = 2.3. A substantial-looking score, produced by nothing.

The scikit-learn project reproduces the same experiment in its own documented example. Scoring random uniform labelings, it reports that ARI and AMI vary around 0.0 while the Rand index saturates and V-measure grows with the number of clusters. Its conclusion is written for practitioners: “Non-adjusted clustering evaluation metric can therefore be misleading as they output large values for fine-grained labelings, one could be lead to think that the labeling has captured meaningful groups while they can be totally random.”

That is why the adjusted forms below exist. It is also why the entry “Different normalizations exist” is a warning rather than a footnote.

A segmentation should be challenged several ways. A theorem sets the ceiling on what those challenges can tell you.

In the large-sample limit, the stability of idealised k-means turns on one thing. Does the limit k-means objective have a single global minimum, or several? That is a symmetry property of the distribution. It is not a statement about whether K is the correct number of clusters. Ben-David and von Luxburg proved it with a third author in 2006, and von Luxburg restates the lemma in her survey: “The stability or instability of parameter K does not depend on whether K is “correct” or “wrong”, but only on whether the K-means objective function for this particular value K has one or several global minima.” She calls that interpretation “distressing”. She adds that the idealised result does not carry over unchanged to the realistic setting.

The same hurdle appears in independent work. Shamir and Tishby state it in the introduction to their 2010 paper on stability and model selection in k-means: “clustering stability might 'break down' for large enough samples ... and thus achieve stability regardless of whether the model fits the data or not”. They then argue that, once instability is suitably scaled, clustering stability does not 'break down' even for arbitrarily large samples.

Read together, the two papers say what a passed stability test is worth. Refits that agree are evidence that the algorithm keeps landing in the same basin. They are not evidence that the basin is the right one.

Each family can fail while another looks strong. Usefulness is the one that has to be earned outside the algorithm. Here is what earning it looks like: a partition of patients across which the sign of a randomised treatment effect flips.

Latent class analysis of acute respiratory distress syndrome trial data produced two subphenotypes. They were derived independently in two cohorts, ARMA (n=473) and ALVEOLI (n=549), and reported by Calfee and colleagues in 2014. Mortality split 44% against 23% in the first and 51% against 19% in the second. The interaction with PEEP strategy came out at p=0.049.

The same two classes turned up in a third trial, FACTT (n=1,000). Famous and colleagues reported that in 2017. Their abstract gives the numbers: “Fluid management strategy had significantly different effects on 90-day mortality in the two subphenotypes (P = 0.0039 for interaction); mortality in subphenotype 1 was 26% with fluid-liberal strategy versus 18% with fluid-conservative, whereas mortality in subphenotype 2 was 40% with fluid-liberal strategy versus 50% in fluid-conservative.” The better strategy is not the same one in the two groups. It reverses.

An independent Dutch observational cohort recovered two comparable phenotypes. Cluster analysis of 20 biomarkers in 454 patients gave 'uninflamed' (N=218) and 'reactive' (N=236), with mortality 15.6% against 36.4%. Bos and colleagues published that in Thorax in 2017.

Three randomised trials and one independent observational cohort. That is the price of the fourth node in the diagram below, and no internal index can be substituted for it.

Known categories can reveal whether clusters recover a relevant distinction, but disagreement is not automatically failure. The algorithm may discover subtypes, cross-cutting structure, or artifacts.

For networks this is a theorem rather than a caution. Peel and colleagues proved it in Science Advances in 2017: “We prove that no algorithm can uniquely solve community detection, and we prove a general No Free Lunch theorem for community detection, which implies that there can be no algorithm that is optimal for all possible community detection tasks.” They also take aim at the standard practice they are arguing against. Treating observed node attributes — the metadata — as ground truth induces severe theoretical and practical problems.

Peixoto restates the theorem independently in the same terms: “when averaged over all problem instances, all algorithms have the same accuracy”. Summed over every instance, no method is ahead. A method that beats another on your labels is telling you about the fit between that method and that particular partition.

Inspect contingency tables and examples before interpreting adjusted metrics. Reference labels themselves may be noisy, incomplete, or unrelated to the intended discovery.

Combine quantitative and qualitative evidence. Each single line of evidence has a documented way of passing while the partition means nothing. Modularity was maximised in the Louvain runs that returned up to 16% disconnected communities. Refits agree whenever the objective has a unique global minimizer, correct K or not. Unadjusted NMI and the Rand index climb with K across 10,000 random clusterings. And 500 points of pure Gaussian noise produced dramatic-looking islands at perplexity 2. Each step below exists because one of the others can be passed by a partition that is not there.