CTGC: Cluster-Aware Transformer for Graph Clustering

Authors: Jinxiang Xia, He Zhu, Junran Wu, Ke Xu
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Clustering, Graph Transformer

Abstract:
Graph clustering is a fundamental unsupervised task in graph mining. However, mainstream clustering methods are built on graph neural networks, thus inevitably suffer from the difficulty in long-range dependencies capturing. Moreover, current two-stage clustering scheme, consisting of representation learning and clustering, limits the ability of the graph encoder to fully exploit task-related information, resulting in suboptimal embeddings. In this work, we propose CTGC ($\textbf{C}$luster-Aware $\textbf{T}$ransformer for $\textbf{G}$raph $\textbf{C}$lustering) to mitigate these issues. Specifically, considering the excellence of transformer in long-range dependencies modeling, we first introduce transformer to graph clustering as the crucial graph encoder. To further enhance the task awareness of encoder during representation learning, we presents two mechanisms: momentum cluster-aware attention and cluster-aware regularization. In momentum cluster-aware attention, previous clustering results are adopted to guide the node embedding production with specially designed cluster-aware queries. Cluster-aware regularization is designed to fuse the cluster information into bordering nodes through minimizing the overlap between different clusters while maximizing the completeness of each cluster. We evaluate our method on seven real-world graph datasets and achieve superior results compared to existing state-of-the-art methods, demonstrating its effectiveness in improving the quality of graph clustering.

Decision: reject
Reviewer scores: 5, 5, 3

Reviews and discussion:
<thread>
creation date:
1730104786080

thread_type:
official_review

<thread_object>
creator: reviewer_5hpk

<content>
summary:
The paper introduces an approach to graph clustering by incorporating the transformer architecture, which is particularly excel at capturing long-range dependencies. The authors propose two key mechanisms: momentum cluster-aware attention and cluster-aware regularization, to enhance the model's task awareness during representation learning.

strengths:
- Alleviating the long-distance dependency problem in graph clustering is a research challenge.
- The paper is written in a very clear and accessible manner.

weaknesses:
- The author claims to be the first to introduce the graph transformer, but this statement isn't entirely accurate. Several prior studies[1,2] on graph clustering have likely also incorporated graph transformers.
- How does the transformer's ability to capture long-range dependencies translate to improved clustering performance compared to traditional GNNs, and what theoretical justifications exist for this choice?
- The long-distance dependencies in graph clustering are constrained by the over-smoothing problem. Does the method proposed by the authors effectively address the over-smoothing issue in GNNs?
- Could the authors elaborate on the design choices behind the momentum cluster-aware attention mechanism, and how it contributes to the model's ability to learn more effective representations?
- Given the computational complexity of transformer models, how does the proposed model scale with larger and more complex graphs?
- The authors' method is very similar to [3]. Could you explain the differences between them?

[1] Transforming Graphs for Enhanced Attribute Clustering: An Innovative Graph Transformer-Based Method

[2] Attribute graph clustering via transformer and graph attention autoencoder

[3] Less is More: on the Over-Globalizing Problem in Graph Transformers

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

</thread>
<thread>
creation date:
1730305956029

thread_type:
official_review

<thread_object>
creator: reviewer_guuy

<content>
summary:
This paper presents CTGC, a novel approach integrating transformers into graph clustering to effectively capture long-range dependencies. The method enhances representation learning through momentum cluster-aware attention and cluster-aware regularization, resulting in improved clustering performance on seven real-world graph datasets compared to existing SOTAs.

strengths:
1.  CTGC effectively models long-range dependencies in graph clustering, overcoming the limitations of traditional GNN methods that primarily focus on local node aggregation.

2. The paper includes numerous experiments that validate the effectiveness of the proposed method, providing strong empirical support for its claims.

3. The article is well-structured, making it easy to read and follow, which enhances the understanding of the proposed methods and results.

weaknesses:
The paper states, “To the best of our knowledge, we are the first to introduce a transformer for graph clustering to alleviate long-range dependency modeling.” However, existing studies have already applied transformers in graph clustering, which questions the novelty of this approach. For example[1],[2]. Including these recent works in the baseline would enhance the credibility of the claims.

[1] Li Y, Li L, Liu X, et al. Influence maximization for heterogeneous networks based on self-supervised clustered heterogeneous graph transformer[J]. Pattern Recognition, 2024, 154: 110595.

[2] Weng W, Hou F, Gong S, et al. Attribute graph clustering via transformer and graph attention autoencoder[J].

questions:
What is the time complexity of the CTGC algorithm, particularly for the momentum cluster-aware attention and cluster-aware regularization mechanisms? How does it compare to traditional clustering methods?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730653785103

thread_type:
official_review

<thread_object>
creator: reviewer_vxmc

<content>
summary:
Graph clustering faces challenges with long-range dependencies and suboptimal embeddings due to a two-stage approach. CTGC addresses these by integrating transformers for better dependency modeling and introducing mechanisms to enhance task awareness, leading to improved clustering quality on real-world datasets.

strengths:
1. Nice presentation with clear figures.

2. Technique sound. Lots of experiments are provided.

3. The paper is well-written and organized.

weaknesses:
1. From my idea, the proposed method seems to integrate Transformer frameworks in node-level clustering, which lacks novelty. Maybe you should emphasize the importance of why you use transformer instead of other frameworks. In other words, the motivation should be more clear.

2. As for the long-range dependencies, I would recommend the authors add case studies to intuitively show that the Transformer framework indeed helps with it, rather than only relying on the performance.

3. Maybe larger datasets should be used for comparison.

4. If possible, I would like to see the performances of the proposed method on graph-level clustering.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732189652797

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Evaluation on Large-Scale Datasets

comment:
To comprehensively evaluate the effectiveness of our proposed method, we conducted validation on two large-scale datasets, ogbn-arxiv and ogbn-products. The experimental results, presented in Table 1, include comparative performance metrics against baseline methods cited from [1]. As shown in the table, our method consistently outperforms existing GNN-based approaches, even when applied to larger datasets, thereby demonstrating its scalability and superior efficacy.

Table 1: Clustering performance of CTGC and five baselines on larger graph datasets. The bold and underlined scores indicate the best and second best results respectively.

|    Dataset    | Metric | KMeans | Node2Vec |       S$^3$GC       | DMoN  |         MAGI         |      Ours      |
| :-----------: | :----: | :----: | :------: | :-------------------: | ----- | :-------------------: | :-------------: |
|  ogbn-arxiv  |  ACC  | 18.10 |  29.00  |         35.00         | 25.00 | $\underline{38.80}$ | **41.09** |
|              |  NMI  | 22.10 |  40.60  |         46.30         | 35.60 | $\underline{46.90}$ | **47.58** |
|              |  ARI  |  7.40  |  19.00  |         27.00         | 12.70 | $\underline{31.00}$ | **34.36** |
|              |   F1   | 12.90 |  22.00  |         23.00         | 19.00 | $\underline{26.60}$ | **28.52** |
| ogbn-products |  ACC  | 20.00 |  35.70  |         40.20         | 30.40 | $\underline{42.50}$ | **43.20** |
|              |  NMI  | 27.30 |  48.90  |         53.60         | 42.80 | $\underline{55.10}$ | **55.96** |
|              |  ARI  |  8.20  |  17.00  | $\underline{23.00}$ | 13.90 |         21.50         | **24.80** |
|              |   F1   | 12.40 |  24.70  |         25.00         | 21.00 | $\underline{27.60}$ | **28.52** |

---

[1] Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspective
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper focuses on two issues in graph clustering: long-range dependencies capturing difficulty and two-stage clustering. It utilizes transformer as crucial graph encoder, and designs momentum cluster-aware attention and cluster-aware regularization to enhance the encoder task-awareness. In momentum cluster-aware attention, the clustering results are utilized to guide the node embedding production via cluster-aware queries. In cluster-aware regularization, the cluster information is fused into bordering nodes by minimizing the overlap between clusters while maximizing the cluster completeness.   Experimental results validate the effectiveness of proposed scheme.  


After rebuttal, all reviewers are still negative about this paper. Especially, the importance of why utilizing transformer rather than other frameworks is not clear. Existing studies have already applied transformers in graph clustering, and the proposed method is very similar to existing works. So, the novelty of proposed approach is limited. The mechanism of momentum cluster-aware attention is not elaborated. 
The authors are encouraged to further perfect this manuscript according to relevant comments.