Essential Tensor Learning for Multi-view Spectral Clustering

Jianlong Wu, Zhouchen Lin, Hongbin Zha

Abstract

Multi-view clustering attracts much attention recently, which aims to take advantage of multi-view information to improve the performance of clustering. However, most recent work mainly focus on self-representation based subspace clustering, which is of high computation complexity. In this paper, we focus on the Markov chain based spectral clustering method and propose a novel essential tensor learning method to explore the high order correlations for multi-view representation. We first construct a tensor based on multi-view transition probability matrices of the Markov chain. By incorporating the idea from robust principle component analysis, tensor singular value decomposition (t-SVD) based tensor nuclear norm is imposed to preserve the low-rank property of the essential tensor, which can well capture the principle information from multiple views. We also employ the tensor rotation operator for this task to better investigate the relationship among views as well as reduce the computation complexity. The proposed method can be efficiently optimized by the alternating direction method of multipliers (ADMM). Extensive experiments on six real world datasets corresponding to five different applications show that our method achieves superior performance over other state-of-the-art methods.

Introduction

In many real-world applications, data is inherently multi-modal or multi-view. For instance, a video can be characterized by visual frames, audio signals, and textual descriptions. Multi-view spectral clustering seeks to integrate these diverse information sources to achieve more robust grouping than single-view methods.

Despite its potential, multi-view clustering faces two primary challenges. First, many existing approaches fail to capture high-order correlations, often focusing only on shared information or pairwise relationships, thereby losing view-specific nuances. Second, high-performance methods like those based on self-representation are computationally expensive, limiting their scalability to large datasets.

Methodology

The ETLMSC framework integrates Markov chain-based spectral clustering with advanced tensor learning techniques. The process involves several key stages:

  1. Transition Probability Construction: For each view $m$, a similarity matrix is constructed and transformed into a transition probability matrix $P^{(m)}$, representing a random walk on a graph.
  2. Tensor Representation and Rotation: These matrices are stacked into a 3-order tensor $\mathcal{P} \in \mathbb{R}^{N \times N \times M}$. To better explore cross-view correlations and optimize computation, the tensor is rotated into $\tilde{\mathcal{P}} \in \mathbb{R}^{N \times M \times N}$. This rotation ensures that the Fast Fourier Transform (FFT) used in subsequent steps operates across the view dimension.
  3. Essential Tensor Learning: The rotated tensor is decomposed into a low-rank "essential" tensor $\mathcal{Z}$ and a sparse error tensor $\mathcal{E}$. The t-SVD based tensor nuclear norm regularizes $\mathcal{Z}$, providing a tighter convex relaxation of tensor rank than traditional methods.
  4. Optimization: The model is efficiently solved using the Alternating Direction Method of Multipliers (ADMM).
The ETLMSC pipeline: from multi-view data to essential tensor learning via rotation and t-SVD decomposition.

Experimental Evaluation

The authors evaluated ETLMSC on seven diverse real-world datasets, including BBC-Sport (text), UCI-Digits (handwritten digits), COIL-20 (objects), Notting-Hill (faces), Scene-15, MITIndoor-67 (scenes), and Caltech-101 (large-scale objects).

ETLMSC consistently outperformed state-of-the-art (SOTA) methods across six evaluation metrics, including NMI and Accuracy. Notable results include:

  • Accuracy: On BBC-Sport and MITIndoor-67, ETLMSC improved accuracy by over 10% compared to the next best method.
  • Efficiency: On the COIL-20 dataset, ETLMSC completed in 19.6 seconds, significantly faster than RMSC (74.8s) and various subspace methods (over 1,000s).
  • Clustering Quality: Visualizations of learned transition matrices revealed cleaner, block-diagonal structures, indicating superior cluster separation.

Discussion

A core innovation of ETLMSC is the tensor rotation operator. This is not merely a mathematical convenience; it aligns the view dimension for FFT operations, preserving inter-feature relationships while reducing the size of matrices requiring SVD. This leads to substantial speedups.

Furthermore, unlike previous Markov-chain methods that seek a single shared probability matrix, ETLMSC learns an "essential tensor." This allows the model to retain both consistent information across views and valuable view-specific details. Robustness is further enhanced by using the $\ell_{2,1}$-norm on the error tensor $\mathcal{E}$, mitigating the impact of noisy samples.

Conclusion

ETLMSC provides an efficient and effective framework for multi-view spectral clustering by leveraging high-order tensor correlations. While the method is significantly faster than previous tensor-based approaches, its complexity remains tied to the number of samples ($N$). Future research may explore sampling techniques or tensor sketching to further scale the algorithm for massive, web-scale datasets.

Summary updated

Abstract

Multi-view clustering attracts much attention recently, which aims to take advantage of multi-view information to improve the performance of clustering. However, most recent work mainly focus on self-representation based subspace clustering, which is of high computation complexity. In this paper, we focus on the Markov chain based spectral clustering method and propose a novel essential tensor learning method to explore the high order correlations for multi-view representation. We first construct a tensor based on multi-view transition probability matrices of the Markov chain. By incorporating the idea from robust principle component analysis, tensor singular value decomposition (t-SVD) based tensor nuclear norm is imposed to preserve the low-rank property of the essential tensor, which can well capture the principle information from multiple views. We also employ the tensor rotation operator for this task to better investigate the relationship among views as well as reduce the computation complexity. The proposed method can be efficiently optimized by the alternating direction method of multipliers~(ADMM). Extensive experiments on six real world datasets corresponding to five different applications show that our method achieves superior performance over other state-of-the-art methods.
BibTeX
@article{wu2019essential,
  author = {Jianlong Wu and Zhouchen Lin and Hongbin Zha},
  title = {{Essential Tensor Learning for Multi-view Spectral Clustering}},
  journal = {IEEE Trans. Image Process.},
  year = {2019},
  url = {https://openreview.net/forum?id=Q2jRXGo-WUC},
}
Figure