Hierarchical Gene Clustering With Topological Overlap

From Network Neighborhoods to a Gene Dendrogram

A pair of genes can be similar in a co-expression network for more than one reason. They may have a strong direct edge, or they may connect to many of the same genes. Topological overlap (TOM) combines these features into a pairwise similarity. Hierarchical clustering then organizes the genes by that similarity, producing a dendrogram whose shape depends in part on the chosen linkage method.

The procedure starts with a network whose nodes are genes and whose edge weights encode the chosen co-expression relationships. The earlier material on topological overlap defines how direct adjacency and shared neighbors contribute; here the focus is on transforming those values into a clustering input and interpreting the resulting merges. Clustering describes nested similarity patterns in the supplied network. It does not establish that genes regulate one another or that a group is biologically functional.

Definition: Let $a_{ij}=a_{ji}$ be the adjacency between genes $i$ and $j$, with $0\leq a_{ij}\leq1$ and $a_{ii}=0$. The weighted degree (or strength) of gene $i$ is $k_i=\sum_u a_{iu}$. The shared-neighbor weight for genes $i$ and $j$ is $l_{ij}=\sum_u a_{iu}a_{uj}$. For $i\ne j$, their topological overlap is $$ \operatorname{TOM}_{ij}=\frac{l_{ij}+a_{ij}}{\min(k_i,k_j)+1-a_{ij}}. $$ Set $\operatorname{TOM}_{ii}=1$. The corresponding topological-overlap dissimilarity is $d_{ij}=1-\operatorname{TOM}_{ij}$, with $d_{ii}=0$.

This version assumes a symmetric, nonnegative adjacency scaled to $[0,1]$, with no self-loops. The denominator uses the smaller of the two weighted degrees, with an adjustment for the direct edge. The formula is used for $i\ne j$; the diagonal is set by convention. For a signed network, the adjacency supplied to this formula must still be nonnegative and defined consistently with the chosen network construction. Genes with no edges have zero off-diagonal overlap with other isolated genes under this definition.

Why the Dissimilarity Is Bounded, but Not Necessarily a Metric

For each $u$, $a_{iu}a_{uj}\leq a_{iu}$ and $a_{iu}a_{uj}\leq a_{uj}$, since every adjacency is between zero and one. With no self-loops, summing over $u$ gives $l_{ij}\leq k_i-a_{ij}$ and $l_{ij}\leq k_j-a_{ij}$. Therefore,

l_{ij}+a_{ij}\leq\min(k_i,k_j).

Also, $\min(k_i,k_j)+1-a_{ij}\geq\min(k_i,k_j)$. The denominator is positive, so $0\leq\operatorname{TOM}_{ij}\leq1$, and hence $0\leq d_{ij}\leq1$. Symmetry of the adjacency makes both TOM and its dissimilarity symmetric. These properties make the matrix a natural input to many hierarchical clustering algorithms.

They do not guarantee the triangle inequality required of a metric. For example, two genes can each have TOM equal to one with a third gene, while having TOM below one with each other. Thus $d_{ij}$ is best called a dissimilarity, not automatically a distance in a geometric space. This distinction matters when choosing a linkage method and when interpreting dendrogram heights.

Worked Example: Calculating TOM in a Small Network

Suppose a hypothetical unweighted network has five genes, A through E, and edges A–B, A–C, B–C, C–D, and D–E. Each listed edge has adjacency one; all other adjacencies are zero. The weighted degrees are $k_A=2$, $k_B=2$, $k_C=3$, $k_D=2$, and $k_E=1$. Calculate TOM for A and D, then for C and E.

A and D have no direct edge, so $a_{AD}=0$. They share C as a neighbor: $a_{AC}a_{CD}=1$, while the products through all other genes are zero. Thus $l_{AD}=1$, and

\operatorname{TOM}_{AD} =\frac{1+0}{\min(2,2)+1-0} =\frac{1}{3}\approx0.3333, \qquad d_{AD}=1-\frac{1}{3}=\frac{2}{3}.

C and E are not directly connected, but they share D: $a_{CD}a_{DE}=1$, so $l_{CE}=1$. Therefore,

\operatorname{TOM}_{CE} =\frac{1+0}{\min(3,1)+1-0} =\frac{1}{2}=0.5000, \qquad d_{CE}=0.5000.

The shared-neighbor contribution gives C and E greater overlap than A and D, relative to the normalization in each pair. This calculation does not imply that the genes have a direct edge: both pairs have adjacency zero.

How Linkage Builds the Dendrogram

Agglomerative hierarchical clustering begins with every gene in its own cluster. At each step, it merges the two clusters with the smallest linkage dissimilarity, records that value as the merge height, and continues until all genes are in one cluster. The dissimilarity between individual genes comes from the TOM dissimilarity matrix; linkage specifies how to combine those pairwise values when clusters contain multiple genes.

Linkage	Cluster dissimilarity	Typical effect
Single	Smallest pairwise $d_{ij}$ across the two clusters	Can join clusters through a chain of close pairs.
Complete	Largest pairwise $d_{ij}$ across the two clusters	Requires even the least similar cross-cluster pair to be relatively close.
Average	Arithmetic mean of all pairwise $d_{ij}$ across the two clusters	Summarizes all cross-cluster pairs and often provides an intermediate result.

For average linkage, every gene pair across the two clusters receives equal weight in the mean. This is also called unweighted pair-group average linkage. It differs from weighted average linkage, which averages cluster-level dissimilarities and can give different influence to a cluster formed at an earlier step. A dendrogram displays merge order and height; a vertical branch length is not a gene’s expression change, a correlation, or a p-value.

Worked Example: How Linkage Changes a Merge Height

Use the five-gene network from the previous example. Its TOM values are one for A–B, A–C, B–C, and D–E; $1/2$ for C–D and C–E; $1/3$ for A–D and B–D; and zero for A–E and B–E. The remaining pairs are determined by symmetry. Consequently, A, B, and C can form a cluster at height zero, and D and E can form a cluster at height zero. Compare the dissimilarity between clusters $\{A,B,C\}$ and $\{D,E\}$ under three linkages.

The six cross-cluster dissimilarities are $d_{AD}=2/3$, $d_{AE}=1$, $d_{BD}=2/3$, $d_{BE}=1$, $d_{CD}=1/2$, and $d_{CE}=1/2$. Single linkage takes the smallest:

d_{\text{single}}(\{A,B,C\},\{D,E\})=\min(2/3,1,2/3,1,1/2,1/2)=1/2.

Complete linkage takes the largest, giving $d_{\text{complete}}=1$. Average linkage sums all six values and divides by six:

d_{\text{average}} =\frac{2/3+1+2/3+1+1/2+1/2}{6} =\frac{13/3}{6} =\frac{13}{18}\approx0.7222.

The methods therefore place the merge of these two clusters at different heights: 0.5000, 0.7222, or 1.000, respectively. Single linkage treats the existence of one relatively close cross-pair as sufficient; complete linkage is governed by the most dissimilar cross-pair. The initial zero-height merges are tied, so software may display equivalent merge orders differently. Such ties should not be mistaken for a biological ordering among A, B, and C.

Interpreting the Dissimilarity and Choosing Linkage

A short dissimilarity means the pair has high TOM in this particular network; it does not mean their expression profiles are identical. TOM incorporates the constructed network’s direct edges and neighborhoods, so its interpretation depends on the correlation measure, adjacency transformation, and any thresholding used to produce that network. The dendrogram inherits those choices.

Single linkage is useful when connected chains are meaningful, but it can produce chaining: a sequence of genes can join a cluster even when its endpoints are far apart. Complete linkage limits the maximum within-cluster dissimilarity at each merge, but can be sensitive to an unusual pair. Average linkage uses all cross-pairs and can be a compromise, though it is not universally preferable. None of these methods is an objective-free “correct” tree; they answer different questions about what cluster similarity means.

Ward linkage is a different option, but its standard interpretation is as minimizing increases in within-cluster sums of squares under Euclidean geometry. TOM dissimilarities are not guaranteed to be Euclidean, so applying Ward’s criterion directly to $1-\operatorname{TOM}$ need not have that variance-minimizing interpretation. Likewise, community detection, covered in the earlier material on community detection objectives, optimizes a network partition objective rather than building a nested tree. A dendrogram is useful when nested merge structure is of interest; it is not a substitute for every network clustering goal.

A dendrogram’s merge height records the linkage dissimilarity at that step. A larger height indicates a less similar merge under the chosen definition, but it is not a calibrated measure of evidence that two modules differ. The agglomerative algorithm does not undo an earlier merge. Therefore, a high late merge cannot repair an early merge that was undesirable under the scientific goal. Ties, near-ties, and clusters joined by single-link chains deserve particular attention.

Diagnostics and Common Pitfalls

Before interpreting a tree, check the matrix and the clustering output. The adjacency should be symmetric, have the intended diagonal convention, and use weights in the range expected by the TOM formula. The resulting TOM should be symmetric and bounded by zero and one; the derived dissimilarity should have zero diagonal and values in the same range. Large asymmetries or values outside the range usually signal an indexing, formula, or preprocessing error. Confirm that genes are in the same order in the matrix and the dendrogram labels.

Inspect the distribution of off-diagonal dissimilarities and the merge heights. Many exact zeros can indicate identical or redundant network neighborhoods, or can arise from the normalization for direct links. A long sequence of small single-link merges followed by a large jump may indicate chaining. A few unusually large complete-link merges can be driven by outlying pairs. Compare plausible linkage choices and network definitions when the resulting grouping is sensitive; such comparison is a diagnostic, not proof that one tree is biologically correct. Sampling variation in the estimated network also carries into TOM and the dendrogram.

Worked Example: A Zero Dissimilarity Does Not Prove Identical Profiles

Consider a hypothetical three-gene network with only the edges A–B and B–C, each of weight one. Its degrees are $k_A=1$, $k_B=2$, and $k_C=1$. For A and B, there is no shared neighbor contributing to $l_{AB}$, and $a_{AB}=1$. Thus

\operatorname{TOM}_{AB} =\frac{0+1}{\min(1,2)+1-1}=1, \qquad d_{AB}=0.

The same calculation gives $\operatorname{TOM}_{BC}=1$ and $d_{BC}=0$. A and C have no direct edge but share B, so $l_{AC}=1$ and

\operatorname{TOM}_{AC} =\frac{1+0}{\min(1,1)+1-0} =\frac{1}{2}, \qquad d_{AC}=\frac{1}{2}.

Here $d_{AC}=1/2$, while $d_{AB}+d_{BC}=0$, so the triangle inequality fails. Also, a zero dissimilarity between A and B does not establish identical expression profiles; it reflects the TOM normalization for this network. Treating $1-\operatorname{TOM}$ as an ordinary metric or as raw expression distance would therefore be a mistake.

Key takeaway: Topological overlap supplies a bounded, symmetric gene dissimilarity, while linkage determines how those pairwise values become cluster merges. State both choices, inspect ties and chaining, and interpret the dendrogram as a description of the constructed network rather than a direct biological or inferential conclusion.

Check Your Understanding

Answer each question, then compare with the solutions below.

In a network with $a_{ij}=0.4$, $k_i=1.2$, $k_j=0.8$, and $l_{ij}=0.3$, calculate $\operatorname{TOM}_{ij}$ and $d_{ij}$.
For cross-cluster dissimilarities 0.2, 0.5, 0.6, and 0.9, calculate single, complete, and average linkage.
Why does single linkage sometimes produce a long chain of genes in one cluster?
Give one reason not to interpret a dendrogram merge height as a p-value or as evidence of causation.

Solutions. (1) The denominator is $\min(1.2,0.8)+1-0.4=1.4$. Thus $\operatorname{TOM}_{ij}=(0.3+0.4)/1.4=0.5000$, and $d_{ij}=1-0.5000=0.5000$. (2) Single linkage is the minimum, 0.2; complete linkage is the maximum, 0.9; average linkage is $(0.2+0.5+0.6+0.9)/4=0.5500$. (3) It uses only the smallest cross-cluster pair at each step, so a succession of close pairs can join endpoints that are not themselves close. (4) Merge height is calculated from network dissimilarities and a linkage rule, not from a sampling distribution or causal model; it is not a p-value and does not establish causation.

Linkage	Cluster dissimilarity	Typical effect
Single	Smallest pairwise \(d_{ij}\) across the two clusters	Can join clusters through a chain of close pairs.
Complete	Largest pairwise \(d_{ij}\) across the two clusters	Requires even the least similar cross-cluster pair to be relatively close.
Average	Arithmetic mean of all pairwise \(d_{ij}\) across the two clusters	Summarizes all cross-cluster pairs and often provides an intermediate result.