Why Cluster Validation Needs an Explicit Null
A cluster score has no context-free meaning. A high agreement score between two partitions, for example, may reflect genuine alignment or simply the sizes of the groups being compared. A within-cluster feature contrast may look large even when the feature values have no cell-level organization beyond their observed distributions. A null model makes the comparison explicit: it specifies what structure would remain if the particular pattern of interest were absent.
The important design choice is not merely which random numbers to generate. It is which aspects of the observed data to preserve and which to disrupt. A null that removes too much structure can make an observed score look unusually strong; one that preserves the pattern being tested may conceal it. A null distribution therefore answers a conditional question about a chosen reference model, not whether a clustering is biologically true.
Two broad constructions are useful. A label null model randomizes cluster or reference labels while keeping the measured data fixed. A feature null model randomizes some part of the feature data, usually before recalculating the clustering and its validation score. These answer different questions and do not substitute for one another.
Label Null Models: Preserve Group Sizes, Break Alignment
Suppose each cell has a cluster assignment and an independent reference label, such as a manually curated cell type. To ask whether the two partitions agree more than expected by chance, keep the cluster assignments fixed and permute the reference labels across cells. This preserves the number of cells in each cluster and the number with each reference label, while disrupting which cells carry which reference labels. The null is conditional on those observed margins.
For this test to have its intended interpretation, cells must be exchangeable under the null: conditional on any restrictions built into the randomization, every permitted allocation of reference labels must be equally plausible. If donor or batch affects reference-label prevalence, unrestricted shuffling may break that structure and provide an inappropriate comparison. A restricted permutation, such as shuffling within donor, can preserve donor-specific label counts. The restriction must match the null question rather than be chosen after seeing which version gives a smaller p-value.
Worked Example: Testing Partition Agreement With a Label Null
Consider eight hypothetical cells. A clustering assigns three cells to cluster A and five to cluster B. The reference annotation has four cells of type X and four of type Y. The observed contingency table is:
| Reference X | Reference Y | Total | |
|---|---|---|---|
| Cluster A | 3 | 0 | 3 |
| Cluster B | 1 | 4 | 5 |
| Total | 4 | 4 | 8 |
Use the adjusted Rand index (ARI) as the score. For a contingency table with cell counts \(n_{ij}\), row totals \(a_i\), column totals \(b_j\), and \(n\) cells, define \(T=\sum_{ij}\binom{n_{ij}}{2}\), \(R=\sum_i\binom{a_i}{2}\), and \(C=\sum_j\binom{b_j}{2}\). The ARI is
Here \(T=\binom{3}{2}+\binom{0}{2}+\binom{1}{2}+\binom{4}{2}=3+0+0+6=9\), \(R=\binom{3}{2}+\binom{5}{2}=3+10=13\), \(C=\binom{4}{2}+\binom{4}{2}=6+6=12\), and \(\binom{8}{2}=28\). Thus
Now hold the cluster assignments fixed and permute the four X and four Y reference labels among the eight cells. Suppose 999 such random permutations produce 21 ARI values at least as large as 0.4949. The observed agreement is in the upper tail of this conditional null distribution. With the standard add-one estimate, the one-sided Monte Carlo p-value is \((21+1)/(999+1)=0.022\). This is evidence against random alignment under this label-permutation null; it does not establish that either partition is biologically correct.
Feature Null Models: Preserve Marginals, Disrupt Cell-Level Organization
A feature null model is useful when the validation question concerns structure in the expression data itself. One simple construction independently permutes the values of each gene across cells. It preserves each gene's observed empirical distribution, including its mean and all its observed values, but breaks the pairing of values across genes within cells. Depending on the setup, it also breaks associations between gene values and fixed cell attributes. It does not automatically preserve library sizes, donor effects, gene-gene correlations, or other dependencies.
The score and the rerandomization steps must reflect the question. If the question is whether an entire clustering pipeline finds more structure than expected under the feature null, generate a null feature matrix, rerun the preprocessing and clustering steps that are part of that pipeline, and recalculate the score. If the labels are held fixed while features are randomized, the test instead asks whether that already-fixed partition aligns with the randomized features. These are distinct procedures.
Worked Example: A Gene-Wise Feature Null
Four hypothetical cells are assigned to clusters A (cells 1 and 2) and B (cells 3 and 4). On a transformed expression scale, gene 1 has values \(8,10,2,4\), and gene 2 has values \(7,9,3,5\), in cell order. Define the score as the average, across the two genes, of the absolute difference in mean expression between clusters. The units are transformed expression units.
For gene 1, the cluster means are \((8+10)/2=9\) and \((2+4)/2=3\), giving a difference of 6. For gene 2, they are \((7+9)/2=8\) and \((3+5)/2=4\), giving a difference of 4. Therefore the observed score is \((6+4)/2=5\) transformed expression units.
For each null replicate, independently permute the four values within each gene across the cells, retain the cluster sizes of two and two, and calculate the same score. This preserves each gene's four observed values but destroys the observed cell-wise alignment between gene values and cluster membership. Suppose 99 null replicates yield seven scores at least 5. Then the add-one upper-tail estimate is \((7+1)/(99+1)=0.08\). This result does not provide strong evidence of an unusually large score at the 0.05 level under this particular null. It does not show that the clusters are meaningless: the null ignores, among other things, gene dependence and any structure not represented by this randomization.
Independent gene-wise permutation is only one feature null. Permuting within donor can retain donor-specific empirical distributions; permuting blocks of correlated genes can retain some gene-gene structure; and a fitted parametric null can simulate features under a specified model. Each preserves different features and therefore tests a different null hypothesis. For instance, a null that preserves donor structure cannot test whether the observed pattern is explained by donor differences alone unless its design is specifically constructed to represent that explanation.
Comparing an Observed Score With Its Null Distribution
Let \(S_{\mathrm{obs}}\) be the observed score and \(S_1,\ldots,S_B\) the scores from \(B\) null replicates. If unusually large scores count against the null, a common Monte Carlo estimate is
where \(I(\cdot)\) is 1 when its condition is true and 0 otherwise. For evidence in the lower tail, use \(S_b\leq S_{\mathrm{obs}}\); for a two-sided question, define in advance what “at least as extreme” means. The add-one form avoids reporting a zero p-value merely because no simulated score exceeded the observation. Its smallest possible value is \(1/(B+1)\), so the number of replicates limits the attainable resolution.
Why the Add-One Comparison Is Justified
Under a valid randomization null, the observed arrangement and the \(B\) randomized arrangements are exchangeable: under the null, each has the same chance of occupying any rank in the combined set. With no ties, the rank of the observed score among these \(B+1\) scores is therefore uniform on the integers from 1 to \(B+1\). The upper-tail rank divided by \(B+1\) gives the add-one comparison. Ties are handled conservatively by counting null scores equal to the observed score in the upper tail. This justification depends on a valid null randomization; adding 1 does not repair a misspecified null or non-exchangeable cells.
Choosing and Diagnosing a Null Model
Start with the claim the validation analysis is meant to examine, then identify the score and the structures that should remain under that claim. The following comparison summarizes the main choices:
| Construction | Typically preserves | Typically disrupts | Question it can address |
|---|---|---|---|
| Permute reference labels across cells | Feature data, cluster assignments, label counts | Cell-wise alignment of the two partitions | Is reference-label agreement unusually high given the observed group sizes? |
| Permute labels within strata | Group counts within each specified stratum | Alignment within the allowed permutation sets | Is alignment unusual after conditioning on factors such as donor? |
| Permute each feature across cells | Each feature's empirical marginal values | Cell-wise feature co-occurrence and feature-to-cluster alignment | Is the score unusual when these marginal values lack their observed cell organization? |
| Simulate from a fitted feature model | Only features represented in the fitted model | Features the model treats as absent or random | Is the score unusual under that explicit parametric model? |
Several checks help reveal a poorly chosen or failing null:
- Check what was actually preserved. Compare cluster sizes, label counts, donor composition, feature marginals, and any other claimed invariants before and after randomization.
- Check exchangeability. If cells have different permutation probabilities because of donor, batch, or sampling structure, unrestricted shuffling may not represent the null. Use justified restrictions or a model that accounts for that structure.
- Check the score direction and scale. A high score may indicate stronger structure for one measure and worse validity for another. Specify the tail before interpreting the comparison.
- Inspect the null scores. A constant or highly discrete distribution may be a real consequence of small samples, but it can also indicate that the randomization barely changes the score. Verify that the intended part of the data is being randomized.
- Account for the full analysis when needed. If feature selection, tuning, or clustering used the observed data, omitting those steps from each null replicate can make the reference distribution too narrow for a claim about the full pipeline.
A parametric null can represent dependence that simple permutations destroy, but its conclusions depend on the model being adequate. A permutation null avoids specifying some distributional forms, but still relies on exchangeability and on the chosen invariants. Neither is universally preferable. For multiple scores or many alternative clusterings, searching for the most favorable observed-versus-null comparison also changes the interpretation; the search or multiplicity should be accounted for rather than treating the selected result as a single prespecified test.
Check Your Understanding
Answer each question, then compare with the brief solutions.
- When reference labels are permuted across cells while cluster assignments are fixed, name two quantities preserved and the pattern disrupted.
- A researcher independently permutes each gene's expression values across cells. What is preserved, and why might the resulting null be unsuitable when donor effects are central?
- In 499 null replicates, 14 scores are at least as large as the observed score. Calculate the add-one upper-tail p-value.
- Why does a small label-permutation p-value not show that a clustering is biologically correct?
Solutions. (1) The cluster assignments and their sizes are preserved, as are the reference-label counts; the cell-wise alignment between the partitions is disrupted. (2) Each gene's empirical marginal values are preserved, but donor-specific patterns may be broken by unrestricted permutation, so the null fails to condition on donor structure. A donor-restricted or otherwise appropriate null may be needed. (3) \((14+1)/(499+1)=15/500=0.03\). (4) The p-value measures how unusual the observed score is under the specified conditional null. It does not establish biological truth, rule out other explanations, or validate assumptions not represented by the null.