How hard is to distinguish graphs with graph neural networks?

Andreas LoukasNeurIPS 2020 · OpenReview

A hallmark of graph neural networks (GNNs) is their ability to distinguish the isomorphism class of their inputs—essentially, telling whether two graph structures are fundamentally the same or different. However, exactly how much computational "bandwidth" does a GNN need to tell two graphs apart?

This mini-paper explores the NeurIPS 2020 study by Andreas Loukas, which establishes fundamental limits on the expressive power of GNNs. By bridging GNN architecture with classic communication complexity, the research provides the first tight lower bounds for practical, finite-sized GNNs, proving that even with unique node identifiers, GNNs require significant architectural resources to "see" the difference between complex structures.

The Expressivity Bottleneck in Practical GNNs

Graph Neural Networks, specifically the popular Message-Passing Neural Network (MPNN) variety, are the standard for graph classification. Historically, their expressive power has been studied either in the "limit" (assuming infinite network size) or restricted to "anonymous" networks where nodes lack unique features.

In practice, however, we use finite networks and often provide nodes with unique features (like one-hot encodings). The community has lacked a clear understanding of the "hardness" of graph isomorphism for these practical networks. Previous analyses often relied on the "diameter" of a graph (how many steps it takes to cross it), but these bounds were often too loose to be useful.

Bridging GNNs and Communication Complexity

To find tighter bounds, the author introduces a novel framework that treats the GNN as a communication network where edges have limited bandwidth.

The framework bridges communication capacity, communication complexity (the Alice and Bob model), and graph isomorphism testing.

The framework relies on two core concepts:

  1. Communication Capacity ($c_g$): This metric defines the maximum amount of information nodes can exchange during a forward pass. It is a product of the network's depth ($d$), width ($w$), message size ($m$), and global state size ($\gamma$).
  2. The Alice and Bob Model: To establish lower bounds, the author imagines partitioning a graph into two halves, held respectively by "Alice" and "Bob." For a GNN to correctly classify the entire graph, Alice and Bob must exchange enough information about their respective halves.

By calculating the minimum bits required to solve the graph isomorphism problem in this partitioned setting, the study derives necessary conditions for the GNN's capacity.

Key Insights: How Capacity Scales

The analysis reveals that a network's depth alone is insufficient to guarantee expressivity; the total "volume" of information flow is the true bottleneck. A very deep but narrow network might fail just as easily as a wide but shallow one.

Specifically, the capacity required scales differently depending on the graph structure:

  • Quadratic Scaling for General Graphs: For general connected graphs, the capacity must grow as $\Omega(n^2)$, where $n$ is the number of nodes. This means that doubling the number of nodes requires four times the architectural resources to maintain the same discriminative power.
  • Linear Scaling for Trees: Distinguishing trees only requires a linear capacity of $\Omega(n)$. This confirms the intuition that tree structures, lacking cycles, are fundamentally less complex for message-passing architectures.
  • Average-Case Hardness: Unlike many theoretical results that only apply to pathological worst-case scenarios, these bounds hold for the average case (expected behavior over a distribution of graphs).

Empirical Alignment

The study validates these theoretical bounds with a rigorous empirical setup involving 12 graph classification tasks and 420 different GNN configurations. The datasets featured synthetic universes of all possible connected graphs (up to 12 nodes) and trees (up to 22 nodes), with nodes given unique identifiers to test the non-anonymous case.

The experiments demonstrated a striking correlation between the proposed Communication Capacity and actual test accuracy. The theoretical lower bounds perfectly predicted a "failure zone" where GNN architectures would exhibit poor performance. For instance, while a 6-node graph only required a capacity of 4 to reach 99% accuracy, a 12-node graph required a capacity of roughly 112. Furthermore, the derived bounds proved to be up to two orders of magnitude tighter than those suggested by simple diameter-based arguments.

Limitations and Future Directions

While comprehensive, the analysis is tailored to Message-Passing architectures (like GCN, GAT, and GIN) and assumes specific types of readout mechanisms (such as majority-voting or consensus). "Higher-order" GNNs that bypass the standard message-passing paradigm, or networks utilizing exotic readout functions, might not be subject to these exact limits.

Looking forward, this communication-centric view opens new avenues for analyzing other graph properties. The framework could be extended to understand the hardness of counting specific subgraphs or detecting long-range dependencies, further illuminating the fundamental limits of graph representation learning.

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
@inproceedings{loukas2020how,
  author = {Andreas Loukas},
  title = {{How hard is to distinguish graphs with graph neural networks?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=cTIkTtlonE},
}
Figure