# p-Norm Flow Diffusion for Local Graph Clustering

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

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

- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Finding Bipartite Components in Hypergraphs](https://mlsanity.com/paper/2205.02771/) (2022)
- [Local Clustering on Complex Graphs and Complex Hypergraphs](https://mlsanity.com/paper/2412.03008/) (2024)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (1)](https://mlsanity.com/paper/2304.03170/) (2023)
- [Scalable and Effective Conductance-based Graph Clustering](https://mlsanity.com/paper/2211.12511/) (2022)
- [Multi-class Graph Clustering via Approximated Effective p-Resistance](https://mlsanity.com/paper/2306.08617/) (2023)
- [Local Graph Clustering with Noisy Labels](https://mlsanity.com/paper/2310.08031/) (2023)
- [Adaptive Local Clustering over Attributed Graphs](https://mlsanity.com/paper/2503.20488/) (2025)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)
- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)

## Abstract (arXiv)

Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clustering, community detection, nodes ranking and feature inference. Prior work on local graph clustering mostly falls into two categories with numerical and combinatorial roots respectively. In this work, we draw inspiration from both fields and propose a family of convex optimization formulations based on the idea of diffusion with p-norm network flow for p∈ (1,∞). In the context of local clustering, we characterize the optimal solutions for these optimization problems and show their usefulness in finding low conductance cuts around input seed set. In particular, we achieve quadratic approximation of conductance in the case of p=2 similar to the Cheeger-type bounds of spectral methods, constant factor approximation when prightarrow∞ similar to max-flow based methods, and a smooth transition for general p values in between. Thus, our optimization formulation can be viewed as bridging the numerical and combinatorial approaches, and we can achieve the best of both worlds in terms of speed and noise robustness. We show that the proposed problem can be solved in strongly local running time for p≥ 2 and conduct empirical evaluations on both synthetic and real-world graphs to illustrate our approach compares favorably with existing methods.