# Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)

arXiv: https://arxiv.org/abs/1902.10132 · HTML: https://mlsanity.com/paper/1902.10132/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

## Built on by (most cited first, 7 of 7)

- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [A nonlinear diffusion method for semi-supervised learning on hypergraphs](https://mlsanity.com/paper/2103.14867/) (2021)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Temporal Inductive Logic Reasoning over Hypergraphs](https://mlsanity.com/paper/2206.05051/) (2022)
- [A Simple Hypergraph Kernel Convolution based on Discounted Markov Diffusion Process](https://mlsanity.com/paper/2210.16884/) (2022)
- [Modeling Edge-Specific Node Features through Co-Representation Neural Hypergraph Diffusion](https://mlsanity.com/paper/2405.14286/) (2024)

## Abstract (arXiv)

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.