Communication Capacity and Information Bottlenecks in Graph Neural Networks

This direction is merged into another direction: 1-WL expressivity limit. Its last version stays readable and citable here.

Version 1 of 18 papers24 conceptsfrozen 2026-10-04

In the study of Graph Neural Networks (GNNs), researchers have traditionally focused on expressivity: what functions can a GNN theoretically represent? This is often measured by the Weisfeiler-Lehman (WL) test, which determines if a model can distinguish between different graph structures. However, a growing body of evidence suggests that expressivity is only half the story. Even if a GNN is theoretically capable of distinguishing two graphs, it may fail in practice because it cannot move enough information across the graph's topology.

This shift in perspective treats GNNs not just as function approximators, but as distributed communication systems with finite bandwidth.

The Receptive Field Fallacy

A common intuition in GNN design is that "deeper is better" because it increases the receptive field. If a graph has a diameter $D$, it is often assumed that a GNN with $D$ layers is sufficient for every node to "see" the entire graph.

Andreas Loukas challenged this assumption in How hard is graph isomorphism for graph neural networks?. He demonstrated that having a large enough receptive field is a necessary but not sufficient condition for solving structural tasks. Even if every node can theoretically reach every other node, the "pipes" connecting them—defined by the network's width and message size—might be too narrow.

Loukas introduced the concept of communication capacity: the total amount of information nodes can exchange during a forward pass. If the capacity is lower than the complexity of the graph structure, the model will fail to distinguish non-isomorphic graphs, regardless of its depth.

Capacity as a Resource Budget

If depth alone isn't the answer, how should we scale GNNs? In What graph neural networks cannot learn: depth vs width, Andreas Loukas proved that the computational power of a GNN is fundamentally constrained by the product of its depth ($d$) and width ($w$).

This $d \times w$ metric represents a unified capacity budget. For a GNN to solve fundamental problems like cycle detection or finding shortest paths, this product must scale polynomially with the number of nodes $n$ in the graph. This creates a trade-off: you can achieve the necessary capacity with a very deep, narrow network or a shallower, wider one. However, if the total budget is too small, the GNN becomes "blind" to global properties, effectively becoming a local algorithm despite its theoretical architecture.

The Over-squashing Phenomenon

When the communication capacity is insufficient, GNNs suffer from over-squashing. This occurs when information from an exponentially growing number of nodes is compressed into a single fixed-size vector as it propagates through the layers.

Francesco Di Giovanni, Michael M. Bronstein, and their colleagues explored this in How does over-squashing affect the power of GNNs?. They linked over-squashing to the "resistance" or "commute time" between nodes in a graph. In graphs with bottlenecks (like a bridge connecting two dense clusters), the network must possess significantly higher architectural complexity to "mix" information across that bottleneck.

Interestingly, simply increasing the width of the hidden layers provides diminishing returns. Giannis Nikolentzos and his co-authors showed in What Do GNNs Actually Learn? Towards Understanding their Representations that standard GNNs like GCN and GIN essentially act as "walk counters." Beyond a certain threshold, wider layers cannot compensate for the inherent loss of information caused by the graph's connectivity patterns; the structural constraints of message-passing itself become the bottleneck.

Beyond the WL Test

The traditional focus on the WL test often ignores the physical constraints of computation. Guanyu Cui, Hsin-Hao Su, and others argued in WL Tests Are Far from All We Need that we must revisit GNN power from a distributed computation perspective.

They pointed out that simulating a single iteration of the WL test is not a "free" operation. In a real-world setting with limited message sizes and finite precision, the depth required to propagate information scales not just with the graph diameter, but also with the ratio of edges to available width. This means that in deterministic settings, matching the expressivity of standard graph isomorphism tests requires significantly more layers and resources than previously assumed.

Summary of Intuition

To understand why a GNN succeeds or fails, stop looking only at the "logic" of the update functions and start looking at the "plumbing" of the architecture:

  1. Depth provides the reach (receptive field).
  2. Width and Message Size provide the bandwidth.
  3. Capacity ($d \times w$) is the total volume of information the network can process.
  4. Graph Topology (bottlenecks) determines how much bandwidth is required to prevent information from being "squashed" into oblivion.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_communication_capacity_and_information_b_5b311ffd,
  title = {Communication Capacity and Information Bottlenecks in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/communication-capacity-and-information-bottlenecks-in-graph-neural-networks/rdr_5b311ffd1fb145738222d5d80e3244d0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_communication_capacity_and_information_b_5b311ffd_v1,
  title = {Communication Capacity and Information Bottlenecks in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/communication-capacity-and-information-bottlenecks-in-graph-neural-networks/rdr_5b311ffd1fb145738222d5d80e3244d0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}