What graph neural networks cannot learn: depth vs width

By Andreas Loukas. International Conference on Learning Representations, 2019

345 citations recorded by the source corpus.

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNmp can lose a significant portion of their power when their depth and width is restricted. The proposed impossibility statements stem from a new technique that enables the repurposing of seminal results from distributed computing and leads to lower bounds for an array of decision, optimization, and estimation problems involving graphs. Strikingly, several of these problems are deemed impossible unless the product of a GNNmp's depth and width exceeds a polynomial of the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/7f42da4abfadf9d5a464affe22d0bd4bf21c0edb

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

Recipe for a General, Powerful, Scalable Graph Transformer (2022, background): “, diagonals of m-steps random walk) can successfully capture the difference in the skip links of the two graphs [39], resulting in their different node coloring [15].”
Learning to Drop: Robust Graph Neural Network via Topological Denoising (2020, methodology): “ong“noisy” edges may decrease the quality of node embeddings. Overwhelming information from multiple communities put GNNs at the risk of oversmoothing, especially when multiple GNN layers are stacked [30, 38, 55]. Existing methods either utilize graph sparsification strategies to extract subgraphs o”
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].”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “Loukas (Loukas, 2020) and Sato et al. studied the limits of GNNs when applied to combinatorial problems.”
Benchmarking Graph Neural Networks (2023, background): “The equivalence is based on the condition when MP-GCNs handle anonymous nodes (Loukas, 2020), i.”
Everything is Connected: Graph Neural Networks (2023, methodology): “To supplement this further, Loukas (2020) showed that, under proper initial features, suﬃcient depth-width product (#layers × dim h u ), and correct choices of ψ and φ , GNNs in Equation 10 are Turing universal —likely to be able to simulate any computation which any computer can perform over such…”
Can graph neural networks count substructures? (2020, background): “For example, Loukas [37] shows that GNNs under assumptions are Turing universal but lose power when their depth and width are limited, though the arguments rely on the nodes all having distinct features and the focus is on the asymptotic depth-width tradeoff.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, methodology): “based GNNs [33], [37], [38] that obtain universality at the”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, background): “Given the recent theoretical results on the importance of informative graph PE for expressive GNNs (Murphy et al., 2019; Srinivasan & Ribeiro, 2019; Loukas, 2020), we are interested in a generic framework that can enable GNNs to separate positional and structural representations to increase their…”
Generalization and Representational Limits of Graph Neural Networks (2020, methodology): “They and (Loukas, 2020) also established connections to distributed local algorithms.”
How Powerful are Spectral Graph Neural Networks (2022, methodology): “, 2020b), simulating Turing Machine (Loukas, 2020), computing graph properties (Garg et al.”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “Regarding computability, Loukas [81] proves that some GNNs can be too small to compute some properties of graphs, such as nding their diameter or a minimum spanning tree, and give minimum depth and width requirements for such tasks.”