Graph Transformers: A Survey

Area of Science:

• Machine Learning
• Artificial Intelligence
• Graph Theory

Background:

• Graph-structured data is prevalent in many domains.
• Traditional models struggle with complex graph relationships.
• Transformers excel at sequence modeling but need adaptation for graphs.

Purpose of the Study:

• To provide a comprehensive review of graph transformers.
• To analyze design principles and integration of graph features.
• To classify existing graph transformer models and identify future research directions.

Main Methods:

• Review of foundational concepts in graph learning and transformers.
• Analysis of architectural designs integrating graph inductive biases and attention.
• Development of a taxonomy for classifying graph transformers.
• Discussion of applications and challenges.

Main Results:

• Graph transformers show strong performance across node, edge, and graph-level tasks.
• Key design considerations include inductive biases and attention mechanisms.
• A taxonomy based on depth, scalability, and pretraining is proposed.
• Identified challenges include scalability, robustness, and interpretability.

Conclusions:

• Graph transformers represent a significant advancement in machine learning for graph data.
• Further research is needed to address challenges in scalability, generalization, and interpretability.
• The field holds great potential for diverse applications.