# An Optimization Approach to Locally-Biased Graph Algorithms

@article{Fountoulakis2017AnOA, title={An Optimization Approach to Locally-Biased Graph Algorithms}, author={Kimon Fountoulakis and David F. Gleich and Michael W. Mahoney}, journal={Proc. IEEE}, year={2017}, volume={105}, pages={256-272} }

Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm; but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it… Expand

#### Figures, Tables, and Topics from this paper

#### 15 Citations

A Short Introduction to Local Graph Clustering Methods and Software

- Computer Science
- ArXiv
- 2018

A brief introduction to local graph clustering is provided, some representative examples of the perspective are provided, and the software named Local Graph Clustering (LGC) is introduced. Expand

Statistical guarantees for local graph clustering

- Computer Science, Mathematics
- AISTATS
- 2020

It is shown that l1-regularized PageRank and approximate personalized PageRank (APPR), another very popular method for local graph clustering, are equivalent in the sense that one can lower and upper bound the output of one with theoutput of the other. Expand

Learning Resolution Parameters for Graph Clustering

- Computer Science
- WWW
- 2019

This work views its framework as a type of single-shot hyperparameter tuning, as it is able to learn a good resolution parameter with just a single example, and can be applied to learn resolution parameters for both local and global graph clustering objectives. Expand

Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance

- Computer Science, Mathematics
- ArXiv
- 2020

A unifying fractional programming optimization framework is presented that permits us to distill out in a simple way the crucial components of all these cluster improvement algorithms, and makes apparent similarities and differences between related methods. Expand

Sublinear Algorithms for Local Graph Centrality Estimation

- Mathematics, Computer Science
- 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
- 2018

These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node. Expand

Learning by Unsupervised Nonlinear Diffusion

- Computer Science, Mathematics
- J. Mach. Learn. Res.
- 2019

A novel clustering algorithm that combines graph-based diffusion geometry with techniques based on density and mode estimation is proposed and analyzed, demonstrating the theoretical and empirical advantages over both spectral clustering and density-based clustering techniques. Expand

Compressive Sensing for Cut Improvement and Local Clustering

- Computer Science, Mathematics
- SIAM J. Math. Data Sci.
- 2020

This work shows how one can phrase the cut improvement problem for graphs as a sparse recovery problem, whence one can use algorithms originally developed for use in compressive sensing (such as SubspacePursuit or CoSaMP) to solve it and proposes new methods for local clustering and semi-supervised clustering. Expand

GraphRAD : A Graph-based Risky Account Detection System

- 2018

Given the linked account graph with tens of millions of vertices, and a list of confirmed risky accounts, how can we quickly find a short list of potentially risky accounts for further human expert… Expand

Training Recommender Systems at Scale: Communication-Efficient Model and Data Parallelism

- Computer Science, Mathematics
- KDD
- 2021

A compression framework called Dynamic Communication Thresholding (DCT) is proposed for communication-efficient hybrid training of large recommendation models and improves end-to-end training time for a state-of-the-art industrial recommender model by 37%, without any loss in performance. Expand

Connected Population Synthesis for Transportation Simulation

- SSRN Electronic Journal
- 2019

Agent-based modeling in transportation problems requires detailed information on each of the agents that represent the population in the region of a study. To extend the agent-based transportation… Expand

#### References

SHOWING 1-10 OF 84 REFERENCES

Exploiting Optimization for Local Graph Clustering

- Mathematics
- 2016

Local graph clustering methods aim to identify well-connected clusters around a given "seed set" of reference nodes. The main focus of prior theoretical work has been on worst-case running time… Expand

A Local Algorithm for Finding Well-Connected Clusters

- Computer Science, Mathematics
- ICML
- 2013

This work develops a method with better theoretical guarantee compared to all previous work, both in terms of the clustering accuracy and the conductance of the output set, and outperforms prior work when the cluster is well-connected. Expand

Flow-Based Algorithms for Local Graph Clustering

- Computer Science, Mathematics
- SODA
- 2014

This work shows how to use LocalImprove to obtain a constant approximation O(OPT) as long as CONN/OPT = Omega(1), the first flow-based algorithm and shows that spectral methods are not the only viable approach to the construction of local graph partitioning algorithm and open door to the study of algorithms with even better approximation and locality guarantees. Expand

A local spectral method for graphs: with applications to improving graph partitions and exploring data graphs locally

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2012

This paper introduces a locally-biased analogue of the second eigenvector of the Laplacian matrix, and demonstrates its usefulness at highlighting local properties of data graphs in a semi-supervised manner and shows how it can applied to finding locally- biased sparse cuts around an input vertex seed set in social and information networks. Expand

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

- Mathematics, Computer Science
- ICML
- 2016

This work introduces and analyzes a new method for locally-biased graph-based learning called SimpleLocal, which finds good conductance cuts near a set of seed vertices and achieves localization through an implicit L1-norm penalty term. Expand

A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning

- Computer Science, Mathematics
- SIAM J. Comput.
- 2013

This work presents a local clustering algorithm, a useful primitive for handling massive graphs, such as social networks and web-graphs, that finds a good cluster---a subset of vertices whose internal connections are significantly richer than its external connections---near a given vertex. Expand

Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms

- Mathematics, Computer Science
- KDD
- 2015

This work studies robustness with respect to the details of graph constructions, errors in node labeling, degree variability, and a variety of other real-world heterogeneities, studying these methods through a precise relationship with mincut problems. Expand

Empirical comparison of algorithms for network community detection

- Computer Science, Physics
- WWW '10
- 2010

Considering community quality as a function of its size provides a much finer lens with which to examine community detection algorithms, since objective functions and approximation algorithms often have non-obvious size-dependent behavior. Expand

Finding sparse cuts locally using evolving sets

- Mathematics, Computer Science
- STOC '09
- 2009

A randomized local partitioning algorithm is introduced that finds a sparse cut by simulating the volume-biased evolving set process, which is a Markov chain on sets of vertices and the expected value of the work/volume ratio is polylognoparen(φ-1/2). Expand

Anti-differentiating approximation algorithms: A case study with min-cuts, spectral, and flow

- Computer Science
- ICML
- 2014

A case study of approximation algorithms for finding locally-biased partitions in data graphs, demonstrating connections between min-cut objectives, a personalized version of the popular PageRank vector, and the highly effective "push" procedure for computing an approximation to personalized PageRank. Expand