2022

Pure Transformers are Powerful Graph Learners

Kim, Jinwoo, Nguyen, Tien Dat, Min, Seonwoo et al.

Understand

We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice.

Given a graph, we simply treat all nodes and edges as independent tokens, augment them with token embeddings, and feed them to a Transformer.
With an appropriate choice of token embeddings, we prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers, which is already more expressive than all message-passing Graph Neural Networks (GNN).
When trained on a large-scale graph dataset (PCQM4Mv2), our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results compared to Transformer variants with sophisticated graph-specific inductive bias.

Built on

Multilayer feedforward networks are universal approximators
K. Hornik, M. B. Stinchcombe, and H. White · 1989
Earlier work this paper cites.
Emergence of scaling in random networks
A.-L. Barabasi and R. Albert · 1999
Earlier work this paper cites.
Adam: A method for stochastic optimization
D. P. Kingma and J. Ba · 2015
Earlier work this paper cites.
Efficient object localization using convolutional networks
J. Tompson, R. Goroshin, A. Jain, Y. LeCun, and C. Bregler · 2015
Earlier work this paper cites.
Group equivariant convolutional networks
T. Cohen and M. Welling · 2016
Earlier work this paper cites.
Approximation with random bases: Pro et contra
A. N. Gorban, I. Y. Tyukin, D. V. Prokhorov, and K. I. Sofeikov · 2016
Earlier work this paper cites.
Deep networks with stochastic depth
G. Huang, Y. Sun, Z. Liu, D. Sedra, and K. Q. Weinberger · 2016
Earlier work this paper cites.
Orthogonal random features
F. X. Yu, A. T. Suresh, K. M. Choromanski, D. N. Holtmann-Rice, and S. Kumar · 2016
Earlier work this paper cites.
Geometric deep learning: Going beyond euclidean data
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst · 2017
Earlier work this paper cites.
The unreasonable effectiveness of structured random orthogonal embeddings
K. M. Choromanski, M. Rowland, and A. Weller · 2017
Earlier work this paper cites.
Steerable cnns
T. S. Cohen and M. Welling · 2017
Earlier work this paper cites.
Neural message passing for quantum chemistry
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl · 2017
Earlier work this paper cites.
Approximating continuous functions by relu nets of minimal width
B. Hanin and M. Sellke · 2017
Earlier work this paper cites.
Semi-supervised classification with graph convolutional networks
T. N. Kipf and M. Welling · 2017
Earlier work this paper cites.
Equivariance through parameter-sharing
S. Ravanbakhsh, J. G. Schneider, and B. Póczos · 2017
Earlier work this paper cites.
Attention is all you need
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin · 2017
Earlier work this paper cites.
Deep sets
M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. Salakhutdinov, and A. J. Smola · 2017
Earlier work this paper cites.
Gaussian error linear units (gelus)
D. Hendrycks and K. Gimpel · 2018
Earlier work this paper cites.
Deeper insights into graph convolutional networks for semi-supervised learning
Q. Li, Z. Han, and X. Wu · 2018
Earlier work this paper cites.
Pitfalls of graph neural network evaluation
O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann · 2018
Earlier work this paper cites.
Tensor field networks: Rotation- and translation-equivariant neural networks for 3d point clouds
N. Thomas, T. E. Smidt, S. Kearnes, L. Yang, L. Li, K. Kohlhoff, and P. Riley · 2018
Earlier work this paper cites.
Graph attention networks
P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio · 2018
Earlier work this paper cites.
3d steerable cnns: Learning rotationally equivariant features in volumetric data
M. Weiler, M. Geiger, M. Welling, W. Boomsma, and T. Cohen · 2018
Earlier work this paper cites.
Convolution, attention and structure embedding
J.-M. Andreoli · 2019
Earlier work this paper cites.
BERT: pre-training of deep bidirectional transformers for language understanding
J. Devlin, M. Chang, K. Lee, and K. Toutanova · 2019
Earlier work this paper cites.
Universal invariant and equivariant graph neural networks
N. Keriven and G. Peyré · 2019
Earlier work this paper cites.
First place solution of 2019 champs predicting molecular properties challenge
Z. Kolter, S. Bai, D. Wilmott, M. Kornbluth, and J. Mailoa · 2019
Earlier work this paper cites.
Set transformer: A framework for attention-based permutation-invariant neural networks
J. Lee, Y. Lee, J. Kim, A. R. Kosiorek, S. Choi, and Y. W. Teh · 2019
Earlier work this paper cites.

Similar

Decoupled weight decay regularization
I. Loshchilov and F. Hutter · 2019
Cited alongside, same era.
Provably powerful graph networks
H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman · 2019
Cited alongside, same era.
Invariant and equivariant graph networks
H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman · 2019
Cited alongside, same era.
On the universality of invariant networks
H. Maron, E. Fetaya, N. Segol, and Y. Lipman · 2019
Cited alongside, same era.
Self-attention with structural position representations
X. Wang, Z. Tu, L. Wang, and S. Shi · 2019
Cited alongside, same era.
How powerful are graph neural networks?
K. Xu, W. Hu, J. Leskovec, and S. Jegelka · 2019
Cited alongside, same era.
On the computational power of transformers and its implications in sequence modeling
S. Bhattamishra, A. Patel, and N. Goyal · 2020
Cited alongside, same era.
Low-rank bottleneck in multi-head attention models
S. Bhojanapalli, C. Yun, A. S. Rawat, S. J. Reddi, and S. Kumar · 2020
Cited alongside, same era.
Language models are few-shot learners
T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei · 2020
Cited alongside, same era.
A note on over-smoothing for graph neural networks
C. Cai and Y. Wang · 2020
Cited alongside, same era.
Can graph neural networks count substructures?
Z. Chen, L. Chen, S. Villar, and J. Bruna · 2020
Cited alongside, same era.
On the relationship between self-attention and convolutional layers
J. Cordonnier, A. Loukas, and M. Jaggi · 2020
Cited alongside, same era.

Then

OGB-LSC: A large-scale challenge for machine learning on graphs
W. Hu, M. Fey, H. Ren, M. Nakata, Y. Dong, and J. Leskovec · 2021
Later among the works it cites.
Edge-augmented graph transformers: Global self-attention is enough for graphs
M. S. Hussain, M. J. Zaki, and D. Subramanian · 2021
Later among the works it cites.
Perceiver IO: A general architecture for structured inputs & outputs
A. Jaegle, S. Borgeaud, J. Alayrac, C. Doersch, C. Ionescu, D. Ding, S. Koppula, D. Zoran, A. Brock, E. Shelhamer, O. J. Hénaff, M. M. Botvinick, A. Zisserman, O. Vinyals, and J. Carreira · 2021
Later among the works it cites.
Perceiver: General perception with iterative attention
A. Jaegle, F. Gimeno, A. Brock, O. Vinyals, A. Zisserman, and J. Carreira · 2021
Later among the works it cites.
Transformers generalize deepsets and can be extended to graphs and hypergraphs
J. Kim, S. Oh, and S. Hong · 2021
Later among the works it cites.
Rethinking graph transformers with spectral attention
D. Kreuzer, D. Beaini, W. L. Hamilton, V. Létourneau, and P. Tossou · 2021
Later among the works it cites.
On the expressive power of self-attention matrices
V. Likhosherstov, K. Choromanski, and A. Weller · 2021
Later among the works it cites.
Mesh graphormer
K. Lin, L. Wang, and Z. Liu · 2021
Later among the works it cites.
Luna: Linear unified nested attention
X. Ma, X. Kong, S. Wang, C. Zhou, J. May, H. Ma, and L. Zettlemoyer · 2021
Later among the works it cites.
Random feature attention
H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. A. Smith, and L. Kong · 2021
Later among the works it cites.
Multi-scale attributed node embedding
B. Rozemberczki, C. Allen, and R. Sarkar · 2021
Later among the works it cites.
Efficient attention: Attention with linear complexities
Z. Shen, M. Zhang, H. Zhao, S. Yi, and H. Li · 2021
Later among the works it cites.
How to train your vit? data, augmentation, and regularization in vision transformers
A. Steiner, A. Kolesnikov, X. Zhai, R. Wightman, J. Uszkoreit, and L. Beyer · 2021
Later among the works it cites.
Which transformer architecture fits my data? A vocabulary bottleneck in self-attention
N. Wies, Y. Levine, D. Jannai, and A. Shashua · 2021
Later among the works it cites.
Nyströmformer: A nyström-based algorithm for approximating self-attention
Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh · 2021
Later among the works it cites.
Do transformers really perform bad for graph representation?
C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T. Liu · 2021
Later among the works it cites.
Incorporating convolution designs into visual transformers
K. Yuan, S. Guo, Z. Liu, A. Zhou, F. Yu, and W. Wu · 2021
Later among the works it cites.
How attentive are graph attention networks?
S. Brody, U. Alon, and E. Yahav · 2022
Closest in time.
Sign and basis invariant networks for spectral graph representation learning
D. Lim, J. Robinson, L. Zhao, T. E. Smidt, S. Sra, H. Maron, and S. Jegelka · 2022
Closest in time.
Transformer for graphs: An overview from architecture perspective
E. Min, R. Chen, Y. Bian, T. Xu, K. Zhao, W. Huang, P. Zhao, J. Huang, S. Ananiadou, and Y. Rong · 2022
Closest in time.
Universal graph transformer self-attention networks
D. Q. Nguyen, T. D. Nguyen, and D. Phung · 2022
Closest in time.
Permutation equivariant layers for higher order interactions
H. Pan and R. Kondor · 2022
Closest in time.
Grpe: Relative positional encoding for graph transformer
W. Park, W. Chang, D. Lee, J. Kim, and S. won Hwang · 2022
Closest in time.
A generalist agent
S. Reed, K. Żolna, E. Parisotto, S. G. Colmenarejo, A. Novikov, G. Barth-Maron, M. Giménez, Y. Sulsky, J. Kay, J. T. Springenberg, T. Eccles, J. Bruce, A. Razavi, A. Edwards, N. Heess, Y. Chen, R. Hadsell, O. Vinyals, M. Bordbar, and N. de Freitas · 2022
Closest in time.
Benchmarking graphormer on large-scale molecular modeling datasets
Y. Shi, S. Zheng, G. Ke, Y. Shen, J. You, J. He, S. Luo, C. Liu, D. He, and T. Liu · 2022
Closest in time.
Deepnet: Scaling transformers to 1, 000 layers
H. Wang, S. Ma, L. Dong, S. Huang, D. Zhang, and F. Wei · 2022
Closest in time.
1-wl expressiveness is (almost) all you need
M. Zopf · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…