Cluster-Wise Stability and Assignment Uncertainty

Why Examine Stability at Two Scales?

A global comparison can summarize how much two partitions differ, but it does not tell us which group is responsible for the difference or which cells change membership. For single-cell data, this distinction matters: a large, consistently recovered group can coexist with a small or ambiguous region of the partition. Cluster-wise retention describes recovery of each reference group, while per-cell assignment frequencies show how consistently individual cells are assigned to each group.

These are descriptive summaries across a specified set of perturbations. A perturbation might change the sampled cells, features, preprocessing choices, or random seed. The summaries do not establish that a cluster is biologically real, and they do not measure uncertainty under every conceivable analysis. They describe reproducibility under the perturbation scheme actually used.

Definition: Let \(C_i\) denote the reference-cluster label of cell \(i\), and let \(C_i^{(b)}\) denote its label in perturbation run \(b\), when that cell is included in the run. Before comparing labels, align the clusters in each run to the reference labels using a stated matching rule. A cell's aligned label in run \(b\) is written \(\widetilde C_i^{(b)}\). For reference cluster \(k\), per-run retention is the proportion of its observed reference members assigned to its matched cluster in run \(b\). Per-cell assignment frequency is the proportion of runs containing that cell in which it receives a specified aligned label.

Matching Labels and Defining Retention

Cluster labels are arbitrary: a cluster called “1” in one run might correspond to cluster “3” in another. Directly comparing the numbers would therefore be meaningless. Cluster matching addresses this label-switching problem by matching perturbed clusters to reference clusters, typically using their overlap among shared cells. A one-to-one matching can be selected to maximize total overlap. If the number of clusters differs, unmatched clusters should be recorded as unmatched rather than silently treated as equivalent to a reference cluster.

Let \(I_b\) be the set of cells included in run \(b\), and let \(n_{kb}\) be the number of cells in reference cluster \(k\) that are included in that run. Let \(a_{kb}\) be the number of those cells assigned to the cluster matched to \(k\). Provided \(n_{kb}>0\), the per-run retention is \(R_{kb}=a_{kb}/n_{kb}\). It is a recall-like measure: its denominator is the reference members available to be recovered, not all cells assigned to the matched perturbed cluster.

R_{kb} = \frac{\sum_{i\in I_b} \mathbf{1}(C_i=k,\ \widetilde C_i^{(b)}=k)} {\sum_{i\in I_b} \mathbf{1}(C_i=k)} = \frac{a_{kb}}{n_{kb}}

Here \(\mathbf{1}(\cdot)\) equals 1 when the condition inside parentheses holds and 0 otherwise. A pooled retention across runs is calculated by adding recovered cells and dividing by the number of opportunities to recover them:

R_k = \frac{\sum_b a_{kb}}{\sum_b n_{kb}}

This pooled quantity weights each run according to how many reference-cluster cells it contains. An alternative is the unweighted mean of \(R_{kb}\) over runs with \(n_{kb}>0\); that gives each run equal weight. The choice should be stated, especially when subsampling makes the numbers of observed cells vary. A run with no observed members of cluster \(k\) has no defined retention for that cluster; it is not a zero-retention run.

Worked Example: Pooled Retention for One Cluster

Suppose a hypothetical reference partition contains four cells in cluster A. Three perturbation runs include all four cells. After matching labels, the numbers assigned to the matched A cluster are 4, 3, and 2, respectively. The per-run retentions are:

R_{A1}=\frac{4}{4}=1,\qquad R_{A2}=\frac{3}{4}=0.75,\qquad R_{A3}=\frac{2}{4}=0.50

Because each run contains the same four reference members, pooled retention is:

R_A=\frac{4+3+2}{4+4+4} =\frac{9}{12}=0.75

Thus, 75% of the reference-cluster A cell-run opportunities resulted in assignment to the matched A cluster. This does not mean there is a 75% probability that cluster A is correct. It is a summary of these hypothetical perturbation results under the specified matching and perturbation procedures.

Per-Cell Assignment Frequencies

Cluster retention can hide whether the same cells are consistently recovered. For each cell \(i\) and aligned cluster \(k\), let \(B_i\) be the set of runs in which cell \(i\) is included, and let \(m_i\) be the number of those runs. The assignment frequency \(q_{ik}\) is the proportion of those runs in which the cell is assigned to aligned cluster \(k\). These frequencies sum to 1 across the possible aligned labels only when every included cell has an assignment in every counted run and unmatched assignments are handled explicitly.

q_{ik} = \frac{\sum_{b\in B_i}\mathbf{1}(\widetilde C_i^{(b)}=k)} {m_i}

A simple measure of assignment uncertainty is \(U_i=1-\max_k q_{ik}\). It is 0 when the cell always receives the same aligned label and increases as the most frequent assignment becomes less dominant. This measure captures only the largest assignment frequency; it does not distinguish every possible pattern among the remaining labels. The full vector of frequencies is therefore useful to report or inspect alongside \(U_i\).

Worked Example: Frequencies for Cells With Different Inclusion Counts

In five hypothetical perturbation runs, cell \(c_1\) is included every time and receives aligned labels A, A, A, A, and B. Cell \(c_2\) is included in four runs and receives A, A, B, and B. Their frequency vectors and uncertainty summaries are:

(q_{c_1,A},q_{c_1,B})= \left(\frac{4}{5},\frac{1}{5}\right)=(0.80,0.20), \qquad U_{c_1}=1-0.80=0.20

(q_{c_2,A},q_{c_2,B})= \left(\frac{2}{4},\frac{2}{4}\right)=(0.50,0.50), \qquad U_{c_2}=1-0.50=0.50

Cell \(c_1\) has a more consistent assignment in these runs, while \(c_2\) is split evenly between A and B. The denominators differ because \(c_2\) is absent from one run; treating that absence as an assignment to a third cluster would misrepresent what was observed.

How Cluster and Cell Summaries Connect

Pooled cluster retention is an opportunity-weighted average of the per-cell frequencies for the reference cluster's own label. This identity clarifies why a pooled cluster summary can be high even when some members are unstable: cells with more observed runs contribute more opportunities.

Derivation: For a cell \(i\) in reference cluster \(k\), let \(m_i\) be its number of observed runs and \(q_{ik}\) its frequency of assignment to aligned cluster \(k\). The total number of successful assignments from that cell is \(m_iq_{ik}\), because the frequency is the number of successes divided by \(m_i\). Summing successes over reference-cluster cells and dividing by all their observed opportunities gives:

R_k = \frac{\sum_{i:C_i=k}m_iq_{ik}} {\sum_{i:C_i=k}m_i}

The equality assumes the same aligned label definition is used in both calculations and that each included cell has an assignment counted in each run. It also shows why the unweighted average of cell frequencies need not equal pooled retention when cells have different inclusion counts. If a cell is absent from many runs, its frequency is based on fewer opportunities and should be interpreted accordingly.

Worked Example: A Split Cluster and a Contaminated Match

Suppose a hypothetical reference partition has six cells in A and six in B. In one perturbed run, the clusters are U and V, with overlap counts as follows. Matching U to A and V to B maximizes total overlap: \(4+6=10\), compared with \(2+0=2\) for the alternative one-to-one match.

Reference label	Perturbed U	Perturbed V	Reference total
A	4	2	6
B	0	6	6
Perturbed total	4	8	12

Under that matching, A retention is \(4/6=0.667\), while B retention is \(6/6=1.00\). The low A retention indicates that two reference A cells were assigned to V. Retention alone does not reveal that matched V also contains two A cells. For B, the matched V cluster has 6 B cells among 8 total members, so its precision-like fraction is \(6/8=0.75\). Reporting both quantities makes the interpretation clearer: all reference B cells were retained in V, but V also absorbed two A cells.

This pattern is consistent with a split of reference A across the perturbed clusters and a mixed matched cluster V. It does not, by itself, determine why the split occurred. The cell-level frequencies and the overlap table help locate the instability, while the perturbation design and biological context are needed to interpret it.

Diagnostics, Comparisons, and Limitations

Inspect the full set of per-run retentions and the distribution of per-cell frequency vectors, not only a pooled average. A low retention in one run may indicate sensitivity to a particular perturbation; persistently low retention suggests a more general instability under the chosen perturbation scheme. Cells with a largest assignment frequency near one are consistently assigned in these runs, whereas cells with similar frequencies for multiple labels lie near a membership boundary or in a region where the partition changes.

Check the overlap tables used for matching. A one-to-one match can conceal a split or merge because it forces each matched cluster to represent at most one reference cluster. Strong off-diagonal overlaps, many unmatched clusters, or a large gap between the best and alternative matches are warnings that a simple label alignment may be inadequate. In such cases, report the overlap structure and do not present retention as if it alone summarized the change.

These summaries complement, rather than replace, global comparisons. Variation of information and the adjusted Rand index summarize partition differences across all cells, but can obscure which cluster or cell contributes to a difference. Co-association summaries describe how often pairs of cells appear together and avoid relying on a single reference label for each cell, but they do not directly give a reference-cluster retention rate. Retention and assignment frequencies are more local and interpretable, but depend on a reference partition and the matching rule.

The main assumptions are practical as well as mathematical: cell identifiers must be tracked correctly across runs; the perturbed runs must be comparable enough for matching to be meaningful; and the reference partition and matching rule must be specified. If perturbations include different cells, denominators must reflect only observed cell-run opportunities. A small number of runs can make frequencies coarse and sensitive to individual runs. Furthermore, runs generated by related perturbations are not automatically independent statistical replicates, so the frequencies are not confidence levels or formal probabilities of a true membership.

Common Mistakes

Comparing raw cluster numbers. Cluster labels can be permuted between runs. Align labels before calculating assignments or retention.
Using the wrong denominator. Retention is the recovered fraction of reference-cluster cells present in a run. Dividing by the matched perturbed cluster size instead gives a precision-like quantity.
Counting absence as a failed assignment. A cell not included in a run has no observed assignment there. Exclude that run from its frequency denominator and from the corresponding cluster opportunity count.
Treating a frequency as a probability of truth. A frequency of 0.80 means the aligned label appeared in 80% of the observed, specified perturbation runs for that cell; it does not mean an 80% chance that the label is biologically correct.
Reporting only a cluster average. A stable average can conceal a subset of cells that repeatedly changes labels. Pair cluster retention with per-cell frequencies or their distribution.

Key takeaway: Use cluster-wise retention to ask how much of each reference group is recovered, and per-cell assignment frequencies to ask which cells keep or change their aligned labels. Interpret both relative to the perturbations, matching rule, and observed-cell denominators.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

A reference cluster has 10 cells. Across two runs, 8 and 6 of the observed reference cells are assigned to its matched cluster; 10 cells are present in each run. What is pooled retention?
A cell appears in 4 of 6 runs and receives label B in 3 of those runs. What is its B assignment frequency, and how should the two absent runs be handled?
Why can a reference cluster have retention 1.00 while its matched perturbed cluster contains cells from another reference cluster?
What does a per-cell frequency of 0.75 establish, and what does it not establish?

Solutions. (1) The pooled retention is \((8+6)/(10+10)=14/20=0.70\). (2) The B frequency is \(3/4=0.75\); the two absent runs are excluded because the cell had no assignment in them. (3) Retention's denominator includes only cells from the reference cluster, so every one of those cells can be recovered even if the matched perturbed cluster also contains other cells; the overlap table or a precision-like fraction reveals that mixing. (4) It establishes that the cell received the aligned label in 75% of the observed runs containing it under the stated perturbation scheme. It does not establish the probability that the label is true or that the cell belongs to that group biologically.