Long Range Dependencies in Graph Neural Networks

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2778 papers833 conceptsfrozen 2026-10-04

The standard paradigm for learning on graphs, popularized by Thomas Kipf and Max Welling in Semi-Supervised Classification with Graph Convolutional Networks, relies on Message Passing (MP). In this framework, a node updates its representation by aggregating features from its immediate neighbors. While highly effective for local patterns, this "locality bias" creates a fundamental bottleneck: to understand how two nodes separated by ten hops interact, the model must stack ten layers.

As the field moves toward complex physical simulations, brain connectivity, and molecular modeling, researchers have found that this local-only approach is insufficient. The current research direction focuses on breaking the locality constraint to capture Long-Range Dependencies (LRD)—the global relationships that define a graph's true structure.

The Locality Bottleneck

In a standard GNN, each layer expands the "receptive field" of a node by exactly one hop. This creates two primary failure modes when trying to reach distant nodes:

  1. Over-squashing: As information from an exponentially growing neighborhood is compressed into a single fixed-size vector, signals from distant nodes are "squashed" and lost. Dai Shi and colleagues characterize this in Exposition on over-squashing problem on GNNs as a fundamental information bottleneck.
  2. Over-smoothing: To reach distant nodes, one might simply add more layers. However, Dimitrios Kelesis and Georgios Paliouras show in Analyzing the effect of residual connections to oversmoothing in graph neural networks that deep GNNs often converge to a state where all node features become indistinguishable, effectively washing out the signal.

This bottleneck is particularly visible in scientific domains. For instance, Mario Lino notes in Simulating Continuum Mechanics with Multi-Scale Graph Neural Networks that capturing instantaneous pressure changes in fluids requires global communication that local MP cannot provide. Similarly, Shan Jin argues in Long-range Brain Graph Transformer that brain networks rely on "small-world" properties where distant anatomical regions must communicate directly to support cognition.

Architectures for Global Reasoning

To solve these problems, researchers are moving beyond simple neighbor aggregation toward architectures that allow "shortcuts" across the graph.

Graph Transformers and Global Attention

The most direct solution is to treat the graph as a set of tokens and apply self-attention. Graphormer demonstrated that Transformers can outperform GNNs if they are "injected" with structural information like spatial and edge encodings. To handle the $O(N^2)$ complexity of attention, Ladislav Rampásek proposed the GPS (General, Powerful, Scalable) Graph Transformer, which decouples local message-passing from global linear attention. This allows the model to maintain local structural integrity while allowing every node to "see" every other node in a single layer.

Sequence Modeling on Random Walks

An emerging alternative is to treat the graph not as a static structure, but as a collection of paths. Dexiong Chen and Till Hendrik Schulz introduced NeuralWalker in Learning Long Range Dependencies on Graphs via Random Walks. By converting random walks into sequences and processing them with State Space Models (SSMs) like Mamba, the model can capture dependencies across hundreds of hops without the memory overhead of full attention. Similarly, Moshe Eliasof and Claudio Gallicchio developed GRAMA, which uses autoregressive moving average models to propagate information efficiently across the graph diameter.

Hierarchical and Multi-Scale Integration

In physical systems, long-range effects often manifest at different scales. BENO, developed by Haixin Wang and colleagues, solves elliptic PDEs by mimicking Green’s functions using a dual-branch GNN and Transformer. This allows the model to capture how a change at a distant boundary influences the entire interior domain. In robotics, Jeongwhan Choi uses a Hierarchical Contact Mesh Transformer to model the "ripple effects" of collisions across flexible bodies.

The Need for New Benchmarks

A significant hurdle in this research direction is that classic graph benchmarks (like Cora or Citeseer) are "local" by nature; they can be solved with 2-3 layers of message passing. To address this, Vijay Prakash Dwivedi and others introduced the Long Range Graph Benchmark (LRGB).

These new datasets, such as Peptides-func, specifically require the model to integrate information across large geodesic distances. As Haitz Sáez de Ocáriz Borde argues in Towards Quantifying Long-Range Interactions in Graph Machine Learning, without these specialized benchmarks, we cannot distinguish between a model that is "deep" and a model that truly understands global structure. The shift toward LRD represents a transition from GNNs as local feature extractors to GNNs as global reasoning engines.

Papers in this version

Showing 60 of 778 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 480 papers
  2. Version 1 · 2026-10-04 · 778 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_long_range_dependency_bottleneck_bb7e9a02,
  title = {long-range dependency bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/long-range-dependency-bottleneck/rdr_bb7e9a027c9c4d8fae29716595508d9d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_long_range_dependencies_in_graph_neural__bb7e9a02_v1,
  title = {Long Range Dependencies in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/long-range-dependencies-in-graph-neural-networks/rdr_bb7e9a027c9c4d8fae29716595508d9d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}