Sample-level Multi-view Graph Clustering

Yuze Tan, Yixi Liu, Shudong Huang, Wentao Feng, Jiancheng Lv

Abstract

Traditional multi-view clustering (MVC) methods often rely on coarse-grained, view-wise fusion, which can be sensitive to noise and fails to capture the intricate manifold structures of high-dimensional data. This paper introduces a novel multi-view graph clustering framework that shifts the focus toward a more precise "sample-wise" approach. By learning the underlying topological relevance of data and weighting the importance of different views for every individual sample, the proposed method achieves state-of-the-art performance while remaining robust to noise in specific data sources.

Introduction

In the real world, data objects are frequently described by multiple features or "views." For instance, an image can be characterized by color, texture, and shape, while a webpage may be defined by its text content and its hyperlink network. Multi-view clustering (MVC) aims to integrate these diverse perspectives to uncover a consistent underlying structure.

However, existing MVC methods face two major hurdles. First, they often treat data as if it exists in simple Euclidean space, ignoring the "topological structure"—the idea that data points might be related through a chain of neighbors on a curved manifold. Second, most methods employ coarse-grained fusion, assigning a single weight to an entire view. This is problematic when a view is informative for some samples but noisy for others. For example, a color-based view might be excellent for identifying a red car but misleading for a translucent glass bottle.

Methodology

The proposed framework addresses these limitations through three key components:

1. Topological Relevance Learning

Instead of relying on simple geometric similarity, the model learns the "topological relevance" between points. This ensures that if point A is a neighbor of B, and B is a neighbor of C, A and C are treated as highly consistent even if they are geometrically distant in the original feature space.

2. Sample-level Graph Fusion

This is the core innovation of the work. The authors arrange the multi-view data into a 3D tensor and "slice" it by sample. This allows the model to learn a specific weight matrix ($W$) for every single data point. If a specific view is noisy for a particular sample, the model can automatically down-weight it for that instance while maintaining its importance for others.

The process of transforming multi-view data into a 3D tensor and slicing it to achieve sample-level fusion.

3. The Intermediate Variable ($Q$)

To bridge the gap between raw topological learning and the final fused graph, the authors introduce a variable $Q$. This acts as a "buffer" that helps the optimization process find a consensus across views without being forced into a sub-optimal structure by a single "bad" view. The resulting non-convex optimization problem is solved efficiently using an iterative algorithm based on the Augmented Lagrangian Multiplier (ALM) method.

Experimental Evaluation

The researchers evaluated their method on six diverse benchmark datasets, including plant species (100leaves), handwritten numerals (HW), general images (MSRC), faces (ORL & Yale), and web pages (Cornell).

Key Results

The proposed method consistently outperformed 13 other state-of-the-art (SOTA) methods across metrics such as Accuracy (ACC) and Normalized Mutual Information (NMI):

  • Handwritten Numerals (HW): Achieved a near-perfect 99.25% Accuracy and 98.15% NMI.
  • 100leaves: Reached 90.86% Accuracy, significantly gapping SOTA methods that typically ranged between 35% and 77%.
  • Robustness: Parameter analysis demonstrated that the model is remarkably stable across a wide range of hyperparameter settings ($\alpha, \beta, \lambda, \gamma$).
Parameter sensitivity analysis demonstrating the stability of the model's NMI performance across various hyperparameter configurations.

Conclusion

By treating multi-view fusion as a local, sample-level problem rather than a global, view-wise one, this framework more accurately reflects the behavior of real-world data. The integration of manifold awareness and sample-level weighting provides a robust solution to the challenges of noise and inconsistent data structures. Future work will explore extending this logic into deep learning and kernel-based frameworks to handle even more complex, non-linear relationships.

Summary updated

Abstract

Multi-view clustering has hitherto been studied due to their effectiveness in dealing with heterogeneous data. Despite the empirical success made by recent works, there still exists several severe challenges. Particularly, previous multi-view clustering algorithms seldom consider the topological structure in data, which is essential for clustering data on manifold. Moreover, existing methods cannot fully explore the consistency of local structures between different views as they uncover the clustering structure in a intra-view way instead of a inter-view manner. In this paper, we propose to exploit the implied data manifold by learning the topological structure of data. Besides, considering that the consistency of multiple views is manifested in the generally similar local structure while the inconsistent structures are the minority, we further explore the intersections of multiple views in the sample level such that the cross-view consistency can be better maintained. We model the above concerns in a unified framework and design an efficient algorithm to solve the corresponding optimization problem. Experimental results on various multi-view datasets certificate the effectiveness of the proposed method and verify its superiority over other SOTA approaches.
BibTeX
@inproceedings{tan2023sample,
  author = {Yuze Tan and Yixi Liu and Shudong Huang and Wentao Feng and Jiancheng Lv},
  title = {{Sample-level Multi-view Graph Clustering}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2023},
  doi = {10.1109/cvpr52729.2023.02295},
}
Figure