Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
Authors: Nate Veldt
Austin R. Benson
Jon Kleinberg
Venue: NeurIPS 2021 Poster (2021)
Keywords: decomposable submodular function minimization
hypergraph clustering
sparse graphs
graph cuts

Abstract: Minimizing a sum of simple submodular functions of limited support is a special case of general submodular function minimization that has seen numerous applications in machine learning. We develop faster techniques for instances where components in the sum are cardinality-based, meaning they depend only on the size of the input set. This variant is one of the most widely applied in practice, encompassing, e.g., common energy functions arising in image segmentation and recent generalized hypergraph cut functions. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem, with graph sparsity controlled by the desired approximation factor. Our method relies on a new connection between sparse graph reduction techniques and piecewise linear approximations to concave functions. Our sparse reduction technique leads to significant improvements in theoretical runtimes, as well as substantial practical gains in problems ranging from benchmark image segmentation tasks to hypergraph clustering problems. 

Approximate Decomposable Submodular Function Minimization for Cardinality- Components
Nate Veldt* nveldtStamu edu Texas A&M University
Austin R. Benson arbêcs cornell. edu Cornell University
Jon Kleinberg kleinberg@cornell edu Cornell University
Abstract
Minimizing sum of simple submodular functions of limited support is a spe- cial case of general submodular function minimization that has seen numerous applications machine learning. We develop fast techniques for instances where components in the sum cardinality-basee meaning they depend only on the size of the input set. This variant is one the most widely applied in practice, encompassing, e.g., common energy functions arising in image segmentation and recent generalized hypergraph cut functions. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem, with graph sparsity controlled by the desired approximation factor. Our method relies on sparse graph reduction techniques and piecewise linear approximations to concave functions. Our sparse reduction technique leads significant improvements in theoretical runtimes, as well as substantial practical gains in problems ranging from benchmark image segmentation tasks hypergraph clustering problems.
connection between
1 Introduction
Given ground set V, function f: 2V - IR is submodular if for every A, B C V it satisfies f(A) - J(B) 2 [(A n ((AU Submodular functions are ubiquitous in combinatorial optimization and machine learning, arising, e.g., in image segmentation [22), hypergraph clustering [30, data subset selection 44,, document summarization [31, and dense subgraph discovery [43]. Algorithms for minimizing submodular functions are well studied. Strongly-polynone
time algorithms for general submodular minimization exist [36 17 [8). but their runtimes are impractical in most cases. The past decade has witnessed several advances in faster algorithms for decomposable submodular function minimization (DSFM), i.e., minimizing a sum of simpler submodular functions [9] 24 39]
29 35
10
21 19). This problem is defined by identifying set E 2 of subsets of the ground set.
The goal is then to solve
minimizesgy f(S) = EeEr fe(Sne),
where for each E E, Se is a submodular function supported on a subset e C V. Functions of this form often arise energy functions in computer vision [22 23 I3, and generalized cut functions
for hypergraph clustering and learning [12 28
30
32
among other applications.
This paper focuses on cardinality-based DSFM (Card-DSFM), where every component f. in the
sum concave cardinality function, i.e., fe (A) ge (IAl) for some concave function ge. single concave cardinality function is effectively function of one variable and is trivial to minimize. However, set functions obtained via sums these functions are much more complex and have broad modeling power, making this one of the most widely studied and applied variants since the earliest
"This research was performed while the author was postdoctoral associate at Cornell University.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

work on DSFM 24 39
In terms of theory, previous research has addressed specialized runtimes In practice, cardinality-basee decomposable submodular functions frequently arise as higher-order energy functions in computer vision [22] and set cover functions [39 The most widely used generalized hypergraph cut functions are also cardinality Even previous research on algorithms for the more general DSFM problem
and solution techniques 24
based 30 32
tends to focus on cardinality- -based examples in experimental results [9] 39
29].
We present the first approximation algorithms for Card-DSFM, using a purely combinatorial ap- proach that relies on approximately reducing (I) to a sparse graph cut problem. The fact that concave cardinality functions are representable by graph cuts has previously been noted in different contexts [22] 39 - can be accomplished by combining simple graph gadgets, whose cut properties together model the function. However, previous techniques are limited in that they (i) focus only on exact reduction techniques, (ii) do not consider the density of the resulting graph, and (iii) do not address any questions regarding the optimality of such reduction. Here we develop new approximate reduction methods leading to a sparse graph, which we show is optimally sparse in terms of the standard gadget reduction strategy. We show that representing concave cardinality function with a sparse graph is equivalent to approximating a concave function with a piecewise linear curve, where the number of linear pieces determines the sparsity of the reduced graph. We develop new algorithm for the resulting piecewise linear approximation problem, and prove new bounds on the number of edges needed to model different concave functions that arise in practice. Combining our reduction strategy with state of the art algorithms for maximum flow [5] 26 40 [4] leads to fast runtime guarantees for finding approximate solutions to Card-DSFM. Our algorithm is also easy to implement and achieves substantial practical improvements on benchmark image segmentation
experiments [19 29] and algorithms for hypergraph clustering 42
2 Background on Graph Reductions
A nonnegative set function f: 2V + R on a ground set V is graph reducible if there exists a directed graph G = (V,, Ey) on a larger node set V, = V U A U {s,t), which includes an auxiliary node set A as well as source and sink nodes and t, whose s-t cut structure models f. More precisely, f is graph reducible if for every S C V we have
S(S) minimize cuta((s)USST)) TCA
where cuta is the cut function the graph G. In words, this says that evaluating S(S) is equivalent to finding the minimum 8-/ cut penalty that could be obtained by placing S on the s-side of the cut and V on the t-side. Given such a graph, f can be minimized by finding the minimum s-t cut set U* C A G and taking S = n n When (2) holds, we say that G models f.
Graph reduction strategy for Card-DSFM. In general, the function f(S) = =YCEE (( is not a concave cardinality function, even if individual components fe in the sum are. However, in order to show f is graph reducible, it suffices to find small reduced graph Ge for each E E that models fe in the sense of @2) and combine these together into a larger graph. A number of related own previous reduction strategy (41), which we build on in this paper. Modeling Se can be accomplished by combining a set of cardimality-basel (CB) gadgets [1). For a set
approaches for this task have been developed [39 22 41. We review
V of size k- = |el. CB- EB-ggeeet is small graph parameterized by positive weights (a, b). Each v E e defines a node, and the gadget also involves a single auxiliary node ug. For each E e, there is a directed edge (v, v.) with weight (k 6). and a directed edge (Ve, v) with weight a - b. The resulting graph gadget models the function
fa,((S) = a min (k- b), (A- [S))-bb]
(3)
To see why, consider where we must place the auxiliary node U. when solving a minimum s-t cut problem involving this small graph gadget. If we place i = |S] nodes on the s-dide, then placing Ve on the s-dide has a cut penalty of ab(k - i), whereas placing Ve on the t-side gives a penalty of ai(k b). To minimize the cut as in 2 for a fixed S S we choose the smaller of the two cut penalties. We previously showed that any cardinality-
submodular function Se on ground
set can be modeled by combining |e| 1 CB- -B-ggagett [1]. Analogously, Stobbe and Krause (39 showed that a concave cardinality function on ground set e can be decomposed into a sum of |e| -
threshold potentials [39 and can be represented by graph cuts, though they provided no explicit

---

reduction strategy. Priori to this, Kohli et al. [22] highlighted a similar type of gadget for modeling class of robust potential functions for image segmentation, noting that multiple gadgets could be combined to model arbitrary concave functions. Using any of these techniques, the function Se can be modeled the sense of using graph with ((el) nodes and O(lel²) edges.
3 Sparse Reductions via Piecewise Linear Approximation
We now turn to a new and refined problem of finding sparse and approximate reduction strategies for Card-DSFM, which we prove can be cast as approximating a concave function with a piecewise linear curve. All proofs are given in the supplement, where we also derive a similar graph reduction scheme that slightly more efficient for modeling symmetric functions, i.e., (A( [e(e))A).
3.1 The sparse approximate reduction problem
We first introduce a special parameterized function with broad modeling power.
Definition A k-node combined gadget function (CGF) of order J is a function of the form:
f(x) 20 (k - x) + 2k x Ej= aj min ak--kk---o (b)))). (lc -2) -b,)
(4)
parameterized by scalars 20 2 0, 2/ 2 0, and vectors a = (az) E R. and b = (b₃) E B where
by for .., 1] and by < k.
If we define a set function on ground set e of size by fe(S)= = E([S)), then fc is exactly the function that is modeled by combining J CB- (B-gadgets with parameters (aj. by } and additionally placing a directed edge from a source node s to each v E weight zo, and an edge from v E to sink node / with weight function y on an interval [0, k:] (representing a submodular function [e(S) = g(S))) matches some k-node CGF of order k- 1 at integer inputs [41 39). We focus new sparse reduction problem.
Previous reduction techniques amount to proving that any concave
Definition Let g: [0. k] + R+ be nonnegative concave function and fix E 2 O. The sparsest approximate reduction (SpAR) problem seeks a k-node CGF l with minimum order J so that
g < ((i) S (1 + e)g(i) for all i E 20, k).
(5)
This is equivalent to finding the minimum number of CB-gadgets needed to approximately model concave cardinality function. Thus, solving this problem provides the sparsest reduction in terms of a standard reduction strategy. Without loss of generality, Definition is restricted to considering functions that upper bound g. Any other approximating function could be scaled produce an upper bound leading to the same guarantees for Card-DSFN Importantly, we care about approximating the concave function g only at integer inputs, since we are ultimately concerned with modeling the set function (S) {(())). Satisfying (zx) < {(x) < (1 + e)g(x) for all x E [0, k] is much stronger requirement and may require more CB- CB-gadgets than actually necessary to approximate fe-
Connection to piecewise linear approximation Our first result establishes precise one-to-one correspondence between a certain class of piecewise linear functions and combined gadget functions.
Lemma The k-node CGF in (4) is nonnegative, piecewise linear, concave, and has exactly J + 1 linear pieces. Conversely, let E [0, k) + R be concave and piecewise linear with J - linear pieces, and let m; be the slope of the ith linear piece and B, be the ith breakpoint. Then E' is uniquely characterized the k-node CGF parameterized by 0; %. (m, m4+1) and b, for i JJ,,, 20 (0)/k, k. and
(k))k.
This result tells us that solving SpAR (Def for g is equivalent to finding a concave piecewise linear function with the smallest number of linear pieces approximating g at integer points. Although some techniques for approximating concave function with piecewise linear curve already exist [34] and could be used as heuristics, these are ultimately unable to find optimal solutions for SpAR. First of all, these methods focus on approximating concave functions over continuous intervals rather than just at integer inputs. More importantly, they do not provide instance optimal approx but only give upper bounds on the number of linear pieces needed. We therefore turn to new methods that will allow us to exactly solve sparse approximation problem.
3

---

Algorithm 1 GREEEDYPL.OVERRgg
Input: 2 O, concave function 9
Output: piecewise linear i with fewest linear pieces such that g(i) < {i1) < C 0, u 0
//u smallest integer not covered by approximating 1ine
while u Σ k do
u', L NEXTLINE(G, u, //line covering widest range [u, u'-1]
+ (L), 't'
end while Return {(x) minpec L(x)
3.2 Optimal sparse approximate reduction
Our goal is to find piecewise linear function é with a minimum number of linear pieces satisfying condition (5). This is equivalent to finding minimum sized collection L of linear functions that "cover" points {j.g(}}} for integers j. in the sense that (i) each linear function L E L satisfies g(i) & T.j) for all j E 1, ..... k), and (ii) for every j E (0, ...... k} there exists some I. E L satisfying I(j) S +)g((). Then, ((x) minzec [xx is the desired piecewise linear solution.
We develop simple method (Alg. to grow a collection L satisfying these conditions. Each iteration considers the integer u that is not currently covered by a (1 + -aaaproxina line, and uses subroutine NEXTLINE to find a line L that covers u and also satisfies g(t) < L()) S (1+ ()g((( for the largest integer This is done by taking the line through the point {u, (1 =)g(u)} that has the minimum slope while still upper bounding every point {i, g(i) To provide intuition for this strategy. note that C must contain some line that provides a (1 E) -pprrxxiimaaoonn
{0. g()).. It can only help us to choose a line that provides this guarantee while also providing (1 + E) apaproxximttioon for the widest possible range {0, .....,... ......,. t}. The same logic applies to finding linear pieces to approximate the function at remaining integer inputs. The supplementary material contains pseudocode for NEXTLINE and proof of the following result.
Theorem Algorithm solves the sparsest approximate reduction problem in O(k) operations.
3.3 Bounds on optimal reduction size
For concave function g, existing method of Magnanti and Stratila [33 34 can find piecewise linear function that approximates g over continuous interval [a, bj with O log ) linear pieces. Although this method does not optimally solving SpAR, it can be used to show the following worst-case upper bound the number of linear pieces found by our instance-optimal method.
Theorem Let g: [0, k] - IR+ be concave and let e 2 O. Algorithum 7 will return a piecewise linear function with most O(min(k, log k3) linear pieces satisfying
Previous lower bounds on the number of linear pieces needed to approximate concave function do not apply to our problem, as these are focused on approximating functions over continuous intervals [34. Since k points on a concave function can always be covered using & linear pieces, proving meaningful lower bounds for our problem more challenging. Nevertheless, using an existing lower-bound for approximating the square root function over a continuous interval
black-box 34 we prove that the upper bound in Theorem nearly asymptotically tight.
Theorem
Let g(x) fo and 2 k-5 for constant 5 E (0, Every piecewise linear & satisfying (() < {(i) S (1 + eig()) for E 1,. k} contains ((log k) linear pieces where =
= 2:(2 +) + 2(1 + (E +)) This behaves as 111-1/2 1/2 log k) as
In many cases the number of linear pieces returned by Algorithm 1 will be far smaller than the bounds above and the number of pieces returned by previous approaches [34]. One of our central contributions is the following guarantee for concave function that arises extensively in applications. Its proof is somewhat involved, and relies on bounding the number of iterations it takes to provide an
approximation for subintervals of the form [kk] 1/2-/ KE 1/2' for j = 1 to j = [log, log, = -1.

---

Algorithm 2 SPARSECARD(S,$)
Input: & 2 0, function S(S) - Eese [e(Sne) E 9e (e nel) ground set V
Output: Set S' C V satisfying f(S") S c1+ minggr f(S).
A < 0, <- V //initialize auxiliary node and edge set for reduced graph
for E E do
te f GREEDY
1/1: Solve SpAR (Algorithm 1)
G. (e E.) < CGPTOGADGET(()
//2: Build combined gadget (Lemma 1)
A AuA + &
//3: Add gadget to graph
end for
G = (V A..
//Build graph G modeling f //Find minimum s-t cut //Ignore auxiliary nodes
T (INSTCUT(G))
Return S = TVV
Theorem Let g(x) = (k x) for a positive integer For e > 0, the approximating function returned by Algorithm will have
log log =1 linear pieces.
This result is significant in number of ways. First of all, and somewhat surprisingly, the number of linear pieces needed to approximate g is independent of k. Our instance optimal algorithm therefore leads to significant improvement over the O log k) upper bound in Theorem 3 and the piecewise linear approximation that could be obtained using existing techniques [34]. More importantly, this
theorem has significant implications for approximately modeling the concave cardinality function Se( ([ (where Ce can be any positive constant) using graph cuts. Although previous exact graph reduction techniques [22 39 42 require O(lel) nodes and O(le{²) edges to model this function, can approximate it with only ((els- 1/2 log log tog)= edges. This savings is particularly significant given how extensively this function appears in practice. This function is a commonly used region potential in image segmentation, and shows up frequently in work on DSFM 9
19 39 29]
also appears often in hypergraph clustering applications, where it results from clique expansion 16 477, which replaces each hyperedge e with a clique on nodes in e. The cut function of the resulting graph is a decomposable submodular function whose components have the form fe = c. | SS.. This arises similarly as the cut function of graph obtained from co-occurrence relationships, or graph obtained from projection of bipartite graph (8) Our results provide a useful new type of sparsifier for all of these types of graphs.
of hypergraph 2
Theorem 5 also has implications for sparsifying a complete graph, a problem of interest in the theoretical computer science literature. Existing sparsifiers model the cut properties of a complete graph on n nodes with O(ne edges (6]. This is tight for spectral sparsifiers [6]. as well as for regrear cut sparsifiers with uniform edge weights [3] Our result implies that we are willing to include small number of additional nodes and use directed edges, the cut properties of the complete graph can be modeled using only (n)) nodes and One- log log e e-) edges.
4 Theoretical Runtime Analysis and Comparison
The ability to approximately model a single concave cardinality function makes it possible to quickly obtain an arbitrarily good approximate solution to an instance of Card-DSFM by reducing it to minimum s-t cut problem on sparse graph. Define a function f on ground set by
f(S) E.EE ne))) =. 9. (e)),
(6)
where each ge is concave, We assume each fe is nonnegative; if not we can adjust the objective by a constant without affecting optimal solutions. Algorithm 2 gives pseudocode for our new method SPARSECARD for minimizing (6. The method finds a sparse approximate graph reduction for each concave function Ir using Algorithm| [ combines these into a larger graph whose cut properties approximate f. and then applies a minimum s-t cut solver to that graph. Finding sparse reductions is fast, so the asymptotic runtime guarantee just the time it takes to solve the cut problem, which can be accomplished using any algorithm for solving the dual maximum s-t flow problem 15
14 26 40)
Theorem Let n = -VI and = =FE.. When & O, the graph constructed by SPARSECARD will have OeEEEE (el) nodes and 0 le(?) edges. When > 0, the graph will have O(n
5

---

ErEgE- log lel) nodes and O( EeEg le| log le]) edges. In either case, and the method will return a set T satisfying S(T) & (1 + é) minsgv ((S).
The graph returned by SPARSECARD can also be asymptotically sparser for specialized concave functions, such as the popular clique expansion function in Theorem 5
In the remainder of the section, we provide careful runtime comparison between SPARSECARD and competing runtimes for Card-DSFM. We reiterate that most previous techniques are designed to solve more general DSFM problems. However, these typically achieve improved runtime guarantees in the case of cardinality- -baseed components. Our goal is to understand the theoretical runtime improvements that can be achieved for Card-DSFM, especially in cases where approximate solutions suffice. We focus on each runtime's 's dependence on [V], R E,,, and support sizes |e), and use Ô notation to hide logarithmic factors of n. R. and 1/E. To easily compare weakly polynomial runtimes, we assume that each fe has integer outputs, and assume that log (maxs f(S)) small enough that can also be absorbed by Ô notation. Among algorithms for DSFM, SPARSECARD is unique its ability to quickly find solutions with priori multiplicative approximation guarantees. Previous approaches for DSFM focus on either obtaining exact solutions, or solving a problem to within an additive approximation error > 0 9 29 19]. In the latter case, setting small enough will guarantee an optimal solution in the case of integer output functions. We stress that this type of approximation is very different in nature and not directly comparable to the multiplicative approximations achieved by SPARSECARD. In our comparisons, we assume that previous methods are run until optimality, since the runtime of competing methods only improves by logarithmic factors if we assume the method is run until an additive approximation error >> 0 is achieved.
Competing runtime guarantees. Table T lists runtimes for existing methods for DSFM. We also give the asymptotic runtime for SPARSECARD when applying the recent maximum flow algorithm of van den Brand et al. [40] While this leads to the best theoretical guarantees for our method, asymptotic runtime improvements over competing methods can also be shown using alternative fast algorithms for maximum flow D4 26 13). For the submodular flow algorithm of Kolmogorov 144, we have reported the runtime guarantee provided specifically for Card-DSFM. While other approaches have frequently been applied to -ard-DSFM 9 39 29 19], runtimes guarantees for this case have not been presented explicitly and are more challenging to exactly pinpoint. Runtimes for most algorithms depend certain oracles for solving smaller minimization problems at functions fe in an inner loop. For e E E, let O2 be a quadratic minimization oracle, which for an arbitrary vector w solves min |yy w|ll where B(fe) is the base polytope of the submodular function fc (see 9 5 19 for details). Let 0, be the time it take to evaluate the oracle at e E E, and define 0 = max,c F. Og and Oangg >.e Or. Although these oracles admit faster implementations in the case of concave cardinality functions, it is not immediately clear from previous work what is the best possible runtime. When w = O. solving minye B(fa) lly + =wll takes O[Ee log lel) time [19], so this serves as best case runtime we can expect for the more general oracle O. based on previous results. We note also that in the case of the region potential function (AA) | AA). Enc et al. [9] highlight that an
O(ee] log lel + |elrz) algorithm can be used, where Te denotes the time it take to evaluate (S ne) for any S S e. In our runtime comparisons will use the bound 6. = ?((el). as it is reasonable to expect that any meaningful submodular function we consider should take a least linear time to minimize. We remark finally that for discrete DSFM algorithms, a slightly weaker oracle than the quadratic minimization oracle can be used 4 9. However, this does not lead to improved runtime case.
guarantees, as these are subject to the same lower bounds in the cardinality-
Fast approximate solutions (E >> O). Barring the regime where support sizes |e| are all very small, the accelerated coordinate descent method (ACDM) of Ene al. [10] provides the fastest previous runtime guarantee. For a simple parameterized runtime analysis, consider a DSFM problem where the average support size (1/ R) Σ. le| = O(n") for a E [0, 1], and R = O(r²), ), where 8 Z 1- a must hold if we assume each V is in the support for at least one function fe- An exact runtime comparison between SPARSEC ARD and ACDM depends on the best runtime for the oracle O. for concave cardinality functions. If an O(Ie] log je() oracle is possible, the overall runtime guarantee for ACDM would be 2(n #)) Mcanwhile, for a small constant > O, SPARSECARD provides a (1 + e) approximatee solution in time a(n + max(n3/2 mnax n,38/2)), which will faster by at least a factor Ö(vr) whenever 3 < 1. When 8 1, finding an approximation with SPARSECARD is guaranteed to be faster whenever R==00 2+20). If the best case oracle O2 for concave cardinality functions is w[e] log lel), the runtime improvement of our method is even more significant.

---

32 37 We Table 1: Runtimes for Card-DFSM for various methods, where R |E n
[V, μ = E.
and f22 Ee lel2. Oracle runtimes satisfy fee = [mmxx |e(), and awy a CeEE (e]).
Tm (N,, M) ) is the time solve a max-flow problem with N nodes and M edges.
Method
Discrete/Cont
Runtime
Kolmogorov SF
24
Discrete
Ō(2²)
IBFS [
9
Discrete
0 (n mew
+ Eelele
AP 35
Continuous
n RB RRggtt
RCDM 10
Continuous
nn (n²R0av aug)
ACDM 10 9
Continuous
( RB RBaug)
Axiotis et al.
Discrete
max le|2
- + Tmy (n,n+ + 12))
SPARSECARD E = 0
Discrete
O (Tmf (H, (2) 0 (12 + +
SPARSECARD E > O
Discrete
Ô (Tmy (n + 11 1
(2)) Ô 0 (n+ 23332)
Guarantees for exact solutions (c 0). As added bonus, running SPARSECARD with leads to the fastest runtime for finding exact solutions in many regimes. In this case, we can guarantee SPARSECARD will be faster than ACDM when the average support size (nn)) and R = o SPARSECARD can also find exact solutions faster than other discrete optimization methods [24 in wide parameter regimes. Unlike SPARSECARD, these methods are designed for problems where all support sizes are small, but become impractical if even single function has a large support size.
The runtime guarantee for SPARSECARD when 0 can be matched asymptotically by combining existing exact reduction techniques 22
39 41 with fast maximum flow algorithms. However, method has the practical advantage of finding the sparsest exact reduction in terms of CB- gadgets. This results in a reduced graph with roughly half the number of edges as our previous exact reduction technique [4]] Analogously, while Stobbe and Krause (39] showed that concave cardinality function can be decomposed as a sum of modular functions plus a combination of |el threshold potentials, our approximation technique will find a linear combination with [|el/2] threshold potentials. This amounts to the observation that any ++1 points {i, gi)) can be joined by [k/2] + lines instead of using Overall though, the most significant advantage of SPARSECARD over existing reduction methods is its ability to find fast approximate solutions with sparse approximate reductions.
Experiments
In addition to strong theoretical guarantees, SPARSECARD very practical and leads to substantial improvements in benchmark image segmentation problems and hypergraph clustering tasks. We focus on DSFM problems that simultaneously include component functions of large and small support, which are common in computer vision and hypergraph clustering applications [38] 9 41
ran experiments on a laptop with a 2.2 GHz Intel Core i7 processor and 8GB of RAM. We consider public datasets previously made available for academic research, and use existing open source software for competing methods Code for our algorithms and experimental results is available /attps://githur wwwo//vveddteeeeoe /SaarseCardDSFM
Benchmark Image Segmentation Tasks. SPARSECARD provides faster approximate solutions for standard image segmentation tasks previously used as benchmarks for DSFM [9 29 9. We consider the smallplant and octopus segmentation tasks from Jegelka et al. 220 19. These amount to minimizing decomposable submodular function on ground set of size VV 427 640 = 273280, where each v E V is a pixel from 427 x 640 pixel image and there are three types of component functions. The first type unary potentials for each pixel/node. i.c., functions of support size I representing each node's ' bias to be in the output set. The second type are pairwise potentials from 4-neighbor grid graph; pixels and share edge if they are directly adjacent vertically or horizontally. The third type are region potentials of the form fe(A) = [Alle\A] for A C e,
IImage datasets: httpp:/peoppe...tt. csail. mit. edu/steffe/code html Hypergraph clustering
arb/ data/ DSFM algorithms: from githhu.. com/ com/1ipan00123 DSFM-with hww.hh-iiniieeec--eelattiicee (MIT license); Hypergraph clustering algorithms: gitthu.. com/
datasets: /www. cs wornelll......oooooo............ hawpea//lldduaaaarddaaaaaaaaaaaa
hww.tt///tpperrrppprroo/ousssssp (MIT license).
7

---

Table 2: Results from SPARSECARD for different E > on the smallplant instance with 500 superpixels. Sparsity is the fraction of edges in the approximate graph reduction compared with the exact reduction. Finding the exact solution on the dense exact reduced graph took s/20 minutes.
1.0
0.2336
0.0546
0.0127
0.003
0.0007
0.0002
Approx.- -1
4 10 3
2 2-10-
6 6-10-
6-10-
3 3-10-s
7 10
7.10-
Sparsity
0.013
0.017
0.02
0.035
0.06
0.108
0.196
Runtime
4.1
5.6
6.7
11.5
24.3
41.4
74.3
oct, 200 superpixels
oct 500 superpixels
plant, 200 superpixels
plant, 500 superpixels
Approx Ratio
10.
10" 1.
10"
10"
10" 1.
IAP
RCDM
ACDM defiault
10"
10" 2
10
10" 1
10" 2
10
10"
10"
ACDM best
10 3
4
10" 3
10"
10"
SparseCard
10"
10"
10
10"
10
10"
10"
10"
0
10 20 30 40 50 60
0
10
20 30
40 50 60
10 20 30 40 50 60
10 20 30 40 50 60 Runtime (seconds)
R Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Figure 1: Approximation factor minus 1 vs. runtime for solutions returned by SPARSECARD and competing methods on four image segmentation tasks. We display the average of 5 runs for competing methods, with lighter colored region showing upper and lower bounds from these runs. SPARSECARE deterministic and was run once for each ε on a decreasing logarithmic scale. Our method maintains an advantage even against post-hoc best case parameters for competing approaches: ACDM-best is the best result obtained by running ACDM for range of empirical parameters for each dataset and reporting the best result. The default is c 10 (blue curve). Best post-hoc results for the plots from left to right were e = 25, 10, 50, 25. unclear how to determine the best e in advance.
where e represents a superpixel region. The problem can be solved via maximum flow even without sophisticated reduction techniques for cardinality functions, as regional potential function on can be modeled by placing a clique of edges on e. We compute an optimal solution using this reduction. Compared with the exact reduction method, running SPARSECARD with graphs, much faster runtimes, and a posteriori approximation factors that are significantly better than s). In Table 2 we list the sparsity, runtime, and posteriori guarantee obtained for a range of values on the smallpiant dataset using the superpixel segmentation with 500 regions.
leads much sparser
We also compare against recent C++ implementations of ACDM, RCDM, and Incidence Relation AP (an improved version of the standard AP method (35) provided by Li and Milenkovic (29]. These use the -ivide-and-conuuer method of Jegelka et al. [1)], implemented specifically for concave cardinality functions, to solve the quadratic minimization oracle O2 for region potential functions. Although these continuous optimization methods come with no a priori approximation guarantees, we can compare them against SPARSECARD by computing a posteriori approximations obtained using intermediate solutions returned after every few hundred iterations. Figure [ displays approximation ratio versus runtime for four DSFM instances (two datasets x two superpixel segmentations), SPARSECARD was run for range of ε values on a decreasing logarithmic scale from 10-4, and obtains significantly better results on all but the octopus with 500 superpixels instance. This is the easiest instance; all methods obtain a solution within factor 1.001 of optimality within a few seconds. ACDM depends on a hyperparameter e controlling the number of iterations in outer loop. Even when we choose the best post-hoc e value for each dataset, SPARSECARD maintains its overall advantage. Note that we focus on comparisons with continuous optimization methods rather than other discrete optimization methods, as the former are better equipped for our goal of finding approximate solutions to DSFM problems involving functions of large support. To our knowledge, no implementations for the methods of Kolmogorov [24] or Axiotis et al. 4 exist. Meanwhile, IBFS [T] is designed for finding exact solutions when all support sizes small. Recent empirical results confirm that this method is not designed to handle the large region potential functions we consider here.
9
Hypergraph local clustering. Graph reduction techniques have been frequently and success- fully used as subroutines for hypergraph local clustering and semi-supervised learning meth- 45) Replacing exact reductions with our approximate reductions can lead to signifi- cant runtime improvements without sacrificing on accuracy, and opens the door to running local clus- tering algorithms problems where exact graph reduction would be infeasible. We illustrate this by
ods 32 42
28
8

---

Table 3: Average Fl score and standard deviation for detecting 45 local clusters in a stackoverflow question hypergraph using HyperLocal [41] + SPASECARD with four hyperedge cut penalty functions. The 8-linear penalty had the fastest runtime (26 seconds on average) as it has sparse optimal (e = 0) reduction. For Time, we compute the ratio between the runtime of g-linear and the runtime of each method on all 45 clusters, then report the mean and standard deviation of these ratios. The # Best row indicates the number of times a method obtains the highest Fl score out of the 45 clusters.
8-linear
clique
r9.9
sqrT
8
C
0.1
=
& = 0.1
|
=
0.1
Fl
0.53 10.22
0.56
19
0.56
10.19
0.54
20.20
0.54
10.21
0.42 10.18
0.42 10.19
ATime
1.32
10.33
1.81
10.43
1.17
20.25
2.04
10.42
2.02
10.99
3.19 =1.4
# Best
7
10
16
8
3
1
using SPARSECARD as a subroutine for an existing method called HYPERLOCAL 42 This algorithm finds local clusters in a hypergraph by repeatedly solving Card-DSFM problems corresponding to hy- pergraph minimum s-t cuts. For these DSFM problems, E E is a hyperedge and fe (A) is the penalty for cutting a hyperedge so that nodes in A S e are on one side of the cut. HYPERLOCAL was originally designed to handle only the d-linear penalty fA) = min le) e\,Al, 6). for parameter ó 1, which can already be modeled sparsely with a single CB- CB-gadget. SPARSECARD makes it possible to sparsely model any concave cardinality penalty. We specifically use approximate reductions for the weighted clique penalty (A) = (le) - 1aa1-11--1p -|Al||/ AA), the square root penalty fA) / /minn| |A], e e\,A|), and the sublinear power function penalty (A) (min |A] |e's (A)))).
9 all of which require O(lel²) edges to model exactly using previous reduction techniques. Weighted clique penalties in particular
have been used extensively in hypergraph clustering 45 25 47, including by methods specifically
designed for local clustering and semi-supervised learning 27 45 46
We consider
hypergraph clustering problem where nodes are 15.2M questions on stackoverflow com and each of the 1.1M hyperedges defines a set of questions answered by the same user. The mean hyperedge size is 23.7, the maximum size is over 60k, and there are 2165 hy- peredges with at least 1000 nodes. Questions with the same topic tag (e.g., "common-lisp") constitute small labeled clusters in the dataset. We previously showed that HYPERLOCAL can detect clusters quickly with the 5-linear penalty by solving localized s-t cut problems near a seed set. Applying exact graph reductions for other concave cut penalties is infeasible, due to the extremely large hyperedge sizes, and we found previously that using a clique expansion after simply removing large hyperedges performs poorly 42 Using SPARSECARD
subroutine opens up new possibilities.
Following an existing approach 42,, we seek to detect 45 labeled clusters using a random seed set of 5% of each cluster. Table 1 reports average Fl scores and relative runtimes for four hyperedge cut penalties. Given the natural variation in cluster structure and size, standard deviations should not be viewed as error bars for each approach per se, but these provide rough indication for how the performance of each method varies across clusters. Detailed results for each cluster are included in the supplement. Importantly, cut penalties that previously could not be used obtain the best results for most clusters. The square root penalty does not perform particularly well on this dataset, but it is instructive to consider its runtime. Theorem 4 shows that asymptotically this function has a worst-case behavior in terms of the number of CB-gadgets needed to approximate it. We nevertheless obtain reasonably fast results for this penalty function, indicating that our techniques can provide effective sparse reductions for any concave cardinality function of interest. We also ran experiments with 0.01, which led to noticeable increases in runtime but only very slight changes in F1 scores. This indicates why exact reductions are not possible in general, while also showing that our sparse approximate reductions serve fast and very good proxies for exact reductions.
this dataset (clique, 2..9)
6 Conclusion and Discussion
We have introduced a sparse graph reduction technique leading to the first approximation algorithms for cardinality- DSFM. Our method provides an optimal reduction strategy terms of previously considered graph gadgets, comes with improved theoretical runtime guarantees over competing methods, and leads to significant improvements in benchmark image segmentation and hypergraph clustering experiments. An interesting direction for future research is to explore lower bounds or

---

improved techniques for other possible graph reduction strategies. For the very special case of clique splitting functions, practical open question to explore is whether uniformly sampling edges in clique works well in practice. On a more theoretical note, another open question to explore is whether the maximum flow techniques of Axiotis et al. could be combined with our sparsification methods to achieve even better theoretical runtimes for cardinality-basee based DSFM.
Regarding potential limitations of our work, our method applies only to the cardinality-based variant of the problem, whereas most existing methods solve a more general problem. Nevertheless, Card- DSFM is one of the most widely applied variants in practice, which highlights the utility of developing better theory and algorithms for this special case. Another limitation is that our method is not as easy to parallelize continuous optimization methods. An open question is whether better specialized (parallel or serial) runtimes can be obtained for continuous methods for Card-DSFM Finally, while our research focuses on faster algorithms for fundamental optimization task, there are ways in which tools for image segmentation and clustering (which are downstream applications of our work) can result in negative societal impacts depending on their use. For example, image segmentation could be used in illicit targeted video surveillance. Clustering methods could be used to de-anonymized private information in a social network, or to segment population of voters for micro-targeted political campaigns that potentially lead to increased political polarization. Nevertheless, algorithms for decomposable submodular function minimization, as well as the more specific tasks of image segmentation and hypergraph clustering, remain very general and are also broadly useful for many positive applications.
Funding Statement
Austin Benson is supported by ARO Award W911NF- 1EIIN-----1-057,, ARO MURI, and NSF CAREER Award IIS- IIS-2045555. Jon Kleinberg is supported by Vannevar Bush Faculty Fellowship, ARO MURI, AFOSR grant FA9550-19-1-018. and Simons Investigator grant. We declare no financial competing interests.
References
[1] Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In Proceedings of the 23rd International Conference on Machine Learning. ICML '06, pages 17-24, 2006.
[2] Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David Kriegman, and Serge Belongie. Beyond pairwise clustering. In Proceedings of the 2005 IEEE Computer Society Conference Computer Vision and Pattern Recognition, CVPR '05, pages 838 845, 2005.
[3] Noga Alon. On the edge-expansion of graphs. Comb. Probab. Comput., 6(2):145-152, June 1997.
[4] Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Adrian Vladu. Decomposable submodular function minimization via maximum flow. In Proceedings of the 38th International Conference on Machine Learning, ICML '21, pages 446-456, Jul 2021.
[5] Francis Bach. Learning with Submodular Functions: A Convex Optimization Perspective. Now Publishers Inc., Hanover, MA, USA, 2013.
[6] Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM Review, 56(2):315-33) 3344, 2014.
[7] Austin R. Benson, David F. Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295) 2016.
[8] Austin R. Benson, Paul Liu, and Hao Yin. A simple bipartite graph projection model for clustering in networks. http:://oxixoorg/bb222000..0
2020.
[9] Alina Ene, Huy Nguyen, and László A Végh. Decomposable submodular function minimization: discrete and continuous. In Advances Neural Information Processing Systems, NeurlPS '17, pages 2870 2880, 2017.
10

---

[10] Alina Ene and Huy L. Nguyen. Random coordinate descent methods for minimizing decompos- able submodular functions. In Proceedings of the 32nd International Conference on Machine Learning, ICMI. '15, pages 787-795, 2015.
[11] A. Fix, T. Joachims, S. M. Park, and R. Zabih. Structured learning of sum-of-submodular higher order energy functions. In 2013 IEEE International Conference on Computer Vision, ICCV '13, pages 3104-3111 2013.
[12] Kimon Fountoulakis, Pan Li, and Shenghao Yang. Local hyper-flow diffusion. arX- fv/2102.07945 2021.
[13] D. Freedman and Drineas. Energy minimization via graph cuts: settling what is possible. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '05, pages 939-946, 2005.
[14] Yu Gao, Yang P. Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than Goldberg-Rao. In 62nd Annual IEEE Symposium on Foundations of Computer Science, FOCS '1, 2021.
[15] Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. A.M,M (5 797. September 1998.
[16] Scott W. Hadley. Approximation techniques for hypergraph partitioning problems. Discrete Applied Mathematics, 59(2):115 127, 1995.
[17] Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM, 48(4))761 July 2001.
[18] Satoru Iwata and James B. Orlin. A simple combinatorial algorithm for submodular func- tion minimization. In Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 1230-1237, 2009.
[19] Stefanie Jegelka, Francis Bach, and Suvrit Sra. Reflection methods for user-friendly submodular optimization. In Advances Neural Information Processing Systems, NeurIPS '13, pages 1313-1321, 2013.
[20] Stefanie Jegelka and Jeff Bilmes. Submodularity beyond submodular energies: Coupling edges in graph cuts. In Proceedings of the 201/ IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, pages 1897-1904, 2011.
[21] Stefanie Jegelka, Hui Lin, and Jeff A Bilmes. On fast approximate submodular minimization. In Advances in Neural Information Processing Systems, NeurIPS 11, pages 460-468, 201
[22] Pushmeet Kohli, Philip HS Torr, et al. Robust higher order potentials for enforcing label consistency. International Journal of Computer Vision, 82(3):30 2009.
[23] V. Kolmogorov and R. Zabin. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 2672514 Feb 2004.
[24] Vladimir Kolmogorov. Minimizing sum of submodular functions. Discrete Appl. Math., 160(15):224-2255 October 2012.
[25] Tarun Kumar, Sankaran Vaidyanathan, Harini Ananthapadmanabhan. Srinivasan Parthasarathy, and Balaraman Ravindran. Hypergraph clustering by iteratively reweighted modularity maxi- mization. Applied Network Science, 5(1):52, 2020.
[26] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Övrank iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS ',, pages 423-433, 2014.
[27] Jianbo Li, Jingrui He, and Yada Zhu. E-tail product return prediction via hypergraph-based local graph cut. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '1, pages 519-527, 2018.
11

---

[28] Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. In Advances Neural Information Processing Systems, NeurIPS '17. pages 2318-2318, 2017.
[29] Pan Li and Olgica Milenkovic. Revisiting decomposable submodular function minimization with incidence relations. In Advances in Neural Information Processing Systems, NeurlPS' 18, page 2242-2252, 2018.
[30] Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-laplacians, Cheeger inequalities and spectral clustering. In Proceedings of the 35th International Conference on Machine Learning, ICML 18, pages 3014-3023, 2018.
[31] Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Téchnologies, pages 510-520, June 2011.
[32] Meng Liu, Nate Veldt, Haoyu Song. Pan Li, and David F. Gleich. Strongly local hypergraph diffusions for clustering and suni-supervieed learning. In Proceedings of the Web Conference 2021, WWW '21, page 2092-2103 103, 2021.
[33] Thomas L. Magnanti and Dan Stratila. Separable concave optimization approximately equals piecewise linear optimization. In Conference on Integer Programming and Combinatorial Optimization, IPCO '04, pages 234-243, 2004.
[34] Thomas L Magnanti and Dan Stratila. Separable concave optimization approximately equals piecewise-linea optimization. https://urrivoor//aa///1101.111 2012.
[35] Robert Nishihara, Stefanie Jegelka, and Michael Jordan. On the convergence rate of decom- posable submodular function minimization. In Advances in Neural Information Processing Systems, NeurIPS 14, pages 640-648, 2014.
[36] James B. Orlin. A faster strongly polynomial time algorithm for submodular function minimiza- tion. Mathematical Programming. 118(2):237-22 251, May 2009.
[37] Pulak Purkait, Tat-Jun Chin, Alireza Sadri, and David Suter. Clustering with hypergraphs: the case for large hyperedges. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997111697 2016.
[38] Shanu, C. Arora, and P. Singla. Min norm point algorithm for higher order MRF-MAP inference. In Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR '1, pages 5365-5374, 2016.
[39] Peter Stobbe and Andreas Krause. Efficient minimization of decomposable submodular func- tions. In Advances in Neural Information Processing Systems, NeurlPS '0, pages 2208-2211 16, 2010.
[40] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and & fr-regression in nearly linear time for dense instances. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages
2021.
[41] Nate Veldt, Austin R. Benson, and Jon Kleinberg. Hypergraph cuts with general splitting functions. arXiv preprint: 2001.02817, 2020.
[42] Nate Veldt, Austin R. Benson, and Jon Kleinberg. Minimizing localized ratio cut objectives in hypergraphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '20, pages 1708-1718, 2020.
[43] 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 '1, page 1604-1614, 2021.
[44] Kai Wei, Rishabh lyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. Proceedings of the 32nd International Conference on Machine Learning, ICMI. "15, pages 1954-1963, 2015.
12

---

[45] Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, pages 555-564, 2017.
[46] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clus- tering, classification, and embedding. In Advances in Neural Information Processing Systems, NeurIPS '06, pages 1601-1608, 2006.
[47] J. Y. Zien, M. D. F. Schlag, and P. K. Chan. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1899):189911399 Sep. 1999.
13


Reviews:
[{"review_id": "iebkTH1sBYb", "reviewer": "Reviewer_tCoX", "summary": "This paper presents an algorithm for minimizing submodular functions that are the sum of cardinality-based components. This is a special case of decomposable submodular function minimization. Formally, the problem considered is to minimize $f(S) = \\sum\\limits_{e\\in E} g_e(|S \\cap e|)$, where $E\\subseteq 2^V$ and $g_e$ are 1-dimensional concave functions. One instance of such functions are the region potentials used in image segmentation, where $g_e(x) = c_e \\cdot x (|e| - x)$ for some constant $c_e \\geq 0$. Such minimization problems are also considered in hypergraph clustering applications.\n\nThe authors propose an approximation algorithm that works by approximately reducing their problem to a graph min cut problem. The fact that concave functions can be _exactly_ represented by graphs is known, and the resulting number of edges in the graph is $O\\left(\\sum\\limits_{e\\in E} |e|^2\\right)$. The main result of the paper is to show how to reduce the number of edges by allowing _approximate_ reductions, leading to a graph with $\\widetilde{O}\\left(\\frac{1}{\\epsilon} \\sum\\limits_{e\\in E} |e|\\right)$ edges while incurring an $(1+\\epsilon)$-multiplicative error in the objective.\n\nThe idea is to simplify each concave function before converting it to a graph. Viewing each concave function as a piecewise linear function, the size of the resulting graph depends on the number of pieces. The authors present an algorithm that is able to find the _best_ (in terms of the number of pieces) $(1+\\epsilon)$-approximation to this function. By known results, the optimal number of pieces is $\\widetilde{O}\\left(\\frac{1}{\\epsilon}\\right)$, thus follows the $\\widetilde{O}\\left(\\frac{1}{\\epsilon} \\sum\\limits_{e\\in E} |e|\\right)$ bound on the number of edges.\n\nFor the special case of the region potentials $g_e(x) = c_e \\cdot x (|e| - x)$, the authors are able to get a better bound of $\\widetilde{O}\\left(\\frac{1}{\\sqrt{\\epsilon}} \\sum\\limits_{e\\in E} |e|\\right)$ on the number of edges.\n\nThe theoretical results are accompanied by experimental results in the problems of image segmentation and hypergraph clustering. For image segmentation, the results show a speedup of at least 3x in 3 out of 4 experiments compared to previous methods, while it is slower in 1 of the 4 experiments. For hypergraph clustering, the F1 score is improved by 3 percentage points at the expense of a 30% runtime increase.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nThe idea of finding the _optimal_ approximation to the concave functions and then turning the new function into a graph is very nice and original to the best of my knowledge. Also, the experimental work gives original insights into the performance of these algorithms.\n\n**Quality**\n\nI checked most of the theoretical results and they are sound. The experimental section is explained well and seems like a fair analysis between different methods, albeit quite limited (e.g. only 4 image segmentation examples). However, I have doubts regarding the theoretical comparison between methods in Section 4. \n\n-The discussion in lines 214-220 seems misguided to me. The fact that exact algorithms don't give a speedup when the error tolerance increases does _not_ make them worse than approximation algorithms. Additionally, the statement about multiplicative approximation doesn't make much sense to me, in the context of comparing to exact algorithms. I would just remove this paragraph.\n\n-In Section 4, it should be emphasized that all previous methods are more general, as they work with arbitrary submodular functions. This is written in other parts of the paper, but should be emphasized in this section which compares different results. In particular, certain runtimes from previous work can be improved in the case of cardinality functions. As an example, in the $\\sum\\limits_{e} |e|^2 \\theta_e$ dependence in [4], the $\\theta_e$ comes from solving problems of the form $\\min_S f_e(S) + w(S)$, where $w$ is linear. If $f_e$ is a cardinality function, these can be easily solved by sorting, immediately improving this term to $\\sum\\limits_{e} |e|^2$.\n\n-On the same note, it seems to me that it might be possible to plug the graph approximation results in the current paper into [4] in an almost black-box way to replace the existing graph approximation routine, in order to give an _exact_ algorithm for Card-DSFM running in time $\\widetilde{O}\\left(T_{mf}(n+R, \\mu)\\right)$. The authors could mention a statement to this effect, as it seems to be a natural connection.\n\n-Another question I had was regarding the region potentials. Since these correspond to complete graphs, one can very easily sparsify them (by uniformly sampling a few edges from them). I am curious how the performance would compare to the authors' approach.\n\n**Clarity**\n\nThe writing is nice in general. I appreciate the authors' sharing the code and data, as well as documentation. I tried to run the code, but it seems that read_data.jl is missing. I also have some minor comments.\n\n-Line 54: “lead” -> “leads”\n\n-Line 148: “solving” -> “solve”\n\n-Line 227: “runtimes” -> “runtime”\n\n-Line 249: “which will faster” -> “which will be faster”\n\n-Line 288: Space missing\n\n-Line 353: “leading to the first approximation algorithms for cardinality-based DSFM” -> “leading to the first approximation algorithms specifically for cardinality-based DSFM”\n\n-Multiple places: “DFSM” -> “DSFM”\n\n**Significance**\n\nThis seems like a result that is significant in practice. As the authors note, cardinality-based functions are common in image segmentation, hypergraph clustering, etc, and this paper improves the runtime considerably in the practical examples tested, although for conclusive statements to be made, more experiments would need to be done.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation that I could find in the paper is that there are not enough experiments to make a conclusive practical evaluation (e.g. only 4 image segmentation examples). The authors have addressed the societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "h6phZYPxeK6", "reviewer": "Reviewer_uhsD", "summary": "This work studies minimizing decomposable submodular functions, which are of the form f(S) = \\sum_{e \\in E}f_e(S \\cap e), where each f_e is a ``simple'' submodular function. In many practical applications, f_e(A) is cardinality based, that is, f_e(A) = g_e(|A|) for some concave function g_e. Several discrete/continuous algorithms have been proposed to minimize such decomposable submodular functions. One combinatorial approach to tackle this problem is to introduce a gadget graph G_e so that, for any A, g_e(|A|) is equal to the minimum cut of G_e subject to A (in addition to some special vertex) being contained in one side of the cut. It is known that any cardinality-based submodular function can be represented this way as a gadget graph of O(|e|) vertices and O(|e|^2) edges.\n\nThe main contribution of this work is providing a method for constructing a gadget graph that ``approximates'' cardinality-based submodular function instead of exactly simulating it. Specifically, it is shown that, to obtain a multiplicative error of 1 \\pm epsilon, we only need O(epsilon^{-1} |e| log |e|) edges. A lower bound of O(epsilon^{-1/2} |e| log |e|) is also shown. When g(x) = x(k-x), which often appears in practice, it is shown that the number of edges can be further improved to O(\\epsilon^{-1/2}log log epsilon^{-1} \\cdot |e|). These results are obtained by approximating the concave function g_e with a piecewise linear function l and then representing l as a gadget graph.\n\nEmpirical results on image segmentation tasks show that the proposed approximate reduction outputs a much smaller gadget graph compared to the exact reduction without much sacrificing the quality of the solution. For example, for some choice of the parameters, the size of the output graph becomes 0.013 (1/0.013?) times smaller while the multiplicative error is merely 1 \\pm 4*10^-3. It is then confirmed that the trade-off of the approximation ratio and runtime of the proposed method is much better than those of other methods. It is also empirically investigated that the quality of hypergraph clustering does not deteriorate much by replacing the objective submodular functions with gadget graphs obtained by the proposed approximate reduction.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The biggest issue in evaluating this work is that I don't fully understand the relevance of this study. I understand that the proposed method outperforms other methods when there are large e's in the input decomposable submodular function. But in practice are there large e's? I understand there are a few of them as in the hypergraph used in the experiment on local clustering, but can't we just ignore those large hyperedges and quickly get a good approximation?\n- Related to the question above, in the image segmentation task, what is the max/average size of e?\n- It is nice that a detailed comparison of time complexity is provided because it is often implicit in the literature, which blurs the difference between existing methods.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "_O4I3LH8DrI", "reviewer": "Reviewer_YQq9", "summary": "This paper proposes a fast approximate method for minimizing decomposable submodular function where each component is cardinality-based. The runtime is improved by exploiting sparse piecewise linear approximation to concave functions at integer points, which is combined with graph reduction to convert the original minimization problem as an s-t cut problem on a sparse graph. Empirical results show that the mehtod can be faster than state-of-the-art numerical methods. Moreover, the approximation ratios are generally much smaller than the worst-case approximation guarantee.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Decomposable submodular function minimization has many applications in machine learning. This paper considers a specific setting where the components are cardinality-based submodular functions. While the results obtained in this paper are interesting, they are not very surprising.\n\nOverall, the paper is very well written and nicely structured. Theoretical analyses appear to be adequate. The proposed method can be a nice tool to have. However, the experiments do not seem to provide a strong evidence for the significance of this work. In particular, the running time of existing numerical methods does not seem to be a limiting factor that prevents the use of cardinality-based submodular functions in the two applications presented in the experiments. For example, for the hypergraph clustering case, why can't ACDM be applied? Are there hypergraph clustering experiments where the proposed method is compared with existing numerical methods?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I cannot think of any potential negative societal impact based on this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "UNKRAwpp_t8", "reviewer": "Reviewer_dwqT", "summary": "The paper tackles the problem of cardinality-based decomposable submodular function minimization (Card-DSFM). DSFMs have been a popular topic of research, and the authors claim that the case when every component function is a cardinality based concave function is an important one in practical applications. For this subproblem, they derive the first approximation algorithms via reduction to sparse graph cuts.\n\nGiven a concave cardinality function, the aim is to model it via gadgets (directed graphs on which we will solve a max-flow instance). The authors show that the problem of finding such gadgets is equivalent to finding piecewise linear functions which can approximate the original function with minimum number of linear components. This problem is solved using a greedy method, which gives a better bound on the number of pieces than existing methods.\n\nOnce these are optimally computed, they are converted into equivalent gadgets. Once all gadgets are combined into a graph, a max-flow instance is run. The obtained minimum cut also gives a solution to the underlying Card-DSFM.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results in this paper apply to a wide variety of practical problems, and formulating theoretical bounds for this problem as an approximation algorithm is a valuable contribution. \nTheoretical details are rigorously proved and much effort is gone into formalizing definitions and theorems for this problem. As the paper shows, the results outdo previous baseline results theoretically, even in the case of exact computation. These theoretical contributions, by themselves, are valuable and warrant acceptance in my opinion.\n\nThe experiments are also strong, and are able to showcase the strength of the method, in terms of getting better approximations in faster time as opposed to competing methods. The paper also showcases the effectiveness in using the proposed technique as an approximate reduction to graphs for existing methods, and shows improvements in runtimes.\n\nThe writing overall is of good quality. The authors do a good job of giving intuition about the technical details in words - however, this can still be improved upon in Section 3.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors make a genuine effort into analyzing their limitations, and also talk in some detail about possible negative societal effects of their work on impacts of the paper. There is a clear mention of how it only solves a particular class of problems, as compared to existing methods.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciate the problem and the technical contribution of the paper.
Decision: Accept (Poster)