Handling Diagonals, Ties, and Disconnected Nodes

Why Small Network Conventions Matter

In a patient similarity network, a diagonal entry compares a patient with themself; an off-diagonal entry represents a relationship between distinct patients. These values have different roles. A large diagonal can be a valid self-similarity in a kernel, but it should not be mistaken for evidence connecting that patient to another. Tied neighbor distances and isolated patients create a related challenge: implementation choices can change the graph even when the underlying distances are unchanged.

This tutorial sets out practical conventions for sparse affinities and their use in Similarity Network Fusion (SNF). It assumes that distances have been chosen, local scales and affinities have been constructed, and the basic diffusion update is familiar. The key is to make edge-selection and diagonal policies explicit before normalizing or iterating. Otherwise, self-weights can consume neighborhood slots, ties can be broken invisibly, and a zero-degree row can make a transition matrix undefined.

Separate Self-Similarity From Patient-to-Patient Edges

A kernel or a dense similarity matrix may have \(K_{ii}=1\), or another positive self-similarity, by construction. A sparse affinity graph often instead begins with \(W_{ii}=0\), because its purpose is to record selected relationships between distinct patients. These are not contradictory conventions: the matrices serve different purposes. The important rule is not to let a diagonal entry silently count as a neighbor or as evidence of a between-patient edge.

For K-nearest-neighbor selection, exclude patient \(i\) from their own candidate list. If a matrix with a positive diagonal is used directly, the self-entry may rank first and take one of the \(K\) available slots. That leaves fewer than \(K\) other patients, even though the intended neighborhood size referred to other patients. Set the diagonal aside before ranking distances or similarities. If a diagonal is retained in an intermediate matrix, document its role and ensure the neighbor-selection code excludes it.

A useful distinction in SNF is between the sparse affinity \(W^{(v)}\) and the local transition matrix \(S^{(v)}\). In a common convention, \(W^{(v)}\) has zero diagonal at initialization, while \(S^{(v)}\) assigns a fixed amount of mass to the patient themself. For example, if the selected neighbors of \(i\) have positive total affinity, set \(S^{(v)}_{ii}=1/2\) and distribute the other half among those neighbors in proportion to their affinities. This diagonal is a deliberate self-retention term in a diffusion operator; it is not a patient-to-patient edge. Iterated affinities may also acquire diagonal mass. Do not interpret that mass as an observed connection between distinct patients, and do not remove it midway through an algorithm unless the chosen algorithm explicitly requires that step.

Tied Distances at the Neighborhood Boundary

For a patient \(i\), order the distances to the other \(n-1\) patients from smallest to largest. With target neighborhood size \(K\), a boundary tie occurs when two or more patients have the same distance as the \(K\)th closest patient. There is no data-based reason to prefer one of those equally distant patients. A software tie-break based on row order or patient identifier is deterministic, but it adds an arbitrary choice to the graph.

Two defensible policies are common. A tie-inclusive policy includes every patient whose distance is no greater than the \(K\)th order statistic; the realized neighborhood can therefore contain more than \(K\) patients. A fixed-size policy selects exactly \(K\), using a declared, reproducible secondary rule. Tie inclusion avoids excluding an equally distant patient merely to meet an exact count, but can increase degrees, particularly in data with rounded distances or duplicate profiles. Fixed size controls the number of selected neighbors, but the secondary rule can create artificial differences between patients. State the policy and assess whether conclusions depend on it.

The directed neighbor relation also needs a rule for making an undirected network. Under a union rule, retain an edge if either patient selects the other. Under a mutual rule, retain it only if both select each other. The union rule is less likely to discard a relationship selected by one endpoint, but may produce higher degrees. The mutual rule is more restrictive and can create isolated nodes even when each patient had selected neighbors. For a symmetric affinity graph, apply the chosen rule to the neighbor sets and then assign a symmetric edge weight, for example by using the original symmetric affinity. Normalize only after this construction: the row sums depend on both the tie policy and the symmetrization rule.

Isolated Patients and Row Normalization

Given a nonnegative affinity matrix with zero diagonal, the usual row-normalized transition is \(P_{ij}=W_{ij}/\sum_{k\ne i}W_{ik}\). This is defined only when the off-diagonal row sum is positive. For an isolated patient, the denominator is zero, so neither division by zero nor replacing the resulting undefined values with zeros produces a row-stochastic transition. A zero row has total probability mass zero, not one.

First verify that isolation is real rather than an implementation failure. Check that self-similarity was excluded from the neighbor search, that distances and affinities are finite, that the similarity threshold has not removed every edge, and that a mutual-neighbor rule has not removed all of the patient's edges. In local scaling, also check whether a scale parameter became zero because several distances were exactly zero; a formula that divides by a zero scale needs a declared duplicate-profile or scale-floor policy. These checks distinguish a genuinely unsupported patient from a numerical or coding problem.

If a patient is genuinely isolated, there is no universally correct way to infer missing connections. A practical option for a transition matrix is to assign that row an absorbing self-transition, \(P_{ii}=1\), and \(P_{ij}=0\) for \(j\ne i\). This yields a valid stochastic row and says that, in this view, the patient has no supported move to another patient. It is a computational convention, not evidence of self-similarity or a newly observed edge. Keep an isolation indicator and exclude the artificial diagonal from summaries of between-patient graph structure.

For the local diffusion matrix \(S^{(v)}\), one compatible convention is \(S^{(v)}_{ii}=1\) for an isolated row and zero elsewhere in that row. This avoids dividing by a zero neighbor-affinity sum and preserves row stochasticity. If the standard non-isolated convention assigns \(1/2\) to the diagonal and \(1/2\) across neighbors, its row sums are one because

provided \(N_i\) is nonempty and the neighbor affinities have positive sum. For an empty neighborhood, the \(1/2\)-plus-neighbors formula cannot apply; assigning the full unit mass to the diagonal is the stated fallback.

How the Conventions Affect SNF Iteration

A common SNF update for view \(v\) combines its local operator \(S^{(v)}\), the average transition information from the other views, and the transpose of its local operator. In schematic form, at iteration \(t\),

where \(V>1\) is the number of views and each transition matrix must be defined under the implementation's row policy. This expression illustrates why a diagonal convention matters: \(S^{(v)}\) spreads information through each patient's local neighborhood, and its diagonal controls how much information remains at that patient. Tie handling changes the neighborhoods and their normalized weights; an isolated-node fallback changes a row used in the update. Neither choice is a harmless formatting detail.

The update may produce positive diagonal entries even if the initial sparse affinity had a zero diagonal. Retain or remove those entries according to the specified SNF implementation, not as an undocumented cleanup step. When inspecting the resulting graph as a network of distinct patients, report off-diagonal structure separately from diagonal retention. Similarly, if one view isolates a patient but other views connect that patient, fused information may support between-patient links. Do not claim those links came from the isolated view. If isolation should persist in that view, preserve an appropriate mask or freeze its unsupported relationships; if cross-view recovery is allowed, describe that interpretation and check that the update does not treat the artificial self-loop as observed evidence.

A short diagnostic sequence helps make these choices auditable:

Choosing and Reporting a Policy

There is no single convention that is best for every data set. Tie inclusion is transparent when distances are genuinely equal, while fixed-size selection is useful when a strict computational bound is required. Union symmetrization retains one-sided selections; mutual symmetrization demands reciprocal selection but can increase the number of isolates. An absorbing self-transition is convenient for a stochastic matrix, while leaving a node unmodeled or using an explicitly justified alternative may better match some applications. Whatever the choice, use it consistently across views and iterations, and report it so another analyst can reproduce the network.

A common mistake is to say, “The diagonal is one, so that patient has a strong self-edge; I will count it as a neighbor and then normalize the row.” This mixes self-similarity with between-patient evidence and may displace a real neighbor from the selected set. The correction is to exclude the diagonal from neighbor selection and off-diagonal degree calculations, while retaining a diagonal only where the specified kernel or diffusion method requires it. A related error is to replace a zero row with zeros and call it a transition distribution. A transition row must sum to one; either apply a stated fallback and mark it, or use a method that explicitly accommodates missing transitions.