Co-Association Matrices and Consensus Clustering

Why Summarise Repeated Clusterings?

A clustering run assigns cells to groups, but repeating the analysis under different perturbations can produce different assignments. The cluster labels themselves are arbitrary: “cluster 1” in one run need not correspond to “cluster 1” in another. A co-association matrix avoids that label-matching problem by asking a simpler question for every pair of cells: how often were these two cells grouped together when both were clustered?

The resulting matrix displays repeated pairwise grouping patterns. High values within a block and low values between blocks suggest consensus groups; intermediate values can expose boundaries that are not consistently resolved. These are statements about agreement under a specified set of clustering runs, not proof that the groups are true biological populations.

Definition and Construction

Definition: For $n$ cells and $B$ clustering runs, let $z_i^{(b)}$ denote the cluster assigned to cell $i$ in run $b$, when that cell is included. Let $O_{ib}=1$ if cell $i$ is included in run $b$, and $O_{ib}=0$ otherwise. For cells $i$ and $j$, define $m_{ij}=\sum_{b=1}^{B}O_{ib}O_{jb}$, the number of runs in which both cells are included. Their co-association is $$ C_{ij}=\frac{\sum_{b=1}^{B}O_{ib}O_{jb}\,\mathbf{1}\{z_i^{(b)}=z_j^{(b)}\}}{m_{ij}}, $$ provided $m_{ij}>0$. Here $\mathbf{1}\{\cdot\}$ is 1 when its condition holds and 0 otherwise. If $m_{ij}=0$, $C_{ij}$ is undefined, not zero. The matrix $C$ is symmetric, and $C_{ii}=1$ for a cell observed in at least one run.

When all cells appear in every run, $m_{ij}=B$, so $C_{ij}$ is simply the proportion of runs that place cells $i$ and $j$ together. The matrix is label-invariant: changing the numerical names of clusters within any run does not change any entry. Runs may also use different numbers of clusters; the pairwise definition still applies.

The construction assumes consistent cell identities across runs and a clearly specified clustering procedure and perturbation scheme. Interpret the entries relative to that scheme: for example, runs may differ because of cell subsampling, feature perturbation, or random initialization. If cells are missing from some runs, the denominator makes each entry conditional on both cells being included together. If inclusion is related to the clustering outcome, that conditional summary may not represent the behaviour of a typical run. With different $m_{ij}$, some entries are also supported by more runs than others.

What the Matrix Estimates

For a pair observed in every run, define $Y_{ij}^{(b)}=\mathbf{1}\{z_i^{(b)}=z_j^{(b)}\}$. Suppose the runs are independent repetitions of the same perturbation protocol, with a common probability $p_{ij}$ that the pair is clustered together. Then $C_{ij}$ is the sample mean of the $B$ indicators. Its expectation is $p_{ij}$, and its variance is $p_{ij}(1-p_{ij})/B$. Thus, under these assumptions, more runs reduce the Monte Carlo variability of the estimated pairwise agreement.

This justification concerns repeated runs conditional on the data and protocol. It does not turn the entries into probabilities that two cells share a true cell type, nor does it quantify biological sampling uncertainty. If runs are strongly dependent—for example, because they reuse nearly identical perturbations—the effective information can be less than the run count suggests. For incomplete runs, the analogous proportion describes agreement among runs in which both cells were included; interpreting it as a broader target requires an appropriate inclusion mechanism.

Worked Example: Computing a Matrix From Five Runs

Suppose four hypothetical cells, A, B, C, and D, are present in all five runs. The partitions are: runs 1, 2, and 5 each give $\{A,B\}$ and $\{C,D\}$; run 3 gives $\{A,B,C\}$ and $\{D\}$; run 4 gives $\{A\}$ and $\{B,C,D\}$. For every pair, $m_{ij}=5$.

A and B are together in runs 1, 2, 3, and 5, so $C_{AB}=4/5=0.800$. C and D are together in runs 1, 2, 4, and 5, so $C_{CD}=4/5=0.800$. B and C are together in runs 3 and 4, so $C_{BC}=2/5=0.400$. A and C are together only in run 3, giving $C_{AC}=1/5=0.200$. A and D are never together, giving $C_{AD}=0/5=0$; B and D are together only in run 4, giving $C_{BD}=1/5=0.200$.

Using symmetry and a diagonal of 1, the matrix is $$ C= \begin{pmatrix} 1 & 0.800 & 0.200 & 0 \\ 0.800 & 1 & 0.400 & 0.200 \\ 0.200 & 0.400 & 1 & 0.800 \\ 0 & 0.200 & 0.800 & 1 \end{pmatrix}. $$

The strong A–B and C–D entries suggest two recurring pairs. The B–C entry is intermediate: these cells cross the apparent boundary in two of the five runs. The matrix therefore records both the recurring structure and a less consistent boundary; it does not, by itself, decide whether B and C should be merged.

From Pairwise Agreement to Consensus Groups

A consensus partition is a single grouping derived from the repeated-run summary. There is no uniquely required rule: a researcher must specify how the matrix is converted into groups. Two common choices are to treat $1-C_{ij}$ as a dissimilarity and apply a clustering method that accepts that input, or to threshold the co-association values and group cells connected by sufficiently strong pairwise links. A threshold is a chosen decision rule, not a universal biological cutoff.

For a threshold graph, each cell is a vertex, and an edge is drawn between $i$ and $j$ when $C_{ij}\geq t$, for a selected threshold $t$. Connected components then define groups. This is transparent but can have a chaining effect: a sequence of strong links can put two cells in the same component even if their direct co-association is low. Clustering $1-C$ can produce different results depending on the algorithm and its settings. In particular, $1-C$ is a useful dissimilarity for analysis, but should not automatically be assumed to satisfy every property of a metric.

Worked Example: Reading Blocks and an Ambiguous Boundary

Consider eight hypothetical runs on four cells, numbered 1–4. In four runs, the partition is $\{1,2\}$, $\{3,4\}$. In two runs, it is $\{1,2,3\}$, $\{4\}$. In the final two, it is $\{1\}$, $\{2,3,4\}$. All cells appear in every run.

Cells 1 and 2 are together in the four default runs and the two runs that merge 1, 2, and 3, giving $C_{12}=6/8=0.750$. By symmetry of the run counts, $C_{34}=6/8=0.750$. Cells 2 and 3 are together in the two runs of each merged configuration, so $C_{23}=4/8=0.500$. Cells 1 and 3 are together in only the first merged configuration, and cells 2 and 4 only in the second, so $C_{13}=C_{24}=2/8=0.250$. Cells 1 and 4 are never together, so $C_{14}=0$.

With a stated threshold $t=0.70$, the graph contains edges 1–2 and 3–4, and its components are $\{1,2\}$ and $\{3,4\}$. The direct agreement between cells 2 and 3 is $0.500$, so the threshold does not join these components. That is one defensible consensus rule, not evidence that 0.70 is intrinsically correct. A lower threshold could join groups, and a clustering procedure using the full matrix could make a different choice.

Handling Incomplete Runs and Diagnosing the Result

Worked Example: Using the Pair-Specific Denominator

Suppose four hypothetical runs each include only three of cells A, B, C, and D. Their partitions are: run 1 observes A, B, C and groups $\{A,B\}$, $\{C\}$; run 2 observes A, B, D and groups $\{A\}$, $\{B,D\}$; run 3 observes A, C, D and groups $\{A,C\}$, $\{D\}$; run 4 observes B, C, D and groups $\{B,C\}$, $\{D\}$.

A and B are jointly observed in runs 1 and 2. They are together once, so $m_{AB}=2$ and $C_{AB}=1/2=0.500$, not $1/4$. A and C are jointly observed in runs 1 and 3, and are together once, giving $C_{AC}=1/2=0.500$. A and D are jointly observed in runs 2 and 3 and are never together, so $C_{AD}=0/2=0$. B and C are jointly observed in runs 1 and 4, together once, giving $C_{BC}=0.500$. B and D are jointly observed in runs 2 and 4, together once, so $C_{BD}=0.500$. C and D are jointly observed in runs 3 and 4 and are never together, giving $C_{CD}=0$.

Each estimate uses only runs in which the pair is jointly observed. Their denominators are all two here, but in larger analyses the values of $m_{ij}$ can differ substantially. Record or inspect those denominators alongside the co-association matrix: a high value based on very few jointly observed runs should not be treated as equally well supported as one based on many.

Useful checks include confirming that $C$ is symmetric, that its defined entries lie between 0 and 1, and that diagonal entries are 1 for cells observed at least once. A visibly asymmetric matrix usually signals an implementation error. Inspect the joint-observation counts $m_{ij}$, and check that the same cell identifiers are used consistently across runs. A heatmap with rows and columns ordered to reveal blocks can help, but the ordering itself does not validate the groups.

Also examine whether the apparent blocks persist under reasonable changes to the perturbation protocol and consensus rule. Weak, diffuse blocks or many intermediate values indicate that the repeated runs do not resolve a crisp partition under the chosen setup. This is a diagnostic of the analysis, not a reason to force a clean grouping. A consensus can be stable because the procedure repeatedly captures a strong signal, but it can also consistently reflect technical structure or other features of the data.

Alternatives, Limitations, and a Common Mistake

Approach	What it summarises	Key consideration
Co-association matrix	Pairwise frequency of being assigned together	Invariant to cluster-label permutations; preserves pair-level ambiguity.
Matching cluster labels across runs	Correspondence between named clusters	Useful for tracking clusters, but requires a matching rule and is not needed to calculate pairwise co-association.
One selected clustering run	One hard partition	Simple to use, but discards disagreement across runs.
Thresholded consensus graph	Groups formed from links exceeding a chosen value	Explicit and interpretable, but sensitive to the threshold and possible chaining.

A common mistake is to call $C_{ij}=0.9$ a 90% probability that cells $i$ and $j$ are the same cell type. The calculation supports a narrower statement: among the specified runs in which both cells were included, they were assigned to the same cluster in 90% of runs. The conclusion depends on the run-generation protocol, and clustering agreement alone does not establish biological identity.

Co-association also compresses the run history. Different sets of partitions can yield similar pairwise frequencies, and the matrix does not preserve which whole partition produced each set of pairwise relations. If a hard consensus is needed, its construction rule and sensitivity to that rule should be reported. The introductory material on clustering stability motivates repeating analyses under perturbations; the co-association matrix is one way to display their pairwise agreement, not a substitute for choosing defensible perturbations or interpreting the biological context.

Align cell identities.
Use consistent identifiers and record which cells are present in each run.

Count co-assignments and co-observations.
For each pair, count runs in which both cells appear and, separately, runs in which they share a cluster.

Calculate and inspect the matrix.
Divide pairwise counts by the appropriate denominator; check symmetry, range, diagonal, and support counts.

State the consensus rule.
Use the matrix as a descriptive summary, and specify any dissimilarity method, threshold, or other rule used to obtain groups.

Check Your Understanding

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

For a pair observed together in 12 runs and co-clustered in 9 of them, what is its co-association, and what does that value describe?
Two cells are never jointly observed in any run. What should their matrix entry be?
If a threshold graph has a path of strong links between two cells but their direct co-association is low, can they still belong to the same connected component?
Why is a high co-association not, by itself, evidence that two cells belong to the same biological cell type?

Solutions. (1) $C_{ij}=9/12=0.750$; it is the observed fraction of runs in which both cells appeared that assigned them together. (2) It is undefined, because the denominator $m_{ij}$ is zero; recording zero would incorrectly mean they were observed and never co-clustered. (3) Yes. Connected components use paths, so indirect links can connect cells even when their direct pairwise value is low. (4) The value describes agreement under the specified clustering and perturbation protocol, not biological truth; technical structure or other features could also produce consistent grouping.