From Fused Similarities to Patient Edges
A fused kernel summarizes pairwise patient similarity across omics views, but a dense matrix is not yet a sparse network. In a dense matrix, nearly every patient pair has an entry; a graph instead retains selected pairs as edges. This conversion is a modeling choice: the edge rule determines which relationships remain visible, and the symmetrization rule determines how an undirected network is formed.
Let \(K\) be the fused similarity matrix for \(n\) patients, with entry \(K_{ij}\) describing the similarity of patients \(i\) and \(j\). This tutorial assumes the matrix has finite entries and is symmetric, so \(K_{ij}=K_{ji}\). Larger values must represent greater similarity. The diagonal describes self-similarity and is excluded from edge selection: a patient is not connected to themself. The rules below also require nonnegative edge weights. A positive threshold ensures this for thresholding; for nearest-neighbor selection, only positive similarities are eligible. If a kernel contains negative values, they should not be silently treated as ordinary positive edge weights.
The graph conversion does not require the resulting adjacency matrix to be a positive semidefinite kernel. Positive semidefiniteness is a property useful for kernel methods; an adjacency matrix serves a different purpose. Nor does retaining an edge establish a causal or biological interaction. It records similarity under a specified selection rule.
Global Thresholding
Thresholding uses one cutoff for all patient pairs. Choose a positive threshold \(\tau\), omit the diagonal, and retain a pair when its fused similarity reaches or exceeds the cutoff. This is an absolute rule: the same similarity value is treated alike regardless of how many other strong neighbors either patient has.
Because \(K\) is symmetric, the threshold condition is identical for \(K_{ij}\) and \(K_{ji}\), so \(W^{(\tau)}\) is symmetric. A positive \(\tau\) also ensures that every retained weight is positive. Raising \(\tau\) can only remove edges, not add them. This makes thresholding straightforward to interpret, but a single cutoff can leave patients with very different degrees, including isolated patients.
Worked Example: Thresholding a Four-Patient Kernel
Suppose a hypothetical fused kernel for four patients has diagonal entries equal to 1 and the following off-diagonal similarities: \(K_{12}=0.82\), \(K_{13}=0.31\), \(K_{14}=0.12\), \(K_{23}=0.55\), \(K_{24}=0.28\), and \(K_{34}=0.74\). Symmetry supplies the corresponding entries in the other triangle. Choose \(\tau=0.50\).
The rule retains a pair exactly when \(K_{ij}\ge 0.50\). Thus \(K_{12}=0.82\), \(K_{23}=0.55\), and \(K_{34}=0.74\) pass; the other three similarities are below the cutoff. In patient order 1 through 4, the weighted adjacency matrix is
For example, patient 2 has weighted degree, also called strength, \(0.82+0.55=1.37\). There are 3 retained edges among the \(\binom{4}{2}=6\) possible pairs, so the graph density is \(3/6=0.500\). The matrix is symmetric, as required for an undirected graph.
Nearest-Neighbor Selection and Symmetrization
A \(k\)-nearest-neighbor rule chooses neighbors separately for each patient. For each row \(i\), rank the eligible off-diagonal similarities \(K_{ij}\) and select up to the \(k\) largest positive ones. This initially defines directed choices: patient \(i\) may select \(j\) without \(j\) selecting \(i\). An undirected graph therefore needs an explicit symmetrization rule.
These definitions preserve symmetry: the union condition is unchanged when \(i\) and \(j\) are exchanged, and so is the mutual condition. The union graph has at least as many edges as the mutual graph for the same directed selections. Union selection protects against isolated patients more than mutual selection does, but can include edges that are not among the recipient patient's own top \(k\). Mutual selection is more conservative and may leave patients disconnected.
Ties at the \(k\)th rank need a stated policy. One option is to include every patient tied at that rank, which can produce more than \(k\) directed selections for a row. Another is a reproducible tie-break rule, which preserves a strict upper bound of \(k\) but can make the graph depend on that rule. If a patient has fewer than \(k\) positive eligible similarities, select only those available; do not invent edges to fill the quota.
Worked Example: Union and Mutual k-Nearest-Neighbor Graphs
For a hypothetical five-patient kernel, suppose the off-diagonal similarities are \(K_{12}=0.80\), \(K_{13}=0.50\), \(K_{14}=0.10\), \(K_{15}=0.20\), \(K_{23}=0.60\), \(K_{24}=0.55\), \(K_{25}=0.15\), \(K_{34}=0.70\), \(K_{35}=0.45\), and \(K_{45}=0.65\). Let \(k=1\), with no ties.
The largest off-diagonal entry in row 1 is \(0.80\), so \(N_1(1)=\{2\}\). Row 2 selects patient 1 because \(0.80\) is its largest entry. Row 3 selects patient 4 at \(0.70\); row 4 selects patient 3 at \(0.70\); and row 5 selects patient 4 at \(0.65\). Thus the directed selections are \(1\to2\), \(2\to1\), \(3\to4\), \(4\to3\), and \(5\to4\).
Under the union rule, the undirected edges are \(\{1,2\}\), \(\{3,4\}\), and \(\{4,5\}\). Their weights are respectively \(0.80\), \(0.70\), and \(0.65\). Under the mutual rule, \(\{4,5\}\) is omitted because patient 4 did not select patient 5. Patients 1 and 2, and patients 3 and 4, remain paired; patient 5 is isolated. This example shows why the symmetrization choice can matter even when the original similarity matrix is symmetric.
Comparing the Rules and Checking the Result
Thresholding and nearest-neighbor selection answer different questions. A threshold asks whether a pair has a sufficiently large absolute similarity. A \(k\)-nearest-neighbor rule asks whether a pair ranks highly relative to at least one patient's other similarities (union) or to both patients' similarities (mutual). Neither rule is universally preferable.
| Choice | What controls edge selection | Typical structural consequence |
|---|---|---|
| Global threshold | One similarity cutoff \(\tau\) | Similarities are comparable on one scale; degrees can vary widely or be zero |
| kNN union | Top \(k\) choices by either endpoint | Retains more edges than mutual selection; often limits isolation |
| kNN mutual | Top \(k\) choices by both endpoints | More selective; may be disconnected or have isolated patients |
For a simple structural check, the density of an undirected graph with \(m\) edges and \(n\) patients is \(m/\binom{n}{2}\). The strength of patient \(i\) is the sum of their incident edge weights, \(\sum_{j\ne i}W_{ij}\); their degree is the number of incident edges with positive weight. These summaries help reveal whether a choice has produced a nearly dense graph, unexpected isolates, or a small number of unusually connected patients. They are diagnostics, not evidence that one graph is biologically correct.
A useful justification for the symmetrization step is direct. Define \(a_{ij}=1\) when \(j\in N_k(i)\), and \(a_{ij}=0\) otherwise. Under union selection, the edge indicator is \(e_{ij}=\max(a_{ij},a_{ji})\). Exchanging \(i\) and \(j\) leaves this expression unchanged, so \(e_{ij}=e_{ji}\). Under mutual selection, \(e_{ij}=a_{ij}a_{ji}\), which is also unchanged by exchanging the indices. If the edge weight is \(e_{ij}K_{ij}\), symmetry of \(K\) then gives \(W_{ij}=W_{ji}\) in either construction.
Confirm that the matrix indexes the same patients in both dimensions, is symmetric up to numerical precision, and uses larger values for greater similarity. Exclude the diagonal from neighbor ranking.
For thresholding, report \(\tau\). For kNN, report \(k\), the positive-similarity eligibility rule, tie policy, and whether union or mutual symmetrization is used.
Set unselected entries to zero, retain the original fused similarity as the edge weight, enforce a zero diagonal, and check symmetry, density, degrees, strengths, and isolates.
Worked Comparison and Failure Modes
Worked Example: Comparing a Cutoff with kNN
Consider a hypothetical four-patient kernel with off-diagonal similarities \(K_{12}=0.80\), \(K_{13}=0.45\), \(K_{14}=0.20\), \(K_{23}=0.60\), \(K_{24}=0.35\), and \(K_{34}=0.70\). Use threshold \(\tau=0.60\), including equality, and compare it with \(k=1\) followed by union symmetrization.
Thresholding retains \(K_{12}=0.80\), \(K_{23}=0.60\), and \(K_{34}=0.70\). Thus \(m=3\) and density is \(3/\binom{4}{2}=3/6=0.500\). The strengths are \(s_1=0.80\), \(s_2=0.80+0.60=1.40\), \(s_3=0.60+0.70=1.30\), and \(s_4=0.70\).
For \(k=1\), patients 1 and 2 select each other through the \(0.80\) similarity; patient 3 selects patient 4 through \(0.70\); and patient 4 selects patient 3 through \(0.70\). The union graph therefore has edges \(\{1,2\}\) and \(\{3,4\}\), with weights \(0.80\) and \(0.70\). Its density is \(2/6=0.333\), and its strengths are \(0.80, 0.80, 0.70,\) and \(0.70\). The two rules disagree because thresholding retains the \(0.60\) edge between patients 2 and 3, whereas that pair is not a top-one choice for either endpoint.
Several diagnostics are especially important. First, verify \(W=W^\mathsf{T}\) and \(W_{ii}=0\); a failure usually indicates inconsistent index handling or a symmetrization bug. Second, inspect the number of edges, degree distribution, isolates, and weight distribution. A threshold can yield no edges if it is too high, while a low threshold can produce a nearly dense graph. A very small \(k\) may fragment the graph; a large \(k\) can erase the intended sparsity. Third, check for negative or non-finite entries before selection. Negative centered similarities are not ordinary positive edge weights, and missing values cannot be ranked reliably without an explicit policy.
A common mistake is to apply a row-wise kNN rule and call the result an undirected graph without symmetrizing it. The directed selection can have \(a_{ij}\ne a_{ji}\), even when the kernel itself is symmetric; the correction is to choose and report union or mutual symmetrization. Another mistake is to assume that a fixed \(k\) produces exactly \(k\) undirected edges per patient. It does not: union can increase degrees beyond \(k\), mutual can reduce them, and ties or too few eligible positive similarities also alter counts.
The threshold rule is easy to interpret when kernel values are meaningfully calibrated across patients, but its density depends on the similarity scale and cutoff. The kNN rule adapts to local rankings, but can connect a patient to a comparatively weak neighbor when all of that patient's similarities are low. Neither rule removes the need to assess graph structure or sensitivity to parameter choices. A graph is a simplified representation of the fused similarities, not a lossless replacement for the kernel matrix.
Check Your Understanding
Answer each question, then compare with the solutions below.
- A symmetric kernel has \(K_{12}=0.40\) and \(K_{21}=0.40\). With threshold \(\tau=0.50\), is the pair retained? What changes if the rule is \(K_{ij}>0.50\)?
- In a directed kNN selection, patient 1 selects patient 2 but patient 2 does not select patient 1. Which symmetrization rule retains the pair?
- With \(n=5\) patients, a threshold graph has 4 undirected edges. What is its density?
- Why can a mutual kNN graph contain an isolated patient even when that patient selected \(k\) neighbors?
Solutions. (1) The pair is not retained under \(K_{ij}\ge0.50\), because \(0.40<0.50\); it is also not retained under the strict rule \(K_{ij}>0.50\). (2) Union retains the pair because at least one endpoint selected the other; mutual omits it because both did not select each other. (3) There are \(\binom{5}{2}=5(4)/2=10\) possible undirected pairs, so density is \(4/10=0.400\). (4) Mutual selection requires the patient to be selected in return by each retained neighbor. If none of the patients they selected also selected them, no incident edge remains and they are isolated.