From Dictionary to Tensor: A Scalable Multi-View Subspace Clustering Framework with Triple Information Enhancement

Zhibin Gu, Songhe Feng

TL;DR

The STONE framework (Scalable TMSC with Triple infOrmatioN Enhancement) revolutionizes multi-view subspace clustering by moving away from computationally expensive self-representation toward a lean, anchor-based approach. By combining a refined hyperbolic tangent tensor rank, anchor-based hypergraphs, and a latent dictionary mechanism, STONE achieves state-of-the-art accuracy while reducing processing times from hours to seconds on large-scale datasets.

The Challenge of Multi-View Subspace Clustering

In modern machine learning, "multi-view" data is ubiquitous—consider a video clip that contains both image frames and audio tracks, or a document with text and structural metadata. Multi-View Subspace Clustering (MVC) aims to group these complex objects by finding a shared low-dimensional structure (a "subspace") that explains all views simultaneously.

While recent methods using 3D tensors have proven highly effective at capturing complex correlations across views, they suffer from three major limitations:

  1. Computational Bloat: Most methods use the entire dataset as a "dictionary" to represent itself. This leads to quadratic ($O(n^2)$) or even cubic ($O(n^3)$) computational complexity, rendering them unusable for large-scale datasets.
  2. Ignoring the "Local" for the "Global": Existing models often focus so heavily on high-level correlations between views that they ignore the local geometric relationships (the "manifold structure") within each individual view.
  3. The "Fairness" Trap in Math: Standard models treat all singular values—mathematical markers of signal and noise—equally. In reality, large singular values represent core features, while small ones are usually just noise. Treating them the same leads to over-smoothing and loss of important data nuances.

The STONE Framework

To address these bottlenecks, the authors propose STONE, which introduces three specific enhancements:

  • Enhanced Anchor Dictionary (EAD): Instead of using every data point as a reference, STONE selects a small set of representative "anchors." It also incorporates a "Latent Low-Rank Representation" (LatLRR) strategy, which essentially creates a "virtual" dictionary to fill in the gaps if the observed data is noisy or insufficient.
  • Anchor Hypergraph Laplacian (AHR): To capture local geometry, the authors utilize hypergraphs. Unlike a standard graph that connects two points with a single edge, a hypergraph can connect a whole group of related points simultaneously. This preserves the complex, non-linear relationships within each view.
  • Hyperbolic Tangent Rank (HTR): This is the mathematical "secret sauce" for the tensor operations. The authors developed a new non-convex function based on the hyperbolic tangent ($tanh$) to approximate the tensor rank.
Comparison of rank approximation functions

As illustrated above, this function is "smarter" because it applies different levels of penalty to different singular values. It protects the large signals while aggressively filtering out the small noise, allowing the curve to "hug" the true rank much more closely than standard methods like the Tensor Nuclear Norm (TNN).

Datasets and Key Insights

The researchers evaluated STONE on eight diverse benchmark datasets, ranging from text (NGs, BBCSport) and digits (HW) to images (Scene15, MSRCV1, Caltech101-all) and large-scale object datasets (ALOI-100 with 10,800 samples, CIFAR10 with 50,000 samples).

  • Linear Scalability is King: By utilizing anchors, the complexity of the algorithm becomes linear ($O(n)$) relative to the number of samples. This allows STONE to handle 50,000 images (CIFAR10) with ease, whereas many competitors would crash due to memory limits or take days to finish.
  • Synergy Matters: Ablation studies demonstrated that the model's performance drops significantly if any of the three enhancements are removed. The "Triple Enhancement" is a functional requirement for the high performance observed, not just a theoretical addition.

Key Results

STONE dominated the competition across almost every metric, including Accuracy (ACC), Normalized Mutual Information (NMI), and F-score.

Clustering performance across benchmark datasets
  • Perfect Scores: As seen in the performance table, STONE achieved a 1.000 (100%) accuracy score on the NGs, BBCSport, HW, and MSRCV1 datasets, significantly outperforming both deep learning and traditional tensor methods.
  • Massive Speedups: On the ALOI-100 dataset, a leading competitor (TBGL) took over 26,000 seconds (over 7 hours) to run. STONE finished the exact same task in just 66.57 seconds.
  • Robustness: Even when the dictionary was "under-sampled" (meaning the model had very few reference points to work with), STONE maintained high accuracy thanks to its latent dictionary mechanism.

Limitations and Future Work

While STONE represents a major leap forward for multi-view clustering, a few areas remain ripe for exploration:

  • Parameter Sensitivity: The model relies on five different hyperparameters (such as $\delta$ for the rank approximation and the number of anchors $l$). While the authors provide a grid search strategy, finding optimal settings for a brand-new dataset might require trial and error.
  • Anchor Selection: The current method uses k-means or random selection to find anchors. Future work could investigate more sophisticated, "data-aware" ways to pick these representative points to further boost accuracy in highly complex datasets.
  • Incomplete Data: The authors note that while STONE is robust, it wasn't specifically designed for "incomplete" multi-view data (where some views are missing for certain samples), which remains a common real-world challenge.

Summary updated

Abstract

While Tensor-based Multi-view Subspace Clustering (TMSC) has garnered significant attention for its capacity to effectively capture high-order correlations among multiple views, three notable limitations in current TMSC methods necessitate consideration: 1) high computational complexity and reliance on dictionary completeness resulting from using observed data as the dictionary, 2) inaccurate subspace representation stemming from the oversight of local geometric information and 3) under-penalization of noise-related singular values within tensor data caused by treating all singular values equally. To address these limitations, this paper presents a \textbf{S}calable TMSC framework with \textbf{T}riple inf\textbf{O}rmatio\textbf{N} \textbf{E}nhancement (\textbf{STONE}). Notably, an enhanced anchor dictionary learning mechanism has been utilized to recover the low-rank anchor structure, resulting in reduced computational complexity and increased resilience, especially in scenarios with inadequate dictionaries. Additionally, we introduce an anchor hypergraph Laplacian regularizer to preserve the inherent geometry of the data within the subspace representation. Simultaneously, an improved hyperbolic tangent function has been employed as a precise approximation for tensor rank, effectively capturing the significant variations in singular values. Extensive experimentation on a variety of datasets demonstrates that our approach surpasses SOTA methods in both effectiveness and efficiency.
BibTeX
@inproceedings{gu2024from,
  author = {Zhibin Gu and Songhe Feng},
  title = {{From Dictionary to Tensor: A Scalable Multi-View Subspace Clustering Framework with Triple Information Enhancement}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=p4a1nSvwD7},
}
Figure