NearFormer: Linear-Size Sparse Attention via Randomized Near Neighbors
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 , the resulting attention support has linear size . The NN graph is built once by within-bin search and then held fixed. We use these edges as sparse global-attention supports, with optional learned attention biases, while preserving the original graph for local message passing. Experiments on long-range graph benchmarks and synthetic structural tasks show that NearFormer provides a favorable accuracy--scalability trade-off relative to local message passing, dense and sparse attention.
Figures & tables
| Model | PascalVOC-SP | COCO-SP | Peptides-Func | Peptides-Struct | PCQM-Contact |
|---|---|---|---|---|---|
| F1 score | F1 score | AP | MAE | MRR | |
| GCN | |||||
| GINE | |||||
| GatedGCN | |||||
| GatedGCN+RWSE | |||||
| Transformer+LapPE |
| Method | ECHO-Synth | ECHO-Chem | |||||
|---|---|---|---|---|---|---|---|
| diam | ecc | sssp | Mean SSSP | Mean ER | Energy | Charge | |
| A-DGN | |||||||
| DRew | |||||||
| GraphCON | |||||||
| GCN | |||||||
| GCNII | |||||||
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Graphs | Avg. nodes | Avg. edges | Level | Metric |
|---|---|---|---|---|---|
| PascalVOC-SP | 11,355 | 479.4 | 2,710.5 | node | F1 |
| COCO-SP | 123,286 | 476.9 | 2,693.7 | node | F1 |
| Peptides-Func | 15,535 | 150.9 | 307.3 | graph | AP |
| Peptides-Struct | 15,535 | 150.9 | 307.3 | graph | MAE |
| PCQM-Contact | 529,434 | 30.1 | 61.0 | link | MRR |
| Dataset | Graphs | Nodes | Edges | Avg. shortest path | Diameter |
|---|---|---|---|---|---|
| LRIM-16 | 10,000 | 256 | 512 | 8.03 | 16 |
| LRIM-32 | 10,000 | 1,024 | 2,048 | 16.02 | 32 |
| LRIM-64 | 10,000 | 4,096 | 8,192 | 32.01 | 64 |
| LRIM-128 | 10,000 | 16,384 | 32,768 | 64.00 | 128 |
| LRIM-256 | 10,000 | 65,536 | 131,072 | 128.00 | 256 |
| Dataset | Graphs | Avg. nodes | Avg. edges | Avg. diameter |
|---|---|---|---|---|
| ECHO-Synth | 10,080 | |||
| ECHO-Charge | 170,367 | |||
| ECHO-Energy | 196,528 |
| Method | Quantity | 16 | 32 | 64 | 128 | 256 |
|---|---|---|---|---|---|---|
| NearFormer (NN) | Attn. edges | |||||
| Peak mem (GB) | ||||||
| Step time (ms) | ||||||
| NN preproc. (ms) | ||||||
| Exphormer | Attn. edges |
| Hyperparameter | PascalVOC-SP | COCO-SP | Peptides-Func | Peptides-Struct | PCQM-Contact | ECHO |
|---|---|---|---|---|---|---|
| Num Layers | 4 | 7 | 8 | 4 | 7 | Table 10 |
| Hidden Dim | 96 | 72 | 64 | 88 | 64 | Table 10 |
| Num Heads | 8 | 4 | 4 | 4 | 4 | 2 |
| Dropout | 0.15 | 0 | 0.12 | 0.12 | 0 | 0 |
| PE | LapPE | LapPE | LapPE | LapPE | LapPE | LapPE |
| Batch Size | 32 | 32 | 128 | 128 | 128 | 128 |
| Hyperparameter | Search interval | diam | sssp | ecc | ECHO-Charge | ECHO-Energy |
|---|---|---|---|---|---|---|
| Number of layers | 17 | 26 | 17 | 36 | 26 | |
| Hidden dimension | 40 | 56 | 162 | 216 | 192 | |
| Learning rate | 0.00004 | 0.00031 | 0.00034 | 0.00005 | 0.000024067 | |
| Weight decay | 0.00015 | 0.00029 | 0.00007 | 0.00005 | 0.00038179 | |
| GNN Backbone | GCN | GCN | GCN | GCN | GCN | |
| Number of Backbone Layers | 1 | 1 | 1 | 1 | 1 |
| Model | 16 | 32 | 64 | 128 | 256 |
|---|---|---|---|---|---|
| GIN | |||||
| GatedGCN | |||||
| GatedGCN-VNG | |||||
| GPS-Base | OOM | OOM | OOM | ||
| GPS-RWSE | OOM | OOM | OOM | ||
| GPS-LapPE | OOM | OOM | OOM |
| Method | Heat Diffusion |
|---|---|
| A-DGN | |
| DRew | |
| GraphCON | |
| GCN | |
| GCNII | |
| GIN |
| Overlay | LRIM-32-hard | LRIM-64-hard | ||
|---|---|---|---|---|
| Ordinary -NN | ||||
| NearFormer (NN) | ||||
| NearFormer (NN) | ||||
| NearFormer (NN) | ||||
| NearFormer (NN) | ||||
| Global-random |
| Overlay | LRIM-32-hard | PascalVOC-SP | COCO-SP | |
|---|---|---|---|---|
| Ordinary -NN | ||||
| NearFormer (NN) | ||||
| NearFormer (NN) | ||||
| NearFormer (NN) | ||||
| NearFormer (NN) | ||||
| Exphormer | – |
Graph Transformer
Graph Transformers adapt self-attention to represent relationships, topology, and long-range dependencies in graph-structured data.
See all 104 papers