Graph transformer

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 2106.05234 §1 2110.07875 §2. The fourth, D3G, runs the other way: the graph is the output, not the input 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 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 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).

Variants

Structural attention bias (Graphormer)

The model is an ordinary pre-LN Transformer encoder with three additions 2106.05234 §3.1–3.2:

• a learned in-degree and out-degree vector per node, added to the input features 2106.05234 eq. 5;
• a learned scalar per shortest-path distance, added to the attention score of each node pair 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 2106.05234 eq. 7.

A virtual graph token is connected to every node, and its final state is the graph representation 2106.05234 §3.2. Card: Do Transformers Really Perform Bad for Graph Representation?.

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 2106.05234 tab. 1–3 app. B.2.2–B.2.3. The ZINC result uses a smaller model of about 489K parameters 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 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 2110.07875 §3.1 tab. 3. Two of the tested models are fully connected Transformer GNNs: SAN and GraphiT 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 2110.07875 app. C.2.1–C.2.2. Card: Graph Neural Networks with Learnable Structural and Positional Representations.

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 and 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 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 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 2306.08385 §3.3 eq. 8, and an edge-likelihood term is added to the loss 2306.08385 §3.4 eq. 9–10. Both are used only when an input graph exists 2306.08385 fig. 1. The paper's targets are node-level tasks on large graphs and on data with no graph at all 2306.08385 §1 §2. Card: NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification.

The author-reported results are: 77.45 ± 1.15 ROC-AUC on OGB-Proteins, against 74.63 ± 1.24 for GraphSAINT-GAT 2306.08385 tab. 2; and 87.85 ± 0.24 accuracy on Amazon2M, against 83.90 ± 0.10 for GCN 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 2306.08385 tab. 2–3. The edge term matters most on Cora, where removing it lowers accuracy from 88.69 to 81.98 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 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 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 2409.02035 §4.3 eq. 5–9. Card: A Modern Take on Visual Relationship Reasoning for Grasp Planning.

The authors built the D3GD bin-picking benchmark on MetaGraspNetV2, with synthetic Easy, Medium and Hard splits and a set of real test images 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 2409.02035 tab. 3. On the synthetic-to-real split, D3G reaches 24.44, and the best baseline, EGTR, reaches 15.11 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) 2409.02035 tab. 6.

The ablations move the results less than the scene split does. The four edge initialisations in 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 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 2407.09777 §3.1. It splits attention into global quadratic, global linear and local mechanisms 2407.09777 §3.2. It then groups published models into shallow, deep, scalable and pre-trained types 2407.09777 §4. In that grouping, Graphormer is deep 2407.09777 §4.2 and NodeFormer is scalable 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

The survey's design guide 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 and not repeated here.

# 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

# 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 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 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 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 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 2409.02035 §4.3. Pick one and document it.
• D3G's text and code name different softmax axes for the attention matrix 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 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 2409.02035 §5.

Contradictions

• SAN on ZINC. The LSPE paper reports SAN without positional encoding at 0.181 ± 0.004 with 10 layers 2110.07875 tab. 1. Its comparison table quotes SAN at 0.139 ± 0.006 2110.07875 tab. 2. Graphormer's baseline table also quotes SAN at 0.139 ± 0.006 with 508K parameters 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 2106.05234 §3.2. The released ZINC and PCQM4M scripts train with post-LN unless a flag is set 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 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 2407.09777 §3.2.1. NodeFormer computes the key sums once and reuses them for every query, which gives linear cost per layer 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 2409.02035 tab. 5 and 76.27 in 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?: 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: 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: kernelized Gumbel-Softmax attention with random features, linear in the node count, learning a sparse latent graph per layer.
• Graph Transformers: A Survey: 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: D3G, a DETR-style detector with a dense graph transformer that predicts dependencies between object queries, plus the D3GD bin-picking benchmark.