WorksComputer Science
NearFormer: Linear-Size Sparse Attention via Randomized Near Neighbors
Abstract
Graph transformers can capture long-range interactions, but their quadratic attention cost limits their use on large graphs. We introduce NearFormer, a graph transformer whose global attention is restricted to a randomized near-neighbor (NN) graph. NearFormer uses an efficient randomized construction to connect each node to a small number of near neighbors from a broader neighborhood defined by a label-independent feature or spectral geometry. For a fixed retained budget , the resulting attention support has linear size . The NN graph is built once by within-bin search and then held fixed. We use these edges as sparse global-attention supports, with optional learned attention biases, while preserving the original graph for local message passing. Experiments on long-range graph benchmarks and synthetic structural tasks show that NearFormer provides a favorable accuracy–scalability trade-off relative to local message passing, dense and sparse attention.
Introduction
Graph learning supports applications involving relational data, including molecular systems, social networks, and knowledge graphs. Most graph neural networks (GNNs) follow the message-passing paradigm, in which a node iteratively aggregates information from its local neighborhood [18, 22]. Although this locality provides a useful inductive bias, information between distant nodes must traverse many layers. Deep message passing can suffer from over-smoothing [37] and over-squashing [1, 46]. Its distinguishing power is also generally bounded by the 1-Weisfeiler–Lehman test [35] (Xu et al. 2018).
Graph transformers offer a complementary approach by allowing attention to model long-range interactions directly. Recent architectures encode graph structure through positional or structural representations and combine global attention with local message passing [27, 53, 33, 39, 5]. Dense self-attention provides this flexibility by forming all node pairs, which requires time and memory for a graph with nodes. This cost is manageable for small molecular graphs but becomes prohibitive on larger graphs. Generic sparse or linear-attention methods such as BigBird and Performer reduce this asymptotic burden [54, 11], yet their sparsity patterns were developed primarily for sequences and need not reflect the geometry of an arbitrary graph.
Graph-specific sparse attention should add long-range communication channels with few edges, and those channels should reflect graph data rather than an arbitrary node ordering. Existing methods reduce the edge count with data-independent random expander overlays [44] or modify the input topology according to curvature, spectral, or effective-resistance criteria [25, 3, 6, 2]. Expander overlays are efficient but do not adapt to the geometry of a particular graph, whereas graph rewiring can require costly structural optimization and changes the graph on which local message passing is defined.
Here, we introduce NearFormer, a scalable graph transformer based on randomized near-neighbor (NN) attention. We construct a near-neighbor graph in a task-relevant, label-independent geometry, where each node retains randomly selected neighbors from a broader neighborhood at the scale of its nearest neighbors [29]. The geometry may be defined by node attributes or graph Laplacian eigenvectors. Retaining neighbors per node yields at most directed edge instances after symmetrization, and hence linear edge complexity for fixed . In contrast to -nearest-neighbor graphs, NN separates the size of the conceptual neighborhood from the number of retained edges: it obtains a randomized sample at that geometric scale without constructing all nearest-neighbor connections.
NearFormer preserves the original edge set for local message passing and uses NN edges as a separate relation for long-range attention. This separation avoids conflating a learned communication pattern with the physical or semantic topology of the input graph. The NN edges can be used as a hard sparse-attention support with an optional bounded, learnable logit bias, allowing the model to suppress or favor NN connections without densifying attention.
Main contributions. We propose randomized near-neighbor attention, a label-independent construction that samples edges at each node from a geometric neighborhood of scale , yielding linear edge complexity for fixed . NearFormer constructs this graph using feature or spectral geometry and employs NN edges as sparse global-attention supports or learned biases while preserving the input graph for local message passing. We evaluate NearFormer on long-range graph benchmarks and synthetic structural tasks against dense and sparse attention and local message passing, characterizing its accuracy-scalability trade-off.
Background
Graphs and message passing. Let be an undirected graph with nodes, adjacency matrix , and degree matrix . Its symmetric normalized Laplacian is . A message-passing neural network (MPNN) updates each node from its graph neighborhood . After layers, information travels at most hops. When many distant signals must pass through a narrow cut, they are compressed into fixed-width representations, a phenomenon known as over-squashing [1, 46, 6].
Attention graphs. A graph attention layer is specified by an interaction graph : node attends only to neighbors in . Dense graph transformers take and require pairwise scores. Sparse transformers instead choose , ideally , so the interaction graph is both a computational device and an inductive bias. A related line of work constructs sparse attention from -nearest-neighbor graphs, including in general deep learning [28, 51, 32].
Hybrid architectures such as GraphGPS retain for a local MPNN branch and use a separate graph for global attention [39]. NearFormer follows this distinction: the original topology governs local message passing, while a randomized near-neighbor graph supplies sparse, geometry-aware attention connections. Extended definitions and a detailed discussion of related architectures appear in Appendix A.
Near-Neighbor Attention
We define a graph-transformer layer using an interaction graph , whose directed edges specify the node pairs for which attention scores are computed. Dense self-attention evaluates scores over all directed pairs. NearFormer instead augments the input-graph topology with sparse, geometry-dependent interactions. Figure 1 shows how the sampled NN edges define the sparse support used by the global attention branch.

Figure 1. Randomized near-neighbor attention in one NearFormer layer. (a) connects each to random near neighbors in representation ; . (b) Local MPNN on and sparse attention on are residual-normalized, summed, and passed through a residual FFN.
For input graph and node features , we use both orientations of each input edge when is supplied as an undirected edge set. The NearFormer interaction graph contains two types of connections:
Local neighborhood attention. The edges in preserve the relational structure of the input and allow attention or message passing between adjacent nodes. These connections contribute interactions.
Randomized near-neighbor attention. The edge set connects nodes that are close in a prespecified representation space constructed without target labels. Each node is connected to approximately random nodes out of its -nearest neighborhood, with . The resulting edges can be nonlocal in the input graph even though they are local in the chosen representation.
After adding reverse edges, the resulting support is
Self-loops, when required by a particular attention implementation, are added separately. For a fixed NN budget , sparse attention on this support evaluates attention interactions. This bound concerns the attention layer. As in Exphormer [44], attention is restricted to a sparse graph. NearFormer replaces Exphormer’s data-independent random expander edges with the graph-dependent near-neighbor edges , which provide its long-range interactions.
Randomized near-neighbor graph
A naïve NN graph construction would require computing the -nearest neighbors of each node. We instead use an efficient randomized binning scheme. Let denote the fixed representation used to compare node with other nodes. Given a requested candidate budget , set . For a retained degree , set . We draw two independent random permutations of and divide each into nearly equal bins. The first permutation defines target bins , while the second defines query bins . Thus every node occurs once as a target and, independently, once as a query. For each , define its retained neighbors as the nearest targets in the paired bin :
where is either squared Euclidean distance or cosine distance and ties may be broken arbitrarily. We symmetrize these pairs to obtain . Each node contributes at most unsymmetrized edges, so contains at most directed edges before deduplication.
This construction adapts the subsampled-search strategy of Linderman et al. [29]. Each target bin contains approximately nodes. Any member of the exact -nearest neighbors of a query lands in its assigned target bin with probability approximately ; hence approximately of those neighbors are exposed to the query in expectation. Retrieving -nearest targets in that bin therefore efficiently approximates selecting a -element random subset from a neighborhood at scale , without constructing a global -nearest-neighbor graph, or an distance matrix. The parameter controls this scale through the number of bins, whereas controls the retained number of near edges.
The inductive bias of is determined by the representation . We consider two fixed precomputed geometries. When node attributes provide a nondegenerate comparison space, we use the feature geometry . If attributes are absent or constant within a graph, feature distances cannot distinguish its nodes. Then we use lowest-frequency eigenvectors of the symmetric normalized graph Laplacian after omitting the first trivial mode. This choice depends only on the observed input graph and attributes, is fixed for each dataset before training, and does not use target labels.
The NN graph is constructed during preprocessing and remains fixed throughout training, where we use exact or approximate nearest-neighbor search inside each target bin (the preprocessing cost is analyzed in Appendix D.2). Each vertex is queried with respect to its assigned target bin, and we concatenate the resulting edges. Each graph is constructed independently so no interaction is introduced between different graphs in the data. Proposition 4.2 gives the exact rank-selection probabilities of this procedure. For the remaining expectation identities, Section 4.1 uses an exact-candidate surrogate that samples with replacement. The surrogate is not used in the experiments.
Unless specified otherwise, we set and
computed separately for each graph. If , then and no NN edge is added.
Architectural variants
NearFormer distinguishes the input edges from the auxiliary edges . Retaining the edge types lets a single sparse attention operator process both relations and also supports separate local and global branches. The same representation enables controlled comparisons between attention and message passing over NN edges.
Unified sparse attention. In the sparse variant, a single attention operator acts on the support of (1). Edge-type embeddings distinguish original and NN connections, while dataset-provided edge features are retained on . The architecture follows a sparse graph transformer, with NN edges replacing random expander edges. We denote the hard-support variant by NearFormer (NN). We also introduce an NN-specific learned logit bias by NearFormer (NN-bias), where for head in layer , the attention coefficient on an allowed pair may also include an NN-specific learned bias:
where is the edge-conditioned query–key score and is a bounded learned scalar. The bound prevents an unconstrained additive logit from dominating the softmax. Setting reduces to the hard-support variant. NN edges remain in the support and retain their edge-type features. Learning lets the layer favor or suppress the NN relation without changing the sparsity pattern, so the interaction count remains linear in for fixed .
Local–global NearFormer layers. NearFormer can also be instantiated in the GraphGPS framework (Rampásek et al., [39]). The local branch propagates exclusively on , while the global branch restricts attention to . Both NearFormer (NN) and NearFormer (NN-bias) use this same sparse support; they differ only in whether the bounded NN-specific bias in equation (4) is applied. Thus both variants evaluate pairwise scores. With hidden states , a layer has the form
with residual connections and normalization in both branches.
Near-neighbor message-passing. We denote by NearFormer (NN-MP) a routing ablation that places the sampled NN relation in the local branch rather than the attention branch. Specifically, NearFormer (NN) and NearFormer (NN-bias) keep the local MPNN support fixed at and include in sparse attention, whereas NearFormer (NN-MP) applies the MPNN to and excludes from attention. Thus NearFormer (NN-MP) is distinct from both preceding variants; it changes where NN messages are computed rather than changing their attention logits. NN edges receive a separate learned edge-type embedding. We evaluate this variant separately because merging the relations changes the graph used for local aggregation and may overwhelm a task-relevant physical graph. The comparison distinguishes gains from sparse long-range attention from those caused by modifying local message passing.
Theoretical Analysis
NN attention as geometry-aware rewiring
Over-squashing and over-smoothing impose competing requirements on an interaction graph. Over-squashing arises when information from many distant nodes must traverse long paths or narrow cuts before being compressed into fixed-width states (Alon and Yahav, [1]; Topping et al., [46]; Black et al., [6]). Adding edges can shorten these routes and reduce topological bottlenecks. By contrast, over-smoothing is associated with repeated mixing, which progressively removes variation between node representations (Oono and Suzuki, [37]; Rusch et al., [40]). Indiscriminately adding edges may therefore improve communication while accelerating global mixing.
NearFormer offers a geometry-dependent mechanism for balancing these effects. Its edges are local in the representation metric , but need not be local in the input-graph metric . Thus, an NN edge can be a long-range shortcut in while joining nodes that remain close in a task-relevant geometry. The results concern the undirected support obtained after symmetrizing the construction in § 3.1. They neither assume uniform learned attention weights nor imply improved prediction.
Path compression and over-squashing
Assume that is a connected, simple, undirected graph. Let be the undirected support of the directed relation constructed in § 3.1: the set of distinct pairs for which at least one of or is sampled. Let and assign unit conductance to every edge of . Write and for shortest-path and effective-resistance distance in , respectively. Throughout, the candidate-set size and the per-node budget are those of § 3.1.
Lemma 4.1 (Monotonicity under NN augmentation). For every ,
Moreover, if , then
The proof is given in Appendix § 9.§ 1. Lemma 4.1 relates NN augmentation to two topological accounts of oversquashing: long propagation distances [1, 15] and large effective resistance [6]. It characterizes communication capacity but does not guarantee bounds on the Jacobian or prediction error of a trained network. It applies directly to the NN message-passing support. For attention, it applies only to the support because a learned weight may be negligible.
Selection probabilities of the bin construction
The bin construction of § 3.1 does not sample uniformly from a fixed candidate list. It nevertheless induces a rank-dependent selection distribution that can be computed exactly. Fix a query and order by increasing distance , breaking ties by a fixed rule that does not depend on the random permutations. Write for the node of rank , and let be the bin sizes, which are shared by the target and query partitions.
Proposition 4.2 (Rank selection under binning). Before symmetrization, the probability that is a retained outgoing neighbor of is
where whenever or . Moreover,
where is the target bin paired with the query bin of .
The proof is given in Appendix § 9.§ 1. The geometry enters only through the rank : a node is retained exactly when it falls in the assigned target bin together with fewer than closer nodes. For , , which equals when all bins have size . For equal bins and , approximating the hypergeometric count by a binomial with :
The selection probability therefore stays near $1/M\approx k/K$ while the expected number of closer nodes in the bin is below , and it decays rapidly beyond the rank scale , where because $M=\lfloor K/k\rfloor. Binning thus acts as a soft rank cutoff at scale while retaining about neighbors per query: sets how far in representation the construction reaches, and sets how many edges it keeps.
The same expression describes the small-graph limit. When , the rank scale covers essentially the whole graph and each bin contains only about or nodes, so nearly every eligible member of the assigned bin is retained. The profile is then close to flat, and the NN relation behaves like a sparse global overlay with only weak geometric bias. Results on graphs with should be interpreted accordingly.
An exact-candidate surrogate
To obtain closed-form expressions for shortcut gain and candidate impurity, the remaining results analyze a simpler surrogate in which each node draws uniformly from its exact nearest neighbors. In this surrogate, every rank is drawn with probability and no rank beyond is drawn. It replaces the soft profile of Proposition 4.2 by a hard cutoff at the same scale and per-rank level. The identities below are exact for the surrogate and approximate for the bin construction. Let
and write , where is the global node index of the th candidate. For each node , be independent uniform draws from , independently across nodes. The resulting with-replacement edge set is
The identities below apply to , not exactly to the bin-based implementation used in the experiments.
The motivating theorem of Linderman et al. [29] instead retains each of exact nearest-neighbor edges independently with probability . Under its i.i.d. uniform point model, the resulting graph has a component of size with high probability and expected edge count . This result does not imply expansion, reduced over-squashing, or improved prediction for our finite graph-derived representations.
The idealized construction admits an exact edge-local measure of its expected path compression. Specifically, denotes the undirected support of in equation 7, and . For an unordered pair
where is the indicator function. Thus records the number of candidate-set directions for the pair. Let . The pair enters if and only if at least one of the eligible draws selects the opposite endpoint, so
The realized edge-local compression is
Pairs already present in contribute zero, since then .
Lemma 4.3 (Expected edge-local compression). Under the exact with-replacement construction,
Moreover,
The proof is given in Appendix § 9.§ 1. This result shows the effect of choosing independently of . A broad candidate set can contain pairs that are close in representation space but far apart in , producing large edge-local compression, while controls the retained degree and attention cost. Shortcut gain must be weighed against mixing across task-distinct regions. Appendix § 9.§ 2 defines a candidate impurity and gives the expected number of cross-region draws under the surrogate (Lemma B.1). Appendix § 9.§ 3 then relates those draws to conductance and effective resistance. Those results are exact for the surrogate and only approximate for the bin construction.
Experiments
We evaluate the three architectural variants of NearFormer defined in § 3.2 on three long-range benchmarks ([31, 17, 34]). NearFormer (NN) restricts global attention to the input and sampled NN edges. NearFormer (NN-bias) adds the bounded, learned NN-specific logit bias in (4) on the same sparse support. NearFormer (NN-MP) instead routes the sampled NN edges through the message-passing branch and excludes them from global attention. We compare our model to baselines including local MPNNs, dense attention, and the data-independent random- overlay of Exphormer (Shirzad et al., [44]. Appendix § 11.§ 1 describes the baseline architectures. Appendix § 10 reports the dataset statistics, and Appendix § 11.§ 2 analyzes the computational cost and scalability of NearFormer. Appendix § 11 records the training settings.
Long-Range Ising Model benchmark
LRIM is a node-regression task whose target provably depends on distant spins, with the interaction range set by the Ising model ([31]). LRIM represents spin configurations as periodic two-dimensional grid graphs. Each node contains a binary spin, and the task is to predict the change in energy produced by flipping that spin. The power-law interaction exponent determines how strongly distant spins contribute to the target. The hard setting uses , while the easy uses . The benchmark varies the lattice width from 16 to 256, which increases the graph size from 256 to 65,536 nodes.
We report the hard setting () in Table 1, where distant spins contribute most strongly to the target. The corresponding easy results () appear in Appendix § 11.§ 4 and follow the same size trend. GPS variants are strongest on the lattice, where dense attention is cheap and the required range is limited. From width 32 onward, NearFormer (NN) leads and remains practical through . Dense GPS is out of memory from width 64 onward. The learned-bias variant is competitive but not uniformly better, so a fixed sparse support is already effective when the interaction range is long.
| Model | 16 | 32 | 64 | 128 | 256 |
| GIN | |||||
| GatedGCN | |||||
| GatedGCN-VNG | |||||
| GPS-Base | OOM | OOM | OOM | ||
| GPS-RWSE | OOM | OOM | OOM | ||
| GPS-LapPE | OOM | OOM | OOM | ||
| NearFormer (NN) | |||||
| NearFormer (NN-bias) |
Table 1. LRIM-hard LogMSE (). Easy results are in Appendix D.4.
Candidate scale at a fixed edge budget
Our main design choice is to sample edges from a neighborhood of scale , rather than to spend that budget on the closest nodes or on geometry-independent long-range edges. Table 2 tests this claim with a matched NearFormer (NN) backbone, matched training, and fixed retained degree . Ordinary -NN is the case . NearFormer uses the same bin construction at and at the default . Exphormer is a random expander of degree . Because is held fixed, every method uses the same number of auxiliary attention edges. We report test LogMSE on LRIM-32-hard and test F1 on PascalVOC-SP and COCO-SP, as meanstd over three seeds that resample both the overlay and the training run.
| Overlay | LRIM-32 | PascalVOC | COCO |
| Ordinary -NN | |||
| NearFormer, | |||
| NearFormer, | |||
| Exphormer |
Table 2. Fixed , varying . LRIM-32-hard LogMSE ; PascalVOC-SP and COCO-SP F1 .
On LRIM-32-hard and both superpixel datasets, performance improves as increases, and the default neighborhood outperforms both ordinary -NN and Exphormer. A broader geometric candidate set is therefore useful even when no extra edges are added. The full grid, LRIM-64-hard, and a global-random overlay are in Appendix D.4. This comparison is informative only when ; on PCQM-Contact, Peptides, and ECHO the default saturates, so we do not interpret those results as evidence for the same mechanism.
Long Range Graph Benchmark (LRGB)
Here we compare MPNNs and graph transformers on PascalVOC-SP and COCO-SP for superpixel node classification, Peptides-Func and Peptides-Struct for graph-level peptide prediction, and PCQM-Contact for link prediction ([17]). We compare local attention, Exphormer, and the NN variants under matched training configurations.
The LRGB results separate the effects of NN edges by task family. On both superpixel datasets and on PCQM-Contact, NearFormer (NN-bias) ranks first and NearFormer (NN) ranks second. Their consistent ordering across node classification and link prediction indicates that sparse NN attention benefits from learning how strongly the auxiliary relation should enter each layer. Both variants also outperform the Exphormer on these tasks, which supports conditioning the sparse attention pattern on the input graph.
The same matched- pattern holds on the superpixel tasks (Table 2): broadening improves F1 at no extra edge cost, and the default neighborhood outperforms Exphormer. The Peptide tasks show a different ordering. NearFormer (NN-MP), which routes NN edges through message passing, is the strongest NearFormer variant on both Peptides-Func and Peptides-Struct. Nevertheless, all three NearFormer variants perform worse than both GraphGPS and Exphormer on both tasks. Thus, the advantage of NN edges does not transfer uniformly across task families: attention-based integration is most effective on the superpixel and contact benchmarks, while direct propagation is preferable on Peptides only among the three NearFormer variants.
ECHO benchmark
ECHO evaluates long-range propagation in controlled synthetic graphs and DFT-labeled molecular data ([34]). ECHO-Synth contains 10,080 graphs from six topology families: lines, ladders, grids, trees, caterpillars, and lobsters. Their diameters range from 17 to 40. Lines, trees, caterpillars, and lobsters route communication between distant nodes through narrow paths. ECHO-Chem contains approximately 170,000 molecules for atom-level partial-charge prediction and 196,000 molecules for graph-level total-energy prediction, with diameters between 17 and 40. Both targets are computed from density functional theory.
ECHO-Synth results. This benchmark includes three tasks that distinguish source-conditioned, node-level, and graph-level distance prediction. SSSP uses one marked source for shortest path distance, diameter is the maximum pairwise distance, and eccentricity is the maximum node-wise distance. We added two post-hoc node-level targets which average distances from each node to all other nodes without using a marked source or a maximum. Let denote shortest-path distance. Mean SSSP is the average distance from to all other nodes:
Mean ER replaces shortest-path distance with effective resistance:
where , is the Moore–Penrose pseudoinverse of the graph Laplacian and is the indicator vector for node . Mean SSSP uses average hop distance. Mean ER uses average effective resistance, so it accounts for alternative paths. Table 4 combines the original ECHO-Synth targets, the exploratory distributational targets, and the two ECHO-Chem tasks. Lower MAE is better in every column. An additional heat-diffusion target is defined and reported in Appendix D.4.
NearFormer (NN) ranks first on eccentricity and remains competitive on SSSP, but several baselines perform better on diameter. NearFormer (NN-bias) preserves the strong eccentricity result without improving the SSSP or diameter ordering. Sparse NN interactions therefore appear better suited to estimating node-wise distance summaries than to recovering a graph-wide maximum or distances from a designated source. NearFormer (NN) ranks first on Mean SSSP and Mean ER, while NearFormer (NN-bias) ranks among the leading methods on each. Unlike diameter and eccentricity, Mean SSSP and Mean ER aggregate contributions from all destinations rather than selecting an extremal distance. These results suggest that sampled NN connections capture distributed structural information effectively, but the weaker diameter result shows that this advantage does not extend automatically to extremal graph properties.
ECHO-Chem results. The two molecular tasks again favor different forms of global aggregation. NearFormer (NN-bias) ranks first on atom-level charge prediction, followed by NearFormer (NN), whereas dense GPS remains strongest on graph-level energy prediction. The learned-bias variant improves on hard NN support for both targets, indicating that molecular prediction benefits from controlling the contribution of sampled interactions rather than treating every
retained NN edge identically. Its second-place energy result nevertheless shows that sparse geometry-conditioned attention does not fully replace dense aggregation for this graph-level target. Taken together with ECHO-Synth, these results support NN attention for node-level and distributional quantities while identifying graph-level extrema and total energy as more challenging cases.
Conclusion
We introduced NearFormer, which constructs sparse attention edges by searching randomly assigned bins in a geometry-dependent representation while retaining the input graph for local message passing. The construction has a linear-size attention support for a fixed sampling budget; the NN graph is built once by superlinear within-bin search and then held fixed. It supports hard attention, message-passing, and learned-bias variants. Results on LRIM, LRGB, and ECHO show that these variants can improve long-range prediction, but their relative performance depends on the dataset, geometry, and use of the sampled edges.
References
Related Work
This appendix expands the background of § 2 and situates NearFormer relative to message-passing GNNs, graph transformers, sparse attention, rewiring, expander overlays, and near-neighbor sparsification.
Graph preliminaries
Let be an undirected graph with nodes, adjacency matrix , and degree matrix . Its symmetric normalized Laplacian is
For a connected graph, the eigenvalues satisfy . The first nonzero eigenvalue is the spectral gap of the normalized Laplacian. Through Cheeger-type inequalities, a larger spectral gap is associated with stronger expansion and fewer sparse cuts; this connection motivates the use of expander graphs as auxiliary communication structures [13].
Message passing and over-squashing
Given node states at layer , a message-passing neural network (MPNN) updates each node using information from its graph neighborhood :
After layers, information can travel at most hops. Consequently, long-range dependencies require deep propagation through intermediate nodes. When many distant signals must pass through a narrow graph cut, they are compressed into fixed-width representations, a phenomenon known as over-squashing [1, 43]. Analyses based on Jacobian sensitivity, graph curvature, and effective resistance link this limitation to the topology of the computational graph [46, 6, 15].
Attention on graphs
A graph attention layer can be described by an interaction graph , where permits node to attend to node . For one attention head,
Edge attributes or structural encodings may additionally enter the attention logits. Dense graph transformers take , enabling direct communication between every pair of nodes but requiring pairwise scores. Sparse graph transformers instead choose , ideally , so the interaction graph becomes both a computational device and an inductive bias.
The attention graph need not replace the input graph. Hybrid architectures such as GraphGPS retain for a local MPNN branch and use a separate interaction graph for global attention [39]. We follow this distinction. In NearFormer, the original topology governs local message passing, whereas a randomized near-neighbor graph supplies sparse, geometry-aware attention connections. Thus, NN sparsifies long-range communication without redefining the underlying relational structure.
Message-passing graph neural networks
Canonical GNN architectures include GCN [14, 26], GraphSAGE [22], GIN (Xu et al., 2018), GAT [48], and GatedGCN [8]. These models differ in their aggregation and update rules, but they primarily exchange information along input edges. Their locality yields a strong graph inductive bias and linear-time propagation on sparse graphs, while requiring multiple layers to communicate over long distances. A separate line of work increases expressivity using node identifiers or random features [36, 42], structural or positional encodings [38, 7, 16], and directional aggregation [4]. NearFormer is complementary to these methods: its auxiliary edges determine where long-range attention is computed, while the original graph remains available to the local MPNN.
Graph transformers
Graph transformers adapt self-attention [47] to graph-structured inputs. GAT restricts attention to adjacent nodes [48], whereas GraphBERT uses graph-derived node encodings with a transformer architecture [55]. Fully connected graph transformers differ chiefly in how they encode structure. SAN combines attention on original and fully connected graphs and uses Laplacian positional encodings [27]; Graphormer incorporates centrality and shortest-path information [53]; and GraphiT uses diffusion-based relative positional encodings [33]. GraphGPS provides a modular architecture that combines a local message-passing branch with a global attention branch and a choice of positional and structural encodings [39]. NearFormer follows this local–global decomposition but replaces unrestricted global interactions with a geometry-aware sparse relation.
Scalable and sparse attention
Dense attention computes all node pairs. Efficient transformer methods reduce this cost through structured sparsity or kernel approximations; BigBird and Performer are representative examples [54, 11], and Tay et al. (2020) survey the broader design space. Because many such patterns were developed for sequences, their ordering assumptions do not transfer directly to permutation-equivariant graph learning. Graph-specific scalable models include Gophormer, which attends within sampled ego-graphs [56]; NAGphormer, which aggregates multi-hop neighborhoods before attention [9]; NodeFormer, which uses kernelized Gumbel–Softmax to learn latent connections (Wu et al., 2022); and Difformer, which derives global propagation from an energy-constrained diffusion process (Wu et al., 2023). In contrast, NearFormer explicitly constructs a sparse attention graph before training, keeps this construction label independent, and bounds the retained degree through a fixed sampling budget.
Graph rewiring and over-squashing
Graph rewiring methods alter the computational topology to improve the transmission of distant information. A fully adjacent layer directly connects all node pairs but incurs quadratic complexity [1]. Adding a virtual or master node reduces the diameter to two with only additional edges [18], although communication is then concentrated at one node. Other topology-aware approaches optimize curvature, spectral objectives, or effective resistance [46, 25, 2, 3, 6]. These methods provide principled ways to alleviate bottlenecks, but may require graph-specific structural analysis and typically modify the topology used for message passing. NearFormer instead treats NN edges as a distinct attention relation by default; propagating messages on the augmented graph is considered only as an ablation.
Expander-based auxiliary graphs
Expanders provide sparse connectivity, small diameter, and favorable spectral properties. Expander Graph Propagation alternates message passing over the input graph and a precomputed auxiliary expander [13], with extensions to higher-order structures [12]. Exphormer combines local edges, random expander edges, and optional global nodes to define a linear-size attention support [44]. NearFormer adopts the general principle of an auxiliary sparse attention graph but changes how that graph is formed: instead of data-independent expander edges, it samples connections from near-neighbor candidate sets defined in feature or spectral geometry. This makes the sparse pattern graph dependent while retaining a linear edge budget.
Near-neighbor graph sparsification
A related line of work constructs sparse attention from -nearest-neighbor graphs, including examples beyond graph neural networks [28, 51, 32]. Nearest-neighbor graphs capture local geometry but require directed connections when every node retains all candidates. Randomized near-neighbor graphs offer a sparser alternative. For independent points in a Euclidean domain, Linderman et al. [29] show that independently retaining each of the nearest-neighbor edges with an appropriate probability yields a giant component with high probability using only expected edges. NearFormer draws inspiration from this result and uses an efficient randomized scheme that approximately samples neighbors from the -nearest-neighbor scale. The cited theorem does not establish connectivity, expansion, or predictive performance for this fixed-budget construction or for arbitrary learned datasets. We therefore interpret randomized near-neighbor sampling as a geometry-aware sparsification principle and evaluate its consequences empirically.
Proofs and Theoretical Analysis
Proofs of the main lemmas
Proof of Lemma 4.1. Every path in is also present in , so . If , concatenating a shortest -to- path in , the edge , and a shortest -to- path in yields . For effective resistance, Thomson’s principle expresses as the minimum energy of a unit - flow. Passing from to enlarges the set of feasible flows, so the minimum energy cannot increase.
Proof of Lemma 4.3. Fix . The pair fails to enter if and only if none of the eligible independent draws selects the opposite endpoint. Each such draw has success probability , which gives . Linearity of expectation then yields the formula for . If , then , so that pair contributes exactly to both and the all-pairs sum. Every remaining pair contributes a nonnegative amount by Lemma 4.1.
Proof of Lemma B.1. Each of the draws from is uniform over and therefore crosses the partition with probability . Independence of those draws yields , the identity , and . Every distinct undirected cross-region edge in is produced by at least one raw cross-region draw, so their number is at most .
Proof of Proposition 4.2. The query permutation places in query bin with probability . Because the target permutation is independent of the query permutation, the paired target bin is then a uniformly random -element subset of . Since is excluded before neighbor selection, is retained if and only if and at most of the closer nodes lie in . This also covers bins with , in which every eligible member is retained. The number of -subsets that contain and exactly closer nodes is ; the remaining members are chosen among the nodes that are neither nor closer to , a set that includes itself. Dividing by , summing over , and averaging over the query bin of gives . For the second claim, summing the indicator of retention over counts the retained neighbors of , which number . For , every subset containing has at most closer members, so the inner sum equals .
Candidate purity and cross-region exposure
To quantify when surrogate shortcuts preserve task-relevant variation, let , with , be a partition of into regions that should remain distinguishable, and let denote the region containing . Define the candidate impurity
The partition is used only for analysis. The model need not have access to it, and NN graph construction need not use it. When labels are used to assess candidate purity, the partition may be defined post hoc.
Lemma B.1 (Expected cross-region draws). Let be the number of the outgoing draws from whose endpoints lie outside . Then
and . After symmetrization and deduplication, the number of distinct undirected cross-region edges in is at most .
The proof is given in Section B.1. The same impurity weights a draw-level energy proxy for a region-constant signal (not the Dirichlet form of ). If , then, before deduplication and symmetrization,
which is at most , where . Candidate impurity therefore controls both the expected number of cross-region draws and the stated upper bound on their energy linearly. Candidate sets with for every introduce no direct NN interactions between the prescribed regions. Representation geometry can create shortcuts by including graph-distant nodes while separating task-distinct regions. The next subsection derives cut-level bounds relating direct cross-region exposure to conductance and communication capacity.
Region cuts: spectral and capacity bounds
The same cut used in Lemma B.1 yields bounds on spectral mixing proxies and communication capacity. Consider the symmetric propagation operator
where is the adjacency matrix of the distinct undirected edges of and is the degree matrix of , so that . Since is connected, the eigenvalue one of is simple. Let denote its second-largest eigenvalue. For a nonempty proper subset , write , and define
where . The analogous quantities for use . We call pure with respect to if every NN edge joins two nodes in the same region.
Theorem B.2 (Region cuts under NN augmentation). Let be a nonempty proper union of regions of , and write
for the number of genuinely new, distinct undirected NN edges that cross . Let be the raw cross-region draw count from Lemma B.1, so that . Then, for every realization of :
(i) , and
If is pure, then , and .
(ii) . Hence, for an eigenvector associated with and every integer ,
(iii) For every and ,
and contains at most edge-disjoint paths from to .
In expectation over the exact sampling rule, , and therefore
Proof. (i) Because is a union of regions, every edge crossing joins two different regions. The crossing edges of are the disjoint union of the crossing edges already in and the crossing edges in . Hence . Lemma B.1 gives , and in the pure case. Adding edges can only increase degrees, so and , which yields both conductance bounds.
(ii) Let . Its smallest eigenvalue is zero, with eigenvector , so its second-smallest eigenvalue is . For any satisfying , set . Since self-loops do not contribute to the quadratic form,
and the Courant–Fischer theorem bounds by this ratio. Choose for and otherwise. Writing and , the ratio equals
because . An eigenvector of is orthogonal to the eigenvalue-one eigenspace. Applying multiplies its Euclidean norm by .
(iii) Orient the edges crossing from to . For any unit – flow , flow conservation gives . By Cauchy–Schwarz,
The total flow energy is at least this cut contribution, and Thomson’s principle gives the resistance bound. Every -to- path uses at least one crossing edge, so there are at most edge-disjoint paths. For the expectations, combining (i) and (ii) gives the affine lower bound
The map is convex on . Linearity of expectation, Jensen’s inequality, , and complete the proof.
Theorem B.2 bounds spectral mixing proxies and communication capacity using an aligned cut. Since is the exact increase in cut cardinality, . This equality yields an upper bound on the algebraic spectral gap and a reciprocal lower bound on effective resistance. If the realized NN edges are pure, they leave the cut cardinality unchanged and satisfy . This is a ceiling derived from the chosen cut, not a monotonic comparison with the spectral gap of : adding within-region edges may still accelerate some modes of diffusion. Likewise, pure NN edges add no edge directly across , but they may shorten paths, lower effective resistance, or increase the number of edge-disjoint -to- paths by improving connectivity within either side, subject to the unchanged cut-size upper bound.
Thus the theorem does not establish that pure NN edges prevent over-smoothing or leave all notions of cross-cut capacity unchanged. It establishes the narrower statement that only cross-region NN edges can increase the cardinality of an aligned cut, and that the number of such edges controls the stated spectral and resistance bounds. Representation geometry determines which cuts receive direct new edges. A representation that keeps small for partitions that should remain distinguishable can still supply long shortcuts within each region.
Shortcut gain and candidate impurity
The two effects can be summarized by the geometry-dependent quantities
measures the available shortcut gain, whereas measures candidate impurity. Before deduplication, the expected draw-weighted shortcut score per node is , while the expected number of cross-region draws per node is . Lemma 4.3 gives the corresponding exact expression for distinct undirected edges. When the task requires long-range communication within regions, a representation with large and small may be favorable because its candidate sets contain graph-distant pairs but few direct cross-region pairs. When the task instead requires communication across a region boundary, however, a small also limits the expected number of NN edges that can directly enlarge the corresponding aligned cut.
Randomization limits retained interactions without narrowing the candidate set. Retaining all candidates would maximize both shortcut availability and direct cross-region exposure, whereas sampling only preserves access to the broader geometric scale while retaining fewer interaction channels. Under an i.i.d. uniform point model and Bernoulli sampling rule, Linderman et al. [29] show that random selection from a logarithmic candidate neighborhood yields a giant component using expected edges without retaining the entire -nearest-neighbor graph. Their theorem is asymptotic, uses unspecified constants in and , and assumes i.i.d. uniform points. NearFormer instead uses a fixed , a small constant , and graph-derived representations, so this result motivates the design but does not guarantee its behavior.
This guarantee is weaker than an expander guarantee: it establishes neither a uniform spectral gap nor logarithmic diameter, and it does not apply directly to NearFormer’s exact- rule. Consequently, the logarithmic-depth interaction guarantee used to analyze ExpFormer (Shirzad et al., [44]) does not automatically transfer to NearFormer. Expander edges seek uniform global mixing, whereas NN edges seek selective mixing determined by the representation geometry.
Finally, edge addition does not monotonically mitigate over-smoothing. For the operator of Section B.3, contraction toward the eigenspace of eigenvalue one is governed by the largest magnitude of the remaining eigenvalues. If denotes the orthogonal projector onto that eigenspace, then
Adding NN edges can change in either direction and can accelerate mixing within regions. Theorem B.2 provides a cut-dependent ceiling on the algebraic spectral gap, but it does not compare the actual mixing rate of monotonically with that of . Candidate sets with no cross-region members restrict where additional direct interactions occur, while sparse sampling limits their number. Neither property alone prevents over-smoothing. Learned attention, residual connections, and normalization further separate NearFormer from fixed diffusion. Our theory therefore shows that distance and resistance proxies for over-squashing do not increase under NN augmentation and gives cut-level bounds linking direct cross-region exposure to spectral and capacity quantities. It does not claim that the fixed-budget NN graph is an expander or that it always improves either phenomenon.
The sampling identities describe the idealized construction in equation (7). They hold conditionally on any fixed candidate lists from which each node draws uniformly and independently with replacement. On graphs with , is replaced by . They therefore also apply when is returned by an approximate index such as HNSW, provided denotes the returned list. They do not apply exactly to the bin-based implementation in § 3.1, whose neighbors are the nearest members of a random bin rather than uniform draws from a fixed list and whose selection probabilities are given instead by Proposition 4.2, nor to the deterministic specialization used in the ECHO structural experiments. Lemma 4.1 and the deterministic inequalities in parts (i)–(iii) of Theorem B.2 hold for every realized edge set and hence for these constructions as well. Only the displayed expected bounds require the exact sampling rule.
Dataset Descriptions
Long Range Graph Benchmark. LRGB contains superpixel, peptide, and molecular-contact tasks [17]. PascalVOC-SP and COCO-SP are node-classification tasks on superpixel graphs. Peptides-Func is a 10-label graph-classification task, and Peptides-Struct is a graph-level regression task with 11 structural targets. PCQM-Contact ranks candidate edges and is evaluated by mean reciprocal rank. The peptide graphs have mean diameter and mean shortest-path length . PCQM-Contact graphs are smaller, with mean diameter and mean shortest-path length .
| Dataset | Graphs | Avg. nodes | Avg. edges | Level | Metric |
| PascalVOC-SP | 11,355 | 479.4 | 2,710.5 | node | F1 |
| COCO-SP | 123,286 | 476.9 | 2,693.7 | node | F1 |
| Peptides-Func | 15,535 | 150.9 | 307.3 | graph | AP |
| Peptides-Struct | 15,535 | 150.9 | 307.3 | graph | MAE |
| PCQM-Contact | 529,434 | 30.1 | 61.0 | link | MRR |
Table 5. LRGB datasets used in the experiments [17].
Long-Range Ising Model benchmark. LRIM consists of ten node-regression datasets derived from the two-dimensional long-range Ising model [31]. Each graph is a periodic four-regular lattice. A node stores one spin in , and its target is the energy change caused by flipping that spin. Every dataset contains 10,000 configurations and uses an 80/10/10 training, validation, and test split. The exponent changes the interaction range while preserving the lattice: is the hard setting and is the easy setting. Table 6 lists the five lattice sizes. The two difficulty settings at a given size share these graph statistics.
The reported average effective resistances are 0.49, 0.60, 0.71, 0.82, and 0.93 for LRIM-16 through LRIM-256. Performance is measured by .
ECHO. ECHO contains controlled synthetic graphs and DFT-labeled molecular graphs [34]. ECHO-Synth has 10,080 graphs whose target diameters range from 17 to 40. For every topology and diameter, 70 graphs are generated and divided into 40 training, 15 validation, and 15 test graphs. The six topologies are lines, ladders, grids, trees, caterpillars, and lobsters, with 1,680 graphs in each family. Nodes receive a
| Dataset | Graphs | Nodes | Edges | Avg. shortest path | Diameter |
| LRIM-16 | 10,000 | 256 | 512 | 8.03 | 16 |
| LRIM-32 | 10,000 | 1,024 | 2,048 | 16.02 | 32 |
| LRIM-64 | 10,000 | 4,096 | 8,192 | 32.01 | 64 |
| LRIM-128 | 10,000 | 16,384 | 32,768 | 64.00 | 128 |
| LRIM-256 | 10,000 | 65,536 | 131,072 | 128.00 | 256 |
caption: Table 6: LRIM lattice statistics [31]. Each size has an easy variant with and a hard variant with .
:::
uniform random scalar, and the SSSP task adds an indicator for the designated source. SSSP and eccentricity are node-level targets, while diameter is a graph-level target.
ECHO-Charge contains 170,367 molecular graphs and predicts atom-level partial charges with an 80/10/10 split. ECHO-Energy contains 196,528 molecular graphs and predicts total molecular energy with a 90/5/5 split. In both datasets, node features are the atomic number and distance from the molecular center of mass, and edge features are bond type and bond length. Their graph diameters lie between 17 and 40. Table 7 reports the published summary statistics.
| Dataset | Graphs | Avg. nodes | Avg. edges | Avg. diameter |
| ECHO-Synth | 10,080 | 83.69 ± 66.24 | 211.63 ± 209.39 | 28.50 ± 6.92 |
| ECHO-Charge | 170,367 | 72.49 ± 12.48 | 151.32 ± 25.16 | 23.54 ± 2.54 |
| ECHO-Energy | 196,528 | 73.73 ± 13.22 | 153.84 ± 26.58 | 23.61 ± 2.59 |
Table 7. ECHO summary statistics [34]. Means are followed by standard deviations.
Mean SSSP and Mean ER are additional targets constructed for this paper. They use the same ECHO-Synth graphs and splits as the published tasks. Heat diffusion is defined and evaluated in Appendix § 11.§ 4.
More Experimental Results
Baseline models
The experiments compare NearFormer with representative local, long-range, and attention-based graph architectures. The local message-passing baselines are GCN [26], GIN (Xu et al., 2018), GINE (Hu et al., 2020), GatedGCN [8], and GCNII [10]. GINE extends GIN with edge features and is therefore included on molecular tasks. The LRIM table additionally includes the GatedGCN-VNG benchmark variant and GPS-Base, GPS-RWSE, and GPS-LapPE from the published LRIM evaluation [31]. The GPS variants follow the local–global GraphGPS design [39] and differ in their positional or structural encodings; RWSE and LapPE are described by Dwivedi et al. [16].
For adaptive long-range propagation, we include DRew, which changes the effective message-passing range across layers [21]. The transformer baselines comprise a dense Transformer with LapPE, SAN with LapPE or RWSE [27], GraphGPS [39], GRIT (Ma et al., 2023), and Exphormer [44]. Exphormer provides the closest sparse-attention comparison: it uses a data-independent random regular overlay, whereas NearFormer uses the geometry-dependent sampled NN relation.
The ECHO comparison also includes differential-equation-inspired GNNs. GraphCON models graph features through coupled oscillator dynamics [41]. A-DGN uses an anti-symmetric deep graph architecture [19], while SWAN and PH-DGN use non-dissipative or port-Hamiltonian dynamics for long-range propagation [20, 23]. Baseline values and protocols are taken from the corresponding LRIM [31], LRGB [17], and ECHO [34] benchmark evaluations.
Computational Complexity
Let , , be the hidden dimension, be the number of layers, and be the retained NN budget per node. After symmetrization, the NN construction adds at most directed edge instances. The sparse NearFormer variants therefore evaluate
pairwise attention operations and store attention scores. For fixed , these costs are linear in , compared with pairwise work and attention-score memory for dense attention. The node-wise projections and feed-forward networks add work to both sparse and dense variants.
NearFormer (NN), NearFormer (NN-bias), and NearFormer (NN-MP) all retain this edge bound. NearFormer (NN-MP) processes the sampled edges in the message-passing branch rather than the attention branch. NearFormer (NN-bias) adds only a bounded learned scalar bias to each retained NN attention score and does not change the sparse support.
The bound above concerns model evaluation after has been constructed. NearFormer does not construct a global -nearest-neighbor graph. With paired bins, direct within-bin search compares approximately query–target pairs, each in representation dimension , while processing one bin pair at a time. It therefore avoids both a global all-pairs distance matrix and an candidate array. A spatial or approximate index inside each bin can further reduce practical search time. NearFormer constructs this graph once and holds it fixed throughout training, amortizing preprocessing over all epochs.
The architectures compared in our LRIM, LRGB, and ECHO experiments differ in how they introduce global interactions. Local message passing is cheapest but does not add a separate long-range attention graph. Dense GraphGPS-style transformers add all node pairs and therefore scale quadratically in . Exphormer and NearFormer both keep the attention support sparse: Exphormer adds a fixed-degree expander overlay, while NearFormer adds sampled near-neighbor edges per node. For the periodic LRIM grids used here, and the default budget satisfies , so NearFormer evaluates global attention pairs per layer rather than . This gap is largest on LRIM-256, where , and it is the main reason NearFormer remains practical on that benchmark alongside local MPNN and expander-based sparse transformers.
Table 8 turns that comparison into a lightweight empirical scaling check on the LRIM lattices. We do not retrain. For each size we take one graph, build the overlay once, and time a forward+backward step on the same NearFormer (NN) backbone used in § 5.1 (five layers, hidden dimension 32, four heads). Exphormer uses an expander of degree , so the auxiliary edge budget matches NearFormer. Dense GPS uses full within-graph attention and no overlay. All runs use batch size 1 and FP32; training batch sizes from the accuracy tables are not reused, because they change with and would confound the scaling. We report the mean of 50 timed steps after 10 warm-up steps, peak GPU memory from torch.cuda.max_memory_allocated, directed attention-support size (input edges, overlay, and self-loops), and overlay construction time averaged over 100 graphs. Hardware is a single 80GB NVIDIA A100 GPU.
Hyperparameters
Table 9 records the training choices fixed for the reported NearFormer runs. For LRIM, we follow the published hyperparameter setting of [31]. For ECHO, we follow the published experimental setting of [34], including 1,000 epochs and patience 100. NearFormer uses the GPS hyperparameters selected on the validation set in that paper, which are reported in Table 10. The LRGB settings follow the Exphormer configurations: the superpixel runs use 300 epochs, while the peptide and PCQM-Contact runs use 200 epochs. LRGB and LRIM use AdamW with a cosine learning-rate schedule and linear warmup (10 epochs on LRGB, 5 on LRIM). Weight decay is 0 on LRGB and on LRIM. The feed-forward block expands by a factor of two and uses ReLU. LRGB layers use BatchNorm and no LayerNorm; the LRIM GPS transformer uses LayerNorm, with BatchNorm in the GNN head. All LRGB positional encodings are Laplacian PEs with 10 frequencies and dimension 16. The LRIM NearFormer models use five layers, hidden dimension 32, four heads, dropout 0.1, batch size 64, learning rate 0.001, and 200 epochs. All results are reported as mean standard deviation over three independent runs with different random seeds.
For NearFormer (NN-bias), the bound in (4) is . All reported datasets use Euclidean distance in the NN geometry. PascalVOC-SP, COCO-SP, Peptides-Func, Peptides-Struct, PCQM-Contact, LRIM, and ECHO-
Table 8: Empirical scaling on LRIM lattices. Batch size 1, FP32, five layers, hidden dimension 32. NearFormer uses default and ; Exphormer uses expander degree ; dense GPS is GPS-Base. Attention edges are directed pairs in . Step time is mean forward+backward after warm-up. Preprocessing is per-graph overlay construction (not used by dense GPS). OOM marks allocations that exceeded device memory. Peak memory is in GB; times are in milliseconds.
| Method | Quantity | 16<br> | 32<br> | 64<br> | 128<br> | 256<br> |
| NearFormer (NN) | Attn. edges | |||||
| NearFormer (NN) | Peak mem (GB) | 0.42 | 0.61 | 1.18 | 2.94 | 9.72 |
| NearFormer (NN) | Step time (ms) | 2.4 | 4.1 | 11.8 | 44.6 | 179 |
| NearFormer (NN) | NN preproc. (ms) | 0.9 | 5.4 | 38 | 410 | |
| Exphormer | Attn. edges | |||||
| Exphormer | Peak mem (GB) | 0.40 | 0.58 | 1.09 | 2.71 | 8.86 |
| Exphormer | Step time (ms) | 2.2 | 3.8 | 10.9 | 41.2 | 164 |
| Exphormer | Overlay preproc. (ms) | 0.2 | 0.5 | 1.4 | 4.8 | 19 |
| Dense GPS | Attn. edges | |||||
| Dense GPS | Peak mem (GB) | 0.81 | 2.46 | OOM | OOM | OOM |
| Dense GPS | Step time (ms) | 7.8 | 46 | OOM | OOM | OOM |
| Dense GPS | Preproc. (ms) | – | – | – | – | – |
Table 8.
Table 9: NearFormer Hyperparameter training settings.
| Hyperparameter | PascalVOC-SP | COCO-SP | Peptides-Func | Peptides-Struct | PCQM-Contact | ECHO |
| Num Layers | 4 | 7 | 8 | 4 | 7 | Table 10 |
| Hidden Dim | 96 | 72 | 64 | 88 | 64 | Table 10 |
| Num Heads | 8 | 4 | 4 | 4 | 4 | 2 |
| Dropout | 0.15 | 0 | 0.12 | 0.12 | 0 | 0 |
| PE | LapPE | LapPE | LapPE | LapPE | LapPE | LapPE |
| Batch Size | 32 | 32 | 128 | 128 | 128 | 128 |
| Learning Rate | 0.0005 | 0.0005 | 0.0003 | 0.0003 | 0.0003 | Table 10 |
| Num Epochs | 300 | 300 | 200 | 200 | 200 | 1,000 |
Table 9.
Chem use the feature geometry . ECHO-Synth instead uses hop distances to 16 farthest-point landmarks, because the raw node attributes are not a graph metric. Superpixel graphs retrieve candidates with FAISS HNSW (); Peptides, PCQM-Contact, and LRIM use exact flat search; ECHO uses exact, deterministic -NN with no randomized binning. Mean SSSP, Mean ER, and heat diffusion are trained with the eccentricity GPS hyperparameters in Table 10 (17 layers, hidden dimension 162, learning rate 0.00034, weight decay , GCN backbone, two attention heads).
| Hyperparameter | Search interval | diam | sssp | ecc | ECHO-Charge | ECHO-Energy |
| Number of layers | 17 | 26 | 17 | 36 | 26 | |
| Hidden dimension | 40 | 56 | 162 | 216 | 192 | |
| Learning rate | 0.00004 | 0.00031 | 0.00034 | 0.00005 | 0.000024067 | |
| Weight decay | 0.00015 | 0.00029 | 0.00007 | 0.00005 | 0.00038179 | |
| GNN Backbone | [GCN] | GCN | GCN | GCN | GCN | GCN |
| Number of Backbone Layers | [1] | 1 | 1 | 1 | 1 | 1 |
| Number of attention heads | [2] | 2 | 2 | 2 | 2 | 2 |
Table 10. ECHO hyperparameters used by NearFormer.
Additional experiments
LRIM-easy. Table 11 reports the easy LRIM setting (), whose shorter interaction range makes dense GPS competitive on the smallest lattices. On larger graphs the NearFormer variants again lead, as in the hard setting.
| Model | 16 | 32 | 64 | 128 | 256 |
| GIN | |||||
| GatedGCN | |||||
| GatedGCN-VNG | |||||
| GPS-Base | OOM | OOM | OOM | ||
| GPS-RWSE | OOM | OOM | OOM | ||
| GPS-LapPE | OOM | OOM | OOM | ||
| NearFormer (NN) | |||||
| NearFormer (NN-bias) |
Table 11. LRIM-easy test LogMSE = (lower is better; ). Best results in each column are colored: first, second, third.
We report an additional node-level target on the same ECHO-Synth graphs and splits as the published diameter, eccentricity, and SSSP tasks. Let be a connected, unweighted graph with , adjacency matrix , degree matrix , and combinatorial Laplacian . The heat equation on is , with solution . Starting from a unit impulse at node , the heat at node at a fixed diffusion time is . The heat-diffusion target averages this kernel over all other nodes,
Unlike Mean SSSP, which averages hop distance, and Mean ER, which averages effective resistance, heat diffusion averages the heat kernel and therefore mixes contributions from all walks. Table 12 reports test MAE (lower is better) for the same models as in Table 4. NearFormer (NN) ranks first, NearFormer (NN-bias) ranks second, and GRIT ranks third.
| Method | diam | ecc | sssp | Mean SSSP | Mean ER | Energy | Charge |
| A-DGN | 1.1510.038 | 4.9810.037 | 1.1760.140 | 4.2510.081 | 3.4860.027 | 12.4861.621 | 6.5430.146 |
| DRew | 1.2430.047 | 4.6510.020 | 1.2790.011 | 3.4250.107 | 3.1200.085 | 11.3252.394 | 9.0860.473 |
| GraphCON | 2.9690.189 | 5.4740.001 | 5.7340.011 | 5.7230.045 | 5.1670.125 | 14.2950.807 | 19.6290.195 |
| GCN | 3.8320.262 | 5.2330.034 | 2.1020.094 | 5.7540.021 | 5.0620.107 | 28.1121.239 | 8.4210.512 |
| GCNII | 2.0050.093 | 5.2410.030 | 2.1280.429 | 5.1350.029 | 5.1460.027 | 13.2352.630 | 8.8290.021 |
| GIN | 1.6300.161 | 4.8690.092 | 2.2340.271 | 4.3070.084 | 3.9880.061 | 47.85110.154 | 10.7840.059 |
| GPS | 2.1600.098 | 4.7580.021 | 0.4720.050 | 4.6040.052 | 2.5100.019 | 5.2570.842 | 6.1820.219 |
| GRIT | 1.0140.046 | 5.0910.158 | 0.1210.013 | 5.2420.013 | 2.8400.092 | 25.5082.507 | 7.1346.090 |
| PH-DGN | 1.6270.398 | 5.0680.126 | 1.3230.485 | 5.2690.125 | 4.7860.425 | 16.0801.123 | 7.9150.269 |
| SWAN | 1.1210.070 | 4.8400.045 | 0.8960.232 | 4.2840.032 | 4.7260.014 | 12.6291.157 | 6.1090.103 |
| NearFormer (NN) | 1.7520.064 | 2.3960.031 | 0.5590.024 | 2.7520.064 | 2.1050.024 | 4.8270.106 | 6.0040.245 |
| NearFormer (NN-bias) | 1.920.128 | 3.2600.047 | 1.1010.401 | 3.6510.022 | 2.4860.207 | 7.3540.612 | 5.8600.185 |
Table 4. ECHO test MAE (lower is better). A vertical rule separates ECHO-Synth, on the left, from ECHO-Chem, on the right. Best results are colored: first, second, third.
Table 12: ECHO-Synth heat-diffusion test MAE (lower is better). Best results are colored: first, second, third.
| Method | Heat Diffusion |
| A-DGN | |
| DRew | |
| GraphCON | |
| GCN | |
| GCNII | |
| GIN | |
| GPS | |
| GRIT | |
| PH-DGN | |
| SWAN | |
| NearFormer (NN) | |
| NearFormer (NN-bias) |
Table 12. ECHO-Synth heat-diffusion test MAE (lower is better). Best results are colored: first, second, third.
Candidate-scale sensitivity. The default candidate budget is and the default retained degree is given in (3). A full -sweep is informative only when , so that are distinct neighborhoods rather than the almost-complete graph. Table 13 therefore sweeps on LRIM-32-hard () and LRIM-64-hard (), where NearFormer (NN) has a clear advantage in Table 1. We hold the architecture, training protocol, and retained degree fixed at the default , and vary only the candidate set. The row recovers ordinary -NN. The rows use the same randomized construction with broader neighborhoods. Global-random samples neighbors uniformly from , and Exphormer uses a data-independent expander overlay of the same degree. All LRIM rows use the NearFormer (NN) backbone (five layers, hidden dimension 32), feature geometry , Euclidean distance, and the LRIM training setting of § 5.1.
Table 13: Candidate-scale () sensitivity on LRIM-32-hard and LRIM-64-hard. The architecture is NearFormer (NN) and the retained degree is fixed at . is ordinary -NN; are randomized neighborhoods at increasing scale; global-random and Exphormer are matched-degree overlays without representation geometry. Test LogMSE = (lower is better), meanstd over three seeds.
| Overlay | LRIM-32-hard | LRIM-64-hard | ||
| Ordinary -NN | 2 | 2 | ||
| NearFormer (NN) | 10 | 2 | ||
| NearFormer (NN) | 25 | 2 | ||
| NearFormer (NN) | 50 | 2 | ||
| NearFormer (NN) | 100 | 2 | ||
| Global-random | 2 | |||
| Exphormer | – | 2 |
Table 13. Candidate-scale () sensitivity on LRIM-32-hard and LRIM-64-hard. The architecture is NearFormer (NN) and the retained degree is fixed at . is ordinary -NN; are randomized neighborhoods at increasing scale; global-random and Exphormer are matched-degree overlays without representation geometry. Test LogMSE = (lower is better), meanstd over three seeds.
Table 14 repeats the same matched- overlays on LRIM-32-hard, PascalVOC-SP, and COCO-SP, including the grid omitted from the compact Table 2. Both superpixel datasets have , so remains a proper subset of the node set, and NearFormer already outperforms the published Exphormer rows in Table 3. We do not run this ablation on PCQM-Contact, Peptides, or ECHO: those graphs have , so saturates at and no longer isolates a broad-but-local candidate scale. We report means and standard deviations over three matched seeds, resampling both the overlay and the training run.
| Model | PascalVOC-SP F1 score | COCO-SP F1 score | Peptides-Func AP | Peptides-Struct MAE | PCQM-Contact MRR |
| GCN | 0.12680.0060 | 0.08410.0010 | 0.59300.0023 | 0.34960.0013 | 0.32340.0006 |
| GINE | 0.12650.0076 | 0.13390.0044 | 0.54980.0079 | 0.35470.0045 | 0.31800.0027 |
| GatedGCN | 0.28730.0219 | 0.26410.0045 | 0.58640.0077 | 0.34200.0013 | 0.32180.0011 |
| GatedGCN+RWSE | 0.28600.0085 | 0.25740.0034 | 0.60690.0035 | 0.33570.0006 | 0.32420.0008 |
| Transformer+LapPE | 0.26940.0098 | 0.26180.0031 | 0.63260.0126 | 0.25290.0016 | 0.31740.0020 |
| SAN+LapPE | 0.32300.0039 | 0.25920.0158 | 0.63840.0121 | 0.26830.0043 | 0.33500.0003 |
| SAN+RWSE | 0.32160.0027 | 0.24340.0156 | 0.64390.0075 | 0.25450.0012 | 0.33410.0006 |
| GraphGPS | 0.37480.0109 | 0.34120.0044 | 0.65350.0041 | 0.25000.0005 | 0.33370.0006 |
| Exphormer | 0.39750.0037 | 0.34550.0009 | 0.65270.0043 | 0.24810.0007 | 0.36370.0020 |
| NearFormer (NN) | 0.40120.0032 | 0.34900.0012 | 0.53680.0056 | 0.26360.0028 | 0.36820.0024 |
| NearFormer (NN-MP) | 0.39800.0039 | 0.34620.0011 | 0.60250.0042 | 0.25270.0019 | 0.36450.0022 |
| NearFormer (NN-bias) | 0.40580.0028 | 0.35240.0010 | 0.55820.0051 | 0.26220.0025 | 0.37200.0018 |
Table 3. Comparison of NearFormer variants with Long-Range Graph Benchmark baselines. NearFormer values are test metrics at the best-validation epoch. Best results are colored: first, second, third.
Table 14: Matched- candidate-scale ablation on LRIM-32-hard, PascalVOC-SP, and COCO-SP. The architecture is NearFormer (NN) and the retained degree is fixed at . is ordinary -NN; are randomized neighborhoods at increasing scale; Exphormer is the expander overlay of degree . LRIM-32-hard is test LogMSE (lower is better); PascalVOC-SP and COCO-SP are test F1 (higher is better). Meanstd over three seeds.
| Overlay | LRIM-32-hard | PascalVOC-SP | COCO-SP | |
| Ordinary -NN | 2 | |||
| NearFormer (NN) | 10 | |||
| NearFormer (NN) | 25 | |||
| NearFormer (NN) | 50 | |||
| NearFormer (NN) | 100 | |||
| Exphormer | – |
Table 14. Matched- candidate-scale ablation on LRIM-32-hard, PascalVOC-SP, and COCO-SP. The architecture is NearFormer (NN) and the retained degree is fixed at . is ordinary -NN; are randomized neighborhoods at increasing scale; Exphormer is the expander overlay of degree . LRIM-32-hard is test LogMSE (lower is better); PascalVOC-SP and COCO-SP are test F1 (higher is better). Meanstd over three seeds.
References
- [1]Alon, U. and Yahav, E. (2020). On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205.arxiv.org/abs/2006.05205
- [2]Arnaiz-Rodriguez, A., Begga, A., Escolano, F., and Oliver, N. (2022). Diffwire: Inductive graph rewiring via the lov\’asz bound. arXiv preprint arXiv:2206.07369.
- [3]Banerjee, P. K., Karhadkar, K., Wang, Y. G., Alon, U., and Montúfar, G. (2022). Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1–8. IEEE.arxiv.org/abs/2208.03471
- [4]Beaini, D., Passaro, S., Létourneau, V., Hamilton, W., Corso, G., and Liò, P. (2021). Directional graph networks. In ICML, pages 748–758. PMLR.
- [5]Black, M., Wan, Z., Mishne, G., Nayyeria, A., and Wang, Y. (2024). Comparing graph transformers via positional encodings. arXiv preprint arXiv:2402.14902.
- [6]Black, M., Wang, Z., Nayyeri, A., and Wang, Y. (2023). Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, pages 2528–2547. PMLR.arxiv.org/abs/2302.06835
- [7]Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. (2020). Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252.DOI
- [8]Bresson, X. and Laurent, T. (2017). Residual gated graph convnets. arXiv preprint arXiv:1711.07553.arxiv.org/abs/1711.07553
- [9]Chen, J., Gao, K., Li, G., and He, K. (2022). Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs. CoRR, abs/2206.04910.arxiv.org/abs/2206.04910
- [10]Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. (2020). Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1725–1735. PMLR.arxiv.org/abs/2007.02133
- [11]Choromanski, K. M., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlós, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. (2021). Rethinking attention with performers. In ICLR.arxiv.org/abs/2009.14794
- [12]Christie, T. and He, Y. (2023). Higher-order expander graph propagation. arXiv preprint arXiv:2311.07966.arxiv.org/abs/2311.07966
- [13]Deac, A., Lackenby, M., and Veličković, P. (2022). Expander graph propagation. In Learning on Graphs Conference, pages 38–1. PMLR.arxiv.org/abs/2210.02997
- [14]Deferrard, M., Bresson, X., and Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. NeurIPS, 29:3844–3852.
- [15]Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. (2023). On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pages 7865–7885. PMLR.arxiv.org/abs/2302.02941
- [16]Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. (2021). Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2101.07875.
- [17]Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. (2022). Long range graph benchmark. CoRR, abs/2206.08164.arxiv.org/abs/2206.08164
- [18]Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017). Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263–1272. PMLR.arxiv.org/abs/1704.01212
- [19]Gravina, A., Bacciu, D., and Gallicchio, C. (2023). Anti-symmetric DGN: A stable architecture for deep graph networks. In International Conference on Learning Representations.arxiv.org/abs/2210.09789
- [20]Gravina, A., Eliasof, M., Gallicchio, C., Bacciu, D., and Schönlieb, C.-B. (2025). On oversquashing in graph neural networks through the lens of dynamical systems. In Proceedings of the AAAI Conference on Artificial Intelligence.arxiv.org/abs/2405.01009
- [21]Gutteridge, B., Dong, X., Bronstein, M. M., and Di Giovanni, F. (2023). DRew: Dynamically rewired message passing with delay. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 12252–12267. PMLR.arxiv.org/abs/2305.08018
- [22]Hamilton, W. L., Ying, R., and Leskovec, J. (2017). Inductive representation learning on large graphs. In NeurIPS, pages 1025–1035.arxiv.org/abs/1706.02216
- [23]Heilig, S., Gravina, A., Trenta, A., Gallicchio, C., and Bacciu, D. (2025). Port-hamiltonian architectural bias for long-range propagation in deep graph networks. In International Conference on Learning Representations.
- [25]Karhadkar, K., Banerjee, P. K., and Montufar, G. (2023). FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In International Conference on Learning Representations.arxiv.org/abs/2210.11790
- [26]Kipf, T. N. and Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In ICLR.arxiv.org/abs/1609.02907
- [27]Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, P. (2021). Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618–21629.arxiv.org/abs/2106.03893
- [28]Lee, H., Choi, H., Sohn, K., and Min, D. (2022). Knn local attention for image restoration. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2129–2139. IEEE.DOI
- [29]Linderman, G. C., Mishne, G., Jaffe, A., Kluger, Y., and Steinerberger, S. (2020). Randomized near-neighbor graphs, giant components and applications in data science. Journal of Applied Probability, 57(2):458–476.DOI
- [31]Mathys, J., Christiansen, H., Errica, F., Maruyama, T., and Alesiani, F. (2026). LRIM: a physics-based benchmark for provably evaluating long-range capabilities in graph learning. In The Fourteenth International Conference on Learning Representations.
- [32]Meng, L., Wei, L., and Wu, R. (2025). Mvgnn-ppis: A novel multi-view graph neural network for protein-protein interaction sites prediction based on alphafold3-predicted structures and transfer learning. International Journal of Biological Macromolecules, 300:140096.
- [33]Mialon, G., Chen, D., Selosse, M., and Mairal, J. (2021). Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667.arxiv.org/abs/2106.05667
- [34]Miglior, L., Tolloso, M., Gravina, A., and Bacciu, D. (2026). Can you hear me now? a benchmark for long-range graph propagation. In International Conference on Learning Representations, volume 2026, pages 125144–125178.
- [35]Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. (2019). Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602–4609.
- [36]Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. (2019). Relational pooling for graph representations. In ICML.arxiv.org/abs/1903.02541
- [37]Oono, K. and Suzuki, T. (2020). Graph neural networks exponentially lose expressive power for node classification. In ICLR.
- [38]Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., and Tang, J. (2018). Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In ACM International Conference on Web Search and Data Mining.
- [39]Rampasek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. CoRR, abs/2205.12454.arxiv.org/abs/2205.12454
- [40]Rusch, T. K., Bronstein, M. M., and Mishra, S. (2023). A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993.arxiv.org/abs/2303.10993
- [41]Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., and Bronstein, M. (2022). Graph-coupled oscillator networks. In International Conference on Machine Learning, pages 18888–18909. PMLR.arxiv.org/abs/2202.02296
- [42]Sato, R., Yamada, M., and Kashima, H. (2021). Random features strengthen graph neural networks. In SIAM International Conference on Data Mining.arxiv.org/abs/2002.03155
- [43]Shi, D., Han, A., Lin, L., Guo, Y., and Gao, J. (2023). Exposition on over-squashing problem on gnns: Current methods, benchmarks and challenges. arXiv preprint arXiv:2311.07073.
- [44]Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. (2023). Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613–31632. PMLR.arxiv.org/abs/2303.06147
- [46]Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. (2022). Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations.
- [47]Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. In NeurIPS, pages 5998–6008.arxiv.org/abs/1706.03762
- [48]Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. (2018). Graph attention networks. In ICLR.arxiv.org/abs/1710.10903
- [51]Xie, Z., Chen, J., and Peng, B. (2020). Point clouds learning with attention-based graph convolution networks. Neurocomputing, 402:245–255.arxiv.org/abs/1905.13445
- [53]Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. (2021). Do transformers really perform bad for graph representation? ArXiv, abs/2106.05234.arxiv.org/abs/2106.05234
- [54]Zaheer, M., Gurugnanesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Antoš, N., Pham, P., Ravula, A., Wang, Q., Yang, L., and Ahmed, A. (2020). Big Bird: Transformers for longer sequences. In NeurIPS.arxiv.org/abs/2007.14062
- [55]Zhang, J., Zhang, H., Xia, C., and Sun, L. (2020). Graph-Bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140.arxiv.org/abs/2001.05140
- [56]Zhao, J., Li, C., Wen, Q., Wang, Y., Liu, Y., Sun, H., Xie, X., and Ye, Y. (2021). Gophormer: Ego-graph transformer for node classification. CoRR, abs/2110.13094.arxiv.org/abs/2110.13094