AutoGT: Automated Graph Transformer Architecture Search

Zizhao Zhang, Xin Wang, Chaoyu Guan, Ziwei Zhang, Haoyang Li, Wenwu ZhuICLR 2023 · OpenReview

TL;DR

AutoGT is the first Neural Architecture Search (NAS) framework specifically designed for Graph Transformers. By jointly optimizing the model's internal architecture and its graph-specific encoding strategies through a novel "encoding-aware" supernet training process, it consistently outperforms state-of-the-art hand-crafted models like Graphormer across diverse benchmarks.

What Problem Does This Paper Address?

While Transformers have revolutionized NLP and Computer Vision, applying them to graphs is tricky. Graphs are non-Euclidean; unlike words in a sentence or pixels in an image, nodes in a graph don't have a natural "order." To fix this, researchers developed Graph Transformers (GTs), which use special "encodings" (like Laplacian eigenvectors or centrality scores) to help the model understand graph topology.

However, designing a state-of-the-art Graph Transformer currently requires immense human expertise. Designers must manually choose both the neural architecture (number of layers, heads, dimensions) and the encoding strategies (how to represent node positions and edge relationships). These two components are tightly "coupled"—a specific architecture might work great with one encoding but fail with another. Existing automated search methods for Transformers ignore these graph-specific encodings, leaving a significant gap in automating graph-based machine learning.

Methods

The authors introduce AutoGT, which automates the design process through three key innovations:

1. Unified Search Space

They developed a mathematical formulation that encompasses almost all existing SOTA Graph Transformers. The search space includes five architectural hyperparameters (layers, hidden dimensions, etc.) and seven distinct graph encoding strategies.

Unified Graph Transformer Architecture

2. Encoding-Aware Supernet Training

In standard NAS, a "supernet" is trained once to represent all possible models. However, the authors found that different graph encodings change the "meaning" of the weights so much that a single supernet produces unreliable performance estimates. To solve this, they gradually split the supernet into eight specialized subnets based on combinations of attention map augmentations. This provides a much more accurate "fine-grained" prediction of how a specific model will actually perform.

Encoding-Aware Supernet Training Process

After training the subnets, AutoGT uses an evolutionary algorithm (mutation and crossover) to efficiently navigate the massive search space and identify the optimal combination of architecture and encoding for a specific dataset.

Datasets

The researchers evaluated AutoGT on nine diverse graph classification datasets:

  • TUDatasets: Five relatively small-scale benchmarks (COX2_MD, BZR_MD, PTC_FM, DHFR_MD, PROTEINS).
  • Large-Scale: The DBLP dataset.
  • Open Graph Benchmark (OGB): Three molecular property prediction datasets (OGBG-MolHIV, OGBG-MolBACE, OGBG-MolBBBP).

These datasets range from hundreds to tens of thousands of graphs, testing the model's ability to generalize across different scales and domains (chemistry, social networks, etc.).

Key Insights and Ideas

  • The Coupling Effect: The most significant insight is that architecture and encoding cannot be optimized in isolation. The "encoding-aware" strategy acknowledges that the data representation (encoding) fundamentally alters how the neural operations (architecture) should behave.
  • Subnet Splitting over One-Shot: Moving away from a single "one-shot" supernet to a "split" supernet approach significantly reduces the noise in performance estimation. This allows the search algorithm to find "hidden gems" that a standard NAS might overlook.
  • Automated vs. Hand-Crafted: The results suggest that human bias in design (e.g., always using 8 heads or specific positional encodings) often leads to sub-optimal performance. AutoGT frequently finds non-intuitive combinations that work better for specific data distributions.

Key Results

AutoGT achieved state-of-the-art results across the board:

  • Superior Accuracy: On the PROTEINS dataset, AutoGT reached 77.17% accuracy, significantly higher than the hand-crafted Graphormer (75.29%).
  • OGB Performance: On OGBG-MolHIV, AutoGT achieved an AUC of 74.95%, outperforming all standard baselines like GIN and GraphSAGE.
  • Efficiency: While searching is more expensive than a single training run, the total time cost for AutoGT was only about 7 times the cost of training a single Graphormer. Given that manual tuning often takes weeks of trial and error, this is a highly efficient trade-off.
  • Ablation Success: The authors proved that their "supernet splitting" was vital; without it (the "One-Shot" variant), performance dropped by over 1.2% on the PROTEINS dataset.

Limitations and Future Work

  • Computational Overhead: Although 7x training time is reasonable for research, it may still be a barrier for teams with very limited GPU resources or for extremely large-scale graphs.
  • Task Specificity: This paper focuses primarily on graph classification. Future work could extend AutoGT to node-level tasks (like node classification in citation networks) or link prediction.
  • Heterogeneous Graphs: The current search space is designed for homogeneous graphs. Adapting the framework for heterogeneous graphs (where nodes and edges have different types) remains an open challenge.

Summary updated

Abstract

Although Transformer architectures have been successfully applied to graph data with the advent of Graph Transformer, current design of Graph Transformer still heavily relies on human labor and expertise knowledge to decide proper neural architectures and suitable graph encoding strategies at each Transformer layer. In literature, there have been some works on automated design of Transformers focusing on non-graph data such as texts and images without considering graph encoding strategies, which fail to handle the non-euclidean graph data. In this paper, we study the problem of automated graph Transformer, for the first time. However, solving these problems poses the following challenges: i) how can we design a unified search space for graph Transformer, and ii) how to deal with the coupling relations between Transformer architectures and the graph encodings of each Transformer layer. To address these challenges, we propose Automated Graph Transformer (AutoGT), a neural architecture search framework that can automatically discover the optimal graph Transformer architectures by joint optimization of Transformer architecture and graph encoding strategies. Specifically, we first propose a unified graph Transformer formulation that can represent most of state-of-the-art graph Transformer architectures. Based upon the unified formulation, we further design the graph Transformer search space that includes both candidate architectures and various graph encodings. To handle the coupling relations, we propose a novel encoding-aware performance estimation strategy by gradually training and splitting the supernets according to the correlations between graph encodings and architectures. The proposed strategy can provide a more consistent and fine-grained performance prediction when evaluating the jointly optimized graph encodings and architectures. Extensive experiments and ablation studies show that our proposed AutoGT gains sufficient improvement over state-of-the-art hand-crafted baselines on all datasets, demonstrating its effectiveness and wide applicability.
BibTeX
@inproceedings{zhang2023autogt,
  author = {Zizhao Zhang and Xin Wang and Chaoyu Guan and Ziwei Zhang and Haoyang Li and Wenwu Zhu},
  title = {{AutoGT: Automated Graph Transformer Architecture Search}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=GcM7qfl5zY},
}
Figure