# Efficient High-Quality Clustering for Large Bipartite Graphs

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 71 references that are in the map.
- First posted on arXiv 28 Dec 2023.

## Builds on (most cited first, 10 of 10)

- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [Efficiently inferring community structure in bipartite networks](https://mlsanity.com/paper/1403.2933/) (2014)
- [Community Detection in Bipartite Networks with Stochastic Blockmodels](https://mlsanity.com/paper/2001.11818/) (2020)
- [Efficient and Effective Similarity Search over Bipartite Graphs](https://mlsanity.com/paper/2312.06724/) (2023)
- [Scalable and interpretable product recommendations via overlapping co-clustering](https://mlsanity.com/paper/1604.02071/) (2016)

## Built on by (most cited first, 11 of 11)

- [Large Language Model Meets Graph Neural Network in Knowledge Distillation](https://mlsanity.com/paper/2402.05894/) (2024)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)
- [Spectral Subspace Clustering for Attributed Graphs](https://mlsanity.com/paper/2411.11074/) (2024)
- [Bridging Academia and Industry: A Comprehensive Benchmark for Attributed Graph Clustering](https://mlsanity.com/paper/2602.08519/) (2026)
- [Effective Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs](https://mlsanity.com/paper/2406.13369/) (2024)
- [GegenNet: Spectral Convolutional Neural Networks for Link Sign Prediction in Signed Bipartite Graphs](https://mlsanity.com/paper/2508.19907/) (2025)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)
- [PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding](https://mlsanity.com/paper/2408.02705/) (2024)
- [Revisiting Graph Projections for Effective Complementary Product Recommendation](https://mlsanity.com/paper/2506.09209/) (2025)
- [Rethinking Semi-Supervised Node Classification with Self-Supervised Graph Clustering](https://mlsanity.com/paper/2511.19976/) (2025)
- [Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems](https://mlsanity.com/paper/2604.18351/) (2026)

## Abstract (arXiv)

A bipartite graph contains inter-set edges between two disjoint vertex sets, and is widely used to model real-world data, such as user-item purchase records, author-article publications, and biological interactions between drugs and proteins. k-Bipartite Graph Clustering (k-BGC) is to partition the target vertex set in a bipartite graph into k disjoint clusters. The clustering quality is important to the utility of k-BGC in various applications like social network analysis, recommendation systems, text mining, and bioinformatics, to name a few. Existing approaches to k-BGC either output clustering results with compromised quality due to inadequate exploitation of high-order information between vertices, or fail to handle sizable bipartite graphs with billions of edges. Motivated by this, this paper presents two efficient k-BGC solutions, HOPE and HOPE+, which achieve state-of-the-art performance on large-scale bipartite graphs. HOPE obtains high scalability and effectiveness through a new k-BGC problem formulation based on the novel notion of high-order perspective (HOP) vectors and an efficient technique for low-rank approximation of HOP vectors. HOPE+ further elevates the k-BGC performance to another level with a judicious problem transformation and a highly efficient two-stage optimization framework. Two variants, HOPE+ (FNEM) and HOPE+ (SNEM) are designed when either the Frobenius norm or spectral norm is applied in the transformation. Extensive experiments, comparing HOPE and HOPE+ against 13 competitors on 10 real-world datasets, exhibit that our solutions, especially HOPE+, are superior to existing methods in terms of result quality, while being up to orders of magnitude faster. On the largest dataset MAG with 1.1 billion edges, HOPE+ is able to produce clusters with the highest clustering accuracy within 31 minutes, which is unmatched by any existing solution for k-BGC.