SNF Transition and Local Affinity Matrices

Two Matrices, Two Roles

Similarity Network Fusion (SNF) represents each omics view as a patient-similarity network. Before networks can exchange information, SNF uses two related but distinct matrices: a transition matrix that distributes each row's mass across patients while retaining some mass on the patient itself, and a local affinity matrix that assigns weights to a patient's selected neighbors. Their entries are normalized, but they answer different questions. The transition matrix describes a one-step movement rule on the affinity network; the local affinity matrix describes how strongly each selected neighbor contributes relative to the other selected neighbors.

Assume there are $n$ patients in one omics view. Let $W$ be their affinity matrix: $W_{ij}$ is the nonnegative similarity between patients $i$ and $j$. For the definitions here, assume $W$ is symmetric, has a zero diagonal, and has positive off-diagonal row sums. These conditions are appropriate for an undirected affinity network without self-loops and ensure that the transition normalization is defined. The local matrix also requires each patient to have at least one selected neighbor with positive affinity. A zero row sum requires a separate policy, not division by zero.

Definition: Write $d_i=\sum_{k\ne i}W_{ik}$ for patient $i$'s total affinity to other patients. The SNF transition matrix $P$ is defined by $$ P_{ij}= \begin{cases} \frac{1}{2}, & i=j,\\[4pt] \frac{W_{ij}}{2d_i}, & i\ne j. \end{cases} $$ For a chosen neighborhood $\mathcal{N}_i$ of patient $i$, define the local affinity matrix $S$ by $$ S_{ij}= \begin{cases} \frac{W_{ij}}{\sum_{k\in\mathcal{N}_i}W_{ik}}, & j\in\mathcal{N}_i,\\[4pt] 0, & j\notin\mathcal{N}_i. \end{cases} $$ Here neighborhoods exclude $i$, and only positive-affinity neighbors are included.

The factor of $1/2$ in $P$ gives every patient a diagonal entry of one half and allocates the other half across its off-diagonal affinities. In contrast, $S$ has no diagonal self-weight under this convention: its row is normalized over selected neighbors only. The neighborhood rule must be specified when constructing $S$. For example, it may select the $K$ highest-affinity patients for each row. This row-wise rule can produce different neighbor sets for different patients; an optional symmetrization changes the support and must be stated rather than assumed.

Why the Normalizations Work

Both matrices are row-stochastic when their denominators are positive: their entries are nonnegative and each row sums to one. This makes rows interpretable as distributions of normalized weight. The entries are not, by themselves, calibrated probabilities of a clinical event or evidence of a causal relation.

\sum_{j=1}^{n}P_{ij} =\frac{1}{2}+\sum_{j\ne i}\frac{W_{ij}}{2d_i} =\frac{1}{2}+\frac{d_i}{2d_i} =1.

The same check for $S$ follows directly from its definition: for a nonempty positive-weight neighborhood, $\sum_j S_{ij}=\sum_{j\in\mathcal{N}_i}W_{ij}/\sum_{k\in\mathcal{N}_i}W_{ik}=1$. These checks are also practical diagnostics: a row sum different from one often signals a normalization error, an unintended diagonal entry, or a zero or missing denominator.

Row-stochasticity does not imply symmetry. Even if $W_{ij}=W_{ji}$, the transition entries $P_{ij}$ and $P_{ji}$ use different row totals $d_i$ and $d_j$. The local entries can also differ because each is divided by its own row's neighborhood sum; row-wise neighborhoods may additionally give the two directions different support. Thus $W$ can describe an undirected weighted graph while $P$ and $S$ describe directed, row-normalized weights.

Worked Example: Constructing Both Matrices

Suppose three hypothetical patients have the symmetric affinity matrix $$ W= \begin{pmatrix} 0&0.8&0.2\\ 0.8&0&0.4\\ 0.2&0.4&0 \end{pmatrix}. $$ Use all positive-affinity patients as each patient's neighborhood. Compute $P$ and $S$.

The row totals are $d_1=0.8+0.2=1.0$, $d_2=0.8+0.4=1.2$, and $d_3=0.2+0.4=0.6$. For patient 1, for example, $P_{12}=0.8/(2\times1.0)=0.4$, while $P_{11}=0.5$. Applying the same formula row by row gives $$ P= \begin{pmatrix} 0.5&0.4&0.1\\ 0.3333&0.5&0.1667\\ 0.1667&0.3333&0.5 \end{pmatrix}. $$ Each row sums to one, up to displayed rounding.

For $S$, normalize each row over its neighbors. Patient 1 has weights $0.8$ and $0.2$, whose sum is $1.0$, so its local weights are $0.8$ and $0.2$. Patient 2's denominator is $1.2$, giving $0.8/1.2=0.6667$ and $0.4/1.2=0.3333$. Patient 3's denominator is $0.6$, giving $0.2/0.6=0.3333$ and $0.4/0.6=0.6667$. Therefore, $$ S= \begin{pmatrix} 0&0.8&0.2\\ 0.6667&0&0.3333\\ 0.3333&0.6667&0 \end{pmatrix}. $$

Here $S$ is the full off-diagonal row normalization because every nonzero affinity was selected. In each row, $P$ instead assigns half the weight to the diagonal and half to the off-diagonal distribution. If only a subset of affinities were selected for $\mathcal{N}_i$, $S$ would also be sparse and would renormalize over that subset.

Interpreting the Difference

For a row of $P$, the diagonal value is a self-retention weight: under this construction, one half of the row's total mass stays at the same patient, and the other half is distributed in proportion to all off-diagonal affinities in $W$. For a row of $S$, the entries express the relative allocation among the selected neighbors; the row has no self-weight, and unselected patients receive zero weight. Thus $S$ is local by support, while $P$ includes the fixed diagonal component and uses the off-diagonal affinity distribution.

In the example, patient 2 assigns transition weights $0.3333$ to patient 1 and $0.1667$ to patient 3, alongside $0.5$ to itself. Its local weights are $0.6667$ and $0.3333$ across those neighbors. These numbers are consistent: the transition's neighbor weights are half the local weights because all of patient 2's positive-affinity neighbors were selected. If the neighborhood contains only patient 1, then $S_{21}=1$, even though $P_{21}$ remains $0.3333$. The local matrix answers a relative-neighbor question, not the question of how much of the transition row's mass goes to a particular patient.

The two matrices are inputs to later SNF operations, but they should be understood before those operations are considered. In particular, $S$ should not be mistaken for an alternative estimate of the same transition rule as $P$: its neighborhood restriction and normalization define a different weighting object.

Worked Example: A Symmetric Network Can Give Asymmetric Local Weights

Consider a hypothetical three-patient network with $W_{12}=2$, $W_{23}=1$, and $W_{13}=0$, with symmetric entries and zero diagonal. Let each patient use its positive-affinity neighbors, so $\mathcal{N}_1=\{2\}$, $\mathcal{N}_2=\{1,3\}$, and $\mathcal{N}_3=\{2\}$.

For patient 1, its only selected neighbor has weight 2, so $S_{12}=2/2=1$. For patient 2, the neighborhood sum is $2+1=3$, giving $S_{21}=2/3=0.6667$ and $S_{23}=1/3=0.3333$. Patient 3 has one selected neighbor, so $S_{32}=1/1=1$. Thus $$ S= \begin{pmatrix} 0&1&0\\ 0.6667&0&0.3333\\ 0&1&0 \end{pmatrix}. $$

Although $W_{12}=W_{21}=2$, the normalized values are $S_{12}=1$ and $S_{21}=0.6667$. The first denominator is patient 1's local total, 2; the second is patient 2's local total, 3. The asymmetry is a consequence of row normalization, not evidence that the original pairwise affinity was asymmetric.

Construction Checks and Common Alternatives

Before using either matrix, verify the assumptions and inspect the construction. In each view, confirm that the affinity scale is nonnegative, that the diagonal convention is applied consistently, and that all required row denominators are positive. For $S$, verify that every patient has at least one selected neighbor with positive weight, and that the selected support matches the intended neighborhood rule. If a row has no positive affinity, its normalized weights are undefined; adding a small constant or assigning an arbitrary self-loop changes the method and should not be done silently.

The diagonal convention matters. If $W_{ii}$ is nonzero but is included in the off-diagonal total $d_i$, the transition row no longer has the stated half-self, half-neighbor interpretation. Under the definitions here, set $W_{ii}=0$ and handle the transition diagonal separately. Likewise, including $i$ in $\mathcal{N}_i$ would give $S$ a self-weight and change its interpretation.

A common alternative is simple row normalization of all affinities, $W_{ij}/d_i$ off the diagonal, with no special diagonal mass. That alternative is row-stochastic but does not have the fixed self-retention of $P$. Another option is symmetric degree normalization, often written $D^{-1/2}WD^{-1/2}$, where $D$ contains row sums. This can preserve symmetry when $W$ is symmetric, but its rows generally do not sum to one, so it is not the same transition matrix. These alternatives may be useful for other purposes, but substituting them changes the interpretation and is not an innocuous numerical adjustment.

Worked Example: Localizing a Row to One Neighbor

Suppose a hypothetical patient's affinities to three other patients are $0.7$, $0.2$, and $0.1$, and the neighborhood rule selects only the first patient. Compute the patient's local row and transition row entries for these four patients, including the diagonal.

The total off-diagonal affinity is $d_i=0.7+0.2+0.1=1.0$. The transition row has diagonal value $0.5$, and its off-diagonal entries are $0.7/(2\times1.0)=0.35$, $0.2/(2\times1.0)=0.10$, and $0.1/(2\times1.0)=0.05$. Its row sum is $0.5+0.35+0.10+0.05=1.0$.

The local neighborhood contains only the affinity $0.7$, so its neighborhood total is $0.7$. The local row assigns $0.7/0.7=1$ to the selected patient and zero to the other two patients and to itself. The contrast is deliberate: $P$ reflects all off-diagonal affinities plus fixed self-retention, whereas $S$ reflects allocation within the selected local neighborhood.

Diagnostics and Limitations

Useful checks include examining row sums, diagonal entries, sparsity, and the distribution of local neighborhood sizes. A row sum far from one suggests an implementation error or rounding beyond what is reasonable. Nonzero diagonal entries in $S$ conflict with the convention used here. A dense $S$ may indicate that the neighborhood restriction was not applied; a row with too few selected neighbors may indicate a tie-handling or indexing issue. It is also helpful to compare $S_{ij}$ with $S_{ji}$: large differences can be expected when row totals or neighborhoods differ, but unexpected asymmetry in the underlying $W$ should be checked separately.

These constructions do not resolve weaknesses in the original affinities. If the distance or similarity measure is poorly chosen, if patient profiles have been scaled inappropriately, or if the neighborhood rule is unstable, normalization will not repair the underlying problem. The fixed diagonal mass in $P$ also does not guarantee that all patients are equally well connected: a weakly connected patient still distributes its non-self mass over a potentially poor set of neighbors. Finally, row-normalized entries are relative weights within their respective rows, so comparing an entry from one row directly with an entry from another requires care.

Key takeaway: $P$ is a row-stochastic transition matrix with fixed half-mass on the diagonal and the remaining mass distributed across off-diagonal affinities. $S$ is a row-stochastic, neighborhood-restricted weighting matrix with zero diagonal. Their normalization and support—not merely their names—determine their distinct roles.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

If $d_i=4$ and $W_{ij}=1.2$ for $j\ne i$, what is $P_{ij}$? What is the diagonal entry $P_{ii}$?
A patient has selected-neighbor affinities $0.6$ and $0.4$. What are the two nonzero entries in that row of $S$?
Why can $S_{ij}\ne S_{ji}$ even when $W_{ij}=W_{ji}$?
What is wrong with normalizing an $S$ row when its selected neighbors all have zero affinity?

Solutions. (1) $P_{ij}=1.2/(2\times4)=0.15$, and $P_{ii}=0.5$. (2) The neighborhood total is $0.6+0.4=1.0$, so the local entries are $0.6$ and $0.4$. (3) The two entries use different row-specific denominators, $\sum_{k\in\mathcal{N}_i}W_{ik}$ and $\sum_{k\in\mathcal{N}_j}W_{jk}$; different totals can produce different normalized values. (4) Its denominator is zero, so the normalized row is undefined. The neighborhood or an explicit isolate-handling policy must be revised rather than dividing by zero.