A Simple and Strongly-Local Flow-Based Method for Cut Improvement
Title | A Simple and Strongly-Local Flow-Based Method for Cut Improvement |
Publication Type | Conference Paper |
Year of Publication | 2016 |
Authors | Veldt, N., Gleich D., & Mahoney M. |
Published in | Proceedings 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. |
URL | http://www.stat.berkeley.edu/~mmahoney/pubs/veldt16-icml16.pdf |
ICSI Research Group | Big Data |