2020

A Survey on The Expressive Power of Graph Neural Networks

Sato, Ryoma

Understand

Graph neural networks (GNNs) are effective machine learning models for various graph learning problems.

Despite their empirical successes, the theoretical limitations of GNNs have been revealed recently.
Consequently, many GNN models have been proposed to overcome these limitations.
In this survey, we provide a comprehensive overview of the expressive power of GNNs and provably powerful variants of GNNs.

Built on

Paths, trees, and flowers
Jack Edmonds · 1965
Earlier work this paper cites.
Topological organic chemistry. polyhedranes and prismanes
Harry P Schultz · 1965
Earlier work this paper cites.
A reduction of a graph to a canonical form and an algebra arising during this reduction
Boris Weisfeiler and Andrei A Lehman · 1968
Earlier work this paper cites.
Approximation algorithms for combinatorial problems
David S. Johnson · 1974
Earlier work this paper cites.
On the ratio of optimal integral and fractional covers
László Lovász · 1975
Earlier work this paper cites.
Local and global properties in networks of processors (extended abstract)
Dana Angluin · 1980
Earlier work this paper cites.
Random graph isomorphism
László Babai, Paul Erdös, and Stanley M. Selkow · 1980
Earlier work this paper cites.
Total synthesis of dodecahedrane
Leo A Paquette, Robert J Ternansky, Douglas W Balogh, and Gary Kentgen · 1983
Earlier work this paper cites.
Approximation by superpositions of a sigmoidal function
George Cybenko · 1989
Earlier work this paper cites.
Multilayer feedforward networks are universal approximators
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White · 1989
Earlier work this paper cites.
Describing graphs: A first-order approach to graph canonization
Neil Immerman and Eric Lander · 1990
Earlier work this paper cites.
Approximation capabilities of multilayer feedforward networks
Kurt Hornik · 1991
Earlier work this paper cites.
A note on compact graphs
Gottfried Tinhofer · 1991
Earlier work this paper cites.
An optimal lower bound on the number of variables for graph identifications
Jin-yi Cai, Martin Fürer, and Neil Immerman · 1992
Earlier work this paper cites.
Locality in distributed graph algorithms
Nathan Linial · 1992
Earlier work this paper cites.
Fractional isomorphism of graphs
Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman · 1994
Earlier work this paper cites.
What can be computed locally?
Moni Naor and Larry J. Stockmeyer · 1995
Earlier work this paper cites.
A neural device for searching direct correlations between structures and properties of chemical compounds
Igor I. Baskin, Vladimir A. Palyulin, and Nikolai S. Zefirov · 1997
Earlier work this paper cites.
Approximation of k -set cover by semi-local optimization
Rong-chii Duh and Martin Fürer · 1997
Earlier work this paper cites.
Supervised neural networks for the classification of structures
Alessandro Sperduti and Antonina Starita · 1997
Earlier work this paper cites.
Network motifs: simple building blocks of complex networks
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon · 2002
Earlier work this paper cites.
The structure and function of complex networks
Mark E. J. Newman · 2003
Earlier work this paper cites.
A new model for learning in graph domains
Marco Gori, Gabriele Monfardini, and Franco Scarselli · 2005
Earlier work this paper cites.
Automatic generation of complementary descriptors with molecular graph networks
Christian Merkwirth and Thomas Lengauer · 2005
Earlier work this paper cites.
A new algorithm for optimal 2-constraint satisfaction and its implications
Ryan Williams · 2005
Earlier work this paper cites.
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
Michal Parnas and Dana Ron · 2007
Earlier work this paper cites.
Approximation hardness of dominating set problems in bounded degree graphs
Miroslav Chlebík and Janka Chlebíková · 2008
Earlier work this paper cites.
Fast distributed approximations in planar graphs
Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak · 2008
Earlier work this paper cites.

Similar

Vertex cover might be hard to approximate to within 2-epsilon
Subhash Khot and Oded Regev · 2008
Cited alongside, same era.
Leveraging linial’s locality limit
Christoph Lenzen and Roger Wattenhofer · 2008
Cited alongside, same era.
A local 2-approximation algorithm for the vertex cover problem
Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto · 2009
Cited alongside, same era.
Introduction to algorithms
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein · 2009
Cited alongside, same era.
The graph neural network model
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini · 2009
Cited alongside, same era.
Local algorithms in (weakly) coloured graphs
Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto · 2010
Cited alongside, same era.
Nonparametric tree graphical models
Le Song, Arthur Gretton, and Carlos Guestrin · 2010
Cited alongside, same era.
Subcubic equivalences between path, matrix and triangle problems
Virginia Vassilevska Williams and Ryan Williams · 2010
Cited alongside, same era.
Kernel belief propagation
Le Song, Arthur Gretton, Danny Bickson, Yucheng Low, and Carlos Guestrin · 2011
Cited alongside, same era.
Weak models of distributed computing, with connections to modal logic
Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema · 2012
Cited alongside, same era.
Combinatorial optimization , volume 2
Bernhard Korte, Jens Vygen, B Korte, and J Vygen · 2012
Cited alongside, same era.
Sherali–adams relaxations and indistinguishability in counting logics
Albert Atserias and Elitza Maneva · 2013
Cited alongside, same era.

Then

Deep sets
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola · 2017
Later among the works it cites.
Deep models of interactions across sets
Jason S. Hartford, Devon R. Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh · 2018
Later among the works it cites.
Covariant compositional networks for learning graphs
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi · 2018
Later among the works it cites.
Combinatorial optimization with graph convolutional networks and guided tree search
Zhuwen Li, Qifeng Chen, and Vladlen Koltun · 2018
Later among the works it cites.
Modeling relational data with graph convolutional networks
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling · 2018
Later among the works it cites.
Graph attention networks
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio · 2018
Later among the works it cites.
On some fine-grained questions in algorithms and complexity
Virginia Vassilevska Williams · 2018
Later among the works it cites.
Graph convolutional neural networks for web-scale recommender systems
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec · 2018
Later among the works it cites.
An end-to-end deep learning architecture for graph classification
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen · 2018
Later among the works it cites.
Graph neural networks: A review of methods and applications
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun · 2018
Later among the works it cites.
On the equivalence between graph isomorphism testing and function approximation with gnns
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna · 2019
Later among the works it cites.
Graph neural networks for social recommendation
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin · 2019
Later among the works it cites.
Exact combinatorial optimization with graph convolutional neural networks
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi · 2019
Later among the works it cites.
Exact-k recommendation via maximal clique optimization
Yu Gong, Yu Zhu, Lu Duan, Qingwen Liu, Ziyu Guan, Fei Sun, Wenwu Ou, and Kenny Q. Zhu · 2019
Later among the works it cites.
Universal invariant and equivariant graph neural networks
Nicolas Keriven and Gabriel Peyré · 2019
Later among the works it cites.
Understanding attention and generalization in graph neural networks
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer · 2019
Later among the works it cites.
Provably powerful graph networks
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman · 2019
Later among the works it cites.
Weisfeiler and leman go neural: Higher-order graph neural networks
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe · 2019
Later among the works it cites.
Estimating node importance in knowledge graphs using graph neural networks
Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, and Christos Faloutsos · 2019
Later among the works it cites.
Approximation ratios of graph neural networks for combinatorial problems
Ryoma Sato, Makoto Yamada, and Hisashi Kashima · 2019
Later among the works it cites.
A comprehensive survey on graph neural networks
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu · 2019
Later among the works it cites.
How powerful are graph neural networks?
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka · 2019
Later among the works it cites.
The logical expressiveness of graph neural networks
Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva · 2020
Closest in time.
Can graph neural networks count substructures?
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna · 2020
Closest in time.
Generalization and representational limits of graph neural networks
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola · 2020
Closest in time.
What graph neural networks cannot learn: depth vs width
Andreas Loukas · 2020
Closest in time.
Random features strengthen graph neural networks
Ryoma Sato, Makoto Yamada, and Hisashi Kashima · 2020
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…