2019

Stability and Generalization of Graph Convolutional Neural Networks

Verma, Saurabh, Zhang, Zhi-Li

Understand

Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets.

Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties.
In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting.
In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter.

Built on

Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. 1989 · 1989
Earlier work this paper cites.
Probably approximately correct learning
David Haussler. 1990 · 1990
Earlier work this paper cites.
Interlacing eigenvalues and graphs
Willem H Haemers. 1995 · 1995
Earlier work this paper cites.
Diffusion-convolutional neural networks. In Advances in Neural Information Processing Systems . 1993–2001
James Atwood and Don Towsley. 2016 · 2001
Earlier work this paper cites.
Stability and generalization
Olivier Bousquet and André Elisseeff. 2002 · 2002
Earlier work this paper cites.
Regularization and semi-supervised learning on large graphs. In International Conference on Computational Learning Theory . Springer, 624–638
Mikhail Belkin, Irina Matveeva, and Partha Niyogi. 2004 · 2004
Earlier work this paper cites.
Stability and generalization of bipartite ranking algorithms. In International Conference on Computational Learning Theory . Springer, 32–47
Shivani Agarwal and Partha Niyogi. 2005 · 2005
Earlier work this paper cites.
Stability of randomized learning algorithms
Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. 2005 · 2005
Earlier work this paper cites.
Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization
Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. 2006 · 2006
Earlier work this paper cites.
Learning on graph with Laplacian regularization. In Advances in neural information processing systems . 25–32
Rie K Ando and Tong Zhang. 2007 · 2007
Earlier work this paper cites.
Stability of transductive regression algorithms. In Proceedings of the 25th international conference on Machine learning . ACM, 176–183
Corinna Cortes, Mehryar Mohri, Dmitry Pechyony, and Ashish Rastogi. 2008 · 2008
Earlier work this paper cites.
Spectra of principal submatrices of nonnegative matrices
Thomas J Laffey and Helena Šmigoc. 2008 · 2008
Earlier work this paper cites.
Generalization bounds for ranking algorithms via algorithmic stability
Shivani Agarwal and Partha Niyogi. 2009 · 2009
Earlier work this paper cites.
Shallow vs. deep sum-product networks. In Advances in Neural Information Processing Systems . 666–674
Olivier Delalleau and Yoshua Bengio. 2011 · 2011
Earlier work this paper cites.
Spectral networks and locally connected networks on graphs
Original
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. 2013 · 2013
Earlier work this paper cites.
The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2013 · 2013
Earlier work this paper cites.

Similar

Manifold-preserving graph reduction for sparse semi-supervised learning
Shiliang Sun, Zakria Hussain, and John Shawe-Taylor. 2014 · 2014
Cited alongside, same era.
Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems . 2224–2232
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. 2015 · 2015
Cited alongside, same era.
Train faster, generalize better: Stability of stochastic gradient descent
Original
Moritz Hardt, Benjamin Recht, and Yoram Singer. 2015 · 2015
Cited alongside, same era.
Convolutional rectifier networks as generalized tensor decompositions. In International Conference on Machine Learning . 955–963
Nadav Cohen and Amnon Shashua. 2016 · 2016
Cited alongside, same era.
Discriminative embeddings of latent variable models for structured data. In International Conference on Machine Learning . 2702–2711
Hanjun Dai, Bo Dai, and Le Song. 2016 · 2016
Cited alongside, same era.
Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems . 3837–3845
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016 · 2016
Cited alongside, same era.
The power of depth for feedforward neural networks. In Conference on Learning Theory . 907–940
Ronen Eldan and Ohad Shamir. 2016 · 2016
Cited alongside, same era.
Semi-supervised classification with graph convolutional networks
Original
Thomas N Kipf and Max Welling. 2016a · 2016
Cited alongside, same era.
Variational graph auto-encoders
Original
Thomas N Kipf and Max Welling. 2016b · 2016
Cited alongside, same era.
Deep vs. shallow networks: An approximation theory perspective
Hrushikesh N Mhaskar and Tomaso Poggio. 2016 · 2016
Cited alongside, same era.
Learning convolutional neural networks for graphs. In Proceedings of the 33rd annual international conference on machine learning. ACM
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016 · 2016
Cited alongside, same era.
Benefits of depth in neural networks
Original
Matus Telgarsky. 2016 · 2016
Cited alongside, same era.

Then

Generalization in deep learning
Original
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. 2017 · 2017
Later among the works it cites.
Deriving neural architectures from sequence and graph kernels
Original
Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. 2017 · 2017
Later among the works it cites.
Exploring generalization in deep learning. In Advances in Neural Information Processing Systems . 5947–5956
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. 2017 · 2017
Later among the works it cites.
Unifying local and non-local signal processing with graph CNNs
Original
Gilles Puy, Srdan Kitic, and Patrick Pérez. 2017 · 2017
Later among the works it cites.
3d graph neural networks for rgbd semantic segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition . 5199–5208
Xiaojuan Qi, Renjie Liao, Jiaya Jia, Sanja Fidler, and Raquel Urtasun. 2017 · 2017
Later among the works it cites.
Robust spatial filtering with graph convolutional neural networks
Felipe Petroski Such, Shagan Sah, Miguel Alexander Dominguez, Suhas Pillai, Chao Zhang, Andrew Michael, Nathan D Cahill, and Raymond Ptucha. 2017 · 2017
Later among the works it cites.
Quantum Walk Neural Networks for Graph-Structured Data. In International Workshop on Complex Networks and their Applications . Springer, 182–193
Stefan Dernbach, Arman Mohseni-Kabir, Siddharth Pal, and Don Towsley. 2018 · 2018
Later among the works it cites.
Covariant Compositional Networks For Learning Graphs
Original
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. 2018 · 2018
Later among the works it cites.
Adaptive Graph Convolutional Neural Networks
Original
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. 2018 · 2018
Later among the works it cites.
Modeling relational data with graph convolutional networks. In European Semantic Web Conference . Springer, 593–607
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018 · 2018
Later among the works it cites.
Exploring graph-structured passage representation for multi-hop reading comprehension with graph neural networks
Original
Linfeng Song, Zhiguo Wang, Mo Yu, Yue Zhang, Radu Florian, and Daniel Gildea. 2018 · 2018
Later among the works it cites.
Graph Classification with 2D Convolutional Neural Networks
Antoine J-P Tixier, Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2018 · 2018
Later among the works it cites.
Deep graph infomax
Original
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2018 · 2018
Later among the works it cites.
Graph Capsule Convolutional Neural Networks
Original
Saurabh Verma and Zhi-Li Zhang. 2018 · 2018
Later among the works it cites.
How Powerful are Graph Neural Networks?
Original
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018 · 2018
Later among the works it cites.
Quantum-based subgraph convolutional neural networks
Zhihong Zhang, Dongdong Chen, Jianjia Wang, Lu Bai, and Edwin R Hancock. 2019 · 2019
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…