wikillm

Paper · 2022-07-06 · cs.LG, cs.AI

Pure Transformers are Powerful Graph Learners

Treats every node and edge of a graph as one token, attaches orthogonal node labels and learned type labels to each token, and feeds the tokens to an unmodified Transformer (TokenGT). Theory: at least as expressive as 2-IGN, hence more than message-passing GNNs. On PCQM4Mv2, TokenGT (Lap) reaches 0.0910 validation MAE against 0.1083 for the best GNN baseline; author-reported.

Graph transformerPositional encodingEquivariance constraintGraph neural networkgraph-learninggraph-transformerexpressivenesspositional-encodingpure-transformer

arXivPDFCodeMarkdown14 min read

AI-compiled by claude-haiku-5-5 on 2026-11-13, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Most graph networks work by letting each node exchange messages with its neighbours. This paper asks what happens if that machinery is dropped. Every node and every edge becomes one item in a list, and a standard Transformer, the same kind of model used for text and images, reads the list. A Transformer alone cannot tell which items are linked, so each item carries two kinds of label. A node label says which node an item refers to, and a second label says whether the item is a node or an edge. With these labels the authors argue that the approach is at least as strong as a known family of graph networks. On a large set of molecules it beats the simple graph networks in its comparison table and is competitive with Transformers that were built specially for graphs. All numbers are the authors' own.

TL;DR

Plain Transformers can be used on graphs without graph-specific changes if each node and edge is a token and the tokens carry identifiers for their incidence and type. The authors prove this model is at least as expressive as 2-IGN and so more expressive than message-passing GNNs under the Gilmer et al. framework. On PCQM4Mv2 (3.7M molecules) the best variant (TokenGT with Laplacian node identifiers) is better than every GNN in the paper's table and slightly behind Graphormer. Quadratic attention cost over n+m tokens is the main drawback.

Problem

Graph Transformers usually add graph-specific pieces: attention restricted to neighbourhoods, message-passing layers next to global attention, or edge information injected as attention bias §1. The authors argue these pieces limit versatility and make it hard to reuse standard Transformer engineering such as linear attention §1. The question is whether an unmodified Transformer on node and edge tokens can work on graphs §1.

A naive version fails for a clear reason: giving the Transformer the node and edge features alone discards connectivity §2. The paper's fix is to add identifiers, and the cost is that attention runs over n+m tokens, so the asymptotic cost is O((n+m)^2) for softmax attention §6 §5.2 Table 2.

Method

The model is called Tokenized Graph Transformer (TokenGT). Overview in §2 and fig. 1. Appendix sections are cited by their LaTeX numbering (§7.x), since the source has no \appendix command; the compiled PDF was not checked for the same numbers. Notation: a graph has n nodes and m edges, with node features X^V (n × C) and edge features X^E (m × C). Each node and each edge is one token, so there are n+m tokens, stacked as X = [X^V; X^E] §2. Atom and bond features are looked up in embedding tables and summed over feature categories tokenizer.py.

Node identifiers P (n × d_p). P has n orthonormal rows. A node token v is augmented with [X_v, P_v, P_v]; an edge token (u, v) with [X_(u,v), P_u, P_v] §2. Two admissible choices are given: orthogonal random features (rows of a random orthogonal matrix from the QR decomposition of a Gaussian matrix) and Laplacian eigenvectors of I − D^(−1/2) A D^(−1/2) §2. ORF identifiers carry no structural information; the authors nevertheless report that the Transformer learns structure from them §2 §5.2.

Type identifiers E (2 × d_e), trainable. E^V is added to node tokens and E^E to edge tokens, so attention heads can separate node and edge tokens §2. The appendix sets d_e = d, the encoder width §7.3.1.

Input and encoder. The augmented token X^in ∈ R^((n+m) × (C + 2d_p + d_e)) is projected by a trainable matrix w^in to the model width d. A trainable [graph] token is prepended, and its output at the last layer is the graph representation, fed to a linear head §2. The encoder is a standard Transformer: alternating multi-head self-attention (MSA) and MLP layers §2 eq. 3. No attention bias or mask is added tokengt_graph_encoder.py, and the tokenizer does not use degree encodings: in-degree and out-degree are read but unused in the forward pass tokenizer.py.

Theory. Definitions: k-IGNs stack equivariant linear layers with activations, close with an invariant linear layer and an MLP eq. 1; an equivariant linear layer is a sum of basis tensors B^μ with weights, plus bias basis tensors C^λ eq. 2 §3.1. The Transformer's multi-head attention is the form in eq. 3 §3.2. Self-attention can approximate an equivariant basis tensor only if it is given auxiliary input that is orthonormal per node, and with the node identifiers of §2 Lemma 1 holds: the attention coefficients of the heads can approximate every basis tensor, up to normalisation §3.3. The first-order example is worked through with eq. 4 to eq. 6 §3.2. Theorem 1 gives approximation of an order-k equivariant layer by a Transformer layer with bell(2k) heads; Theorem 2 extends this to a k-IGN with T layers, sum pooling and an MLP; Corollaries 1 and 2 give at-least-as-expressive-as k-IGN, k-WL and all message-passing GNNs in the Gilmer et al. framework §3.3. The proofs are in the appendix §7.1.

Pseudocode for the tokens and the forward pass, following the paper's description §2 §7.3.3:

Pseudocode
# TokenGT tokens for one graph  [§2] [fig. 1]
# Input:  node_feats (n, C), edge_feats (m, C), edges (m, 2) node indices
#         node_ids (n, d_p) orthonormal, node_type (d_e,), edge_type (d_e,)
# Output: tokens (n + m, C + 2 d_p + d_e), before the projection w^in

def tokenize(node_feats, edge_feats, edges, node_ids, node_type, edge_type):
    # Node token [X_v, P_v, P_v, E^V] for every node v  [§2]
    node_tokens = concat(node_feats, node_ids, node_ids, node_type)
    # Edge token [X_(u,v), P_u, P_v, E^E] for every edge (u, v)  [§2]
    sources = node_ids[edges[:, 0]]            # (m, d_p)
    targets = node_ids[edges[:, 1]]            # (m, d_p)
    edge_tokens = concat(edge_feats, sources, targets, edge_type)
    # Stack node tokens above edge tokens  [§2]
    return concat(node_tokens, edge_tokens)    # (n + m, C + 2 d_p + d_e)
Pseudocode
# Forward pass  [§2] [§7.3.3]
# Input:  tokens from tokenize(), a trainable graph_token of shape (d,)
# Output: one scalar prediction per graph

def tokengt_forward(tokens, graph_token):
    # Project tokens to the model width d  [§2]
    hidden = tokens @ w_in                     # (n + m, d)
    # Prepend the trainable [graph] token  [§2]
    hidden = concat(graph_token, hidden)       # (1 + n + m, d)
    # Pre-LayerNorm encoder layers, 12 in total  [§7.3.3]
    for layer in encoder_layers:
        # Multi-head self-attention, with a residual  [§7.3.3] [eq. 3]
        hidden = hidden + attention(layer_norm(hidden))
        # Feed-forward MLP, with a residual  [§7.3.3]
        hidden = hidden + mlp(layer_norm(hidden))
    # Linear head on the [graph] token  [§2]
    return head(hidden[0])                     # scalar

Node identifiers, per the appendix §7.3.1:

Pseudocode
# Orthonormal node identifiers P, shape (n, d_p)  [§2] [§7.3.1]
# ORF: rows of a random orthogonal matrix from a Gaussian matrix  [§2]
# Laplacian: eigenvectors of the normalised graph Laplacian  [§2]

def orf_node_ids(n, d_p):
    # QR of an n x n Gaussian matrix gives a random orthogonal Q  [§2]
    gauss = random_normal(n, n)                # (n, n)
    q = qr_decomposition(gauss).q              # (n, n), orthonormal
    # Zero-pad if n < d_p; keep d_p channels if n > d_p  [§7.3.1]
    return pad_or_keep(q, d_p)                 # (n, d_p)

def lap_node_ids(adjacency, d_p):
    # Laplacian I - D^(-1/2) A D^(-1/2)  [§2]
    d_inv_sqrt = diag(degree(adjacency) ** -0.5)  # (n, n)
    lap = identity(n) - d_inv_sqrt @ adjacency @ d_inv_sqrt
    # Eigenvectors of the d_p smallest eigenvalues  [§7.3.1]
    values, vectors = eigendecompose(lap)      # ascending values
    return vectors[:, :d_p]                    # (n, d_p)

Hyperparameters

Main PCQM4Mv2 models (TokenGT and the ablation), unless noted §5.2 §7.3.3:

NameValueWhereNotes
encoder layers12§5.2 §7.3.3
hidden dimension d768§5.2 §7.3.3
attention heads32§5.2 §7.3.3head dimension 24 §7.3.3
FFN widthnot stated§7.3.3MLP is two linear layers with GELU §7.3.3; code uses 768 tokengt.py
normalisationPreLN§7.3.3see Paper vs code on the final norm
ORF dimension d_p64§7.3.3pcqv2-orf.sh
Laplacian dimension d_p16§7.3.3eigenvectors with smallest eigenvalues §7.3.1
eigenvector sign fliprandom, training only§7.3.1tokenizer.py
eigenvector dropout (Lap)0.2§7.3.3channel dropout, as in ConvNets §7.3.1
attention dropout0.1§7.3.3
MLP (activation) dropout0.1§7.3.3
stochastic depthlinear, to 0.1 at the last layer§7.3.3tokengt_graph_encoder.py
optimizerAdamW§5.2betas (0.99, 0.999) in the text; script uses (0.9, 0.999), see Paper vs code
weight decay0.1§5.2 §7.3.3
peak learning rate2e-4§7.3.3
warmup60k iterations§5.2 §7.3.3
schedulelinear decay over 1M iterations§5.2 §7.3.3to 0 in text; to 1e-9 in script
batch size1024§5.2script uses 128 per GPU on 8 GPUs (inferred from §5.2 hardware) pcqv2-lap.sh
gradient clippingglobal norm 5.0§7.3.3
lossL1 (MAE)§7.3.3
training budgetabout 3 days on 8 RTX 3090§5.2
fine-tuned Performer0.1M steps, 1k warmup, cosine§5.2script uses 200k max updates, see Paper vs code

Synthetic second-order basis experiment §7.3.2: a single multi-head self-attention layer, hidden d = 1024, bell(4) = 15 heads, head dimension 128, d_p = 24 (ORF) or 20 (Laplacian), AdamW, 3k steps, linear warmup for 1k steps to peak 1e-4 then linear decay, input dropout 0.1, L2 loss between each head's attention and its normalised basis tensor, batch sizes 512 (sparse) and 256 (dense). Data: 1152 training and 128 test Barabási–Albert graphs with 10 to 20 nodes §7.3.2.

Results

Author-reported. Synthetic second-order basis approximation, tab. 1 §5.1, mean and standard deviation of L2 error over heads over 3 runs; ○ marks a type identifier present, × absent. "Dense" uses all n² pairs as tokens, "sparse" uses only the m present edges §5.1.

node id.type id.train L2 densetest L2 densetrain L2 sparsetest L2 sparse
××47.95 ± 0.60053.93 ± 1.42629.88 ± 0.45034.70 ± 1.167
×○32.38 ± 0.44840.06 ± 1.20215.92 ± 0.27520.39 ± 0.765
Random (first-order)○32.19 ± 0.47632.49 ± 3.68715.87 ± 0.24716.56 ± 0.904
ORF (first-order)○32.35 ± 0.36939.87 ± 1.26315.87 ± 0.24716.56 ± 0.908
Random×5.909 ± 0.0195.548 ± 0.0908.152 ± 0.0428.270 ± 0.285
ORF×5.472 ± 0.0355.143 ± 0.0787.167 ± 0.0257.190 ± 0.217
Laplacian eigenvector×1.899 ± 3.0501.702 ± 2.9120.288 ± 0.0190.064 ± 0.010
Random○0.375 ± 0.0090.234 ± 0.0110.990 ± 0.1080.875 ± 0.042
ORF○0.080 ± 0.0010.009 ± 5e-50.129 ± 0.0020.011 ± 0.002
Laplacian eigenvector○0.053 ± 1.5e-50.005 ± 1e-40.101 ± 0.0030.019 ± 0.007

The authors read this as support for Lemma 1: approximation is accurate only with orthonormal node identifiers and type identifiers together, and non-orthogonal random identifiers approximate poorly §5.1.

PCQM4Mv2 large-scale regression, tab. 2 §5.2: MAE, lower is better. Validation MAE is the main metric; test-dev MAE where the authors could get it. "N/A" means not reported.

ModelParamsValid MAETest-devComplexity
GCN2.0M0.13790.1398O(n + m)
GIN3.8M0.11950.1218O(n + m)
GAT6.7M0.1302N/AO(n + m)
GCN-VN4.9M0.11530.1152O(n + m)
GIN-VN6.7M0.10830.1084O(n + m)
GAT-VN6.7M0.1192N/AO(n + m)
GAT-VN (large)55.2M0.1361N/AO(n + m)
Graphormer48.3M0.0864N/AO(n²)
EGT89.3M0.08690.0872O(n²)
GRPE46.2M0.08900.0898O(n²)
Transformer (no identifiers)48.5M0.2340N/AO((n+m)²)
TokenGT (ORF)48.6M0.0962N/AO((n+m)²)
TokenGT (Lap)48.5M0.09100.0919O((n+m)²)
TokenGT (Lap) + Performer48.5M0.0935N/AO(n+m)

Setup: PCQM4Mv2 from OGB-LSC, 3.7M molecular graphs, atom and bond types as features §5.2 §7.3.3. Average graph size: 14.1 nodes and 14.6 edges §7.3.2. The "Transformer" row is the ablation with neither node nor type identifiers §5.2. The paper states TokenGT is slightly behind Graphormer and the other graph-specific Transformers on validation MAE §5.2 §7.5.

Attention distance by head and depth, fig. 3 §5.2: early layers mix local and global heads, deeper layers attend globally. The authors note this resembles vision Transformers §5.2.

Paper vs code

Official repository: https://github.com/jw9730/tokengt, cloned at commit bb767583c8036e018a7055263dc0458ed4c445b7. The abstract links it, which is why it is used. The LICENSE file is MIT; its copyright line names Microsoft Corporation, and the tokenizer and encoder files say they are modified from Graphormer tokengt.py. Treat code_license as MIT as the file says; the attribution to upstream Graphormer code is worth keeping in mind.

Differences found:

  • Optimizer betas. The text gives AdamW with (β1, β2) = (0.99, 0.999) §5.2. The training scripts use adam with betas (0.9, 0.999) pcqv2-lap.sh.
  • Final learning rate. The text says linear decay to 0 §5.2. The scripts set end learning rate 1e-9 pcqv2-lap.sh.
  • Fine-tuning length. The text gives 0.1M steps for the Performer fine-tune §5.2. The script sets --max-update 200000 pcqv2-lap-performer-finetune.sh.
  • ORF truncation. The appendix says that when n > d_p, ORF keeps a random subset of d_p channels §7.3.1. The code keeps the first d_p columns and then re-normalises each row to unit length tokenizer.py. Because the matrix is random, keeping the first columns or a random subset gives the same distribution (my reading); the re-normalisation after dropping columns is not described in the text.
  • Prediction head. The text describes a linear prediction head §2. The code applies a Linear, GELU, LayerNorm, then a bias-free Linear to one output, plus a learned scalar bias, to the [graph] token tokengt.py.
  • Final layer norm. The text says PreLN puts layer normalisation before the output projection after the last layer §7.3.3. The code creates final_layer_norm for PreLN tokengt_graph_encoder.py but never applies it in the encoder forward, which returns the [graph] token of the last hidden state directly tokengt_graph_encoder.py.
  • Special tokens. The text mentions only the [graph] token §2. The code always prepends a second, [null], token tokenizer.py tokenizer.py; it is used in the synthetic experiment §7.3.2 and is present in the PCQM model too.
  • Identifier injection. The text concatenates identifiers and type identifiers before w^in §2. The code adds separate projections of each part to the token embedding tokenizer.py. With bias-free linear maps these are equivalent; the type identifier is an embedding lookup, which equals a one-hot linear map.
  • Type identifier rule. The code sets the type to "node" when the two indices of a token are equal tokenizer.py. The text defines node tokens as (v, v). They coincide, but an edge token whose two endpoints are the same node would also get the node type. The text does not discuss self-loops.
  • Laplacian degrees. The code uses in-degree clipped at 1 in the normalised Laplacian algos.py. Isolated nodes therefore get degree 1. The text does not say this.
  • Synthetic experiment. The appendix gives d_p = 24 (ORF) and 20 (Laplacian) §7.3.2. The scripts pass --orf_node_id_dim 48 sparse-orf-type.sh and --lap_node_id_dim 40 dense-lap-type.sh. The scripts' default batch sizes are 128 and 64, while the appendix gives 512 (sparse) and 256 (dense) §7.3.2; I did not check whether individual runs override the default.
  • Loss in the synthetic experiment. The code sums squared differences between each head's attention and the normalised basis tensor, divides by batch size times the number of structures, and logs the log of the per-structure sum train.py. The text says "L2 loss" §5.1, and the table's "L2 error" is not defined further.
  • Sign flip and dropout at evaluation. Both are gated on training mode tokenizer.py tokenizer.py. The text does not say how evaluation is done.
  • Randomness at evaluation. The ORF identifiers are sampled inside forward on every call, with no seed or caching tokenizer.py. The text does not say so.

No further discrepancies found in the attention, encoder layer or criterion code beyond those listed. The criterion is an L1 loss with sum reduction, normalised by the number of graphs l1_loss.py. I found no target standardisation in the criterion.

Pitfalls

  • Orthonormality needs d_p ≥ n. The proof uses P_i^T P_j = 1 if i = j and 0 otherwise §3.2. That needs n orthonormal rows in R^(d_p), so d_p must be at least n. The model uses d_p = 64 (ORF) and 16 (Laplacian) §7.3.3. The average PCQM graph has 14.1 nodes §7.3.2, so the Laplacian setting is truncated for every graph above 16 nodes; the size distribution is not given. Truncated identifiers are no longer orthonormal, and the theory does not cover this case. The paper does not discuss it.
  • Theory is for dense tensors; experiments use sparse tokens. The theorems use dense n^k tensors, and the authors say the sparse form is "interchangeable but slightly different" §3.1. The sparse case with identifiers is tested empirically, not proven.
  • Approximation only up to normalisation. Softmax rows sum to one, so the head approximates each basis tensor only up to row normalisation. The proofs use an MLP after attention to undo this §3.2 §3.3. An implementation without that denormalisation step does not carry the expressiveness guarantee.
  • Head count versus basis count. The construction needs bell(2k) = 15 heads per layer for k = 2 §3.3 §7.3.2. The PCQM models use 32 heads §5.2. The construction fits inside that, but the trained model is not forced to use one head per basis tensor.
  • Lap sign ambiguity at test time. Eigenvectors are sign-flipped only during training tokenizer.py. At evaluation the sign is whatever the eigensolver returns, so validation numbers depend on that choice. The authors list sign ambiguity as a known problem §7.5.
  • ORF is random at evaluation. Each forward call draws new orthogonal matrices tokenizer.py. Validation MAE for ORF models is therefore a random quantity unless the seed is fixed. This matters for comparing the ORF row of tab. 2 with the Laplacian row.
  • Edge count convention. The authors say an undirected edge is used as two directed tokens, which doubles the edge tokens and adds redundancy §7.5. The paper does not say whether the reported average of 14.6 edges counts each bond once or twice §7.3.2. Token counts, and so cost, depend on that.
  • Quadratic cost. Softmax attention over n+m tokens costs O((n+m)²) §6 §5.2. The linear-cost variant uses kernelised attention (Performer). It needs a separate fine-tune from the softmax checkpoint, and the fine-tune length in the text and in the script differ (see Paper vs code).
  • No structural bias in the model. The encoder passes no attention bias or mask tokengt_graph_encoder.py. Structure enters only through the identifiers. Models that add shortest-path or edge-type bias (Graphormer, EGT, GRPE) are a different design.
  • Validation versus test. Several rows have no test-dev number tab. 2. Compare validation MAE within the table and treat test-dev as partial.
  • Author-reported numbers. All results are the authors' own, with the 3-day, 8-GPU budget §5.2. The fp16 setting in the scripts pcqv2-lap.sh is not stated in the text.
  • High variance in one synthetic row. The Laplacian row without type identifiers has train L2 1.899 ± 3.050 tab. 1. The mean is not a reliable summary there.

Lineage

  • Builds on: Graphormer, the Transformer configuration §5.2 and code base tokengt.py; second-order invariant graph networks (2-IGN, k-IGN) and their expressiveness results §3.1 §3.3; Laplacian eigenvector positional encodings §2; orthogonal random features §2.
  • Compared against: GCN, GIN, GAT and virtual-node variants tab. 2; Graphormer, EGT and GRPE tab. 2; Performer for linear attention §5.2.
  • Superseded by: not stated in this paper. The authors suggest more powerful node positional encodings and single tokens per undirected edge as future work §7.5.

Source and license

Adapted from “Pure Transformers are Powerful Graph Learners” by Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, Seunghoon Hong (arXiv:2207.02505), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/jw9730/tokengt at commit bb767583c803 (MIT). Any quoted code is shown under that license.