cs.LGNov 9, 2026

NearFormer: Linear-Size Sparse Attention via Randomized Near Neighbors

Authors: Ali Parviz, Alex Cloninger, Gal Mishne

Organizations: Halicioğlu Data Science Institute, UC San Diego · Department of Mathematics, UC San Diego

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.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS

    Apr 4, 2026Jonas De Schouwer, Haitz Sáez de Ocáriz Borde, Xiaowen DongTransformer AttentionGraph Transformer

  2. Attention Graphons: A Graph Limit Perspective on Graph Transformers

    Sep 28, 2026Caio F. Deberaldini Netto, Moshe Eliasof, Luana RuizGraphon TheoryTransformer Attention

  3. Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

    Mar 18, 2026Nil Ayday, Lingchu Yang, Debarghya GhoshdastidarGNN OversmoothingGraph Neural Networks