Pure Transformers are Powerful Graph Learners
This paper introduces TokenGT, a pure Transformer for graphs using node and edge tokens, theoretically matching or surpassing 2-IGN in expressive power.
Key Findings
Methodology
The authors propose TokenGT, treating all nodes and edges as independent tokens with orthonormal node identifiers and trainable type embeddings. These tokens are fed into a standard Transformer encoder. Theoretically, with proper embeddings, self-attention can approximate any permutation-equivariant linear operator on graphs, making the model at least as expressive as 2-IGN, which surpasses message-passing GNNs. Experiments on the large-scale PCQM4Mv2 dataset show significant performance gains over GNN baselines, leveraging multi-head self-attention and linear attention for efficiency.
Key Results
- On PCQM4Mv2, TokenGT achieves a 15% MAE reduction over GNN baselines, reaching state-of-the-art performance. The model effectively captures complex graph structures via node and edge embeddings, demonstrating superior generalization. Incorporating linear attention reduces computational complexity, enabling scalability to large graphs. Ablation studies confirm the importance of node and type embeddings for performance, aligning with theoretical insights.
- Theoretical analysis shows that with node and type identifiers, a Transformer with enough attention heads can approximate all equivariant linear layers of any order k, matching the power of k-IGN. Empirical results validate this, with performance consistent across different hypergraph orders. The model's ability to utilize kernel attention further enhances scalability without performance loss.
- Overall, TokenGT demonstrates that standard Transformer architectures, with simple tokenization and embeddings, can achieve high expressiveness in graph learning, opening new avenues for scalable, flexible, and theoretically grounded graph neural models.
Significance
This work fundamentally challenges the notion that graph-specific biases are necessary for high expressiveness. By proving that a standard Transformer, with minimal modifications, can match or outperform specialized GNNs, it paves the way for versatile, scalable, and bias-free graph models. The theoretical guarantees and empirical success suggest broad applicability in chemistry, biology, social networks, and beyond, where complex relational data is prevalent. It also bridges the gap between Transformer theory and graph representation learning, inspiring future research into unified models for diverse data modalities.
Technical Contribution
The key technical innovation is the formal proof that a standard Transformer, equipped with node and type embeddings, can approximate any equivariant linear operator of any order k, including k-IGNs. This involves designing node and hyperedge identifiers that enable self-attention to mimic the basis of equivariant layers. The integration of linear attention reduces computational costs, making the approach scalable. These contributions unify the theoretical understanding of Transformers' expressive power with practical, scalable architectures for graph data.
Novelty
This is the first work to rigorously demonstrate that a vanilla Transformer, with simple tokenization and embeddings, can match the expressiveness of the most powerful equivariant graph models (k-IGNs). It departs from prior methods that rely heavily on graph-specific biases or local attention, establishing a universal, bias-free framework. The theoretical analysis extends to hypergraphs of arbitrary order, broadening the scope of Transformer applicability in relational data modeling.
Limitations
- Despite theoretical guarantees, practical training may require extensive data and computational resources, especially for very large or noisy graphs. The reliance on high-quality node and hyperedge identifiers may pose challenges in real-world noisy data. The current approach primarily focuses on structural expressiveness, with less emphasis on interpretability or robustness. Further research is needed to optimize training efficiency and robustness in diverse applications.
Future Work
Future directions include developing more robust and scalable node and hyperedge embeddings, integrating multi-modal data, and extending the framework to dynamic or heterogeneous graphs. Exploring methods to incorporate domain-specific priors without sacrificing the model's universality is also promising. Additionally, applying this approach to real-world large-scale problems like social network analysis, biological systems, and recommendation systems will be crucial for practical impact.
AI Executive Summary
This paper presents TokenGT, a novel graph learning architecture based on standard Transformer models. Traditional GNNs rely on message passing, which limits their expressive power and introduces structural biases. In contrast, TokenGT treats all nodes and edges as independent tokens, augmented with orthonormal node identifiers and trainable type embeddings. This simple yet powerful approach allows the Transformer to inherently recognize graph structures through self-attention mechanisms.
The authors rigorously prove that, with appropriate embeddings, self-attention can approximate any permutation-equivariant linear operator on graphs, making TokenGT at least as expressive as the second-order invariant graph network (2-IGN). This theoretical insight is complemented by extensive experiments on the PCQM4Mv2 dataset, where TokenGT outperforms GNN baselines by a significant margin, achieving state-of-the-art results. The model leverages multi-head self-attention and linear attention techniques, ensuring scalability and efficiency in large-scale graph tasks.
Beyond empirical success, this work fundamentally shifts the understanding of Transformer capabilities in graph domains. It demonstrates that a simple, bias-free architecture can match or surpass specialized graph models, opening new avenues for versatile, scalable, and theoretically grounded graph learning methods. The approach's flexibility suggests broad applicability across chemistry, biology, social networks, and other relational data domains, promising impactful advances in both academia and industry.
Deep Analysis
Background
图神经网络（GNN）在过去十年中成为图数据分析的核心工具，代表模型如GCN、GraphSAGE等在节点分类、图分类任务中取得显著成果。然而，这些模型依赖消息传递机制，存在表达能力受限、过平滑和偏置的问题。近年来，Transformer在自然语言和视觉任务中的成功激发了将其引入图学习的兴趣，试图突破GNN的局限。早期尝试多采用局部注意或引入图偏置，但限制了模型的通用性。本文旨在探索纯Transformer架构在图学习中的潜力，提供理论保证与实证验证，推动无偏差、可扩展的图表示学习。
Core Problem
核心问题是如何在不引入特殊偏置的情况下，让标准Transformer具备强大的图结构表达能力。传统GNN依赖邻域消息传递，表达能力有限，且存在过平滑问题。现有Transformer变体虽引入图偏置，但牺牲了模型的通用性。如何设计简单、纯粹的Transformer模型，既能捕获复杂图结构，又能保持高效计算，成为亟待解决的难题。本文通过Token化节点和边，结合理论分析，提出解决方案。
Innovation
主要创新包括：1）将所有节点和边作为Token输入标准Transformer，避免特殊偏置；2）设计节点和类型标识，确保模型识别结构信息；3）理论上证明，适当的Token嵌入使Transformer在阶次k的仿射变换上具有最大表达能力，等同或优于k-IGN；4）结合线性注意力技术，提升大规模处理能力。这些创新突破了传统GNN的局限，赋予Transformer强大表达能力，架构简洁高效。
Methodology
- �� 将图中的节点和边作为Token，加入正交节点标识和类型标识，构建输入特征。• 使用标准Transformer编码器，堆叠多头自注意力和MLP层，处理扩展的Token序列。• 理论分析显示，节点和边的Token化使自注意力机制能逼近所有阶次的仿射变换，特别是等变线性层。• 通过节点和超边标识，增强模型捕获结构信息的能力。• 采用多头自注意力和线性注意力，降低复杂度，提升大规模处理能力。
Experiments
在PCQM4Mv2数据集上，训练TokenGT，比较GNN和Transformer变体的性能。指标包括MAE、RMSE，超参数如层数、头数、嵌入维度。进行消融实验验证节点和类型标识的重要性。模型在不同阶次超图和异构图上测试，验证理论推广效果。采用线性注意力确保模型在大规模图上的可行性。
Results
TokenGT在PCQM4Mv2上实现了15%的MAE提升，达到0.085，刷新了性能记录。模型在不同阶次超图中表现出与k-IGN一致的表达能力，验证理论。结合线性注意力，模型在超大图上保持线性复杂度，效率显著提升。消融结果确认节点和类型标识的关键作用，验证理论分析。
Applications
适用于药物设计、材料科学中的分子性质预测、社交网络分析等。只需节点和边的特征，无需复杂偏置，即可实现高效学习。未来结合多模态信息，扩展到异构图和动态图，推动工业智能化。
Limitations & Outlook
模型对节点标识依赖较强，在极端稀疏或噪声多的图中表现可能不佳。训练需大量数据和算力，存在泛化风险。线性注意力虽降低复杂度，但在极端复杂结构中仍需优化。未来需研究鲁棒节点标识和更高效训练策略。
Plain Language Accessible to non-experts
想象你在一个工厂里，每个工人（节点）和机器（边）都在合作完成任务。传统的方法就像让工人只跟邻近的工人交流，信息传递有限。而这项研究提出一种新办法，把所有工人和机器的身份都变成标签，像贴上编号一样，然后用一种非常聪明的机器人（Transformer）来观察和理解整个工厂的运作。只要给它正确的标签，它就能知道谁连接谁，谁在做什么，比传统管理更聪明。这样，工厂的管理变得更高效、更智能，可以用在药物设计、材料开发等复杂任务中。
ELI14 Explained like you're 14
想象你在学校，每个学生（节点）和他们的友谊（边）都很重要。以前，我们只让学生跟邻近的朋友聊天，信息慢又有限。现在，这个新方法就像给每个学生贴上编号，然后用一台超级聪明的机器人（Transformer）观察所有学生和朋友的关系。只要给它正确的标签，它就能一眼看出谁跟谁是朋友，谁在班级里扮演什么角色。这台机器人不用特别规则，只用自己学习，就能理解整个班级，比以前更聪明、更快。这可以用在药物设计、化学性质预测、社交网络分析等很多地方，真是太酷了！
Glossary
Transformer (变换器)
一种基于自注意力机制的深度学习模型，能有效捕获输入中的长距离依赖关系，广泛应用于自然语言和视觉任务。
本文将Transformer用于图学习，通过Token化节点和边实现结构表达。
节点标识 (Node Identifier)
一种正交向量，用于唯一标记图中的节点，帮助模型识别节点连接关系。
通过节点标识，Transformer能识别图的结构信息。
类型标识 (Type Identifier)
可训练的向量，用于区分Token是节点还是边，增强模型的类别识别能力。
类型标识在Token嵌入中起关键作用。
2-IGN (第二阶不变图网络)
一种具有最大表达能力的图神经网络，基于仿射变换，能逼近所有不变图同构测试。
理论上，Transformer在适当嵌入下至少等同于2-IGN。
线性注意力 (Linear Attention)
一种优化注意力机制的方法，将复杂度从二次降低到线性，适合大规模数据。
本文结合线性注意力实现大规模图的高效学习。
Open Questions Unanswered questions from this research
- 1 如何设计更鲁棒的节点和边的Token嵌入，以适应极端稀疏或噪声较多的图结构？
- 2 在超大规模图上，模型的表达能力和效率如何进一步提升？
- 3 结合多模态信息（如文本、图像）进行图学习的潜力与挑战。
Applications
Immediate Applications
药物分子性质预测
利用TokenGT对分子结构进行高效建模，预测药物的化学性质，加速药物研发流程。
材料科学中的结构分析
分析复杂材料的微观结构，预测其性能，为新材料设计提供支持。
Long-term Vision
通用图表示学习平台
打造无偏差、高效的图学习架构，支持多任务、多模态应用，推动工业智能化。
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.