Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
By Michaël Defferrard, Xavier Bresson, Pierre Vandergheynst. 2016
8,688 citations recorded by the source corpus.
In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or words' embedding, represented by graphs. We present a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localized convolutional filters on graphs. Importantly, the proposed technique offers the same linear computational complexity and constant learning complexity as classical CNNs, while being universal to any graph structure. Experiments on MNIST and 20NEWS demonstrate the ability of this novel deep learning system to learn local, stationary, and compositional features on graphs.
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Transportation, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Mohit Bansal
- Percy Liang
- Jianfeng Gao
- Quoc V. Le
- Sergey Levine
- Ruslan Salakhutdinov
- Luke S. Zettlemoyer
In Statistical and Nonlinear Physics
- Jure Leskovec
- William L. Hamilton
- Stephan Günnemann
- Matthias Fey
- Michael M. Bronstein
- Aleksandar Bojchevski
- Yoshua Bengio
- Bryan Perozzi
In Transportation
- Yu Zheng
- Irwin King
- Michael M. Bronstein
- Stephan Günnemann
- Max Welling
- Philip S. Yu
- Qiang Yang
- Petar Velickovic
In Graph Learning
- William L. Hamilton
- Jure Leskovec
- Stephan Günnemann
- Matthias Fey
- Michael M. Bronstein
- Rex Ying
- Aleksandar Bojchevski
- Marinka Zitnik
Citations in the corpus
- Semi-Supervised Classification with Graph Convolutional Networks (2016, methodology): “Defferrard et al. (2016) use this K -localized convolution to define a convolutional neural network on graphs.”
- Graph Attention Networks (2017, methodology): “We also directly compare our model against GCNs (Kipf & Welling, 2017), as well as graph convolutional models utilising higher-order Chebyshev filters (Defferrard et al., 2016), and the MoNet model presented in Monti et al.”
- Inductive Representation Learning on Large Graphs (2017, neutral): “The majority of these methods do not scale to large graphs or are designed for whole-graph classification (or both) [4, 9, 8, 24].”
- Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “A key criticism of spectral approaches such as [11, 18, 13] is the fact that the spectral definition of convolution is dependent on the Fourier basis (Laplacian eigenbasis), which in turn is domain-dependent.”
- Neural Logic Machines (2019, background): “Graph convolution networks (GCNs) (Bruna et al., 2014; Li et al., 2016; Defferrard et al., 2016; Kipf & Welling, 2017) is a family of neural architectures working on graphs.”
- Knowledge Graph Convolutional Networks for Recommender Systems (2019, methodology): “[4] approximate the convolutional filters by Chebyshev expansion of the graph Laplacian, and Kipf et al.”
- Neural Message Passing for Quantum Chemistry (2017, background): “Laplacian Based Methods, Bruna et al. (2013); Defferrard et al. (2016); Kipf & Welling (2016) These methods generalize the notion of the convolution operation typically applied to image datasets to an operation that operates on an arbitrary graph G with a real valued adjacency matrix A.”
- E(n) Equivariant Graph Neural Networks (2021, methodology): “Horie et al. (2020) proposes a set of isometric invariant and equivairant transformations for Graph Neural Networks.”
- Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018, background): “Following on this work, a number of authors proposed improvements, extensions, and approximations of these spectral convolutions [6, 10, 11, 13, 18, 21, 24, 29, 31], leading to new state-of-the-art results on benchmarks such as node classification, link prediction, as well as recommender system task”
- Graph Convolutional Networks for Text Classification (2018, background): “Some recent studies explored graph neural networks for text classification (Henaff, Bruna, and LeCun 2015; Defferrard, Bresson, and Vandergheynst 2016; Kipf and Welling 2017; Peng et al. 2018; Zhang, Liu, and Song 2018).”
- Fast Graph Representation Learning with PyTorch Geometric (2019, background): “(2019), the spectral chebyshev and ARMA filter convolutions (Defferrard et al., 2016; Bianchi et al., 2019), GraphSAGE (Hamilton et al.”
- Attacking Graph-based Classification via Manipulating the Graph Structure (2019, background): “the same label have similar feature vectors and nodes having different labels have distinct feature vectors. For instance, Graph Convolutional Network (GCN) [38] leverages spectral graph convolutions [18] in a neural network to learn feature vectors, and adopts a logistic regression classifier in th”
- Auto-GNN: Neural architecture search of graph neural networks (2019, methodology): “A wide variety of GNNs have been proposed to learn the node representation effectively, e.g., recursive neural networks [1, 2], graph convolutional networks [9, 30–32, 37 ] and Neural Architecture Search.”
- Relational inductive biases, deep learning, and graph networks (2018, background): “(2017) introduced the message-passing neural network (MPNN), which unified various graph neural network and graph convolutional network approaches (Monti et al., 2017; Bruna et al., 2014; Henaff et al., 2015; Defferrard et al., 2016; Kipf and Welling, 2017; Bronstein et al., 2017) by analogy to mess”
- Flexible Neural Representation for Physics Prediction (2018, background): “[4], which in turn use ideas from graph-based neural networks [39, 44, 9, 30, 22, 14, 13, 24, 8, 40].”
- Differentiable Physics-informed Graph Networks (2019, background): “One branch of these studies is a spectral approach to aggregate locally connected attributes (Bruna et al., 2014; Defferrard et al., 2016; Kipf & Welling, 2017) and another branch is a spatial approach (or message passing method) (Gilmer et al., 2017; Monti et al., 2017; Hamilton et al., 2017).”
- Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, background): “For each graph, UGRAPHEMB first generates a set of node embeddings using neighbor aggregation methods based on Graph Convolutional Networks (GCN) (Kipf & Welling, 2016a), which are permutation-invariant and inductive.”
- How Powerful are Graph Neural Networks? (2018, methodology): “Many GNN variants with different neighborhood aggregation and graph-level pooling schemes have been proposed (Scarselli et al., 2009b; Battaglia et al., 2016; Defferrard et al., 2016; Duvenaud et al., 2015; Hamilton et al., 2017a; Kearnes et al., 2016; Kipf & Welling, 2017; Li et al., 2016; Velickov”
- Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “network (GNN) models have been proposed in recent years, including methods inspired by convolutional neural networks [5, 8, 11, 16, 21, 24, 29, 36], recurrent neural networks [25], recursive neural networks [1, 30] and loopy belief propagation [7].”