Robust Graph Clustering Network for Multiple Missing Data

Keyuan Qiu; Renda Han; Zhen Tang; Qiang He; Xingwei Wang; Wenxin Zhang; Guangzhen Yao; Junxin Chen

cs.LGSep 25, 2026

Robust Graph Clustering Network for Multiple Missing Data

Authors: Keyuan Qiu, Renda Han, Zhen Tang, Qiang He, Xingwei Wang, Wenxin Zhang, Guangzhen Yao, Junxin Chen, +1 more

Organizations: Northeastern University · University of Chinese Academy of Sciences · Northeast Normal University · Dalian University of Technology · Southeast University

Abstract

Clustering on graphs where both node attributes and structural links are partially missing remains a challenging task. Existing methods typically rely on imputation-then-clustering on single-view missingness incomplete graphs, which are vulnerable to cross-view error propagation and cluster-boundary blurring under simultaneous attribute and structure missingness. To address these limitations, we propose a Robust Graph Clustering Network for Multiple Missing Data (RGCN), which is designed to handle simultaneous node attribute and graph structure incompleteness. RGCN introduces three key innovations: First, we design a view-decoupled dual-branch imputation to mitigate interference and enable mutual enhancement in recovering missing data. Second, we employ a multi-hyperspherical mixture prior to enhance intra-cluster compactness and inter-cluster separability on a directional latent manifold. Third, a boundary-aware contrastive enhancement objective mitigates the blurring of clusters caused by imputation bias. Extensive experiments on real-world datasets demonstrate that RGCN consistently outperforms state-of-the-art baselines under various missing patterns.

Figures & tables

Figure 1: RGCN first extracts node attributes through a dual-branch network. Subsequently, it alternates between diffusion-based attribute imputation and structure inference to progressively recover missing values. Finally, clustering optimization is conducted under a multi-hyperspherical mixture prior, yielding the final clustering results.

Method	ACM				REUT				HHAR
Method	ACC	NMI	ARI	F1	ACC	NMI	ARI	F1	ACC	NMI	ARI	F1
SDCN	43.1±0.3	10.6±0.4	1.5±0.4	38.5±1.4	36.7±0.9	3.6±0.4	2.2±0.4	21.8±0.4	43.4±1.0	7.5±0.9	5.8±0.1	32.8±0.2
DFCN	38.1±0.2	0.8±0.5	0.2±0.4	26.7±0.3	35.4±1.2	3.8±1.5	2.4±1.1	23.2±0.7	28.5±7.7	16.7±15.7	6.4±11.0	16.0±9.1
DCLN	40.5±1.4	4.3±1.2	5.6±1.1	35.4±1.0	40.5±0.3	3.2±0.1	2.9±0.3	25.5±0.6	34.3±0.9	30.3±2.0	23.1±2.0	23.5±1.4
SCGC	41.6±1.7	18.6±0.8	19.5±0.6	22.3±1.2	33.4±0.7	6.9±0.4	3.1±2.1	18.7±0.5	35.4±1.0	35.5±2.2	25.8±2.4	22.7±1.6
ABR	45.6±0.2	11.9±1.9	2.7±1.3	40.6±1.2	41.4±0.8	7.7±1.2	4.0±1.6	29.9±1.3	33.3±0.1	34.4±0.2	21.5±0.8	16.7±0.2

Table 1: Performance comparison results (%) under 50% attribute and structure missing (expressed as mean ± standard deviation) under six datasets. Bold and underlined figures represent the highest and second-highest performances, respectively. “OOM” represents memory limitation exceeded.

Dataset	Metric	None	w/o DD	w/o MH	OURS
ACM	ACC	43.4±1.2	47.8±0.4	49.5±2.6	68.5±1.6
	NMI	10.5±1.7	13.4±1.8	14.3±1.4	34.7±1.6
	ARI	12.3±1.0	17.5±0.9	15.8±1.7	34.5±1.5
REUT	ACC	36.4±1.2	40.4±1.1	43.6±2.0	58.5±2.4
	NMI	5.6±0.8	7.5±1.3	10.6±1.8	22.9±1.5
	ARI	2.9±0.3	11.3±0.9	11.5±1.3	21.4±1.8

Table 2: Clustering performance with 50% missing rate under RGCN and its variants. Bold figures represent the highest performances for any column.

Figure 2: Sensitivity analysis results of RGCN under different $\lambda_{1}:\lambda_{2}$ ratios.

Figure 3: Clustering performance under missing rates from 50% to 80%, compared with six baselines.

Figure 4: Comparison with two-stage impute-then-cluster pipelines.

Figure 5: Epoch-wise ACC, NMI, and ARI performance curves on ACM, REUT, and Co.CS datasets.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description	Symbol	Description
$\mathcal{G}$	Attributed graph	$\mathcal{V}$	Node set
$n$	Node count	$d$	Feature dimension
$\mathbf{X}$	Complete attribute matrix	$\mathbf{A}$	Complete adjacency matrix
$K$	Cluster count	$r$	Rank dimension
$m$	Landmark size	$\mathbf{X}_{obs}$	Observed attribute matrix
$\mathbf{A}_{obs}$	Observed adjacency matrix	$\mathbf{M}_{X}$	Binary mask for attributes

Appendix

Table 3: Summary of Key Notations in RGCN

Dataset	Type	Dimensions	Samples	Edges	Clusters	Domain
ACM	Graph	1870	3025	13128	3	Citation
REUT	Text	2000	10000	30000	4	News
HHAR	Record	561	10299	30897	6	Human Activity
DBLP	Graph	334	4057	3528	4	Citation
Arxiv	Textural	128	169343	1166243	40	Citation
Co.CS	Graph	6805	18333	81894	15	Co-authorship

Appendix

Table 4: Datasets summary.

Explore similar work

When Missingness Follows the Graph: Beyond Feature Propagation for Missing Features
Oct 13, 2026Enrico Chialà, Francesco Ferrini, Antonio Longa +4Learning with Missing Data Graph Neural Networks
University of Trento · Fondazione Bruno Kessler · UiT, The Arctic University of Norway +1
SPORT: Structure-Aware Prototype Disentanglement for Incomplete Multi-View Clustering
Jul 11, 2026Yaoyuan Guo, Zhibin Gu, Songhe Feng +2Multi-View Consistency Disentangled Representation Learning
College of Computer and Cyberspace Security, Hebei Normal University, Shijiazhuang 050024, China · Department of Statistics and Data Science, Southern University of Science and Technology, Shenzhen 518055, China · Key Laboratory of Tibetan Information Processing, Ministry of Education, Qinghai Normal University, Xining 810008, China +2
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

Oct 13, 2026J/K move · Enter open · S save

When Missingness Follows the Graph: Beyond Feature Propagation for Missing Features

Enrico Chialà, Francesco Ferrini, Antonio Longa, Bruno Lepri+3

University of Trento · Fondazione Bruno Kessler · UiT, The Arctic University of Norway+1

Learning with Missing Data Graph Neural Networks Incomplete Data Imputation

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) commonly assume that node features are fully observed, despite missing features being pervasive in real-world applications. By leveraging the dependence between node features and graph structure, existing graph-specific methods handle missingness by propagating observed feature values along graph edges. However, these methods have mainly been evaluated in overly optimistic settings, where feature entries are removed independently and uniformly across the graph. This overlooks realistic scenarios in which missingness propagates among connected nodes, as can occur during localized sensing failures in sensor networks. We formalize this complementary notion as graph-structured mask dependence, where the joint distribution of missingness indicators is shaped by the graph, and introduce a controlled mechanism that instantiates this setting. We study propagation-based methods theoretically and empirically in this setting, showing that their effectiveness changes substantially compared with the uniformly random regime. Motivated by this limitation, we propose PEMix, designed to remain effective under challenging graph-structured missingness. Rather than propagating observed values, PEMix uses global structural representations to condition a probabilistic model of incomplete node features before message passing. Experiments under controlled graph-structured missingness and naturally occurring missingness show that PEMix remains robust across complex missingness regimes, with particularly strong performance as missingness becomes severe.

Abstract

Explore similar work

When Missingness Follows the Graph: Beyond Feature Propagation for Missing Features

SPORT: Structure-Aware Prototype Disentanglement for Incomplete Multi-View Clustering

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