PaperlayerView exact revision on arXiv

Source-linked AI summary

Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view

Zhao Kang, Zhiping Lin, Xiaofeng Zhu, Wenbo Xu

arXiv:2102.07943v1cs.LGcs.AIcs.CV

TL;DR

Graph-based subspace clustering faces high computational cost, weakly explicit cluster structure, and difficulty handling unseen data. The paper addresses these issues with anchor-based bipartite graph learning and connectivity constraints, extending the framework to multi-view data. Experiments report improved clustering performance and efficiency against state-of-the-art methods.

  • Problem

    Graph-based subspace clustering must address high complexity, insufficiently explicit graph structure, and inability to generalize to unseen data points.

  • Method

    The framework selects anchors, learns a smaller sample–anchor bipartite graph with constrained connectivity, and extends it to multi-view data with view-wise weights.

  • Results

    SGL outperforms state-of-the-art methods in most cases, improving KMM by 12.57% in ACC, 15.06% in NMI, and 14.49% in Purity on average.

  • Takeaways & Limitations

    The framework learns an explicit cluster structure in linear complexity while reducing time complexity without sacrificing clustering performance.

Abstract

from arXiv · show

Graph-based subspace clustering methods have exhibited promising performance. However, they still suffer some of these drawbacks: encounter the expensive time overhead, fail in exploring the explicit clusters, and cannot generalize to unseen data points. In this work, we propose a scalable graph learning framework, seeking to address the above three challenges simultaneously. Specifically, it is based on the ideas of anchor points and bipartite graph. Rather than building a $n\times n$ graph, where $n$ is the number of samples, we construct a bipartite graph to depict the relationship between samples and anchor points. Meanwhile, a connectivity constraint is employed to ensure that the connected components indicate clusters directly. We further establish the connection between our method and the K-means clustering. Moreover, a model to process multi-view data is also proposed, which is linear scaled with respect to $n$. Extensive experiments demonstrate the efficiency and effectiveness of our approach with respect to many state-of-the-art clustering methods.

I. INTRODUCTION

The paper targets high complexity, weakly explicit cluster structure, and the inability to handle unseen data in graph-based subspace clustering. It proposes scalable single-view and multi-view graph learning based on anchors and bipartite graphs.

  • Motivation: Graph-based subspace clustering can require O(n^2) memory and O(n^3) eigen-decomposition time, making large-scale processing costly.Existing graph-based models also do not generalize to unseen data points because the graph must be learned for all samples during training.
  • Objectives: The framework jointly addresses high complexity, explicit graph structure, and out-of-sample handling for subspace clustering.Its multi-view extension additionally seeks a structured graph compatible across views.
  • Approach: The method selects m landmarks with K-means, learns a sample–landmark bipartite graph, and obtains a cluster indicator matrix from its k connected components.The framework uses the smaller graph to preserve manifold information and applies view-wise weights for multi-view data.
  • Contributions: The proposed structured graph learning framework is designed for large-scale subspace clustering in linear time and supports out-of-sample data.A scalable multi-view model lets the bipartite graph, cluster indicator matrix, and view-wise weights interactively supervise one another.
  • Validation: Theoretical analysis connects the method to K-means, while experiments report effectiveness and efficiency against state-of-the-art clustering techniques.The paper organizes separate single-view and multi-view experiments after its theoretical and complexity analyses.

A. Subspace Clustering

Conventional subspace clustering learns an n×n similarity graph and then applies spectral clustering, creating scalability and out-of-sample limitations. The paper instead uses anchors and imposes an explicit connected-component structure on a smaller graph.

  • Subspace clustering: Subspace clustering represents each sample as a combination of points in the same subspace, with the coefficient matrix serving as a similarity graph.The standard model combines reconstruction error with a regularizer under nonnegativity and row-sum constraints.
  • Limitations: The n×n graph and subsequent spectral clustering can impose O(n^3) computation, burdening computation and storage for large-scale data.Existing low-complexity methods may still fail to handle out-of-sample data or explicitly encode graph structure.
  • Anchor graph: Anchors are a small set of representative samples used to build a smaller n×m graph measuring relationships between data points and anchors.Anchors may be selected by K-means cluster centers or random sampling, while Gaussian-kernel graph construction may be inflexible for complex data.
  • Structured graph: The unconstrained anchor graph may form one connected component, so the model seeks exactly k connected components when the data contain k clusters.This constraint explicitly ties the graph structure to the desired cluster structure.

III. STRUCTURED GRAPH LEARNING

The structured graph learning model uses bipartite-graph connectivity to make cluster structure explicit. Spectral graph theory links the number of connected components to zero Laplacian eigenvalues, motivating a rank constraint that is later relaxed.

  • Bipartite graph: A bipartite graph explicitly represents relationships between data samples and anchors, enabling direct control of its connected components.The constrained graph is intended to contain a specified number of components.
  • Graph spectrum: The normalized Laplacian is constructed from the bipartite graph and its degree matrix.The degree of node i is defined as the sum of its incident edge weights.
  • Graph spectrum: The number of connected components equals the multiplicity of the zero eigenvalue of the normalized Laplacian.This spectral property provides the basis for encoding a desired cluster count.
  • Connectivity constraint: If rank(L) = (n + m) − k, the n samples and m anchors are grouped into k clusters.The resulting constraint is combined with nonnegative graph weights and row-normalization.
  • Optimization: The proposed Structured Graph Learning framework relaxes the hard rank constraint and solves the resulting problem by alternating optimization.The framework is presented as an explicit structured graph-learning formulation.

A. Optimization Strategy

The method alternates updates of the graph and clustering-related variables, exploiting the bipartite graph structure to reduce eigenvector computation to a smaller matrix. The objective value decreases monotonically and therefore converges.

  • The optimization alternates between fixing Z and updating F, then fixing F and updating Z.
  • With Z fixed, the F subproblem is solved using the special structure of the graph matrix S.The method avoids directly computing all eigenvectors of S.
  • The optimal factor matrices are obtained from the top k left and right singular vectors of Q.
  • The complete alternating algorithm monotonically decreases the objective and converges because the objective has a lower bound.

B. Out-of-sample Problem

SGL addresses unseen data by propagating anchor-point labels with kNN, while its connectivity constraint makes connected components correspond directly to clusters and links the formulation to K-means.

  • Out-of-sample handling: For each unseen data point, SGL propagates anchor-point cluster labels using classic kNN in O(md) time.The method outputs anchor embeddings and labels before applying kNN.
  • Connectivity and K-means: When α approaches infinity, the proposed problem becomes equivalent to the K-means problem.
  • Connectivity and K-means: The connectivity constraint requires k connected components, with each component containing data points and anchor points assigned to one cluster.
  • Connectivity and K-means: The method's partition objective is exactly the K-means objective after imposing the component structure.

B. Complexity Analysis

SGL scales through an anchor-based graph Z ∈ R^n×m with m ≪ n and SVD on the smaller matrix, while its iterative updates have explicitly analyzed costs.

  • SGL constructs a smaller graph Z ∈ R^n×m, where m ≪ n, and applies SVD to reduce computational complexity.
  • The SVD step for obtaining U costs O(m^3t + mnt), while computing W costs O(mnt).
  • Solving Z by convex quadratic programming costs O(nm^3t), and the updates can be solved in parallel.
  • Building the anchor dictionary costs O(nmt1d), while final K-means on U costs O(nk^2t1).
  • Several scalable clustering methods have linear complexity, although some sacrifice accuracy for time efficiency.

V. MULTI-VIEW STRUCTURED GRAPH LEARNING

MSGL extends structured graph learning to multi-view data by using a shared graph across views and view-specific weights to balance their importance.

  • MSGL handles multi-view data matrices X1, X2, ..., Xc while requiring all views to share one cluster pattern.
  • The model uses a unique graph Z to represent the common clustering structure across views.
  • View-specific weights λv balance the different roles and importance of individual views.
  • Different anchor points are generated for different views, and the variables are optimized alternately.

B. Fix λv, Z, Update F

The multi-view procedure iteratively updates the graph-related variables and view weights, then applies K-means to matrix U to obtain the final partition. MSGL is reported to retain SGL’s explicit graph structure, linear complexity, out-of-sample extension, and convergence guarantee.

  • Properties: MSGL inherits SGL’s explicit graph structure, linear complexity, out-of-sample extension, and convergence guarantee.
  • Algorithm: The multi-view algorithm takes data matrices, anchor matrices, the cluster number, and parameters α, β, and γ as input, and outputs k clusters.
  • Optimization: MSGL iteratively updates Z, F, and λv until convergence, using Eq. (17), Eq. (11), and Eq. (20), respectively.The algorithm initializes F randomly and λv as 1/c before repeating these updates.
  • Optimization: K-means is run on matrix U to achieve the final partition.

A. Data Sets

The single-view evaluation uses nine data sets spanning image, text, evolutionary, and forest-cover data, with three data sets also examined for out-of-sample clustering. SGL is compared with five scalable methods and generally achieves stronger clustering performance and favorable runtime, including on RCV1-4.

  • Data Sets: Nine data sets cover image, text, evolutionary, and forest-cover data; MNIST, CoverType, and Pokerhand are evaluated for out-of-sample clustering.
  • Compared Methods: Five representative scalable clustering methods are selected for comparison: ALRR, KMM, ESSC, FNC, and SSCOMP.
  • Evaluation: Performance is measured with ACC, NMI, and Purity, and SGL is reported to outperform other state-of-the-art techniques in most cases.
  • Clustering Results: SGL improves KMM by 12.57% in ACC, 15.06% in NMI, and 14.49% in Purity on average.
  • Clustering Results: SGL improves ESSC by 16.66% in ACC, 16.19% in NMI, and 12.17% in Purity on average.
  • Runtime Results: ESSC takes 4078 seconds on RCV1-4, whereas SGL takes 98.86 seconds.

D. Parameter Analysis

Parameter analysis examines anchor selection, anchor number, initialization, and α/β sensitivity, alongside out-of-sample and multi-view experiments. Results indicate that performance is stable across broad α and β ranges, while anchor choice and neighbor count affect outcomes.

  • Anchor Selection: The method uses anchor points selected by K-means or FFS, with anchor number m treated as a model parameter.The dictionary A consists of anchor points; K-means and FFS are discussed as selection strategies.
  • Anchor Number and Initialization: Anchor number and initialization affect clustering performance, but good performance does not require too many anchors.Experiments vary anchors over [40, · · ·, 120] for ORL and [10, · · ·, 90] for TR45.
  • Anchor Selection: K-means-based anchors outperform FFS-based anchors on TR45 and ORL.The authors attribute this to the anchors being close to a few cluster centroids, whereas FFS is suited to anchors near a union of subspaces.
  • Parameter Sensitivity: Clustering performance remains very stable across the tested ranges of α and β, so α can be fixed while β is tuned.β ranges from 0.0001 to 10; α ranges from 0.001 to 50 on TR45 and 0.1 to 50 on ORL.
  • Out-of-Sample Experiment: The out-of-sample experiment evaluates MNIST, CoverType, and Pokerhand using randomly selected in-sample data and kNN-based testing.The setup uses 1000 in-sample points for CoverType and Pokerhand, 2000 for MNIST, and applies 3NN and 1NN to anchor points and the input data.
  • Out-of-Sample Results: The method surpasses SLSR accuracy by about 10% on CoverType and Pokerhand, while achieving comparable NMI and Purity.The results suggest that the selected anchor points represent the raw-data structure, and that kNN neighbor count strongly influences final performance.
  • Efficiency: The approach finishes 1M samples in less than 1 second and is at least 200 times faster than SLSR.It also runs faster than conventional kNN because it uses fewer points.
  • Multi-View Experiment: The multi-view evaluation compares MSGL with four state-of-the-art methods on Caltech-7, NUS, and Citeseer.The compared methods include AMGL, MLRSSC, MSC IAS, and LMVSC; parameter selection uses grid search, with γ searched from [−1, −2, −3, −4, −5].

B. Results

Across Caltech-7, Citeseer, and NUS, MSGL generally outperforms competing methods while substantially reducing runtime. It preserves clustering performance, converges quickly, and performs particularly strongly against LMVSC on accuracy and Purity.

  • Clustering performance: MSGL outperforms other methods in most clustering-performance cases across Caltech-7, Citeseer, and NUS.The comparison includes the three datasets reported in Tables VI–VIII.
  • Clustering performance: MSGL constantly outperforms LMVSC on accuracy and Purity, while achieving comparable or better NMI.LMVSC is identified as the closest competitor in the reported multi-view experiments.
  • Runtime: 10 minutes versus about 12 hours: MSGL completes the NUS experiment far faster than MSC IAS.Both MSGL and LMVSC have linear time complexity, but LMVSC is faster because it is iteration-free.
  • Runtime: MSGL is usually faster than baseline methods except LMVSC, whose one-pass design gives it a runtime advantage.LMVSC does not model graph structure or distinguish views, whereas MSGL does.
  • Convergence: MSGL converges within 10 iterations on all three real-world datasets.The objective value behavior in Fig. 5 supports the algorithm’s convergence and efficiency.
  • Overall outcome: The framework learns explicit cluster structure in linear complexity without sacrificing clustering performance.The conclusion links this outcome to the anchor, bipartite-graph, and spectral-graph design.
Loading 2102.07943v1…