mlsanityData to 7 Oct 2026

Linear Transformer Topological Masking with Graph Random Features

arXiv 2410.03462 ↗First posted 4 Oct 2024cs.LG stat.MLcited by 7

Not on the map. Why?

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.

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

Builds on

31 of 58 references.

References · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  3. 2015U-Net: Convolutional Networks for Biomedical Image Segmentationcited by 19,604
  4. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 8,964
  5. 2017Graph Attention Networkscited by 8,854
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,801
  8. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  9. 2017The Kinetics Human Action Video Datasetcited by 1,894
  10. 2021ViViT: A Video Vision Transformercited by 1,610
  11. 2020Rethinking Attention with Performerscited by 1,584
  12. 2018Self-Attention with Relative Position Representationscited by 1,112
19 more
  1. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  2. 2022Point-NeRF: Point-based Neural Radiance Fieldscited by 503
  3. 2020Mat'ern Gaussian Processes on Graphscited by 65
  4. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 50
  5. 2021From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformerscited by 38
  6. 2021Relative Positional Encoding for Transformers with Linear Complexitycited by 36
  7. 2014Heat kernel based community detectioncited by 30
  8. 2021Hybrid Random Featurescited by 25
  9. 2020Gaussian Processes on Graphs via Spectral Kernel Learningcited by 24
  10. 2023Taming graph kernels with random featurescited by 17
  11. 2023Learning 3D Particle-based Simulators from RGB-D Videoscited by 17
  12. 2024Modeling the Real World with High-Density Visual Particle Dynamicscited by 12
  13. 2023General Graph Random Featurescited by 10
  14. 2023Simplex Random Featurescited by 9
  15. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  16. 2020Learning Manifold Implicitly via Explicit Heat-Kernel Learningcited by 7
  17. 2023Repelling Random Walkscited by 6
  18. 2024Masked Graph Transformer for Large-Scale Recommendationcited by 5
  19. 2024Variance-Reducing Couplings for Random Featurescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 3.

7 papers.

  1. 2025Learning the RoPEs: Better 2D and 3D Position Encodings with STRINGcited by 19
  2. 2025Graph Random Features for Scalable Gaussian Processescited by 4
  3. 2025Computationally-efficient Graph Modeling with Refined Graph Random Featurescited by 2
  4. 2025Rotary Position Encodings for Graphscited by 1
  5. 2026RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodingscited by 1
  6. 2026SWING: Unlocking Implicit Graph Representations for Graph Random Featurescited by 0
  7. 2026Global and Local Topology-Aware Attention with Persistent Homology and Euler Biases for Time-Series Forecastingcited by 0