Why Weight an Edge by Neighborhood Similarity?
A cell-neighborhood graph records which pairs of cells are connected, but an unweighted edge treats every connection alike. Two cells may be connected even though their neighbor lists overlap little, while another pair may have many of the same nearby cells. Assigning a weight based on that overlap gives the graph a way to distinguish those relationships. This tutorial develops three choices: a binary shared-neighbor weight, the Jaccard similarity, and a rank-based score.
The weights depend on neighbor lists already constructed from cell profiles. As in the earlier material on shared nearest-neighbor graphs, the key comparison is between the lists for two cells, not between their expression profiles directly. A weight therefore describes agreement in the local neighborhoods produced by the chosen distance metric and neighbor count; it is not a probability that two cells have the same biological identity.
For the definitions below, assume that every neighbor list has the same size \(k\), and that the ranks in each list are ordered from 1 (nearest) to \(k\) (farthest). If distances tie, a deterministic tie-breaking rule is needed to assign ranks. The formulas are symmetric in \(i\) and \(j\), so they give the same weight whichever cell is named first. A weight of zero can be represented as no edge; alternatively, an implementation may retain a zero-weight candidate edge, but it contributes no positive connection strength.
Three Weighting Schemes
The binary scheme asks only whether there is any overlap. The Jaccard scheme measures the fraction of distinct neighbors that the lists have in common. The rank-based scheme also accounts for where shared cells appear in the two ordered lists. For a precise rank-based calculation, use the following rank-weighted overlap score. It assigns more credit when a shared neighbor is highly ranked in both lists.
Here \(\mathbf{1}(c_{ij}>0)\) equals 1 when the lists share at least one neighbor and equals 0 otherwise; \(r_i(u)\) is the rank of neighbor \(u\) in cell \(i\)'s list. The binary weight retains only the existence of overlap. Jaccard similarity retains its relative size: with equal list sizes, \(|N_i\cup N_j|=2k-c_{ij}\). The rank-based score gives a shared neighbor more contribution when its rank is better in both lists, using the worse of its two ranks.
The denominator in \(R_{ij}\) scales the score to the interval from 0 to 1. For any shared neighbor \(u\), its contribution is nonnegative and at most \(k+1-r_i(u)\). Summing this upper bound over the ranks in \(N_i\) gives \(k+(k-1)+\cdots+1=k(k+1)/2\). Thus \(0\leq R_{ij}\leq1\). Identical lists with identical rankings receive score 1; a pair with no shared neighbors receives score 0.
This rank-based formula is one explicit rank-weighted overlap choice, not a universal definition of every rank-based graph weight. When using a software implementation, check its exact score and normalization rather than assuming that all methods called “rank-based” use the same formula.
Worked Calculations
Worked Example: Computing All Three Weights
Suppose \(k=4\). Cell A has the neighbor list \(\{u,v,w,x\}\), and cell B has the list \(\{v,u,q,w\}\). The listed order is nearest to farthest. Calculate each weight for the pair.
The shared neighbors are \(\{u,v,w\}\), so \(c_{AB}=3\). The union is \(\{u,v,w,x,q\}\), with size 5. Therefore the binary weight is \(B_{AB}=1\), because the overlap is nonempty, and the Jaccard weight is
For the rank-based score, the ranks are \(r_A(u)=1\), \(r_B(u)=2\); \(r_A(v)=2\), \(r_B(v)=1\); and \(r_A(w)=3\), \(r_B(w)=4\). With \(k=4\), the denominator is \(4(5)/2=10\). The three contributions are \(5-2=3\), \(5-2=3\), and \(5-4=1\), respectively. Hence
All three measures indicate some shared neighborhood structure, but they report different aspects of it: binary records only that overlap exists, Jaccard records the overlap relative to the union, and the rank-based score gives greater influence to the high-ranked shared neighbors.
Worked Example: Same Overlap, Different Rank Agreement
Let \(k=4\), \(N_i=\{a,b,c,d\}\) in that order, and \(N_j=\{a,b,e,f\}\). Compare two possible rank orders for cell \(j\): first, \(e,f,b,a\); second, \(a,b,e,f\). The neighbor sets are unchanged between the two cases.
In both cases, the shared set is \(\{a,b\}\) and the union has six cells. Thus \(B_{ij}=1\) and \(J_{ij}=2/6=1/3\), regardless of the order. In the first ordering, \(a\) has ranks 1 and 4, while \(b\) has ranks 2 and 3. Their contributions are \(5-4=1\) and \(5-3=2\), giving \(R_{ij}=3/10=0.300\). In the second ordering, the shared cells have matching ranks 1 and 2. Their contributions are \(5-1=4\) and \(5-2=3\), giving \(R_{ij}=7/10=0.700\).
The binary and Jaccard weights cannot distinguish these cases because neither uses rank information. The rank-based score does distinguish them. This is useful when closeness within a neighbor list is meaningful, but it also makes the score more sensitive to the ordering and tie-breaking used to construct those lists.
Worked Example: Interpreting a Weak Relative Overlap
Two cells each have \(k=5\) neighbors and share one neighbor. For example, let \(N_i=\{a,b,c,d,e\}\) and \(N_j=\{a,f,g,h,m\}\). Their shared-neighbor count is 1 and their union has 9 cells. Their weights are
The binary weight marks this pair as having overlap, without indicating that the overlap is small. The Jaccard value shows that only 1 of the 9 distinct neighbors is shared. For the rank-based score, suppose \(a\) ranks 1 in both lists. The denominator is \(5(6)/2=15\), and the contribution is \(6-1=5\), so \(R_{ij}=5/15\approx0.333\). If \(a\) instead ranks 5 in both lists, the contribution is \(6-5=1\), so \(R_{ij}=1/15\approx0.0667\). The example shows that even a single shared neighbor can have different rank-based weights depending on its position.
What the Weights Preserve—and What They Lose
No one weighting scheme preserves every feature of two neighbor lists. Choosing a scheme means deciding which distinctions are relevant for the graph.
| Weight | Information retained | Information discarded |
|---|---|---|
| Binary shared-neighbor weight | Whether at least one neighbor is shared | Number of shared neighbors, list size relative to overlap, and ranks |
| Jaccard similarity | Shared-neighbor count relative to the union size | Ranks and the identities or biological meaning of the shared cells |
| Rank-based score defined here | Overlap and the ranks of shared neighbors in both lists | Rank information for neighbors that are not shared, beyond their effect on the shared neighbors' ranks |
For fixed, equal list sizes, Jaccard similarity is a monotone function of the shared-neighbor count: \(J_{ij}=c_{ij}/(2k-c_{ij})\). Consequently, it orders pairs in the same way as the raw count in this setting, although its scale is different and bounded by 1. If list sizes vary, the union denominator also reflects their sizes, so comparisons need not reduce to ordering by the count alone. The binary scheme is coarser still: every pair with any overlap receives the same value.
An edge weight should be interpreted as a property of the constructed graph, conditional on the neighbor lists. It is not a calibrated measure of transcriptomic distance, a p-value, or evidence of a causal or biological relationship. The upstream choices—including the cell representation, distance metric, and \(k\)—affect the lists and therefore the weights.
Assumptions, Diagnostics, and Common Pitfalls
These calculations require valid neighbor lists for the cells being compared. In particular, the lists should use a consistent definition of neighbor, should exclude the focal cell itself, and should have a known size. The rank-based definition additionally needs an ordering within each list. If a graph starts from directed nearest-neighbor lists, the edge candidate set and any symmetrization rule should be decided separately; the formulas above calculate a symmetric similarity once both lists are specified.
Several checks can expose implementation or interpretation problems:
- Confirm that \(0\leq J_{ij}\leq1\) and \(0\leq R_{ij}\leq1\), and that pairs with no shared neighbors have both scores equal to zero.
- Check symmetry: swapping \(i\) and \(j\) should not change a weight.
- Verify that no cell appears in its own neighbor list. Self-inclusion can inflate overlap in unintended ways.
- Inspect the distribution of weights, not just a few edges. If nearly all Jaccard weights are zero or nearly all are similar, the chosen \(k\) or neighbor construction may provide little discrimination for the intended use.
- For rank-based weights, check how distance ties are resolved. Different tie-breaking can change ranks and hence weights even when the underlying distances tie.
A common mistake is to interpret \(B_{ij}=1\) as evidence of strong similarity. The reasoning is wrong because that value only says \(c_{ij}>0\): one shared neighbor and many shared neighbors both produce 1. Use Jaccard or an explicitly chosen rank-sensitive measure when the amount or placement of overlap matters. A second mistake is to treat a larger rank-based weight as a direct measure of biological similarity. It means the specified rank-weighted overlap is larger, conditional on the lists; it does not establish biological identity.
The schemes also have limitations. Binary weights can erase meaningful variation in overlap. Jaccard weights do not use ordering and may assign equal weights to pairs whose shared neighbors have very different ranks. Rank-based weights depend on the chosen scoring rule, the value of \(k\), and rank handling; they can be less comparable when lists have different lengths unless a suitable normalization is defined. None of these weights corrects a poor upstream neighborhood construction or resolves whether the resulting graph reflects meaningful cell structure.
A Practical Calculation Sequence
For a reproducible comparison, keep the edge-support decision separate from the weighting formula and record which formula was used. A compact calculation sequence is:
Record the neighbor-list size, self-neighbor convention, and which pairs are eligible to have edges.
For each pair, calculate \(N_i\cap N_j\), \(c_{ij}\), and \(N_i\cup N_j\).
Use the binary indicator, the Jaccard ratio, or the stated rank-based formula. Do not describe one scheme's information as if another scheme retained it.
Check bounds and symmetry, then describe the weight as neighborhood overlap under the chosen construction.
Check Your Understanding
Answer each question, then compare your work with the solutions below.
- Two lists each have size \(k=3\) and share two neighbors. What are the binary and Jaccard weights?
- For \(k=3\), a pair shares one neighbor ranked 1 in both lists. Calculate the rank-based score defined in this tutorial.
- Can two pairs have the same Jaccard weight but different rank-based weights? Explain briefly.
- What does a binary weight of 1 establish, and what does it not establish?
Solutions. (1) The binary weight is 1 because the overlap is nonempty. The union has \(3+3-2=4\) neighbors, so \(J=2/4=0.500\). (2) The denominator is \(3(4)/2=6\). The shared neighbor contributes \(4-\max(1,1)=3\), so \(R=3/6=0.500\). (3) Yes. Jaccard uses only the overlap count and union size, whereas the rank-based score also uses the positions of shared neighbors. Pairs with the same sets' overlap sizes can therefore have different rank-based scores. (4) It establishes that at least one neighbor is shared. It does not establish how many are shared, how large the overlap is relative to the lists, or whether the shared neighbors are highly ranked.