We present a new approach for solving a class of convex relaxations for graph clustering objectives which involve triangle-inequality constraints. Many approximation algorithms for graph clustering rely on solving these metric-constrained optimization problems, but these are rarely implemented in practice due to extremely high memory requirements. We present a memory-efficient approach for solving these problems based on iterative projections methods. In practice we use our approach to address relaxations involving up to 2.9 trillion metric constraints.
Optimization on graphs is a powerful tool for understanding networks, for example we can use it to plan flows of good or data, or to understand network clusters. Second order methods are a powerful tool in optimization, but they require solving linear equations, making them slow. However, second order methods for graph optimization lead to structured linear equations, and we can use this structure to solve the linear equations much faster. We will see how to solve such linear equations, known as Laplacians, quickly both in theory and in practice.
Large-scale graphs consist of interesting small or medium-scale clusters. Existing approaches require touching the whole graph to find large clusters and they often fail to locate small and medium-scale clusters. In this talk we will analyze the performance of a local graph clustering approach, i.e., the l1-regularized PageRank model, on large-scale graphs with many small or medium-scale clusters. We will demonstrate average-case results for the l1-regularized PageRank model and we will show that proximal gradient descent finds the optimal number of non-zeros without touching the whole graph.