# Flow-Based Local Graph Clustering with Better Seed Set Inclusion

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2018.

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

- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [Multi-class Graph Clustering via Approximated Effective p-Resistance](https://mlsanity.com/paper/2306.08617/) (2023)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)
- [Random Walk on Multiple Networks](https://mlsanity.com/paper/2307.01637/) (2023)

## Abstract (arXiv)

Flow-based methods for local graph clustering have received significant recent attention for their theoretical cut improvement and runtime guarantees. In this work we present two improvements for using flow-based methods in real-world semi-supervised clustering problems. Our first contribution is a generalized objective function that allows practitioners to place strict and soft penalties on excluding specific seed nodes from the output set. This feature allows us to avoid the tendency, often exhibited by previous flow-based methods, to contract a large seed set into a small set of nodes that does not contain all or even most of the seed nodes. Our second contribution is a fast algorithm for minimizing our generalized objective function, based on a variant of the push-relabel algorithm for computing preflows. We make our approach very fast in practice by implementing a global relabeling heuristic and employing a warm-start procedure to quickly solve related cut problems. In practice our algorithm is faster than previous related flow-based methods, and is also more robust in detecting ground truth target regions in a graph, thanks to its ability to better incorporate semi-supervised information about target clusters.