mlsanityData to 14 Oct 2026

One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering

arXiv 2305.07386 ↗First posted 12 May 2023cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

The bipartite graph structure has shown its promising ability in facilitating the subspace clustering and spectral clustering algorithms for large-scale datasets. To avoid the post-processing via k-means during the bipartite graph partitioning, the constrained Laplacian rank (CLR) is often utilized for constraining the number of connected components (i.e., clusters) in the bipartite graph, which, however, neglects the distribution (or normalization) of these connected components and may lead to imbalanced or even ill clusters. Despite the significant success of normalized cut (Ncut) in general graphs, it remains surprisingly an open problem how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut (OBCut) criterion with normalized constraints, and theoretically prove its equivalence to a trace maximization problem. Then we extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled in a unified objective function, and an alternating optimization algorithm is further designed to solve it in linear time. Experiments on a variety of general and large-scale datasets demonstrate the effectiveness and scalability of our approach.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 20 of its 70 references that are in the map. First posted on arXiv 12 May 2023.

Builds on

20 of 70 references.

References · 20

  1. 2019Large-scale Multi-view Subspace Clustering in Linear Timecited by 66
  2. 2015Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuitcited by 50
  3. 2019Ultra-Scalable Spectral Clustering and Ensemble Clusteringcited by 50
  4. 2014Robust and Efficient Subspace Segmentation via Least Squares Regressioncited by 47
  5. 2018Subspace Clustering by Block Diagonal Representationcited by 38
  6. 2021Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-viewcited by 30
  7. 2021Effective and Efficient Graph Learning for Multi-view Clusteringcited by 28
  8. 2022Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicitycited by 28
  9. 2016Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Frameworkcited by 26
  10. 2020Multi-View Spectral Clustering Tailored Tensor Low-Rank Representationcited by 21
  11. 2017Toward Multidiversified Ensemble Clustering of High-Dimensional Data: From Subspaces to Metrics and Beyondcited by 18
  12. 2020Multi-view Graph Learning by Joint Modeling of Consistency and Inconsistencycited by 18
8 more
  1. 2018Enhanced Ensemble Clustering via Fast Propagation of Cluster-wise Similaritiescited by 17
  2. 2017A generalized power iteration method for solving quadratic problem on the Stiefel manifoldcited by 15
  3. 2020Large-Scale Subspace Clustering via k-Factorizationcited by 14
  4. 2022Strongly Augmented Contrastive Clusteringcited by 14
  5. 2022Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph Learningcited by 10
  6. 2019Structure Learning with Similarity Preservingcited by 9
  7. 2023Refining a k-nearest neighbor graph for a computationally efficient spectral clusteringcited by 6
  8. 2023Adaptive Graph Convolutional Subspace Clusteringcited by 4

Built on by

Not cited yet.