Paper deep dive
Compactness and Consistency: A Conjoint Framework for Deep Graph Clustering
Wei Ju, Siyu Yi, Kangjie Zheng, Yifan Wang, Ziyue Qiao, Li Shen, Yongdao Zhou, Xiaochun Cao, Jiancheng Lv
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 10/10/2026, 1:49:27 AM
Summary
The paper proposes CoCo, a conjoint framework for deep graph clustering that addresses limitations of existing GNN-based methods regarding global relationship capture and noise/redundancy in node representations. CoCo utilizes graph convolutional filters on both local (adjacency matrix) and global (graph diffusion matrix) views to extract features. It then employs a low-rank subspace learning strategy based on Gaussian Mixture Models to create compact embeddings, eliminating redundancy and noise. Finally, a consistency learning strategy ensures semantic alignment between the local and global views, improving clustering performance.
Entities (9)
Relation Signals (8)
CoCo → solves → Graph Clustering
confidence 95% · we propose a conjoint framework CoCo, which captures compactness and consistency in the learned node representations for deep graph clustering.
CoCo → produces → Low-rank Compact Embeddings
confidence 92% · encodes them into low-rank compact embeddings, thus effectively removing the redundancy and noise
CoCo → includes → Consistency Learning
confidence 90% · we develop a consistency learning strategy based on compact embeddings to facilitate knowledge transfer from the two perspectives.
CoCo → uses → Graph Diffusion Matrix
confidence 90% · our CoCo first leverages the graph convolutional filters to encode the node attributes and graph topology based on the original graph and graph diffusion matrix
CoCo → employs → Gaussian Mixture Model
confidence 88% · we leverage the Gaussian mixture model (GMM) to learn the optimal low-dimensional subspace
GNNs → struggleswith → Global Relationships
confidence 85% · representations learned through GNNs typically struggle to capture global relationships between nodes via local message-passing mechanisms.
CoCo → outperforms → SDCN
confidence 80% · Our experimental results indicate that our CoCo outperforms state-of-the-art counterparts on various datasets.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Graph clustering is a fundamental task in data analysis, aiming at grouping nodes with similar characteristics in the graph into clusters. This problem has been widely explored using graph neural networks (GNNs) due to their ability to leverage node attributes and graph topology for effective cluster assignments. However, representations learned through GNNs typically struggle to capture global relationships between nodes via local message-passing mechanisms. Moreover, the redundancy and noise inherently present in graph data may easily result in node representations lacking compactness and robustness. To address these issues, we propose a conjoint framework CoCo, which captures compactness and consistency in the learned node representations for deep graph clustering. Technically, our CoCo leverages graph convolutional filters to learn robust node representations from both local and global views, and then encodes them into low-rank compact embeddings, thus effectively removing the redundancy and noise as well as uncovering the intrinsic underlying structure. To further enrich the node semantics, we develop a consistency learning strategy based on compact embeddings to facilitate knowledge transfer from the two perspectives. Our experimental results indicate that our CoCo outperforms state-of-the-art counterparts on various datasets.
Tags
Links
- Source: https://arxiv.org/abs/2610.11506v1
- Canonical: https://arxiv.org/abs/2610.11506v1
Trouble viewing inline? Open PDF directly →
Full Text
102,703 characters extracted from source content.
Expand or collapse full text
Compactness and Consistency: A Conjoint Framework for Deep Graph Clustering Wei Ju Affiliation: College of Computer Science, Sichuan University Email: juwei@scu.edu.cn Siyu Yi Email: siyuyi@scu.edu.cn Kangjie Zheng Affiliation: Wellcome Sanger Institute Email: ydzhou@nankai.edu.cn Yifan Wang Affiliation: University of International Business and Economics Ziyue Qiao Affiliation: School of Computing and Information Technology, Great Bay University Li Shen Affiliation: School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University Yongdao Zhou †thanks: Corresponding Authors. Affiliation: NITFID, School of Statistics and Data Science, Nankai University Xiaochun Cao, Jiancheng Lv Affiliation: College of Computer Science, Sichuan University Affiliation: School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University Affiliation: College of Mathematics, Sichuan University Abstract Graph clustering is a fundamental task in data analysis, aiming at grouping nodes with similar characteristics in the graph into clusters. This problem has been widely explored using graph neural networks (GNNs) due to their ability to leverage node attributes and graph topology for effective cluster assignments. However, representations learned through GNNs typically struggle to capture global relationships between nodes via local message-passing mechanisms. Moreover, the redundancy and noise inherently present in graph data may easily result in node representations lacking compactness and robustness. To address these issues, we propose a conjoint framework CoCo, which captures compactness and consistency in the learned node representations for deep graph clustering. Technically, our CoCo leverages graph convolutional filters to learn robust node representations from both local and global views, and then encodes them into low-rank compact embeddings, thus effectively removing the redundancy and noise as well as uncovering the intrinsic underlying structure. To further enrich the node semantics, we develop a consistency learning strategy based on compact embeddings to facilitate knowledge transfer from the two perspectives. Our experimental results indicate that our CoCo outperforms state-of-the-art counterparts on various datasets. The code is available at https://github.com/juweipku/CoCo. 1 Introduction Graph clustering, as a critical task in network analysis and machine learning, plays a significant role in organizing and understanding complex relational data (Liu et al., 2022b). It involves partitioning the nodes of a graph into clusters, aiming to group nodes that exhibit similar characteristics or share related patterns. Its application spans across various domains, including social network analysis, biological networks, and recommender systems, among others. By identifying cohesive groups of nodes, graph clustering provides valuable insights into the underlying structure and connections within the data, enabling more effective knowledge extraction and decision-making processes. For the past decades, many efforts have been devoted to gaining a profound understanding of this fundamental problem, traditional methods typically rely on hand-crafted features (Yan et al., 2006) or graph partitioning algorithms (Ng et al., 2001; Vidal, 2011), which aim to project data samples into a low-dimensional space while incorporating constraints to ensure clear separation between the samples. However, the conventional training paradigm tends to yield unsatisfactory outcomes, as the limited model capacity restricts their potential, failing to fully exploit the abundant structural information contained in the graph. This has led us to study deep graph clustering, offering superior adaptability and expressive power by automatically extracting informative features from graphs (Bo et al., 2020; Ju et al., 2023; Liang et al., 2025b). Recently, graph neural networks (GNNs) have emerged as an effective approach, achieving remarkable success in capturing complex dependencies in graph-structured data and serving as a promising tool for deep graph clustering. Based on this strength, many researchers have explored the potential of GNNs for deep graph clustering (Liu et al., 2022a; Yang et al., 2023; Yang et al., 2024; Liu et al., 2024a). For example, SDCN (Bo et al., 2020) is the first to integrate structural information into deep clustering by bridging autoencoder representations with GCN layers through a delivery operator, while MAGI (Liu et al., 2024a) introduces a community-aware graph clustering framework that uses modularity maximization as a contrastive pretext task to uncover communities and mitigate semantic drift. In addition, DMGC-GTN (Wang et al., 2025a) explores a novel multi-modal graph clustering method that integrates structural and feature information via graph smoothing and transformer to exploit their complementarity. These GNN-based methods offer a data-driven way to learn node representations inherently capturing node attributes and the relational dependencies among neighboring nodes, potentially leading to more meaningful cluster assignments. Despite the tremendous success of previous methods, there still exist some inherent limitations. First, existing graph clustering methods often struggle to effectively capture global relationships among nodes without any intervention (Chen et al., 2020a). Since effective local message passing mechanisms (Gilmer et al., 2017) in GNNs typically propagate information for only a few layers, they often overlook long-range dependencies, limiting their ability to capture the underlying node distribution and resulting in suboptimal clustering. For instance, existing works (MAGI and DMGC-GTN) typically only perform local augmentation or random walks on the original graph, which fails to capture longer-range dependencies and consequently prevents clusters from accurately representing the underlying community structure. Second, the inherent redundancy and noise present in graph data poses challenges in learning compact and informative node representations (Kang et al., 2019). Existing graph clustering methods often overlook the inherent redundancy and noise in data, which inevitably skews the training process and hinders the exploration of the underlying structure among data, thereby obscuring important relationships and patterns, and ultimately leading to less discriminative embeddings. To address these challenges, we propose a conjoint framework capturing both Compactness and Consistency in the learned node representations, abbreviated as CoCo. Specifically, to explore both neighbor information and long-range relationships between nodes from local and global views respectively, our CoCo first leverages the graph convolutional filters to encode the node attributes and graph topology based on the original graph and graph diffusion matrix, thus effectively learning complementary node representations. Then, we encode node representations into low-rank compact embeddings, which learns the optimal low-dimensional subspace to characterize the intrinsic underlying structure, thereby fully eliminating redundancy and noise. To well facilitate the knowledge sharing of the compact embeddings from the two perspectives, we introduce a consistency learning strategy to encourage the model to produce consistent similarity distributions for each node, thus further enabling the learned node representations with richer semantics from both local and global information. Comprehensive experimental results across various graph datasets demonstrate the superior performance and effectiveness of our method over previous approaches. 2 Methodology Notations. Let =,ℰ,,G=\V,E,X,A\ denote an attribute graph of N nodes, where =v1,⋯,vNV= \v_1,·s,v_N \ represents the set of nodes and ℰ⊆×E ×V is the set of edges. Denote by ∈ℝN×FX ^N× F the attribute matrix of all nodes, where F is the dimension of attributes. ∈0,1N×NA∈\0,1\^N× N is the adjacency matrix, where Aij=1A_ij=1 if (vi,vj)∈ℰ(v_i,v_j) . The normalized adjacency matrix is denoted as ~=^−1/2^^−1/2 A= D^-1/2 A D^-1/2, where A equals to +NA+I_N with added self-connections, and D is the diagonal degree matrix with D^ii=∑j=1NA^ij D_i= _j=1^N A_ij. Then the symmetric normalized graph Laplacian matrix is defined as ~=N−~ L=I_N- A. Deep Graph Clustering. The task of deep graph clustering is to partition an unlabeled graph with N nodes into C disjoint clusters, denoted as 1,…,C\C_1,…,C_C\ based on a well-trained node representation matrix ∈ℝN×DZ ^N× D. In general, a self-supervised loss is developed to guide the training process to learn informative node representations. Then, a clustering algorithm such as K-means, spectral clustering, or a neural-network clustering layer, is performed on the trained node representations to output the clustering results. In this section, we present a novel framework CoCo for deep graph clustering. The complete framework is depicted in Figure 1. Figure 1: Illustration of the proposed framework CoCo. 2.1 Local- and Global-view Feature Extraction To learn effective node representations, most existing methods employ graph convolution on the adjacency matrix, which propagates messages between one-hop neighbors. For capturing long-range neighbor information, the convolution layers are deepened, which inevitably leads to the over-smoothing issue, i.e., indistinguishable node representations of different clusters, due to the over-mixing of features and noises (Chen et al., 2020a). To alleviate this issue and fully explore graph topology, we leverage graph diffusion in this paper to smooth out the neighborhood over the graph. Formally, the graph diffusion matrix S is defined as: =α(N−(1−α)~)−1S=α(I_N-(1-α) A)^-1, which adopts the personalized PageRank (Page et al., 1999) with teleport probability α∈(0,1)α∈(0,1). The elements in S measures the influence/correlation between all pairs of nodes. Compared with the adjacency matrix A, S characterizes the soft relationships among the nodes, thus achieving the ability to globally exploit the long-range neighbor information. To reduce the computational complexity, there are fast approximations to achieves a linear runtime (Andersen et al., 2006; Wei et al., 2018) and we also sparsify (e.g., set values below a certain threshold to zero) S to obtain ′S , and modify it as ^≜(′+′⊤)/2 S (S +S )/2 to maintain symmetry. In the following, we treat the tuples ,\X,A\ and ,^\X, S\ as the local and global views to retrieve different knowledge over the given graph. Inspired by Wu et al. (2019), the entanglement of graph convolutional filter and weight matrix in GNN will harm both the performance and robustness when learning node representations. Instead, we adopt the disentangled architecture to encode the attribute and structure information from local and global views. First, we utilize the generalized Laplacian smoothing filters to denoise the high-frequency components and integrate node attributes and structure information: ~l=(N−~l/kl)t,~g=(N−~g/kg)t, X^l=(I_N- L^l/k^l)^tX, X^g=(I_N- L^g/k^g)^tX, (1) where kl,kg(>0)k^l,k^g(>0) are real values and t is the number of the filter layers. ~l(=~) L^l(= L) and ~g L^g are the local- and global-view normalized graph Laplacian matrix, in which ~g L^g can be acquired like the expression of ~ L except replacing A with S. Theoretically, we can derive the following conclusion and the proof is shown in Appendix B.1. theorem kl=λ~maxlk^l= λ^l_max and kg=λ~maxgk^g= λ^g_max are the optimal choice to pursue low-pass filters, where λ~maxg λ^g_max and λ~maxl λ^l_max are the maximal eigenvalues of ~l L^l and ~g L^g, respectively. Then, to make node representations trainable, we learn weight parameters by feeding the filtered features into two unshared multi-layer perceptrons (MLP1MLP_1 and MLP2MLP_2) for two views as: l=MLP1(~l),g=MLP2(~g).Z^l=MLP_1( X^l), ^g=MLP_2( X^g). (2) 2.2 Compactness Learning for Redundancy Elimination Low-rank representations can effectively exploit the inherent underlying correlation structure among data and suppress the impact of noise under the assumption that high-dimensional data points often intrinsically lie on a low-dimensional subspace (Ren et al., 2019; Tang et al., 2019; Jin et al., 2022a). For self-supervised learning, to achieve better fusion of the semantics from the local and global views, we expect to utilize the same set of low-dimensional subspace to abstract and reconstruct the low-rank node representations of the two perspectives, which closes the gap between their semantic spaces and eliminates the redundancies in features, thereby uncovering the underlying data structure and yielding compact node representations from the two views. Low-rank Subspace Training. Technically, we leverage the Gaussian mixture model (GMM, in Appendix A) (Richardson and Green, 1997) to learn the optimal low-dimensional subspace that can represent the local- and global-view node embeddings in Equation 2. Let N¯=2N N=2N, denote the embedding space as =(l⊤,g⊤)⊤∈ℝN¯×DZ=(Z^l ,Z^g ) N× D, the learnable subspace as ∈ℝN¯×K N× K (K≪DK D), the j-th column of Z as ⋅,j=(z1j,…,zN¯j)⊤z_·,j=(z_1j,…,z_ Nj) , and the k-th column of as ⋅,k=(λ1k,…,λN¯k)⊤ λ_·,k=( _1k,…, _ Nk) . We introduce the latent variable matrix ∈ℝD×KY ^D× K, where the element yjky_jk in Y indicates whether ⋅,jz_·,j is related to ⋅,k λ_·,k. Under GMM, the goal is to maximize logp(|) p(Z| λ) and the likelihood functions for the observed data Z and the complete data ,\Z,Y\ are proportionally formulated as: p(|) p(Z| λ) ∝∏j=1D(∑k=1K(⋅,j|⋅,k,σN¯)),p(,|)∝∏j=1D∏k=1K(⋅,j|⋅,k,σN¯)yjk, Π _j=1^D (Σ _k=1^KN(z_·,j| λ_·,k, _ N) ),~p(Z,Y| λ) Π _j=1^DΠ _k=1^KN(z_·,j| λ_·,k, _ N)^y_jk, where σ is a hyper-parameter to adjust the normal distribution. By implementing the expectation-maximization (EM) algorithm (Dempster et al., 1977), introduced in Appendix A , we can obtain in the E step that the posterior probability of the latent variable (p(|,)p(Y|Z, λ)) is calculated by: γ(yjk)=p(yjk=1|⋅,j,⋅,kold)=(⋅,j|⋅,kold,σN¯)∑k′=1K(⋅,j|⋅,k′old,σN¯);γ(y_jk)=p(y_jk=1|z_·,j, λ_·,k^old)= N(z_·,j| λ_·,k^old, _ N) _k =1^KN(z_·,j| λ_·,k ^old, _ N); and the posterior expectation Q(,old)Q( λ, λ^old) is: Q(,old)=E|,old(logp(,|)).Q( λ, λ^old)=E_Y|Z, λ^old( p(Z,Y| λ)). In the M step, we maximize Q(,old)Q( λ, λ^old) and the subspace is updated by: λiknew=1∑j=1Dγ(yjk)∑j=1Dγ(yjk)zij. _ik^new= 1Σ _j=1^Dγ(y_jk)Σ _j=1^Dγ(y_jk)z_ij. (3) Here, the qualities of the Gaussian means ⋅,k λ_·,k and the posteriors γ(yjk)γ(y_jk) are critical. To simplify the model, we fix the mixture weights (priors) to be equal and the covariance matrices to be isotropic. It does not compromise the model’s generality, since the equal prior does not affect the posterior trends, which are primarily data-driven. It also has advantages: (1) equal weights mitigate cluster collapse and promotes uniform coverage of the embedding space; and (2) fixing the covariance focuses the model’s fitting capacity on the “mean-defined subspace”, since based on the negative ELBO bound, maximizing the log-likelihood in the M-step is equivalent to minimizing the weighted squared-distance objective ∑j,kγ(yjk)‖⋅,j−⋅,k‖2 _j,kγ(y_jk)\|z_·,j- λ_·,k\|^2. Theoretically, the iterative algorithm is guaranteed to converge (Dempster et al., 1977), as stated in Remark 2.2 and proven in Appendix B.2. In the experiment, we verify that the subspace searching algorithm can achieve good performance within 10 iterations across different datasets, incurring negligible additional computational cost. remark In each iteration, we have logp(|new)≥logp(|old) p(Z| λ^new)≥ p(Z| λ^old). By repeatedly iterating the E step and M step until converging, the algorithm enforces the trained subspace to effectively represent the core characteristics of the embedded representation Z, as only the principal and cluster-level directions captured by the GMM means are retained while correlated or weakly informative variations are removed. As such, the intrinsic data relationship is preserved in while removing the redundancy. Discussion on the comparison with other rank reduction ways can be found in Appendix C. Feature Reconstruction. Further, to hold the main energy of the “clean” data (Ren et al., 2019), we perform data reconstruction to produce low-rank and compact representations stripped of redundancy. Concretely, we use the well-trained posterior probability of the latent variable γ^(yjk) γ(y_jk) and the optimal subspace ^=(λ^ik) =( λ_ik) to linearly reconstruct the original features, i.e., each entry in the reconstructed embedding ^=(z^ij)∈ℝN¯×D Z=( z_ij) N× D is formulated as: z^ij=∑k=1Kλ^ikγ^(yjk). z_ij=Σ _k=1^K λ_ik γ(y_jk). (4) Since the noise or unstable fluctuations in the original embeddings cannot be expressed within the constrained subspace and thus vanish when reconstructing onto the original dimensions (mathematically, we have rank(^)=rank(^^⊤)≤minrank(^),rank(^)=Krank( Z)=rank( )≤ \rank( ),rank( )\=K, which indicates that Z maintains the low-rank property). Further, we argue in Theorem 2.2 that the proposed approach reconstructs embedding Z in a way that optimally preserves individual information and total variation of the original embedding Z. The proof is shown in Appendix B.3. theorem Under the low-rank feature reconstruction defined in Equation 4, the following two conservation properties hold: (1) Individual Mass Conservation: the aggregated information for each individual is preserved: ∑j=1Dzij=∑j=1Dz^ijfor all i∈1,…,N¯.Σ _j=1^Dz_ij=Σ _j=1^D z_ij all i∈\1,…, N\. (2) Maximal Variation Preservation: the reconstruction Z maximally preserves the total variation of the original embedding Z among all low-rank factorizations. Specifically, it is the solution to the optimization problem: ^=argmin′∈ℝN¯×D∑i=1N¯∑j=1Dzij(zij−zij′)subject to ′=⊤, Z= _Z N× DΣ _i=1 NΣ _j=1^Dz_ij(z_ij-z _ij) to Z = , where ∈ℝN¯×K N× K and ∈ℝD×K ^D× K with K≪DK D. Theorem 2.2 (1) guarantees the invariance of each individual’s total signal mass. This is crucial for fairness and interpretability, as it prevents the model from systematically biasing the reconstructed profiles of any individual; while Theorem 2.2 (2) ensures that our reconstruction prioritizes the retention of the significant variations (with large zijz_ij) due to the cross-term ∑i,jzijzij′ _i,jz_ijz _ij. This enables our low-rank reconstruction to align strongly with these dominant patterns. By leveraging the optimal low-dimensional subspace to reconstruct both the local- and global-view node embeddings, the semantic gap between them is also well alleviated. The obtained compact representation from both views can express the underlying data structure better, which is promising and beneficial to enhance the graph clustering. However, the above implementation is performed outside the gradient flow, we hence inject the tuned representations back into the gradient path using a residual connection: ~=(~l⊤,~g⊤)⊤=^+. Z=( Z^l , Z^g ) = Z+Z. (5) On the one hand, it ensures the model remains trainable by allowing gradients to flow through the residual path; on the other hand, it combines the global trends captured by the low-rank component with the local details preserved in the original Z, mitigating the over-smoothing that may result from relying solely on a low-rank constraint and preventing model collapse (He et al., 2016). 2.3 Consistency Learning for Semantic Enhancing On the basis of compact node representations ~l=(~1l,…,~Nl)⊤ Z^l=( z_1^l,…, z_N^l) and ~g=(~1g,…,~Ng)⊤ Z^g=( z_1^g,…, z_N^g) in Equation 5, we develop the consistency learning to facilitate the exchange of knowledge between the two complementary perspectives. Meanwhile, we expect that the final representations can finely reflect the inherent relationships among nodes, thereby enhancing the label-free graph clustering. Toward this end, we share the compact semantics by comparing the similarities of each node to other samples in the embedding spaces of the two views. We first randomly select a set of nodes over the given graph with indices a1,…,aM\a_1,…,a_M\ as the anchor samples. Then, we calculate the cosine similarities between each node and these anchor samples and formulate the similarity distribution by the softmax operation. Mathematically, for the i-th node representations from the local and global views, the similarity scores of the m-th anchor are: pmi p_m^i =exp(cos(~il,~aml)/τ)∑m′=1Mexp(cos(~il,~am′l)/τ),qmi=exp(cos(~ig,~amg)/τ)∑m′=1Mexp(cos(~ig,~am′g)/τ), = ( ( z_i^l, z_a_m^l)/τ) _m =1^M ( ( z_i^l, z_a_m ^l)/τ),~q_m^i= ( ( z_i^g, z_a_m^g)/τ) _m =1^M ( ( z_i^g, z_a_m ^g)/τ), where cos(,)=⊤/(‖⋅‖) (a,b)=a b/(||a||·||b||) is the cosine similarity, τ denotes the temperature parameter. For a comprehensive similarity measure, we need a large number of anchor samples so that they have large variations to cover the neighborhood of any node. However, it requires high computational costs to process too many samples in a single iteration. To address this problem, we maintain a memory bank with size M as a queue defined on the fly by random nodes and calculate the similarity scores for each node and the samples in the queue. By dynamically updating the queue, we improve the diversity of the anchors with low complexity. With the local- and global-view similarity distributions i=(p1i,…,pMi)p^i=(p^i_1,…,p^i_M) and i=(q1i,…,qMi)q^i=(q^i_1,…,q^i_M), we encourage the consistency of them to facilitate the knowledge transfer and mutually enhance the representation semantics. Formally, we define the consistency learning loss as: ℒ=12N∑i=1N(KL(i||i)+KL(i||i)),L= 12NΣ _i=1^N (KL(p^i||q^i)+KL(q^i||p^i) ), (6) where KL(⋅||⋅)KL(·||·) is the Kullback-Leibler (KL) divergence. In the training, we minimize ℒL to optimize our proposed CoCo and enhance self-supervised learning. After converging, we fuse the local- and global-view representations by: F=(~l+~g)/2.Z^F=( Z^l+ Z^g)/2. (7) Then, we perform K-means on the fused node representation FZ^F to obtain the clustering results. An outline of the training procedure is provided in Appendix D. A detailed analysis of time and space complexities can be found in Section 3.8 and Appendix E. 3 Experiment 3.1 Experimental Setup We evaluate our CoCo with five widely used benchmark datasets for deep graph clustering, i.e., Cora (Sen et al., 2008), AMAP (Shchur et al., 2018), BAT (Liu et al., 2023c), EAT (Liu et al., 2023c), and UAT (Liu et al., 2023c). To comprehensively assess the effectiveness of our CoCo, we benchmark it against leading state-of-the-art methods, including antoencoder-based methods, i.e., DEC (Xie et al., 2016), IDEC (Guo et al., 2017), DAEGC (Wang et al., 2019), ARGA (Pan et al., 2019), SDCN (Bo et al., 2020), DFCN (Tu et al., 2021), and contrastive learning-based methods, i.e., AGE (Cui et al., 2020), MVGRL (Hassani and Khasahmadi, 2020), GDCL (Zhao et al., 2021), AutoSSL (Jin et al., 2022b), AGC-DRR (Gong et al., 2022), AFGRL (Lee et al., 2022), GDCL (Zhao et al., 2021), ProGCL (Xia et al., 2022), RGC (Liu et al., 2023a), Dink-Net (Liu et al., 2023b), CCGC (Yang et al., 2023), GraphLearner (Yang et al., 2024), and MAGI (Liu et al., 2024a). Details on evaluation metrics and implementation are presented in Appendix F. Table 1: Clustering performance on five benchmark datasets (mean ± standard deviation). The top two results for each method are marked in bold and underline, respectively. Dataset Metric SDCN DFCN AutoSSL AFGRL GDCL ProGCL CCGC GraphLearner MAGI CoCo (Ours) Cora ACC 35.60±2.83 36.33±0.49 63.81±0.57 26.25±1.24 70.83±0.47 57.13±1.23 73.88±1.20 74.91±1.78 76.21±0.50 79.36+0.69 NMI 14.28±1.91 19.36±0.87 47.62±0.45 12.36±1.54 56.30±0.36 41.02±1.34 56.45±1.04 58.16±0.83 59.84±0.43 60.71±0.59 ARI 07.78±3.24 04.67±2.10 38.92±0.77 14.32±1.87 48.05±0.72 30.71±2.70 52.51±1.89 53.82±2.25 57.63±0.81 58.76±1.47 F1 24.37±1.04 26.16±0.50 56.42±0.21 30.20±1.15 52.88±0.97 45.68±1.29 70.98±2.79 73.33±1.86 74.07±0.45 77.95±0.72 AMAP ACC 53.44±0.81 76.82±0.23 54.55±0.97 75.51±0.77 43.75±0.78 51.53±0.38 77.25±0.41 77.24±0.87 75.42±3.22 79.27±0.70 NMI 44.85±0.83 66.23±1.21 48.56±0.71 64.05±0.15 37.32±0.28 39.56±0.39 67.44±0.48 67.12±0.92 64.98±1.92 68.85±1.55 ARI 31.21±1.23 58.28±0.74 26.87±0.34 54.45±0.48 21.57±0.51 34.18±0.89 57.99±0.66 58.14±0.82 55.68±2.88 60.94±1.51 F1 50.66±1.49 71.25±0.31 54.47±0.83 69.99±0.34 38.37±0.29 31.97±0.44 72.18±0.57 73.02±2.34 73.03±3.30 72.36±1.15 BAT ACC 53.05±4.63 55.73±0.06 42.43±0.47 50.92±0.44 45.42±0.54 55.73±0.79 75.04±1.78 75.50±0.87 59.54±3.90 78.85±0.91 NMI 25.74±5.71 48.77±0.51 17.84±0.98 27.55±0.62 31.70±0.42 28.69±0.92 50.23±2.43 50.58±0.90 29.83±5.13 55.00±0.87 ARI 21.04±4.97 37.76±0.23 13.11±0.81 21.89±0.74 19.33±0.57 21.84±1.34 46.95±3.09 47.45±1.53 23.91±3.76 53.52±1.15 F1 46.45±5.90 50.90±0.12 34.84±0.15 46.53±0.57 39.94±0.57 56.08±0.89 74.90±1.80 75.40±0.88 59.12±6.11 78.56±1.01 EAT ACC 39.07±1.51 49.37±0.19 31.33±0.52 37.42±1.24 33.46±0.18 43.36±0.87 57.19±0.66 57.22±0.73 49.10±1.50 58.87±0.49 NMI 08.83±2.54 32.90±0.41 07.63±0.85 11.44±1.41 13.22±0.33 23.93±0.45 33.85±0.87 33.47±0.34 27.00±2.65 34.10±1.26 ARI 06.31±1.95 23.25±0.18 02.13±0.67 06.57±1.73 04.31±0.29 15.03±0.98 27.71±0.41 26.21±0.81 21.52±1.01 27.91±1.52 F1 33.42±3.10 42.95±0.04 21.82±0.98 30.53±1.47 25.02±0.21 42.54±0.45 57.09±0.94 57.53±0.67 44.38±2.20 58.06±2.64 UAT ACC 52.25±1.91 33.61±0.09 42.52±0.64 41.50±0..25 48.70±0.06 45.38±0.58 56.34±1.11 55.31±2.42 50.35±0.16 59.68±0.36 NMI 21.61±1.26 26.49±0.41 17.86±0.22 17.33±0.54 25.10±0.01 22.04±2.23 28.15±1.92 24.40±1.69 21.45±0.28 30.12±0.51 ARI 21.63±1.49 11.87±0.23 13.13±0.71 13.62±0.57 21.76±0.01 14.74±1.99 25.52±2.09 22.14±1.67 17.79±0.23 29.46±0.47 F1 45.59±3.54 25.79±0.29 34.94±0.87 36.52±0.89 45.69±0.08 39.30±1.82 55.24±1.69 52.77±2.61 47.52±0.13 58.03±0.34 3.2 Experimental Results In Table 1 and Appendix G, we present the quantitative results of our proposed CoCo, compared with various competitive deep graph clustering baselines. From the tables, we draw the following key observations. On the one hand, compared to autoencoder-based methods, contrastive learning-based approaches show better performance. The reason lies in the ability of contrastive learning to more effectively exploit the intrinsic semantic information of the graph-structured data. By learning discriminative representations in a principled manner, contrastive learning better serves the clustering task. On the other hand, our approach achieves almost the best results on all five datasets, and significantly outperforms the runner-ups on many datasets. For instance, on Cora and BAT in Table 1, our proposed CoCo surpass the runner-ups by 4.13%\%, 1.45%\%, 2.00%\%, 5.23%\% and 4.16%\%, 8.74%\%, 12.79%\%, 4.19%\% under four evaluation metrics, providing substantial evidence for the superiority of our approach. These results substantiate the success of the compactness learning and consistency learning embodied in CoCo for graph clustering, while also implicitly suggesting the superiority of cross-view consistency learning over contrastive learning, which is further validated in detail in Section 3.3 and Appendix H. 3.3 Ablation Study In this section, we analyze the impact of various components of our proposed method. Comparison of different model variants. We first define different model variants as: (i) M1M_1: solely adopt the local Laplacian smoothing filter to extract node representations (i.e., ~l X^l) for clustering; (i) M2M_2: solely adopt the global one (i.e., ~g X^g) for clustering; (i) M3M_3: adopt local low-rank embeddings (i.e., ~l Z^l) by compactness learning based on ~l X^l for clustering; (iv) M4M_4: adopt global low-rank embeddings (i.e., ~g Z^g) by compactness learning based on ~g X^g for clustering; (v) M5M_5: remove compactness learning from our full model CoCo. The results are summarized in Figure 2. (a) Cora (c) EAT (b) AMAP (d) UAT Figure 2: The ablation experimental results. Comparing M3M_3 with M1M_1 and M4M_4 with M2M_2, mapping raw node features to low-rank embeddings improves the performance in both cases, indicating the effectiveness of our low-rank representations in learning better cluster assignments. Similarly, when comparing M5M_5 with our CoCo, removing the low-rank mapping also leads to performance degradation, further emphasizing the necessity of compactness learning. In addition, comparing M5M_5 and CoCo with M1M_1-M4M_4, we observe a significant performance difference between the two groups, possibly because our consistency learning effectively integrates semantic knowledge from both local and global perspectives, enabling more discriminative and robust representations compared to any single viewpoint. Below, we further consider the comparison between the consistency loss and other surrogate losses. Table 2: The comparative results of consistency learning loss v.sv.s MSE and InfoNCE. Dataset Loss ACC NMI ARI F1 Cora MSE 77.84±0.67 60.31±0.89 57.81±1.42 73.89±1.09 InfoNCE 75.57±1.16 58.03±1.44 54.69±1.85 72.58±1.81 Consistency 79.36+0.69 60.71±0.59 58.76±1.47 77.95±0.72 AMAP MSE 77.62±0.44 67.68±0.76 58.51±0.97 71.84±0.77 InfoNCE 77.25±0.33 67.12±0.46 58.24±0.57 71.89±0.53 Consistency 79.27±0.70 68.85±1.55 60.94±1.51 72.36±1.15 UAT MSE 57.18±0.74 28.43±0.62 25.65±1.11 56.96±0.73 InfoNCE 56.72±0.23 27.67±0.42 25.01±0.45 56.39±0.39 Consistency 59.68±0.36 30.12±0.51 29.46±0.47 58.03±0.34 Influence of Consistency Learning. To investigate the advantages of our proposed consistency learning, we compare two widely used loss functions, Mean Squared Error (MSE) and contrastive loss InfoNCE (Chen et al., 2020b), on all datasets. The comparative results are presented in Table 2 and Appendix H. It can be observed that InfoNCE performs worse than MSE in most cases. This could be potentially attributed to InfoNCE’s reliance on extensive negative instance sampling in contrastive learning, which may introduce more complexity and sensitivity to hyper-parameter tuning compared to the direct regression-based optimization of MSE. Moreover, the performance of consistency learning significantly outperforms the other two loss functions, which fully demonstrates the effectiveness of semantic enhancement brought by aligning the similarity distributions of local and global perspectives in consistency learning. 3.4 Visualization Analysis To visually verify the validity of our proposed CoCo, we plot the projected distributions (t-SNE) of the learned embeddings on Cora and AMAP (Van der Maaten and Hinton, 2008), compared with six baselines. The visualization results are displayed in Figure 3. It can be observed that CoCo exhibits a lower degree of inter-cluster confusion on Cora and better separability among different clusters on AMAP, showcasing CoCo’s ability to learn more discriminative representations and effective cluster assignments compared with competitive methods. SDCN AutoSSL ProGCL CCGC GraphLearner MAGI CoCo (Ours) Figure 3: The t-SNE results comparing our CoCo with competitive baselines on two datasets. The first row and second row correspond to Cora and AMAP, respectively. 3.5 Sensitivity Analysis Here, we study the sensitivity of key hyper-parameters: the subspace dimension K, the anchor number M, and the teleport probability α. The results are presented in Figure 4 and Appendix I. We also perform robust analysis with varying t (in Equation 1) in Appendix J. Effect of K. As shown in the first row of Figure 4, when K ranges from 32 to 128, the clustering performance under four metrics on two datasets increases slowly. However, as K further increases, the performance of the model starts to decline. This is because incorporating (a) Cora (b) AMAP Figure 4: Sensitivity experimental results. too high-dimensional subspace introduces redundant or irrelevant underlying structural information, which hinders the compactness of node embeddings. Effect of M. The second row of Figure 4 reports the impact of the number of anchor samples M in the queue. It can be observed that when M is very small (M=64), the model’s performance is poorer. This is because for each node, there are not enough anchor samples in its vicinity to adequately represent the node’s neighborhood structure. As M increases, the model maintains relatively high performance and remains stable. This allows the model to better capture the neighborhood structure information of nodes and enhances consistency learning. Effect of α. In the third row of Figure 4, we report the impact of the teleport probability α in graph diffusion matrix S. It can be observed that the model performance remains relatively stable when α is set to 0.1 or 0.2. However, as α continues to increase, the performance begins to decline, with a particularly noticeable drop at α = 0.8. This is because a larger α leads to a more “localized” diffusion scope (prioritizing the node’s own information), causing the two branches to capture increasingly similar information and thus failing to provide additional benefits. In contrast, a smaller α results in a more “global” diffusion (integrating information across the entire graph), which is more critical for capturing richer and complementary knowledge. 3.6 Robustness Analysis on Noisy Graphs To further assess the effectiveness and robustness of CoCo, we construct noisy graphs from BAT under three noise settings: (1) attribute noise by adding Gaussian noise (0,5)N(0,5); (2) edge noise by Table 3: Comparison of accuracy on noisy BAT. Noise Type Attribute Edge Attribute & Edge GraphLearner 52.52 36.79 38.63 MAGI 36.26 38.70 35.19 CoCo (Ours) 64.12 55.57 48.78 randomly adding/deleting edges with probability 0.3; and (3) both attribute and edge noise. The clustering accuracy results in Table 3 show that, although noise degrades performance for all methods (cf. Table 1), our CoCo still consistently outperforms GraphLearner and MAGI. It highlights the strong redundancy-reduction and noise-resistant ability of compactness learning, as well as the role of consistency learning in capturing richer semantic information to ensure robustness when facing noise. 3.7 Performance Comparison on Heterophilic Graphs To further validate the applicability of our method, we compare the proposed CoCo with competitive baselines on the heterophilic graphs Cornell and Wisconsin (Pei et al., 2020), and we also compare CoCo on homophilic graphs with method tailored for homophilic graphs, i.e., DGCN (Pan and Kang, 2023). From Table 5, our CoCo mostly outperforms the recent competitive baselines GraphLearner and MAGI on heterophilic graphs, likely due to its robustness against cross-class edges via compactness and consistency learning. From Table 5, CoCo also surpasses DGCN on homophilic graphs, further confirming the effectiveness and applicability of our CoCo. Table 4: Comparison on heterophilic graphs. Dataset GraphLearner MAGI CoCo (Ours) ACC NMI ACC NMI ACC NMI Cornell 43.00 14.17 34.26 7.63 59.68 24.34 Wisconsin 46.06 19.38 33.39 8.40 56.39 17.04 Table 5: Comparison on homophilic graphs. Dataset DGCN CoCo (Ours) ACC NMI ACC NMI Cora 72.89 56.82 79.36 60.71 AMAP 76.06 65.36 79.27 68.85 3.8 Time and Space Complexity Comparison (a) Cora-Runtime (b) Cora-Memory (c) AMAP-Runtime (d) AMAP-Memory Figure 5: Comparisons of average training time per epoch and memory cost. In this part, we compare the time and space complexities of our CoCo with several latest and competitive methods, i.e., CCGC, Dink-Net, GraphLearner, MAGI, in Figure 5. The results show a comparison of clustering accuracy (ACC, ↑ ) and average runtime/memory cost (↓ ) among different methods. Our CoCo achieves best clustering performance on Cora and AMAP while maintaining relatively low time and space complexity, which further demonstrates the efficiency and scalability of our approach. Detailed theoretical analysis and comparison are provided in Appendix E. Table 6: Impact of EM iterations. Iterations Cora AMAP NMI Efficiency NMI Efficiency 1 47.99± 4.07 1.62% 62.96± 2.16 2.23% 5 59.81± 0.73 2.93% 68.50± 1.25 3.27% 10 60.71± 0.59 4.28% 68.85± 1.55 4.24% 20 60.69± 0.57 6.69% 68.87± 1.88 6.16% 30 60.70± 0.60 8.46% 68.81± 1.70 8.42% Besides, to explore the impact of EM iterations on efficiency, we here we examine how different iteration counts affect performance (using NMI as an example) and efficiency (EM time per iteration / total time per iteration), with the results presented in Table 6. From the results, we can see that although the proportion of EM iteration time in the total runtime gradually increases with the number of iterations, the performance stabilizes after 10 iterations, indicating that the model has already converged. Further increasing the number of EM iterations yields no additional benefits. Therefore, it can be concluded that the EM iterative algorithm accounts for only about 4% of the total training time, demonstrating remarkably high efficiency. Table 7: Performance comparison on node classification task (OOM denotes Out of Memory). Dataset WikiCS Computers Photo Coauthor CS Coauthor Physics GCN 77.19±0.12 86.51±0.54 92.42±0.22 93.03±0.31 95.65±0.16 node2vec 71.79±0.05 84.39±0.08 89.67±0.12 85.08±0.03 91.19±0.04 DeepWalk 74.35±0.06 85.68±0.06 89.44±0.11 84.61±0.22 91.77±0.15 DGI 75.35±0.14 83.95±0.47 91.61±0.22 92.15±0.63 94.51±0.52 GMI 74.85±0.08 82.21±0.31 90.68±0.17 OOM OOM MVGRL 77.52±0.08 87.52±0.11 91.74±0.07 92.11±0.12 95.33±0.03 GCA 78.30±0.62 88.49±0.51 92.99±0.27 92.76±0.16 OOM GRACE 78.25±0.65 88.15±0.43 92.52±0.32 92.60±0.11 OOM CCA-SSG 77.88±0.41 87.01±0.41 92.59±0.25 92.77±0.17 95.16±0.10 BGRL 79.36±0.53 88.35±0.32 92.87±0.27 91.72±0.21 95.43±0.09 GTCA 79.58±0.65 89.15±0.57 92.97±0.31 92.33±0.18 95.24±0.07 CoCo 80.06±0.45 89.62±0.43 93.34±0.37 93.07±0.13 95.52±0.08 3.9 Evaluation on Node Classification Task We further analyze the generalization ability of our CoCo to verify whether the learned node representations perform well on downstream tasks beyond graph clustering task, taking node classification as an example. We evaluate its performance under the predicted accuracy metric using widely adopted datasets including WikiCS (Mernyei and Cangea, 2020), Computers (McAuley et al., 2015), Photo (McAuley et al., 2015), Coauthor CS (Sinha et al., 2015), and Coauthor Physics (Sinha et al., 2015), and compare it with several competitive state-of-the-art methods, i.e., GCN (Kipf and Welling, 2017), node2vec (Grover and Leskovec, 2016), DeepWalk (Perozzi et al., 2014), DGI (Velickovic et al., 2019), GMI (Peng et al., 2020), MVGRL (Hassani and Khasahmadi, 2020), GCA (Zhu et al., 2020), GRACE (Zhu et al., 2021), CCA-SSG (Zhang et al., 2021), BGRL (Thakoor et al., 2022) and GTCA (Liang et al., 2025a). Specifically, we first perform unsupervised pre-training using the proposed framework, followed by supervised fine-tuning on a labeled dataset. As shown in Table 7, our proposed CoCo outperforms all baseline methods across all datasets, demonstrating the strong generalizability of our learned node representations. This superior performance can be attributed to our method’s ability to capture structural information from multiple perspectives and learn low-rank node representations that align more closely with the data distribution, effectively supporting various downstream tasks. 4 Conclusion In this paper, we propose a novel approach named CoCo for deep graph clustering. CoCo first encodes the attribute and topology information from local and global views. Then CoCo exploits low-rank embeddings via GMM to remove noise and redundancy, thereby uncovering the intrinsic structure of nodes. Based on the compact low-rank embeddings, CoCo also performs consistency learning of node similarities to enrich semantics information. Experiments under different data types (homophilic, heterophilic, and noisy graphs) and different tasks (graph clustering mainly and node classificaion) show that our CoCo outperforms the state-of-the-art methods. In addition, the comparison of spatiotemporal complexity demonstrates the efficiency of our method. For future work, we aim to extend our model to temporal graph clustering and single-cell genomics clustering, facilitating the analysis of dynamic structures and accurate grouping of cells by genetic profiles. Acknowledgments This work is supported in part by the National Natural Science Foundation of China under Grants 62306014, 12501344 and 12131001, the Fundamental Research Funds for the Central Universities, LPMC, and KLMDASR, the Postdoctoral Fellowship Program (Grade A) of CPSF under Grant BX20250376 and BX20240239, the China Postdoctoral Science Foundation under Grant 2024M762201, the Sichuan Science and Technology Program under Grant 2025ZNSFSC1506 and 2025ZNSFSC0808, and the Sichuan University Interdisciplinary Innovation Fund. References Abbahaddou et al. (2024) Y. Abbahaddou, S. Ennadir, J. F. Lutzeyer, M. Vazirgiannis, and H. Boström Bounding the expected robustness of graph neural networks subject to node feature attacks. In International Conference on Learning Representations, Cited by: §K.3. Alchihabi et al. (2023) A. Alchihabi, Q. En, and Y. Guo Efficient low-rank gnn defense against structural attacks. In IEEE International Conference on Knowledge Graph, p. 1–8. Cited by: §K.3. Andersen et al. (2006) R. Andersen, F. Chung, and K. Lang Local graph partitioning using pagerank vectors. In Annual IEEE Symposium on Foundations of Computer Science, p. 475–486. Cited by: §2.1. Bo et al. (2020) D. Bo, X. Wang, C. Shi, M. Zhu, E. Lu, and P. Cui Structural deep clustering network. In Proceedings of The Web Conference, p. 1400–1410. Cited by: §K.1, Appendix F, Appendix F, §1, §1, §3.1. Cai et al. (2023) C. Cai, T. S. Hy, R. Yu, and Y. Wang On the connection between mpnn and graph transformer. In International Conference on Machine Learning, p. 3408–3430. Cited by: §K.2. Chen et al. (2020a) D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on Artificial Intelligence, Vol. 34, p. 3438–3445. Cited by: §1, §2.1. Chen et al. (2020b) T. Chen, S. Kornblith, M. Norouzi, and G. Hinton A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, p. 1597–1607. Cited by: Appendix C, Appendix C, §3.3. Cheng et al. (2021) J. Cheng, Q. Wang, Z. Tao, D. Xie, and Q. Gao Multi-view attribute graph convolution networks for clustering. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, p. 2973–2979. Cited by: §K.1. Cui et al. (2020) G. Cui, J. Zhou, C. Yang, and Z. Liu Adaptive graph encoder for attributed graph embedding. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, p. 976–985. Cited by: Appendix F, §3.1. Dempster et al. (1977) A. P. Dempster, N. M. Laird, and D. B. Rubin Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society Series B: Statistical Methodology 39 (1), p. 1–22. Cited by: Appendix A, §2.2, §2.2. Deng et al. (2023) Z. Deng, Y. Dong, and J. Zhu Batch virtual adversarial training for graph convolutional networks. AI Open 4, p. 73–79. Cited by: §K.3. Feng et al. (2019) F. Feng, X. He, J. Tang, and T. Chua Graph adversarial training: dynamically regularizing based on graph structure. IEEE Transactions on Knowledge and Data Engineering 33 (6), p. 2493–2504. Cited by: §K.3. Fu et al. (2025) Y. Fu, Y. Zhang, C. Chen, J. JianwenMa, Q. Yuan, R. Tu, X. Huang, W. Ye, X. Luo, and M. Deng MARK: multi-agent collaboration with ranking guidance for text-attributed graph clustering. In Findings of the Association for Computational Linguistics: ACL 2025, p. 6057–6072. Cited by: §K.1. Gasteiger et al. (2019) J. Gasteiger, S. Weißenberger, and S. Günnemann Diffusion improves graph learning. Advances in Neural Information Processing Systems 32. Cited by: Appendix E. Gilmer et al. (2017) J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl Neural message passing for quantum chemistry. In International Conference on Machine Learning, p. 1263–1272. Cited by: §K.2, §1. Gong et al. (2022) L. Gong, S. Zhou, W. Tu, and X. Liu Attributed graph clustering with dual redundancy reduction. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, p. 3015–3021. Cited by: Appendix F, §3.1. Grover and Leskovec (2016) A. Grover and J. Leskovec Node2vec: scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 855–864. Cited by: §3.9. Guo et al. (2017) X. Guo, L. Gao, X. Liu, and J. Yin Improved deep embedded clustering with local structure preservation. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, p. 1753–1759. Cited by: Appendix F, §3.1. Guo et al. (2025) Z. Guo, Z. Shen, X. Xie, L. Wen, and Z. Kang Disentangling homophily and heterophily in multimodal graph clustering. In Proceedings of the 33rd ACM International Conference on Multimedia, p. 2044–2053. Cited by: §K.1. Guo et al. (2024) Z. Guo, L. Xia, Y. Yu, Y. Wang, K. Lu, Z. Huang, and C. Huang Graphedit: large language models for graph structure learning. arXiv preprint arXiv:2402.15183. Cited by: §K.2. Hassani and Khasahmadi (2020) K. Hassani and A. H. Khasahmadi Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, p. 4116–4126. Cited by: Appendix F, §3.1, §3.9. He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, p. 770–778. Cited by: §2.2. Horn and Johnson (2012) R. A. Horn and C. R. Johnson Matrix analysis. Cambridge University Press. Cited by: §B.1. Huo et al. (2023) C. Huo, D. Jin, Y. Li, D. He, Y. Yang, and L. Wu T2-gnn: graph neural networks for graphs with incomplete features and structure via teacher-student distillation. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 4339–4346. Cited by: §K.3. Jin et al. (2022a) P. Jin, J. Huang, F. Liu, X. Wu, S. Ge, G. Song, D. Clifton, and J. Chen Expectation-maximization contrastive learning for compact video-and-language representations. Advances in Neural Information Processing Systems 35, p. 30291–30306. Cited by: §2.2. Jin et al. (2022b) W. Jin, X. Liu, X. Zhao, Y. Ma, N. Shah, and J. Tang Automated self-supervised learning for graphs. In International Conference on Learning Representations, Cited by: Appendix F, §3.1. Ju et al. (2023) W. Ju, Y. Gu, B. Chen, G. Sun, Y. Qin, X. Liu, X. Luo, and M. Zhang Glcc: a general framework for graph-level clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 4391–4399. Cited by: §K.1, §1. Ju et al. (2024a) W. Ju, Z. Mao, S. Yi, Y. Qin, Y. Gu, Z. Xiao, Y. Wang, X. Luo, and M. Zhang Hypergraph-enhanced dual semi-supervised graph classification. In Forty-first International Conference on Machine Learning, p. 22594–22604. Cited by: §K.2. Ju et al. (2024b) W. Ju, S. Yi, Y. Wang, Q. Long, J. Luo, Z. Xiao, and M. Zhang A survey of data-efficient graph learning. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, p. 8104–8113. Cited by: §K.3. Ju et al. (2025) W. Ju, S. Yi, Y. Wang, Z. Xiao, Z. Mao, H. Li, Y. Gu, Y. Qin, N. Yin, S. Wang, et al. A survey of graph neural networks in real world: imbalance, noise, privacy and ood challenges. IEEE Transactions on Pattern Analysis and Machine Intelligence, p. 3036–3055. Cited by: §K.3. Ju et al. (2026) W. Ju, W. Zhang, S. Yi, Z. Mao, Y. Wang, J. Yuan, Z. Xiao, Z. Qiao, and M. Zhang Identifying and correcting label noise for robust gnns via influence contradiction. arXiv preprint arXiv:2601.17469. Cited by: §K.3. Kang et al. (2019) Z. Kang, H. Pan, S. C. Hoi, and Z. Xu Robust graph learning from noisy data. IEEE Transactions on Cybernetics 50 (5), p. 1833–1843. Cited by: §1. Kipf and Welling (2017) T. N. Kipf and M. Welling Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, Cited by: §3.9. Lee et al. (2022) N. Lee, J. Lee, and C. Park Augmentation-free self-supervised learning on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 7372–7380. Cited by: Appendix F, §3.1. Li et al. (2025) R. Li, X. Luo, Z. Xiao, W. Ju, and M. Zhang HEAL: hybrid enhancement with llm-based agents for text-attributed hypergraph self-supervised representation learning. In Findings of the Association for Computational Linguistics: EMNLP 2025, p. 6815–6829. Cited by: §K.2. Liang et al. (2025a) J. Liang, X. Wei, M. Chen, Z. Wang, and J. Liang GNN-transformer cooperative architecture for trustworthy graph contrastive learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 18667–18675. Cited by: §3.9. Liang et al. (2023) K. Liang, Y. Liu, S. Zhou, W. Tu, Y. Wen, X. Yang, X. Dong, and X. Liu Knowledge graph contrastive learning based on relation-symmetrical structure. IEEE Transactions on Knowledge and Data Engineering 36 (1), p. 226–238. Cited by: §K.2. Liang et al. (2025b) K. Liang, L. Meng, H. Li, J. Wang, L. Lan, M. Li, X. Liu, and H. Wang From concrete to abstract: multi-view clustering on relational knowledge. IEEE Transactions on Pattern Analysis and Machine Intelligence. Cited by: §1. Liu et al. (2023a) Y. Liu, K. Liang, J. Xia, X. Yang, S. Zhou, M. Liu, X. Liu, and S. Z. Li Reinforcement graph clustering with unknown cluster number. In Proceedings of the 31st ACM International Conference on Multimedia, p. 3528–3537. Cited by: §K.1, Appendix F, Appendix G, §3.1. Liu et al. (2023b) Y. Liu, K. Liang, J. Xia, S. Zhou, X. Yang, X. Liu, and S. Z. Li Dink-net: neural clustering on large graphs. In International Conference on Machine Learning, p. 21794–21812. Cited by: §K.1, Appendix F, §3.1. Liu et al. (2022a) Y. Liu, W. Tu, S. Zhou, X. Liu, L. Song, X. Yang, and E. Zhu Deep graph clustering via dual correlation reduction. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 7603–7611. Cited by: §1. Liu et al. (2022b) Y. Liu, J. Xia, S. Zhou, X. Yang, K. Liang, C. Fan, Y. Zhuang, S. Z. Li, X. Liu, and K. He A survey of deep graph clustering: taxonomy, challenge, application, and open resource. arXiv preprint arXiv:2211.12875. Cited by: §K.1, §1. Liu et al. (2023c) Y. Liu, X. Yang, S. Zhou, X. Liu, S. Wang, K. Liang, W. Tu, and L. Li Simple contrastive graph clustering. IEEE Transactions on Neural Networks and Learning Systems 35 (10), p. 13789–13800. Cited by: Appendix F, §3.1. Liu et al. (2024a) Y. Liu, J. Li, Y. Chen, R. Wu, E. Wang, J. Zhou, S. Tian, S. Shen, X. Fu, C. Meng, et al. Revisiting modularity maximization for graph clustering: a contrastive learning perspective. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 1968–1979. Cited by: Appendix F, §1, §3.1. Liu et al. (2024b) Y. Liu, X. Gao, T. He, T. Zheng, J. Zhao, and H. Yin Reliable node similarity matrix guided contrastive graph clustering. IEEE Transactions on Knowledge and Data Engineering 36 (12), p. 9123–9135. Cited by: §K.1. McAuley et al. (2015) J. McAuley, C. Targett, Q. Shi, and A. Van Den Hengel Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 43–52. Cited by: §3.9. Mernyei and Cangea (2020) P. Mernyei and C. Cangea Wiki-cs: a wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv:2007.02901. Cited by: §3.9. Ng et al. (2001) A. Ng, M. Jordan, and Y. Weiss On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems, Vol. 14. Cited by: §1. Page et al. (1999) L. Page, S. Brin, R. Motwani, and T. Winograd The pagerank citation ranking: bringing order to the web.. Technical report Stanford InfoLab. Cited by: §2.1. Pan and Kang (2021) E. Pan and Z. Kang Multi-view contrastive graph clustering. In Advances in Neural Information Processing Systems, Vol. 34, p. 2148–2159. Cited by: §K.1. Pan and Kang (2023) E. Pan and Z. Kang Beyond homophily: reconstructing structure for graph-agnostic clustering. In International Conference on Machine Learning, p. 26868–26877. Cited by: §K.1, §3.7. Pan et al. (2019) S. Pan, R. Hu, S. Fung, G. Long, J. Jiang, and C. Zhang Learning graph embedding with adversarial training methods. IEEE Transactions on Cybernetics 50 (6), p. 2475–2487. Cited by: Appendix F, §3.1. Pei et al. (2020) H. Pei, B. Wei, K. C. C. Chang, Y. Lei, and B. Yang GEOM-gcn: geometric graph convolutional networks. In International Conference on Learning Representations, Cited by: §3.7. Peng et al. (2020) Z. Peng, W. Huang, M. Luo, Q. Zheng, Y. Rong, T. Xu, and J. Huang Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, p. 259–270. Cited by: §3.9. Peng et al. (2021) Z. Peng, H. Liu, Y. Jia, and J. Hou Attention-driven graph clustering network. In Proceedings of the 29th ACM International Conference on Multimedia, p. 935–943. Cited by: §K.1. Perozzi et al. (2014) B. Perozzi, R. Al-Rfou, and S. Skiena Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 701–710. Cited by: §3.9. Ren et al. (2025) T. Ren, H. Zhang, Y. Wang, W. Ju, C. Liu, F. Meng, S. Yi, and X. Luo MHGC: multi-scale hard sample mining for contrastive deep graph clustering. Information Processing & Management 62 (4), p. 104084. Cited by: §K.1. Ren et al. (2019) Z. Ren, Q. Sun, B. Wu, X. Zhang, and W. Yan Learning latent low-rank and sparse embedding for robust image feature extraction. IEEE Transactions on Image Processing 29, p. 2094–2107. Cited by: §2.2, §2.2. Richardson and Green (1997) S. Richardson and P. J. Green On Bayesian analysis of mixtures with an unknown number of components (with discussion). Journal of the Royal Statistical Society Series B: Statistical Methodology 59 (4), p. 731–792. Cited by: Appendix A, §2.2. Sen et al. (2008) P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad Collective classification in network data. AI magazine 29 (3), p. 93–93. Cited by: Appendix F, §3.1. Shchur et al. (2018) O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868. Cited by: Appendix F, §3.1. Shi et al. (2019) D. Shi, L. Zhu, Y. Li, J. Li, and X. Nie Robust structured graph clustering. IEEE Transactions on Neural Networks and Learning Systems 31 (11), p. 4424–4436. Cited by: §K.1. Sinha et al. (2015) A. Sinha, Z. Shen, Y. Song, H. Ma, D. Eide, B. Hsu, and K. Wang An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th International Conference on World Wide Web, p. 243–246. Cited by: §3.9. Tang et al. (2019) C. Tang, X. Liu, X. Zhu, J. Xiong, M. Li, J. Xia, X. Wang, and L. Wang Feature selective projection with low-rank embedding and dual laplacian regularization. IEEE Transactions on Knowledge and Data Engineering 32 (9), p. 1747–1760. Cited by: §2.2. Thakoor et al. (2022) S. Thakoor, C. Tallec, M. G. Azar, M. Azabou, E. L. Dyer, R. Munos, P. Velickovic, and M. Valko Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representations, Cited by: §3.9. Trivedi et al. (2024) P. Trivedi, N. Choudhary, E. Huang, V. N. Ioannidis, K. Subbian, and D. Koutra Large language model guided graph clustering. In Learning on Graphs Conference, Cited by: §K.1. Tu et al. (2021) W. Tu, S. Zhou, X. Liu, X. Guo, Z. Cai, E. Zhu, and J. Cheng Deep fusion clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 9978–9987. Cited by: §K.1, Appendix F, §3.1. Van der Maaten and Hinton (2008) L. Van der Maaten and G. Hinton Visualizing data using t-sne. Journal of Machine Learning Research 9 (11). Cited by: §3.4. Velickovic et al. (2019) P. Velickovic, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm Deep graph infomax. In International Conference on Learning Representations, Cited by: §3.9. Vidal (2011) R. Vidal Subspace clustering. IEEE Signal Processing Magazine 28 (2), p. 52–68. Cited by: §1. Wang et al. (2019) C. Wang, S. Pan, R. Hu, G. Long, J. Jiang, and C. Zhang Attributed graph clustering: a deep attentional embedding approach. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, p. 3670–3676. Cited by: Appendix F, §3.1. Wang et al. (2025a) Q. Wang, H. Xu, Z. Zhang, W. Feng, and Q. Gao Deep multi-modal graph clustering via graph transformer network. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 7835–7843. Cited by: §1. Wang and Yang (2022) Y. Wang and Y. Yang Bayesian robust graph contrastive learning. arXiv preprint arXiv:2205.14109. Cited by: §K.3. Wang et al. (2025b) Y. Wang, Y. Ding, Y. Gu, Z. Qiao, C. Chen, X. Hua, M. Zhang, and W. Ju Deep graph clustering with disentangled representation learning. In Proceedings of the 33rd ACM International Conference on Multimedia, p. 767–776. Cited by: §K.1. Wei et al. (2018) Z. Wei, X. He, X. Xiao, S. Wang, S. Shang, and J. Wen Topppr: top-k personalized pagerank queries with precision guarantees on large graphs. In Proceedings of the 2018 International Conference on Management of Data, p. 441–456. Cited by: §2.1. Wu et al. (2019) F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger Simplifying graph convolutional networks. In International Conference on Machine Learning, p. 6861–6871. Cited by: §2.1. Wu et al. (2022) Q. Wu, W. Zhao, Z. Li, D. P. Wipf, and J. Yan Nodeformer: a scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems 35, p. 27387–27401. Cited by: §K.2. Xia et al. (2022) J. Xia, L. Wu, G. Wang, J. Chen, and S. Z. Li Progcl: rethinking hard negative mining in graph contrastive learning. In International Conference on Machine Learning, p. 24332–24346. Cited by: Appendix F, §3.1. Xie et al. (2016) J. Xie, R. Girshick, and A. Farhadi Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning, p. 478–487. Cited by: Appendix F, §3.1. Xing et al. (2024) Y. Xing, X. Wang, Y. Li, H. Huang, and C. Shi Less is more: on the over-globalizing problem in graph transformers. In International Conference on Machine Learning, p. 54656–54672. Cited by: §K.2. Yan et al. (2006) S. Yan, D. Xu, B. Zhang, H. Zhang, Q. Yang, and S. Lin Graph embedding and extensions: a general framework for dimensionality reduction. IEEE transactions on Pattern Analysis and Machine Intelligence 29 (1), p. 40–51. Cited by: §1. Yang et al. (2023) X. Yang, Y. Liu, S. Zhou, S. Wang, W. Tu, Q. Zheng, X. Liu, L. Fang, and E. Zhu Cluster-guided contrastive graph clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, p. 10834–10842. Cited by: §K.1, Appendix F, Appendix F, §1, §3.1. Yang et al. (2024) X. Yang, E. Min, K. Liang, Y. Liu, S. Wang, S. Zhou, H. Wu, X. Liu, and E. Zhu Graphlearner: graph node clustering with fully learnable augmentation. In Proceedings of the 32nd ACM international conference on multimedia, p. 5517–5526. Cited by: Appendix F, §1, §3.1. Yi et al. (2023) S. Yi, W. Ju, Y. Qin, X. Luo, L. Liu, Y. Zhou, and M. Zhang Redundancy-free self-supervised relational learning for graph clustering. IEEE Transactions on Neural Networks and Learning Systems 35 (12), p. 18313–18327. Cited by: §K.1. Yi et al. (2025a) S. Yi, Z. Mao, Y. Wang, Y. Gu, Z. Xiao, C. Chen, X. Hua, M. Zhang, and W. Ju Hypergraph consistency learning with relational distillation. IEEE Transactions on Multimedia, p. 7028–7039. Cited by: §K.2. Yi et al. (2025b) S. Yi, Z. Mao, K. Zheng, Z. Xiao, Z. Qiao, C. Chen, X. Hua, Y. Zhou, M. Zhang, and W. Ju Learning generalizable contrastive representations for graph zero-shot learning. IEEE Transactions on Multimedia, p. 7584–7595. Cited by: §K.2. Ying et al. (2021) C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T. Liu Do transformers really perform badly for graph representation?. In Advances in Neural Information Processing Systems, Vol. 34, p. 28877–28888. Cited by: §K.2. You et al. (2020) Y. You, T. Chen, Y. Sui, T. Chen, Z. Wang, and Y. Shen Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, Vol. 33, p. 5812–5823. Cited by: Appendix C, Appendix C. Yuan et al. (2023a) J. Yuan, X. Luo, Y. Qin, Z. Mao, W. Ju, and M. Zhang Alex: towards effective graph transfer learning with noisy labels. In Proceedings of the 31st ACM international conference on multimedia, p. 3647–3656. Cited by: §K.3. Yuan et al. (2023b) J. Yuan, X. Luo, Y. Qin, Y. Zhao, W. Ju, and M. Zhang Learning on graphs under label noise. In IEEE International Conference on Acoustics, Speech and Signal Processing, p. 1–5. Cited by: §K.3. Zhang et al. (2021) H. Zhang, Q. Wu, J. Yan, D. Wipf, and P. S. Yu From canonical correlation analysis to self-supervised graph neural networks. Advances in Neural Information Processing Systems 34, p. 76–89. Cited by: §3.9. Zhang et al. (2022) Z. Zhang, Q. Liu, Q. Hu, and C. Lee Hierarchical graph transformer with adaptive node sampling. In Advances in Neural Information Processing Systems, Vol. 35, p. 21171–21183. Cited by: §K.2. Zhao et al. (2021) H. Zhao, X. Yang, Z. Wang, E. Yang, and C. Deng Graph debiased contrastive learning with joint representation clustering. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, p. 3434–3440. Cited by: Appendix F, §3.1. Zhu et al. (2020) Y. Zhu, Y. Xu, F. Yu, Q. Liu, S. Wu, and L. Wang Deep graph contrastive representation learning. arXiv preprint arXiv:2006.04131. Cited by: §3.9. Zhu et al. (2021) Y. Zhu, Y. Xu, F. Yu, Q. Liu, S. Wu, and L. Wang Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, p. 2069–2080. Cited by: §3.9. Appendix A Expectation-Maximization Algorithm for Gaussian Mixture Model The Gaussian mixture model (GMM) (Richardson and Green, 1997) is a linear superposition of multiple Gaussian components. Assuming GMM consists of K Gaussians, given the observed data =(1,…,N)⊤X=(x_1,…,x_N) , the likelihood function is given by p(|)=∏i=1N(∑k=1Kπk(i|k,k)),p(X| θ)= _i=1^N ( _k=1^K _kN (x_i| μ_k, _k ) ), where =πk,k,kk=1K θ=\ _k, μ_k, _k\_k=1^K, (|k,k)N(x| μ_k, _k) is the probability density function of the k-th Gaussian, and πk _k is the prior probability. We can employ the expectation-maximization (EM) algorithm (Dempster et al., 1977) to fit GMM, in which the latent variables =(yik)∈ℝN×KY=(y_ik) ^N× K are introduced to indicate whether the i-th sample belongs to the k-th Gaussian by yiky_ik. In the E step, EM computes the posterior probability: γ(yik)=p(yik=1|i,old)=πkold(i|kold,kold)∑j=1Kπjold(i|jold,jold),γ(y_ik)=p(y_ik=1|x_i, θ^old)= _k^oldN(x_i| μ_k^old, _k^old) _j=1^K _j^oldN(x_i| μ_j^old, _j^old), and the posterior expectation: Q(,old)= Q( θ, θ^old)= ∑k=1K∑i=1Nγ(yik)(logπk+log(i|k,k)). _k=1^K _i=1^Nγ(y_ik)( _k+ N(x_i| μ_k, _k)). In the M step, EM maximizes Q(,old)Q( θ, θ^old) to achieve the updated parameters new θ^new: knew= μ_k^new= 1∑i=1Nγ(yik)∑i=1Nγ(yik)i,πknew=∑i=1Nγ(yik)N, 1 _i=1^Nγ(y_ik) _i=1^Nγ(y_ik)x_i,~~ _k^new= _i=1^Nγ(y_ik)N, knew= _k^new= 1∑i=1Nγ(yik)∑i=1Nγ(yik)(i−knew)(i−knew)⊤. 1 _i=1^Nγ(y_ik) _i=1^Nγ(y_ik)(x_i- μ_k^new)(x_i- μ_k^new) . Appendix B Proofs B.1 Proof of Theorem 2.1. Proof. The smoothness of a graph signal x, defined on the vertices of the graph, can be characterized by the Rayleigh quotient based on the normalized graph Laplacian matrix ~ L (Horn and Johnson, 2012), i.e., ⊤~/⊤x Lx/x x, which expresses the normalized variance score of x. The smaller this value is, the smoother the signal is. Denote by ~p=(~1p,…,~Np)⊤ U^p=( u_1^p,…, u_N^p) and ~p=diag(λ~1p,…,λ~Np) ^p= diag( λ_1^p,…, λ_N^p) the eigenvector matrix and eigenvalue matrix of ~p(p=l,g) L^p(p=l,g). Based on the eigendecomposition of ~p L^p, the signal x can be decomposed into: ~pp=∑i=1Ncip~ip(Fourier inverse transform), U^pc^p= _i=1^Nc_i^p u_i^p~(Fourier inverse transform), where pc^p is the coefficient vector. Then the filtered signal by Equation 1 is ~p=∑i=1N(1−λ~ip/kp)tcip~ip x^p= _i=1^N(1- λ^p_i/k^p)^tc_i^p u_i^p and the corresponding Rayleigh quotient is: ~p⊤~pp~~p⊤~p=∑i=1N[(1−λ~ip/kp)tcip]2λ~ip∑i=1N[(1−λ~ip/kp)tcip]2. x^p L^p x^p x^p x^p= _i=1^N[(1- λ_i^p/k^p)^tc_i^p]^2 λ_i^p _i=1^N[(1- λ_i^p/k^p)^tc_i^p]^2. To filter high-frequency noise, kpk^p should be set to ensure the low-pass property of the filter (for any t), also the smoothness. On the one hand, 1−λ~ip/kp1- λ_i^p/k^p should be non-negative. Hence, kp≥λ~ipk^p≥ λ_i^p for any 1≤i≤N1≤ i≤ N, which leads to kp≥λ~maxpk^p≥ λ_max^p. On the other hand, 1−λ~ip/kp1- λ_i^p/k^p should become smaller as λ~ip λ_i^p becomes larger to ensure that the filter captures low-frequency signal. So the value of kpk^p should be small and the optimal kpk^p is set to λ~maxp λ_max^p, which completes the proof. ∎ B.2 Proof of Remark 2.2. Proof. By the conditional probability formula, we have: logp(|new)= p(Z| λ^new)= logp(,|new)−logp(|,new). p(Z,Y| λ^new)- p(Y|Z, λ^new). Hence, we further have: logp(|new)= p(Z| λ^new)= ∫p(|,old)logp(|new) p(Y|Z, λ^old) p(Z| λ^new)dY = = ∫p(|,old)logp(,|new)− p(Y|Z, λ^old) p(Z,Y| λ^new)dY- ∫p(|,old)logp(|,new) p(Y|Z, λ^old) p(Y|Z, λ^new)dY ≜ Q(new,old)−H(new,old). Q( λ^new, λ^old)-H( λ^new, λ^old). If Q(new,old)≥Q(old,old)Q( λ^new, λ^old)≥ Q( λ^old, λ^old) and H(new,old)≤H(old,old)H( λ^new, λ^old)≤ H( λ^old, λ^old) hold, we can conclude that: logp(|new)≥logp(|old). p(Z| λ^new)≥ p(Z| λ^old). In the E step, we maximized the Q-function, which implies that Q(new,old)≥Q(old,old)Q( λ^new, λ^old)≥ Q( λ^old, λ^old). As for the H-function, we have: H(new,old)−H(old,old) H( λ^new, λ^old)-H( λ^old, λ^old) = = ∫p(|,old)logp(|,new)p(|,old) p(Y|Z, λ^old) p(Y|Z, λ^new)p(Y|Z, λ^old)dY ≤ ≤ log∫p(|,new)d=log1=0, p(Y|Z, λ^new)dY= 1=0, which follows from the Jensen inequality, i.e., E(logX)≤logE(X)E( X)≤ E(X). The proof is completed. ∎ B.3 Proof of Theorem 2.2. Proof. After the subspace training algorithm converges, according to Equation 3 and summing over k, we have: ∑k=1Kλ^ik∑j=1Dγ^(yjk)=∑k=1K∑j=1Dγ^(yjk)zij. _k=1^K λ_ik _j=1^D γ(y_jk)= _k=1^K _j=1^D γ(y_jk)z_ij. Then the following equality also holds: ∑j=1D(∑k=1Kλ^ikγ^(yjk))=∑j=1D(∑k=1Kγ^(yjk))zij. _j=1^D ( _k=1^K λ_ik γ(y_jk) )= _j=1^D ( _k=1^K γ(y_jk) )z_ij. It implies that ∑j=1Dz^ij=∑j=1Dzij _j=1^D z_ij= _j=1^Dz_ij, which follows from that ∑k=1Kγ^(yjk)=1 _k=1^K γ(y_jk)=1 and Equation 4 holds. This guarantees that the total mass of each row in Z is preserved, meaning that the aggregated information associated with individual i remains unchanged after reconstruction. Also, it ensures that the individual-level signal encoded in the original embedding is retained. In addition, the Q-function defined in the proof of Remark 2.2 can be rewritten as: Q(,old)= Q( λ, λ^old)= ∑j=1D∑k=1Kγ(yjk)log[1(2π)N¯2σ12exp(−‖⋅,j−⋅,k‖22σ)] _j=1^D _k=1^Kγ(y_jk) [ 1(2π) N2σ 12 (- ||z_·,j- λ_·,k||^22σ ) ] = = ∑j=1D∑k=1Kγ(yjk)log1(2π)N¯2σ12+∑j=1D∑k=1Kγ(yjk)⋅‖⋅,j−⋅,k‖22σ _j=1^D _k=1^Kγ(y_jk) 1(2π) N2σ 12+ _j=1^D _k=1^Kγ(y_jk)· ||z_·,j- λ_·,k||^22σ = = −Dlog[(2π)N¯2σ12]+12σ∑i=1N¯∑j=1D∑k=1Kp(yjk=1|⋅,j,⋅,k)(zij−λik)2, -D [(2π) N2σ 12]+ 12σ _i=1 N _j=1^D _k=1^Kp(y_jk=1|z_·,j, λ_·,k)(z_ij- _ik)^2, which is maximized in the M step. Obviously, continuously maximizing Q-function throughout the entire iteration process is equivalent to minimizing the objective: ∑i=1N¯∑j=1D∑k=1Kp(yjk=1|⋅,j,⋅,k)(zij−λik)2. _i=1 N _j=1^D _k=1^Kp(y_jk=1|z_·,j, λ_·,k)(z_ij- _ik)^2. (8) Again, when converging, due to that ∑k=1Kγ^(yjk)=1 _k=1^K γ(y_jk)=1 and Equation 4 holds, the optimized objective in Equation 8 can be written as: ∑i=1N¯∑j=1D(zij2+∑k=1Kγ^(yjk)λ^ik2−2zijz^ij). _i=1 N _j=1^D (z_ij^2+ _k=1^K γ(y_jk) λ_ik^2-2z_ij z_ij ). As for the term ∑k=1Kγ^(yjk)λ^ik2 _k=1^K γ(y_jk) λ_ik^2, we have: ∑j=1D∑k=1Kγ^(yjk)λ^ik2=∑k=1Kλ^ik2∑j=1Dγ^(yjk) _j=1^D _k=1^K γ(y_jk) λ_ik^2= _k=1^K λ_ik^2 _j=1^D γ(y_jk) = = ∑k=1Kλ^ik2⋅∑j=1Dγ^(yjk)zijλ^ik(by Equation 3) _k=1^K λ_ik^2· _j=1^D γ(y_jk)z_ij λ_ik (by Equation~ em_lambda) = = ∑j=1Dzij∑k=1Kλ^ikγ^(yjk)=∑j=1Dzijz^ij. _j=1^Dz_ij _k=1^K λ_ik γ(y_jk)= _j=1^Dz_ij z_ij. Thus, we can obtain that the objective in Equation 8 is minimized to ∑i=1N¯∑j=1Dzij(zij−z^ij)=∑i,jzij2⏟original total variation−∑i,jzijz^ij⏟alignment with reconstruction. _i=1 N _j=1^Dz_ij(z_ij- z_ij)= _i,jz_ij^2_original total variation- _i,jz_ij z_ij_alignment with reconstruction. The first term, ∑i,jzij2 _i,jz_ij^2, measures the total variation (energy) of the original embedding, while ∑i,jzijz^ij _i,jz_ij z_ij quantifies how much of this variation is preserved in the reconstructed representation. Notably, compared with the self-energy ∑i,j(z^ij)2 _i,j( z_ij)^2, the cross-term zijz^ijz_ij z_ij directly captures how well the reconstructed embedding aligns with the original signal rather than merely measuring its own magnitude. Hence, maximizing the cross-correlation term corresponds to keeping the dominant variations present in Z, and the above minimized objective brings a reconstruction Z that preserves as much of the original total variation as possible while suppressing redundant or noisy components, which completes the proof. ∎ Appendix C More Discussions on the proposed CoCo GMM v.s. Other optional Rank Reduction Methods. In order to obtain low-rank representations, many methods can achieve this goal. However, the advantage of GMM lies in its linear modeling complexity, with time and space complexities of O(NDK)O(NDK) and O(ND)O(ND), respectively, while PCA has time and space complexities of O(ND2+D3)O(ND^2+D^3) and O(ND+D2)O(ND+D^2). When the number of features is high, the complexity of PCA is also high. Compared to K-means, since GMM is a probabilistic model and belongs to soft clustering algorithms, it is more robust to outliers and can be applied to a wider range of data distributions. Compared to methods like autoencoders for dimensionality reduction, GMM has fewer training parameters and lower time and space complexities. Therefore, our paper chooses GMM to achieve low-rank representation learning. Of course, other better ways to conduct low-rank space training can be further explored. Consistency Learning v.s. Contrastive Learning. Contrastive learning (Chen et al., 2020b; You et al., 2020) shares similar ideas with our consistency learning, utilizing the similarity of data representations under different data augmentations to bring similar samples closer and push dissimilar samples apart. However, there are significant differences between contrastive learning and our consistency learning. First, the proposed consistency learning aims to uncover relationship information among non-iid nodes, thereby better reflecting the underlying structural distribution of nodes in the representation. Second, we consider consistency learning at the relational information level from both local and global perspectives, emphasizing alignment learning. This enables representations from two perspectives to interact, guide each other, and learn, thereby obtaining more semantically rich node representations to better serve graph clustering. Third, contrastive learning involves negative samples, whereas our consistency learning does not. In summary, contrastive learning focuses on sample discriminability at the instance level, whereas our consistency learning considers to bridge the gap between the considered local and global views at the relational distribution level. This is a higher-order, more global approach to capturing semantic knowledge in graph data. Besides, in Table 2 of the experiments section and Appendix H, we also compare the performance of our consistency learning loss with the contrastive learning loss (InfoNCE) (Chen et al., 2020b; You et al., 2020). It’s clear that our consistency learning outperforms contrastive learning by a considerable margin, which fully demonstrates that our distribution-based consistency is more capable of capturing the intrinsic dependencies between nodes at a higher semantic level. Appendix D Training Procedure The training procedure of the whole framework is shown in Algorithm 1 below. Algorithm 1 The Optimization Framework of CoCo Input: Graph =,ℰ,,G=\V,E,X,A\; Cluster number C; Output: Clustering result c; 1: Obtain the local- and global-view filtered attribute matrix ~l X^l and ~g X^g in Equation 1; 2: Initialize the trainable parameters in MLP1MLP_1 and MLP2MLP_2; 3: while not converge do 4: Update lZ^l and gZ^g by encoding ~l X^l and ~g X^g in the unshared MLP encoders; 5: Update the optimal subspace by performing iterations through Equation 3; 6: Update the reconstructed embeddings ~l Z^l and ~g Z^g by Equation 4 and Equation 5; 7: Update the similarity distributions ip^i and iq^i for i=1,…,Ni=1,…,N; 8: Calculate the loss ℒL in Equation 6; 9: Perform backpropagation and update the entire network in CoCo by minimizing ℒL; 10: end while 11: Derive clustering result c by applying K-means to the fused representations from Equation 7; Appendix E Complexity Analysis Table 8: Theoretical analysis of complexity Method Time Space MVGRL O(N2D)O(N^2D) O(N2)O(N^2) RGC O(N2D)O(N^2D) O(N2)O(N^2) CCGC O(N2D)O(N^2D) O(N2)O(N^2) Dink-Net O(NCD)O(NCD) O(NC+ND)O(NC+ND) GraphLearner O(N2D)O(N^2D) O(N2)O(N^2) MAGI O(ND2)O(ND^2) O(ND+|ℰ|+N2)O(ND+|E|+N^2) CoCo (Ours) O(NDK+NMD)O(NDK+NMD) O(ND+NM)O(ND+NM) Given a graph dataset comprising N nodes and E edges. The sparse diffusion matrix S S can be approximately calculated in linear time and space, i.e., O(N)O(N) (Gasteiger et al., 2019). Assume the number of non-zero elements in the sparse diffusion matrix S S is denoted as nnz(S^)nnz( S), the computational complexity of graph convolutional filters is O(nnz(S^)∗N)O(nnz( S)*N). For each dataset, they only need to be computed once at the beginning of training. In each epoch, GMM training and feature reconstruction have linear time complexity of O(NDK)O(NDK) and space complexity of O(ND)O(ND). Consistency learning has time complexity of O(NMD)O(NMD) and space complexity of O(NM)O(NM). In summary, the preprocessing time and space complexities of CoCo based on sparsification are O(N)O(N) and O(E)O(E), respectively. In each training epoch, the time complexity of CoCo is O(NDK+NMD)O(NDK+NMD) and the space complexity of CoCo is O(ND+NM)O(ND+NM). Comparison between our CoCo and several recent and competitive baselines is presented in the Table 8. It can be observed that, comparing with the quadratic time complexity of MVGRL, RGC, CCGC and GraphLearner, our CoCo scales linearly with the number of samples, making it more suitable for large-scale datasets where computational efficiency is crucial. Appendix F Details of Experimental Setup Datasets. Following Yang et al. (2023), we assess the performance of our CoCo with five widely used benchmark datasets for deep graph clustering, i.e., Cora (Sen et al., 2008), AMAP (Shchur et al., 2018), BAT (Liu et al., 2023c), EAT (Liu et al., 2023c), and UAT (Liu et al., 2023c). Baseline Methods. To comprehensively assess the effectiveness of our proposed CoCo, we benchmark it against leading state-of-the-art methods, including autoencoder-based deep graph clustering/self-supervised learning methods: DEC (Xie et al., 2016), IDEC (Guo et al., 2017), DAEGC (Wang et al., 2019), ARGA (Pan et al., 2019), SDCN (Bo et al., 2020), DFCN (Tu et al., 2021); and contrastive deep graph clustering/self-supervised learning methods: AGE (Cui et al., 2020), MVGRL (Hassani and Khasahmadi, 2020), GDCL (Zhao et al., 2021), AutoSSL (Jin et al., 2022b), AGC-DRR (Gong et al., 2022), AFGRL (Lee et al., 2022), GDCL (Zhao et al., 2021), ProGCL (Xia et al., 2022), RGC (Liu et al., 2023a), Dink-Net (Liu et al., 2023b), CCGC (Yang et al., 2023), GraphLearner (Yang et al., 2024), and MAGI (Liu et al., 2024a). Evaluation Metrics and Implementation Details. We adopt four benchmark metrics following Bo et al. (2020) for evaluation: Accuracy (ACC), Normalized Mutual Information (NMI), Average Rand Index (ARI), and Macro F1-score (F1). Larger values imply better clustering results. For each method, we present the mean and standard deviation of the four metrics across 10 runs. The proposed model is implemented with PyTorch and all experiments are carried out on NVIDIA GeForce RTX 4090. The hidden dimension d is set to 500 for AMAP/UAT, and 1500 for other datasets. We set the total number of training epochs to 1000 and the number of filter layers to 3. The dimension of the subspace K is set to 64 and the number of the selected anchor samples M is set to 128. The parameters of temperature τ and teleport probability α are set to 0.02 and 0.2, respectively. Appendix G Additional Main Experimental Results Table 9: Clustering performance on five benchmark datasets (mean ± standard deviation). The top two results for each method are marked in bold and underline, respectively. Dataset Metric DEC IDEC DAEGC ARGA AGE MVGRL GDCL AGC-DRR RGC Dink-Net CoCo (Ours) Cora ACC 46.50±0.26 51.61±1.02 70.43±0.36 71.04±0.25 73.50±1.83 70.47±3.70 70.83±0.47 40.62±0.55 - 77.11±0.10 79.36±0.69 NMI 23.54±0.34 26.31±1.22 52.89±0.69 51.06±0.52 57.58±1.42 55.57±1.54 56.30±0.36 18.74±0.73 57.60+1.36 59.76±0.10 60.71±0.59 ARI 15.13±0.42 22.07±1.53 49.63±0.43 47.71±0.33 48.05±0.72 48.70±3.94 50.10±2.14 14.80±1.64 49.46+2.72 38.16±0.13 58.76±1.47 F1 39.23±0.17 47.17±1.12 68.27±0.57 69.27±0.39 69.28±1.59 67.15±1.86 52.88±0.97 31.23±0.57 - 74.76±0.10 77.95±0.72 AMAP ACC 47.22±0.08 47.62±0.08 75.96±0.23 69.28±2.30 75.98±0.68 41.07±3.12 43.75±0.78 76.81±1.45 - 79.11±0.43 79.27±0.70 NMI 37.35±0.05 37.83±0.08 65.25±0.45 58.36±2.76 65.38±0.61 30.28±3.94 37.32±0.28 66.54±1.24 69.61+0.36 67.70±0.30 68.85±1.55 ARI 18.59±0.04 19.24±0.07 58.12±0.24 44.18±4.41 55.89±1.34 18.77±2.34 21.57±0.51 60.15±1.56 59.58+0.39 59.76±0.76 60.94±1.51 F1 46.71±0.12 47.20±0.11 69.87±0.54 64.30±1.95 71.74±0.93 32.88±5.50 38.37±0.29 71.03±0.64 - 72.86±0.32 72.36±1.15 BAT ACC 42.09±2.21 39.62±0.87 52.67±0.00 67.86±0.80 56.68±0.76 37.56±0.32 45.42±0.54 47.79±0.02 - 54.20±0.13 78.85±0.91 NMI 14.10±1.99 12.80±1.74 21.43±0.35 49.09±0.54 36.04±1.54 29.33±0.70 31.70±0.42 19.91±0.24 51.58+0.83 28.33±0.32 55.00±0.87 ARI 07.99±1.21 07.85±1.31 18.18±0.29 42.02±1.21 26.59±1.83 13.45±0.03 19.33±0.57 14.59±0.13 47.16+1.35 23.00±0.54 53.52±1.15 F1 42.63±2.35 40.11±0.99 52.23±0.03 67.02±1.15 55.07±0.80 29.64±0.49 39.94±0.57 42.33±0.51 - 53.22±0.17 78.56±1.01 EAT ACC 36.47±1.60 35.56±1.34 36.89±0.15 52.13±0.00 47.26±0.32 32.88±0.71 33.46±0.18 37.37±0.11 - 50.78±0.17 58.87±0.49 NMI 04.96±1.74 04.63±0.97 05.57±0.06 22.48±1.21 23.74±0.90 11.72±1.08 13.22±0.33 07.00±0.85 37.77+0.13 21.66±0.36 34.10±1.26 ARI 03.60±1.87 03.19±0.76 05.03±0.08 17.29±0.50 16.57±0.46 04.68±1.30 04.31±0.29 04.88±0.91 30.16+0.15 18.87±0.66 27.91±1.52 F1 34.84±1.28 35.52±1.50 34.72±0.16 52.75±0.07 45.54±0.40 25.35±0.75 25.02±0.21 35.20±0.17 - 48.28±0.19 58.06±2.64 UAT ACC 45.61±1.84 46.90±0.17 52.29±0.49 49.31±0.15 52.37±0.42 44.16±1.38 48.70±0.06 42.64±0.31 - 57.65±0.09 59.68±0.36 NMI 16.63±2.39 17.84±0.35 21.33±0.44 25.44±0.31 23.64±0.66 21.53±0.94 25.10±0.01 11.15±0.24 28.79±0.35 25.28±0.15 30.12±0.51 ARI 13.14±1.97 16.34±0.40 20.50±0.51 16.57±0.31 20.39±0.70 17.12±1.46 21.76±0.01 09.50±0.25 19.89±1.30 26.42±0.14 29.46±0.47 F1 44.22±1.51 46.51±0.17 50.33±0.64 50.26±0.16 50.15±0.73 39.44±2.19 45.69±0.08 35.18±0.32 - 54.52±0.10 58.03±0.34 Apart from the comparisons with a range of competitive baselines in Table 1, we carry out more extensive comparative experiments herein. Table 9 presents a performance comparison between our proposed CoCo and several other graph clustering or unsupervised learning methods. It can be seen that RGC (Liu et al., 2023a) outperforms our model on certain metrics in AMAP and EAT, possibly because RGC can automatically learn the number of clusters, which may, to some extent, better approximate the true data distribution. However, we still achieve the best performance on most datasets. It can be attributed to the fact that our proposed CoCo captures complementary semantic information from both local and global views, enabling a more comprehensive exploration of the graph’s characteristics. Moreover, our CoCo learns low-rank embeddings, which effectively removes redundancies and noise. Finally, consistency learning enriches the semantics of node representations from both local and global perspectives. Hence, different modules complement each other to facilitate better clustering assignments. Appendix H Additional Results on Influence of Consistency Learning Table 10: The comparative analysis of consistency learning across all datasets. Dataset Loss ACC NMI ARI F1 Cora MSE 77.84±0.67 60.31±0.89 57.81±1.42 73.89±1.09 InfoNCE 75.57±1.16 58.03±1.44 54.69±1.85 72.58±1.81 Consistency 79.36+0.69 60.71±0.59 58.76±1.47 77.95±0.72 AMAP MSE 77.62±0.44 67.68±0.76 58.51±0.97 71.84±0.77 InfoNCE 77.25±0.33 67.12±0.46 58.24±0.57 71.89±0.53 Consistency 79.27±0.70 68.85±1.55 60.94±1.51 72.36±1.15 BAT MSE 76.87±0.60 53.30±1.18 50.85±1.07 76.32±0.71 InfoNCE 78.70±0.53 53.99±0.74 51.85±1.14 78.03±0.51 Consistency 78.85±0.91 55.00±0.87 53.52±1.15 78.56±1.01 EAT MSE 57.42±0.45 32.80±0.86 26.27±0.74 57.83±0.38 InfoNCE 55.26±1.25 30.34±0.96 23.76±0.94 55.53±0.94 Consistency 58.87±0.49 34.10±1.26 27.91±1.52 58.06±2.64 UAT MSE 57.18±0.74 28.43±0.62 25.65±1.11 56.96±0.73 InfoNCE 56.72±0.23 27.67±0.42 25.01±0.45 56.39±0.39 Consistency 59.68±0.36 30.12±0.51 29.46±0.47 58.03±0.34 To further comprehensively verify the effectiveness of our proposed consistency learning strategy, we conduct additional experiments on two more datasets beyond Table 2. As clearly shown in Table 10, the reported results consistently show that our consistency learning significantly outperforms both MSE and InfoNCE across all evaluated datasets. This superior overall performance strongly highlights the ability of our method to effectively capture high-order semantic similarity relations via the powerful distribution-based alignment. The reason why the two compared metrics perform poorly may be that MSE only focuses on point-wise errors and ignores inter-sample correlations, while InfoNCE is prone to instability due to the influence of negative sample selection. Overall, these additional results provide a broader and more empirical basis for our conclusions, further reinforcing the superiority, and robustness of our proposed consistency learning approach. Appendix I Additional Sensitivity Analysis (a) Cora (b) AMAP (c) BAT (d) EAT (e) UAT Figure 6: The sensitivity analysis of three hyper-parameters on all five datasets. Here we extend the sensitivity analysis of the key hyper-parameters K, M and α to three additional datasets. The results in Figure 6 show that the clustering performance on all datasets increases slowly as K ranges from 32 to 128, but starts to decline when K becomes too large. This is consistent with the observations on the two datasets in Figure 4 of the main text, indicating that a too high-dimensional subspace introduces redundant or irrelevant information, which hinders the compactness of node embeddings. For the number of anchor samples M, the model’s performance is poor when M is very small, due to the insufficient anchor samples to represent the neighborhood structure of nodes. As M increases, the performance improves and remains stable, which aligns with the findings in the main text. For the teleport probability α, the model performance is stable at low α values but deteriorates with further increases, showing a marked decline at α=0.8. This trend aligns with findings in the main text. The degradation occurs because a higher α results in a more localized diffusion process, which over-prioritizes the node’s own information. Conversely, a smaller α promotes global integration of graph information, which is essential for learning diverse and complementary representations. These consistent trends across different datasets further validate the robustness of our model with respect to the three hyper-parameters. Appendix J Graph Convolutional Filter v.s.v.s. GCN To show that our proposed disentangling of graph convolutional filters (GCF) and weight matrices can enhance the robustness of the model, we conduct comparative experiments between GCF+MLP (a) Cora (b) AMAP Figure 7: Robustness analysis. and GCN under the CoCo framework as the number of convolutional layers (i.e., the parameter t in GCF, Equation 1) increased. The results are shown in Figure 7. It can be observed that GCF+MLP consistently outperforms GCN in terms of clustering performance across different convolutional layers. We also note that the performance of GCF+MLP remains relatively stable as the number of layers (t in Equation 1) increases, whereas GCN tends to first improve and then deteriorate with the addition of more layers in most cases. This evidences the high performance and robustness brought about by disentangling the GCF from the weight matrices within our CoCo framework. Appendix K Related Work K.1 Deep Graph Clustering Over the years, substantial research efforts have been devoted to advancing deep graph clustering, with the goal of partitioning nodes in a graph into cohesive and well-connected clusters in an end-to-end framework (Liu et al., 2022b). Deep learning breakthroughs have enabled the development of graph algorithms that leverage both graph structures and node attributes to tackle this inherently complex task (Shi et al., 2019; Cheng et al., 2021; Yang et al., 2023; Yi et al., 2023; Liu et al., 2024b; Trivedi et al., 2024; Guo et al., 2025; Ren et al., 2025; Wang et al., 2025b). Specifically, SDCN (Bo et al., 2020) and DFCN (Tu et al., 2021) provide a foundation for integrating graph structure into clustering objectives, laying the groundwork for more recent models. Several advanced methods have since been proposed, each targeting specific challenges in graph clustering. AGCN (Peng et al., 2021) designs a dynamic attention mechanism to adaptively aggregate the multi-scale features, while MCGC (Pan and Kang, 2021) learns a consensus graph by filtering out high-frequency noise, preserving graph geometric features. GLCC (Ju et al., 2023) is the first to extend clustering tasks to the graph-level scenario using the concept of contrastive learning. To address the challenges of large-scale graph data, Dink-Net (Liu et al., 2023b) integrates representation learning with clustering optimization through dilation-shrink mechanisms and uses mini-batches for scalability. To eliminate the need for a predefined cluster number, RGC (Liu et al., 2023a) employs reinforcement learning to jointly learn representations and adaptively adjust cluster numbers for better cohesion and separation. To generalize graph clustering to heterophilic scenarios, DGCN (Pan and Kang, 2023) and DMGC (Guo et al., 2025) reconstructs homophilic and heterophilic graphs with a mixed filter that captures multi-frequency features. Additionally, GCLR (Trivedi et al., 2024) and MARK (Fu et al., 2025) leverage large language models to enhance text-attributed graph clustering. Despite these advancements, a common challenge remains: the inability to capture long-range dependencies in graphs and the neglect of inherent redundant information and noise in data. These factors are crucial to capturing cohesive clusters in complex graph structures. By learning robust and compact node representations in our method CoCo, it is promising to uncover meaningful patterns and communities within the graph. K.2 Global Dependencies in GNNs Despite the success of GNNs in various graph-structured applications, their message-passing mechanism (Gilmer et al., 2017) usually restricts them from capturing long-range dependencies. To overcome this, a growing body of research has been dedicated to enhancing GNNs with global dependency capabilities, which can be roughly categorized into two lines: implicit global interaction and explicit structural augmentation. The first group keeps the original graph unchanged and introduces model-level global interactions, enabling node representations to exchange information globally in feature space (Ying et al., 2021; Zhang et al., 2022; Cai et al., 2023; Liang et al., 2023; Xing et al., 2024; Yi et al., 2025a). For example, Graphormer (Ying et al., 2021) leverages structural encodings within a Transformer framework to effectively capture graph dependencies, while CoBFormer (Xing et al., 2024) adopts a bi-level architecture and collaborative training to more effectively capture global dependencies while retaining important local information. The second group focuses on directly modifying the graph’s connectivity by adding ‘shortcuts’ to physically shorten the distance between distant nodes, enabling standard GNNs to more flexibly capture global relationships (Wu et al., 2022; Guo et al., 2024; Ju et al., 2024a; Yi et al., 2025b; Li et al., 2025). Specifically, GraphEdit (Guo et al., 2024) leverages large language models to learn global node-wise dependencies, denoise connections, and enhance graph structure learning through instruction-tuned reasoning. In our work, we follow the second paradigm by constructing a graph diffusion matrix to capture global dependencies, effectively modeling indirect connections and enabling clusters to accurately represent underlying community structures. K.3 Noise-Resilient Learning in GNNs GNNs are highly sensitive to various types of noise (Ju et al., 2024b; Ju et al., 2025), including feature perturbations and redundant information, which can distort feature distributions and degrade performance. Existing noise-resilient learning approaches can be broadly divided into two lines: adversarial defense and loss refinement. The first line explicitly defends against malicious or worst-case perturbations by simulating or constraining adversarial noise (Feng et al., 2019; Alchihabi et al., 2023; Yuan et al., 2023a). For instance, BVAT (Deng et al., 2023) employs batch virtual adversarial training to counteract noise and better capture local graph structures, while GCORN (Abbahaddou et al., 2024) enhances robustness against node feature attacks by enforcing orthonormal weight matrices. The second line enhances robustness by modifying training objectives to handle noisy or redundant inputs (Wang and Yang, 2022; Huo et al., 2023; Yuan et al., 2023b; Ju et al., 2026). Specifically, BRGCL (Wang and Yang, 2022) iteratively estimates confident nodes to compute robust cluster prototypes and applies prototypical contrastive learning to learn noise-resistant node representations, while T2-GNN (Huo et al., 2023) uses a dual teacher-student framework to transfer clean patterns and recover noisy or corrupted node attributes. Unlike adversarial or loss refinement approaches, we introduce the idea of low-rank learning to help the model learn compact representations for graph clustering, as it explicitly models the underlying low-dimensional structure, and separate noise and redundancy at the data-distribution level, thereby producing more robust and more clustering-friendly representations.