What graph neural networks cannot learn: depth vs width

Abstract

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.

arXiv comment17 pages, 10 figures. International Conference on Learning Representations (ICLR), 2020

References in corpus (18)

• Emergence of scaling in random networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Message Passing for Quantum Chemistry
• Molecular Graph Convolutions: Moving Beyond Fingerprints
• Graph Convolutional Matrix Completion
• Learning Combinatorial Optimization Algorithms over Graphs
• Interaction Networks for Learning about Objects, Relations and Physics
• Gated Graph Sequence Neural Networks
• How Powerful are Graph Neural Networks?
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Universal Invariant and Equivariant Graph Neural Networks
• Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
• On the Turing Completeness of Modern Neural Network Architectures
• On the equivalence between graph isomorphism testing and function approximation with GNNs
• Survey of Distributed Decision
• Discriminative structural graph classification

Cited by in corpus (8)

• Revisiting Over-smoothing in Deep GCNs
• Bridging the Gap between Spatial and Spectral Domains: A Survey on Graph Neural Networks
• Graph Neural Networks: Methods, Applications, and Opportunities
• Can Graph Neural Networks Count Substructures?
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework
• From Local Structures to Size Generalization in Graph Neural Networks
• The Impact of Global Structural Information in Graph Neural Networks Applications
• What training reveals about neural network complexity