Matching Clusters Across Resampled Runs

Why Cluster Matching Requires More Than Comparing Labels

A clustering algorithm can assign entirely different labels to the same grouping of cells in two runs: “cluster 1” in one run has no inherent relationship to “cluster 1” in another. Resampling adds a second complication. A run may contain only some of the cells, and the clusters themselves may change in size or structure. To assess stability at the cluster level, we need a label-invariant way to compare memberships and a rule for deciding which clusters correspond.

The central comparison in this tutorial is the Jaccard index, calculated from the cells shared by two runs. It measures the proportion of cells in either of two clusters that belong to both. A subsequent one-to-one assignment gives a convenient summary of correspondences, but it must not be allowed to conceal clusters that split, merge, or lack an adequate counterpart.

Definition: For two resampling runs $r$ and $s$, let $U_{rs}$ be the set of cells included and assigned in both runs. Let $C_i^{(r)}$ and $C_j^{(s)}$ denote clusters $i$ and $j$ restricted to $U_{rs}$. Their overlap is $O_{ij}=|C_i^{(r)}\cap C_j^{(s)}|$, and their Jaccard index is $$ J_{ij}=\frac{|C_i^{(r)}\cap C_j^{(s)}|}{|C_i^{(r)}\cup C_j^{(s)}|} =\frac{O_{ij}}{|C_i^{(r)}|+|C_j^{(s)}|-O_{ij}}. $$ When the union is nonempty, $J_{ij}$ lies between 0 and 1. It equals 1 for identical memberships and 0 for disjoint memberships.

The restriction to $U_{rs}$ is essential. A cell missing from one run provides no evidence about whether that run would have assigned it to a particular cluster. It should not be counted as a disagreement. If $U_{rs}$ is empty, the runs cannot be compared by cell overlap. If a cluster has no cells in $U_{rs}$, its membership is not estimable in this pairwise comparison; do not treat that case as an observed zero-Jaccard match.

This comparison assumes that cell identities are aligned correctly across runs, that the cluster labels being compared refer to the same clustering target, and that each included cell has one well-defined cluster assignment in each run. The Jaccard index itself does not require equal cluster counts or equal cluster sizes. However, a very small shared-cell set may make the score unstable or unrepresentative, so its size and composition should be reported.

From Pairwise Overlaps to a One-to-One Match

With $K_r$ clusters in run $r$ and $K_s$ in run $s$, calculate a $K_r$-by-$K_s$ matrix of Jaccard indices. A tempting strategy is to give every cluster in the first run its highest-scoring partner. That can assign the same cluster in the second run to several clusters in the first, even when the goal is a one-to-one correspondence. Instead, choose a set of pairs that maximizes the total Jaccard score subject to each cluster appearing in at most one pair.

\max_{M}\ \sum_{(i,j)\in M}J_{ij}, \qquad \text{subject to each }i\text{ and each }j\text{ appearing at most once in }M.

This is a maximum-weight bipartite matching problem. Standard assignment algorithms, such as the Hungarian algorithm, find a globally optimal solution. To allow clusters to remain unmatched, the assignment can be padded with dummy partners that contribute zero. A minimum acceptable Jaccard threshold $\tau$ can also be specified in advance: pairs below $\tau$ are not eligible, and dummy assignments represent unmatched clusters. There is no universal value of $\tau$; the choice depends on the application and should be justified rather than selected after inspecting the desired matches.

A short justification explains why the global rule matters. Suppose two clusters from run $r$ both have their largest individual Jaccard score with the same cluster from run $s$. Independent selection would reuse that cluster and leave the correspondence inconsistent with the one-to-one goal. Global assignment instead compares the total score of competing sets of pairs and selects the best feasible set. It does not guarantee that every selected pair is biologically meaningful: that is why eligibility thresholds, unmatched labels, and separate split/merge diagnostics are needed.

Worked Example: Calculating the Match From a Jaccard Matrix

Suppose the shared cells in two hypothetical runs are numbered 1 through 10. Run $r$ has $C_1^{(r)}=\{1,2,3,4,5,6\}$ and $C_2^{(r)}=\{7,8,9,10\}$. Run $s$ has $C_1^{(s)}=\{1,2,3,4,7\}$ and $C_2^{(s)}=\{5,6,8,9,10\}$. Each partition contains all 10 shared cells.

For $C_1^{(r)}$ and $C_1^{(s)}$, the intersection has four cells and the union has $6+5-4=7$ cells. Thus $J_{11}=4/7=0.5714$. For $C_1^{(r)}$ and $C_2^{(s)}$, the intersection is $\{5,6\}$, so $J_{12}=2/(6+5-2)=2/9=0.2222$.

For $C_2^{(r)}$ and $C_1^{(s)}$, the intersection is $\{7\}$, giving $J_{21}=1/(4+5-1)=1/8=0.1250$. For $C_2^{(r)}$ and $C_2^{(s)}$, the intersection is $\{8,9,10\}$, giving $J_{22}=3/(4+5-3)=3/6=0.5000$.

The matrix is therefore $\begin{pmatrix}0.5714&0.2222\\0.1250&0.5000\end{pmatrix}$. Matching the diagonal gives total score $0.5714+0.5000=1.0714$; the off-diagonal assignment gives $0.2222+0.1250=0.3472$. The diagonal is the global optimum. If the predeclared threshold were $\tau=0.30$, both diagonal pairs would be eligible, while neither off-diagonal pair would be. The conclusion is that these two pairs are the preferred correspondences under that rule, not that the clusters are identical.

Unmatched Clusters, Splits, and Merges

A one-to-one matching is a summary, not a complete description of changes in membership. A cluster can divide into multiple clusters in another run, or multiple clusters can combine into one. In either case, a single best partner may capture only part of the relationship. To diagnose these patterns, inspect the overlap matrix and use directional overlap proportions as well as Jaccard indices.

Definition: For a pair with overlap $O_{ij}$, define the fraction of cluster $i$ represented in cluster $j$ as $O_{ij}/|C_i^{(r)}|$, and the fraction of cluster $j$ represented in cluster $i$ as $O_{ij}/|C_j^{(s)}|$. These directional proportions answer different questions because their denominators differ. A possible split is suggested when substantial portions of one cluster are distributed across several clusters in the other run; a possible merge is suggested by the reverse pattern.

For example, a high fraction of a reference cluster in each of two run-specific clusters can indicate that the reference cluster has split. Conversely, if one run-specific cluster contains substantial fractions of two reference clusters, those clusters may have merged. These are descriptive diagnostics, not automatic proof of a biological split or merge. Report the relevant overlaps and cluster sizes, and avoid imposing a universal cutoff: what counts as “substantial” depends on the application.

Worked Example: Detecting a Split Behind an Unmatched Cluster

In a hypothetical comparison on the same eight shared cells, run $r$ has $A_1=\{1,2,3,4,5,6,7,8\}$. Run $s$ divides these cells into $B_1=\{1,2,3,4,5\}$ and $B_2=\{6,7,8\}$. The Jaccard indices are $J(A_1,B_1)=5/(8+5-5)=5/8=0.625$ and $J(A_1,B_2)=3/(8+3-3)=3/8=0.375$.

With a one-to-one assignment and threshold $\tau=0.50$, $A_1$ matches $B_1$, while $B_2$ is unmatched under the threshold rule. But $B_2$ is not simply an unrelated cluster: the two directional proportions for $A_1$ and $B_2$ are $3/8=0.375$ and $3/3=1$. Across both clusters, $B_1$ and $B_2$ together cover all of $A_1$. The matching table should therefore be accompanied by a split diagnostic, rather than interpreted as evidence that $B_2$ has no relationship to the earlier cluster.

Worked Example: Recognizing a Merge and a Weak Forced Match

Suppose two clusters in run $r$ are $A_1=\{1,2,3,4\}$ and $A_2=\{5,6,7,8\}$, while run $s$ has one cluster $B_1=\{1,2,3,4,5,6,7,8\}$. Then $J(A_1,B_1)=4/(4+8-4)=0.5000$, and $J(A_2,B_1)=4/(4+8-4)=0.5000$. The one-to-one assignment can match $B_1$ to only one of the two clusters; if there is no other information, either choice has the same total score. With a threshold of $0.60$, neither pair is eligible, so both reference clusters are unmatched.

Neither outcome should be reported alone. The directional proportions are $4/4=1$ for each reference cluster and $4/8=0.5000$ for $B_1$. Thus the single cluster $B_1$ contains all cells from each of the two reference clusters, consistent with a merge in this comparison. The threshold correctly avoids claiming a strong one-to-one match, while the overlap pattern reveals the many-to-one relationship.

Diagnostics, Alternatives, and Limitations

Before interpreting a match, check that the two runs share enough cells for a meaningful comparison and that the shared cells are not concentrated in a narrow subset of the data. Record the number of shared cells and the sizes of the compared clusters on that shared set. Inspect the full overlap matrix for ambiguous ties, many-to-one patterns, and clusters whose only possible matches have small Jaccard values. Repeat the comparison under reasonable changes to any chosen threshold; conclusions that change sharply should be described as threshold-sensitive.

A cluster with no cells in the shared set is not evaluable in that pairwise comparison. A cluster with shared cells but no eligible partner is unmatched under the stated rule. These are different situations. Likewise, a cluster left unmatched by a one-to-one assignment may still have substantial overlap with a cluster already assigned elsewhere, which is precisely why split and merge checks matter.

Jaccard matching is useful when the question concerns interpretable, cluster-by-cluster correspondences. The adjusted Rand index instead summarizes agreement between two entire partitions, correcting pairwise agreement for chance; it does not produce a list of matched cluster pairs. Comparing labels directly is invalid because label names are arbitrary. Matching by cluster centroids can be useful in some settings, but it compares locations in a chosen representation rather than cell memberships and may be misleading if representations or embeddings differ across runs. No single summary answers all these questions.

The Jaccard index is sensitive to cluster size and to which cells are shared: the same intersection can yield different scores when the union differs. A high score is evidence of similar membership among the shared cells, not proof that a cluster is a true cell type or that its membership is stable under every perturbation. Conversely, a low score can reflect a genuine structural change, limited shared cells, or both. The measure is also pairwise: comparisons across many runs can use different shared sets, so their scores are not automatically on a directly comparable footing.

Common pitfall: “Each cluster should be matched to its highest-Jaccard partner, so every cluster has a counterpart.” This can reuse one cluster for multiple partners, force weak matches, and hide splits or merges. Instead, use a global one-to-one assignment with an explicit unmatched option and a justified threshold, then inspect the full overlap pattern and report unmatched or structurally changed clusters.

A Practical Matching Workflow

Define the comparison set.
Find the cells assigned in both runs and state the size and scope of this shared set.

Build the overlap and Jaccard matrices.
For every cluster pair, calculate the intersection, union, and Jaccard index using only the shared cells.

Set eligibility and assign pairs.
Specify a minimum Jaccard threshold when appropriate, then maximize the total score with one-to-one constraints and dummy unmatched assignments.

Check for structural changes.
Use directional overlap proportions and the full matrix to identify potential splits, merges, ties, and clusters without eligible partners.

Report limits and sensitivity.
Give the shared-cell count, cluster sizes, threshold, matched pairs, unmatched or unevaluable clusters, and any threshold-sensitive conclusions.

Check Your Understanding

Answer each question, then compare with the solutions below.

Two clusters have intersection size 6 and sizes 10 and 8. What is their Jaccard index?
Why should cells absent from one run not be counted as disagreements in the Jaccard calculation?
Two clusters in one run both have their largest Jaccard value with the same cluster in another run. What does global one-to-one matching prevent?
What is the difference between a cluster with no cells in the shared set and one that has cells in the shared set but falls below the match threshold?
One cluster in the second run contains all the cells from each of two clusters in the first run. What pattern does this suggest, and what should be inspected besides the one-to-one assignment?

Solutions. (1) The union size is $10+8-6=12$, so $J=6/12=0.5000$. (2) An absent cell has no assignment in one run to compare with the other assignment; counting it as disagreement would treat unobserved membership as observed disagreement. (3) It prevents the same cluster from being assigned as the one-to-one partner of multiple clusters, choosing the feasible set of pairs with the greatest total score instead. (4) The first is unevaluable for that run pair because it has no observed shared-cell membership; the second is evaluable but unmatched under the chosen rule. (5) It suggests a merge. Inspect the full overlap matrix and directional proportions, because the one-to-one assignment can select only one of the two reference clusters as the partner.