HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity

Could please acknowledge and respond to the rebuttal.

Our work generalizes a spectral clustering framework to adapt to heterophilous and asymmetrical graphs, with a theoretical foundation rooted in a primal-dual framework. This approach is markedly different from existing work.

As we mentioned in our responses to other reviewers, we will include additional comparisons with more general representation learning methods for heterophilous graphs in our final paper. However, the most relevant comparison remains with MUSE, the current state-of-the-art for purely unsupervised node clustering in heterophilous graphs. Contrary to your statement, MUSE does not specifically focus on multi-view graphs; rather, it constructs two views as part of its approach.

Could please acknowledge and respond to the rebuttal.

Q1: Theoretical Motivation

The motivation behind HeNCler is to propose a spectral-based method, as such methods have proven theoretical and empirical success in node clustering tasks. Rather than specifically targeting heterophily, we alleviate the homophily assumption inherent in many spectral-based methods. By learning a new similarity graph, HeNCler can adapt to heterophilous settings.

Q2: Dual formulation

The dual formulation is an essential part of our theoretical framework and underpins the model’s motivation. Section 3.1 introduces the new similarity graph and proves the equivalence of the primal formulation to the spectral clustering objective. This is critical to HeNCler’s soundness and demonstrates that the wKSVD-based objective is not arbitrary but deeply tied to spectral clustering principles. We argue that this part of the paper is highly relevant to the soundness of our method and its theoretical understanding.

Q3: Additional Comparisons

We compare HeNCler with MUSE, the current state-of-the-art for purely unsupervised node clustering in heterophilous graphs. In response to your feedback, we will include comparisons with additional methods, based on the references provided by the other reviewers. These experiments will help contextualize HeNCler’s performance among broader heterophilous representation learning approaches.

Could please acknowledge and respond to the rebuttal.

Thank you for pointing out the need for broader literature coverage. We will revise the Related Work section to include additional references on heterophilous graph representation learning, such as heterophilous node classification, to provide a more comprehensive context for our contributions. We will better point out the unique challenges of purely unsupervised heterophilous node clustering and the limitations of these generally supervised methods.

Q1: Performance on Directed vs. Undirected Graphs

The core motivation behind our asymmetrical model is to handle both directed and undirected datasets, as opposed to existing spectral-based methods that rely heavily on symmetry. Our analysis of Table 7 indicates that the asymmetry introduced by HeNCler significantly improves performance on directed datasets. Specifically, we observe a noticeable gap between the performance of the 'Undirected' baseline and HeNCler, which supports the effectiveness of our design for directed graphs.

For undirected graphs, the performance improvements are less pronounced. This aligns with our hypothesis that latent asymmetries are less critical for these datasets. However, HeNCler still achieves slight performance gains for undirected graphs, suggesting that it effectively captures subtle asymmetries that may exist even in nominally undirected data.

The larger performance gains in directed graphs stem from HeNCler’s ability to simultaneously relax the homophily and symmetry assumptions. In contrast, the symmetry assumption is naturally satisfied in undirected datasets, limiting the potential impact of HeNCler’s asymmetry.

Q2: Low NMI Scores and Class Imbalance

We choose to use supervised metrics such as F1 and NMI, as they are commonly used in the literature. However, the assumption that good clustering should align with the given labels may not always hold. Determining the most suitable metric for clustering remains an open problem and is beyond the scope of this paper. Nevertheless, we observe that NMI tends to be particularly low for datasets with significant class imbalance. Despite these challenges, the relative improvements achieved by HeNCler demonstrate its efficacy under such conditions

Weakness 1

Our literature review focuses on unsupervised clustering and representation learning techniques specifically designed for heterophilous graphs. While graph rewiring techniques, such as those referenced (e.g., [2]), are relevant, they are predominantly introduced in a supervised setting. As our method targets an unsupervised scenario, it diverges from these approaches in both objectives and methodology. We will clarify this distinction in our final paper.

Weakness 2

We agree that methods like [4] and [5] are valuable references; however, these approaches are designed to enhance homophily in already homophilous graphs, which contrasts with our aim of effectively addressing heterophilous graphs. Nonetheless, we will incorporate these related works into our literature review to provide a comprehensive view of the landscape and clearly articulate how our approach differs in terms of both goals and methodology.

Weakness 1 + 2

We appreciate your suggestion and will integrate a more extensive discussion of these related works into our literature review. Additionally, we will expand our baseline comparisons in the final version of the paper to include the most relevant and best performing methods, ensuring a robust evaluation of our approach.

Weakness 3

We appreciate the request for further elaboration on our ablation results. As shown in Tables 4 and 7, all loss components contribute positively to HeNCler's overall performance. For directed datasets, model asymmetry emerges as a significant contributor, while for undirected datasets, the reconstruction loss, asymmetry, and wKSVD loss contribute roughly equally. We will provide a more detailed discussion of these findings in the final version to offer deeper insights into the contributions of individual components.

Weakness 4

We understand the importance of evaluating our method on larger datasets. Unfortunately, as noted, there are currently no large-scale datasets in the literature that are intrinsically heterophilous. The ogbn-arxiv dataset is inherently homophilous, and the arxiv-year dataset (Lim et al., NeurIPS 2021) simply reassigns labels based on publication years, which lacks interpretability in an unsupervised setting. Nonetheless, we will include experiments on the arxiv-year dataset to assess the computational scalability of our method. These results will provide insights into the computational challenges and scalability of HeNCler, even if the heterophily aspect is not fully represented.