HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity

## Abstract

Abstract Clustering nodes in heterophilous graphs presents unique challenges due to the asymmetric relationships often overlooked by traditional methods, which moreover assume that good clustering corresponds to high intra-cluster and low inter-cluster connectivity. To address these issues, we introduce HeNCler —a novel approach for He terophilous N ode Cl ust er ing.
Our method begins by defining a weighted kernel singular value decomposition to create an asymmetric similarity graph, applicable to both directed and undirected graphs. We further establish that the dual problem of this formulation aligns with asymmetric kernel spectral clustering, interpreting learned graph similarities without relying on homophily. We demonstrate the ability to solve the primal problem directly, circumventing the computational difficulties of the dual approach. Experimental evidence confirms that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.

## 1 Introduction

Graph neural networks (GNNs) have substantially advanced machine learning applications to graph-structured data by effectively propagating node attributes end-to-end. Typically, GNNs rely on the assumption of homophily, where nodes with similar labels are more likely to be connected [, ].

The homophily assumption holds true in contexts such as social networks and citation graphs, where models like GCN [], GIN [], and GraphSAGE [] excel at tasks like node classification and graph prediction. However, this is not the case in heterophilous datasets, such as web page and transaction networks, where edges often link nodes with differing labels.
Models such as GAT [] and various graph transformers [, ] show improved performance on these datasets. With their attention mechanisms that learns edge importances, they reduce the dependency on the homophily.

In this setting, our work specifically addresses unsupervised attributed node clustering tasks, which require models to function without any label information during training. Such tasks necessitate entirely unsupervised or self-supervised learning approaches.

For instance, models like GALA [] and ARVGA [] leverage auto-encoder architectures for node representation but lack a direct clustering objective, thereby not enhancing cluster-ability. S^3GC [] employs a self-supervised technique assuming that proximity in graphs implies similarity, a form of assumed homophily based on random walk co-occurrences.

In addition, MinCutPool [] and DMoN [] introduce unsupervised losses linked to graph structure, with theoretical ties to spectral clustering and graph modularity, respectively. These methods, however, are restricted to undirected graphs and presuppose that effective clustering correlates with high intra-cluster and low inter-cluster connectivities—a premise often invalid in heterophilous graphs.

To this end, we propose to
integrate both graph structure and node features to effectively enhance cluster-ability, rather than relying solely on the graph’s structural properties. In particular, we contend that a performant node clustering model for heterophilous attributed graphs is missing in literature, which HeNCler addresses. Table 1 provides an overview on the limitations of existing state-of-the-art methods.
We observe that existing node clustering models for attributed graphs assume homophily, and that it is unclear how to effectively combine node attributes with graph structure information to obtain good cluster-able representations for heterophilous graphs, especially when they are directed.

Contributions:   Our contributions in this work can be summarized as follows:

- •
We propose HeNCler—a kernel spectral biclustering framework that formulates a clustering objective for a *directed* and *learned* similarity graph.
- •
We introduce a primal-dual framework for a generic weighted kernel singular value decomposition (wKSVD) model.
- •
We show that the dual wKSVD formulation allows for biclustering of bipartite/asymmetric graphs, while we employ a computationally feasible implementation in the primal wKSVD formulation.
- •
We further generalize our approach with trainable feature mappings, using node and edge decoders, such that the similarity matrix to cluster is learned.
- •
We train HeNCler in the primal setting and demonstrate its superior performance on the node clustering task for heterophilous attributed graphs. Our implementation is available in supplementary materials.

**Table 1: Qualitative comparison of HeNCler with several baselines. In the table, $|\mathcal{V}|$, $|\mathcal{B}|$, and $|\mathcal{E}|$ denote the total number of nodes, the mini-batch size, and the number of edges respectively.**
|  | baselines | ours |  |  |
| --- | --- | --- | --- | --- |
|  | MinCutPool | DMoN | S^3GC | HeNCler |
| Can handle heterophily | ✗ | ✗ | ✗ | ✓ |
| Directed graphs | ✗ | ✗ | ✓ | ✓ |
| Space complexity | $\mathcal{O}(|\mathcal{V}|^{2})$ | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | $\mathcal{O}(|\mathcal{B}|)$ | $\mathcal{O}(|\mathcal{B}|)$ |
| Time complexity | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | $\mathcal{O}(|\mathcal{V}|)$ | $\mathcal{O}(|\mathcal{V}|)$ |

## 2 Preliminaries and related work

We use lowercase symbols (e.g., $x$) for scalars, lowercase bold (e.g., $\mathbf{x}$) for vectors and uppercase bold (e.g., $\mathbf{X}$) for matrices. A single entry of a matrix is represented by $X_{ij}$. $\phi(\cdot)$ denotes a mapping and $\bm{\phi}_{v}=\phi(\mathbf{x}_{v})$ represents the mapping of node $v$ in the induced feature space.
We represent a graph $\mathcal{G}$ by its vertices (i.e., nodes) $\mathcal{V}$ and edges $\mathcal{E}$, $\mathcal{G}=(\mathcal{V},\mathcal{E})$, or by its node feature matrix and adjacency matrix $\mathcal{G}=(\mathbf{X},\mathbf{A})$. For a bipartite graph, we have $\mathcal{G}=(\mathcal{I},\mathcal{J},\mathcal{E})$ or $\mathcal{G}=(\mathbf{X}_{\mathcal{I}},\mathbf{X}_{\mathcal{J}},\mathbf{S})$ where $S_{ij}$ is the edge weight between nodes $i\in\mathcal{I}$ and $j\in\mathcal{J}$. Note that $\mathbf{S}$ is generally asymmetric and rectangular, and that the adjacency matrix of the bipartite graph is given by $\mathbf{A}=$ $\left[\begin{smallmatrix}\mathbf{0}&\mathbf{S}\\
\mathbf{S}^{\top}&\mathbf{0}\end{smallmatrix}\right]$ .

Graph transformers   [] are based on the same idea as Transformers [], i.e., to learn relational dependencies through an attention mechanism, rather than assuming these dependencies are only encoded in a given structure (a line structure for sentences or more general graphs for graph transformers). A graph transformer can therefore learn long-range dependencies in a single layer, which is particularly interesting for heterophilous graphs. To incorporate the structure, both methods use some kind of positional encoding and the attention mechanism is asymmetric.

Kernel singular value decomposition   (KSVD) [] sets up a primal-dual framework, based on Lagrange duality, that formulates a variational principle in the primal formulation that corresponds to the matrix singular value decomposition (SVD) in the dual. By employing non-linear feature mappings or asymmetric kernel functions, this framework allows for non-linear extensions of the SVD problem. The KSVD framework can be applied on data structures such as row and column features, directed graphs, and/or can exploit asymmetric similarity information such as conditional probabilities []. Interestingly, KSVD often outperforms the similar though symmetric kernel principle component analysis model on tasks where the asymmetry is not immediately apparent []. A different connection is shown in Primal-Attention [], where the authors demonstrate the relation between canonical self-attention, which is asymmetric, and KSVD. They show how to gain computational efficiency by considering a primal equivalent of the attention mechanism.

Spectral clustering   generalizations have been proposed in many settings. Spectral graph biclustering [] formulates the spectral clustering problem of a bipartite graph $\mathcal{G}=(\mathcal{I},\mathcal{J},\mathbf{S})$ and shows the equivalence with the SVD of the normalized matrix $\mathbf{S}_{n}=\mathbf{D}_{1}^{-1/2}\mathbf{S}\mathbf{D}_{2}^{-1/2}$, where $D_{1,ii}=\sum_{j}S_{ij}$ and $D_{2,jj}=\sum_{i}S_{ij}$. Cluster assignments for nodes $\mathcal{I}$ and nodes $\mathcal{J}$ can be inferred from the left and right singular vectors respectively. Further, kernel spectral clustering (KSC) [] proposes a weighted kernel principal component analysis in which the dual formulation corresponds to the random walks interpretation of the spectral clustering problem. KSC and the aforementioned spectral biclustering formulation lack asymmetry and a primal formulation respectively, which are limitations that our model will address.

Restricted kernel machines   (RKM) [] possess primal and dual model formulations, based on the concept of conjugate feature duality. It is an energy-based framework for (deep) kernel machines, that shows relations with least-squares support vector machines [] and restricted Boltzmann machines []. The RKM framework encompasses many model classes, including classification, regression, kernel principal component analysis and KSVD, and allows for deep kernel learning [] and deep kernel learning on graphs []. One possibility to represent the feature maps in RKMs is by means of deep neural networks, e.g., for unsupervised representation learning [, ]. RKM models can work in either primal or dual setting, and with decomposition or gradient based algorithms [].

## 3 Method

Model motivation
Inspired by graph transformers, we employ a KSVD setting to learn long range relational dependencies for heterophilous graphs, where a double feature map that uses node features and positional encodings yields an asymmetric matrix. Rather than utilizing this matrix as an attention mechanism, we simply consider it to be a learned similarity matrix. We further adapt the KSVD setting to a weighted KSVD setting, as this on the one hand enhances the cluster-ability of the learned representations and on the other hand yields the spectral graph biclustering interpretation. We cast all this in a RKM auto-encoder framework, since it has a proven track record for unsupervised representation learning and jointly training the feature mappings and projection matrices in a kernel-based framework []. We will next introduce a general wKSVD framework, after which we will introduce our HeNCler model that operates in the primal setting while jointly learning the feature mappings in an end-to-end.

### 3.1 Kernel spectral biclustering with asymmetric similarities

Consider a dataset with two, possibly different, input sources $\{\mathbf{x}_{i}\}_{i=1}^{n}$ and $\{\mathbf{z}_{j}\}_{j=1}^{m}$, on which we want to define an unsupervised learning task.
To this end, we introduce a weighted kernel singular value decomposition model (wKSVD), starting from the following primal optimization problem, which is a weighted variant of the KSVD formulation:

$$ $\displaystyle\underset{\mathbf{U},\mathbf{V},\mathbf{e},\mathbf{r}}{\min}J \triangleq\text{Tr}(\mathbf{U}^{\top}\mathbf{V})-\frac{1}{2}\sum_{i=1}^{n}w_{1 ,i}\mathbf{e}_{i}^{\top}\bm{\Sigma}^{-1}\mathbf{e}_{i}-\frac{1}{2}\sum_{j=1}^{ m}w_{2,j}\mathbf{r}_{j}^{\top}\bm{\Sigma}^{-1}\mathbf{r}_{j}$ $\displaystyle\text{s.t. }\{\mathbf{e}_{i}=\mathbf{U}^{\top}\phi(\mathbf{x}_{i} ),\ \forall i=1,\dots,n;\quad\mathbf{r}_{j}=\mathbf{V}^{\top}\psi(\mathbf{z}_{ j}),\forall j=1,\dots,m\},$ (1) $$

with projection matrices $\mathbf{U},\mathbf{V}\in\mathbb{R}^{d_{f}\times s}$; strictly positive weighting scalars $w_{1,i},w_{2,j}$; latent variables $\mathbf{e}_{i},\mathbf{r}_{j}\in\mathbb{R}^{s}$; diagonal and positive definite hyperparameter matrix $\bm{\Sigma}\in\mathbb{R}^{s\times s}$; and centered feature maps $\phi(\cdot):\mathbb{R}^{d_{x}}\mapsto\mathbb{R}^{d_{f}}$ and $\psi(\cdot):\mathbb{R}^{d_{z}}\mapsto\mathbb{R}^{d_{f}}$. (^1^11Details on centering of the feature maps are provided in Appendix A.).
The following derivation shows the equivalence with the spectral biclustering problem.

###### Proposition 1 .

The solution to the primal problem (1) can be obtained by solving the singular value decomposition of

$$ $\mathbf{W}_{1}^{1/2}\mathbf{S}\mathbf{W}_{2}^{1/2}=\mathbf{H}_{e}\bm{\Sigma} \mathbf{H}_{r}^{\top},$ (2) $$

where $\mathbf{W}_{1}$ and $\mathbf{W}_{2}$ are diagonal matrices such that $W_{1,ii}=w_{1,i}$ and $W_{2,jj}=w_{2,j}$, $\mathbf{S}=\bm{\Phi\Psi}^{\top}$ is an asymmetric similarity matrix where $S_{ij}=\phi({\mathbf{x}_{i}})^{\top}\psi({\mathbf{z}_{j}})$, $\bm{\Phi}=[\phi({\mathbf{x}_{1}})\dots\phi({\mathbf{x}_{n}})]^{\top}$, $\bm{\Psi}=[\psi({\mathbf{z}_{1}})\dots\psi({\mathbf{z}_{m}})]^{\top}$, $\mathbf{H}_{e}=[\mathbf{h}_{\mathbf{e}_{1}}\dots\mathbf{h}_{\mathbf{e}_{n}}]^{\top}$, and where $\mathbf{H}_{r}=[\mathbf{h}_{\mathbf{r}_{1}}\dots\mathbf{h}_{\mathbf{r}_{m}}]^{\top}$ are the left and right singular vectors respectively; and by applying $\mathbf{r}_{j}=\bm{\Sigma}\mathbf{h}_{\mathbf{r}_{j}}/\sqrt{w_{2,j}}$ and $\mathbf{e}_{i}=\bm{\Sigma}\mathbf{h}_{\mathbf{e}_{i}}/\sqrt{w_{1,i}}$.

###### Proof.

We now introduce dual variables $\mathbf{h}_{\mathbf{e}_{i}}$ and $\mathbf{h}_{\mathbf{r}_{j}}$ using a case of Fenchel-Young inequality []:

$$ $\frac{1}{2}w_{1,i}\ \mathbf{e}_{i}^{\top}\bm{\Sigma}^{-1}\mathbf{e}_{i}+\frac{ 1}{2}\mathbf{h}_{\mathbf{e}_{i}}^{\top}\bm{\Sigma}\mathbf{h}_{\mathbf{e}_{i}} \geq\sqrt{w_{1,i}}\ \mathbf{e}_{i}^{\top}\mathbf{h}_{\mathbf{e}_{i}},\qquad \frac{1}{2}w_{2,j}\ \mathbf{r}_{j}^{\top}\bm{\Sigma}^{-1}\mathbf{r}_{j}+\frac{ 1}{2}\mathbf{h}_{\mathbf{r}_{j}}^{\top}\bm{\Sigma}\mathbf{h}_{\mathbf{r}_{j}} \geq\sqrt{w_{2,j}}\ \mathbf{r}_{j}^{\top}\mathbf{h}_{\mathbf{r}_{j}},$ (3) $$

$\forall\mathbf{e}_{i},\mathbf{r}_{j},\mathbf{h}_{\mathbf{e}_{i}},\mathbf{h}_{
\mathbf{r}_{j}}\in\mathbb{R}^{s},\ \forall w_{1,i},w_{2,j}\in\mathbb{R}_{>0},
\ \forall\bm{\Sigma}\in\mathbb{R}^{s\times s}_{\succ 0}$. The above inequalities can be verified by writing it in quadratic form: $\frac{1}{2}\begin{bmatrix}\mathbf{e}^{\top}_{i}&\mathbf{h}^{\top}_{e_{i}}\\
\end{bmatrix}\begin{bmatrix}w_{1,i}\mathbf{\Sigma}^{-1}&-\sqrt{w_{1,i}}\
\mathbb{I}_{s}\\
-\sqrt{w_{1,i}}\ \mathbb{I}_{s}&\mathbf{\Sigma}\end{bmatrix}\begin{bmatrix}
\mathbf{e}_{i}\\
\mathbf{h}_{e_{i}}\end{bmatrix}\geq 0,\quad\forall i,$
with $\mathbb{I}_{s}$ the $s$-dimensional identity matrix, which follows immediately from the Schur complement form: for a matrix $\mathbf{Q}=$ $\left[\begin{smallmatrix}\mathbf{Q}_{1}&\mathbf{Q}_{2}\\
\mathbf{Q}_{2}^{\top}&\mathbf{Q}_{3}\end{smallmatrix}\right],$
one has $\mathbf{Q}\succeq 0$ if and only if $\mathbf{Q}_{1}\succ 0$ and the Schur complement $\mathbf{Q}_{3}-\mathbf{Q}_{2}^{\top}\mathbf{Q}_{1}^{-1}\mathbf{Q}_{2}\succeq 0$
[].

By substituting the constraints of (1) and inequalities (3) into the objective function of (1), we obtain an objective in primal and dual variables as an upper bound on the primal objective $\bar{J}\geq J$:

$$ $\min_{\mathbf{U},\mathbf{V},\mathbf{h}_{e},\mathbf{h}_{r}}\bar{J}\triangleq \text{Tr}(\mathbf{U}^{\top}\mathbf{V})-\sum_{i=1}^{n}\sqrt{w_{1,i}}\ \phi( \mathbf{x}_{i})^{\top}\mathbf{U}\mathbf{h}_{\mathbf{e}_{i}}+\frac{1}{2}\sum_{i =1}^{n}\mathbf{h}_{\mathbf{e}_{i}}^{\top}\bm{\Sigma}\mathbf{h}_{\mathbf{e}_{i} }\\ -\sum_{j=1}^{m}\sqrt{w_{2,j}}\ \psi(\mathbf{z}_{j})^{\top}\mathbf{V}\mathbf{h} _{\mathbf{r}_{i}}+\frac{1}{2}\sum_{j=1}^{m}\mathbf{h}_{\mathbf{r}_{j}}^{\top} \bm{\Sigma}\mathbf{h}_{\mathbf{r}_{j}}.$ (4) $$

Next, we formulate the stationarity conditions of problem (4):

$$ $\begin{array}[]{ccc}\dfrac{\partial\bar{J}}{\partial\mathbf{V}}=0\Rightarrow\ \mathbf{U}=\sum_{j=1}^{m}\sqrt{w_{2,j}}\ \psi(\mathbf{z}_{j})\mathbf{h}_{ \mathbf{r}_{j}}^{\top},&&\dfrac{\partial\bar{J}}{\partial\mathbf{h}_{\mathbf{e }_{i}}}=0\Rightarrow\ \bm{\Sigma}\mathbf{h}_{\mathbf{e}_{i}}=\sqrt{w_{1,i}}\ \mathbf{U}^{\top}\phi(\mathbf{x}_{i}),\\ &&\\ \dfrac{\partial\bar{J}}{\partial\mathbf{U}}=0\Rightarrow\ \mathbf{V}=\sum_{i=1 }^{n}\sqrt{w_{1,i}}\ \phi(\mathbf{x}_{i})\mathbf{h}_{\mathbf{e}_{i}}^{\top},&& \dfrac{\partial\bar{J}}{\partial\mathbf{h}_{\mathbf{r}_{j}}}=0\Rightarrow\ \bm {\Sigma}\mathbf{h}_{\mathbf{r}_{j}}=\sqrt{w_{2,j}}\ \mathbf{V}^{\top}\psi( \mathbf{z}_{j}),\end{array}$ (5) $$

from which we then eliminate the primal variables $\mathbf{U}$ and $\mathbf{V}$. This yields the eigenvalue problem:

$$ $\left[\begin{array}[]{cc}\mathbf{0}&\mathbf{W}_{1}^{1/2}\mathbf{S}\mathbf{W}_{ 2}^{1/2}\\ \mathbf{W}_{2}^{1/2}\mathbf{S}^{\top}\mathbf{W}_{1}^{1/2}&\mathbf{0}\end{array }\right]\left[\begin{array}[]{c}\mathbf{\mathbf{H}_{e}}\\ \mathbf{\mathbf{H}_{r}}\end{array}\right]=\left[\begin{array}[]{c}\mathbf{ \mathbf{H}_{e}}\\ \mathbf{\mathbf{H}_{r}}\end{array}\right]\bm{\Sigma},$ (6) $$

where $\mathbf{0}$ is an all-zeros matrix. Note that, by Lanczos’ Theorem [], the above eigenvalue problem is equivalent with (2), and that the stationarity conditions (5) provide the relationships between primal and dual variables, which concludes the proof.
∎

Figure: Figure 1: The HeNCler model. HeNCler operates in the primal setting (top of the figure in red) and uses a double multilayer perceptron (MLP) to map node representations to a feature space. The obtained representations $\bm{\phi}_{v}$ and $\bm{\psi}_{v}$ are then projected to latent representations $\mathbf{e}_{v}$ and $\mathbf{r}_{v}$ respectively. The wKSVD loss ensures that these latent representations correspond to the dual equivalent (bottom of the figure in blue) i.e., a biclustering of the asymmetric similarity graph defined by $\mathbf{S}$. The node and edge reconstructions (dashed arrows) aid in the feature map learning.

We have thus shown the connection between the primal (1) and dual formulation (6). Similarly to the KSVD framework, the wKSVD framework can be used for learning with asymmetric kernel functions and/or rectangular data sources. The spectral biclustering problem can now easily be obtained by choosing the weights $a$ and $b$ appropriately.

###### Corollary 2 .

Given Proposition 1, and by choosing $\mathbf{W}_{1}$ and $\mathbf{W}_{2}$ to equal $\mathbf{D}^{-1/2}_{1}$ and $\mathbf{D}^{-1/2}_{2}$, where $D_{1,ii}=\sum_{j}S_{ij}$ and $D_{2,jj}=\sum_{i}S_{ij}$, we obtain the random walk interpretation $\mathbf{D}_{1}^{-1/2}\mathbf{S}\mathbf{D}_{2}^{-1/2}=\mathbf{H}_{e}\bm{\Sigma}
\mathbf{H}_{r}^{\top}$ of the spectral graph bipartitioning problem for the bipartite graph $\mathcal{S}=(\bm{\Phi},\bm{\Psi},\mathbf{S})$.

Moreover, the wKSVD framework is more general as, on the one hand, one can use a given similarity matrix (e.g. adjacency matrix of a graph) or (asymmetric) kernel function in the dual, or, on the other hand, one can choose to use explicitly defined (deep) feature maps in both primal or dual.

###### Proposition 1 .

###### Proof.

###### Corollary 2 .

### 3.2 The HeNCler model

HeNCler employs the wKSVD framework in a graph setting, where the dataset is a node set $\mathcal{V}$ and where the asymmetry arises from employing to different mappings that operate on the nodes given the entire graph $\mathcal{G=(\mathbf{X},\mathbf{A}}$). Our method is visualized in Figure 1, where red indicates the primal setting of the framework and blue the dual.

In the preceding subsection, we showed that problem (1) has an equivalent dual problem corresponding to the graph bipartitioning problem, when $w_{1,i}$ and $w_{2,j}$ are chosen to equal the square root of the inverse of the out-degree and in-degree of a similarity graph $\mathcal{S}$ respectively. This similarity graph $\mathcal{S}$ depends on the feature mappings $\phi(\cdot)$ and $\psi(\cdot)$, which for our method does not only depend on the node of interest, but also on the rest of the input graph and the learnable parameters. The mappings for node $v$ thus become $\phi(\mathbf{x}_{v},\mathcal{G};\bm{\theta_{\phi}})$ and $\psi(\mathbf{x}_{v},\mathcal{G};\bm{\theta_{\psi}})$ and we will ease these notations to $\phi(\mathbf{x}_{v})$ and $\psi(\mathbf{x}_{v})$. The ability of our method to learn these feature mappings is an important aspect of our contribution, as a key motivation behind our model is that we need to learn new asymmetric similarities for clustering heterophilous graphs.
The loss function is comprised of three terms: the wKSVD-loss, a node-reconstruction loss, and an edge-reconstruction loss:

$$ $\mathcal{L}_{\text{wKSVD}}(\mathbf{U},\mathbf{V},\bm{\theta}_{\phi},\bm{\theta }_{\psi})+\mathcal{L}_{\text{NodeRec}}(\mathbf{U},\mathbf{V},\bm{\theta}_{\phi },\bm{\theta}_{\psi},\bm{\theta}_{rec})+\mathcal{L}_{\text{EdgeRec}}(\mathbf{U },\mathbf{V},\bm{\theta}_{\phi},\bm{\theta}_{\psi}),$ $$

where the trainable parameters of the model are in the the multilayer perceptron (MLP) feature maps ($\bm{\theta}_{\phi}$ and $\bm{\theta}_{\psi}$), the MLP node decoder ($\bm{\theta}_{rec}$), and in the $\mathbf{U}$ and $\mathbf{V}$ projection matrices. All these parameters will be trained end-to-end and we will next explain the losses in more detail.

wKSVD-Loss
Rather than solving the SVD in the dual formulation, HeNCler employs the primal formulation of the wKSVD framework for computational efficiency. However, we further modify the objective function in (1) by rescaling the projection matrices $\tilde{\mathbf{U}}=\mathbf{U}\bm{\Sigma}^{1/2}$ and $\tilde{\mathbf{V}}=\mathbf{V}\bm{\Sigma}^{1/2}$ and instantiating the weighting scalars $w_{1,v}=D_{1,vv}^{-1}=1/\sum_{u}\phi(\mathbf{x}_{v})^{\top}\psi(\mathbf{x}_{u})$ and $w_{2,v}=D_{2,vv}^{-1}=1/\sum_{u}\phi(\mathbf{x}_{u})^{\top}\psi(\mathbf{x}_{v})$:

$$ $J_{\text{H}}\triangleq\text{Tr}(\bm{\Sigma}^{-1}\tilde{\mathbf{U}}^{\top} \tilde{\mathbf{V}})-\sum_{v=1}^{|\mathcal{V}|}D_{1,vv}^{-1}\phi(\mathbf{x}_{v} )^{\top}\tilde{\mathbf{U}}\tilde{\mathbf{U}}^{\top}\phi(\mathbf{x}_{v})\\ -\sum_{v=1}^{|\mathcal{V}|}D_{2,vv}^{-1}\psi(\mathbf{x}_{v})^{\top}{\tilde{ \mathbf{V}}}{\tilde{\mathbf{V}}}^{\top}\psi(\mathbf{x}_{v}).$ (7) $$

The role of the projection matrices is to project the feature mappings to a lower dimensional space. To do this efficiently, we impose that they are orthogonal. Additionally, to increase the difference in the two feature mappings and/or latent node embeddings, and thus enhance the asymmetry and obtained information, we impose that they are mutually orthogonal as well. This gives rise to the following constraint on the projection matrices:

$$ $\text{s.t.}\left[\begin{array}[]{c}\tilde{\mathbf{U}}^{\top}\\ \tilde{\mathbf{V}}^{\top}\end{array}\right]\left[\begin{array}[]{cc}\tilde{ \mathbf{U}}&\tilde{\mathbf{V}}\end{array}\right]=\mathbb{I}_{2s}.$ (8) $$

Note that this constraint allows us to ignore the first term in (7) which is now constant, and that the rescaling eliminates the need for the hyperparameter matrix $\bm{\Sigma}$ in the remaining terms. For ease of notation, we omit the tildes in the remainder of the paper, and arrive at the wKSVD loss for HeNCler:

$$ $\mathcal{L}_{\text{wKSVD}}\triangleq-\sum_{v=1}^{|\mathcal{V}|}D_{1,vv}^{-1} \phi(\mathbf{x}_{v})^{\top}{\mathbf{U}}{\mathbf{U}}^{\top}\phi(\mathbf{x}_{v}) \\ -\sum_{v=1}^{|\mathcal{V}|}D_{2,vv}^{-1}\psi(\mathbf{x}_{v})^{\top}{{\mathbf{V }}}{{\mathbf{V}}}^{\top}\psi(\mathbf{x}_{v}).$ (9) $$

For the two feature maps $\phi(\cdot)$ and $\psi(\cdot)$, we employ two MLPs: $\phi(\mathbf{x}_{v},\mathcal{G};\bm{\theta}_{\phi})\equiv\text{MLP}_{\phi}(
\mathbf{x}_{v}||\text{PE}_{v};\bm{\theta}_{\phi})$ and $\psi(\mathbf{x}_{v},\mathcal{G};\bm{\theta}_{\psi})\equiv\text{MLP}_{\psi}(
\mathbf{x}_{v}||\text{PE}_{v};\bm{\theta}_{\psi})$. We construct a random walks positional encoding (PE) [] to embed the network’s structure and concatenate this encoding with the node attributes. The MLPs have two layers and use a LeakyReLU activation function.

Reconstruction losses
Note that the formulation (1) assumes that the feature maps are given. Conversely, the above loss (9) and constraint (8) are used for training the projection matrices $\mathbf{U}$ and $\mathbf{V}$, and in order to find good parameters for the MLPs, an augmented loss is required. As the node clustering setting is completely unsupervised, we add a decoder network and a reconstruction loss. This technique has been proven to be effective for unsupervised learning in the RKM-framework [], as well as for unsupervised node representation learning []. For heterophilous graphs, we argue that it is particularly important to also reconstruct node features and not only the graph structure.

For the node reconstruction, we first project the $\mathbf{e}$ and $\mathbf{r}$ variables back to feature space, concatenate these and then map to input space with another MLP. This MLP has also two layers and a leaky ReLU activation function. The hidden layer size is set to the average of the latent dimension and input dimension.
With the mean-squared-error as the associated loss, this gives:

$$ $\mathcal{L}_{\text{NodeRec}}=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}|| \text{MLP}_{rec}(\mathbf{U}\mathbf{e}_{v}||\mathbf{V}\mathbf{r}_{v};\bm{\theta }_{rec})-\mathbf{x}_{v}||^{2}.$ (10) $$

To reconstruct edges, we use a simple dot-product decoder $\sigma(\mathbf{e}_{u}^{\top}\mathbf{r}_{v})$ where $\sigma$ is the sigmoid function. By using the $\mathbf{e}$ representation for source nodes and $\mathbf{r}$ for target nodes, this reconstruction is asymmetric and can reconstruct directed graphs. We use a binary cross-entropy loss:

$$ $\mathcal{L}_{\text{EdgeRec}}=\frac{1}{|\mathcal{U}|}\sum_{(u,v)\in\mathcal{U}} \text{BCE}(\sigma(\mathbf{e}_{u}^{\top}\mathbf{r}_{v}),\mathcal{E}_{uv}),$ (11) $$

where $\mathcal{U}$ is a node-tuple set, resampled every epoch, containing $2|\mathcal{V}|$ positive edges from $\mathcal{E}$ and $2|\mathcal{V}|$ negative edges from $\mathcal{E}^{C}$, and $\mathcal{E}_{uv}\in\{0,1\}$ indicates whether an edge $(u,v)$ exist: $(u,v)\in\mathcal{E}$.

Optimizers and cluster assignment   Given the constraint on $\mathbf{U}$ and $\mathbf{V}$, we use CayleyAdam [] to optimize these parameters. For the parameters of the MLPs, we use the Adam optimizer [].
Cluster assignments are obtained by KMeans clustering on the concatenation of learned $\mathbf{e}$ and $\mathbf{r}$ node representations.

**Table 2: Dataset statistics of the employed heterophilous graphs.**
| Dataset | # Nodes | # Edges | # Classes | Directed | $\mathcal{H}(\mathcal{G})$ |
| --- | --- | --- | --- | --- | --- |
| Texas | 183 | 325 | 5 | ✓ | 0.000 |
| Cornell | 183 | 298 | 5 | ✓ | 0.150 |
| Wisconsin | 521 | 515 | 5 | ✓ | 0.084 |
| Chameleon | 2,277 | 31,371 | 5 | ✗ | 0.042 |
| Squirrel | 5,201 | 198,353 | 5 | ✗ | 0.031 |
| Roman-empire | 22,662 | 32,927 | 18 | ✗ | 0.021 |
| Amazon-ratings | 24,492 | 93,050 | 5 | ✗ | 0.127 |
| Minesweeper | 10,000 | 39,402 | 2 | ✗ | 0.009 |
| Tolokers | 11,758 | 519,000 | 2 | ✗ | 0.180 |
| Questions | 48,921 | 153,540 | 2 | ✗ | 0.079 |

## 4 Experiments

Datasets   We assess the performance of HeNCler on heterophilous attributed graphs that are available in literature. We use three sets of datasets. First, we use Texas, Cornell, and Wisconsin, which are directed webpage networks where edges encode hyperlinks between pages [].(^2^22http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-11/www/wwkb) Second, we use Chameleon and Squirrel, which are undirected Wikipedia webpage networks where edges encode mutual links []. The third set of graphs we assess our model on contains the undirected graphs: Roman-empire, Amazon-ratings, Minesweeper, Tolokers, and Questions, which are a graph representation of a Wikipedia article, a co-purchasing network, a grid graph based on the minesweeper game, a crowd-sourcing network, and a Q&A-forum interaction network respectively []. The dataset statistics can be consulted in Table 2, where the class insensitive edge homophily ratio $\mathcal{H}(\mathcal{G})$ [] is a measure for the level of homophily in the graph.

**Table 3: Experimental results for directed heterophilous graphs, comparing HeNCler with state-of-the-art baselines. We report average best NMI and F1 performances, together with the standard deviation. All metrics are in %, where higher is better. Best results are highlighted in bold.**
| Dataset | Metric | baselines | ours |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| KMeans | MinCutPool | DMoN | S^3GC | HeNCler |  |  |
| Texas | NMI | 4.97$\pm$1.00 | 11.60$\pm$2.19 | 9.06$\pm$2.11 | 11.56$\pm$1.46 | 36.50$\pm$3.63 |
| F1 | 59.27$\pm$0.83 | 55.26$\pm$0.56 | 47.76$\pm$4.79 | 43.69$\pm$2.74 | 67.38$\pm$3.39 |  |
| Cornell | NMI | 5.42$\pm$2.04 | 17.04$\pm$1.61 | 12.49$\pm$2.51 | 14.48$\pm$1.79 | 29.65$\pm$6.40 |
| F1 | 52.97$\pm$0.24 | 51.21$\pm$5.06 | 43.83$\pm$6.23 | 33.13$\pm$0.83 | 56.78$\pm$4.21 |  |
| Wisconsin | NMI | 6.84$\pm$4.39 | 13.38$\pm$2.36 | 12.56$\pm$1.23 | 13.07$\pm$0.61 | 41.88$\pm$4.34 |
| F1 | 56.16$\pm$0.58 | 55.63$\pm$2.96 | 45.72$\pm$7.85 | 31.71$\pm$2.25 | 66.46$\pm$2.24 |  |

Model selection and metrics   Model selection in this unsupervised setting is non-trivial, and the best metric depends on the task at hand. Therefore, this is not the scope of this paper and we assess our model agnostically to the model selection, and fairly w.r.t. to the baselines. We fix the hyperparameter configuration of the models across all datasets, and we do not perform early stopping. We keep track of the evaluation metrics during training and report the best observed result. We repeat the training process 10 times and report average best results with standard deviations.
We report the normalized mutual information (NMI) and pairwise F1-scores, based on the class labels.

Baselines and hyperparameters   We compare our model with a simple KMeans using the node-attributes, and with state-of-the-art node clustering methods MinCutPool [], DMoN [], and S^3GC []. For HeNCler, we fix the hyperparameters to: MLP hidden dimensions $256$, output dimensions $128$, latent dimension $s=2\times\#classes$, learning rate $0.01$, and epochs $300$.
For the baselines, we used their code implementations and the default hyperparameter settings as proposed by the authors. The number of clusters to infer is set to the number of classes cfr. Table 2 for all methods.

Experiments   Table 3 summarizes the experimental results for the directed heterophilous graphs. We observe that HeNCler demonstrates superior performance, outperforming KMeans, MinCutPool, DMoN, and S^3GC with a significant margin on these heterophilous directed graphs.

The experimental results for the other graphs are shown in Table 4. With 7 out of 14 best performances, HeNCler is the overall most performant model, compared with KMeans (1/14), MinCutPool (3/14), DMoN (2/14), and S^3GC (1/14).

The experiments were run on a Nvidia V100 GPU, and the total training time for HeNCler of 10 runs for all datasets in Tables 3 and 4 was 101 minutes, including the KMeans cluster assignments at every iteration to track performance. We provide a detailed table with computation times in Appendix C.

**Table 4: Experimental results for undirected graphs. We report average best NMI and F1 performances, together with the standard deviation. All metrics are in %, where higher is better. Best results are highlighted in bold.**
| Dataset | Metric | baselines | ours |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| KMeans | MinCutP. | DMoN | S^3GC | HeNCler |  |  |
| Chameleon | NMI | 0.44$\pm$0.11 | 11.88$\pm$1.99 | 12.87$\pm$1.86 | 15.83$\pm$0.26 | 22.19$\pm$1.09 |
| F1 | 53.23$\pm$0.07 | 50.40$\pm$5.65 | 45.05$\pm$4.30 | 36.51$\pm$0.24 | 47.73$\pm$2.62 |  |
| Squirrel | NMI | 1.40$\pm$2.12 | 6.35$\pm$0.32 | 3.08$\pm$0.38 | 3.83$\pm$0.11 | 9.35$\pm$0.38 |
| F1 | 54.05$\pm$2.72 | 55.26$\pm$0.57 | 49.21$\pm$2.74 | 35.08$\pm$0.18 | 44.14$\pm$4.18 |  |
| Roman | NMI | 35.20$\pm$1.79 | 9.97$\pm$2.02 | 13.14$\pm$0.53 | 14.48$\pm$0.21 | 39.79$\pm$0.73 |
| empire | F1 | 37.17$\pm$2.12 | 42.19$\pm$0.26 | 22.69$\pm$3.91 | 17.76$\pm$0.53 | 38.97$\pm$1.43 |
| Amazon | NMI | 0.08$\pm$0.01 | 0.82$\pm$0.30 | 0.53$\pm$0.10 | 0.83$\pm$0.03 | 0.22$\pm$0.05 |
| ratings | F1 | 30.52$\pm$0.83 | 51.63$\pm$4.40 | 39.94$\pm$7.46 | 17.99$\pm$0.15 | 36.40$\pm$2.87 |
| Mine- | NMI | 0.02$\pm$0.02 | 6.16$\pm$2.17 | 6.87$\pm$2.91 | 6.53$\pm$0.17 | 0.10$\pm$0.01 |
| sweeper | F1 | 73.63$\pm$3.58 | 71.76$\pm$8.86 | 70.42$\pm$9.47 | 48.78$\pm$0.63 | 80.52$\pm$0.32 |
| Tolokers | NMI | 3.04$\pm$2.83 | 6.68$\pm$0.98 | 6.69$\pm$0.20 | 5.99$\pm$0.05 | 5.30$\pm$1.04 |
| F1 | 65.56$\pm$10.49 | 72.10$\pm$10.38 | 67.87$\pm$4.74 | 59.17$\pm$0.27 | 74.18$\pm$5.16 |  |
| Questions | NMI | 0.18$\pm$0.45 | 0.84$\pm$0.23 | 0.32$\pm$0.25 | 0.97$\pm$0.02 | 1.73$\pm$0.00 |
| F1 | 78.79$\pm$10.29 | 92.01$\pm$6.39 | 92.51$\pm$4.23 | 74.13$\pm$0.57 | 95.18$\pm$0.08 |  |

Ablation   We further compare HeNCler with a simplified version of itself, which uses a single MLP for the $\phi(\cdot)$ and $\psi(\cdot)$ mappings, and only the $\mathbf{U}$ projection matrix (i.e., $\phi(\cdot)\equiv\psi(\cdot)$ and $\mathbf{U}\equiv\mathbf{V}$). This simplified version reduces the model to a symmetric model. We run one experiment for each dataset, where the initialisation was the same for both methods. Interestingly, we observe in Table 5 that also for the undirected graphs, the asymmetry in HeNCler improves the clustering performance.

**Table 5: Ablation study, comparing HeNCler with a simplified undirected version. NMI and F1 performances are in % and higher is better. More results are provided in Appendix B.**
| Metric | Method | Tex | Cor | Squi | Rom | Ama | Tol | Que |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| NMI | HeNCler | 41.61 | 24.27 | 9.04 | 40.04 | 0.17 | 6.30 | 1.73 |
| Undirec. | 18.50 | 16.50 | 8.20 | 36.44 | 2.48 | 5.79 | 0.95 |  |
| F1 | HeNCler | 68.27 | 55.32 | 46.81 | 39.64 | 34.74 | 77.18 | 95.28 |
| Undirec. | 58.69 | 49.09 | 37.35 | 32.65 | 24.54 | 65.75 | 87.13 |  |

## 5 Discussion

Figure: Figure 2: The learned matrix $\mathbf{S}=\bm{\Phi\Psi}^{\top}$ for the Wisconsin (left) and Roman-empire (right) dataset. Rows and columns are grouped according to ground-truth node labels. $\mathbf{S}$ is asymmetric and is showing clear block structures that represent similarities between groups of nodes, relevant to the heterophilous labels.
Refer to caption: x1.png

We compare HeNCler with a basic KMeans clustering algorithm. Note that the focus of our method lies in the node representation learning aspect, and that it uses the same KMeans clustering algorithm for the cluster assignments. The comparisons between HeNCler and KMeans in Tables 3 and 4 therefore indicate that our model improves the node representations for the node clustering task, w.r.t. the input features, and that it effectively learns from both the node attributes as well as the network structure of the graph.

One of the key motivations of HeNCler is to exploit asymmetric information in the data. The superior performance of our model for the directed graphs (Table 3) validates this motivation. Furthermore, our ablation study in Table 5 indicates that even for the undirected graphs, HeNCler is able to learn relevant asymmetric information in the two node embeddings. At the same time, HeNCler outperforms the state-of-the-art models on the undirected graphs as well. We attribute this observation to another key motivation of our method, i.e., that it learns a new similarity that is not defined by the network structure alone.

We visualize the learned similarity matrix $\mathbf{S}=\bm{\Phi\Psi^{\top}}$ for two datasets in Figure 2. We see that these matrices are asymmetric, and that, given the observable block structures, these similarities are meaningful w.r.t. to the ground truth node labels. Note however that our model operates in the
primal setting and directly projects the learned mappings $\bm{\phi}$ and $\bm{\psi}$ to their final embeddings $\mathbf{e}$ and $\mathbf{r}$ using $\mathbf{U}$ and $\mathbf{V}$ respectively, avoiding quadratic space complexity and cubic time complexity of the SVD. This is the motivation of employing a kernel based method, and exploiting the primal-dual framework that comes with it. In fact, the matrices in Figure 2 are only constructed for the sake of this visualization.

Computational complexity
The space and time complexity of the current implementation of HeNCler are both linear w.r.t. the number of nodes $\mathcal{O}(|\mathcal{V}|)$. Whereas MinCutPool and DMoN need all the node attributes in memory to calculate the loss w.r.t. the full adjacency matrix, HeNCler is easily adaptable to work with minibatches which reduces space complexity to the minibatch size $\mathcal{O}(|\mathcal{B}|)$. Although HeNCler relies on edge reconstruction, the edge sampling avoids quadratic complexity w.r.t. number of nodes, and is specifically designed to scale with the number of nodes, rather than the number of edges. Assuming the graphs are sparse, we add an overview of space and time complexity w.r.t. the number of nodes and edges for all methods in Table 1.

Limitations
We wish we could include more experiments on directed heterophilous graphs but we observe that literature needs more directed heterophilous graph benchmarks. Nevertheless, we demonstrated that the asymmetric framework is also beneficial for undirected graphs.

Broader impact   This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work that are general to this kind of Machine Learning research. We address two of these that are more specifically related to this paper.
First, since our method relies more than other methods on the attributes of the nodes, and thus less on smoothing of these attributes over the graph, our method might be more susceptible to differential privacy issues.
Second, given that we focus on heterophilous graphs, we strongly hope that HeNCler allows for companies and
institutions to develop algorithms that better account for the beauty of human diversity.

## 6 Conclusion and future work

We tackle two limitations of current node clustering algorithms, that prevent these methods from effectively clustering nodes in heterophilous graphs: they assume homophily in their loss and they are often only defined for undirected graphs.

To this end, we introduce a weighted kernel SVD framework and harness its primal-dual equivalences. HeNCler relies on the dual interpretation for its theoretical motivation, while it benefits from the computational advantages of its implementation in the primal. In an end-to-end fashion, it learns asymmetric similarities, and node embeddings resulting from the spectral biclustering interpretation of these learned similarities. As empirical evidence shows, our approach effectively eliminates the aforementioned limitations, significantly outperforming current state-of-the-art alternatives.

As current self-supervised clustering models assume that similarity is related to closeness in the graph, future work could investigate what a good self-supervised approach would be for heterophilous graphs, and how adding such a self-supervised component to HeNCler would further boost its performance. Another next step can be to investigate how to do the cluster assignments in a graph pooling setting (i.e., differentiable graph coarsening), to enable end-to-end learning for downstream graph prediction tasks.

## Acknowledgments

We thank the following institutions for their funding:
(i) The research leading to these results has received funding from the European Research Council under the European Union’s Horizon 2020 research and innovation program / ERC Advanced Grant E-DUALITY (787960). This paper reflects only the authors’ views and the Union is not liable for any use that may be made of the contained information.
(ii) Research Council KUL: projects ’Tensor Tools for Taming the Curse’ (iBOF/23/064) and ’Optimization frameworks for deep kernel machines’ (C14/18/068).
(iii) Flemish Government FWO project GOA4917N (Deep Restricted Kernel Machines: Methods and Foundations), PhD/Postdoc grant.
(iv) This research received funding from the Flemish Government (AI Research Program). Johan Suykens and Sonny Achten are affiliated to Leuven.AI - KU Leuven institute for AI, B-3000, Leuven, Belgium.
(v) This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043),
and (vi) by ARO under Grant Number W911NF-24-1-0048.

## Appendix A Note on feature map centering

In the wKSVD framework, we assume that the feature maps are centered. More precisely, given two arbitrary mappings $\phi(\cdot)$ and $\psi(\cdot)$, the centered mappings are obtained by subtracting the weighted mean:

$$ $\displaystyle\phi_{c}(\mathbf{x}_{i})=\phi(\mathbf{x}_{i})-\frac{\sum_{k=1}^{n }w_{1,k}\ \phi(\mathbf{x}_{k})}{\sum_{k=1}^{n}w_{1,k}},$ $\displaystyle\psi_{c}(\mathbf{z}_{j})=\psi(\mathbf{z}_{j})-\frac{\sum_{l=1}^{m }w_{2,l}\ \psi(\mathbf{z}_{l})}{\sum_{l=1}^{m}w_{2,l}}.$ $$

Although we use the primal formulation in this paper, we next show how to obtain this centering in the dual for the sake of completeness. When using a kernel function or a given similarity matrix, one has no access to the explicit mappings and has to do an equivalently centering in the dual using:

$$ $\mathbf{S}_{c}=\mathbf{M}_{1}\mathbf{S}\mathbf{M}_{2}^{\top},$ $$

where $\mathbf{M}_{A}$ and $\mathbf{M}_{B}$ are the centering matrices:

$$ $\displaystyle\mathbf{M}_{1}=\mathbb{I}_{n}-\frac{1}{\mathbf{1}_{n}^{\top} \mathbf{W}_{1}\mathbf{1}_{n}}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\mathbf{W}_{1}$ $\displaystyle\mathbf{M}_{2}=\mathbb{I}_{m}-\frac{1}{\mathbf{1}_{m}^{\top} \mathbf{W}_{2}\mathbf{1}_{m}}\mathbf{1}_{m}\mathbf{1}_{m}^{\top}\mathbf{W}_{2},$ $$

with $\mathbb{I}_{n}$ and $\mathbf{1}_{n}$ a $n\times n$ identity matrix and a $n$-dimensional all-ones vector respectively. We omit the subscript $c$ in the paper and assume the feature maps are always centered. Note that this can easily be achieved in the implementations by using the above equations.

## Appendix B Ablation Results

Table 6 provides the results of the ablation study for all datasets.

**Table 6: Ablation study, comparing HeNCler with a simplified undirected version. NMI and F1 performances are in % and higher is better.**
| Metric | Method | Texas | Cornell | Wisconsin | Chameleon | Squirrel |
| --- | --- | --- | --- | --- | --- | --- |
| NMI | HeNCler | 41.61 | 24.27 | 37.19 | 23.16 | 9.04 |
| Undirec. | 18.50 | 16.50 | 27.99 | 16.15 | 8.20 |  |
| F1 | HeNCler | 68.27 | 55.32 | 63.69 | 45.83 | 46.81 |
| Undirec. | 58.69 | 49.09 | 56.32 | 51.07 | 37.35 |  |
| Metric | Method | Roman-e. | Amazon-r. | Minesw. | Tolokers | Questions |
| NMI | HeNCler | 40.04 | 0.17 | 0.10 | 6.30 | 1.73 |
| Undirec. | 36.44 | 2.48 | 0.06 | 5.79 | 0.95 |  |
| F1 | HeNCler | 39.64 | 34.74 | 80.64 | 77.18 | 95.28 |
| Undirec. | 32.65 | 24.54 | 79.16 | 65.75 | 87.13 |  |

## Appendix C Computation times

We trained MinCutPool, DMoN, and HeNCler for 300 iterations; and S^3GC for 30 iterations on a Nvidia V100 GPU, and report the computation times in Table 7.
Figure 3 visualises these result w.r.t. the number of nodes in the graph, showing the linear time complexity of HeNCler and that it is insensitive to the number of edges. We conclude that HeNCler demonstrates fast computation times.

**Table 7: Computation times in seconds.**
| Dataset | baselines | ours |  |  |
| --- | --- | --- | --- | --- |
| MinCutP. | DMoN | S^3GC | HeNCler |  |
| Chameleon | 8 | 20 | 89 | 24 |
| Squirrel | 14 | 86 | 105 | 49 |
| Roman-empire | 67 | 71 | 312 | 57 |
| Amazon-rating | 109 | 93 | 195 | 63 |
| Minesweeper | 55 | 27 | 98 | 21 |
| Tolokers | 71 | 198 | 100 | 35 |
| Questions | 340 | 215 | 217 | 125 |

Figure: Figure 3: Computation times of MinCutPool, DMoN, S^3GC, and HeNCler w.r.t. the number of nodes of the datasets. We observe that HeNCler scales linearly with the number of nodes, and that it is not sensitive to the number of edges, as opposed to DMoN, showing a significant peak for the Tolokers dataset due the large number of edges in this graph.
Refer to caption: x2.png

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: See Weakness.
soundness: 3
strengths: 1. The proposed method is easy to understand.
2. It addresses an important problem.
summary: This paper proposes a kernel spectral biclustering framework to learn an induced asymmetric similarity graph suited for node clustering of heterophilous graphs.
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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 3
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.
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.
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?

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
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.
soundness: 2
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.
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.
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.

---

confidence: 5
contribution: 2
initial_rating: 1
presentation: 3
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.
soundness: 3
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.
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.
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).

Meta-review: 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.

Decision: Reject