# Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks](https://mlsanity.com/paper/1810.00825/) (2018)
- [DeepInf: Social Influence Prediction with Deep Learning](https://mlsanity.com/paper/1807.05560/) (2018)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [Implicit Graph Neural Networks](https://mlsanity.com/paper/2009.06211/) (2020)
- [Deep Models of Interactions Across Sets](https://mlsanity.com/paper/1803.02879/) (2018)
- [Hyper-SAGNN: a self-attention based graph neural network for hypergraphs](https://mlsanity.com/paper/1911.02613/) (2019)
- [Random walks on hypergraphs](https://mlsanity.com/paper/1911.06523/) (2019)
- [Set2Graph: Learning Graphs From Sets](https://mlsanity.com/paper/2002.08772/) (2020)

## Built on by (most cited first, 30 of 35)

- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Graph Metanetworks for Processing Diverse Neural Architectures](https://mlsanity.com/paper/2312.04501/) (2023)
- [3Mformer: Multi-order Multi-mode Transformer for Skeletal Action Recognition](https://mlsanity.com/paper/2303.14474/) (2023)
- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance](https://mlsanity.com/paper/2306.02866/) (2023)
- [High-Order Pooling for Graph Neural Networks with Tensor Decomposition](https://mlsanity.com/paper/2205.11691/) (2022)
- [Devil's on the Edges: Selective Quad Attention for Scene Graph Generation](https://mlsanity.com/paper/2304.03495/) (2023)
- [A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide](https://mlsanity.com/paper/2404.01039/) (2024)
- [Crystalformer: Infinitely Connected Attention for Periodic Structure Encoding](https://mlsanity.com/paper/2403.11686/) (2024)
- [Equivariant Hypergraph Neural Networks](https://mlsanity.com/paper/2208.10428/) (2022)
- [Classification of Edge-dependent Labels of Nodes in Hypergraphs](https://mlsanity.com/paper/2306.03032/) (2023)
- [Towards Understanding Inductive Bias in Transformers: A View From Infinity](https://mlsanity.com/paper/2402.05173/) (2024)
- [Towards Principled Graph Transformers](https://mlsanity.com/paper/2401.10119/) (2024)
- [Attending to Topological Spaces: The Cellular Transformer](https://mlsanity.com/paper/2405.14094/) (2024)
- [Meet JEANIE: a Similarity Measure for 3D Skeleton Sequences via Temporal-Viewpoint Alignment](https://mlsanity.com/paper/2402.04599/) (2024)
- [On permutation-invariant neural networks](https://mlsanity.com/paper/2403.17410/) (2024)
- [Cell Graph Transformer for Nuclei Classification](https://mlsanity.com/paper/2402.12946/) (2024)
- [On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers](https://mlsanity.com/paper/2404.03380/) (2024)
- [Fast computation of permutation equivariant layers with the partition algebra](https://mlsanity.com/paper/2303.06208/) (2023)
- [Recasting Generic Pretrained Vision Transformers As Object-Centric Scene Encoders For Manipulation Policies](https://mlsanity.com/paper/2405.15916/) (2024)
- [G-Signatures: Global Graph Propagation With Randomized Signatures](https://mlsanity.com/paper/2302.08811/) (2023)
- [Graph as Point Set](https://mlsanity.com/paper/2405.02795/) (2024)
- [CSA-Trans: Code Structure Aware Transformer for AST](https://mlsanity.com/paper/2404.05767/) (2024)
- [SE3Set: Harnessing equivariant hypergraph neural networks for molecular representation learning](https://mlsanity.com/paper/2405.16511/) (2024)
- [Graph Transformers Dream of Electric Flow](https://mlsanity.com/paper/2410.16699/) (2024)
- [Using Random Noise Equivariantly to Boost Graph Neural Networks Universally](https://mlsanity.com/paper/2502.02479/) (2025)
- [There is more to graphs than meets the eye: Learning universal features with self-supervision](https://mlsanity.com/paper/2305.19871/) (2023)
- [Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks](https://mlsanity.com/paper/2511.03824/) (2025)

## Abstract (arXiv)

We present a generalization of Transformers to any-order permutation invariant data (sets, graphs, and hypergraphs). We begin by observing that Transformers generalize DeepSets, or first-order (set-input) permutation invariant MLPs. Then, based on recently characterized higher-order invariant MLPs, we extend the concept of self-attention to higher orders and propose higher-order Transformers for order-k data (k=2 for graphs and k>2 for hypergraphs). Unfortunately, higher-order Transformers turn out to have prohibitive complexity O(n2k) to the number of input nodes n. To address this problem, we present sparse higher-order Transformers that have quadratic complexity to the number of input hyperedges, and further adopt the kernel attention approach to reduce the complexity to linear. In particular, we show that the sparse second-order Transformers with kernel attention are theoretically more expressive than message passing operations while having an asymptotically identical complexity. Our models achieve significant performance improvement over invariant MLPs and message-passing graph neural networks in large-scale graph regression and set-to-(hyper)graph prediction tasks. Our implementation is available at https://github.com/jw9730/hot.