Community Detection Using Total Variation and Surface Tension

Thursday, September 17, 2020 - 12:30pm - 1:15pm
Zach Boyd (University of North Carolina, Chapel Hill)
In the last few years, several papers have leveraged a connection between graph cuts and total variation to derive nonlinear relaxations of combinatorially hard problems, which yield algorithms that have proved to be effective, scalable, and theoretically tractable. In particular, Hu et al. showed that the modularity maximization problem that is the basis for the most popular community detection algorithms and much of the accompanying theory can be expressed in this terms of graph cuts and then approximately solved using total-variation-based techniques. I will present two additions to this field.

First, I will explore the modularity optimization problem in depth, deriving other cut-based relaxations that make the nature of the problem non-convexity easier to understand. In particular, I am able to show that no convex relaxation exists satisfying certain conditions. I then present a non-convex Ginzbug-Landau relaxation that can incorporate supervision and which is efficiently solved by an MBO scheme. I show Gamma-Convergence and how to estimate some of the algorithmic parameters and show that this approach is particularly effective for geometric graphs such as those arising in hyperspectral image segmentation.

Second, I will extend the cut perspective to more sophisticated stochastic block models. In this case, rather than total variation, it is more effective to use ides from surface tension dynamics from crystal growth applications. I will explain this new analogy, give a Gamma convergence result, and derive novel and efficient block model fitting algorithm that use ideas from surface tension in the graph context. I discuss the particular challenges of this multi-scale and non-convex problem, then describe practical innovations to navigate these issues. A few examples will then illustrate the comparative advantages of this approach in various settings.

This is joint work with Andrea L. Bertozzi, Xue-Cheng Tai, Mason Porter, and Egil Bae.