Sharper Error Bounds in Late Fusion Multi-view Clustering Using Eigenvalue Proportion

Liang Du, Henghui Jiang, Xiaodong Li, Yiqing Guo, Yan Chen, Feijiang Li, Peng Zhou, Yuhua QianarXiv 2024 · OpenReview

Abstract

Multi-view clustering (MVC) aims to integrate complementary information from multiple views to enhance clustering performance. Late Fusion Multi-View Clustering (LFMVC) has shown promise by synthesizing diverse clustering results into a unified consensus. However, current LFMVC methods struggle with noisy and redundant partitions and often fail to capture high-order correlations across views. To address these limitations, we present a novel theoretical framework for analyzing the generalization error bounds of multiple kernel $k$-means, leveraging local Rademacher complexity and principal eigenvalue proportions. Our analysis establishes a convergence rate of $\mathcal{O}(1/n)$, significantly improving upon the existing rate in the order of $\mathcal{O}(\sqrt{k/n})$. Building on this insight, we propose a low-pass graph filtering strategy within a multiple linear $k$-means framework to mitigate noise and redundancy, further refining the principal eigenvalue proportion and enhancing clustering accuracy. Experimental results on benchmark datasets confirm that our approach outperforms state-of-the-art methods in clustering performance and robustness. The related codes is available at https://github.com/csliangdu/GMLKM .

Introduction

Multi-view clustering (MVC) is the process of finding a single consensus partition from data collected from multiple sources, such as an image's pixels and its text description. Late Fusion (LFMVC) is a popular strategy where views are clustered independently before being fused into a final result. However, LFMVC faces two major hurdles: noise propagation from initial view-specific clusters and loose theoretical guarantees. Most existing methods have generalization error bounds—mathematical promises of performance on unseen data—that are relatively loose, typically $\mathcal{O}(\sqrt{k/n})$. This makes it difficult to guarantee high performance in complex, high-dimensional scenarios.

This paper addresses these issues by tightening theoretical bounds and introducing an algorithm that practically exploits these mathematical insights to improve clustering robustness.

Methods

The proposed approach combines theoretical advancements with a novel algorithm design to bridge the gap between error bounds and practical performance.

Theoretical Framework: Local Rademacher Complexity and PEP

Instead of using global complexity measures, the authors utilize local Rademacher complexity. They link this to the Principal Eigenvalue Proportion (PEP), a metric measuring the variance captured by the top eigenvalues of the data. By focusing on PEP, they prove that the generalization error converges at a rate of $\mathcal{O}(1/n)$, a significant "sharpening" from the standard square-root rate.

Algorithm: GMLKM

To operationalize this theory, the authors developed Graph filter-enhanced Multiple Linear K-Means (GMLKM):

  • Low-Pass Filtering: Inspired by graph signal processing, a low-pass filter is applied to base partitions to smooth out high-frequency noise while preserving low-frequency cluster structures.
  • Learnable Filters: Unlike traditional fixed filters, GMLKM learns optimal filter coefficients for each view.
  • Optimization: An alternating optimization strategy is used to solve for the consensus result, view weights, and filter parameters simultaneously.

Datasets

The authors evaluated GMLKM on ten benchmark datasets spanning image data (JAFFE, ISOLET, Mfeat), biological/single-cell data (Lung, MouseBladder, PBMC, CBMC), and text corpora (CSTR, WAP, K1b). These datasets vary significantly in sample size and feature dimensionality, as detailed in the table below.

Summary of the ten benchmark datasets used in the evaluation.

Key Insights

  • PEP as a Quality Metric: The Principal Eigenvalue Proportion serves as a proxy for clustering "easiness." Dominant eigenvalues indicate a prominent cluster structure and a tighter error bound.
  • Filtering for Theoretical Improvement: Graph filtering is mathematically designed to increase the PEP. By smoothing embeddings, the model "sharpens" its own theoretical bound during execution.
  • Efficiency: Operating in a multiple linear K-means framework ensures computational efficiency, making the method suitable for large datasets where kernel-based methods struggle.

Key Results

GMLKM consistently outperformed state-of-the-art (SOTA) late fusion methods, such as OPLF and ALMVC, across Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI).

Clustering performance comparison across ten datasets using ACC, NMI, and ARI metrics.

As shown in the results table, GMLKM achieved significant gains. For instance, on the Lung dataset, GMLKM reached 87.2% accuracy, compared to 81.5% for standard LFMVC. On the JAFFE dataset, it reached 97.3% accuracy, matching or exceeding other SOTA methods. Furthermore, lower standard deviations in many cases suggest that graph filtering enhances stability against random noise.

Limitations and Future Work

While GMLKM shows strong performance, it relies on a neighborhood size parameter (set to 5 in this study) that may require tuning for very different data structures. Future work may involve exploring more complex or diverse graph filters to further enhance the Principal Eigenvalue Proportion. Additionally, extending the "sharp" $\mathcal{O}(1/n)$ analysis to other multi-view fusion types, such as deep learning-based fusion, remains an open theoretical challenge.

Summary updated

Abstract

Multi-view clustering (MVC) aims to integrate complementary information from multiple views to enhance clustering performance. Late Fusion Multi-View Clustering (LFMVC) has shown promise by synthesizing diverse clustering results into a unified consensus. However, current LFMVC methods struggle with noisy and redundant partitions and often fail to capture high-order correlations across views. To address these limitations, we present a novel theoretical framework for analyzing the generalization error bounds of multiple kernel $k$-means, leveraging local Rademacher complexity and principal eigenvalue proportions. Our analysis establishes a convergence rate of $\mathcal{O}(1/n)$, significantly improving upon the existing rate in the order of $\mathcal{O}(\sqrt{k/n})$. Building on this insight, we propose a low-pass graph filtering strategy within a multiple linear $k$-means framework to mitigate noise and redundancy, further refining the principal eigenvalue proportion and enhancing clustering accuracy. Experimental results on benchmark datasets confirm that our approach outperforms state-of-the-art methods in clustering performance and robustness. The related codes is available at https://github.com/csliangdu/GMLKM .
BibTeX
@misc{du2024sharper,
  author = {Liang Du and Henghui Jiang and Xiaodong Li and Yiqing Guo and Yan Chen and Feijiang Li and Peng Zhou and Yuhua Qian},
  title = {{Sharper Error Bounds in Late Fusion Multi-view Clustering Using Eigenvalue Proportion}},
  year = {2024},
  eprint = {2412.18207},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.18207},
}
Figure