2020

Revisiting Over-smoothing in Deep GCNs

Yang, Chaoqi, Wang, Ruijie, Yao, Shuochao et al.

Understand

Oversmoothing has been assumed to be the major cause of performance drop in deep graph convolutional networks (GCNs).

In this paper, we propose a new view that deep GCNs can actually learn to anti-oversmooth during training.
This work interprets a standard GCN architecture as layerwise integration of a Multi-layer Perceptron (MLP) and graph regularization.
We analyze and conclude that before training, the final representation of a deep GCN does over-smooth, however, it learns anti-oversmoothing during training.

Built on

Spectral graph theory
Fan RK Chung and Fan Chung Graham · 1997
Earlier work this paper cites.
A global geometric framework for nonlinear dimensionality reduction
Joshua B Tenenbaum, Vin De Silva, and John C Langford · 2000
Earlier work this paper cites.
Learning from labeled and unlabeled data with label propagation
Xiaojin Zhu and Zoubin Ghahramani · 2002
Earlier work this paper cites.
Laplacian eigenmaps and spectral techniques for embedding and clustering
Mikhail Belkin and Partha Niyogi · 2002
Earlier work this paper cites.
Laplacian eigenmaps for dimensionality reduction and data representation
Mikhail Belkin and Partha Niyogi · 2003
Earlier work this paper cites.
Kernels and regularization on graphs
Alexander J Smola and Risi Kondor · 2003
Earlier work this paper cites.
Learning on graph with laplacian regularization
Rie K Ando and Tong Zhang · 2007
Earlier work this paper cites.
A tutorial on spectral clustering
Ulrike Von Luxburg · 2007
Earlier work this paper cites.
Deep learning via semi-supervised embedding
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert · 2012
Earlier work this paper cites.
Discrete signal processing on graphs
Aliaksei Sandryhaila and José MF Moura · 2013
Earlier work this paper cites.
Deepwalk: Online learning of social representations
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena · 2014
Earlier work this paper cites.
Discrete signal processing on graphs: Sampling theory
Siheng Chen, Rohan Varma, Aliaksei Sandryhaila, and Jelena Kovačević · 2015
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.
Batch normalization: Accelerating deep network training by reducing internal covariate shift
Original
Sergey Ioffe and Christian Szegedy · 2015
Earlier work this paper cites.

Similar

Semi-supervised classification with graph convolutional networks
Original
Thomas N Kipf and Max Welling · 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.
Revisiting semi-supervised learning with graph embeddings
Original
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov · 2016
Cited alongside, same era.
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2016
Cited alongside, same era.
Graph attention networks
Original
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio · 2017
Cited alongside, same era.
Inductive representation learning on large graphs
Will Hamilton, Zhitao Ying, and Jure Leskovec · 2017
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.
Hierarchical graph representation learning with differentiable pooling
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec · 2018
Cited alongside, same era.
Deep graph infomax
Original
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm · 2018
Cited alongside, same era.
Predict then propagate: Graph neural networks meet personalized pagerank
Original
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann · 2018
Cited alongside, same era.
How powerful are graph neural networks?
Original
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka · 2018
Cited alongside, same era.
Deeper insights into graph convolutional networks for semi-supervised learning
Qimai Li, Zhichao Han, and Xiao-Ming Wu · 2018
Cited alongside, same era.

Then

Spectralnet: Spectral clustering using deep neural networks
Original
Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger · 2018
Later among the works it cites.
Fastgcn: fast learning with graph convolutional networks via importance sampling
Original
Jie Chen, Tengfei Ma, and Cao Xiao · 2018
Later among the works it cites.
Simplifying graph convolutional networks
Original
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger · 2019
Later among the works it cites.
Hyperbolic graph neural networks
Qi Liu, Maximilian Nickel, and Douwe Kiela · 2019
Later among the works it cites.
Graph neural networks exponentially lose expressive power for node classification
Kenta Oono and Taiji Suzuki · 2019
Later among the works it cites.
What graph neural networks cannot learn: depth vs width
Original
Andreas Loukas · 2019
Later among the works it cites.
Understanding the representation power of graph neural networks in learning graph topology
Nima Dehmamy, Albert-László Barabási, and Rose Yu · 2019
Later among the works it cites.
Deepgcns: Can gcns go as deep as cnns?
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem · 2019
Later among the works it cites.
Dropedge: Towards deep graph convolutional networks on node classification
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang · 2019
Later among the works it cites.
Pairnorm: Tackling oversmoothing in gnns
Original
Lingxiao Zhao and Leman Akoglu · 2019
Later among the works it cites.
Deep iterative and adaptive learning for graph neural networks
Original
Yu Chen, Lingfei Wu, and Mohammed J Zaki · 2019
Later among the works it cites.
Revisiting graph neural networks: All we have is low-pass filters
Original
Hoang NT and Takanori Maehara · 2019
Later among the works it cites.
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
Later among the works it cites.

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…