Relational Attention: Generalizing Transformers for Graph-Structured Tasks

Cameron Diao, Ricky LoyndICLR 2023

Transformers have revolutionized AI, dominating tasks from natural language processing to image generation. However, they possess a persistent blind spot: they are fundamentally "set processors." They treat inputs as a collection of items, relying on positional encodings to understand sequences. When confronted with complex graph-structured data—where the relationships (edges) between entities (nodes) are as crucial as the entities themselves—standard Transformers often struggle compared to specialized Graph Neural Networks (GNNs).

In their ICLR 2023 paper, Cameron Diao and Ricky Loynd introduce Relational Attention, a mathematically elegant approach that elevates edges to "first-class citizens" within the Transformer architecture.

The Challenge of Graph Reasoning

While Transformers are highly expressive, they lack the relational inductive biases necessary to reason effectively over graphs. In a graph, an edge is rarely just a binary connection; it often carries rich data, such as the type of bond in a molecule or the distance between cities.

Standard GNNs handle this by passing messages strictly along edges, but they frequently lack the global reasoning power and optimization stability inherent to Transformers. Previous attempts to bridge this gap usually involved "flattening" graphs into sets or using edges merely as static bias terms in the attention matrix. The authors argue that for complex algorithmic reasoning, models require an architecture where nodes and edges can communicate and evolve together throughout the network layers.

Enter the Relational Transformer

The core innovation of this paper is the Relational Transformer (RT), which generalizes standard attention by conditioning node interactions on explicit edge features and updating those edges in every layer.

One layer of computation in the Relational Transformer, illustrating how node and edge representations are jointly updated.

In a standard Transformer, the Query ($Q$), Key ($K$), and Value ($V$) vectors for an interaction between node $i$ and node $j$ are derived solely from the node features. In the Relational Transformer, this process is fundamentally altered:

  1. Conditioned Attention: The $Q, K,$ and $V$ computations are conditioned on the directed edge vector $e_{ij}$ between the nodes. The node and edge vectors are concatenated before being projected (e.g., $q_{ij} = [n_i, e_{ij}]W^Q$).
  2. Maintained Efficiency: To keep the computational complexity at $O(N^2)$—matching a standard Transformer—the authors demonstrate that this can be implemented efficiently by projecting nodes and edges separately and summing the results.
  3. Dynamic Edge Updates: Unlike models that keep edge features static, the RT updates edge vectors in every layer. An edge $e_{ij}$ is updated based on its current value, the reverse edge $e_{ji}$, and the updated features of its two connected nodes ($n_i$ and $n_j$).
  4. Native Graph-to-Graph: By maintaining and updating an edge matrix, the model natively ingests and outputs graph structures without requiring complex encoding schemes.

Key Insights and Performance

The authors subjected the RT to a rigorous battery of tests, most notably the CLRS-30 Algorithmic Reasoning Benchmark, a suite of 30 classic computer science algorithms designed to test if a model can "reason" like a program.

Performance comparison on the CLRS-30 benchmark, showing the Relational Transformer (RT) significantly outperforming baseline GNNs.
  • State-of-the-Art on CLRS-30: The Relational Transformer achieved an average score of ~67% across all 30 tasks, representing a massive leap over the best-tuned GNN baselines (which hovered around 41-49%).
  • Dominance in Dynamic Programming (DP): The RT was particularly dominant in DP tasks. The authors discovered that many DP algorithms require storing and updating values on edges (like sub-problem costs). Standard GNNs, which focus primarily on node updates, struggle here. The RT excels because it treats edges as primary storage mechanisms.
  • Implicit Graph Discovery: In reinforcement learning tasks like Sokoban, the RT outperformed standard Transformers even when no explicit graph was provided. This suggests the model can "discover" and utilize latent relational structures in unstructured data.

Limitations and Future Directions

Despite its strong performance, the RT has limitations. It slightly underperformed on "Greedy" algorithms (like Activity Selector). The authors hypothesize this is because Transformers use "soft" attention (averaging), whereas greedy algorithms require "hard" discrete choices (like max-pooling), which GNNs handle more naturally.

Furthermore, while node attention is global, edge updates are currently "local" (only looking at immediate neighbors). Allowing edges to attend to other edges directly could be a powerful next step. Finally, while the model excels on algorithmic benchmarks, future work must evaluate its scalability on massive real-world datasets where the $O(N^2)$ complexity might pose a bottleneck.

Summary updated

BibTeX
@inproceedings{diao2023relational,
  author = {Cameron Diao and Ricky Loynd},
  title = {{Relational Attention: Generalizing Transformers for Graph-Structured Tasks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
}
Figure