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

TitleA Simple and Strongly-Local Flow-Based Method for Cut Improvement
Publication TypeConference Paper
Year of Publication2016
AuthorsVeldt, N., Gleich D., & Mahoney M. W.
Published inProceedings of the 33rd ICML Conference

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 Simple Local, 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 `1norm penalty term. As a flowbased method, our algorithm exhibits several advantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of Simple Local by solving problems on a 467 million edge graph based on an MRI scan.


We’d like to acknowledge and thank several funding agencies for supporting our work. Gleich was supported by NSF awards IIS-1546488, Center for Science of Information STC, CCF-093937, CAREER CCF-1149756, and DARPA SIMPLEX. Veldt was supported by NSF award IIS-1546488. Mahoney would like to acknowledge the Army Research Office, the Defense Advanced Research Projects Agency, and the Department of Energy for providing partial support for this work.

ICSI Research Group

Big Data