From Pairwise Scores to a Sparse Graph
A pairwise similarity matrix records how alike every pair of patients is, but a dense matrix can obscure the local relationships of interest: most patients may have a recorded score with every other patient. A sparse affinity graph keeps only selected relationships. Its nodes are patients, its edges indicate retained relationships, and its edge weights represent the strength of those relationships. Sparsification is therefore not just a computational shortcut. The neighborhood rule determines which relationships the graph treats as relevant.
This tutorial starts with a symmetric similarity score \(s_{ij}\) for each pair of distinct patients \(i\) and \(j\). For a conventional weighted affinity graph, assume the scores are finite and nonnegative, with larger values meaning greater similarity. We also assume \(s_{ij}=s_{ji}\). If scores are distances, their ordering must first be converted so that larger values represent closer pairs; the distance-to-similarity choice is a separate modeling decision. Similarities obtained through local scaling can be used as the input scores when they satisfy the symmetry and nonnegativity conditions.
The directed selections must be turned into an undirected graph if the desired affinity matrix is symmetric. Two common rules are the union rule, which retains an edge if either endpoint selects the other, and the mutual rule, which retains an edge only if both endpoints select each other. Unless stated otherwise, the weight of a retained edge is the original symmetric similarity \(s_{ij}\), and a non-retained pair receives weight zero.
What the Symmetrization Rule Changes
The union rule favors coverage: a patient can retain a connection to a highly similar neighbor even when that neighbor has other, still closer options. The mutual rule favors reciprocal local closeness: a connection survives only when each patient ranks the other among its neighbors. This can reduce weak or one-sided links, but it can also leave some patients with very few or no edges.
Both matrices are symmetric. For the union rule, exchanging \(i\) and \(j\) leaves the condition “either endpoint selects the other” unchanged; for the mutual rule, it leaves “both endpoints select each other” unchanged. The weight is also unchanged because \(s_{ij}=s_{ji}\). Thus \(W_{ij}=W_{ji}\) under either rule. With exactly \(k\) selected neighbors per patient and no cutoff ties, the directed selections contain \(nk\) directed links. The number of union edges is at least \(nk/2\), because an undirected edge accounts for at most two directed links, and at most \(nk\), because every union edge requires at least one directed link. A mutual graph has at most \(nk/2\) edges, since each of its edges requires two directed selections. These bounds need not hold as stated when ties cause patients to select more than \(k\) neighbors.
Worked Example: Applying Union and Mutual Retention
Suppose five hypothetical patients have the following symmetric similarities. The diagonal is omitted because self-comparisons do not determine neighbors.
| Pair | Similarity |
|---|---|
| A–B | 0.90 |
| A–C | 0.70 |
| A–D | 0.20 |
| A–E | 0.10 |
| B–C | 0.60 |
| B–D | 0.50 |
| B–E | 0.10 |
| C–D | 0.80 |
| C–E | 0.20 |
| D–E | 0.75 |
Set \(k=2\). Ranking each patient's four other patients by similarity gives \(N_2(A)=\{B,C\}\), \(N_2(B)=\{A,C\}\), \(N_2(C)=\{D,A\}\), \(N_2(D)=\{C,E\}\), and \(N_2(E)=\{D,C\}\). For example, C selects D at 0.80 and A at 0.70; B at 0.60 is third in C's ranking.
Under union retention, an edge is included if at least one endpoint selects the other. The retained pairs are AB, AC, BC, CD, CE, and DE. Their weights are respectively 0.90, 0.70, 0.60, 0.80, 0.20, and 0.75. Under mutual retention, only AB and CD survive: A and B select each other, and C and D select each other. Their weights are 0.90 and 0.80. The difference is not a change in the similarity scores; it is the consequence of the edge-retention rule.
Ties at the Neighborhood Boundary
If several patients share the similarity score at the \(k\)th position, the phrase “the \(k\) nearest neighbors” does not identify a unique set of exactly \(k\) patients. There are two standard responses. A fixed-size rule selects exactly \(k\), resolving a boundary tie through a stated, reproducible convention. An inclusive rule selects every patient whose similarity is at least the \(k\)th-largest score, so the set may contain more than \(k\) patients. Neither convention is universally correct; the choice should match the analysis goal and be reported.
A deterministic ordering, such as sorting by a stable patient identifier after sorting by similarity, makes a fixed-size result reproducible. But the identifiers have no similarity meaning: if they decide a tie, the chosen edge is partly an artifact of the ordering. Including all boundary ties avoids arbitrarily separating patients with equal scores, but it no longer guarantees exactly \(k\) selections per patient and may increase graph density. Whichever policy is used, apply it consistently before symmetrizing; otherwise the retained edges are difficult to reproduce or interpret.
Worked Example: Two Valid Tie Policies
Consider three hypothetical patients with \(s_{AB}=0.80\), \(s_{AC}=0.80\), and \(s_{BC}=0.20\), and set \(k=1\). Patient A has a tie between B and C for its nearest neighbor. B's nearest neighbor is A, and C's nearest neighbor is A.
With a fixed-size rule that breaks A's tie in favor of B, the directed sets are \(N_1(A)=\{B\}\), \(N_1(B)=\{A\}\), and \(N_1(C)=\{A\}\). Mutual retention gives AB, because A and B select one another, but not AC, because A did not select C. The mutual matrix has \(W^{\mathrm{M}}_{AB}=W^{\mathrm{M}}_{BA}=0.80\) and all other off-diagonal entries zero.
With the inclusive boundary-tie rule, \(N_1(A)=\{B,C\}\), while \(N_1(B)=\{A\}\) and \(N_1(C)=\{A\}\). Now mutual retention gives both AB and AC, each with weight 0.80. Patient A has two selected neighbors although \(k=1\). The difference illustrates why a report should specify both the tie policy and the symmetrization rule.
Thresholds, Weights, and Practical Diagnostics
A \(k\)-nearest-neighbor rule controls how many outgoing selections each patient makes, not the minimum strength of a retained relationship. A similarity threshold \(\tau\) can be added by requiring \(s_{ij}\geq\tau\) as well as the chosen neighbor rule. This can remove weak edges, but it can also produce patients with fewer than \(k\) retained edges or no edges at all. The threshold is a distinct modeling choice from \(k\); changing either can change graph structure.
Worked Example: A Threshold Can Create Isolated Patients
For four hypothetical patients, suppose the similarities are \(s_{PQ}=0.82\), \(s_{PR}=0.44\), \(s_{PS}=0.12\), \(s_{QR}=0.51\), \(s_{QS}=0.30\), and \(s_{RS}=0.77\). Use \(k=1\). The nearest-neighbor sets are \(N_1(P)=\{Q\}\), \(N_1(Q)=\{P\}\), \(N_1(R)=\{S\}\), and \(N_1(S)=\{R\}\). Both union and mutual retention therefore give edges PQ with weight 0.82 and RS with weight 0.77.
Now add the threshold \(\tau=0.80\). Retain an edge only if its score is at least 0.80. Since \(0.82\geq0.80\), PQ remains; since \(0.77<0.80\), RS is removed. The resulting graph has one edge of weight 0.82 and two isolated patients, R and S. This is not an arithmetic error: it is a direct consequence of imposing a threshold that is stronger than the neighborhood rule alone.
Useful diagnostics include the number of connected components, the number of isolated nodes, the distribution of node degrees, and the range of retained edge weights. Compare these summaries under plausible values of \(k\), under union versus mutual retention, and under any proposed threshold. A sudden increase in isolated nodes under the mutual rule, for example, signals that reciprocal neighborhoods are rare at the chosen \(k\). A graph with almost every pair retained is not meaningfully sparse; a graph split into many tiny components may fail to represent relationships across the cohort. These checks describe the graph that was constructed, not whether the similarities capture valid biology.
Choosing a Construction Rule
| Construction | What it retains | Typical consequence |
|---|---|---|
| Union \(k\)-nearest neighbors | At least one endpoint selects the other | Greater coverage; may retain one-sided links and increase degree. |
| Mutual \(k\)-nearest neighbors | Both endpoints select each other | More selective; may reduce weak links but create isolated nodes. |
| Similarity-threshold graph | Pairs exceeding a fixed score threshold | Uses an absolute score cutoff; degrees can vary widely or be zero. |
| Dense similarity matrix | Every pair receives a weight | Preserves all pairwise scores but does not provide sparsity. |
The union and mutual rules are alternatives to a threshold-only graph, not automatic improvements over it. A fixed threshold has a direct score-scale interpretation but may behave unevenly across patients when their similarity distributions differ. A \(k\)-nearest-neighbor rule adapts the number of local selections to each patient's ranking, but it can keep weak links in sparse regions. If local scaling was used to account for uneven patient densities, the resulting scores may help make local rankings more comparable; it does not remove the need to specify \(k\), edge retention, and tie handling.
The resulting affinity matrix is a representation of selected pairwise relationships. It does not establish that an edge is causal, nor does a zero entry prove that two patients are biologically unrelated. Sparsification discards information by design, and its results can be sensitive to score construction, \(k\), tie policy, symmetrization, and thresholding. Record these choices and inspect their consequences before using the graph in a downstream method.
A Practical Construction Sequence
A reliable workflow separates ranking, tie resolution, edge retention, and weighting. Doing so makes it clear which choice produced each part of the graph.
Confirm that the pairwise scores are symmetric, finite, and oriented so that larger values mean greater similarity. Exclude self-comparisons from neighbor ranking.
For each patient, rank the other patients and select the top \(k\), stating whether boundary ties are broken to keep exactly \(k\) or all included.
Choose union or mutual retention, then assign each retained edge its pairwise similarity score. Set non-retained off-diagonal entries to zero.
Check symmetry, degree and component summaries, isolated nodes, and retained weight values. Repeat under reasonable alternative choices if conclusions depend on them.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- If \(j\in N_k(i)\) but \(i\notin N_k(j)\), which of the union and mutual rules retain the pair?
- With \(k=3\), a patient has four others tied at the third-largest similarity. What is the consequence of including all boundary ties?
- Why can a mutual graph have an isolated patient even when each patient's directed neighborhood contains exactly \(k\) patients?
- In a symmetric similarity matrix, what weight is assigned to a retained edge under the convention used here?
- What should be checked if a similarity threshold is added to a \(k\)-nearest-neighbor graph?
Solutions. (1) The union rule retains the pair because one endpoint selected the other; the mutual rule does not, because the selection is not reciprocal. (2) The patient selects four neighbors rather than exactly three, so its directed degree can exceed \(k\), and the symmetrized graph can become denser. (3) Mutual retention requires other patients to select that patient as well; if none do, no edge incident to the patient survives. (4) The retained edge receives its original pairwise similarity \(s_{ij}\), with the same value in both symmetric matrix entries. (5) Check whether low-scoring selected edges are removed, how many nodes become isolated, and whether the number of components or degree distribution changes substantially.