HOGT: High-Order Graph Transformers

Dear Reviewer,

Thanks for reviewing our paper and the valuable comments. Please find our point-by-point response to your concerns below.

Q1. Analysis on the sensitivity of the HOGT model's performance to its hyperparameters such as walk length, hidden dimension, and dropout. Have the authors experimented with different optimization algorithms for hyperparameter tuning, and if so, what were the results?

A1. We conducted an analysis of HOGT's sensitivity to various hyperparameters, including walk length, hidden dimension, dropout, and optimizer. The results are summarized in the following table. From the findings, we observe that HOGT, when using the random walk sampling method, demonstrates low sensitivity to walk length and dropout. However, on the Cora dataset, the model shows higher sensitivity to the hidden dimension and optimizer, indicating its importance in influencing performance. In our experiments, AdamW is adopted for HOGT and other GT models.

Table: The performances of HOGT with different hyperparameters.

Q2. Further exploration of the sampling method's performance in graphs with irregular or sparse structures would enhance the understanding of the model's robustness.

A2. Citeseer and Pubmed can be considered sparse graphs, with node-to-edge ratios of 1.4 and 2.2, respectively. To further evaluate the robustness of the proposed HOGT in handling graphs with fewer edges, we conducted additional experiments by randomly removing 10% and 20% of the edges from Citeseer and Pubmed. The results, presented in the following table, demonstrate that HOGT, when using the random walk sampling method, maintains strong performance even under these conditions. This highlights the robustness of HOGT in processing graphs with irregular or sparse structures.

Table: The performance of HOGT (randomwalk) with sparse structure on Citeseer and Pubmed. The edge ratio means the reserving ratio of original edges.

Thanks again for your patience! Here is the rest.

Q6. Could the authors discuss how HOGT captures long-term dependencies in the graph and compare this with other methods that focus on long-range interactions?

A6. In HOGT, long-range dependencies between nodes are effectively captured through the use of community nodes and the three-step message-passing scheme. Community nodes act as intermediaries that aggregate and propagate information from their associated nodes, enabling efficient communication between distant nodes. Specifically, any two graph nodes can interact within fewer than three hops via two community nodes, facilitating the propagation of long-range dependencies with minimal computational overhead.

Compared to HOGT, general Graph Transformer (GT) models address long-range interactions by establishing direct connections between distant nodes through global attention. While this approach is effective for modeling global dependencies, it often incurs substantial computational costs due to the quadratic complexity of global attention. Alternative methods attempt to mitigate this by introducing anchor nodes [1, 2] or supernodes [3, 4], derived from the graph structure to connect distant nodes. However, these methods heavily depend on the initial graph structure, which may inadequately represent and balance critical information in complex or large-scale graphs. More discussion can be found in the Related Work section.

Empirical results on heterophilic and large-scale datasets, which inherently require modeling long-range dependencies, highlight HOGT's effectiveness. Our experiments demonstrate that HOGT consistently outperforms other GT models capable of capturing global information. This performance gain arises from HOGT's ability to efficiently capture and propagate long-range dependencies through its community-node mechanism, while maintaining a lower computational complexity compared to traditional global attention-based methods.

[1] Wenhao Zhu, et al. Anchorgt: Efficient and flexible attention architecture for scalable graph transformers. IJCAI, 2024.

[2] Bo Jiang, et al. Agformer: Efficient graph representation with anchor-graph transformer. arXiv preprint arXiv:2305.07521, 2023.

[3] Weirui Kuang, et al. Coarformer: Transformer for large graph via graph coarsening, 2022. In URL https://openreview. net/forum, 2021.

[4] Wenhao Zhu, et al. Hierarchical transformer for scalable graph learning. IJCAI, 2023.

Thank you very much for your patience! Here is the rest part.

Q3. A more detailed comparison of HOGT's computational complexity, including training time and memory usage, with other state-of-the-art models is needed.

A3. The following table provides a detailed comparison of the training time per epoch, inference time, and GPU memory usage for popular GNN methods including GAT and APPNP, and GT models including Graphormer, LiteGT, polynormer, and HOGT on the Cora and ogbn-proteins datasets. Since the standard practice for model training on these datasets involves a fixed number of epochs, we report the training time per epoch to effectively compare training efficiency.

The results show that HOGT is orders of magnitude faster than Graphormer and polynormer, which require quadratic complexity for global attention. Additionally, HOGT significantly reduces memory consumption due to its efficient implementation of global attention with $\mathcal{O}(N)$ complexity. Compared to GAT, APPNP, and SGFormer, HOGT strikes a balance between performance and efficiency. This result indicates the effectiveness of HOGT in scaling to large-scale datasets by introducing community nodes and a multi-step message-passing strategy.

Table: Efficiency comparison of HOGT and graph Transformer competitors w.r.t. training time per epoch, inference time and GPU memory (GB) cost on a A100. The missing results are caused by out-of-memory.

Q4. Can the authors elaborate on the theoretical analysis of the model's expressiveness and how it relates to the approximation of global attention?

A4. The theoretical foundation for approximating self-attention in HOGT is based on the following: (1) Message-Passing Neural Networks with community nodes (MPNN+CN) can act as a self-attention layer, and (2) under the three-step message-passing framework, the combination of MPNN+CN with self-attention achieves an approximation of full self-attention in graphs.

For Point (1): The approximation error of self-attention by MPNN+CN can be bounded under the following assumptions. A detailed proof can be found in [1]. Below, we summarize the key assumptions and results:

Assumption 1.

$\forall i \in [n]$, $\boldsymbol{x}_i \in \mathcal{X}_i$, and $|\boldsymbol{x}_i| < C_1$, implying that the feature space $\mathcal{X}$ is compact.

Assumption 2.

$|\boldsymbol{W}_Q| < C_2$, $|\boldsymbol{W}_K| < C_2$, and $|\boldsymbol{W}_V| < C_2$ for the target layer $\mathbf{L}$. Combined with Assumption 1, this ensures that the unnormalized attention $\alpha^{\prime}(\boldsymbol{x}_i, \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{W}_Q (\boldsymbol{W}_K)^T \boldsymbol{x}_j$ is bounded, and $\sum_j e^{\alpha^{\prime}(\boldsymbol{x}_i, \boldsymbol{x}_j)}$ is also upper and lower bounded.

Under these assumptions, MPNN+CN with $\mathcal{O}(1)$ width and $\mathcal{O}(1)$ depth can approximate ${{Performer}}$ and ${\text{Linear-Transformer}}$ arbitrarily well, as shown in [1]. In Proposition 4.1, we consider the Linear Transformer for simplicity.

Dear Reviewer,

Thank you for your thoughtful consideration and for taking the time to review our rebuttal. We greatly appreciate your feedback and your decision to increase the score in support of our paper.

Best regards,

The Authors

Dear Reviewer,

We sincerely appreciate your time and effort in providing valuable feedback. Below, we have addressed each of the concerns and questions raised.

Q1. The problems of node classification and graph classification are well-studied in the past 10 years. You can find the old baselines like GAT are very competitive. Due to task saturation, HOGT shows relatively small improvements compared to these simple algorithms.

A1. Please allow us to clarify the following points:

1. In our experiments, HOGT consistently achieves notable performance improvements across various datasets compared to traditional baselines. For example, as shown in Table 2 of the paper, HOGT outperforms GAT by absolute margins of 4.15% and 4.46% on Pubmed and ogbn-arxiv, respectively. Furthermore, HOGT demonstrates significantly better performance on heterophilic datasets, achieving substantial margins of improvement over GAT and other traditional GCN-based methods. Additionally, we conducted a t-test to evaluate the statistical significance of HOGT's improvements, finding that the gains over the baselines are highly significant (p-value $\ll$ 0.05).

2. Traditional GCN-based methods generally perform well on homophilic datasets (as shown in Table 2 of the paper), while heterophily-based methods like H2GCN and GPRGNN excel on heterophilic datasets (Table 3 in the paper). GT models, on the other hand, deliver superior results on large-scale datasets such as ogbn-arxiv, roman-empire, and amazon-ratings, which require capturing long-range dependencies.

HOGT distinguishes itself as a unified framework capable of capturing diverse types of information—local, global, and high-order relationships (Table 1 in the paper). Unlike prior models that focus on specific aspects, HOGT demonstrates versatility by effectively accommodating various graph types (graphs and hypergraphs), data characteristics (homophily and heterophily), data scales (small-scale and large-scale), and diverse graph tasks. This adaptability underscores the broader applicability of the HOGT framework.

Table: A summary of the capabilities of various graph models in processing graph information and types

Q2. The theoretical part of the paper seems like mainly from a related work. Further analysis about HOGT is needed.

A2. We analyze the proposed HOGT framework from two perspectives: (1) HOGT's ability to approximate self-attention as implemented in general Graph Transformers (GTs), and (2) HOGT's functionality as a high-order Graph Transformer leveraging community nodes (detailed in Appendix A.4 of the paper).

1. Approximation of Self-Attention in HOGT:

The approximation of self-attention in HOGT is demonstrated as follows:

• (1) Message-Passing Neural Networks with community nodes (MPNN+CN) can act as a self-attention layer.

• (2) Within our three-step message-passing framework, the combination of MPNN+CN and self-attention achieves an approximation of full self-attention in graphs.

While point (1) has been established in related work [1], we focuse on demonstrating (2) in the paper. Specifically:

• In the Graph Node-to-Community Node (G2C-MP) step, message-passing through a newly introduced community node (connected to all nodes within the community) approximates self-attention within the community, as supported by Proposition 4.1 in the paper.

• In the Community Node-to-Community Node (C2C-ATTN) step, a self-attention mechanism propagates information among community nodes.

• Finally, in the Community Node-to-Graph Node (C2G-MP) step, global information from community nodes is propagated back to graph nodes via another MPNN+CN, approximating "full" self-attention.

Thank you very much for your patience! Here is the rest part.

2. HOGT as a Higher-Order Graph Transformer:
We analyze HOGT’s ability to capture higher-order representations through the role of community nodes, which function analogously to hyperedges in hypergraph convolutional networks.

• Encoding Complex Relationships:
  To capture higher-order correlations in complex graphs, HGCNs introduce hyperedges connecting multiple nodes. Similarly, HOGT introduces a community node for each community, representing multiple nodes sharing common properties (e.g., semantics or structural information). Like hyperedges, community nodes connect to every node within their community, enabling higher-order information encoding.

• High-Order Message-Passing:

(Apologies for the poor readability caused by incompatible formulas. Please refer to the relevant content in Appendix A.4 in the paper for clarification.)

Following the message-passing paradigm, HGCNs first aggregate information along hyperedges and then propagate it to nodes. In spectral-based HGCNs, convolution is defined as:

$\mathbf{\Delta}=\mathbf{D}_{v}^{-1 / 2} \mathbf{S} \mathbf{W}$

$\mathbf{D}_{e}^{-1} \mathbf{S}^{T}$

$\mathbf{D}_{v}^{-1 / 2}$,

$\boldsymbol{h}^{(k)} =\sigma\left(\mathbf{\Delta} \boldsymbol{Z}^{(k-1)} \mathbf{\Theta}^{(k)}\right)$,

where $\mathbf{D}_v$ and $\mathbf{D}_e$ are diagonal matrices representing vertex and hyperedge degrees, $\mathbf{S}$ is the incidence matrix indicating node-hyperedge relationships, and $\mathbf{W}$ represents hyperedge connections. This can be refined into three steps: node-to-hyperedge, hyperedge-to-hyperedge, and hyperedge-to-node:

$\boldsymbol{a}_{e^h}^{(k)} = \mathbf{S}^{\top} \boldsymbol{z}^{(k-1)},$

$\boldsymbol{a}_{e^h}^{(k)} =$

$\mathbf{W} \boldsymbol{a}_{e^h}^{(k)},$

$\boldsymbol{z}^{(k)} = \mathbf{S} \boldsymbol{a}_{e^h}^{(k)}.$

Similarly, HOGT’s three-step message-passing process—Graph Node-to-Community Node, Community Node-to-Community Node, and Community Node-to-Graph Node—mirrors this structure. Moreover, in HGCNs, the relationships of hyperedges can typically be ignored, i.e., $\mathbf{W}=\mathbf{I}$. In HOGT, the framework can also be simplified to two steps, excluding the Community Node-to-Community Node step.

At a high level, graph convolutional networks can be seen as special cases of hypergraph convolutional networks. In comparison, our proposed HOGT framework can be simplified to other existing GT models, demonstrating its adaptability and generalizability.

[1] Chen Cai, et al. On the connection between MPNN and graph transformer. ICML 2023.

Q3. The method is too complex.

A3. While HOGT employs a general framework with a multi-step message-passing strategy, its overall complexity remains low and manageable.

1. Computational Complexity: The complexity of HOGT is $\mathcal{O}(m^2 + N)$, where $m$ is the number of communities and $N$ is the number of graph nodes. Since $m \ll N$, the complexity of HOGT approximates to $\mathcal{O}(N)$, making it nearly linear. In contrast, general Graph Transformers (GTs) have a complexity of $\mathcal{O}(N^2)$. This difference makes HOGT significantly more computationally efficient than general GTs, particularly for large-scale graphs. Regarding the time complexity of community sampling, this process is performed as a preprocessing step using techniques like random walk or spectral clustering and does not incur additional computational costs during model training. Furthermore, HOGT maintains excellent performance even when treating the entire graph as a single community, demonstrating its flexibility.

2. Efficiency in Practice: Experimental results confirm that HOGT significantly reduces training time and memory usage, addressing concerns about its complexity. Table 6 in the paper reports the training time per epoch, inference time, and GPU memory consumption on the Cora and ogbn-arxiv datasets. To ensure a fair comparison, we report the training time per epoch, as fixed training epochs are standard for these datasets. We observe that HOGT is orders of magnitude faster than popular GT models, including Graphormer, LiteGT, and Polynormer. Additionally, HOGT's memory consumption is substantially lower due to its simplified global attention mechanism, which scales with $\mathcal{O}(N)$ complexity.

These aspects demonstrate that while HOGT introduces a general and powerful framework, its design is computationally efficient, practical, and well-suited for large and complex graph datasets.

Dear Reviewer,

Thank you for taking the time to review our paper and provide valuable feedback. Below are our responses to your concerns.

Q1. Domain Limitation of Datasets. Expanding the evaluation to include diverse domains, such as those in the TEG-DB datasets [1], which feature rich node and edge text, would strengthen the findings.

A1. Thank you for your insightful suggestion. We have conducted experiments on the TEG-DB datasets [1], specifically the Goodreads-Children and Goodreads-Crime datasets. The results, summarized in the table below, demonstrate that HOGT achieves either better or comparable performance compared to other methods. In these experiments, we treated the data in each batch as a community and introduced a community node for each batch, effectively extending the HOGT framework to these diverse domains.

Table: Performance Comparison Across Methods on Goodreads-Children.

Table: Performance Comparison Across Methods on Goodreads-Crime.

[1] Zhuofeng Li, et al. TEG-DB: A Comprehensive Dataset and Benchmark of Textual-Edge Graphs. NeurIPS 2024.

Q2. Narrow Applicability. The model’s applicability is somewhat restricted to specific tasks within graph domains, such as node classification. The authors should consider its potential for other important tasks, like link prediction.

A2. In addition to the experiments on the TEG-DB datasets for link prediction, we also applied HOGT to graph classification tasks to further demonstrate its versatility and superiority, as detailed in Appendix A.8.

Performance on Graph Classification

We evaluated HOGT on several widely-used real-world datasets from the TU database [2] for graph classification tasks.

NCI1: This dataset consists of 4,110 molecular graphs representing two balanced subsets of chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines.

PROTEINS: This dataset includes 1,113 protein graphs, where each graph corresponds to a protein molecule. Nodes represent amino acids, and edges capture interactions between them.

As shown in Table 12 in the Appendix A.8, HOGT achieves state-of-the-art performance across all datasets. Compared to GT models such as GraphGPS, HOGT demonstrates the ability to encode more comprehensive and nuanced information in the graph, highlighting its effectiveness and broader applicability beyond node classification.

[2] Christopher Morris, et al. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv:2007.08663, 2020.

Dear Reviewer:

Thank you for your constructive comments and suggestions. They have been invaluable in helping us enhance the quality and clarity of our paper. Please find our point-by-point responses to your concerns below.

Q1. The strict hierarchy in the three-step message-passing mechanism could introduce bottlenecks in information flow. By requiring all long-range communication to route through community nodes, the model risks distorting or weakening critical direct relationships between nodes—especially in tasks where pairwise connections hold essential information. The assumption that this hierarchical structure is universally beneficial may be too broad, as the paper offers little discussion on cases where direct node-to-node communication might better capture necessary details.

A1. Please allow us to clarify pairwise connections and their importance from the following perspectives:

Preservation of Pairwise Connections: In scenarios where pairwise relationships hold critical information, the proposed HOGT framework explicitly addresses this during the final step—Community Node-to-Graph Node. At this stage, the representation of each graph node is updated by aggregating information from both its associated community nodes and its directly connected neighbors. This mechanism ensures that essential local connections are preserved and effectively incorporated into the model.

Flexibility in Community Optimization: HOGT is a general framework that allows for the optimization of the number of communities to suit different datasets. In extreme cases, treating the entire dataset as a single community naturally emphasizes direct node-to-node communication. Furthermore, the random walk sampling approach generates communities for only a subset of graph nodes, offering flexibility in balancing local and global interactions. This adaptability ensures that the model can capture pairwise relationships when necessary while still benefiting from the hierarchical structure.

Overall, the hierarchical structure introduced by community nodes provides a versatile framework for balancing local and global interactions in graphs. While HOGT is designed to capture comprehensive information across various types of graphs, we acknowledge that achieving an optimal balance between local and global information in complex graph structures remains a challenge. This is a current limitation and a promising direction for future research.

Q2. The approach to initializing community nodes also feels underdeveloped and could pose challenges. Starting with random initialization may lead to instability and slower convergence, particularly in early training stages. Additionally, there's no clear strategy for aligning community node dimensionality with original node features, which seems like a significant gap. Given that these community nodes are crucial bridges for information flow, their initial setup could substantially impact the quality of the representations learned.

A2. We appreciate the reviewer’s insightful comments regarding the initialization of community nodes and its potential impact on stability and convergence.

Initialization of Community Nodes: The introduced virtual nodes (community nodes) can be initialized using either zero vectors or random initialization. In our experiments, we observed that both approaches resulted in similar final performance after 200 epochs, suggesting that the choice of initialization method has minimal impact on the final outcomes.

Stability and Convergence: To address your concerns about stability, we have conducted experiments with 10 independent runs using different random seeds. The results demonstrated low variance, indicating that our framework is robust and stable across various initialization conditions. While random or zero initialization is effective, an alternative approach—such as using max or mean pooling of the features of graph nodes within a community to initialize community node features—could potentially accelerate convergence by providing a more informed starting point for community node embeddings. However, this method introduces additional computational overhead, which we have deliberately avoided in our current implementation to maintain efficiency.

We will update our paper to discuss the potential advantages of alternative initialization strategies and the trade-offs involved, ensuring a comprehensive understanding of our approach.

Thank you for your rebuttal. I have no further questions. I will maintain my score.