# Adaptive Local Clustering over Attributed Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 97 references that are in the map.
- First posted on arXiv 26 Mar 2025.

## Builds on (most cited first, 30 of 31)

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [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)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Attributed Social Network Embedding](https://mlsanity.com/paper/1705.04969/) (2017)
- [Graph Communal Contrastive Learning](https://mlsanity.com/paper/2110.14863/) (2021)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [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)
- [Local Graph Clustering with Network Lasso](https://mlsanity.com/paper/2004.12199/) (2020)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Capacity Releasing Diffusion for Speed and Locality](https://mlsanity.com/paper/1706.05826/) (2017)
- [Efficient Estimation of Heat Kernel PageRank for Local Clustering](https://mlsanity.com/paper/1904.02707/) (2019)
- [Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks](https://mlsanity.com/paper/1403.3795/) (2014)
- [Approximate Closest Community Search in Networks](https://mlsanity.com/paper/1505.05956/) (2015)
- [Attribute Truss Community Search](https://mlsanity.com/paper/1609.00090/) (2016)
- [Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical Guarantees](https://mlsanity.com/paper/2301.13187/) (2023)
- [Efficient and Effective Similarity Search over Bipartite Graphs](https://mlsanity.com/paper/2312.06724/) (2023)
- [Panther: Fast Top-k Similarity Search in Large Networks](https://mlsanity.com/paper/1504.02577/) (2015)
- [Cross-Space Adaptive Filter: Integrating Graph Topology and Node Attributes for Alleviating the Over-smoothing Problem](https://mlsanity.com/paper/2401.14876/) (2024)
- [A Short Introduction to Local Graph Clustering Methods and Software](https://mlsanity.com/paper/1810.07324/) (2018)
- [Bidirectional PageRank Estimation: From Average-Case to Worst-Case](https://mlsanity.com/paper/1507.08705/) (2015)
- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [Local Partition in Rich Graphs](https://mlsanity.com/paper/1803.05084/) (2018)

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

- [Cross-Contrastive Clustering for Multimodal Attributed Graphs with Dual Graph Filtering](https://mlsanity.com/paper/2511.20030/) (2025)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)

## Abstract (arXiv)

Given a graph G and a seed node vs, the objective of local graph clustering (LGC) is to identify a subgraph Cs ∈ G (a.k.a. local cluster) surrounding vs in time roughly linear with the size of Cs. This approach yields personalized clusters without needing to access the entire graph, which makes it highly suitable for numerous applications involving large graphs. However, most existing solutions merely rely on the topological connectivity between nodes in G, rendering them vulnerable to missing or noisy links that are commonly present in real-world graphs. To address this issue, this paper resorts to leveraging the complementary nature of graph topology and node attributes to enhance local clustering quality. To effectively exploit the attribute information, we first formulate the LGC as an estimation of the bidirectional diffusion distribution (BDD), which is specialized for capturing the multi-hop affinity between nodes in the presence of attributes. Furthermore, we propose LACA, an efficient and effective approach for LGC that achieves superb empirical performance on multiple real datasets while maintaining strong locality. The core components of LACA include (i) a fast and theoretically-grounded preprocessing technique for node attributes, (ii) an adaptive algorithm for diffusing any vectors over G with rigorous theoretical guarantees and expedited convergence, and (iii) an effective three-step scheme for BDD approximation. Extensive experiments, comparing 17 competitors on 8 real datasets, show that LACA outperforms all competitors in terms of result quality measured against ground truth local clusters, while also being up to orders of magnitude faster. The code is available at https://github.com/HaoranZ99/alac.