Computer scientists have introduced an unsupervised framework that significantly stabilizes deep graph clustering when node attributes are partially absent or corrupted across networked datasets. Real-world graphs representing citation networks, social connections, and recommender systems rely on edge topology alongside individual node feature vectors to delineate underlying community structures. In typical data collection scenarios, privacy constraints, hardware failures, or network anomalies often leave substantial portions of node attributes unrecorded. When standard graph neural architectures process these incomplete graphs, traditional neighborhood propagation routines distribute corrupted or blank feature representations to adjacent nodes, causing blurred cluster boundaries and misclassifications across downstream partitions. The new progressive architecture, termed Progressive Feature Completion and Multi-Level Contrastive Clustering, overcomes these vulnerabilities by combining iterative topological completion with structured multi-level contrastive regularizations.
Traditional clustering models designed for fully observed graphs typically assume complete access to attribute matrices, leading to severe performance degradation whenever missing attributes arise. While previous strategies attempted to address incomplete networks through single-step propagation, distribution matching, or generative recovery, they frequently encountered critical algorithmic bottlenecks. Fixed-neighborhood aggregation often aggregates information from noisy or irrelevant neighbors that happen to share an edge, directly contaminating the feature vectors of connected samples. Furthermore, existing pipelines commonly isolate feature imputation from the final clustering objective, incorporating cluster guidance only after feature propagation has concluded. The newly published system resolves this separation by systematically coupling feature recovery, localized neighborhood filtering, global cluster-center anchoring, and iterative optimization into a single unified training workflow.
The foundational stage of the proposed methodology establishes a base feature view by subjecting the corrupted attribute matrix to multi-step graph structural propagation. The model applies symmetric normalization to the graph adjacency matrix after stripping original self-loops, scaling edge connections by the inverted square root of node degrees. This normalized structure performs Laplacian propagation over a specified number of propagation steps, smoothing out isolated attribute deficiencies by gathering information across the surrounding topology. However, because topological neighbors in raw graphs frequently belong to differing underlying classes, structural smoothing alone can propagate discordant features. To prevent dissimilar adjacent nodes from skewing the representations, the system computes pairwise cosine similarities across the smoothed features to quantify attribute alignment between connected nodes, restricting calculations strictly to observed graph edges.
Using these calculated similarities, the architecture generates a coarse feature propagation matrix that adaptively alters neighborhood message weights. For each node, the model identifies a set of nearest neighbors exhibiting high attribute similarity and filters them through the graph’s native adjacency connections. A coarse propagation balancing coefficient regulates the relative contribution between the original normalized adjacency matrix and the similarity-derived weights, while a stabilizing constant avoids division anomalies during matrix normalization. The resulting coarse feature view is formed through a residual combination that blends the structurally smoothed base representation with the similarity-weighted propagation output. This topology-constrained reweighting dampens the influence of discordant neighbors without introducing fabricated edges into the graph structure, yielding a reliable base for subsequent representational refinement.
To transition from localized neighborhood recovery to global partition guidance, the framework encodes both the base view and the coarsely completed view through a shared parametric feature encoder equipped with nonlinear activation and Euclidean normalization. Averaging the resulting node embeddings produces a unified shared representation that mitigates specific modeling biases inherent to either isolated view. The shared representation is subsequently partitioned using K-means clustering to establish cluster centroids and derive discrete cluster assignments for all samples in the graph. By mapping each node directly to its assigned cluster center, the framework constructs a cluster-center representation matrix. This mapping supplies each sample with an explicit anchor pointing toward its global cluster mean, bridging the conceptual gap between localized topological adjacency and overarching graph partitions.
The refinement phase integrates this macro-level structure back into individual node features to generate a refined feature view. The system combines the shared representation with a scaled sum of normalized neighborhood-aggregated features and the corresponding cluster-center vectors, passing the normalized outcome through a two-layer multilayer perceptron decoder with intermediate rectification. A fine refinement coefficient regulates the magnitude of this structural adjustment, ensuring that cluster centroids guide the feature space without overriding reliable local characteristics. Feeding this decoded view back into the encoder yields a refined representation. By moving beyond isolated neighborhood imputation, the model progressively infuses cluster-level geometric constraints into the node representations, ensuring that completed features actively support crisp separation between distinct categories.
To guarantee that node embeddings remain consistent as they evolve across progressive completion stages, the authors instituted a multi-level contrastive learning scheme operating at dual geometric scales. At the local level, contrastive loss constraints are enforced between the base representation and the coarsely completed representation, regularizing the shifts that occur when attribute similarities reweight local edges. At the global level, a secondary contrastive constraint binds the shared representation directly to the refined representation, explicitly regulating the structural adjustments induced by neighborhood aggregation and cluster-center guidance. Rather than contrasting against an entire graph-level summary vector, the global objective focuses specifically on aligning node embeddings with their assigned cluster prototypes while pulling identical node instances across different views together.
To prevent attribute missingness from distorting pairwise contrastive associations, the loss formulation utilizes a structure-aware similarity metric that integrates both raw node vector alignments and neighborhood-aggregated similarities. A balancing hyperparameter balances the direct cosine similarity between contrasting node embeddings and the cosine similarity between their normalized neighborhood representations, buffering against residual noise in individual vectors. Across both local and global levels, positive sample pairs are formed by mapping the identical node across two distinct representational phases, while negative pairs are drawn across different nodes. The total contrastive objective computes a weighted sum of the local and global losses, applying tunable weighting coefficients to preserve representation coherence across all operational stages of the completion pipeline.
Model training proceeds end-to-end under a joint objective function that pairs multi-level contrastive learning with bidirectional feature reconstruction and a dynamic sample-weight update mechanism. Because the decoding operation in the refinement phase can cause feature distributions to drift from the original inputs, a bidirectional reconstruction loss penalizes divergence between the normalized distributions of the base and refined feature views. Simultaneously, the framework periodically recalculates pseudo-labels from the shared representation, isolating high-confidence samples based on their proximity to assigned cluster centroids relative to a confidence threshold. For sample pairs within this high-confidence set, pair weights are scaled based on the absolute discrepancy between pseudo-label agreements and normalized representation similarities, compelling the contrastive loss to focus intensively on hard sample pairs near partition boundaries.
The mathematical validity of the sample-weighting mechanism is substantiated through theoretical analysis establishing an explicit upper bound on weight deviations. When pseudo-labels contain classification errors, the average deviation between the assigned sample-pair weights and their ideal counterparts remains strictly bounded by the error rate of the pseudo-label relations within the high-confidence set. Because low-confidence nodes located near ambiguous cluster perimeters are excluded from weight updates, erroneous pseudo-labels are prevented from disproportionately destabilizing the gradient updates. Periodic retraining cycles refresh the cluster centers, pseudo-labels, and sample weights simultaneously, ensuring that the model converges stably toward an optimal clustering landscape despite the presence of missing attributes in the raw data.
Empirical validation was performed across six public benchmark networks encompassing citation databases, co-purchasing records, and transportation systems, specifically CORA, CITE, DBLP, ACM, AMAP, and BAT. Testing covered fully observed attribute conditions alongside simulated node-level and feature-level attribute missingness at ratios of 10 percent, 30 percent, and 50 percent. When evaluated under complete-attribute baselines against specialized clustering architectures including SAT, CCGC, SCGC, HSAN, AMGC, MHGC, and TDAR, the proposed method achieved leading scores across accuracy, normalized mutual information, adjusted Rand index, and F1-score on DBLP, AMAP, and BAT, while recording the highest adjusted Rand index and F1 values on CITE. These results confirm that adaptive neighborhood reweighting prevents inter-cluster topological contamination even when complete node information is available.
Under severe corruption regimes where 50 percent of node attribute vectors were fully zeroed, the framework exhibited pronounced resilience. Accuracy metrics remained robust at 78.56 percent on AMAP, 77.33 percent on BAT, and 79.44 percent on ACM, while outperforming competing imputation and clustering models across sensitive citation graphs. Extensive ablation experiments conducted at 50 percent missingness demonstrated that removing the coarse completion module, the fine refinement stage, or the multi-level contrastive objectives caused substantial performance degradation across all datasets. For example, on the CITE network, removing coarse completion reduced clustering accuracy from 59.49 percent to 55.37 percent, while omitting contrastive objectives caused accuracy on CORA to drop from 73.22 percent to 66.83 percent, confirming the necessity of each interconnected stage.
Computational cost assessments conducted on modern hardware revealed that while the framework maintains practical runtimes across standard benchmarks, its dense similarity matrix calculations introduce quadratic scaling constraints. Structural Laplacian propagation scales linearly with graph edges, but computing full pairwise attribute similarities and node-pair contrastive losses demands quadratic complexity relative to node counts. The resulting memory footprint remains easily manageable for benchmark networks containing several thousand samples, but poses operational hurdles for massive industrial graphs scaling to millions of entities. Future extensions of this research will focus on integrating sparse nearest-neighbor searches, block-wise partition approximations, and sampling-based contrastive loss formulations to extend progressive completion capabilities to web-scale networks and dynamic graph environments.
Subject of Research: Unsupervised graph representation learning and clustering for attribute-missing graphs
Article Title: Progressive feature completion and multi-level contrastive clustering for attribute-missing graphs
Article References: Fang, Z., Chen, B., Zhou, L., Liu, B., & Ji, M. (2026). Progressive feature completion and multi-level contrastive clustering for attribute-missing graphs. Journal of King Saud University Computer and Information Sciences, 38(9), Article 1000. https://doi.org/10.1007/s44443-026-01364-4
Image Credits: AI Generated
DOI: 10.1007/s44443-026-01364-4
Keywords: deep graph clustering, attribute-missing graphs, unsupervised learning, contrastive learning, feature completion, structural propagation, neighborhood aggregation, pseudo-labeling, node representation, cluster centers, feature reconstruction, graph neural networks, CORA dataset, CITE dataset, DBLP dataset, ACM dataset, AMAP dataset, BAT dataset
News Source: Denise Maddox. (November 21, 2026). Progressive Feature Completion Framework Improves Node Clustering on Incomplete Real-World Graphs. Scienmag.



