Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs (2021-10-27T00:00:00.000000Z)

TL;DR

This work presents sparse second-order Transformers with kernel attention that 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.

Abstract

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 $\mathcal{O}(n^{2k})$ 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.

Authors

Seunghoon Hong

6 papers

Jinwoo Kim

2 papers

Saeyoon Oh

1 papers

TL;DR

Abstract

Authors

References58 items

OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs

A Generalization of Transformer Networks to Graphs

Rethinking Attention with Performers

Implicit Graph Neural Networks

Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention

A Note on Over-Smoothing for Graph Neural Networks

Set2Graph: Learning Graphs From Sets

On Layer Normalization in the Transformer Architecture

Are Transformers universal approximators of sequence-to-sequence functions?

Random walks on hypergraphs

Hyper-SAGNN: a self-attention based graph neural network for hypergraphs

Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

Provably Powerful Graph Networks

Universal Invariant and Equivariant Graph Neural Networks

Graph Neural Networks: A Review of Methods and Applications

Deep Learning on Graphs: A Survey

Set Transformer

Invariant and Equivariant Graph Networks

DeepInf: Social Influence Prediction with Deep Learning

Deep Models of Interactions Across Sets

Neural Relational Inference for Interacting Systems

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

Decoupled Weight Decay Regularization

Protein Interface Prediction using Graph Convolutional Networks

Approximating Continuous Functions by ReLU Nets of Minimal Width

Attention is All you Need

Neural Message Passing for Quantum Chemistry

Deep Sets

Layer Normalization

Gaussian Error Linear Units (GELUs)

The MovieLens Datasets: History and Context

Adam: A Method for Stochastic Optimization

Collaborative Filtering Meets Mobile Recommendation: A User-Centered Approach

Laplacian Eigenmaps for Dimensionality Reduction and Data Representation

Multilayer feedforward networks are universal approximators

A Comprehensive Survey on Graph Neural Networks

and s

Dropout: a simple way to prevent neural networks from overfitting

IMPROVED BOUNDS ON BELL NUMBERS AND ON MOMENTS OF SUMS OF RANDOM VARIABLES

Sur la sphère vide

Bulletin de l'Académie des Sciences de l'URSS, Classe des

Did you discuss any potential negative societal impacts of your work?

(a) Did you state the full set of assumptions of all theoretical results? [Yes] (b) Did you include complete proofs of all theoretical results?

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable

As a first step, we encode X and E into a single A ∈ R n×n×(2dv+de) [26]. In the first d v channels, we replicate X on the rows

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation

Did you discuss whether and how consent was obtained from people whose data you're using/curating?

Output dimension of a layer is denoted in parenthesis

To do this, we first reduce Attn 2→2 (A) ij = A ij and apply MLP l→l on top of it. We reduce MLP l→l to entry-wise MLP. As Attn 2→2 (A) ij = A ij Method Architecture MLP π (D/S)

/o global Enc 2→2,φ,ablated (16)-Enc 2→1,φ,ablated (16)-LN-Linear(2) Ours (S) Enc 2→2 (16)-Enc 2→1 (16)-LN-Linear(2) Ours (S, φ) Enc 2→2,φ (16)-Enc 2→1

Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?

Have you read the ethics review guidelines and ensured that your paper conforms to them

code, data, models) or curating/releasing new assets... (a) If your work uses existing assets

If you used crowdsourcing or conducted research with human subjects... (a) Did you include the full text of instructions given to participants and screenshots

with respect to the random seed after running experiments multiple times)? [Yes] We reported standard deviation of ten repeated experiments in Table 1

(a) Did you include the code, data, and instructions needed to reproduce the main experimental results

LN-Linear(1) MLP π (S) [L 2→2 (256) − ReLU] ×8 -L 2→0 (256)-Linear(1) Ours (S, φ) −SMALL Enc 2→2

Before feeding the output to the second Enc 2 → 2 , we concatenate the original input A with the output of the ﬁrst layer in the channel dimension to make A (cid:48) ∈ R n × n × (2 d v + d e + d m )

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names