Papers › Transformers Generalize DeepSets and Can be Extended to Graphs & Hypergraphs

Transformers Generalize DeepSets and Can be Extended to Graphs & Hypergraphs

21 May 2021NeurIPS 2021 12archive 2025-07-28

Jinwoo Kim, Saeyoon Oh, Seunghoon Hong

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 𝒪(n²ᵏ) 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.

PaperPDFCode

Syntology This paper has no arXiv id in the archive, and this site joins papers to Syntology's graph by arXiv id, so this page does not say whether the graph holds it.

Code

jw9730/hot officialmentioned in paperpytorchSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs (arXiv:2110.14416; that paper's own run record: 0 ran · 1 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

2kGraph Regression

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections