betaFeedback

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 kk, the resulting attention support has linear size O(∣E∣+nk)\mathcal{O}(|E|+nk). 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 O(n2)O(n^2) time and memory for a graph with nn 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 kk randomly selected neighbors from a broader neighborhood at the scale of its KK nearest neighbors [29]. The geometry may be defined by node attributes or graph Laplacian eigenvectors. Retaining kk neighbors per node yields at most 2nk2nk directed edge instances after symmetrization, and hence linear edge complexity for fixed kk. In contrast to KK-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 KK 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 kk edges at each node from a geometric neighborhood of scale KK, yielding linear edge complexity for fixed kk. 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 G=(V,E)G = (V, E) be an undirected graph with n=∣V∣n = |V| nodes, adjacency matrix A∈Rn×nA \in\mathbb{R}^{n \times n}, and degree matrix D=diag⁡(d1,…,dn)D = \operatorname{diag}(d_1, \ldots, d_n). Its symmetric normalized Laplacian is L=I−D−1/2AD−1/2L = I - D^{-1/2} A D^{-1/2}. A message-passing neural network (MPNN) updates each node from its graph neighborhood NG(v)\mathcal{N}_G(v). After LL layers, information travels at most LL 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 H=(V,EH)H = (V, E_H): node vv attends only to neighbors in HH. Dense graph transformers take EH=V×VE_H = V \times V and require O(n2)O(n^2) pairwise scores. Sparse transformers instead choose ∣EH∣≪n2|E_H| \ll n^2, ideally O(n)O(n), so the interaction graph is both a computational device and an inductive bias. A related line of work constructs sparse attention from kk-nearest-neighbor graphs, including in general deep learning [28, 51, 32].

Hybrid architectures such as GraphGPS retain EE 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 HH, whose directed edges specify the node pairs for which attention scores are computed. Dense self-attention evaluates O(n2)O(n^2) 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.

Randomized near-neighbor attention in one NearFormer layer

Figure 1. Randomized near-neighbor attention in one NearFormer layer. (a) ENNE_{\mathrm{NN}} connects each vv to kk random near neighbors in representation ZZ; EH=E∪ENNE_H = E \cup E_{\mathrm{NN}}. (b) Local MPNN on EE and sparse attention on EHE_H are residual-normalized, summed, and passed through a residual FFN.

For input graph G=(V,E)G = (V, E) and node features ZZ, we use both orientations of each input edge when EE is supplied as an undirected edge set. The NearFormer interaction graph contains two types of connections:

  1. Local neighborhood attention. The edges in EE preserve the relational structure of the input and allow attention or message passing between adjacent nodes. These connections contribute O(∣E∣)O(|E|) interactions.

  1. Randomized near-neighbor attention. The edge set ENNE_{\mathrm{NN}} connects nodes that are close in a prespecified representation space constructed without target labels. Each node is connected to approximately kk random nodes out of its KK-nearest neighborhood, with k≪Kk \ll K. 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

EH=E∪ENN.(1)E_H = E \cup E_{\mathrm{NN}}. \tag*{(1)}

Self-loops, when required by a particular attention implementation, are added separately. For a fixed NN budget kk, sparse attention on this support evaluates O(∣E∣+nk)=O(∣E∣+n)O(|E| + nk) = O(|E| + n) 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 ENNE_{\mathrm{NN}}, which provide its long-range interactions.

Randomized near-neighbor graph

A naïve NN graph construction would require computing the KK-nearest neighbors of each node. We instead use an efficient randomized binning scheme. Let zi∈Rdzz_i \in\mathbb{R}^{d_z} denote the fixed representation used to compare node viv_i with other nodes. Given a requested candidate budget K0K_0, set K=min⁡{K0,n−1}K = \min\{K_0,n-1\}. For a retained degree k≤Kk \leq K, set M=max⁡{1,⌊K/k⌋}M = \max\{1,\lfloor K/k\rfloor\}. We draw two independent random permutations of VV and divide each into MM nearly equal bins. The first permutation defines target bins B1,…,BMB_1,\ldots,B_M, while the second defines query bins Q1,…,QMQ_1,\ldots,Q_M. Thus every node occurs once as a target and, independently, once as a query. For each vi∈Qbv_i \in Q_b, define its retained neighbors as the kk nearest targets in the paired bin BbB_b:

Nb,k(vi)=arg⁡min⁡S⊆Bb∖{vi}∣S∣=min⁡{k,∣Bb∖{vi}∣} ∑vj∈Sd(zi,zj)(2)\mathcal{N}_{b,k}(v_i)=\underset{\substack{S\subseteq B_b\setminus\{v_i\}\\ |S|=\min\{k,|B_b\setminus\{v_i\}|\}}}{\arg\min}\ \sum_{v_j\in S} d(z_i,z_j) \tag*{(2)}

where dd is either squared Euclidean distance or cosine distance and ties may be broken arbitrarily. We symmetrize these pairs to obtain ENNE_{\mathrm{NN}}. Each node contributes at most kk unsymmetrized edges, so ENNE_{\mathrm{NN}} contains at most 2nk2nk directed edges before deduplication.

This construction adapts the subsampled-search strategy of Linderman et al. [29]. Each target bin contains approximately n/M≈nk/Kn/M \approx nk/K nodes. Any member of the exact KK-nearest neighbors of a query lands in its assigned target bin with probability approximately 1/M≈k/K1/M \approx k/K; hence approximately kk of those KK neighbors are exposed to the query in expectation. Retrieving kk-nearest targets in that bin therefore efficiently approximates selecting a kk-element random subset from a neighborhood at scale KK, without constructing a global KK-nearest-neighbor graph, or an n×nn \times n distance matrix. The parameter KK controls this scale through the number of bins, whereas kk controls the retained number of near edges.

The inductive bias of ENNE_{\mathrm{NN}} is determined by the representation ziz_i. We consider two fixed precomputed geometries. When node attributes provide a nondegenerate comparison space, we use the feature geometry zi=xiz_i=x_i. If attributes are absent or constant within a graph, feature distances cannot distinguish its nodes. Then we use qq 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 K0=100K_0=100 and

k=min⁡{K,max⁡{2,⌊log⁡(log⁡(max⁡{n,2})+1)⌋}},(3)k=\min\left\{K,\max\left\{2,\left\lfloor\log\left(\log\left(\max\{n,2\}\right)+1\right)\right\rfloor\right\}\right\}, \tag*{(3)}

computed separately for each graph. If n=1n=1, then K=0K=0 and no NN edge is added.

Architectural variants

NearFormer distinguishes the input edges EE from the auxiliary edges ENNE_{\mathrm{NN}}. 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 EHE_H (1). Edge-type embeddings distinguish original and NN connections, while dataset-provided edge features are retained on EE. 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 hh in layer ℓ\ell, the attention coefficient on an allowed pair may also include an NN-specific learned bias:

αuv(h)=exp⁡(suv(h)+βℓ1[(u,v)∈ENN])∑w:(w,v)∈EHexp⁡(swv(h)+βℓ1[(w,v)∈ENN])(4)\alpha_{uv}^{(h)} = \frac{\exp\left(s_{uv}^{(h)}+\beta_{\ell}\mathbf{1}[(u,v)\in E_{\mathrm{NN}}]\right)} {\sum_{w:(w,v)\in E_H}\exp\left(s_{wv}^{(h)}+\beta_{\ell}\mathbf{1}[(w,v)\in E_{\mathrm{NN}}]\right)} \tag*{(4)}

where suv(h)s_{uv}^{(h)} is the edge-conditioned query–key score and βℓ=bmax⁡tanh⁡(θℓ)\beta_{\ell}=b_{\max}\tanh(\theta_{\ell}) is a bounded learned scalar. The bound prevents an unconstrained additive logit from dominating the softmax. Setting θℓ=0\theta_{\ell}=0 reduces to the hard-support variant. NN edges remain in the support and retain their edge-type features. Learning βℓ\beta_{\ell} lets the layer favor or suppress the NN relation without changing the sparsity pattern, so the interaction count remains linear in ∣E∣+n|E|+n for fixed kk.

Local–global NearFormer layers. NearFormer can also be instantiated in the GraphGPS framework (Rampásek et al., [39]). The local branch propagates exclusively on EE, while the global branch restricts attention to E∪ENN∪{(v,v):v∈V}E\cup E_{\mathrm{NN}}\cup\{(v,v):v\in V\}. 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 O(∣E∣+nk)O(|E|+nk) pairwise scores. With hidden states H(ℓ)H^{(\ell)}, a layer has the form

H(ℓ+1)=FFN⁡ℓ(MPNN⁡ℓ(H(ℓ),E)+Attn⁡ℓ(H(ℓ);E,ENN))(5)H^{(\ell+1)}=\operatorname{FFN}_{\ell}\left(\operatorname{MPNN}_{\ell}(H^{(\ell)},E)+\operatorname{Attn}_{\ell}(H^{(\ell)};E,E_{\mathrm{NN}})\right) \tag*{(5)}

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 EE and include ENNE_{\mathrm{NN}} in sparse attention, whereas NearFormer (NN-MP) applies the MPNN to E∪ENNE\cup E_{\mathrm{NN}} and excludes ENNE_{\mathrm{NN}} 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 d(zi,zj)d(z_i,z_j), but need not be local in the input-graph metric dG(vi,vj)d_G(v_i,v_j). Thus, an NN edge can be a long-range shortcut in GG 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 G=(V,E)G=(V,E) is a connected, simple, undirected graph. Let ENNE_{\mathrm{NN}} be the undirected support of the directed relation constructed in § 3.1: the set of distinct pairs {v,u}\{v,u\} for which at least one of (v,u)(v,u) or (u,v)(u,v) is sampled. Let H=(V,E∪ENN)H=(V,E\cup E_{\mathrm{NN}}) and assign unit conductance to every edge of HH. Write dHd_H and RHR_H for shortest-path and effective-resistance distance in HH, respectively. Throughout, the candidate-set size KK and the per-node budget kk are those of § 3.1.

Lemma 4.1 (Monotonicity under NN augmentation). For every x,y∈Vx,y\in V,

dH(x,y)≤dG(x,y),RH(x,y)≤RG(x,y).d_H(x,y)\le d_G(x,y),\qquad R_H(x,y)\le R_G(x,y).

Moreover, if {v,u}∈ENN\{v,u\}\in E_{\mathrm{NN}}, then

dH(x,y)≤dG(x,v)+1+dG(u,y).d_H(x,y)\le d_G(x,v)+1+d_G(u,y).

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 viv_i and order V∖{vi}V\setminus\{v_i\} by increasing distance d(zi,⋅)d(z_i,\cdot), breaking ties by a fixed rule that does not depend on the random permutations. Write vi,(r)v_{i,(r)} for the node of rank r∈{1,…,n−1}r\in\{1,\ldots,n-1\}, and let s1,…,sMs_1,\ldots,s_M 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 vi,(r)v_{i,(r)} is a retained outgoing neighbor of viv_i is

ψn,k(r)=∑b=1Msbn∑j=0k−1(r−1j)(n−rsb−1−j)(nsb).\psi_{n,k}(r)=\sum_{b=1}^{M}\frac{s_b}{n}\sum_{j=0}^{k-1}\frac{\binom{r-1}{j}\binom{n-r}{s_b-1-j}}{\binom{n}{s_b}}.

where (ac)=0\binom{a}{c}=0 whenever c<0c<0 or c>ac>a. Moreover,

∑r=1n−1ψn,k(r)=E[min⁡{k,∣Bb∖{vi}∣}]≤k,\sum_{r=1}^{n-1}\psi_{n,k}(r)=\mathbb{E}\left[\min\{k,\lvert B_b\setminus\{v_i\}\rvert\}\right]\le k,

where BbB_b is the target bin paired with the query bin of viv_i.

The proof is given in Appendix § 9.§ 1. The geometry enters only through the rank rr: a node is retained exactly when it falls in the assigned target bin together with fewer than kk closer nodes. For r≤kr\le k, ψn,k(r)=∑b(sb/n)2\psi_{n,k}(r)=\sum_b(s_b/n)^2, which equals 1/M1/M when all bins have size n/Mn/M. For equal bins and sb≪ns_b\ll n, approximating the hypergeometric count by a binomial with p=1/Mp=1/M:

ψn,k(r)≈p Pr⁡[Bin⁡(r−1,p)≤k−1].\psi_{n,k}(r)\approx p\,\Pr\left[\operatorname{Bin}(r-1,p)\le k-1\right].

The selection probability therefore stays near $1/M\approx k/K$ while the expected number (r−1)/M(r-1)/M of closer nodes in the bin is below kk, and it decays rapidly beyond the rank scale kMkM, where K−k<kM≤KK-k<kM\le K because $M=\lfloor K/k\rfloor. Binning thus acts as a soft rank cutoff at scale KK while retaining about kk neighbors per query: KK sets how far in representation the construction reaches, and kk sets how many edges it keeps.

The same expression describes the small-graph limit. When K=n−1K=n-1, the rank scale kMkM covers essentially the whole graph and each bin contains only about kk or k+1k+1 nodes, so nearly every eligible member of the assigned bin is retained. The profile ψn,k\psi_{n,k} is then close to flat, and the NN relation behaves like a sparse global overlay with only weak geometric bias. Results on graphs with n≲K0n\lesssim K_0 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 KK nearest neighbors. In this surrogate, every rank r≤Kr\le K is drawn with probability 1−(1−1/K)k≈k/K1-(1-1/K)^k\approx k/K and no rank beyond KK 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

CK(vi)=arg⁡min⁡S⊆V∖{vi}∣S∣=K ∑vj∈Sd(zi,zj).(6)C_K(v_i)=\underset{\substack{S\subseteq V\setminus\{v_i\}\\ |S|=K}}{\arg\min}\ \sum_{v_j\in S}d(z_i,z_j). \tag*{(6)}

and write CK(vi)={vi(1),…,vi(K)}C_K(v_i)=\{v_{i(1)},\ldots,v_{i(K)}\}, where vi(j)v_i(j) is the global node index of the jjth candidate. For each node viv_i, Ji,1,…,Ji,kJ_{i,1},\ldots,J_{i,k} be independent uniform draws from {1,…,K}\{1,\ldots,K\}, independently across nodes. The resulting with-replacement edge set is

E~NN=⋃vi∈V⋃r=1k{(vi,vvi(Ji,r)),(vvi(Ji,r),vi)}.(7)\widetilde{E}_{\mathrm{NN}}=\bigcup_{v_i\in V}\bigcup_{r=1}^{k}\left\{(v_i,v_{v_i(J_{i,r})}),(v_{v_i(J_{i,r})},v_i)\right\}. \tag*{(7)}

The identities below apply to E~NN\widetilde{E}_{\mathrm{NN}}, not exactly to the bin-based implementation used in the experiments.

The motivating theorem of Linderman et al. [29] instead retains each of K=cd,1log⁡nK=c_{d,1}\log n exact nearest-neighbor edges independently with probability p=cd,2log⁡log⁡n/log⁡np=c_{d,2}\log\log n/\log n. Under its i.i.d. uniform point model, the resulting graph has a component of size n−o(n)n-o(n) with high probability and expected edge count Θ(nlog⁡log⁡n)\Theta(n\log\log n). 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, ENNE_{\mathrm{NN}} denotes the undirected support of E~NN\widetilde{E}_{\mathrm{NN}} in equation 7, and H=(V,E∪ENN)H=(V,E\cup E_{\mathrm{NN}}). For an unordered pair

mij=1[vj∈CK(vi)]+1[vi∈CK(vj)],m_{ij}=\mathbf{1}[v_j\in C_K(v_i)]+\mathbf{1}[v_i\in C_K(v_j)],

where 1[⋅]\mathbf{1}[\cdot] is the indicator function. Thus mij∈{0,1,2}m_{ij} \in\{0,1,2\} records the number of candidate-set directions for the pair. Let UK={{vi,vj}∈(V2):mij>0}U_K=\{\{v_i,v_j\}\in\binom{V}{2}:m_{ij}>0\}. The pair enters ENNE_{\mathrm{NN}} if and only if at least one of the KmijKm_{ij} eligible draws selects the opposite endpoint, so

πij:=Pr⁡{{vi,vj}∈ENN}=1−(1−1K)Kmij.\pi_{ij}:=\Pr\{\{v_i,v_j\}\in E_{\mathrm{NN}}\}=1-\left(1-\frac{1}{K}\right)^{Km_{ij}}.

The realized edge-local compression is

S(H;G)=∑{vi,vj}∈UK(dG(vi,vj)−1)1[{vi,vj}∈ENN].S(H;G)=\sum_{\{v_i,v_j\}\in U_K}(d_G(v_i,v_j)-1)\mathbf{1}[\{v_i,v_j\}\in E_{\mathrm{NN}}].

Pairs already present in EE contribute zero, since then dG(vi,vj)=1d_G(v_i,v_j)=1.

Lemma 4.3 (Expected edge-local compression). Under the exact with-replacement construction,

E[S(H;G)]=∑{vi,vj}∈UK(dG(vi,vj)−1)πij.\mathbb{E}[S(H;G)]=\sum_{\{v_i,v_j\}\in U_K}(d_G(v_i,v_j)-1)\pi_{ij}.

Moreover,

∑{vi,vj}∈(V2)(dG(vi,vj)−dH(vi,vj))≥S(H;G).\sum_{\{v_i,v_j\}\in\binom{V}{2}}(d_G(v_i,v_j)-d_H(v_i,v_j))\geq S(H;G).

The proof is given in Appendix § 9.§ 1. This result shows the effect of choosing KK independently of kk. A broad candidate set can contain pairs that are close in representation space but far apart in GG, producing large edge-local compression, while kk 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 qiq_i 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-dd 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 σ\sigma determines how strongly distant spins contribute to the target. The hard setting uses σ=0.6\sigma=0.6, while the easy uses σ=1.5\sigma=1.5. 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 (σ=0.6\sigma=0.6) in Table 1, where distant spins contribute most strongly to the target. The corresponding easy results (σ=1.5\sigma=1.5) appear in Appendix § 11.§ 4 and follow the same size trend. GPS variants are strongest on the 16×1616\times16 lattice, where dense attention is cheap and the required range is limited. From width 32 onward, NearFormer (NN) leads and remains practical through n=65,536n=65{,}536. 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.

Model163264128256
GIN−2.533±0.313-2.533 \pm0.313−2.249±0.135-2.249 \pm0.135−3.744±0.253-3.744 \pm0.253−3.672±0.171-3.672 \pm0.171−2.326±0.051-2.326 \pm0.051
GatedGCN−3.844±0.055-3.844 \pm0.055−4.087±0.238-4.087 \pm0.238−3.564±0.111-3.564 \pm0.111−4.064±0.112-4.064 \pm0.112−4.285±0.126-4.285 \pm0.126
GatedGCN-VNG−4.068±0.131-4.068 \pm0.131−3.243±0.177-3.243 \pm0.177−4.324±0.127-4.324 \pm0.127−4.022±0.013-4.022 \pm0.013−4.076±0.006-4.076 \pm0.006
GPS-Base−4.211±0.155-4.211 \pm0.155−4.044±0.122-4.044 \pm0.122OOMOOMOOM
GPS-RWSE−4.011±0.129-4.011 \pm0.129−4.134±0.075-4.134 \pm0.075OOMOOMOOM
GPS-LapPE−4.334±0.065-4.334 \pm0.065−4.032±0.092-4.032 \pm0.092OOMOOMOOM
NearFormer (NN)−4.003±0.005-4.003 \pm0.005−5.241±0.036-5.241 \pm0.036−4.925±0.025-4.925 \pm0.025−5.204±0.106-5.204 \pm0.106−5.803±0.046-5.803 \pm0.046
NearFormer (NN-bias)−4.027±0.013-4.027 \pm0.013−4.432±0.092-4.432 \pm0.092−4.493±0.067-4.493 \pm0.067−5.052±0.162-5.052 \pm0.162−5.021±0.008-5.021 \pm0.008

Table 1. LRIM-hard LogMSE ↓\downarrow (σ=0.6\sigma= 0.6). Easy results are in Appendix D.4.

Candidate scale at a fixed edge budget

Our main design choice is to sample kk edges from a neighborhood of scale KK, rather than to spend that budget on the kk 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 k=2k=2. Ordinary kk-NN is the case K=kK=k. NearFormer uses the same bin construction at K=25K=25 and at the default K=100K=100. Exphormer is a random expander of degree d=kd=k. Because kk 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 mean±\pmstd over three seeds that resample both the overlay and the training run.

OverlayLRIM-32 ↓\downarrowPascalVOC ↑\uparrowCOCO ↑\uparrow
Ordinary kk-NN−4.248±0.071-4.248 \pm0.0710.3861±0.00440.3861 \pm0.00440.3388±0.00180.3388 \pm0.0018
NearFormer, K=25K = 25−4.982±0.047-4.982 \pm0.0470.3965±0.00370.3965 \pm0.00370.3454±0.00140.3454 \pm0.0014
NearFormer, K=100K = 100−5.241±0.036-5.241 \pm0.0360.4012±0.00320.4012 \pm0.00320.3490±0.00120.3490 \pm0.0012
Exphormer−4.173±0.082-4.173 \pm0.0820.3794±0.00480.3794 \pm0.00480.3352±0.00200.3352 \pm0.0020

Table 2. Fixed k=2k = 2, varying KK. LRIM-32-hard LogMSE ↓\downarrow; PascalVOC-SP and COCO-SP F1 ↑\uparrow.

On LRIM-32-hard and both superpixel datasets, performance improves as KK increases, and the default neighborhood outperforms both ordinary kk-NN and Exphormer. A broader geometric candidate set is therefore useful even when no extra edges are added. The full K∈{10,25,50,100}K\in\{10,25,50,100\} grid, LRIM-64-hard, and a global-random overlay are in Appendix D.4. This comparison is informative only when n≫Kn \gg K; on PCQM-Contact, Peptides, and ECHO the default K0=100K_0 = 100 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-kk pattern holds on the superpixel tasks (Table 2): broadening KK 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 dG(u,v)d_G(u,v) denote shortest-path distance. Mean SSSP is the average distance from vv to all other nodes:

MeanSSSP⁡(v)=1n−1∑u∈V∖{v}dG(v,u).\operatorname{MeanSSSP}(v) = \frac{1}{n-1} \sum_{u \in V \setminus\{v\}} d_G(v,u).

Mean ER replaces shortest-path distance with effective resistance:

MeanER⁡(v)=1n−1∑u∈V∖{v}Reff(v,u).\operatorname{MeanER}(v) = \frac{1}{n-1} \sum_{u \in V \setminus\{v\}} R_{\mathrm{eff}}(v,u).

where Reff(v,u)=(ev−eu)TL†(ev−eu)R_{\mathrm{eff}}(v,u) = (e_v - e_u)^\mathsf{T} \mathbf{L}^{\dagger}(e_v - e_u), L†\mathbf{L}^{\dagger} is the Moore–Penrose pseudoinverse of the graph Laplacian and eve_v is the indicator vector for node vv. 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 G=(V,E)G = (V, E) be an undirected graph with n=∣V∣n = |V| nodes, adjacency matrix A∈Rn×n\mathbf{A} \in\mathbb{R}^{n \times n}, and degree matrix D=diag⁡(d1,…,dn)\mathbf{D} = \operatorname{diag}(d_1, \ldots, d_n). Its symmetric normalized Laplacian is

L=I−D−1/2AD−1/2.(8)\mathbf{L} = \mathbf{I} - \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}. \tag*{(8)}

For a connected graph, the eigenvalues satisfy 0=λ0<λ1≤⋯≤λn−1≤20 = \lambda_0 < \lambda_1 \le\cdots\le\lambda_{n-1} \le2. The first nonzero eigenvalue λ1\lambda_1 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 hv(ℓ)\mathbf{h}_v^{(\ell)} at layer ℓ\ell, a message-passing neural network (MPNN) updates each node using information from its graph neighborhood NG(v)\mathcal{N}_G(v):

muv(ℓ)=Message⁡ℓ(hv(ℓ),hu(ℓ),euv),mv(ℓ)=Aggregate⁡ℓ{muv(ℓ):u∈NG(v)},hv(ℓ+1)=Update⁡ℓ(hv(ℓ),mv(ℓ)).(9)\begin{aligned} \mathbf{m}_{uv}^{(\ell)} &= \operatorname{Message}_{\ell}\left(\mathbf{h}_v^{(\ell)}, \mathbf{h}_u^{(\ell)}, e_{uv}\right),\\ \mathbf{m}_v^{(\ell)} &= \operatorname{Aggregate}_{\ell}\left\{\mathbf{m}_{uv}^{(\ell)} : u \in\mathcal{N}_G(v)\right\},\\ \mathbf{h}_v^{(\ell+1)} &= \operatorname{Update}_{\ell}\left(\mathbf{h}_v^{(\ell)}, \mathbf{m}_v^{(\ell)}\right). \tag*{(9)} \end{aligned}

After LL layers, information can travel at most LL 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 H=(V,EH)H = (V, E_H), where (u,v)∈EH(u, v) \in E_H permits node vv to attend to node uu. For one attention head,

suv=(WQhv)⊤(WKhu)d,αuv=exp⁡(suv)∑w∈NH(v)exp⁡(svw),yv=∑u∈NH(v)αuvWVhu.(10)\begin{aligned} s_{uv} &= \frac{(\mathbf{W}_Q\mathbf{h}_v)^\top(\mathbf{W}_K\mathbf{h}_u)}{\sqrt{d}},\\ \alpha_{uv} &= \frac{\exp(s_{uv})}{\sum_{w \in\mathcal{N}_H(v)} \exp(s_{vw})},\\ \mathbf{y}_v &= \sum_{u \in\mathcal{N}_H(v)} \alpha_{uv}\mathbf{W}_V\mathbf{h}_u. \tag*{(10)} \end{aligned}

Edge attributes or structural encodings may additionally enter the attention logits. Dense graph transformers take EH=V×VE_H = V \times V, enabling direct communication between every pair of nodes but requiring O(n2)O(n^2) pairwise scores. Sparse graph transformers instead choose ∣EH∣≪n2|E_H| \ll n^2, ideally O(n)O(n), 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 EE 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 n2n^2 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 O(n)O(n) 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 kk-nearest-neighbor graphs, including examples beyond graph neural networks [28, 51, 32]. Nearest-neighbor graphs capture local geometry but require nKnK directed connections when every node retains all KK 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 Θ(log⁡n)\Theta(\log n) nearest-neighbor edges with an appropriate probability yields a giant component with high probability using only Θ(nlog⁡log⁡n)\Theta(n \log\log n) expected edges. NearFormer draws inspiration from this result and uses an efficient randomized scheme that approximately samples kk neighbors from the KK-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 GG is also present in HH, so dH(x,y)≤dG(x,y)d_H(x,y) \le d_G(x,y). If {v,u}∈ENN\{v,u\} \in E_{\mathrm{NN}}, concatenating a shortest xx-to-vv path in GG, the edge {v,u}\{v,u\}, and a shortest uu-to-yy path in GG yields dH(x,y)≤dG(x,v)+1+dG(u,y)d_H(x,y) \le d_G(x,v) + 1 + d_G(u,y). For effective resistance, Thomson’s principle expresses RH(x,y)R_H(x,y) as the minimum energy of a unit xx-yy flow. Passing from GG to HH enlarges the set of feasible flows, so the minimum energy cannot increase.

Proof of Lemma 4.3. Fix {vi,vj}∈UK\{v_i,v_j\} \in U_K. The pair fails to enter ENNE_{\mathrm{NN}} if and only if none of the kmijkm_{ij} eligible independent draws selects the opposite endpoint. Each such draw has success probability 1/K1/K, which gives πij=1−(1−1/K)kmij\pi_{ij}=1-(1-1/K)^{km_{ij}}. Linearity of expectation then yields the formula for E[S(H;G)]\mathbb{E}[S(H;G)]. If {vi,vj}∈ENN\{v_i,v_j\} \in E_{\mathrm{NN}}, then dH(vi,vj)=1d_H(v_i,v_j)=1, so that pair contributes exactly dG(vi,vj)−1d_G(v_i,v_j)-1 to both S(H;G)S(H;G) and the all-pairs sum. Every remaining pair contributes a nonnegative amount by Lemma 4.1.

Proof of Lemma B.1. Each of the kk draws from viv_i is uniform over CK(vi)C_K(v_i) and therefore crosses the partition with probability qiq_i. Independence of those draws yields Xi∼Binomial⁡(k,qi)X_i \sim\operatorname{Binomial}(k,q_i), the identity E[∑iXi]=k∑iqi\mathbb{E}[\sum_i X_i]=k\sum_i q_i, and Pr⁡(Xi=0)=(1−qi)k\Pr(X_i=0)=(1-q_i)^k. Every distinct undirected cross-region edge in ENNE_{\mathrm{NN}} is produced by at least one raw cross-region draw, so their number is at most ∑iXi\sum_i X_i.

Proof of Proposition 4.2. The query permutation places viv_i in query bin QbQ_b with probability sb/ns_b/n. Because the target permutation is independent of the query permutation, the paired target bin BbB_b is then a uniformly random sbs_b-element subset of VV. Since viv_i is excluded before neighbor selection, vi,(r)v_{i,(r)} is retained if and only if vi,(r)∈Bbv_{i,(r)} \in B_b and at most k−1k-1 of the r−1r-1 closer nodes vi,(1),…,vi,(r−1)v_{i,(1)},\ldots,v_{i,(r-1)} lie in BbB_b. This also covers bins with ∣Bb∖{vi}∣<k|B_b \setminus\{v_i\}|<k, in which every eligible member is retained. The number of sbs_b-subsets that contain vi,(r)v_{i,(r)} and exactly jj closer nodes is (r−1j)(n−rsb−1−j)\binom{r-1}{j}\binom{n-r}{s_b-1-j}; the remaining sb−1−js_b-1-j members are chosen among the n−rn-r nodes that are neither vi,(r)v_{i,(r)} nor closer to viv_i, a set that includes viv_i itself. Dividing by (nsb)\binom{n}{s_b}, summing over j=0,…,k−1j=0,\ldots,k-1, and averaging over the query bin of viv_i gives ψn,k(r)\psi_{n,k}(r). For the second claim, summing the indicator of retention over rr counts the retained neighbors of viv_i, which number min⁡{k,∣Bb∖{vi}∣}\min\{k,\lvert B_b\setminus\{v_i\}\rvert\}. For r≤kr\leq k, every subset containing vi,(r)v_{i,(r)} has at most k−1k-1 closer members, so the inner sum equals (n−1sb−1)/(nsb)=sb/n\binom{n-1}{s_b-1}/\binom{n}{s_b}=s_b/n.

Candidate purity and cross-region exposure

To quantify when surrogate shortcuts preserve task-relevant variation, let P={V1,…,Vm}\mathcal{P}=\{V_1,\ldots,V_m\}, with m≥2m\geq2, be a partition of VV into regions that should remain distinguishable, and let P(vi)\mathcal{P}(v_i) denote the region containing viv_i. Define the candidate impurity

qi=∣{vj∈CK(vi):P(vj)≠P(vi)}∣K.q_i=\frac{\left|\{v_j\in C_K(v_i):\mathcal{P}(v_j)\ne\mathcal{P}(v_i)\}\right|}{K}.

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 XiX_i be the number of the kk outgoing draws from viv_i whose endpoints lie outside P(vi)\mathcal{P}(v_i). Then

Xi∼Binomial⁡(k,qi),X_i\sim\operatorname{Binomial}(k,q_i),
E[∑vi∈VXi]=k∑vi∈Vqi,\mathbb{E}\left[\sum_{v_i\in V}X_i\right]=k\sum_{v_i\in V}q_i,

and Pr⁡(Xi=0)=(1−qi)k\Pr(X_i=0)=(1-q_i)^k. After symmetrization and deduplication, the number of distinct undirected cross-region edges in ENNE_{\mathrm{NN}} is at most ∑vi∈VXi\sum_{v_i\in V}X_i.

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 HH). If xi=aP(vi)x_i=a_{\mathcal{P}(v_i)}, then, before deduplication and symmetrization,

E[∑vi∈V∑r=1k∥xi−xvi(Ji,r)∥22]=kK∑vi∈V∑vj∈CK(vi)∥aP(vi)−aP(vj)∥22,\begin{aligned} \mathbb{E}\left[\sum_{v_i\in V}\sum_{r=1}^{k}\left\|x_i-x_{v_i(J_i,r)}\right\|_2^2\right] \\ &=\frac{k}{K}\sum_{v_i\in V}\sum_{v_j\in C_K(v_i)}\left\|a_{\mathcal{P}(v_i)}-a_{\mathcal{P}(v_j)}\right\|_2^2, \end{aligned}

which is at most kΔmax⁡2∑vi∈Vqik\Delta_{\max}^2\sum_{v_i\in V}q_i, where Δmax⁡=max⁡i≠j∥ai−aj∥2\Delta_{\max}=\max_{i\ne j}\|a_i-a_j\|_2. Candidate impurity therefore controls both the expected number of cross-region draws and the stated upper bound on their energy linearly. Candidate sets with qi=0q_i=0 for every viv_i 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

PH=D~H−1/2A~HD~H−1/2,A~H=AH+I,P_H=\widetilde{D}_H^{-1/2}\widetilde{A}_H\widetilde{D}_H^{-1/2},\qquad\widetilde{A}_H=A_H+I,

where AHA_H is the adjacency matrix of the distinct undirected edges of HH and D~H\widetilde{D}_H is the degree matrix of A~H\widetilde{A}_H, so that d~H(v)=deg⁡H(v)+1\widetilde{d}_H(v)=\deg_H(v)+1. Since HH is connected, the eigenvalue one of PHP_H is simple. Let μ2(PH)\mu_2(P_H) denote its second-largest eigenvalue. For a nonempty proper subset S⊂VS\subset V, write S‾=V∖S\overline{S}=V\setminus S, and define

δH(S)={{u,v}∈E(H):u∈S, v∈S‾},\delta_H(S)=\{\{u,v\}\in E(H):u\in S,\ v\in\overline{S}\},
cut⁡H(S)=∣δH(S)∣,\operatorname{cut}_H(S)=|\delta_H(S)|,
vol⁡H(S)=∑v∈Sd~H(v),\operatorname{vol}_H(S)=\sum_{v\in S}\widetilde{d}_H(v),
ΦH(S)=cut⁡H(S)min⁡{vol⁡H(S),vol⁡H(S‾)}.\Phi_H(S)=\frac{\operatorname{cut}_H(S)}{\min\{\operatorname{vol}_H(S),\operatorname{vol}_H(\overline{S})\}}.

where E(H)=E∪ENNE(H)=E\cup E_{\mathrm{NN}}. The analogous quantities for GG use d~G(v)=deg⁡G(v)+1\tilde{d}_G(v)=\deg_G(v)+1. We call ENNE_{\mathrm{NN}} pure with respect to P\mathcal{P} if every NN edge joins two nodes in the same region.

Theorem B.2 (Region cuts under NN augmentation). Let SS be a nonempty proper union of regions of P\mathcal{P}, and write

XS=∣{{u,v}∈ENN∖E:u∈S, v∈S‾}∣X_S=\left|\left\{\{u,v\}\in E_{\mathrm{NN}}\setminus E:u\in S,\ v\in\overline{S}\right\}\right|

for the number of genuinely new, distinct undirected NN edges that cross SS. Let X=∑vi∈VXiX=\sum_{v_i\in V}X_i be the raw cross-region draw count from Lemma B.1, so that XS≤XX_S\le X. Then, for every realization of ENNE_{\mathrm{NN}}:

(i) cut⁡H(S)=cut⁡G(S)+XS\operatorname{cut}_H(S)=\operatorname{cut}_G(S)+X_S, and

ΦH(S)≤cut⁡G(S)+XSmin⁡{vol⁡G(S),vol⁡G(S‾)}.\Phi_H(S)\le\frac{\operatorname{cut}_G(S)+X_S}{\min\{\operatorname{vol}_G(S),\operatorname{vol}_G(\overline{S})\}}.

If ENNE_{\mathrm{NN}} is pure, then XS=0X_S=0, cut⁡H(S)=cut⁡G(S)\operatorname{cut}_H(S)=\operatorname{cut}_G(S) and ΦH(S)≤ΦG(S)\Phi_H(S)\le\Phi_G(S).

(ii) μ2(PH)≥1−2ΦH(S)\mu_2(P_H)\ge1-2\Phi_H(S). Hence, for an eigenvector g2≠0\mathbf{g}_2\ne0 associated with μ2\mu_2 and every integer ℓ≥1\ell\ge1,

∥PHℓg2∥2∥g2∥2=∣μ2(PH)∣ℓ≥(1−2ΦH(S))ℓ.\frac{\lVert P_H^\ell\mathbf{g}_2\rVert_2}{\lVert\mathbf{g}_2\rVert_2}=|\mu_2(P_H)|^\ell\ge(1-2\Phi_H(S))^\ell.

(iii) For every x∈Sx\in S and y∈S‾y\in\overline{S},

RH(x,y)≥1cut⁡H(S)≥1cut⁡G(S)+XS,R_H(x,y)\ge\frac{1}{\operatorname{cut}_H(S)}\ge\frac{1}{\operatorname{cut}_G(S)+X_S},

and HH contains at most cut⁡G(S)+XS\operatorname{cut}_G(S)+X_S edge-disjoint paths from xx to yy.

In expectation over the exact sampling rule, E[XS]≤E[X]=k∑iqi\mathbb{E}[X_S]\le\mathbb{E}[X]=k\sum_iq_i, and therefore

E[μ2(PH)]≥1−2(cut⁡G(S)+k∑iqi)min⁡{vol⁡G(S),vol⁡G(S‾)},\mathbb{E}[\mu_2(P_H)]\ge1-\frac{2(\operatorname{cut}_G(S)+k\sum_iq_i)}{\min\{\operatorname{vol}_G(S),\operatorname{vol}_G(\overline{S})\}},
E[RH(x,y)]≥1cut⁡G(S)+k∑iqi.\mathbb{E}[R_H(x,y)]\ge\frac{1}{\operatorname{cut}_G(S)+k\sum_iq_i}.

Proof. (i) Because SS is a union of regions, every edge crossing SS joins two different regions. The crossing edges of HH are the disjoint union of the crossing edges already in EE and the XSX_S crossing edges in ENN∖EE_{\mathrm{NN}}\setminus E. Hence cut⁡H(S)=cut⁡G(S)+XS\operatorname{cut}_H(S)=\operatorname{cut}_G(S)+X_S. Lemma B.1 gives XS≤XX_S\le X, and XS=0X_S=0 in the pure case. Adding edges can only increase degrees, so vol⁡H(S)≥vol⁡G(S)\operatorname{vol}_H(S)\ge\operatorname{vol}_G(S) and vol⁡H(S‾)≥vol⁡G(S‾)\operatorname{vol}_H(\overline{S})\ge\operatorname{vol}_G(\overline{S}), which yields both conductance bounds.

(ii) Let L~H=I−PH\widetilde{L}_H=I-P_H. Its smallest eigenvalue is zero, with eigenvector D~H1/21\widetilde{D}_H^{1/2}\mathbf{1}, so its second-smallest eigenvalue is 1−μ2(PH)1-\mu_2(P_H). For any f\mathbf{f} satisfying ∑vd~H(v)fv=0\sum_v\tilde{d}_H(v)f_v=0, set g=D~H1/2f\mathbf{g}=\widetilde{D}_H^{1/2}\mathbf{f}. Since self-loops do not contribute to the quadratic form,

gTL~HggTg=∑{u,v}∈E(H)(fu−fv)2∑vd~H(v)fv2.\frac{\mathbf{g}^{\mathsf{T}}\widetilde{L}_H\mathbf{g}}{\mathbf{g}^{\mathsf{T}}\mathbf{g}}= \frac{\sum_{\{u,v\}\in E(H)}(f_u-f_v)^2}{\sum_v\tilde{d}_H(v)f_v^2}.

and the Courant–Fischer theorem bounds 1−μ2(PH)1-\mu_2(P_H) by this ratio. Choose fv=vol⁡H(S)−1f_v=\operatorname{vol}_H(S)^{-1} for v∈Sv\in S and fv=−vol⁡H(S‾)−1f_v=-\operatorname{vol}_H(\overline{S})^{-1} otherwise. Writing a=vol⁡H(S)a=\operatorname{vol}_H(S) and b=vol⁡H(S‾)b=\operatorname{vol}_H(\overline{S}), the ratio equals

cut⁡H(S)a+bab≤2cut⁡H(S)min⁡{a,b}=2ΦH(S),\operatorname{cut}_H(S)\frac{a+b}{ab}\le\frac{2\operatorname{cut}_H(S)}{\min\{a,b\}}=2\Phi_H(S),

because (a+b)/max⁡{a,b}≤2(a+b)/\max\{a,b\}\le2. An eigenvector of μ2(PH)\mu_2(P_H) is orthogonal to the eigenvalue-one eigenspace. Applying PHℓP_H^\ell multiplies its Euclidean norm by ∣μ2(PH)∣ℓ|\mu_2(P_H)|^\ell.

(iii) Orient the edges crossing SS from SS to S‾\overline{S}. For any unit xx–yy flow f\mathbf{f}, flow conservation gives ∑e∈δH(S)fe=1\sum_{e\in\delta_H(S)}f_e=1. By Cauchy–Schwarz,

∑e∈δH(S)fe2≥1cut⁡H(S).\sum_{e\in\delta_H(S)}f_e^2\ge\frac{1}{\operatorname{cut}_H(S)}.

The total flow energy is at least this cut contribution, and Thomson’s principle gives the resistance bound. Every xx-to-yy path uses at least one crossing edge, so there are at most cut⁡H(S)\operatorname{cut}_{H}(S) edge-disjoint paths. For the expectations, combining (i) and (ii) gives the affine lower bound

μ2(PH)≥1−2(cut⁡G(S)+XS)min⁡{vol⁡G(S),vol⁡G(S‾)}.\mu_{2}(\mathbf{P}_{H}) \ge1-\frac{2(\operatorname{cut}_{G}(S)+X_{S})}{\min\{\operatorname{vol}_{G}(S),\operatorname{vol}_{G}(\overline{S})\}}.

The map t↦1/(c+t)t\mapsto1/(c+t) is convex on t≥0t\ge0. Linearity of expectation, Jensen’s inequality, XS≤XX_{S}\le X, and E[X]=k∑iqi\mathbb{E}[X]=k\sum_i q_i complete the proof.

Theorem B.2 bounds spectral mixing proxies and communication capacity using an aligned cut. Since XSX_{S} is the exact increase in cut cardinality, cut⁡H(S)=cut⁡G(S)+XS\operatorname{cut}_{H}(S)=\operatorname{cut}_{G}(S)+X_{S}. This equality yields an upper bound on the algebraic spectral gap 1−μ2(PH)1-\mu_{2}(\mathbf{P}_{H}) and a reciprocal lower bound on effective resistance. If the realized NN edges are pure, they leave the cut cardinality unchanged and satisfy 1−μ2(PH)≤2ΦG(S)1-\mu_{2}(\mathbf{P}_{H})\le2\Phi_{G}(S). This is a ceiling derived from the chosen cut, not a monotonic comparison with the spectral gap of GG: adding within-region edges may still accelerate some modes of diffusion. Likewise, pure NN edges add no edge directly across SS, but they may shorten paths, lower effective resistance, or increase the number of edge-disjoint xx-to-yy 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 qiq_i 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

ΓK=1nK∑vi∈V∑vj∈CK(vi)(dG(vi,vj)−1),\Gamma_{K}=\frac{1}{nK}\sum_{v_i\in V}\sum_{v_j\in C_{K}(v_i)}\left(d_{G}(v_i,v_j)-1\right),
QK=1n∑vi∈Vqi.Q_{K}=\frac{1}{n}\sum_{v_i\in V}q_i.

ΓK\Gamma_{K} measures the available shortcut gain, whereas QKQ_{K} measures candidate impurity. Before deduplication, the expected draw-weighted shortcut score per node is kΓKk\Gamma_{K}, while the expected number of cross-region draws per node is kQKkQ_{K}. 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 ΓK\Gamma_{K} and small QKQ_{K} 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 QKQ_{K} 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 KK candidates would maximize both shortcut availability and direct cross-region exposure, whereas sampling only k≪Kk\ll K 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 Θ(nlog⁡log⁡n)\Theta(n\log\log n) expected edges without retaining the entire KK-nearest-neighbor graph. Their theorem is asymptotic, uses unspecified constants in K=cd,1log⁡nK=c_{d,1}\log n and p=cd,2log⁡log⁡n/log⁡np=c_{d,2}\log\log n/\log n, and assumes i.i.d. uniform points. NearFormer instead uses a fixed KK, a small constant kk, 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-kk 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 PHP_H of Section B.3, contraction toward the eigenspace of eigenvalue one is governed by the largest magnitude ρH\rho_H of the remaining eigenvalues. If ΠH\Pi_H denotes the orthogonal projector onto that eigenspace, then

∥PHℓX−ΠHX∥F≤ρHℓ∥X−ΠHX∥F.\left\|P_H^\ell X-\Pi_HX\right\|_F\leq\rho_H^\ell\left\|X-\Pi_HX\right\|_F.

Adding NN edges can change ρH\rho_H 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 HH monotonically with that of GG. 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 n≤Kn \leq K, KK is replaced by min⁡{K,n−1}\min\{K,n-1\}. They therefore also apply when CK(vi)C_K(v_i) is returned by an approximate index such as HNSW, provided CK(vi)C_K(v_i) 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 56.99±28.7256.99 \pm28.72 and mean shortest-path length 20.89±9.7920.89 \pm9.79. PCQM-Contact graphs are smaller, with mean diameter 9.86±1.799.86 \pm1.79 and mean shortest-path length 4.63±0.634.63 \pm0.63.

DatasetGraphsAvg. nodesAvg. edgesLevelMetric
PascalVOC-SP11,355479.42,710.5nodeF1
COCO-SP123,286476.92,693.7nodeF1
Peptides-Func15,535150.9307.3graphAP
Peptides-Struct15,535150.9307.3graphMAE
PCQM-Contact529,43430.161.0linkMRR

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 {−1,+1}\{-1,+1\}, and its target is the energy change ΔEi\Delta E_i caused by flipping that spin. Every dataset contains 10,000 configurations and uses an 80/10/10 training, validation, and test split. The exponent σ\sigma changes the interaction range while preserving the lattice: σ=0.6\sigma=0.6 is the hard setting and σ=1.5\sigma=1.5 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 log⁡10(MSE)\log_{10}(\mathrm{MSE}).

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

DatasetGraphsNodesEdgesAvg. shortest pathDiameter
LRIM-1610,0002565128.0316
LRIM-3210,0001,0242,04816.0232
LRIM-6410,0004,0968,19232.0164
LRIM-12810,00016,38432,76864.00128
LRIM-25610,00065,536131,072128.00256

caption: Table 6: LRIM lattice statistics [31]. Each size has an easy variant with σ=1.5\sigma= 1.5 and a hard variant with σ=0.6\sigma= 0.6.

:::

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.

DatasetGraphsAvg. nodesAvg. edgesAvg. diameter
ECHO-Synth10,08083.69 ± 66.24211.63 ± 209.3928.50 ± 6.92
ECHO-Charge170,36772.49 ± 12.48151.32 ± 25.1623.54 ± 2.54
ECHO-Energy196,52873.73 ± 13.22153.84 ± 26.5823.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 n=∣V∣n = |V|, m=∣E∣m = |E|, dd be the hidden dimension, LL be the number of layers, and kk be the retained NN budget per node. After symmetrization, the NN construction adds at most 2nk2nk directed edge instances. The sparse NearFormer variants therefore evaluate

O(L(m+nk)d)O(L(m + nk)d)

pairwise attention operations and store O(m+nk)O(m + nk) attention scores. For fixed kk, these costs are linear in m+nm + n, compared with O(Ln2d)O(Ln^{2}d) pairwise work and O(n2)O(n^{2}) attention-score memory for dense attention. The node-wise projections and feed-forward networks add O(Lnd2)O(Lnd^{2}) 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 ENNE_{\mathrm{NN}} has been constructed. NearFormer does not construct a global KK-nearest-neighbor graph. With M=⌊K/k⌋M = \lfloor K/k \rfloor paired bins, direct within-bin search compares approximately ∑b∣Qb∣∣Bb∣≃n2/M=O(n2k/K)\sum_b |Q_b||B_b| \simeq n^{2}/M = O(n^{2}k/K) query–target pairs, each in representation dimension dzd_z, while processing one bin pair at a time. It therefore avoids both a global all-pairs distance matrix and an n×Kn \times K 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 nn. Exphormer and NearFormer both keep the attention support sparse: Exphormer adds a fixed-degree expander overlay, while NearFormer adds kk sampled near-neighbor edges per node. For the periodic LRIM grids used here, m=Θ(n)m = \Theta(n) and the default budget satisfies k=O(1)k = O(1), so NearFormer evaluates O(n)O(n) global attention pairs per layer rather than O(n2)O(n^{2}). This gap is largest on LRIM-256, where n=65,536n = 65{,}536, 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 d=k=2d = k = 2, 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 nn 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 ∣EH∣|E_H| (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 10−510^{-5} 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 ±\pm standard deviation over three independent runs with different random seeds.

For NearFormer (NN-bias), the bound in (4) is bmax⁡=5b_{\max} = 5. 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 k=2k = 2 and K=100K = 100; Exphormer uses expander degree d=2d = 2; dense GPS is GPS-Base. Attention edges are directed pairs in EHE_H. 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.

MethodQuantity16<br>n=256n=25632<br>n=1,024n=1{,}02464<br>n=4,096n=4{,}096128<br>n=16,384n=16{,}384256<br>n=65,536n=65{,}536
NearFormer (NN)Attn. edges2.3×1032.3 \times10^39.2×1039.2 \times10^33.7×1043.7 \times10^41.5×1051.5 \times10^55.9×1055.9 \times10^5
NearFormer (NN)Peak mem (GB)0.420.611.182.949.72
NearFormer (NN)Step time (ms)2.44.111.844.6179
NearFormer (NN)NN preproc. (ms)0.95.4384103.6×1033.6 \times10^3
ExphormerAttn. edges1.8×1031.8 \times10^37.2×1037.2 \times10^32.9×1042.9 \times10^41.1×1051.1 \times10^54.6×1054.6 \times10^5
ExphormerPeak mem (GB)0.400.581.092.718.86
ExphormerStep time (ms)2.23.810.941.2164
ExphormerOverlay preproc. (ms)0.20.51.44.819
Dense GPSAttn. edges6.6×1046.6 \times10^41.0×1061.0 \times10^61.7×1071.7 \times10^72.7×1082.7 \times10^84.3×1094.3 \times10^9
Dense GPSPeak mem (GB)0.812.46OOMOOMOOM
Dense GPSStep time (ms)7.846OOMOOMOOM
Dense GPSPreproc. (ms)–––––

Table 8.

Table 9: NearFormer Hyperparameter training settings.

HyperparameterPascalVOC-SPCOCO-SPPeptides-FuncPeptides-StructPCQM-ContactECHO
Num Layers47847Table 10
Hidden Dim9672648864Table 10
Num Heads844442
Dropout0.1500.120.1200
PELapPELapPELapPELapPELapPELapPE
Batch Size3232128128128128
Learning Rate0.00050.00050.00030.00030.0003Table 10
Num Epochs3003002002002001,000

Table 9.

Chem use the feature geometry z~i=xi\tilde{z}_i = x_i. 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 (M=32M = 32); Peptides, PCQM-Contact, and LRIM use exact flat search; ECHO uses exact, deterministic kk-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 7×10−57 \times10^{-5}, GCN backbone, two attention heads).

HyperparameterSearch intervaldiamssspeccECHO-ChargeECHO-Energy
Number of layers[1−40][1 - 40]1726173626
Hidden dimension[16−256][16 - 256]4056162216192
Learning rate[10−5−10−2][10^{-5} - 10^{-2}]0.000040.000310.000340.000050.000024067
Weight decay[10−8−10−3][10^{-8} - 10^{-3}]0.000150.000290.000070.000050.00038179
GNN Backbone[GCN]GCNGCNGCNGCNGCN
Number of Backbone Layers[1]11111
Number of attention heads[2]22222

Table 10. ECHO hyperparameters used by NearFormer.

Additional experiments

LRIM-easy. Table 11 reports the easy LRIM setting (σ=1.5\sigma= 1.5), 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.

Model163264128256
GIN−3.564±0.111-3.564\pm0.111−3.446±0.307-3.446\pm0.307−3.423±0.317-3.423\pm0.317−3.342±0.287-3.342\pm0.287−3.258±0.214-3.258\pm0.214
GatedGCN−4.817±0.111-4.817\pm0.111−4.940±0.298-4.940\pm0.298−3.270±0.094-3.270\pm0.094−3.282±0.007-3.282\pm0.007−3.46±0.046-3.46\pm0.046
GatedGCN-VNG−4.612±0.101-4.612\pm0.101−4.322±0.229-4.322\pm0.229−4.256±0.230-4.256\pm0.230−4.762±0.103-4.762\pm0.103−4.120±0.028-4.120\pm0.028
GPS-Base−5.296±0.026-5.296\pm0.026−5.134±0.054-5.134\pm0.054OOMOOMOOM
GPS-RWSE−5.133±0.235-5.133\pm0.235−5.103±0.074-5.103\pm0.074OOMOOMOOM
GPS-LapPE−5.154±0.177-5.154\pm0.177−4.858±0.231-4.858\pm0.231OOMOOMOOM
NearFormer (NN)−4.256±0.022-4.256\pm0.022−5.203±0.091-5.203\pm0.091−5.076±0.064-5.076\pm0.064−4.864±0.077-4.864\pm0.077−5.134±0.032-5.134\pm0.032
NearFormer (NN-bias)−4.671±0.044-4.671\pm0.044−4.724±0.125-4.724\pm0.125−4.645±0.022-4.645\pm0.022−5.065±0.026-5.065\pm0.026−5.045±0.102-5.045\pm0.102

Table 11. LRIM-easy test LogMSE = log⁡10(MSE)\log_{10}(\mathrm{MSE}) (lower is better; σ=1.5\sigma= 1.5). 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 G=(V,E)G = (V, E) be a connected, unweighted graph with n=∣V∣n = |V|, adjacency matrix AA, degree matrix DD, and combinatorial Laplacian L=D−AL = D - A. The heat equation on GG is ∂tf=−Lf\partial_t f = -Lf, with solution f(t)=e−tLf(0)f(t) = e^{-tL}f(0). Starting from a unit impulse at node vv, the heat at node uu at a fixed diffusion time t>0t > 0 is (e−tL)vu(e^{-tL})_{vu}. The heat-diffusion target averages this kernel over all other nodes,

HeatDiff⁡t(v)=1n−1∑u∈V∖{v}(e−tL)vu.\operatorname{HeatDiff}_t(v) = \frac{1}{n-1} \sum_{u \in V \setminus\{v\}} \left(e^{-tL}\right)_{vu}.

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.

MethoddiameccssspMean SSSPMean EREnergyCharge
A-DGN1.151±\pm0.0384.981±\pm0.0371.176±\pm0.1404.251±\pm0.0813.486±\pm0.02712.486±\pm1.6216.543±\pm0.146
DRew1.243±\pm0.0474.651±\pm0.0201.279±\pm0.0113.425±\pm0.1073.120±\pm0.08511.325±\pm2.3949.086±\pm0.473
GraphCON2.969±\pm0.1895.474±\pm0.0015.734±\pm0.0115.723±\pm0.0455.167±\pm0.12514.295±\pm0.80719.629±\pm0.195
GCN3.832±\pm0.2625.233±\pm0.0342.102±\pm0.0945.754±\pm0.0215.062±\pm0.10728.112±\pm1.2398.421±\pm0.512
GCNII2.005±\pm0.0935.241±\pm0.0302.128±\pm0.4295.135±\pm0.0295.146±\pm0.02713.235±\pm2.6308.829±\pm0.021
GIN1.630±\pm0.1614.869±\pm0.0922.234±\pm0.2714.307±\pm0.0843.988±\pm0.06147.851±\pm10.15410.784±\pm0.059
GPS2.160±\pm0.0984.758±\pm0.0210.472±\pm0.0504.604±\pm0.0522.510±\pm0.0195.257±\pm0.8426.182±\pm0.219
GRIT1.014±\pm0.0465.091±\pm0.1580.121±\pm0.0135.242±\pm0.0132.840±\pm0.09225.508±\pm2.5077.134±\pm6.090
PH-DGN1.627±\pm0.3985.068±\pm0.1261.323±\pm0.4855.269±\pm0.1254.786±\pm0.42516.080±\pm1.1237.915±\pm0.269
SWAN1.121±\pm0.0704.840±\pm0.0450.896±\pm0.2324.284±\pm0.0324.726±\pm0.01412.629±\pm1.1576.109±\pm0.103
NearFormer (NN)1.752±\pm0.0642.396±\pm0.0310.559±\pm0.0242.752±\pm0.0642.105±\pm0.0244.827±\pm0.1066.004±\pm0.245
NearFormer (NN-bias)1.92±\pm0.1283.260±\pm0.0471.101±\pm0.4013.651±\pm0.0222.486±\pm0.2077.354±\pm0.6125.860±\pm0.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.

MethodHeat Diffusion
A-DGN4.206±0.0144.206 \pm0.014
DRew4.056±0.1054.056 \pm0.105
GraphCON5.244±0.0515.244 \pm0.051
GCN5.234±0.0125.234 \pm0.012
GCNII4.326±0.1534.326 \pm0.153
GIN4.228±0.7314.228 \pm0.731
GPS4.677±0.1524.677 \pm0.152
GRIT3.226±0.1053.226 \pm0.105
PH-DGN5.286±0.1605.286 \pm0.160
SWAN4.362±0.1914.362 \pm0.191
NearFormer (NN)2.126±0.0412.126 \pm0.041
NearFormer (NN-bias)3.126±0.0073.126 \pm0.007

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 K0=100K_0 = 100 and the default retained degree is given in (3). A full KK-sweep is informative only when n≫Kn \gg K, so that K∈{k,10,25,50,100}K \in\{k, 10, 25, 50, 100\} are distinct neighborhoods rather than the almost-complete graph. Table 13 therefore sweeps KK on LRIM-32-hard (n=1,024n = 1{,}024) and LRIM-64-hard (n=4,096n = 4{,}096), where NearFormer (NN) has a clear advantage in Table 1. We hold the architecture, training protocol, and retained degree fixed at the default k=2k = 2, and vary only the candidate set. The row K=k=2K = k = 2 recovers ordinary kk-NN. The rows K∈{10,25,50,100}K \in\{10, 25, 50, 100\} use the same randomized construction with broader neighborhoods. Global-random samples kk neighbors uniformly from V∖{vi}V \setminus\{v_i\}, 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 zi=xiz_i = x_i, Euclidean distance, and the LRIM training setting of § 5.1.

Table 13: Candidate-scale (KK) sensitivity on LRIM-32-hard and LRIM-64-hard. The architecture is NearFormer (NN) and the retained degree is fixed at k=2k = 2. K=kK = k is ordinary kk-NN; K∈{10,25,50,100}K \in\{10, 25, 50, 100\} are randomized neighborhoods at increasing scale; global-random and Exphormer are matched-degree overlays without representation geometry. Test LogMSE = log⁡10(MSE)\log_{10}(\mathrm{MSE}) (lower is better), mean±\pmstd over three seeds.

OverlayKKkkLRIM-32-hard ↓\downarrowLRIM-64-hard ↓\downarrow
Ordinary kk-NN22−4.248±0.071-4.248 \pm0.071−3.962±0.088-3.962 \pm0.088
NearFormer (NN)102−4.671±0.058-4.671 \pm0.058−4.381±0.072-4.381 \pm0.072
NearFormer (NN)252−4.982±0.047-4.982 \pm0.047−4.672±0.055-4.672 \pm0.055
NearFormer (NN)502−5.186±0.039-5.186 \pm0.039−4.864±0.041-4.864 \pm0.041
NearFormer (NN)1002−5.241±0.036-5.241 \pm0.036−4.925±0.025-4.925 \pm0.025
Global-randomn−1n - 12−4.062±0.094-4.062 \pm0.094−3.718±0.102-3.718 \pm0.102
Exphormer–2−4.173±0.082-4.173 \pm0.082−3.841±0.091-3.841 \pm0.091

Table 13. Candidate-scale (KK) sensitivity on LRIM-32-hard and LRIM-64-hard. The architecture is NearFormer (NN) and the retained degree is fixed at k=2k = 2. K=kK = k is ordinary kk-NN; K∈{10,25,50,100}K \in\{10, 25, 50, 100\} are randomized neighborhoods at increasing scale; global-random and Exphormer are matched-degree overlays without representation geometry. Test LogMSE = log⁡10(MSE)\log_{10}(\mathrm{MSE}) (lower is better), mean±\pmstd over three seeds.

Table 14 repeats the same matched-kk overlays on LRIM-32-hard, PascalVOC-SP, and COCO-SP, including the K∈{10,25,50}K \in\{10, 25, 50\} grid omitted from the compact Table 2. Both superpixel datasets have n≈480n \approx480, so K=100K = 100 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 n≲150n \lesssim150, so K0=100K_0 = 100 saturates at n−1n - 1 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.

ModelPascalVOC-SP F1 score ↑\uparrowCOCO-SP F1 score ↑\uparrowPeptides-Func AP ↑\uparrowPeptides-Struct MAE ↓\downarrowPCQM-Contact MRR ↑\uparrow
GCN0.1268±\pm0.00600.0841±\pm0.00100.5930±\pm0.00230.3496±\pm0.00130.3234±\pm0.0006
GINE0.1265±\pm0.00760.1339±\pm0.00440.5498±\pm0.00790.3547±\pm0.00450.3180±\pm0.0027
GatedGCN0.2873±\pm0.02190.2641±\pm0.00450.5864±\pm0.00770.3420±\pm0.00130.3218±\pm0.0011
GatedGCN+RWSE0.2860±\pm0.00850.2574±\pm0.00340.6069±\pm0.00350.3357±\pm0.00060.3242±\pm0.0008
Transformer+LapPE0.2694±\pm0.00980.2618±\pm0.00310.6326±\pm0.01260.2529±\pm0.00160.3174±\pm0.0020
SAN+LapPE0.3230±\pm0.00390.2592±\pm0.01580.6384±\pm0.01210.2683±\pm0.00430.3350±\pm0.0003
SAN+RWSE0.3216±\pm0.00270.2434±\pm0.01560.6439±\pm0.00750.2545±\pm0.00120.3341±\pm0.0006
GraphGPS0.3748±\pm0.01090.3412±\pm0.00440.6535±\pm0.00410.2500±\pm0.00050.3337±\pm0.0006
Exphormer0.3975±\pm0.00370.3455±\pm0.00090.6527±\pm0.00430.2481±\pm0.00070.3637±\pm0.0020
NearFormer (NN)0.4012±\pm0.00320.3490±\pm0.00120.5368±\pm0.00560.2636±\pm0.00280.3682±\pm0.0024
NearFormer (NN-MP)0.3980±\pm0.00390.3462±\pm0.00110.6025±\pm0.00420.2527±\pm0.00190.3645±\pm0.0022
NearFormer (NN-bias)0.4058±\pm0.00280.3524±\pm0.00100.5582±\pm0.00510.2622±\pm0.00250.3720±\pm0.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-kk candidate-scale ablation on LRIM-32-hard, PascalVOC-SP, and COCO-SP. The architecture is NearFormer (NN) and the retained degree is fixed at k=2k = 2. K=kK = k is ordinary kk-NN; K∈{10,25,50,100}K \in\{10, 25, 50, 100\} are randomized neighborhoods at increasing scale; Exphormer is the expander overlay of degree d=kd = k. LRIM-32-hard is test LogMSE (lower is better); PascalVOC-SP and COCO-SP are test F1 (higher is better). Mean±\pmstd over three seeds.

OverlayKKLRIM-32-hard ↓\downarrowPascalVOC-SP ↑\uparrowCOCO-SP ↑\uparrow
Ordinary kk-NN2−4.248±0.071-4.248 \pm0.0710.3861±0.00440.3861 \pm0.00440.3388±0.00180.3388 \pm0.0018
NearFormer (NN)10−4.671±0.058-4.671 \pm0.0580.3918±0.00410.3918 \pm0.00410.3426±0.00160.3426 \pm0.0016
NearFormer (NN)25−4.982±0.047-4.982 \pm0.0470.3965±0.00370.3965 \pm0.00370.3454±0.00140.3454 \pm0.0014
NearFormer (NN)50−5.186±0.039-5.186 \pm0.0390.3996±0.00340.3996 \pm0.00340.3476±0.00130.3476 \pm0.0013
NearFormer (NN)100−5.241±0.036-5.241 \pm0.0360.4012±0.00320.4012 \pm0.00320.3490±0.00120.3490 \pm0.0012
Exphormer–−4.173±0.082-4.173 \pm0.0820.3794±0.00480.3794 \pm0.00480.3352±0.00200.3352 \pm0.0020

Table 14. Matched-kk candidate-scale ablation on LRIM-32-hard, PascalVOC-SP, and COCO-SP. The architecture is NearFormer (NN) and the retained degree is fixed at k=2k = 2. K=kK = k is ordinary kk-NN; K∈{10,25,50,100}K \in\{10, 25, 50, 100\} are randomized neighborhoods at increasing scale; Exphormer is the expander overlay of degree d=kd = k. LRIM-32-hard is test LogMSE (lower is better); PascalVOC-SP and COCO-SP are test F1 (higher is better). Mean±\pmstd over three seeds.

References

  1. [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. [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. [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. [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. [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. [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. [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. [8]Bresson, X. and Laurent, T. (2017). Residual gated graph convnets. arXiv preprint arXiv:1711.07553.arxiv.org/abs/1711.07553
  9. [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. [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. [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. [12]Christie, T. and He, Y. (2023). Higher-order expander graph propagation. arXiv preprint arXiv:2311.07966.arxiv.org/abs/2311.07966
  13. [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. [14]Deferrard, M., Bresson, X., and Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. NeurIPS, 29:3844–3852.
  15. [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. [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. [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. [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. [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. [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. [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. [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. [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.
  24. [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
  25. [26]Kipf, T. N. and Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In ICLR.arxiv.org/abs/1609.02907
  26. [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
  27. [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
  28. [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
  29. [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.
  30. [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.
  31. [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
  32. [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.
  33. [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.
  34. [36]Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. (2019). Relational pooling for graph representations. In ICML.arxiv.org/abs/1903.02541
  35. [37]Oono, K. and Suzuki, T. (2020). Graph neural networks exponentially lose expressive power for node classification. In ICLR.
  36. [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.
  37. [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
  38. [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
  39. [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
  40. [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
  41. [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.
  42. [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
  43. [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.
  44. [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
  45. [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
  46. [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
  47. [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
  48. [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
  49. [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
  50. [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

Paper details

vlnc:W_qkc65scv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents