Research map / Graph learning / GNN architectures
Linear Transformer Topological Masking with Graph Random Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes graph-random-feature (GRF) estimates of learnable power-series graph node kernel masks, giving O(N) topological masking for linear transformers with new concentration bounds, tested on ViT image classification and HD-VPD point-cloud dynamics.
Problem
Topological masking of transformer attention on general graphs is costly: exact masks need O(N^2) time, and prior subquadratic methods are limited to restricted graphs (grids, trees) or O(N log N) time, so efficient low-rank masking with flexible functions on general graphs was out of reach.
Approach
Parameterise the attention mask as a learnable power series in a weighted adjacency matrix (a graph node kernel), and approximate its factorised feature map with sparse Monte Carlo graph random features from random walks, proving exponential concentration and O(1) feature sparsity so masked linear attention runs in O(N).
Key results
- GRF-masked linear attention reaches 0.730 on ImageNet vs 0.693 unmasked linear (+3.7%) and 0.741 unmasked softmax, the best O(N) variant.
- On iNaturalist2021 GRF-masked linear gets 0.689 vs 0.667 unmasked linear; on Places365 0.548 vs 0.543.
- On HD-VPD with 32768 particles, the GRF Interlacer gives higher frame SSIM than the vanilla transformer and message-passing Interlacer baselines; ViViT on Kinetics improves from 0.754 to 0.758.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add GRF topological masking to unmasked linear attention | ViT · ImageNet test | accuracy: 0.693 -> 0.730 | Helped |
| Add GRF topological masking to unmasked linear attention | ViT · iNaturalist2021 test | accuracy: 0.667 -> 0.689 | Helped |
| Add GRF topological masking to unmasked linear attention | ViT · Places365 (Small) test | accuracy: 0.543 -> 0.548 | Helped |
| Add GRF topological masking to softmax attention | ViViT · Kinetics 400 test | accuracy: 0.754 -> 0.758 | Helped |
| Increase the number of random walkers (ablation) | GRF-masked ViT · ImageNet test | accuracy | Helped |
| Remove random-walk probability and edge-weight reweighting (ablation) | GRF-masked ViT · ImageNet test | accuracy: 0.730 -> 0.689 | Hurt |
| Replace the adjacency-function mask with fully learnable dense graph features (ablation) | GRF-masked ViT · ImageNet test | accuracy: 0.730 -> 0.696 | Hurt |
| Replace message passing with GRF-masked linear attention | Interlacer · HD-VPD particle dynamics | image SSIM | Helped |
Surprising findings
- Ad-hoc random-walk masks without importance-sampling weights perform worse than the unmasked linear baseline (0.689 vs 0.693 is slightly lower in ablation table than GRF but the ad-hoc mask is reported as worse than unmasked), showing importance weighting is crucial.
- Fully learnable dense N-dimensional mask features give only a very small gain (0.696 vs 0.693 unmasked), suggesting the structural graph-function inductive bias matters more than flexibility.
Limitations
- Variance of asymmetric GRF mask estimates tends to be higher and is unproven.
- Sparse matrix operations are not well optimised in ML libraries, so theoretical complexity gains may not fully materialise in practice.
- Video (ViViT) results are preliminary with a small +0.4% gain on a single run.
Experimental setup
Datasets: ImageNet iNaturalist2021 Places365 Kinetics 400 HD-VPD robotics dataset
Benchmarks: ImageNet iNaturalist2021 Places365 (Small) Kinetics 400 HD-VPD SSIM rollouts
Metrics: test accuracy SSIM FLOPs
Baselines: Unmasked softmax Toeplitz-masked linear M_alpha-masked linear (exact) Unmasked linear Ad-hoc random walk kernel Fully learnable features Message passing Interlacer Vanilla transformer
Builds on: Toeplitz masking (stochastic position encoding / FFT masks) Graphormer Performer Linear transformers (elu+1) Interlacer graph attention networks
Closest papers by meaning
- Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers (NeurIPS 2024 · similarity 0.89)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.88)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 2025 · similarity 0.87)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.87)
- VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections (ICLR 2024 · similarity 0.86)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.