# A Simple and Strongly-Local Flow-Based Method for Cut Improvement

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2016.

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

- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (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)
- [Scalable and Effective Conductance-based Graph Clustering](https://mlsanity.com/paper/2211.12511/) (2022)

## Abstract (arXiv)

Many graph-based learning problems can be cast as finding a good set of vertices nearby a seed set, and a powerful methodology for these problems is based on maximum flows. We introduce and analyze a new method for locally-biased graph-based learning called SimpleLocal, which finds good conductance cuts near a set of seed vertices. An important feature of our algorithm is that it is strongly-local, meaning it does not need to explore the entire graph to find cuts that are locally optimal. This method solves the same objective as existing strongly-local flow-based methods, but it enables a simple implementation. We also show how it achieves localization through an implicit L1-norm penalty term. As a flow-based method, our algorithm exhibits several ad- vantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of SimpleLocal by solving problems on a 467 million edge graph based on an MRI scan.