--- kind: concept slug: graph-transformer title: Graph transformer summary: >- A graph transformer runs self-attention over a graph's nodes and adds structure: as attention biases (Graphormer), as learned positional vectors on Transformer GNNs (LSPE), as a per-layer latent graph with linear-cost attention (NodeFormer), or as a predicted pairwise graph over detected objects (D3G). Full attention grows with the square of the node count. All numbers are author-reported. tags: [graph-learning, transformer, graph-level-prediction, node-classification, molecular-graph, positional-encoding, attention-bias, linear-complexity, shortest-path-distance, random-walk-encoding, relation-prediction, grasp-planning] papers: ["2106.05234", "2110.07875", "2306.08385", "2407.09777", "2409.02035"] related: [graph-neural-network, positional-encoding, attention-mechanism, self-attention, linear-attention, random-feature-approximation, molecular-representation-learning, scene-graph-generation, object-queries, bipartite-matching] status: draft updated_at: 2026-10-25 --- ## Overview A graph transformer applies self-attention to the nodes of one graph. Plain self-attention compares nodes only by their features, so it cannot see the graph's shape. Three of the four variants below therefore add structural information to the attention or to the node inputs [arxiv:2106.05234 §1] [arxiv:2110.07875 §2]. The fourth, D3G, runs the other way: the graph is the output, not the input [arxiv:2409.02035 §4.2]. Message-passing GNNs are the usual alternative. A Transformer is a message-passing GNN on a fully connected graph with no edge features [arxiv:2110.07875 §3.1], so the two families share one design space. Five cards on wikillm list this concept. They differ in what they add and in the task they target. Graphormer and LSPE add structure to all-pairs attention for graph-level prediction, mostly on molecules. NodeFormer targets node classification on one large graph and keeps the cost linear in the node count. D3G applies dense attention over the object queries of a detector to predict which objects depend on which, for robot picking. The survey [arxiv:2407.09777] sorts the design choices and the published models into categories; it runs no experiments. The numbers come from the papers themselves, and the comparisons use different parameter budgets, tasks and training settings (see [Contradictions](#contradictions)). ## Variants ### Structural attention bias (Graphormer) The model is an ordinary pre-LN Transformer encoder with three additions [arxiv:2106.05234 §3.1–3.2]: - a learned in-degree and out-degree vector per node, added to the input features [arxiv:2106.05234 eq. 5]; - a learned scalar per shortest-path distance, added to the attention score of each node pair [arxiv:2106.05234 eq. 6]; - an edge term, which averages the edge features along one shortest path with learned weights and adds the result to the attention score [arxiv:2106.05234 eq. 7]. A virtual graph token is connected to every node, and its final state is the graph representation [arxiv:2106.05234 §3.2]. Card: [Do Transformers Really Perform Bad for Graph Representation?](/papers/2106.05234). The paper's molecular results come from large models: a PCQM4M-LSC regression model (47.1M parameters) and fine-tuned models for MolHIV and MolPCBA, the latter with FLAG augmentation [arxiv:2106.05234 tab. 1–3] [app. B.2.2–B.2.3]. The ZINC result uses a smaller model of about 489K parameters [arxiv:2106.05234 tab. 4]. It also shows that a GNN layer such as GIN, GCN or GraphSAGE can be written as a Graphormer layer with suitable weights [arxiv:2106.05234 §3.3] [app. A]. ### Fully connected Transformer GNNs with learned positional encodings (LSPE) LSPE gives each node a second, positional stream. Its starting values are random-walk return probabilities (RWPE) or Laplacian eigenvectors (LapPE). The stream is updated in every layer, and the card records the RWPE variant as the one that works best [arxiv:2110.07875 §3.1] [tab. 3]. Two of the tested models are fully connected Transformer GNNs: SAN and GraphiT [arxiv:2110.07875 app. C.2]. For SAN, the attention over all node pairs is split into existing and non-existing edges, weighted by a balance scalar. For GraphiT, the attention weights are multiplied by a diffusion kernel [arxiv:2110.07875 app. C.2.1–C.2.2]. Card: [Graph Neural Networks with Learnable Structural and Positional Representations](/papers/2110.07875). On ZINC with about 500K parameters, RWPE with LSPE lowers the test MAE of SAN from 0.181 to 0.104 and of GraphiT from 0.181 to 0.106 [arxiv:2110.07875 tab. 1]. The same paper also tests sparse GNNs with LSPE (GatedGCN and PNA). Those sparse variants are not Transformers, so they belong to the [graph neural network](/concepts/graph-neural-network) and [positional encoding](/concepts/positional-encoding) pages. ### Latent-graph attention with linear cost (NodeFormer) Every node can pass messages to every other node in each layer, but the cost per layer is linear in the node count. The softmax kernel is approximated with positive random features, so the sums over all nodes are computed once and reused for every query [arxiv:2306.08385 §3.1 eq. 3–5]. Gumbel noise on the attention logits, scaled by a temperature τ, makes each layer draw a sparse latent graph, and the output is averaged over K draws [arxiv:2306.08385 §3.1 eq. 6–7] [alg. 1]. If the data comes with a graph, an observed edge adds a learned, squashed scalar to the attention weight [arxiv:2306.08385 §3.3 eq. 8], and an edge-likelihood term is added to the loss [arxiv:2306.08385 §3.4 eq. 9–10]. Both are used only when an input graph exists [arxiv:2306.08385 fig. 1]. The paper's targets are node-level tasks on large graphs and on data with no graph at all [arxiv:2306.08385 §1] [§2]. Card: [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](/papers/2306.08385). The author-reported results are: 77.45 ± 1.15 ROC-AUC on OGB-Proteins, against 74.63 ± 1.24 for GraphSAINT-GAT [arxiv:2306.08385 tab. 2]; and 87.85 ± 0.24 accuracy on Amazon2M, against 83.90 ± 0.10 for GCN [arxiv:2306.08385 tab. 3]. Replacing the Gumbel step with an ordinary softmax at the same τ = 0.25 costs about 1.3 points on OGB-Proteins and 0.3 on Amazon2M, and those rows still beat the baselines [arxiv:2306.08385 tab. 2–3]. The edge term matters most on Cora, where removing it lowers accuracy from 88.69 to 81.98 [arxiv:2306.08385 tab. 6]. ### Dense graph transformer that predicts object relations (D3G) D3G has no input graph. A DETR-style detector produces N object queries, and a dense graph transformer then fills an N x N table that says, for each ordered pair, whether one object rests on the other [arxiv:2409.02035 §4.1–4.2]. Each layer keeps a feature for every pair of queries. Attention scores are multiplied by an edge projection and the edge features are updated from them [arxiv:2409.02035 §4.2 eq. 1–4]. Only the edge features of the last layer are read out, through a small MLP that gives one logit per pair [arxiv:2409.02035 §4.2]. Training matches queries to ground-truth objects with the Hungarian algorithm, then applies a binary cross-entropy to the matched sub-matrix [arxiv:2409.02035 §4.3 eq. 5–9]. Card: [A Modern Take on Visual Relationship Reasoning for Grasp Planning](/papers/2409.02035). The authors built the D3GD bin-picking benchmark on MetaGraspNetV2, with synthetic Easy, Medium and Hard splits and a set of real test images [arxiv:2409.02035 §3] [tab. 1]. On AP_rel, the author-reported values are 76.27 (DETR) and 76.96 (Deformable DETR) on Synth Easy, against 73.29 for VMRN. On Synth Hard they are 43.99 and 46.45, against 42.49 [arxiv:2409.02035 tab. 3]. On the synthetic-to-real split, D3G reaches 24.44, and the best baseline, EGTR, reaches 15.11 [arxiv:2409.02035 tab. 3]. On the standard VMRD benchmark the D3G models have the best mAP (96.66 for the Deformable variant) and the best IA and OP for the DETR variant, while GGNN has the best OR (90.09) [arxiv:2409.02035 tab. 6]. The ablations move the results less than the scene split does. The four edge initialisations in [arxiv:2409.02035 tab. 4] lie within about 1.2 points of each other on Easy, Medium and Hard, and the chosen pairwise concatenation is the lowest of the four on Medium. Across the six graph configurations in [arxiv:2409.02035 tab. 5], Easy AP_rel ranges from 73.38 to 76.77, and Medium from 54.84 to 60.00. The survey distinguishes four ways graph structure can reach attention: a positional term on each node, a structural term on each edge, a message-passing step placed alongside attention, and a direct change to the attention scores [arxiv:2407.09777 §3.1]. It splits attention into global quadratic, global linear and local mechanisms [arxiv:2407.09777 §3.2]. It then groups published models into shallow, deep, scalable and pre-trained types [arxiv:2407.09777 §4]. In that grouping, Graphormer is deep [arxiv:2407.09777 §4.2] and NodeFormer is scalable [arxiv:2407.09777 §4.3]. The survey gives no numbers of its own, and its tables record the authors' reading of the original papers. ## When to use which | Situation | Use | Why | |---|---|---| | Plain Transformer code base, no custom kernels | Structural attention bias | The bias is added to the attention scores, so a standard attention layer can take it [arxiv:2106.05234 eq. 6–7]. | | Large molecular data set and pre-training is possible | Structural attention bias | The paper's strongest molecular results come from a pre-trained model on PCQM4M-LSC [arxiv:2106.05234 tab. 1–3]. | | About 500K parameters on ZINC | Structural attention bias, if the parameter count is binding | Graphormer-Slim reaches 0.122 MAE at 489K parameters [arxiv:2106.05234 tab. 4]. SAN and GraphiT with RWPE reach 0.104 and 0.106 at about 588K parameters, against 0.181 for each without positional encoding [arxiv:2110.07875 tab. 1]. The papers use different training setups, so do not rank them directly. | | Sparse graph where accuracy on ZINC matters most | Sparse GNN with LSPE (not a transformer) | GatedGCN-LSPE reports the lowest ZINC MAE in the LSPE paper, 0.090 [arxiv:2110.07875 tab. 2]. | | Positional vectors must not carry an arbitrary sign | RWPE rather than LapPE | Laplacian eigenvectors have sign ambiguity and need random sign flips in training. RWPE has no sign ambiguity [arxiv:2110.07875 §2] [§3.1]. | | One large graph, labels on nodes, memory is binding | NodeFormer | Cost per layer is linear in the node count [arxiv:2306.08385 §3.1 eq. 5]. The paper trains in mini-batches of 10,000 to 100,000 nodes [arxiv:2306.08385 §4.2]. Its gains are author-reported. | | Graph edges are missing, noisy or absent (for example image or text features) | NodeFormer, with or without a kNN graph | On Mini-ImageNet the no-graph run scores 87.46 against 86.77 with a k = 5 kNN graph. On 20News it scores 64.71 against 66.01 [arxiv:2306.08385 tab. 4]. The best choice depends on the data. | | Large graphs with graph-level labels | Check before use | Attention over all node pairs scales with the square of the node count. The Graphormer paper names this as a limitation and leaves large graphs to future work [arxiv:2106.05234 §6] [app. D]. NodeFormer's linear cost is shown for node-level tasks only [arxiv:2306.08385 §2]. | | Predicted dependency or relation graph over a few detected objects, graph is the output (for example, which object must be removed first) | D3G-style dense graph transformer over object queries | Each pair's answer can use the other objects, not only the two objects' crops of the image [arxiv:2409.02035 §1] [§4.2]. Author-reported AP_rel on D3GD is above the pair-pooling baselines in every synthetic split [arxiv:2409.02035 tab. 3]. | | Scenes with few objects, where the relation gap is small | Compare with the pair-pooling baseline first | On Synth Easy, VMRN scores 73.29 against 76.27–76.96 for D3G [arxiv:2409.02035 tab. 3]. The gap widens with clutter: on Hard, 42.49 against 43.99–46.45. | | Memory is binding and the scene needs more queries than the paper's test scenes (up to 35 objects) | Check before use | The edge tensor is N x N x F per sample, so memory grows with the square of the query count. The paper's efficiency claim is about compute, not memory [arxiv:2409.02035 §3] [§4.2]. | The survey's design guide [arxiv:2407.09777 §6] suggests shallow models with 2–4 layers below 10³ nodes and deeper models with 6–12 layers above 10⁵ nodes. It gives no source for these numbers and leaves 10³ to 10⁵ nodes unaddressed. Treat them as rules of thumb. ## Implementation sketch The common core is one Transformer over `N` nodes plus one graph token, with an extra bias added to the attention scores. The bias comes from structure. The Graphormer bias is shown. An LSPE variant would instead add a learned positional stream to the node inputs and update it in each layer. D3G does not fit this core: its edge features are the output, so its layer is shown in its [card](/papers/2409.02035) and not repeated here. ```pseudocode # Graphormer forward pass [arxiv:2106.05234 §3.1] [§3.2] # Input: nodes (N, F); in_degree (N,); out_degree (N,); spd (N, N) # path_edges (N, N, path length, d_E) # Output: one prediction per graph def graphormer(nodes, in_degree, out_degree, spd, path_edges): # Degree encoding: add learned in- and out-degree vectors [eq. 5] h = nodes + in_degree_table[in_degree] + out_degree_table[out_degree] # Prepend the virtual graph token [§3.2] h = concat(graph_token, h) # (N + 1, d) # Build the attention bias once; every layer reuses it [§3.1] bias = build_attention_bias(spd, path_edges) # (heads, N+1, N+1) for layer in layers: h = graphormer_layer(h, bias) # Read the prediction from the graph token [§3.2] return head(h[0]) # head not stated # Structural bias: spatial term plus edge term [arxiv:2106.05234 eq. 6–7] def build_attention_bias(spd, path_edges): # One learned scalar per shortest-path distance value [eq. 6] spatial = spatial_table[spd] # (N, N) # Graph token gets its own learned scalar [§3.2] spatial = pad_with_virtual_scalar(spatial) # (N+1, N+1) # Average over the path of edge feature . learned weight [eq. 7] edge = mean_over_path(path_edges, edge_weights) # (N, N) return spatial + pad(edge) # One pre-LN layer [§3.2] [eq. 8] [eq. 9] def graphormer_layer(h, bias): h = h + multi_head_attention(layer_norm(h), bias) h = h + feed_forward(layer_norm(h)) # inner size d return h ``` ```pseudocode # Linear all-pairs attention with random features [arxiv:2306.08385 §3.1] # Input: q, k, v (N, d); tau; omega (m, d) random directions # Output: (N, d), one message per node from all nodes def linear_all_pairs(q, k, v, tau, omega): # Scale queries and keys by sqrt(tau) before the feature map [eq. 7] q = q / sqrt(tau) k = k / sqrt(tau) # Positive random features of each query and key [eq. 4] qf = random_features(q, omega) # (N, m) kf = random_features(k, omega) # (N, m) # Gumbel step (training only): scale each key feature by exp(g / tau) # with g ~ Gumbel(0, 1), one draw per node [eq. 7] [alg. 1] # Sums over all nodes are computed once and reused by every query [eq. 5] kv = kf.T @ v # (m, d) z = kf.sum(axis=0) # (m,) return (qf @ kv) / (qf @ z)[:, None] # (N, d) ``` Notes that the cards give for implementers: - The released code uses per-head scalars and a 5-hop edge cut-off, and it adds the graph-token distance to both its row and column [arxiv:2106.05234 Paper vs code]. The paper's formulas do not state the cut-off. - LSPE's RWPE is computed once per graph. It is the diagonal of the return probabilities of `RW = A D^-1` for `k` steps [arxiv:2110.07875 §3.1] [eq. 10]. - NodeFormer's random-feature count `m` is not fixed in its main text, and the paper says small τ needs a large `m` for an accurate approximation [arxiv:2306.08385 §3.2]. Tune the two together and report both. - NodeFormer's repository has no license file, so take the method from the paper's equations rather than from its code. The [card](/papers/2306.08385) lists where the released code differs. - D3G's relation loss is a sum over the P x P pairs in eq. 9. The released code uses a mean, multiplied back by the number of matched objects, so the two loss scales differ [arxiv:2409.02035 §4.3]. Pick one and document it. - D3G's text and code name different softmax axes for the attention matrix [arxiv:2409.02035 §4.2]. The ground-truth matrix in the code is the transpose of the stored dependency matrix, multiplied by −1, so check the direction against the stored graphs before training [arxiv:2409.02035 §4.3]. - D3G thresholds the relation output at 0.5 after the sigmoid, which fixes OR and OP. AP_rel sweeps only the detection confidence, so the threshold is not tuned by it [arxiv:2409.02035 §5]. ## Contradictions - **SAN on ZINC.** The LSPE paper reports SAN without positional encoding at 0.181 ± 0.004 with 10 layers [arxiv:2110.07875 tab. 1]. Its comparison table quotes SAN at 0.139 ± 0.006 [arxiv:2110.07875 tab. 2]. Graphormer's baseline table also quotes SAN at 0.139 ± 0.006 with 508K parameters [arxiv:2106.05234 tab. 4]. The LSPE card does not say whether 0.139 comes from the original SAN paper or from a rerun, so the two SAN values are not reconciled here. - **Layer norm placement.** Graphormer's text describes pre-LN [arxiv:2106.05234 §3.2]. The released ZINC and PCQM4M scripts train with post-LN unless a flag is set [arxiv:2106.05234 Paper vs code]. The paper does not say which setting produced the reported numbers. - **Batch size and learning rate.** Graphormer's ZINC table lists batch 256 and 40K warm-up steps, while the released script uses batch 64 and 60K warm-up steps [arxiv:2106.05234 Paper vs code]. - **Cost of linear attention.** The survey's linear-attention formula still sums over all `N` keys in the denominator for every query, which is the quadratic pattern [arxiv:2407.09777 §3.2.1]. NodeFormer computes the key sums once and reuses them for every query, which gives linear cost per layer [arxiv:2306.08385 §3.1 eq. 5]. This page does not pick one form; check the cited paper before implementing either. - **D3G Easy AP_rel.** The S = 2, L = 2 configuration scores 76.77 on Easy in [arxiv:2409.02035 tab. 5] and 76.27 in [arxiv:2409.02035 tab. 3] and [tab. 4]. The other columns agree across the tables. This page does not resolve which Easy value is correct. ## Papers - [Do Transformers Really Perform Bad for Graph Representation?](/papers/2106.05234): Graphormer, a Transformer with degree, shortest-path and edge-path attention biases and a virtual graph token. - [Graph Neural Networks with Learnable Structural and Positional Representations](/papers/2110.07875): LSPE, a learned positional stream with RWPE or LapPE starts, applied to sparse GNNs and to the fully connected SAN and GraphiT. - [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](/papers/2306.08385): kernelized Gumbel-Softmax attention with random features, linear in the node count, learning a sparse latent graph per layer. - [Graph Transformers: A Survey](/papers/2407.09777): taxonomy of how graph structure enters attention and of shallow, deep, scalable and pre-trained models; no experiments. - [A Modern Take on Visual Relationship Reasoning for Grasp Planning](/papers/2409.02035): D3G, a DETR-style detector with a dense graph transformer that predicts dependencies between object queries, plus the D3GD bin-picking benchmark.