HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity

Authors: Sonny Achten, Francesco Tonin, Volkan Cevher, Johan Suykens
Primary area: learning on graphs and other geometries & topologies
Keywords: Heterophily, Node Clustering, Singular Value Decomposition

Abstract:
Clustering nodes in heterophilous graphs is challenging as traditional methods assume that effective clustering is characterized by high intra-cluster and low inter-cluster connectivity. To address this, we introduce HeNCler—a novel approach for **He**terophilous **N**ode **Cl**ust**er**ing. 
HeNCler  *learns* a similarity graph by optimizing a clustering-specific objective based on weighted kernel singular value decomposition.
Our approach enables spectral clustering on an *asymmetric* similarity graph, providing flexibility for both directed and undirected graphs. By solving the primal problem directly, our method overcomes the computational difficulties of traditional adjacency partitioning-based approaches. Experimental results show that HeNCler significantly improves node clustering performance in heterophilous graph settings, highlighting the advantage of its asymmetric graph-learning framework.

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

Reviews and discussion:
<thread>
creation date:
1729989781015

thread_type:
official_review

<thread_object>
creator: reviewer_avnn

<content>
summary:
HeNCler employs weighted kernel singular value decomposition (wKSVD) to learn an induced asymmetric similarity graph, avoiding reliance on homophily and enabling more effective clustering in heterophilous settings.

strengths:
1.The motivation is clear. 
2. The proposed method is sound to me.
3. The experimental results show the effectiveness of the proposed method.

weaknesses:
1. The technique contribution is limited. The main contribution is the construction of asymmetric similarity, while the other method part is a combination of existing components.
2. The authors ignore many existing works, like [1] and [2].
3. The comparison methods are not enough to show their effectiveness. For example, the newest baselines S3GC and MUSE are from 2022 and 2023 respectively. Besides, S3GC focuses on homophilic and large graphs and MUSE focuses on multi-view graphs.
4. The application is limited. This work seems to focus only on heterophyllous graphs. From Table 6, it achieves poor performance on homophilous graphs. However, the homophily is unknown without the labeled data.

[1] Dong, Y., Dupty, M. H., Deng, L., Liu, Z., Goh, Y. L., & Lee, W. S. (2024). Differentiable Cluster Graph Neural Network. arXiv preprint arXiv:2405.16185.
[2] Jiang, Mengying, et al. "GCN-SL: Graph Convolutional Networks with Structure Learning for Graphs under Heterophily." arXiv preprint arXiv:2105.13795 (2021).

questions:
1. There are a number of works that performs clustering on heterophilic graph, which should be cited or compared. To name a few, [1-4]
2. In fact, some existing methods also learn new similarity matrices from data for heterophilic graph [1-2], which share a similar idea with the proposed method.  


Refs:
[1] Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering, ICML 2023.
[2] Robust Graph Structure Learning under Heterophily, arXiv 2024.
[3] Homophily-enhanced structure learning for graph clustering. Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 2023.
[4] Homophily-Related: Adaptive Hybrid Graph Filter for Multi-View Graph Clustering. AAAI 2024.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730472570619

thread_type:
official_review

<thread_object>
creator: reviewer_zv7t

<content>
summary:
The paper introduces HeNCler, a novel approach for clustering nodes in heterophilous graphs. Traditional clustering methods often assume homophily, where nodes with similar labels are more likely to be connected. HeNCler addresses this challenge by learning a similarity graph through a clustering-specific objective based on weighted kernel singular value decomposition. The authors claim that HeNCler significantly improves node clustering performance in heterophilous graph settings, highlighting the advantage of its asymmetric graph-learning framework.

strengths:
1. The paper addresses a significant and under-explored problem in the field of node clustering for heterophilous graphs. This is a practical and relevant issue, as many real-world graphs exhibit heterophily.
2. Leveraging weighted kernel singular value decomposition to learn a similarity graph for deep node clustering appears to be novel.
3. The whole objective combines the proposed wKSVD loss with a graph autoencoder. Ablation studies suggest that both components contribute to the overall performance of HeNCler.

weaknesses:
1. The relationship between the proposed wKSVD loss and the characteristics of heterophilous graphs is unclear, which limits the soundness of the method. To my understanding, the most important part of wKSVD is its asymmetric similarity measure, which applies different projections to the pairs. However, it is a pretty trivial operation and this paper does not provide a in-depth explanation of how it helps in the context of heterophilous graphs.
2. While the paper claims significant performance improvements, it does not compare with strong baselines or state-of-the-art methods for heterophilous graphs. There are various unsupervised heterophilous graph representation learning methods that could serve as competitive baselines, but the only competitor designed for heterophilous graphs is MUSE.
3. I don't agree with the claimed computational complexity improvement of HeNCler. According to _Optimizer, constraints, and cluster assignment_, cluster assignments are obtained by KMeans clustering on the final embeddings, so you need to include the complexity of KMenas in the overall complexity analysis.
4. The wKSVD-loss is based on the primal formulation of wKSVD, so it's unclear how most of Section 3.1 relates to the proposed method.

questions:
1. Please provide more theoretical evidence to strengthen the effectiveness of wKSVD for heterophilous graphs.
2. Consider removing the dual formulation if it's unrelated to the proposed method.
3. Please add additional experiments comparing HeNCler with state-of-the-art methods for heterophilous graph clustering or representation learning.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730648242016

thread_type:
official_review

<thread_object>
creator: reviewer_8wdq

<content>
summary:
Focusing on node clustering on heterophilous graph, this paper introduces an RMK-based framework for learning an asymmetric similarity. By incorporating wKSVD framework into graph clustering with two reconstruction loss, HeCler can optimize a bipartite graph with theoretical interpretability.  The experimental results and empirical analysis can demonstrate the effectiveness.

strengths:
1. Novelty: Although the overall idea of learning a similarity matrix for heterophilous graph learning is not new, this paper proposed an interesting framework by observing the advantage of RMK framework.
2. The theoretical support brings interpretability to this framework.
3. The discussion could empirically interpret how the method works.

weaknesses:
1. One weakness is the lack of literature on heterophyllous graph learning. The authors only list three works for heterophilous node clustering. Other methods for heterophyllous graph representation learning are suggested to be included on top of node clustering (such as heterophilous node classification, multi-view heterophilous node clustering, etc).

2. Analysis about the experimental results are somehow insufficient. The experimental results on undirected graphs seems not as good as directed graphs, such as Chamelon, squirrel. The authors should analyze this. In addition, the NMI in these datasets are very low (such as 9.67, 0.06, 6.73), which phenomenon indicates that the model even does not learn any clustering information. How to explain this?

questions:
1. Can you provide a detailed analysis of why your method performs differently on directed vs undirected graphs, particularly for datasets like Chameleon and Squirrel?
2. The NMI scores for some datasets (e.g. 9.67, 0.06, 6.73) are very low. What might these low scores indicate about the model's performance or limitations on these particular datasets? Are there any insights to be gained from comparing these results to other methods or baseline performance on these challenging datasets?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730818975493

thread_type:
official_review

<thread_object>
creator: reviewer_9rsz

<content>
summary:
This paper proposes a kernel spectral biclustering framework to learn an induced asymmetric similarity graph suited for node clustering of heterophilous graphs.

strengths:
1. The proposed method is easy to understand.
2. It addresses an important problem.

weaknesses:
1. The innovation seems limited, as graph rewiring is already a common approach to tackle heterophilous graphs, as seen in [1] and [2]. However, it would be beneficial for the authors to clarify how their kernel spectral biclustering approach meaningfully differs from existing graph rewiring techniques. Specifically, a comparison of how these methods address heterophily and clustering effectiveness would strengthen the argument for the novelty of their approach. By expanding on the specific advantages or unique contributions of kernel spectral biclustering over rewiring methods, the authors could better situate their work within the current landscape.

2. While the proposed method achieves the best performance in 11 out of 16 cases, the choice of only five baselines may limit the comprehensiveness of this evaluation. I suggest including additional baselines that are well-regarded in heterophilous graph clustering to provide a more robust comparison, like [4][5]. Additionally, reporting on the statistical significance of the observed improvements would help clarify whether these performance gains are practically meaningful or consistent across datasets.

3. More detailed analysis of Table 4 would improve the discussion of the results. Specifically, it would be helpful for the authors to discuss the relative impact of the different components (e.g., the kernel spectral biclustering loss vs. reconstruction losses) in achieving the overall performance. Additionally, an investigation into any observed trends or dependencies among these components would provide insights into the roles they play in model performance.

4. I recommend adding larger datasets, such as Ogbn-arxiv [3], to further validate the proposed method. Testing on larger datasets could help assess the scalability and robustness of the approach and reveal any computational challenges that might arise when handling high-dimensional data. This addition could provide a more comprehensive evaluation and help demonstrate the method's potential for broader applications.

[1] Jiang, W., Gao, X., Xu, G., Chen, T., & Yin, H. (2024, May). Challenging Low Homophily in Social Recommendation. In Proceedings of the ACM on Web Conference 2024 (pp. 3476-3484).
[2] Zheng, Y., Zhang, H., Lee, V., Zheng, Y., Wang, X., & Pan, S. (2023, July). Finding the missing-half: Graph complementary learning for homophily-prone and heterophily-prone graphs. In International Conference on Machine Learning (pp. 42492-42505). PMLR.
[3] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., ... & Leskovec, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33, 22118-22133.
[4] Li W Z, Wang C D, Xiong H, et al. Homogcl: Rethinking homophily in graph contrastive learning[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 1341-1352.
[5] Gu M, Yang G, Zhou S, et al. Homophily-enhanced structure learning for graph clustering[C]//Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 2023: 577-586.

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

</thread>


Metareview:
metareview:
Clustering nodes in graphs where relationships are not symmetric (heterophilous graphs) is challenging for traditional methods that rely on high similarity within clusters. The proposed method, uses a technique to capture asymmetric relationships.

Strengths: 

See comments by the reviewers.

Weaknesses: 

1) limited innovation 
2) More comparisons to baselines are needed
3) More comparisons to larger datasets
4) More analysis on comparisons to undirected graphs.
5) Better literature review.

The rebuttal didn't seem to address the concerns of the reviewers.
Overall, the paper needs major revision and cannot be accepted at this stage.