AutoGT: Automated Graph Transformer Architecture Search
Authors: Zizhao Zhang
Xin Wang
Chaoyu Guan
Ziwei Zhang
Haoyang Li
Wenwu Zhu
Venue: ICLR 2023 notable top 5% (2023)

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.


Published as a conference paper at ICLR 2023
AuTOGT: AUTOMATED GRAPH TRANSFORMER ARCHI- TECTURE SEARCH
Zizhao Zhang', Xin :ang! Chaoyu Guan', Ziwei Zhang', Haoyang Li', Wenwu Zhu DDepartment of Computer Science and Technology. Tsinghua University ITHU-Bosche JCML Center, Tsinghua University
[zzz22, guancyl9, 1ihyl8 @mailss tsinghua .dd..cd xxin_wwawa wang, zwzhang, wwzhu @tsinghua. edu.cr en
ABSTRACT
Although Transformer architectures have been successfully applied to graph data with the advent of Graph Transformer, the current design of Graph Transformers still heavily relies human labor and expertise knowledge decide proper neural architectures and suitable graph encoding strategies at each Transformer layer. In literature, there have been some works on the automated design of Trans- formers focusing on non-graph data such as texts and images without considering graph encoding strategies, which fail handle the non-euclidean graph data. In this paper, we study the problem of automated graph Transformers, for the first time. However, solving these problems poses the following challenges: 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 automati- cally discover the optimal graph Transformer architectures by joint optimization of Transformer architecture and graph encoding strategies. Specifically, we first propose unified graph Transformer formulation that can represent most 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 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-gra tne-ggrined performance prediction when evaluating the jointly optimized graph encodings and architectures. Extensive experiments and ablation studies show that our proposed AutoGiT gains sufficient improvement over state-of-the of-the-art hand-cratee cradtcr baselines on all datasets, demonstrating its effectiveness and wide applicability.
INTRODUCTION
Recently, designing Transformer for graph data has attracted intensive research interests (Dwivedi & Bresson 2020 Ying et al., 2021). As powerful architecture to extract meaningful information from
relational data, the graph Transformers have been successfully applied in natural language process-
ing (Zhang & Zhang 2020 Cai & Lam 2020 Wang et al. 2023), social networks (Hu et al. 2020b),
chemistry (Chen et al. 2019 Rong et al. 2020), recommendation (Xia et al. 2021) 1) etc. However, developing state-of of heavily relies on the tedious trial-and-error hand-crafted human design, including determining the best Transformer architecture and the choices of proper graph encoding strategies utilize, etc. In addition, the inefficient hand-crafted design will also inevitably introduce human bias, which leads sub-optimal solutions for developing graph transformers. In literature, there have been works on automatically searching for the architectures of Transformer, which are designed specifically for data
the art graph Transformer for downstream tasks is still challenging because
"Corresponding authors

---

Published as a conference paper at ICLR 2023
in Natural Language Processing (Xu et al. 2021) and Computer Vision (Chen et al. 2021b). These works only focus on non non-graph data without considering the graph encoding strategies which are shown to be very important in capturing graph information (Min et al. 2022a), thus failing to handle graph data with non-euclidean properties.
In this paper, we study the problem of automated graph Transformers for the first time. However, previous work (Min et al., 2022a) has demonstrated that a good graph Transformer architecture is expected only select proper neural architectures for every layer but also utilize appropriate encoding strategies capable of capturing various meaningful graph structure information to boost graph Transformer performance. Therefore, there exist two critical challenges for automated graph Transformers:
How to design unified search space appropriate for graph Transformer? A good graph Transformer needs to handle the non-euclidean graph data, requiring explicit consideration of node relations within the search space, where the architectures, as well the encoding strategies, be incorporated simultaneously.
How to conduct encoding-aware architecture search strategy to tackle the coupling relations between Transformer architectures and graph encoding? Although one simple solution may resort a one-shot formulation enabling efficient searching in vanilla Transformer operation space which can change its functionality during supernet training, the graph encoding strategies differ from vanilla Transformer in containing certain meanings related to structure information. How to train an encoding aacae aware supernet specifically designed for graphs is challenging.
To address these challenges, propose Automated Graph Transformer, AutoGT novel neural architecture search method for graph Transformer. In particular, we propose a unified graph Trans- former formulation cover most of the state-of-the-ard graph Transformer architectures space. Besides the general search space of the Transformer with hidden dimension, feed-forward dimension, number of attention head, attention head dimension, and number of layers, our unified search space introduces two new kinds of augmentation strategies to attain graph information: node attribution augmentation and attention map augmentation. To handle the coupling relations, we further propose novel encoding-awan the encoding strategy and architecture have strong coupling relations when generating results, our AutoGT split the supernet based the important encoding strategy during evaluation to handle the coupling relations. As such, we propose to gradually train and split the supernets according to the most coupled augmentation, attention map augmentation, using various supernets to evaluate different architectures in our unified searching space, which can provide a more consistent and fine-grate -raigrai performance prediction when evaluating the jointly optimized architecture and encoding. In summary, we made the following contributions:
search
performance estimation strategy tailored for graphs. As
We propose Automated Graph Transformer, AutoGT, novel neural architecture search frame- work for graph Transformer, which can automatically discover the optimal graph Transformer architectures for various down-streaming tasks. To the best of our knowledge, AutoGT is the first automated graph Transformer framework.
We design a unified search space containing both the Transformer architectures and the essential graph encoding strategies, covering most of the state-of-the-art graph Transformer, which can lead global optimal for structure information excavation and node information retrieval.
We propose an encoding- aware performance estimation strategy tailored for graphs to provide more accurate and consistent performance prediction without bringing heavier computation costs. The encoding strategy and the Transformer architecture are jointly optimized to discover the best graph Transformers.
The extensive experiments show that our proposed AutoGT model can significantly outperform the rfate-of-the-at baselines on graph classification tasks over several datasets with different scales.
RELATED WORK
The Graph Transformer. Graph Transformer, category of neural networks, enables Transformer to handle graph data (Min et al. 2022a). Several works (Dwivedi & Bresson 2020 Ying et al.)
Our codes are publicly availahle http://ggiiua.ccom///mmttttt//ae
2

---

Published as a conference paper at ICLR 2023
2021
Hussain et al., 2021 Zhang et al. 2020 Kreuzer al. 2021: Shi al. 2021 propose to
pre-calculate some node positional encoding from graph structure and add them to the node attributes after a linear or embedding layer. Some works (Dwivedi & Bresson 2020: Zhao et al.
2021: Ying
et al. [021] Khoo et al. 2020) also propose to add manually designed graph structura information into the attention matrix in Transformer layers. Others (Yao et al.) 2020: Min et al. 2022b) explore
the mask mechanism in the attention matrix, masking the influence of non-neighbor nodes. In particular, UniMP (Shi et al., 202T) achieves new state-of-the-ar art results on OGB (Hu et al. 2020a) datasets, Graphormer (Ying et al.) (021)) won first place in KDD Cup Challenge on Large-SCale graph classification by encoding various information about graph structures into graph Transformer.
Neural Architecture Search. Neural architecture search has drawn increasing attention in the past
few years (Elsken et al. 2019 Zoph & Le [017 Ma al. 2018
Pham et al. 2018 Wei et al.) 202T]
Cai et al.) 2022 Guan et al. 2021b] 2022, Qin et al.) 2022a b Zhang et al. [021]] ?). There are
many efforts to automate the design of Transformers. (So et al.
2019) propose the first automated
framework for Transformer in neural machine translation tasks. Trans (Zhu al. (202]) improves the search efficiency of the NLP Transformer through a one-shot supernet training. NAS-BERT (Xu et al. 2021) further leverages the neural architecture search for big language model distillation and compression. AutoFormer (Chen et al., 2021b) migrates the automation of the Transformer for vision tasks, where they utilize weight-entanglement to improve the consistency of the supernet training. GLiT (Chen et al., 2021a) proposes to search both global and local attention for the Vision Transformer using a hierarchical evolutionary search algorithm. (Chen et al. 2021ch further propose to evolve the search space of the Vision Transformer to solve the exponential explosion problems.
3 AUTOMATED GRAPH TRANSFORMER ARCHITECTURE SEARCH (AUTOGT)
To automatically design graph Transformer architectures, we first unify the formulation of current graph Transformers Section 3.1 Based on the unified formulation, we design the search space tailored for the graph Transformers in Section 3.2 We propose a novel encoding-aware performance estimation strategy in Section 3.3 and introduce our evolutionary search strategy in Section 3.4 The whole algorithm presented by Figure
3.1 THE UNIFIED GRAPH TRANSFORMER FRAMEWORK
Transformer Architecture
Current representative graph Trans- former designs can be regarded as improving the input and atten- tion map in Transformer architec- ture through various graph encod- ing strategies. We first introduce the basic Transformer architecture and then show how to combine various graph encoding strategies.
Multi-Head Attention
Peed Forward
Viatoe
Pleuctou
Fabiina
Add & Neens
Antention Outpur
Eimbeddnng
Lineer
Affeetion
Embeedinng
Trrhve- dass
Lincer
Bimbed-
ding
Embedding
Astariian Kaap Ausroentution
Prosiinity
AM
Eahaneed
Let G E) denote graph where V = {U1, U2 vn rep- resents the set of nodes and E (ei, e2, } represents the set of edges, and denote n [V| and m = [E| as the number of nodes and edges, respectively. Let v,, e (1....,.. n. represents the features of node Us and e E (1,..., m) rep- resents the features of edge ej-
Augmentas tigns
Adtoc
(SVTD-assec) Trattional
Adl
Muls-ffed
Attention Mask
Add Mae
Encodingo
Rust or
Eaplosion Eigenvecter
Centrality Encoding!
Spatial Uncoding
Edge Biscoding
Graphormer
Graph Specific Encoding
Figure 1:
The unified graph Transformer search space. It consists of the Transformer architecture space and the graph specific encoding space. The Transformer architecture search space is detailed Table The graph specific encoding search space is to decide whether each encoding strategy should be adopted or not and the mask threshold for the attention mask.
3.1.1 BASIC TRANSFORMER
As shown in Figure I basic Transformer consists of several stacked blocks, with each block containing two modules, namely the multi-head attention (MHA) module and the forward network (FFN) module.
3

---

Published as a conference paper at ICLR 2023
At block I, the node representation H E Ruxd first goes through the MHA module interact with each other and pass information through self-attention:
Qa K (1)
A ( softmax
0000 = A (
(I)
vdz
where A h E Ruxn is the message passing matrix, 0 is the output of the self-attention mech- anism of the h attention head, h = 1,2, Head, Head is the number of attention heads, and k0 (1) v(( E Buxx the key, query, value calculated as:
K H
q.ht Vi = H Ww o.hr
where W W W!l Bdxxd are learnable parameters. Then, the representations of different k q.ht v.h heads concatenated and further transformed as:
o = 0
Head
where w! (d Had) is the parameter and O is the multi-head result. Then, the attended representation will go through the FFN module further refine the information of each node:
H ( 6(0 !T
(4)
where O E Rexd is the output, w dR xd,, w E Rd.ddd are weight matrices.
As for the input of the first block, we concatenate all the node features H = [Vi,.., Vnl. After blocks, we obtain the final representation each node H(L)
3.1.2 GRAPH ENCODING STRATEGY
From Section 3.1.1 we can observe that directly using the basic Transformer on graphs can only process node attributes, ignoring important edge attributes and graph topology information in the graph. To make the Transformer architecture aware of the graph structure, several works resort to various graph encoding strategies, which can be divided into two kinds of categories: node attribution augmentation and attention map augmentation.
The node attribution augmentations take the whole graph G input and generate the topology-aware features Encnade (G) for each node directly improve the node representations:
(9 EnCrode
(5)
aug
On the other hand, the attention map augmentations generate an additional attention map EnCmap (G). which represents the relationships of any two nodes and improves the attention map generated by self-attention in Eq equation as:
Q L O
h.aug softmax
EnCmap(G))
(6)
Combining node attribution augmentations and attention map augmentations together, our proposed framework is as follows:
(1) will 9.h
(H wilh w()))
H(+1) =o Concatt
softmax
+ EECmmp((G)
H with
w(()
W!!)
Vdl.
where ( H!) Encnode (G).
3.2 THE GRAPH TRANSFORMER SEARCH SPACE
Based on the unified graph Transformer formulation, we propose unified search space design, which can be decomposed into two parts, i.c. Transformer Architecture space and graph encoding space. Figure 1 shows the unified graph Transformer search space.
4

---

Published as a conference paper at ICLR 2023
Input
input embedding
KQV
key query value
#HHaad
number of heads
Mid
intermediate embedding
FFN feed forward network embedding
Mask
attention mask threshold
CE
centrality encoding
SE
spatial encoding
EE
edge encoding
LPE
Laplacian eigenvector
SVD
SVD-based positional encoding
PMA
proximity enhanced attention
Layer
Layer
Input
Input
Layer
Layer
KQV
KQV
Input
Split
Input
Heads
#Heada
KQV
KQV
Mid
Mid
#Heads
FFN
FFN
BOEE
#Heads
Mid
Mid
FFN
Secoding-Awarts Supernet Training
Evol
FFN
Mask
Search
Mask
Layer
Layer
Layer
Layer
Mask
Masic
CE
CE
LPE
LPE
Split
SE
SE
EE
SVD
SVD
EE
PMA
SE
SE
EE
Figure 2: The framework of our work. Firstly, we construct the search space for each layer, consisting of the Transformer architecture space (above) and the graph encoding strategy space (below). Then, we carry out our encoding-awand supernet training method in two stages: before splitting, we train a supernet by randomly sampling architectures from the search space, while after splitting, we train multiple subnets (inheriting the weights from the supernet) by randomly sampling architectures with fixed attention map augmentation strategies (except for attention mask). Finally, we conduct an evolutionary search based on the subnets and obtain our final architecture and results.
3.2.1 TRANSFORMER ARCHITECTURE SPACE
Following Section 3.1.1 we automate five key architecture components for graph Transformer as follows: the number of encoder layers L. the dimension d, the intermediate dimension d,, the hidden dimension d,, the number of attention heads Head, and the attention head dimension dg in graph Transformer. Notice that these five components already cover the most important designs for Transformer architectures.
suitable search space should be only expressive enough allow powerful architectures, but also compact enough to enable efficient searches. With this principle mind, we propose two search spaces for these components with different size ranges. Table gives the detailed search space for these two spaces.
3.2.2 GRAPH ENCODING SPACE
To exploit the potential of the graph encoding strategies, we further determine whether and which graph encoding strategies to use for each layer of the graph Transformer. Specifically, we explore the node attribution augmentations encoding and attention map augmentations encoding as below.
Node Attribution Augmentations:
Centrality Encoding Ying et al. 2021). Use two node embeddings with the same size represent- ing the in-degree and the out-de of nodes, i.e.,
1 = (v:)
Z (v.)
(8)
where h! is the input embedding in layer 24 is the input attribution of node layer I, and z and Tt are the embedding generated by the in-degree and out-degree.
Laplacian Eigenvector (Dwivedi & Bresson 2020 Conducting spectral decomposition of the graph Laplacian matrix:
U AU =I I 1/2 A
(9)
5

---

Published as a conference paper at ICLR 2023
Table 1: The Transformer Architecture Search Space for AutoGT base and AutoGT.
AutoGT base
AutoGT
Choices
Supernet Size
Choices
Supemet Size
#Layers Input Dimension df
(2,3,4)
4
[5.6.7.8]
[24.28.32]
32
[96.112.128]
Intermediate Dimension de
(24,28.32)
32
(96,112,1288
128
Hidden Dimension da
(24,28,32)
32
[96,112,128]
128
#Attention Hcads
(2,3,4)
4
(6,7,8)
Attention Head Dimension dx
[6,8]
8
(12,14
where A G is the adjacency matrix of graph G, D is the diagonal degree matrix, and U and are the cigenvectors and cigenvalues, respectively. We only select the cigenvectors of the & smallest non-zero eigenvalues as the final embedding and concatenate them to the input node attribute matrix for each layer.
SVD-based Positional Encoding (Hussain et al. 2021). Conducting singular value decomposition to the graph adjacency matrix:
SVD UEV = (UVE) -VVV) ÚVT
(10)
where U, V Raxx contains the left and right singular vectors of the top singular values in the diagonal matrix Σ E Rexr. Without loss of generality, we only choose Ü as final embedding since they are highly correlated for symmetric graphs (with differences signs, to be specific). Similar Laplacian cigenvector, we concatenate it to input node attribute matrix for each layer.
Attention Map Augmentations Space:
Spatial Encoding (Ying et al. 2021). Spatial encoding is added to the attention result before softmax:
Aug (h, Wk)" + botouin))
(11)
Vdh
where (bu;, vy) is the length of the shortest path from e uy and E R is weight parameter generated by ((v,,)))
Edge Encoding (Ying et al. 2021). ). Edge encoding is added to the attention result before softmax:
A, (h, (h,,
1
Bep (w )
(12)
Vdl.
N
where Te., is the feature of the rith edge en on the shortest path between ii and By. and w the nith learnable embedding vector.
Froximity-Enhanee Attention (Zhao et al. 2021). Proximity-nnhaneed Attention is added to the attention result before softmax:
(hs (hh,)) dd
Agg
+ +
(13)
where b R Mx1 is learnable parameter, 6ij Concat 4 (U,, 1.)lm 0, M is the
structural encoding generated from: 4 2m, v2)) À A j]. where Norm(A + I) represents
the normalized adjacency matrix. Thus the augmentation denotes the reachable probabilities between nodes.
Attention Mask (Min al. 2022b Yao et 2020p. Attention Mask is added to the attention result before softmax:
Aij (h, Wx) Vdd
Mask.. (u;, vz)
(14)
where m is the mask threshold, Mask,, (v, vy) depends on the relationship between m and Φ(v, 0z), i.e the shortest path length between i; and uy. When 2 Φ(v, vy), Mask,n (V,, bt)) 0. Otherwise, Maskm (V,, vz) is -00, masking the corresponding attention in practical terms.

---

Published as a conference paper at ICLR 2023
Table 2: Comparison of our proposed unified framework with state-of-the-art graph Transformer models. CE. LPE, SVD, SE, EE, PMA, Mask denote Centrality Encoding, Laplacian Eigenvector, SVD-based Positional Encoding, Spatial Encoding, Edge Encoding, Proximity-Enhance Attention,
and Attention Mask respectively.
CE
LPE
SVD
SE
PMA
Mask
EGT (Hussain al. Gophormer (Zhao ct al.
2021)
2021
Graph Trans (Dwivedi & Bresson Graphormer ( Ying el al
2020
V
Ours
3.3 ENCODING-AWARE SUPERNET TRAINING
We next introduce our proposed encoding-aware performance estimation strategy for efficient training.
Similar to general NAS problems, the graph Transformer architecture search can be formulated as bi-level optimization problem:
a' argmax Acceat (W' a), s.t.W" argmin Strain (W, .):
(15)
where A is the architecture in the search space A, Acceal stands for the validation accuracy, W represents the learnable weights, and a* and (a)a) denotes the optimal architecture and the optimal weights for the architecture a.
Following one-shot NAS methods (Liu et al. 2019 Pham et al., 2018 we encode all candidate architectures in the search space into a supernet and transtorm Eq. equation 15 into a two-step optimization (Guo et al. 2020):
a (W", .a,
w argminw Eo Ehrann (W,a),
(16)
where W denotes the shared learnable weights in the supernet with optimal value W for all the architectures in the search space.
To further improve the optimization efficiency of the supernet training, we leverage weight entan- glement (Guan et al.) 2021aa Chen et al. 2021b; Guo et al.] (020) to deeply share the weights of architectures with different hidden sizes. Specifically, for every architecture sampled from the supernet, we use a (-1 I mask to discard unnecessary hidden channels instead of maintaining new set of weights. In this way, the number of parameters in the supernet will remain the same as the largest (i.e., with the most parameters) model in the search space, thus leading to efficient optimization.
Although this strategy is fast and convenient, using the same supernet parameters W for all archi- tectures will decrease the consistency between the estimation of the supernet and the ground-truth architecture performance. To improve the consistency and accuracy of supernet, we propose an incoding-aware supernet training strategy. Based the contribution coupling of different encoding strategies, we split the search space into different sub-spaces based on whether adopting three kinds of attention map augmentation strategies: spatial encoding, edge encoding, and proximity-enhancee attention. Therefore, there are 2 = 8 supernets.
To be specific. first train single supernet for certain epochs and split the supernet into 8 subnets according to the sub-spaces afterward. Then, we continuously train the weights in each subnet W; by only sampling the architecture from the corresponding subspace A, Experiments to support such a design are provided in Section
3.4 EVOLUTIONARY SEARCH
Similar to other NAS research, our proposed graph transformer search space is too large to enumerate. Therefore, propose utilize the evolutionary algorithm to efficiently explore the search space to obtain the architecture with optimal accuracy on the validation dataset.
Specifically, first maintain population consisting of T architectures by random sample. Then, we evolve the architectures through our designed mutation and crossover operations. In the mutation operation, randomly choose from the top-k architectures with the highest performance in the
7

---

Published as a conference paper at ICLR 2023
Table 3: Comparisons of AutoGT against state-of-the-art hand-crafted baselines. We report the average accuracy (%) and the standard deviation on all the datascts. Out-of-time (OOT) indicates the method cannot produce results in GPU day.
Dataset
COX2 MD
BZR MD
PTC FM
DHFR MD
PROTEINS
DBLP
GIN
45.8214.35
59.6814.65
57.87
62.88s.26
73.764.61
91.18a.42
DGCNN
54,81
62. 62.7420.50
62.173.62
63.895.a1
72.683.75
91.570.54
DiflPool
14.45
65.01
60.165.87
61.06g.42
73.31s.75
OOT
GraphSAGE
12.59
57.43
64. 64.17% 173.28
66.922.35
67.196.97
51.01o.02
Graphormer
56,3915.u3
63. 63.9412.68
64.887.58
64.887.68
75.29
89.362.31
GT(ours)
54.4416.81
1..33
64.182.60
65.685.64
73.94s.78
90.67
AutoGT(ourr)
59.7223.26
65.92.0.00
65.603.71
68.22s.02
77.173.40
91.660.79
Table 4: Comparisons of AutoGT against state-of-the-art hand-crafted baselines. We report the area under the curve (AUC) [%] and the standard deviation all the datasets.
Dataset
OGBG-Mo/HIV OGBG-MoIBACE.
OGBG-MoIBBBP
GIN
71.1
70.424.78
63.37
DGCNN
69. 69.972.16
75.622.64
60.921.78
DifiPool
74.581.71
73.874.50
66.68s.0s
GraphSAGE
67.823.67
72.911.24
64.193.50
Graphormer
71.892.66
76.421..7
66.52o.74
AutoGT(ours)
74.95
76.701.42
67.29 1.46
last generation and change its architecture choices with probabilities. In the crossover operation, we randomly select pairs of architectures with the same number layers from the remaining architectures, and randomly switch their architecture choices.
EXPERIMENTS
In this section, we present detailed experimental results as well as the ablation studies to empirically show the effectiveness of our proposed AutoGT.
Datasets and Baselines. We first consider six graph classification datasets from Deep Graph Kernels Benchmark( Yannardag & Vishwanathan (015)) and TUDataset (Morris al.) (0020). namely COX2_MB BZR_MD PTC PTC_FM, DHFR MD. PROTEINS, and DBLP. We also adopt three datasets from Open Graph Benchmark (OGB) (Hu et al. 2020a), including OGBG-MolHIV,
OGBG-MolBACE and DGBG-MolBBBR The task is to predict the label of each graph using node/edge attributes and graph structures. The detailed statistics of the datasets are shown in Table 6 in the appendix.
We compare AutoGT with state-of-the-art hand-crafted baselines, including GIN Xuu al. 2019), DGCNN (Zhang et al., 2018), DiffPool (Ying et al. 2018), GraphSAGE (Hamilton et al. and Graphormer (Ying et al. 202I). Notice that Graphormer a Kate-of-thee-e graph Transformer architecture that won first place in the graph classification task of KDD Cup 2021 (OGB-LSC).
2017).
For the datasets, we follow Errica et al., (Erriaa et al., 2020) to utilize 10-fold cross-validation for all the baselines and proposed method. All the paperr-rrreeterss and training strategies of baselines are implemented according to the publicly available codes (Errica et al. 2020
Implementation Details. Recall that proposed architecture space has two variants, larger AutoGT(L = 8, = 128) and a smaller AutoGTTauceLL = 4, d 32). In our experiments, we adopt the smaller search space for five relatively small datasets, i.e., all datasets except DBLP, and the larger search space for DBLP. We use the Adam optimizer, and the learning rate is 3c - 4. For the smaller/larger datasets, we the number of iterations split (i.e.. T. in Algorithm I Appendix) as 50/6 and the maximum number of iterations (i.e., Tm in Algorithm [ as 200/50. The batch size is 128. The hyperparameters of these baselines are kept consistent with our method for a fair comparison.
8

---

Published as a conference paper at ICLR 2023
We also report the results of our unified framework in Section 3.1 our search space with the supernet but without the search part, denoted as GT(Graph Transformer).
i.e. mixing all the encodings in
Experimental Results. We report the results in Table 3 We make the following observations. First, AutoGT consistently outperforms all the existing hand-crafted methods on all datasets, demon- strating the effectiveness of our proposed method. Graphormer shows remarkable performance and achieves the second-best results on three datasets, showing the great potential Transformer archi- manually designed architecture
tectures in processing graph data. However, since Graphormer and cannot adapt to different datasets, it fails to be as effective as our proposed automatic solution. Lastly, GT, our proposed unified framework, fails show strong performance in most cases. The results indicate that simply mixing different graph Transformers cannot produce satisfactory results, demonstrating the importance of searching for effective architectures to handle different datasets.
We also conduct experiments on Open Graph Benchmark (OGB) (Hu et al. 2020a). On the three binary classification datasets of OGB, we report the AUC score of our method and all the baselines. The results also show that our method outperforms all the hand-crafted baselines these datasets.
Time Cost. We further show the time comparison of AutoGT with hand-crafted graph transformer Graphormer. On OGBG-MolHIV dataset, both Graphormer and AutoGT cost 2 minutes for one epoch on single GPU. The default Graphormer is trained for 300 epochs, which costs 10 hours to obtain the result of one random seed. For AutoGT, we train shared supernet for 50 epochs. 8 supernets inherit, and continue to train for 150 epochs. So the training process costs totally 1250 epochs with 40 hours. And the evolutionary search stage, evaluate 2000 architectures' inheriting weight performances, which costs about 900 epochs with 30 hours. In summary, the total time cost for AutoGT is only 7 times total time cost for a hand-crafted graph transformer Graphormer.
Ablation Studies. We verify the effectiveness of the proposed encoding-aware supernet training strategy by reporting the results the PROTHINS dataset, while other datasets show similar patterns.
To show the importance of considering encoding strategies when training the supernet, we design two variants of AutoGT and compare the results:
One-Shot. We only train a single supernet and use it to evaluate all the architectures.
Pusitional-Aware. We also split up the supernet into 8 subnets but based on three node attribute augmentations instead of the three attention map augmentation as in AutoGT.
The results of AutoGT and two variants are shown in Ta- 5 From the table, we can observe that, compared with the result of one-shot NAS, positional-aware and AutoGT methods achieve different levels of improvement. Further comparing the accuracy gain, we find that the result of AutoGT (1.25%) is nearly 5 times larger than the result of positional-aware (0.27%) even though both methods adopt 8 subnets. We attribute the significant difference in accuracy gain from supernet splitting the different degrees of coupling of graph encoding strategies with the Transformer architecture. For example, the dimensional- ity of node attribution augmentation is the same as the number of nodes. while the attention map augmentation has a quadratic dimensionality, resulting in different coupling degrees. Our proposed encoding- awarre performance estimation based on three attention map augmentation strategies is shown to be effective in practice.
Table 5:
The ablation study the effec- tiveness of the proposed encoding-awan supernet training strategy. We report the average accuracy[ [%] with the variance PROTEINS.
Method
Accuracy
One-Shot
75.92..
Positional-Aware
76.19..42
AutoGT
77.173.40
CONCLUSION
In this paper, we propose AutoGT, a neural architecture search framework for graph Transformers. We design a search space tailored for graph Transformer architectures, and an encoding-awan supernet training strategy to provide reliable graph Transformer supernets considering various graph encoding strategies. Our method integrates the existing graph Transformer into a unified framework, where different Transformer encodings demonstrate that our proposed AutoGT consistently outperforms state-of-the-e baselines on all datasets, demonstrating its strength on various graph tasks.
enhance each other. Extensive experiments six datasets

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work was supported in part by the National Key Research and Development Program of China No. 2020AAA0106:000, National Natural Science Foundation of China (No. 62250008, 62222209, 62102222, 6193601 I, 622061499 19), China National Postdoctoral Program for Innovative Talents No. BX20220185, and China Postdoctoral Science Foundation No. 2022M711813 Tsinghua GuoQiang Research Center Grant 2020GQG1014 and partially funded by THUU-Bssch JCML Center. All opinions, findings, and conclusions in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.
REFERENCES
Deng Cai and Wai Lam. Graph transformer for graph-to-sequence learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7464-7471, 2020.
Jie Cai, Xin Wang, Chaoyu Guan, Yateng Tang, Jin Xu, Bin Zhong, and Wenwu Zhu. Multimodal con- tinual graph learning with neural architecture search. In Proceedings of the ACM Web Conference 2022, pp. 1292-1300, 2022.
Benson Chen, Regina Barzilay, and T. Jaakkola. Path Path-augmented graph transformer network. ArXiv, abs/1905.1177 2019.
Boyu Chen, Peixia Li, Chuming Li, Baopu Li, Lei Bai, Chen Lin, Ming Sun, Junjie Yan, and Wanli Ouyang. Glit: Neural architecture search for global and local image transformer. Proceedings of the IEEF/CVF International Conference on Computer Vision (ICCV), pp. 12-21, October 2021a.
Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. Autoformer: Searching transformers for visual recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 12270-12280) October 2021b.
Minghao Chen, Kan Wu, Bolin Ni, Houwen Peng, Bei Liu, Jianlong Fu, Hongyang Chao, and Haibin Ling. Searching the search space of vision transformer. Advances in Neural Information Processing Systems, 34:8714-8726, 2021c.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.0969) 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 199():1977-2117, 2019.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Chaoyu Guan, Ziwci Zhang, Haoyang Li, Heng Chang, Zeyang Zhang, Yijian Qin, Jiyan Jiang, Xin Wang, and Wenwu Zhu. Autogl: A library for automated graph learning. In ICLR 2021 Workshop on Geometrical and Topological Representation Learning.
Chaoyu Guan, Yijian Qin. Zhikun Wei, Zeyang Zhang, Zizhao Zhang, Xin Wang, and Wenwu Zhu. One-shot neural channel search: What works and what's next. In CVPR Workshop on NAS, 202
Chaoyu Guan, Xin Wang, and Wenwu Zhu. Autoattend: Automated attention representation search. In International conference machine learning, pp. 3864-3874, PMLR, 2021b.
Chaoyu Guan, Xin Wang, Hong Chen, Ziwei Zhang, and Wenwu Zhu. Large-scale graph neural architecture search. In International Conference on Machine Learning, pp. 7968-7981. PMLR, 2022.
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. In Computer ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVI, pp. 544-560 2020.
10

---

Published as a conference paper at ICLR 2023
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 1--22118-2213, 2020a.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pp. 2704-2710, ACM / IW3C2, 2020b.
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Edge-augmented graph transformers: Global self-attention is enough for graphs. arXiv preprini D.Xiv:2/08.03:: 2021.
Ling Min Serena Khoo, Hai Leong Chieu, Zhong Qian, and Jing Jiang. Interpretable rumor detection in microblogs by attending to user interactions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 8783-878799 2020.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Léourrnaau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. Shufflenet v2: Practical guidelines for efficient architecture design. In Proceedings of the European conference computer vision (ECCV), pp. 116-131, 2018.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455, 2022a.
Erxue Min, Yu Rong, Tingyang Xu, Yatao Bian, Peilin Zhao, Junzhou Huang, Da Luo, Kangyi Lin, and Sophia Ananiadou. Masked transformer for neighhourhood-aware click-through rate prediction, arXiv preprint arXiv:2201. 13311, 2022b.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08666. 2020.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International conference on machine learning, pp. 4095-4101) PMLR, 2018.
Yijian Qin, Xin Wang, Ziwei Zhang, Pengtao Xie, and Wenwu Zhu. Graph neural architecture search under distribution shifts. In International Conference on Machine Learning, pp. 18083-18095. PMLR, 2022a.
Yijian Qin, Ziwei Zhang, Xin Wang, Zeyang Zhang, and Wenwu Zhu. bos-bench-graphee Benchmark- ing graph neural architecture search. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022b.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer large-scale molecular data. Advances Neural Information Processing Systems, 33:12559-125711 2020.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In International Joint Conference on Artificial Intelligence, pp. 1548-1554. ijcai.org, 2021.
David R. So, Quoe V. Le, and Chen Liang. The evolved transformer. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5877-5886. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2023
Xin Wang, Yue Liu, Jiapei Fan, Weigao Wen, Hui Xue, and Wenwu Zhu. Continual few-shot learning with transformer adaptation and knowledge regularization. In Proceedings of the ACM Web Conference 2023, 2023.
Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. Pooling architecture search for graph classification. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2091-2100, 2021.
Lianghao Xia, Chao Huang. Yong Xu, Peng Dai, Xiyue Zhang, Hongsheng Yang, Jian Pei, and Liefeng Bo. Knowledge-enhanced hierarchical graph transformer network for multi-behavior recommendation. In Pruceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4486 4493, 2021.
Jin Xu, Xu Tan, Renqian Luo, Kaitao Song, Jian Li, Tao Qin, and Yan Liu. Nas-bert: task-agnostic and adaptive-size bert compression with neural architecture search. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, pp. 1933-1943, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemnels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-13744 2015.
Shaowei Yao, Tianming Wang, and Xiaojun Wan. Heterogeneous graph transformer for graph-to- sequence learning. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7145-7154, 2020.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tin Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
Haopeng Zhang and Jiawei Zhang. Text graph transformer for document classification. In Conference on Empirical Methods Natural Language Processing (EMNLP), 2020.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprini arXiv:2001.051400 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Ziwei Zhang, Xin Wang, and Wenwu Zhu. Automated machine learning on graphs: A survey, In International Joint Conference on Artificial Intelligence, 2021.
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. arXiv preprint arXiv:2110.1300 2021.
Wei Zhu, Xiaoling Wang, Yuan Ni, and Guotong Xie. Autotrans: Automating transformer design via reinforced architecture search. In Natural Language Processing and Chinese Computing: 10th CCF International Conference, NLPCC 2021, Qingdao, China, October 13-17, 2021, Proceedings. Part I, pp. 169-182, 2021.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations, 2017.
12

---

Published as a conference paper at ICLR 2023
A TRAINING PROCEDURE
We list the training procedure of our method Algorithm
Algorithm 1 Our proposed encoding-aware supernet training strategy
Initialize. Supernet weights subnet weights W., search space A. subspace A. the split iteration T., the max iteration Tm. a dataset 2>.
2: for t :' ' do
3: Sample architecture and encoding strategies A.
4: Sample batch of graph data D3 D.
Calculate the training loss Lerain over the sampled data.
6: Update the supernet weights W through gradient descents.
7:
end for
8: for i
Let subnet W, inherit the weights from supernet W.
10:
for =T Tm do
11:
Sample architectures and encoding strategics from the subspace E Ai. Sample batch of graph data D. E D. Calculate the training loss Lirain the sampled batch. Update the subnet weights W. through gradient descents.
12:
13:
15:
end for
16:
end for
17:
Output. Subnets with weights W..
B DATASET
We provide the statistics of the adopted datasets in Table Table 7
Table 6: Statistics of graph classification datasets (precision) used to compare AutoGT with baselines. We adopt five datasets with relatively small numbers of graphs (upper part) and one dataset with larger size (lower part) to demonstrate the efficiency of the proposed AutoGT.
Dataset
#Graph
#Class
#Avg. Nodes
#Avg. Edges
# Node Feature
Edge Feature
COX2
26.28
335.12
BZR MD
306
21.3
225.06
8
PTC_FM
349
2
14.11
14.48
18
4
DHER_M MD
393
23.87
283.01
7
5
PROTEINS
1,133
39.06
72.82
3
0
DBLP
19,456
10.48
19.65
41,325
3
Table 7: Statistics of graph classification datasets (AUC) used to compare AutoGT with baselines.
We adopt two datasets with relatively small numbers of graphs (upper part) and one dataset with larger size (lower part) to demonstrate the efficiency of the proposed AutoGT.
Dataset
#Graph
#Class
#Avg. Nodes
#Avg. Edges
Node Feature
# Edge Feature
OGBG-MoIBACE
1,513
2
25.51
27.47
OGBG-MoIBBBP
2,039
2
34.09
36.86
3
OGBG-MolHIV
41,127
2
24.06
25.95
3
C ADDITIONAL EXPERIMENTS
In Table the results on COX2 MD and BZR MD show larger standard deviations than other datasets. One plausible reason is that the number of graphs of these two datasets relatively small, so that the results the model can sensitive to dataset splits. To obtain more convincing results on these two datasets, conduct additional experiments by still utilizing 10-fold cross-validation for all
13

---

Published as a conference paper at ICLR 2023
Table 8: Comparisons of AutoGT against state-of-the-art hand-crafted baselines. We report the average accuracy (%) and the standard deviation on all the datasets.
Dataset
COX2_MB
BZR_MD
GIN
57.22g.74 74
62.648.23
DGCNN
60.337,56
64.91 9.44
DiftPool
59,528.20
64.848.51
GraphSAGE 53.626.95
55.83
Graphormer
59.227.04
64.53y.43
AutoGT(ours)
63.45g.04
67.18
Table 9: Comparisons of AutoGT with the different number of supernets. We report the average accuracy (%) and the standard deviation on the datasets.
Dataset
PROTEINS
supernet
75.923.10
2 supernet
76.733.25
4 supernet
76.913.35
8 supernet
77.173.40
16 supernet
77.273.65
baselines and our proposed method, and repeat the 10-fold cross-validation with random seeds. We report the results in T The results are consistent with Table i.e., our method consistently outperforms other baselines, while the standard deviations are considerably smaller by adopting more repeated experiments.
addition, to further explore how the number of supernets affects our proposed method, we carry out experiments with I, 2, 4, 8, 16 supernets the PROTEINS dataset, and report results in Table 9 We can observe that as the number of subnets increases, the performance of our method increases. One possible reason is that more well-trained subnets can bring more consistent performance estimation results, which improves performance.
14


Reviews:
[{"review_id": "g4da3T2lsK", "reviewer": "Reviewer_iKrv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is the first work on automating the architecture design of graph Transformer, which is rarely studied in graph Transformer research. The contributions lie in solving the two challenges specifically related to graph-structured data during the design of neural architecture search.", "summary_of_the_review": "This work proposes a neural architecture search based framework, Automated Graph Transformer (AutoGT), for automating the architecture design of graph Transformers. Tailored for non-euclidean graph data, the search space of AutoGT takes both the graph encoding strategy and Transformer architecture into considerations. Furthermore, the performance estimation strategy of AutoGT is designed to be encoding-aware through joint optimization of the encoding strategy and graph Transformer architectures. Experiments over several graph datasets with different sizes demonstrate the effectiveness of the proposed AutoGT. I think this paper investigates an interesting problem of good importance and I recommend to accept.\n", "strength_and_weaknesses": "Strengths:\n1. The novel idea of automating the design procedure of graph transformer.\n2. Utilizing the neural architecture search for graph Transformers tends to become popular and practically important in graph representation learning community.\n3. The proposed model is solid and the solution is appropriate for solving the challenges.\n4. The paper is well written and the related work eases the understanding of neural architecture search and graph Transformer literature.\n\nWeaknesses:\n1. Fig. 1 is presented without explanation. Detailed explanations are expected to be provided. \n2. For the architecture search and training step, the authors are encouraged to further discuss the difference from the proposed main ideas from the previous works on neural architecture search.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dNfBjyqNgAr", "reviewer": "Reviewer_C87i", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Existing graph transformers have succeeded in different applications but require cumbersome architecture designs and tuning by experienced engineers. This paper proposed a novel search framework for graph transformers, automatically searching within the designed unified search space for optimal architecture designs. The proposed method is compatible with most of the existing state-of-art graph transformers designs without introducing a substantial amount of computation cost. The experimental results show proposed strategy results in better designs over hand-crafted baselines. ", "summary_of_the_review": "This paper proposed AutoGT, which can automatically search the design space, which is compatible with most of the existing state-of-art graph transformers designs, without introducing a substantial amount of computation cost. The experimental results show proposed strategy results in better designs over hand-crafted baselines. However, I have concerns about the ease of use since AutoGT introduces extra hyperparameters that need to be tuned. And the auto designs from AutoGT have less consistent performance. \n\nI recommend 6-marginally above the acceptance threshold. \n\n\n----- After hearing back from authors 11/16 -----\n\nThanks for the explanation and new results. They cleared all of my concerns. Changing to \"8: accept, good paper \"", "strength_and_weaknesses": "Strength \n1. Well-explained basic transformer and graph encoding strategy, which show excellent intuition of the search space design. \n2. The proposed framework is compatible with more existing graph encoding strategies, which allows a broader comparison between graph transformer designs. \n3. Tab5 shows an ablation study using a single supernet vs. additional supernets. The ablation study shows the improvement of performance by splitting a supernet. Such a design brings extra performance without extra parameters. \n\nWeakness:\n1. Section 3 explained the proposed AutoGT well in text. However, neither Fig 1 nor Fig 2 are self-explanatory. I could not understand their relations with the proposed method without reading the main paragraphs. The small fonts in the figures made it more challenging.\n2. Figure 2 was never mentioned in the text, which makes it tricky to understand which section it belongs to. \n3. Table 3 tries to show the importance of the proposed evolution search by comparing it to simple random selection and existing hand-crafted options. The results have large deviations. How can we ensure the proposed method results in consistently high-quality architecture designs? \n4. The proposed method aims to automatically provide graph transformer designs. However, AutoGT introduces extra hyper-parameters such as the number of supernet sizes and the search space's design. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "MgzktF4mZeH", "reviewer": "Reviewer_ueHs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the interesting problem of automated graph transformer through neural architecture search. The authors first propose a unified graph Transformer formulation that can represent most of the state-of-the-art graph transformer architectures. Then, an encoding-aware architecture searching and supernet training strategy are proposed. Experimental results over several graph datasets including the large-scale OGB datasets show the effectiveness of the proposed method.", "summary_of_the_review": "This paper studies an interesting problem of automating the neural architecture design of graph transformer. The authors raise the challenges in the investigated problem, followed by the proposal of technical solid solution. Extensive experimental results validate the effectiveness of the proposed solution. I think this paper tends to be interesting to the research community and recommend acceptance for this paper.", "strength_and_weaknesses": "### Strengths:\n+ The proposal of automatically searching the optimal graph transformer architecture is important in the community of machine learning.\n+ Constructing a unified graph Transformer formulation by combining several typical transformer architectures and graph encoding strategies seems to be a novel contribution.\n+ Taking graph-specific properties into the automated graph transformer architecture search process is helpful and can distinguish this paper from other approaches such as autoformer.\n+ Experiments are conducted over several widely used and benchmark datasets.\n\n### Weaknesses:\n- The major focus in this work is the complex relations between transformer architectures and the graph encodings in transformer layer. The authors are suggested to further discuss why this problem is important and challenging, and how the authors address the problem specifically. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%