Enhancing Graph Transformers with Hierarchical Distance Structural Encoding
Authors: Yuankai Luo
Hongkang Li
Lei Shi
Xiao-Ming Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Transformers
Graph Neural Networks
Graph Classification
Node Classification
Large Graphs
Scalability
Primary area: graph_neural_networks
TL;DR: We introduce Hierarchical Distance Structural Encoding (HDSE), a method that enhances graph transformers on both graph-level tasks and large-scale node classification.

Abstract: Graph transformers need strong inductive biases to derive meaningful attention scores. Yet, current methods often fall short in capturing longer ranges, hierarchical structures, or community structures, which are common in various graphs such as molecules, social networks, and citation networks. This paper presents a Hierarchical Distance Structural Encoding (HDSE) method to model node distances in a graph, focusing on its multi-level, hierarchical nature. We introduce a novel framework to seamlessly integrate HDSE into the attention mechanism of existing graph transformers, allowing for simultaneous application with other positional encodings. To apply graph transformers with HDSE to large-scale graphs, we further propose a high-level HDSE that effectively biases the linear transformers towards graph hierarchies. We theoretically prove the superiority of HDSE in terms of expressivity and generalization. Empirically, we demonstrate that graph transformers with HDSE excel in graph classification, regression on 7 graph-level datasets, and node classification on 11 large-scale graphs.

Enhancing Graph Transformers with Hierarchical Distance Structural Encoding
Yuankai L.o 1.3
Hongkang Li²
Lei Shi
Xiao-Ming Su
"Beihang University
*Rnsssllaer Polytechnic Institute
The Hong Kong Polytechnic University
Juoyk&buaa.edux
xiao-ming. wuêpolyu. edu hk
Abstract
Graph transformers need strong inductive biases to derive meaningful attention scores. Yet, current methods often fall short in capturing longer ranges, hicrarchical structures, or community structures, which are common in various graphs such as molecules, social networks, and citation networks. This paper presents a Hier- archical Distance Structural Encoding (HDSE) method model node distances in a graph, focusing on its multi-level, hierarchical nature. We introduce a novel framework to seamlessly integrate HDSE into the attention mechanism of existing graph transformers, allowing for simultaneous application with other positional encodings. To apply graph transformers with HDSE to large-scale graphs, we further propose high-level HDSE that effectively biases the linear transformers towards graph hierarchies. We theoretically prove the superiority of HDSE in terms of expressivity and generalization. Empirically, we demonstrate that graph transformers with HDSE excel graph classification, regression graph-level datasets, and node classification on large-scale graphs.
Introduction
The success of Transformers [74] in various domains, including natural language processing (NLP) and computer vision [18], has sparked significant interest in developing transformers for graph data [19, 86, 46, 11, 68, 61, 89, 60, 82]. Scholars have turned their attention this area, aiming to address the limitations of Pressage-Passingg Graph Neural Networks (MPNNs) [30] such as over- smoothing [54] and over-squa [1. 73].
However, Transformers [74] are known for their lack strong inductive biases [18]. contrast to MPNNs, graph transformers do rely fixed graph structure information. Instead, they compute pairwise interactions for all nodes within a graph and represent positional and structural data using more flexible, soft inductive biases. Despite its potential, this mechanism does not have the capability to learn hierarchical structures within graphs. Developing effective positional encodings is also challenging, it requires identifying important hierarchical structures among nodes, which differ significantly from other Euclidean domains [10]. Consequently, graph transformers are prone to overfitting and often underperform MPNNs when data is limited [61] especially in tasks involving large graphs with relatively few labeled nodes [82]. These challenges become even more significant when dealing with various molecular graphs. such as those found in polymers proteins. These graphs are characterized by multitude of substructures and exhibit long-range and hierarchical structures. The inability of graph transformers learn these hierarchical structures can significantly impede their performance in tasks involving such complex molecular graphs.
CCorresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

HDSE
key D3
P1
12
Pg
VG
By
D. Pio
MatMul
SoftMax
GHD
Scale
MatMul
Linear
Linear
Linear
V2
GHD
F11
GHOP 9p7
GHDT 9a7
Node Feature
Position Encoding
Figure 1: Overview of our proposed hierarchical distance structural encoding (HIDE) and its integration with graph transformers. HDSE the interpretable patterns graph-structured data by using diverse graph coarsening algorithms. Darker colors indicate longer distances.
graph hierarchy distance (GHD, refer to Definition that capture
Further, the global all-pair attention mechanism in transformers poses significant challenge due to its time and space complexity, which increases quadratically with the number of nodes. This quadratic complexity significantly restricts the application of graph transformers large graphs, as training them on graphs with millions of nodes can require substantial computational resources. Large-scale graphs, such as social networks and citation networks, often exhibit community structures characterized by closely interconnected groups with distinct hicrarchical properties. To enhance the scalability and effectiivnesss of graph transformers, is crucial to incorporate hierarchical structural information at various levels.
To address the aforementioned challenges and unlock the true potential of the transformer architecture in graph learning, we propose a Hierarchical Distance Structural Encoding (HDSE) method (Sec. 3.1), which can be combined with various graph transformers produce more expressive node embeddings. HDSE encodes the hierarchy distance, a metric that measures the distance between nodes in graph, taking into account multi-level graph hierarchical structures. We utilize popular coarsening methods [43, 65, 31, 6, 57] to construct graph hierarchies, enabling us to measure the distance relationship between nodes across various hierarchical levels.
HDSE enables us to incorporate a robust inductive bias into existing transformers and address the issue of lacking canonical positioning. To achieve this, introduce a novel framework (Sec. 3.2), as illustrated in Figure 1. We utilize an end-to-end trainable function to encode HDSE as structural bias weights into the attentions, allowing the graph transformer to integrate both HDSE and other positional encodings simultaneously. Our theoretical analysis demonstrates that graph transformers equipped with HDSE are significantly more powerful than the ones with the commonly used shortest path distances or without relative positional encodings, in terms of both expressiveness and generul- ization. We rigorously evaluate our HDSE in ablation studies and show that it successfully improves different kinds of bascline transformers, from vanilla graph transformers [19] to state-of-the-arr graph transformers [68, 11, 91, 61], across graph-level datasets.
To enable the application of graph transformers with HDSE to large graphs ranging from millions to billions of nodes, we introduce high-level HDSE (Sec. 3.3), which effectively biases the linear transformers towards the multi-level structural nature of these large networks. We demonstrate our high-level HDSE method exhibits high efficiency and quality across 11 large-scale node classification datasets, with sizes to the billion-node level.
Our implementation is available at http://gitthb.coomm//00111999999
Background and Related Works
We refer to a graph tuple G (V,EXX) with node set V, edge set E C V V, and node features X R Vixd Each row in X represents the feature vector of node, with V denoting the number of nodes and feature dimension d. The features of node e denoted by x, gd

---

Table I: Comparison of popular graph coarsening algorithms.
Coarsening algorithm
METIS [43]
Spectral [65] Loukas [57] Newman [31]
Louvain [6]
Complexity
O(E)
O(VV))
O(IV)) O((E)1V) O(V] [V]
2.1 Graph Hierarchies
()k))))))) Given an input graph G, graph hierarchy of G consists a sequence graphs (G*, ob )20) where
G = G and ox V + Vk+1 are surjective node mapping functions. Each node vf E vk+ represents cluster of subset of nodes {uā] C Vkk This partition can be described by projection matrix pk
{0, |*|X|**+] where pk = if and only if o = (x()). The normalized 1/2
version can be defined by pk = Ck 1/2 where C* RRVV+
[x|V*+*| [RI**+Ix]]**")
is diagonal matrix with its j-th diagonal entry being the cluster size of e We define the node feature matrix X*+1
for Gk+1 by X = pk X where each row of X represents the average of all entries within a specific cluster. The edge set g of G*+1 defined as E = {(u w Bu 6% (uu+)), of E 2x (u such that (0f,v") E E.
Graph hierarchies can be constructed by repeatedly applying graph coarsening algorithms. These algorithms take graph, G and generate a mapping function Φk V* + y which maps the nodes in G to the nodes in the coarser graph G A summary and comparison of popular graph coarsening algorithms,, along with their computational complexities, can be found in Table 1. We define the coarsening ratio
y++1 TV* which represents the proportion of the number of nodes in the coarser graph G++1 to the number of nodes in the original graph G Consequently, each graph G where k >> 0, captures specific substructures derived from the preceding graph.
2.2 Graph Transformers
Transformers [74] have recently gained significant attention in graph learning, due to their ability to
learn intricate relationships that extend beyond the capabilities of conventional GNNs [44, 33, 59, 58], and in unique way. The architecture of these models primarily contain self-attention module and forward neural network, each of which is followed by a residual connection paired with normalization layer. Formally, the self-attention mechanism involves projecting the input node features X using three distinct matrices Wq E gaxd', WK dddxd and Wy E Rdxd', resulting in the representations for query (Q), key (K), and value (V), which are then used to compute the output features described as follows:
XWQ. TC=WW V= XWV,
[QK Vd
Attention (X) softmax
V.
(I)
Technically, transformers be considered message-passing GNNs operating on fully-connected
graphs, decoupled from the input graphs. The main research question in the context of graph transformers is how incorporate the structural bias of the given input graphs by adapting the
attention mechanism or by augmenting the original features. The Graph Transformer (GT) [19] represents an early work using Laplacian eigenvectors positional encoding (PE), and various extensions and alternative models have been proposed since then [64]. For instance, the structure- aware transformer (SAT) [11] extracts a subgraph representation rooted each node before computing the attention. Most initial works in the area focus on the classification of smaller graphs, such as molecules; yet, recently. GraphGPS [68] and follow-up works [92, 81, 80, 82, 12, 45, 72,
16, 26] also consider larger graphs.
2.3 Hierarchy in Graph Learning
In message passing GNNs, hierarchical pooling of node representations is a proven method for incorporating coarsening into reasoning [5, 28, 87, 48, 36, 69]. With GNNs, coarsened graph

---

representations are further considered in the context of molecules [42] and virtual nodes [39]. Additionally, HTAK [3] employ graph hierarchies develop novel graph kernel by transitively aligning the nodes across multi-level hierarchical graphs. The recent HC-GNN [94] demonstrates competitive performance in node classification on large-scale graphs, utilizing hierarchical community
structures for message passing.
In graph transformers, there are currently only few hierarchical models. ANS-GT [91] use adaptive node sampling in their graph transformer, enabling it for large-scale graphs and capturing long-range dependencies. Their model groups nodes into super-nodes and allows for interactions between them. Similarly, HSGT [96] aggregates multi-level graph information and employs graph hierarchical structure to construct intra-level and inter-level transformer blocks. The intra-level block facilitates the exchange and transformation of information within the local context of each node, while the inter- level block adaptively coalesces every substructure present. Our concurrent work directly incorporates hierarchy into the attention, fundamental building block of the transformer architecture, making it flexible and applicable to existing graph transformers. Additionally, Coarformer [47] utilizes graph coarsening techniques generate coarse views of the original graph, which are subsequently used as input for the transformer model. Likewise, PatchGT [27] starts by segmenting graphs into patches using spectral clustering and then learns from these non-trainable graph patches. MGT [66] learns atomic representations and groups them into meaningful clusters, which are then fed to a transformer encoder calculate the graph representation. However, these approaches typically yield coarse-level representations that lack comprehensive awareness of the original node-level features [41] In contrast, model integrates hierarchical information from broader distance perspective, thereby avoiding the oversimplification these coarse-level representations.
3
Our Method
3.1 Hierarchical Distance Structural Encoding (HDSE)
Firstly, we introduce a novel concept called graph hierarchy distance (GHD), which is defined as follows.
Definition 1 (Graph Hierarchy Distance). Given two nodes u, v in graph G, and graph hierarchy (G', (2)20) the k-level hierarchy distance between u and v is defined as
GHD (u, v) SPD (u,v), GHD (u, b) = SPD (dx=1...00 (u), Φb (x-1...
(2)
where SPD (.,-) is the shortest path distance between two nodes ( (oc if the nodes are not connected), and 0x-11..00()) maps node in Go to node in Gh.
Note that the kevel hierarchy distance adheres to the definition of metric, being zero for v u, invariably positive, symmetric, and fulfilling the triangle inequality. As illustrated on the left side of Figure I, it can be observed that GHD (V1, v11) = 7, whereas GHD! (V1, 01) = 2.
Graph hierarchies have been observed to assist in identifying community structures in graphs that exhibit a clear property of tightly knit groups, such as social networks and citation networks [31]. They may also aid in prediction over graphs with a clear hierarchical structure, such as orgal-organic frameworks or proteins. Fig. 2 shows that with the graph hierarchies generated by the Newman coarsening method, GHD is capable of capturing chemical motifs, including CF3 and aromatic rings.
Based GHD, propose hierarchical distance structural encoding (HDSE), defined for each pair of nodes i,j E V:
Dr, = [GHDD, GHD!
GHD* K i.
E E K+]
(3)
where GHD* is the k-level hierarchy distance matrix, and K E N controls the maximum level of hierarchy considered.
We demonstrate the superior expressiveness of HDSE over SPD using recently proposed graph isomorphism tests inspired by the Weisfeiler- Leman algorithm [78]. In particular, [89] introduced the Generalized Distance Weisfeiler-Leman (GD-WL.) Test and applied it to analyze a graph transformer architecture that employs SPD(i,j) as relative positional encodings. They proved that the graph

---

graph
Darranningreut
GHO
Dedecubedr
GHID
Melemie grophe
Coarsening
Examples of graph coarsening results and hierarchy distances. Left: HDSE can capture chemical motifs such as CF3 and aromatic rings molecule graphs. Right: HDSE can distinguish the Dedecahedron and Desargues graphs. The Dodecahedral graph has 1-level hierarchy distances of length 2 (indicated the dark color). while Desargues graph doesn't. I, In contrast, GD- WL test SPD cannot distinguish these graphs [89].
Figure 2:
transformer's maximum expressiveness is the GD-WL test with SPD. Here, we also use the GD-WL test to showease the expressiveness of HDSE.
Proposition (Expressiveness of HDSE). GD-WL with HDSE (Dig) is strictly more expressive than GD-WL with the shortest path distance SPD(i.
The proof is provided in Appendix 4. Firstly, we show that the GD-WL test using HDSE can differentiate between any two graphs that can distinguished by the GD-WL test with SPD. Next, we show that the GD-WL test with HDSE is capable of distinguishing the Dodecahedron and Desargues graphs (Figure while the one with SPD cannot.
3.2 Integrating HDSE in Graph Transformers
We integrate HDSE (Da.)) into the attention mechanism of each graph transformer layer to bias each node update. To achieve this, we use an end-to-end trainable function Bias R+1 + to learn the biased structure weight Hi,- Bias(Daa)) We limit the maximum distance length value L, based on the hypothesis that detailed information loses significance beyond a certain distance. By imposing this limit, the model can extend acquired patterns graphs of varying sizes encountered in training. Specificially, we implement the function Bias using an MLP as follows:
H. MLP ([eA T
ee clip
E E,
clip., A = min T., GHD
K,
where [oj, ...... o oSEEK E [Rdx(L+1) collects ++ learnable feature embedding vectors of for hierarchy level k. By embedding the hierarchy distances at different levels into learnable feature vectors, it may enhance the aggregation multi-level graph information among nodes and expands the receptive field of nodes to larger scale. We assume single-headed attention for simplified notation, but when extended to multiheaded attention, one bias is learned per distance per head.
We incorporate the learned biased structure weights H to graph transformers, using the popular biased self-attention method proposed by [86], formulated as:
Attention (X) softmax (A H) V.A QK
V
where the original attention score A is directly augmented with H. This approach is backbone-agnostic and can be seamlessly integrated into the self-attention mechanism of existing graph transformer architectures. Notably, we have the following results on expressiveness and generalization.
The power of a graph transformer with HDSE to distinguish non non-isomorphic graphs is at most equivalent to that of the GD-WL. test with HDSE. With proper parameters and an adequate number of heads and layers, a graph transformer with HDSE can match the power of the GD-WI. test with HDSE.
Proposition 2.
5

---

See the proof in Appendix 5. This result provides precise characterization of the expressivity power and limitations graph transformers with HDSE. Combining Proposition I, and Proofs A.1 in [86] immediately yields the following corollary:
Corollary (Expressiveness of Graph Transformers with HDSE), There exists a gruph trans- former using HDSE (with fixed parumeters), denoted M, such that M is more expressive than graph transformers with the same architeclure using SPD or using no relative positional encoding, regardless of their parameters.
This is a fine ane-grained expressiveness result of graph transformers with HDSE. demonstrate the superior expressiveness of HDSE over SPD in graph transformers.
Proposition (Generalization of Graph Transformers with HDSE). (Informal) For a semi- supervised binary node classification problem, suppose the label of each node i E V is determined by node features the "hierarchical core neighborhood" S = [j Daj D*} for a certain D' where Dig is HDSE defined in (3). Then, properly initialized one-layer graph transformer equipped with HDSE can learn such graphs with desired generalization error, while using SPD or using no relative positional encoding cannol guarantee satisfactory generalization.
The formal version and the proof are given in Appendix Proposition 3 a corollary and extension of Theorem 4.1 of [53] from SPD to HDSE. It indicates that learning with HDSE can capture the labeling function characterized by the hierarchical core neighborhood. which more general and comprehensive than the core neighborhood for SPD proposed in [53].
3.3 Scaling HDSE to Large-scale Graphs
For large graphs with millions of nodes, training and deploying transformer with full global attention is impractical due to the quadratic cost. Some existing graph transformers address this issue by sampling nodes for attention computation [91, 96]. While our HDSE enhance these models, this sampling approach compromises the expressivity needed to capture interactions among all pairs of nodes. However, in the NLP domain, Linformer [77] utilizes learnable low-rank projection matrix P to reduce the complexity of the self-attention module to linear levels:
Attention (X) softmax (XWo 1T/ //VV PXWv
Inspired by Linformer, models like GOAT [45] and Gapformer [56] in the graph domain also employ projection matrices to reduce the number of nodes by projecting them onto fewer super- nodes, consequently compressing the input node feature matrix X into a smaller dimension. This transformation enables the aggregation of information from super-nodes and reduces the quadratic complexity of attention computation to linear complexity. Here, we can replace the projection matrix with our coarsening partition matrix P (see Sec. 2.1) to obtain representations of coarser graphs at higher levels. Observe that we can still calculate meaningful distances at these higher hierarchy levels, using a high-level HDSE follow:
D = GHD II P')
GHD
P
Iseg
I=0
t=
i.
where each row of the projection matrix pl (see Sec. 2.1) one-hot vector representing the 1-level cluster that an input node belongs to, and D ||V"''V" x(K+1-c), Note that GHD** pt), S < K computes distances from input nodes to clusters at c-level graph hierarchy (see App. A). In practice, these distances can be directly obtained by calculating the hierarchy distance between all node pairs at the c-level. When establishes attention between nodes in the input graph G and clusters at high level hierarchies. For example, we can integrate the high-level HDSE into Linformer by adapting Equation (6):
0, D' becomes D in Eq 3. In this way, the high-level HDSE
Attention (X) = softmax XWQ(X*WK)) Vd + H X
H BD* E IV
where X E [xd (see Sec. 2.1) represents the features of clusters at k-level, and Bias R
+ R is end-to-end trainable function as defined in Sec. 3.2.

---

4 Evaluation
We evaluate our proposed HDSE on 18 benchmark datasets, and show state-of-the-art performance in many cases. Primarily, the following questions are investigated:
Can HDSE improve upon existing graph transformers, and how does the choice of coarsening algorithm affect performance? (Sec. 4.2)
Does our adaptation for large graphs also show effectiveness, it marked by efficiency, and how does high-level HDSE impact the performance? (Sec. 4.3)
4.1 Experiment Setting
Datasets. We consider various graph learning tasks from popular benchmarks as detailed below and Appendix B.
Graph-level Tasks. For graph classification and regression, we evaluate our method on five datasets from Benchmarking GNNs [20]: ZINC. MNIST, CIFARIO, PATTERN, and CLUSTER. We also test on two peptide graph benchmarks from the Long-Range Graph Benchmark [23]: Peptides-func
and Peptides- struct, focusing on classifying graphs into 10 functional classes and regressing 11
structural properties, respectively. We follow all evaluation protocols suggested by [68].
Node Classification on Large-scale Graphs. We consider node classification over the citation graphs Cora, CiteSeer and PubMed [44], the Actor co-occurrence graph [14], and the Squirrl
and Chameleon page-page networks from [71], all of which have 1K-20K nodes. Further, we
extend our evaluation to larger datasets from the Open Graph Benchmark (OGB) [35]: ogbn-arxiv, arxiv-year, oghn-papers I 00M,, ogbn-proteins and ogbn pronuupo, with node numbers ranging from
0.16M to O.IB. We maintain all the experimental settings as described in [82].
Baselines. We compare our method to the following prevalent GNNs: GCN [44], GIN [84], GAT [75]. GatedGCN [9], GatedGCN-RWWS [22], JKNet [85], APPNP [291. PNA [15), GPRGNN [14],
SIGN [70], H2GCN [95]; and other recent GNNs with SOTA performance: LINKX [55], CIN [8],
GIN-AK+ [93], HC-GNN [94]. In terms of transformer models, we consider GT[19], Graphormer
[86], SAN [46], Coarformer ANS-GT [91], EGT [38], NodeFormer [81]. Specformer [7], MGT
[66]. AGT [62], HSGT [96]. Graphormer-GD [89], SAT [11], GOAT [45], Gapformer [56], Graph
ViT/MI.P-Mixer [34], LargeGT [21], NAGphormer [12), Exphormer [72], DRew [32], VCR-GT [26],
CoBFormer [83] and recent SOTA graph transformers GraphGPS [68], GRIT [61], SGFormer [82].
Models HDSE. We integrate HDSE into GT, SAT, GraphGPS, GRIT (and ANS-GT in appendix) only modifying their self-attention module by Eq. 5. For fair comparisons, we use the same hyperparameters (including the number of layers, hidden dimension etc.). PE and readout as the baseline transformers. Given one of the baseline transformers M, we denote the modified model using HDSE by M + HDSE Additionally, we integrate our high-level HDSE into GOAT, denoted as GOAT + HDSE. We fix the maximum distance length L 30 and vary the maximum hierarchy level K in (0, 1, in all experiments. A sensitivity analysis of these two parameters is presented in Appendix C. During training. the steps of coarsening and distance calculation [17] can be treated as pre-processing, since they only need to be run once. We detail the choice and runtime coarsening algorithms for HDSE in the appendix. Detailed experimental setup and hyperparameters are in Appendix B due to space constraints.
4.2 Results on Graph-level Tasks
Benchmarks from Benchmarking GNNs, Table 2. We observe that nearly all four baseline graph transformers, when combined with HDSE, demonstrate performance improvements. Note that the enhancement is overall especially considerable for GT. On CIFARIO, we also obtain similar improvement for GraphGPS. Among them, GT shows the greatest enhancement and becomes competitive more complex models. Our model attains the best or second- mean performance for all datasets. While the improvement for GRIT is smaller, as its relative random walk probabilities (RRWP) already incorporate distance information [61], we still observe improvements datasets. This indicates that HDSE can provide additional information beyond what is captured by RRWP. Notably, is observed that the SOTA SGFormer tailored for large- scale node classification underperforms graph-level tasks.
three
7

---

Table 2: Test performance in five benchmarks from [20]. The results are presented as the mean + standard deviation from using different random seeds. Baseline results obtained from their respective original papers. indicates a statistically significant difference against the baseline w/o HDSE from the one-tailed t-test. Highlighted are the top first, second and third results.
Model
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER Accuracy
MAE 4
Accuracy 1
Accurncy f
Accuracy 1
GCN
0.367 2 0.011
90.705 = 0,218
55,710 a 0.381
71.892 a 0.334 85, *
68.49% =: 0.976
0.526 0.051
# 1.527
64.716
GatedGCN
0.282 + 0.015
97.340 = 0,
67.312 + 0.311
85.568 + 0.088
73,840 0.326
PNA
0.188 0.004
97,940 = 0.120
70.350 # 0.630
CIN
0.09+00000
GIN-AK+
0.080 + 0.001
72. 190 + 0.130
86.850 + 0.057
SGFormer
0.306 + 0.023
85.287 + 0.097
69.972 0.634
SAN
0.139 0.006
86.581 0.037
76.691 + 0.650
Graphormer-GD
0.081 = 0.009
Specforer
0.066 0.003
EGT
0.108 0.009
98. = 0.087
68. 702 + 0.409
86.821 * 0.020
79.232 0.348
Gruph VII/MLP-Mixer
0.073 a 0.001
97.422 a 0.110
73,961 a: 0.330
Exphomeer
98.550 0.039
74.696 0.125
86.742 0.015
78.071 0.037
GT
0.226 0.014
0.161
a:
GT + HDSE
0.159 + 0.006"
94.394 + 0.177
64.651 = 0.591
86.713 + 0.049
74,223 = 0.573"
SAT
0.094 0.008
86.848 0.037
77,856 0.104
SAT + HDSE
0.084 + 0.003"
86,933 + 0.039"
78.513 = 0.097"
GraphGPS
0,070 0.004
98.051 1 0.126
72.298 a 0,356
86.685 0.059
78.016 0.180 78.498 =: 0.121*
GruphGPS HDSE
0.062 a: 0.003"
98.367 a: 0.106"
76.180 a 0.277'
86.731 a 0.055
GRIT
0.059 = 0.002
98. 108 0.111
76.468 a: 0.881
87. 196 a: 0.076
80.026 0.277
GRIT HDSE
0.059 0.004
98.424 0.124"
76.473 + 0.429
* 0.064
79.965 0.203
Table 3: Test performance two peptide datasets from Long-Range Graph Benchmarks (LRGB) [23].
Table 4: Ablation experiments of coarsening algo- rithms ZINC.
Model
Peptides-func AP
Peptides-struct MAE
Model
Coarsening algorithm
ZINC MAE
GCN
0.5930 0.0023
0.349 0.0013
w/o
0.094 0.008
GINE
0.5498 a 0.0079
0,3547 1 0.0045
GatedGCN
0,5864 0.0035
0,3420 0.0013
METIS
0.089 +
GaedGGNN-RWSE
0,6069 0.0035
0,3357 0.0006
SAT
Spectral
0.088 + 0.004
Lonkas
0.084 + 0.003
GT
0.6326 0.0126
0,2529 0.0016
Nowman
0,087 0,002
SAN+RWSE
0.6439 1 0.0075
0,2545 1 0.0012
Louvain
0.088 2 0.003
MGT+WavePE
0.6817 = 0.0064
0,2453 0.0025
GRIT
0.6988 0.0082
0,2460 0.0012
w/o
0.070 + 0.004
Exphormer
0.6527 0.0043
0,2481 0.0007
METIS
0.069 0.002
Graph VIT/MI Pixeer
0.6970 0,008D
0,2475 0.0015
GraphGPS
Spectral
0.063 a: 0.003
DRew
0.7150 a 0.0044
0,2536 + 0.0015
Loukas
GraphGPS
0,6535 0.0041
0,2500 + 0.0012
Newman
0.062 # 0.003
GraphGPS HDSE
0.7156 4 0.0058'
0,2457 a 0.0013'
Louvain
0.064 : 0.002
Long-Range Graph Benchmark, Table 3. We consider GraphGPS due to its superior performance. Note that our HDSE module only introduces a small number of additional parameters, allowing it to remain within the benchmark's ~500k model parameter budget. In the Peptides-fum dataset, HDSE yields a significant improvement of 6.21% %. This is a promising result and hints at potentially great benefits for macromolecular data more generally.
Ablation Study and Visualization, Table 4, 13, 16, Figure 3, 5. First, we conduct several ablation experiments of coarsening algorithms ZINC and observe that the dependency on the coarsening varies with the transformer backbone. For instance, the multi-level graph structures extracted by the Newman algorithm yields the largest improvement for GraphGPS. More generally, our experiments indicate that Newman works best for molecular graphs. We visualize the attention scores on the ZINC and Peptides-func datasets respectively, shown in Figure 3. The results indicate that HDSE method successfully leverages hierarchical structure.
We also conduct a sensitivity analysis on maximal hierarchy level K and maximum distance length in Appendix C. The variation in the optimal K and L. could stem from the distinct hierarchical structures inherent in different graphs.
8

---

Molecular graph
Transformer attn
HDSE attn
0.00
0.35
0.07
0.06
0.05
0.20
0.15
0.03
0.02
0.00
0.00
Peptides graph
Transformer attn
HDSE attn
0,020
0.12
0.10
0.06
0.010
0.005
0.02
Figure 3: Visualization of attention weights for the transformer attention and HDSE attention. The left side illustrates the graph coarsening result. The center column displays the attention weights a sample node learned by the classic GT [19], while the right column showcases the attention weights learned by the HDSE attention.
Table 5: Node classification on large-scale graphs (%). The baseline results were primarily taken from [82], with the remaining obtained from their respective original papers. OOM indicates out-of-memory when training GPU with 24GB memory.
Car
Chiceer
PoMMal
Actre
Squirol
Clametoon
egtheggmenn
oglevandi
arthe-joe
oghts-prddcct
4,552
20,95
88554
L186.243
L,166233
61,59.140
8415
Accenay?
Accinay
Ascumsyt
Assunest
Accusayy
ROC-AIC1
Accuscy1
Assunsy!
Assumeyt
Accuracs
SIGN
12.1.:03
12.4
1..5
38.1100
25
21
71.24 046
2.10
10.2 0.16
65.11 0L14
LINKX
15.
413
29
0618 0.33
11:51=330
7
1.
419
OOM
SAT
12.4
6..91...
0OM
00M
0OM
COM
COM
DOM
ANS.CO GT
7.4009
6.7
0.77
33.2
088221
426227
7467 065
22.34:2000
$0.64 0.29
765+006
331408
COM
DOM
Caplomas
63.52004
7.
2..
2119
LaigeT
64.73 D.S
VCB-CTT
NAGghemer
34.300
73.55 +
12.64
ModeFoemer
122209
72.5
7999
369+
315
3877441
17165
59,00
72.3
CofFeenerr
3744
73.17 i
78.15 0007
SCieeeer
$45
72.61..2
21.99.111
418
44.
79.53 0.38
22.63:2..133
75:35.0.35
6601
316113
3.911.5
32.1118
78.39
10.40
13.36.0.19'
Synthetic Community Graphs, Table 19. We evaluate our methods on the community datasets from [88], generated using the Erdos-Renyi model [24]. These graphs have adjacency matrices that obey the certain clustered structure. As evidenced Table 19, GT struggles to detect such structures; and solely utilizing SPD proves inadequate; however, our HDSE, enriched with coarsening structural information, effectively captures these structures.
4.3 Results on Large-scale Graphs
Overall Performance, Table 5. We select four categories of baselines: GNNs, graph transformers with proven performance on graph-level tasks, graph transformers with hierarchy, and scalable graph transformers. It is noteworthy that while some graph transformers exhibit superior performance on graph-level tasks, they consistently result in out-of-memory (OOM) in large-scale node tasks. The results remarkably consistent. In relatively smaller datasets graphs (on the left side), the integra-

---

Table Efficiency comparison of GOAT HDSE and scalable graph transformer competitors; training time per
epoch.
PubMed
ogbn-proteins
ogbn-arxiv
ogbn-products
ogbn-papers 100M
NodeFormer
321.4ms
1.8s
0.6s
5.6s
595.1s
SGFormer
15.4ms
0.8s
0.2s
4.8s
579.4s
GOAT+HDSE 13.2ms
0.6s
0.2s
5.3s
446.5s
Table 7: Ablation study of GOAT + HDSE. "woo coarsening" refers replacing the projection matrix with the original projection matrix used in GOAT.
Actor t
ogbn-proteins 1
arxiv-year 1
GOAT+HDSE
38,0 = 1.5
80.3 = 0.3
54.2 0.2
w/o HDSE
34.6 = 2.2
79.4 = 0.3
53.6 + 0.3
w/o coarsening
32.1 + 1.8
78.3 + 0.4
53.5 = 0.2
tion of high-level HDSE enables GOAT to demonstrate competitive performance among baseline models. This could be due the coarsening projection filtering out the edges from neighboring nodes of different categories and providing global perspective enriched with multi-level structural information. For larger graphs (on the right side), our high-level HDSE method significantly enhances GOAT's performance beyond its original version. This indicates that the structural bias provided by graph hierarchies is capable of handling the node classification task in such larger graphs and effectively retains global information. We investigated this in more detail in our ablation experiments. Furthermore, we also observed that all graph transformers with hierarchy suffer from serious overfitting, attributed to their relatively complex architectures. In contrast, model's simple architecture contributes to its better generalization.
Efficiency Comparison, Table 6. We report the efficiency results on PubMed, arxiv, ogbn-products and ogbn- ogbn-100M. It is easy to see that our model outperforms NodeFoormer in speed, matching the pace of the latest and fastest model, SGFormer [82]. It achieves true linear complexity with a streamlined architecture.
ogbn-
Ablation Study, Table 7. To determine the utility of our architectural design choices, we conduct ablation experiments on GOAT HDSE over three datasets. The results presented in Table 7, include (I) removing the high-level HDSE and (2) replacing the coarsening projection matrix with the original projection matrix used GOAT. These experiments reveal decline in all performance, thereby validating the effectiveness of our architectural design.
Conclusions
We have introduced the Hicrarchical Distance Structural Encoding (HDSE) method to enhance the capabilities of transformer architectures in graph learning tasks. We have developed flexible frame- work to integrate HDSE with various graph transformers. Further, for applying graph transformers with HDSE large-scale graphs, have introduced high-level HDSE approach that effectively biases linear transformers towards the multi-level structure. Theoretical analysis and empirical results validate the effectiveness and generalization capabilities of HDSE, demonstrating its potential for various real-world applications.
Acknowledgments and Disclosure of Funding
We extend our sincere gratitude Veronika Thost, Yicheng Pan, Zixu Zhao and Jaan Li for their invaluable guidance in our experiments. We also express our appreciation to all the anonymous reviewers and ACs for their insightful and constructive feedback. This work received support from National Key R&D Program of China (2021 YFB3500700), NSFC Grant 62172026, National Social Science Fund China 22&2D153, the Fundamental Research Funds for the Central Universities, State Key Laboratory of Complex & Critical Software Environment (CCSE), HK PolyU Grant PO051029 HK PolyU Grant P0038850, and HK ITF Grant ITS/359/21FP. Lei Shi is with Beihang University and State Key Laboratory of Complex & Critical Software Environment.
10

---

References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint mxxi::2006.05255 2020.
[2] Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-margin token selection in attention mechanism. Advances in Neural Information Processing Systems, 36:48314-48362, 2023.
[3] Lu Bai, Lixin Cui, and Hancock Edwin. hierarchical transitive-aligned graph kernel for un-attributed graphs. In International Conference on Machine Learning, pages 1327-1336. PMI.R, 2022.
[4] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2 10.02910, 2021.
[5] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, pages 974-883, PMLR, 2020.
[6] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P1000S, 2008
[7] Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. arXiv preprint 2303:23033.0028, 2023.
[8] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pictro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning pages 1026-1037. PMLR, 2021.
[9] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv:1711.07533, 2017.
[10] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2 13478, 2021.
[11] Dexiong Chen, Leslie O' Bray, and Karsten Borgwardt. Structure-awart transformer for graph representation learning. In International Conference on Machine Learning, pages PMLR, 2022.
[12] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, 2022.
[13] Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang. Unveiling induction heads: Prov- able training dynamics and feature learning in transformers. arXiv preprint 1xXv5:2409.10559 2024.
[14] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2020.
[15] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pictro Liô, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1322 2020.
[16] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expreste graph transformer in linear time. In The Twelfth International Conference on Learning Representations, 2024.
[17] EW Dijkstra. note on two problems in connexion with graphs. Numerische Mathematik, (1):269-271, 1959.

---

[18] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani. Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
[19] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint 201200900,, 2020.
[20] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 2023.
[21] Vijay Prakash Dwivedi, Yozen Liu, Anh Tuan Luu, Xavier Bresson, Neil Shah, and Tong Zhao. Graph transformers for large graphs. arXiv preprint arXiv:23/2.11109 2023.
[22] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. International Conference Learning Representations, 2021.
[23] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. arXiv preprint arXiv:2206.08166 2022.
[24] ERDdS and A R&wi. On random graphs Publ. math. debrecen, 6(290-297):18, 1959.
[25] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
arXiv preprini arXiv: 190..090330323 2019.
[26] Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. VCR- -ce-graphormer: A mini-batch graph transformer via virtual connections. In The Twelfth International Conference Learning Representations, 2024.
[27] Han Gao, Xu Han, Jiaoyang Huang, Jian-Xun Wang, and Liping Liu. Patchgt: Transformer over non-trainable clusters for learning graph representations. In Learning on Graphs Conference, pages 27-1. PMLR, 2022.
[28] Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning. pages 2083-2092. PMLR, 2019.
[29] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05991 2018.
[30] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272, PMLR, 2017.
[31] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7221-7822 2002.
[32] Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pages 12252-12267. PMLR, 2023.
[33] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
[34] Xiaoxin He. Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs. In International Conference on Machine Learning. pages 12724-12745. PMLR, 2023.
[35] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Lesoove. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22 18 22113,,, 2020.
12

---

[36] Jingjia Huang, Zhangheng Li, Nannan Li. Shan Liu, and Ge Li. Atipool: Towards hierarchical feature representation in graph convolutional networks via attention mechanism. In Proceedings of the IEEE/CVF international conference on computer vision, pages 6480-6489, 2019.
[37] Yu Huang, Yuan Cheng, and Yingbin Liang. In-context convergence of transformers. In Forty-first International Conference on Machine Learning, 2024.
[38] Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self- attention as a replacement for graph convolution. Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 655-665, 2022.
[39] EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis of virtual nodes in graph neural networks for link prediction (extended abstract). In The First Learning on Graphs Conference, 2022.
[40] Samy Jelassi, Michael Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. Advances in Neural Information Processing Systems,
2022.
[41] Bo Jiang, Fei Xu, Ziyan Zhang, Jin Tang, and Feiping Nie. Agformer: Efficient graph represen- tation with anchor-graph transformer. arXiv preprint arXiv:2305.0752), 2023.
[42] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International conference on machine learming, pages 4839- 4848. PMLR, 2020.
[43] George Karypis and Vipin Kumar. A software package for partitioning unstructured graphs partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, MN, 38:7-1, 1998.
[44] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[45] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A global transformer on large-scale graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17375-17390. PMLR, 23-29 Jul 2023.
[46] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34:21618 14221618-21629, 2021.
[47] Weirui Kuang, WANG Zhen, Yaliang Li, Zhewei Wei, and Bolin Ding. Coarformer: Transformer for large graph via graph coarsening. 2021.
[48] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International conference on machine learning, pages 3734-3743. PMLR, 2019.
[49] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection. 2014. 2016.
[50] Hongkang Li, Meng Wang. Sijia Liu, and Pin-Yt Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. In The Eleventh International Conference on Learning Representations, 2023.
[51] Hongkang Li, Meng Wang, Songtao Lu, Xiaodong Cui, and Pin- Yu Chen. Training nonlinear transformers for thhouhtf- inference: A theoretical generalization analysis. arXiv preprint 16Xiv22410.00166, 2024.
[52] Hongkang Li, Meng Wang, Songtao Lu, Hui Wan, Xiaodong Cui, and Pin-Yu Chen. Transform- ers as multi-task feature selectors: Generalization analysis of in-context learning. In NeurlPS 2023 Workshop on Mathematics of Modern Machine Learning, 2023.
13

---

[53] Hongkang Li, Meng Wang, Tengfei Ma, Sijia Liu, ZAIXI ZHANG, and Pin- Yu Chen. What improves the generalization of graph transformers? a theoretical dive into the self-attention and positional encoding. In Forty-first International Conference on Machine Learning, 2024.
[54] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.0333 03324, 2018
[55] Derek Lim, Felix Matthew Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Prasad Bhalerao, and Ser-Nam Lim. Large scale learning on non-homophilous graphs: New bench- marks and strong simple methods. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[56] Chuang Liu, Yibing Zhan, Xueqi Ma, Liang Ding, Dapeng Tao, Jia Wu, and Wenbin Hu. Gapformer: Graph transformer with graph pooling for node classification. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAL, pages 2205, 2023.
[57] Andreas Loukas. Graph reduction with spectral and cut guarantees. J. Mach, Learn. Res., 20(116): 2019.
[58] Yuankai Luo, Lei Shi, and Veronika Thost. Improving self-supervised molecular representation learning using persistent homology. Advances in Neural Information Processing Systems, 36, 2024.
[59] Yuankai Luo, Lei Shi, Mufan Xu, Yuwen Ji, Fengli Xiao, Chumming Hu, and Zhiguang Shan. Impact-oriented contextual scholar profiling using self-citation graphs. arXiv preprint arXiv:2304. 12217, 2023.
[60] Yuankai Luo, Veronika Thost, and Lei Shi. Transformers over directed acyclic graphs. Advances in Neural Information Processing Systems, 36, 2024.
[61] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriant Puneet K Dokania, Mark Coates, Philip Torr, and Sem-Nam Lim. Graph inductive biases in transformers without message passing. arXiv preprint arXiv: 17589, 2023.
[62] Xiaojun Ma. Qin Chen, Yi Wu, Guojie Song, Liang Wang, and Bo Zheng. Rethinking structural encodings: Adaptive graph transformer for node classification task. In Proceedings of the ACM Web Conference 2023, pages 533-544, 2023.
[63] Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 785-794, 2015.
[64] 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:
2022.
[65] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
[66] Nhat Khang Ngo, Truong Son Hy, and Risi Kondor. Multiresolution graph transformers and wavelet positional encoding for learning long-range and hierarchical structures. The Journal of Chemical Physics, 159(3). 2023.
[67] Hongbin Pei, Bingzhe Wei, Kevin metric graph convolutional networks. In International Conference on Learning Representations, 2019.
Chang, Yu Lei, and Bo Yang. Geom-gen: Geo-
[68] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205.1245: 2022.
[69] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5470-5477,2000
14

---

[70] Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. / 198, 7:15, 2020.
[71] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())xcnab014, 2021.
[72] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. arXiv preprint arXiv:2303.06147 2023.
[73] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. arXiv preprint arXiv:2 14522, 2021.
[74] 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 information processing systems, 30, 2017.
[75] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[76] Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufci Li, Xiang Song. Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, seghlyppefoommnt package for graph neural networks. arXiv preprint arXiv:1909.01115, 2019.
[77] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768 2020.
[78] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 129)1 1968.
[79] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pages 6861-6871. PMLR, 2019.
[80] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. In The Eleventh International Conference on Learning Representations, 2023.
[81] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27401. 2022.
[82] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. In seirth-seventh Conference on Neural Information Processing Systems, 2023.
[83] Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is more: the over- globalizing problem in graph transformers. arXiv preprint arXiv:2405.01 102, 2024.
[84] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00826 2018.
[85] 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 machine learning, pages 5453-5462. PMLR, 2018.
[86] 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.
[87] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances neural information processing systems, 31, 2018.
15

---

[88] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrmn: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pages 5708-5717. PMLR, 2018.
[89] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023.
[90] Yihua Zhang. Hongkang Li, Yuguang Yao, Aochuan Chen, Shuai Zhang, Pin- Yu Chen, Meng Wang, and Sijia Liu. Visual prompting reimagined: The power of activation prompts, 2024.
[91] Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. Hierarchical graph transformer with adaptive node sampling, Advances in Neural Information Processing Systems, 35:21171-21183, 2022.
[92] 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.
[93] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2110.03753, 2021.
[94] Zhiqiang Zhong, Cheng-Te Te Li, and Jun Pang. Hierarchical message-passing graph neural networks. Data Mining and Knowledge Discovery, 37(1):381-408, 2023.
[95] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances neural information processing systems, 33:7793-7804 2020.
[96] Wenhao Zhu, Tianyu Wen, Guojie Song, Xiaojun Ma, and Liang Wang. Hierarchical transformer for scalable graph learning, arXiv preprint arXiv:2305.022 02866, 2023.
16

---

A Proof
Proposition 4. (Restatement of Proposition 1) GD-WL. with HDSE (Dis) strictly more expressive than GD-W- WL with shortest path distances (SPD(i,5)).
Proof. First, we show that GD-WL with HDSE at least as expressive as GD-WL with shortest path distances (SPD). Then, provide specific example of two graphs that cannot be distinguished by GD-WL with SPD, but can be distinguished by GD- BL with HDSE.
Let ji) IR denote the encoding for shortest path distance. It is worth mentioning that
Dijo0 GHD (i.j) SPD (i.j).
Thus, Di.j is a function of SPD (i.j), and hence Da refines SPD (i.j). To conclude this, we utilize Lemma 2 from [4], which states that refinement is maintained when using multisets of colors. This observation confirms that GD with HDSE is at least as powerful as GD-WL with SPD.
To show that GD-WI. with HDSE is strictly isomorphic graphs that can be distinguished by the HDSE but not the SPD: the Desargues graph and the Dodecahedral graph. As depicted in Figure 6 of [89], has been observed that GD-WL with SPD fails to distinguish these graphs. However, GD-WL with our HDSE can. Figure 4 shows the coarsening results of the Girvan-Newman Algorithm [31]. We can demonstrate that, for the Dodecahedral graph, each node has 1-level hierarchy distances of length 2 to other nodes. On the other hand, in the Desargues graph, there are no such distances of length 2 between any pair of nodes.
expressive, we provide example of
Dedecabedron
GHD
GHD
Desargues graph
GHO
GHO
Figure 4: GD-WI. with HDSE can distinguish Dodecahedron and Desargues graphs, but GD-WI. with SPD cannot.
Proposition 5. (Restatement of Corollary 2) The power of graph transformer with HDSE to distinguish non-isomorphic graphs is at most equivalent to that of the GD-WL test with HDSE. With proper parameters and adequate number of heads and layers, graph transformer with HDSE can match the power of the GD-WL test with HDSE
Proof. The theorem is divided into two parts: the first and second halves. We begin by considering the first half: The power of graph transformer with HDSE to distinguish non -somosoooppicc graphs is most equivalent to that of the GD-WL test with HDSE.
Recall that the GD-WL with HDSE is quite straightforward and can be expressed as:
(o( == hash (Dr... (w)) u
where (v) represents color mapping function.
Suppose after iterations, a graph transformer with HDSE M has M(Gi) + M(G2)), ((G2),yer yet GD-WL with HDSE fails to distinguish G1 and G2 as non-isomorphic. It implies that from iteration 0 to in GD-WI test, G1 and G2 always have the same collection of node labels. Particularly, since Gi and G2 have the same GD-WL node labels for iterations + for any = O...., they also
17

---

share the same collection of GD-WL node labels {(Dr.u, xx(x))= ):: E Vj. Otherwise, the GD-WL test would have produced different node labels iteration + 1 for G1 and G2.
We show that within the same graph, for example G = G1, if GD-WL. node labels Xc(x) = X2 (w), then the graph transformer node features hi, = Rig for any iteration i. This is clearly true for i = because GD-WI WL and graph transformer start with identical node features. Assuming this holds true for iteration j. if for any v, w, XG ++1 (v) xaa (w), then we must have
{De.. Xa ()) u E v
Xe(w)) [ul]]))]e]]]
By our assumption at iteration j. we deduce that
hot1
Σ softmax(Bias(D...)) + 1e WWWh The = (ee : : wev)).
EEV
Hence,
N²+1 = ol (P xo(w)) : - = (Dmas : a E vv]] hot
By induction, if GD-WL node labels (0((0) = ((), we always have the graph transformer node features hi = h for any iteration i. Consequently, from Gj and G2 having identical GD-WL node labels, it follows that they also have the same graph transformer node features.
Therefore, h,#1 M Given that the graph-level readout function is permutation-invarinn with respect to the collection of node features, M(G = M(G2). This leads to a contradiction.
This completes the proof of the first half of the theorem. For the theorem's 's second half, we can entirely leverage the proof of Theorem E.3 by [89] (provided in Appendix E.3), which presents a similar situation.
Proposition 6. (Full version of Proposition 3) For a semi- ceni-supervised binary node classification problem, suppose the label of each node i E V in the whole graph is determined by the majority vote of diseriminative node features the "hierarchical core neighborhood" S {j Di,, D"} for a certain D", where Di.j is HDSE defined in (3). Assume noiseless node features. Then, as long as the model is large enough, the batch size B 2 M)( the step size < 1, the number of iterations T satisfies T = 1122 and the number of known labels satisfies |C] 2 max + ob-) log N), BT), where ōD- measures the maximum number of nodes in the hierarchical core neighborhood St. for all nodes n, then with a probability of at least 0.99, the returned one-layer graph transformer with HDSE trained by the SGD variant Algorithm I and Hinge loss in [53] can achieve a generalization error which is at most for any e >> O. However, we do not have generalization guarantee learn such a graph characterized by the hierarchical core neighborhood with one-layer graph transformer with SPD encoding or without any relative positional encoding.
Before starting the proof, we first briefly introduce and extend some notions and setups used in [53]. The major differences are that (1) we extend their core neighborhood from based on SPD to HDSE (2) we use HDSE in the transformer by encoding it as a one-hot encoding for simplicity of analysis.
Their work focuses on a semi cepi-supe binary node classification problem on structured graph data, where each node feature corresponds to either discriminative or -isciiicriminaeive feature, and the dominant discriminative feature in the core neighborhood determines each ground truth node label. The node features are sampled from a set of orthonormal vectors following other reature-learning works [40, 50, 2, 37, 52, 51, 90, 13] in theoretically analyzing Transformers. For each node, the neighboring nodes with features consistent with the label are called class-relevant nodes, while nodes with features opposite to the label are called confusion nodes. Denote the class-relevant and confusion nodes set for node n as D. and D respectively. A new definition here is the distance- neighborhood, NB, which is the set of nodes {j Dr.jj = D,j E V}. D is the HDSE defined in (3). Then, by following Definition 1 in [53]. we define the winning margin for each node n of distance D as (D) = (D. n. (D n.Ng). The core distance D is the distance D where the average winning margin over all nodes is the largest. We call the set of neighboring nodes
18

---

S. = = Dn.j = } the core neighborhood. We then make the assumption that (n() > 0 for all nodes V. following Assumption 1 in [53]. The one-layer transformer we study formulated as
F(hn) = Relu( Σ
softmax(B(DD.... T hn (h Wk) Th Wv Wo)a
NEV
where Wo E Rdd'
xd" and a E TRd are the hidden and output weights in the two-layer feedforward network, and E 2 is the trainable parameter to learn the relative positional encoding. The one-hot relative positional encoding B(Dr.u.) is defined as
B(D,,a, = C..
(10)
where O2 the s-th standard basis in R²_ Z the total number of all possible values of Dr, for n, u E V. B(-) is a bijection from (d E RK+1, d -naas for certain n, v. E V} to fei, C2, ... .zz)-
Then, we provide the proof for Proposition 6.
Proof. The proof follows Theorem 4.1 in [53] given the above reformulation. Note that (10) can also map the SPD relationship, which a special me-dimensioonll case of De... between nodes as (2) in [53] by the definition of itself. It means that (9) with HDSE can achieve a generalization performance on the graph characterized by the core neighborhood as good as [53].
However, we cannot have an inverse conclusion, i.e., providing a generalization guarantee on the graph characterized by the hierarchical core neighborhood using (9) with SPD. This is because SPD cannot distinguish nodes with the same SPD but different HDSE to a certain node. Hence, for a certain node: i V, aggregating nodes using SPD may include nodes outside the hierarchical core neighborhood, of which the labels are inconsistent with the node i, and lead to a wrong prediction. Likewise, we cannot guarantee the generalization using a Graph Transformer without any relative positional encoding since such model cannot distinguish nodes with different HDSE.
Proposition 7. For a semi- supervised binary node classification problem, suppose the label of each node i V in the whole graph is determined by the majority vote of discrininative node features in the "core neighborhood": : St = {j D,, D*} } for a certain D*, where Dr,5 is HDSE defined in (3). Then. for each node E V, properly initialized one-layer graph transformer (i) without HDSE (ii) and only aggregate nodes from St, can achieve the same generalization error as learning with a one-layer graph transformer (a) with HDSE (b) aggregate all nodes in the graph without knowing S in prior.
Proof. The proof follows Theorem 4.3 in [53]. When b 0 is fixed during the training, but the nodes used for training and testing in aggregation for node n are subsets of N the bound for attention weights on class-relevant nodes is still the same as in (63) and (64) of [53]. Given a known core neighborhood ST the remaining parameters follow the same order-wise update as Lemmas 4. 5, and 7. The remaining proof steps follow the contents the proof of Theorem 4.1 of [53], which leads to generalization on one-layer transformer with HDSE and aggregation with all nodes in the graph.
Explanation of GHD Computation in Equation 7. As defined in Eq. 2, GHD E RIVI represents the shortest path distance between any two input nodes the m-level graph hierarchy. Vm, GHD 12 has the same size GHD".
In Eq. 7, our high-level HDSE computes, at each level S m S K, distances between input nodes and clusters obtained by coarsening (i.e., super nodes at the c-level graph hierarchy). This is achieved by multiplying the projection matrices I pl to GHD".. In effect, it is equvalent to selecting corresponding columns from GHD"". For instance, referring to Figure 1, GHD po RIxx calculates the distances from input nodes to the super nodes at 1-level graph hierarchy, essentially selecting the first, fourth, and tenth columns from GHD!
Likewise, GHD"'([[ P') E | selects |Vo columns from GHD to represent the dis- tances, at the m-level graph hierarchy, between the input nodes and the c-level super nodes (i.e., clusters obtained through coarsening).
19

---

B Experimental Details
B.1 Computing Environment
Our implementation is based on PyG [25] and DGL [76]. The experiments are conducted on single workstation with RTX 3090 GPUs and a quad-core CPU.
Table 8: Overview the graph learning dataset used in this work [20, 23, 44, 14, 67, 71, 35, 63, 49).
Daraset
Graphs
Avg. podes
Avg. # odges
# Feats
Prediction level
Prediction task
Metric
ZINC
12,000
23.2
24.9
28
graph
regression
MAE
MNIST
70,000
70.6
564.5
3
graph
10-slass clussif,
Accuracy
CIFARIO
60,000
117.6
941.1
graph
10-class classif.
Accuracy
PATTERN
14,000
118.9
3,039.3
3
node
binary classif.
Accuracy
CLUSTER
12,000
117.2
2,150.9
node
6-class clasif.
Accuracy
Peptides fune
15.535
150,9
307.3
9
graph graph
10-task classif.
AP
septides-struet
15,535
150.9
307.3
II I1-task regression
MAR
Cora
2,708
5,278
2,708
mode
7-class classif.
Accuracy
Citeseer
1
3,327
4,522
3,703
nnde
6-class classif.
Accuracy
Pubmed
19.717
44,324
500
mode
3-class classif.
Accuracy
Actor
7,600
26,659
931
node
5-class classif.
Aucuracy
Squirrel
I
5,201
216,933
2,089
node
5-class classif.
Accuracy
Chameleon
2,277
36,101
2,325
node
5-class classif.
Accuracy
ogha-proteins
1
132.534
39,561,252
node
112 binury classif.
ROC-AUC
oghn-ardiv
169,343
1,166,243
128
mode
40 class classif.
Accuracy
arxiv-year
169,345 343
1,166, 243
128
node
5-class classif.
Accuracy
ogba-products
2
2,4499,029
61,859,140
100
node
47-olass classif.
Accuracy
1gba-papers100M
1
111.059.956
1.615,685.872
128
node
172-class classif.
Accuracy
B.2 Description of Datasets
Table 8 presents a summary of the statistics and characteristics of the datasets. The initial five datasets are sourced from [20], followed by two from [23]. and finally the remaining datasets are obtained from [44, 14, 67, 71, 35, 63, 49].
ZINC, MNIST, CIFARIO, PATTERN, CLUSTER, Peptides-func and Peptides-struct. For each dataset, we follow the standard train/validationntest splits and evaluation metrics in [68]. For more comprehensive details, readers encouraged to refer to [68].
Cora, Citeseer, Pubmed, Actor, Squirrel, Chameleon, ogbn-proteing proteins, ogbn-arxiv,
and ogbn-papers 1 100M. For each dataset, we use the same train/validationntesl splits and evaluation metries as [82]. For detailed information on these datasets, please refer [82].
Arxiv-year is a citation network among all computer science arxiv papers, as described by [55]. In this network, each node corresponds to an arxiv paper, and the edges indicate the citations between papers. Each paper is associated with 128-dimensional feature vector, obtained by averaging the word embeddings of its title and abstract. The word embeddings are generated using the W WORD2VEC model. The labels of arxiv-year are publication years clustered into fve intervals. We use the public splits shared by [55], with a vrain/validation/tsst split ratio of 50%/25%/2544
B.3 Hyperparameter and Reproducibility
Models + HDSE For fair comparisons, we use the same hyperparameters (including training schemes, optimizer, number of layers, hidden dimension etc.) as baseline models for all of our HDSE versions. Taking GraphGPS + HDSE as an example, Tables 9 and 10 showcase the corresponding hyperparameters and coarsening algorithms. It is important to note that our HDSE module introduces only a small number of additional parameters. And each experiment is repeated times to get the mean value and error bar.
To accelerate training, we do not adopt the neighbor sampling (NS) method from GOAT to sample neighbors; instead, we train directly on the entire graph. For graphs with over one million nodes, we randomly sample nodes within the graph and select their induced subgraph for batch training. For the hyperparameter selections of our high-level HDSE model, in addition to what
GOAT + HDSE.
20

---

Table 9: Hyperparameters of GraphGPS + HDSE for five datasets from [20].
Hyperparameter
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
GPS Layers
10
3
Hidden dim
64
52
52
64
48
GPS-MPNN
GINE
GatedGCN Transformer
GatedGCN Transformer
GatedGCN
GatedGCN
CPS-GlobAttn
Transformer
Transformer
Transformer
Heads
4
Attention dropout
0.5
0.5
0.5
0.5
0.5
Graph pooling
sum
mean
mcan
Positional Encoding
RWSE-20
LapPE-8
LapPE-8
LapPE-16 16
LapPE-10 16
PE dim
28
8
8
PE encoder
linear
DeepSet 16
DeepSet
DeepSet 32
DeepSet
Batch size
32
Learning Rate
0.001
0.001
0.001
0.0005
0.0005
Epochs
2000
100
200
100
Warmup epochs
.0
5
5
5
5
Weight decay
le-5
le-5
1e-5
1c-5
1c-5
K
1
Coarsening algorithm
Newman
Louvain
Louvain
Loukas (a 0.1)
Louvain
Parameters
437,389
124,565
121,913
352,695
517,446
Table 10: Hyperparameters of GraphGPS HDSE for two LRGB datasets from [23].
Hyperparameter
Peptides-func
Peptides-struct
# GPS Layers
4
Hidden dim GPS-MPNN
96
96
GatedGCN
GatedGCN
GPS-GlobAttn
Transformer
Transformer
# Heads
4
Atlention dropout
0.5
0.5
Graph pooling
mean
Positional Encoding
LapPE-10
LapPE-10
PE dim
16
16
PE encoder
DeepSet 16
DeepSet 128
Batch size
Learning Rate
0.0003 200
0.0003
# Fipcchs
200
# Warmup epochs Weight decay
5
0
K
0
Coarsening algorithm
Newman
METIS (a 0.1)
# Parameters
505,866
506,235
we have covered in the setting part of the experiment section that datasets share in common, we list other settings in Table 11. It's important to note that our hyperparameters were determined within the SGFormer's grid search space. Furthermore, all other experimental parameters, including dropout, batch size, training schemes, optimizer, etc., consistent with those used in the SGFormer [79]. The testing accuracy achieved by the model that reports the highest result on the validation set is used for evaluation. And each experiment repeated 10 times to get the mean value and error bar.
SGFormer on Graph-level Tasks. To accurately demonstrate the capabilities of SGFormer on these datasets, we use all the same experimental settings and conduct the same grid search as outlined in GraphGPS [68].
21

---

Table 11: GOAT HDSE dataset-specific hyperparameter settings.
Dataset
|V|
Hidden dim
Heads
Glob. Layers
Local GNN
GNN Layers
Epochs
LR
Cora
32
128
GCN
2
500
le-2
Citeseer
200
GCN
le-2
Pubmed
64
128
GCN
2
500
le-2
Actor
200
128
GCN
2
1000
le-2
Squirrel
128
128
GCN
2
500
le-2
Chameleon
32
128
GCN
2
500
le:2
ogbn-proteins
1024
128
GrapSAAEE
4
1000
5e-4
ogbn-arxiv
1024
256
GCN
2000
564
arxiv-year
2048
128
GAT
500
le-3
ogbn products
1024
256
GraphSAGE
1000
3e3
ogba-100M 100M
1024
GCN
1o-3
C Additional Experimental Results
C.1 Performance on Large-Scale Heterophilic Graphs
We run additional experiments on the Pokec and snap-patents datasets [55]. Pokec represents the friendship network of Slovak online social platform, where nodes correspond to users and directed edges denote friendship relationships. Each node is labeled with the user's reported gender, and features are derived from profile information, including geographical region, registration time, and age. The mapp-ptennts dataset comprises utility patents in the United States, where nodes represent individual patents and edges indicate citation relationships between them. Node features are extracted from patent metadata.
We use the default splits and features from the LINKX [55] and reported the mean accuracy over runs. The results further demonstrate the effectiveness of our HDSE on large-scale heterophilic graphs.
Table 12: Performance on large-scale heterophilic graphs.
Pokec Accuracyf
map-patents Accuracyf
LINKX
82.04 + 0.07
61.95 + 0.12
GOAT
84.69 0.18
62.43 + 0.37
GOAT HDSE
85.88 + 0.33
63.56 # 0.26
C.2 Sensitivity Analysis Maximal Hierarchy Level K
We conduct sensitivity analysis the maximum hierarchy level K on ZINC. The results shown in Table 13. Note that when K = 0, HDSE degenerates into SPD, leading to a worse performance. This result of K is about graph classification tasks, where the size of graphs is typically small. Therefore, at level (K = 1), the quantity of coarsened nodes is quite small, eliminating the necessity for higher K. We further investigate the impact of K on trgge-grph node classification, across datasets: Squirrel, arxiv-year, and ogbn-arxiv. Based on the results displayed in Table 14, we can make the following observations: (1) K does not consistently yield the best results. Optimal performance is achieved with K" = on some datasets. (2) The improvement brought about by K over K- is relatively minor.
The variation in the optimal K could stem from the distinct hicrarchical structures inherent in different graphs. Larger graphs may possess more pronounced multi-level structures, thus necessitating higher K. However, the slight improvement resulting from a larger K could suggest limitations in the coarsening algorithm.
This study reinforces our selection of K = aligning with results from other hierarchical graph transformer papers such as HSGT [96] and ANS-GT [91]. We anticipate that the real potential of a higher will be revealed through the application of a proper, effective coarsening algorithm on graphs with hierarchical community structures. We look forward to exploring this in the future.
22

---

Table 13: Sensitivity analysis the maximum hierarchy level K of GraphGPS
HDSE ZINC.
K 0 (SPD)
K
K 2
ZINC +
0.069 + 0.003
0.062 + 0.003
0.064 + 0.004
Table 14: Sensitivity analysis on the maximum hierarchy level K of GOAT + HDSE.
Squirrel f
arxiv-year f
oghn-arxiv
K
2.4
54.23 + 0.26
73.26 0.19
2.1
54.51 0.17
73.36 = 0.15
C,3
Sensitivity Analysis of Maximum Distance Length L
Table 15: Overview of the graph diameters of datasets used graph classification
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
Peptides: fune
Peptides struct
Average Diameter
12.47
6.85
9.17
2,00
2.17
$6.86 159
56,86
Maximum Diameter
22
8
12
159
Table 16: Sensitivity analysis the maximum distance length L.
Peptides-fune f
Peptides-struct f
GraphGPS HDSE (L = 20)
0.7105 + 0.0051
0.2481 = 0.0016
GraphGPS HDSE (L 30)
0.7156 = 0.0058
0.2457 = 0.0013
GraphGPS HDSE (L =50) 0.7124 # 0.0053
0.2466 0.0021
For each graph classification dataset, we calculate the graph diameter of each graph in the dataset and then compute the average graph diameter and maximum graph diameter for the entire dataset, as detailed in Table 15. Note that we use high-level HDSE to deal with node classification
large graphs; therefore, we not calculate the distances between the nodes in these large graphs. The data indicates L, = 30 is a reasonable choice, as it encompasses most of the graph diameters. We do not use larger number as we hypothesize that for graphs with larger diameters, the utility of detailed information loses significance beyond certain distance.
Additionally, conducted sensitivity analysis regarding the selection of L, outlined in Table 16, which confirms that L = 30 is an appropriate choice.
C.4
Coarsening Runtime
Table 17 gives the runtime of coarsening algorithms (including distance calculation) on graph-level tasks, illustrating the practicality of our method. The Newman algorithm is unsuited for larger graphs due to high complexity. In addition, our HDSE module almost does not increase the runtime of the baselines. For example, GraphGPS runs at 10 seconds per epoch, compared to 11 seconds per epoch with HDSE module on ZINC.
Additionally, for all large-scale graphs, we employ METIS due to its efficiency with a time complexity of EI). This makes it highly effective for partitioning large graphs, such as ogbn-products, less than 5 minutes, and even the vast ogbn-papers 100M, with size of 0.1 billion nodes, requires only 59 minutes.
Table 17: Empirical runtime of coarsening algorithms.
Algorithm
ZINC
PATTERN
MNIST
P-func
METIS
31s
0.1h
0.2h
0.
Newman
88s
>500h
18h
1.6h
Louvain
76s
5h
1.6h
1.1h
23

---

C.5
Impact of Coarsening Algorithms on Large-scale Graphs
Table 18: Node classification results with linear coarsening algorithms on Cora, CiteSeer, and PubMed.
Cora
CiteSeer t
PubMed f
GOAT GOAT HDSE (METIS)
82.1 + 0.9
71.6 + 1.3
78.9 + 1.5
83,9 0.7
73.1 # 0.7
80.6 # 1.0
GOAT HDSE (Loukas)
8.9
72.5 +
79.8 = 0.9
Our study on coarsening algorithms in Table focuses on the ZINC dataset, where the size of graphs typically small (around 20 nodes). The Newman algorithm exhibits optimal performance these small graphs; however, on large-scale graphs, we use a linear complexity algorithm METIS.
To further assess the impact of linear coarsening algorithms, study the impact of linear coarsening algorithms on node classification across three datasets: Cora, CiteSeer, and PubMed. The results, as shown in Table 18, demonstrate the advantage of METIS, which is the coarsening algorithm used for node classification in our experiments.
conduct additional experiments to
C.6 Synthetic Community Dataset
We evaluate the Community-smal dataset from GraphRNN [88], synthetic dataset featuring com- munity structures. comprises 100 graphs, each with two distinct communities. These communities are generated using the Erdos-Renyi model (E-R). Node features are generated from random numbers and node labels are determined by their respective cluster numbers with accuracy as the chosen evaluation metric. We use the a random train/validation//ee split ratio of 60%
Table 19: Node classification on synthetic community datasets.
Dataset
GT
GT SPD
GT HDSE
Community-small
64.7 1.1
81.5 1.7
88.6 0.9
We select the Louvain method as our coarsening algorithm and integrate the HDSE module into the Graph Transformer (GT). As shown in Table 19, the GT struggles to detect such structures; and solely utilizing SPD proves inadequate; however, our HDSE, enriched with coarsening structural information, effectively captures these structures.
C.7 ANS-GT + HDSSE
We validate the performance of HDSE framework using the efficient ANS-GT [91], which uses a multi-armed bandit algorithm to adaptively sample nodes for attention, We use the Louvain method as coarsening algorithm. And for each pair of nodes sampled adaptively the ANS-GT, we calculate their HDSE and bias the attention computation. For fair comparisons, we tune the hyperparameters using the same grid search reported in their paper [91]. Note that we report the supervised learning setting (different from the text), since this is the one considered in the ANS-GT [91]. Overall, Table 20 shows that HDSE yields consistent performance improvements, even in this challenging scenario, where nodes are sampled.
C.8 Gapformer HDSE
To further validate the effectiveness of our HDSE framework, we also integrate our high-leve HDSE with Gapformer [56], and observe promising results, as reported in Table 21.
Note that we follow the supervised split setting (48%/3296/20% training/validationneess sets) used in the Gapformer [56] here.
C.9 Clustering Coefficients Analysis
We check if there is correlation with the cluster structure according to [35], by computing clustering coefficients five benchmarks in Table 22, but do not observe direct correlation. Notably, the

---

Table 20: Node classification accuracy ANS-GT HDSE (%). The baseline results were taken from [91].
We apply runs random data splitring indicates the results obtained from our re-running.
Model
Cora
Citeseer 1
Pubmed f
GCN
87.33 0.38
79.43 + 0.26
84.86 = 0.19
GAT
86.29 + 0.53
80.13 # 0.62
84,40 = 0.05
APPNP
87.15 0.43
79.33 # 0.35
87.04 0.17
JKNet
87.70
78,43 # 0.31
87.64 0.26
H2GCN
87.22
7
89.55
GPRGNN
0.40
78,46 + 0.88
89.38 + 0.43 0.43
GT
0.62
67.38 0.76
82.11 = 0.39
SAN
74.02
70.64
86.22 + 0.43
Graphormer
82.76 6.82 0.76
Gophormer
87.65 0.20
76.43 0.78
88.33 + 0.44
Coarformer
88.69 0.82
79.20 + 0.89
89.75
ANS-GT
88. 28.60 0.45 89.67 = 0.39
77.75 + 0.79
89.56 + 0.55
ANS-GT HDSE
78.31 # 0.58
90.63 # 0.26
Table 21: Node classification results of Gapformer with and without HIDSE on Cora, CiteSeer, and PubMed.
Cora
CiteSeer f
PubMed f
Gapformer Gapformer + HDSE
87.3 # 0.7 88.4 0.7
76.2 + 1.4
88.9 + 0.4
76.9 # 0.6
89.7 + 0.5
ZINC dataset, which comprises small molecules, has low clustering coefficient; however, HDSE shows a significant improvement on it. This improvement could be attributed to the HDSE capturing chemical motifs that cannot be captured by the clustering coefficient, illustrated in Figure 2.
Table 22: Clustering Coefficients Analysis.
Model
7INC MAE
MNIST Accuracy f
CIFARIO Accuracy
PATTERN Accuracy f
CLUSTER
Accuracy f
Average Clust. Coeff.
0.006
0.477
0.454
0.427
0.316
GT
0.226 = 0.014
90.831 0,161
59.753 0.293
808 0.068
73,169 0.622
GT HDSE
0.159 0.006
94.394 # 0.177
64.651 + 0.591
86.713 + 0.049
74.223 + 0.573
SAT
0.094 0.008
86.848 0.037
77,856 a 0.104
SAT + HDSE
0.084 0.003
86.933 + 0.039
78.513 0.097
GraphGiP
0.070 0.004
98.051 a 0.126
72.298 0.356
86.685 a: 0.059
78.016 a 0.180
GraphGPS HDSE
0.062 0.003
98.367 + 0.106
76.180 0.277
86.737 + 0.055
78.498 + 0.121
D HDSE Visualization
Here, we demonstrate that our HDSE method also provides interpretability compared to the classic GT. We train the GT HDSE and GT on ZINC and Peptides-func graphs, and compare the attention scores between the selected node and other nodes. Figure 5 visualizes the attention scores on ZINC and Peptides-func. The results indicate that, after integrating the HDSE bias, the attention mechanism tends to focus on certain community structures rather than individual nodes seen in classic attention. Furthermore, different selected nodes lead different attention weights and consistently demonstrate our HDSE's s capability to capture multi-level hierarchical structure.
E Additional Discussion
Positional Encoding or Structural Encoding?
We would like clarify that our HDSE method aligns with the definitions of structural encoding. While GraphGPS [68] does classify SPD encoding under relative positional encoding, it defines
25

---

relative structural encoding as "allow two nodes to understand how much their structures differ". Given that our HDSE not only incorporates SPD information but also embeds multi- level graph hierarchical structures, it is reasonable to classify it under the category of structural encoding.
Limitations. In larger graphs, the presence of multi-level structures may require higher maximal hierarchy level, K. The marginal improvements observed with increased K may indicate limitations in the coarsening algorithm. We anticipate that the real potential of higher K will be revealed through the application of a proper, effective coarsening algorithm on graphs with hierarchical community structures. We look forward to exploring this in the future.
Broader Impacts. This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Further Related Works
Graph Transformers over Clustering Pooling. [45] employs hybrid approach that integrates neighbor-sampling local module with global module, the latter featuring a trainable, fixed-size codebook obtained by K-Means to represent global centroids, which noted for its efficiency. Meanwhile, Gapformer [56] involves the incorporation of a graph pooling layer designed to refine the key and value matrices into pooled key and value vectors through graph pooling operations. This approach aims to minimize the presence of irrelevant nodes and reduce computational demands. However, the performance these methods remains constrained due to lack of effective inductive biases.
Graph Transformers Virtual Nodes. Several graph transformer models utilize anchor nodes or virtual nodes for message propagation. For instance, Graphormer [86] introduces a virtual node and establishes connections between the virtual node and each individual node. AGFormer [41] selects representative anchors and transforms node-to-node message passing into an anchor-to- cooorrttonoode nodd message passing process. Additionally, AGT [62] extracts structural patterns from subgraph views and designs an adaptive transformer block to dynamically integrate attention scores node-specific manner.
and
26

---

Molecular
Transformer
HOSE attn
0.08
0.35
0.30
0.20
0.04
0.10
0.05
0.01
Peptides graph
0.34
0.020
0.30
0.08
0.010
0.04
0.00
0.000
Molecular graph
Transformer attn
HDSE attn
0.3
0.15
0.2
-.10
Molacular graph
Transformer attn
HOSE mttn
0.12
0.09
0.04
Molecular graph
Transformer attn
HOSE attn
0.2
0.10
Molecular Transformer
HDSE
0.20
0.3
0.15
0.10
0.0
0.00
Figure 5: Visualization of attention weights for the transformer attention and HDSE attention. The left side illustrates the graph coarsening result. The center column displays the attention weights of a randomly sample node (enclosed weights learned by the HDSE attention. Note that different randomly selected nodes consistently demonstrate the ability to capture a multi-level hicrarchical structure.
green dashed box) learned by the classic GT. while the right column showcases the attention
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations Appendix E.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
We provide the full set of assumptions and complete proofs in Appendix A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Code, data, and instructions are available at https//giittbbcom///UU///999999 HDSE.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer: [Yes]
Justification:
Code, data, and instructions are available at https//gthubb.om///1001119999
HDSE.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https:/nips..ccppblic
guidessCodeSSubmisiinnddiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wtw.bb/iegguieeeeooeeeeiiiieiiie
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe the datasets, splits and hyperparameters in Appendix B. Full configuration files are provided http:///gttub.coommm//////1////9
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We include standard deviations over several random seeds depending on the dataset evaluation protocol, more details are in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
30

---

The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We elaborate the compute and used resources in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://eeein...camaillrriiiieie
Answer: [Yes]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. . if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss impacts in Appendix E.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system Iearns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite the creators. For datasets see Appendix B.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided, For popular datasets, paperswithcode.. http:wiihccooe..c/aattaaeeeeeeee com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's 's creators.
32

---

13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The souree code is available at http://giilbbboom////00xx9999999
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "QQqKygQTyq", "reviewer": "Reviewer_p468", "summary": "To enhance the effectiveness and scalability of graph transformers, this paper proposes a hierarchical distance structural encoding (HDSE) method to incorporate hierarchical structural information with graph transformers. Theoretical analysis of graph transformer equipped with HDSE shows the improvements of both expressiveness and generalization. Experiments have been conducted to verify the effectiveness and efficiency of the proposed method.", "questions": "1. Although combining the hierarchical structural information into graph transformer indeed improves the performance of the transformer, the improvements vary with different coarsening algorithms. Thus, can the authors provide theoretical analysis on what is the optimal hierarchical structural information and conduct more experiments on how to select suitable coarsening algorithm in practice?\n\n2. The authors integrate HDSE into GT, SAT, GraphGPS and GRIT for graph classification and regression experiments (in Table 2), but only use GOAT + HDSE in the node classification tests (in Table 5), why? Moreover, the results of node classification on classical datasets Core, CiteSeer and PubMed should be reported and discussed in the Evaluation section rather than Appendix.", "limitations": "Please refer to weakness and questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is interesting and reasonable to improve the performance of graph transformer based on the hierarchical structural information of the input graph. Moreover, the proposed method is easy to be applied on existing graph transformer models.\n2. Theoretical analysis are provided to guarantee the improvements of expressiveness and generalization of combining HDSE with graph transformer.\n3. A technique of speeding up HDSE to large-scale graphs is provided and verified in experiments on large graphs with millions of nodes.\n4. The paper is well-organized and describes the motivation and methodology clearly.", "weaknesses": "1. It can be seen from Table 4 that the performance of the proposed method varies with different coarsening algorithms and transformer backbones, which should be discussed in details.\n\n2. The experimental settings are not described clearly. Four model + HDSE methods are used for graph-level tasks but only one GOAT + HDSE used for node classification, which makes the results slightly inconvincible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We greatly appreciate your comprehensive understanding of our work and recognizing our contributions! We hope our response below will further enhance your confidence in our work.**\n\n**W1 & Q1: Impact of Coarsening Algorithms**\n\n>It can be seen from Table 4 that the performance of the proposed method varies with different coarsening algorithms and transformer backbones, which should be discussed in details.\n\n>Can the authors provide theoretical analysis on what is the optimal hierarchical structural information and conduct more experiments on how to select suitable coarsening algorithm in practice?\n\nThank you for the insightful comment and question.\n\n\n\nOur study on coarsening algorithms in Table 4 focuses on the ZINC dataset, where the size of graphs is typically small (around 20 nodes). The Newman algorithm exhibits optimal performance on these small graphs; however, as delineated in Appendix C.4, its high computational complexity makes it impractical for larger graphs. Therefore, **for coarsening on large graphs, we recommend using a *linear complexity* algorithm, such as METIS or Loukas**.\n\nFollowing your suggestion, we conducted additional experiments to study the impact of *linear coarsening algorithms* on node classification across three datasets: Cora, CiteSeer, and PubMed. The results, as shown below, demonstrates the advantage of METIS, which is the coarsening algorithm used for node classification in our experiments.\n\n|                      | Cora↑          | CiteSeer↑      | PubMed↑        |\n| -------------------- | -------------- | -------------- | -------------- |\n| GOAT                 | 82.1 ± 0.9     | 71.6 ± 1.3     | 78.9 ± 1.5     |\n| GOAT + HDSE (METIS)  | **83.9 ± 0.7** | **73.1 ± 0.7** | **80.6 ± 1.0** |\n| GOAT + HDSE (Loukas) | 83.5 ± 0.9     | 72.5 ± 0.6     | 79.8 ± 0.9     |\n\nBased on our observations, **we suggest using higher-complexity algorithms like Newman or Louvain for small graphs, and linear-complexity algorithms like METIS for large graphs**. We will include the discussion in the revised manuscript.\n\nAdditionally, different coarsening algorithms tend to produce different hierarchical structures, which benefit different types of graph classification tasks. For instance, preserving rings is crucial for certain tasks. Similarly, the Newman algorithm, which calculates edge betweenness and tends to identify bridges, may be particularly well-suited to networks where bridges play a critical role. \n\nHence, we now treat the choice of coarsening algorithm as a hyperparameter, considering the unique structures inherent to different graphs and the broad scope of various applications. This allows graph experts to tailor their analysis by selecting the most appropriate coarsening algorithm for the structures of specific graphs. \n\nFurther theoretical exploration into the optimal hierarchical structural information for different types of graphs is very interesting. We look forward to exploring this in the future.\n\n\n\n**W2 & Q2: Clarity of Experimental Settings**\n\n> The experimental settings are not described clearly. Four model + HDSE methods are used for graph-level tasks but only one GOAT + HDSE used for node classification, which makes the results slightly inconvincible.\n\n>The authors integrate HDSE into GT, SAT, GraphGPS and GRIT for graph classification and regression experiments (in Table 2), but only use GOAT + HDSE in the node classification tests (in Table 5), why?\n\nWe apologize for the confusion. \n\nPlease note that we have two separate experimental settings: one for **graph-level tasks using Conventional Graph Transformers + HDSE**, another for **large-graph node classification using *Linear-attention* Graph Transformer (e.g., GOAT) + HDSE** (high-level HDSE). This distinction arises from the constraints imposed by the quadratic complexity of conventional graph transformers (like GT, SAT, GraphGPS, GRIT), which are not feasible for large-scale graphs due to out-of-memory issues.\n\nTherefore, since **large-graph node classification necessitates the use of Linformer-style linear-attention graph transformers such as GOAT and Gapformer (see line 214)**, we use GOAT as the base model for this task. To further validate the generability and effectiveness of our HDSE framework, we also experimented with another linear transformer model, Gapformer, and observed promising results, as reported below. \n\n\n\n|                      | Cora↑          | CiteSeer↑      | PubMed↑        |\n| -------------------- | -------------- | -------------- | -------------- |\n| Gapformer            | 87.3 ± 0.7     | 76.2 ± 1.4     | 88.9 ± 0.4     |\n| **Gapformer + HDSE** | **88.4 ± 0.7** | **76.9 ± 0.6** | **89.7 ± 0.5** |\n\nPlease note that we followed the supervised split setting (48%/32%/20% training/validation/test sets) used in the Gapformer paper. We are committed to conduct more experiments to further substantiate our findings and incorporate the results in the revised version.\n\n>  The results of node classification on classical datasets Core, CiteSeer and PubMed should be reported and discussed in the Evaluation section rather than Appendix.\n\nWe appreciate your suggestion. We placed the experiments on Cora, CiteSeer and PubMed in the Appendix due to space constraints, we will move them to the main paper given additional space in the final version. \n\nWe will incorporate your feedback and the rebuttal discussion into the paper. Thank you once again for helping us improve our work.", "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": "", "extra_scores": {}}, {"review_id": "HbHRHTSGMp", "reviewer": "Reviewer_4HNX", "summary": "This paper leverages graph coarsening techniques to help the graph transformer capture hierarchical distance information on a graph, improving its performance on both node-level and graph-level tasks. Besides empirical validation, the paper also provides theoretical guarantee about the better expressiveness and generalization of the graph transformer with the proposed HDSE.", "questions": "Besides the questions mentioned above, there are some additional questions:\n\n**Q1:** In Equation 7 and the illustration below, could you please explain why $\\text{GHD}^m\\prod \\limits_{l=0}^{c-1}P^l$  computes distances from input nodes to clusters at the c-level graph hierarchy? For the input node, why is it not $\\text{GHD}^0$? $\\text{GHD}^m$ represents the distance at hierarchy $m$. What is the meaning of $\\text{GHD}^m$ with the product of projection (coarsening) matrices from level $0$ to $c-1$ (i.e. $\\prod \\limits_{l=0}^{c-1}P^l$)? \n\n**Q2:** In Table 6, the efficiency of GOAT+HDSE, SGFormer, and NodeFormer was compared. However, since NodeFormer and SGFormer use linear attention, is GOAT+HDSE still competitive in terms of efficiency when the graphs are larger (i.e., ogbn-products and ogbn-papers100m)? As the method is claimed to have scalability, illustrations on such large-scale graphs would be beneficial. Additionally, as HDSE is based on graph coarsening and GHD, the cost of coarsening and computation of GHD at each level should also be considered, especially on graphs with more nodes than those used in Table 17.\n\n**Q3:** In the Experiment Setting, the same hyperparameters are used for the proposed method and the baseline transformers. It is also claimed that the hyperparameters are determined within SGFormer's grid search space. However, the optimal hyperparameters for the proposed method may not be suitable for the baseline models. Could you clarify this?\n\n**Q4:** In Appendix 4, the attention scores are displayed between the selected node and the other nodes. How was the node selected? Would different selected nodes lead to different attention weights and still reflect the capability to capture a multi-level hierarchical structure?", "limitations": "When graphs are larger, a higher maximal hierarchy level $K$, is needed to obtain multi-level structure information, which may be limited by current coarsening algorithms. This limitation can be addressed with more effective coarsening algorithms.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well organized and clearly written.\n- The method incorporates coarsening technology, integrating distance information at different hierarchical levels into the attention score. It is easy to understand and implement and is somewhat novel. Additionally, it has a certain theoretical guarantee regarding the expressiveness and generalization of the proposed method.\n- The experiments are comprehensive, evaluating the model's performance on homophilic and heterophilic graphs, as well as on large-scale graphs. Efficiency and ablation studies are also conducted, along with visualizations. The improvements are significant on some datasets, such as Peptides-func, Chameleon, and Squirrel.", "weaknesses": "- There are some missing results in the experiments (mainly in Tables 2 and 5). For example, the results for models such as ANS-GT, NAGphormer, and LINKX on Actor, Squirrel, and Chameleon are missing. Although implementing all work on all datasets is time-consuming, the missing results reduce the paper's convincingness. Additionally, some results differ from previous reports. For instance, LINKX reported its performance as about 56 on the arxiv-year dataset [1], but in this paper, it is around 53.53. Is this because of different experimental settings?\n- Besides, the performance of the model on large-scale heterophilic graphs remains unknown. The few heterophilic graphs shown in Table 5 are not large. To further demonstrate the model's performance on large-scale heterophilic datasets, experiments on datasets such as pokec, snap-patents, and wiki [1] are recommended. This would enhance the quality of the experiments.\n\n[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We greatly appreciate the very detailed feedback and your recognition of our contributions! We hope our response below will further enhance your confidence in our work.**\n\n**W1: Incompleteness of Experimental Results**\n\n> The results for models such as ANS-GT, NAGphormer, and LINKX on Actor, Squirrel, and Chameleon are missing.\n\nSince we experimented with well-known datasets, **we reported the baseline results from their respective original papers**. We did not run them ourselves, but are happy to add results based on your recommendations. We have run all the missing results you mentioned. The additional results below further demonstrate the effectiveness of our HDSE. We will include these results in the revised version.\n\n|                 | Actor↑         | Squirrel↑      | Chameleon↑     |\n| --------------- | -------------- | -------------- | -------------- |\n| ANS-GT          | 35.2 ± 1.3     | 40.8 ± 2.1     | 42.6 ± 2.7     |\n| NAGphormer      | 34.3 ± 0.9     | 39.7 ± 0.8     | 40.3 ± 1.7     |\n| LINKX           | 36.1 ± 1.5     | 41.9 ± 1.2     | 43.8 ± 2.9     |\n| **GOAT + HDSE** | **38.0 ± 1.5** | **43.2 ± 2.4** | **46.0 ± 3.2** |\n\n> The arxiv-year results differ from previous reports. \n\nYes, the observed discrepancies on the arxiv-year dataset are due to different experimental settings. We employed the experimental setup used in GOAT to ensure a fair comparison. The results we reported—53.53 for LINKX and 53.57 for GOAT—are consistent with those in the original GOAT paper (Table 2 in GOAT paper).\n\n**W2: Performance on Large-Scale Heterophilic Graphs**\n\n>  Experiments on datasets such as pokec, snap-patents, and wiki are recommended.\n\nWe appreciate your suggestion.\n\nWe ran additional experiments on the pokec and snap-patents datasets. We attempted to run experiments on the wiki dataset, but the download link for the label file 'wiki_views2M' was no longer valid. We contacted the authors of the LINKX paper but haven't received a response yet. We utilized the default splits and features from the LINKX paper and reported the mean accuracy over 5 runs. The results further demonstrate the effectiveness of our HDSE on large-scale heterophilic graphs. We will include the results in the revised version.\n\n|                 | pokec↑           | snap-patents↑    |\n| --------------- | ---------------- | ---------------- |\n| LINKX           | 82.04 ± 0.07     | 61.95 ± 0.12     |\n| GOAT            | 84.69 ± 0.18     | 62.43 ± 0.37     |\n| **GOAT + HDSE** | **85.88 ± 0.33** | **63.56 ± 0.26** |\n\n**Q1: Explanation of GHD Computation**\n\n> Why $\\mathrm{GHD}^m (\\prod_{l=0}^{c-1} P^l)$ computes distances from input nodes to clusters at the $c$-level graph hierarchy? \n\nWe apologize for the confusion.\n\nAs defined in Eq.2, $\\mathrm{GHD}^m \\in \\mathbb{R}^{|V| \\times |V|}$ represents **the shortest path distance between any two *input nodes* at the $m$-level graph hierarchy.** $\\forall m, \\mathrm{GHD}^m$ has the same size as $\\mathrm{GHD}^0$ (see illustration in Figure 1).\n\nIn Eq.7, our high-level HDSE computes, at each level $c\\leq m \\leq K$, distances between input nodes and clusters obtained by coarsening (i.e., super nodes at the $c$-level graph hierarchy). This is achieved by multiplying the projection matrices $\\prod_{l=0}^{c-1} P^l$ to $\\mathrm{GHD}^m$. In effect, it is equvalent to selecting corresponding columns from $\\mathrm{GHD}^m$. For instance, referring to Figure 1, $\\mathrm{GHD}^1P^0 \\in \\mathbb{R}^{11 \\times 3}$ calculates the distances from input nodes to the super nodes at $1$-level graph hierarchy, essentially selecting the first, fourth, and tenth columns from $\\mathrm{GHD}^1$. \n\nLikewise, $\\mathrm{GHD}^m  (\\prod_{l=0}^{c-1} P^l) \\in \\mathbb{R}^{|V| \\times |V^c|}$ selects $|V^c|$ columns from $\\mathrm{GHD}^m$ to represent the distances, at the $m$-level graph hierarchy, between the input nodes and the $c$-level super nodes (i.e., clusters obtained through coarsening).\n\n**Q2: Efficiency on Large-Scale Graphs**\n\n> Is GOAT+HDSE still competitive in terms of efficiency when the graphs are larger (i.e., ogbn-products and ogbn-papers100M)? \n\nThank you for the suggestion. As noted in lines 214-218, GOAT also uses linear attention. The integration of HDSE does not increase the complexity of GOAT. We provide additional results on larger graphs below, further demonstrating the competitiveness of GOAT+HDSE in terms of efficiency.\n\n| Training time per epoch | ogbn-products | ogbn-papers100M |\n| ----------------------- | ------------- | --------------- |\n| NodeFormer              | 5.6s          | 595.1s          |\n| SGFormer                | **4.8s**      | 579.4s          |\n| **GOAT + HDSE**         | 5.3s          | **446.5s**      |\n\nWe have reported the empirical runtime for coarsening and the computation of GHD on ogbn-products (5min using METIS) and ogbn-papers100m (59min using METIS) in *Appendix C.4* of our manuscript.  We will add the results in Table 17.\n\n**Q3:  Optimal Hyperparameters for Baselines**\n\n> Could you clarify the optimal hyperparameters for the baselines?\n\nWe apologize for the confusion. \n\nIt's important to note that **we obtained the results for all baselines from their original papers or established leaderboards, where they were optimally tuned**. \n\nPlease also note that we adopted two distinct experimental setups:\n\n1. For **Graph-Level Tasks**, we used **Base Model + HDSE**. The base model (e.g., GT, SAT, GraphGPS, or GRIT) was optimally tuned according to the original paper. ***We used the same hyperparameters as the base model to demonstrate the plug-and-play capability of our HDSE***.\n\n2. For **Large-Graph Node Classification**, our model is **GOAT + HDSE**. We tuned the hyperparameters of our model within SGFormer's grid search space.\n\nWe will further clarify that in the revised version.\n\n**Q4: Selection of Nodes to Display Attention Scores**\n\nThank you for your careful reading. Due to space constraints, please refer to the \"Global Reply\": #G1 item.", "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": "", "extra_scores": {}}, {"review_id": "gSLX1gzREC", "reviewer": "Reviewer_o879", "summary": "This work proposes a new structural encoding for graphs, which can be applied in e.g. graph transformers. The method relies on some graph partitioning / coarsening methods to generate hierarchical clustering of a graph, and the structural encoding is more informative than shortest path structural encoding. The paper proves the the new structural encoding has higher expressivity, and empirical results are good on most graph datasets.", "questions": "According to the definition of edge set $E^{k+1}$ in line 78, wouldn't there be information loss? If there are multiple edges across two clusters, the number of edges is not represented. \nIn section 3.3, is the partition matrix low rank? Especially if the coarsening ratio is close to 1, I guess the partition matrix would be almost full rank.", "limitations": "According to authors, for larger graphs, more hierarchies are required.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The method is novel, instead of running a graph transformer on different hierarchical clusters, it makes use of the shortest path on different hierarchies. \nOverall the writing is pretty good, the narrative is clear and easily understandable. The illustration is also nice. \nThe theoretical and empirical results are strong. The experiments are exhaustive.", "weaknesses": "The graph partitioning / coarsening preprocess, including the paritioning algorithm and shortest path computation, can also be complex.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thank you for clearly understanding the core of our work and fully recognizing our contributions!**\n\n**W1: Complexity**\n\n>The graph partitioning / coarsening preprocess, including the paritioning algorithm and shortest path computation, can also be complex.\n\nThis is a fair point. We acknowledge that our approach introduces an additional cost. However, we would like to clarify that this cost is manageable. In our configuration, we employ the METIS algorithm for coarsening on large graphs, which is characterized by a linear time complexity of $O(|E|)$, making it efficient for partitioning graphs. For example, as reported in in *Appendix C.4* of our manuscript, it takes less than five minutes for coarsening and shortest path computation on the ogbn-products graph with 2 million nodes.\n\nWe believe that the enhanced performance of our method, as demonstrated in our empirical evaluations, justifies the additional small computational overhead.\n\n\n**Q1: Theoretical Details**\n\n> According to the definition of edge set Ek+1 in line 78, wouldn't there be information loss? If there are multiple edges across two clusters, the number of edges is not represented.\n\nThank you for carefully checking the theoretical details! We adhere to the standard definitions of Graph Hierarchies. Under this framework, some information loss regarding the number of edges between clusters is inevitable. However, our HDSE framework addresses this by retaining the original edge information within $\\text{GHD}^0$, the shortest path distance matrix of the input graph.\n\n> In section 3.3, is the partition matrix low rank? Especially if the coarsening ratio is close to 1, I guess the partition matrix would be almost full rank.\n\nYes, the partition matrix is inherently low-rank. In our settings, the coarsening ratio is much smaller than 1, ensuring that the partition matrix remains low-rank.\n\nOnce again, we sincerely appreciate your acknowledgment of our work.", "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": "", "extra_scores": {}}]

Author rebuttal:
**We express our gratitude to all reviewers for their invaluable time, effort, and the comprehensive, constructive feedback they have provided!** 

--------

**G1 Additional Visualizations**

We attach a one-page PDF that contains additional visualization results as suggested by the Reviewer 4HNX. In Figure 4 of Appendix D, the node used for visualization was selected randomly. We have clearly marked this node in the **attached PDF** (Figure 1 in PDF) and will update the manuscript accordingly. Furthermore, we have conducted additional visualizations on other randomly selected nodes, also included in the **attached PDF** (Figure 1 in PDF). These visualizations confirm that different selected nodes lead to different attention weights and consistently demonstrate our HDSE's capability to capture a multi-level hierarchical structure.

--------

In the following separate responses, we address each weakness and question raised and will incorporate the suggestions and new results into our revised paper. We are happy to provide additional information if needed.

Meta-review: This manuscript introduces a hierarchical distance structural encoding (HDSE) method to enhance the performance of graph transformers by incorporating hierarchical structural information. Theoretical analysis demonstrates that the HDSE-equipped graph transformer improves expressiveness and generalization, while empirical experiments validate its effectiveness and efficiency. The proposed method outperforms traditional shortest-path structural encoding, offering superior results in both node-level and graph-level tasks.

The reviewers unanimously recommend that this manuscript be accepted. However, they also suggest including a more comprehensive ablation study and caution against making overclaims. The authors are advised to incorporate the reviewers’ feedback when preparing the final version of the paper.
Decision: Accept (poster)