Abstract: Correlation clustering is a framework for partitioning signed graphs that has been studied extensively from the perspective of approximation algorithms and computational hardness results. This talk will introduce a new weighted variant of the problem called LambdaCC, which is motivated by applications to community detection. We show that LambdaCC unifies and generalizes a number of previously studied graph clustering objectives, including sparsest cut, modularity clustering, and cluster deletion. All of these objectives can be viewed as special cases of LambdaCC for a fixed value of a clustering resolution parameter lambda. By extending previous correlation clustering techniques, we obtain novel approximation guarantees and a hardness result for LambdaCC.

 

In the second part of the talk we consider practical optimization tools for graph clustering that are motivated by the LambdaCC framework. The first tool is a practical solver for the linear programming relaxation of LambdaCC based on memory-efficient projection methods. This enables efficient implementation of the best algorithms for LambdaCC and can be applied more broadly to solve a certain class of convex relaxations of other NP-hard objectives that are often used in approximation algorithms. In particular we are able to solve optimization problems with up to 3 trillion constraints. We finish by considering a novel framework for learning good clustering resolution parameters (such as the lambda in LambdaCC), when given a single example of a “good” clustering in a specific application domain.

Short Bio: Nate Veldt is a PhD student in his final year at Purdue University, where he is advised by Professor David Gleich in Purdue’s department of computer science. His research focuses on models, algorithms, and complexity results for problems in network science and data analysis. Much of his recent work is more specifically focused on algorithms for graph clustering, which includes approximation algorithms for correlation clustering, flow-based methods for local community detection, and fast solvers for convex relaxations of graph clustering objectives.