Hyperspherical Prototype Node Clustering
Authors: Jitao Lu
Danyang Wu
Feiping Nie
Rong Wang
Xuelong Li
Venue: Accepted by TMLR ()

Abstract: The general workflow of deep node clustering is to encode the nodes into node embeddings via graph neural networks and uncover clustering decisions from them, so clustering performance is heavily affected by the embeddings. However, existing works only consider preserving the semantics of the graph but ignore the inter-cluster separability of the nodes, so there's no guarantee that the embeddings can present a clear clustering structure. To remedy this deficiency, we propose Hyperspherical Prototype Node Clustering (HPNC), an end-to-end clustering paradigm that explicitly enhances the inter-cluster separability of learned node embeddings. Concretely, we constrain the embedding space to a unit-hypersphere, enabling us to scatter the cluster prototypes over the space with maximized pairwise distances. Then, we employ a graph autoencoder to map nodes onto the same hypersphere manifold. Consequently, cluster affinities can be directly retrieved from cosine similarities between node embeddings and prototypes. A clustering-oriented loss is imposed to sharpen the affinity distribution so that the learned node embeddings are encouraged to have small intra-cluster distances and large inter-cluster distances. Based on the proposed HPNC paradigm, we devise two schemes (HPNC-IM and HPNC-DEC) with distinct clustering backbones. Empirical results on popular benchmark datasets demonstrate the superiority of our method compared to other state-of-the-art clustering methods, and visualization results illustrate improved separability of the learned embeddings.

Published in Transactions on Machine Learning Research (01/2024)
Hyperspherical Prototype Node Clustering
Jitao Lu
dkanbuyjaao@mmaiilcco
School of Computer Science, School of Artificial Intelligence, OPtics and ElectroNics (iOPEN), Northwestern. Polytechnical University
Danyang Wu
donyangwu. wwwpw/www...mm.i...o com State Key Laboratory for Manafaccuring Systems Engineering, School of Electronic and Information Engineering, Xi Ki'on Jinotong University
Feiping Nie*
feipingnie@gmaie com School of Artificial Intelligence, OPtics and ElectroNics (iOPEN), Northwestern Polytechnical University
wangrong@77@tsingluu. org.en School of Artificial Intelligence, OPtics and ElectroNics (iOPEN), Northwestern Pokytechmical University
Rong Wang
#'Snwpu.edu.cm School of Artificial Intelligence, OPtics and ElectroNics (1OPEN), Northwestern Polgtechnical University
Xuelong Li
Reviewed on OpenReview: openrevveeee forum? id= =32ina0M0d
Abstract
The general workflow of deep node clustering is to encode the nodes into node embeddings via graph neural networks and uncover clustering decisions from them, so clustering performance heavily affected by the embeddings. However, existing works only consider preserving the semantics of the graph but ignore the inter-cluster separability of the nodes, so there's no guarantec that the embeddings can present clear clustering structure. To remedy this deficiency, we propose Hyperspherical Prototype Node Clustering (HPNC), an end-to-end clustering paradigm that explicitly enhances the inter-cluster separability of learned node embeddings. Concretely, we constrain the embedding space to a unit-hypersphere enabling us to scatter the cluster prototypes over the space with maximized pairwise distances. Then, employ graph antoencoder to map nodes onto the same hypersphere manifold. Con- sequently, cluster affinitics be directly retrieved from cosine similarities between node embeddings and protolypes. A clustering-orientel loss is imposed to sharpen the alfinity distribution so that the learned node embeddings are encouraged to have small intra-cluster distances and large inter-cluster distances. Based on the proposed HPNC paradigm, we devise two schemes (HPNC-IM and HPNC-DEC) with distinct clustering backbones. Em- pirical results on popular benehmark datasets demonstrate the superiority of our method compared to other state-of-the-ade clustering methods, and visualization results illustrate improved separability of the learned embeddings.
1 Introduction
Graph-structured data are ubiquitous in numerous domains, including social networks, recommendation systems, physics, and biology. Community structure one of the most important characteristics of a graph and is useful in many downstream tasks. Finding communities from graph can be formulated as node
clustering problem. Node clustering aims to categorize the nodes of graph into set of disjoint groups such that similar nodes are assigned to common group. Spectral clustering fvon Luxburg, 2007) has been one of the most successful and well-known node clustering methods in the past two decades. Given a
*Corresponding author.

---

Published in Transactions on Machine Learning Research (01/2024)
weighted undirected graph, spectral clustering firstly uses Laplacian eigenmaps (Belkin & Niyogi 2003) to embed the nodes into a low-dimensional feature space, then employs K-means to uncover clustering results from them. Being the first step of spectral clustering, the task of encoding nodes into feature vectors is called node embeddings (Cui et al. 2019), and Laplacian eigenmap is essentially the earliest node embedding method. Hence, the output of general-purpose node embedding methods can also be passed to K-means or other clustering methods for node clustering. However, real-world graph data, are usually too complex for "shallow" embedding methods to capture the underlying relationships, leading to suboptimal performance of downstream tasks including clustering.
Recently, a surge in research on graph neural networks (GNNs) has led to state-of-thc-art results on numer- ous rownstream tasks. Moreover, the encoder can be easily chained with downstream tasks to customize the embeddings for them, which is non-trivial for previous methods. Methods employing a graph neural network (GNN) to do node embedding and perform clustering after that are called deep clustering. For example, graph autoencoder (GAE, Kipf Welling 2016) uses stacked graph convolution network (GCN, Kipf & Welling 2017] layers to encode the input graph and node features into a low-dimensionall space, then reconstructs the graph by inner products of the latent embeddings and minimizes the reconstruction error to self-supervise the training. After converging, the embeddings are passed to K-mcans to obtain clustering results. Later autoencoder- based approaches (Wang et al. 2017 Pan et al. 2020: Cui et al. 2020 Wang
et al. 2020 Hou et al. 2022 Zhang et al. 2022) improved the GNN towards better latent embeddings. However, they mostly focus on having the learned embeddings better reconstruct the input graph and/or node features. That is, optimizing their objectives does not explicitly lead to better clusterability, so the resulting embeddings may not be suitable for clustering. To be specific, these methods overlooked the dis- tribution of cluster prototype different cluster prototypes should be far from each other for their affiliated node embedldings to be dislinguuishabl. A concurrent work (Liu et al.] (023b) noticed this issue and proposed to push away different cluster centroids by penalizing the smallest centroid distance, but this is implemented as a regularization term so the effect is not guaranteed in practice.
On the other hand, most existing works either adopt the same sequential pipeline as GAE or follow (Yang et al.
2017) to iteratively optimize reconstruction loss and K-means loss. The fact is not limited
autocncoder- based approaches but also contrastive-leariing- basedd approaches (Park et al. 2022 Devvrit
2022 Liu et al. 2022a) that becoming popular in recent years. Exceptions are DAEGC (Wang et al. 2019) and SDCN (Bo et al. 2020). They pretrain the GAF as usual in the first step, then use K-means to obtain cluster centroids from the latent embeddings and follow (Xie et al. 2016) to form soft labels based on sample-centroid distances. After that, the emboddings are refined by self-training, and final clustering results are obtained from the soft labels after refinement. SDCN additionally normalized the latent em- beddings by softmax function so soft labels can also be obtained there, but K-means is still unavoidable to obtain the centroids. The most critical drawback of K-means in a deep learning pipeline that K-means' objective is not differentiable. As result, it cannot be optimized by gradient descent thus prohibiting chained training with other downstream tasks. Moreover, the network parameters and clustering centroids have to be alternatively updated as the original K-means does, which leads to error propagation, prevents parallelism, and is prone to gel stuck in bad local optimums.
et al.
In order for the learned embeddings to present a clear clustering structure, their intra-cluster distance should be as small as possible and inter-cluster distance should be as large as possible. Motivated by this criterion, this work mainly focuses on enhancing the separability of different clusters in unsupervised settings. In fact, this is similar to the objective of distance metric learning (Wang et al. 2014 Zhao et al. 2021b), which treats samples from the same class as positive pairs and samples from different classes as negative pairs and trains the neural network to generate similar embeddings for positive pairs and dissimilar embeddings for negative pairs. For instance, Proxy-NCA loss (Mosshovitz-Attias et al. 2017) assigns a proxy to each class. During training, a data point is encouraged to be close to its corresponding class proxy, and far apart from other class proxies. As long as the proxies are separable, the learned embeddings are also separable. However, these class proxies are selected according to ground truth labels of the training set, so it's impossible to follow its selection strategy in unsupervised tasks and metric learning methods cannot be trivially adopted in clustering. Nonetheless, our method is heavily inspired by ProXy-NCA.
1 Also known as cluster centroids some clustering methods.
2

---

Published in Transactions on Machine Learning Research (01/2024)
0.0.0
0.0.0
0000
Q
Cosine
Encode
Similarity
0.0.0
Reconstruct
oos 0g
Normalize
Cod 0g
0000
0000
o
P
Decode
Unit-hypersphere
0000
ODOG
COCO
Figure The workflow of HPNC. The input nodes are passed to several GNN layers to generate node embeddings. Then, the embeddings are passed a GNN layer to reconstruct node features and an inner product decoder reconstruct edges. I0-normalization is applied to make them fit unit-hypersphere manifold. Given uniformly distributed cluster prototypes the same manifold, the soft labels Q can be obtained by the cosine similaritics between node embeddings (gray circle) and cluster prototypes (colored triangles). A clustering loss is imposed on Q to sharpen it so that confident predictions are emphasized and unconfident predictions are suppressed. The clustering loss is jointly minimized with the reconstruction errors towards discriminative node embeddings. Clustering results are directly obtained from Q.
In this paper, we simultancously address the issues mentioned above and propose Hyperspherical Prototype Node Clustering (HPNC), a fully differentiable and end-lo-end clustering paradigm which explicitly considers the separability of different clusters. Unlike previous works that infer clustering centroids from preliminary node embeddings, we use predefined controids and maximize their margins to encourage the scparability of different clusters. To this goal, we constrain the embedding space to a unit-hypersphere where the maximum distance between points is bounded. Then, scatter the cluster prototypes the hypersphere manifold so they have equal and maximized pairwise distances. After that, to map the input nodes onto the same manifold. Consequently, the soft labels can be obtained by their cosine similarities between prototypes. A clustering-oriented objective is jointly optimized with GAF to push nodes to corresponding prototypes. Remarkably, our HPNC is general pipcline and can be used with any unsupervised representation learning methods and any deep clustering objective for joint representation learning and clustering. We demonstrate such flexibility by devising two clustering schemes based on HPNC, The general pipeline of HPNC is illustrated in Figure 1 Our main contributions are:
use graph autoencoder
We propose a novel node clustering paradigm called HPNC for joint representation learning and node clustering. HPNC explicitly maximizes the inter-cluster distances of the learned embeddings to provide sufficient discriminative power for clustering. Moreover, HPNC is fully differentiable so can be easily integrated into deep learning pipeline and jointly optimized with other modules.
We develop a learning- based prototype rotation strategy to assist GNN to find matching prototypes. allows the predefined prototypes to rotate on the hypersphere manifold so HPNC becomes loss sensitive to their initial coordinates. Ablation study results verify that it's crucial to the clustering performance.
Based the proposed HPNC paradigm, we devise two schemes (f.e., HPNC-IM and HPNC-DEC) to demonstrate the flcxibility of HPNC to work with different clustering backbones. HPNC can also combine with other backbones to enjoy their advantages.
Empirical results on widely adopted node clustering benchmark datasets consistently verify the effec- tiveness of our proposal compared to other state-of-the-art. methods. To explore the characteristics of
3

---

Published in Transactions on Machine Learning Research (01/2024)
the learned embeddings, we further apply K-means clustering and t-SNE visualization on them, and the results significantly reveal that our method indeed leads to more discriminative and separable latent embeddings.
2
Related Work
In this section, we briefly review the techniques closely related to our work, including unsupervised graph representation learning and deep clustering methods.
2.1 Unsupervised Graph Representation Learning
Unsupervised graph representation learning (UGRL) aims at projecting the nodes, edges, subgraphs, entire graph, to a low-dimensional vector RT, without access to ground truth labels, that they can be effectively handled by downstream machine learning algorithms. Traditional UGRL methods utilize matrix factorization (Belkin & Niyogi 2003 Cao et al. 2015) and random walks (Grover & Leskovee 2016) to capture graph characteristics. Specifically, Deep Walk Perozzi et al. (2014) defines the similarity between two nodes as the probability that they co-occur on a random walk, so it first estimates these probabilities from fixed-length and unbiased random walks sampled over the graph, then employs the skip-gram model to learn node embeddings that reconstruct these probabilities. node2vec Grover & Leskoved (2066) improved the walk strategy by using flexible, biased random walks that can trade off between local and global views of the graph. NetRA Yu et al. (2018b) proposed to learn the node embeddings with adversarially regularized autoendoers. Unlike skip-gram based models, it employs a long short-term memory (LSTM) network to map one hot vertex encodings into latent reprosentations and train them to reconstruct the input. In addition to static graphs, Net Walk Yu et al. (2018a) proposed a novel reservoir sampling stralegy to incrementally maintain the learned embeddings to effectively handle dynamic graphs. However, these methods utilize the graph topology only, For attributed graphs where each node is also associated with feature vector, they are unable to exploit such extra information thus leading to suboptimal performance on downstream tasks. With the advance of deep learning on graphs, recent UGRL methods employ GNN to perform the projection and design various unsupervised objectives to train the GNN. Autoencoder-based methods are the most popular thanks to their simplicity and effectivencss. GAE and VGAE (Kipf & Welling 2016) take the dot products of latent embeddings as predicted edges and let. them reconstruct the input graph. ARGA and ARVGA (Pan et al., 2020) introduced an adversarial regularizer on top of GAE and VGAE to encourage the latent emboddings to also follow prior distribution. MGAE (Wang al.) 2017) passes corrupted node features to the GNN and lets the latent embeddings reconstruct uncorrupted node features. GALA (Park et al.) 2019) designed decoder to reconstruct node features from latent embeddings. Another fruitful avenue of UGRL. is based on contrastive learning (Zhu et al. 2021), which Icarns meaningful embeddings by pulling predefined positive pairs and pushing negalive pairs. DGT (Velickovic et al. 2019) generates graph embeddings of the input graph and its corrupted counterpart, then treats them as positive and negative samples of the uncorrupted node embeddings, respectively. InfoGraph (Sun et al., (2200) extends DGI to handle a batch of graphs, node embeddings from the same graph are positive pairs, and vice versa. MVGRL (Hassani & Ahmadi 2020) employs graph diffusion (Kliepera et al.) 2019) to generate
augmented view of the graph, then regards node embeddings from one view and graph embedding of another view as positive pairs. GRACE (Zhu et al. 2020) and SimGRACE (Xia et al. instance discrimination task (Wu et al.] views as positive, and all other pairs as negative. GGD (Zheng et al. 2022) simplified DGI and improved it to scale to large data. Compared to traditional UGRL methods, Gasebased methods usually incorporate the node attributes when learning latent embeddings, hence performing better on downstream tasks.
2022 generate two augmented views of the graph, then follow the
2018) to treat a pair of embeddings of the same node in different
2.2 Deep Clustering
Real-world data are usually high high-dimensional and non-globular, so shallow clustering methods such as K- mcans can not effectively handle them. Methods employing a deep neural network (DNN) to do non-lincar mapping and perform clustering after that are called deep clustering, whose assumption is that mapped data distributions are more suitable for clustering than raw features. However, directly combining DNN
4

---

Published in Transactions on Machine Learning Research (01/2024)
with K-means is not viable approach, because the global optimum of K-means is achieved when DNN maps all data samples to one single point, which is called cluster collapse. To avoid this issue, most works employ an autoencoder to do the feature mapping, because the autoencoder's objective requires the latent embeddings to reconstruct the original inputs, which ensures that critical semantic information is preserved. GraphEncoder (Tian al.) 2014) is the earliest deep clustering method, il sequentially uses an autoencoder to perform feature mapping and K-means to cluster the latent embeddings. Beyond that, DCN (Yang eet al.) 2017) summed up K-means and autoencoder objectives and iteratively optimize their parameters, indirectly avoiding cluster collapse by minimizing autoencoder's reconstruction error. DEC (Xie et al.) 2016) developed self-supervised loss to iteratively refine autoencoder embeddings by confident predictions. Other than autoencoders, there are also deep clustering methods based on spectral clustering (Shaham et al.
2018
subspace clustering (Ji et al. 2017), mixture of experts (Tsai et al. 20211) elc. We suggest. the readers refer to [Zhou et al. 2022) for a comprehensive survey on deep clustering methods.
As described above, the basic assumption of doep clustering is that the Iearned representations are more suitable for clustering, i.e., more distinguishable from different clusters compared to raw features. Nonethe- less, we argue that the assumption hardly holds for previous deep clustering methods. First, the repre- scntation learning modules aim at preserving the scmantics (Kipf & Welling 2016 Bo et al. 2020 or
consistency (Bachman et al.] 2019 Ji et al. 2019) of the latent embeddings, or making the embeddings discriminative at instance level (Zhao et al. 2021a Tao et al. 2021 Devvrit et al. 2022) Second, clustering centroids and soft labels are inferred from the learned embeddings and (optionally) employed to finetune the embeddings. Unfortunately, none of the representation learning objectives contribute cluster-wise dis- crimination due to inaccessible ground truth labels, and hence the ambiguous clustering centroids and soft labels, leading to suboptimal clustering performance. In word, the chicken the egg causality dilemma prohibits conventional deep clustering from learning unambiguous clustering results.
3 Method
An attributed undirected graph dataset G &,, X) consists of a node set V, an edge set E, and a tabular data matrix X E Raxd Each node is associated with feature vector 2; E R. The edge set & can also be represented by an adjacency matrix A, where
f1. -f1
if E
An, -
(1)
hewwiss
Node clustering algorithms aim to partition the nodes into disjoint clusters without ground truth labels so that nodes from the same cluster are similar to each other, and nodes from different clusters are not.
Next, we give an overview of the proposed HPNC method and analysis how it differs from conventional deep clustering diagrams. After that, we introduce its pipeline and details of each submodule.
3.1 Overview
Intuitively, cluster prototypes should be as far as possible from each other, so that the data samples dis- tributed around them are more distinguishable from different clusters. Unlike previous works that infer a K-means-like fashion (Xie al., 2016 Devvrit
cluster prototypes from the learned node embeddings et al. 2022), we directly maximize their distances in a dala-independent approach. However, it's impossible to give the coordinates of the farthest pair of points in unconstrained Euclidean space, because the distances are up to infinity. Hence, the embedding space needs to be constrained to make the distances bounded. In this work, we simply restrict the embedding space to a unit hypersphere, which is widcly adopted and massively studied in various machine learning tasks (Davidson et al. 2018 Xu el al., 2019:: Wang & Isola 2020 Tan et al.) 2022). On a hypersphere manifold, the sum of pairwise distances of cluster prototypes is maximized when uniformly scattered, which implics the best separability among different clusters. Once obtaining the prototypes, their coordinates are fixed and no longer updated during training, so that their separability is always guaranteed and the cluster collapse issue is thoroughly avoided.
5

---

Published in Transactions on Machine Learning Research (01/2024)
3.2 Hyperspherical Prototype Node Clustering
Next, elaborate on the pipeline of HPNC. It merely consists of a representation learning module to map the nodes onto the same hypersphere manifold as the cluster prototypes, and a clustering module to push them close to corresponding prototypes. In this way, the intra-cluster distances are also naturally minimizod, leading to discriminate embeddingg. Moreover, the clustering labels can be directly retrieved from indexes of the nearest. prototypes for each node, without reliance on external clustering algorithms.
3.2.1 Pretrain Prototypes
The prerequisite step of HPNC is to obtain the coordinates of the cluster prototypes. Specifically, we propose to use uniformly scattered points on a unit-hypersphere as cluster protolypes. Uniformly placing e points on a m-dimensional unit-Lypersphere sm-1 so that the minimum distance between any two points gets maximized is known as the Tammes problem (Tammes 1930) in geometry. For S' (í.e., unit-circle on a 2D plane), this is easy as splitting it into e equal slices, and there are optimal solutions for S as well. Unfortunately, no such solutions exist for m 3 given an arbitrary (Musin & Tarasov 2015). To this end, we follow (Mettes et al. 2019 to adopt tradient-based approach. Concretely, we minimize the maximum pairwise cosine similarities by gradient descent:
CHP Σ max 14 | ||ا|||
m. jaj
j cej
(2)
where p4 E R are unnormalized prototypes. For convenience, we use p.: = Pr to denote n'-normalized prototypes. Thus, üú will uniformly scatter on sm-1 after convergence. It's worth noting that the optimiza- tion is very fast because there are just cx scalars to update. The pretraining is data-independent and thus only needs to be done once for each pair of (c, m). It's worthwhile to emphasize again that the prototypes are fixed after pretraining, they work as constants and are no longer updated in later steps of HPNC.
3.2.2 Representation Learning
The next step is to map the input graph into low-dimensional node embeddings. Without access to ground truth labels in a clustering context, an unsupervised objective is demanded to produce meaningful embed- dings. Motivated by recent advances in generative graph representation learning, we adopt masked graph autoencoder (GraphMAE) (Hou et al. 2022) as the representation learning backbone. We briefly introduce its objective in this section.
Masked feature reconstruction. Unlike conventional GAEs that reconstruct edges, GraphMAE devel- oped masked feature reconstruction strategy to recover masked node features X E Raxd To be specific, large random subset (e.g., 50%) of nodes Viaas V are sampled, and their node features are replaced by shared, trainable mask token. Then, the partially masked features and unaltered input graph are fed into multiple GNN layers to generate latent embeddings Z Raxm_ A re-mask strategy is applied to Z before feeding it to the decoder, which replaces the embeddings of Vmusk again, but with zeros. Denoting the reconstructed node features as X E Raxd, GraphMAE introduced scaled cosine error to minimize the reconstruction error as
Liea
1
Σ
(1
2;
L; [
7 1.
(3)
Vimask
During inference, the original node features without mask and re-mask strategies are used. As a result, it potentially leads to mismatch between training and interference because the mask token is not observed in the later stage. To mitigate this issuc, GraphMAE adopts a. 'random-substitnttion mothod that randomly substitutes node features of small subset of Vuask (e.g., 15%) with node features sampled from X.
Edge reconstruction. GraphMAE focuses on classification and the authors argue that feature recon- struction more beneficial than edge reconstruction (Hou et al.) (2022), so they propose to reconstruct node features only. However, reconstructing the edges A captures more node pair-level information (Liu et al.

---

Published in Transactions on Machine Learning Research (01/2024)
2023a) and thus beneficial for link prediction and clustering Pan et al. 2020 Hence, also reconstruct
the edges in addition to node leatures (Gao & Huang 2018 Salehi & Davuleu 2020 To be specific, we
adopt the widely used inner product decoder (Kipf & Welling 2016 to predict edges based on the latent embeddings:
Z 2v
Au,
(4)
||
|
where (()) is the sigmoid function. Then, we measure their discrepancies between ground truth edges by binary cross entropy as
Ledge
Elog log Ag, + Elog(1 - -Au.o) (U,D)E
Σlon
(5)
[8]
(u,D)Eε
where &l is the set of unconnected edges obtained by negative sampling and |g| [E). By applying just Ceea and Ledge, the GNN can generate semantically meaningful node embeddings, and clustering results can be obtained by applying external clustering algorithms such as K-means. Next, we describe how to further refine them for better clustering performance and obtain clustering labels without reliance on K-means.
3.2.3 Rotated Clustering Affinity
In order to prevent collapsed clusters and encourage large inter-cluster distance of the latent embeddings, we aim to map nodes around scattered cluster prototypes while leaving these prototypes unchanged. However, we empirically find that it's too challenging for the GNN to map nodes to appropriate prototypes. To mitigate this issue, we propose allowing the prototypes to rotate on the hypersphere. With a shared rotation matrix, their pairwise similaritics still remain unchangod so the large scparation property is preserved, while their coordinates can change to some extent. In other words, the GNN doesn't need learn rotate the nodes anymore it will converge easier. To be specific, we first apply L (--normalization to latent embeddings and denote them as द; I then the cosine similarity of the i-th node and j-th rotated prototype is simply their inner product 2 Ríj,, where R E Rmxm, R R = is the rotation matrix. Finally, we apply the softmax function to make them sum up to 1:
exp( 2 RØí) Qi Σ = exp(2, R
s.t. R
(6)
Hence, Q E Raxe can be interpreted as (soft) clustering labels. The rolation matrix R is learnable and updated by gradient descent]] After obtaining preliminary clustering affinities, we devise two schernes to refine them (hence the node embeddings) as we claborate below.
3.3 Scheme 1: HPNC-IM
The clustering affinities Q should be unambiguous and sharp for to be discriminative, so that intra- cluster distances are minimized and inter-cluster distances are maximized. To this end, we can employ the information mazimization (IM) loss (Gomes al.) 2010 Hu et al., 2017: Liang et al. 2020) encourage the cluster distributions individually unambiguous and globally uniform. Let X' and y denote the domains of data samples and cluster assignments, IM minimizes the following objective:
LI = - -
We initialize R identity matrix and enforce orthogonal constraint with PyToor built-in function utilut pattaaaaaaanettttinnn. wtt.rriiiattooooooooooaaaa orthogonal during training.
7

---

Published in Transactions on Machine Learning Research (01/2024)
where X E X and Y y denotes the random variables for data samples and cluster assignments, H-)) and H()))) are the marginal and conditional entropy, which can be estimated as
1 Σ 1=1
Dbl = HY) = h(ps(y)) h
= h
Qi:
= log c
DKL Ex, (po
(8)
Lent = H( = Ex ( = - (Qu.))
(9)
t=1
where Po(y) and (ull))) are the marginal and conditional probabilities over label values E {1...., cf modeled by a GNN with parameters 0, h(p) = EØ= Pj log denotes the entropy function, and is a vector with all ones.
Intuitively, maximizing Eq. (8) encourages the average cluster probabilities (po((a))) converge to the uniform distribution, data samples tend to be evenly assigned to different clusters. On the other hand, minimizing Eq. (9] encourages individual cluster probabilities po(y)æ;) to approximate the onc-hot distribution, so the cluster assignment becomes unambiguous, and the samples are pushed far from the decision boundaries. In summary, minimizing Eq. 7 trains the GNN to learn embeddings that agree with the cluster assumption (Chapelle Zieen, 2005), hence improving clustering performance. Combining Eqs.
3
5
and
( togother, the full objective of HPNC-IM
(10) Unlike previous works that require bootstrapping the autoencoder for hundreds of epochs with the recon- struction loss only, randomly initialize the network parameters and train HPNC-IM with the full objective from scratch.
LHPNC-IM Lisa aLodge - BL 7hent
Finally, clustering results are directly obtained as the indices of the largest Q without relying on external clustering algorithms such as K-means. Nonetheless, we'll show later in Section 4.2.2 that the clustering per- formance of Q and K-means on Z are very close, verifying that our objective actually leads to discriminative node embeddings.
3.4 Scheme 2: HPNC-DEC
In addition to the IM loss, we demonstrate that our proposed HPNC paradigm can also integrate with a simplified version of the DEC loss (Xie et al. 2016). As introduced in Section the original version of DEC is threo-stage process:
Employing an autoencoder to learn preliminary embeddings {*,....,,,, 2n from the input data.
Performing K-means on the embeddings to obtain clustoring centroids (pi....,pd then calculating the cluster assignment distribution Q with the Student's 's (-distribution as the similarity measurement between the embeddings and clustering centroids:
Qi = (1 - 1 - ل
(11)
(1+ Iz 1200
where a is the degree of freedom of the Student's t-distribution.
3. Defining an auxiliary distribution P by raising Q to the second power and normalizing it to sum up to
Pi Er Qus
P. E EE_ Q+.)
(12)
Then, their Kullback-Leiih (KT.) divergence is minimized to finetune the encoder network:
!
ΣΣΣ
Paj Pa. log
LDEC (KL(PI))
(13)
Q
T1
8

---

Published in Transactions on Machine Learning Research (01/2024)
P is sharper than Q because confident predictions (ones with large Qiy) are emphasized and unconfident predictions (ones with small Qi,) are suppressed. Hence, minimizing the KT, divergence will sharpen Q: leading to discriminative and cluster-aware embeddings. DEC iteratively performs 2) and 3) until conver- gence. However, the reliance on K-means and iterative optimization prohibits the potential use of DEC in an end-to-end deep learning pipeline.
We propose a crucial simplification to integrate DEC with the HPNC paradigm, that is replace the Student's edistributionnbasedd cluster assignment distribution (d.e., step 2) with Eq. ( Benefiting from the pipeline of HPNC, we longer need K-means because the clustering centroids are given in advance. The iterative optimization of centroids and encoder parameters is also discarded because the centroids are not updated during training HPNC.
Intuitively, DEC shares a similar purpose with the conditional entropy minimization part 1M (9) to make the target cluster assignment certain. However, docsn't consider balancing the scale of different clusters it may produce emply clusters, which is undesired when we would like to ensure that all elusters are assigned data samples. Thus, we simply employ the marginal entropy maximization part of IM ( to prevent degenerate solutions with empty clusters. Finally, the full objective of HPNC-DEC is as follows:
CHPNC-DEC Liea aLedge BLoal + LDEC.
(14)
As HPNC-IM, HPNC-DEC is also trained from randomly initialized network parameters by end-to-end gradient descent, without any form of pretraining. The loss functions of both schemes Eqs. (10) and (14) are fully differentiable and thus can be easily integrated into a deep learning pipeline and jointly optimized with other modules.
3.5 Complexity Analysis
When pretraining prototypes, the time complexity of calculating their pairwise similarities is Oc²m), and there are cm parameters to be updated, so the complexity of pretraining is Ocemmtpre) where tpre refers to the number of pretraining epochs. We empirically find that setting (pre to 3000 sufficient, so this step usually finishes half of minite.
The complexity of representation learning depends on the specific backbone, which is usually linear with the number of nodes and edges.
The complexity of calculating rotated clustering affinity (6 is O(nem + m²cc by applying rotation to pro- tolypes first and obtain their inner products with samples later. There are m² trainable parameters in R, and its orthogonal parametrization also O(m?). Hence, this step needs O(nn + m)cmt) in total, where is the number of training epochs.
The complexity of the clustering backbone also depends on the specific choice, which is O(net) for both IM and DEC that employed in this work.
In summary, the time complexity of HPNC without representation learning is Oce + (n + m) m)mnt). The time complexity of K-means clustering is O(nemt), so HPNC is comparable to applying K-means after representation learning.
4 Experiments
In this section, conduct extensive experiments to evaluate the effectiveness of the proposed HPNC paradigm. The experiments are designed with the aim to answer the following research questions:
RQ1:
What's the clustering performance of the proposed HPNC paradigm along with the two devised schemes?
RQ2:: How useful is the proposed rotated clustering affinity compared conventional cosine simi- larity?

---

Published in Transactions on Machine Learning Research (01/2024)
Table 1: Averaged clustering performance. The best results are in bold, second- best results are underlined.
Coru
CiteBeer
P Pubiked
ACM
DBLP
Mechod
ACC
NM
ART
ACC
NMI
ART
ACC
NMT
ARE
ACC
NMI
ART
ACC
NMI
ARI
GAR
53.320.2 a 40.740.3
30.9.0.2
43.340.4
16.30. a 20.3 63.140.4 26.920.3 21.7
56.541.4
55.441.0
59.54..1
61.221.2 30 $0.00000
220
VGAR
26.0
35.5
34/720.3
4..20.2
22.220.3
20.0 65
65.520.2
25.020.4
20.320.2
58.220.6
50
57.72007
58
28.0
20 20.1
17.200.1
MCAE
68.4go.3
45.0.n.3
68.52n.
$9.720.4
42/820.5
59.320.a
28.220.2
24.820.a
87.620.0
62.52000
67-120.0
76.920.1
48.82012
47 47.02222
ARGA
6
45.3
87.3
35.200
34.40.
080.0.5
27.840.4
20.0
88310.
63.4.0.
64.800
29.40099
26.0.0.9
61.020.5
26.2
26.220.
51.320.4
11.700.
$3.2000
57.8212
20.4
25.200.a
19.220.4
NeIRA
20.4
75.7an
1:2110
40.020.0
0,0.0.0
0.0.0.0
30/220
0.020.1
0.520.1
38.920.4
1.20.22
0.920.2
NetWaik
27.2
4.000.
24.220.2
9.620.2
10
35.822.
0.1900.8
0.200.3
37.920.4
1.020.4
0.20.0
34.920.0
2.020.8
1.8.0.0
AGC
68.920.5
537700
4
68.aan.a
41-120.4
41.20.
69.220.4
31.820.4
74920.0
40.220.0
21.200.0
69.420.1
3882200
26.20.
DARGG
10.4 4 52.1103
19.7
07.5
3977005
00.800.
20.610.2
27.7
80 80.11
20.2144
50 58.4
on lind 32.510.5 21.0....
ACE 72.6 5 68:1 a 60.3 70.0
44.020.4
46.420.5
60.040.0
20.1
81.4000
00.0.0
68 68.7
74.320.4
76. 76.1 46, 40.0go.a
47.0g0.8
SDCN 45.520.5 24.020.4
68.020.3
38.220.3
40.220.4
64.221.
#2.22..0
22.522.0
90 20.5002
00.320.1
73.220.4
08 08.1
30.3g1. 29.222.0
DCRN 63.4g0
40.210.4
80.3a0
70.9an.2
45.920.
47.0100
60.0a0.
92.2200
$14400
91.9002
71.010.
77.010.5
79.7100
49.0 63.0.0.5
GraphMAE
08.042.0 o 07.01111
69.000.
43.6005
4444005
04940.5
54.440.5
32940077
71:440.
73.840.
45.740. 43.8.0.7
SUBLIME 71.220 1 63.020.4 50.022.4
68.120.0
43.220.3
48.420.7
63.21a
27.421.4
24.342.
38.9.0.a
00.020.
70.120.7
64.822.0
30.222.0 18.122.4
NAFS 70.420.0 58.020.0
480200
71.820.0
45.22000
47.0200
70.320.0
$3.920.0
53/22000
81.220.1
51.420.
5292002
25 25.720.1 14.720.0
CONVERT 14.1 356111
50.0:12
68.4
41.6107
42/11.
67.111
30.01..5
20.3
56.4
55.3144
52.91
20.4 17:9
HPNC-I 74.120.5 58922.. 51.52000
72-420.5
48322077
48420.7
70.400.4
92 1201
72-120.0
78-120.0
80.020.4
49.820.4 94..
1Dx0. 59. 51. 2 7a.0 20.0 200.7 70.02000 23.1
33.3+1.4 92.9 10..0o011..0000 7..1 g0. 55.00000000000.....
Despite clustering assignments can be dircetly retrieved from the soft labels Q, what's the difference between the ones obtained by performing K-means on the embeddings 2?
RQ3:
RQ4:
What's the relationship between the centroids found by performing K-means on 2 and the rotated HPNC protolypes { [R 1
RQ5:
Is the separability of the learned embeddings really improved?
Basclines.
We compare HPNC with 13 classical and stato-of-the-art node clustering and node embedding
models, including GAE, VGAE (Kipf & Welling, 2016), MGAE (Wang et al. 2017 ARGA, ARVGA (Pan
et al.
2020
NetRA Yu et al.
2018b),
Walk Yu et al. (2018a). AGC (Zhang et al. 2019), DAEGC (Wang
ct al.
2019
AGE (Cui et al.)
2020 SDCN (Bo et al. 2020), DCRN (Liu et al. 2022b). GraphMAE (Hou
ct al.
2022
SUBLIME (Liu et al. 2022a). NAFS (Zhang et al. 2022), and CONVERT Yang et al. (2023).
Ne and Net Walk are random-wall walk-based node embedding met that utilize graph topology only, and
the rest competitors are designed to handle attributed graphs.
Evaluation protocol. For node embedding methods that cannot directly produce cluster assignments, we perform K-means on the learned embeddings obtain labels for comparison. K-means is reinitialized for 50 times to eliminate randomness, learned embeddings. We run all competitors five times with distinct random seeds and report the averaged results and standard deviations of the best epochs.
that their clustering performance solely depends on the quality of the
We present the selected datasets, evaluation metrics and implementation details in Appendices A.1 to respectively.
4.1 Node Clustering Performance Comparison (RQ1)
Table I reports the clustering performance of our method and other baselines. As shown in the table, both schemes of our proposed HPNC consistently achieved the best or sccond-best clustering performance on all five datasets, revealing the effectiveness of HPNC. In contrast, some competitors achieved appealing performance on certain datasets but failed on others. For instance, the ACC of AGE on Cora is only 1.6
10

---

Published in Transactions on Machine Learning Research (01/2024)
lower than that of HPNC-DEC, but it failed to handle DBLP, and the ACC is 5.0 lower, which is severe performance drop. DCRN's ACC on ACM is only 0.2 lower than that of HPNC-IM, but 10.7 lower on Cora. Generally speaking, the performance of HPNC is quite competitive compared with recent state-of-the-art models. Apart from clustcring performance, HPNC also enjoys the benefits from its end-to-end training strategy: Other strong baselines including but not limited to AGE, GraphMAE, and NAFS all rely on K- means or spectral clustering to obtain clustering labels, increasing hardware requirements on CPU /Pemmooory and prohibiting end-to-end training with other downstream tasks. Notably, HPNC-DEC seemss to perform slightly better than HPNC-IM, but their differences marginal (less than 0.5) in most cases owing to similar objectives between IM 9 and DEC 13
4.2
Ablation Study
In this section, we further perform ablation studies to confirm the effectiveness of individual design choices of HPNC.
4.2.1 Prototype Rotation (RQ2)
When calculating the affinities between nodes and cluster prototypes, we propose to introduce learnable rolation matrix R applied to these protolypes to allow them to rotate on the hypersphere manifold. To verify whether it's useful to assist the GNN to converge, we replace R in Eq. (6) with an identity matrix such that the coordinates of prototypes are strictly equal to their initial states, i.c., ones randomly initialized and refined by minimizing Eq. ( The clustering results are reported Table 2 where the first four rows do not apply rotation and the last four are their counterparts with rotation applied.
We observe that the clustering performances with prototype rotation outperform their counterparts without rolation. Specifically, HPNC-IM and HPNC-DEC have drastic 24.3 and 31.1 NMI drops on the Cora dataset after disabling prototype rotation. What's worse, the NMT on PubMed dataset without rotation is only 9.3 for HPNC-IM and 8.5 for HPNC-DEC, which means the clustering algorithm is not even working. In contrast, they give a plausible performance with rotation enabled, and the standard deviations are much lower. The results strongly suggest that allowing the prototypes rotate on the hypersphere manifold is indeed helpful and essential. The rcason that we consider pairwise distances of prototypes only in Eq. (2) while their coordinates are ignored. And as result, unsuitable random initialization of prototypes may fail to match up semantic centroids of node embeddings, leading to performance degradation. Our prototype rotation is thus also regarded as learning-based strategy to reduce sensitivity to initial states to stabilize training.
4.2.2 K-means Labels vs Soft Labels (RQ3)
The clustering results of our proposed HPNC are obtained by directly applying arg max to Eq. 6 so external clustering algorithms are not needed all. Nonetheless, the learned node embeddings 2 can be also used for clustering or potentially other downstream tasks. Here, feed them into K-means and report the clustering results in Table 2 (marked Z+KM). We observe that:
With prototype rotation applicd, the clustcring performance of K-means and soft labels are very comparable, which means HPNC can indeed guide the GNN lowards discriminative node embeddiings so that traditional clustering algorithms can also work well.
The clustering performance of both K-means and soft-labels degenerate without prototype rotation, but K-mcans works better than soft-labels in most cases. The reason might be that the autoencoder backbone preserved the clustering structure of the latent embeddings to some extent for K-means to discover, but their geometric centroids deviate far from the predefined prototypes so it's too challenging for HPNC to match them up.
To further investigate the consistency between K- K-means predictions and soft labels (HPNC-DEC is employed in this experiment), we calculate the proportion of them being the same and plot the results in Figure We
11

---

Published in Transactions on Machine Learning Research (01/2024)
Table 2: Clustering performance of HPNC with different ablation settings. Z+KM denotes K-means results of latent embeddings, Q denoles results of Eq.
Rotate prototype
Scheme
Target
Metric
Cora
CiteSeer
PubMed
ACM
DBLP
ACC
60.215.0
59.9_10.3
69.1
80.4
61.414.3
Z+KM
NMT
50.2
37.1
32.3
58.018.3
35.4
ARI
40.023.
36.728.4
31.3
59.9_11.5
37 37.644.3
HPNC-IM
ACC
49.3+4.0
11.912.0
52.526.7
87.542.5
63.945.1
NM1
34.6+7.2
26.3+3..
9.3+6.6
63.0+5.1
35.7+3.0
ARI
26.5+5.6
22.4+3.2
9.6+7.3
67.4+5.6
37.8+5.1
ACC
62.3
61.1
69.3
92.1
64.724.6
Z+KM
NM1
52.5+1.8
38.0+1.4
32.5=2.0
72.
36.3+2.6
ART
42.5
36.612.4
31.5
78.020.4
38.814.6
HPNC-DEC
ACC
44.9+2.6
53.543.5
52.0+6.4
92.1+0.1
64.22+4.65
Q
NMI
28.3+4.2
32.4+3.7
8.5
72.2
36.1
ART
20.013.2
27.814.0
8.3
78.1
38.414.7
ACC
71.4+2.9
70.1+1.6
69.7 79.75
92.1+0.1
80.0+0.4
Z+KM
NMI
57.521.6
45.420.9
33.520.6
72.02a.2
49.8
ARI
49.1+1.4
47.1+1.3
32.3
77.9
55.0+0.6
HPNC-IM
ACC
74.1
72.410.5
70.4
92.1 10.1
80.010.4
Q
NMI
58.910.6
46.3
34.620.7
72.1
49.8
ARI
51.540.9
48.4+0.7
33.5
78.1
51.940.6
ACC
70.6
70.6+2.1
69.8.0.5
92.2+0.1
80.2+0.6
Ž+KM
NMI
57.4+0.5
46.2+0.9
33.8+o.2
72.3+0.3
50.0+0.4
ARI
48.8
48.3+
32.6+0.8
78.3+0.2
55.1
HPNC-DEC
ACC
74.4
73.0
70.620.9
92.3+0.1
80.1
NMT
59.410.9
46.910.7
33.1
72.440.3
49.910.5
ARI
51.941.2
49. 49.7.0.7
33.3
78.4
55.040.7
HPNC-IM
HPNC-DEC
same prediction
same prediction
H
0.4
0.2
w/ rot
w/ rot w/o rot
w/o rot
0.0
Cora
CiteSeer PubMed
ACM
DBLP
Cora
CiteSeer PubMed
ACM
DBLP
Figure2 2: The proportion of Eq. 6 and K-means making the same predictions.
observe that they are highly consistent on all datasets when protolype rolation is applied but deviate far from each other without This again confirms our analysis before. To summarize, prototype rotation is a very important component of our proposed HPNC paradigm. It not only helps HPNC to match semantic and predefined prototypes but also leads more discriminative latent embeddings for potential as input of other downstream algorithms.
12

---

Published in Transactions on Machine Learning Research (01/2024)
1:20 6. 123
E33
135
L33
L11L 610
6:0
-20
124
3:35
1:
LS4
1.00
911
Cora
(b) CiteSeer
(c) PubMed
(d) ACM
(e) DBLP
Figure 3: Cosine distances between rotated prototypes of HPNC and K-means centroids.
(a) GAE
(b) AGE
(c) DCRN
(d) CraphMAE
(c) HPNC
Figure t-SNE visualization of learned latent embeddings on CiteSeer datasct. Pentagrams in HPNC
denote cluster protolypes. HPNC embeddings are the most discriminative and separable among all the competitors.
4.2.3 K-means Centroids vs Prototypes (RQ4)
To investigate the relationships between the clustcring controids inferred from the latent embeddings by K-means and HPNC's (HPNC-DEC is employed this experiment) rolated protolypes (Rūj)ÿī=: we calculate their pairwise cosine distances and plot the confusion matrices in Figure We observe that K-means centroids and rotated prototypes corresponding to the same cluster distribute very close to cach other, which means they are consistent. On the other hand, the pairwise distances between centroids of different clusters are nearly the same, which means different clusters are successfully scattered on the hypersphere manifold. Since K-means centroids are inferred from the latent embeddings, we conclude that HPNC indeed successfully mapped nodes from different clusters to their corresponding prototypes, and made them uniformly distribute on the hypersphere manifold to have large margins.
4.3 Visualization (RQ5)
We employ t-SNE (Van der Maaten Hinton, 2008 to visualize the learned latent embeddings of HPNC (HPNC-DEC employed in this experiment) on the CiteSeer dataset and compare it with different bascline methods. The results are illustrated in Figure 4 In addition, the cluster prototypes of HPNC are marked in pentagrams. It's obvious that the embeddings learned by HPNC are the most discriminative and separable among all the competitors. Also, data samples from the same cluster distribute evenly around corresponding prototypes, which is a desired property of our motivation.
5 Conclusion
This paper presents a novel HPNC paradigm for end-to-end node clustering. In HPNC, uniformly scattered points on a unit-hypersphere are regarded as cluster prototypes. Then, a graph autoencoder is employed to encode the nodes onto the same manifold with the guidance to push them close to the prototypes. Unlike previous works that overlook the separability of learned embeddings, HPNC explicitly maximizes their inter- cluster distances to provide sufficient discriminative power. Moreover, HPNC does not rely external
13

---

Published in Transactions on Machine Learning Research (01/2024)
clustering algorithms to uncover clustering labels and its objective is fully differentiable, which enables its use a module in deep learning pipelines. We devise two different schemes based on HPNC to demonstrate its flexibility to work with different clustering backbones. Extensive experiments on real-world graph datasets strongly confirm the effectiveness of HPNC.
Acknowledgments
This work was supported in part by the China Postdoctoral Science Foundation under Grant 2022M722532.
References
Philip Bachman, R. Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. In NewrIPS, pp. 15509 15519, 2019.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Newrul Comput., 15(6):1373-1396 2003.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In WWW, pp. 1400-1410, 2020.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In CIKM, pp. 891-900, 2015.
Olivier Chapelle and Alexander Zien. Semi-supervised classification by low density separation. In AISTATS, 2005.
Ganqu Cui, Jie Zhou, Cheng Yang, and Zhiyuan Liu. Adaptive graph encoder for attributed graph embed- ding. In KDD, pp. 976-985, 2020.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey network embedding. IEEE Trans. Knowl. Data Eng., (1833883--55, 2019.
Tim R. Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M. Tomczak. Hyperspherical variational auto-encoders. In UAI, pp. 856 865, 2018.
Fnu Devvrit, Aditya Sinha, Inderjit S Dhillon, and Pratcek Jain. S3GC: Scalable sclf-supervised graph clustering. In NeurIPS, pp. 3248 3261, 2022.
Hongchang Gao and Heng Huang. Deep altributed network embedding. In IJCAI, pp. 3364 3370, 2018.
Ryan Gomes, Andreas Krause, and Pietro Perona. Discriminative clustering by regularized information maximization. In NIPS, pp. 775-783, 2010.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp. 855 864, 2016.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In ICML, volume 119, pp. 4116-4126, 2020.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmac: Self-supervised masked graph autoencoders. In KDD, pp. 594 604, 2022.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In ICML, pp. 1558-1567, 2017.
Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and lan D. Reid. Deep subspace clustering networks. In NIPS, pp. 24-33, 2017.
Xu Ji, Andrea Vedaldi, and João F. Henriques. Invariant information clustering for unsupervised image classification and segmentation. In ICCV, pp. 2019.
14

---

Published in Transactions on Machine Learning Research (01/2024)
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/1611.07308,, 2016.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Kliepera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Tn NewrIPS, pp. 13333 13345, 2019.
Jian Liang, Dapeng Hu, and Jiashi Feng. Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation. In ICML, pp. 6028 6039, 2020.
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. In WWW, pp. 1392-1403, 2022a.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip S. Yu. Graph sell-supervised learning: A survey. IEEE Trans. Knowl. Data Eng., 35(6):5879 5900, 2023a.
Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. Deep graph clustering via dual correlation reduction. In AAAI, pp. 7603 7611, 2022b.
Yue Liu, Ke Liang, Jun Xia, Sihang Zhou, Xihong Yang, Xinwang Liu, and Stan Z. Li. Dink-net: Neural clustering on large graphs. In JCML, 2023b.
Pascal Mettes, Elise van der Pol, and Cees Snoek. Hyperspherical prototype networks. In NewrIPS, pp. 1485-1495 2019.
Yair Movshovitz-Attiss, Alexander Toshev, Thomas K. Leung, Sergey lofle, and Saurabh Singh. No fuss 2017.
distance metric learning using proxies. In ICCV, pp.
Oleg R Musin and Alexey S Tarasov. The tammes problem for 14. Eap. Math., 24(4):460-463 2015.
Shirui Pan, Ruiqi Hu, Sai-Fu Fung, Guodong Long, Jing Jiang, and Chengqi Zhang, Learning graph embed- ding with adversarial training methods. IEEE Trans. Cybern., (446))2475-222 2487, 2020.
Jiwoong Park, Minsik Lee, Hyung Jin Chang, Kyuewang Lee, and Jin Young Choi. Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In ICCV, pp. 6518 6527, 2019.
Namyong Park, Ryan A. Rossi, Eunyee Koh, Iftikhar Ahamath Burhanuddin, Sungchul Kim, Fan Du, Nesreen K. Ahmed, and Christos Faloutsos. CGC: contrastive graph clustering forcommunity detection and tracking. In WWW, pp. 1115 1126, 2022.
Bryan Perozzi, Rami A1-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In KDD, pp. 701 710, 2014.
Amin Salehi and Hasan Davulcu. Graph attention auto-encoders. In ICTAI, pp. 989 996, 2020.
Uri Shaham, Kelly P. Stanton, Henry Li, Ronen Basri, Boaz Nadler, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks. In ICLR, 2018.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In ICLR, 2020.
Pieter Merkus Lambertus Tammes. On the origin of number and arrangement of the places of exit on the surface of pollen-grains. Recueil Trau. Bot. Néerl,, (7(1):1-84 1930.
Cheng Tan, Zhangyang Gao, Lirong Wu, Siyuan Li, and Stan Z. Li. Hyperspherical consistency regulariza- tion. In CVPR, pp. 7234 7245, 2022.
Yaling Tao, Kentaro Takagi, and Kouta Nakata. Chstering-friendlly representation learning via instance discrimination and feature decorrelation. In ICLR, 2021.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tic- Yan Liu. Learning deep representations for graph clustering. In AAAT, pp. 1293-1299, 2014.
Tsung Wei Tsai, Chongxuan Li, and Jun Zhu, Mice: Mixture of contrastive experts for unsupervised image clustering. In TCLR, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9(11), 2008.
Petar Velickovie, William Fedus, William L. Hamilton, Pietro Lió, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In TCLR, 2019.
Ulrie von Luxburg. A tutorial on spectral clustering. Stat. Comput., 17(4):395-41 -16,,416 2007.
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. MGAE: marginalized graph autoencoder for graph clustering. In CIKM, pp. 889-898, 898, 2017.
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chenggi Zhang. Attributed graph clustering: A deep attentional embedding approach. In IJCAI, pp. 3670 3676, 2019.
Chun Wang, Bo Han, Shirui Pan, Jing Jiang, Gang Niu, and Guodong Long. Cross-graph: Robust and unsupervisod embodding for attributed graphs with corrupted structure. In ICDM, pp. 571-580, 2020.
Jiang Wang, Yang Song, Thomas Leung, Chuck Rosenberg, Jingbin Wang, James Philbin, Bo Chen, and Ying Wu. Learning fine-grained image similarity with deep ranking. In CVPR, pp. 1386-1393, 2014.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformily the hypersphere. In ICML, pp. 9929 9939, 2020.
Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised feature learning via non-paraectric instance discrimination. In CVPR, pp. 3733 3733-3742, 2018.
Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z. Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In WWW, pp. 1070-1011 1079, 2022.
Junyuan Xie, Ross B. Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In TCML, pp. 478-487, 2016.
Ruijia Xu, Guanbin Li, Jihan Yang, and Liang Lin. Larger norm more transferable: An adaptive feature norm approach for unsuperviscd domain adaptation. In ICCV, pp. 1436-1435, 2019.
Bo Yang, Xiao Fu, Nicholas D. Sidiropoulos, and Mingyi Hong. Towards k-means-friendly spaces: Simulta- neous deep learning and clustering. ICML, pp. 3861 3870, 2017.
Xihong Yang, Cheng Tan, Yue Liu, Ke Liang, Siwci Wang. Sihang Zhou, Jun Xia, Stan Z. Li, Xinwang Liu, and En Zhu. CONVERT: contrastive graph clustering with reliable augmentation. In ACM Multimedia, pp. 319-327, 2023.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supe learning with graph embeddings. In ICML, pp. 40-48, 2016.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In NewrIPS, 2020.
Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In KDD, pp. 2672-2672222 2681, 2018a.
Wenchao Yu, Cheng Zheng, Wei Cheng, Charu C. Aggarwal, Dongjín Song, Bo Zong, Haifeng Chen, and Wei Wang. Learning deep network representations with adversarially regularized autoencoders. In KDD, pp.
2018b.
Wentao Zhang, Zeang Sheng, Mingyu Yang, Yang Li, Yu Shen, Zhi Yang, and Bin Cui. NAFS: A simple yet tough-to-beat baseline for graph representation learning. In ICML, pp.
2022.
16

---

Published in Transactions on Machine Learning Research (01/2024)
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. In IJCAT, pp. 4327-4333, 2019.
Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering. In IJCAI, pp. 3434-3440, 2021a.
Wenliang Zhao, Yongming Rao, Ziyi Wang, Jiwen Lu, and Jie Zhou. Towards interpretable deep metric learning with structural matching. In ICCV, pp. 9867 9876, 2021b.
Yizhen Zheng, Shirui Pan, Vincent C. S. Lee, Yu Zheng, and Philip Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In NeurIPS, 2022.
Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Zhao Li, Jiajun Bu, Jia Wu, Xin Wang, Wenwu Zhu, and Martin Ester. A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. CoRR, abs/2206.075773 2022.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive represen- tation learning. CoRR, abs/2006.04 2020.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. In NewrIPS Datasets and Benchmarks, 2021.
A Appendix:
Experimental Setups
A.1 Datasets
We evaluate the clustering performance on five widely adopted attributed graph datasets: Cora, CiteSeer, PubMed Yang et al. 2016 ACM and DBLP (Bo et al. 2020
Cora is a citation graph of number of machine-learning papers divided into seven research topics. Each edge represents a citation.
CiteSeer is a citation graph of scientific publications classified into one of six machine-learning areas. Each edge represents a citation.
PubMed is citation graph from the PubMed database, where nodes papers about three diabetes types and edges are citations among them.
ACM is paper graph from the ACM Digital Library. The papers are categorized into three research areas. There is an edge between two papers if they written by the same author.
DBLP is an author graph from the DBLP computer science bibliography. Edges denote co-authorship between two authors. The authors are categorized into four research areas.
Statistics of these datasets summarized in Table g
A.2 Evaluation Metrics
We employ three widely adopted metrics to evaluate node clustering performance, including clustering ac- curacy (ACC), normalized mutual information (NMI), and adjusted Rand index (ART). The larger values are, the better the clustering performance.
httpe://gthuuu.cm//tiiiyuou////p
com/ http://b..commm/aty/////////
17

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: Statistics for benchmark datasets.
Dataset
Nodes
Edges
Clusters
Dimension
Cora
2708
5278
7
1433
CiteSeer
3327
4552
3703
PubMed
19717
44324
3
500
ACM
3025
13128
3
1870
DBLP
4057
3528
4
334
A.3 Implementation Details
We implement our proposed HPNC in PyTorch 2.0 and PyG 2.3.0 and use GraphGym YYou et al. 2020 for experiment management to ensure reproducibility. Throughout the experiments, the encoders of HPNC are all composed of two GAT layers with 4 128d attention heads and dropout probability 0.1 for attention coefficients. We also apply dropout with probability 0.2 between the GAT layers and use PRcLU as the activation function. The decoder single GAT layer without non-linear activalion. The coefficients a, B and y Eqs. (10) and (14) are tuned by random search within the following ranges: a e (0.0,0.01, 0.02), 8, y E (0.0, 0.1]. Detailed hyperparameter settings be found in YAML configuration files from our code.
18


Reviews:
[{"review_id": "5QCQITUb2m", "reviewer": "Reviewer_mTj2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ It is interesting to improve node embeddings for node clustering by enforcing small intra-cluster distances and large inter-cluster distances. The proposed method looks reasonable to me.\n\n+ Experiments on 5 datasets are conducted to show that HPNC outperforms many baseline methods. \n\n+ The presentation is overall good. The motivation is clearly described and the paper is easy to follow.\n\nI have some concerns regarding the method and experiments. \n- The novelty of this paper is incremental to me. Leveraging loss to encourage small intra-cluster distances and large inter-cluster distances is a common idea for improving the clustering algorithm. In addition, it is relatively straightforward that incorporating clustering-based loss into self-supervised loss will improve the clustering performance. \n\n- The improvement of HPNC over baseline methods is not significant. In many cases, the improvements are less than 1%. In addition, the authors should consider comparing more recent graph self-supervised learning baseline methods. Moreover, in the ablation study, it is necessary to report the results of all metrics rather than just NMI. It is also necessary to report the standard deviations of the results over several repeated experiments. \n\n- The current experimental datasets are relatively small. It is better to consider large-scale graph datasets, such as large datasets in OGB.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new node clustering method called Hyperspherical Prototype Node Clustering (HPNC). The general idea is to leverage the clustering-oriented loss with the learned node embeddings to encourage small intra-cluster distances and large inter-cluster distances. Some experiments are conducted to demonstrate the effectiveness of HPNC compared with many baseline methods. Ablation study and analytical results are also provided.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In my opinion, the novelty of this work is incremental and the experiments should be improved. Please see the above weakness for any changes.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EOejqlla9U", "reviewer": "Reviewer_hnq8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\n1) The work identifies the problem that clusters need to be separated and then devises optimization terms to encourage separation. \n\n2) The experiment results are generally solid. They verify the hypothesis in the work. \n\n\nWeakness:\n\nThe paper writing should be improved. Here is a list of detailed comments. \n1) Section 3.1 should be merged into the Introduction and Related Work sections. \n2) Section 3.2.2 is mostly from previous work and not this work's contribution. It should be in a \"Background\" section\n3) Equation (6) it is unclear how R^TR = I is enforced. \n4) Section 3.3 introduces new notations y and Q. They should be defined at the problem definition. \n5) In figure 1, the word \"disambiguate\" is not even used in the text. Does it mean \"sharpening\"?\n6) The word \"prototype\" is not great. It's meaning is \"a first, typical or preliminary model of something, especially a machine, from which other forms are developed or copied.\", which doesn't seem to be appropriate for a cluster center. Maybe \"cluster centers\" are better?\n7) The experiment settings should be included in the text because they are important for the analysis of the results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new method for node clustering tasks. The main innovation of the work is to enforce cluster separation in the optimization objective. Two measures are used to achieve separation:  1) explicitly setting cluster centers and maximizing distances between them; and 2) encouraging the sharpness of the cluster membership matrix. The results indicate the proposed method achieves clear separation and better clustering performance than previous methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please check the list of comments in the \"Weakness\" section.", "broader_impact_concerns": "No concerns detected.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4nZb0Muuhh", "reviewer": "Reviewer_AWXy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- HPNC enhances the inter-cluster separability of learned node embeddings, which can lead to improved clustering performance.\n- The method constrains the embedding space to a unit-hypersphere, which enables the scattering of cluster prototypes over the space with maximized pairwise distances.\n- HPNC employs a graph autoencoder to map nodes onto the same hypersphere manifold, which can simplify the clustering process.\n- The proposed method is an end-to-end clustering paradigm, which eliminates the need for additional clustering algorithms such as K-means or spectral clustering.\n- HPNC has demonstrated competitive clustering performance compared to recent state-of-the-art models on various real-world datasets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces an approach to deep node clustering called Hyperspherical Prototype Node Clustering (HPNC). The proposed method enhances the inter-cluster separability of learned node embeddings by constraining the embedding space to a unit hypersphere. The paper provides a detailed explanation of the HPNC paradigm and its benefits over existing approaches to deep node clustering. It also includes experimental results demonstrating the superior clustering performance of HPNC on various real-world datasets. Overall, the paper presents an interesting technique that has the potential to advance the field of deep node clustering. However, the novelty of the idea is not encouraging. Basically, \"enhancing the inter-cluster separability\" is a very traditional research point for clustering. It is not clear what is the very unique part of node clustering.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Cons:\n- The major concern is the novelty of the idea is not encouraging. Basically, \"enhancing the inter-cluster separability\" is a very traditional research point for clustering. It is not clear what is the very unique part of node clustering. The authors are suggested to include more description on this point.\n- Some unsupervised node embedding approaches are not cited and compared, such as:\nNetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks. KDD'18\nLearning Deep Network Representations with Adversarially Regularized Autoencoders. KDD'18\nIt is suggested to have a more thorough literature survey on the graph embedding part.\n- The paper does not provide a detailed comparison of the computational efficiency of HPNC compared to other clustering algorithms.\n- The paper does not provide a detailed analysis of the robustness of HPNC to noise or outliers in the data.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers agree that this paper is technically correct, and I am confident it is of interest to the TMLR audience. 2 out of 3 reviewers recommended to accept the paper, the 3rd reviewer leaned towards rejection on the grounds of 1) novelty 2) datasets and 3) marginal improvement. After careful consideration I decided to accept the submission for publication, mainly because even though all reviewers noticed to some extent that the novelty may be limited, the TMLR guidelines clearly state that **Papers should be accepted if they meet the criteria [claims/evidence and audience] , even if the contribution or significance of the work is modest. **. I believe that the submission meets both these criteria and hence should published in TMLR. 

Please prepare the final version of the manuscript, while doing so, I suggest renaming the new section 3.5 to "Complexity Analysis" (instead of  "Complexity Analyses").
Decision: Accept (poster)