Federated Multi-view Graph Clustering with Incomplete Attribute Imputation

Wei Feng, Zeyu Bi, Qianqian Wang, Bo DongIJCAI 2025 · DOI

TL;DR

This paper introduces FMVC-IAI, a novel federated multi-view clustering method that tackles the challenge of incomplete data across different views. It achieves this by leveraging graph structures for attribute imputation and using anchor graphs for efficient and private knowledge sharing, outperforming existing methods, especially in scenarios with significant missing data.

What Problem Does This Paper Address?

In today's data-rich world, information is often collected from multiple perspectives or "views." Multi-view clustering (MVC) aims to group data points based on these diverse views, often yielding better results than using a single view. However, a significant challenge arises when data is distributed across different organizations (clients) for privacy reasons. This "federated" setting introduces two main problems:

  1. Data Privacy: Clients cannot directly share their raw data features with each other or a central server.
  2. Incomplete Views: It's common for some data points to be missing in certain views for specific clients. Traditional MVC methods, which assume complete and centralized data, fail in these scenarios.

Existing federated MVC (FedMVC) methods often struggle with incomplete data or require uploading sensitive local features, risking privacy leakage and incurring high communication costs. This paper aims to bridge this gap by proposing a FedMVC method that can effectively handle incomplete multi-view data while preserving privacy and minimizing communication overhead.

Methods

The proposed method, Federated Multi-view Graph Clustering with Incomplete Attribute Imputation (FMVC-IAI), operates in a federated setting with a central server and multiple clients. Here's a breakdown of its key components:

  • Incomplete-view Imputation: Each client uses a Graph Neural Network (GNN) to impute missing features. This process leverages a global graph structure provided by the server. First, local data is encoded into a latent space using an Autoencoder (AE). Missing features in this latent space are then filled with zeros. Finally, a diffusion process, guided by the global graph, propagates information from existing features to fill in the missing ones. This is crucial for handling the "incomplete view" problem.
  • GAE-based Embedding: After imputation, a Graph Autoencoder (GAE) is employed to extract high-level, robust features. This involves using a Graph Attention Network (GAT) for feature extraction and then a decoder to reconstruct attributes and structure. The GAE is trained using a combination of feature reconstruction loss and structural reconstruction loss.
  • Anchor Graph for Knowledge Sharing: To mitigate privacy risks and reduce communication costs, instead of uploading full local adjacency graphs or feature embeddings, clients upload "anchor graphs." These are smaller representations derived from the high-level embeddings, significantly reducing the amount of data transmitted. The paper suggests this reduces communication complexity from O(N²) to O(Nr), where 'r' is the number of anchors, much smaller than 'N' (number of samples).
  • Client-Server Interaction and Global Clustering:
    • Clients upload their anchor graphs and other local information (like prototype distance matrices) to the server.
  • The server aggregates these anchor graphs using a weighted fusion mechanism, where weights are determined by the similarity between local and global clustering assignments (measured by Earth Mover's Distance).
  • The server then constructs a global adjacency graph and uses it to generate global clustering assignments and pseudo-labels. This global information is then sent back to the clients to guide their local training.
  • Clients use this global supervision to refine their local clustering and update their models.

Datasets

The paper evaluates FMVC-IAI on three multi-view datasets:

  • HW: A dataset of handwritten digits with six different view features.
  • OutdoorScene: A dataset of outdoor scenes with four views.
  • NoisyMNIST: A modified MNIST dataset where one view is the original and the other is corrupted with Gaussian noise.

The authors also simulate incomplete data by randomly selecting a percentage of samples and deleting half of their view data, testing the method across various missing rates (η = 0.1, 0.3, 0.5, 0.7, 0.9).

Key Insights and Ideas

  • Graph-based Imputation is Key: The paper highlights that using graph structures, particularly a global graph, is an effective way to impute missing features in a federated setting, addressing a critical limitation of many existing methods.
  • Anchor Graphs for Privacy and Efficiency: The introduction of anchor graphs as a communication mechanism is a significant contribution. It cleverly balances the need for information sharing with privacy preservation and drastically reduces communication overhead.
  • Weighted Fusion for Robustness: The server's weighted fusion of client-provided information, based on how well local assignments align with global ones, makes the aggregation process more robust to variations in client data quality or contributions.
  • Federated Learning for Incomplete Data: The work demonstrates that federated learning can be successfully applied to multi-view clustering even when data is incomplete, a scenario that is highly relevant in real-world applications.

Key Results

The experimental results demonstrate the superiority of FMVC-IAI, particularly in scenarios with high missing rates.

  • Outperforms State-of-the-Art: FMVC-IAI consistently achieves better clustering performance (measured by ACC, NMI, and ARI) compared to seven other methods, including both centralized and federated approaches, especially when the missing rate is high (e.g., η = 0.9).
  • Robustness to Missing Data: The method shows a smaller performance drop compared to other methods as the missing rate increases, highlighting the effectiveness of its imputation strategy.
  • Reduced Communication Overhead: The paper quantifies the communication complexity, showing it's significantly lower than O(N²) due to the use of anchor graphs.
  • Ablation Study: The ablation study confirms the importance of each proposed module, with the GCN-based feature completion and the structural reconstruction loss in GAE showing particularly significant impacts on performance.

Limitations and Future Work

  • Parameter Sensitivity: While the paper analyzes parameter sensitivity, finding optimal values for parameters like the number of neighbors (k) and the clustering loss coefficient (α) might still require tuning for different datasets.
  • Anchor Number 'r': The choice of the number of anchors 'r' is a trade-off between communication cost and information representation. The paper suggests that a relatively small number of anchors is sufficient, but further exploration into optimal anchor selection strategies could be beneficial.
  • Future Work: The authors suggest that future research could explore more advanced imputation techniques or investigate the application of this framework to other federated learning tasks beyond clustering. The current work focuses on graph-based imputation, and exploring other imputation methods within the federated framework could be a promising direction.

Summary updated

BibTeX
@inproceedings{feng2025federated,
  author = {Wei Feng and Zeyu Bi and Qianqian Wang and Bo Dong},
  title = {{Federated Multi-view Graph Clustering with Incomplete Attribute Imputation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/570},
}
Figure