# Local Clustering on Complex Graphs and Complex Hypergraphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 4 Dec 2024.

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

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Random Walks on Hypergraphs with Edge-Dependent Vertex Weights](https://mlsanity.com/paper/1905.08287/) (2019)
- [Efficient Algorithms for Personalized PageRank Computation: A Survey](https://mlsanity.com/paper/2403.05198/) (2024)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Hypergraph Clustering Based on PageRank](https://mlsanity.com/paper/2006.08302/) (2020)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning](https://mlsanity.com/paper/2011.07752/) (2020)
- [Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical Guarantees](https://mlsanity.com/paper/2301.13187/) (2023)
- [Fairness Rising from the Ranks: HITS and PageRank on Homophilic Networks](https://mlsanity.com/paper/2402.13787/) (2024)
- [A Simple and Strongly-Local Flow-Based Method for Cut Improvement](https://mlsanity.com/paper/1605.08490/) (2016)
- [Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://mlsanity.com/paper/2411.03331/) (2024)
- [Computing Heat Kernel Pagerank and a Local Clustering Algorithm](https://mlsanity.com/paper/1503.03155/) (2015)
- [Deterministic Near-Linear Time Minimum Cut in Weighted Graphs](https://mlsanity.com/paper/2401.05627/) (2024)
- [An Efficient and Balanced Graph Partition Algorithm for the Subgraph-Centric Programming Model on Large-scale Power-law Graphs](https://mlsanity.com/paper/2010.09007/) (2020)
- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [Revisiting Local Computation of PageRank: Simple and Optimal](https://mlsanity.com/paper/2403.12648/) (2024)
- [A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs](https://mlsanity.com/paper/2307.04139/) (2023)

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

- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [APEX2: Adaptive and Extreme Summarization for Personalized Knowledge Graphs](https://mlsanity.com/paper/2412.17336/) (2024)
- [ClimateBench-M: A Multi-Modal Climate Data Benchmark with a Simple Generative Method](https://mlsanity.com/paper/2504.07394/) (2025)
- [Thresholded Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2606.09340/) (2026)

## Abstract (arXiv)

Local/seeded clustering aims to find a compact cluster near the given starting instances. While most existing studies on graph clustering assume a discrete graph setting (i.e., unweighted, undirected graphs without self-loops), real-world graphs can be more complex. In this paper, we extend the classic non-approximating Andersen-Chung-Lang (ACL) clustering algorithm beyond discrete graphs and generalize its quadratic optimality to a wider range of complex graphs, including weighted, directed, and self-looped graphs and hypergraphs with edge-dependent vertex weights. Specifically, by leveraging PageRank, we propose two algorithms: GeneralACL for graphs and HyperACL for hypergraphs. We prove that, under two mild conditions, both algorithms can identify a quadratically optimal cluster in terms of conductance. Additionally, we provide experiments to validate our theoretical findings. Our code is available at https://github.com/iDEA-iSAIL-Lab-UIUC/HyperACL.