- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes Cluster Attention (CLATT), a graph learning mechanism that allows nodes within the same cluster to exchange information through attention. By using graph clustering as a preprocessing step, CLATT aims to capture longer-range dependencies while preserving structural information from the graph. The method can be integrated into both message-passing neural networks and Graph Transformers. The authors consider four clustering algorithms and select suitable clusterings for different datasets. Experiments on 12 graph datasets show that adding CLATT generally improves the performance of different graph learning models.
Critical strengths
- The paper addresses an important problem in graph learning: how to capture longer-range dependencies while retaining useful structural information. Using graph clusters to define the attention scope provides a reasonable middle ground between local message passing and global attention.
- CLATT can be integrated into different graph learning architectures without replacing their original message-passing or attention mechanisms. The experiments include GCN, GraphSAGE, LGT, and two Global Graph Transformer variants, showing that the method can be applied to different types of models.
- The experimental evaluation covers 12 datasets with different graph structures and learning tasks, including both homophilous and heterophilous graphs. This provides relatively broad evidence for the usefulness of cluster attention.
- The paper considers several graph clustering algorithms and examines the attention distances learned by different models. These analyses help explain how cluster attention differs from local and global attention in terms of the nodes that can interact.
Critical weaknesses
1.The core idea of CLATT is to partition graph nodes using existing graph clustering algorithms, perform standard multi-head self-attention within each cluster, and then combine the outputs with the original message passing or global attention. Although this design has a clear intuitive motivation, its main components are based on existing techniques, including community detection, grouped self-attention, and multi-branch feature fusion. The authors should explain in more detail how the proposed design differs from existing sparse attention, grouped attention, and hierarchical graph modeling methods, and clarify where its advantages come from and which components contribute to them. 2.The paper claims that modern graph clustering algorithms run much faster than GNN training, making the clustering preprocessing time negligible. However, CLATT may use multiple clustering algorithms simultaneously, and the computational costs of different clustering algorithms can vary significantly on large-scale graphs. Does this claim still hold in such cases? The authors should provide a more detailed explanation or additional experimental evidence to support it. 3.In Table 2, the paper uses underlining to indicate statistically significant performance differences, but does not sufficiently explain the statistical test used, the significance level, or how the test was conducted. Reporting only the mean and standard deviation is also insufficient to reproduce the significance testing results. The authors should clarify these details to improve the transparency and reproducibility of the experiments. 4.The experiments mainly evaluate CLATT by comparing the original GCN, GraphSAGE, LGT, and GGT models with their CLATT-augmented versions. However, the augmented models not only change the range of information exchange between nodes but also introduce additional query, key, and value projections, increasing the number of model parameters and the computational cost. Therefore, it is difficult to determine whether the performance improvements come from the increased model capacity or from the cluster attention mechanism itself.
Questions for authors
1.The paper considers four graph clustering algorithms, but the main experiments do not include a random grouping baseline with matched cluster sizes. I suggest adding random grouping and simple structure-based grouping baselines with matched cluster sizes to better evaluate the independent contribution of graph community structure to the final performance. 2.The paper treats the selection of clustering algorithms as a dataset-level hyperparameter, but in practice, it only uses LGT to select the clustering algorithms and assumes that the selected clusterings transfer well across different models, without providing experiments to verify this assumption. Since different models have different receptive fields, attention mechanisms, and abilities to capture graph structure, the clustering combination that works best for LGT may not necessarily be the best choice for other architectures. I suggest selecting clustering algorithms separately for different models on at least a few representative datasets and comparing model-specific selection with shared selection to verify whether this assumption is reasonable.
5 comments
Response to Reviewer vbGR (Part 2)
2.The paper claims that modern graph clustering algorithms run much faster than GNN training, making the clustering preprocessing time negligible. However, CLATT may use multiple clustering algorithms simultaneously, and the computational costs of different clustering algorithms can vary significantly on large-scale graphs. Does this claim still hold in such cases? The authors should provide a more detailed explanation or additional experimental evidence to support it.
Thank you for this question. Indeed, the speed of different clustering algorithms differs significantly, however, as we discuss in Section 4, for our work we have selected 4 algorithms that run very fast even on large graphs (specifically, they are all almost linear in graph size). Empirically, our largest graph is pokec-regions with 1.5+M nodes and 22+M edges, and each of the considered algorithms takes no more than 2 minutes to cluster this graph (with all 4 algorithms together finishing in less than 5 minutes), which is quite negligible compared to each model training run which takes approximately 30 minutes (and we perform many training runs for hyperparameter selection, while clustering is performed once). We will add the time measurements to the updated version of our paper.
3.In Table 2, the paper uses underlining to indicate statistically significant performance differences, but does not sufficiently explain the statistical test used, the significance level, or how the test was conducted. Reporting only the mean and standard deviation is also insufficient to reproduce the significance testing results. The authors should clarify these details to improve the transparency and reproducibility of the experiments.
Thank you for pointing this out. All experiments were repeated 10 times with different random seeds, the t-test with a significance level of 5% was used. We will clarify this is the updated version of our paper.
4.The experiments mainly evaluate CLATT by comparing the original GCN, GraphSAGE, LGT, and GGT models with their CLATT-augmented versions. However, the augmented models not only change the range of information exchange between nodes but also introduce additional query, key, and value projections, increasing the number of model parameters and the computational cost. Therefore, it is difficult to determine whether the performance improvements come from the increased model capacity or from the cluster attention mechanism itself.
Indeed, our CLATT mechanism introduces additional model parameters. However, for each model (both CLATT and non-CLATT versions) extensive hyperparameter tuning was performed, including sweeps across the number of layers and the hidden dimension, so each model could increase its parameter count if it is useful for the task, but the best versions of all models (by the validation set performance) all turned out to be smaller than the maximum size allowed in our sweeps (and in fact, optimal CLATT versions of models are typically less deep than the corresponding non-CLATT versions, which suggests that the inclusion of longer-range interactions by CLATT allows decreasing the number of message passing layers).
Response to Reviewer vbGR (Part 3)
1.The paper considers four graph clustering algorithms, but the main experiments do not include a random grouping baseline with matched cluster sizes. I suggest adding random grouping and simple structure-based grouping baselines with matched cluster sizes to better evaluate the independent contribution of graph community structure to the final performance.
This is indeed a good suggestion. To verify that the cluster structure is what makes CLATT perform well and that simple random groupings are not enough, we conducted experiments with randomized clusters of the same size as you suggest. Further, besides completely randomized clusters, we also tried partially randomized clusters, where for each cluster a certain percentage of nodes is taken from the original cluster, and the remaining nodes are assigned randomly. Due to a large number of experiments, we limit this investigation to our strongest model (LGT) and 5 datasets (please let us know if you would like to see more models or datasets, we can add them later). We provide the experimental results in the table below. No-CLATT stands for our baseline – LGT without CLATT. CLATT-random-X% stands for using CLATT with X% of nodes being assigned to clusters randomly, i.e. CLATT-random-0% uses the original clustering with no randomness, and CLATT-random-100% uses a completely random clustering, while the levels of randomness of 10%, 25%, and 50% lie between these two extremes.
| dataset | city-roads-M | lastfm-asia | amazon-ratings-5core | hm-categories | |
|---|---|---|---|---|---|
| No-CLATT | 58.05 | 83.97 | 92.17 | 51.26 | 69.25 |
| CLATT-random-100% | 58.02 | 83.91 | 92.20 | 51.10 | 69.31 |
| CLATT-random-50% | 58.00 | 83.94 | 92.20 | 51.27 | 69.23 |
| CLATT-random-25% | 58.40 | 84.12 | 92.48 | 52.35 | 69.53 |
| CLATT-random-10% | 59.71 | 84.41 | 92.60 | 53.08 | 69.92 |
| CLATT-random-0% (orig) | 60.26 | 84.55 | 92.71 | 53.70 | 70.22 |
We can see that the model with 100% of randomized cluster assignments performs on the level of the No-CLATT baseline, i.e., the model likely learns to ignore the CLATT mechanism since it provides no useful information when clusters are completely randomized. CLATT with 50% of noise also performs similar to the baseline, suggesting that such a randomness level is still too high to extract useful information. CLATT with 25% of randomness performs better than the baseline, while CLATT with 10% of randomness performs close to the original CLATT, suggesting that the CLATT mechanism can withstand low randomness levels and retain most of its performance benefits. Overall, we can see that the cluster structure is what explains the practical effectiveness of CLATT, as the larger parts of the clusters get randomized, the worse performance CLATT achieves, and CLATT with completely randomized clusters does not outperform the baseline model without CLATT.
Response to Reviewer vbGR (Part 1)
Dear reviewer, thank you for your positive assessment and valuable feedback. We address your concerns below.
Indeed, our method builds on existing techniques, however, we believe the specific way we combine them is novel and very different from prior works (and is empirically very useful, as our experiments show). While there are prior works that use some form of sparse attention in Graph Transformers [1], to our knowledge none of them use graph clustering to specify which node pairs can and cannot attend to each other, which is our key contribution. Other prior works use graph pooling and/or hierarchical modeling to iteratively merge nodes into supernodes, which essentially performs a form of learnable node clustering [2-5]. However, these approaches lose information about individual nodes when merging them, and thus cannot be applied to node-level tasks (which are the focus of our work), and are rather applied to graph-level tasks like molecule classification. Further, this works allow interactions between supernodes (which represent node clusters), which is inter-cluster interaction, while our method allows interactions between nodes within the same cluster, which is intra-cluster interaction. Moreover, these works learn to perform node clustering and the target task simultaneously, which significantly complicates the training pipeline, while our method relies on off-the-shelf node clustering methods as a cheap preprocessing step and thus not only simplifies training, but also enables the reuse of decades of prior research on classic community detection algorithms. Finally, some works use attention-based models to solve the task of node clustering [6, 7]. This is very different from our work, which uses node clustering as a preprocessing step to restrict attention and solve standard node-property prediction tasks. Overall, while there are some prior works bridging sparse attention and Graph Transformers or graph clustering and GNNs, none of them use classic graph clustering to restrict attention between nodes in the graph, which is the key method of our work and is our novel approach. We will extend the Related Work section to discuss these papers and how our method differs from them.
[1] NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (NeurIPS 2022)
[2] Hierarchical Transformer for Scalable Graph Learning (arxiv preprint, 2023)
[3] Hierarchical Graph Pooling with Structure Learning (arxiv preprint, 2023)
[4] Hierarchical message-passing graph neural networks (DMKD 2023)
[5] Hierarchical Attention-based Graph Neural Network with Relevance-driven Pruning (arxiv preprint, 2026)
[6] Transforming Graphs for Enhanced Attribute Clustering: An Innovative Graph Transformer-Based Method (arxiv preprint, 2023)
[7] Attention-based Graph Clustering Network with Dual Information Interaction (Knowledge-Based Systems, 2025)