PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Inductive Biases in Transformers without Message Passing

Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip Torr, Ser-Nam Lim

arXiv:2305.17589v1cs.LGcs.AI

TL;DR

Graph Transformers must balance weak inductive bias without message passing against inherited message-passing limitations and reduced transferability. GRIT introduces a message-passing-free architecture with learned random-walk positional encodings, flexible node-pair attention, and degree information, and reports expressive theoretical results and state-of-the-art performance across graph benchmarks.

  • Problem

    Graph Transformers without message passing can perform poorly on smaller datasets, while message-passing-based models inherit MPNN limitations and differ from Transformers in other domains.

  • Method

    GRIT incorporates graph inductive biases without explicit message passing using learned RRWP-initialized relative encodings, joint node and node-pair updates, and degree information.

  • Results

    GRIT can express shortest-path distances and various graph propagation matrices, and achieves state-of-the-art empirical performance across small- and large-scale graph benchmarks.

  • Takeaways & Limitations

    Graph Transformers without message passing can incorporate graph inductive biases while delivering strong performance across a variety of graph datasets.

  • Takeaways & Limitations

    The expressivity results assume finite random-walk lengths and include a technical extension for vector-valued distances in the generalized distance-WL analysis.

Abstract

from arXiv · show

Transformers for graph data are increasingly widely studied and successful in numerous learning tasks. Graph inductive biases are crucial for Graph Transformers, and previous works incorporate them using message-passing modules and/or positional encodings. However, Graph Transformers that use message-passing inherit known issues of message-passing, and differ significantly from Transformers used in other domains, thus making transfer of research advances more difficult. On the other hand, Graph Transformers without message-passing often perform poorly on smaller datasets, where inductive biases are more crucial. To bridge this gap, we propose the Graph Inductive bias Transformer (GRIT) -- a new Graph Transformer that incorporates graph inductive biases without using message passing. GRIT is based on several architectural changes that are each theoretically and empirically justified, including: learned relative positional encodings initialized with random walk probabilities, a flexible attention mechanism that updates node and node-pair representations, and injection of degree information in each layer. We prove that GRIT is expressive -- it can express shortest path distances and various graph propagation matrices. GRIT achieves state-of-the-art empirical performance across a variety of graph datasets, thus showing the power that Graph Transformers without message-passing can deliver.

1. Introduction

Graph Transformers face a trade-off between message-passing limitations and the need for graph inductive biases, especially across dataset scales. GRIT addresses this trade-off without explicit message-passing and reports strong performance across small and large graph benchmarks.

  • Motivation: Graph Transformers may overfit limited data because their learned attention has weaker topology-based inductive bias than message-passing networks.Meaningful attention scores also require positional or structural relationships that are challenging to design for graphs.
  • Motivation: Message-passing modules can inherit MPNN limitations, reduce similarity to Transformers in other domains, and increase architectural and tuning complexity.These differences make transferring Transformer research advances to graph learning more difficult.
  • Motivation: 12,000 graphs: message-passing GNNs lead ZINC, whereas about 3,700,000 graphs: Graph Transformers lead PCQM4MV2.These benchmark observations illustrate how relative performance varies with dataset scale.
  • GRIT: GRIT incorporates graph inductive biases without explicit message-passing through learned RRWP positional encodings, joint node and node-pair updates, and degree information.Its design choices are theoretically justified and empirically evaluated.
  • Results: GRIT achieves state-of-the-art empirical performance across a variety of small- and large-scale graph learning benchmarks.The authors present this as bridging the performance gap between message-passing and non-message-passing approaches.

2. Related Work

Related work develops graph Transformers with positional or structural encodings, message-passing components, and alternatives that avoid local message passing. These approaches differ in how they represent graph structure and update node or edge information.

  • Positional and Structural Encodings: Graph Transformers often use positional or structural encodings to enhance both message-passing networks and Transformer architectures.The literature uses these encodings to capture graph information beyond raw node features.
  • Positional and Structural Encodings: Positional and structural encodings are used interchangeably in related literature, so this work uses “positional encodings” as an umbrella term.
  • Graph Transformers with Message-Passing: Early Graph Transformers used Laplacian positional encodings, while later models combined sparse neighborhood attention, global attention, or message-passing modules.Examples include the original global-attention model, SAN, and SignNet-based processing of Laplacian eigenvectors.
  • Graph Transformers without Message-Passing: The related-work landscape includes models whose code and models are publicly available, including the GRIT implementation.
  • Graph Transformers with Message-Passing: Random-walk structural encodings have also been used, but models using them integrated message-passing modules because they encode less positional information.
  • Graph Transformers without Message-Passing: Message-passing-free Graph Transformers use relative pairwise encodings such as shortest-path distances or generalized graph distances.Other variants treat nodes and edges as tokens, update node and edge tokens, or use alternative positional encodings for directed graphs.

3. Methodology and Theory

GRIT incorporates graph inductive biases without explicit message passing through learned RRWP-based relative encodings, flexible node-pair attention, and degree injection. Its theory establishes expressivity beyond shortest-path encodings, while visualizations and experiments show that RRWP captures higher-order structure and supports propagation-like attention.

  • Architecture: GRIT uses learned relative positional encodings initialized with relative random walk probabilities, flexible attention updating nodes and node pairs, and degree information in every layer.These three design choices are theoretically justified and are intended to incorporate graph inductive biases without explicit local message-passing modules.
  • Learned Random Walk Relative Encodings: RRWP encodes, for each node pair, the identity matrix and powers of the random-walk transition matrix up to a maximum walk length K.The transition matrix is M = D^-1A, where M_ij is the one-step probability of moving from node i to node j; K controls the maximum walk length.
  • Learned Random Walk Relative Encodings: Longer random walks reveal higher-order molecular structures and better expose stochastic-block-model communities while reducing bottlenecks.The fluorescein visualization highlights cliques in 3-step walks and star patterns in 4-step walks.
  • RRWP + MLP Expressivity: An elementwise MLP updates RRWP into learned relative encodings that can approximate shortest-path distances and broad classes of graph propagation matrices to arbitrary ϵ > 0 accuracy.For K-hop RRWP, shortest-path distances are recoverable for node pairs up to K − 1 hops; K = n recovers all shortest-path distances under the stated disconnected-node convention.
  • Flexible Attention Mechanism: GRIT conditions attention on learned node-pair representations and updates those pair representations, enabling the positional encodings themselves to evolve during Transformer layers.This flexibility addresses limitations of attention mechanisms that cannot reliably attend to specific tokens and supports applying an elementwise MLP to RRWP.
  • RRWP versus SPD: RRWP is strictly more expressive than shortest-path distances in the GD-WL analysis, distinguishing the Dodecahedron and Desargues graphs that SPD cannot distinguish.The result follows from RRWP-based GD-WL matching every SPD distinction and separating this additional non-isomorphic graph pair.
  • Injecting Degree Information: After attention, GRIT injects degree information into node representations, and LayerNorm makes sum-, degree-scaled-, and mean-aggregated representations equivalent.The degree term uses log(1 + d_i) with learnable weights before the standard feed-forward network.

4. Experimental Results

GRIT performs strongly across small, medium, long-range, and large-scale graph benchmarks without explicit message-passing modules. Ablations and synthetic experiments support its architectural choices and graph-propagation capabilities.

  • Benchmarking GNNs: GRIT achieves the best mean performance on four of five Benchmarking GNNs datasets, with statistically significant improvements.On the remaining dataset, it reaches second-best performance without a statistically significant difference from the best performer.
  • Long-Range Graph Benchmark: On both Peptides-func and Peptides-struct, GRIT obtains the best mean performance over MPNNs and Graph Transformers.The two tasks are designed to evaluate long-range graph interactions through multilabel classification and regression.
  • ZINC-full: On ZINC-full, GRIT achieves the best mean performance among MPNNs, Graph Transformers, higher-order GNNs, and PE-enhanced GNNs.ZINC-full contains approximately 250,000 graphs.
  • PCQM4Mv2: On PCQM4Mv2, GRIT reaches comparable performance to GraphGPS and Graphormer while using fewer learnable parameters.The result is based on a single run because of the dataset's size, and no hyperparameter search was conducted.
  • Ablations: Replacing GRIT's degree scalers, RRWP update, global attention, degree encoding, attention mechanism, or RRWP with alternatives worsens ZINC performance.The tested alternatives include sparse attention, Graphormer degree encoding, RWSE, and SPDPE.
  • Sensitivity analysis: GRIT remains state-of-the-art or near state-of-the-art across many RRWP K values, except for unreasonable settings such as K = 2.Other K values may perform slightly worse because hyperparameters selected for K = 21 were held fixed.
  • Synthetic experiments: In synthetic experiments, GRIT significantly outperforms other baselines by an order of magnitude when learning graph propagation patterns.Its attention mechanism matches both target sparsity and attention magnitudes, unlike the other evaluated mechanisms.

5. Conclusion

The paper concludes that GRIT incorporates graph inductive biases into Graph Transformers without local message passing. Its theoretical expressiveness and broad empirical results support this design as a way to improve Graph Transformer performance across dataset scales.

  • 5. Conclusion: GRIT uses learned RRWP-initialized relative positional encodings and flexible attention to capture shortest-path distances and graph propagation families.The paper also reports that RRWP initialization is strictly more expressive than shortest-path distances in the GD-WL graph isomorphism test.
  • 5. Conclusion: GRIT achieves state-of-the-art performance across a wide range of graph datasets without integrating local message-passing modules.A synthetic experiment also shows that its flexible attention mechanism can learn propagation matrices other Graph Transformers cannot learn as effectively.

A.1. Visualization of the Transformer Architecture of GRIT

Figure 4 provides an overview of the GRIT Transformer and a detailed view of its Transformer block. The visualization organizes the model's conceptual building blocks into one architecture.

  • A.1. Visualization of the Transformer Architecture of GRIT: Figure 4(a) visualizes the conceptual relationship between GRIT's proposed RRWP feature and the Transformer architecture.
  • A.1. Visualization of the Transformer Architecture of GRIT: Figure 4(b) shows the detailed design of the GRIT Transformer block.

B.1. Description of Datasets

The experiments use graph datasets drawn from Benchmarking GNNs, the Long-Range Graph Benchmark, and PCQM4Mv2. Together, these datasets cover the benchmark collection used throughout the study.

  • A.1. Description of Datasets: The first five datasets in the overview table come from Benchmarking GNNs.
  • A.1. Description of Datasets: The middle two datasets come from the Long-Range Graph Benchmark, while the final dataset comes from PCQM4Mv2.

B.2. Dataset splits and random seed

Experiments use standard benchmark splits and repeated random-seed runs, while hyperparameters follow established budgets without exhaustive search. Statistical comparisons use one-tailed two-sample t-tests against the second-best model.

  • Each dataset uses standard train/validation/test splits, with four runs at random seeds 0, 1, 2, and 3.
  • Hyperparameters were not exhaustively or grid searched because of limited time and computational resources.
  • The study follows common parameter budgets: up to 500k parameters for five benchmarks and 100k for MNIST and CIFAR10.
  • Final hyperparameter settings are reported in Tables 9 and 10.
  • Results are compared with the second-best model using a two-sample one-tailed t-test, drawing baselines from prior work with 10 or 4 runs.

B.5. Visualization for the Synthetic Experiment

The synthetic experiment tests whether a single attention layer can learn k-hop neighborhoods from positional encodings alone. GRIT most closely matches target sparsity and attention magnitudes, while other methods either diffuse attention or struggle to learn the target.

  • GRIT most successfully matches both the target sparsity pattern and attention magnitudes.
  • Transformer+RWSE struggles to learn attention to k-hop neighbors, whereas Graphormer+SPDPE attends to most targeted nodes but assigns residual attention elsewhere.
  • SAN+LapPE* better captures target attention scales but assigns high scores to multiple nodes outside the target neighborhoods.
  • GRIT and RRWP retain asymptotic costs of O(|V|^2) for attention and O(K|V||E|) for RRWP, matching common Graph Transformer attention complexity.
  • The accompanying runtime and GPU-memory reference compares SAN, GraphGPS, and GRIT on ZINC using batch size 32.

C.1. GD-WL

The GD-WL analysis establishes that RRWP positional encodings are at least as expressive as shortest-path distances and strictly stronger on a specific graph pair. The proofs construct MLPs that recover distances, propagation matrices, and adjacency-based functions, while also motivating BatchNorm because LayerNorm removes degree information.

  • GD-WL expressivity: GD-WL with RRWP is at least as strong as GD-WL with shortest-path distances.
  • GD-WL expressivity: RRWP is strictly stronger because it distinguishes the non-isomorphic Desargues and Dodecahedral graphs that shortest-path distances cannot distinguish.
  • RRWP and MLP: An MLP can approximate truncated shortest-path distances from RRWP entries, assigning distances below K and K to farther node pairs.
  • RRWP and MLP: The proof uses RRWP P(A) = [I, M, ..., M^(K−1)] and continuous MLP-approximable transformations to recover reachability and propagation functions.
  • RRWP and MLP: The same construction approximates weighted sums of powers of the random-walk matrix and adjacency-based functions such as θ0I + θ1A.
  • LayerNorm and degree information: LayerNorm removes degree information from sum-aggregated node representations, and the same conclusion applies to degree scalers.
Loading 2305.17589v1…