2020

Unifying Graph Convolutional Neural Networks and Label Propagation

Wang, Hongwei, Leskovec, Jure

Understand

Label Propagation (LPA) and Graph Convolutional Neural Networks (GCN) are both message passing algorithms on graphs.

Both solve the task of node classification but LPA propagates node label information across the edges of the graph, while GCN propagates and transforms node feature information.
However, while conceptually similar, theoretical relation between LPA and GCN has not yet been investigated.
Here we study the relationship between LPA and GCN in terms of two aspects: (1) feature/label smoothing where we analyze how the feature/label of one node is spread over its neighbors; And, (2) feature/label influence of how much the initial feature/label of one node influences the final feature/label of another node.

Built on

An information flow model for conflict and fission in small groups
Zachary, W. W · 1977
Earlier work this paper cites.
Nonlinear dimensionality reduction by locally linear embedding
Roweis, S. T. and Saul, L. K · 2000
Earlier work this paper cites.
Semi-supervised learning using gaussian fields and harmonic functions
Zhu, X., Ghahramani, Z., and Lafferty, J. D · 2003
Earlier work this paper cites.
Learning with local and global consistency
Zhou, D., Bousquet, O., Lal, T. N., Weston, J., and Schölkopf, B · 2004
Earlier work this paper cites.
Semi-supervised learning with graphs
Zhu, X., Lafferty, J., and Rosenfeld, R · 2005
Earlier work this paper cites.
Hyperparameter learning for graph based semi-supervised learning algorithms
Zhang, X. and Lee, W. S · 2007
Earlier work this paper cites.
Mlle: Modified locally linear embedding using multiple weights
Zhang, Z. and Wang, J · 2007
Earlier work this paper cites.
Collective classification in network data
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T · 2008
Earlier work this paper cites.
Label propagation through linear neighborhoods
Wang, F. and Zhang, C · 2008
Earlier work this paper cites.
Sparsity induced similarity measure for label propagation
Hong, C., Liu, Z., and Yang, J · 2009
Earlier work this paper cites.

Similar

Understanding the difficulty of training deep feedforward neural networks
Glorot, X. and Bengio, Y · 2010
Cited alongside, same era.
An iterative locally linear embedding algorithm
Kong, D., Ding, C., Huang, H., and Nie, F · 2012
Cited alongside, same era.
Manifold-based similarity adaptation for label propagation
Karasuyama, M. and Mamitsuka, H · 2013
Cited alongside, same era.
Dropout: a simple way to prevent neural networks from overfitting
Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R · 2014
Cited alongside, same era.
Adam: A method for stochastic optimization
Kingma, D. P. and Ba, J · 2015
Cited alongside, same era.
Label propagation via teaching-to-learn and learning-to-teach
Gong, C., Tao, D., Liu, W., Liu, L., and Yang, J · 2017
Cited alongside, same era.
Inductive representation learning on large graphs
Hamilton, W., Ying, Z., and Leskovec, J · 2017
Cited alongside, same era.
Semi-supervised classification with graph convolutional networks
Kipf, T. N. and Welling, M · 2017
Cited alongside, same era.
Understanding black-box predictions via influence functions
Koh, P. W. and Liang, P · 2017
Cited alongside, same era.
Learning to propagate labels: Transductive propagation network for few-shot learning
Liu, Y., Lee, J., Park, M., Kim, S., Yang, E., Hwang, S. J., and Yang, Y
Cited in the paper.
Geniepath: Graph neural networks with adaptive receptive paths
Liu, Z., Chen, C., Li, L., Zhou, J., Li, X., Song, L., and Qi, Y
Cited in the paper.

Then

Deeper insights into graph convolutional networks for semi-supervised learning
Li, Q., Han, Z., and Wu, X.-M · 2018
Later among the works it cites.
Pitfalls of graph neural network evaluation
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S · 2018
Later among the works it cites.
Attention-based graph neural network for semi-supervised learning
Original
Thekumparampil, K. K., Wang, C., Oh, S., and Li, L.-J · 2018
Later among the works it cites.
Graph attention networks
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y · 2018
Later among the works it cites.
Representation learning on graphs with jumping knowledge networks
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S · 2018
Later among the works it cites.
Gaan: Gated attention networks for learning on large and spatiotemporal graphs
Original
Zhang, J., Shi, X., Xie, J., Ma, H., King, I., and Yeung, D.-Y · 2018
Later among the works it cites.
Lanczosnet: Multi-scale deep graph convolutional networks
Liao, R., Zhao, Z., Urtasun, R., and Zemel, R. S · 2019
Later among the works it cites.
Gmnn: Graph markov neural networks
Qu, M., Bengio, Y., and Tang, J · 2019
Later among the works it cites.
How powerful are graph neural networks?
Xu, K., Hu, W., Leskovec, J., and Jegelka, S · 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…