# Linear Transformer Topological Masking with Graph Random Features

arXiv: https://arxiv.org/abs/2410.03462 · HTML: https://mlsanity.com/paper/2410.03462/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 58 references that are in the map.
- First posted on arXiv 4 Oct 2024.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [The Kinetics Human Action Video Dataset](https://mlsanity.com/paper/1705.06950/) (2017)
- [ViViT: A Video Vision Transformer](https://mlsanity.com/paper/2103.15691/) (2021)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Point-NeRF: Point-based Neural Radiance Fields](https://mlsanity.com/paper/2201.08845/) (2022)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding](https://mlsanity.com/paper/2106.12566/) (2021)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [Relative Positional Encoding for Transformers with Linear Complexity](https://mlsanity.com/paper/2105.08399/) (2021)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Gaussian Processes on Graphs via Spectral Kernel Learning](https://mlsanity.com/paper/2006.07361/) (2020)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Learning 3D Particle-based Simulators from RGB-D Videos](https://mlsanity.com/paper/2312.05359/) (2023)
- [Modeling the Real World with High-Density Visual Particle Dynamics](https://mlsanity.com/paper/2406.19800/) (2024)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Learning Manifold Implicitly via Explicit Heat-Kernel Learning](https://mlsanity.com/paper/2010.01761/) (2020)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Masked Graph Transformer for Large-Scale Recommendation](https://mlsanity.com/paper/2405.04028/) (2024)

## Built on by (most cited first, 7 of 7)

- [Learning the RoPEs: Better 2D and 3D Position Encodings with STRING](https://mlsanity.com/paper/2502.02562/) (2025)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Rotary Position Encodings for Graphs](https://mlsanity.com/paper/2509.22259/) (2025)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings](https://mlsanity.com/paper/2605.10706/) (2026)
- [SWING: Unlocking Implicit Graph Representations for Graph Random Features](https://mlsanity.com/paper/2602.12703/) (2026)
- [Global and Local Topology-Aware Attention with Persistent Homology and Euler Biases for Time-Series Forecasting](https://mlsanity.com/paper/2605.03163/) (2026)

## Abstract (arXiv)

When training transformers on graph-structured data, incorporating information about the underlying topology is crucial for good performance. Topological masking, a type of relative position encoding, achieves this by upweighting or downweighting attention depending on the relationship between the query and keys in a graph. In this paper, we propose to parameterise topological masks as a learnable function of a weighted adjacency matrix -- a novel, flexible approach which incorporates a strong structural inductive bias. By approximating this mask with graph random features (for which we prove the first known concentration bounds), we show how this can be made fully compatible with linear attention, preserving O(N) time and space complexity with respect to the number of input tokens. The fastest previous alternative was O(N log N) and only suitable for specific graphs. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data, including with >30k nodes.