Quadratic Decomposable Submodular Function Minimization
This work addresses a convex optimization problem relevant for learning on graphs and hypergraphs, such as semi-supervised learning and PageRank, offering incremental improvements in efficiency and accuracy.
The paper tackles the problem of quadratic decomposable submodular function minimization, which arises in graph-based learning tasks, and demonstrates that their proposed algorithm achieves significant improvements in prediction accuracy over state-of-the-art methods in semi-supervised learning on hypergraphs.
We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization. The problem is closely related to decomposable submodular function minimization and arises in many learning on graphs and hypergraphs settings, such as graph-based semi-supervised learning and PageRank. We approach the problem via a new dual strategy and describe an objective that may be optimized via random coordinate descent (RCD) methods and projections onto cones. We also establish the linear convergence rate of the RCD algorithm and develop efficient projection algorithms with provable performance guarantees. Numerical experiments in semi-supervised learning on hypergraphs confirm the efficiency of the proposed algorithm and demonstrate the significant improvements in prediction accuracy with respect to state-of-the-art methods.