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

cs.LGOct 8, 2026

Compactness and Consistency: A Conjoint Framework for Deep Graph Clustering

Authors: Wei Ju, Siyu Yi, Kangjie Zheng, Yifan Wang, Ziyue Qiao, Li Shen, Yongdao Zhou, Xiaochun Cao, +1 more

Organizations: College of Computer Science, Sichuan University · College of Mathematics, Sichuan University · Wellcome Sanger Institute · University of International Business and Economics · School of Computing and Information Technology, Great Bay University · School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University · NITFID, School of Statistics and Data Science, Nankai 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.

Figures & tables

Figure 1: Illustration of the proposed framework CoCo.

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

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.

Panel of Figure 2 — Figure 2: The ablation experimental results.

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

Table 2: The comparative results of consistency learning loss

v.s

MSE and InfoNCE.

Panel of Figure 3 — 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.

Panel of Figure 4 — Figure 4: Sensitivity experimental results.

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

Table 3: Comparison of accuracy on noisy BAT.

Table 8

Panel of Figure 5 — Figure 5: Comparisons of average training time per epoch and memory cost.

Iterations	Cora		AMAP
Iterations	NMI	Efficiency	NMI	Efficiency
1	47.99 $\pm$ 4.07	1.62%	62.96 $\pm$ 2.16	2.23%
5	59.81 $\pm$ 0.73	2.93%	68.50 $\pm$ 1.25	3.27%
10	60.71 $\pm$ 0.59	4.28%	68.85 $\pm$ 1.55	4.24%
20	60.69 $\pm$ 0.57	6.69%	68.87 $\pm$ 1.88	6.16%
30	60.70 $\pm$ 0.60	8.46%	68.81 $\pm$ 1.70	8.42%

Table 6: Impact of EM iterations.

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

Table 7: Performance comparison on node classification task (OOM denotes Out of Memory).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Time	Space
MVGRL	$O(N^{2}D)$	$O(N^{2})$
RGC	$O(N^{2}D)$	$O(N^{2})$
CCGC	$O(N^{2}D)$	$O(N^{2})$
Dink-Net	$O(NCD)$	$O(NC+ND)$
GraphLearner	$O(N^{2}D)$	$O(N^{2})$
MAGI	$O(ND^{2})$	$O(ND+\|\mathcal{E}\|+N^{2})$

Appendix

Table 8: Theoretical analysis of complexity

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

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

Appendix

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	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

Appendix

Table 10: The comparative analysis of consistency learning across all datasets.

Panel of Figure 6 — Figure 6: The sensitivity analysis of three hyper-parameters on all five datasets.

Panel of Figure 7 — Figure 7: Robustness analysis.

Explore similar work

Robust Contrastive Graph Clustering with Adaptive Local-Global Integration
May 27, 2026Lei Zhang, Fubo Sun, Haipeng Yang +2Graph Representation Learning Multi-Scale Feature Fusion
School of Computer Science and Technology, Anhui University · College of Management and Economics, Tianjin University
Bridge the Gaps: Heterogeneous Attributed Graph Clustering via Quaternion Representation Learning
Jun 22, 2026Xinxi Chen, Junyang Chen, Yiqun Zhang +2Graph Structure Learning Graph Neural Networks
School of Computer Science and Technology, Guangdong University of Technology, Guangzhou 510006, China
CoRe-GNN: Multilevel Message passing on Coarsened graphs
Aug 3, 2026Antonin Joly, Nicolas Keriven, Aline RoumyGraph Neural Networks Graph Coarsening
CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE

May 27, 2026, cs.LGJ/K move · Enter open · S save

Robust Contrastive Graph Clustering with Adaptive Local-Global Integration

Lei Zhang, Fubo Sun, Haipeng Yang, Zhong Guan+1

School of Computer Science and Technology, Anhui University · College of Management and Economics, Tianjin University

Graph Representation Learning Multi-Scale Feature Fusion Graph Clustering Graph Contrastive Learning

Open paper AskPDF arXiv

Graph clustering is essential in graph analysis for revealing structural patterns and node communities. Despite recent advances in self-supervised contrastive learning that have improved clustering via structural and attribute signals, existing methods still struggle to flexibly capture high-order local structures and often overlook global semantics in complex graphs. These limitations lead to suboptimal node representations, especially in real-world graphs with fragmented structures and ambiguous cluster boundaries. To address these limitations, a contrastive graph clustering framework is proposed to jointly integrate multi-scale local structures with global semantics via attention mechanisms. At the local level, GNN-based topological signals extracted from multiple propagation depths are adaptively fused through attention-based weighting to capture multi-scale neighborhood features. At the global level, semantic prototypes derived from dynamically evolving cluster centers are adaptively aggregated through attention to guide node representations and enhance inter-cluster separability. The model is trained under a dual-view contrastive learning paradigm with a hybrid objective that combines instance-level and structure-aware losses to improve representation robustness and discrimination. Experiments on eight real-world graph datasets demonstrate that our method achieves competitive clustering performance. Code is available at https://github.com/vege12138/w2.

Abstract

Explore similar work

Robust Contrastive Graph Clustering with Adaptive Local-Global Integration

Bridge the Gaps: Heterogeneous Attributed Graph Clustering via Quaternion Representation Learning

CoRe-GNN: Multilevel Message passing on Coarsened graphs