2021/10/27 by Jinwoo Kim, Kim, Jinwoo, Saeyoon Oh +3 · 2 citations
Computer Science · Environmental Science · #Advanced Graph Neural Networks #Energy and Environment Impacts #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2110.14416
openalex publication_date 2021/10/27 · openalex created_date 2021/11/08 · openalex updated_date 2026/07/28
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.