mlsanityData to 14 Oct 2026

From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers

arXiv 2107.07999 ↗First posted 16 Jul 2021cs.LG cs.AIcited by 38

Not on the map. Why?

Abstract (arXiv)

In this paper we provide, to the best of our knowledge, the first comprehensive approach for incorporating various masking mechanisms into Transformers architectures in a scalable way. We show that recent results on linear causal attention (Choromanski et al., 2021) and log-linear RPE-attention (Luo et al., 2021) are special cases of this general mechanism. However by casting the problem as a topological (graph-based) modulation of unmasked attention, we obtain several results unknown before, including efficient d-dimensional RPE-masking and graph-kernel masking. We leverage many mathematical techniques ranging from spectral analysis through dynamic programming and random walks to new algorithms for solving Markov processes on graphs. We provide a corresponding empirical evaluation.

Key facts. Cited by 38 papers in the map (data through 14 Oct 2026). Builds on 27 of its 48 references that are in the map. First posted on arXiv 16 Jul 2021.

Builds on

27 of 48 references.

References · 27

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  5. 2017Graph Attention Networkscited by 8,923
  6. 2017Inductive Representation Learning on Large Graphscited by 6,320
  7. 2018How Powerful are Graph Neural Networks?cited by 4,393
  8. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  9. 2020Rethinking Attention with Performerscited by 1,601
  10. 2017Deep Setscited by 1,421
  11. 2018Self-Attention with Relative Position Representationscited by 1,120
  12. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
15 more
  1. 2019Stand-Alone Self-Attention in Vision Modelscited by 542
  2. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  3. 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 471
  4. 2021Random Feature Attentioncited by 354
  5. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
  6. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 310
  7. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  8. 2021Scaling Local Self-Attention for Parameter Efficient Visual Backbonescited by 220
  9. 2020Funnel-Transformer: Filtering out Sequential Redundancy for Efficient Language Processingcited by 162
  10. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 51
  11. 2020Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformerscited by 49
  12. 2021Relative Positional Encoding for Transformers with Linear Complexitycited by 37
  13. 2020Relative Positional Encoding for Speech Recognition and Direct Translationcited by 23
  14. 2019Improving Generalization of Transformer for Speech Recognition with Parallel Schedule Sampling and Relative Positional Embeddingcited by 12
  15. 2019On Graph Classification Networks, Datasets and Baselinescited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 7; 2024: 16; 2025: 8; 2026: 5.

38 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  2. 2023Attending to Graph Transformerscited by 83
  3. 2023GIMLET: A Unified Graph-Text Model for Instruction-Based Molecule Zero-Shot Learningcited by 70
  4. 2024Polynormer: Polynomial-Expressive Graph Transformer in Linear Timecited by 65
  5. 2024Graph Transformers: A Surveycited by 32
  6. 2024On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systemscited by 28
  7. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  8. 2025Learning the RoPEs: Better 2D and 3D Position Encodings with STRINGcited by 19
  9. 2023Taming graph kernels with random featurescited by 17
  10. 2023Are More Layers Beneficial to Graph Transformers?cited by 15
  11. 2025A Survey of Graph Transformers: Architectures, Theories and Applicationscited by 14
  12. 2024Tensor-view Topological Graph Neural Networkcited by 12
26 more
  1. 2024Gradformer: Graph Transformer with Exponential Decaycited by 11
  2. 2023Learning a Fourier Transform for Linear Relative Positional Encodings in Transformerscited by 10
  3. 2023Mnemosyne: Learning to Train Transformers with Transformerscited by 9
  4. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  5. 2023Efficient Graph Field Integrators Meet Point Cloudscited by 7
  6. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  7. 2025Graph Random Features for Scalable Gaussian Processescited by 5
  8. 2024Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformerscited by 3
  9. 2024Instruction-Based Molecular Graph Generation with Unified Text-Graph Diffusion Modelcited by 3
  10. 2024Building on Efficient Foundations: Effectively Training LLMs with Structured Feedforward Layerscited by 2
  11. 2024Graph Transformers Dream of Electric Flowcited by 2
  12. 2025Rotary Position Encodings for Graphscited by 2
  13. 2024Continuous Predictive Modeling of Clinical Notes and ICD Codes in Patient Health Recordscited by 1
  14. 2024GrokFormer: Graph Fourier Kolmogorov-Arnold Transformerscited by 1
  15. 2025TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flowscited by 1
  16. 2026ToTMNet: FFT-Accelerated Toeplitz Temporal Mixing Network for Lightweight Remote Photoplethysmographycited by 1
  17. 2026Size-Transferability of Graph Transformers with Convolutional Positional Encodingscited by 1
  18. 2026RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodingscited by 1
  19. 2026SMat-Attention: Structured Long-Context Sequence Modelingcited by 1
  20. 2022Karyotype AI for Precision Oncologycited by 0
  21. 2024Graph Expansion in Pruned Recurrent Neural Network Layers Preserve Performancecited by 0
  22. 2024AKBR: Learning Adaptive Kernel-based Representations for Graph Classificationcited by 0
  23. 2025Lightweight yet Efficient: An External Attentive Graph Convolutional Network with Positional Prompts for Sequential Recommendationcited by 0
  24. 2025Graph Fourier Transformer with Structure-Frequency Informationcited by 0
  25. 2025Predictive Multimodal Modeling of Diagnoses and Treatments in EHRcited by 0
  26. 2026ClockRoPE: Random Fourier Rotations for Temporal Routine Modelingcited by 0