Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
This work addresses optimization bottlenecks in machine learning for graph and hypergraph tasks, offering incremental advancements with practical gains in applications like local partitioning and semi-supervised learning.
The paper tackles the problem of quadratic decomposable submodular function minimization (QDSFM), a convex optimization challenge for learning on graphs and hypergraphs, by proposing dual strategies with linear convergence rates and demonstrating applications like hypergraph-adapted PageRank and semi-supervised learning that show significant accuracy improvements over state-of-the-art methods.
We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The problem exhibits close ties to decomposable submodular function minimization (DSFM), yet is much more challenging to solve. We approach the problem via a new dual strategy and formulate an objective that can be optimized through a number of double-loop algorithms. The outer-loop uses either random coordinate descent (RCD) or alternative projection (AP) methods, for both of which we prove linear convergence rates. The inner-loop computes projections onto cones generated by base polytopes of the submodular functions, via the modified min-norm-point or Frank-Wolfe algorithm. We also describe two new applications of QDSFM: hypergraph-adapted PageRank and semi-supervised learning. The proposed hypergraph-based PageRank algorithm can be used for local hypergraph partitioning, and comes with provable performance guarantees. For hypergraph-adapted semi-supervised learning, we provide numerical experiments demonstrating the efficiency of our QDSFM solvers and their significant improvements on prediction accuracy when compared to state-of-the-art methods.