Beyond Low-Rank Representations: Orthogonal Clustering Basis Reconstruction with Optimized Graph Structure for Multi-view Spectral Clustering

Yang Wang, Lin Wu

TL;DR

This paper proposes a novel approach to multi-view spectral clustering by reframing Low-Rank Representation (LRR) as a latent clustered orthogonal projection. This new perspective allows for the simultaneous learning of cluster bases and optimized local graph structures for each view, leading to improved multi-view consensus and superior clustering performance.

What Problem Does This Paper Address?

Spectral clustering is a powerful technique for partitioning data based on its underlying manifold structure. However, real-world data often comes with multiple feature representations (multi-view data), and effectively combining these views to achieve a better clustering result is a significant challenge. While Low-Rank Representation (LRR) has shown promise in multi-view spectral clustering by encoding local manifold structures, existing LRR methods have limitations: they may not adequately capture flexible latent cluster structures, and the learned low-rank similarities across views might not be on the same magnitude, hindering effective consensus. This paper aims to address these limitations by proposing a new LRR formulation that explicitly models clustered orthogonal projections and optimizes local graph structures in a unified framework.

Methods

The core of this paper's contribution lies in its novel reinterpretation of LRR. Instead of viewing LRR solely as a self-expressive similarity representation, the authors propose to see it as a latent clustered orthogonal projection. This leads to the formulation of a new objective function that simultaneously learns:

  • Orthogonal Clustered Representation ($U_i$): Each column of $U_i$ acts as a cluster basis, indicating the relevance of data points to that cluster. This is achieved through low-rank matrix factorization, where $Z_i = U_i U_i^T$.
  • Optimized Local Graph Structure ($W_i$): For each view, an optimized local graph structure is learned based on the clustered representation $U_i$. This is crucial for spectral clustering and is learned in conjunction with the representation.
  • Multi-view Consensus: The method ensures that the learned representations and graph structures across different views have the same magnitude, facilitating a more robust multi-view consensus.

The optimization problem is solved using an Alternating Direction Minimization (ADM) strategy, iteratively updating the variables $U_i$, $E_i$, $D_i$, $G_i$, and $W_i$ for each view. A key innovation is an efficient row-updating strategy for $U_i$, significantly reducing computational complexity from $O(n^3)$ to $O(c^3)$, where $c$ is the number of clusters.

Datasets

The proposed method is evaluated on three benchmark multi-view datasets:

  • UCI handwritten Digit set: Features character shapes and profile correlations.
  • Animal with Attribute (AwA): Consists of animal descriptions across multiple feature views (color histogram, local self-similarity, etc.).
  • NUS-WIDE-Object (NUS): A large dataset with 31 categories and multiple views derived from color histogram, color moments, color correlation, edge estimation, and wavelet texture.

The paper does not introduce new datasets.

Key Insights and Ideas

  • LRR as Clustered Orthogonal Projection: The most significant insight is reframing LRR from a pure self-expression model to one that explicitly incorporates clustered orthogonal projections. This shift allows for a more direct modeling of cluster structures.
  • Joint Learning of Representation and Graph: The paper highlights the benefit of jointly learning the latent cluster representation and the local graph structure for each view, rather than relying on pre-defined or independently learned graph structures.
  • Magnitude Consistency for Consensus: The insight that ensuring consistent magnitudes of learned representations and graph structures across views is crucial for achieving effective multi-view consensus is a key enabler of the proposed method's superiority.
  • Computational Efficiency: The development of an efficient row-updating strategy for the orthogonal projection matrix $U_i$ is a practical advancement that makes the method more scalable.

Key Results

The proposed method demonstrates superior performance across all three benchmark datasets, achieving higher clustering accuracy (ACC) and normalized mutual information (NMI) compared to several state-of-the-art multi-view spectral clustering methods, including RLRR and LRRGL. For instance, on the NUS dataset, the proposed method achieved an ACC of 45.78%, significantly outperforming LRRGL (41.02%). The paper also shows that the proposed method achieves a smaller multi-view consensus ratio metric, indicating better agreement between views.

Limitations and Future Work

  • Parameter Tuning: The performance of the method is sensitive to the choice of parameters ($\lambda_1, \lambda_2, \beta$). While the paper provides parameter studies and suggests optimal values, finding these parameters can still be a challenge.
  • ADM Convergence: The paper acknowledges that the ADM strategy converges to a stationary point but not necessarily a global optimum. Convergence is defined by a threshold on the reconstruction error or a maximum iteration number.
  • Future Work: The authors suggest that further research could explore more advanced optimization techniques and investigate the application of this framework to other related tasks beyond spectral clustering.

Summary updated

Abstract

Low-Rank Representation (LRR) is arguably one of the most powerful paradigms for Multi-view spectral clustering, which elegantly encodes the multi-view local graph/manifold structures into an intrinsic low-rank self-expressive data similarity embedded in high-dimensional space, to yield a better graph partition than their single-view counterparts. In this paper we revisit it with a fundamentally different perspective by discovering LRR as essentially a latent clustered orthogonal projection based representation winged with an optimized local graph structure for spectral clustering; each column of the representation is fundamentally a cluster basis orthogonal to others to indicate its members, which intuitively projects the view-specific feature representation to be the one spanned by all orthogonal basis to characterize the cluster structures. Upon this finding, we propose our technique with the followings: (1) We decompose LRR into latent clustered orthogonal representation via low-rank matrix factorization, to encode the more flexible cluster structures than LRR over primal data objects; (2) We convert the problem of LRR into that of simultaneously learning orthogonal clustered representation and optimized local graph structure for each view; (3) The learned orthogonal clustered representations and local graph structures enjoy the same magnitude for multi-view, so that the ideal multi-view consensus can be readily achieved. The experiments over multi-view datasets validate its superiority.
BibTeX
@article{wang2017beyond,
  author = {Yang Wang and Lin Wu},
  title = {{Beyond Low-Rank Representations: Orthogonal Clustering Basis Reconstruction with Optimized Graph Structure for Multi-view Spectral Clustering}},
  journal = {Neural Networks},
  year = {2017},
  doi = {10.1016/j.neunet.2018.03.006},
}
Figure