2016/05/27 by Nate Veldt, David F. Gleich, Veldt, Nate +3
Computer Science · Engineering · #Advanced Graph Neural Networks #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Data Classification #Social and Information Networks (cs.SI) #Sparse and Compressive Sensing Techniques #cs.DS #cs.SI
paper · pdf · doi:10.48550/arxiv.1605.08490
arxiv created 2016/05/27 · openalex publication_date 2016/05/27 · arxiv updated 2016/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.