2021

Equivariant Subgraph Aggregation Networks

Bevilacqua, Beatrice, Frasca, Fabrizio, Lim, Derek et al.

Understand

Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability.

Unfortunately, it was shown that these architectures are limited in their expressive power.
This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue.
Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs.

Built on

A congruence theorem for trees
Paul J Kelly · 1957
Earlier work this paper cites.
The reduction of a graph to canonical form and the algebra which appears therein
Boris Weisfeiler and Andrei Leman · 1968
Earlier work this paper cites.
An optimal lower bound on the number of variables for graph identification
Jin-Yi Cai, Martin Fürer, and Neil Immerman · 1992
Earlier work this paper cites.
Encoding labeled graphs by labeling RAAM
Alessandro Sperduti · 1994
Earlier work this paper cites.
Chemnet: a novel neural network based method for graph/property mapping
Dmitry B Kireev · 1995
Earlier work this paper cites.
Learning task-dependent distributed representations by backpropagation through structure
Christoph Goller and Andreas Kuchler · 1996
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.
Supervised neural networks for the classification of structures
Alessandro Sperduti and Antonina Starita · 1997
Earlier work this paper cites.
On graph kernels: Hardness results and efficient alternatives
Thomas Gärtner, Peter Flach, and Stefan Wrobel · 2003
Earlier work this paper cites.
Strongly regular graphs
Peter J Cameron · 2004
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.
The graph neural network model
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini · 2008
Earlier work this paper cites.
Efficient graphlet kernels for large graph comparison
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt · 2009
Earlier work this paper cites.
Weisfeiler-lehman graph kernels
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt · 2011
Earlier work this paper cites.
Faster canonical forms for strongly regular graphs
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes · 2013
Earlier work this paper cites.
Spectral networks and locally connected networks on graphs
Original
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun · 2013
Earlier work this paper cites.
Batch normalization: Accelerating deep network training by reducing internal covariate shift
Sergey Ioffe and Christian Szegedy · 2015
Earlier work this paper cites.
ZINC 15 – ligand discovery for everyone
Teague Sterling and John J. Irwin · 2015
Earlier work this paper cites.
Diffusion-convolutional neural networks
James Atwood and Don Towsley · 2016
Earlier work this paper cites.
Group equivariant convolutional networks
Taco Cohen and Max Welling · 2016
Earlier work this paper cites.
Propagation kernels: efficient graph kernels from propagated information
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting · 2016
Earlier work this paper cites.
Deep learning with sets and point clouds
Original
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos · 2016
Earlier work this paper cites.
Geometric deep learning: going beyond euclidean data
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst · 2017
Earlier work this paper cites.
Neural message passing for quantum chemistry
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl · 2017
Earlier work this paper cites.
Inductive representation learning on large graphs
William L Hamilton, Rex Ying, and Jure Leskovec · 2017
Earlier work this paper cites.
Semi-supervised classification with graph convolutional networks
Thomas N Kipf and Max Welling · 2017
Earlier work this paper cites.
Pointnet: Deep learning on point sets for 3d classification and segmentation
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas · 2017
Earlier work this paper cites.
Equivariance through parameter-sharing
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos · 2017
Earlier work this paper cites.

Similar

Deep sets
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola · 2017
Cited alongside, same era.
Learning so (3) equivariant representations with spherical cnns
Carlos Esteves, Christine Allen-Blanchette, Ameesh Makadia, and Kostas Daniilidis · 2018
Cited alongside, same era.
Automatic chemical design using a data-driven continuous representation of molecules
Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Aguilera-Iparraguirre, Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik · 2018
Cited alongside, same era.
Junction tree variational autoencoder for molecular graph generation
Wengong Jin, Regina Barzilay, and Tommi Jaakkola · 2018
Cited alongside, same era.
Image generation from scene graphs
Justin Johnson, Agrim Gupta, and Li Fei-Fei · 2018
Cited alongside, same era.
On the generalization of equivariance and convolution in neural networks to the action of compact groups
Risi Kondor and Shubhendu Trivedi · 2018
Cited alongside, same era.
Covariant compositional networks for learning graphs
Original
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi · 2018
Cited alongside, same era.
Representation learning on graphs with jumping knowledge networks
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka · 2018
Cited alongside, same era.
An end-to-end deep learning architecture for graph classification
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen · 2018
Cited alongside, same era.
On the equivalence between graph isomorphism testing and function approximation with gnns
Original
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna · 2019
Cited alongside, same era.
Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh · 2019
Cited alongside, same era.
Graph neural networks for social recommendation
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin · 2019
Cited alongside, same era.

Then

The expressive power of kth-order invariant graph networks, 2020
Floris Geerts · 2020
Later among the works it cites.
Open graph benchmark: Datasets for machine learning on graphs
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec · 2020
Later among the works it cites.
What graph neural networks cannot learn: depth vs width
Andreas Loukas · 2020
Later among the works it cites.
On learning sets of symmetric elements
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya · 2020
Later among the works it cites.
Global attention improves graph networks generalization
Original
Omri Puny, Heli Ben-Hamu, and Yaron Lipman · 2020
Later among the works it cites.
A survey on the expressive power of graph neural networks
Original
Ryoma Sato · 2020
Later among the works it cites.
Graph neural networks in particle physics
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant · 2020
Later among the works it cites.
On the equivalence between positional node embeddings and structural graph representations
Balasubramaniam Srinivasan and Bruno Ribeiro · 2020
Later among the works it cites.
Counting substructures with higher-order graph neural networks: Possibility and impossibility results
Original
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka · 2020
Later among the works it cites.
Building powerful and equivariant graph neural networks with structural message-passing
Clément Vignac, Andreas Loukas, and Pascal Frossard · 2020
Later among the works it cites.
Equivariant networks for hierarchical structures
Renhao Wang, Marjan Albooyeh, and Siamak Ravanbakhsh · 2020
Later among the works it cites.
Graph neural network with automorphic equivalence filters
Original
Fengli Xu, Quanming Yao, Pan Hui, and Yong Li · 2020
Later among the works it cites.
Factorizable graph convolutional networks
Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang · 2020
Later among the works it cites.
Graphsaint: Graph sampling based inductive learning method
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna · 2020
Later among the works it cites.
Expressive power of invariant and equivariant graph neural networks
Waiss Azizian and Marc Lelarge · 2021
Closest in time.
Breaking the limits of message passing graph neural networks
Muhammet Balcilar, Pierre Heroux, Benoit Gauzere, Pascal Vasseur, Sebastien Adam, and Paul Honeine · 2021
Closest in time.
Directional graph networks
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò · 2021
Closest in time.
Partition and code: learning how to compress graphs
Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, and Michael M Bronstein · 2021
Closest in time.
Geometric deep learning: Grids, groups, graphs, geodesics, and gauges
Original
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković · 2021
Closest in time.
Equivariant geometric learning for digital rock physics: estimating formation factor and effective permeability tensors from morse graph
Original
Chen Cai, Nikolaos Vlassis, Lucas Magee, Ran Ma, Zeyu Xiong, Bahador Bahmani, Teng-Fong Wong, Yusu Wang, and WaiChing Sun · 2021
Closest in time.
Learning the relevant substructures for tasks on graph data
Lei Chen, Zhengdao Chen, and Joan Bruna · 2021
Closest in time.
Reconstruction for powerful graph representations
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro · 2021
Closest in time.
Weisfeiler–leman, graph spectra, and random walks
Original
Gaurav Rattan and Tim Seppelt · 2021
Closest in time.
Ego-gnns: Exploiting ego structures in graph neural networks
Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton · 2021
Closest in time.
Random features strengthen graph neural networks
Ryoma Sato, Makoto Yamada, and Hisashi Kashima · 2021
Closest in time.
Autobahn: Automorphism-based graph neural nets
Erik Henning Thiede, Wenda Zhou, and Risi Kondor · 2021
Closest in time.
Identity-aware graph neural networks
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec · 2021
Closest in time.
Improving graph neural network expressivity via subgraph isomorphism counting
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein · 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…