Source-linked AI summary
Transformers are Graph Neural Networks
Chaitanya K. Joshi
TL;DR
The paper asks how Transformers relate to GNNs for representation learning on structured data. It formalizes Transformers as message-passing GNNs on fully connected token graphs, with self-attention modeling token relationships and positional encodings supplying structural hints. The connection explains both their expressive flexibility and their practical advantage from efficient dense hardware operations.
Problem
The paper examines the relationship between Transformer representation learning and graph neural networks for structured data.
Method
The paper establishes a formal equivalence between Transformer multi-head attention and message passing on fully connected graphs, incorporating positional encodings as structural information.
Results
Transformers are expressive set-processing networks that capture local and global relationships without requiring predefined sparse graph structure, while dense operations are more hardware-efficient than sparse message passing.
Takeaways & Limitations
Transformers can serve as flexible architectures for representation learning on structured data, including graphs, and have motivated Graph Transformers combining local message passing with global attention.
Abstract
from arXiv · showhide
We establish connections between the Transformer architecture, originally introduced for natural language processing, and Graph Neural Networks (GNNs) for representation learning on graphs. We show how Transformers can be viewed as message passing GNNs operating on fully connected graphs of tokens, where the self-attention mechanism capture the relative importance of all tokens w.r.t. each-other, and positional encodings provide hints about sequential ordering or structure. Thus, Transformers are expressive set processing networks that learn relationships among input elements without being constrained by apriori graphs. Despite this mathematical connection to GNNs, Transformers are implemented via dense matrix operations that are significantly more efficient on modern hardware than sparse message passing. This leads to the perspective that Transformers are GNNs currently winning the hardware lottery.
1 Transformers for Natural Language Processing
Transformers build token representations in parallel through attention, replacing sequential RNN processing with scalable mechanisms that capture relationships among words. Their multi-head architecture combines diverse token interactions with token-wise feed-forward processing.
- Representation learning: The architecture supports expressive and scalable representation learning, which underpins predictive and generative machine learning tasks.Deep neural networks compress statistical and semantic information into latent representations, while general-purpose representations can transfer across related tasks.
- From RNNs to Transformers: Transformers build word representations in parallel, computing each word’s importance relative to every other word.This contrasts with RNNs, which process words sequentially and can struggle with long contexts.
- The attention mechanism: Attention updates each token by weighting value representations according to pairwise importance scores normalized across all sentence tokens.The weights are computed from transformed representations using a dot product followed by softmax normalization.
- Multi-head attention: Multi-head attention learns separate query, key, and value transformations, allowing simultaneous modeling of syntactic, semantic, and contextual relationships.The outputs of the heads are concatenated and projected back to the original representation dimension.
- Transformer layers: A Transformer layer processes attention-updated token representations through residual connections, layer normalization, and a token-wise multilayer perceptron.Modern variants may use SwiGLU activations and apply normalization before attention and feed-forward sub-layers.
2 Graph Neural Networks for Representation Learning on Graphs
Graphs represent interconnected systems as nodes with attributes and edges, while GNNs learn node representations by exchanging and aggregating messages over graph neighborhoods. Attention-based GNNs extend this process by weighting neighbors according to their importance.
- Graph representations: Graphs model complex systems as nodes connected by edges, with node attributes stored in H and connectivity represented by adjacency matrix A.Each adjacency entry indicates whether an edge connects nodes i and j; N_i lists node i’s neighbors.
- Graph representations: Graph learning must respect permutation symmetry because graph nodes have no canonical ordering and can be shuffled without changing the graph.The corresponding permutation acts on both the rows and columns of A and the node representations H.
- Message passing: GNNs update node representations through message construction, neighborhood aggregation, and an update using the aggregated message and previous representation.Messages capture relationships between node i and neighbor j; an MLP can construct each message, while a permutation-invariant operator combines them.
- Message passing: Permutation-invariant aggregation with operators such as sum, mean, or max preserves graph symmetry because neighbor order does not affect the result.Stacking message-passing layers propagates information beyond immediate neighbors and captures multi-hop relationships.
- Graph attention: Graph Attention Networks weight different neighbors during aggregation, learning which neighbors matter more for each node.Multi-head attention computes multiple sets of weights in parallel, allowing different relationship aspects to be learned.
- Graph attention: GAT attention equations are almost identical to the Transformer mechanism that computes the relative importance of words in a sentence.This provides a direct connection between attention-based graph message passing and Transformer attention.
3 Transformers are GNNs over Fully Connected Graphs
The paper establishes a formal equivalence between Transformer multi-head attention and message passing on fully connected graphs. This perspective explains Transformers' expressive, unconstrained modeling of relationships and motivates Graph Transformers.
- Transformer multi-head attention can be instantiated directly within the message-passing framework of Graph Attention Networks.
- On a complete token graph, self-attention computes relative token importance, aggregates weighted messages, and updates each token representation with a feedforward network.
- The resulting update equations are exactly the same as those introduced for the Transformer architecture.
- Transformers capture local and global context without being constrained by predefined sparse graph structure, supporting expressive set processing.
- Graph Attention Networks can conversely be viewed as Transformers whose attention is restricted to local neighborhoods through sparse or masked attention.
- Positional encodings softly inject graph structure into Transformer blocks, motivating Graph Transformers that combine local message passing with global attention.
4 Transformers are GNNs Winning the Hardware Lottery
Although Transformers are mathematically equivalent to GNNs on fully connected graphs, their dense implementations are better matched to modern accelerator hardware. This hardware efficiency, together with scalable expressivity and learned structural biases, underlies their prominence for structured-data representation learning.
- Transformers are GNNs over fully connected graphs, but their practical implementation differs substantially from typical sparse GNN message passing.
- Dense matrix multiplication lets Transformers compute global multi-head attention in parallel on modern GPUs and TPUs.
- Multi-head projections and subsequent token-wise operations can also be parallelized across heads and tokens.
- Sparse GNN message passing is substantially less efficient on current GPUs for typical problem scales, except on very sparse or billion-scale graphs.
- At sufficient scale, Transformers can learn GNN-like inductive biases such as locality when given suitable positional encodings.
- Transformers are therefore characterized as GNNs currently winning the hardware lottery.