arXiv:2505.17443cs.DScs.LG2025-05NeurIPS被引 1

统一求解各类子模与超模比值优化问题,通用算法表现超越专用方法。

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems

  • 将多种优化问题统一为最小范数点问题,实现算法互通。
  • 通用凸优化与网络流方法在400+实验中优于专用算法。
  • 适用于图分割、子模最小化等任务,适合研究者与工程师使用。

我们研究在非空子集上最小化或最大化子模或超模集合函数的平均值 $ f(S)/|S| $。该问题推广了经典问题如最密子图(DSG)、最密超模集(DSS)和子模函数最小化(SFM)。受近期应用启发,我们引入两类新公式:无限制最稀疏子模集(USSS)和无限制最密超模集(UDSS),支持负值与非单调函数。我们证明 DSS、SFM、USSS、UDSS 及最小范数点(MNP)问题在强多项式时间内可相互归约,实现算法跨领域应用。通过基多面体中的 MNP 视角,我们将 Fujishige 理论与密集分解联系起来,发现 Fujishige-Wolfe 算法与启发式 extsc{SuperGreedy++} 可作为所有这些问题的通用求解器,包括子模最小化。理论上解释了 extsc{SuperGreedy++} 在子模最小化与最小 $ s $-$ t $ 割等任务中有效的原因。实验证明,在七类问题与大规模真实/合成数据集上,通用凸优化与流方法的表现超过专用基线,表明恰当建模下通用优化技术可同时具备可扩展性与领先性能。

原文摘要 · Abstract (English)

We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function $ f: 2^V \to \mathbb{R} $ over non-empty subsets $ S \subseteq V $. This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications, we introduce two broad formulations: Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), which allow for negative and non-monotone functions. We show that DSS, SFM, USSS, UDSS, and the Minimum Norm Point (MNP) problem are equivalent under strongly polynomial-time reductions, enabling algorithmic crossover. In particular, viewing these through the lens of the MNP in the base polyhedron, we connect Fujishige's theory with dense decomposition, and show that both Fujishige-Wolfe's algorithm and the heuristic \textsc{SuperGreedy++} act as universal solvers for all these problems, including sub-modular function minimization. Theoretically, we explain why \textsc{SuperGreedy++} is effective beyond DSS, including for tasks like submodular minimization and minimum $ s $-$ t $ cut. Empirically, we test several solvers, including the Fujishige-Wolfe algorithm on over 400 experiments across seven problem types and large-scale real/synthetic datasets. Surprisingly, general-purpose convex and flow-based methods outperform task-specific baselines, demonstrating that with the right framing, general optimization techniques can be both scalable and state-of-the-art for submodular and supermodular ratio problems.

子模优化图算法通用求解凸优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。