Generalization and Representational Limits of Graph Neural Networks

Vikas Garg, Stefanie Jegelka, Tommi Jaakkola
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:3419-3430, 2020.

Abstract

We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties, e.g., shortest/longest cycle, diameter, or certain motifs, cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structure (e.g., via relative orientation of messages, or local port ordering) to distinguish neighbors of each node. Our treatment includes a novel graph-theoretic formalism. Second, we provide the first data dependent generalization bounds for message passing GNNs. This analysis explicitly accounts for the local permutation invariance of GNNs. Our bounds are much tighter than existing VC-dimension based guarantees for GNNs, and are comparable to Rademacher bounds for recurrent neural networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-garg20c, title = {Generalization and Representational Limits of Graph Neural Networks}, author = {Garg, Vikas and Jegelka, Stefanie and Jaakkola, Tommi}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {3419--3430}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/garg20c/garg20c.pdf}, url = {https://proceedings.mlr.press/v119/garg20c.html}, abstract = {We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties, e.g., shortest/longest cycle, diameter, or certain motifs, cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structure (e.g., via relative orientation of messages, or local port ordering) to distinguish neighbors of each node. Our treatment includes a novel graph-theoretic formalism. Second, we provide the first data dependent generalization bounds for message passing GNNs. This analysis explicitly accounts for the local permutation invariance of GNNs. Our bounds are much tighter than existing VC-dimension based guarantees for GNNs, and are comparable to Rademacher bounds for recurrent neural networks.} }
Endnote
%0 Conference Paper %T Generalization and Representational Limits of Graph Neural Networks %A Vikas Garg %A Stefanie Jegelka %A Tommi Jaakkola %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-garg20c %I PMLR %P 3419--3430 %U https://proceedings.mlr.press/v119/garg20c.html %V 119 %X We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties, e.g., shortest/longest cycle, diameter, or certain motifs, cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structure (e.g., via relative orientation of messages, or local port ordering) to distinguish neighbors of each node. Our treatment includes a novel graph-theoretic formalism. Second, we provide the first data dependent generalization bounds for message passing GNNs. This analysis explicitly accounts for the local permutation invariance of GNNs. Our bounds are much tighter than existing VC-dimension based guarantees for GNNs, and are comparable to Rademacher bounds for recurrent neural networks.
APA
Garg, V., Jegelka, S. & Jaakkola, T.. (2020). Generalization and Representational Limits of Graph Neural Networks. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:3419-3430 Available from https://proceedings.mlr.press/v119/garg20c.html.

Related Material