Why Direction Matters in a kNN Graph
A k-nearest-neighbor (kNN) graph starts with a simple, local question for each cell: which other \(k\) cells are closest to it under the chosen distance metric? Because this question is asked separately for every cell, the resulting neighbor relation need not be reciprocal. Cell \(j\) may be among the nearest neighbors of cell \(i\), even when \(i\) is not among the nearest neighbors of \(j\).
This difference matters when a graph is used to represent cell relationships. A directed graph preserves which cell selected which neighbor. An undirected graph instead represents a connection without an arrow. Turning the directed kNN graph into an undirected graph therefore requires a rule for deciding which one-way and two-way neighbor relations to keep. Two common rules are union symmetrization and mutual-neighbor symmetrization. They can produce different edge sets and different connectivity.
The k value and distance metric are taken as fixed here. The earlier material on choosing \(k\) and distance metrics addresses how those choices are made; this tutorial focuses on what happens to the graph after the directed neighbor lists have been formed.
This definition assumes that the distance metric is fixed and that the neighbor ranking is well-defined. If distances tie at the \(k\)th position, a procedure must specify how ties are handled. A deterministic tie-break keeps exactly \(k\) neighbors per cell; including all tied cells can give some cells more than \(k\) outgoing edges. Unless noted otherwise, examples here assume there are no ties and exactly \(k\) neighbors are selected for every cell.
With no ties, each of the \(n\) cells selects \(k\) neighbors, so the directed graph contains \(nk\) directed edges. This count is about directed edges: if \(i \to j\) and \(j \to i\) both occur, they are two directed edges, even though they refer to one pair of cells.
Two Ways to Make the Graph Undirected
The union rule keeps every cell pair represented by at least one directed edge. The mutual rule keeps only reciprocal pairs. Each undirected edge is counted once, regardless of whether its original relation had one or two arrows. These are different decisions about the meaning of a connection, not just different ways of drawing the same graph.
Let \(E_{\mathrm{union}}\) and \(E_{\mathrm{mutual}}\) denote the sets of undirected edges produced by the two rules. For any pair of cells, mutual selection implies that at least one of them selected the other. Therefore,
This inclusion gives a direct connectivity result. A path is a sequence of vertices in which consecutive vertices share an edge. Every path in the mutual-neighbor graph is also a path in the union graph, because all of its edges are retained by the union rule. Thus, if two vertices are connected in the mutual-neighbor graph, they must also be connected in the union graph. The converse need not hold: the union graph can connect vertices using one-way neighbor relations that the mutual graph discards.
Worked Examples
Worked Example: Symmetrizing a Four-Cell kNN Graph
Consider four hypothetical cells \(A,B,C,D\), with the following pairwise distances: \(d(A,B)=1\), \(d(A,C)=4\), \(d(A,D)=7\), \(d(B,C)=2\), \(d(B,D)=6\), and \(d(C,D)=3\). All distances are distinct for each cell’s neighbor ranking. Take \(k=1\), so each cell selects its single nearest neighbor.
For \(A\), the distances to \(B,C,D\) are \(1,4,7\), so \(A \to B\). For \(B\), the distances to \(A,C,D\) are \(1,2,6\), so \(B \to A\). For \(C\), the distances to \(A,B,D\) are \(4,2,3\), so \(C \to B\). For \(D\), the distances to \(A,B,C\) are \(7,6,3\), so \(D \to C\). The directed edges are therefore \(A \to B\), \(B \to A\), \(C \to B\), and \(D \to C\).
There are \(n=4\) cells and \(k=1\), so the directed-edge count is \(nk=4(1)=4\), as the list confirms. Under union symmetrization, the undirected edges are \(AB,BC,CD\). Thus the union graph has 3 edges. Under mutual symmetrization, only \(A\) and \(B\) selected each other, so the graph contains just edge \(AB\), for a total of 1 edge.
The union graph has a path \(A-B-C-D\), connecting all four cells. The mutual graph connects \(A\) and \(B\), but \(C\) and \(D\) have no mutual edge. This example shows that a directed graph with a fixed number of outgoing edges per cell does not imply that the mutual graph will connect all cells.
Worked Example: Counting Edges From Neighbor Lists
Suppose five hypothetical cells have these directed neighbor lists for \(k=2\): \(N_2(A)=\{B,C\}\), \(N_2(B)=\{A,C\}\), \(N_2(C)=\{B,D\}\), \(N_2(D)=\{C,E\}\), and \(N_2(E)=\{D,C\}\). The directed graph has \(nk=5(2)=10\) directed edges.
For the undirected union graph, combine each pair that appears in at least one neighbor list, counting a pair only once. The resulting set is \(AB,AC,BC,CD,CE,DE\), so the union graph has 6 undirected edges. For the mutual graph, keep only pairs that appear in both directions: \(AB\), \(BC\), \(CD\), and \(DE\). It has 4 undirected edges.
The four mutual edges form the path \(A-B-C-D-E\), so all five cells are connected in the mutual graph and therefore also in the union graph. In this example, \(AC\) and \(CE\) are union-only edges: each pair was selected in one direction but not both. The arithmetic also illustrates why the directed count \(nk=10\) is not the number of edges in either undirected graph. Reciprocal directed edges collapse to one undirected edge, while one-way edges may or may not be retained depending on the rule.
Worked Example: When Union Connects More Than Mutual
For six hypothetical cells and \(k=1\), suppose the directed neighbor lists are \(A \to B\), \(B \to A\), \(C \to B\), \(D \to C\), \(E \to D\), and \(F \to E\). There are \(nk=6(1)=6\) directed edges.
The union graph contains the undirected edges \(AB,BC,CD,DE,EF\). There are 5 edges, and they make the path \(A-B-C-D-E-F\), so every cell is connected to every other by a path. The mutual graph contains only \(AB\): the other directed edges have no corresponding arrow in the reverse direction. It has 1 edge, and cells \(C,D,E,F\) are not connected to \(A\) or \(B\) in that graph.
The difference is not a change in the underlying neighbor lists; it comes entirely from the symmetrization rule. Union retains a one-way link such as \(C \to B\) as undirected edge \(BC\). Mutual discards it because \(B\) did not select \(C\). Therefore, greater edge retention can preserve connections that mutual symmetrization removes, although it does not guarantee that any particular graph is connected.
Choosing a Symmetrization Rule
The appropriate rule depends on what an edge is intended to represent. If an edge means that at least one cell regards the other as a close neighbor, union symmetrization matches that interpretation. It is inclusive of one-way relations and preserves every pair appearing in the directed kNN graph. If an edge is intended to indicate reciprocal neighborhood membership, mutual symmetrization matches that stricter interpretation. It excludes one-way relations and consequently cannot have more edges than the union graph.
| Representation | Edge rule | What it retains | Connectivity implication |
|---|---|---|---|
| Directed kNN | Keep each selected relation \(i \to j\) | Which cell selected which neighbor | Direction must be considered when interpreting paths |
| Union graph | Keep a pair if either direction is present | All directed neighbor pairs, without arrows | At least as connected as the mutual graph on the same vertices |
| Mutual graph | Keep a pair only if both directions are present | Reciprocal neighbor pairs | May lose paths that exist in the union graph |
The directed representation is useful when the asymmetry itself is meaningful or when a method expects directed edges. The two undirected representations are alternatives when a method expects an undirected graph. Union is often considered when retaining local links is important; mutual is considered when requiring reciprocal support is important. Neither rule is universally preferable, and neither should be chosen solely because its graph looks visually cleaner.
Diagnostics, Assumptions, and Limitations
Before interpreting a symmetrized graph, verify the construction. Check that self-neighbors were excluded, that the same distance metric was used consistently, and that \(k\) is valid for the number of cells. Inspect how ties at the neighbor cutoff were handled: including all ties may invalidate the simple \(nk\) directed-edge count. For an explicit small graph, count directed edges first, then form unique unordered pairs for union and mutual edges. This helps catch accidental double-counting of reciprocal selections.
The edge-set inclusion \(E_{\mathrm{mutual}} \subseteq E_{\mathrm{union}}\) is a basic diagnostic. If a proposed mutual edge is absent from the union graph, or if the mutual graph has more edges than the union graph built from the same neighbor lists, the construction is inconsistent. To compare connectivity, use the same vertices and the same original directed neighbor lists; otherwise, a difference may come from changed inputs rather than symmetrization.
A common failure mode is to assume that every undirected graph obtained from a kNN construction has exactly \(nk\) edges. The directed graph has \(nk\) edges under the no-ties, fixed-\(k\) assumption, but reciprocal selections collapse to one undirected pair and one-way selections are treated differently by the two rules. Edge counts in either undirected graph depend on the actual neighbor lists.
Another limitation is that symmetrization cannot fix an unsuitable distance representation or a poorly chosen \(k\). It only changes how already-selected neighbor relations are interpreted. Union may retain a one-way relation that is not reciprocated; mutual may remove useful links and break paths. Conversely, keeping all one-way links may retain connections that a reciprocal-neighbor interpretation would regard as insufficiently supported. These are structural trade-offs, not guarantees about biological validity or cluster quality.
A Short Connectivity Justification
The inclusion of edge sets provides a complete justification of the connectivity comparison. By definition, an edge \(\{i,j\}\) belongs to \(E_{\mathrm{mutual}}\) only when both \(j \in N_k(i)\) and \(i \in N_k(j)\). In particular, at least one of these statements is true, which is the condition for \(\{i,j\}\) to belong to \(E_{\mathrm{union}}\). Thus every mutual edge is a union edge. If a sequence of vertices forms a path in the mutual graph, each consecutive pair is therefore also a union edge, and the same sequence is a path in the union graph. Hence a pair connected in the mutual graph is connected in the union graph. The implication is one-way: union-only edges can create paths that are absent from the mutual graph.
Check Your Understanding
Answer each question using the stated neighbor lists. Solutions follow the questions.
- For three cells with \(N_1(A)=\{B\}\), \(N_1(B)=\{C\}\), and \(N_1(C)=\{B\}\), list the union and mutual edges. Which graph connects all three cells?
- With \(n=8\) cells and \(k=3\), assuming exactly \(k\) distinct neighbors per cell and no ties, how many directed edges are there? Does that determine the number of union edges?
- Can two cells be connected in the mutual graph but not connected in the union graph formed from the same neighbor lists? Explain.
- Suppose a pair appears as \(i \to j\), but not as \(j \to i\). Which symmetrization rules retain the pair, and why?
Solutions. 1. The directed edges are \(A \to B\), \(B \to C\), and \(C \to B\). The union edges are \(AB\) and \(BC\), which connect all three cells by the path \(A-B-C\). The mutual graph contains only \(BC\), so it does not connect \(A\) to the other cells. 2. The directed-edge count is \(nk=8(3)=24\). This does not determine the union-edge count because reciprocal selections collapse to one undirected pair and the number of distinct selected pairs depends on the neighbor lists. 3. No. Every mutual edge is also a union edge, so every mutual path is a union path. 4. Union retains the pair because at least one direction is present; mutual discards it because the reverse selection is absent.