Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework

Liangchen Liu, Qiuhong Ke, Chaojie Li, Feiping Nie, Yingying ZhuarXiv 2022 · DOI · arXiv

Introduction

Clustering is a fundamental task in data analysis, yet traditional spectral methods often fall short when dealing with complex, multi-view datasets. Standard spectral clustering typically follows a disjointed two-step process: first constructing a similarity graph and then performing optimization (e.g., k-means) to identify clusters. This separation leads to significant information loss, as the data representation is not explicitly optimized for the clustering objective. Furthermore, many existing methods ignore the inherent non-negativity of real-world data—such as image pixels or word counts—resulting in representations that lack physical interpretability.

To address these challenges, this paper proposes Umv-ONGC, a unified framework that integrates multi-view fusion, non-negative constraints, and graph-based learning into a single optimization problem.

Methodology: The Umv-ONGC Framework

The core innovation of Umv-ONGC lies in its unified objective function, which jointly learns data representations and clustering results. The model seeks to minimize the reconstruction error between a weighted combination of multi-view graphs and a low-rank representation ($FG^T$).

Key Constraints

  1. Orthonormality ($F^T F = I$): This constraint ensures that the learned features are distinct and stable, preventing the solution space from collapsing.
  2. Non-negativity ($G \ge 0$): By enforcing non-negativity on the variable $G$, the model preserves the physical structure of the data, acting as a powerful regularizer that captures the manifold structure of high-dimensional data more effectively than unconstrained methods.
  3. Adaptive Multi-view Weighting ($\alpha$): Rather than treating all views equally, the framework automatically learns weights for different data sources, prioritizing the most informative views for the final clustering result.

Optimization Strategy

The authors developed a three-stage iterative algorithm to solve the optimization problem:

  • Update $F$: Solving for the representation using Singular Value Decomposition (SVD) while keeping other variables fixed.
  • Update $G$: Utilizing a Lagrange multiplier method to enforce non-negativity.
  • Update $\alpha$: Optimizing view weights through Quadratic Programming (QP).

Experimental Evaluation

The framework was tested on several benchmark datasets, including Handwritten (HW), Cal7, Cal20, and a-Pascal & a-Yahoo (ApAy). Beyond traditional hand-crafted features, the authors explored the fusion of deep features extracted from VGG16, GoogLeNet, and ResNet architectures.

Performance and Convergence

Umv-ONGC consistently outperformed state-of-the-art baselines such as MMSC and MVCSS across various metrics, including Accuracy (ACC) and F1-score.

Comparative performance of Umv-ONGC against baseline methods across HW, Cal7, Cal20, and Average (AVE) datasets.

The experiments highlighted the power of deep feature fusion. For instance, on the Cal20 dataset, fusing multiple deep neural network outputs allowed Umv-ONGC to reach an accuracy of 0.865, a significant improvement over single-view methods.

In addition to accuracy, the model demonstrates high computational efficiency. Convergence analysis shows that the objective function typically stabilizes within 40 iterations, making it a practical choice for medium-to-large scale datasets.

Convergence curves for the original and modified objective functions, showing stability within approximately 40 iterations.

Discussion and Conclusion

The Umv-ONGC framework demonstrates that joint learning and non-negative constraints are vital for robust multi-view clustering. By treating representation learning and clustering as a single task, the model avoids the pitfalls of traditional two-step approaches. While the model shows some sensitivity to the mixing parameter ($\mu$), its ability to fuse diverse data views—particularly deep features—marks a significant step forward in unsupervised learning. Future work may involve refining pre-processing techniques for complex image datasets and extending the framework to real-world applications like social network analysis and web mining.

Summary updated

Abstract

Spectral clustering is an effective methodology for unsupervised learning. Most traditional spectral clustering algorithms involve a separate two-step procedure and apply the transformed new representations for the final clustering results. Recently, much progress has been made to utilize the non-negative feature property in real-world data and to jointly learn the representation and clustering results. However, to our knowledge, no previous work considers a unified model that incorporates the important multi-view information with those properties, which severely limits the performance of existing methods. In this paper, we formulate a novel clustering model, which exploits the non-negative feature property and, more importantly, incorporates the multi-view information into a unified joint learning framework: the unified multi-view orthonormal non-negative graph based clustering framework (Umv-ONGC). Then, we derive an effective three-stage iterative solution for the proposed model and provide analytic solutions for the three sub-problems from the three stages. We also explore, for the first time, the multi-model non-negative graph-based approach to clustering data based on deep features. Extensive experiments on three benchmark data sets demonstrate the effectiveness of the proposed method.
BibTeX
@misc{liu2022unified,
  author = {Liangchen Liu and Qiuhong Ke and Chaojie Li and Feiping Nie and Yingying Zhu},
  title = {{Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework}},
  year = {2022},
  eprint = {2211.02883},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.02883},
}
Figure