Hard Thresholding And Sparse Adjacency Matrices

From Correlations to Binary Edges

A correlation matrix records the estimated strength and direction of association for every pair of genes. A network representation makes a different choice: it declares each pair either connected or not connected. A hard threshold makes that choice by comparing each estimated correlation with a specified cutoff. The result is simple to inspect, but the cutoff discards information and can materially change the resulting graph.

Let \(p\) be the number of genes in a prespecified analysis set, and let \(r_{ij}\) be the estimated correlation between genes \(i\) and \(j\), for \(i\ne j\). Assume the estimates use a consistent correlation measure and a common, documented preprocessing and sample-selection strategy. The rule must also specify how the sign of a correlation is treated. In this tutorial, the main rule uses correlation magnitude: a pair is retained when its absolute estimated correlation meets or exceeds a threshold \(\tau\).

Definition: For an undirected network with a fixed set of \(p\) genes and threshold \(0<\tau\leq 1\), the absolute-correlation hard-threshold adjacency matrix \(A=(a_{ij})\) is defined by \(a_{ii}=0\) and \(a_{ij}=I(|r_{ij}|\geq\tau)\) for \(i\ne j\). Here \(I(\cdot)\) is 1 when its condition is true and 0 otherwise. An entry of 1 represents a retained pair; an entry of 0 represents a pair that did not meet the rule. The diagonal is set to zero, so the matrix contains no self-edges.

When the pairwise correlations are symmetric, this construction gives \(a_{ij}=a_{ji}\), as required for an undirected network. The absolute-value rule retains both positive and negative correlations when their magnitudes are large enough; the binary matrix does not preserve the sign or the size of the correlation. A different rule, such as retaining only correlations \(r_{ij}\geq\tau\), produces a different network. The rule, including the use of absolute value and whether equality counts, must be stated rather than inferred from the resulting graph.

The transformation is descriptive. A retained edge says that an estimated correlation satisfied the chosen rule; by itself, it does not establish a causal link, a direct molecular interaction, or a statistically significant association. Thresholding correlations also does not produce conditional links: marginal correlations can reflect indirect relationships or shared influences.

Edge Counts, Density, and Connectivity

For a simple undirected graph, each unordered gene pair can contribute at most one edge. There are \(\binom{p}{2}=p(p-1)/2\) possible pairs. If \(m\) pairs are retained, the network density is the fraction of possible pairs that are edges:

m=\sum_{i<j} a_{ij}, \qquad D=\frac{m}{\binom{p}{2}}.

Density ranges from 0 (no retained pairs) to 1 (every possible pair retained). It depends on the number of genes and on the chosen threshold, so comparisons across networks are meaningful only when the gene universe and edge rule are made clear. In particular, a density change can reflect a changed threshold, changed genes, or changed correlation estimates.

Connectivity describes whether paths of edges join genes. A graph is connected if every pair of vertices can be joined by a path; otherwise it has multiple connected components. A gene with no retained edges is isolated. These are graph-level properties, not measures of whether an individual edge is biologically important.

Worked Example: Constructing an Adjacency Matrix

Suppose four hypothetical genes, A, B, C, and D, have the following estimated correlations: \(r_{AB}=0.82\), \(r_{AC}=0.51\), \(r_{AD}=-0.18\), \(r_{BC}=0.69\), \(r_{BD}=0.32\), and \(r_{CD}=-0.74\). Use the absolute-correlation rule with \(\tau=0.60\).

Compare each magnitude with 0.60. The magnitudes are 0.82, 0.51, 0.18, 0.69, 0.32, and 0.74, respectively. Thus, AB, BC, and CD meet the rule; the other three pairs do not. In the order A, B, C, D, the adjacency matrix is:

A= \begin{pmatrix} 0&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&0 \end{pmatrix}.

There are \(\binom{4}{2}=6\) possible pairs and \(m=3\) retained pairs, so \(D=3/6=0.5\). The graph is a path from A through B and C to D, hence it is connected. The CD edge is retained because \(|-0.74|=0.74\geq0.60\); the binary matrix records that edge but not its negative sign.

What Changing the Threshold Does

A hard threshold creates a discontinuity: a small change in an estimated correlation can switch an edge from 0 to 1, or from 1 to 0, when it crosses \(\tau\). Threshold choice therefore affects both which associations are retained and the overall graph. It is useful to study more than one plausible threshold rather than treating one cutoff as self-evident.

Result: For a fixed gene set and fixed correlation estimates, if \(\tau_1\leq\tau_2\), then every edge retained at \(\tau_2\) is also retained at \(\tau_1\). Therefore, increasing the threshold cannot increase the edge count or density. It can remove paths and split connected components, but it cannot join previously separate components.

The reason is direct: if \(|r_{ij}|\geq\tau_2\) and \(\tau_2\geq\tau_1\), then \(|r_{ij}|\geq\tau_1\). Thus the edge set at the higher threshold is a subset of the edge set at the lower threshold. Any path at the higher threshold is also present at the lower one. Removing edges cannot create a new path between two vertices that were not previously joined, though it may break an existing path. With the vertex set held fixed, the number of connected components can stay the same or increase as the threshold rises.

Worked Example: Density and Components Across Thresholds

For five hypothetical genes A–E, suppose the absolute estimated correlations are: AB = 0.72, AC = 0.48, AD = 0.12, AE = 0.08, BC = 0.55, BD = 0.43, BE = 0.09, CD = 0.67, CE = 0.38, and DE = 0.51. There are \(\binom{5}{2}=10\) possible pairs.

At \(\tau=0.50\), the retained pairs are AB, BC, CD, and DE. Thus \(m=4\), and \(D=4/10=0.40\). These edges form the path A–B–C–D–E, so all five genes are in one connected component.

At \(\tau=0.60\), only AB and CD remain. The density is \(2/10=0.20\). The components are {A, B}, {C, D}, and {E}; E is isolated. The increase from 0.50 to 0.60 removed two edges, and the removal of BC and DE broke the paths joining the genes.

At \(\tau=0.40\), the retained pairs are AB, AC, BC, BD, CD, and DE, so \(m=6\) and \(D=6/10=0.60\). The graph is connected: A is linked to B and C, D is linked to B or C, and E is linked to D. This example illustrates that a modest change in threshold can affect connectivity as well as density.

Threshold Choice and Diagnostics

There is no universally correct threshold supplied by the adjacency-matrix definition. A scientifically useful choice depends on the analysis purpose and the reliability and scale of the correlation estimates. It should be selected and reported transparently, not tuned after inspecting which genes or pathways become prominent without accounting for that selection.

Before constructing the graph, check that the gene set, correlation estimator, preprocessing, and missing-data handling are consistent across pairs. If some correlations are undefined, do not silently treat them as zero: an undefined estimate is not evidence of a weak association. Specify how such pairs are handled and how the possible-pair denominator is defined. Also verify that the correlation matrix is symmetric; if a procedure produces different estimates for \(r_{ij}\) and \(r_{ji}\), resolve that inconsistency before treating the graph as undirected.

A practical diagnostic is to calculate edge count, density, and connected components over a prespecified range of thresholds. Inspect the correlation estimates near the cutoff: a large group of pairs clustered just above or below \(\tau\) signals that small estimation changes may alter many edges. Sampling uncertainty in genome-wide correlations, discussed in the earlier material on sampling uncertainty, remains relevant after thresholding; the binary encoding does not remove it. Resampling or independent data can reveal whether conclusions depend heavily on a narrow set of borderline edges.

Interpret the diagnostics together. Very low density can leave many genes isolated or divide the graph into small components. Very high density can make the binary representation uninformative by retaining most pairs. Neither outcome alone proves a threshold is wrong: it may reflect the correlation structure, the analysis set, or the chosen cutoff. The important question is whether the resulting graph is useful for the stated purpose and robust enough for the intended interpretation.

Worked Example: A Fixed Edge Count Is a Different Rule

Suppose four hypothetical genes have six absolute estimated correlations, in descending order: 0.81, 0.61, 0.58, 0.42, 0.25, and 0.11. Under a magnitude threshold of \(\tau=0.60\), only the first two pairs are retained. The edge count is \(m=2\), and the density is \(2/\binom{4}{2}=2/6=0.333\).

An alternative is to retain the three strongest pairs, regardless of their absolute values. That rule gives \(m=3\) and density \(3/6=0.50\), including the pair with magnitude 0.58. This is not the same as hard thresholding at 0.60: a fixed edge-count rule controls the number of retained pairs, while a correlation threshold controls the minimum magnitude. The fixed-count rule also forces the same number of edges even when all correlations are weak. If ties occur at the selected rank, a tie-handling rule is needed to make the edge count reproducible.

Comparisons and Common Pitfalls

A significance-test cutoff and a correlation-magnitude cutoff answer different questions. A test-based rule retains pairs whose tests meet a specified inferential criterion; its results can depend on sample size and on how multiple comparisons are handled. A magnitude rule retains pairs based on estimated effect size, not on a claim that a null hypothesis has been rejected. Neither rule automatically establishes that retained links are direct or causal. Marginal correlations and conditional links also have different interpretations: a hard threshold applied to marginal correlations does not turn them into conditional associations.

A weighted adjacency approach retains graded edge weights rather than making every retained pair equal to 1; that is a distinct network construction. Here the binary representation is useful when a clear inclusion rule and a sparse set of links are desired, but its simplicity comes at a cost: it discards correlation magnitudes beyond the cutoff and treats correlations just above the threshold the same as much larger ones.

Mistake: “An edge means the genes are significantly associated.” The correction is that the edge means only that the specified estimated-correlation rule was met. Statistical significance requires a separate inferential procedure and appropriate treatment of the testing context.
Mistake: “A negative correlation cannot be retained.” Under the absolute-correlation rule, negative correlations are retained when their magnitudes meet the threshold. A positive-only rule would be a different, explicitly stated construction.
Mistake: “Higher thresholds always make a more reliable biological network.” They do remove edges, but can also remove genuine associations, fragment the graph, and amplify sensitivity to estimation error near the cutoff. A sparse graph is not automatically a better graph.
Mistake: “Density is the fraction of genes with an edge.” Density is the fraction of possible gene pairs retained, \(m/\binom{p}{2}\). The fraction of genes incident to at least one edge is a different quantity.

Hard thresholding is most informative when the correlation rule, threshold, gene universe, and treatment of unavailable pairs are reported together. A threshold sweep can show whether broad conclusions persist or hinge on one arbitrary boundary. It cannot, on its own, resolve uncertainty in the correlations or determine which network representation is scientifically appropriate.

Check Your Understanding

For each question, work out the result before reading its solution.

For three genes with estimated correlations \(r_{12}=0.70\), \(r_{13}=-0.40\), and \(r_{23}=0.55\), construct the adjacency matrix using the absolute-correlation rule at \(\tau=0.50\). Give the density.
With a fixed gene set and fixed correlations, explain why raising \(\tau\) cannot increase density.
A network has six genes and five retained undirected edges. Calculate its density. Does this information alone tell you whether the graph is connected?
Explain why an undefined pairwise correlation should not automatically be entered as a zero before thresholding.

Solutions. (1) The three possible pairs have magnitudes 0.70, 0.40, and 0.55, so pairs 12 and 23 are retained. In gene order 1, 2, 3, \(A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}\). The density is \(2/\binom{3}{2}=2/3=0.667\). (2) If a pair meets the higher threshold, its magnitude also meets every lower threshold. Thus the higher-threshold edge set is a subset of the lower-threshold edge set, so its edge count and density cannot be larger. (3) There are \(\binom{6}{2}=15\) possible pairs, so density is \(5/15=0.333\). The count alone does not specify which pairs are present, so it does not determine connectivity. (4) An undefined correlation is not an estimate of zero association. Replacing it with zero can wrongly treat missing information as evidence that the pair fails the threshold and can distort the graph and its density.