Graph-based Neural Networks

This page is to summarize important materials about graph-based neural networks and relational networks. If I miss some recent works or anyone wants to recommend other references, please let me know.

Background

(You can find many materials for deep neural networks in other places. Here, I mainly cover materials about graphs.)

• Basic Graph Theory by Xavier Bresson, See Lecture 3 and 16
• Spectral Graph Theory by Fan Chung
• Graph Signal Processing GSP by Ortega et al.
  • This paper provide an overview of core ideas in GSP and their connection to conventional digital signal processing.
  • Signal processing is required to understand the convolution in the spectral domain.
• Keywords : graph theory, spectral graph theory, discrete Fourier transform (DFT)
• A tutorial on Spectral Clustering by Ulrike Von Luxeborg (Statistics and Computing 2007)

List of Related Works

• Early works using graph structure

  • A new model for learning in graph domains
    • M. Gori, G. Monfardini, F. Scarselli, IJCNN 2005
    • First attempts to generalize neural networks to graphs
  • The graph neural network model
    • F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, IEEE Trans. Neural Networks 2009
  • These works optimized over the parameterized steady state of some diffusion process (or random walk) on the graph.

• Review paper (highly recommend)

  • Geometric deep learning: going beyond Euclidean data
    • Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, Pierre Vandergheynst, IEEE Signal Processing Magazine 2017
    • First review paper of geometric deep learning

• Graph Convolutional Networks (GCNs)

  • Spectral Networks and Locally Connected Networks on Graphs
    • Joan Bruna, Wojciech Zaremba, Arthur Szlam, Yann LeCun, ICLR 2014
    • First formulation of CNNs on graphs in the spectral domain
  • Deep Convolutional Networks on Graph-Structured Data
    • Mikael Henaff, Joan Bruna, Yann LeCun, 2015
    • Spatial localization of smooth filters in the frequency domain
  • Convolutional Networks on Graphs for Learning Molecular Fingerprints
    • David Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, Ryan P. Adams, NIPS 2015
  • Gated Graph Sequence Neural Networks
    • Yujia Li, Daniel Tarlow, Marc Brockschmidt, Richard Zemel, ICLR 2016
    • Sliding a filter on the vertices as conventional CNNs, not spectral filtering
  • Learning Convolutional Neural Networks for Graphs
    • Mathias Niepert, Mohamed Ahmed, Konstantin Kutzkov, ICML 2016
  • Generalizing the Convolution Operator to extend CNNs to Irregular Domains
    • Jean-Charles Vialatte, Vincent Gripon, Grégoire Mercier, arXiv 2016
    • Generalize CNNs to irregular domains using weight sharing and graph-based operators
  • Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering , [PyTorch Code] [TF Code]
    • Michaël Defferrard, Xavier Bresson, Pierre Vandergheynst, NIPS 2016
    • Spectral CNN with Chebychev polynomial filters (ChebNet)
  • Learning Shape Correspondence with Anisotropic Convolutional Neural Networks
    • Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Michael M. Bronstein, NIPS 2016
    • Anisotropic CNN framework
  • Diffusion-convolutional neural network
    • James Atwood and Don Towsley, NIPS 2016
  • Semi-Supervised Classification with Graph Convolutional Networks , [Code], [Blog]
    • Thomas N. Kipf, Max Welling, ICLR 2017
    • Graph Convolutional Networks (GCN) framework, a simplification of ChebNet
  • Geometric Deep Learning on Graphs and Manifolds using Mixture Model CNNs
    • Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, Michael M. Bronstein, CVPR 2017
    • MoNets
  • Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks, [Code]
    • Federico Monti, Michael M. Bronstein, Xavier Bresson, NIPS 2017
    • Recommendation systems
  • Fast GCN: Fast learning with graph convolutional Networks with Importance Sampling
    • Jie Chen, Tengfei Ma, Cao Xiao, ICLR 2018 (IBM Research)
  • CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters
    • Ron Levie, Federico Monti, Xavier Bresson, Michael M. Bronstein, arXiv 2017
    • Spectral CNN with complex rational filters (CayleyNet)
  • Residual Gated Graph ConvNets
    • Xavier Bresson, Thomas Laurent, arXiv 2017

• Relational Networks (RNs), Relational Reasoning, Interactions

  • Interaction networks for learning about objects, relations and physics
    • Peter W. Battaglia, Razvan Pascanu, Matthew Lai, Danilo Rezende, Koray Kavukcuoglu, NIPS 2016
  • A simple neural network module for relational reasoning, [Deepmind Article], [Code]
    • Adam Santoro, David Raposo, David G.T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, Timothy Lillicrap, arXiv 2017
    • Consider all possible pairs
  • Neural Message Passing for Quantum Chemistry
    • Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, George E. Dahl, ICML 2017
  • Pointnet: Deep learning on point sets for 3d classification and segmentation
    • Charles R. Qi, Hao Su, Kaichun Mo, Leonidas J. Guibas, CVPR2017
  • SchNet: A continuous-filter convolutional neural network for modeling quantum interactions
    • Kristof T. Schütt, Pieter-Jan Kindermans, Huziel E. Sauceda, Stefan Chmiela, Alexandre Tkatchenko, Klaus-Robert Müller, NIPS 2017
  • VAIN: Attentional Multi-agent Predictive Modeling
    • Yedid Hoshen, NIPS 2017
  • Inductive Representation Learning on Large Graphs
    • William L. Hamilton, Rex Ying, Jure Leskovec, NIPS 2017
  • Modeling Relational Data with Graph Convolutional Networks
    • Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, Max Welling, arXiv 2017
  • Graph Attention Networks , [Code]
    • Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, Yoshua Bengio, ICLR 2018

• Graph Auto-Encoder (GAE)

  • Variational Graph Auto-Encoders, [Code]
    • Thomas N. Kipf, Max Welling, NIPS Workshop on Bayesian Deep Learning 2016
    • Question: Why the adjacency matrix is reconstructed rather than the feature matrix?
  • Modeling Relational Data with Graph Convolutional Networks
    • Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, Max Welling, 2017
  • Graph Convolutional Matrix Completion
    • Rianne van den Berg, Thomas N. Kipf, Max Welling, 2017

• Other Applications using Graph-based Neural Networks

  • Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting, [Code]
    • Yaguang Li, Rose Yu, Cyrus Shahabi, Yan Liu, ICLR 2018
  • Automatically Inferring Data Quality for Spatiotemporal Forecasting
    • Sungyong Seo, Arash Mohegh, George Ban-Weiss, Yan Liu, ICLR 2018

• Some Recent Graph Kerenel Based Approaches

  • Deep Graph Kernels KDD 2015
    • Pinar Yanardag, S.V.N. Viswanathan, KDD 2015 (University of California)

• Miscallenous developements in graphs in completely orthogonal Directions

  • Graphs, mergeons and so on
    • Justin Eldridge, Mikhail Belkin, Yusu Wang, NIPS 2016 (Ohio State University)
  • Hunt for the Unique, Stable Sparse and Fast Feature Learning on Graphs
    • S. Verma and Zhi-Li Zhang, NIPS 2017 (University of Minnesota)
  • Wavelets on Graphs via Spectral Graph Theory Applied and Computational Harmonic Analysis
    • D. Hammond, P. Vandergheynst, and R. Gribonval.,  Applied and Computational Harmonic Analysis 2009

Tutorials or Workshops

• IPAM18 Workshop, New Deep Learning Techniques
• NIPS17 Tutorial, Geometric Deep Learning on Graphs and Manifolds
• CVPR17 Tutorial, Geometric Deep Learning on Graphs

Useful Resources

• Kipf's blog
• Geometric Deep Learning highly recommended
• CVPR17 tutorial, Geometric and Semantic 3D Reconstruction, 240MB
• How do I generalize convolution of neural networks to graphs?, Defferrard's answers in Quora
• PointNet

List of Researchers

• Thomas Kipf, University of Amsterdam
• Joan Bruna, NYU
• Michaël Defferrard, EPFL
• Xavier Bresson, NTU
• Federico Monti, Università della Svizzera Italiana
• Michael M. Bronstein, Università della Svizzera Italiana