CONGREGATE: Contrastive Graph Clustering in Curvature Spaces

1 Introduction

Graph clustering aims to group nodes into different clusters so that the intra-cluster nodes share higher similarity than the inter-cluster ones, receiving continuous research attention [Yin et al., 2017]. The state-of-the-art clustering performance on graphs has been achieved by deep clustering methods in recent years [Liu et al., 2023; Wang et al., 2019; Li et al., 2020]. Meanwhile, we find that several important issues on deep graph clustering still largely remain open.

The first issue is on the geometric graph clustering. In the literature, classic concepts such as modularity [Li et al., 2022], conductance [Duval and Malliaros, 2022] and motifs

[Jia et al., 2019] are frequently revisited. Little effort has been devoted to clustering from a geometric perspective. In the Riemannian geometry, Ricci curvatures on the edges can help determine the cluster boundary [Jost and Liu, 2014], thereby showing the density and clustering behavior among the nodes. However, graph clustering has rarely been touched yet in Riemannian geometry, since it lacks a promising Riemannian space for graph clustering. Most existing graph representation spaces present a single curvature radius, independent of nodes/edges [Xiong et al., 2022b; Chami et al., 2019; Law, 2021], and cannot allow for a closer look over the various curvatures for graph clustering. Also, typical clustering algorithms in Euclidean space (e.g., K-means) cannot be directly applied as an alternative, due to the inherent difference in geometry. Consequently, it calls for a new Riemannian curvature space, supporting a fine-grained curvature modeling for geometric clustering.

The second is on the unsupervised learning. Deep models are typically trained by the supervisions while graph clustering is unsupervised by nature. Recently, the contrastive clustering without external supervision draws dramatic attention [Park et al., 2022; Devvrit et al., 2022; Li et al., 2022]. In the line of contrastive graph clustering, the issues of augmentation and hard samples are still unclear in general. Unlike the easily obtained augmentations on images, graph augmentation is nontrivial [Hassani and Ahmadi, 2020]. In addition, the noise injected in this process usually requires a careful treatment to avoid misleading on graph clustering [Gong et al., 2022]. Robinson et al. [2021] point out the hardness unawareness of typical loss function such as InfoNCE. Hard negative samples have shown to be effective for graph contrastive learning [Xia et al., 2022], but little effort is made to its counterpart, hard positive samples. In fact, the hard positives in our context are the border nodes of a cluster, and plays a crucial role in clustering performance. Unfortunately, hard sample mining in curvature space largely remains open.

Motivated by the observations above, we rethink the problem of graph clustering from the geometric perspective, and make the first attempt to address graph clustering in a novel Curvature Space, rather than traditional single curvature ones, with an advanced contrastive loss.

To this end, we propose a novel end-to-end contrastive graph clustering model in curvature spaces (CONGREGATE), where we approach graph clustering via geometric clustering with Ricci curvatures so that positive Ricci curvature groups the nodes while negative Ricci departs them in spirit of the famous Ricci flow. To address the fine-grained curvature modeling for graph clustering (the first issue), we introduce a novel Heterogeneous Curvature Space, which is a key innovation of our work. It is designed as the product of learnable factor manifolds and multiple free coordinates. We prove that the proposed space allows for different curvatures on different regions, and the fine-grained node curvatures can be inferred to accomplish curvature modeling. Accordingly, we generate deep representations via the product of Graph Convolutional Nets (GCNs), where fully Riemannian GCN is designed to address the inferior caused by tangent spaces. To address the unsupervised learning (the second issue), we propose a rewighted geometric contrastive approach in our curvature space. On the one hand, our approach is free of augmentation as we contrast across the geometric views generated from the proposed heterogeneous curvature space itself. On the other hand, we equip a novel dual reweighting to the Node-to-Node and Node-to-Cluster contrastive losses to train the clusters. In this way, we pay more attention to both hard negatives and hard positives when maximizing intra-cluster similarity and minimizing inter-cluster similarity.

To sum up, the noteworthy contributions are listed below:

• Problem. We rethink the graph clustering from geometric respective. To the best of our knowledge, we are the first to introduce the heterogeneous curvature space, supporting fine-grained curvatures modeling, to the problem of graph clustering.
• Methodology. We propose an end-to-end CONGREGATE free of graph augmentation, in which we approach geometric graph clustering with the reweighting contrastive loss in the proposed heterogeneous curvature space, paying attention to hard positives and hard negatives.
• Experiments. We evaluate the superiority of our model with 19 strong competitors on 4 datasets, examine the proposed components by ablation study, and further discuss why Ricci curvature works.

2 Preliminaries

In this section, we first introduce the necessary fundamentals of Riemannian geometry for better understanding our work, and then formulate the studied problem in this paper. In short, we are interested in the end-to-end graph clustering in a novel curvature space.

2.1 Riemannian Geometry

Manifold. A Riemannian manifold (M, g) is a smooth manifold M endowed with a Riemannian metric g. Every point x ∈ M is associated with a Euclidean-like tangent space TxMon which the metric g is defined. The exponential map projects from the tangent space onto the manifold, and the logarithmic map does inversely [Lee, 2013].

Curvature. For each point x in the manifold, it is coupled with a curvature cx describing how the space around x derives from being flat and a corresponding curvature radius

1 |cx| . When cx is equal everywhere in the manifold, it induces a homogeneous curvature space (a.k.a. constant curvature space) with a simplified notation of scalar curvature c. Concretely, it is said to be hyperbolic H if c < 0, and hyperspherical S if c > 0. Euclidean space R is special case with c = 0. On the contrary, heterogeneous curvature space refers to a manifold whose curvatures on different regions are not the same, which is a more practical yet challenging case.

2.2 ProblemFormulation

In this paper, we consider the node clustering on attributed graphs. An attributed graph is described as a triplet of G = (V, E,X), where V = {v1, v2, · · · , vN} is the set ofN nodes, E ⊂ V × V is the edge set, and X ∈ RN×F is the attribute matrix. Let K denote the number of node clusters. The nodeto-cluster assignment is described as the cluster membership vector πi ∈ RK attached to node vi. πi is a stochastic vector adding up to 1, whose k-th element πik is the probability of vi belonging to cluster k. Now, we formulate the problem of Geometric Graph Clustering in Generic Curvature Space.

Problem Definition. Given G = (V, E,X), the goal of our problem is to learn an encoder f : vi → [zi,πi], ∀v ∈ V that 1) directly outputs cluster membership πi (end-to-end) so that the nodes are more similar to those grouped in the same cluster than the nodes in different clusters and 2) the node encodings in the generic curvature space zi ∈ M, supporting the geometric graph clustering.

Distinguishing with the prior works, we rethink the problem of graph clustering from the geometric perspective, and make the first attempt to study graph clustering in a novel Curvature Space, rather than traditional single curvature ones.

Notations. The lowercase x, boldfaced x and uppercase X denote scalar, vector and matrix, respectively.

3 Methodology: CONGREGATE

We propose an end-to-end contrastive graph clustering model (CONGREGATE) where we introduce the first curvature space to graph clustering, a key innovation of our work. In brief, we directly learn the node clusters by training randomly initialized centroids {φk}k=1,··· ,K in a novel curvature space. φk is the centroid of cluster k. The soft assignment of node vi to cluster k is given as πik = Normalize(δ(zi, φk)), where the similarity δ(zi,φk) = exp(-dP(zi,φk)) and dP is distance metric in our curvature space. Softmax normalization is applied so that πi adds up to 1.

We illustrate our model in Figure 1. Concretely, we present a geometric clustering approach with Ricci curvatures (Sec 3.1), introduce the novel heterogeneous curvature space (Sec 3.2), and train cluster centroids by the proposed reweighted contrastive loss in our curvature space (Sec 3.3).

3.1 Geometric Clustering with Ricci Curvature

In CONGREGATE, we address graph clustering from a geometric perspective, more concretely, the notion of Ricci curvature, and formulate a novel geometric clustering loss.

We first discuss why Ricci curvature clusters nodes. Let us begin with its definition [Jost and Liu, 2014; Lin et al., 2011]:

Given a graph with mass distribution mλi (·) on vi's neighbor nodes, Ricci curvature Ric(i, j) of edge (vi, vj) is defined as

and W(mλi ,mλj ) is the Wasserstein distance between the mass distributions on nodes, where mλi (·) is defined as

where dG is the length of shortest path on the graph, and λ is a control parameter. The intuition is that the Ricci curvature of an edge describes the overlap extent between neighborhoods of its two end nodes, and thus signifies the density among nodes. Specifically, if vi and vj belong to different clusters, it is costing to move the distribution mλi to mλj due to fewer common neighbors. The less overlapped neighborhoods present large W(mλi ,mλj ) and negative Ric(i, j). On the contrary, intra-cluster edges are most positively curved, and the nodes within the cluster are densely connected.

With the observation above, we connect the Ricci curvature on edges to the density among the nodes. Then, intra-cluster density is formulated as summing the Ric(i, j) whose end nodes belong to the same cluster,

Similarly, the inter-cluster density is given as

Consequently, the Ricci loss is defined as follows,

where α0 is a weighting coefficient. The rationale of our formulation is that we maximize node density within the cluster while minimizing the density across different clusters.

Connection to the Famous Ricci Flow. In differential geometry, the Ricci flow approach is to divide a smooth manifold into different regions based on the Ricci curvature. The regions of large positive curvature shrink in whereas regions of very negative curvature spread out [Chen and Zhu, 2005]. Analogy to the smooth manifold, we divide a graph into different node clusters where positive Ricci curvature groups the nodes and negative Ricci departs them.

Ni et al. [2019]; Sia et al. [2019] leverage Ricci curvatures to group nodes, but they do not consider the end-to-end clustering in a curvature space, essentially different from our setting. We are the first to introduce the curvature space to the problem of graph clustering to the best of out knowledge.

3.2 Constructing Heterogeneous Curvature Space

We are facing a challenging task: constructing a new curvature space for the geometric graph clustering. Most existing graph curvature spaces present as a single curvature radius (either the typical hyperbolic, spherical and Euclidean spaces or the recent ultrahyperbolic and quotient manifolds [Xiong et al., 2022b; Law, 2021]). However, rather than a single curvature, geometric clustering requires a closer look over the various fine-grained curvatures on the graph.

A core contribution of our work is that we introduce a novel heterogeneous curvature space, bridging this gap. In a nutshell, it is a product space of learnable factor manifolds and multiple free coordinates, as shown in Fig 1 (b).

A Novel Product Manifold

We introduce the intuition of our idea before the formal theory. The graph curvature spaces above are restricted by a fixed norm, thus yielding a single curvature radius. We enrich the curvatures by producting a single radius space with multiple free coordinates that do not have any norm restriction. (A more theoretical rationale based on rotational symmetry [Giovanni et al., 2022] is given in Appendix.) Our heterogeneous curvature space PH is constructed as follows,

where ⊗ denotes the Cartesian product. It is a product of M restricted factors and a free factor of d0 free coordinates. In the product space, a point z ∈ PH is thus expressed as the concatenation of its factors zm ∈ Mcm,dm m with the combinational distance metric of d2P (x, y) = ∑m d2cm (xm, ym).

A restricted factor Mcm,dm m is defined on the manifold,

with the metric inner product 〈z, z〉cm = sgn(cm)z2 t +z⊤ s zs, where sgn is the sign function. cm and dm denote the curvature and dimension, respectively. The induced norm restriction is given as ‖z‖2cm = 〈z, z〉cm . zt is the 1st dimension, and is usually termed as t-dimension. The north pole is 0 = (|cm|- 12 , 0, · · · , 0). The closed-form distance dcm , logarithmic logcm z and exponential maps expcm z are derived in Skopek et al. [2020]. The free factor Rd0 looks Euclidean like, but in fact we inject the rotational symmetry in it. The closed-form distance d0 is given in [Giovanni et al., 2022]. We do not use its logarithmic/exponential maps in our model.

We prove that the proposed PH has heterogeneous curvatures, i.e., it allows for different curvatures on the different regions. Supporting curvature heterogeneity is the foundation of geometric clustering. We start with the concept below.

Definition (Diffeomorphism [Lee, 2013]). Given two manifolds M1 andM2, a smooth map ϕ : M1 →M2 is referred to as a diffeomorphism if ϕ is bijective and its inverse ϕ-1 is also smooth. M1 and M2 are said to be diffeomorphic and denoted as M1 ≃M2 if there exists a ϕ connecting them.

Proposition 1 (Curvature Heterogeneity). ∀d0 > 1, ∀cm, there exists a diffeomorphism of PH ≃ (⊗Mm=1Mcm,dm m ⊗ M0,d )⊗RS where a point zi's curvature is a map ψ((zi)[S], c1, · · · , cM) w.r.t. its location with the differential operator

for some smooth ρ and (zi)[S] is the coordinate of RS, where M0,d ⊗RS = Rd0 and RS is the axis for rotational symmetry.

Fine-grained Curvature Modeling for Graph Clustering Here, we derive the fine-grained node-level curvature in our product space. With the definition of Diffeomorphism above and Proposition 1, the curvature ci of zi ∈ PH can be derived from the map (ϕ ◦ ψ)((zi)[S], c1, · · · , cM) and the differential operator on ρ. That is, zi's curvature is inferred via a map regarding the curvatures of factor manifold c1, · · · , cM and its coordinate of rotation symmetry (zi)[S]. In our construction, (zi)[S] is given in the 1st dimension of the zi's free factor (z0 i )[1]. We employ a multilayer perceptron (MLP) to approximate the map. The estimated curvature ¯ ci is given as,

In the graph domain, node curvature Ric(i) is defined by averaging the Ricci curvature in its neighborhood, in analogy to tracing around the tangent space of the manifold. That is, the node-level curvature on the graph is formulated as Ric(i) = 1 degreei ∑j∈Ni Ric(i, j), where degreei is the degree of vi and Ni denotes the 1-hop neighborhood of node i. Then, we propose a node-level curvature consistency loss as

so that curvatures of factor manifolds are jointly learnt with the model via the fine-grained curvature modeling.

Till now, we construct the heterogeneous curvature space modeling the fine-grained curvatures of the graph. Thereby, the constructed curvature space supports geometric graph clustering with the Ricci loss, which requires a closer look over the various Ricci curvatures on the graph (Eqs. 3-5).

Remarks. The advantages of our design are 1) PH supports node-level curvature modeling for geometric clustering, and its factors has learnable curvatures, different from the product manifolds in Gu et al. [2019]; Wang et al. [2021]. 2) PH as a whole owns the closed form expression of geometric metrics inherited from its factor manifolds. 3) PH decomposes itself into (M +1) different geometric views corresponding to each factor (i.e., M restricted views and 1 free view).

Generate Deep Representations in the Product Manifold

Thanks to the product construction, encoding in the heterogeneous curvature space is transformed into encoding in each factor manifold. Most of the Riemannian GCNs involve the tangent space out of the original manifold, and recent studies observe the inferior of tangential methods [Dai et al., 2021].

To bridge this gap, we design a fully Riemannian GCN (fRGCN) for the restricted factorMc,d , whose novelty lie in that all the operations are fully Riemannian for any c, i.e., no tangent space is involved. We design the manifold preserving operators of fRGCN as follows.

Feature Transformation. First, we formulate a generalized Lorentz Transformation (gLT) for dimension transformation, inspired by the classic LT. The transformMc,dm → Mc,dn is done via the matrix left-multiplication with the transform matrix derived as follows,

Recall that z = [zt zs]⊤ ∈ Mc,dm . In gLT, wt is responsible to scale zt while W transforms zs. We derive the closed-form t-scaling as wt = 1 zt √sgn(c) ( 1c - ℓ(W , zs)) and ℓ(W, zs) = ‖Wzs‖2 .

Now, we prove that the transformed feature with gLT resides in the target manifold.

Proposition 2 (Manifold Preserving). ∀z ∈ Mc,dm , ∀c, gLT c,dm→dn z (W)z ∈ Mc,dn holds for any W ∈ Rdn×dm .

Note that, the classic LT works with a fixed dimension. Recently, Dai et al. [2021] optimize with orthogonal constraint unfriendly to deep learning. Chen et al. [2022] restrict in negative curvature. That is, all of them cannot satisfy our need.

Second, we add the bias for gLT and obtain the linear layer in the manifold of any curvature c as follows,

where b is the bias and ℓ(W, zs) = ‖Wzs +b‖2 . It is easy to check that LLc is manifold preserving.

Attentive Aggregation. The encoding of i is updated as the weighted geometric centorid over the set ¯Ni, the neighbors of i and itself, i.e., argminhi∈M ∑j∈ ¯Ni νijd2c (hi, hj), ∀c and νij denotes the attentive weight. For any c, we derived the closed form solution hi = AGGc ({hj , νij}|j ∈ ¯Ni),

The attentive weights νij is the importance of j in the aggregation over ¯Ni. We define the attentive weights based on the distance in the manifold, νij = Softmax(-τdc (hj, hi) - γ), where τ is an inverse temperature and we add a bias γ. It is easy to check that the centroid in Eq. (13) lives in the manifold, ∀c, and thus AGGc is manifold preserving.

Note that, Einstein midpoint formulates an arithmetic mean in the manifold but lacks geometric interpretation. Fr´echet mean elegantly generalizes from Einstein midpoint but does not offer any closed form solution [Chen et al., 2022]. Our closed form solution in Eq. (13), generalizing to any curvature, is the geometric centroid of squared distance.

The Free Factor. Linear layer LL0 is done via replacing LLc with a free wt ∈ R. Attentive aggregation is defined as AGG0 ({hj, νij}|j ∈ ¯Ni) = ∑j∈ ¯Ni νijhj where attentive weights νij is computed based on distance d0. They are manifold preserving as there is no norm restriction in Rd0 .

3.3 Learning by Reweighted Geometric Contrasting

In this subsection, we train the graph clusters with a contrastive loss in the proposed curvature space. Specifically, we propose a Reweighted Geometric Contrasting (RGC) approach, in which we contrast across different geometric views with a novel dual reweighting, as shown in Fig 1 (c).

Augmentation-Free Geometric Contrast

The augmentation is nontrivial for graph contrastive learning, and requires special design for clustering [Gong et al., 2022]. Instead, our CONGREGATE is free of augmentation where we take advantage of the carefully designed PH for contrastive learning. Thanks to the product construction, PH itself owns different geometric views as remarked in Sec. 3.2. The contrast strategy is that we contrast each restricted view in Mcm,dm m with the free view in Rd0 , and vice versa.

The remaining challenge is how to contrast between different manifolds, i.e., Mcm,dm m and Rd0 . The difference in both curvature and dimension blocks the application of typical similarity functions. We propose to bridge this gap by gLT and bijection ψM→R of Diffeomorphism. (Recall that we have already provided an effective mathematics tool for dimension transformation, gLT .) Specifically, we introduce an

Algorithm 1: Training CONGREGATE

Input: Graph G, #(Clusters)=K, #(Factors)=(M+1) Output: Encoder f, Cluster centroids {φk}k=1,··· ,K 1 Preprocessing: Compute Ricci curvatures on G; 2 while not converging do 3 Create geometric views [z0 z1 · · · zM ] ← fRGCN; 4 for each restricted view zm, m ∈ [1, M] do 5 /* Contrast with the free view z0 */ 6 Node-to-Node contrast based on Eq. (17); 7 Node-to-Cluster contrast based on Eq. (18); 8 end 9 Train {φk}k=1,··· ,K by optimizing J in Eq. (20); 10 end

image of restricted view ˆ zm that is comparable with the free view. First, we employ gLT to transform zm intoMcm,d0-1 m whose ambient space is Rd0 . Second, we apply the diffeomorphism bijection and thus the image is given as follows,

where parameter W characterizes gLT , and logcm 0 (·) is utilized as the bijection since its differentiable inverse exists logcm 0 (expcm 0 (z)) = z. Note that ˆ zm i ∈ Rd0 . Then, we define the similarity as a bilinear critic with parameter S,

Our formulation of Eq. (15) does not introduce additional tangent space, and its advantage is examined in Sec. 4.3.

Dual Reweighting in Curvature Space

A drawback of the popular InfoNCE loss is hardness unawareness (equally treating the hard sample pairs and the easy ones), limiting the discriminative ability [Robinson et al., 2021]. To address this issue, we propose a dual reweighting, paying more attention to both hard negatives and hard positives for contrastive learning in curvature space.

First, we specify the hard samples in the context of graph clustering where cluster assignment offers pseudo labels. Intuitively, the nodes assigned to different clusters but sharing large similarity are referred to as hard negatives, while the border nodes sharing small similarity to the cluster centroid are hard positives. Second, we model the hardness by comparing cluster assignment (pseudo label) and representation similarity, and formulate the dual reweighting as follows,

where the control coefficient β is a positive integer, and W(zm i , z0 j ) up-weights both hard positives and hard negatives while down-weighting the easy ones.

Recently, Sun et al. [2022a] design a Riemannian reweighing for node embedding only and thus fail to consider clusters. Liu et al. [2023] select hard positives in Euclidean space while we need to handle different manifolds. Both of them cannot meet our need and motivate our design of Eq. (16).

Node-to-Node & Node-to-Cluster Contrasting

The RGC loss consists of Node-to-Node and Node-to-Cluster contrasting, where we contrast different geometric views with the dual reweighting and Sim function in generic curvature space. First, we define Node-to-Node contrast loss as follows,

Second, we contrast node encoding of one view with cluster centroids of another view, and formulate the Node-to-Cluster contrast loss as follows,

where node vi is assigned to cluster ki. Here, inW(zm i ,φ0ki ), the inner product term is simplified as [πi]ki the probability of vi assigned to cluster ki. Thus, we have RGC loss as follows,

In our curvature space, intra-cluster node similarity is maximized as they positively contrast to the same centroid, while inter-cluster nodes are separated by negative contrast. Meanwhile, more attention is paid to the similar cluster centorids (hard negatives) and the nodes residing in the cluster border (hard positives), thanks to dual reweighting of Eq. (16).

Overall Loss. Finally, the overall loss of CONGREGATE is formulated as follows,

where α1 and α2 are weighting coefficients. In this way, we end-to-end train node encodings and cluster centorids, so that the nodes in the graph are clustered in the proposed heterogeneous curvature space.

Complexity Analysis

We summarize the training process of CONGREGATE in Algorithm 1, in which Eq. (19) is the most costly, yielding the computational complexity of O(2M|V|2 + 2MK|V|). Note that, the computational complexity is similar to typical contrastive methods [Veliˇckovi´c et al., 2019; Hassani and Ahmadi, 2020]. The Ricci curvatures only need to be computed once as a pre-processing, and can be effectively obtained similar to Ni et al. [2019]; Ye et al. [2020].

4 Experiment

In this section, we evaluate our model with 19 baselines on 4 public datasets, aiming to answer the following research questions (RQs),

• RQ1: How does the proposed CONGREGATE perform?
• RQ2: What are the effects of the proposed components?
• RQ3: Why does Ricci Curvature work?

4.1 Experimental Setups

Datasets &Baselines. To evaluate the proposed model, we choose 4 public datasets, i.e., Cora and Citeseer [Devvrit et al., 2022], and larger MAG-CS [Park et al., 2022] and Amazon-Photo [Li et al., 2022]. We give the statistics of the datasets in Table 1.

We focus on deep graph clustering with no labels available. Thus, both the strong deep clustering methods (DC) and self-supervised learning methods (SS) are included as Euclidean Baselines for a comprehensive evaluation. There are 13 strong DC methods and 5 SS methods, summarized in Table 2. Specifically, SS methods are GAE, VGAE [Kipf and Welling, 2016], ARGA [Pan et al., 2020], and the recent contrastive ones, DGI [Veliˇckovi´c et al., 2019] and MVGRL [Hassani and Ahmadi, 2020]. DC methods are DAEGC [Wang et al., 2019], SDCN [Bo et al., 2020], AGE [Cui et al., 2020], GMM-VGAE [Hui et al., 2020], AGCN [Peng et al., 2021], GDCL [Zhao et al., 2021], S3GC [Devvrit et al., 2022], CGC [Park et al., 2022], gCooL [Li et al., 2022], HostPool [Duval and Malliaros, 2022], AGC-DRR [Gong et al., 2022], FT-VGAE [Mrabah et al., 2022] and HSAN [Liu et al., 2023]. There exists few Riemannian Baselines (R). Note that, recent Riemannian GNNs do not have clustering ability, as typical clustering algorithms cannot be directly applied/incorporated owing to the inherent difference in geometry. Instead, we choose a recent shallow model, RicciCom [Ni et al., 2019]. We are the first to bridge Riemannian space and graph clustering to our knowledge.

Evaluation Metric. We employ 3 popular evaluation metrics, i.e., Normalized Mutual Information (NMI), Adjusted Rand Index (ARI) and Accuracy (ACC) [Devvrit et al., 2022; Li et al., 2022; Mrabah et al., 2022].

Reproducibility. In our model, the number of restricted factors M and their dimensions need to be configured for an instantiation, while the factors' curvatures are jointly learnt with the model. In fRGCN, the convolutional layer is stacked twice. The parameters living in the factor (e.g., W in gLT, and the centroid in the factors) are optimized via Riemannian Adam [Kochurov et al., 2020]. The grid search is performed over search spaces for the hyperparameters, e.g., learning rate: [0.001, 0.003, 0.005, 0.008, 0.01], dropout rate: [0.0, 0.1, 0.2, 0.3, 0.4]. We utilize a 2-layer MLP to approximate the fine-grained curvature. In RGC loss, hyperparameter β of the reweighting is 2 as default. If input features live in the Euclidean space, we use the inverse bijection ψ-1 M→R in Eq. (14) to map the Euclidean input to a factor manifold. Further details and code are provided https://github.com/CurvCluster/Congregate.

4.2 RQ1: Main Results

The clustering results on all the datasets in terms of NMI, ARI and ACC are reported in Table 2. We perform 10 independent runs, and report the mean value with standard deviation for fair comparisons. The number of clusters K is set as the number of real classes on each dataset. For the encodingclustering baselines, we apply K-means to obtain the results. In Table 2, our CONGREGATE is instantiated with 4 factor manifolds whose dimensionality are {32, 32, 16, 16}, and it consistently achieves the best results among 19 competitors on 4 datasets. The reasons are two-fold. 1) We take advantage of the proposed curvature space and the consensus clustering from different geometric views. 2) We learn high discriminative encodings and cluster centroids in an end-to-end fashion.

4.3 RQ2: Ablation Study

We investigate on how each proposed component contributes to the success of our CONGREGATE: i) fRGCN for modeling graph fully Riemannianly, ii) ϕ ◦ gLT for contrasting between different manifolds and iii) the dual reweighting in W for paying attention to hard samples.

To evaluate the effectiveness of fRGCN, we introduce a variant which replaces fRGCN with a GAT c . Concretely, GAT c generalizes GAT [Veliˇckovi´c et al., 2018] in a manifold of curvature c with tangent spaces. We utilize the tangential methods of any c formulated in Skopek et al. [2020]. To evaluate the effectiveness of ϕ◦ gLT , we introduce a variant using Tlogcm 0 instead, where the matrix T is given for dimension transformation. It introduce an additional tangent space compare to the design in our model. To evaluate the effectiveness of W, we introduce two kinds of variants. The first variant (denoted as -pAware) removes the W on the numerators of our RGC loss, thus keeping the attention to hard negatives only. The second variant (denoted as -hard) eliminates all the W, resulting in an InfoNCE in Riemannian space without hardness awareness. In addition, we examine the effect on the number of factor manifolds. To this end, the variants above are instantiated in product space of 4 factors and 5 factors, respectively. We report the NMI and ACC of the clustering results on Cora and Citeseer datasets in Table 2, and find that: i) Our CONGREGATE beats the -fRGCN and -ϕ◦gLT. It shows that introducing addtional tangent spaces trends to results in inferior clustering, and thus testifies the effectiveness of fully Riemannian model. ii) The product space 5 factors outperforms that of 4 factors. Here, the number of factors corresponds to the number of curvatures. It suggests that more factor manifolds may benefit the performance, and the reason is that more factors give further flexibility for the fine-grained curvaturemodeling. iii) -posAvariant performs better than -hard, and the proposed RGC loss is the best. It shows the importance of hard samples, and more attentions to hard positives (the border nodes) further help the performance, which is the reason of our design that we pay more attentions to both hard positives and hard negatives.

4.4 RQ3: Ricci Curvature &Clustering

We discuss why Ricci curvature works. Empirically, we further study the clustering capability of Ricci curvature comparing with classic concepts (gCooL with refined modularity, HostPool with motif conductance and RicciCom with Ricci curvature). We examine the result clusters from mi-

(c) Cluster Density on Citeseer

(d) Cluster Entropy on Citeseer

Figure 2: Visualize density and entropy of the clusters.

croscopic perspective by cluster density and entropy [Li et al., 2022]. The density is Ek[ Ek Vk(Vk-1) ], where Ek and Vk are the number of edges and nodes in cluster k. The entropy is -Ek[∑c pk(c) log pk(c)], where pk(c) is the frequency of class (label) c occurred in cluster k. Lower entropy means better result, i.e., the cluster contains a major class. The results are visualized in Fig. 2. After a few hundred epochs, Ricci methods achieves even better density than moduarity/conductance methods. It shows the clustering capability of Ricci curvature, verifying our motivation. Also, we have lower entropy than RicciCom. It is because we further introduce the novel curvature space, supporting fine-grained curvature modeling for graph clustering.

5 RelatedWork

DeepGraph Clustering. In the literature, deep graph clustering methods are roughly divided into 3 categories regarding the learning paradigm. 1) Reconstructive methods provide supervision signal by recovering graph information, and generate node clusters by applying or incorporating clustering methods [Duval and Malliaros, 2022; Mrabah et al., 2022]. 2) Adversarial methods regulate the generative process by a discriminator in a min-max game [Jia et al., 2019; Yang et al., 2020]. 3) Contrastive methods acquire discriminative representation without labels by pulling positive samples together while pushing negative samples apart [Park et al., 2022; Devvrit et al., 2022]. Meanwhile, deep methods are introduced to bipartite graphs [Zhou et al., 2022], signed graphs [He et al., 2022; Kang et al., 2021], temporal graphs [Yao and Joe-Wong, 2021], heterogeneous graphs [Khan and Kleinsteuber, 2022], and etc. Recently, He et al. [2021] present a novel generative model with EM algorithm; Fettal et al. [2022] introduce a strong matrix optimization framework. Distinguishing from the prior studies, we rethink the problem of graph clustering from the geometric perspective.

Riemannian Graph Representation Learning. Recent years have witnessed the remarkable success achieved by Riemannian graph learning. As hyperbolic space is well aligned with hierarchical or power-law graphs, shallow models are first introduced [Nickel and Kiela, 2017; Suzuki et al., 2019], and hyperbolic GCNs with different formulations are then proposed [Chami et al., 2019; Liu et al., 2019; Zhang et al., 2021]. Beyond hyperbolic space, κ-GCN [Bachmann et al., 2020] extend GCN to constant-curvature spaces with κsterographical model. Yang et al. [2022] model the graph in the dual space of Euclidean and hyperbolic ones. Xiong et al. [2022a,b] study graph learning on a kind of pseudo Riemannian manifold, ultrahyperbolic space. Law [2021] introduce a quotient manifold for graph learning. Both ultrahyperbolic and quotient manifolds present a single curvature radius. Cruceru et al. [2021] study the matrix manifold of Riemannian spaces. Gu et al. [2019]; Wang et al. [2021]; Sun et al. [2022b] explore node embedding in the product manifold. Our work is based on the product manifold, but we further explore the curvature heterogeneity. Sun et al. [2022a]; Yang et al. [2021]; Sun et al. [2021] consider representation learning on temporal graphs. Very recently, Giovanni et al. [2022] investigate in the rotational symmetry of the manifold, but do not consider fine-grained curvature modeling and learnable factors, different from our study. However, none of existing studies focus on graph clustering in Riemannian manifolds to the best of our knowledge.

6 Conclusion

In this paper, we formulate the problem of geometric graph clustering, which is the first to introduce the curvature space allowing for fine-grained curvature modeling to graph clustering. We present an end-to-end CONGREGATE built upon a novel heterogeneous curvature space that we construct for geometric graph clustering with Ricci curvatures. Accordingly, graph clusters are trained by an augmentation-free contrastive loss, where we pay more attention to both hard positives and hard negatives in our curvature space. The empirical results show the superiority of our model.

Acknowledgments

Thanks to the anonymous reviewers. The authors were supported in part by National Natural Science Foundation of China under Grant 62202164, the National Key R&D Program of China through grant 2021YFB1714800, S&T Program of Hebei through grant 21340301D and the Fundamental Research Funds for the Central Universities 2022MS018. Prof. Philip S. Yu is supported in part by NSF under grants III-1763325, III-1909323, III-2106758, and SaTC-1930941. Corresponding Authors: Li Sun and Hao Peng.