# Online Sparsification of Bipartite-Like Clusters in Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 25 references that are in the map.
- First posted on arXiv 7 Aug 2025.

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

- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [Lead-lag detection and network clustering for multivariate time series with an application to the US equity market](https://mlsanity.com/paper/2201.08283/) (2022)
- [Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs](https://mlsanity.com/paper/1611.00755/) (2016)
- [Distributed Graph Clustering and Sparsification](https://mlsanity.com/paper/1711.01262/) (2017)
- [An SDP-Based Algorithm for Linear-Sized Spectral Sparsification](https://mlsanity.com/paper/1702.08415/) (2017)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)

## Abstract (arXiv)

Graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.