Choosing k for a Cell Neighborhood Graph

Why the Choice of k Matters

A cell neighborhood graph connects each cell to other cells judged close in the chosen representation and distance metric. The neighbor count \(k\) controls how many neighbors are selected for each cell. A small \(k\) tends to emphasize very local relationships, but can leave the graph fragmented into many components. A large \(k\) adds connections that reach farther through the data, which can improve connectivity while blurring local structure. Neither outcome is automatically desirable: the useful value depends on the data and on what the graph will be used to represent.

Choosing \(k\) is therefore a diagnostic decision, not a search for a universally optimal integer. The cell representation and distance metric should be fixed while comparing candidates; otherwise changes in the summaries cannot be attributed to \(k\) alone. The earlier material on distance metrics for cell neighborhoods motivates that choice. Here the question is how different neighbor counts alter the graph and what degree, component, and neighborhood-overlap summaries can reveal.

Definition: For a fixed set of \(n\) cells and a fixed distance metric, the \(k\)-nearest-neighbor list \(N_i(k)\) for cell \(i\) contains its \(k\) closest other cells. Self-neighbors are excluded, so \(1 \leq k \leq n-1\). For the undirected union graph used in the diagnostics below, cells \(i\) and \(j\) are joined if \(j \in N_i(k)\) or \(i \in N_j(k)\). A cell's degree is the number of distinct cells joined to it in this graph. A connected component is a maximal set of cells in which every pair is linked by some path.

The union convention matters. A selected neighbor creates an undirected edge whether the selection was made by one endpoint or both. This convention makes the summaries below easy to compare across \(k\); a different graph convention can have different degree properties. Ties in distance should be handled consistently, for example by a fixed tie-breaking rule, so that neighbor lists are well defined. When \(k\) increases under a fixed ranking of neighbors, each cell's list contains its previous list plus additional cells.

How k Changes Sparsity and Locality

Each cell selects exactly \(k\) other cells, so the directed selections number \(nk\). In the undirected union graph, reciprocal selections count as just one edge. Increasing \(k\) can therefore add edges and cannot remove existing union edges when the neighbor rankings are fixed. The graph usually becomes less sparse: degrees tend to rise, and components can join. The new neighbors are generally farther away in the ranked list, so the graph also represents a less strictly local notion of neighborhood.

This gives a practical tension. If \(k\) is very small, the graph may preserve fine local distinctions but be sensitive to individual neighbor choices or small perturbations. If \(k\) is large, it may connect regions through relatively distant neighbors and make distinct local structures less evident. These are tendencies to investigate, not guarantees about biological groups. A graph summary cannot establish that a particular cell type or state exists.

Useful Summaries and a Basic Bound

For a candidate \(k\), inspect the degree distribution, the number and sizes of connected components, and a neighborhood-overlap summary. The mean degree is a compact sparsity measure, while a degree range or quantiles can expose unusually low- or high-degree cells. Component counts indicate whether the graph is broken into many pieces or joined into a small number. Overlap can indicate whether nearby cells tend to have similar neighbor lists.

A useful consistency check follows directly from the union-graph definition. Let \(m\) be the number of distinct undirected edges. There are \(nk\) directed selections. Every undirected edge corresponds to either one selection or two reciprocal selections, so:

\frac{nk}{2} \leq m \leq nk.

The sum of the degrees is \(2m\), because each undirected edge contributes one degree to each of its two endpoints. Thus the mean degree \(\bar{d}\) satisfies:

\bar{d} = \frac{2m}{n}, \qquad k \leq \bar{d} \leq 2k.

This is a bound, not a prediction that the mean degree will equal either endpoint. If many selections are reciprocal, the union graph has fewer distinct edges and the mean degree is closer to \(k\); if few are reciprocal, it is closer to \(2k\). Also, every cell has degree at least \(k\): it has at least the \(k\) distinct edges created by its own selections. Consequently, an isolated cell is impossible in a union graph built from complete \(k\)-neighbor lists with \(k \geq 1\).

Worked Examples

Worked Example: A Small Graph Gains Connectivity

Consider six hypothetical cells with positions on a line at 0, 1, 2.2, 3.8, 8, and 9.5 distance units, labelled A through F in that order. Use ordinary absolute distance, exclude self-neighbors, and make the lists deterministic. At \(k=1\), the lists are A:{B}, B:{A}, C:{B}, D:{C}, E:{F}, and F:{E}.

The distinct union edges are AB, BC, CD, and EF. The degrees are A:1, B:2, C:2, D:1, E:1, and F:1. Their sum is 8, so the mean degree is \(8/6 = 1.333\). There are two components, {A, B, C, D} and {E, F}. The bound also checks: for \(k=1\), the mean degree must be between 1 and 2.

At \(k=2\), the lists are A:{B,C}, B:{A,C}, C:{B,D}, D:{C,B}, E:{F,D}, and F:{E,D}. The union edges are AB, AC, BC, BD, CD, DE, DF, and EF. The degrees are 2, 3, 3, 4, 2, and 2, respectively. Therefore, the mean degree is \(16/6 = 2.667\), which is between \(k=2\) and \(2k=4\). All six cells are now in one component. In this example, increasing \(k\) joins the two previously disconnected groups, but the added connections to D also span the larger distance gap between D and E. Connectivity improved; locality became less strict.

Worked Example: Comparing Candidate k Values with Summaries

Suppose a hypothetical analysis uses the same 1,000 cells, representation, metric, and union-graph convention at three values of \(k\). The following are illustrative graph summaries.

k	Mean degree	Connected components	Mean neighbor-list overlap on graph edges
5	9.8	14	0.08
15	29.1	3	0.23
30	57.4	1	0.49

Check the mean-degree bounds before interpreting the table. At \(k=5\), the permitted range is 5 to 10, and 9.8 is within it. At \(k=15\), the range is 15 to 30, and 29.1 is within it. At \(k=30\), the range is 30 to 60, and 57.4 is also within it. For example, the \(k=5\) mean implies \(1{,}000 \times 9.8 / 2 = 4{,}900\) undirected edges, which lies between \(nk/2=2{,}500\) and \(nk=5{,}000\).

The component count falls as \(k\) grows, while the mean degree and reported overlap rise. These summaries suggest that \(k=5\) is relatively sparse and fragmented in this hypothetical graph; \(k=30\) is much more connected and has higher neighbor-list similarity along its edges. \(k=15\) is an intermediate candidate worth examining further. The table does not prove that 15 is best: the decision depends on whether the graph retains the local distinctions needed for the analysis. In particular, a single component is not by itself evidence that the chosen \(k\) is appropriate.

Worked Example: Calculating Neighborhood Overlap

For two cells joined by an edge, suppose their neighbor lists at a particular \(k\) are \(N_i=\{B,C,D,E\}\) and \(N_j=\{A,C,D,F\}\). Define their Jaccard overlap as the number of shared neighbors divided by the number of distinct neighbors in either list:

J(i,j) = \frac{|N_i \cap N_j|}{|N_i \cup N_j|}.

The shared set is \(\{C,D\}\), of size 2. The union is \(\{A,B,C,D,E,F\}\), of size 6. Therefore, \(J(i,j)=2/6=0.333\). This says that one third of the distinct cells in the two lists are shared. It does not mean that the cells are one third as distant, or that the overlap is statistically significant.

A graph-level summary might report the mean Jaccard overlap across its edges, using a stated convention for which neighbor lists are compared. Such an average can help identify a candidate whose connections often join cells with similar neighborhoods. However, overlap depends on \(k\), the metric, and the cell distribution. It is a descriptive diagnostic, not a universal target to maximize.

A Practical Selection Workflow

Fix the comparison conditions.
Use the same cells, representation, distance metric, self-neighbor rule, and tie handling for all candidate values. This makes changes in graph summaries interpretable as consequences of changing \(k\).

Choose a modest range of candidates.
Compare several plausible integers rather than treating one default as self-evidently correct. Keep each candidate within \(1 \leq k \leq n-1\).

Check degree and components.
Confirm that the mean degree lies in \([k,2k]\) for the union graph and that there are no isolated cells. Examine component counts and sizes to see whether a very small \(k\) leaves many fragments or a larger \(k\) merges them.

Examine neighborhood overlap and context.
Calculate overlap under a clearly stated definition, then inspect whether the summary supports or contradicts the degree and component picture. Choose a value whose locality and connectivity are appropriate for the intended analysis, and check whether that choice is sensitive to nearby candidate values.

Diagnostics, Alternatives, and Limitations

The summaries are most useful together. A high component count with degrees close to their lower bound can indicate that a small \(k\) has not connected many parts of the graph. A sharp decline in component count as \(k\) rises identifies a range where connectivity changes quickly. Conversely, if increasing \(k\) greatly raises degrees and overlap while adding connections across regions that should remain locally distinct, the candidate may be too large for the intended purpose. These patterns are prompts for investigation, not automatic pass-fail rules.

A fixed-\(k\) graph gives each cell the same number of selected neighbors, but the distances to those neighbors need not be equal across cells. In a sparse region, the \(k\)th neighbor may be far away; in a dense region, it may be close. A fixed-radius neighborhood is a different alternative: it uses a distance threshold, so the number of neighbors can vary by cell. It may therefore respond differently to variation in density. Neither construction is uniformly superior; the appropriate choice depends on the question and the geometry represented by the chosen metric.

All these diagnostics are conditional on the representation and metric. If those choices distort or fail to capture relevant similarities, changing \(k\) cannot repair that problem. A single mean can also hide a broad or uneven degree distribution, and a component count says nothing by itself about whether cells within a component are biologically similar. Overlap summaries can be dominated by common local structure and should be interpreted alongside the actual neighborhoods, not as a stand-alone objective.

Common Mistakes

Calling \(k\) the undirected degree. Each cell selects \(k\) neighbors, but the union degree can exceed \(k\) because other cells may select it too. For this graph, the degree is at least \(k\) and at most \(n-1\).
Reporting isolated cells in a union graph built from complete lists. This is impossible for \(k \geq 1\): each cell's own selections give it at least \(k\) incident edges. Check for missing or filtered cells, incomplete lists, or a different graph definition before interpreting such a result.
Choosing the \(k\) that produces one component. One component only says that paths connect all cells. It does not establish that the edges preserve useful local structure.
Maximizing overlap without context. High overlap can accompany a graph with broad neighborhoods. It is a descriptive summary, not proof that the graph is more accurate.
Changing several settings at once. If the representation, metric, and \(k\) all change, the effect of \(k\) cannot be isolated from the other changes.

Key takeaway: Choose \(k\) by comparing a consistent set of graphs, not by treating any one summary as a universal optimum. Degree bounds check whether a union graph is coherent, components describe connectivity, and neighborhood overlap adds a view of local similarity. Interpret all three in the context of the intended analysis.

Check Your Understanding

Try each question, then compare your reasoning with the solutions below.

For a union k-nearest-neighbor graph with \(n=80\) cells and \(k=10\), what bounds must hold for the number of edges and the mean degree?
At fixed distances and tie handling, can a union graph acquire more connected components when \(k\) increases? Explain.
Two neighbor lists have three shared cells and nine distinct cells in their union. Calculate their Jaccard overlap and interpret it.
A report says that 4% of cells are isolated in the union graph built from complete lists with \(k=6\). What should be checked?

Solutions. (1) The edge count satisfies \(nk/2 \leq m \leq nk\), so \(400 \leq m \leq 800\). The mean degree satisfies \(k \leq \bar{d} \leq 2k\), giving \(10 \leq \bar{d} \leq 20\). (2) No. With fixed neighbor rankings, increasing \(k\) only adds union edges; adding edges can join components but cannot split a component. (3) \(J=3/9=0.333\). One third of the distinct cells in the two lists are shared. (4) Isolated cells are impossible under the stated construction because each cell selects six other cells and therefore has at least six incident union edges. Check whether the graph uses a different cell set or construction, whether lists were truncated or incomplete, and whether the reported isolation summary was calculated on the stated graph.