How hard is to distinguish graphs with graph neural networks?

Abstract

A hallmark of graph neural networks is their ability to distinguish the isomorphism class of their inputs. This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN). MPNN encompasses the majority of graph neural networks used today and is universal when nodes are given unique features. The analysis relies on the introduced measure of communication capacity. Capacity measures how much information the nodes of a network can exchange during the forward pass and depends on the depth, message-size, global state, and width of the architecture. It is shown that the capacity of MPNN needs to grow linearly with the number of nodes so that a network can distinguish trees and quadratically for general connected graphs. The derived bounds concern both worst- and average-case behavior and apply to networks with/without unique features and adaptive architecture -- they are also up to two orders of magnitude tighter than those given by simpler arguments. An empirical study involving 12 graph classification tasks and 420 networks reveals strong alignment between actual performance and theoretical predictions.

References in corpus (19)

• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Molecular Graph Convolutions: Moving Beyond Fingerprints
• Graph Convolutional Matrix Completion
• Interaction Networks for Learning about Objects, Relations and Physics
• Gated Graph Sequence Neural Networks
• Adaptive Computation Time for Recurrent Neural Networks
• Principal Neighbourhood Aggregation for Graph Nets
• Universal Invariant and Equivariant Graph Neural Networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Adaptive Propagation Graph Convolutional Network
• A Survey on The Expressive Power of Graph Neural Networks
• Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology
• Generalization and Representational Limits of Graph Neural Networks
• Can Graph Neural Networks Count Substructures?
• Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networks in Molecular Graph Analysis
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework

Cited by in corpus (7)

• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Building powerful and equivariant graph neural networks with structural message-passing
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
• Generalizing Downsampling from Regular Data to Graphs
• Connecting Graph Convolutional Networks and Graph-Regularized PCA