A Generalization of Transformer Networks to Graphs

By Vijay Prakash Dwivedi, Xavier Bresson. arXiv.org, 2020

1,129 citations recorded by the source corpus.

We propose a generalization of transformer neural network architecture for arbitrary graphs. The original transformer was designed for Natural Language Processing (NLP), which operates on fully connected graphs representing all connections between the words in a sequence. Such architecture does not leverage the graph connectivity inductive bias, and can perform poorly when the graph topology is important and has not been encoded into the node features. We introduce a graph transformer with four new properties compared to the standard model. First, the attention mechanism is a function of the neighborhood connectivity for each node in the graph. Second, the positional encoding is represented by the Laplacian eigenvectors, which naturally generalize the sinusoidal positional encodings often used in NLP. Third, the layer normalization is replaced by a batch normalization layer, which provides faster training and better generalization performance. Finally, the architecture is extended to edge feature representation, which can be critical to tasks s.a. chemistry (bond type) or link prediction (entity relationship in knowledge graphs). Numerical experiments on a graph benchmark demonstrate the performance of the proposed graph transformer architecture. This work closes the gap between the original transformer, which was designed for the limited case of line graphs, and graph neural networks, that can work with arbitrary graphs. As our architecture is simple and generic, we believe it can be used as a black box for future applications that wish to consider transformer and graphs.

Subfields: Artificial Intelligence, Materials Chemistry

View Paper: https://www.semanticscholar.org/paper/849b88ddc8f8cabc6d4246479b275a1ee65d0647

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Materials Chemistry

Citations in the corpus

Do Transformers Really Perform Bad for Graph Representation? (2021, methodology): “The original implementation of GT [13] employs a hidden dimension of 64 to reduce the total number of parameters.”
DiGress: Discrete Denoising diffusion for graph generation (2022, methodology): “We chose to extend the graph transformer network proposed by Dwivedi & Bresson (2021), as attention mechanisms are a natural model for edge prediction.”
PDFormer: Propagation Delay-aware Dynamic Long-range Transformer for Traffic Flow Prediction (2023, methodology): “In addition, the Transformer architecture performs well in representation learning, which has been demonstrated in recent studies (Dwivedi and Bresson 2020; Ren et al. 2021; Ren, Wang, and Zhao 2022; Jiang et al. 2023).”
Do Transformers Really Perform Badly for Graph Representation? (2021, methodology): “The original implementation of GT [13] employs a hidden dimension of 64 to reduce the total number of parameters.”
NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (2023, background): “While this latter scenario has been explored in the context of graph structure learning [38] and all-pair message passing design, e.g., graph Transformers [9], existing efforts do not scale to the large graphs endemic to node-level prediction.”
Long Range Graph Benchmark (2022, methodology): “For the baselines, we select GCN [33], GCNII [11], GINE [62, 28] and GatedGCN [8] models from the local MP-GNN class, and fully connected Transformer [58] with Laplacian PE (LapPE) [14, 13] and SAN [34] models from the Transformer class.”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, methodology): “However, these methods either use non-learnable PEs to encode graph structure information (Dwivedi & Bresson, 2021; Ying et al., 2021; Mialon et al., 2021), or inject learned PEs to the Transformer network that relies on Laplacian eigenvectors (Kreuzer et al., 2021), thus inheriting the sign…”
Language is All a Graph Needs (2023, methodology): “Three most powerful Transformer-based single-model graph learners on the two benchmarks, i.e., CoarFormer, Graphormer, and GT (Dwivedi and Bresson, 2020), are also considered as baseline for comparison.”
How Attentive are Graph Attention Networks? (2021, methodology): “…defined as: DPGAT (Vaswani et al., 2017): e (hi,hj) = (( h>i Q ) · ( h>j K )>) / √ dk (8) Variants of DPGAT were used in prior work (Gao and Ji, 2019; Dwivedi and Bresson, 2020; Rong et al., 2020a; Veličković et al., 2020; Kim and Oh, 2021), and we consider it here for the conceptual and…”
Equiformer: Equivariant Graph Attention Transformer for 3D Atomistic Graphs (2022, background): “A parallel line of research focuses on applying Transformer networks [78] to other domains like computer vision [9, 16, 73] and graph [18, 44, 85, 66] and has demonstrated widespread success.”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, methodology): “Global attention, however, requires nodes to be better identifiable within the graph and its substructures [13].”
EquiformerV2: Improved Equivariant Transformer for Scaling to Higher-Degree Representations (2023, positive): “…GNNs. Equivariant neural networks [5,7,11–18 , 31– 38] use equivariant irreps features built from vector spaces of irreducible representations ( irreps Invariant GNNs. Prior works [4,8,43–51] extract invariant information from 3D atomistic graphs and operate on the resulting graphs augmented…”
Structure-Aware Transformer for Graph Representation Learning (2022, methodology): “Examples of position-based methods include the Laplacian positional encoding (Dwivedi & Bresson, 2021; Kreuzer et al., 2021), Weisfeiler–Lehman-based positional encoding (Zhang et al., 2020), and random walk positional encoding (RWPE) (Li et al., 2020b; Dwivedi et al., 2022), while distance-based…”
Representing Long-Range Context for Graph Neural Networks with Global Attention (2022, methodology): “Recent works such as Zhang et al. [38], Rong et al. [24], and Dwivedi and Bresson [12] propose GNN layers that let nodes attend to other nodes in some surrounding neighborhood via Transformer-style attention, whereas we use self attention for a permutation-invariant, graph-level pooling or…”
Rethinking Graph Transformers with Spectral Attention (2021, methodology): “As a result, there is a growing interest in deep learning techniques that encode graph structure as a soft inductive bias, rather than as a hard-coded aspect of message passing [14, 24].”
Geometric Transformers for Protein Interface Contact Prediction (2021, methodology): “As shown in Figure 3, the Geometric Transformer expands upon the existing Graph Transformer architecture (Dwivedi & Bresson (2021)) by introducing ( 1 ) an edge initialization module, ( 2 ) an edge-wise positional encoding (EPE), and ( 3 ) a geometry-evolving conformation module employing repeated…”