(For a full list see below or go to Google Scholar

Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clustering, community detection, nodes ranking and feature inference. Prior work on local graph clustering mostly falls into two categories with numerical and combinatorial roots respectively. In this work, we draw inspiration from both fields and propose a family of convex optimization formulations based on the idea of diffusion with p-norm network flow for p in (1,infinity). In the context of local clustering, we characterize the optimal solutions for these optimization problems and show their usefulness in finding low conductance cuts around input seed set. In particular, we achieve quadratic approximation of conductance in the case of p=2 similar to the Cheeger-type bounds of spectral methods, constant factor approximation when p goes to infinity similar to max-flow based methods, and a smooth transition for general p values in between. Thus, our optimization formulation can be viewed as bridging the numerical and combinatorial approaches, and we can achieve the best of both worlds in terms of speed and noise robustness. We show that the proposed problem can be solved in strongly local running time for p greater or equal to 2 and conduct empirical evaluations on both synthetic and real-world graphs to illustrate our approach compares favorably with existing methods.

*K. Fountoulakis, D. Wang, S. Yang*

**International Conference on Machine Learning (ICML) 2020**

** **

Clustering points in a vector space or nodes in a graph is a ubiquitous primitive in statistical data analysis, and it is commonly used for exploratory data analysis. In practice, it is often of interest to refine or improve a given cluster that has been obtained by some other method. In this survey, we focus on principled algorithms for this cluster improvement problem. Many such cluster improvement algorithms are flow-based methods, by which we mean that operationally they require the solution of a sequence of maximum flow problems on a (typically implicitly) modified data graph. These cluster improvement algorithms are powerful, both in theory and in practice, but they have not been widely adopted for problems such as community detection, local graph clustering, semi-supervised learning, etc. Possible reasons for this are the steep learning curve for these algorithms; the lack of efficient and easy to use software; and the lack of detailed numerical experiments on real-world data that demonstrate their usefulness. Our objective here is to address these issues. To do so, we guide the reader through the whole process of understanding how to implement and apply these powerful algorithms. We present a unifying fractional programming optimization framework that permits us to distill out in a simple way the crucial components of all these algorithms. It also makes apparent similarities and differences between related methods. Viewing these cluster improvement algorithms via a fractional programming framework suggests directions for future algorithm development. Finally, we develop efficient implementations of these algorithms in our LocalGraphClustering python package, and we perform extensive numerical experiments to demonstrate the performance of these methods on social networks and image-based data graphs.

*K. Fountoulakis, M. Liu, D. F. Gleich, M. W. Mahoney*

** **

Â

Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks

*S. Yang, P. Senapati, D. Wang, C. T. Bauch, K. Fountoulakis *

arXiv:2006.06939

p-Norm Flow Diffusion for Local Graph Clustering

*K. Fountoulakis, D. Wang, S. Yang *

International Conference on Machine Learning (ICML) 2020

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

*K. Fountoulakis, M. Liu, D. F. Gleich, M. W. Mahoney *

arXiv:2004.09608

Statistical Guarantees for Local Graph Clustering

*W. Ha, K. Fountoulakis, M. W. Mahoney *

International Conference on Artificial Intelligence and Statistics (AISTATS) 2020

Parallel and Communication Avoiding Least Angle Regression

*S. Das, J. Demmel, K. Fountoulakis, L. Grigori, M. W. Mahoney, S. Yang *

arXiv:1905.11340

Locality And Structure Aware Graph Node Embedding

*E. Faerman, F. Borutta, K. Fountoulakis, M. W. Mahoney *

International Conference on Web Intelligence 2018 (Best student paper award)

A Flexible Coordinate Descent Method

*K. Fountoulakis, R. Tappenden *

Computational Optimization and Applications

Avoiding Synchronization in First-Order Methods for Sparse Convex Optimization

*A. Devarakonda, K. Fountoulakis, J. Demmel, M. Mahoney *

International Parallel and Distributed Processing Symposium (IPDPS) 2018

Variational Perspective on Local Graph Clustering

*K. Fountoulakis, F. Roosta-Khorasani, J. Shun, X. Cheng, M. Mahoney *

Mathematical Programming

Capacity Releasing Diffusion for Speed and Locality

*D. Wang, K. Fountoulakis, M. Henzinger, M. Mahoney, S. Rao *

International Conference on Machine Learning (ICML) 2017

Avoiding communication in primal and dual block coordinate descent methods

*A. Devarakonda, K. Fountoulakis, J. Demmel, M. Mahoney *

SIAM Journal on Scientific Computing (SISC)

A Randomized Rounding Algorithm for Sparse PCA

*K. Fountoulakis, A. Kundu, E. M. Kontopoulou, P. Drineas *

ACM Transactions on Knowledge Discovery from Data

An Optimization Approach to Locally-Biased Graph Algorithms

*K. Fountoulakis, D. Gleich, M. Mahoney *

Proceedings of the IEEE

Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems

*K. Fountoulakis, J. Gondzio *

Computational Optimization and Applications

A Second-Order Method for Strongly-Convex L1-Regularization Problems

*K. Fountoulakis, J. Gondzio *

Mathematical Programming

Parallel Local Graph Clustering

*J. Shun, F. Roosta-Khorasani, K. Fountoulakis, M. Mahoney *

Proceedings of the VLDB Endowment (VLDB) 2016

A Preconditioner for a Primal-dual Newton Conjugate Gradients Method for Compressed Sensing Problems

*I. Dassios, K. Fountoulakis, J. Gondzio *

SIAM Journal on Scientific Computing (SISC)

Matrix-free interior point method for compressed sensing problems

*K. Fountoulakis, J. Gondzio, P. Zhlobich *

Mathematical Programming Computation

Higher-Order Methods for Large-Scale Optimization

*K. Fountoulakis *

Kimon Fountoulakisâ€™ PhD Thesis