# Effective and Scalable Clustering on Massive Attributed Graphs

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

## Key facts

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

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [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)
- [Clustering attributed graphs: models, measures and methods](https://mlsanity.com/paper/1501.01676/) (2015)
- [Community detection in networks: Structural communities versus ground truth](https://mlsanity.com/paper/1406.0146/) (2014)
- [Efficient Estimation of Heat Kernel PageRank for Local Clustering](https://mlsanity.com/paper/1904.02707/) (2019)

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

- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)
- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation](https://mlsanity.com/paper/2408.05459/) (2024)
- [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 Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs](https://mlsanity.com/paper/2406.13369/) (2024)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [Attention-based graph neural networks: a survey](https://mlsanity.com/paper/2605.08679/) (2026)

## Abstract (arXiv)

Given a graph G where each node is associated with a set of attributes, and a parameter k specifying the number of output clusters, k-attributed graph clustering (k-AGC) groups nodes in G into k disjoint clusters, such that nodes within the same cluster share similar topological and attribute characteristics, while those in different clusters are dissimilar. This problem is challenging on massive graphs, e.g., with millions of nodes and billions of edges. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality. In this paper, we propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. The main contributions of ACMin are twofold: (i) a novel formulation of the k-AGC problem based on an attributed multi-hop conductance quality measure custom-made for this problem setting, which effectively captures cluster coherence in terms of both topological proximities and attribute similarities, and (ii) a linear-time optimization solver that obtains high-quality clusters iteratively, based on efficient matrix operations such as orthogonal iterations, an alternative optimization approach, as well as an initialization technique that significantly speeds up the convergence of ACMin in practice. Extensive experiments, comparing 11 competitors on 6 real datasets, demonstrate that ACMin consistently outperforms all competitors in terms of result quality measured against ground-truth labels, while being up to orders of magnitude faster. In particular, on the Microsoft Academic Knowledge Graph dataset with 265.2 million edges and 1.1 billion attribute values, ACMin outputs high-quality results for 5-AGC within 1.68 hours using a single CPU core, while none of the 11 competitors finish within 3 days.