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

arXiv: https://arxiv.org/abs/2305.07386 · HTML: https://mlsanity.com/paper/2305.07386/

## 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 (most cited first, 20 of 20)

- [Large-scale Multi-view Subspace Clustering in Linear Time](https://mlsanity.com/paper/1911.09290/) (2019)
- [Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit](https://mlsanity.com/paper/1507.01238/) (2015)
- [Ultra-Scalable Spectral Clustering and Ensemble Clustering](https://mlsanity.com/paper/1903.01057/) (2019)
- [Robust and Efficient Subspace Segmentation via Least Squares Regression](https://mlsanity.com/paper/1404.6736/) (2014)
- [Subspace Clustering by Block Diagonal Representation](https://mlsanity.com/paper/1805.09243/) (2018)
- [Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view](https://mlsanity.com/paper/2102.07943/) (2021)
- [Effective and Efficient Graph Learning for Multi-view Clustering](https://mlsanity.com/paper/2108.06734/) (2021)
- [Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicity](https://mlsanity.com/paper/2203.11572/) (2022)
- [Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework](https://mlsanity.com/paper/1610.05211/) (2016)
- [Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation](https://mlsanity.com/paper/2004.14705/) (2020)
- [Toward Multidiversified Ensemble Clustering of High-Dimensional Data: From Subspaces to Metrics and Beyond](https://mlsanity.com/paper/1710.03113/) (2017)
- [Multi-view Graph Learning by Joint Modeling of Consistency and Inconsistency](https://mlsanity.com/paper/2008.10208/) (2020)
- [Enhanced Ensemble Clustering via Fast Propagation of Cluster-wise Similarities](https://mlsanity.com/paper/1810.12544/) (2018)
- [A generalized power iteration method for solving quadratic problem on the Stiefel manifold](https://mlsanity.com/paper/1701.00381/) (2017)
- [Large-Scale Subspace Clustering via k-Factorization](https://mlsanity.com/paper/2012.04345/) (2020)
- [Strongly Augmented Contrastive Clustering](https://mlsanity.com/paper/2206.00380/) (2022)
- [Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph Learning](https://mlsanity.com/paper/2209.04187/) (2022)
- [Structure Learning with Similarity Preserving](https://mlsanity.com/paper/1912.01197/) (2019)
- [Refining a k-nearest neighbor graph for a computationally efficient spectral clustering](https://mlsanity.com/paper/2302.11296/) (2023)
- [Adaptive Graph Convolutional Subspace Clustering](https://mlsanity.com/paper/2305.03414/) (2023)

## 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.