PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex Sparse Spectral Clustering: Single-view to Multi-view

Canyi Lu, Shuicheng Yan, Zhouchen Lin

arXiv:1511.06860v3cs.CV

TL;DR

Spectral clustering does not explicitly exploit the ideally sparse, block-diagonal structure of UU^T, and its multi-view pairwise extension is nonconvex. The paper introduces convex sparse spectral models, solves them with ADMM, and reports effective single-view and multi-view performance on real-world datasets.

  • Problem

    Spectral clustering does not explicitly use the ideally block-diagonal, sparse structure of UU^T, while pairwise multi-view clustering has a nonconvex objective.

  • Method

    SSC adds sparsity regularization to UU^T and uses a Fantope-based convex relaxation; PSSC extends SSC to multi-view data, with ADMM optimization.

  • Results

    SSC outperforms SC in all reported comparisons, while PSSC generally achieves the best or comparable multi-view performance and is more stable than other multi-view methods.

  • Takeaways & Limitations

    Sparse regularization on UU^T is effective for improving spectral clustering, and the proposed convex formulations make optimal solutions computable.

Abstract

from arXiv · show

Spectral Clustering (SC) is one of the most widely used methods for data clustering. It first finds a low-dimensonal embedding $U$ of data by computing the eigenvectors of the normalized Laplacian matrix, and then performs k-means on $U^\top$ to get the final clustering result. In this work, we observe that, in the ideal case, $UU^\top$ should be block diagonal and thus sparse. Therefore we propose the Sparse Spectral Clustering (SSC) method which extends SC with sparse regularization on $UU^\top$. To address the computational issue of the nonconvex SSC model, we propose a novel convex relaxation of SSC based on the convex hull of the fixed rank projection matrices. Then the convex SSC model can be efficiently solved by the Alternating Direction Method of \canyi{Multipliers} (ADMM). Furthermore, we propose the Pairwise Sparse Spectral Clustering (PSSC) which extends SSC to boost the clustering performance by using the multi-view information of data. Experimental comparisons with several baselines on real-world datasets testify to the efficacy of our proposed methods.

I. INTRODUCTION

Clustering partitions data into groups whose within-cluster points are more similar than points in other clusters. Spectral Clustering is a widely used clustering method with many variants and applications.

  • Clustering partitions data points into groups with greater within-cluster similarity than between-cluster similarity.
  • Spectral Clustering is one of the most widely used clustering methods.
  • Spectral Clustering has multiple variants and has been applied across several disciplines.

A. Related Work

Prior work improves spectral clustering through affinity construction or clustering-result optimization. This paper focuses on sparse spectral embeddings and extends them to pairwise multi-view clustering.

  • Related approaches: Existing spectral-clustering improvements generally target robust affinity or graph construction, or improve clustering with a fixed affinity matrix.
  • Positioning: This work focuses on constructing the low-dimensional embedding U differently rather than changing the affinity matrix or Laplacian construction.
  • Multi-view learning: Multi-view data provide complementary representations, and exploiting them generally boosts learning-task performance.
  • Pairwise spectral clustering: Pairwise Spectral Clustering trades off spectral-clustering objectives against cross-view embedding disagreement, but its nonconvex optimization lacks convergence guarantees when m > 2.
  • Proposed extension: Pairwise Sparse Spectral Clustering further encourages each UiUi^T to be sparse and uses a convex formulation solved by ADMM.

B. Contributions

The paper proposes convex sparse spectral methods for single-view and multi-view clustering, together with an efficient ADMM solver.

  • Contributions: The convex SSC model encourages UU^T to be sparse, treating |UU^T| as an affinity matrix expected to be block diagonal ideally.
  • Contributions: PSSC leverages multi-view information and remains convex, making its optimal solutions computable.
  • Contributions: An efficient ADMM algorithm solves the convex SSC and PSSC problems.

II. SPARSE SPECTRAL CLUSTERING

SSC promotes a sparse, block-diagonal-like refined affinity structure in spectral clustering. A Fantope-based convex relaxation replaces the nonconvex formulation, after which eigenvectors and k-means produce clusters.

  • Motivation: In the ideal block-diagonal affinity case, UU^T is block diagonal and therefore naturally sparse.
  • SSC model: SSC adds a sparsity penalty on UU^T, balancing the spectral-clustering objective against sparsity through β.
  • Convex relaxation: The nonconvex SSC problem replaces the ℓ0 penalty with ℓ1 and the fixed-rank projection set with its convex hull.
  • Convex relaxation: The convex feasible set is the Fantope: P satisfies 0 ⪯ P ⪯ I and Tr(P) = k.
  • Convex relaxation: With β = 0, the convex formulation is equivalent to spectral clustering; with β > 0, it is a relaxation rather than a guaranteed extreme-point solution.
  • Optimization and clustering: ADMM efficiently computes the convex solution, whose leading eigenvectors approximate U for the final spectral-clustering procedure.
  • Relation to sparse PCA: SSC differs from sparse PCA because its sparse matrix represents a refined affinity matrix, while sparse PCA targets sparse principal components.

III. MULTI-VIEW EXTENSION: PAIRWISE SPARSE SPECTRAL CLUSTERING

PSSC extends sparse spectral clustering to multi-view data by combining pairwise view agreement with sparse regularization, then relaxes the nonconvex model to a convex problem.

  • III. MULTI-VIEW EXTENSION: PAIRWISE SPARSE SPECTRAL CLUSTERING: PSSC extends SSC beyond single-view clustering by using information from multiple data views.The model assumes m views with corresponding normalized Laplacian matrices.
  • III. MULTI-VIEW EXTENSION: PAIRWISE SPARSE SPECTRAL CLUSTERING: The model trades off pairwise spectral embedding agreement against sparse regularizers on each view's projection matrix.Common α weights pairwise co-regularizers, while common β weights sparsity across views.
  • III. MULTI-VIEW EXTENSION: PAIRWISE SPARSE SPECTRAL CLUSTERING: PSSC replaces its nonconvex formulation with a convex relaxation using Fantope constraints on projection matrices.The constraints require 0 ⪯ Pi ⪯ I and Tr(Pi) = k for every view.
  • III. MULTI-VIEW EXTENSION: PAIRWISE SPARSE SPECTRAL CLUSTERING: After solving the convex problem, PSSC extracts each view's leading eigenvectors and combines them before k-means clustering.The eigenvectors correspond to the largest k eigenvalues of each optimized projection matrix.

IV. OPTIMIZATION BY ADMM

The paper solves the convex PSSC formulation with ADMM by splitting coupled variables into separable blocks. The method has a convergence rate of O(1/K), but its O(Kmn^3) complexity can exceed traditional SC for larger datasets.

  • IV. OPTIMIZATION BY ADMM: SSC is a special case of PSSC, so the paper presents ADMM optimization details for the convex PSSC problem.SSC corresponds to m = 1 and α = 0.
  • IV. OPTIMIZATION BY ADMM: ADMM introduces auxiliary variables Pi = Qi and alternately updates the projection and auxiliary-variable blocks.The augmented Lagrangian separates updates across views, and dual variables are updated after both blocks.
  • IV. OPTIMIZATION BY ADMM: The Pi updates use the proximal mapping of the ℓ1-norm, implemented elementwise through a soft-thresholding operation.The supplied passages describe the proximal mapping and its elementwise update.
  • IV. OPTIMIZATION BY ADMM: The Qi updates project onto the set of matrices satisfying 0 ⪯ Qi ⪯ I and Tr(Qi) = k.This projection reduces to a capped simplex projection problem.
  • IV. OPTIMIZATION BY ADMM: For convex PSSC, ADMM is guaranteed to reach an optimal solution with convergence rate O(1/K).K denotes the number of iterations.
  • IV. OPTIMIZATION BY ADMM: The algorithm has computational complexity O(Kmn^3), with experiments finding approximately 100–200 iterations and a potential K-fold cost over traditional SC.The paper identifies scalable SSC as future work.

V. EXPERIMENTS

Experiments on real-world datasets evaluate SSC for single-view clustering and PSSC for multi-view clustering, including comparisons of running time.

  • V. EXPERIMENTS: The experiments assess SSC against SC for single-view clustering and PSSC for multi-view clustering.The study also reports running times for compared methods on several datasets.

A. Single-view Experiments

Single-view experiments evaluate SSC on motion segmentation and face clustering using affinity matrices from ℓ1-graph and LRR-graph methods. SSC offers limited gains on Hopkins 155 but significantly outperforms SC in most Extended Yale B cases.

  • A. Single-view Experiments: SSC is tested on Hopkins 155 motion segmentation and Extended Yale B face clustering.The affinity matrices are constructed using ℓ1-graph and LRR-graph methods.
  • A. Single-view Experiments: Hopkins 155 contains 155 video sequences, including 120 with two motions and 35 with three motions.The experiments report mean and median segmentation error rates across 156 subspace-segmentation problems.
  • A. Single-view Experiments: Extended Yale B contains 2,414 face images from 38 subjects and is evaluated on randomly selected subsets of 5, 8, and 10 subjects.Images are resized to 32×32 pixels and used as 1,024-dimensional vectorized data points over 20 repeated trials.
  • A. Single-view Experiments: Hopkins 155 shows limited improvement from SSC because preprocessing reduces noise and both affinity constructions are already discriminative.SC performs very well, with most sequence segmentation errors equal to zero.
  • A. Single-view Experiments: SSC significantly outperforms SC in most Extended Yale B cases, where illumination variation produces larger clustering errors.The best SSC regularization values are β = 10^-4 for ℓ1-graph and β = 10^-3 for LRR-graph.

B. Multi-view Experiments

The multi-view experiments evaluate PSSC against single-view and multi-view baselines on five real-world datasets. PSSC is usually best or comparable to the best, while sparse methods incur greater computational cost and require parameter tuning.

  • Experimental setup: The datasets represent complementary views including image features, multilingual documents, news sources, webpages, and handwritten-digit features.Examples include three views for Caltech-101, five views for Reuters, three sources for 3-sources, content and links for WebKB, and three selected features for UCI Digit.
  • Experimental setup: The study evaluates PSSC on five real-world multi-view datasets against single-view and multi-view clustering methods.The compared methods include SC, SSC, LD-SSC, Feature Concatenation, Kernel Addition, RMSC, PSC, and PSSC.
  • Results: PSSC achieves the best performance or is comparable to the best result in most cases and is more stable than some multi-view methods.The paper specifically notes poor performance by RMSC on the 3-sources dataset.
  • Results: SSC always outperforms SC, while PSSC similarly outperforms PSC, supporting sparse regularization on the spectral embedding products.The compared matrices act as affinity matrices, and SSC/PSSC exhibit more salient block-diagonal structure than SC/PSC.
  • Results: Single-view SC and SSC can outperform some multi-view methods on the first three datasets, so multi-view gains are not guaranteed.The paper states that view discriminativeness, diversity, and the method used to combine views are crucial.
  • Efficiency and sensitivity: SSC and PSSC have higher computational cost than SC, and their additional β parameter requires tuning.The running-time comparison reports SC as more efficient than SSC; PSSC is slower than PSC, while β values no larger than 10^-3 performed well and stably.

VI. CONCLUSIONS AND FUTURE WORK

The paper develops convex SSC and PSSC methods for sparse spectral clustering, but identifies unresolved theoretical questions about SSC’s clustering quality and relaxation tightness.

  • Conclusions: SSC extends spectral clustering with sparse regularization, while PSSC additionally exploits multiview information.The methods are presented as convex approaches, with the original SSC formulation relaxed using projection-matrix structure.
  • Conclusions: The original SSC model is nonconvex, motivating a tight convex relaxation based on the convex hull of fixed-rank projection matrices.The appendix characterizes optimal solutions through eigenvalue decompositions under the relaxation constraints.
  • Conclusions: The paper reports extensive real-world experiments demonstrating the effectiveness of the proposed methods.
  • Future work: The authors lack proof that the SSC formulation computes a reasonable clustering or specify conditions under which it performs well.These questions are left for future exploration.
  • Future work: The tightness of the convex relaxation remains unresolved, including when solving the relaxation can recover the original nonconvex solution.
Loading 1511.06860v3…