2019

What graph neural networks cannot learn: depth vs width

Loukas, Andreas

Understand

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp).

Two results are presented.
First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness.
Second, it is discovered that GNNmp can lose a significant portion of their power when their depth and width is restricted.

Built on

On the universality of invariant networks
Original
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman · 1901
Earlier work this paper cites.
Provably powerful graph networks
Original
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman · 1905
Earlier work this paper cites.
Local and global properties in networks of processors (extended abstract)
Dana Angluin · 1980
Earlier work this paper cites.
Unbiased bits from sources of weak randomness and probabilistic communication complexity
Benny Chor and Oded Goldreich · 1988
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 Stinchcombe, and Halbert White · 1989
Earlier work this paper cites.
The probabilistic communication complexity of set intersection
Bala Kalyanasundaram and Georg Schintger · 1992
Earlier work this paper cites.
Locality in distributed graph algorithms
Nathan Linial · 1992
Earlier work this paper cites.
What can be computed locally?
Moni Naor and Larry J. Stockmeyer · 1993
Earlier work this paper cites.
Turing universality of neural nets (revisited)
J Pedro Neto, Hava T Siegelmann, J Félix Costa, and CP Suárez Araujo · 1997
Earlier work this paper cites.
Distributed Computing: A Locality-Sensitive Approach
D. Peleg · 2000
Earlier work this paper cites.
Networks cannot compute their diameter in sublinear time
Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer · 2012
Earlier work this paper cites.
Distributed verification and hardness of distributed approximation
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer · 2012
Earlier work this paper cites.
Towards a complexity theory for local distributed computing
Pierre Fraigniaud, Amos Korman, and David Peleg · 2013
Earlier work this paper cites.
Distributed minimum cut approximation
Mohsen Ghaffari and Fabian Kuhn · 2013
Earlier work this paper cites.
Survey of local algorithms
Jukka Suomela · 2013
Earlier work this paper cites.

Similar

On the power of the congested clique model
Andrew Drucker, Fabian Kuhn, and Rotem Oshman · 2014
Cited alongside, same era.
On the power of color refinement
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky · 2015
Cited alongside, same era.
Convolutional networks on graphs for learning molecular fingerprints
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams · 2015
Cited alongside, same era.
Graphs identified by logics with counting
Sandra Kiefer, Pascal Schweitzer, and Erkal Selman · 2015
Cited alongside, same era.
Gated graph sequence neural networks
Original
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel · 2015
Cited alongside, same era.
Anonymous distributed computing: computability, randomization and checkability
Jochen Seidel · 2015
Cited alongside, same era.
Near-linear lower bounds for distributed distance computations, even in sparse networks
Amir Abboud, Keren Censor-Hillel, and Seri Khoury · 2016
Cited alongside, same era.
Interaction networks for learning about objects, relations and physics
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al · 2016
Cited alongside, same era.
Survey of distributed decision
Original
Laurent Feuilloley and Pierre Fraigniaud · 2016
Cited alongside, same era.
Molecular graph convolutions: moving beyond fingerprints
Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley · 2016
Cited alongside, same era.
Semi-supervised classification with graph convolutional networks
Original
Thomas N Kipf and Max Welling · 2016
Cited alongside, same era.
Graph convolutional matrix completion
Original
Rianne van den Berg, Thomas N Kipf, and Max Welling · 2017
Cited alongside, same era.

Then

Relational inductive biases, deep learning, and graph networks
Original
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al · 2018
Later among the works it cites.
Deterministic subgraph detection in broadcast congest
Janne H Korhonen and Joel Rybicki · 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.
How powerful are graph neural networks?
Original
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka · 2018
Later among the works it cites.
Mincut pooling in graph neural networks
Original
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi · 2019
Closest in time.
On the equivalence between graph isomorphism testing and function approximation with gnns
Original
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna · 2019
Closest in time.
Understanding the representation power of graph neural networks in learning graph topology
Original
Nima Dehmamy, Albert-László Barabási, and Rose Yu · 2019
Closest in time.
An efficient graph convolutional network technique for the travelling salesman problem
Original
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson · 2019
Closest in time.
Universal invariant and equivariant graph neural networks
Original
Nicolas Keriven and Gabriel Peyré · 2019
Closest in time.
Lanczosnet: Multi-scale deep graph convolutional networks
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel · 2019
Closest in time.
Break the ceiling: Stronger multi-scale deep graph convolutional networks
Original
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup · 2019
Closest in time.
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
Closest in time.
On the turing completeness of modern neural network architectures
Original
Jorge Pérez, Javier Marinković, and Pablo Barceló · 2019
Closest in time.
Approximation ratios of graph neural networks for combinatorial problems
Ryoma Sato, Makoto Yamada, and Hisashi Kashima · 2019
Closest in time.
Discriminative structural graph classification
Original
Younjoo Seo, Andreas Loukas, and Nathanael Peraudin · 2019
Closest in time.
Edgenets:edge varying graph neural networks, 2020
Elvin Isufi, Fernando Gama, and Alejandro Ribeiro · 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…