From Distances to a Weighted Graph
A distance table contains pairwise information, but a graph makes a different object: it retains selected cell-to-cell relationships and can attach a strength to each one. The construction has distinct decisions. First select neighbors from the distances; then decide how directed selections become undirected edges; finally assign weights to those edges. Keeping these steps separate makes it easier to check the result and to locate mistakes.
This worked construction uses a directed k-nearest-neighbor (kNN) list for each cell, symmetrizes by the union rule, and assigns an edge the Jaccard similarity of the endpoint cells’ neighbor sets. This is one explicit, reproducible convention, not the only possible weighted graph construction. In particular, another symmetrization or edge-weight definition can produce a different graph from the same distances.
The construction assumes that the distance table concerns the same set of distinct cells, that distances are symmetric and comparable across cells, and that \(k\) is a fixed integer with \(1\leq k<n\), where \(n\) is the number of cells. The neighbor sets exclude the cell itself. To avoid a tie-breaking ambiguity in the worked calculation, assume there are no tied distances at the \(k\)th-neighbor boundary. In real analyses, the representation and distance measure, the value of \(k\), and any tie-handling rule must be specified; the graph cannot resolve those choices for us.
Worked Construction From a Distance Table
Suppose five hypothetical cells, A through E, have the following pairwise distances. They are illustrative values, not measurements from a study. The table is symmetric, and the diagonal entries are zero because each cell’s distance from itself is zero.
| Cell | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 1.0 | 1.8 | 6.0 | 7.0 |
| B | 1.0 | 0 | 3.0 | 7.0 | 8.0 |
| C | 1.8 | 3.0 | 0 | 1.5 | 2.0 |
| D | 6.0 | 7.0 | 1.5 | 0 | 1.8 |
| E | 7.0 | 8.0 | 2.0 | 1.8 | 0 |
Worked Example: Selecting Neighbors and Calculating Weights
Set \(k=2\). For each cell, choose the two smallest distances to other cells. The resulting neighbor sets are \(N_A=\{B,C\}\), \(N_B=\{A,C\}\), \(N_C=\{A,D\}\), \(N_D=\{C,E\}\), and \(N_E=\{C,D\}\). For example, C’s distances in ascending order are 1.5 to D, 1.8 to A, 2.0 to E, and 3.0 to B, so its two neighbors are D and A. All boundary distances are untied.
Applying union symmetrization gives the candidate edges \(\{A,B\}\), \(\{A,C\}\), \(\{B,C\}\), \(\{C,D\}\), \(\{C,E\}\), and \(\{D,E\}\). For instance, \(\{B,C\}\) is a candidate because C belongs to \(N_B\), even though B does not belong to \(N_C\).
For edge \(\{A,B\}\), the shared-neighbor set is \(N_A\cap N_B=\{C\}\), and the union is \(N_A\cup N_B=\{A,B,C\}\). Thus \(w_{AB}=1/3=0.3333\). For \(\{A,C\}\), the intersection of \(\{B,C\}\) and \(\{A,D\}\) is empty, so \(w_{AC}=0/4=0\). For \(\{B,C\}\), the intersection is \(\{A\}\) and the union is \(\{A,C,D\}\), giving \(w_{BC}=1/3\).
The remaining positive weights are also \(1/3\): \(N_C\cap N_E=\{D\}\) and \(N_C\cup N_E=\{A,C,D\}\), so \(w_{CE}=1/3\); \(N_D\cap N_E=\{C\}\) and \(N_D\cup N_E=\{C,D,E\}\), so \(w_{DE}=1/3\). For \(\{C,D\}\), the sets \(\{A,D\}\) and \(\{C,E\}\) have an empty intersection, so \(w_{CD}=0\). The two candidate edges with zero weight have no shared neighbors and do not appear as positive-weight edges.
The adjacency matrix records the weights in the same cell order, A, B, C, D, E. Because the graph is undirected, \(W_{ij}=W_{ji}\); because self-links are excluded, its diagonal is zero.
The positive-weight edges are \(\{A,B\}\), \(\{B,C\}\), \(\{C,E\}\), and \(\{D,E\}\). The entries \(W_{AC}\) and \(W_{CD}\) are zero even though those pairs were candidate edges under union symmetrization. A matrix entry of zero here means there is no positive shared-neighbor weight; it does not mean that the original pairwise distance was infinite or unavailable.
Why the Jaccard Weight Has This Form
The numerator counts how many neighbors the two endpoint cells share. The denominator counts all distinct cells that occur in either endpoint’s neighbor set. Dividing the overlap by the union adjusts the count for the total neighborhood represented by the pair. Thus a larger weight indicates greater proportional overlap, not necessarily a smaller original distance. With nonempty neighbor sets, the weight is between zero and one, inclusive; it is one when the sets are identical and zero when they do not overlap.
For the example, both neighbor sets have size two. If two such sets share one cell, their union has size \(2+2-1=3\), so the Jaccard weight is \(1/3\). If they share none, the union has size four and the weight is zero. More generally, the identity
follows because adding the two set sizes counts every shared element twice, whereas the union should count it once. Subtracting the intersection size corrects that double count. This also provides a useful arithmetic check on a manually computed weight.
Worked Example: Interpreting an Edge Weight
Suppose a hypothetical candidate edge joins cells U and V, with \(N_U=\{a,b,c,d\}\) and \(N_V=\{b,c,e,f\}\). The shared set is \(\{b,c\}\), of size two. The union is \(\{a,b,c,d,e,f\}\), of size six. Therefore,
This weight says that the two neighbor sets overlap by one third of their combined distinct members. It does not say that U and V are one third as far apart as some other pair, nor is it a probability that the cells belong to the same biological type.
Symmetrization and Matrix Checks
The union rule keeps a pair if at least one endpoint selects the other. The alternative mutual rule keeps a pair only if both endpoints select each other. These rules answer different questions: union is more inclusive, while mutual selection requires reciprocal proximity. Neither rule changes the original neighbor lists; it changes how those directed lists are converted to undirected candidate edges.
Worked Example: Union Versus Mutual Selection
In the five-cell construction, B selects C because \(C\in N_B\), but C does not select B because \(N_C=\{A,D\}\). Likewise, E selects C, but C does not select E. Union symmetrization therefore includes candidate edges \(\{B,C\}\) and \(\{C,E\}\). Mutual symmetrization would exclude both. The reciprocal selections A–B, A–C, C–D, and D–E would remain candidates under the mutual rule. After applying the same Jaccard weights, A–C and C–D have weight zero, while the reciprocal positive-weight edges A–B and D–E remain. The final positive-weight graph would therefore differ from the union construction.
This comparison shows why a graph should be reported with its symmetrization rule. Reporting only “a kNN graph” does not reveal whether a one-sided neighbor selection was retained.
Before using a constructed matrix, check it directly. The following checks catch common implementation errors:
- Symmetry: verify \(W_{ij}=W_{ji}\) for every pair. An asymmetric matrix is inconsistent with the stated undirected construction.
- Diagonal: verify \(W_{ii}=0\); no cell should be its own neighbor.
- Range: every Jaccard weight should satisfy \(0\leq W_{ij}\leq1\).
- Candidate rule: every positive weight must correspond to a pair selected by at least one endpoint under union symmetrization.
- Set arithmetic: check intersections and unions against the stated neighbor sets, rather than inferring a weight from distance alone.
Confirm that the table concerns the intended cells, has symmetric pairwise distances, and uses a stated tie-handling rule. Do not include self-distances when ranking neighbors.
For the chosen \(k\), list exactly the \(k\) nearest distinct cells for every vertex. Keeping these lists visible makes later calculations auditable.
For the union rule, include a pair if either endpoint selected the other. Record the rule before computing weights.
For each candidate pair, calculate the intersection and union of its neighbor sets. Place the resulting weight symmetrically in the matrix; leave zero-weight and noncandidate pairs at zero.
Diagnostics, Alternatives, and Limitations
A useful diagnostic is to compare the directed neighbor lists, candidate edges, and positive-weight edges rather than inspecting only the final matrix. A cell with unexpectedly few positive-weight connections may have neighbors that rarely share neighbors with it; alternatively, a coding error may have included self in \(N_i\), used a distance-table row in the wrong order, or confused the union rule with mutual selection. Recalculate a few entries by hand and confirm the matrix symmetry before interpreting the graph.
The union rule and mutual rule are the main symmetrization alternatives in this construction. Union retains more candidate pairs, including one-sided selections; mutual is stricter and can remove them. A second choice is the similarity weight. Jaccard similarity divides shared-neighbor count by union size, whereas a raw shared-neighbor count uses only \(|N_i\cap N_j|\). With fixed-size neighbor sets, the two are monotone in the shared count, but their numerical scales differ. A count and a Jaccard weight should not be interpreted as interchangeable values.
The method also has limits. The graph depends on the chosen representation, distance definition, \(k\), symmetrization rule, and weight formula. Changing any of them can alter both edges and weights. Jaccard weights capture neighborhood overlap, not a causal relationship, a cell-type label, or a calibrated probability. A zero weight can discard a candidate pair that was close enough to be selected by one endpoint; conversely, a positive weight does not prove that the cells share a biological identity. The construction supplies a graph for subsequent analysis, not a conclusion about clusters by itself.
Check Your Understanding
Answer each question using the stated union-plus-Jaccard construction. Solutions are included for checking your reasoning.
- If \(N_P=\{a,b,c\}\) and \(N_Q=\{b,c,d\}\), calculate the Jaccard weight. Solution: The intersection is \(\{b,c\}\), of size two, and the union is \(\{a,b,c,d\}\), of size four. Thus \(w_{PQ}=2/4=0.5000\).
- Cell R selects S, but S does not select R. Is \(\{R,S\}\) a candidate edge under union symmetrization? Solution: Yes. Union includes the pair when at least one endpoint selects the other.
- For the five-cell example, why is \(W_{AC}=0\) although A and C are candidate neighbors? Solution: Their sets are \(N_A=\{B,C\}\) and \(N_C=\{A,D\}\). The intersection is empty, so their Jaccard weight is zero.
- What matrix check would reveal that a purported undirected weighted graph was assembled inconsistently? Solution: Check symmetry. If \(W_{ij}\ne W_{ji}\) for any pair, the matrix does not represent the stated undirected graph.
- Would mutual symmetrization retain the candidate edge \(\{B,C\}\) in the five-cell example? Solution: No. B selects C, but C does not select B, so the selection is not reciprocal.