Essential Tensor Learning for Multi-View Spectral Clustering

Jianlong Wu, Zhouchen Lin, Hongbin Zha

TL;DR

Essential Tensor Learning for Multi-view Spectral Clustering (ETLMSC) is a novel framework that captures high-order correlations across multiple data sources by treating transition probability matrices as a 3D tensor. By employing a clever "tensor rotation" trick and t-SVD-based nuclear norm regularization, the method achieves state-of-the-art clustering accuracy while being significantly faster than previous tensor-based approaches.

What Problem Does This Paper Address?

In the real world, data often comes from multiple "views"—for example, a video can be represented by its raw pixels, audio tracks, and text captions. Multi-view spectral clustering aims to combine these sources to group data more accurately than any single view could.

However, existing methods face two major hurdles:

  1. Ignoring High-Order Correlations: Many methods only look at pairwise relationships between views or focus solely on what information is shared across all views, discarding unique, view-specific details that could help clustering.
  2. Computational Complexity: Methods that do try to model complex relationships (like those based on self-representation) often have high computational costs, making them impractical for larger datasets.

Methods

The authors propose ETLMSC, which integrates Markov chain-based spectral clustering with advanced tensor learning. The pipeline follows these key steps:

  1. Transition Probability Construction: For each view, a similarity matrix is built and converted into a transition probability matrix (representing a random walk on a graph).
  2. Tensor Representation: These matrices are stacked into a 3-order tensor $\mathcal{P} \in \mathbb{R}^{N \times N \times M}$ (where $N$ is the number of samples and $M$ is the number of views).
  3. The Rotation Trick: To better explore correlations and save time, the authors rotate the tensor into $\tilde{\mathcal{P}} \in \mathbb{R}^{N \times M \times N}$. This aligns the "view" dimension such that the subsequent Fast Fourier Transform (FFT) operations better capture cross-view relationships.
  4. Essential Tensor Learning: The rotated tensor is decomposed into an "essential" low-rank tensor $\mathcal{Z}$ and a sparse error tensor $\mathcal{E}$. They use the t-SVD based tensor nuclear norm to regularize $\mathcal{Z}$, which is a tighter convex relaxation of tensor rank than previous methods.
  5. Optimization: The model is solved efficiently 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.

Datasets

The authors evaluated ETLMSC on seven diverse real-world datasets:

  • BBC-Sport: Text documents (news articles).
  • UCI-Digits: Handwritten digit images.
  • COIL-20: Images of 20 different objects.
  • Notting-Hill: Video-based face dataset.
  • Scene-15 & MITIndoor-67: Natural and indoor scene categories.
  • Caltech-101: A large-scale object image dataset.

Key Insights and Ideas

  • Rotation is Key: Rotating the tensor isn't just a mathematical quirk; it ensures that the FFT (a core part of the t-SVD process) operates across the view dimension. This preserves relationships between different features and, crucially, reduces the size of the matrices that need SVD, leading to massive speedups.
  • Beyond "Shared" Information: Unlike previous Markov-chain methods (like RMSC) that only look for a single shared probability matrix, ETLMSC learns a full "essential tensor." This allows it to preserve both consistent information across views and useful view-specific information.
  • Robustness via $\ell_{2,1}$-norm: By using the $\ell_{2,1}$-norm on the error tensor $\mathcal{E}$, the model becomes more robust to "noisy" samples that might otherwise skew the transition probabilities.

Key Results

ETLMSC consistently outperformed state-of-the-art (SOTA) methods across all six evaluation metrics (NMI, Accuracy, F-score, etc.):

  • Accuracy Gains: On the BBC-Sport and MITIndoor-67 datasets, ETLMSC improved accuracy by more than 10% over the next best method.
  • Efficiency: On the COIL-20 dataset, ETLMSC finished in 19.6 seconds, whereas the second-best spectral method (RMSC) took 74.8 seconds, and some subspace methods took over 1,000 seconds.
  • Visual Clarity: Visualization of the learned transition matrices shows that ETLMSC produces much cleaner, block-diagonal structures compared to its predecessors, indicating much clearer cluster separation.

Limitations and Future Work

While ETLMSC is efficient, its overall complexity is still tied to the number of samples ($N$). For truly massive datasets with millions of points, even $O(N^2 \log N)$ can be a bottleneck. The authors suggest that future work could explore sampling techniques or tensor sketching to recover the essential tensor from a much smaller "seed" tensor, potentially making the algorithm scalable to web-scale data.

Summary updated

Abstract

Recently, multi-view clustering attracts much attention, which aims to take advantage of multi-view information to improve the performance of clustering. However, most recent work mainly focuses on the 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 the 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 seven 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},
}

Loading related content...

Figure