Source-linked AI summary
Spectral Perturbation Meets Incomplete Multi-view Data
Hao Wang, Linlin Zong, Bing Liu, Yan Yang, Wei Zhou
TL;DR
The paper studies clustering when instances are missing from some views, a setting that challenges standard complete-sampling assumptions. It proposes PIC, which completes missing similarities and uses spectral perturbation to learn a consensus clustering representation. Experiments on synthetic and real-life incomplete multi-view data report considerable improvement over state-of-the-art baselines.
Problem
The paper addresses incomplete multi-view clustering, where instances are missing in certain views despite existing methods commonly assuming complete sampling.
Method
PIC transfers missing data values to missing similarity values, completes the similarity matrices, and weights view-specific Laplacians using spectral perturbation theory.
Results
The paper reports considerable improvement over state-of-the-art baselines on toy or synthetic and real-life incomplete multi-view data.
Takeaways & Limitations
The results support using perturbation-risk control and similarity completion as the paper’s fusion criterion for incomplete multi-view clustering.
Takeaways & Limitations
The method assumes that at least one view is available for each data instance.
Abstract
from arXiv · showhide
Beyond existing multi-view clustering, this paper studies a more realistic clustering scenario, referred to as incomplete multi-view clustering, where a number of data instances are missing in certain views. To tackle this problem, we explore spectral perturbation theory. In this work, we show a strong link between perturbation risk bounds and incomplete multi-view clustering. That is, as the similarity matrix fed into spectral clustering is a quantity bounded in magnitude O(1), we transfer the missing problem from data to similarity and tailor a matrix completion method for incomplete similarity matrix. Moreover, we show that the minimization of perturbation risk bounds among different views maximizes the final fusion result across all views. This provides a solid fusion criteria for multi-view data. We motivate and propose a Perturbation-oriented Incomplete multi-view Clustering (PIC) method. Experimental results demonstrate the effectiveness of the proposed method.
1 Introduction
The paper addresses incomplete multi-view clustering, where instances may be missing from some views, by connecting spectral perturbation theory with similarity-matrix completion and consensus learning. PIC completes missing similarities and weights view-specific Laplacians to produce final clustering results.
- Problem: Incomplete multi-view data violate the complete sampling assumption because sensor faults or machine malfunctions can leave instances unsampled in certain views.Existing multi-view clustering methods generally assume every instance appears in every view.
- Related work: Existing incomplete-clustering methods either learn common or view-specific subspaces, often only for two views, or fill missing instances with average feature values.The paper identifies these as two main directions in prior work.
- Contribution: PIC transfers feature-value missing to similarity-value missing and links incomplete multi-view clustering to spectral perturbation theory.The method is explicitly named Perturbation-oriented Incomplete multi-view Clustering.
- Method: In phase 1, PIC generates one similarity matrix per view and completes missing similarity entries using average similarities from views containing those instances.This completion operates after similarity matrices are generated from the view-specific data.
- Method: In phase 2, PIC computes each completed view’s Laplacian, weights the Laplacians using perturbation theory, learns a consensus Laplacian, and clusters it.The approach uses canonical-angle considerations to reduce perturbations among views while balancing them.
- Results: The paper reports considerable improvement over state-of-the-art baselines on toy or synthetic and real-life incomplete multi-view data.The paper presents this as an experimental contribution alongside its perturbation-risk formulation.
2 Preliminaries
The preliminaries describe spectral clustering as a pipeline from view-specific similarities to Laplacian eigenvectors and row-normalized spectral coordinates. They then motivate perturbation control by noting that deviations in similarity matrices can affect clustering, especially across views and at large scale.
- Spectral clustering: NgSC partitions data using the top k eigenvectors of the Laplacian matrix formed from a single-view similarity matrix.The pipeline starts from a data similarity matrix whose entries encode pairwise relationships.
- Spectral clustering: The spectral pipeline computes the k largest Laplacian eigenvalues and corresponding unit eigenvectors, then forms the eigenvector matrix U.The eigenvectors are stacked as columns of U.
- Spectral clustering: Each row of U is normalized to form Y, and the rows of Y are treated as data instances for partitioning.The supplied pipeline continues with a final clustering step based on these normalized rows.
- Ideal case: In the ideal case, rows of the spectral representation cluster around k=c orthogonal points that correspond exactly to the true clusters.This ideal structure relies on zero off-diagonal blocks and connected clusters.
- Perturbation: In general, nonzero off-diagonal blocks create perturbations, and small similarity-matrix changes can affect spectral coordinates and clustering ability.The perturbation is described by expressing the actual matrix as an ideal matrix plus an error term.
- Motivation: When n is very large, even small ϵ can make nϵ non-negligible, motivating consensus-matrix construction and similarity across the resulting spectral rows.The paper frames handling incomplete views, finding a consensus matrix, and matching ideal spectral clustering as its key questions.
3 Proposed Method
PIC handles incomplete multi-view clustering by completing view-specific similarity matrices and learning a consensus Laplacian whose view weights reduce spectral perturbation risk. The method uses canonical-angle bounds to align eigenvector subspaces across views.
- Similarity Matrix Generation: Incomplete views make standard similarity learning inapplicable because each view may contain only nv ≤ n instances.The method assumes at least one view is available for every data instance.
- Similarity Matrix Generation: PIC transfers missing feature values to missing similarity entries by generating a similarity matrix for each view and marking unavailable relationships as NaN.The missing operator assigns NaN when an instance is absent from a view; otherwise, the instance remains available for similarity construction.
- Similarity Matrix Completion: Because similarity values are bounded by O(1), matrix-completion noise is small, supporting a stable completion scheme under the stated recovery theorem.The paper connects bounded similarity magnitude to a small perturbation level in matrix completion.
- Similarity Matrix Completion: Missing similarity entries are completed with average valid-view similarities, producing a full matrix for each view before consensus learning.The completion scheme uses views with valid similarity vectors for the same instance.
- Consensus Learning: PIC learns a consensus Laplacian by weighting completed view Laplacians, with weights chosen to reduce perturbation risk across views.The consensus matrix is constrained as a weighted combination of view Laplacians, with nonnegative weights summing to one.
- Perturbation Risk: The perturbation objective uses canonical angles between view and consensus eigenvector subspaces, whose largest angle measures perturbation level.The method minimizes an upper bound on sin Θ while targeting an ideal Laplacian whose zero-eigenvalue multiplicity equals the number of clusters.
4 Experiments
Experiments evaluate PIC on generated toy and naturally incomplete multi-view datasets against established baselines, using ACC and NMI averaged over repeated runs. PIC outperforms baselines across partial-example settings and datasets, while remaining consistently effective near ˜β=0.1.
- Datasets and baselines: The evaluation uses four complete datasets for generated incomplete data and three naturally incomplete datasets, summarized by views, clusters, instances, observed instances, and features.The first four datasets are complete, while the last three are naturally incomplete.
- Datasets and baselines: Baselines randomly delete partial examples across views under different Partial Example Ratios, while PIC is evaluated with β scaled to balance its objective terms.PIC uses β = ˜β×∥P_v Q_v∥F /∥I∥F and sets ˜β=0.1 in evaluation.
- Experimental results: Accuracy and normalized mutual information measure clustering performance, with each algorithm run 20 times and average values reported.PER varies from 0.1 to 0.9 for the toy incomplete datasets, with PER=0 also included.
- Experimental results: PIC significantly outperforms all baselines across every PER setting on the four toy incomplete multi-view datasets.As PER increases, clustering performance decreases for all methods.
- Experimental results: PIC achieves the best ACC and NMI on each of the three natural incomplete datasets, markedly outperforming the baselines.The results are reported as average values with standard deviations.
- Parameter study: PIC maintains consistently good performance when ˜β is around 0.1 across three natural incomplete datasets.The balance scheme supports using the same ˜β value for all datasets.
5 Conclusions
The paper connects spectral perturbation theory with incomplete multi-view clustering through PIC. Its key strategy is transferring missingness from the data matrix to the similarity matrix and learning a perturbation-aware consensus representation, with theoretical and experimental results showing effectiveness.
- Conclusion: PIC bridges spectral perturbation theory and incomplete multi-view clustering by transferring missingness from the data matrix to the similarity matrix.The method reduces spectral perturbation risk among views while balancing them to learn a consensus representation.
- Conclusion: The paper reports both theoretical and experimental evidence supporting the effectiveness of PIC.