TOTF: Missing-Aware Encoders for Clustering on Multi-View Incomplete Attributed Graphs

Mengyao Li, Xu Zhou, Jiapeng Zhang, Zhibang Yang, Cen Chen, Kenli LiIJCAI 2025 · DOI

Abstract

Clustering multi-view attributed graphs is a critical task in data mining, yet real-world datasets often suffer from missing node attributes due to privacy concerns or sensor failures. Existing methods primarily address missing views rather than missing attributes within views. We present TOTF (Train Once Then Freeze), a two-stage framework that leverages correlation-aware graph neural networks and an adversarial "missing position reminder" mechanism. TOTF achieves up to a 17% accuracy improvement over state-of-the-art methods and maintains high performance even when 70% of attributes are missing.

Problem Statement: The Challenge of Incomplete Data

In many real-world scenarios, data is represented across multiple "views." For instance, a social network user might have one view representing their follower graph and another representing their interests. However, users frequently leave profile fields blank or restrict access to certain data, leading to Multi-View Incomplete Attributed Graphs.

Figure 1: Real-world example of multi-view incomplete attributed graphs where different views (e.g., social relationships vs. personal interests) contain missing attribute values.

Standard Graph Neural Networks (GNNs) are ill-equipped for this task because they focus on message passing between neighbors while often ignoring the internal correlations between different attribute dimensions of a single node. Furthermore, most incomplete graph clustering research focuses on missing nodes (entirely absent from a view) rather than missing features (where the node exists but its attribute vector is sparse).

The TOTF Framework

To address these limitations, the TOTF framework decouples the representation learning of incomplete attributes from the clustering process through a two-stage approach.

Figure 4: The complete TOTF architecture, illustrating Stage 1 (Missing-aware View-Specific Encoder Training) and Stage 2 (Clustering-Driven Common Information Discovery) alongside the CSAGNN module.

Stage 1: Missing-aware View-Specific Encoder Training

In the first stage, the model trains encoders to be resilient to missing data using two primary components:

  1. CSAGNN (Correlation Strength-Aware GNN): This module explicitly models the relationships between attribute dimensions. By recognizing that certain features (e.g., "Travel" and "Food") are often correlated, CSAGNN can impute missing values using both the graph structure and internal feature logic.
  2. Missing Position Reminder: The authors provide a theoretical proof (Theorem 1) demonstrating that standard Generative Adversarial Networks (GANs) cannot recover the unique true distribution of missing data without assistance. TOTF introduces a "reminder matrix" ($R$) that informs the discriminator which values were originally missing, forcing the generator to learn the actual underlying data distribution rather than an arbitrary one.

Stage 2: Clustering-Driven Common Information Discovery

Once the encoders are trained to handle missingness, their parameters are frozen. This "Train Once Then Freeze" strategy prevents the inherent noise of incomplete attributes from destabilizing the final clustering stage. A "common extractor" then integrates these stable representations to find a consensus clustering partition across all views, optimized via a self-supervised clustering loss.

Key Insights and Results

  • Attribute Correlation: Analysis using the Kendall coefficient confirmed that attributes within a node are highly interdependent, validating the CSAGNN approach.
  • Robustness: TOTF demonstrates remarkable resilience to high missing rates. On the ACM dataset with 70% of attributes missing, TOTF maintained over 80% accuracy, significantly outperforming competitors like MAGC and MvAGC, which saw performance drops to 63% or lower.
  • Ablation Studies: Experiments confirmed that both the CSAGNN and the Reminder Matrix are essential; removing either component led to a significant decrease in the Adjusted Rand Index (ARI).

Conclusion and Future Work

TOTF provides a robust solution for clustering on graphs with sparse attribute data by effectively modeling intra-node correlations and utilizing adversarial reminders. While currently optimized for static graphs with numerical attributes, future research may extend this framework to dynamic graphs and multi-modal data (e.g., text and images) to further its applicability in large-scale industrial systems.

Summary updated

BibTeX
@inproceedings{li2025totf,
  author = {Mengyao Li and Xu Zhou and Jiapeng Zhang and Zhibang Yang and Cen Chen and Kenli Li},
  title = {{TOTF: Missing-Aware Encoders for Clustering on Multi-View Incomplete Attributed Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/340},
}
Figure