Co-Clustering Matrices for Stability Assessment

Why Compare Partitions Pair by Pair?

A clustering fit assigns observations to groups, but a single fitted partition does not show whether those assignments persist under resampling or other controlled perturbations. Comparing cluster labels directly across fits is also awkward: labels such as “cluster 1” and “cluster 2” have no intrinsic meaning and can switch between runs. A co-clustering matrix avoids that label-matching problem by recording, for each pair of observations, how often the pair is assigned to the same cluster.

The matrix is useful as a stability summary, not as a substitute for the fitted models. Its entries describe repeated assignments under a specified fitting and perturbation procedure. Strong blocks suggest groups whose members repeatedly travel together; intermediate entries can highlight observations near unstable boundaries.

Definition and Construction

Definition: Fix $n$ reference observations and perform $B$ clustering fits. In fit $b$, let $z_i^{(b)}$ denote the cluster label assigned to reference observation $i$, for $i=1,\ldots,n$ and $b=1,\ldots,B$. The co-clustering matrix $C$ has entries $$ C_{ij}=\frac{1}{B}\sum_{b=1}^{B} I\!\left(z_i^{(b)}=z_j^{(b)}\right), $$ where $I(A)=1$ if the statement $A$ holds and $I(A)=0$ otherwise. Thus $C_{ij}$ is the proportion of fits in which observations $i$ and $j$ share a cluster.

The reference set must be the same in every fit for this definition to apply directly. If a bootstrap sample omits some original observations, the analyst needs a stated way to assign those observations for that fit—for example, a prediction rule based on the fitted model. An observation that was absent from a resample cannot simply be treated as belonging to a new cluster. The interpretation also depends on the perturbation scheme, fitting algorithm, and policy for choosing the number of clusters.

Relabeling the clusters in any fit leaves every indicator unchanged. The matrix therefore compares partitions without requiring labels to be aligned. It is symmetric, has $C_{ii}=1$, and every entry lies between 0 and 1. An entry of 1 means that the pair was together in every fit; an entry of 0 means that it was separated in every fit.

Worked Example: Computing a Small Co-Clustering Matrix

Suppose four observations are assigned in three fits as follows: fit 1 gives $\{1,2\}\mid\{3,4\}$; fit 2 gives $\{1,2,3\}\mid\{4\}$; and fit 3 gives $\{1,2\}\mid\{3\}\mid\{4\}$. Compute the matrix.

Observations 1 and 2 are together in all three fits, so $C_{12}=3/3=1$. The pair 1 and 3 is together only in fit 2, so $C_{13}=1/3$. The pair 1 and 4 is never together, so $C_{14}=0$. The pair 2 and 3 is together only in fit 2, giving $C_{23}=1/3$. Finally, 3 and 4 are together only in fit 1, giving $C_{34}=1/3$. Symmetry and the unit diagonal complete the matrix: $$ C= \begin{pmatrix} 1&1&1/3&0\\ 1&1&1/3&0\\ 1/3&1/3&1&1/3\\ 0&0&1/3&1 \end{pmatrix}. $$

The pair $\{1,2\}$ is consistently grouped, whereas the remaining co-memberships are less persistent. This is evidence about stability under these three fits; it does not, by itself, establish that the data-generating population has exactly one group containing 1 and 2.

What the Matrix Can and Cannot Say

Rows and columns are indexed by observations, so a block of large off-diagonal entries indicates a set of observations that tends to be assigned together. A block near 1 is strong evidence of persistent co-membership under the chosen procedure. Entries near 0 between two such blocks indicate that the blocks are usually separated. Intermediate entries may signal a boundary whose location shifts across fits, but can also result from a small number of runs or a perturbation scheme that produces varied partitions.

The number of clusters may vary across fits without preventing construction of the matrix, provided each fit assigns every reference observation to one cluster. The matrix summarizes pairwise assignments, not the selected cluster count. It does not reveal why assignments changed, and it does not establish that a stable grouping is scientifically meaningful. Interpret it alongside the model and diagnostics relevant to the analysis.

Worked Example: Reading Blocks and a Diffuse Boundary

Consider six fits on four reference observations with partitions: two fits of $\{1,2\}\mid\{3,4\}$; one fit of $\{1,2,3\}\mid\{4\}$; two fits of $\{1,2\}\mid\{3\}\mid\{4\}$; and one fit of $\{1\}\mid\{2\}\mid\{3,4\}$. The pair $\{1,2\}$ is together in the first two fits and the third fit, plus the two fits with $\{1,2\}$ separated from 3 and 4: five of six fits. Thus $C_{12}=5/6$. The pair $\{3,4\}$ is together in the two initial fits and the final fit, so $C_{34}=3/6=1/2$. Only one fit groups 1 with 3, giving $C_{13}=1/6$; no fit groups 1 with 4 or 2 with 4; and only the fit $\{1,2,3\}\mid\{4\}$ groups 2 with 3, so $C_{23}=1/6$. The resulting matrix is $$ C= \begin{pmatrix} 1&5/6&1/6&0\\ 5/6&1&1/6&0\\ 1/6&1/6&1&1/2\\ 0&0&1/2&1 \end{pmatrix}. $$

The entries support a persistent pair $\{1,2\}$ and a persistent separation between that pair and observation 4. The $1/2$ entry for observations 3 and 4 is diffuse: those two are together in only half the fits. It would be premature to describe $\{3,4\}$ as a stable group based only on this frequency.

Two Properties of the Matrix

The first property gives a useful mathematical check on a computed matrix. A symmetric matrix $C$ is positive semidefinite if $a^\mathsf{T}Ca\geq 0$ for every real vector $a$. Every co-clustering matrix constructed as above has this property.

Theorem: For any finite collection of complete partitions of the same $n$ reference observations, the co-clustering matrix $C$ is symmetric and positive semidefinite, with $C_{ii}=1$ and $0\leq C_{ij}\leq 1$.

Proof. For each fit $b$, let $A^{(b)}$ be the $n\times n$ matrix with entries $A_{ij}^{(b)}=I(z_i^{(b)}=z_j^{(b)})$. For each cluster $g$ in fit $b$, define the vector $v_g^{(b)}$ whose $i$th entry is 1 if observation $i$ belongs to cluster $g$, and 0 otherwise. An entry of $\sum_g v_g^{(b)}(v_g^{(b)})^\mathsf{T}$ equals 1 precisely when its two observations belong to the same cluster, and equals 0 otherwise. Consequently, $$ A^{(b)}=\sum_g v_g^{(b)}(v_g^{(b)})^\mathsf{T}. $$ For every real vector $a$, $$ a^\mathsf{T}A^{(b)}a =\sum_g\left((v_g^{(b)})^\mathsf{T}a\right)^2\geq 0. $$ Since $C=B^{-1}\sum_{b=1}^B A^{(b)}$, it follows that $$ a^\mathsf{T}Ca=\frac{1}{B}\sum_{b=1}^B a^\mathsf{T}A^{(b)}a\geq 0. $$ Each $A^{(b)}$ is symmetric and has a unit diagonal, and its entries are 0 or 1. Their average is therefore symmetric, has a unit diagonal, and has entries in $[0,1]$. $\square$

Positive semidefiniteness is a property of the frequency matrix, not a guarantee that it represents one partition. In general, its entries are fractional averages over many partitions.

The second property explains the probability interpretation of the entries when fits are repeated under a fixed random procedure. Suppose each fit is generated independently under the same procedure, and every fit assigns every reference observation. Define $Y_{ij}^{(b)}=I(z_i^{(b)}=z_j^{(b)})$, and let $q_{ij}=P(z_i=z_j)$ for one such random fit. Then the $Y_{ij}^{(b)}$ are independent, identically distributed Bernoulli random variables with expectation $q_{ij}$.

Result: Under those independence and common-distribution conditions, $C_{ij}\xrightarrow{a.s.}q_{ij}$ as the number of fits $B$ tends to infinity.

Proof. For a fixed pair $i,j$, the variables $Y_{ij}^{(b)}$ are iid and satisfy $E[Y_{ij}^{(b)}]=q_{ij}$. They are bounded, so $E[|Y_{ij}^{(b)}|]\leq 1<\infty$. The strong law of large numbers therefore applies: $$ C_{ij}=\frac{1}{B}\sum_{b=1}^B Y_{ij}^{(b)} \xrightarrow{a.s.} E[Y_{ij}^{(1)}]=q_{ij}. $$ There are only finitely many pairs for fixed $n$, so this convergence holds simultaneously for all entries with probability one. $\square$

This result does not say that the entries estimate a universal or intrinsic probability of belonging to the same group. The probability $q_{ij}$ is defined by the fitting and perturbation procedure. If the runs are dependent or their procedures change from fit to fit, the stated argument does not apply as written.

Worked Example: Why a Threshold Need Not Define Clusters

Suppose five repeated fits produce these partitions: three fits give $\{1,2,3\}$; one gives $\{1,2\}\mid\{3\}$; and one gives $\{2,3\}\mid\{1\}$. Then $C_{12}=4/5$, because observations 1 and 2 are together in the first four fits. Similarly, $C_{23}=4/5$. But $C_{13}=3/5$, since 1 and 3 are together only in the three fits that group all observations.

If an analyst declares two observations “linked” whenever their co-clustering frequency is at least $0.7$, then 1 is linked to 2 and 2 is linked to 3, but 1 is not linked to 3. Thus this thresholded relation is not transitive and does not define a partition. The threshold may be used as a descriptive display choice, but it does not automatically produce coherent clusters.

Common Pitfalls and Practical Interpretation

Reading a frequency as a probability without specifying the procedure. The frequency refers to the repeated fitting scheme used; changing the perturbation or assignment policy can change its interpretation.
Assuming a diffuse entry has only one explanation. It may indicate an unstable boundary, but it can also reflect few fits, differing cluster counts, or changes in more than one part of the partition.
Treating a thresholded matrix as a fitted partition. Pairwise threshold decisions need not be transitive, as the worked example shows.
Comparing unmatched observations across fits. Entries require both observations to have defined assignments in every fit. If resampling leaves some observations out, the rule for assigning them must be explicit.
Equating stability with validity. Repeated agreement is evidence of reproducibility under a procedure, not proof that the clusters capture meaningful population structure.

In practice, report how the fits were generated, which observations were evaluated, how assignments were obtained when needed, and whether the number of clusters was held fixed or allowed to vary. A heat map with observations ordered to display blocks can make the structure easier to see, but the numerical entries and their construction should remain the basis of interpretation.

Check Your Understanding

Use the definitions and results above to answer these questions.

In one fit, observations 4 and 7 share a cluster in 18 of 24 runs. What is their co-clustering frequency, and what does it summarize?
Why does relabeling clusters within a fit leave the co-clustering matrix unchanged?
What assumptions allow a co-clustering entry to converge almost surely to a pairwise co-membership probability?
Why can a matrix of pairwise frequencies be positive semidefinite without representing one partition?
Give one reason a pairwise frequency near one should not, by itself, be treated as evidence that a cluster is scientifically valid.