Elamur Research
☰
home / papers / 2018 / How Powerful are Graph Neural Networks?

How Powerful are Graph Neural 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/1810.00826

Summary

Graph Neural Networks (GNNs) work by repeatedly gathering and transforming information from each node's neighbours. They have done well on many node- and graph-level tasks, but before this paper there was little theory on which graph structures they can and cannot tell apart. Xu, Hu, Leskovec and Jegelka address this by modelling each node's neighbourhood as a multiset of feature vectors and treating aggregation as a function on those multisets. They prove that no neighbourhood-aggregation GNN can separate more graphs than the Weisfeiler-Lehman (WL) isomorphism test. A GNN reaches that limit only when both its neighbour aggregation and its graph-level readout are injective. Popular designs such as GCN (mean pooling) and GraphSAGE (max pooling) do not meet this condition, so they miss some simple structural differences. The authors then propose the Graph Isomorphism Network (GIN), which uses sum aggregation followed by an MLP and is provably as powerful as WL. In experiments on standard graph classification benchmarks, GIN fits the training data almost perfectly while weaker variants underfit, and it reaches state-of-the-art test accuracy. The work turned GNN design from trial and error into a question of formal expressiveness.

Key points

  • Main theorem: a GNN can be at most as discriminative as the 1-dimensional WL test. It matches WL when neighbour aggregation, the update (combine) step and the READOUT function are all injective over multisets.
  • Each aggregator keeps a different amount of information. Sum can encode the full multiset. Mean keeps only the proportions of each neighbour feature, so a neighbourhood and a scaled copy of it look the same. Max keeps only the set of distinct elements. A single ReLU layer followed by summation is also not enough: the multisets {1,1,1,1,1} and {2,3} receive the same output.
  • GIN updates a node with an MLP applied to (1+ε)·(the node's own feature) plus the sum of its neighbours' features. With an irrational ε this pairing of a node and its neighbourhood is provably injective.
  • Bioinformatics benchmarks: MUTAG (188 nitro compounds), PROTEINS, PTC (344 compounds) and NCI1. Social-network benchmarks: IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDIT-MULTI5K and COLLAB.
  • The excerpt you sent omits the middle of the paper, so the accuracy tables were not available. The summary therefore leaves out exact scores and relies on the paper's claim of state-of-the-art results.

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

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

Cite

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

@misc{xu2018how,
  title = {{How Powerful are Graph Neural Networks?}},
  author = {Xu, Keyulu and Hu, Weihua and Leskovec, Jure and Jegelka, Stefanie},
  year = {2018},
  doi = {10.48550/arxiv.1810.00826},
  eprint = {1810.00826},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1810.00826}
}

References

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

  1. James Atwood and Don Towsley. Diffusion-convolutional neural networks. In Advances in Neural Information Processing Systems (NIPS), pp. 1993–2001, 2016. find
  2. László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 684–697. ACM, 2016. find
  3. László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In Foundations of Computer Science, 1979., 20th Annual Symposium on, pp. 39–46. find
  4. Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems (NIPS), pp. 4502–4510, 2016. find
  5. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992. find
  6. Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):27, 2011. 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), pp. 3844–3852, 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. pp. 2224–2232, 2015. find
  10. Sergei Evdokimov and Ilia Ponomarenko. Isomorphism of coloured graphs with slowly increasing multiplicity of jordan blocks. Combinatorica, 19(3):321–333, 1999. find
  11. Michael R Garey. A guide to the theory of np-completeness. Computers and intractability, 1979. find
  12. Michael R Garey and David S Johnson. Computers and intractability, volume 29. wh freeman New York, 2002. find
  13. Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), pp. 1273–1272, 2017. find our card
  14. William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NIPS), pp. 1025–1035, 2017a. find our card
  15. William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3):52–74, 2017b. find
  16. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251–257, 1991. find
  17. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366, 1989. find
  18. Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), pp. 448–456, 2015. find
  19. Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference on Machine Learning (ICML), pp. 2191–2200, 2018. find
  20. Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30(8): 595–608, 2016. find
  21. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015. find
  22. Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. find our card
  23. Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Deriving neural architectures from sequence and graph kernels. pp. 2024–2033, 2017. find
  24. Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016. find
  25. Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs. arXiv preprint arXiv:1811.01900, 2018. — [arXiv:1811.01900](https://arxiv.org/abs/1811.01900) find
  26. J. A. Nelder and R. W. M. Wedderburn. Generalized linear models. Journal of the Royal Statistical Society, Series A, General, 135:370–384, 1972. find
  27. Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning (ICML), pp. 2014–2023, 2016. find
  28. Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. Proc. Computer Vision and Pattern Recognition (CVPR), IEEE, 1(2):4, 2017. find
  29. Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Advances in neural information processing systems, pp. 4967–4976, 2017. find our card
  30. Adam Santoro, Felix Hill, David Barrett, Ari Morcos, and Timothy Lillicrap. Measuring abstract reasoning in neural networks. In International Conference on Machine Learning, pp. 4477–4486, 2018. find
  31. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20 (1):81–102, 2009a. find
  32. 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, 2009b. find
  33. Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep): 2539–2561, 2011. find
  34. Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1):1929–1958, 2014. find
  35. Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018. find
  36. Saurabh Verma and Zhi-Li Zhang. Graph capsule convolutional neural networks. arXiv preprint arXiv:1805.08090, 2018. — [arXiv:1805.08090](https://arxiv.org/abs/1805.08090) find
  37. Boris Weisfeiler and AA Lehman. 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
  38. Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning (ICML), pp. 5453–5462, 2018. find
  39. Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365–1374. ACM, 2015. find
  40. Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems (NIPS), 2018. find
  41. Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems, pp. 3391–3401, 2017. find
  42. Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Intelligence, pp. 4438–4445, 2018. find