PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation

Yuheng Jia, Hui Liu, Junhui Hou, Sam Kwong, Qingfu Zhang

arXiv:2004.14705v2cs.LGcs.CVstat.ML

TL;DR

MVSC must model relationships across multiple views, but existing tensor low-rank norms do not account for the local structures of similarity tensors. This paper introduces a tailored norm with jointly optimized within-view and cross-view constraints, and reports significant benchmark gains, including perfect clustering on some datasets.

Abstract

from arXiv · show

This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. Unlike the existing methods that all adopt an off-the-shelf tensor low-rank norm without considering the special characteristics of the tensor in MVSC, we design a novel structured tensor low-rank norm tailored to MVSC. Specifically, we explicitly impose a symmetric low-rank constraint and a structured sparse low-rank constraint on the frontal and horizontal slices of the tensor to characterize the intra-view and inter-view relationships, respectively. Moreover, the two constraints could be jointly optimized to achieve mutual refinement. On the basis of the novel tensor low-rank norm, we formulate MVSC as a convex low-rank tensor recovery problem, which is then efficiently solved with an augmented Lagrange multiplier based method iteratively. Extensive experimental results on five benchmark datasets show that the proposed method outperforms state-of-the-art methods to a significant extent. Impressively, our method is able to produce perfect clustering. In addition, the parameters of our method can be easily tuned, and the proposed model is robust to different datasets, demonstrating its potential in practice.

I. INTRODUCTION

Multi-view spectral clustering uses complementary perspectives from multiple modalities or feature types, while tensor methods model their relationships through stacked similarity matrices. The paper argues that general-purpose tensor low-rank norms miss MVSC’s local structures and proposes a tailored alternative.

I. INTRODUCTION

  • Tensor-based MVSC stacks multiple-view similarity matrices and exploits tensor low-rankness to capture higher-order correlations among features.Prior approaches use different tensor low-rank norms, including one based on tensor SVD and tensor rotation for view consensus.Source: §I · p. 1
  • Earlier tensor-based MVSC methods use general-purpose tensor low-rank norms, although multi-view similarity tensors have distinctive local structures.The paper identifies block-diagonal frontal slices for within-view relationships and column/row-wise sparse horizontal and lateral slices for inter-view relationships.Source: §I · p. 1, Figure 1 · p. 2
  • The proposed MVSC-tailored norm constrains frontal slices symmetrically and horizontally slices as column-wise sparse, optimizing both together for mutual enhancement.The resulting convex low-rank tensor recovery problem is solved with an augmented Lagrange multiplier method.Source: §I · pp. 1–2, Figure 1 · p. 2

A. Tensor Low-Rank Norm (TLRN)

  • Tensors are higher-order multidimensional arrays, and unlike matrix rank, tensor rank is not unique across decompositions.The CP rank is induced by CP decomposition, while Tucker rank is a vector of ranks of mode-wise matricizations.Source: A. Tensor Low-Rank Norm (TLRN) · p. 2
  • The sum of nuclear norms relaxes the discrete, non-convex Tucker rank.Its terms use mode-wise tensor unfoldings, mode-specific weights, and matrix nuclear norms.Source: A. Tensor Low-Rank Norm (TLRN) · p. 2
  • Tensor SVD induces tubal rank, which counts non-zero tubes in its core tensor, and has motivated alternative tensor nuclear norms.The cited alternatives include a norm based on t-SVD and one using only the first frontal slice of the core tensor.Source: A. Tensor Low-Rank Norm (TLRN) · p. 2

B. Mulit-View Spectral Clustering (MVSC)

Multi-view spectral clustering methods seek to combine agreement and complementary information across views, using both shared representations and view-specific strategies. Tensor-based methods exploit stacked similarity matrices, but the paper notes that their general-purpose low-rank norms do not encode MVSC’s special characteristics.

B. Mulit-View Spectral Clustering (MVSC)

  • Non-tensor MVSC methods pursue consensus, complementary information, or both, with approaches including shared representations, co-training, and diversity terms.Other work also explores latent-space formulations.Source: B. Mulit-View Spectral Clustering (MVSC) · p. 3
  • Tensor-based MVSC stacks view similarity matrices and uses tensor low-rankness to refine them from a higher-order perspective, naturally considering consistency and complementarity.Existing approaches include self-representation, t-SVD-based methods, and robust tensor principal component analysis.Source: B. Mulit-View Spectral Clustering (MVSC) · p. 3
  • Prior tensor MVSC work validates low-rank modeling of similarity relationships, but its general-purpose tensor norms do not account for MVSC’s special characteristics.The paper identifies this mismatch as a potential limitation for clustering performance.Source: B. Mulit-View Spectral Clustering (MVSC) · p. 3

III. PROPOSED METHOD

Tensor-based MVSC constructs a tensor by stacking per-view similarity matrices. The paper proposes a tailored low-rank norm because these tensors have special structures that general-purpose norms do not capture.

III. PROPOSED METHOD

  • For each view, an n × n similarity matrix describes pairwise sample relationships, and the matrices are stacked into a 3-D tensor.The i-th frontal slice is the similarity matrix for view i.Source: §III · p. 3
  • The paper argues that general-purpose tensor low-rank norms exploit the tensor globally, whereas MVSC similarity tensors require local structures to be represented.This motivates a tensor low-rank norm tailored to the special structures of multiple similarity matrices.Source: §III · pp. 3–4
  • The proposed tailored norm is designed to better characterize the special structures of tensors formed from multiple similarity matrices.The paper contrasts it with existing tensor low-rank norms, which it says may not be the best choice for MVSC.Source: §III · pp. 3–4

A. Proposed MVSC Tailored TLRN

The tailored norm models intra-view structure through symmetric low-rank frontal slices and inter-view structure through column-wise sparse horizontal slices. Combining the penalties optimizes both relationships together.

A. Proposed MVSC Tailored TLRN

  • Symmetry and low-rankness regularize frontal slices to capture the block-diagonal intra-view similarity structure.Each frontal slice represents relationships among samples within a view.Source: A. Proposed MVSC Tailored TLRN · p. 4
  • Horizontal slices model inter-view relationships for a sample, with column-wise sparsity favoring only a few nonzero columns.The regularizer combines a low-rank term with a column-wise sparse norm.Source: A. Proposed MVSC Tailored TLRN · p. 4
  • The tailored norm combines frontal- and horizontal-slice constraints so intra-view and inter-view relationships are optimized together.The weights balance the two penalties, whose joint minimization is described as allowing them to boost each other.Source: A. Proposed MVSC Tailored TLRN · p. 4
  • The proposed norm replaces rank and ℓ2,0 terms with the nuclear norm and ℓ2,1 norm to obtain a valid convex norm.The paper identifies the nuclear norm and ℓ2,1 norm as convex-hull relaxations of the original terms.Source: A. Proposed MVSC Tailored TLRN · p. 4

B. Proposed MVSC Model

The model casts MVSC as low-rank tensor recovery using the tailored norm. It regularizes the error tensor with a Frobenius-type norm and distinguishes its slice-based constraints from SNN.

B. Proposed MVSC Model

  • The proposed MVSC-tailored norm is used to formulate clustering as a low-rank tensor recovery problem.The recovered tensor is encouraged to match the ideal appearance of a tensor formed from ideal similarity matrices.Source: B. Proposed MVSC Model · p. 4
  • The model regularizes its noise error tensor with a Frobenius-type norm rather than an ℓ1 norm.The authors state that a sparse regularizer on the error tensor would conflict with the ℓ2,1 norm on horizontal slices.Source: B. Proposed MVSC Model · p. 4
  • Unlike SNN’s tensor matricizations, the proposed norm acts on frontal and horizontal slices with symmetric and column-wise sparse constraints, respectively.The paper characterizes SNN as a general-purpose relaxation of tensor Tucker rank and its own norm as tailored to MVSC tensor structure.Source: B. Proposed MVSC Model · p. 4

C. Optimization Algorithm

The optimization uses inexact augmented Lagrange multipliers to split the convex recovery problem into smaller subproblems. It iterates updates and constructs a final similarity matrix from the recovered tensor for spectral clustering.

C. Optimization Algorithm

  • IALM introduces three auxiliary tensors, each constrained to equal the recovered tensor, and splits the recovery problem into smaller subproblems.The reformulation also imposes W = Lk + E for each auxiliary tensor.Source: C. Optimization Algorithm · p. 4
  • The resulting subproblems include symmetric nuclear-norm minimization, nuclear-norm minimization, and ℓ2,1-norm minimization, each with a closed-form solution.The tensor and multiplier updates are performed iteratively until convergence.Source: C. Optimization Algorithm · p. 5
  • The algorithm iteratively updates the slice variables, recovered tensor, error tensor, multipliers, and penalty parameter.Its input includes the stacked-view similarity matrices and the parameters ω1, λ, and α.Source: C. Optimization Algorithm · p. 5
  • After recovery, the method averages L along the frontal direction to form S and applies spectral clustering to S.The stated output of the iterative algorithm is L.Source: C. Optimization Algorithm · p. 5

D. Computational Complexity Analysis

The algorithm’s stated computational complexity is O(v^2n^2 + cvn^2), dominated by the two nuclear-norm subproblems.

D. Computational Complexity Analysis

A. Experiment Settings

The experiments evaluate multi-view clustering on five image datasets, comparing tensor and non-tensor methods under a shared clustering and evaluation protocol.

A. Experiment Settings

  • The study uses five multi-view image datasets, including face and object data and UCI-digit, with three feature views constructed for each dataset.Face and object datasets use Gabor, LBP, and intensity features; UCI-digit uses Fourier coefficients, morphological features, and pixel averages.Source: A. Experiment Settings · p. 6
  • Coil20 has 20 objects with 72 samples each; Yale has 165 face images from 15 people; ORL has 40 people with 10 images each.YaleB contains about 64 images per person across 38 people, and the study uses its first 10 classes; UCI-digit has 2,000 digits in 10 classes.Source: A. Experiment Settings · p. 6
  • Comparisons include non-tensor MVSC methods L-MSC, DiMSC, MCLES, and AWP, plus tensor-based methods including LT-MSC, Ut-SVD-MSC, t-SVD-MSC, ETLMSC, and SCMV-3DT.SNN and TRPCA are also included as tensor low-rank norm comparisons.Source: A. Experiment Settings · pp. 6–7
  • All methods were clustered using SC; for compared MVSC methods, hyperparameters were exhaustively tuned within original-paper suggested ranges, and best average results and standard deviations were reported over 20 trials.Seven metrics were used: ACC, NMI, ARI, F1-score, Precision, Recall and Purity; larger values indicate better performance for all metrics.Source: A. Experiment Settings · p. 7

B. Comparison of Clustering Performance

The proposed method achieves perfect or near-perfect clustering on several datasets and leads across all five; visual comparisons show sparser, more diagonal similarity connections than competing approaches.

B. Comparison of Clustering Performance

  • Table VII is an ablation study of the model's regularization terms; its caption states that setting a parameter to zero removes the corresponding term.Source: Table VII · p. 8
  • All samples are clustered correctly on ORL and Coil20, while ACC reaches 0.988 on Yale and 0.998 on UCI-digit; on YaleB, all metrics exceed 0.90 versus below 0.71 for other methods.On YaleB, the proposed method improves ARI by more than 65% over the second-best method and consistently performs best across datasets.Source: B. Comparison of Clustering Performance · pp. 7–8

C. Visual Comparison of the Learned Similarity Matrix

  • Figure 4 reports that the method achieves its highest clustering performance across wide ranges of ω1, λ, and α.The caption presents this as evidence of robustness to these hyper-parameters.Source: Figure 4 · p. 9
  • Figure 5 compares the running times of different methods on five datasets, without stating a runtime winner in the supplied text.Source: Figure 5 · p. 9
  • On ORL and YaleB, the proposed method yields sparse, diagonal similarity connections, unlike the dense SNN and TRPCA matrices and the incorrect cross-cluster links of LT-MSC and t-SVD-MSC.The text attributes removal of incorrect connections to column-wise sparse regularization on horizontal slices while preserving correct connections through cross-view information.Source: C. Visual Comparison of the Learned… · p. 9, Figure 3 · p. 9

D. Parameter Analysis

Across five benchmark datasets, the model significantly outperformed eleven state-of-the-art MVSC methods. Its parameters were relatively easy to choose, and its running time was roughly comparable to most methods under comparison.

D. Parameter Analysis

  • ORL’s highest ACC spans ω1=0.3–0.7, α=2–7, and λ=10–44; selected settings across datasets are close and within these ranges.Coil20 also attains its highest ACC across a wide range of hyper-parameters.Source: D. Parameter Analysis · pp. 9–10

E. Ablation Study

  • Removing any regularization term substantially reduces clustering performance, and setting ω1=0 usually produces the worst result.The paper links the frontal slice to intra-view similarity and the final clustering task.Source: E. Ablation Study · p. 10
  • Using LT-MSC or ETLMC outputs as initial similarity matrices, the proposed model significantly improves each method’s performance.The authors conclude that it can serve as a post-processing technique for existing MVSC methods.Source: E. Ablation Study · p. 10

F. Comparison of Running Time

  • Running time is roughly at the same level as SNN, TRPCA, and LT-MSC, and the method is much faster than MCLES on large datasets.The reported large datasets are YaleB, Coil20, and UCI-digital.Source: F. Comparison of Running Time · p. 10

V. CONCLUSION AND FUTURE WORK

  • The MVSC-tailored norm characterizes intra- and inter-view relationships, framing MVSC as low-rank tensor learning solved with an augmented Lagrange multiplier method.Source: §V · p. 10
  • Across five benchmark datasets, the model significantly outperformed eleven state-of-the-art MVSC methods.The conclusion also reports robustness to different datasets and initial similarity matrices.Source: §V · pp. 10–11

Related papers

Loading 2004.14705v2…