2018

Invariant and Equivariant Graph Networks

Maron, Haggai, Ben-Hamu, Heli, Shamir, Nadav et al.

Understand

Invariant and equivariant networks have been successfully used for learning images, sets, point clouds, and graphs.

A basic challenge in developing such networks is finding the maximal collection of invariant and equivariant linear layers.
Although this question is answered for the first three examples (for popular transformations, at-least), a full characterization of invariant and equivariant linear layers for graphs is not known.
In this paper we provide a characterization of all permutation invariant and equivariant linear layers for (hyper-)graph data, and show that their dimension, in case of edge-value graph data, is 2 and 15, respectively.

Built on

Learning Convolutional Neural Networks for Graphs
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov · 1938
Earlier work this paper cites.
Backpropagation applied to handwritten zip code recognition
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel · 1989
Earlier work this paper cites.
Steerable CNNs
Original
Taco S. Cohen and Max Welling · 1990
Earlier work this paper cites.
Approximation capabilities of multilayer feedforward networks
Kurt Hornik · 1991
Earlier work this paper cites.
A new model for earning in raph 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.
Graph kernels
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt · 2010
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.
Imagenet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton · 2012
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.
Representation theory: a first course , volume 129
William Fulton and Joe Harris · 2013
Earlier work this paper cites.
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
Earlier work this paper cites.
Deep Convolutional Networks on Graph-Structured Data
Original
Mikael Henaff, Joan Bruna, and Yann LeCun · 2015
Earlier work this paper cites.

Similar

Gated Graph Sequence Neural Networks
Original
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel · 2015
Cited alongside, same era.
Deep Graph Kernels
Pinar Yanardag and S.V.N. Vishwanathan · 2015
Cited alongside, same era.
Tensorflow: a system for large-scale machine learning
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al · 2016
Cited alongside, same era.
Diffusion-convolutional neural networks
James Atwood and Don Towsley · 2016
Cited alongside, same era.
Convolutional neural networks on graphs with fast localized spectral filtering
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst · 2016
Cited alongside, same era.
Semi-supervised classification with graph convolutional networks
Original
Thomas N Kipf and Max Welling · 2016
Cited alongside, same era.
Propagation kernels: efficient graph kernels from propagated information
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting · 2016
Cited alongside, same era.
Neural message passing for quantum chemistry
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl · 2017
Cited alongside, same era.
Inductive representation learning on large graphs
Will Hamilton, Zhitao Ying, and Jure Leskovec · 2017
Cited alongside, same era.
CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters
Original
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein · 2017
Cited alongside, same era.
Geometric deep learning on graphs and manifolds using mixture model cnns
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein · 2017
Cited alongside, same era.
Pointnet: Deep learning on point sets for 3d classification and segmentation
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas · 2017
Cited alongside, same era.

Then

Dynamic edge-conditioned filters in convolutional neural networks on graphs
Martin Simonovsky and Nikos Komodakis · 2017
Later among the works it cites.
Graph Attention Networks
Original
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio · 2017
Later among the works it cites.
Hunt for the unique, stable, sparse and fast feature learning on graphs
Saurabh Verma and Zhi-Li Zhang · 2017
Later among the works it cites.
Deep sets
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola · 2017
Later among the works it cites.
Spherical cnns
Original
Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling · 2018
Closest in time.
Deep models of interactions across sets
Jason S. Hartford, Devon R. Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh · 2018
Closest in time.
Anonymous walk embeddings
Original
Sergey Ivanov and Evgeny Burnaev · 2018
Closest in time.
On the generalization of equivariance and convolution in neural networks to the action of compact groups
Original
Risi Kondor and Shubhendu Trivedi · 2018
Closest in time.
Covariant compositional networks for learning graphs
Original
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi · 2018
Closest in time.
3D Steerable CNNs: Learning Rotationally Equivariant Features in Volumetric Data
Original
Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco Cohen · 2018
Closest in time.
Universal approximations of invariant maps by neural networks
Original
Dmitry Yarotsky · 2018
Closest in time.
Hierarchical Graph Representation Learning with Differentiable Pooling
Original
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. , and Jure Leskovec · 2018
Closest in time.
An end-to-end deep learning architecture for graph classification
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen · 2018
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…