Elamur Research
☰
home / papers / 2016 / Semi-Supervised Classification with Graph Convolutional Networks

Semi-Supervised Classification with Graph Convolutional Networks

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1609.02907

Summary

The paper addresses node classification when only a few nodes in a graph have labels, for example documents in a citation network. Classic graph-based semi-supervised methods add a Laplacian smoothing penalty to the loss, which assumes that linked nodes share a class. Kipf and Welling take a different route. They give a neural network both the node features and the adjacency matrix, and they train it only on the labelled nodes. To derive their Graph Convolutional Network (GCN) layer, they cut the Chebyshev expansion of spectral graph filters down to first order, fix the eigenvalue scale and tie the two remaining parameters. They then add self-loops and normalise symmetrically, which they call a "renormalization trick", to keep training stable. Each layer becomes a sparse-dense matrix product, so compute and memory grow linearly with the number of edges. The authors tested a two-layer GCN on the Cora, Citeseer and Pubmed citation graphs and on a knowledge-graph dataset. It beat earlier approaches in both accuracy and wall-clock time. This simple propagation rule became a standard baseline for graph neural networks.

Key points

  • Layer rule: H⁽ˡ⁺¹⁾ = σ(D̃^-½ à D̃^-½ H⁽ˡ⁾ W⁽ˡ⁾) with à = A + I_N. The classifier applies softmax to ·ReLU(ÂXW⁽⁰⁾)·W⁽¹⁾, and the cross-entropy loss is computed only over labelled nodes.
  • Cost is O(|E|CHF). Training uses full-batch gradient descent with dropout, implemented in TensorFlow; code is at github.com/tkipf/gcn.
  • Depth study (5-fold cross-validation on Cora, Citeseer and Pubmed): 2–3 layers work best. Without residual connections, models deeper than about 7 layers become hard to train.
  • On Zachary's karate club (34 nodes, 154 edges), an untrained 3-layer GCN with random weights gives embeddings comparable to DeepWalk. Trained with one label per class (4 labels in total) for 300 Adam iterations, it separates the communities linearly.
  • The authors also give an alternative reading of the propagation rule as a differentiable form of the Weisfeiler-Lehman algorithm.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Other

Cited by

1378 papers of our library cite it (of the 140673 whose bibliographies we read); 30 of them have a page here, 1348 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1609.02907 · arXiv 1609.02907

@misc{kipf2016semi,
  title = {{Semi-Supervised Classification with Graph Convolutional Networks}},
  author = {Kipf, Thomas N. and Welling, Max},
  year = {2016},
  doi = {10.48550/arxiv.1609.02907},
  eprint = {1609.02907},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1609.02907}
}

References

32 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Martı́n Abadi et al. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. find
  2. James Atwood and Don Towsley. Diffusion-convolutional neural networks. In Advances in neural information processing systems (NIPS), 2016. find
  3. Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research (JMLR), 7(Nov):2399–2434, 2006. find
  4. Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On modularity clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188, 2008. find
  5. Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations (ICLR), 2014. find
  6. Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka Jr, and Tom M. Mitchell. Toward an architecture for never-ending language learning. In AAAI, volume 5, pp. 3, 2010. find
  7. Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems (NIPS), 2016. find our card
  8. Brendan L. Douglas. The Weisfeiler-Lehman method and graph isomorphism testing. arXiv preprint arXiv:1101.5211, 2011. — [arXiv:1101.5211](https://arxiv.org/abs/1101.5211) find
  9. David K. Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems (NIPS), pp. 2224–2232, 2015. find
  10. Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, volume 9, pp. 249–256, 2010. find
  11. Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks., volume 2, pp. 729–734. find
  12. Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016. find
  13. David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011. find
  14. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. find
  15. Thorsten Joachims. Transductive inference for text classification using support vector machines. In International Conference on Machine Learning (ICML), volume 99, pp. 200–209, 1999. find
  16. Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015. find
  17. Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016. find
  18. Qing Lu and Lise Getoor. Link-based classification. In International Conference on Machine Learning (ICML), volume 3, pp. 496–503, 2003. find
  19. Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research (JMLR), 9(Nov):2579–2605, 2008. find
  20. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems (NIPS), pp. 3111–3119, 2013. find
  21. Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning (ICML), 2016. find
  22. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701–710. ACM, 2014. find
  23. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. find
  24. Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine, 29(3):93, 2008. find
  25. Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research (JMLR), 15(1):1929–1958, 2014. find
  26. Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067–1077. ACM, 2015. find
  27. Boris Weisfeiler and A. A. Lehmann. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, 2(9):12–16, 1968. find
  28. Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi-supervised embedding. In Neural Networks: Tricks of the Trade, pp. 639–655. Springer, 2012. find
  29. Zhilin Yang, William Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning (ICML), 2016. find
  30. Wayne W. Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research, pp. 452–473, 1977. find
  31. Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in neural information processing systems (NIPS), volume 16, pp. 321–328, 2004. find
  32. Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In International Conference on Machine Learning (ICML), volume 3, pp. 912–919, 2003. find