Aligning Cluster Labels Across Resamples

Why Cluster Labels Need Alignment

Cluster labels are names, not measurements. A clustering algorithm may call a group “1” in one run and “3” in another even when the groups contain essentially the same subjects. Conversely, the same label can refer to different subjects in different runs. Directly comparing the numbers or names assigned by separate runs therefore has no general meaning.

A useful way to compare runs is to identify the subjects present in both, count how often each reference cluster overlaps each resampled cluster, and choose a relabeling that maximizes total overlap. The resulting labels make comparisons easier to read, but do not make the partitions identical or establish that a subgroup is biologically real. Alignment is a bookkeeping operation based on observed overlap.

Constructing an Overlap-Based Assignment

Let \(I\) be the set of subjects for which both runs have cluster assignments. Write \(R_i\) for subject \(i\)'s reference label and \(S_i\) for its resampled label. The overlap table has one row per reference cluster and one column per resampled cluster:

Each subject in \(I\) contributes to exactly one cell, so the sum of all cells equals \(|I|\). Row totals describe reference-cluster sizes within the shared subjects; column totals describe resampled-cluster sizes within those same subjects. Using only shared subjects is essential: a subject absent from one run cannot provide evidence about the correspondence between that run's labels.

Represent a proposed pairing by binary variables \(x_{ab}\), where \(x_{ab}=1\) means reference cluster \(a\) is paired with resampled cluster \(b\). A cluster may be paired with at most one cluster on the other side. The assignment objective is:

This is a maximum-weight bipartite assignment problem. The Hungarian algorithm and other standard assignment algorithms solve it. The inequalities allow clusters to remain unmatched, which matters when cluster counts differ and can also matter when the overlap structure does not support a useful pairing. In a square assignment implementation, dummy rows and columns can be added with zero weight to represent unmatched clusters. A real-to-real pairing with zero overlap should be treated as unsupported, not as a meaningful match.

The objective uses raw counts because it maximizes the number of shared subjects whose cluster labels agree after relabeling. That choice gives larger clusters more influence. If the scientific goal calls for a different weighting, it must be specified explicitly; it is not equivalent to maximizing the number of correctly paired subjects.

What the Assignment Does—and Does Not—Establish

The objective has a direct interpretation. For any proposed one-to-one relabeling, every shared subject whose reference and relabeled resampled labels agree contributes one to the corresponding overlap cell. Summing the selected cells counts all such agreements. Thus, maximizing the sum selects the one-to-one relabeling with the greatest number of label agreements among the shared subjects.

This justification depends on the runs assigning each shared subject to exactly one cluster and on subject identities being matched correctly across runs. It does not require the cluster labels to have the same names or order. Nor does it require that the clusters represent the same underlying biological entities: that is a substantive interpretation, not a consequence of the algorithm.

Unmatched Groups, Weak Matches, and Multiple Runs

Unequal cluster counts are only one reason to leave a group unmatched. A cluster may contain no shared subjects, or its shared subjects may overlap several clusters without a clear one-to-one correspondence. An unmatched label is informative: it says that the selected assignment did not give that group a partner under the stated objective. It is not a claim that the group has no members or no scientific relevance.

The maximum-count solution always chooses the best available assignment, even when the best overlap is small. It is therefore useful to inspect the selected overlap counts alongside row and column totals. A match involving 3 subjects out of a reference cluster of 40, for example, deserves more caution than one involving 30 of 35. These counts describe the support for the alignment; they are not, by themselves, a universal pass-or-fail threshold.

If a minimum match strength is required, define it before inspecting results and specify how it changes the assignment problem. One option is to disallow pairings that fail a prespecified rule and permit the affected groups to remain unmatched. Another is to use an explicit cost for leaving a group unmatched. Either choice changes the optimization target and should be reported. Applying an informal threshold after seeing the chosen pairing can make the procedure difficult to interpret.

For several resampling runs, a practical approach is to choose one reference run and align each other run to it independently, using the subjects shared by that pair of runs. This avoids a chain of changing label conventions in which the alignment of a later run depends on an earlier run's arbitrary labels. The reference choice should be recorded: choosing a different reference can change which pairings are selected, particularly when overlap is weak or the runs have different cluster counts. If a run shares no subjects with the reference, its labels cannot be aligned to that reference from shared-subject overlap alone. A bridge run or another defensible reference is needed; the data provide no overlap-based correspondence in that case.

Diagnostics and Alternative Approaches

Before interpreting aligned labels, check that the overlap table is based on the intended subject intersection and that every shared subject contributes exactly once. Then inspect:

• Row and column totals: a zero total means that cluster has no shared subjects and cannot be matched from this comparison.
• Selected cell counts: small counts indicate limited direct support, even when the assignment objective selects that pairing.
• Competing cells: similar overlap counts for multiple possible partners indicate an ambiguous correspondence. The algorithm still returns an optimum, but another assignment may be nearly as good.
• Unmatched groups: record them explicitly, including whether they have zero overlap or were left unmatched because one-to-one pairing favored another group.
• Sensitivity to the reference: if plausible reference choices change the correspondence substantially, treat the labels as reference-dependent rather than canonical.

Directly comparing label names is appropriate only when labels have been defined by a shared, fixed convention across runs. Otherwise, it compares arbitrary codes. Manual relabeling can work for a small overlap table, but it is easy to make a locally sensible choice that loses total overlap, as the first example showed. Assignment algorithms provide a reproducible global optimum for the chosen weights and constraints.

Matching cluster centers or other feature-space summaries is another possible strategy when subject overlap is unavailable or insufficient. It relies on comparable feature representations and a defensible distance between summaries; preprocessing choices can affect those distances. Overlap-based assignment instead uses subject identities and observed memberships, so it is transparent when shared subjects are available. Neither approach resolves a genuine split or merge: a one-to-one assignment can name only one partner for each cluster.

A common mistake is to treat the output labels as proof that a cluster persisted unchanged. For example, someone may see that resampled cluster Y was relabeled A and conclude that A was stable. The correction is to report the overlap counts, the shared-subject denominator, unmatched groups, and any split or merge pattern. Alignment makes label comparisons coherent; it does not replace a stability analysis or justify causal or biological claims.

A Practical Alignment Workflow