Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
arXiv:1902.10132
Abstract
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.
arXiv commentA part of the work appeared in NeurIPS 2018. The current version is to appear in JMLR (Revise some typos). arXiv admin note: substantial text overlap with arXiv:1806.09842
References in corpus (11)
- Higher-order organization of complex networks
- Efficient Minimization of Decomposable Submodular Functions
- The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
- Reflection methods for user-friendly submodular optimization
- Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
- Provable Submodular Minimization using Wolfe's Algorithm
- Decomposable Submodular Function Minimization: Discrete and Continuous
- Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
- Scalable Variational Inference in Log-supermodular Models
- Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian
- Polynomial-Time Algorithms for Submodular Laplacian Systems