k-Hop Neighborhoods and Locality in Tensor Message Passing

Depth in a graph neural network is not like depth in a CNN — it has a precise combinatorial meaning. After L rounds of message passing, a node's representation depends on exactly its L-hop neighbourhood, and nothing further away. That single fact governs how far information travels, how many layers you need, and why stacking too many can hurt. In a tensor-aware framework like TGraphX there is a twist: locality lives at two scales at once. This note formalises both and points to where the source lets you work with k-hop neighbourhoods directly.

It builds on Inside Tensor Message Passing and the two-geometries view from Topology vs Feature Geometry.

The k-hop ball

Fix a node v. Its k-hop neighbourhood is the set of nodes within geodesic distance k:

N_k(v) = { u ∈ V : d_G(u, v) ≤ k }
        

where d_G is the shortest-path distance along edges. N_1(v) is v plus its immediate neighbours; N_2(v) adds neighbours-of-neighbours, and so on. The central locality theorem of message passing is simple to state: one message-passing layer mixes information across one hop, so an L-layer network computes h_v as a function of N_L(v) only. A node cannot be influenced by another node further than L edges away, no matter how the parameters are set.

This is why depth is a reach parameter. If two nodes that must interact are 4 hops apart, you need at least 4 layers for any signal to pass between them. Pick L by asking how far the relevant structure extends in your graph.

Two locality scales in a tensor GNN

Here is the part unique to tensor-valued graphs. There are two independent notions of "nearby":

As covered in the message-passing article, ConvMessagePassing uses 1×1 convolutions, which mix channels at each spatial location but do not themselves grow the spatial receptive field within a node. So graph depth controls how far you reach across nodes, while the spatial design controls reasoning within each node's feature map. Conflating the two — expecting more GNN layers to sharpen spatial detail, or expecting spatial ops to reach distant nodes — is a common modelling confusion that the two-scale picture dissolves.

Working with k-hop neighborhoods in code

TGraphX exposes neighbourhood extraction directly. tgraphx/sampling.py provides k_hop_subgraph, which returns the exact L-hop subgraph around a set of seed nodes, plus neighbor_sample for bounded fan-out. These are the building blocks beneath the mini-batch loaders:

import tgraphx as tgx
        sub_nodes, sub_edge_index, mapping, edge_mask = tgx.k_hop_subgraph(
            node_idx=seeds, num_hops=2, edge_index=g.edge_index, num_nodes=g.num_nodes,
        )
        

The connection to scalability is direct: as discussed in mini-batch sampling math, NeighborLoader is exactly a bounded version of this k-hop expansion — instead of the full N_L, it samples up to s neighbours per hop, capping the receptive field at O(s^L). Understanding the exact k-hop ball is what lets you reason about what the sampled version approximates.

Why more hops is not always better

Locality also explains a well-known failure mode. As L grows, the receptive fields of different nodes overlap more and more, and repeated averaging can push node representations toward a common value — the over-smoothing phenomenon documented across the GNN literature. The practical implication is that L is a genuine hyperparameter with a sweet spot, not a dial to turn up indefinitely. This is a property of message passing in general, not specific to TGraphX; the tensor-valued setting inherits it because the cross-node aggregation is the same order-independent reduction.

Honest framing

Two caveats. First, the "exactly N_L(v)" statement assumes standard message passing without skip connections to distant nodes or global readout tokens; architectural additions can widen reach, and TGraphX's pooling provides a separate global path. Second, the right L is empirical — the locality math tells you the minimum depth for a given reach, not the optimal depth for accuracy, which you should determine by validation rather than assume.

Estimating cost from hops

The locality bound also gives a back-of-the-envelope cost estimate. If a graph has average degree d̄, the expected size of an L-hop neighbourhood grows roughly like d̄^L until it saturates the graph. For d̄ = 10 and L = 3, that is on the order of a thousand nodes feeding each target's representation — and with tensor-valued nodes each of those is a full feature map, so the memory cost is d̄^L times the per-node tensor size. This is precisely why bounded neighbour sampling exists: capping fan-out at s per hop replaces the uncontrolled d̄^L with a controllable s^L.

So depth interacts with both reach and cost: every extra layer widens the receptive field and multiplies the work per node. When you choose L, you are simultaneously choosing how far signals travel and how expensive each node update is. Estimate d̄^L for your graph, and measure the actual step time rather than assuming a default depth is free — for tensor nodes the constant factor (the feature-map size) is large enough to matter.

Related guides

• Inside Tensor Message Passing: The φ → AGG → ψ Pipeline
• Topology vs Feature Geometry in Tensor Graphs
• Mini-Batch Sampling Math

Conclusion

Graph locality is exact: L layers see N_L(v), and k_hop_subgraph lets you materialise that ball directly. In a tensor GNN, hold the two locality scales apart — graph hops reach across nodes, spatial operators reason within them — and depth becomes a deliberate reach parameter rather than a guess. The combinatorics, not intuition, should set how deep you go.