Building a k-Nearest-Neighbor Graph from Cell Profiles

From Cell Profiles to Neighbor Edges

A cell-neighborhood graph turns a collection of cell profiles into a set of local relationships. The central operation is simple: for each cell, find the \(k\) other cells closest to it under a specified distance, then draw an edge from that cell to each selected neighbor. The result is a compact representation of local similarity, not a clustering or a claim that the cells have the same biological identity.

The input must be specified before distances can be calculated. A profile might consist of selected gene-expression measurements, transformed expression values, or coordinates in a reduced representation. The graph depends on that choice: changing the features or their scale can change the distance rankings and therefore the edges. Here the input representation and distance are treated as fixed. The introductory material on cell-cell neighborhood graphs establishes the graph interpretation; this tutorial makes the neighbor-ranking construction explicit.

Definition: Let \(X\) be an \(n \times p\) matrix of profiles, with one row for each of \(n\) cells and one column for each of \(p\) features. For a chosen distance \(d(i,j)\), the directed \(k\)-nearest-neighbor graph has an edge \(i \to j\) when cell \(j\) is among the \(k\) closest eligible cells to cell \(i\). A cell is not eligible to be its own neighbor. The graph is directed because \(i \to j\) does not, in general, imply \(j \to i\).

Conditions and Construction

For the basic construction, each cell must have a profile in the same feature space, and the chosen distance must be calculable between each pair of cells. The distance should be finite and comparable across pairs. Missing or nonfinite profile values need to be handled before ranking; otherwise some pairwise distances may be undefined, or different pairs may be compared using different information. The profiles and distance are inputs to the procedure, not quantities estimated by the neighbor-ranking step.

The integer \(k\) must satisfy \(1 \leq k < n\). The strict upper bound leaves at least one cell out of each cell's neighbor list, since a cell cannot be its own neighbor. Rankings exclude self-distance even if a software routine returns zero on the diagonal of a distance matrix. Ties at the \(k\)th position also need a rule. To obtain exactly \(k\) outgoing edges per cell, use a specified deterministic tie-breaker, such as a fixed cell ordering. Another possible convention is to include every cell tied at the boundary, but then a cell may have more than \(k\) outgoing edges. The convention should be reported rather than left implicit.

For illustration, use Euclidean distance between profiles \(x_i\) and \(x_j\), each with \(p\) coordinates. This tutorial uses that distance for its calculations; the choice of distance itself is a separate modeling decision.

d(i,j) = \sqrt{\sum_{\ell=1}^{p}(x_{i\ell}-x_{j\ell})^2}

The construction can be written with an adjacency matrix \(A\). Its entry \(A_{ij}\) is 1 if \(j\) is selected among \(i\)'s \(k\) nearest neighbors, and 0 otherwise. Rows refer to the source cell and columns to the destination cell. Thus \(A_{ij}=1\) records \(i \to j\), and the diagonal entries are zero. If the boundary ties are resolved to select exactly \(k\) neighbors for every cell, every row sums to \(k\).

Fix the profiles and distance.
Record which features or coordinates form each row and which distance will be used. Confirm that the same representation applies to every cell.

Compute pairwise distances.
For each cell, calculate its distance to every other cell. Exclude the cell itself from its candidate list.

Rank and select.
Sort each cell's eligible neighbors by increasing distance and retain the first \(k\), applying the stated rule if the boundary is tied.

Record directed edges and check them.
Set \(A_{ij}=1\) for selected neighbors. Verify the diagonal and row sums, and check that each edge matches the corresponding ranking.

Worked Calculations

Worked Example: Ranking Neighbors From Two-Feature Profiles

Suppose four hypothetical cells have two-feature profiles \(A=(0,0)\), \(B=(1,0)\), \(C=(0,2)\), and \(D=(3,1)\). Use Euclidean distance and \(k=1\). The profiles are finite and share two coordinates, so every pairwise distance is defined. Since \(1 \leq 1 < 4\), the chosen \(k\) is allowed.

For cell \(A\), the distances to the other cells are \(d(A,B)=\sqrt{(0-1)^2+(0-0)^2}=1\), \(d(A,C)=\sqrt{(0-0)^2+(0-2)^2}=2\), and \(d(A,D)=\sqrt{(0-3)^2+(0-1)^2}=\sqrt{10}\approx3.162\). Its nearest neighbor is \(B\).

For cell \(B\), \(d(B,A)=1\), \(d(B,C)=\sqrt{(1-0)^2+(0-2)^2}=\sqrt{5}\approx2.236\), and \(d(B,D)=\sqrt{(1-3)^2+(0-1)^2}=\sqrt{5}\approx2.236\). The nearest neighbor is \(A\), with distance 1; the tie between the two more distant cells does not affect the selection.

For cell \(C\), \(d(C,A)=2\), \(d(C,B)=\sqrt{5}\approx2.236\), and \(d(C,D)=\sqrt{(0-3)^2+(2-1)^2}=\sqrt{10}\approx3.162\). Its nearest neighbor is \(A\). For cell \(D\), \(d(D,A)=\sqrt{10}\approx3.162\), \(d(D,B)=\sqrt{5}\approx2.236\), and \(d(D,C)=\sqrt{10}\approx3.162\), so its nearest neighbor is \(B\).

The directed edges are \(A \to B\), \(B \to A\), \(C \to A\), and \(D \to B\). In particular, \(C \to A\) does not require \(A \to C\). The calculations give each of the four cells exactly one outgoing edge, and no cell points to itself.

Worked Example: Constructing an Adjacency Matrix for \(k=2\)

Consider four hypothetical one-coordinate profiles \(P=0\), \(Q=1\), \(R=3\), and \(S=7\). Use absolute Euclidean distance, \(d(i,j)=|x_i-x_j|\), and \(k=2\). The profiles are finite and comparable in the same one-dimensional space, and \(2<4\), so every cell has two eligible neighbors to select.

For \(P\), the distances to \(Q,R,S\) are \(1,3,7\), so \(P\) selects \(Q\) and \(R\). For \(Q\), the distances to \(P,R,S\) are \(1,2,6\), so \(Q\) selects \(P\) and \(R\). For \(R\), the distances to \(P,Q,S\) are \(3,2,4\), so \(R\) selects \(Q\) and \(P\), in that order. For \(S\), the distances to \(P,Q,R\) are \(7,6,4\), so \(S\) selects \(R\) and \(Q\), in that order. There are no ties at a selection boundary.

In the cell order \(P,Q,R,S\), the adjacency matrix is

A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix}

Each row sums to 2, so the graph has \(4 \times 2=8\) directed edges. The matrix is not symmetric: \(A_{SR}=1\), whereas \(A_{RS}=0\). This is consistent with the rankings: \(R\) selects \(P\) and \(Q\), while \(S\) selects \(R\) and \(Q\). A row sum of \(k\) is a check on outgoing edges, not a statement that every cell receives \(k\) edges.

Worked Example: Resolving a Tie at the Selection Boundary

Four hypothetical two-coordinate profiles are \(A=(0,0)\), \(B=(1,0)\), \(C=(-1,0)\), and \(D=(0,3)\). Use Euclidean distance, \(k=1\), and resolve any tie by selecting the alphabetically first cell. All profiles are finite, in the same feature space, and \(1<4\).

For \(A\), \(d(A,B)=1\), \(d(A,C)=1\), and \(d(A,D)=3\). Its two closest cells tie, so the stated rule selects \(B\), giving \(A \to B\). For \(B\), the distances are \(d(B,A)=1\), \(d(B,C)=2\), and \(d(B,D)=\sqrt{10}\approx3.162\), giving \(B \to A\). For \(C\), the distances are \(d(C,A)=1\), \(d(C,B)=2\), and \(d(C,D)=\sqrt{10}\approx3.162\), giving \(C \to A\). For \(D\), the distances are \(d(D,A)=3\), \(d(D,B)=\sqrt{10}\approx3.162\), and \(d(D,C)=\sqrt{10}\approx3.162\). Its closest cell is \(A\), giving \(D \to A\).

With rows and columns in the order \(A,B,C,D\), the resulting matrix is

A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}

The tie rule produces one outgoing edge from \(A\), rather than two. If the convention instead included every cell tied at the boundary, \(A\) would point to both \(B\) and \(C\), and its row sum would be 2. Thus “\(k=1\)” alone does not fully specify the result when ties are possible.

Why the Edge Count Follows From the Construction

When ties are resolved so that each row selects exactly \(k\) distinct other cells, the graph has exactly \(nk\) directed edges. To see this, consider row \(i\) of \(A\). Each of its \(k\) selected neighbors contributes one entry equal to 1, and every other entry is 0. Therefore \(\sum_{j=1}^{n}A_{ij}=k\). Summing over all \(n\) rows gives

\sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij} = \sum_{i=1}^{n} k = nk

The left side counts all directed edges once, by their source row. This argument depends on selecting exactly \(k\) distinct neighbors for every cell and excluding self-edges. If all boundary ties are included, some row sums can exceed \(k\), so the edge count can exceed \(nk\). The result is a bookkeeping property of the construction, not a claim about how many biologically meaningful relationships exist.

Diagnostics, Alternatives, and Limits

A useful first diagnostic is to check that the graph agrees with its inputs and stated rules. Confirm that the cell order used for the matrix matches the order used for the profiles, that distances are finite, and that the diagonal entries are zero. With exactly \(k\) selected neighbors per cell, every row sum must equal \(k\), and there should be \(nk\) directed edges. For a few cells, independently recalculate the nearest distances and confirm the selected columns. This manual check is especially valuable when inspecting an implementation or a small example.

Unexpected results can indicate a problem rather than an interesting biological pattern. A nonzero diagonal suggests that self-distances were not excluded. A row sum other than \(k\) can indicate a tie convention that includes boundary ties, too few eligible cells, or an implementation error. Many identical profiles can create numerous zero-distance ties; the resulting edges may then depend strongly on the tie rule. Extremely large or unexpectedly dominant feature values can also alter rankings. Check the representation and feature scaling before interpreting the graph, and do not assume that a graph built from one representation would be unchanged in another.

A \(k\)-nearest-neighbor graph differs from a radius-based graph, which connects cells within a chosen distance threshold. A fixed-\(k\) construction selects the same number of outgoing neighbors for each cell when ties are resolved to exactly \(k\); a radius construction can give cells different numbers of neighbors, including none. The two approaches therefore answer different local-neighborhood questions. Likewise, neighbors computed from cell profiles need not match neighbors computed from a visualization embedding. An embedding can be useful for display, but its distances represent the embedding geometry, not automatically the distances in the profile space.

The graph is also limited by the representation, distance, value of \(k\), and tie rule used to create it. It records which cells were selected, not the full distance information, uncertainty in cell profiles, or a causal relationship. A directed edge records a one-way selection in a ranking. Do not silently treat it as an undirected connection: whether and how to combine directed edges is a separate graph-construction decision. Approximate neighbor-search algorithms can reduce the computational burden for large data sets, but they may return different neighbors from exact rankings; their accuracy should be checked when the distinction matters. For a small matrix, direct distance calculation and sorting are transparent and easy to verify.

Key takeaway: A directed \(k\)-nearest-neighbor graph is built by calculating distances in a specified cell-profile space, excluding each cell itself, ranking the remaining cells, and recording the first \(k\) selections as outgoing edges. The profile representation, distance, and tie rule are part of the graph's definition.

Check Your Understanding

Answer each question, then compare with the solutions below.

There are 12 cells and \(k=3\), with exactly three distinct neighbors selected for every cell. How many directed edges should the graph contain?
For one cell, the distances to three other cells are 0.4, 0.7, and 0.7. If \(k=1\), what happens under a rule that selects all cells tied at the boundary?
Can cell \(i\) select cell \(j\) as a neighbor while \(j\) does not select \(i\)? Explain using the ranking rule.
Why should the diagonal of the adjacency matrix be zero, even if a distance matrix has zeros on its diagonal?

Solutions. (1) The number is \(nk=12 \times 3=36\) directed edges, because each of the 12 rows has three selected entries. (2) The cell at distance 0.4 is the unique closest neighbor, so it is selected; the tie at 0.7 is beyond the boundary and does not affect the result. If instead the two cells at 0.7 were tied for the closest position, including all boundary ties would give two outgoing edges. (3) Yes. Each cell ranks all the other cells relative to its own profile, and those rankings need not agree; the edge \(i \to j\) does not imply \(j \to i\). (4) A cell is not eligible to be its own neighbor. The zero distance \(d(i,i)=0\) describes a cell's distance from itself, but it must be excluded before ranking and must not be recorded as an edge.