Metric-constrained optimization for graph clustering algorithms

Nate Veldt, David Gleich, Anthony Wirth, James Saunderson

Research output: Contribution to journalArticleResearchpeer-review


We outline a new approach for solving linear programming relaxations of NP-hard graph clustering problems that enforce triangle inequality constraints on output variables. Extensive previous research has shown that solutions to these relaxations can be used to obtain good approximation algorithms for clustering objectives. However, these are rarely solved in practice due to their high memory requirements. We first prove that the linear programming relaxation of the correlation clustering objective is equivalent to a special case of a well-known problem in machine learning called metric nearness. We then develop a general solver for metric-constrained linear and quadratic programs by generalizing and improving a simple projection algorithm, originally developed for metric nearness. We give several novel approximation guarantees for using our approach to find lower bounds for challenging graph clustering tasks such as sparsest cut, maximum modularity, and correlation clustering. We demonstrate the power of our framework by solving relaxations of these problems involving up to $10^7$ variables and $10^{11}$ constraints.
Original languageEnglish
Pages (from-to)333-355
Number of pages23
JournalSIAM Journal on Mathematics of Data Science
Issue number2
Publication statusPublished - 2019

Cite this