Online Sparsification of Bipartite-Like Clusters in Graphs

Joyentanuj Das, Suranjan De, He Sun
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:12490-12508, 2025.

Abstract

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, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-das25a, title = {Online Sparsification of Bipartite-Like Clusters in Graphs}, author = {Das, Joyentanuj and De, Suranjan and Sun, He}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {12490--12508}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/das25a/das25a.pdf}, url = {https://proceedings.mlr.press/v267/das25a.html}, abstract = {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, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online 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.} }
Endnote
%0 Conference Paper %T Online Sparsification of Bipartite-Like Clusters in Graphs %A Joyentanuj Das %A Suranjan De %A He Sun %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-das25a %I PMLR %P 12490--12508 %U https://proceedings.mlr.press/v267/das25a.html %V 267 %X 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, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online 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.
APA
Das, J., De, S. & Sun, H.. (2025). Online Sparsification of Bipartite-Like Clusters in Graphs. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:12490-12508 Available from https://proceedings.mlr.press/v267/das25a.html.

Related Material