Unbalanced Incomplete Multi-view Clustering via the Scheme of View Evolution: Weak Views are Meat; Strong Views do Eat

Xiang Fang, Yuchong Hu, Pan Zhou, Xiao-Yang Liu, Dapeng Oliver Wu

Abstract

Incomplete multi-view clustering is a critical technique for processing real-world data where various perspectives (views) may be missing information. Traditional methods typically assume "balanced incompleteness," where every view lacks a similar proportion of data. However, real-world scenarios often present "unbalanced incompleteness," resulting in strong views (low incompleteness) and weak views (high incompleteness). This imbalance causes existing methods to fail due to matrix dimension mismatches and suboptimal weighting. In this paper, we introduce the Unbalanced Incomplete Multi-view Clustering (UIMC) method. Inspired by biological evolution, UIMC utilizes a novel "view evolution" scheme to dynamically weight views based on their completeness. By integrating weighted multi-view subspace clustering with a low-rank representation for data recovery, UIMC effectively diminishes the impact of noise and missing data. Experimental results show that UIMC improves clustering performance by up to 40% across multiple metrics compared to state-of-the-art methods.

Introduction

Multi-view clustering (MVC) leverages diverse data sources—such as text, images, and metadata—to group instances more accurately than single-view methods. A persistent challenge in this field is the "incomplete view" problem, where some instances are missing from certain views. While significant progress has been made in incomplete multi-view clustering, most existing algorithms operate under the assumption that the missing rate is uniform across all views.

In practice, this assumption rarely holds. For example, in a dataset of web pages, almost all pages have text (a strong view), but only a small fraction may contain video content (a weak view). Standard methods struggle with this disparity because they often require aligned matrices of identical dimensions or treat all views as equally informative, which allows noisy, incomplete views to degrade the final consensus. UIMC addresses these issues by treating view integration as an evolutionary process where the most informative views dominate the clustering outcome.

The UIMC Framework

1. The Scheme of View Evolution

UIMC introduces a biological metaphor for optimization: "survival of the fittest." The algorithm categorizes views based on their missing rates:

  • Strong Views: Views with a missing rate below the average. These are considered highly reliable.
  • Weak Views: Views with a missing rate above the average. These contain useful but sparse information.
  • Dying Views: Views with so little data that they cannot contribute to a meaningful cluster.

During the iterative optimization process, UIMC updates the weights of each view. Strong views "eat" the weights of weak views, increasing their influence on the final clustering result, while dying views are eventually phased out. This ensures that the consensus matrix is driven by the most complete and reliable data sources.

2. Solving Dimension Mismatch with Laplacian Graphs

A major technical hurdle in unbalanced clustering is that different views have different numbers of available instances, leading to matrices of varying sizes. UIMC bypasses this by constructing Laplacian graphs for each view. These graphs map relationships between the total number of instances ($m \times m$) rather than just the available ones. By using these graphs as a bridge, the algorithm can align views mathematically regardless of their specific missing patterns.

3. Data Recovery via Low-Rank Representation

To handle noise and fill in missing information, UIMC employs a robust low-rank representation. The authors developed a novel $\Gamma$-norm (Gamma-norm) combined with an $L_{2,1}$-norm. Unlike the standard nuclear norm, which can sometimes deviate from the true matrix rank, the $\Gamma$-norm provides a more accurate approximation for recovering the underlying data structure. This dual-norm approach effectively denoises the data while preserving the essential features required for clustering.

Experimental Results

The researchers evaluated UIMC against eight state-of-the-art methods, including PVC, MIC, and DAIMC, across four diverse datasets: BUAA (faces), 3-Sources (news), BBC (documents), and Handwritten Digits. To test the robustness of the algorithm, they artificially induced varying rates of incompleteness to simulate unbalanced data.

Performance on Unbalanced Data

UIMC demonstrated significant superiority in unbalanced scenarios. On the Handwritten Digit dataset (with an average missing rate of 0.4), UIMC achieved:

  • 44.50% improvement in Accuracy (ACC)
  • 42.70% improvement in Normalized Mutual Information (NMI)
  • 43.15% improvement in Purity

Even when tested on balanced incomplete data, UIMC remained the top performer, showing improvements of 11% to 17% over existing techniques. This suggests that the evolutionary weighting scheme is beneficial even when the disparity between views is less extreme.

Convergence and Efficiency

Despite an iterative 9-step optimization procedure based on the Alternating Direction Method of Multipliers (ADMM), UIMC exhibits strong convergence properties. Empirically, the algorithm typically stabilizes within 16 iterations, making it viable for practical applications.

Conclusion

UIMC represents a significant step forward in multi-view clustering by specifically addressing the reality of unbalanced data. By utilizing the scheme of view evolution and Laplacian graph alignment, it provides a mathematically sound way to integrate views of varying quality.

While the current iteration of UIMC faces some computational bottlenecks due to the $O(n^3)$ complexity of matrix inversions and SVD operations, it sets a new benchmark for accuracy in incomplete data environments. Future work will focus on integrating online learning techniques to scale the algorithm for massive, web-scale datasets.

Summary updated

Abstract

Incomplete multi-view clustering is an important technique to deal with real-world incomplete multi-view data. Previous works assume that all views have the same incompleteness, i.e., balanced incompleteness. However, different views often have distinct incompleteness, i.e., unbalanced incompleteness, which results in strong views (low-incompleteness views) and weak views (high-incompleteness views). The unbalanced incompleteness prevents us from directly using the previous methods for clustering. In this paper, inspired by the effective biological evolution theory, we design the novel scheme of view evolution to cluster strong and weak views. Moreover, we propose an Unbalanced Incomplete Multi-view Clustering method (UIMC), which is the first effective method based on view evolution for unbalanced incomplete multi-view clustering. Compared with previous methods, UIMC has two unique advantages: 1) it proposes weighted multi-view subspace clustering to integrate these unbalanced incomplete views, which effectively solves the unbalanced incomplete multi-view problem; 2) it designs the low-rank and robust representation to recover the data, which diminishes the impact of the incompleteness and noises. Extensive experimental results demonstrate that UIMC improves the clustering performance by up to 40% on three evaluation metrics over other state-of-the-art methods.
BibTeX
@article{fang2020unbalanced,
  author = {Xiang Fang and Yuchong Hu and Pan Zhou and Xiao-Yang Liu and Dapeng Oliver Wu},
  title = {{Unbalanced Incomplete Multi-view Clustering via the Scheme of View Evolution: Weak Views are Meat; Strong Views do Eat}},
  journal = {IEEE Trans. Emerg. Top. Comput. Intell.},
  year = {2020},
  url = {https://openreview.net/forum?id=QXEZjgvxHt2},
}
Figure