Cayley Graph Propagation

Jj Wilson, Maya Bechler-Speicher, Petar Veličković

Introduction

Graph Neural Networks (GNNs) have become the standard for learning on graph-structured data. However, their reliance on local message-passing—where nodes update their states based on immediate neighbors—introduces a significant bottleneck known as over-squashing. As information travels across a graph to capture long-range dependencies, the exponential growth of a node's receptive field must be compressed into a single fixed-size vector. This often leads to the loss of critical information from distant nodes.

While previous research suggested "rewiring" graphs to add shortcuts, these methods are often computationally expensive or lack a rigorous mathematical foundation. Cayley Graph Propagation (CGP) addresses these challenges by routing information through a complete, bottleneck-free expander graph, maintaining mathematical integrity through the use of virtual nodes.

The Problem: The Truncation Trap

A recent advancement, Expander Graph Propagation (EGP), proposed using Cayley graphs—mathematical structures known for high connectivity and low diameter—as templates for global communication. However, EGP suffered from a critical flaw: it truncated these templates to match the exact number of nodes in the input graph.

This paper provides a theoretical proof that such truncation is detrimental. Even slight modifications to a Cayley graph's structure can cause a "detrimental drop" in the Cheeger constant (a measure of connectivity) and a spike in graph diameter. By attempting to force the expander to fit the data perfectly, previous methods inadvertently re-introduced the very bottlenecks they sought to eliminate.

Methodology: Embracing the Complete Structure

Cayley Graph Propagation (CGP) introduces a framework that "embraces the complete structure" of the expander graph. The methodology consists of four key components:

  1. The Complete Cayley Template: Instead of cutting the graph, CGP identifies the smallest Cayley graph (based on the special linear group $SL(2, \mathbb{Z}_n)$) that is at least as large as the input graph.
  2. Virtual Nodes: To bridge the gap between the input size and the Cayley template, CGP introduces "virtual nodes." These nodes do not represent real data points but function as high-speed "relay stations" or bridges, facilitating global information flow without creating a single point of failure.
  3. Interwoven Layers: The architecture alternates between Input Layers, which preserve local topological features through standard message passing, and Cayley Layers, which utilize the complete expander structure for global communication.
  4. Computational Efficiency: Unlike "Transformer-style" GNNs that face $O(N^2)$ complexity, CGP utilizes a sparse (4-regular) Cayley structure. This ensures the model remains scalable and avoids the memory overhead associated with fully connected graphs.

Experimental Results

The authors evaluated CGP against several competitive benchmarks, including the Open Graph Benchmark (OGB), TUDataset, and the Long Range Graph Benchmark (LRGB).

Performance and Long-Range Dependencies

On the ogbg-molhiv dataset, CGP achieved a Test ROC-AUC of 0.7899 (using a GIN backbone), a significant improvement over EGP (0.7537) and standard GCN/GIN models. Furthermore, on the LRGB Peptides datasets—specifically designed to test long-distance interactions—CGP outperformed traditional graph rewiring techniques like SDRF and FoSR.

Scalability and Speed

CGP demonstrates remarkable efficiency. In runtime tests on the COLLAB dataset, CGP was nearly 7x faster than PANDA. It also successfully processed large graphs where "Fully Adjacent" (FA) methods frequently encountered Out-Of-Memory (OOM) errors.

Theoretical Insights

The superiority of CGP is rooted in its spectral properties. The authors demonstrate that CGP consistently maintains a lower total effective resistance compared to EGP. Mathematically, this indicates that information (or "current") flows much more easily between any two nodes in the system, confirming that the virtual nodes effectively preserve the expander's bottleneck-free nature.

Conclusion and Future Work

Cayley Graph Propagation provides a robust solution to the over-squashing problem by prioritizing the mathematical properties of expander graphs over rigid adherence to input node counts. While highly effective, the authors note that CGP may be less beneficial for graphs that are already extremely dense, where sparse expander structures might override useful inductive biases.

Future research directions include exploring "structure-aware" alignment—mapping input nodes to Cayley nodes based on their physical proximity—and extending these complete expander structures to temporal graphs that evolve over time.

Summary updated

Abstract

In spite of the plethora of success stories with graph neural networks (GNNs) on modelling graph-structured data, they are notoriously vulnerable to over-squashing, whereby tasks necessitate the mixing of information between distance pairs of nodes. To address this problem, prior work suggests rewiring the graph structure to improve information flow. Alternatively, a significant body of research has dedicated itself to discovering and pre-computing bottleneck-free graph structures to ameliorate over-squashing. One such family of bottleneck-free graphs well regarded in the mathematical community are \emph{expander graphs}, with prior work—Expander Graph Propagation (EGP)—proposing the use of a well-known expander graph family—the Cayley graphs of the $\mathrm{SL}(2,\mathbb{Z}_n)$ special linear group—as a computational template for GNNs. However, despite its solid theoretical grounding, the computational graphs used by EGP are truncated to align with a given input graph. In this work, we show that such an approach is detrimental to the coveted expansion properties, and instead propose a method that propagates information over the complete Cayley graph structure, thereby ensuring it is bottleneck-free to better alleviate over-squashing. Our empirical evidence across several real-world datasets not only shows our method recovers significant improvements as compared to EGP, but also akin to or outperforming computationally complex graph rewiring techniques.
BibTeX
@inproceedings{wilson2024cayley,
  author = {JJ Wilson and Maya Bechler-Speicher and Petar Veličković},
  title = {{Cayley Graph Propagation}},
  booktitle = {LoG},
  year = {2024},
  url = {https://openreview.net/forum?id=VaTfEDs6lE},
}
Figure