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 Qian · 2024
Read Sharper Error Bounds in Late Fusion Multi-view Clustering Using Eigenvalue Proportion by Liang Du, Henghui Jiang, Xiaodong Li, Yiqing Guo, Yan Chen, Feijiang Li, Peng Zhou, Yuhua Qian (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18207.txt.
Introduction
Liang Du and co-authors set sharp fault bounds for late-join group picks that read a scene by many views. The work dates to 2024. Join picks from split views beats lone-view reads, yet noise and repeat parts can mar the join. High links cross views oft slip past stock tools.
Their proof uses local curve math and chief wave shares to cap fault growth. The cap rate beats the stock rate by a wide span. A sieve step in the frame strips noise and repeat parts, which lifts the chief share. Bench sets showed the frame tops past tools in pick truth and in grit.
Catalog record
| CREATOR | Liang Du, Henghui Jiang, Xiaodong Li, Yiqing Guo, Yan Chen, Feijiang Li, Peng Zhou, Yuhua Qian |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18207
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
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 Qian 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 k -means, leveraging local Rademacher complexity and principal eigenvalue proportions. Our analysis establishes a convergence rate of 𝒪 ( 1 / n ) \mathcal{O}(1/n) , significantly improving upon the existing rate in the order of 𝒪 ( k / n ) \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 . 1 School of Computer and Information Technology, Shanxi University, Taiyuan, 030006, China 2 College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan, 030600, China 3 School of Computer Science and Technology, Anhui University, Hefei, 230601, China 4 Institute of Big Data Science and Industry, Shanxi University, Taiyuan, 030006, China {duliang,fjli,jinchengqyh}@sxu.edu.cn,[email protected],[email protected] Introduction Multi-view data is pervasive across numerous real-world scenarios, including image processing, bioinformatics, and social network analysis ( Zhou, Du, and Li 2023a ; Tang et al. 2022 ; Wang et al. 2021 ; Liu et al. 2022 ) . By integrating complementary information from multiple views, state-of-the-art multi-view clustering (MVC) techniques have significantly advanced clustering performance ( Zhou and Du 2023 ; Tang et al. 2020 ; Zhou et al. 2024 ; Li et al. 2021 ) . Based on their fusion strategies, MVC methods can be broadly categorized into three paradigms: early fusion-based methods ( Liu et al. 2023 ; Nie, Tian, and Li 2018 ) , kernel fusion-based approaches ( Liu 2023 ; Liu et al. 2020 ) , and late fusion-based multi-view clustering (LFMVC) methods ( Liu et al. 2021 ; Wang et al. 2023 ; Zhou et al. 2023 ) . LFMVC follows a two-stage process: first, it independently generates base clustering partitions for each view using methods such as kernel K-means; second, it synthesizes these base partitions into a unified consensus result ( Wang et al. 2019 ) . This paradigm has gained considerable attention for its adaptability and effectiveness in handling diverse multi-view datasets. Over the years, several notable LFMVC methods have advanced the state of the art. For instance, OPLFMVC ( Liu et al. 2021 ) integrates consensus partition learning and label generation into a unified optimization framework. ALMVC ( Zhang et al. 2022 ) introduces orthogonally learned view-specific anchors to enhance clustering performance. MMLMVC ( Li et al. 2024a ) employs the min-max optimization framework from SimpleMKKM ( Liu 2023 ) to refine late fusion strategies. sLGm ( Wu et al. 2024 ) leverages a Grassmann manifold for partition fusion, preserving the topological structure in high-dimensional spaces. Lastly, RIWLF ( Zhang et al. 2024 ) incorporates sample weights as prior knowledge to regularize the late fusion process, improving robustness and adaptability. Despite their success, existing LFMVC approaches encounter persistent challenges. One major issue is the propagation of noise and redundancy in base clustering partitions, which compounds errors and affects the quality of the synthesized consensus. Another limitation is their inability to capture high-order correlations among samples and views, which is critical for fully leveraging the complementary information in multi-view data. These shortcomings restrict the effectiveness of LFMVC methods, particularly in complex scenarios requiring robust performance. To overcome these limitations, we propose a novel theoretical and algorithmic framework to enhance late fusion-based multi-view clustering. Our contributions are twofold. First, we provide a novel generalization error bound analysis for multiple kernel K-means based on local Rademacher complexity and the principal eigenvalue proportion of the underlying data structure. Unlike previous works that achieve a convergence rate of \mathcal{O}(\sqrt{k/n}) , our method reaches \mathcal{O}(1/n) , representing a significant improvement. Second, inspired by the theoretical analysis and recent advances in graph filtering, we develop a low-pass filtering strategy to refine clustering, aiming to improve the principal eigenvalue proportion, under the multiple linear K-means for LFMVC. We validate the effectiveness of our approach on benchmark datasets, demonstrating improvements over state-of-the-art LFMVC methods in terms of clustering results. The main contributions of this paper are summarized as follows: • We establish a novel generalization error bound for multiple kernel K-means based on local Rademacher complexity and principal eigenvalue proportion, achieving an unprecedented convergence rate of \mathcal{O}(1/n) compared to the conventional \mathcal{O}(\sqrt{k/n}) . • Leveraging insights from our theoretical analysis, we propose a low-pass graph filtering-enhanced strategy within the multiple linear K-means framework, aiming to sharpen the clustering error bound by improving the principal eigenvalue proportion. Related Work In this section, we discuss two closely related works in LFMVC that provides generalization error analysis. One Pass Late Fusion Recognizing that the learning of the consensus partition matrix and the assignment of cluster labels are typically conducted as separate processes, which do not adequately inform each other, thus potentially undermining clustering performance, ( Liu et al. 2021 ) addresses this issue by proposing an approach that seamlessly integrates both tasks into a unified optimization framework. The resulting optimization problem can be formulated as follows: \displaystyle\max\quad \displaystyle\mathrm{tr}\left(\mathbf{C}^{T}\mathbf{Y}^{T}\sum_{p=1}^{m}\gamma_{p}\mathbf{H}_{p}\mathbf{W}_{p}\right) (1) \displaystyle\mathrm{s.t.}\quad \displaystyle\mathbf{C}^{T}\mathbf{C}=\mathbf{I}_{c},\mathbf{W}_{p}^{T}\mathbf{W}_{p}=\mathbf{I}_{c},\forall p, \displaystyle\mathbf{Y}\in\{0,1\}^{n\times k},\sum_{p=1}^{m}\gamma_{p}^{2}=1,\gamma_{p}\geq 0, where the objective denotes the alignment between the consensus partition matrix \mathbf{Y} and a group of pre-calculated base partition matrices \{\mathbf{H}_{p}\}_{p=1}^{m} , and \mathbf{W}_{p} is the p -th transformation matrix. It has been pointed out that the clustering generalization error bound based on the Rademacher complexit is of order \mathcal{O}(k/\sqrt{n}) on unseen samples. Max-Min-Max Late Fusion Motivated by the superior performance of kernel fusion-based methods, such as SimpleMKKM ( Liu 2023 ) , and the low computational complexity of late fusion-based approaches, ( Li et al. 2024a ) propose integrating the kernel fusion-based min-max learning paradigm into late fusion MVC, which can be achieved through a max-min-max optimization framework as follows, \displaystyle\max_{\{\mathbf{W}_{p}\}_{p=1}^{m}}\min_{\boldsymbol{\gamma}}\max_{\mathbf{H}}\quad\mathrm{tr}\left(\mathbf{H}^{T}\left(\sum_{p=1}^{m}\gamma_{p}^{2}\mathbf{H}_{p}\mathbf{W}_{p}\right)\right) (2) \displaystyle\mathrm{s.t.}\quad\mathbf{H}^{T}\mathbf{H}=\mathbf{I}_{c},\sum_{p=1}^{m}\gamma_{p}=1,\gamma_{p}\geq 0,\mathbf{W}_{p}^{T}\mathbf{W}_{p}=\mathbf{I}_{c},\forall p, which maximizes the perturbation matrices \{\mathbf{W}_{p}\}_{p=1}^{m} , minimizes view coefficients \boldsymbol{\gamma} and maximizes the clustering partition matrix \mathbf{H} . The generalization clustering performance is upper bounded with the order \mathcal{O}(\sqrt{k/n}) . Notations and Preliminaries Let \mathbb{P} be an unknown distribution on \mathcal{X} , and let \mathbb{S}=\{\mathbf{x}_{i}\}_{i=1}^{n}\subseteq\mathcal{X} be a set of n i.i.d. samples drawn from \mathbb{P} . The empirical distribution \mathbb{P}_{n} is defined as \mathbb{P}_{n}(\{\mathbf{x}_{i}\})=\frac{1}{n} for each \mathbf{x}_{i}\in\mathbb{S} , and \mathbb{P}_{n}(\mathbf{x})=0 for \mathbf{x}\notin\mathbb{S} . Given a kernel function K:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R} , the corresponding kernel matrix is defined as \mathbf{K}=\left[K(\mathbf{x}_{i},\mathbf{x}_{j})\right]_{i,j=1}^{n} . Let \lambda_{1}(\mathbf{K})\geq\lambda_{2}(\mathbf{K})\geq\cdots\geq\lambda_{n}(\mathbf{K})\geq 0 denote its eigenvalues. The Reproducing Kernel Hilbert Space (RKHS) \mathcal{H} is defined as the completion of the span of \{K(\mathbf{x},\cdot):\mathbf{x}\in\mathcal{X}\} . In multiple kernel K-means, a common choice is the convex combination of m basic kernels: \displaystyle\mathcal{K}^{\text{multiple}}=\left\{\sum_{p=1}^{m}\gamma_{p}^{2}\mathbf{K}_{p}\,\middle|\,\sum^{m}_{p=1}\gamma_{p}=1,\gamma_{p}\geq 0\right\}, (3) where \mathbf{K}_{p} are the basic kernels. Multiple