Why the Edge Rule Matters
A spatial neighborhood graph turns spot coordinates into a statement about which pairs of observations are treated as neighbors. That statement is part of the analysis, not a neutral description of the tissue. A grid graph follows array layout, a radius graph follows a fixed physical distance, and a k-nearest-neighbor graph gives each spot a specified number of nearby candidates. These choices can produce different degrees, connections across gaps, and patterns at tissue boundaries.
The earlier material on spatial coordinate systems establishes that coordinates must be interpreted in their recorded units and orientation. Here, the goal is to define graph construction precisely, inspect its consequences, and select an edge rule that matches the spatial sampling design. A graph records neighborhood structure; by itself, it does not establish spatial association or biological interaction.
Three Rules for Defining Edges
A grid graph uses the known organization of an array. Under four-neighbor adjacency, a spot is connected to observed spots immediately above, below, left, or right of it. Under eight-neighbor adjacency, the four diagonal positions are included as well. The rule uses array positions; it does not require every spot to be present. A missing spot simply contributes no vertex and therefore no edge.
A radius graph connects any two observed spots whose Euclidean distance is no greater than a chosen threshold \(r\). If coordinates are in micrometres, \(r\) is in micrometres. A k-nearest-neighbor graph first ranks the other observed spots by distance from each spot and selects the nearest \(k\). This selection is initially directed: \(j\) can be among the \(k\) nearest spots to \(i\) without \(i\) being among the \(k\) nearest to \(j\). An undirected graph therefore needs a symmetrization rule.
For a radius graph, \(\{i,j\}\in E\) exactly when \(d(i,j)\le r\). For a directed k-nearest-neighbor selection, write \(j\in N_k(i)\) when \(j\) is one of the \(k\) closest other observed spots to \(i\). The union rule includes \(\{i,j\}\) if either \(j\in N_k(i)\) or \(i\in N_k(j)\). The mutual rule includes the edge only if both conditions hold. Union symmetrization retains more edges and ensures that every spot has at least \(k\) neighbors when there are no distance ties and \(k<n\); mutual symmetrization can leave some spots with fewer than \(k\), or even zero, undirected neighbors.
Grid Structure and Edge Counts
For a complete rectangular array with \(m\) rows and \(n\) columns, a four-neighbor grid has \(m(n-1)\) horizontal edges: each of the \(m\) rows has \(n-1\) adjacent pairs. It has \(n(m-1)\) vertical edges by the same reasoning. Thus the total is
For eight-neighbor adjacency, the two diagonal directions contribute \(2(m-1)(n-1)\) additional edges, one pair of diagonals per adjacent \(2\)-by-\(2\) block. Therefore,
These counts apply to a complete array. With missing spots or a tissue mask, retain only edges for which both endpoints are observed and eligible. Grid adjacency is especially interpretable when the array has a known lattice layout. It is not automatically appropriate for irregularly spaced coordinates or for array positions that do not represent physical proximity as intended.
Worked Example: Counting Edges in a Small Grid
Consider a hypothetical complete array with 3 rows and 4 columns of spots. Under four-neighbor adjacency, there are \(3(4-1)=9\) horizontal edges and \(4(3-1)=8\) vertical edges. Thus \(|E_4|=9+8=17\).
There are \((3-1)(4-1)=6\) adjacent \(2\)-by-\(2\) blocks. Each contributes two diagonal edges under eight-neighbor adjacency, so there are \(2(6)=12\) additional edges. The eight-neighbor graph has \(17+12=29\) edges. The count is consistent with each undirected edge being counted once in its orientation or diagonal position, rather than once from each endpoint.
If one interior spot is absent, remove that vertex and all its incident edges. The number removed depends on its position and the adjacency rule; it cannot be determined from the array dimensions alone.
Constructing Radius and k-Nearest-Neighbor Graphs
A radius graph has a fixed distance criterion, but its degrees vary with local sampling density and boundary location. In a dense region, many spots may fall within \(r\); in a sparse region, few may. A k-nearest-neighbor graph instead fixes the number of directed selections per spot, but the distance needed to reach the \(k\)th neighbor varies across space. Neither rule guarantees that the resulting neighborhoods match tissue structure unless that structure is checked.
Worked Example: Applying a Radius Threshold
Suppose four hypothetical spots have coordinates in micrometres: \(A=(0,0)\), \(B=(3,0)\), \(C=(0,4)\), and \(D=(3,4)\). Use a radius threshold \(r=3.5\) micrometres and include pairs at distance exactly \(r\), if any.
The pairwise distances are \(d(A,B)=3\), \(d(A,C)=4\), \(d(A,D)=5\), \(d(B,C)=5\), \(d(B,D)=4\), and \(d(C,D)=3\) micrometres. Comparing each with \(3.5\), only \(A\)--\(B\) and \(C\)--\(D\) meet the threshold. Thus the undirected edge set is \(E=\{\{A,B\},\{C,D\}\}\). Each vertex has degree 1, and the graph has two connected components.
The calculation assumes the coordinates use a common, meaningful length scale in both axes. If one coordinate is in pixels and the other in micrometres, these Euclidean distances are not meaningful until the coordinate scales are reconciled.
Worked Example: k-Nearest Neighbors and Symmetrization
Consider four hypothetical spots on a line with coordinates in micrometres: \(A=0\), \(B=1\), \(C=3\), and \(D=7\). For \(k=1\), the nearest spot to \(A\) is \(B\) at distance 1; to \(B\) it is \(A\) at distance 1; to \(C\) it is \(B\) at distance 2; and to \(D\) it is \(C\) at distance 4. The directed selections are \(A\to B\), \(B\to A\), \(C\to B\), and \(D\to C\).
Under union symmetrization, the undirected edges are \(\{A,B\}\), \(\{B,C\}\), and \(\{C,D\}\). The degrees are 1, 2, 2, and 1 for \(A,B,C,D\), respectively. Under mutual symmetrization, only \(\{A,B\}\) remains: \(C\) selects \(B\), but \(B\) does not select \(C\), and \(D\) selects \(C\), but \(C\) does not select \(D\). The result shows why the symmetrization choice must be reported; the same directed nearest-neighbor selections yield different undirected graphs.
Tissue Boundaries, Gaps, and Diagnostics
Boundary effects arise because only observed, included spots can become vertices. A spot at the edge of a tissue section has fewer nearby observed positions on its exterior side. In a radius graph this often means a lower degree than for a similarly sampled interior spot. In a grid graph, the same effect follows from having fewer adjacent positions within the tissue mask. These are properties of the observed domain, not necessarily evidence that the underlying biology has fewer neighbors at the boundary.
A k-nearest-neighbor rule can behave differently: it still selects \(k\) spots for each vertex when enough candidates exist. Near a tissue edge or hole, some selected spots may be farther away than typical interior neighbors. If two tissue regions are separated by a gap, a k-nearest-neighbor rule may connect them because the closest available spot is across the gap. A radius graph avoids such an edge only when the gap makes the pairwise distance greater than \(r\); a grid graph avoids it when intervening positions are missing and the edge rule does not permit a direct jump.
A tissue mask, when available, can restrict eligible vertices or disallow edges known to cross excluded regions. Disconnected tissue islands should not be joined merely to make the graph connected. Such restrictions should be specified before graph construction and applied consistently. For grid data, determine whether adjacency means array neighbors or physical neighbors, especially when spots are missing. For all graph types, inspect degrees, connected components, and the coordinates of unusually long edges. Also check duplicated coordinates, coordinate scaling, distance ties, and whether the radius or \(k\) gives a plausible neighborhood scale.
Distance ties matter when selecting the \(k\)th neighbor. A reproducible implementation should state how ties are handled—for example, include all spots tied at the cutoff, or use a documented deterministic tie-break. Including all ties can result in more than \(k\) directed neighbors; arbitrary tie-breaking can make the graph depend on spot ordering. Likewise, radius inclusion at the threshold should be stated, although exact equality is uncommon with continuously measured coordinates.
Identify the observed spots and any tissue mask or excluded locations. State how missing positions are treated.
Verify common units, axis scaling, orientation, and the sampling layout before calculating distances or using array adjacency.
Choose grid adjacency, a radius and its inclusive threshold convention, or \(k\) together with a tie and symmetrization rule.
Inspect degrees, components, and edge lengths, with particular attention to tissue boundaries, holes, and disconnected regions.
Choosing Among the Rules
| Rule | What it holds fixed | Typical concern |
|---|---|---|
| Grid | Array-position adjacency | Requires meaningful lattice structure; missing spots and tissue masks alter degrees. |
| Radius | Maximum pairwise distance | Degree varies with sampling density and proximity to boundaries. |
| k-nearest neighbors | Number of directed selections per spot | Neighbor distances vary, and symmetrization changes degrees and edges. |
The appropriate choice follows the sampling design and scientific meaning of “nearby.” A grid is natural for a regular array when lattice neighbors are the intended relation. A radius is useful when a fixed physical range is meaningful. k-nearest neighbors can accommodate variation in sampling density, but may create long edges across gaps. These approaches are alternatives, not interchangeable implementations of one uniquely defined graph. Weighted edges are also possible, for example by assigning larger weights to closer pairs, but a weighted graph requires an additional weight rule beyond the binary edge definitions given here.
Common Mistake and Key Takeaway
Wrong reasoning: “Every spot has \(k\) nearest neighbors, so the undirected k-nearest-neighbor graph gives every spot degree \(k\) and cannot bridge a tissue gap.” This confuses directed selections with undirected edges. Under union symmetrization, a spot can be selected by many others and have degree greater than \(k\); under mutual symmetrization, it can have degree below \(k\). Either version can connect across a gap if those spots are nearest in the available set.
Correction: State whether the graph is directed or undirected and, for an undirected k-nearest-neighbor graph, state the symmetrization rule. Then inspect edge lengths and tissue geometry rather than assuming the rule respects boundaries. More generally, report the coordinate units, graph rule and parameter values, boundary handling, and any tie convention. The resulting graph is a modeling choice whose consequences should be checked before it is used in downstream spatial analysis.
Check Your Understanding
Answer each question, then compare with the brief solutions below.
- A complete 2-by-3 array uses four-neighbor adjacency. How many edges does it have?
- Two spots are 5 micrometres apart. Are they connected in a radius graph with \(r=5\) micrometres if the rule includes distances equal to \(r\)?
- In a directed \(k=1\) selection, \(A\) selects \(B\), but \(B\) selects \(C\). Does the union graph contain \(\{A,B\}\)? Does the mutual graph contain it?
- Why can a k-nearest-neighbor graph have long edges near a tissue hole?
Solutions. (1) \(2(3-1)+3(2-1)=4+3=7\) edges. (2) Yes: the edge criterion is \(d(i,j)\le r\), and \(5\le5\). (3) The union graph contains \(\{A,B\}\), because \(A\) selects \(B\); the mutual graph does not, because \(B\) does not select \(A\). (4) Spots inside the hole are absent, so the nearest available spot may be across the hole and substantially farther away than a typical neighbor in the tissue interior.