# Effective Clustering on Large Attributed Bipartite Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 92 references that are in the map.
- First posted on arXiv 20 May 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [Adaptive Graph Encoder for Attributed Graph Embedding](https://mlsanity.com/paper/2007.01594/) (2020)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [Dink-Net: Neural Clustering on Large Graphs](https://mlsanity.com/paper/2305.18405/) (2023)
- [Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering](https://mlsanity.com/paper/2107.08562/) (2021)
- [Personalized Showcases: Generating Multi-Modal Explanations for Recommendations](https://mlsanity.com/paper/2207.00422/) (2022)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [Community detection in node-attributed social networks: a survey](https://mlsanity.com/paper/1912.09816/) (2019)
- [PANE: scalable and effective attributed network embedding](https://mlsanity.com/paper/2009.00826/) (2020)
- [Clustering attributed graphs: models, measures and methods](https://mlsanity.com/paper/1501.01676/) (2015)
- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [EnsemFDet: An Ensemble Approach to Fraud Detection based on Bipartite Graph](https://mlsanity.com/paper/1912.11113/) (2019)
- [Efficient and Effective Similarity Search over Bipartite Graphs](https://mlsanity.com/paper/2312.06724/) (2023)
- [Effective Community Search on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2302.14498/) (2023)

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

- [GORAG: Graph-based Online Retrieval Augmented Generation for Dynamic Few-shot Social Media Text Classification](https://mlsanity.com/paper/2501.02844/) (2025)
- [Revisiting Dynamic Graph Clustering via Matrix Factorization](https://mlsanity.com/paper/2502.06117/) (2025)
- [Spectral Subspace Clustering for Attributed Graphs](https://mlsanity.com/paper/2411.11074/) (2024)
- [Leveraging Large Language Models for Effective Label-free Node Classification in Text-Attributed Graphs](https://mlsanity.com/paper/2412.11983/) (2024)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)
- [Node Role-Guided LLMs for Dynamic Graph Clustering](https://mlsanity.com/paper/2603.13799/) (2026)
- [Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems](https://mlsanity.com/paper/2604.18351/) (2026)

## Abstract (arXiv)

Attributed bipartite graphs (ABGs) are an expressive data model for describing the interactions between two sets of heterogeneous nodes that are associated with rich attributes, such as customer-product purchase networks and author-paper authorship graphs. Partitioning the target node set in such graphs into k disjoint clusters (referred to as k-ABGC) finds widespread use in various domains, including social network analysis, recommendation systems, information retrieval, and bioinformatics. However, the majority of existing solutions towards k-ABGC either overlook attribute information or fail to capture bipartite graph structures accurately, engendering severely compromised result quality. The severity of these issues is accentuated in real ABGs, which often encompass millions of nodes and a sheer volume of attribute data, rendering effective k-ABGC over such graphs highly challenging. In this paper, we propose TPO, an effective and efficient approach to k-ABGC that achieves superb clustering performance on multiple real datasets. TPO obtains high clustering quality through two major contributions: (i) a novel formulation and transformation of the k-ABGC problem based on multi-scale attribute affinity specialized for capturing attribute affinities between nodes with the consideration of their multi-hop connections in ABGs, and (ii) a highly efficient solver that includes a suite of carefully-crafted optimizations for sidestepping explicit affinity matrix construction and facilitating faster convergence. Extensive experiments, comparing TPO against 19 baselines over 5 real ABGs, showcase the superior clustering quality of TPO measured against ground-truth labels. Moreover, compared to the state of the arts, TPO is often more than 40x faster over both small and large ABGs.