How hard is graph isomorphism for graph neural networks?

Andreas LoukasarXiv 2020 · arXiv

Introduction

A fundamental question in the study of Graph Neural Networks (GNNs) is their expressive power—specifically, their ability to distinguish between non-isomorphic graphs. While traditional analyses link the power of "anonymous" Message-Passing Neural Networks (MPNNs) to the 1st-order Weisfeiler-Lehman (1-WL) test, modern GNNs often utilize unique node identifiers. Theoretically, this makes them universal, but practical constraints on network depth and width remain poorly understood. This research establishes theoretical lower bounds on the resources required for MPNNs to solve the graph isomorphism problem, introducing the concept of communication capacity.

The Communication Capacity Framework

To quantify the limits of GNNs, the author introduces Communication Capacity ($c_g$). This metric represents the maximum amount of information nodes can exchange during a forward pass, determined by the network's depth ($d$), width ($w$), message size ($m$), and the connectivity of the input graph.

Communication capacity measures information flow across graph cuts.

The core of the theoretical approach involves linking this capacity to Communication Complexity. By framing graph isomorphism as a distributed problem where two parties, Alice and Bob, each hold a portion of a graph ($G_a$ and $G_b$), the author determines the minimum number of bits they must exchange to decide if the combined graph $G$ belongs to a specific isomorphism class.

The Alice and Bob setup used to derive communication complexity bounds for graph isomorphism.

Hardness Results for Graphs and Trees

The study derives concrete hardness results for both worst-case and average-case scenarios:

  • The Quadratic Bottleneck: For general connected graphs, the required communication capacity scales as $\Omega(n^2)$. This implies that as the number of nodes $n$ increases, the network's size (depth and width) must grow quadratically to maintain its ability to distinguish graphs.
  • Trees are Linear: In contrast, distinguishing trees is significantly "easier," requiring only linear capacity, $\Omega(n)$.

A critical insight is that a large receptive field is insufficient. Even if a GNN is deep enough for every node to "see" the entire graph, it will fail if the "pipes"—the width and message size—are too narrow to transmit the necessary structural information. These constraints persist even when nodes are equipped with unique identifiers.

Empirical Validation

The theoretical bounds were tested using 12 synthetic isomorphism classification tasks involving connected graphs and trees. The experiments involved training 420 different MPNN architectures (GIN0) with varying depths and widths.

The results showed a striking alignment with the theory. For 6-node graphs, a capacity of 4 was sufficient for 99% accuracy. However, for 12-node graphs, the requirement surged to 112. Networks falling below the theoretical capacity threshold consistently failed to achieve high accuracy, regardless of their specific configuration.

Conclusion

This work provides a rigorous framework for understanding the practical limits of GNNs. By proving that general graph isomorphism requires quadratic communication capacity, it highlights a significant scaling challenge for MPNNs. While GNNs are effective for small graphs, their performance is fundamentally constrained by the information-theoretic "bottleneck" of message passing as graph size increases. Future research may explore how higher-order GNNs or alternative architectures might bypass these linear and quadratic scaling laws.

Summary updated

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.
BibTeX
@misc{loukas2020how,
  author = {Andreas Loukas},
  title = {{How hard is graph isomorphism for graph neural networks?}},
  year = {2020},
  eprint = {2005.06649},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.06649},
}
Figure