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
Abstract

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.
 

Acknowledgment

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.
 

URLhttp://www.stat.berkeley.edu/~mmahoney/pubs/veldt16-icml16.pdf
ICSI Research Group

Big Data