Enhancing Graph Transformers with Hierarchical Distance Structural Encoding

Thank you for clearly understanding the core of our work and fully recognizing our contributions!

W1: Complexity

The graph partitioning / coarsening preprocess, including the paritioning algorithm and shortest path computation, can also be complex.

This 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.

We believe that the enhanced performance of our method, as demonstrated in our empirical evaluations, justifies the additional small computational overhead.

Q1: Theoretical Details

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.

Thank 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.

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.

Yes, 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.

Once again, we sincerely appreciate your acknowledgment of our work.

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.

W1: Incompleteness of Experimental Results

The results for models such as ANS-GT, NAGphormer, and LINKX on Actor, Squirrel, and Chameleon are missing.

Since 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.

The arxiv-year results differ from previous reports.

Yes, 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).

W2: Performance on Large-Scale Heterophilic Graphs

Experiments on datasets such as pokec, snap-patents, and wiki are recommended.

We appreciate your suggestion.

We 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.

Q1: Explanation of GHD Computation

Why $\mathrm{GHD}^m (\prod_{l=0}^{c-1} P^l)$ computes distances from input nodes to clusters at the $c$-level graph hierarchy?

We apologize for the confusion.

As 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).

In 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$.

Likewise, $\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).

Q2: Efficiency on Large-Scale Graphs

Is GOAT+HDSE still competitive in terms of efficiency when the graphs are larger (i.e., ogbn-products and ogbn-papers100M)?

Thank 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.

We 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.

Q3: Optimal Hyperparameters for Baselines

Could you clarify the optimal hyperparameters for the baselines?

We apologize for the confusion.

It's important to note that we obtained the results for all baselines from their original papers or established leaderboards, where they were optimally tuned.

Please also note that we adopted two distinct experimental setups:

1. 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.

2. For Large-Graph Node Classification, our model is GOAT + HDSE. We tuned the hyperparameters of our model within SGFormer's grid search space.

We will further clarify that in the revised version.

Q4: Selection of Nodes to Display Attention Scores

Thank you for your careful reading. Due to space constraints, please refer to the "Global Reply": #G1 item.

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.

W1 & Q1: Impact of Coarsening Algorithms

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.

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?

Thank you for the insightful comment and question.

Our 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.

Following 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.

Based 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.

Additionally, 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.

Hence, 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.

Further 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.

W2 & Q2: Clarity of Experimental Settings

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.

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?

We apologize for the confusion.

Please 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.

Therefore, 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.

Please 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.

The results of node classification on classical datasets Core, CiteSeer and PubMed should be reported and discussed in the Evaluation section rather than Appendix.

We 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.

We will incorporate your feedback and the rebuttal discussion into the paper. Thank you once again for helping us improve our work.