Research map / Learning theory and algorithms / Submodular and game algorithms
Quadratic Decomposable Submodular Function Minimization: Theory and Practice
Pan Li, Niao He, Olgica Milenkovic
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use QRCD with the exact projection for undirected hyperedges (SPE) instead of PDHG | PDHG · Synthetic hypergraph SSL (l = 1) | classification error rate (%): 9.05 -> 2.93 | Improved |
| use QDSFM objective with QRCD-SPE instead of the DSFM objective (DRCD) | DRCD · Synthetic hypergraph SSL (l = 1) | classification error rate (%): 44.7 -> 2.93 | Improved |
| use QRCD-SPE instead of InvLap | InvLap · Synthetic hypergraph SSL (l = 1) | classification error rate (%): 8.17 -> 2.93 | Improved |
| use QRCD-SPE instead of QAP-SPE | QAP-SPE · Synthetic hypergraph SSL (l = 1) | classification error rate (%): 14.9 -> 2.93 | Improved |
| use QRCD-SPE instead of SGD | SGD · Synthetic hypergraph SSL (l = 1) | classification error rate (%): 5.79 -> 2.93 | Improved |
| use QRCD-SPE instead of QRCD-MNP or QRCD-FW on synthetic hypergraphs | QRCD-MNP / QRCD-FW · Synthetic hypergraph SSL | CPU time: 100 to 1000 times slower | Improved |
| use conic MNP subroutine instead of FW, AMP or PWMP in QRCD | QRCD · Synthetic QDSFM (N = 100, R = 100) | primal gap | Improved |
| use conic PWMP with smaller theta (0.25, 0.5 versus 1) (ablation) | QRCD-PWMP · Synthetic QDSFM (N = 100, R = 100) | primal gap | Hurt |
| scale up submodular function by s in {1, 2, 5, 10, 20} (ablation) | conic MNP, FW, AMP, PWMP projections · Single submodular function (theta = 0.25, N = 100) | CPU time | Hurt |
| vary beta from 10^-3 to 10^3 in the QDSFM objective (ablation) | QRCD · Synthetic QDSFM hypergraph SSL | gap ratio | Mixed |
| use InvLap instead of QRCD-SPE on large real hypergraphs | InvLap · UCI Mushroom, Covertype45, Covertype67 | running time (s): 22, 114 and 1802 seconds | Hurt |
Closest papers by meaning
- Quadratic Decomposable Submodular Function Minimization (NeurIPS 2018 · similarity 0.97)
- Decomposable Submodular Function Minimization via Maximum Flow (ICML 2021 · similarity 0.90)
- Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components (NeurIPS 2021 · similarity 0.90)
- Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams (AAAI 2018 · similarity 0.89)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.88)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
