Efficient Global Information Propagation in Graphs

This direction is split into other directions: quadratic attention complexity (global attention scalability). Its last version stays readable and citable here.

Version 1 of 1134 papers143 conceptsfrozen 2026-10-04

Traditional Graph Neural Networks (GNNs) operate like a game of "telephone." In the standard Message Passing (MP) paradigm, a node only learns about its immediate neighbors. To reach a node ten hops away, the information must pass through ten layers of processing. As Vijay Prakash Dwivedi and Ladislav Rampášek highlight in the Long Range Graph Benchmark, this localism leads to "oversquashing"—where the signal from distant nodes is compressed and lost—and "oversmoothing," where node features become indistinguishable after too many iterations.

To solve this, researchers are moving toward Graph Transformers and global propagation mechanisms. These models allow every node to "see" every other node in a single step, effectively turning the graph into a fully connected set. However, this global vision comes with a steep price: quadratic computational complexity ($O(N^2)$). For a graph with a million nodes, a standard attention matrix would require trillions of entries.

The current frontier of research focuses on breaking this quadratic wall, enabling global context with linear scaling.

The Quadratic Wall and the Need for Global Reach

The fundamental tension in graph machine learning is between receptive field and efficiency. While Michael M. Bronstein and colleagues note that global attention can bypass local bottlenecks, the memory and compute requirements grow too fast for real-world applications like social networks or city-wide sensor grids.

As Md Shamim Hussain and Mohammed J Zaki demonstrate with the Edge-augmented Graph Transformer (EGT), global self-attention is a powerful replacement for convolution, but it is often "prohibitively expensive" for large-scale relational data. This has sparked a wave of innovation in architectures that provide the benefits of all-to-all communication without the $O(N^2)$ cost.

Linearizing Global Attention

One primary strategy to achieve efficiency is linearized attention. Instead of computing a massive $N \times N$ similarity matrix between all pairs of nodes, these models change the order of operations.

In Primphormer, Youmei Qiu reformulates self-attention as an optimization problem in "primal space." By avoiding the pairwise matrix entirely, the model achieves $O(N)$ complexity. Similarly, STGformer by Hongjun Wang uses linear attention to process thousands of traffic sensors simultaneously, achieving a 100x speedup over previous global models.

The intuition here is simple: if we can represent node features in a way that allows us to sum them into a "global summary" first, and then let each node query that summary, we reduce the problem from "everyone talking to everyone" to "everyone talking to a central bulletin board."

Latent Workspaces and Virtual Nodes

Another approach to global propagation is the use of Global Workspaces or Virtual Nodes. Instead of forcing every node to attend to every other node, researchers introduce a shared latent memory.

Jie LI proposes InterpGNN-GW, which uses a shared memory buffer. Distant nodes write their information to this buffer, and other nodes read from it. This acts as a "high-speed communication channel," a concept also explored in Neural Atoms by Xuan Li. By creating these "neural atoms" or virtual hubs, the model allows information to leap across the graph in a single hop, bypassing the physical constraints of the edges.

Beyond Attention: Signatures and State Space Models

Some of the most recent work moves away from the Transformer architecture entirely while keeping the global goal.

  • Randomized Signatures: Bernhard Schäfl and Sepp Hochreiter introduced G-Signatures, which treat graphs as paths in latent space. By using rough path theory, they enable global propagation in a single step without any attention matrices.
  • State Space Models (SSMs): Following the success of Mamba in sequence modeling, researchers like Jinbo She are applying SSMs to graphs. DirGraphSSM sequentializes graph data to capture long-range dependencies with linear time complexity, offering a faster alternative to Graph Transformers.
  • Sketched Features: Ryien Hosseini and Henry Hoffmann use Sketched Random Features (SRF) to inject low-dimensional projections of the entire graph's features into every layer. This gives every node a "global sketch" of the network's state at a fraction of the cost of attention.

Why It Works: The Shift to Global Inductive Biases

The success of these models suggests a shift in the fundamental philosophy of graph learning. Early GNNs assumed that homophily (neighbors are similar) was the most important bias. However, as Haoyu Liu points out in the work on SIMGA, many real-world graphs are heterophilous, where a node's most relevant information might be far away.

By building architectures that prioritize global reach—whether through linearized attention, matrix functions as seen in MFNs by Ilyes Batatia, or hierarchical partitioning in S2Transformer—the field is moving toward a "plain" Transformer-like approach. As Liheng Ma argues in Simplifying Graph Transformers, once we solve the scaling and positional encoding issues, global models often outperform local ones because they don't assume that the graph's edges are the only paths for information to flow.

Papers in this version

Showing 60 of 134 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_efficient_global_information_propagation_861e21bb,
  title = {Efficient Global Information Propagation in Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-global-information-propagation-in-graphs/rdr_861e21bb864c428b80c34602386bfc5b},
  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_efficient_global_information_propagation_861e21bb_v1,
  title = {Efficient Global Information Propagation in Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-global-information-propagation-in-graphs/rdr_861e21bb864c428b80c34602386bfc5b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}