Generalization and Representational Limits of Graph Neural Networks

By Vikas K. Garg, Stefanie Sabrina Jegelka, Tommi S. Jaakkola. International Conference on Machine Learning, 2020

372 citations recorded by the source corpus.

We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties 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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/3a5af4545ee3ac3f413841c10c7605a1cefeb9e5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Can graph neural networks count substructures? (2020, background): “[17] provide impossibility results of several classes of GNNs to decide graph properties including girth, circumference, diameter, radius, conjoint cycle, total number of cycles, and k-cliques.”
Principal Neighbourhood Aggregation for Graph Nets (2020, background): “Only recently there have been significant studies on the expressive power of various GNN models [6, 7, 8, 9, 10, 11].”
GemNet: Universal Directional Graph Neural Networks for Molecules (2021, background): “[27] showed the limitations of basic directional message passing.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “Finally, [67] also analysed the expressive power of MPNNs and other more powerful variants and provided generalisation bounds.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “Understanding the representational power of GNNs is a nascent area of research, and recent works adapt existing results from learning theory to the problem of graph representation learning [40, 76, 82, 112, 117].”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “[46] prove generalization bounds for a large class of GNNs that depend mainly on the maximum degree of the graphs, the number of layers, width, and the norms of the learned parameter matrices.”
GeoMol: Torsional Geometric Generation of Molecular 3D Conformer Ensembles (2021, background): “…pitfalls that obstruct direct predictions of 3D atom coordinates from node embeddings, e.g. symmetric or locally isomorphic nodes would always have identical MPNN embeddings [Xu et al., 2019, Garg et al., 2020] and, as a consequence, would be inappropriately assigned identical 3D coordinates.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “Murphy et al. (Murphy et al., 2019b;a) and Sato et al. (Sato et al., 2020) extended the expressivity of GNNs by considering all possible permutations of a graph’s adjacency matrix, or adding random node features, respectivley.”
On the Bottleneck of Graph Neural Networks and its Practical Implications (2020, background): “Thus, from the perspective of a single node v , the rest of the graph may look like a tree, rooted at v (Garg et al., 2020).”
How Powerful are Spectral Graph Neural Networks (2022, background): “, 2020b), simulating Turing Machine (Loukas, 2020), computing graph properties (Garg et al., 2020), and differentiating rooted graphs (Chen et al.”