Overview
A molecule can be represented as a graph with atoms for nodes and bonds for edges. Flatten it into a list of atoms and bonds and their connections can disappear. TokenGT gives each node a mathematical identifier and copies the endpoint identifiers onto each edge. A standard Transformer can then use attention to recover the connections and learn which of them matter for predicting a molecular property.
Key Findings
Can a plain Transformer tell which atoms are bonded?
Picture a molecule written out as a list of atoms and bonds, the way a sentence is a list of words. Hand that list to a standard Transformer and something essential vanishes, because nothing says which bond joins which atoms. Moontae and his colleagues asked whether a small amount of extra information could restore that structure without changing the Transformer at all. Their answer is the Tokenized Graph Transformer, or TokenGT. Every node and every edge becomes one token. Each token receives two additions, which the authors call node identifiers and type identifiers.
Giving every node an address
A node identifier is a vector assigned to each node, and the vectors for different nodes are orthonormal, meaning each has unit length and any two are perpendicular. A node token carries its own identifier twice. An edge from to carries the identifiers of its two endpoints. The authors point out that a dot product between an edge token and a node token then reveals incidence. In their notation, equals 1 exactly when node is one of the edge's endpoints and 0 otherwise. Attention is built from dot products, so a Transformer can see the connections.
The paper offers two ways to produce identifiers. Orthogonal random features are rows of a random orthogonal matrix and carry no information about the graph beyond distinctness. Laplacian eigenvectors come from the graph's normalized Laplacian and encode how far apart nodes sit. The authors note these eigenvectors generalize sinusoidal position embeddings, since a chain graph's eigenvectors are sines and cosines. The type identifier is a trainable vector that marks a token as node or edge, which lets an attention head focus on one kind of token. For graph-level predictions, the model prepends a special graph token, as in BERT and the Vision Transformer. Figure 1 shows the node tokens, edge tokens, and their identifiers.
Why attention heads can imitate symmetry-respecting layers
The theory asks how expressive this setup is. Relabeling a graph's nodes should not change its meaning, so useful layers respect that symmetry. The authors build on invariant graph networks, which stack every linear layer that respects node permutations. Such a network of order is written
where each is an equivariant linear layer, is an activation function, and is an invariant linear layer that collapses everything to one output (their Eq. 1). Each such layer is a sum over binary basis tensors, and for graphs () there are of them.
The authors' intuition starts small. For a set of items, the layer has two basis tensors, the identity and . With orthonormal identifiers and a large scaling factor on queries and keys, the attention matrix approaches (their Eq. 5). Flipping the sign gives the other basis up to row normalization (Eq. 6). Lemma 1 extends this to every basis tensor of any order , and Theorem 1 shows that a Transformer layer with heads approximates an equivariant linear layer to arbitrary precision, using an MLP to undo the normalization. Theorem 2 stacks layers, adds sum-pooling and an MLP, and approximates a whole -IGN. The corollaries follow. The model is at least as expressive as a -IGN and as the -dimensional Weisfeiler-Lehman isomorphism test, and for graphs it exceeds all message-passing networks in the Gilmer framework. The proofs treat dense tensors, and the authors extend the framework to hypergraphs with order- hyperedges.
Testing the mechanism on random graphs
A synthetic experiment checks Lemma 1 directly. The authors generate 1,280 Barabási-Albert random graphs, 1,152 for training and 128 for testing, averaging about 15 nodes. One attention layer with 15 heads is trained to match each of the 15 normalized basis tensors, with attention error measured by L2 loss. Table 1 reports test L2 error on dense input, averaged over 3 runs. Lower is better.
| Node identifiers | Type identifier | Test L2 (dense) |
|---|---|---|
| None | No | 53.93 |
| None | Yes | 40.06 |
| Random | Yes | 0.234 |
| ORF | Yes | 0.009 |
| Laplacian | Yes | 0.005 |
Only the combination of orthonormal identifiers and type identifiers yields accurate approximation. Plain random vectors do worse, which shows orthogonality matters. Sampling a fresh identifier for each token, instead of reusing endpoint identifiers, also fails, which supports the incidence argument. The learned attention maps transfer to unseen graphs nearly perfectly with the strongest identifier settings. Figure 2 shows which heads recover the target attention patterns. One caveat sits in the table. Laplacian identifiers without type identifiers show a large spread across runs on dense input (). On sparse input, ORF edged out Laplacian in test error ( against ).
Molecules at scale
The main benchmark is PCQM4Mv2, a quantum chemistry regression set of 3.7 million molecular graphs, averaging 14.1 nodes. TokenGT uses a 12-layer encoder with 768 hidden dimensions and 32 heads, trained for 1 million steps on 8 RTX 3090 GPUs for about 3 days. Table 2 reports validation mean absolute error.
| Method | Parameters | Valid MAE |
|---|---|---|
| GIN-VN | 6.7M | 0.1083 |
| Graphormer | 48.3M | 0.0864 |
| Transformer, no identifiers | 48.5M | 0.2340 |
| TokenGT (ORF) | 48.6M | 0.0962 |
| TokenGT (Lap) | 48.5M | 0.0910 |
| TokenGT (Lap) + Performer | 48.5M | 0.0935 |
Without identifiers the Transformer fares poorly. With random identifiers alone, TokenGT already beats every message-passing baseline in the table, which the authors call somewhat surprising. Laplacian identifiers improve it further, and the test-dev score is 0.0919. Graphormer, EGT, and GRPE still score lower, and the authors acknowledge this, attributing it partly to keeping the design faithful to the theory. Because TokenGT leaves attention unmodified, a kernel method called Performer can replace it. The authors load the trained Laplacian model and fine-tune for 100,000 steps, which reaches 0.0935 at linear cost in nodes plus edges, the best among linear-cost models in the table. Graphormer-style attention bias requires quadratic cost.
What the heads learn, and where it stretches
The authors also measured attention distance, the average graph hop count between tokens weighted by attention. In early layers some heads stay local like message passing and others look globally. Deeper layers attend mostly globally, echoing the pattern in vision Transformers. Laplacian-based models show more varied heads than random-identifier models. Figure 3 tracks the attention distances across layers.
An appendix tests node classification on six graphs with up to about 34,000 nodes, where Graphormer ran out of memory on Physics. Near-orthonormal random identifiers replace exact ones when nodes outnumber dimensions, and a small added operation called the sparse equivariant basis helps. The best TokenGT variant wins on all datasets except Computers, where it is on par with the best model. The authors list quadratic cost, the gap to the top PCQM4Mv2 scores, and untested efficient attention variants as open problems.
Questions & Answers
Q: Why include bonds as tokens if they already connect the atoms?
A: Bonds can have their own features and can participate directly in attention. Encoding their endpoint identifiers gives other tokens a way to recognize which atoms and bonds share a node.
Q: Does the theorem guarantee that training finds an equivariant solution?
A: The theorem establishes that appropriate settings can approximate the equivariant operations. Training can learn different attention patterns and has its own optimization and data constraints.
Q: Why do random identifiers work at all?
A: The vectors can be random and still be orthogonal. Reusing the same vector for a node wherever it appears lets attention test equality and recover incidence. Laplacian identifiers add a positional signal from the graph and improved the reported validation result.
Q: What costs can a graph identifier introduce before attention even starts?
A: Exact orthonormal identifiers require at least as many coordinates as nodes. Laplacian features also require preprocessing. The molecular benchmark gives evidence for the practical implementation at its reported sizes, while the dense construction in the proof has different computational requirements. A larger graph comparison should count identifier construction, attention memory, and runtime independently.
Future Ideas
A graph model with a measured latency budget for circuit review
Represent a bounded circuit block as component and connection tokens. A connection across several pins can use an order- hyperedge token or be split into pin-level edges. Exact orthonormal identifiers require a dimension at least as large as the number of nodes, which makes bounded circuit blocks a practical starting point. Compare a topology-agnostic baseline, a message-passing model, and an incidence-token Transformer for ranking netlist fragments for engineer review. Train on labeled historical checks and split the test set by circuit family so that copied design patterns do not inflate the estimate.
Use the same features for every model. Measure recall within an engineer’s review budget and record latency, peak memory, and preprocessing separately across graph sizes. Include node relabeling and degree-shift tests. A practical deployment would use the model to prioritize review and retain the existing deterministic checks.
Sources
- NeurIPS 2022 paper record
- arXiv revision 2 with the proof, Figure 1, and Table 2
- Authors’ TokenGT implementation
Original abstract
We show that standard Transformers without graph-specific modifications can lead to promising results in graph learning both in theory and practice. Given a graph, we simply treat all nodes and edges as independent tokens, augment them with token embeddings, and feed them to a Transformer. With an appropriate choice of token embeddings, we prove that this approach is theoretically at least as expressive as an invariant graph network (2-IGN) composed of equivariant linear layers, which is already more expressive than all message-passing Graph Neural Networks (GNN). When trained on a large-scale graph dataset (PCQM4Mv2), our method coined Tokenized Graph Transformer (TokenGT) achieves significantly better results compared to GNN baselines and competitive results compared to Transformer variants with sophisticated graph-specific inductive bias. Our implementation is available at https://github.com/jw9730/tokengt.