Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
Authors: Elfarouk Harb
Yousef Yassin
Chandra Chekuri
Venue: NeurIPS 2025 spotlight ()
Keywords: densest subgraph
densest supermodular set
submodular function minimization.
Primary area: optimization
TL;DR: We unify submodular/supermodular ratio problems and show general algorithms like SuperGreedy++ and min-norm point methods are surprisingly efficient and scalable, outperforming specialized methods in theory and practice

Abstract: We consider the following question: given a submodular or supermodular set function $f:2^V \to \mathbb{R}$, how should one minimize or maximize its average value $f(S)/|S|$ over non-empty subsets $S\subseteq V$? This problem generalizes several well-known objectives including Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications [39, 31], we formalize two new broad problems: the Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS) which allow negative and non-monotone functions.

Using classical results we observe that DSS, SFM, USSS, UDSS, and MNP are all equivalent under strongly polynomial-time reductions. This equivalence enables algorithmic cross-over: methods designed for one problem can be repurposed to solve others efficiently. In particular we use the perspective of the minimum norm point in the base polyhedron of a sub/supermodular function which, via Fujishige's results, yields the dense decomposition as a byproduct. Via this perspective we show that a recent converging heuristic for DSS, \textsc{SuperGreedy++} [15, 29], and Wolfe’s minimum norm point algorithm are both universal solvers for all of these problems. 

On the theoretical front, we explain the observation made in recent work [39, 31] that \textsc{SuperGreedy++} appears to work well even in settings beyond DSS. Surprisingly, we also show that this simple algorithm can be used for Submodular Function Minimization, including for example that it can act as an effective minimum $st$ cut algorithm. 

On the empirical front, we explore the utility of several different algorithms including Fujishige-Wolfe min-norm point algorithm for recent problems. We conduct over 400 experiments across seven problem types and large-scale synthetic and real-world datasets (up to $\approx 100$ million edges). Our results reveal that methods historically considered inefficient, such as convex-programming methods, flow-based solvers, and Fujishige-Wolfe’s algorithm, outperform state-of-the-art task-specific baselines by orders of magnitude on concrete problems like HNSN [39]. These findings challenge prevailing assumptions and demonstrate that with the right framing, general optimization algorithms can be both scalable and state-of-the-art for supermodular and submodular ratio problems.

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
Elfarouk Harb
Yousef Yassin Carleton University
University of Illinois at trbaanaCChampaign eyfuharb@gmail.com
yousef www.syysasaaaaaan.c.... ca
Chandra Chekuri
University of Illinois at Urbana-Chamaan Champaagn
chekuri@illinois edu
Abstract
We consider the following question: given submoduulrr/upprrmdduua set fune- tion f 2 + IR, how should one minimize/maximize its average value [(S)/SS over non-empty subsets S C V? This problem generalizes several well-known objectives, including Densest Subgraph (DSG). Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications 42 34]. we formalize two new broad problems: the Unrestricted Sparsest Sub- modular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), both of which allow negative and non- mon-monoe functions.
Using classical results, we show that DSS, SFM, USSS, UDSS, and Minimum Norm Point (MNP) are all equivalent under strongly polynomial-time reductions. This equivalence enables algorithmic cross-over: methods designed for one prob- lem can be repurposed to solve others efficiently. In particular, we use the perspec- tive of the minimum norm point in the base polyhedron of sub/supermodullr function, which, via Fujishige's ' results, yields the dense decomposition as a byproduct. Through this perspective,
show that a recent converging heuristic for DSS, SUPERGREEDY++ [2] ..2).a and Wolfe's ' minimum norm point algorithm are both universal solvers for all of these problems.
On the theoretical front, we explain the observation made in recent work 42 34 that SUPERGREEDY++ appears to work well even in settings beyond DSS. Surprisingly, we also show that this simple algorithm can be used for Submodular Function Minimization, including acting as practical minimum s-f cut algorithm.
On the empirical front, explore the utility of several algorithms for recent prob- lems. We conduct over 400 experiments across seven problem types and large- scale synthetic and real-world datasets (up to ss 100 million edges). Our results re- veal that methods historically considered inefficient, such as convex monex-prrogramming methods, flo-bbaed solvers, and Fujishige- Wolfe's algorithm, outperform state- of-the-art art task-specific baselines by orders of magnitude on concrete problems like HNSN [22. These findings challenge prevailing assumptions and demon- strate that with the proper framing, general optimization algorithms can be both scalable and state-of-the-art for supermodular and submodular ratio problems.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction and Background
Submodular and supermodular functions play a fundamental role in combinatorial optimization and, thanks to their generality, capture a wide variety of highly relevant problems. For a finite ground set V. the real-valued set function f 2 - IR is submodular iff f(A) + f(B) 2 + (AUB) for all A, B S V. A set function f is supermodular iff -f is submodular; f normalized ff (0) = 0 and monotone if f(A) S fBB) whenever A C B. When working with these functions, we typically assume they are available through a value oracle that returns s' ((S) given a set C V. We make this assumption throughout the paper. A problem of central interest is the following:
Problem 1. (Submodular Function Minimization, SFM). Let f :2 - R be a submodular functiulafuunction function (not necessarity monotone) given via value oracle. Compute ming4.5V f(S).
A classical result in combinatorial optimization is that SFM can be solved in strongly polynomial-
time 30). There have been many theoretical developments since then [37 48 5T
35 12 39 3].
In this paper, we are interested in ratio problems involving submodular and supermodular functions, which have been very interesting in various applications. We start with a concrete and canonical problem of this form.
Problem 2. (Densest Subgraph, DSG). Given an undirected graph G = (V, F) find a subset S S V that maximizes the density [[(S) where E(S) {(u,0) E u, E S).
DSG is a classical problem with wide-ranging applications in data mining, network analysis, and machine learning. Dense subgraphs often reveal crucial structural properties of networks and thus
DSG has been a very active area of recent research; see, for example, [14] 44 9 19 [5] 54 I [56]
23 45
50
6
53 4
[3] 7 A key feature of DSG is its polynomial -ime solvability.
There are several algorithms to solve it exactly: (i) via network flow (29 49 (ii) via reduction to SFM (folklore), and (iii) via an I.P relaxation [5]. Despite these exact algorithms, there has been considerable interest in fast approximation algorithms and heuristics to scale to the large networks that arise in practice. Hence, the Greedy peeling algorithm that yields a 1/2 1/2aapproximation [15] has been popular in practice. Furthermore, there are several theoretical algorithms that obtain (1 1 -)-
approximation in near-linear time for any fixed & via different techniques 10 [7 An important recent algorithm, Greedy++, is iterative version of Greedy that was proposed in [9]. It is simple, combinatorial, and has strong empirical performance. Moreover, it was conjectured to converge to (1 E) approximation in - each of which takes (near) linear time like Greedy. T7 proved that Greedy++ converges to a (1 - E) -aprroximaee solution in ((A(G) log [V]/=*) iterations where (G)) is the maximum degree. Crucial to their proof
perspective based on supermodularity. In particular, they considered the following general ratio problem.
Problem (Densest Supermodular Set, DSS). Let f 2 - R2o be a normalized, monotone supermodular function. Compute maxpysgv f(S)/(S).
DSG is special case of DSS; for all graphs G EV, the function f: 2V + E where f(S) [E(S) is monotone supermodular. DSS can be solved exactly via SFM. [17 defined SuperGreedy and SuperGreedy++ for DSS and showed that SuperGreedy+ converges to a (1 -approxxmmte optimum solution in (a log [VI/=") iterations where ay = max.(f(V) - f(V - v)). This is useful result since several non-trivial problems in dense subgraph discovery can be modeled as a special case of DSS including hypergraph density problems, p-mean density [57] and others for details, refer the reader to the recent survey 41). Several other converging iterative algorithms for DSG have recently been developed via convex optimization methods such as Frank- Wolfe 119. FISTA (3T), and accelerated coordinate descent (47). In another direction, flow-based exact algorithms have been revisited [34, 33). Many of these algorithms are based on structural properties of DSG inherited from supermodularity, which we describe in more detail following the discussion of the motivation for this work.
Motivation for this work: Our initial motivation originates from two recent ratio problems. studied the following problem.
42
Problem 4. (Heavy Nodes in a Small Neighborhood, HNSN). Given bipartite graph G(L.R,E) and a weight function w R + Rzy- find a set S C R of nodes such that ΣvER ((v)/[N(S) maximized where N(S) the set of neighbors of S. Equivalently the goal to minimize IN(S) w(v)).
2

---

In the preceding problem, the function f 2 - R defined as f(5) = [N(S)] is monotone submodular function; it is the coverage function of the set system induced by the bipartite graph G (which can also be viewed as hypergraph). This leads us to consider the following ratio problem.
Problem 5. (Unrestricted Sparsest Submodular Set, USSS). Given a normalized submodular func- tion| f + R. find ming f(S)/SS)
A second motivating problem is the following, which is initially studied in [8] and later revisited in [3
Problem 6. (Anchored Densest Subgraph, ADS), Given graph G = (V, E) and a set R S V. find a vertex set S C V maximizing (2) - Evesnn de /IS), where (eza(") is the degree of in G.
The numerator in the preceding problem is supermodular but is no longer non-negatee non-negative or monotone. This motivates to further define an unrestricted version of DSS.
Problem 7. (Unrestricted Densest Supermodular Set, UDSS). Given a normalized supermodular function f : 2 + I, find max /
42 showed that the HNSN problem can be reformulated as a special case of DSS, allowing iterative peeling algorithms (SUPERGREEDYY++) to converge to the optimal solution. In 34, this perspective is extended by applying SUPERGREEDY non-negativity and monotonicity can be enforced if one first shifts the function by a large modular term, i.e., adding C) for some sufficiently large constant C. This ensures non-negativity and monotonicity while retaining the exact optimal solution (since the density of all sets simply shifts by constant C). However, the shift renders the relative approximation guarantee in [17 inapplicable in a direct way; indeed, 34 state the following: "we hypothesize that iterative peeling remains an effective practical heuristic".
the unrestricted version of DSS (UDSS), noting that
More generally, while USSS and UDSS are equivalent in the exact optimization sense (via nega- tion), approximation guarantees do not easily carry over, especially when relying on relative error measures. This highlights& a key open question: can we formally prove that SUPERGREED? ++ con- verges for all the above problem classes under appropriate approximation guarantees? Addressing this question, as we will in this paper, would provide a unified theoretical foundation for its empirical success observed across diverse submodular and supermodular ratio problems.
Min-norm point and the Fujishige- Wolfe algorithm. Another motivation for this work comes from some essential properties of the min-norm point problem relevant to submodular optimization.
Problem 8. (Minimum Norm Point, MNP). Let f 2V + R be normalized submodular or super- modular function, and let [J) be the corresponding base polytope. Find arg minzeB(J) ||=:112-
It is known that SFM can be reduced to MNP 26 52) Further, 25
showed that the optimum value yields a lexicographically optimal and unique base, which reveals the entire dense decomposi- tion of f. Recent work in the context of DSG has exploited MNP via convex optimization techniques to obtain fast iterative algorithms for DSG and the dense decomposition version of DSG.
26
19
Wolfe defined the min-norm point problem in the more general context of convex optimization and developed an iterative algorithm which is well-known (59) we note that his algorithm is tailored to the quadratic norm objective and is quite different from the more general convex optimization algorithms. Fujishige tailored the algorithm to submodular polytopes. yielding one of the fastest practical SFM solvers (28 [T]. Nagano et al. [46] also studied the densest & subgraph problem in the context of the minimum norm point in the base polyhedron. Despite its well-known empirical performance for SFM, the Fujishige- Wolfe algorithm has not been empirically evaluated for any recent ratio problems.
Revisiting blsed exact algorithms. Flow-based approaches to DSG were deemed impractical for large graphs because they required an expensive binary search procedure []] Recent indepen- dent work by Huang el al. (34] and Hochbaum
33 introduced iterative density-improvement
Binary search is efficient in general, and much faster than simply enumerating all possible density thresh- olds. Our intention here is to indicate that earlier flow-based algorithms for densest subgraph problems used binary search over the density threshold X, requiring full max- max-flow flow computation at each step of the search. The need for high-pree precision convergence and repeated max- flow computations can makes this approach impractical scale.
3

---

framework that overcomes this limitation. Letting f(S) |E(S)] and starting with So = V and An f(So)/|Sol. the method repeatedly computes SK+1 arg ma {f(()) A - via max-flow, updating A++1 = ((Sx+1)//1)) 1///|+++1 until convergence (Sk+1 = St). This approach, guarantees optimality. Although this process may appear worse than binary search in the worst case, potentially requiring up to [V] + 1 flow computations, empirical evidence shows that the number of iterations is typically minimal and often far fewer than those required by binary search. These insights have renewed interest in flow- based algorithms for solving DSG, One can reduce HNSN to a max-flow problem. This raises the question of the performance of flow-based algorithms for HNSN.
rooted in Dinkelbach's classical method from 1967 (0 M
Summary of Motivation. We are motivated by the observation that several closely related sub- modular and supermodular ratio problems are treated disparately across the literature, often with distinct algorithms and analyses, despite underlying connections. We are interested in whether a unified perspective can bridge these gaps. For instance, while the simple combinatorial algorithm SUPERGREEDY++ has provable guarantees for DSS, its empirical success in broader settings lacks corresponding unified theoretical analysis.
Similarly, the Fujishige-Woo Wolfe algorithm, despite its established effectiveness for submodular func- tion minimization, has surprisingly not been evaluated for ratio problems in USSS and UDSS. Moreover, with recent progress in flow-based exact algorithms for densest subgraph problems, it is natural to ask how these methods perform on related submodular ratio problems like HNSN. In essence, our goal is to investigate whether algorithmic successes in one domain can be transferred to others, leveraging tools that have been overlooked to improve empirical performance and deepen thcoretical understanding across these problem classes.
Our Contributions. We formalize connections between five problems via reductions: Mini- mum Norm Point (MNP), Submodular Function Minimization (SFM). Densest Supermodular Set (DSS), Unrestricted Sparsest Submodular Set (USSS), and Unrestricted Densest Supermodular Set (UDSS) by proving that they are equivalent. All the reductions run in either O(n) or O(n log n) (where n is the dimension of the underlying base set) calls and are highly efficient.
While these reductions are rooted in classical concepts, several of these problems such USSS and UDSS have not been formally defined in the literature. For instance, although DSS can be exactly solved via SFM, its formal definition in [17] was instrumental in advancing specialized algo- rithms like SuperGreedy and SuperGreedy+++ By establishing these reductions, we enable algorith- mic cross-over, where methods developed for one problem can be effectively applied to others. This is demonstrated in our experiments: Fijishige- Wolfe's 's Minimum Norm Point algorithm (FW-MNP), originally for MNP, achieves up to 595x speedups over prior offte-oftthe--r art basclines on HNSN (a special case of USSS). Similarly, SUPERGREEDY+++ designed for DSS, delivers scalable and competitive performance on the minimum s-t cut problem (a special case of SFM). Interestingly, is surprising that SUPERGREEDY++ serves as an effective algorithm for minimum s-t cut, despite being extremely simple, requiring no special data structures, and working in the dual (cut) space. To the best of our knowledge, all existing algorithms for minimum s-l cut in the literature operate in the primal space via max-flow formulations.
Additionally, we demonstrate that an approximate solution to the Minimum Norm Point (MNP) problem also provides approximate solutions to all the other problems. We use the notion of additive approximation rather than the relative approximation notion used in the DSG and DSS context. This is necessary since we are working with unrestricted functions that may be negative. We also prove that SUPERGREEDY ++, the Frank-Wolt algorithm, and the Fujishige-Wond Wolfe FW-MNP Algorithm are, in fact, all (under the hood) solving the Minimum Norm Point problem, which explains why these methods have seen much success across seemingly unrelated problems.
It is worth highlighting an interesting observation about SUPER GREEDY++. Although the algorithm was originally developed for the DSS problem- task that itself reduces to SFM -our results show that SUPERGREEDY can also be directly interpreted as an algorithm for solving SFM. This "full-circle" insight, where approximation algorithm for a derived problem effectively addresses a more general problem, is surprising and conceptually satisfying.
We summarize our contributions more concretely:
Problem Equivalence. We prove that the following problems can be reduced to one another in strongly polynomial time using efficient reductions when solved exactly: Submodular Function

---

Minimization (SFM), Densest Supermodular Set (DSS), Minimum Norm Point (MNP). Unre- stricted Sparsest Submodular Set (USSS), and Unrestricted Densest Supermodular Set (UDSS),
2. Approximation Transfer. We prove that approximate solutions to MNP can be transformed into approximate solutions for all the above problems via approximation prreeoovinneeeiiingggg reductions. These approximation-preseee preeeervnn reductions are different from the above exact reductions.
3. SuperGreedy++ and Fujishige- Wolfe FW-MIN Algorithm as Universal Solvers. Despite being designed for specific settings, we prove both SUPER GREEDY++ ++ and Fujishige-Wolfe's FW-MNP algorithm are universal solvers for this broader class of problems.
4. Efficient New Algorithms for HNSN and Minimum s-t Cut. As direct consequence, results imply that the Unrestricted Sparsest Submodular Set, a primary motivation of our work, can be efficiently approximated and solved. This concretely includes, for instance, algorithms for the HNSN problem that are orders of magnitude faster than all 6 state-of-the- art baselines compared in 42 Additionally, we show that SUPER efficient submodular function minimization algorithm and can thus he used to solve the classical minimum s-f cut problem, often converging to the minimum cut within few iterations.
faster
is, in fact, an
5. Empirical Validation at Scale. We conduct an extensive experimental study involving over 400 trials run across seven distinct problems, encompassing both synthetic and real datasets contain- ing graphs with up to & 100 million edges or elements for set functions. Our experiments sys- tematically compare all major algorithmic paradigms. including flow-based methods. LP solvers, convex optimization techniques (e.g., Fujishige- Sejishige-Wolfe'ss Wolfe's FW-MNP algorithm, (oone), and combinatorial baselines (e.g.. SUPERGREEDY++) for each problem class: DSG, DSS, USSS, UDSS, SFM, and MNP. Notably, many algorithms that had never been previously explored in certain problem settings (e.g.. Fujishige-Wole Wolfe's FW-MNP algorithm on HNSN or flow-based methods on USSS instances) outperform problem-specine state-of-the-aat algorithms from prior work by orders of magnitude.
Our results demonstrate that methods often written off as inefficient, such as Wolfe's algorithm and max-flow solvers, are not only competitive but frequently faster and more accurate than tailored heuristics when applied correctly with the right lens.
Remark on Scope and Related Work. Throughout this paper, we discuss several optimization problems such as SFM, HNSN, DSS, DSG, and MNP, each of which has rich history and extensive literature. Due to space constraints, we cannot provide an exhaustive survey or explore all technical nuances and historical developments of each problem. Instead, we have focused on presenting the key connections and ideas necessary for the unified perspective proposed in this work. An expanded version of this paper will include more comprehensive discussion, including detailed related work and contextual background. Due to space constraints, we include several proofs and experimental results in the Appendix. Finally, we include table of acronyms in Table
2 Preliminaries and Main Results
Recall that we already defined submodularity, supermodularity, and monotonicity in the introduc- tion. Throughout this paper, we assume that all set functions are normalized without loss of gener- ality.
Definition 9 (Base Polymatroid). For a submodular function f :V + R. the base polymatroid is defined as B(f) = {ar E VI x{S) & f(S) VS S V, x(V) = =(V)), where x(S)= =
Eves T..
Definition 10 (Base Contrapolymatroidd). For supermodular function f : 2V R, the base contrapolymatroid is defined as B(f) {ir R xxS) 2 f(S) VS VV, x(V)= = f(V)).
For functions that are either submodular or supermodular, we refer collectively to the base polyma- troid and the base contrapolymatroid as the base polytope.
Importance of the Minimum Norm Point in the Base Polytope. A key approach in submodu- lar optimization connects continuous minimization over the base polytope with discrete problems. Specifically, the MINIMUM-NOR NORUUUM-NOOMPPORR POINT (MNP) problem minimizes ||>:|/ over B(f), yield- ing unique minimizer x². Thresholding x² often recovers combinatorial minimizers for penal- ized objectives. While the following connection is classical in submodular function minimization literature, its utility for submodular or supermodular ratio problems has been underexplored. Its significance became clear to us only after recognizing how it simplifies several prior results.
5

---

Lemma 11. Let f be normalized submodular set function and let x² be the optimal solution of min | For any X I. define the set S {v x S X}. Then, Sx is a minimizer of the function f(5) A
Discussion. Lemma has strong implications, helping establish the equivalence of several prob- lems through efficient, strongly polynomial reductions. Specifically, shows (together with other ideas) that all the following problems are equivalent, with very efficient strongly-polynonee polynomial time reductions. Proof in Appendixx A.2
Theorem 12. The following problems are all equivalent when solved exactly, with efficient (strongly
polynomial) near-linear time reductions between them: (1) MINIMUM NORM POINT (MNP) (2) SUBMODULAR FUNCTION MINIMIZATION (SFM) (3) DENSEST SUPERMODULAR SET (DSS)
(4) UNRESTRICTED SPARSEST SUBMODULAR SET (USSS) (5) UNRESTRICTED DENSEST SU- PERMODULAR SET (UDSS).
Approximation equivalence. Although Theorem shows that the aforementioned problems are efficiently reducible to one another when solved exactly, this does not imply that the reductions are approximation preserving... However, as the following Theorem demonstrates, it suffices focus on approximating the MINIMUM NORM POINT problem (MNP).
Theorem 13. Let f 2 - R be a normalized submodular supermodular function, and suppose we can compute & E B)) satisfying
|| S (q, + for all q E B(f):
i.e, an upper bound on the duality gap. Let n = IV]. Then, &t can be used to efficiently obtain approximate solutions:
1. (Submodular Function Minimization): A set Samn with ((Sato) S ((S +nn.
2. (Unrestricted Sparsest Submodular Set): A set Saparse with [(Sppar)))
[1Sppare))
+ 22.
[Saparse
Spuesel
3. (Unrestricted Densest Supermodular Set): A set Saense with ('Smmen
[S
22.
denue
Notably, this theorem shows that approximating SFM, DSS, UDSS, or USSS reduces to approxi- mating the minimum norm point in B(f).
Remark 14. The condition in Theorem 13 assumes approximate solution è satisfying || < (q,5) + x² for all E B(f), which upper hounds the duality gap for MNP. While Theorem 13 focuses how this approximate leads good set-based solutions for other problems (like SFM, USSS), it is worth remarking that that this same is also an approximate solution to the MNP problem itself, in the sense that close to the true minimum-norm point up additive Oe) error.
3 SUPERGREEDY++ and Fujishige-Wold Wolfe's FW-MNP Algorithm as Universal Solvers
Let :: + IR be a normalized submodular or supermodular function. As indicated in Theorem 13 the main challenge in obtaining approximations for USSS, DSS, UDSS, and SFM is to compute an approximate minimum- minimum-norm-pont norm-point & E B(f). We will discuss three different methods, which will refer to collectively as Universal Solvers.
Frank- Wolfe Algorithm. A classical method for solving MNP is the Frank-Wolfe algorithm, an iterative approach for minimizing a convex function h : D IR over compact convex set D. Each iteration computes the linear minimization oracle (LMO) (k() arg min (8, (h(x:(-11)), and
updates (*k)) (1 (x)) (x (k) for 0*
2 For MNP, we set D B(f) and k+2
Mxx) = || reducing the LMO to (k)) = arg min B(J) (d. (b-))) This oracle is efficiently realized via Edmonds' greedy algorithm for (super)submodula) functions (2).
Fujishige- Wolfe Minimum Norm Point Algorithm. Another standard approach is the Fujishige-
Wolfe algorithm (27), which computes & E Bff) satisfying || | < (i, q) + for all q E B(f).
The algorithm requires D(VIQ2//5 /22) iterations, where Q max 1/
Like Frank-Wolfe, the Fujishige- Hoisse Wolfe FW-MNP algorithm repeatedly calls the same linear mini- mization oracle over Bff but additionally requires oracle that minimizes || 1| over the affine

---

hull of a set S of selected extreme points of B(f). This affine minimization oracle can be imple- mented efficiently in O(IS) S time by computing the inverse of B B, where B is the n x |S] matrix whose columns the points in S.
SUPERGREEDY++ Next, we demonstrate that SUPERGREEDY++, originally designed for solv- ing the DSS problem, can be used to approximate MNP. Consequently, it is universal solver for approximating the problems mentioned above.
Theorem 15. Given normalized submodular supermodular function f 2 R. SUPER- GREEDY++ returns a vector i satisfying || & (g. $) + + for all q B(f), after
||s 3 + n f(u (V VV-)= B,f
max
T Ó
iterations, where Ô hides polylogarihmic factors, and [u V u = S(V) J(V {u)). Conse- quently, all approximation guarantees from Theorem 73 follow after the same number of ieerations
Proof in Appendix A.4.
Remark 16. It is worth emphasizing that although SUPERGREEDY++ demonstrates outstanding empirical performance. its theoretical runtime remains vscudo-polynonne due to the presence of function-dependent terms. This contrasts with state-of-the-at SFM algorithmss, which achieve strongly polynomial runtimes. Consequently, applying SUPERGREEDY++ directly to SFM in- stance under our analysis results a preuudo-oolnooiaa algorithm rather than a strongly polynomial one.
Experiments
We evaluate our algorithms and baselines on diverse set of datasets and problem settings, running over 400 experiments across SFM, USSS, and UDSS. Our experiments aim to answer three key questions:
Which algorithms perform best for which problems, especially when applied beyond their original methods (e.g., FW-MNP for USSS) outperform
setting? Are there cases where
problem-specific heuristics?
How do convex optimization methods (e.g., Frank- Fujishige- to combinatorial (e.g. SUPERGREEDY+ LP-based, and flow-based approaches in runtime and solution quality?
Wollf Wolfe FW-MNP) compare
Can SUPER EEDYY++ Frank-Wolfe, and FW-MNP serve as effective general-purpose solvers across multiple problem classes?
Our empirical study is organized per problem class, covering Unrestricted Sparsest Submodular Set (USSS), Submodular Function Minimization (SFM), and Unrestricted Densest Supermodular Set (USSS). We specify problems, datasets, algorithms, and evaluation metrics for each. Experiments were run in parallel on a Slurm-managed cluster (AMD EPYC 7763, 128 cores, 256GB RAM). All methods are implemented in C++2 primarily by the authors, except for specialized baselines (e.g.. GREEDY++). Due to space constraints, we only discuss two experiments here; most of our ex- perimental results are provided in the appendix. Specifically, we selected these two experiments because the HNSN results demonstrate the value of classic algorithms for a recently explored prob- lem, whereas the Minimum t Cut results illustrate the value of newly developed algorithms for a long-standing problem.
(1) Heavy Nodes in a Small Neighhorhood (HNSN). Recall the HNSN problem from the intro- duction. Since the function f(S) [S) is submodular, HNSN is special case of the weighted USSS problem. Ling et al. further reformulate the problem over the left vertex set L, defining the function N 2 + IR by N(S)- = (u E R 5(v) S S} where 5(v) denotes the set of neighbors of v. Under this formulation, the problem becomes that of maximizing wi (NV(())) over non-empty subsets S C T.. We adopt this viewpoint in implementation.
Our code and datasets available at http://ghhhu..ooom/oooooo///oonn
7

---

(a) HNSN on YooChoose (GRR Suboptimal)
(b) HNSN on Econmerce
1
40000
1900
1000
P901000
(c) Min s-t Cut BVZ-sawtooth14
(d) Min s-t Cut BVZ-sawtooth3
Figure I: Performance of algorithms across selected HNSN and Minimum s-t Cut instances.
Algorithms. We compare against the six baselines of Ling et al. 42 and introduce
novel flow-based algorithm (detailed in Appendix B). In total, we evaluate ten algorithms: IP (SUPERGREEDY++)) FW Wolfe),, FW-MNP (Fujishige-Won Wolfe Minimum Norm Point Al- gorithm), FLOW (our new flow-based method), CD (ContractDecompose, (42). LP (Linear Pro- gramming, solved via Gurobi with academic license), GAR (Greedy Approximation, [42), GR (Greedy, 42, FGR (Fast Greedy, (42),, ), and GRR (GreedRatio, (5)). The first four are our imple- mentations; the remaining six follow Ling el al.' 's code (2).
Datasets. Table summarizes the datasets used for the HNSN problem, following the benchmarks introduced by Ling et al. [42). Each dataset is represented as a weighted bipartite graph with left vertices L, right vertices R. weights the right vertices w R 22 and edges E. The graphs are derived from diverse real-world domains, including recommendation systems (e.g.. YooChoose, Kosarak), citation networks (ACM), social networks (NotreDame, IMDB, Digg), and financial trans- actions (c.g., E-commerce, Liquor). The datasets exhibit wide range of sizes, with up to 106 vertices and 2 107 edges.
Discussion of HNSN Results. All algorithms were given a 30-minute time limit per dataset. The full results are provided in Appendix C we plot two example runs in Figures La and lb Across all datasets, FW and FW-MNP consistently emerged as the fastest to converge. In nearly every case, FW-MNP outperformed FW, achieving the best solution quality in the shortest time, with only single dataset where FW was slightly faster. Relative to the six baselines from Ling et al. [42), these methods achieved speedups ranging from 5x to 595x. Figures the rest in the appendix.
la
1b show two examples, with
Our new flow-based algorithm and SUPERGREEDY++ (IP) typically followed, ranking third and fourth in performance across datasets. Figure la shows a particularly striking example where, on the YooChoose dataset, FW-MNP achieved a 595x speedup over the best previously published baseline. In this instance, all algorithms converged to the correct final density, except for GRR, which terminated at a suboptimal solution and was therefore excluded from the runtime comparison.
These results underscore recurring insight consistently observed across our experiments: universal solvers such as FW-MNP and FW, originally developed for broader optimization tasks, can signif- icantly outperform specialized heuristics when applied to specific problems like HNSN, provided they are used within the proper conceptual framework that we have outlined. The results also show the relevance of classic cidmizzttion-assed methods for new problems.
(2) Minimum s-t Cut. We next evaluate our algorithms on the classical Minimum s-1 Cut prob- lem, a fundamental task in combinatorial optimization with widespread applications. Specifically,
8

---

the Minimum s-t Cut problem can be framed as minimizing the normalized submodular function g(S) 8(S U {(}] - [o({s)) over subsets S C V \ {s. ensuring that any feasible solution corresponds to valid s-t cut. Within this formulation, the Minimum 8-f Cut problem becomes an instance of Submodular Function Minimization (SFM), and thus naturally fits within the unified framework established in this paper. This connection allows us to apply universal solvers, such as SUPERGREEDY++ Frank-Woll and Wolfe's Minimum Norm Point algorithm, to this classical combinatorial problem.
Algorithms. We evaluate three iterative algoritmms-Frank-wonnn (FRANKWOLFE), Fujishige- Wolfe Minimum Norm Point (FW-MNP), and SUPERGREEDY+* (SUPERGREEDY)) the Min- imum s-t Cut problem. We also compute the exact minimum cut value for each instance using standard combinatorial flow-based methods (Edmonds Karp algorithm), serving as ground truth. This allows us to assess both the solution quality and runtime efficiency of the optimization- approaches relative to the exact combinatorial solution.
Datasets. Our evaluation spans two groups of datasets. First, consider four classical benchmark instances from the first DIMACS Implementation Challenge on minimum cut [21]. known for their small size but challenging cut structures. Second, to assess scalability and robustness, we include a large-scale dataset family, specifically the BVZ-SAWTOOTH instances [38]. which consist of 20 distinct minimum s-t cut problems. Each instance contains approximately 500,000 vertices and 800,000 edges, testing algorithmic scalability.
Discussion of Minimum s-t Cut Results. Full results are provided in Appendix D we plot two select examples in Figures [ and [d Across all datasets, SUPER
was consistently the fastest to approximate the minimum cut, often by large margins over exact flow-hased methods, FW-MNP, and FW. In 16 of 24 instances, it found the exact min-cut rapidly. In the remaining cases, its solution was within 1.000023x the optimum after 500 iterations at most, always converg- ing before the exact flow solver. A notable example is the BVZ- TZZSSWTOOTH!! 14 instance, where SUPERGREEDY converges orders of magnitude faster (Figure [c]. This strong performance par- allels its success in dense subgraph problems, where it efficiently finds high-quality solutions but can slow down near the optimum. Combining SUPERGREEDY++ with flow-based refinement remains an interesting direction for future work. Interestingly, while FW-MNN and FW excel HNSN, they both underperform here, underscoring how problem structure affects solver efficiency. Finally, the experiments show that recent heuristics like SUPERGREEDY can compete with classical max- flow algorithms for the minimum 8 1 cut problem.
Additional Experiments. Beyond the two highlighted experiments, we conduct comprehensive evaluation across additional problem instances corresponding to each of the general problem classes studied. For SFM, we include the classical Contrapolymatroodd Membership problem (Appendix HH). which tests whether a given vector belongs to the base polytope. For DSS, we evaluate both the Densest Subgraph problem (Appendix E) and the generalized p-mean Densest Subgraph problem For UDSS, we consider the Anchored Densest Subgraph problem (Appendix G We also report experiments the MNP problem (Appendix[I, We refer readers to the appendix for the complete set of experiments across all problem classes.
[58) (Appendix
Flow-Based Methods: Strengths and Limitations. For the classical Densest Subgraph problem, our experiments reaffirm that flow- boseb methods remain among the fastest approaches when com- bined with the
framework introduced by Huang et al. [34 and Hochbaum 33 While Hochbaum uses the PseudoFlow algorithm for this task, our experiments demon- strate that comparable performance can be achieved using more standard push-relabel max-flow solvers within the same density-improvement framework. Essentially, the primary source of speedup comes from the iterative density-improvement strategy rather than the specific choice of flow solver. This holds because for fixed density threshold X, finding a subset S minimizing |slk - f(S) = |sSk - |E(S) naturally reduces to a standard min-cut instance. A similar phc- nomenon occurs in the HNSN problem: as we outline in the appendix, there exists flow reduction that efficiently solves subproblems of the form ASSk - f(S) for HNSN, making flow-based methods highly effective here as well.
However, flow- methods are not universally applicable. For more general problems, such as the generalized p-mean Densest Subgraph problem, no known linear flow network formulations can minimize objectives like S - S(S) for arbitrary supermodular functions. In such cases, flow- based methods cannot be used, and one must resort to algorithms like SUPER Frank-

---

Table 1: Summary of HNSN Datasets. All graphs are weighted bipartite graphs
Dataset
[
[
|
A: (Conneeted components)
Foodmart (FM)
1,559
4.141
18,319
E-commerce (EC)
3,468
14,975
174,354
12
Liquor (LI)
4,026
52,131
410,609
165
Fruithut (FR)
1,265
181,970
652,773
4
YooChoose (YC)
107.276
234.300
507.266
22,033
Kosarak (KS)
41,270
990,002
8,019,015
271
Connectious (CN)
458
394,707
1,127.525
117
Digg (DI)
12,471
872,622
22,624.727
13
NotreDame (ND)
127,823
383,640
1,470,404
3,142
IMDB (IM)
303,617
896.302
3,782,463
7,885
NBA Shot (NBA)
129
1,603
13,726
ACM Citation (ACM)
751,407
739,969
2,265,837
Wolfe, or FW-MNP, which only require access to value oracle. These methods thus offer broader applicability across diverse problem settings where flow reductions are unavailable.
5 Conclusion and Limitations
The overarching conclusion of our study is clear: SUPERGREEDY+++ Frank-Wolfe and the Fujishige-Woll Wolfe FW-MNP algorithms consistently achieve state-of-the-ar performance across a wide range of submodular and supermodular ratio problems. Given the broad applicability of DSS, USSS, SFM, and related formulations, we advocate for these three methods to be included as essen- tial baselines in future empirical evaluations of such problems.
A limitation of our current work that while one of these algorithms consistently outperforms problem-specific heuristics, the identity of the best-performing method varies with the problem in- stance. Developing deeper understanding when and why each algorithm excels remains an open question. Moreover, while results provide general additive approximation guarantees via reduc- tions to the Minimum Norm Point problem, remains an interesting open question to develop a direct, problem-specifee analysis of algorithms like SUPERGREEDY in settings such minimum s-t cut. Finally, while we discussed related work on coordinate descent methods, such as recennt work by Nguyen al. [47), did not dive deep into the broader family of decomposable sub- modular function minimization (DSFM) techniques in detail. A systematic exploration of general DSFM methods and their applicability remains important direction for future research.
Additionally, while our paper focuses on unrestricted versions to allow non-monotone and negative functions (which are common in real-world applications like ADS and HNSN), restricted versions such as Sparsest Submodular Set with Monotone or Positive f could offer both: 1) Simpler theoreti- cal analysis, and 2) Opportunities for improved approximations faster algorithms. It is also worth noting that for DSS, one can obtain results terms multiplicative approximations that cannot be shown for UDSS [17]. We have some preliminary results for SSS in similar vein, for example SuperGreedy performance in terms of curvature constant of f or potentially convergence analysis for SuperGreedy++ that is similar to that for DSS in [17 for multiplicative -approximation rather than additive one.
In many problem-specifi heuristics (e.g., greedy peeling local ratio methods), the "specific struc- ture" that used is often simplistic or myopic, such as removing low-degree nodes without a global view. In contrast, general-purpose methods like FW-MNP, Frank-Wolfe, and SUPERGREEDY++ implicitly operate on the full combinatorial or polyhedral structure of the problem. As a result, they often exploit hidden structure better than naive heuristics.
That said, it remains possible design better problem-specifte algorithms that leverage deeper properties (e.g., flow-augmenting paths, dual decompositions). Our results highlight that some heuristics for specific problems underperform not because the problem hard, but because the heuristic doesn't t fully exploit the structure, which we believe is an exciting direction for future algorithm design in those problems.
10

---

6 Acknowledgment
This work used Delta CPU at NCSA through allocation CIS250079 from the ACCESS 8 program, which is supported by U.S. National Science Foundation grants #2138259, #2138286, #2138307, #2137603, and #2138296.
Chandra Chekuri and Elfarouk Harb are supported part by NSF grant CCF-2402667.
Yousef Yassin gratefully acknowledges support from the Ontario Graduate Scholarship, and the Vector Scholarship in Al from the Vector Institute.
References
[1] Reid Andersen and Kumar Chellapilla. Finding dense subgraphs with size bounds. Kon- stantin Avrachenkov, Debora Donato, and Nelly Litvak, editors, Algorithmms and Models for the Web-Graph, pages 25-37, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
[2] Albert Angel, Nikos Sarkas, Nick Koudas, and Divesh Srivastava. Dense subgraph mainte- nance under streaming edge weight updates for real-time story identification. Proc. VLDB Endow. 5(6):574-5))7 feb 2012.
[3] Brian Axelrod, Yang P Liu,, and Aaron Sidford. Near-optimal approximate discrete and contin- uous submodular function minimization. In Proceedings of the Fourieenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 837-853. SIAM, 2020.
[4] Bahman Bahmani, Ashish Goel, and Kamesh Munagala. Efficient primal-dur drimal-dual graph algo- rithms for mapreduce. In Algorithms and Models for the Web Graph: 11th International Work- shop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings, page 59-78, Berlin, Heidelberg, 2014. Springer-Verlag.
[5] Wenruo Bai, Rishabh Iyer, Kai Wei, and Jeff Bilmes. Algorithms for optimizing the ratio of submodular functions. In International Conference on Machine Learning, pages 2751-2759. PMLR, 2016.
[6] Oana Denisa Balalau, Francesco Bonchi, T-H. Hubert Chan, Francesco Gullo, and Mauro Sozio. Finding subgraphs with maximum total density and limited overlap. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, WSDM '15, page 379-388, New York, NY, USA, 2015. Association for Computing Machinery.
[7] Yuly Billig. Figenvalue approach to dense clusters in hypergraphs. Journal of Graph Theory, 2025.
[8] Timothy J. Boerner, Stephen Deems, Thomas R. Furlani, Shelley L. Knuth, and John Towns. Access: Advancing innovation: Nsf's advanced cyberinfrastructure coordination ecosystem: Services & support. In Practice and Experience in Advanced Research Computing 2023: Computing for the Common Good, PEARC '23, page 173-176, New York, NY, USA, 2023. Association for Computing Machinery.
[9] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting Densest Subgraphs Without Flow Computations, page 573-583. Association for Computing Machinery, New York, NY, USA, 2020.
[10] Digvijay Boob, Saurabh Sawlani, and Di Wang. Faster width-dependent algorithm for mixed packing and covering Ips. Advances in Neural Information Processing Systems 32 (NIPS 2019), 2019.
[11] Deeparnab Chakrabarty, Prateek Jain, and Pravesh Kothari. Provable submodular minimiza- tion using wolfe's 's algorithm. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 14, page 802-809, Cambridge, MA. USA, 2014. MIT Press.
[12] Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. Subquadratic submodular function minimization. Proceedings of the 49th Annual ACM SIGACT Sympo- sium on Theory of Computing, pages 1220-1231, 2017.

---

[13] Karthekeyan Chandrasekaran, Chandra Chekuri, and Shubhang Kulkarni. On deleting vertices reduce density graphs and supermodular functions. arXiv preprint arXiv:2503.0882. 2025.
[14] Karthekeyan Chandrasckaran, Chandra Chekuri, Manuel R. Tores and Weihao Zhu. On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimiza- fion. Algorithuss and Techniques (A (APPROX/RANDOM, 2024), volume 317 of Leibniz Interna- tional Proceedings in Informatics (LIPIcs), pages 9:1-9:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl Leibniz-Zentruum für Informatik.
[15] Moses Charikar. Greedy approximation algorithms for finding dense components in graph. In Klaus Jansen and Samir Khuller, editors, Approximation Algorithms for Combinatorial Op- timization, pages 84-95, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
[16] Moses Charikar. Greedy approximation algorithms for finding dense components in graph. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 84-95. Springer, 2000.
[17] Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1531-1555, 2022.
[18] Yizhou Dai, Miao Qiao, and Lijun Chang. Anchored densest subgraph. In Proceedings of the 2022 International Conference on Management of Data, SIGMOD '22, page 1200-1213, New York, NY, USA, 2022. Association for Computing Machinery.
[19] Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. Large scale density-friendil graph decomposition via convex programming. In Proceedings of the 26th International Conference on World Wide Web, WWW '17, page 233-242, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee.
[20] Werner Dinkelbach. On nonlinear fractional programming. Management Science, 13(7):492-
498, 1967.
[21] Michal Dobrogost. Solving Maximum Flow Problems in - cucave.net. http://www: /www. cucave. wwtp:eaaprs/mmmaaaaaaaeese
[Accessed 16-05-2025).
[22] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. R. Guy, H. Hanani, N. Sauer, and J. Schönheim, editors, Combinutorial Structures and Their Applications (Pro- ceedings Calgary International Conference on Combinatorial Structures and Their Applica- tions, Calgary, Alberta, 1969; R. Guy, H. Hanani, N. Sauer, J. Schönheim, eds.), New York, 1970. Gordon and Breach.
[23] Alessandro Epasto, Silvio Lattanzi, and Mauro Sozio. Efficient densest subgraph computation in evolving graphs. In Proceedings of the 24th International Conference on World Wide Web, WWW 11, page 300-310, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee.
[24] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(12))95-110, 1956.
[25] Satoru Fujishige. Lexicograptically optimal base of polymatroid with respect to weight vector. Mathematics of Operations Research, 5(2):186-196, 1980.
[26] Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
[27] Satoru Fujishige, Takumi Hayashi, and Shigueo Isotani. The
algorithm applied to submodular function minimization and linear programming. 2006.
[28] Satoru Fujishige and Shigueo Isotani. submodular function minimization algorithm based on the minimum-nove norm base. Pacific Journal of Optimization, 7(1):3117, 2011.
12

---

[29] A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD--4-171,
EECS Department, University of California, Berkeley, 1984.
[30] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combi-
natorial optimization, volume 2. Springer Science & Business Media, 2012.
[31] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Faster and scalable algorithms for densest subgraph and decomposition. Advances in Neural Information Processing Systems, 35:26966~ 26979, 2022.
[32] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to lexicographically op- timal base in (contra) polymatroid and applications to densest subgraph and tree packing. arXiv preprini Stti:::3000098877. 2023.
[33] Dorit Hochbaum. Flow best, fast and scalable: The incremental parametric cut for max- imum density and other ratio subgraph problems. In The 16th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management (KDIR 2024), Proceedings, November 2024. 17-19 November, 2024.
[34] Yufan Huang, David F. Gleich, and Nate Veldt. Densest subhypergraph: Negative supermod- ular functions and strongly localized methods. In Proceedings of the ACM Web Conference 2024, WWW '24, page 881-892, New York, NY, USA, 2024. Association for Computing Machinery.
[35] Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial al- gorithm for minimizing submodular functions. Journal of the ACM (JACM), 48(4)776 2001.
[36] Martin Jaggi. Revisiting Wolfe:
Projection-free sparse convex optimization. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, number in Proceedings of Machine Learning Research, pages 427-435, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[37] Stefanie Jegelka, Hui Lin, and Jeff A Bilmes. On fast approximate submodular minimization. Advances in Neural Information Processing Systems, 24, 2011.
[38] Patrick Møller Jensen, Niels Jeppesen, Anders Bjorholm Dahl, and Vedrana Andersen Dahl. Min-Cut/Max-Flow Problem Instances for Benchmarking. 2022.
[39] Haotian Jiang. Minimizing convex functions with rational minimizers. Journal of the ACM, 70(1):1-27, 2022.
[40] Yuko Kuroki, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Online dense subgraph discovery via blurred-graph feedback. In ICML, 2020.
[41] Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. A survey on the densest subgraph problem and its variants, 2023.
[42] Ling Li, Hilde Verbeek, Huiping Chen, Grigorios Loukides, Robert Gwadera, Leen Stougie, and Solon P. Pissis. Heavy nodes in a small neighborhood: Exact and peeling algorithms with applications. IEEE Transactions on Knowledge and Data Engineering, pages 1-16, 2024.
[43] Xiangfeng Li, Shenghua Liu, Zifeng Li, Xiaotian Han, Chuan Shi, Bryan Hooi, He Huang, and Xueqi Cheng. Flowscope: Spotting money laundering based on graphs. In AAAI, 2020.
[44] Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V.S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. Efficient algorithms for densest subgraph discovery on large directed graphs In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD '20, page 1051-1066, New York, NY, USA, 2020. Association for Computing Ma- chinery.
[45] Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa Vu. Densest subgraph in dynamic graph streams. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald T. San- nella, editors, Mathematical Foundations of Computer Science 2015, pages 472-482, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
13

---

[46] Kiyohito Nagano, Yoshinobu Kawahara, and Kazuyuki Aihara. Size-constrained submodular minimization through minimum norm base. In Proceedings of the 28th International Confer- ence on International Conference on Machine Learning, ICMI'11, page 977-984, Madison, WI, USA, 2011. 1. Omnipress.
[47] Ta Duy Nguyen and Alina Ene. Multiplicative weights update, area convexity and random coordinate descent for densest subgraph problems. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024.
[48] James B Orlin. A faster strongly polynomial time algorithm for submodular function mini- mization. Mathematical Programming, 1 18(2):237-251, 2009.
[49] Jean-Claude Picard and Maurice Queyranne. network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks, 12(2):141-15, 1982.
[50] Polina Rozenshtein, Nikolaj Tatti, and Aristides Gionis. Discovering dynamic communities in interaction networks. In Toon Calders, Floriana Esposito, Eyke Hüllermeier, and Rosa Meo, editors, Machine Learning and Knowledge Discovery in Databases, pages 678-693, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
[51] Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80(2):346-355 2000.
[52] Alexander Schrijver al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
[53] Kijung Shin, Tina Eliassi-Rad Rad,, and Christos Faloutsos. Corescope: Graph mining using k-core analysis - patterns, anomalies and algorithms. 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 469-478, 2016.
[54] Bintao Sun, Maximilien Danisch, T-H. Hubert Chan, and Mauro Sozio. Kelist++: A sim- ple algorithm for finding k-clique densest subgraphs in large graphs. Proc. VLDB Endow. 13(10):1628-160) 1640, jun 2020.
[55] Charalampos Tsourakakis. The k-clique densest subgraph problem. In Proceedings of the 24th International Conference on World Wide Web, WWW '15 page 1122-1132, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Commit- tee.
[56] Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guar- antees. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, page 104 112, New York, NY. USA, 2013. Associa- tion for Computing Machinery.
[57] Nate Veldt, Austin R. Benson, and Jon Kleinberg. The generalized mean densest subgraph problem, 2021.
[58) Nate Veldt, Austin R. Benson, and Jon Kleinberg. The generalized mean densest subgraph problem. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, page 1604-1614, New York, NY, USA, 2021. Association for Computing Machinery.
[59] Philip Wolfe. Finding the nearest point in a polytope. Mathematical Programming, 11(1):128- 149, 1976.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
All the claims made in the abstract and introduction are proved later on in the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of which algorithms are better in which contexts are ex-
plained.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificatiin, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
15

---

judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All proofs are given in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code for every single experiment is given in the supplementary section. All datasets are also provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way to accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
16

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All data is open access. The code base gives clear instructions on how to reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /atppp.cc/pbbit//ggaaa////deeeee
ssiiiisssscyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
All methods are explained details in the appendix or supplementary section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
17

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: All algorithms are deterministic, so they produce the same output on every run (so there are error bars).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The system specifications and resources were given in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
18

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Ehtngg.tte////arrrrr.c.ooooo///a
Question:
Answer: [Yes]
Justification: Yes, followed it far aware.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents work whose goal is to advance theoretical machine learn- ing and applied algorithms. The work is mostly theoretical, do not believer there many potential societal consequences of our work (unless used very nefariously) which we feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
19

---

The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: When we use other authors' implementation, code, or datasets, they are prop- erly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode cww.co/ccaao.oo datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
All datasets and code are provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
20

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Not involving crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Not involving crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: No LLM usage beyond basic writing and language editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
21

---

Please refer to our LLM policy (ftrer///berrng.cccc/otttrrororo for what should or should be described.
22

---

Table 2: Acronyms and abbreviations used throughout the paper.
Acronym
Full name
Brief description where used
Problem classes
SFM
Submodular Function
ming48CV [(S) for submodular
Minimization
DSG
Densest Subgraph
maX
[E(8]
Special case of DSS.
DSS
Densest Supermodular Set
maX5;9
(19)
for normalized, monotone super-
modular f.
USSS
Unrestricted Sparsest Submodular Set
min [S]
for (possibly monotone/negative) submodular f- (18) for (possibly monotone/negative) supermodular f.
((S)
non-
UDSS
Unrestricted Densest
max540 [S]
non-
Supermodular Set
MNP
Minimum Norm Point
minge ||>| over the base polytope (f)..
ADS
Anchored Densest Subgraph
Density with vertex penalties outside anchor set R. Bipartite ratio objective: w ((N(S)))\
HNSN
Heavy Nodes in Small Neighborhood
maximize
Algorithms
optimization terms
FW
Trolk (a.k.a. conditional gradient)
First-order method used to solve MNP B(f).
FW-MNP
Fujishige-Waid Woolf MNP algorithm
Specialized algorithm for MNP on submodu- lat/supermodular base polytopes. Accelerated first-order method referenced in re- lated work.
FISTA
Fast Iterative
Shrinkage-Threshollee
Algorithm
LMO
Linear Minimization Oracle
Oracle arg min Vh(2)) used by FW-type methods.
LP
Linear Programming
Used as baseline/alternative exact method. Name used in experiments for SUPER- GREEDY++.
IP
Iterative Peeling (SuperGreedy++))
Benchmarks
misc.
DIMACS
Center for Discrete Mathematics and Theoretical Computer Science
Classic min-cut challenge benchmark suite.
23

---

A Proofs
A.1 Proof of Lemma[1
Proof. Fix À and S V. Since x² B(f), we have
S(S) - (Slk 2 (xt 2)-
(1)
wES
The right-hand side of T minimized by taking S\ {u E V x S Aj.
Σ
A)
X) - x =(x) A|Sa|-
(2)
DESA
We claim that (Sx) f(Sx). Combining this with ! and 2 gives
S(Sx) - A|8x1 S(S) Alsk,
as desired.
To prove the claim, order V so that z;, S x S ... < 2 and define S, = {. U.). For some i, we have Sx S,, so it suffices to show (S;) = f(S)) for all i. This follows from [26 Lemma 7.4 (pp. 218-219, equations 7.12-7.15).
A.2 Proof of Theorem 12
Proof. (1) = (4)/()) Let f 2 + R. be a normalized submodular or supermodular function. We focus submodular functions for USSS; the supermodular case (UDSS) is analogous via negation.
Our goal is to compute the minimum norm point x* e B(f) using an oracle for USSS. We itera- tively build x by decomposing f into sequence of sparsest sets.
Initialize fo = f. At iteration S SCV. (S) U...U...I). Set x,, = ((.)))/\S for all v E St.
1, define S; the minimizer of f((8)/(S] over non-empty
After assigning nu for v S,, contract S, by defining:
(S4 = f((SUS)) - f((S)), VS C U..UU..
Repeat until S U...USS = V. This process requires at most n iterations since the S are disjoint.
Claim: The resulting vector is the minimum norm point in B(f).
Proof of Claim: Let be the vector constructed by the above process, where for each S, we set
To = A = [((S))/\5:l-
We now prove that x is the minimum norm point in B(f) by showing that x is the lexicographically maximum base of B(f). Recall that the lex-maximal vector corresponds the minimum norm point in polymatroid.
We proceed by induction on i show that for each any lex-minimal base x² E B(J) must satisfy x = A for all E S..
Base case (i 1): Since x² E B(f), we have
x² x'(S)) S f(Si) = A1|S1/-
But by construction, Fe = >1 for all u E S1, so xS1) = S1
Therefore, (S;) < (.))). In particular, there exists at least one E S₁ with 2t S A Since x= is lexicographically maximal, must have x; Aı for all St; otherwise, if any xy < \1 for u E S1, lex lex-maximality would be violated.
Induction step: Assume for j = =,,..., i, we have x; X for all v S).
Consider S1+1. Since x² B()), we have
U x *01 .... U S S U S.1))
24

---

Using telescoping sums, this becomes:
f(S, U...U...U.H.. E h=1
-((1 U... ((..U...U...))) Shl-
Thus,
x0(+)) = (S1 U... U (5 U.. S A
where the induction hypothesis gives x (S] U ... U.) = E hm1 Sn|Sk]
Hence, the average value of x over S1+1 most A141. Therefore, there must exist least one e E S with x S Xc+1-
Since x" is lexicographically maximal, must have x. A4t1 for all E S otherwise, if any 2y < A4t1, lex-maximality would be contradicted.
By induction, x, X for all S; and all Hence, x' = Thus, the constructed vector is the lex- ea--mai base of B(f), which is also the minimum norm point.
(4) + (5): Immediate from duality. If f is supermodular, ff is submodular. The sparsest sub- modular set problem becomes densest supermodular set under negation. Hence, solving USSS is equivalent to solving UDSS on -f.
(5) + (3): Given a normalized supermodular function f. define:
C max max((](5))),
SCV
and set g(S) f(S) + C|S). Then g is normalized, monotone, non non-negative, and supermodular, Furthermore,
g(S) arg max f(S) SCV S
arg max SCV SS|
as adding a constant to all sets gains affects neither the maximizer (as it just shifts the sparsity ratio). Thus, UDSS reduces to DSS.
(3) + (2): This reduction is classical (e.g.. 20 34 33)).
Given monotone, normalized, non-negative
supermodular f. iteratively refine maximizer of f(S)/[S) using SFM. Initialize So V, \ = ((oos Sol. At iteration i, solve:
S, = arg min (A,15) f(S)),
SCV.8y0
using SFM. Update A4+1 ((S.)/|S)). Iterate until Ac|SA| f(Sx) Since the sequence of X decreases and if is normalized, the process terminates in at most steps. The last S maximizes (S)/|S)) solving DSS via SFM.
(2) (1): Given f, compute the minimum-none point x' B(f). By Lemma I1 the set
So = {u E V x S 0}
minimizes f(S). Thus, SFM can be reduced to computing x", completing the reduction.
A.3 Proof of Theorem
Proof. (1) This result follows directly from the analysis in |II
(2) We generalize the argument of [TT.. Without loss of generality, reorder indices that d1 S
f2 < < fn. Consider the set $ [ (1,..., that minimizes f(i))/i over i 1,...,
Let A denote the density of the sparsest submodular set, i.e., X = mins [S)/[S) Define & as the smallest index satisfying:
(CI) Pt+1 > X",
(C2) ZK+1 2b 2 +
25

---

From 11 we have the key inequality:
1- 1
(i1+1 2.(((D)) =((D) 6².
Let t = {i [k] f > H²H. Observe:
Σ
=
Σ (x)
1E|K|
x i.g
k
se[k]
10 + ke,
where the second inequality follows since (C2) fails for all i < k with &; > X². fx
Since dx+1
T follows that
f((+)) - [((k)) S kE,
and therefore,
S(()) k
[(( + ke
h
Σ EElA) SA &. + ΣiE(H):e G3 + the
k
x A= 1) X + 2ke X + 2
k
(3) The argument parallels that of (2). We now reorder indices so that o1 2 82 2.
2 Eng and
select the set $ = -11] == f1....,,) .) that maximizes f(il)//
Let X = ma f(5)/(S). Define k as the smallest index satisfying:
(C1) $K+11 < X"
(C2) Sx Sk+ 2 +-
Using the analogous inequality from 11
R-1
(+1)) f((D) s e?.
Let t = (i E [k] fr < /
We have:
Σ
=
Σ (0;-
<x
iE[k]:B, <
i.5
Xt
k
iE[R]
x ke, where the second inequality holds since (C2) fails for all i < l with 2, < X
Since -z-1- ix
E. deduce:
$ ((R) f(b)) S ke,
and consequently,
f(())
b((k)) KE
k
h
Σ [M St + Eie(M] 33 - ke
k
(k: - t) + Art 2kk
X- - 25.
k
26

---

A.4 Proof of Theorem 13
Proof. Our analysis follows the approach of Harb et of laggi (3)..
32 based on the Trank-Wolff framework
Jaggi's Frank-Woo Framework. The Frank-Wolfe algorithm is a classical method for minimiz- ing convex function over convex set. While its convergence has been known since [24]. Jaggi's analysis [6)] offers a modern, simplified treatment that expresses convergence rates in terms of the so-called curvature constant of the objective function.
Definition (Curvature constant), Let C B be a compact convex set, and : D - convex, differentiable function. The curvature constant C% is defined as
C sup E. - 7 y y=a+)(s-a))
(h(y) h(()) (y - J, Vh(x))).
One advantage of Jaggi's formulation is that seamlessly extends to approximate versions of Frank- Wolfe, where the linear minimization oracle (LMO) may only be computed approximately.
R. an e-approximate linear minimization Definition 18 (Approximate LMO). Given h oracle returns & E DD satisfying
(5, Vh(w)) (s", Vh(w)) +
where s" arg min Vh(w)) is the exact LMO.
Jaggi's main result shows that if, iteration k, compute approximate LMO with error most 8Ch. then the Frank- Wolfe algorithm converges with only constant-factor slowdown. k+2
Lemma 19 (36 Define the duality gap at x E D as
g(x) = max q. Vh(x)).
TED
If we use 8C2. aaprrxxmmate LMO at iteration k. then after K iterations there exists an iterate x: (R). with k+2
K, satisfying
7Cp K + (1 6))
g(x(h)) <
Applying SUPERGREEDY+* FW-MNP. Our goal is analyze SUPERGREEDY++ for the Minimum Norm Point (MNP) problem on the base polytope of normalized submodular or supermodular function f: 2V Specifically, we consider
h(x) = || D B(f).
For this quadratic objective, the curvature constant admits simple form:
Lemma 20.
C₁ max ||s dlI2. s.dEB(f)
Proof. This follows by substituting h(z) attained when I, s, and d are chosen to maximize |s - d| yielding the claimed expression.
||01 into the definition of C₁. The supremum is
Next, note that we can, without loss of generality, assume is supermodular function. This is because submodular and supermodular MNP problems are duals of each other under negation:
Lemma 21. Given a normalized submodular funncttooon g, define f = -g. If we can solve the MNP problem for i.e. find & E B(f) such that
|| < (g. 3) + 5 for all q E B(J)
then we can obtain corresponding solution x' - B(g) with the same guarantee:
|| < (g. x²) + for all q B(g).
27

---

Proof. Given let f = 99. Since f is submodular, compute F E B(f) such that
| - (q, + for any B()).
Define x' = ④. Observe that q E B(f) if and only if -q E Bgg). Specifically, g(V) = f(V)
implies VV f(V) g(V). and (()) 2 f(S) and only if -Q(5) -f(S) = g(S). Thus,
x' E (g) and, for any (g),, since - - E B(f),
| 11 11 s (-9. x²) + (q, +
Approximate LMO in SUPERGREEDY++. Algorithm 2 reframes SUPERGREEDY++ as "noisy" Frank-Wolfe algorithm. At each iteration, SUPERGREEDY++ computes a descent direction using the PEELWEIGHTED subroutine. While this is not exact LMO, Harb er al. [32 showed that approximates the LMO to within an error term that decays with
Lemma 22 [32 Let 9t denote the exact LMO direction at iteration and dg be the direction returned by PEEL WEIGHEIGHTED. Then,
(st, (st,bit-1) bit S (de, + n L flu V {uz)²
This shows that at iteration t. SUPERGREEDY++ uses
ni Enev flu V V {u})²
approximate LMO error. Normalizing by the curvature constant Cn, this corresponds to
8 Evev f(u V {u))
C₁
Convergence of SUPERGREEDY+* Substituting this approximation quality into Jaggi's conver- gence lemma, we find that after T iterations, there exists an iterate (x) with
(ax(0) S T
7Ch (1+
(1 T
7Ch n Ewev slu V {u))2
O
Simplifying, this gives
g (xx
7
Ch Ch+n E f(u V fu)}p]
T
To ensure (k): E2, it suffices choose
== ( ( f(u V
(w)))= =0 maxx,deB(1) d|3 + EnEv f(u V {u})²
22
The Ô polylog term comes from the fact that use learning rate (in SUPERGREEDY++) of
1/(t + +1) instead of 2/(t 2).
28

---

Algorithm Peeling Weighted++
I: function PEELWEIGHTED (f 22 - R, w E R)
2: Initialize: d(u)) for all
3: Si +-1 V
4: for j = to n do
5: 0j arg ma (w(r) + f(v) S u)
6: d(u,) - f(e S - U5)
7: Sy+1 Sy \ 1
8: end for
9: return
Algorithm 2 SuperCreedy++ For Minimum Norm Point
function SUPERGREEDY++ 2 R, T)
2: Initialize: (0()) (u) = 0 for all u E V
3: for 1 to T do
4: de + PEELWEIGHTED (t - (t-((-
1idd d, 5: x(() (1- 41 (t(
241
6: end for
7: return (kk), for 0 S k < T, that minimizes || - max (9,
29

---

B A New Flow-Based Algorithm for HNSN
Recall the HNSN problem from the introduction. Since the function f( [N) is submodular, HNSN is special case of the weighted USSS problem. Ling al. further reformulate the problem over the left vertex set L, defining the function N 24 I by N(S) = {u R ō(v) C S} where 8(v) denotes the set of neighbors of c. Under this formulation, the problem becomes that of maximizing w(N(S)))\S) over non-empty subsets S S L. We adopt this viewpoint our implementation.
We adopt the density improvement framework from the proof of Theorem 12 We begin by setting So L and define the function f 2 Rzu by f(S) w(N(S) where N(S) {v R 6(v) [ 5}- We initialize the density parameter as A = f(So)/|Sol, and then minimize the function S| S(S) over subsets 5 S L. Let S1 be the minimizer of this objective, and set A = f( \ This process is repeated iteratively. We will show how each minimization step be performed using single min-cut (or, equivalently, max-flow) computation. Algorithm summarizes this iterative process.
Algorithm Density Improvement via Min-Cut
Require: Left vertex set I, right vertex set R, weight function w R - Rz0, neighborhood function 5 R 2L
1: Define N(S) {u E R 5(v)
_ S)
2: Define S(S) + (HEN(S) w(v)
3: Initialize So < I., I.,51
4: Compute Ao f(5o)/|So)
5: repeat
6: Define ( - A -
7: Find St C minimizing ((S) via min-cut or max-flow computation
8: Compute X [(S))
9:
t ++1
10:
until S
11:
return St
We now show how to minimize Φ(5) A|5k f(S) for fixed X.
Theorem 23, We can minimize ((S) ASl< - ((5) for a fixed X using single minimum s-t cut.
Proof. Construct a directed graph G ((s, U L. R. E) as follows:
Add an edge from to each E L with capacity X.
For each edge (u, v) with L, R, if E 8(u), add edge - with capacity
Add an edge from each R to with capacity w(v).
Consider an s-t cut (A, B), with s E A, t E B. Define the subset = L n B, i.e. the left-hand vertices that are cut off from by the cut. We compute the total capacity of the cut.
The cut capacity consists of:
1. Edges from to S, each with capacity X, totaling A|S]-
2. For each E R, the edge
is only cut if there exists any of its neighbors in S, i.e., 5(v) n S * (,, meaning E N(S) are not cut to t. The edge - contributes w(R) (S)) to the cut.
Thus, the total capacity is:
ISSk w(Rt) w (N((S)
To minimize @(S) = A|S) we observe that this is cquivalent (up to constants) to minimizing S|S| + ((R) - (VV(((V) since adding w(R) R) from both sides doesn't change the argmin. Hence, the minimum s-t cut yields subset that minimizes ((S). as claimed.
30

---

C HNSN Experiments Results
Problem Definition. Recall the HNSN problem from the introduction. Since the function f(S) = [S) is submodular, HNSN is a special case of the weighted USSS problem. Ling et al. further reformulate the problem over the left vertex set L, defining the function N 2 + R by (SS) {u E R d(u) _ S} where d(v) denotes the set of neighbors of v. Under this formulation, the problem becomes that of maximizing ((N(S))\\S] over non-empty subsets S C L. We adopt this viewpoint in our implementation.
Algorithms. We compare against the six baselines of Ling el al. 42). and introduce a new flow-based algorithm (detailed in Appendix BB. In total, we evaluate ten algorithms: IP (SUPERGREEDY++) FW -oole), FW-MNP (Fujishige-Wan) Wolfe Minimum Norm Point Al- gorithm), FLOW (our new flow-based method). CD (ContractDecompose, 422), LP (Linear Pro- gramming, solved via Gurobi with academic license), GAR (Greedy Approximation, [42 GR (Greedy, 42 FGR (Fast Greedy, (42), and GRR (GreedRatio, (5). The first four are our imple- mentations; the remaining six follow Ling et al." 's code [2
Approach. For the three iterative algorithms-IP, FW, and FW-MNP-W- run each for 100 iter- ations and plot the following: (1) the time taken per iteration, (2) the best density found up to that point. We report only the final runtime and the density achieved termination for the remaining algorithms. In the runtime comparison, we include only those algorithms that (1) terminated within the time limit and (2) successfully found the optimal solution.
Our implementation of IP is custom and includes an optimized method for computing marginals. It maintains heap over set S C I. of vertices to peel from and set S C R where 8(v) S for all V E S". Once a vertex & E S is peeled, all its neighbors in R are removed from the data structure S' This allows each iteration be implemented in Om log n) time, where and n are the number of edges and vertices in the bipartite graph, respectively.
the datasets used for the HNSN problem, following the benchmarks introduced by Ling et al. [42]. Each dataset is represented as weighted bipartite graph with left vertices L., right vertices R, weights on the right vertices w : R - IR. 12 and edges F. The graphs are derived from diverse real-world domains, including recommendation systems (e.g., YooChoose, Kosarak), citation networks (ACM), social networks DNotreDame, IMDB, Digg), and financial trans- actions (e.g., E-commerce, Liquor). The datasets exhibit wide range of sizes, with up to 106
Datasets. Table Moolersummrrize
vertices and ~ 2 x 10 edges.
In total, for all algorithms and all datasets, we request 4 CPUs per node and 35G of memory per experiment. All algorithms were given a 30-minute time limit per dataset, after which they were marked as Time Limit Exceeded and given blank values in the plots below.
Resources:
Discussion of HNSN Results. See Figure 2 for all plots. For each dataset, the top plot shows the final density found by each algorithm (the higher, the better), and the bottom plot shows the time each algorithm takes on a log-scale (the lower, the better). We exclude algorithms with a time limit (more than 30 minutes) if they give suboptimal answer. Across all datasets, the Frank-Wole (FW) algorithm and Woolfee Minimum Norm Point (FW-MNP) algorithm consistently emerged as the fastest to converge. In nearly every case, FW-MNP outperformed FW, achieving the best solution quality in the shortest time, with only a single dataset where FW was slightly faster. Relative the six baselines from Ling et al. 42 these methods achieved speedups ranging from 5x to 595x.
Our new flow- algorithm and SUPERGREEDY++ (IP) typically followed, ranking third and fourth in performance across datasets. Figure Ta shows a particularly striking example, where on the YooChoose dataset, FW-MNP achieved 595x speedup over the best previously published baseline. In this instance, all algorithms converged to the correct final density, except for GRR, which terminated at suboptimal solution and was therefore excluded from the runtime comparison.
In particular, the algorithms GRR, GR, GAR, and I.P frequently encountered difficulties, either due to slow performance (time limit exceeding) or convergence to incorrect solutions. These results underscore a recurring insight consistently observed across our experiments: universal solvers such as FW-MNP and FW, originally developed for broader optimization tasks, can significantly outper- form specialized heuristics when applied to specific problems like HNSN, provided they are used within the proper conceptual framework that we have outlined.
31

---

Datamet: dica
Datiment: ecommarce
Carddt
15/0ustim ofrator Wwwph Seuree Set Sertect Lng Scaudd
10 Lunnrine clinhho Whin fannd Spares: Set Serted und Log C00
112
(a) digg. LP GRR Time Limit Exceeded.
ecommerce
Dataset: frukhut
Dataset Equor
6-17
197h www Mither Pa Spurce St Sateel ant Seald
BC of Mittors Whit fos Spunde St: Batad Lot Scald
5
(c) fruithut. GRR Suboptimal Solution.
(d) liquor. GRR & GAR Suboptimal Solution.
(c) ACM
connectious
(g) foodmart
(h) imdb
kosarak
ii NBA
32
(k) notredame
(1) yoochoose
Figure 2: HNSN results across 12 datasets.

---

D Min s-t Cut Experiments
Problem Definition. We next evaluate our algorithms on the classical Minimum s-t Cut prob- lem, a fundamental task in combinatorial optimization with widespread applications. Specifically, the Minimum s-t Cut problem can be framed as minimizing the normalized submodular function g(S) (8( U {(}]] }ō({s})] over subsets S C V \ {s,t), ensuring that any feasible solution corresponds to valid s-t cut. Within this formulation, the Minimum s-t Cut problem becomes an instance of Submodular Function Minimization (SFM), and thus naturally fits within the unified framework established in this paper. This connection allows us to apply universal solvers, such as SUPERGREEDY++, Trank-Woffe and Wolfe's ' Minimum Norm Point algorithm, this classical combinatorial problem.
Algorithms. We evaluate three iterative algorithms-Frande Wolfe (FRANKWOLFE), Fujishige- Wolfe Minimum Norm Point (FW-MNP), and SUPERGREEDY++ (SUPERGREEDY) the Min- imum 8-f Cut problem. For each instance, we also compute the exact minimum cut value using standard combinatorial flow-based methods (Edmonds Karp algorithm), serving ground truth. This allows us to assess both the solution quality and runtime efficiency of the optimization-basee approaches relative to the exact combinatorial solution. We run SUPERGREEDY+++ for 1000 itera- tions on each dataset, 10,000 iterations for FRANKWOLFE, and 500 for FW-MNP.
Marginals. The iterative algorithms leverage the marginal g(v|S - v) g(S) g(S - v): the difference in the cut value when moving from the source partition to the sink partition. It follows that g - v) is realized by deg" (w) deg (v) where deg (v) is the (weighted) degree of v to all vertices u E SU {s} and deg (v) is the (weighted) degree to all vertices w E V (s)).
Datasets. Our evaluation spans two groups of datasets. First, we consider four classical benchmark instances from the first DIMACS Implementation Challenge on minimum cut [21]. known for their small size but challenging cut structures. Second, to assess scalability and robustness, we include a large-scale dataset family, specifically the B BVZ-SAWTOOTH instances 38), which consist of 20 distinct minimum s-t cut problems. Each instance contains approximately 500,000 vertices and 800,000 edges, providing test of algorithmic scalability.
Resources: In total, for all algorithms and all datasets, we request 4 cpus per node, and 40G of memory per experiment. All algorithms were given a 25-minute time limit per dataset (all algorithms finished within this time, and there was no time limit exceeded). We mark with a vertical dotted line the time for the flow algorithm to find the correct minimum cut.
Discussion Minimum s-t Cut Results. Full results are provided in Figure 3 and Across all datasets, SUPERGREEDY++ was consistently the fastest to approximate the minimum cut, of- ten by large margins over exact flow-based methods, FW-MNP, and FW, In 16 of 24 instances, it found the exact min-cut rapidly. In the remaining cases, its solution was within 1.000023 the optimum after at most 500 iterations, always converging before the exact flow solver. A notable example is the B WZZ-SAWTOOTHL instance, where SUPERGREEDY++H converges orders of magni- tude faster (Figure Tc). This strong performance parallels its success in dense subgraph problems, where it efficiently finds high-quality solutions but can slow down near the optimum. Combining SUPERGREEDY+++ with flow-based refinement remains an interesting direction for future work. In- terestingly, while FW-MNP and FW excel HNSN, they both underperform here, underscoring how problem structure affects solver efficiency.
33

---

PuRnAris The undbetC
20/00
3,000
20.80
(a) sawtooth16
(b) sawtooth15
Mis Out Entirers Time -Bvisee))
Zut Criras ad Trme sustact
Bast
May Carsidte
(c) sawtooth3
(d) sawtooth4
(c) sawtoothO
( sawtooth1
(g) sawtooth2
(h) sawtooth5
sawtooth6
(i) sawtooth7
(k) sawtooth9
()) sawtooth10
Figure 3: Min-Cut vs Wall Clock Time (Part 1).
34

---

Thoc sarteid
10.00
00:400
21080
(a) Bawtooth8
(b) sawtooth14
Cit Enfinees Time 19N000911
Min Car Calmara Tine mda
Bast
East May Cerosber
(c) sawtooth11
(d) m50
(c) sawtooth12
sawtooth13
g sawtooth17
(h) sautoothh8
sawtooth19
m10
(k) m30
Figure 4: Min-Cut vs Wall Clock Time (Part 2).
35

---

E Densest Subgraph Problem Experiments
Problem Definition, Given a graph G = (V, E), find a vertex set 0 + S C V maximizing [[SS)
Algorithms. We evaluate seven algorithms- Frank- Wolfe (FRANKWOLFE, 19)). Fujishige- Wolfe
Minimum Norm Point (FW-MNP), and SUPERGREEDY++ (SUPERGREEDY, 9)) FISTA BI,, RCDM 47), the incremental algorithm on the density improvement mechanism, but using push-relabel flow.
[R], and new push-relabel flow-based algorithm based
Table 3: Summary of Densest Subgraph Datasets.
Dataset
# Nodes
Edges
close-cliques
3,230
95,400
com-amazon
334.863
925,872
com-dblp
317.080
1,049,866
com-orkut
3,072,441
117,185,08
disjoint_ _unont__nninaaaa
35,900
16,8888800
roadNet-PA
1,088,092
3,083,796
roadNet-CA
1,965,206
5,533,214
Datasets. Table 3 summarizes the 7 datasets used for the densest subgraph experiments, two of which are synthetic from [31].
Resources: In total, for all algorithms and all datasets, we request 4 CPUs per node and 40G of memory per experiment. The only exception is for the dataset orkuor where we requested 100G of memory. All algorithms were given a 30-minute time limit per dataset; otherwise, they were marked as having exceeded the time limit.
Discussion of Densest Subgraph Results. Figure presents the evolution of subgraph density over time for all datasets in the classic densest subgraph problem. Each plot includes the full runtime and zoomed-in view of the first 20% execution time to highlight early algorithm behavior.
Some literature densest subgraph algorithms has lacked consistent evaluations, with many works often reaching conflicting conclusions about which algorithms are the most efficient. We aim to con- tribute more nuanced and systematic perspective on performance evaluation. We hope future work adopts similar care when assessing and comparing algorithms for the densest subgraph problem.
Memory Comparison: Flow-based algorithms consistently delivered strong performance. partic- ularly when paired with the iterative density-improvemect framework of Veldt et al. [34] and Hochbaum (33). However, significant practical drawback is their memory usage: our exper- iments, flow-based methods often consumed 2-3x x more memory than other approaches. This over- head stems from the substantial bookkeeping constructing and maintaining the flow network.
Moreover, flow-based methods incurred noticeable delays during the initial stages due to the cost of constructing flow networks on large graphs. While Hochbaum employs the Pseudoflow algo- rithm, we observed comparable performance using standard Fush-Relabel solvers within the same density-improvemeen framework, reaffirming that the primary source of speedup lies in the iterative framework itself rather than the specific max-flow implementation.
That said, flow-based methods are not universally applicable. In problems such as the generalized p-mean Densest Subgraph, no known linear flow formulations minimize objectives like A - f(S) for arbitrary supermodular functions. In such cases, algorithms like SUPERGREEDY+#: Frank- Wolfe, and the Fujishige-Wood Wolfe Minimum Norm Point algorithm (FW-MNP) remain the only viable choices, as they operate purely via oracle access and require no specialized structure.
Convergence to (1 c) approximation: For fast convergence to near-optimal solutions, convex programming- based methods were clear standouts. Across nearly all datasets, RCDM consistently reached (1 >-aaprooximaee dense subgraphs in just few iterations. It was closely followed by FISTA and SUPERGREEDY++, which also showed rapid convergence and high-quality intermediate solutions.
However, is essential to note that RCDM and FISTA rely on a projection oracle from 31 which may not be available for generalized objectives (e.g., p-mean Densest Subgraph). In contrast, Su-
36

---

PERGREEDY++ maintains its effectiveness without requiring such oracles, making it more broadly applicable.
On the other hand, Frank-Wolfe and Fujishige-Wolfe's FW-MNP Algorithm often required thou- sands of iterations to achieve reasonable approximation and were generally outperformed by other methods. While their theoretical underpinnings are strong, their practical convergence to high- quality solutions is often prohibitively slow.
Convergence to the optimal solution: When the goal exact optimality, flow-based meth- ods paired with the innrovvmemt framework outperformed all other algorithms by wide margin. Even though convex programming methods like RCDM, FISTA, and SUPERGREEDY++ rapidly approached near-optimal values, they often stalled and required hundreds of iterations to fully converge to the exact solution on some datasets.
In contrast, the flow-based approaches often converged to the optimal solution orders of magnitude faster, especially on mid-sized and large graphs. Notably, this speed is not consequence of the spe- strategy, which efficiently reduces
cific flow algorithm used but instead of the the problem to a sequence of min-cut instances.
Thus, flow-based methods remain the most effective choice for applications where exact solutions are necessary, provided memory usage is manageable and suitable flow reduction exists.
General Takeaways: Our experiments highlight a few key insights:
1. Flow-based algorithms remain among the most potent tools for the exact densest subgraph discovery, especially when integrated with iterative frameworks, but they require significant memory and do not apply to generalized objectives.
2. Convex optimization methods like RCDM and FISTA converge rapidly high-quality ap- proximate solutions, making them ideal for problems with projection oracles and when approximate results suffice.
3. SUPERGREEDY++ offers a strong balance of speed, quality, and generality, consistently performing well across both real and synthetic datasets and requiring specialized prob- lem structure.
4. Finally, algorithm selection should be guided by the problem setting: whether exactness is required, whether flow reduction exists and whether projection oracles are available.
37

---

Denaty Cleck MA
Dera vo recdret
144
(a) roadnet_CA
(b) roadnet. PA
orket
30
330
30
Zocmadi
312
200
10
(c) wOw. 2om.amazon
(d) com_orkut
(e) disjoint iilajoint.union.oom www.unniiiooooto www.suuunooonnuueeeeeeeeeee cliques
(f) close_cliques
g com_dblp
Figure 5: DSG density time
38

---

F Generalized p-mean Densest Subgraph Experiments
Problem Definition. Given a graph
E), find vertex set 0 * S C maximizing the 1/p
generalized density (15 E
Algorithms. We evaluate three algorithms Frank-Wolfe (FRANKWOLFE), Fujishige-Won Wolfe Mini- mum Norm Point (FW-MNP), and SUPERGREEDY++ (SUPERGREEDY). All algorithms are imple- mented in C++.
We adopt the approach from [58] noting that maximizing the objective is equivalent maximizing /(S)/S)), where ((S) Eves (eg which is supermodular. Peeling of any vertex affects the denominator equivalently; hence, we act greedily with respect to the numerator. The marginal cost of peeling a vertex v from S is then given by
Marginals.
[(v|S - = f(S) - J(S v) = deg (v) +
Σ (E6g(u)
(degs(u) (degs (u) 1)
where (5( denotes s's neighbours in S.
Table 4: Summary of Generalized p-mean Densest Subgraph Datasets.
Dataset
# Nodes
# Edges
close-cliques
3,230
95,400
com-amaze amazon
334,863
925,872
com-dblp
317,080
1,049.866
roadNet-PA
1,088,092
3,083,796
roadNct-CA
1,965,206
5,533,214
Datasets. Table summarizes the 5 datasets we used for the generalized p-mean Densest Subgraph experiments. Note that these are subset of the datasets used for DSG. We consider four values p E {1.1, 1.25, 1.5, 1.75J.
Resources. We request 4 CPUs per node and 40G of memory per experiment across all algorithms and datasets. Each trial is given 30-minute time limit; none exceeded this limit.
Discussion of generalized p-mean Densest Subgraph Results. Results for all datasets are pre- sented in Figures|ojto [O] We plot the best density found against wall-clock time, and, as in previous sections, each plot includes both the full runtime and zoomed-in view covering the first 20% of ex- ecution time. Overall, we find that SUPER GREEDY++ generally achieves the highest density within the allotted time and tends to converge more quickly than the other algorithms.
On the close_cli wwwccllieesseecec ques dataset, however, FW and FW-MNP demonstrate stronger early-stage per- formance, reaching the maximum density faster than SUPERGREEDY++ though the latter eventu- ally converges the same value. By contrast, SUPER ++ often converges within the first few iterations on real-world instances, while the other two algorithms trail behind. Relative perfor- mance between FW and FW-MNP varies, with each occasionally outperforming the other.
We also observe that increasing the value of p in the generalized objective improves the performance of both FW and FW-MNP, whereas SUPERGRERDY remains largely unaffected. In fact, for all values of p considered, both FW and FW-MNP show improved performance compared to the classical Densest Subgraph case (p- 1).
(a) 1.1)
(b) (0=1.25)
(p=1.5)
(d) (p=1.75)
Figure 6: DSS density over time close_cliques
39

---

(a) (p=1.1)
(b) 1.25)
(c) (p=1.5)
(d) (p- (p=1.17 1.75)
Figure 7: DSS density time
(a) (p=1.1)
(b) 1025))
(c) (p=1.5)
(d) (p= 1.75)
Figure 8: DSS density over time com_dblp
(a) (p=1.1)
(b) (p=1.25 1.25)
(c) (p=1.5)
(d) (p= 1.75)
Figure DSS density over time roadnet.pa
1.1)
(p=1.25)
1.25)
(p=1.5)
(d) (p=1.75)
Figure 10: DSS density over time roadnet.co ca
40

---

G Anchored Densest Subgraph
Problem Definition. Given graph G = (V, E) and a set S V, find a vertex set 0 + $ maximizing - (ega
Algorithms. We evaluate four algorithms Frank- (FRANKWOLFE), Fujishige- -oolf Wolfe Mini- mum Norm Point (FW-MNP), and SUperGreEDY** (SUPERGREEDY), and the flow-based algo- rithm by Huang al. 34 The authors' code implemented in Julia, re-implement all
algorithms in C++
Marginals. Similar to the generalized p-mean DSG, we recognize that maximizing the objective can be achieved by acting greedy with respect to the numerator where [E()] supermodular, and the degree sum is modular as it's with respect to G. Hence, the objective is supermodular. The marginal cost of peeling v is then
f(u|S v) deg (v) (ug
Datasets. We reused the base graphs from our generalized p-mean Densest Subgraph Experiments, summarized Table These are the initial graphs given, for which anchor sets R are created via random walks.
Generating Random R. As in we generate R with the following process: first, we sample 10 seed nodes from the of vertices uniformly random. Next, using their 2-neighborhood, sample more nodes using a random walk until the total number of nodes R are 201, and mark that as R.
Resources: In total, for algorithms and datasets, we request CPUs per node and 40G of memory per experiment. All algorithms were given a 10-minute time limit per dataset (all algorithms finished within this time, and no time limit was exceeded except on one dataset for the flow-based algorithm).
Discussion of Anchored Densest Subgraph Results. Figure 11 summarizes the results for an- chored densest subgraph. The top plot shows results over the entire runtime, while the bottom plot zooms in on the first 20% to highlight early iterations. For each dataset, we plot the density of the best-anchored subgraph found against wall-clock time.
Across all experiments, SUPERGREEDY++ ++ consistently delivered the best performance, achieving the highest densities in the shortest time. It followed by FW and FW-MNP, which ranked second and third overall, though their relative performance varied across datasets- FW often had the edge over FW-MNP, but not uniformly. The flow-based method, FLOW, performed significantly worse on most datasets (with the notable exception of com amazomzz)). This underperformance may be attributed high variance in edge capacities within the flow network, which cause the algorithm to stall when attempting to push flow efficiently. In future work, it is worth studying the performance of flow algorithms in the weighted case, where such capacity imbalances are pronounced or may offer new opportunities for optimization.
41

---

Derilty vs and Clock Time con arreon
Denalyy tua Coock Time 00MC
(a) com_amazon
(b) close_cliques
(c) roadnet_CA
d roadnet PA
Density som_dblpp
WelC Sc4 Time
com dblp
Figure 11: Anchored density over time 42

---

H
Contrapolymatroid Membership Experiments
Problem Definition (CM), Given a supermodular function f 2 - and arbitrary vector y e RIV, determine if y E B(f).
Approach. The problem can be reduced to an SFM instance by recognizing that -S(S) is submod- ular, hence (s)) f(S) is also submodular. We minimize y(5) ((S) answer the membership question. It is more convenient to interpret this as maximization of f(S) USS), whose value we plot; y is then NO instance iff f(S) ySS) > 0.
For our experiments, we consider undirected graphs G = (V, with f(S) [E(S), SCV.
31 (Theorem 4.4) showed that vector b E B(f) if and only if there exists a vector E R such that the pair (z, b) satisfies the dual of Charikar's s densest subgraph LP [16]. Such a vector b corresponds to YES instance of the Contrapolymatroid Membership (CM) problem. Small perturbations to b can then be used to generate arbitrarily hard NO instances.
Generating Query Vectors. Harb et al.
(V, F), we construct feasible vector b E B()) by orienting edges. We begin by computing the exact densest subgraph using PUSHRELABEL. For each vertex - vertex set of the densest subgraph-we set 6, = A= where X is the maximum density. Harb et al. [31] (Theorem 4.1) show that such assignment in S" For edges not entirely contained in S we assign value of 0.5 to each endpoint if both lie outside S* and a value of the endpoint outside S otherwise.
Given graph G = (V.
always realizable via some orientation of the edges
To generate non-trivial NO instances (i.e., where x(V) = f(V)), we perturb the vector as follows: select two vertices 5 and & S then set by bu and bw +- b e, where is the perturbation magnitude. This results in
x x(S)) = |S - = (E(S) - [[("))
violating the contrapolymatroidd inequality for least the set S
In our experiments, we reuse the generalized p-mean DSG setup with p = 1, using the supermodular objective f(S)= = E' deg)(v). Note that [E(S) - y(S) > 0 if and only if Eves degs (v) 2y(S) > 0. We maximize and report the latter expression, which is always at least 22, with the lower bound attained when 5= S*.
Algorithms. We evaluate three Sagorithms-FFann-Wolll (FW), Fujishige- Wolle Wolfe Minimum Norm Point (FW-MNP), and + (SUPERGREEDY). All algorithms are implemented in C++.
Datasets. We reuse the datasets summarized in Table 4 We generate four increasingly difficult NO instances for each dataset with perturbation magnitudes E {12, 6, 1, 1e-1).
Resources. In total, for all algorithms and all datasets, we request 4 CPUs per node and 40G of memory per experimmntt All algorithms were given a 30-minute time limit per dataset (all algorithms finished within this time, and no time limit was exceeded).
Discussion of Contrapolymatroid Membership Results. Figures 12 16 summarize the results. An algorithm detects a NO instance when its value climbs from 0 to non-zero value. The CM results continue the observed trend: SUPER + performs strongly in general but is outperformed by FW and FW-MNP on CLOSE_ CLOSEECLIQUES, where SUPER fails to identify NO instances until the perturbation sufficiently large (e 2 6), and even then, does so more slowly. For all other instances, SUPER +REEDY++ is usually the first-am and frequently the algorrth to identify NO instances, often outpacing FW and FW-MNP by a wide margin. SUpErGREEDY++ also tends to find larger values, though this is irrelevant for CM. As expected, performance improves with larger=. E.
This strong empirical performance of S is particularly surprising given that Con- trapolymatroid Membership was the original motivation for studying submodular function mini- mization, and FW-MNP has historically been regarded as the algorithm of choice-making it espe- cially noteworthy that combinatorial method like SUPERGREEDY++ outperforms it so consistently across all but one dataset.
43

---

(a) (5=1e-1)
(b) (E=1)
(c) (==6)
(d) (s=12)
Figure 12: Contrapolymatroid Membership Function Value time close
(a) (5=1e-1)
(b) (s=1)
(c) (==6)
(d) (s=12)
Figure 13: Contrapolymatroid Membership Function Value over time com amazon
(a) (c=1e-1)
(b) (s=1)
(c) (E=6)
(d) (c=12)
Figure 14: Contrapolymatroid Membership Function Value over time com dblp
(a) (s=le-1)
(b) (e=1)
(c) (e=6)
(d) (e=12)
Figure 15: Contrapolymatrood Membership Function Value over time roadnet PA
44

---

Danity as Cacc Time madde (epencer))
Dersty Well Ceokk Tiree www.ret CA Inspe1)
Pel Tuee Kay
4.0
Zorrdnn 140 50x
(a) (e=1e-1) 1)
(b) (s=1)
cepe-121
(c) (s=6)
(d) (E=12)
Figure 16: Contrapolymatroid Membership Function Value over time roadnet_CA
45

---

I Minimum Norm Point Problem Experiments
Problem Definition, Let f: 2 - R be a normalized (super)submodular function, and let B(f) denote its base polytope. Our objective is to find the point in B(f) with the minimum Euclidean norm, i.e., arg min ||=112-
Algorithms. We evaluate three algorithms: Frank Wolfe (FRANKWOLFE), Fujishige- Wolfe Min- imum Norm Point (FW-MNP), and SUPERGREDDY+ (SUPERGREEDY). All algorithms are im- plemented in C++
Datasets. We reuse all instances from prior experiments but focus on the load vector norm rather than the original objective.
Resources. Please refer to the previously cited resources for further information on each problem and its resources.
Discussion of Minimum Norm Point Results. Algorithm performance varies significantly across problems and instances. Overall, SUPER + performs best on DSG, consistently achieving the lowest norm point: the other algorithms behave similarly and sub-optimally. For Anchored DSG, Generalized p-mean DSG, and HNSN, FW and FW-MNP typically outperform SUPER + However, all methods generally converge to similar norm values- values-excepl in generalized p-mean DSG, where SUPER +REEDY++ often settles suboptimal norms despite excelling in the classical DSG case (p 1). A comparable pattern appears in the close looee_cliuue instance for Contrapolyma- troid Membership, while in other CM instances, SUPER + converges faster and achieves lower norms. Lastly, for Min s-f Cut, SUPER CUPERGREEDY++ and FW-MNP perform comparably, with SUPERGREEDY ++ slightly outperforming, and both approaches consistently exceeding FW.
I.1 DSG
(a) blose.cliques
(b) com. aom.amazon
(c) com.dblp
(d) com. com.orku orkut
(e) disjoint uniin.c
(I) roadnet.PA
g roadnet_CA
Figure 17: DSG load norm over time
I.2
Anchored DSG
(a) close_cliques
(b) com_amazon
(c) com-dblp
(d) roadnet_PA
(e) roadnet_CA
Figure 18: Anchored DSG load norm over time
46

---

1.3 HNSN
(b) connectious
digg
(d) ecommerce Whe
(e) fruithut
foodmart
Lathen Bothhe
(g) imdb Noreeeeee Ceteeeetuueee
(h) kosarak Lotfe thtt
ii) liquor
i NBA
(k) notredame
(I) yoochoose
Figure 19: HNSN load norm over time
1.4
Min s-l Cut
(a) m10
(b) m30
(c) m50
(d) WW
sawtoothO
i sawtoothi
Bawtooth2
(h) sawtooth3
Bautooth4
(i) sawtooth5
sautooth6
sawtooth7
(m) sawtooth8
(n) sawtooth9
(0) santooth10
(p) sautooth11
47

---

(a) sawtooth12
(b) sawtooth13
(c) sawtoothh4
(d) sawtooth15
(c) sawtooth16
(f) sawtooth17
saatooth18
(h) sawtooth19
Figure 21: Min 8-1 Cut load norm over time
1.5 Generalized p-mean DSG
(a) (p=1.1)
(b) (p=1.25)
(c) (p=1.5)
(d) (p= 1.75
Figure 22: DSS load norm over time close_cliquee..e
(a) (p=1.1)
(b) (p=1.25)
(c) (p=1.5)
(d) (p=1.75)
Figure 23: DSS load norm over time com_amazon
(a) (p=1.1)
(b) (p 1.25
(c) (p=1.5)
(d) (p 1.75)
Figure 24: DSS load norm over time com.dblp
(a) 1111.1)
(b) (Q=1.25)
(c) (p=1.5)
(d) (p=1. 1.75
Figure 25: DSS load norm over time roadnet PA
(a) (p=1.1)
(b) (p=1.25)
(c) (p=1.5)
(d) (p=1.75)
Figure 26: DSS load norm over time roadnet_CA
48

---

1.6
montrapolymatroid Membership
(a) (s=le-1)
(b) (==1)
(c) (==6)
(d) (==12)
Figure 27: Contrapolymatroid Membership load norm over time cliques
(a) (s=le-1)
(b) (s=1)
(c) (e=6)
(d) (==12)
Figure 28: Contrapolymatroid Membership load norm over time com amazon
(a) (s=le-1)
(b)
(==6)
(d) (e=12)
Figure 29: Contrapolymatroid Membership load norm over time comddblp
(a) (s=le-1) 1)
(b) (==1)
(c) (==6)
(d) (s=12)
Figure 30: Contrapolymatroid Membership load norm over time roadnet
(a) (c=1e-1)
(b) (e=1)
(c) (e=6)
(d) (e 12)
Figure 31: Contrapolymatroid Membership load norm over time roadnet CA
49


Reviews:
[{"review_id": "TftuWJ20qN", "reviewer": "Reviewer_xHD5", "summary": "Optimization problems involving submodular and supermodular \nfunctions have many applications in computer science. The paper\naddresses an important version of these problems, called the ratio\noptimization problem where the goal is to optimize the ratio f(S)/|S|,\nwhere S is the solution set and f is the submodular or supermodular\nfunction. The paper points out that the ratio optimization problem models\na number of optimization problems studied in the literature. It is shown\nthat many of these problems are equivalent to each other (with respect to\noptimal solutions) through polynomial time reductions. It is also shown\nthat traditional approximation methods (namely SuperGreedy++ and\nMinimum Norm Point) yield good approximations for all of the problems\nconsidered. Extensive experimental results are presented for the\nproblems considered.", "questions": "(1) In the definition of Problem 4 (lines 82--85), it seems to this\nreviewer that the summation should be over the nodes in the solution\nset S (rather than the set R of all nodes). This may just be a typo.\nPlease clarify.\n\n(2) Lines 127--128: You mention that \"... deemed impractical for\nlarge graphs due to requiring an expensive binary search procedure\".\nCan you please explain? (Usually, binary search is not expensive.)\n\n(3) As stated in Theorem 14, the number of iterations\ndepends on the maximum value of the submodular or supermodular function.\nSo, it seems to this reviewer that SuperGreedy++ is a pseudo-polynomial time\nalgorithm rather than a polynomial time algorithm. Can you please clarify?\n\nA minor suggestion: In several places (e.g., lines 98, 105)\nthe paper has sentences of the form \"[39] showed that ...\" or\n\"indeed [31] state ...\". It is better to revise them to something like\n\"Li et al. [39} showed that ...\".", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n(a) The topic of the paper (optimizing submodular and supermodular\nfunctions) is of great interest to researchers because of numerous\napplications.\n\n(b) The paper nicely unifies known results for many problems and\nshows that traditional approximation methods provide efficient\napproximations for the problems. (The result for minimum st cut was\na pleasant surprise to this reviewer.)\n\n(c) The experimental results are comprehensive.\n\n(d) The paper is written very well.\n\nWeakness:  This reviewer can't identify any major weakness. A (very)\nminor weakness is that the the reader needs to keep track of a large\nnumber of acronyms. A simple way to overcome this minor weakness\nis to include a table of acronyms (in a longer version of the paper).", "was_revised": true, "final_justification": "I have read all the reviews, rebuttals and the subsequent discussion. The results in the paper are nice and strong. I am glad that all the reviewers are in agreement regarding the quality of the paper. As mentioned by the Area Chair, I believe that this paper deserves to get a strong accept.", "rebuttal": "# Response to Reviewer xHD5\n\nWe sincerely thank the reviewer for their thoughtful and encouraging feedback. \n\nWe address your comments and questions below:\n\n### **(1) Clarification of Problem 4 (HNSN):**\n\nYou are correct — this was a typo. The summation in the objective should indeed be over the solution set $S$, not over all of $R$. We will fix this typo in the revised version.\n\n---\n\n### **(2) Binary Search and Flow-Based Algorithms:**\n\nThis is a valid question — binary search is efficient in general, and much faster than simply enumerating all possible density thresholds $\\lambda$. Our intention was to indicate that earlier flow-based algorithms for densest subgraph problems used binary search over the density threshold $\\lambda$, requiring a full **max-flow computation at each step of the search**. The need for **high-precision convergence and repeated max-flow computations** can makes this approach impractical at scale.\n\nFor example, if we search for $\\lambda$ in the range from $1/n$ to $n/2$ (the range of feasible densities), and aim for a precision of $\\epsilon = 0.001$, the number of binary search steps required is roughly $\\geq 30$ for $n\\geq 2,000,000$. This translates to **30 full max-flow computations** for graphs with $n \\sim 10^6$. Each such computation is costly in runtime and memory.\n\nIn contrast, the **density-improvement method** (e.g., Huang et al. \\[32], Hochbaum \\[31]) iteratively updates $\\lambda_k$ by solving\n\n$$\n\\max_{S \\subseteq V} \\set{ f(S) - \\lambda_k |S| },\n$$\n\nand typically converges in **fewer than 3-4 iterations**. This is because the number of \"critical\" values for $\\lambda$ — points at which the optimal solution changes — is small in practice. Thus, density improvement \"prunes\" the solution space more quickly than sequential halving in binary search while achieving the same optimal result.\n\nWe will clarify this example in the final version to better explain the practical difference.\n\n---\n\n### **(3) On Pseudo-Polynomial Time of SUPERGREEDY++ (Theorem 14):**\n\nThis is an important observation. Indeed, the iteration bound in Theorem 14 depends on a function-dependent term involving the function $f$, and therefore **SUPERGREEDY++ is not guaranteed to run in strongly or weakly polynomial time** under our current analysis —  in that sense, you are absolutely correct that it is **pseudo-polynomial**.\n\nWe would also like to point out that even in the original analysis of **SUPERGREEDY++** for the DSS problem by Chekuri et al. (SODA 2022), the convergence rate includes a term $ \\Delta_f $ that is a pseudopolynomial in the input parameters (the function $f$). Our understanding of the precise convergence rate of SuperGreedy++ is still limited even when the function is non-negative and monotone. We will clarify this point in the revision.\n\n---\n\n### **(Minor Suggestion – Citation Style):**\n\nThank you for the suggestion. We agree and will revise citation phrasings like “\\[31] states” to “Huang et al. \\[31] state” for better readability and consistency with the literature.\n\n---\n\n### **Additional Improvements:**\n\nFollowing your helpful suggestion, we plan to add a **table of acronyms** in the longer version to improve readability for new readers and reduce cognitive overhead. \n\n---\n\nOnce again, we truly appreciate your detailed and supportive review. We believe the revisions and clarifications above will further strengthen the clarity, accuracy, and impact of the paper."}, {"review_id": "59J9aozOXE", "reviewer": "Reviewer_XFrn", "summary": "This work mainly proves five classes of problems to be equivalent, and also that approximate solutions to MNP can be transformed into approximate solutions for these five problems. This suggests that the method originally specifically on one of theseo another of these problems (namely, become somewhat problems can be transformed int universal), and even achieve a better performance. It also provides a possible way to connect the independent methods research together in a unified framework. To evaluate the discussion in the theoretical parts, the authors also conducted numerical experiments on a large-scale dataset, where basically convincing results are presented. Many interesting discoveries are discussed in the paper, while some of them are left as open questions in the limitations section.", "questions": "1. According to the experimental results, the authors claim that “MNP and FW excel on HNSN, they both underperform here, underscoring how problem structure affects solver efficiency.” (Line 371, “here” here refers to Minimum s-t Cut). If HNSN and MNP problems are already proven to be equivalent in Theorem 12 (Line 12), then why would the performances of two methos MNP and FW differ that much on two somehow equivalent problems? Can you provide any anaylsis of how exactly the problem structure is affecting the efficiency here?\n\n2. According to the authors’ experimental results, in some problems the general methods can beat sota problem-specific methods. I'm quite curious about this result, does this mean the problem-specific method in fact does not take advantage of that much useful “specific information” in the problem? Is it possible to directly design problem-specific methods with better performance?\n\n3. Some abbreviations are used repeatedly. e.g. MNP refers to both an algorithm (Fujishige-Wolfe Minimum Norm Point Algorithm, e.g. Line 372) and a problem class (MINIMUM NORM POINT Problem, e.g. Line 244). It’s not a major problem but can somehow affect the clarity of the paper, we expect that authors can do a little modification here.", "limitations": "Yes. The authors have already discussed the main limitations from Line 401 to Line 405, though I’m also quite curious about the answers to these limitations.", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\n1. The text is clear and understandable, and the work is clearly discussed in the paper.\n2. The idea of this paper is very interesting and of significance; it proves the equivalence of the problem types in Theorem 12, thereby creating an opportunity to unify the previously independent lines of research on these problems.\n3. The experiments are well-conducted and are basically sufficient to numerically prove the ideas discussed in the theoretical part.\n\nWeakness:\n1. Some important limitations are left as open questions\n2. Some abbreviations are used repeatedly", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer XFrn\n\n\nWe sincerely thank the reviewer for their generous and thoughtful comments. We appreciate the recognition of the paper's contributions. Below, we respond to the specific questions and suggestions:\n\n---\n\n### **Q1: Why do MNP and FW perform well on HNSN but underperform on Minimum s-t Cut, despite theoretical equivalence?**\n\nThis is an important and nuanced question. As you point out, **when solved exactly**, the problems are **mathematically equivalent**, and Theorem 12 provides the reductions showing how their optimal solutions can be transformed into one another. However, **in the approximate setting**, the situation becomes much more subtle. In approximation algorithms, problems with output values that are zero or non-negative are typically more challenging, as additive error—being the more appropriate measure in such cases—is harder to achieve, whereas multiplicative error is generally easier to handle for non-negative objectives.\n\n\nThe key difference lies in the **structure of the underlying submodular functions**:\n\n* For the **HNSN** problem, the function $f(S) = |N(S)|$ is a **coverage function** — it is **monotone**, **non-negative**, and has a clean characterisations.\n* Conversely, in the **minimum s-t cut** formulation, the function $f(S) = |\\delta(S \\cup \\{s\\})| - |\\delta(\\{s\\})|$ is **not monotone**, can take **negative values**, and typically leads to **more complex polytopes** with extreme points that are close together or highly skewed.\n\nThese structural differences strongly influence the **convergence behavior of iterative solvers** such as Frank-Wolfe and MNP. In practice, we find that solver performance can vary significantly depending on the **geometry of the base polytope**, even when the underlying optimization problems are theoretically equivalent. For instance, in the **minimum s–t cut** formulation, the function $f(S) = |\\delta(S \\cup \\{s\\})| - |\\delta(\\{s\\})|$ tends to be sensitive to small changes in the graph, which can result in a **\"thin\" or skewed base polytope** along certain directions.\n\nThis geometric perspective is not merely anecdotal; some convergence analyses of Frank-Wolfe explicitly rely on notions like **pyramidal width**, a purely geometric quantity that captures how “sharp” or “flat” the polytope is in different directions. Since both Frank-Wolfe and MNP operate by navigating the **extreme points** of the base polytope, their efficiency is tightly coupled with its geometric structure.\n\nWhile we consistently observe that **at least one of our universal solvers performs well** on any given problem, **we do not yet fully understand** *which* solver performs best *when*, or *why*. Understanding the interplay between the function structure and solver behavior remains an open question, and is explicitly noted in the limitations of our work.\n\n---\n\n### **Q2: Why do general-purpose methods outperform problem-specific heuristics? Does this mean the heuristics aren’t leveraging the problem structure?**\n\nThis is a great observation. In many problem-specific heuristics (e.g., greedy peeling or local ratio methods), the “specific structure” that is used is often **simplistic** or **myopic**, such as removing low-degree nodes without a global view.\n\nIn contrast, general-purpose methods like MNP, Frank-Wolfe, and SUPERGREEDY++ implicitly operate on the **full combinatorial or polyhedral structure** of the problem. As a result, they can often **exploit hidden structure** better than naive heuristics.\n\nThat said, it remains possible to design *better* problem-specific algorithms that leverage deeper properties (e.g., flow-augmenting paths, dual decompositions). Our results highlight that **some heuristics underperform not because the problem is hard, but because the heuristic doesn’t fully exploit the structure**, which we believe is an exciting direction for future algorithm design. We will elaborate on this in the final paper.\n\n---\n\n### **Q3: Ambiguity in the term \"MNP\" (problem vs. algorithm)**\n\nThank you, this is a valid and very helpful suggestion. We agree that overloading \"MNP\" to mean both the **Minimum Norm Point problem** and the **Fujishige-Wolfe algorithm** can cause confusion. In the final version, we will explicitly distinguish:\n\n* *MNP (problem)*: the Minimum Norm Point problem\n* *FW-MNP*: the Fujishige-Wolfe algorithm used to solve MNP\n\n---\n\nAgain, we thank the reviewer for their encouraging assessment and insightful questions."}, {"review_id": "tYEqL76CSc", "reviewer": "Reviewer_Pm74", "summary": "This paper presents a unified theoretical and algorithmic framework connecting several submodular and supermodular ratio optimization problems, including Densest Subgraph (DSS), Heavy Nodes in a Small Neighborhood (HNSN),  Unrestricted Sparsest Submodular Set (USSS), and Submodular Function Minimization (SFM), Minimum Norm Point (MNP), etc. The authors establish strong polynomial-time equivalences among these problems and demonstrate that their approximation guarantees can be mutually preserved via reductions to the Minimum Norm Point (MNP) problem. This equivalence enables algorithmic cross-pollination: methods like SUPERGREEDY++, Frank-Wolfe, and Fujishige-Wolfe’s MNP algorithm—originally designed for specific settings—are shown to serve as universal solvers across all problem classes.", "questions": "1.\tThe paper states that DSG is polynomial time solvable. What about the rest problems mentioned in the paper? Like DSS, HNSN, USSS, etc.\n\n2.\tIt seems that the condition of Theorem 13 is slightly different with the approximation result for MNP, no matter that we talk about additive approximation or multiplicative approximation. In my understand, the direct implication of the condition is that $||\\hat{x}||_2\\leq ||x^*||_2+\\epsilon^2/||\\hat{x}||_2$. So it might be useful to write down approximation solutions of MNP itself based on this condition in the theorem.\n\n3.\tI want to confirm whether the following understanding is correct. When we say the algorithm (SUPERGREEDY++, Frank-Wolfe, or Fujishige-Wolfe) can solve the problems mentioned in the paper efficiently and with good approximation, we mean that we should firstly transfer the problem into MNP , then use the algorithm to solve the MNP problem and finally transfer the solution back. It does not mean we can obtain good result if we apply the algorithm directly to the problem (suppose we have some natural way to apply the algorithm).", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe connection between several submodular and supermodular ratio optimization problems is very interesting and important. \n\n2.\tThe theoretical insights are compelling, particularly the formalization of how approximations for MNP transfer to other problems, which broadens the applicability of existing algorithms. \n\n3.\tThe experimental results show the theoretical results can be applied in practice. \n\nWeakness: The paper discusses many problems and algorithms, so due to the space limitation, it is difficult to cover every detail in the main body.", "was_revised": true, "final_justification": "The results in the paper are interesting and important. The authors have adequately addressed my questions and clarified the issues mentioned in the review. However, due to page limitations, many details could not be fully elaborated. I look forward to seeing a more comprehensive journal version.", "rebuttal": "# Response to Reviewer Pm74\n\nWe thank the reviewer for their detailed and constructive feedback. Below we address the specific questions and suggestions:\n\n---\n\n### **Q1: Are the other problems (e.g., DSS, HNSN, USSS) also polynomial-time solvable like DSG?**\n\nYes, all of the problems mentioned (DSS, USSS, UDSS, SFM, MNP) are, at least in theory, all **polynomial-time solvable in the exact optimization setting**. In fact, one of our main contributions (Theorem 12) is to show that these problems are **strongly polynomial-time equivalent**, with efficient reductions between them. This means that since Submodular Function Minimization (SFM) and MNP are known to be solvable in strongly polynomial time, so too are DSS, USSS, and others.\n\nOf course, as we also emphasize, the approximation landscape can vary wildly in practice, depending on the function structure, which is discussed in Theorem 13.\n\n---\n\n### **Q2: Theorem 13 condition vs. standard MNP approximation — can we derive an approximate solution to MNP itself from this condition?**\n\nThe condition in Theorem 13 assumes an approximate solution $\\hat{x} \\in B(f)$ satisfying\n\n$$\n\\|\\hat{x}\\|^2 \\le \\langle q, \\hat{x} \\rangle + \\varepsilon^2 \\quad \\text{for all } q \\in B(f),\n$$\n\nwhich upper bounds the **duality gap**. Theorem 14 guarantees such approximate solution after a number of iterations. While Theorem 13 focuses on how this approximate $\\hat{x}$ leads to good *set-based* solutions for other problems (like SFM, USSS), it is true that this same $\\hat{x}$ is also an **approximate solution to the MNP problem itself**, in the sense that $\\hat{x}$ is close to the true minimum-norm point up to additive error $\\varepsilon$.\n\nWe appreciate the suggestion and will include a short clarification that this approximate solution serves both as a good MNP solution and as a bridge to solving the other problems.\n\n---\n\n### **Q3: Do we need to explicitly reduce to MNP before applying the algorithms? Or can we apply them directly?**\n\nThe answer is: **both perspectives are valid**.\n\n* Our reductions show that all five problems can be *reduced to MNP*, and therefore, solving MNP (even approximately) suffices to solve the others.\n* However, we frequently apply the same algorithms (such as Frank-Wolfe, SUPERGREEDY++, or Fujishige-Wolfe) **directly** to each problem—meaning we obtain the solution to the target problem without explicitly transforming it into a Minimum Norm Point (MNP) instance. This is feasible because these algorithms operate over the same base polytope $B(f)$, which is common to all of these problem formulations.\n\nIn fact, one of the key messages of the paper is that many of these algorithms are *implicitly solving MNP*, even when applied “naively” to problems like DSS or SFM. SUPERGREEDY++, for instance, was designed for DSS but is, under the hood, approximating the MNP solution in the base polytope.\n\n**Users can either reduce to MNP explicitly or apply these solvers directly if the base polytope access is available**, the behavior and guarantees remain the same.\n\n---\n\n### **Formatting Suggestion – Monotonicity and SFM**\n\nThank you — this is a helpful comment. We will revise the paragraph to clarify that SFM applies **regardless of monotonicity**, and that the definition is simply introduced for completeness before defining monotone variants like DSS.\n\n---\n\nOnce again, we appreciate the thoughtful comments and high score."}, {"review_id": "zagax1klLm", "reviewer": "Reviewer_z95E", "summary": "In this paper, the authors study a broad range of combinatorial optimization problems related to submodularity and supermodularity, particularly focusing on submodular and supermodular ratio optimization problems. The authors introduce two novel optimization problems: Unrestricted Sparsest Submodular Set (USSS, Problem 5) and Unrestricted Densest Supermodular Set (UDSS, Problem 7). In USSS/UDSS, given a universe $V$ and a normalized submodular/supermodular function $f$, we are asked to find a nonempty $S\\subseteq V$ that minimizes/maximizes $f(S)/|S|$. USSS is a generalization of the recently-introduced graph optimization problem called Heavy Nodes in a Small Neighborhood (HNSN, Problem 4), while UDSS is a generalization of Densest Supermodular Set (DSS, Problem 3), which is also known as a generalization of the well-known graph optimization problem called Densest Subgraph (DSG, Problem 2) and its variant called Anchored Densest Subgraph (ADS, Problem 6). In addition to the above ratio optimization problems, the authors consider two classic problems: Submodular Function Minimization (SFM, Problem 1) and Minimum Norm Point (MNP, Problem 8). The main contribution of this paper is to establish a novel algorithmic foundation for the above problems, especially focusing on USSS, UDSS, DSS, SFM, and MNP. To this end, the authors first prove that the five problems are equivalent in terms of exact optimization, meaning that any exact algorithm for one problem is applicable to any other problem. Specifically, they construct a strongly polynomial-time (at most $O(n\\log n)$ time) reduction between any two problems. Note that some of the reductions are known or trivial (e.g., DSS to SFM) but many of them are not trivial at all. Furthermore, the authors also study the relationships among the problems in terms of approximation. Specifically, they demonstrate that MNP plays a key role in terms of additive approximation by proving that an additive approximation algorithm to MNP can be used to obtain additive approximate solutions to any other problems. Note that the additive approximation is unavoidable, since some of the problems induce negative objective values. Computational experiments using a vast amount of instances for the problems demonstrate that some algorithm for one problem that have never been considered as potential algorithms for the other problems outperform state-of-the-art methods specifically designed for those problems.", "questions": "- Is it possible to summarize the time complexities of the algorithms for different problems. For example, the reviewer is interested in the time complexity of SuperGreedy++ when applying it to SFM. Does it give a competitive complexity with state-of-the-art? The runtime is empirically thoroughly evaluated, but the reviewer believes this kind of work is useful. \n- Isn't it worth studying restricted version of USSS, say SSS?", "limitations": "yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:** \n\nThis is a mathematically solid paper, with a lot of originality and significance. The authors succeed in establishing a novel algorithmic foundation for the diverse problems, including USSS, UDSS, DSS, SFM, and MNP, by constructing a strongly polynomial-time reduction between any two problems and approximation-preserving reductions from USSS, UDSS (DSS), and SFM to MNP. These types of reductions are quite beneficial, since each of the problems (or its special case) has very actively been studied in the literature and the reductions enable algorithmic cross-over, applying an algorithm developed for one problem to the others. For instance, the classic Fujishige--Wolfe's algorithm for MNP is now applicable to the other problems and the authors empirically demonstrate that when applying it to the recent HNSN, a special case of USSS, it significantly outperforms state-of-the-art methods. On the other hand, the recently-invented algorithm for DSS called SuperGreedy++ is now applicable to the classic SFM, and the authors again empirically demonstrate that SuperGreedy++ often performs better than state-of-the-art methods. The experiments are quite thorough, where a vast amount of instances for the problems are used and a lot of baseline methods are implemented and tested. Although the writing has some potential to be improved, the quality and clarity are generally satisfactory. \n\n**Weaknesses:**\n\n- The writing can be improved. Currently, the authors introduce USSS and UDSS as generalizations of the recently-introduced problems. However, this way makes the structure of the introduction a bit too complicated, where many special cases that are not directly studied in the methodological part are intertwined with the other main problems. The reviewer would suggest presenting the main problems first and then motivating them by putting some existing special cases. Considering the theoretical importance of the contribution, the reviewer believes the above presentation strategy still works while improves the readability a lot. The structure of the abstract can be modified in a similar way. \n\n- It would be better to include proof sketches in the main body to make the readers get the intuition about the technical contents better. \n\n- The selection of experiments presented in the main body should be justified. In the reviewer's understanding, the results for HNSN highlight the usefulness of the classic algorithms for the recent problem, while the results for Minimum $st$ Cut highlight the usefulness of the recently-invented algorithms for the classic problem. \n\n- There are some missing references. ADS was originally introduced by Dai et al. (SIGMOD 2022) not by [31]. Nagano et al. (ICML 2011) studied an MNP-based algorithm for Densest $k$-Subgraph, which seems relevant to the present paper. \n\n- There are several undefined notations, typos, and other minor things, listed below.\n\nMissing references: \n- Dai, Qiao, Chang: Anchored Densest Subgraph, SIGMOD 2022.\n- Nagano, Kawahara, Aihara: Size-Constrained Submodular Minimization through Minimum Norm Base, ICML 2011.\n\nTypos etc.:\n- Line 9: MNP is undefined. \n- Line 93: deg is undefined. \n- Line 155: $n$ is undefined. \n- Line 167: no data-structures -> no special data-structures\n- Line 188: It would be better to highlight that the approximation-preserving reductions are different from the above reductions. \n- Line 212: that each have -> each of which has \n- Lines 222 & 247: Put a period. \n- Line 226: $x(S)$ is undefined.\n- Line 241: that that -> that\n- Line 274: $n=|V|$ is redundant. \n- Theorem 14: What is $d$? Should it be $x$? The operation $V-u$ is undefined. \n- Line 310: Should $\\delta(v)\\subseteq S$ be $\\delta(v)\\cap S \\neq \\emptyset$?\n- Figures 1b and 1d are not mentioned (in the main body). \n- Line 384: Veldt -> Huang \n- Line 401: Make a section for conclusion and limitations.", "was_revised": true, "final_justification": "My initial assessment was to accept the manuscript. After carefully reviewing the authors’ responses and the discussions with the other reviewers, I find that the proposed revisions are reasonable. Therefore, I keep recommending acceptance.", "rebuttal": "# Response to Reviewer z95E\n\nThank you for the detailed and thoughtful review. We are grateful for your recognition of the paper’s contributions. Below we respond to your helpful suggestions and questions:\n\n---\n\n### **Presentation and Writing**\n\nWe appreciate your suggestions regarding the structure and clarity of the introduction and abstract. In particular:\n\n* We agree that beginning with the main problems (USSS, UDSS, DSS, SFM, MNP) and then introducing known special cases such as HNSN, ADS, and DSG as motivating applications could enhance readability; in fact, this was our original structure for the introduction. However, we found that starting with concrete problems first offered stronger motivation than beginning with the more abstract formulations. That said, we will revise the text to smooth the transition and introduce the broader abstract problems earlier to better guide the reader.\n* We also acknowledge that proof sketches in the main body would help with intuitions. Unfortunately, because of the page limit, we had to completely skip this for the submission. In the final version (when we get 1 additional page), we plan to include brief sketches for key reductions (e.g., DSS $\\iff$ SFM, USSS $\\Rightarrow$ MNP) and reference the full proofs in the appendix.\n* We will clarify the purpose of each experimental result more explicitly. Specifically, as you noted: (1) the HNSN results demonstrate the **relevance of classic MNP methods for new problems**, and (2) the s-t cut experiments show that **recent heuristics like SUPERGREEDY++ can compete with classical max-flow algorithms**. We’ll make this motivation more clear near Figures 1a–1d.\n\n---\n\n### **Missing References and Attribution**\n\nThank you for catching this, we will correct the following:\n\n* **Anchored Densest Subgraph (ADS)**: We will cite the original work by **Dai et al., SIGMOD 2022** as the correct source for ADS.\n* **Nagano et al., ICML 2011**: This is indeed highly relevant. We will cite and discuss it in the revised related work section.\n\n---\n\n### **Notation, Typos, and Clarifications**\n\nWe will address all the specific issues you noted, including undefined notations, missing periods, and inconsistencies in phrasing. These are extremely helpful. In particular:\n\n* Theorem 14: We will clean up the expression for the number of iterations (it should be $s-d$, not $s-x$) and fix the undefined operations.\n\n---\n\n### **Response to Questions**\n\n#### **Q1: Can you summarize the time complexities of the algorithms, especially SUPERGREEDY++ for SFM?**\n\n\n* For SFM, **SUPERGREEDY++** converges to a solution $S$ such that $f(S) \\leq  \\text{OPT} + 2n\\varepsilon$ in\n\n  $$\n  \\widetilde{O}\\left(\\frac{\\alpha_f }{\\epsilon^2}\\right)\n  $$\n\n  iterations, where $\\alpha_f$ depends on the function $f$ (From Theorem 14).\n\nIts runtime is still pseudo-polynomial due to the function-dependent terms. Empirically, it performs extremely well, but we agree the theoretical runtime should be compared with classical polynomial time algorithms like Iwata-Fleischer-Fujishige or Orlin’s algorithm.\n\nWe will add a small table or section summarizing these complexities in the final version.\n\n#### **Q2: Is it worth studying restricted versions of USSS, like SSS?**\n\nAbsolutely. This is a great idea and a natural extension. In fact, our original motivation for this paper; minimizing $f(S)/|S|$ for $f(S)=|N(S)|$ being the coverage function falls under SSS. \n\nWhile our paper focuses on **unrestricted** versions to allow non-monotone and negative functions (which are common in real-world applications like ADS and HNSN), **restricted versions** such as *Sparsest Submodular Set with Monotone or Positive f* could offer both:\n\n* Simpler theoretical analysis, and\n* Opportunities for improved approximations or faster algorithms.\n\nIt is also worth noting that for DSS, one can obtain results in terms of multiplicative approximations that cannot be shown for UDSS. We have some preliminary results for SSS in similar vein - for example SuperGreedy performance in terms of curvature constant of $f$ or potentially convergence analysis for SuperGreedy++ that is similar\nto that for DSS in the Chekuri et al. SODA paper for a multiplicative $(1+\\varepsilon)$-approximation rather than additive one.\n\nWe will mention this direction explicitly in the conclusion as a promising avenue for future work.\n\n---\n\nOnce again, we thank the reviewer for this thoughtful, technically precise review. Your feedback directly improves the final version."}]

Author rebuttal:

Meta-review: This paper presents a unified theoretical and algorithmic framework connecting several submodular and supermodular ratio optimization problems, such as Densest Subgraph (DSS), Heavy Nodes in a Small Neighborhood (HNSN), Unrestricted Sparsest Submodular Set (USSS), and Submodular Function Minimization (SFM), Minimum Norm Point (MNP). This paper establishes strong polynomial-time equivalences among these problems and demonstrates that their approximation guarantees can be mutually preserved via reductions to the Minimum Norm Point (MNP) problem. This equivalence enables algorithmic cross-pollination: methods like SUPERGREEDY++, Frank-Wolfe, and Fujishige-Wolfe’s MNP algorithm are shown to serve as universal solvers across all problem classes.

This paper is very well written, and its topic is interesting and important. It has nicely unified known results for different problems and shows that traditional approximation methods provide efficient approximations for the problems. The experiments are well-conducted and comprehensive.

All the reviewers recommend accepting this paper. The average rating for this paper is 5.5, and the minimum rating for this paper is 5. After reading the paper, the reviews, and the discussions, I agree with the reviewers that this paper is a significant contribution and strongly recommend accepting this paper.
Decision: Accept (spotlight)