Revisiting Decomposable Submodular Function Minimization with Incidence Relations

Abstract

We introduce a new approach to decomposable submodular function minimization (DSFM) that exploits incidence relations. Incidence relations describe which variables effectively influence the component functions, and when properly utilized, they allow for improving the convergence rates of DSFM solvers. Our main results include the precise parametrization of the DSFM problem based on incidence relations, the development of new scalable alternative projections and parallel coordinate descent methods and an accompanying rigorous analysis of their convergence rates.

A part of this work will be presented in NIPS2018

References in corpus (7)

• Semi-Supervised Classification with Graph Convolutional Networks
• Cooperative Game Theory Approaches for Network Partitioning
• 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

Cited by in corpus (3)

• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• Local Hypergraph Clustering using Capacity Releasing Diffusion