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

Nate Veldt, David Gleich, Michael Mahoney
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1938-1947, 2016.

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 minimum cuts and 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 is related to other 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 advantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of SimpleLocal solving segmentation problems on a 467 million edge graph based on an MRI scan.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-veldt16, title = {A Simple and Strongly-Local Flow-Based Method for Cut Improvement}, author = {Veldt, Nate and Gleich, David and Mahoney, Michael}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1938--1947}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/veldt16.pdf}, url = {https://proceedings.mlr.press/v48/veldt16.html}, 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 minimum cuts and 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 is related to other 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 advantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of SimpleLocal solving segmentation problems on a 467 million edge graph based on an MRI scan.} }
Endnote
%0 Conference Paper %T A Simple and Strongly-Local Flow-Based Method for Cut Improvement %A Nate Veldt %A David Gleich %A Michael Mahoney %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-veldt16 %I PMLR %P 1938--1947 %U https://proceedings.mlr.press/v48/veldt16.html %V 48 %X 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 minimum cuts and 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 is related to other 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 advantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of SimpleLocal solving segmentation problems on a 467 million edge graph based on an MRI scan.
RIS
TY - CPAPER TI - A Simple and Strongly-Local Flow-Based Method for Cut Improvement AU - Nate Veldt AU - David Gleich AU - Michael Mahoney BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-veldt16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1938 EP - 1947 L1 - http://proceedings.mlr.press/v48/veldt16.pdf UR - https://proceedings.mlr.press/v48/veldt16.html AB - 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 minimum cuts and 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 is related to other 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 advantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of SimpleLocal solving segmentation problems on a 467 million edge graph based on an MRI scan. ER -
APA
Veldt, N., Gleich, D. & Mahoney, M.. (2016). A Simple and Strongly-Local Flow-Based Method for Cut Improvement. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1938-1947 Available from https://proceedings.mlr.press/v48/veldt16.html.

Related Material