HOGT: High-Order Graph Transformers

Authors: Xueqi Ma, Xingjun Ma, Chuang Liu, Sarah Monazam Erfani, James Bailey
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph representation learning, Graph Transformer

Abstract:
Inspired by the success of transformers on natural language processing (NLP) and computer vision (CV) tasks, graph transformers (GTs) have recently been proposed to boost the performance of graph learning. 
However, the attention mechanisms used in existing GTs face certain limitations in capturing crucial topological information or scaling to large graphs, due to their quadratic complexity. 
To address these limitations, in this paper, we propose a high-order information propagation strategy within the transformer architecture to simultaneously learn the local, long-range, and higher-order relationships of the graph. 
\textcolor{blue}{We first propose a flexible sampling method to extract communities from the graph, and create new community nodes and in particular a learnable community sampling method with reinforcement learning.} We then propose a three-step message-passing strategy dubbed \emph{HOGT} to capture the local and higher-order information in the communities and propagate long-range dependency information between the community nodes to finally obtain comprehensive node representations. Note that as structural information has been flexibly integrated into our designed community-based message-passing scheme, HOGT discards the positional encoding which was thought to be important for GT.

Decision: reject
Reviewer scores: 6, 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1729174703777

thread_type:
official_review

<thread_object>
creator: reviewer_rhuk

<content>
summary:
The paper presents a unique approach to graph learning by integrating high-order information propagation within the transformer architecture. The paper empirically shows that HOGT achieves competitive results on node and graph classification tasks, especially on heterophilic datasets.

strengths:
The idea of using a learnable community sampling method with reinforcement learning for graph representation is novel. It combines the advantages of community detection and adaptive sampling.By addressing the limitations of existing graph transformers in terms of capturing topological information and scalability, this work contributes to the advancement of the field and opens up new research directions for further exploration.

weaknesses:
Analysis on the sensitivity of the HOGT model's performance to its hyperparameters such as walk length, hidden dimension, and dropout.

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

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

questions:
Could the authors provide more insights into how HOGT scales with graph size, especially in terms of memory usage and training efficiency?


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

How sensitive is HOGT to its hyperparameters, particularly the number of communities and the reinforcement learning-based sampling method?

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?

How sensitive is the performance of HOGT to changes in hyperparameters such as the hidden dimension and dropout rate? 
Have the authors experimented with different optimization algorithms for hyperparameter tuning, and if so, what were the results?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730218194282

thread_type:
official_review

<thread_object>
creator: reviewer_nhvf

<content>
summary:
The paper presents HOGT, a graph transformer that uses community-based processing to handle graph topology and computation complexity issues.
The method consists of three parts: Community sampling using reinforcement learning, Message-passing within communities and information propagation between community nodes. HOGT achieves highly competitive results
across node and graph classification tasks.

strengths:
* The technical part of the paper is good -- the method is of careful design and implementation.

weaknesses:
1. 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.
2. The theoretical part of the paper seems like mainly from a related work. Further analysis about HOGT is needed.
3. The method is too complex.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730423516602

thread_type:
official_review

<thread_object>
creator: reviewer_x76c

<content>
summary:
The paper proposes a high-order graph transformer (HOGT) for graph learning tasks. HOGT introduces a flexible sampling method to extract communities from the graph and a three-step message-passing strategy to capture local, long-range, and higher-order relationships of the graph. The paper demonstrates the effectiveness of HOGT on node classification tasks and shows its superiority over other graph models.

strengths:
(1) The paper introduces a novel approach, HOGT, that combines community-based sampling and message-passing to capture comprehensive information in graph learning.

(2) HOGT achieves competitive results on various graph datasets, demonstrating its effectiveness in node classification tasks.

(3) The paper provides a theoretical analysis of HOGT, showing its approximation capabilities and the relationship with other graph models.

weaknesses:
(1) 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.

(2) 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.

[1] "TEG-DB: A Comprehensive Dataset and Benchmark of Textual-Edge Graphs." NeurIPS 2024.

questions:
See weakness above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730663389537

thread_type:
official_review

<thread_object>
creator: reviewer_2d8y

<content>
summary:
This paper introduces HOGT (High-Order Graph Transformer), a new architecture that tackles key issues in existing graph transformers, especially around capturing topology and scaling to large graphs. The authors use a three-step message-passing process: sampling communities from the graph, creating community nodes as information bridges, and enabling message flow between graph and community nodes. This design removes the need for positional encoding, embedding structure naturally through communities. HOGT shows strong performance across different types of graphs, with impressive computational efficiency.

strengths:
1. The paper introduces a well-founded architecture with a three-step message-passing strategy that effectively captures multi-scale information in graphs, handling local, global, and higher-order details. Theoretically, it’s shown that HOGT can approximate global attention and unify existing models, while the community-based design removes the need for positional encoding.

2. HOGT also demonstrates strong versatility, performing well on various graph types (homophilic, heterophilic, and hypergraphs) and adapting to different community sampling methods, which enhances scalability across graph sizes. Efficiency is greatly improved, with computational complexity reduced from O(N²) to O(m² + N), validated by experiments that show strong results over state-of-the-art methods, especially on challenging datasets.

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

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

questions:
See weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1733216202934

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Chairs and Reviewers,

Hope this message finds you well.

With the closing of the discussion period, we present a brief summary of our discussion with the reviewers as an overview for reference. First of all, we thank all the reviewers for their insightful comments and suggestions. We are encouraged by the positive feedback, as highlighted below:

R1. "The paper introduces a well-founded architecture...", "Theoretically, it’s shown that HOGT can approximate global attention and unify existing models,...", "demonstrates strong versatility, efficiency, ...".

R2. "The paper introduces a novel approach...", "demonstrating its effectiveness in node classification tasks", "provides a theoretical analysis of HOGT,...".

R3. "The technical part of the paper is good -- the method is of careful design and implementation."

R4. “The idea is novel”， “contributes to the advancement of the field and opens up new research directions for further exploration.“.

We have carefully addressed all the comments and provided detailed responses. Since we did not receive specific questions or response from Reviewer nhvf during rebuttal, we summarize the main concerns of other reviews and outline the corresponding updates in the revised manuscript:

**The approach to initializing community nodes.** We added an analysis of community node initialization in Appendix A.7 and shown that the existing initialization approach is reasonable.

**The performance of HOGT on link prediction.** Additional experiments on the TEG-DB dataset for link prediction are included in Appendix A.9, further highlighting the effectiveness of HOGT.

**Hyperparameter sensitivity and robustness evaluations.** We conducted hyperparameter sensitivity and robustness evaluations, presented in Appendices A.10 and A.11, respectively. The results confirm the robustness of the proposed HOGT.

Based on the discussion with reviewers, we also present a brief summary of our paper as follows.

**Observation:** Existing graph models struggle to effectively capture the complex structural relationships in the graph for different graphs and data types, while also providing theoretical support.

**Solution:** We propose a flexible sampling method followed by a three-step message-passing framework in GTs to capture comprehensive information achieving high expressiveness for graph representation learning.

**Results:** The effectiveness of our framework has been demonstrated on various graph types (graph and hypergraph), data types (homophily and heterophily), data scales (same-scale and large-scale), and different graph tasks (node classification, graph classification, and link prediction).

**Highlights:**

- Introduced a higher-order message-passing strategy with flexible sampling methods. 

- Unified message-passing and GTs by constructing communities and introducing new community nodes.

- Provided theoretical proof that the three-step message-passing framework with newly introduced community nodes achieves global attention akin to general transformers.

- Demonstrated the versatility and robustness of HOGT through extensive experiments.


Thanks again for your efforts in the reviewing and discussion. We appreciate all the valuable feedback that helped us to improve our submission.

Sincerely

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
- Scientific Claims and Findings:
    - This paper introduces a high-order graph transformer (HOGT) architecture designed for node classification. The approach involves sampling communities from the graph, creating community nodes, and facilitating message passing between the graph and community nodes. HOGT demonstrates competitive performance across various node classification tasks.
- Strengths:
   - The introduction of a learnable community sampling method using reinforcement learning.
   - The design of the proposed HOGT is well-reasoned.
- Weaknesses:
    - Although HOGT is a reasonable design, it closely resembles existing works such as hierarchical graph transformers or those utilizing graph cluster structures [1] [2] [3] [4], as mentioned in lines 144–151 of the related work section. While the authors discuss the distinctions between HOGT and these works, the core differences do not appear to be substantial.

             [1] Wenhao Zhu, Tianyu Wen, Guojie Song, Xiaojun Ma, and Liang Wang. Hierarchical transformer for scalable graph learning, 2023. 

             [2] Wenhao Zhu, Guojie Song, Liang Wang, and Shaoguo Liu. Anchorgt: Efficient and flexible attention architecture for scalable graph transformers, 2024. 

             [3] Weirui Kuang, Z WANG, Yaliang Li, Zhewei Wei,and Bolin Ding. Coarformer: Transformer for large graph via graph coarsening, 2022. 

             [4] Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is more: on the over-globalizing problem in graph transformers, 2024.

   - The AC concurs with Reviewer nhvf that similar performance can be achieved by older and simpler models. Consequently, the advantages offered by HOGT and similar graph transformer methods may not be significant.

- Most Important Reasons for Decision:
     - Based on the weaknesses mentioned above.