High-order graph fusion for multi-viewclustering

Yunning You, Chang Tang, Xinwang Liu, Xin Zou, Yuanyuan Liu, Liangxiao Jiang, Changqing ZhangScientia 2024 · DOI

Abstract

Graph-based multi-view clustering has received considerable attention due to its ability to explore neighborhood relationships among data points from multiple views. Although these methods have achieved impressive performance, most merely exploit first-order proximity, leading to inadequate information exploration and a degraded capacity for multi-view representation. We propose High-order Graph Fusion for Multi-view Clustering (HCDMC), which constructs high-order graphs from first-order and second-order proximity via a novel implicit weight learning paradigm. By incorporating diversity regularization and a connectivity constraint, HCDMC obtains clustering labels directly without post-processing. Extensive experiments on six datasets demonstrate its superior performance compared to state-of-the-art algorithms.

Introduction

Multi-view clustering (MVC) aims to group data points described by multiple feature sets—for example, a video represented by visual frames, audio tracks, and subtitles. While graph-based MVC is popular for capturing complex data structures, existing methods often suffer from a "short-sighted" perspective by only considering first-order proximity (direct neighbors). This makes them sensitive to noise and prevents them from capturing global structures. Furthermore, many methods require unstable post-processing steps like k-means to generate final clusters.

Methodology

The proposed HCDMC algorithm addresses these challenges through three primary innovations:

  1. High-Order Graph Construction: For each view, the algorithm builds a first-order proximity graph and a second-order graph (representing shared neighbors). These are fused into a "high-order" graph, allowing the model to recognize that points sharing many neighbors likely belong together, even if not directly connected.
  2. Implicit Weight Learning: Instead of manual tuning, HCDMC automatically assigns weights to first-order and second-order information based on reconstruction loss, enhancing robustness to noise across different views.
  3. Diversity Regularization (HSIC): Using the Hilbert-Schmidt Independence Criterion (HSIC), the model ensures that different views contribute unique, complementary information.
  4. Direct Clustering via Laplacian Rank: By imposing a rank constraint on the Laplacian matrix of the consensus graph, the algorithm ensures exactly $k$ connected components, outputting cluster labels directly.
Overview of the HCDMC framework, illustrating the fusion of first-order and second-order proximity into a high-order graph for direct clustering.

Experimental Evaluation

HCDMC was evaluated on six diverse real-world datasets: Yale (faces), WebKB (webpages), MSRC-v1 (scenes), LGG & BRCA (biomedical/cancer data), and HW2sources (handwritten digits).

Key Results

  • Superior Accuracy: HCDMC achieved the highest Accuracy (ACC), Normalized Mutual Information (NMI), and Purity across nearly all datasets. On WebKB, it reached an ACC of 0.7635, outperforming the next best state-of-the-art method.
  • Structural Clarity: The method produces cleaner "block-diagonal" structures in similarity matrices, indicating distinct, low-noise clusters compared to competing algorithms.
  • Efficient Convergence: The iterative optimization process typically converges within 20 iterations, ensuring computational predictability.

Conclusion and Future Work

HCDMC provides a robust framework for multi-view clustering by leveraging high-order relationships and direct label output. While it demonstrates state-of-the-art performance, its $O(mn^3)$ complexity poses challenges for massive datasets. Future research will focus on incorporating "anchor graph" techniques to achieve linear complexity, facilitating large-scale industrial applications.

Summary updated

Abstract

Graph-based multi-view clustering has received considerable attention due to its ability to explore neighborhood relationships amongdata points from multiple views. Although these methods have achieved impressive clustering performance and efficiency in various applications, most of them only merely exploit the first-order proximity graph within multi-view data, which results in inadequate information exploration and a degraded capacity of multi-viewrepresentation. In this paper, we propose a high-order graph fusion for multi-viewclustering (HCDMC). Specifically, the proposed algorithm constructs the corresponding high-order graph from first-order andsecond-order proximity graphs for each view by a novel implicit weight learning paradigm. Then, Hilbert SchmidtIndependence Criterion as a diversity regularization term is to improve the complementary information of the consensus high-ordergraphs. Finally, we impose a connectivity constraint on the consensus high-order graph to obtain clustering labels directly without any post-processing step. An efficient iterative algorithm with good convergence is designed to solve the resultingoptimization problem. Extensive experiments conducted on six multi-view datasets demonstrate the promising performance of ourproposed when compared to recent state-of-the-art algorithms.
BibTeX
@inproceedings{you2024high,
  author = {Yunning YOU and Chang Tang and Xinwang Liu and Xin Zou and Yuanyuan Liu and Liangxiao JIANG and Changqing Zhang},
  title = {{High-order graph fusion for multi-viewclustering}},
  booktitle = {Scientia},
  year = {2024},
  doi = {10.1360/ssi-2023-0217},
}
Figure