Are More Layers Beneficial to Graph Transformers?
Authors: Haiteng Zhao
Shuming Ma
Dongdong Zhang
Zhi-Hong Deng
Furu Wei
Venue: ICLR 2023 poster (2023)
Keywords: Transformer
Graph Representation
Depth

Abstract: Despite that going deep has proven successful in many neural architectures, the existing graph transformers are relatively shallow. In this work, we explore whether more layers are beneficial to graph transformers, and find that current graph transformers suffer from the bottleneck of improving performance by increasing depth. Our further analysis reveals the reason is that deep graph transformers are limited by the vanishing capacity of global attention, restricting the graph transformer from focusing on the critical substructure and obtaining expressive features. To this end, we propose a novel graph transformer model named DeepGraph that explicitly employs substructure tokens in the encoded representation, and applies local attention on related nodes to obtain substructure based attention encoding. Our model enhances the ability of the global attention to focus on substructures and promotes the expressiveness of the representations, addressing the limitation of self-attention as the graph transformer deepens. Experiments show that our method unblocks the depth limitation of graph transformers and results in state-of-the-art performance across various graph benchmarks with deeper models.

Published as a conference paper at ICLR 2023
ARE MORE LAYERS BENEFICIAL TO GRAPH TRANS- FORMERS?
Haiteng Zhao' Shuming Ma², Dongdong Zhang?, Zhi-Hong Deng', Dongg,Funn Furu Wei
1 Peking University
2 Microsoft Research
{ z zhahhaiteng, zhdeng 8 edu a humma,, dozhang, fuwei f /
ABSTRACT
Despite that going deep has proven successful in many neural architectures, the ex- isting graph transformers are relatively shallow. In this work, we explore whether more layers are beneficial to graph transformers, and find that current graph trans- formers suffer from the bottleneck of improving performance by increasing depth. Our further analysis reveals the reason is that deep graph transformers are limited by the vanishing capacity of global attention, restricting the graph transformer from focusing on the critical substructure and obtaining expressive features. To this end, we propose a novel graph transformer model named DeepGraph that ex- plicitly employs substructure tokens in the encoded representation, and applies local attention on related nodes to obtain substructure based attention encoding. Our model enhances the ability of the global attention to focus on substructures and promotes the expressiveness of the representations, addressing the limitation self-attention as the graph transformer deepens. Experiments show that our method unblocks the depth limitation of graph transformers and results in state- of-the-ar art performance across various graph benchmarks with deeper models.
INTRODUCTION
Transformers have recently gained rapid attention in modeling graph-structured data (Zhang al., 2020 Dwivedi & Bresson, 2020 Maziarka et al., 2020) Ying et al. [201]] Chen et al., 2022). Com- pared to graph neural networks, graph transformer implies global attention mechanism enable information passing between all nodes, which is advantageous to learn long-range dependency of the graph stuctures (Alon & Yahav 2020). In transformer, the graph structure information can be encoded into node feature (Kreuzer et al. (222)) or attentions (Ying et al. [02I]) by variant of meth- ods flexibly with strong expressiveness, avoiding the inherent limitations of encoding paradigms that pass the information along graph edges. Global attention (Bahdanau et al., 2015) also enables ex- plicit focus on essential parts among the nodes to model crucial substructures in the graph.
Graph transformer in current studies is usually shallow, i.e., less than 12 layers. Scaling depth is proven to increase the capacity of neural networks exponentially (Poole et al. (0016), and empirically improve transformer performance in natural language processing (Liu et al. 2020al Bachlechner et al. 2021) and computer vision (Zou et al. 2021). Graph neural networks also benent from more depth when properly designed (Chen et al. 2020at Liu et al. 2020b Li al. 2021). However, it is still not clear whether the capability of graph transformers in graph tasks can be strengthened by increasing model depth. So conduct experiments and find that current graph transformers encounter the bottleneck of improving performance by increasing depth. The further deepening will hurt performance when model exceeds 12 layers, which seems be the upper limit of the current graph transformer depth, as Figure [ (left) shows.
In this work, we aim answer why more self-attention layers become disadvantage for graph transformers, and how to address these issues with the proper model design. Self eeff-attention (Bah- danau et al. 2015) makes a leap in model capacity by dynamically concentrating on critical parts
Work done during internship at Microsoft
1 "Correponniig Author

---

Published as a conference paper at ICLR 2023
ZINC
-urr Stophoment-- -2)--541116
-Chr Dtre Gaphormeel-40) -50p-------------0 -40p-24)
0.15
Layer Altentton Capanity
2.112
0.08
20
35
Model Depth
Model Depth
Figure 1: Left: Performance on ZINC dataset of different graph transformers by varying their depths. Our DeepGraph successfully scales up the depth, while the baselines can not. (Lower is better.) Right: Layer attention capacity to substructures with depth.
(Chen et al. 2022). i.c., substructures of graph, and obtaining particular features. Substructures are the basic intrinsic features of graph data widely used in data analysis (Yu et al.) (2020) and machine learning (Shervashidze et al., 2009), as well as graph model interpretability (Miao et al. (022). Al- though the self-attention module appears be very beneficial for automatically learning important substructure features in the graph, our analysis indicates that this ability vanishes as depth grows, restricting the deeper graph transformer from learning useful structure features. Specifically, we focus on the influence of attention different substructures, which we found to decrease after each self-attention layer. In consequence, attention patterns of substructures and obtain expressive graph substructure features.
difficult for deep models to autonomously learn effective
We further propose a graph transformer model named DeepGraph with a simple but effective method to enhance substructure encoding ability of deeper graph transformer. The proposed model explicitly introduces local attention mechanism on substructures by employing additional substructure tokens in the model representation and applying local attention to nodes related to those substructures. Our method not only introduces the substructure based attention to encourage the model to focus on substructure feature, but also enlarges the attention capacity theoretically and empirically, which improves the expressiveness of representations learned on substructures.
In summary, our contributions are as follows:
We present the bottleneck of graph transformers' performance when depth increases, illus- trating the depth limitation of current graph transformers. We study the bottleneck from the perspective of attention capacity decay with layers theoretically and empirically, and demonstrate the difficulty for deep models to learn effective attention patterns of substruc- tures and obtain informative graph substructure features.
According to the above finding, we propose a simple yet effective local attention mecha- nism based on substructure tokens, promoting focus on local substructure features of deeper graph transformer and improving the expressiveness of learned representations.
Experiments show that our method unblocks the depth limitation of graph transformer and achieves state-of of-the-art results on standard graph benchmarks with deeper models.
2
RELATED WORK
Graph transformers Transformer with the self-attention has been the mainstream method in nature language processing (Vaswani al. 2017 Devlin al.) 2019: Liu et al., 2019), and also proven competitive for image in computer vision Dosovitskiy et al. 2020). Pure transformers lack relation information between tokens and need position encoding for structure information. Recent works apply transformers in graph tasks by designing a variety of structure encoding techniques. Some works embed structure information into graph nodes by methods including Laplacian vector, random walk, other feature (Zhang al. 2020 Dwivedi & Bresson, 2020 Kreuzer et al. 2021 Kim et al.)
2022 Wu et al. 2021). Some other works introduce structure information into attention by graph distance, path embedding feature encoded by GNN (Park et al. 2022 Maziarka al. 2020 Ying
eet al. 202T; Chen et al., 2022] Mialon et al. 2021: Choromanski et al. (022). Other works use
transformer module of the whole model (Bastos et al. 2022 Guo et al. 2022)
2

---

Published as a conference paper at ICLR 2023
Deep neural networks There many works focus solving obstacles and release potential of deep neural networks in sred-forward network (FNN) (Telgarsky) 2016: Yarotsky 2017) and convo- lutional neural network (CNN) (He et al. 2016a Simonyan & Zisserman 2014 Xiao et al. 2018
He et al.3 2016b). For graph neural networks, early studies reveal severe performance degradation when stacking many layers (Li et al.) 2019 Xu al. 2018b [i et al. 2018), caused by problems including over-smoothing and gradient vanishing (Oono & Suzuki 2019; Zhao & Akoglu 2019)
Rong al. 2019 Nt & Machara 2019). Recent works alleviate these problems by residual connec- tion, dropout, and other methods (Chen et al., 2020a Li et al. 2020; 2021), and deepen GNN into hundreds and even thousands of layers with better performance. Deep transformer is also proved (022) and computational vision (Zhou et al., 2021, J. while better initialization (Zhang et al. 2019) or architecture (Wang al. | Liu et al,,
powerful in nature language processing (Wang et al.
2020a Bachlechner et al.] [02T] are proposed to solve optimization instability and over-smoothing
(Shi et al. 2021 Wang et al. 2021 Dong et al. 2021).
Graph substructure Substructure is one of the basic intrinsic features of graph data, which is widely used in both graph data analysis (Shervashidze et al.] 2009 Yanardag Vishwanathan 2015) Rossi
et al.
2020) and deep graph neural models (Chen et al. 20200b
et al. [022]] Bodnar al., Zhang & Li [021] Zhao et al.) (021I. In application, substructure related methods are widely
2021
used
various domain including computational chemistry (Murray & Rees |2009] [Ti et al. 2018
2019
Duvenaud et al.] 2015] Yu et al. 2020), computational biology (Koyutürk et al.) 2004) and
social network (Jiang al.) 2010). Certain substructures can also be the pivotal feature for graph property prediction, which is a fundamental hypothesis in graph model interpretability studies (Ying
al.
2019 Miao al. 2022). helping to understand how graph model makes decisions.
PRELIMINARY
3.1
GRAPHI AND SUBSTRUCTURE
We denote graph data {G;, yi); where graph G = R,,, includes nodes N (1... |G| and corresponding edges R C N N, while x and r are node features and edge features. Label can be graph-wise or node-wise, depending on the task definition. Given graph G, a substructure is defined as G {Ns, RS _x. r. where N C N, R (NS x N W Rt i.e. nodes of GS form subset of the graph and edges are all the existing edges in G between nodes subset, which also known as induced subgraph. Because attention is only applied to graph nodes, attention to arbitrary subgraphs is not well-defined. Therefore, we only consider induced subgraphs in this work.
3.2 TRANSFORMER
The core module of the transformer is self-attention Let H: = [M,,... hnn] E Rxd be the hid- den representation in layer I, where is the number of token, and d, is the dimension of hidden em- bedding of each token. The self-attention mapping Attn with parameter WV, WQ, W Rdd and W RRdexds
A (H.W (H.WKKT Vdz
A so)tmax(A),
(I)
Attn(H;) AHW W VH
where VOO A W Wo In practice, a complete transformer layer also contains a two-layer fully- connected network FFN, and layer normalization with residual connection LN is also applied to both self-attention module and fully-connected network:
H1+1 = FFN(Att)()))),
(2)
where Attn(H) = LN(AHWVO), FFN(H') LN(ReLU(HWFF) + 16 T W Fs + 1677)..
IN()(X)) = (X f(x) 1B "D is the layer normalization, where D is diagonal matrix with
normalizing coefficients.
For graph transformer, structure information can be encoded into token representations or attentions. Our model adopts the distance and path- path-based relative position encoding methods as Ying et al. 2021). using graph distance DIS and shortest path information SP as relative position:
3

---

Published as a conference paper at ICLR 2023
A. (h,W9) (h, )
bis(C + Mean byx kEBP(s.))
(3)
vdl
We also employ deepnorm (Wang al. 2022 residual connection method in out model, which adjust the residual connection in layer normalization by constant yy: LN(((X)) = (nx + -(X)-
1b ) to stabilize the optimization of deep transformers.
Substmuctunes
Layer
Feeddl wowwwfo
Global Attention Nodes
Self Attention
For Noces
Substructure Enooding
Towns
Figure 2: Overview of the proposed graph encoding framework.
THEORETICAL RESULTS
In this section, we study the capacity of global attention to explain the depth bottleneck in graph transformers. The global attention is intended to focus on important substructures and learn expres- sive substructure representations automatically. However, the fact that graph transformers perform poorly when more layers are stacked raises doubts about the effectiveness of these self-attention layers. The attention layers require sufficient capacity to represent various substructures, which is necessary for learning attention patterns. We define attention capacity, analyze its variation with depth, and propose that local attention to substructures a potential solution.
4.1 DEFINITION OF ATTENTION CAPACITY
We define the capacity of attention as the maximum difference between representations learned by different substructure attention patterns. Let supp(e) be all the non-zero dimensions of vector e. We define a fixed attention pattern of substructure G as attention vector that only focuses nodes of GS, i.e., supp(e) = N where e E [0, 10" 1
Given graph G with several important substructures G.... G and corresponding attention pat- terns e1 Cm. denote E = (c1, 62 Cm) where columns of m patterns on substructures. We consider the attention space spanned by these attention patterns. At- tention from this space only focuses the important substructures:
are the base vectors of attention
As A Eclc E [o, 1)" c 11=1} 1),
(4)
Denote A as matrix space with columns all in space As. We then define attention capacity as the maximum difference between outputs computed by the self-attention with different attention matrices from space Ag. Let Aftna the self-attention mapping where attention matrix equals A.
Definition The attention capacity is defined as: Aitna, (H) ditns,(H)l
max Fи
Ae Ag Eag
(4.1)
1C ET HW C ET Ho
max (w.0cE(c10000.11xxx.ccc
Attention capacity in graph transformers is crucial. Larger capacity enables varying features by fo- cusing different substructures, while smaller capacity limits attention patterns' impact learned representations. Smaller capacity modules have difficulty learning attention patterns as they are less sensitive substructures.
4

---

Published as a conference paper at ICLR 2023
4.2 ATTENTION CAPACITY DECREASES WITH DEPTH
After defining the measure of attention capacity for substructures, we investigate the attention ca- pacity of graph transformers w.r.t depth both empirically and theoretically. We first empirically demonstrate how the attention capacity in the graph transformer varies with depth, then theoreti- cally analyze the phenomenon and possible solution.
The attention capacity of deep graph transformers for various substructures is computed per Defini- tion 4.1 and normalized by hidden embedding norm (see Appendix (G). Figure | (right) shows the results. Graphormer (Ying et al.] 2021)'s attention capacity decreases significantly after the 24th layer, while SAT (Chen et al. (022) decreases across all layers, indicating their limitations.
Next, illustrate that the stacked self-attention layers cause decreased attention capacity for deeper layers. We first demonstrate that the self-attention module decreases the capacity of attention, then discuss the case with funny-coneetted layers.
Theorem (The stacked attention modules decrease the capacity of attention) We analyze ca- (H; A.H.W.
pucity of attention FH, for stacked attention modules H,+1 Allm
1b T Dj. Assume H&W D; is full row rank for each layer i. Due to the property of layer nor- malization and properly designed initialization, assume the output of attention module equals to ( Then the attention capacity of layer is upper
its input, ie.. for input X, [Xt]n(X)le = bounded by
FB, S v 2m Il (ax) Pm ET 22W 12|PHl
(5)
W D.IF where 04 (PH.+A.PH..NO -16 )Dlrr
with probability I, and a (T- 111"), P.
"D.le
(I -1-17 )."".
Proof is in Appendix The analysis above reveals that the self-attentic module decreases the upper bound of attention capacity exponentially. We next consider the case when fully-connected layers are also included in each layer, just like the architecture practice.
Theorem (The upper bound of attention capacity after stacked transformer layers) For transformer layer with self-attention H! Attn (H,) (H, + A.H,WVO 1b, Dr and fully- connected layer H.+1 FFN(H;) (H₃ + ReLU (H;W: + + >w: + + - N.. DD', with the same assumption as the previous, attention capacity of layer upper bounded as follows:
FH < v 2m Parr)) E 2 PHHle
(6)
where 0g (PH.APA... VO
< with probability 1, and % = [1 +
(PH.+A.PH...O -16." yD.le
R (.W.a.)) l2).
Proof in Appendix 2 Fully-connected layer impact can be bounded by coefficients %. which de- scribe hidden embedding norm change. Previous work Shi al. (202T) shows that % is dominated by D2 and for fraction of data D < 1, leading to attention capacity vanishing in these cases.
4.3 LOCAL ATTENTION FOR DEEP MODEL.
Reducing attention capacity with depth creates two problems for graph transformers: difficulty at- tending to substructures and loss feature expressiveness to substructures. To address the first problem, it's natural to introduce substructure-baset local attention inductive bias into graph transformer to make up for the deficiency of attention on substructures, where each node can only attend to other nodes that belong to same substructures. Furthermore, We will next show that intro- ducing substructures based local attention also addresses the second problem. We next prove that capacity decay be alleviated if local attention to substructures is applied in each layer.
5

---

Published as a conference paper at ICLR 2023
Theorem Define substructure based local attention where each node only attends nodes that belong to the same substructures. Assume that for each node, the number of nodes belonging to the same substructures is most where Theorem [ and a be the decay coefficient of the global attention model. Denoted minimum of a² and for all possible representation H2 and model parameters by a² and of respectively. Then we have a** > a².
Let a² be the decay coefficient of this model in
The proof is in Appendix 3 This theory illustrates that substructure based local attention not only introduces the substructure based attention to encourage the model to focus on substructure features but also enlarges the attention capacity of deep layers, which promotes the representation capacity of the model when it grows deep.
5 APPROACH
Replacing global attention directly with local attention may lead to insufficient learning ability of the model for long-range dependencies. To better introduce local attention to substructure in self- attention models, we propose a novel substructure token based local attention method, DeepGraph, Figure 2 shows. DeepGraph tokenizes the graph into node level and substructure level. Local attention is applied to the substructure token and corresponding nodes, while the global attention between nodes is still preserved. This provides better solution for explicitly introducing attention to substructures in the model while combining global attention, to achieve hetter global-local encoding balance.
Our method first samples substructures of the graph, then encodes substructures into tokens, and finally enforces local attention on substructures.
5.1 SUBSTRUCTURE SAMPLING
As we aim to stress critical substructures in graph, there are numerous types of substructures that are categorized into two groups: neighbors containing local features, such k-hop neighbors Zhang & Li] (2021) and random walk neighbors (Zao et al. (202I), D. and geometric substructures represent- ing graph topological features, such as circles Bodnar et al. (202I), paths, stars, and other special subgraphs Bourrisaa (aggritssBBuusssss et al. (2022). We integrate these substructures into unified substructure vocab- ulary in this work. In order to match geometric substructures, we use the Python package graph-tool that performs efficient subgraph matching. It is practical pre-compute these substructures once, and then cache them for reuse. It takes about 3 minutes to compute all the substructures of ZINC, and about 2 hours for PCQM4M-LSC.
Substructures in a graph often exceed the number of nodes. In order to ensure the feasibility of the computation, we sample substructures each computation. Formally, at each time of encoding, for graph G with the corresponding substructure set {G$), }, we sample a subset {G$, G G as input to our model:
{G ....G.G... SubstructurrSamplinn(((")) }),
9 DeepGraph CGffGG.... G..))
We hope the sampled substructures cover every node of the graph as evenly possible (Zhao et al., 2021) in order to reduce biases resulting from the uneven density of substructures. We also balance the types of substructures in our sampling, due to the divergent ratios of different substructure types graph. The details are in Appendix C and
5.2 SUBSTRUCTURE TOKEN ENCODING
The input embedding contains node tokens embedding {h1, (f1,h2.... he,.h.,...... hn and substructure tokens embedding (hn+1...., hn+m). }. encoded by node feature encoder In and substructure encoder gs individually. The token embedding of graph nodes is mapped from graph node feature feature vector h: h; = 9n (r.), i (1,2.... n.).
For the substructure tokens, apply permutation baasud structure encoding (Mrrhyy et al. 2019; Chen et al.] [020bb Nikolentzos Vazirgianni) 2020) by encoding the substructure adjacency ma- trix A directly. The core idea of permutation- based encoding pooling the encoding output of

---

Published as a conference paper at ICLR 2023
permuted graph information over all the possible permutations. which is permutation invariian and has no information loss. We further apply depth-first search (DFS) with the order of node degree to reduce the possible order of substructure nodes. At the beginning and at each step of DFS, use degrees to sort nodes. random node from the ones with the least degree is selected as the starting point for DFS. The nodes are sorted according to their degree each DFS step, while the same-degree nodes are randomly permuted. See Appendix [ for more details. Using this method, the graph encoding permutations is invariant and the number of possible combinations is greatly reduced. The formal definition of substructure token encoder is
nn-i
Pool Is (T(T(A))), E (1,2.... TEDFS(AF)
(8)
In practice, sampling is applied instead of pooling. A single sample is sufficient during training to allow the model to learn the substructure stably.
5.3 LOCAL ATTENTION ON SUBSTRUCTURES
The substructure and its corresponding nodes receive localized attention after substructure tokens have been added. Given input embedding H1 = (h,, h2...., hntm), mask M is added in self- attention module Attnm (H, M) as
Atinm (11,, M) softmax(Á M)H.WO
where Mij (00-00), i.e., the elements of mask M can be 0 or -o, leading to sparse attention matrix A with zero in position of -oo in M. In our model, the mask is defined as follows to induce local attention substructure tokens and corresponding nodes: Mij Oc if
{n + 1, n + 2, ... m & N j + n E {n + 1, n + 2, 2,... m), N and Mi otherwise. The substructure tokens only apply local attention to corresponding nodes.
The attention in our model is combination of local attention substructures and global atten- tion. Substructure tokens are the core of local attention, attending only to corresponding nodes, and integrating representation from the whole substructure. Nodes belonging to the same substructure share a substructure token message, increasing distinguishability of substructures and promoting substructure representation capacity.
EXPERIMENTS
In this section, we aim to validate the performance of DeepGraph empirically. Specifically, we attempt to answer the following questions: (i) How does DeepGraph perform in comparison to existing transformers
popular benchmarks? (ii) Does DeepGraph's 's performance improve with increasing depth? (iii) Is DeepGraph capable of alleviating the problem of shrinking attention ca- pacity? (IV) What is the impact of each part of the model overall performance? We first conduct experiments to evaluate our model on four popular graph datasets, comparing it with wate-of-the-as graph transformer models, as well their augmented deeper versions. Then we illustrate the atten- tion capacity of DeepGraph by visualization. Finally, we validate the effect of different components through ablation studies. Codes are available at https://gitub..om//aaa com//hao www.m//hhoo//eeeerraappppp
6.1 DATASETS
Our method is validated on the tasks of the graph property prediction and node classification, specifically including PCQM4M-LSC (Hu et al.] 2020). ZINC (Dwivedi al., 2020). CLUSTER (Dwivedi et al. 2020) and PATTERN (Dwivedi et al. 2020), widely used in graph transformer stud- ies. PCQM4M-MMMMPP -SCCMM--SCCEE a large-scale graph-level regression dataset with more than 3.8M molecules. ZINC consists of 12,000 graphs with molecule property for regression. CLUSTER and PATTERN are challenging node classification tasks with graph sizes varying from dozens to hundreds, contain- ing 14,000 and 12,000 graphs, respectively.
6.2 BASELINES
We choose recent state-of-art graph transformer models: GT Dwiieedi & Bresson Kreuzer et al. 202T), Graphormer (Ying et al., 2021) and SAT (Chen al. 2022), covering various
2020). SAN
7

---

Published as a conference paper at ICLR 2023
Graph regression
Node classification
PCOMAM-ISC..
ZINC +
CLUSTER
PATTERN
GCN
0.1691
0.367 0.011
68.498 1 0.976
71.892 0.334
GIN
0.1537
0,526 0.051
64.716 + 1,553
85.387 0.136
GT-sparse
0.014
73.169 1 0.622
84,808 0.068
GT-Fuull
0.598 0.049
27.121 = 8.471
56.482 3.549
SAN-Sparse
0.198 0.004
75.738 = 0.106
81.329 2.150
SAN-Full
0.139 0.006
76.691 4: 0.247
86.581
Graphormer
0.1234
0.002
SAT
0.094 0.008
77.856 0.104
86.865 0.043
DeepGrraph (12)
0.1220
0.078 0.006
77.526 0.122
90.015 0.038
DeepGraph (24)
0,1206
0.076 0.004
77.810 0.167
90,522 0.059
DeepGraph (48)
0.1193
0.072 0.004
77.912 0.138
90.657 0.062
Table 1: Comparison of our DeepGraph to SOTA methods on graph regression and node classifica- tion tasks.
graph transformer methods including absolute and relative position embedding. Graph neural net- works baselines includes GCN (Kipf & Welling 2016) and GIN (Xu et al. 2018a). We first compare model with the deepened model with the standard state-of-art models. Then we compare state-of-arts augmented by recent algorithms for deep transformers, including the fusion method (Shi et al., 2, and reattention method (Zhou 202TT. As training process, we compare DeepGraph to naive deepnorm in the ablation study.
deepnorm stabilize
6.3 SETTINGS
We implement DeepGraph with 12, 24, and 48 layers. The hidden dimension is 80 for ZINC and PATTERN, 48 for CLUSTER, and 768 for PCQM4M-LSC. The training uses Adam optimizer, with warm-up and decaying learning rates. Reported results are the average of over 4 seeds. Both geometric substructure and neighbors are used as substructure patterns in our model. We imply both geometric substructures and k-hop neighbors on ZINC and PCQM4M-LSC. As for CLUSTER and PATTERN, only random walk neighbors are used due to the large scale and dense connection of these two datasets. The effect of different substructure patterns shown the ablation study.
6.4 MAIN RESULTS
Table I summarizes our experimental results on the graph regression and node classification tasks. The data for the baseline models are taken from their papers. The depth of our model varies from 12 to 48 layers. As the results illustrated, our 12-layer model outperforms baseline models on PCQM4M-LSC, ZINC, and PATTERN, especially on ZINC and PATTERN, surpassing the pre- vious best result reported significantly. As model depth increases, our model achieves consistent improvement. Note that our model with 48 layers outperforms baseline models on all the datasets, proving the effectiveness of more stacked DeepGraph layers. The parameter number of each model for each dataset is provided in Appendix
6.5 EFFECT OF DEEPENING
We next compare DeepGraph with other deepened baseline models. We choose Graphormer and SAT as baseline models, and we deepen them by 2 and 4 times compared to the original version. Along with deepening naively, we also enhance baseline models through the fusion method and reattention method.
DeepGraph 12 DeepGraph 48
ZINC CLUSTER ZINC CLUSTER
local attention
0.135
76.167
0.141
76.133
DrepGiraph 12 DeepGirahh
substructure encoding
0.085
76.531
0.124
77.884
Geometric only 0,078
0.075
deepnorm
0.080
77.202
0.074
77.682
Neighbors only 0.086
0.079
DeepGiraph 0.078
77.526
0.072
77.912
Both
0.078
0.072
Table 2: Ablation study of local attention, substructure Table 3: Sensitivity study of different sub- encoding, and deepnorm ZINC and CLUSTER.
structure types ZINC.
8

---

Published as a conference paper at ICLR 2023
comeovaah sPI, whe
2095
CAT MiL
COMERNNNY MALLWWI -AALI SAT
3322
1123
Zoat
07.2
Vocel Depir
Food Depth
Hodel Depth
Depth
Figure 3: Comparison of DeepGraph to SOTA methods deepened by different deep transformer methods.
As shown in Figure DeepGraph outperforms baselines by a significant margin. Naive deepening decreases performance on all the datasets for both baseline models. Note that all the 4-time deep SAT fail to converge CLUSTER due to the training difficulty, as well Graphormer with reattention. Fusion improves deeper Graphormer on PCQM4M-LSC, and reattention boosts 2x deep SAT on CLUSTER slightly. but none of them are consistent. Our methods surpass fusion and reattention methods stably on all 4 datasets, supporting our theoretical claim that sensitivity to substructures is crucial in deep graph transformers.
6.6 VISUALIZATION OF ATTENTION CAPACITY
We visualize attention capacity of our method and deep baselines on ZINC dataset, using the same substructures as our model. Additionally, to illustrate the capacity token representation sub- structures, we also directly compute the maximum difference between all the substructure tokens value vectors. All the results are normalized by the corresponding representation norm. See Ap- for details. The results are plotted in Figure[[rrght]
First, the attention capacity our model remains high across all layers as compared to baselines, indicating that cubstructure-basee local attention can be useful method for preventing attention deficits. Second, substructure tokens have a much higher capacity than attention capacity computed on nodes, demonstrating the benefits of using substructure tokens for substructure encoding.
6.7 ABLATION AND SENSITIVITY STUDY
Finally, we verify our model's effectiveness through an ablation study on ZINC and CLUSTER tasks, removing local attention, substructure encoding, and deepnorm to observe their impact. Note that without local attention, the model is only a relative position-based graph transformer with deep- norm residual connections. Without substructure encoding, randomly initialized embedding is ap- plied to each substructure token. Results in Table 2 show that without local attention, performance decreases significantly on both datasets, especially for deeper models, proving the effectiveness of the proposed methods. Furthermore, substructure encoding also plays an instrumental role, em- phasizing the importance of structural information. Finally, deepnorm also contributes to model performance by stabilizing the optimization, especially for 48-layer models.
We validate the sensitivity of our model to different substructure types by testing the performance of DeepGraph with only geometric substructures or neighbors. Table 3 indicates that both contribute to performance, but geometric substructures are more critical for ZINC. This result expected because specific structures like rings important fundamental features for the molecule data, and it can be further strengthened when combined with neighbor substructures. Our model can flexibly different forms of substructure to fully utilize prior knowledge of data.
7 CONCLUSIONS
This work presents the bottleneck of graph transformers' performance when depth increases. By empirical and theoretical analysis, we find that deep graph transformers are limited by the capac- ity bottleneck of graph attention. Furthermore, we propose novel graph transformer model based on substructure- based local attention with additional substructure tokens. Our model enhances the ability of the attention mechanism to focus substructures and addresses the limitation of encod- ing expressive features as the model deepens. Experiments show that our model breaks the depth bottleneck and achieves state-of-the-art performance popular graph benchmarks.

---

Published as a conference paper at ICLR 2023
REFERENCES
Uri Alon and Fran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2020.
Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley. Rezero is all you need: Fast convergence at large depth. In Uncertainty in Artificial Intelligence, pp. 1352-1361. PMIR, 2021.
Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
Anson Bastos, Abhishek Nadgeri, Kuldeep Singh, Hiroki Kanezashi, Toyotaro Suzumura, and Isa- iah Onando Mulang. Investigating expressiveness of transformer in spectral domain for graphs. arXiv preprint arXiv:2201.093: 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Infor- mation Processing Systems, 34:2625-2640, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph rep- resentation learning. In International Conference on Machine Learning, pp. 3469-3489, PMLR, 2022.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020a.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33: 33:10383-10395, 2020b.
Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosh- erstov, Jack Parker-Holdd Tamas Sarlos, Adrian Weller, and Thomas Weingarten. From block- toeplitz matrices to differential equations on graphs: towards general theory for scalable masked transformers. In International Conference on Machine Learning, pp. 3962-3983, PMLR, 2022.
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume 1 (Long and Short Papers), pp. 4171-4188 2019.
Yihe Dong, Jean-Baptin Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learming, pp. 2793-2803. PMLR, 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An im- age is worth 16x16 words: Transformers for image recognition at scale. International Confer- ence on Learning Representations, 2020.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
10

---

Published as a conference paper at ICLR 2023
Lingbing Guo, Qiang Zhang, and Huajun Chen. Unleashing the power of transformer for graphs. arXiv preprint arXiv:2202.1058) 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645. Springer, 2016b.
Han Hu, Zheng Zhang, Zhenda Xie, and Stephen Lin. Local relation networks for image recognition. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 3464-3473, 2019.
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, 33:22118 18-22133, 2020.
Chuntao Jiang, Frans Coenen, and Michele Zito. Finding frequent subgraphs in longitudinal social network data using weighted graph mining approach. In International Conference on Advanced Data Mining and Applications, pp. 405-416 Springer, 2010.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. International conference on machine learning, pp. 2323-2332. PMLR, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical molecules. arXiv preprint arXiv:1907 1007.//223,, 2019.
translation for
Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Se- unghoon Hong. Pure transformers are powerful graph learners. arXiv preprint arXiv:2207.025005 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: (ETi:1600002907 2016.
Mehmet Koyutürk, Ananth Grama, and Wojciech Szpankowski. An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics, 20(suppl 1:1200-i207,, 2004.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 01221618-2122 2021.
Taku Kudo and John Richardson. Sentencepiece: simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing: System Demonstrations, pp. 66-71, 2018.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference computer vision, pp- 0267-9276, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.0773 07739, 2020.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437-6449, PMLR, 2021.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the diffi- culty of training transformers. In 2020 Conference Empirical Methods in Natural Language Processing, EMNLP 2020, pp. 5747-5763. Association for Computational Linguistics (ACL), 2020a.
11

---

Published as a conference paper at ICLR 2023
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 338-348, 2020b.
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. / 1692, 2019.
Lukasz Maziarka, Tomasz Danel, Stawomir Mucha, Krzysztof Rataj, Jacek Tabor, and Stanistaw Jastrzebski. Molecule attention transformer. arXiv preprint (tt::20022008264, 2020.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106005667 2021.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic atten- tion mechanism. In International Conference on Machine Learning, pp. 15524-15543, PMLR, 2022.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673. PMLR, 2019.
Christopher W Murray and David C Rees. The rise of fragment-based drug discovery. Nature chemistry, 1(3):177-92,, 2009.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. Advances in Neural Information Processing Systems, 53:16211-1622 2020.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 19Xx::9005005500 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2019.
Wonpyo Park, Woong-Gi Chang. Donggeon Lee, Juntae Kim, et al. Grpe: Relative positional encoding for graph transformer. In ICLR2022 Machine Learning for Drug Discovery, 2022.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In International conference machine learning, pp. 4055- 4064. PMLR, 2018.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
Ryan A Rossi, Nesreen Ahmed, Eunyee Koh, Sungchul Kim, Anup Rao, and Yasin Abbasi- Yadkori. A structural graph representation learning framework. In Proceedings of the 13th inter- national conference on web search and data mining, pp. 483-491, 2020.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. Artificial intelligence and statistics, pp- PMLR, 2009.
Han Shi, JIAUUI GAO, Hang Xu, Xiaodan Liang. Zhenguo Li, Lingpeng Kong, Stephen MS Lee, and James Kwok. Revisiting over-smoothing in bert from the perspective of graph. In Interna- tional Conference on Learning Representations, 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
12

---

Published as a conference paper at ICLR 2023
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp- 1517-1539. PMLR, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Hongyu Wang, Shuming Ma, Li Dong, Shaohan Huang, Dongdong Zhang, and Furu Wei. Deepnet: Scaling transformers 1,000 layers. arXiv preprint arXiv:2203.0055: 00555,, 2022.
Peihao Wang, Wenqing Zheng, Tianlong Chen, and Zhangyang Wang. Anti-oversmoothing in deep vision transformers via the fourier domain analysis: From theory to practice. In International Conference on Learning Representations, 2021.
Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek F Wong, and Lidia S Chao. Learning deep transformer models for machine translation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1810-1822, 2019.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34: 1111666613277 2021.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla con- volutional neural networks. In International Conference Machine Learning, pp. 5393-5402. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning. pp. 5453-5462. PMLR, 2018b.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 1365-1374, 2015.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Chengxuan Ying. Tianle Cai. Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888. 2021.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gan explainer: A tool for post-hoc explanation of graph neural networks. arXiv preprint arXi:: 0.994, 2019.
Shuo Yu, Yufan Feng, Da Zhang, Hayat Dino Bedru, Bo Xu, and Feng Xia. Motif discovery in networks: a survey. Computer Science Review, 37:100267, 2020.
Biao Zhang, Ivan Titov, and Rico Sennrich. Improving deep transformer with depth-scaled initial- ization and merged attention. In 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Join! Conference on Natural Language Processing, pp. 898- 909. Association for Computational Linguisties (ACL), 2019.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05 2020.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Process- ing Systems, 34:15734-15744 2021.
Lingxiao Zhao and Leman Akoglu. Paimorm: Tackling oversmoothing in gnns. In International Conference Learning Representations, 2019.
13

---

Published as a conference paper at ICLR 2023
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2021.
Daquan Zhou, Bingyi Kang, Xiaojie Jin, Linjie Yang, Xiaochen Lian, Zihang Jiang, Qibin Hou, and Jiashi Feng. Deepvit: Towards deeper vision transformer. arXiv preprint arXiv:2103.118880 2021.
14

---

Published as a conference paper at ICLR 2023
A PROOF OF THEOREMS
Proof for brevity, define P 2 (I- -11" and Pm & (1- (1-1111)) We first introduce an important property of P: For any matrix B with left eigenvector BI 31, have PBC=PBPC,VC: To
prove it, can deompose C = PC + 11 C. Then
PBC PB C) PBPC +
PBPC
We next prove the main theorem by recursion. By definition,
Fи
Af .. EAB |Attn A, (H) - Ait (H))F
max
[, CCT-II 10 F. HWVO FF F
(10)
|(C - -2) ESSEEE ET HW
max [LCC 1=
Note that (C1 (C- so we can multiply Pm before it:
Fn
max [, ,C/1=1)
|(1 C2) E H
[C] - C2) TT P E HL
max
G,C0EE11CC(0011mx 1=
(II)
[C1 C2) 12 Pm E" HWV
max C.C.E(CICC((..)mm. 1)
22ml Pm FTT HW
where - ((C--C2)* S VI(CI 12) - (2 V2m.
We further decompose Pm, ET HWVO Ip into
P.E HO F = Pm PHWVO |F S Pmm" 121
(12)
For layer 1, recursively compute PH by |HH for layer = 1 1, 2, .... 1:
|PH IP(H, A.H.W 16,2 )d,(r
IPPH + A.P.W.V 16 Ddle
P(PH, + A,PH,WYO IbNT) Dal I(HH A.P.H,YO Ib,7 "Ddl PH
I(PH, A,PH.WYO 1NNT Del
|HH,IP
= =aiA|PHilp
(13)
IP(PH. 16 - Ddle where as (PH.+A.PH.WYY 1b. "DDl
and X; (PH.+A.PH.WY
16 )D,le
[HA.
Note that P = (I L11²) -1" is contraction mapping, so OG S 1, and equal to 1 if and only if A,P.H.WYDD, 16N" D; is orthogonal to the 1-stretched space, which usually impossible, because -1b," D, is in the 1-stretched space, and the probability that projection of A; A,PH,WVO D, on 1-stretched space equals to 16N D, is O due to the property of random matrix. We further show that A,P..WVO D2 is full-rank with probability 1: As assumption, H,WVO D; is full-rank, and 1-stretched space is the only subspace that PH, PH,WW. WYO D, is orthogonal to, i.e.
A JPH.WYY V D, 0 =
15

---

Published as a conference paper at ICLR 2023
So 1" A,PH,WWOD, = 0, 1"A, B1", i.e. AT 31, the probability of which is 0 for random parameters in transformer.
For coefficient X due to the property of layer normalization and good parameter initialization that keeps norm of output equals to input, i.e. [[X + A,XWY - 1b, ) Dilr/XX | Re 1,VX, we have X 1.
Based on the analysis above, we can bound FH, recursively:
FBI S 2m (a.) Pm E WW PHilF
(14)
where a; P.PH. -16
PP (PH.AA,, -D,l')D.1e
1 with probabil-
[PH: -115 DDile
ity I.
Proof 2 As the same method in the previous proof, we need to recursively bound |PHetale by [ for layer = I- 1,1- 2....; Deate Hi = At),(H;), and H441 -H)) Similar to the previous proof, have
PH
Ib, D
-P(PH + A,PH.WYO 1b5² Dilr
IP(PH, + A.H.W - IbN') D I(PH, + A.P.W,YO - 16 "DilE |H
I(PH; + A.H.W. 16,2 Drl
PH1|
= =
(15)
As for PH4+1, we can bound it as
PH P(H ReLU + 1b T |w 1b - -IbNo D
)
P | + 11, F. WW DAlF
S P|E|
11, F. ){F W
(16)
< P| 1 W [
(2 + 11 PH
So the final conclusion is
FH, < 22m II (ara)) / "
|PHHI
(17)
- )D,
(PPH.-AAHH,
where a; (P..AA.P..WY -1677 -D,,"
(PH..A.PH.WY. -16, -NO"" "D.IE 1 with probabil-
ity 1, and D122(1 + ( (2]W 12).
Proof 3 We denote global attention and local attention by A and A", respectively.
(P
By definition, a; [PH.+A.PH,WWD "D.IF"
We analyse the worst case for oc:
16

---

Published as a conference paper at ICLR 2023
(IHH, PA,H,WYY))DA
04 IPH, + A.H.WWY DDN")
(PH, PA
(18)
I(PH (P 1111 A.PHH, (P 16 )
(IPH, PAH.WW
+ (A.HWWYO)D.lp | A.PH,,YO + + Dilr
Further analysis on 1/ 11 W,P..W Dilr shows that
11 A.P.WW Dilr | A.P.H.W Dale
(19)
S S!HWW D. PAT
where PAT1 A7 the element of which between [-1,n 1). and the sum of all elements of which is O. The maximum of A 1/2 is achieved when element is - and other elements are -.
However, for local attention A that each node is only attended by most nodes, where T n, the elements P A 1/2 is only between 1-1,- 1), and thus the maximum | 1/2 2 is less than |PA. 1/2.
We further address that the two inequalities in 18 and both can be achieved for proper H; and parameters. So we can conclude that for the worst case of and of, denoted by af and af""
< at
B DISCUSSION OF SUBSTRUCTURE BASED ATTENTION SPACE
In Definition 4.1 for a substructure G the fixed attention pattern e is an ideal attention pattern to help concentrate the information of this substructure, for example, uniform attention vector on a benzene ring, or attention on a two-hop neighbor graph attenuating according to the distance the central node. Traditional GNN is also an example of such a fixed attention pattern, where each node takes uniform attention to its' neighbor nodes. Although we treat this pattern as fixed on the substructure, we denote that the definition is general because the value can be any learnable attention pattern.
The defined attention space construct attention patterns for all meaningful attention on substructures by containing the combination of all the elementary substructure pattern. As this substructure at- tention patterns are considered important indicative bias, the graph transformer expected to learn attention patterns in this space to utilize the substructure feature. This definition is also general and expressive, as sufficient patterns can added include more general cases.
C SUBSTRUCTURES
The sizes of the different substructures used in this study neighbor substructures including 2-hop neighbor and 10-step random walk neighbor, and geometric substructures including circle with size from star with size from 6, and path with size from 4 to 8. For geometric substructures. we use the python package graph-tool for substructure matching. It takes about minutes to match all the geometric substructures of ZINC, and about hours for PCQM4M-LSC. We cache all the substructures for reuse.
D SURSTRRUCTURSSAMPLNSS
greedy sampling algorithm is used for the substructure sampling process. In each step of the iter- ation, nodes with less coverage have greater probability of being covered in the next iteration. At
17

---

Published as a conference paper at ICLR 2023
the beginning of sampling, randomly select Rona substructures from all the substructures, where different types of substructures are balanced. In each iteration, we first mark nodes as set Nieft that are covered less than threshold thre times by already sampled substructures. Then calculate enly for each substructure left, which is the number nodes in Nieft covered by substructure G. We select sampple from substructures with top k ent randomly. The iteration ends when each node is covered at least thre times, or no substructure is left. In the algorithm, Néxit. k. and nammple determined by thre and nodes number to speed up the iteration and increase sampling variance, while retaining that nodes are covered as evenly as possible.
E DEPTH-FIRST SEARCH (DFS)
We use degree to sort nodes at the beginning of DFS and each step. In the beginning, DFS start from node uniformly sampled from nodes with the least degree. At each step, nodes are sorted according to degree, while nodes with the same degree are permuted randomly. This method keeps the graph encoding permutation invariant, and reduces possible permutations a lot. The drawhack of permutation- encoding is that the number of possible permutations becomes intractable when the graph is large. Fortunately, the substructure size is usually not larger than 10.
F RELATED WORK OF TOKEN UNIT
The most suitable basic unit for transformer as a token has been studied in many works in natural language processing and computational vision. For nature language, sentences are separated into sub-words containing a variant number of primary characters (Kudo & Richardson 2018). In com- putational vision, while previous works apply transformer directly image pixels (Parmar al., 2018 Hu et al. 2019), recent works find more beneficial to treat patches as tokens (Dosovitskiy al. 2020), indicating the importance of proper segmentation of the input. For graph transformers, tokens in most current studies are nodes. We propose to encode substructures together with nodes in the graph as tokens the transformer.
G EMPIRICAL STUDY ON ATTENTION CAPACITY
We empirically explore the capacity of the model for the substructure, and validate our theoretical results. We aim to answer the following three questions: (1) Do attention capacity really decreases in deeper graph transformer?
(2) Can our method, i.e., local attention with substructure tokens, help to increase model capacity of representing substructures? (3) Can our method, i.e., local attention with substructure tokens, help to alleviate attention capacity decrease?
We visualize the attention capacity of our method and deep baselines on the ZINC dataset. The set of substructures is the same as the substructures used in our model, while the base vectors E are defined as uniform distributions supported on corresponding substructures. Because attention capacity in Definition 4.1 depends on the norm of hidden representations, we normalize it by the norm of all the value vectors Σi=1.... 1h, WV la to eliminate the influence of the representation norm. Note that for our model, only node tokens are considered. Additionally, because we explicitly tokenize substructures tokens, also directly compute the maximum difference between all the substructure tokens value vectors, mea.,,e(....m) [hs+n wvo hyt WVO la. and normalize by
1 m "E_1... Ih WVV,,,, to illustrate the capacity of token representation of substructures. The results are plotted in Figure (right). (right)(right)..
First, the result of Graphormer and SAT reveals that attention capacity of substructures decreases in deep layers. Note that in the shallow layer the attention capacity of Graphormer increases, which is not contradicting our theory because we only claim that the upper bound of attention capacity decrease with depth. However, after the 24th layer, attention capacity decreases a lot, revealing the problem of deepening graph transformer. Note that because SAT uses GNN encode substructures for query and key computation, it has a high attention capacity in the first layer. However, it decays fast due the property of global attention.
Second, the result of our model indicates that local attention attention-based substructure tokens improve substructure representation capacity. The difference between substructure tokens is much larger
18

---

Published as a conference paper at ICLR 2023
than the representation learned by attention substructures, indicating learning substructure token representation by local attention can significantly improve the representation capacity of model, which supports our first motivation that introducing substructure-baat local attention help model to encode substructures better.
Finally, compared to baselines, attention capacity of model remains high across all the layers. Although it drops from 0.96 to 0.90 after the 24th layer, the dropping ratio smaller than the baseline graph transformer. This supports our claim that substructure-bassd local attention helps alleviate attention capacity decrease. Note that the capacity of substructure tokens also decreases slower.
H PARAMETER NUMBER COMPARISON
We list parameter numbers of our model and baselines. Note that parameter numbers of Graphormer and SAT computed by running their official code directly, and other baselines are from papers. The parameter number of SAT (*1) different from reported in their papers, which may be due code updates. The parameter number of our base model is comparable previous works, and even less on CLUSTER. The parameter number of our deeper model is also comparable to deeper baselines, while our performance surpasses them.
layer PCQM4M-LSC
ZINC
CLUSTER
PATTERN
GCN
2.0M
421k
571k
380k
GIN GT-Sparse
3.8M
495k
684k
455k
588,929
524,026
522,982
GT-Full
588,929
524,026
522,982
Spa-Se
494.865
530,036
493,340
SAN-Full
508.577
519.186
507,202
Graphormer
44,750,081
489,321
x2
87,309,569
1,055,985
x4
172,428,545
1,996,785
SAT
x1
499,681
741,990
825,986
x2
991,873
1,480,806
1,646,978
x4
1,976,257
2,958,438
3,288,962
Ours
x1
45,563,393
612,705
382,865
612,705
x2
88,122,881
1,078,225
686,225
1,083,
x4
173,241,851
2,019,025
989,585
2,023,905
I TIME COMPLEXITY
The time complexity our methods is mainly due to the larger input size, which increases the cost of transformer. Given graph size N and sampled substructure number M, the complexity of transformer O(M + N) However, as we use sampling to reduce the substructure number, the substructure number is less than the graph size, i.e. M < N, the complexity will not be more than four times of the standard transformer and remains O(N2).
J ABLATION STUDY ON NEIGHBOR SIZE
We conduct ablation studies for random walk neighbors CLUSTER and PATTERN datasets. While we use size 10 neighbors in the paper, we compare the performance with sizes and 15. The result is as follows:
CLUSTER
PATTERN
12
48
12
48
size 5
77.2
77.7
90.1
90.6
size 15
77.1
78
89.6
90.4
size 10
77.5
77.9
90
90.7
19

---

Published as a conference paper at ICLR 2023
The result shows that the performance remains robust to different substructure sizes, especially the deeper model. Smaller substructures are easy for the model to learn its structure features, but they may not cover enough nodes and provide good graph structure information. Larger substructures are more informative about graph feature, but is more difficult for stable learning, especially for shallow model.
20


Reviews:
[{"review_id": "uzT-3aA9Sxc", "reviewer": "Reviewer_n5Mh", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper studies the limitations to deepen graph transformers and argue that substructure learning gets increasingly harder in the canonical formulation of the graph transformers. To address this limitation, the paper proposes a variant of graph transformers that explicitly models substructure attention and encoding. Empirical results suggest that the proposed DeepGraph approach is effective and competitive.", "summary_of_the_review": "Overall, I find the paper interesting and it provides a good insight into how substructure modeling plays a role in the attention and expressivity of modern graph transformers. There is still an obvious gap between the theory section and the empirical section (e.g., the paper did not empirically verify any of the theoretical conclusions), but the empirical results are quite good. I'm inclined to acceptance on the condition that my questions can be answered satisfactorily.", "strength_and_weaknesses": "Strengths:\n1) The paper tries to provide both theoretical and empirical insights on the importance of substructure sensitivity to the capacity of graph transformers.\n2) The writing is generally clear.\n3) I think the problem in itself is interesting (i.e., how can we train deeper graph transformers).\n4) Good empirical results and ablative studies.\n\nWeaknesses/questions:\n1) While it's nice that the paper provides theoretical analysis on the model capacity, it is unclear to me how meaningful they are. Specifically, for example:\n    - Inequality (6) provides an upper bound. In practice, $C_1$ and $C_2$ also depends on $H_\\ell$, so they are not independent. This makes the inequality (12) in the Appendix potentially vacuous. Moreover, while $\\alpha_i$ is accumulated in inequality (6) across layers indeed, it is unclear how $W_\\ell^{VO}$ (which is learnable) evolves across depth. Could it balance this decay process? As another example, Theorem 3 is merely comparing two upper bounds. Without any evidence on the looseness of these upper bounds, it's hard to evaluate the value of this theorem. It'd be great if the authors could elaborate on issues like these.\n    - The theoretical results applies mainly to the input level. $G_1^S, \\dots, G_m^S$ makes sense at the input layer where each node contains the information only about itself. But starting from layer 2, the hidden units already combines information from all lower-level nodes, making the substructure argument a bit vague.\n2) Given the assumptions, the theoretical results should also largely apply to the original (non-graph) transformers, such as those used in NLP. And yet we are able to train very deep transformers there, even though substructures do exist in language. Could the authors discuss more what their results imply in non-graph applications?\n3) Do techniques that allow very deep training of conventional transformers help deepen graph transformers (e.g., ReZero)? This would be an interesting ablative study that demonstrates why the substructure attention is a better alternative for graphs.\n4) For PCQM4M-LSC and ZINC, the # of nodes in these tasks is usually very small (e.g., <60). I'm a bit surprised that substructure is still very useful in these cases as global attention is not operating on a huge graph anyway.\n5) Could the authors provide the # of parameters for each model in Table 1?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dhDYLa4rc9", "reviewer": "Reviewer_KU4L", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 shows the theoretical bottleneck on attention capacity for transformer depth scaling and proposed a new graph transformer model called DeepGraph to address it. The proposed architecture relies on substructure-based attention mechanism, where there are extra substructure tokens that correspond to sampled substructures. Specifically, each substructure token only attends to tokens within it. The model is shown to increase performance on several datasets as depth increases.", "summary_of_the_review": "Overall, the paper is addressing an important issue. The theoretical results and proposed methods seem sound and well tested. The concern is about the significance of the experimental results on depth improvement.", "strength_and_weaknesses": "Strength\n- Depth limitation of gnns and graph transformers has been a key issue in graph ML. The theoretical analysis reveals insights for solving this. \n- The proposed method is conceptually simple and motivated by theoretical results.\n- The proposed method is tested over a diverse set of datasets and tasks and demonstrates empirical gains.\n\nWeaknesses\n- The performance improvements with depth seem pretty small relative to the variances on most datasets.\n- The method seems not completely correspond to the theoretical motivation: in theorem 3 substructure based local attention is defined as  \"where each node only attends nodes that belong to the same substructures\". If I understand correctly, in DeepGraph each node can still attend to all other nodes, but only that the substructure token only attends to and by the nodes in the substructure. Can this be further justified?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "LONNY5swPOX", "reviewer": "Reviewer_n5aK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The author studies the effect of number of layers in graph transformer model, and claims that the previously used graph transformer layer has decreasing attention capacity on attending substructures with increasing attention layers. Then the author improves graph transformer with adding sampled substructures as token along with nodes. Extensive experiments over large real-world datasets are conducted to show its improvement.", "summary_of_the_review": "The author added substructure tokens to current graph transformer and show empirically improvement. In the meantime, the author try to answer why increasing depth doesn't benefit the performance for previous graph transformers, with a measure of attention capacity. However the relationship between the defined attention capacity and the empirical performance drop of increasing depth is not clear. ", "strength_and_weaknesses": "**Strength**: \n1. Substructure based GNNs are widely explored last year and also influences the graph transformer area. It's interesting to see that adding substructure directly helps improving current graph transformers.\n2. The author proposes a measure to define the attention capacity for substructures. This is an interesting angle. \n3. The improvement over real-world dataset is great, especially on PATTERN dataset. \n\n**Weakness**:\n1. Notation and writing is not clear and is too hard to follow. I suggest the author to revise the paper extensively to make the notation easier to follow. For example, the author use $G^S$ for general notation of subgraph, which is really confusing as I was originally thinking that $G^S = G[S]$ representing the set S induced subgraph on G.  For general subgraph pattern, I suggest the author remove the G notation, just use something like $S$ directly, as there is no relation to G. The section 4 needs to be greatly improved. For example, even the first paragraph inside 4.1 is hard to follow. All notations of graph, subgraph, pattern, and support are too hard to follow. Also $supp(e) \\subseteq  N^S$ instead of $supp(e) \\in  N^S$. There are so many confusing notations and I cannot read and evaluate the section 4. Another example is the $\\triangle$ notation...it represents easy stuff in principle but the notation makes the easy stuff hard to interpret. Again, like $Attn_{A}$,  the underscript is never mentioned before using. \n2. Definition 1 of measuring attention capacity is questionable. There are learnable W inside and it's not possible to analyze the F norm directly, as W can have any scale to enlarge the F norm. Also, there is no relationship between small F norm and substructure indistinguishability. (a-b small doesn't imply a=b for graph separation case) I suggest the author at least give some empirical example to link the small F norm and the bad ability of identifying substructure. \n3. Theorem 1 and Theorem 2 I cannot read yet, after the author revise the section 4 I would like to check the theorem correctness. \n4. Section 5 substructure sampling is very similar to the one designed in [Zhao et al. ICLR 22]. The author should mention with reference. \n5. The designed method is a special case of [Kim et al. NeurIPS 22], and it doesn't provide much new contribution to model design. \n6. The ZINC experiment may need 500K parameter restriction in comparison. \n\n[Kim et al. NeurIPS 22] Pure transformer are powerful graph learners. \n[Zhao et al. ICLR 22] From stars to subgraphs \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HWwI1a_o1fF", "reviewer": "Reviewer_1tcv", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "In this paper, the authors first theoretically present the bottleneck of graph transformers’ performance with depth. The authors then propose a simple but effective substructure token based local attention mechanism in graph transformer, promoting focus on local substructure features of deeper graph transformer. Empirical results show that the proposed achieves state-of-the-art results on standard graph benchmarks with deeper models.", "summary_of_the_review": "This paper provides interesting theoretical results and novel Graph Transformer design. The empirical results look good but not enough ablation studies. There's a nontrivial gap between the theory and the actual method proposed.", "strength_and_weaknesses": "Strengths:\n- The theory proposed looks interesting, and the corresponding transformer structure introduced also look very novel.\n- The authors conducted experiments on various benchmarks and the results look very competitive.\n- The paper is clearly written and the motivation is easy to follow.\n\nWeaknesses:\n- Why there's such a negative correlation for Graph Transformer, while for Transformer in NLP the case is the larger, the better? Does the theoretical analysis also apply to Transformer in NLP?\n- The proposed method has so many different designs so that it's hard to tell whether the proposed theory can justify what actually happened. Specifically, the authors proposed to tokenizing substructures subsampled from the graph. This is very different from the previous Graph Transformers as there's no sampling before.\n- The authors didn't discuss the runtime overhead of the proposed method. Is it feasible to scale the proposed method on larger graphs?\n- There isn't much ablation study in the paper. Specifically, the authors should study the size of substructure and how it affects the performance degradation with increased depth.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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: poster