Hypergraphs are a generalization of graphs in which nodes are organized into multiway relationships called hyperedges. Given a hypergraph H = (V, E) and a set of nodes S ⊆ V , a hyperedge e ∈ E is said to be cut by S if both S andS = V \S contain at least one node from e. Developing efficient algorithms for cut problems in hypergraphs is an active area of research in theoretical computer science [15-17, 23, 36] , and has been applied to problems in VLSI layout [4, 28, 35] , sparse matrix partitioning [2, 6] , and machine learning [44, 46, 67] .
Here, we consider recently introduced generalized hypergraph cut functions [44, 46, 66, 70] , which assign different penalties to cut hyperedges based on how the nodes of a hyperedge are split into different sides of the bipartition induced by S. To define a generalized hypergraph cut function, each hyperedge e ∈ E is first associated with a splitting function w e : A ⊆ e → R + that maps each node configuration of e (defined by the subset A ⊆ e in S) to a nonnegative penalty. In order to mirror edge cut penalties in graphs, splitting functions are typically assumed to be symmetric (w e (A) = w e (e\A)) and only penalize cut hyperedges (i.e., w e (∅) = 0). The generalized hypergraph cut function for a set S ⊆ V is then given by cut H (S) = e∈E w e (S ∩ e) .
(1)
The standard hypergraph cut function is all-or-nothing, meaning it assigns the same penalty to a cut hyperedge regardless of how its nodes are separated. Using the splitting function terminology, this means that w e (A) = 0 if A ∈ {e, ∅}, and w e (A) = w e otherwise, where w e is a scalar hyperedge weight. One particularly relevant class of splitting function are submodular functions, which for all A,B ⊆ e satisfy w e (A) + w e (B) ≥ w e (A ∩ B) + w e (A ∪ B). When all hyperedge splitting functions are submodular, solving generalized hypergraph cut problems is closely related to minimizing a decomposable submodular function [20, 21, 39, 45, 54, 64] , which in turn is closely related to energy minimization problems often encountered in computer vision [24, 37, 38] . The standard graph cut function is another well-known submodular special case of (1).
One of the most common techniques for solving hypergraph cut problems is to reduce the hypergraph to a graph sharing similar (or in some cases identical) cut properties. Arguably the most widely used reduction technique is clique expansion, which replaces each hyperedge with a (possibly weighted) clique [10, 28, 44, 71, 73] . In the unweighted case this corresponds to applying a splitting function of the form: w e (A) = |A| · |e\A|. Previous work has also explored other classes of submodular hypergraph cut functions that can be modeled as a graph cut problem on a potentially augmented node set [24, 37, 38, 41, 66] . This research primarily focuses on proving when such a reduction is possible, regardless of the number of edges and auxiliary nodes needed to realize the reduction. However, because hyperedges can be very large and splitting functions may be very general and intricate, many of these techniques lead to large and dense graphs. Therefore, the reduction strategy significantly affects the runtime and practicality of algorithms that run on the reduced graph. This leads to several natural questions. Are the graph sizes resulting from existing techniques inherently necessary for modeling hypergraph cuts? Given a class of functions that are known to be graph reducible, can one determine more efficient or even the most efficient reduction techniques? Finally, is it possible to obtain more efficient reductions and faster downstream algorithms if it is sufficient to just approximately model cut penalties?
To answer these questions, we present a novel framework for sparsifying hypergraph-to-graph reductions with provable guarantees on preserving cut properties. Our framework brings together concepts and techniques from several different theoretical domains, including algorithms for solving generalized hypergraph cut problems [44, 46, 66, 70] , standard graph sparsification techniques [8, 60, 62] , and tools for approximating functions with piecewise linear curves [49, 50] . We present sparsification techniques for a large and natural class of submodular splitting functions that are cardinality-based, meaning that w e (A) = w e (B) whenever |A| = |B|. These are known to always be graph reducible, and are particularly natural for several downstream applications [66] . Our approach leads to graph reductions that are significantly more sparse than previous approaches, and we show that our method is in fact optimally sparse under a certain type of reduction strategy. Our sparsification framework can be directly used to develop faster algorithms for approximately solving hypergraph s-t cut problems [66] , and improve runtimes for a large class of cardinality-based decomposable submodular minimization problems [33, 37, 39, 64] . We also show how our techniques enable us to develop efficient sparsifiers for graphs constructed from co-occurrence data.
Our framework and results share numerous connections with existing work on graph sparsification, which we review here. Let G = (V, E) be a graph with a cut function cut G , which can be viewed as a very restricted case of the generalized hypergraph cut function in Eq. (1) . An ε-cut sparsifier for G is a sparse weighted and undirected graph H = (V, F ) with cut function cut H , such that
for every subset S ⊆ V . This definition was introduced by Benczúr and Karger [9] , who showed how to obtain a sparsifier with O(n log n/ε 2 ) edges for any graph in O(m log 3 n) time for an n-node, m-edge graph. The more general notion of spectral sparsification, which approximately preserves the Laplacian quadratic form of a graph rather than just the cut function, was later introduced by Spielman and Teng [61] . The best cut and spectral sparsifiers have O(n/ε 2 ) edges, which is known to be asymptotically optimal for both spectral and cut sparsifiers [5, 8] . Although studied much less extensively, analogous definitions of cut [17, 36] and spectral [60] sparsifiers for hypergraphs have also been developed. However, these apply exclusively to the all-or-nothing cut penalty, and do not preserve generalized cut functions of the form shown in (1). Bansal et al. [7] also considered a weaker notion of graph and hypergraph sparsification, involving additive approximation terms, but in the present work we only consider multiplicative approximations.
In this paper, we introduce an alternative notion of an augmented cut sparsifier. We present our results in the context of hypergraph-to-graph reductions, though our framework also provides a new notion of augmented sparsifiers for graphs. Let H = (V, E) be a hypergraph with a generalized cut function cut H , and letĜ = (V ∪ A,Ê) be a directed graph on an augmented node set V ∪ A. The graph is equipped with an augmented cut function defined for any S ⊆ V by
where dircutĜ is the standard directed cut function onĜ. We say thatĜ is an ε-augmented cut sparsifier for H if it is sparse and satisfies cut H (S) ≤ cutĜ(S) ≤ (1 + ε)cut H (S).
The minimization involved in (3) is especially natural when the goal is to approximate a minimum cut or minimum s-t cut in H. If we solve the corresponding cut problem inĜ, nodes from the auxiliary node set A will be automatically arranged in a way that yields the minimum directed cut penalty, as required in (3) . IfŜ * is the minimum cut inĜ, S * = V ∩Ŝ * will be a (1+ε)-approximate minimum cut in G. Even when solving a minimum cut problem is not the goal, our sparsifiers will be designed in such a way that the augmented cut function (3) will be easy to evaluate. Unlike the standard graph sparsification problem, in some cases it may in fact be impossible to find any directed graphĜ satisfying (4) , independent of the graph's density. In recent work we showed that hypergraphs with non-submodular splitting functions are never graph reducible [66] . Zivný et al. [74] showed that even in the case of four-node hyperedges, there exist submodular splitting functions (albeit asymmetric splitting functions) that are not representable by graph cuts. Nevertheless, there are several special cases in which graph reduction is possible [24, 37, 38] .
Augmented Sparsifiers for Cardinality-Based Hypergraph Cuts We specifically consider the class of submodular splitting functions that are cardinality-based, meaning they satisfy w e (A) = w e (B) whenever A, B ⊆ e satisfy |A| = |B|. These are known to be graph reducible [37, 66] , though existing techniques will reduce a hypergraph H = (V, E) to a graph with O(|V | + e∈E |e|) nodes and O( e∈E |e| 2 ) edges. We prove the following sparse reduction result. For certain types of splitting functions (e.g., the one corresponding to a clique expansion), we show that our reductions are even more sparse.
Augmented Sparsifiers for Graphs Another relevant class of augmented sparsifiers to consider is the setting where H is simply a graph. In this case, if A is empty and all edges are undirected, condition (4) reduces to the standard definition of a cut sparsifier. A natural question is whether there exist cases where allowing auxiliary nodes and directed edges leads to improved sparsifiers. We show that the answer is yes in the case of dense graphs constructed from co-occurrence data.
Augmented Spectral Sparsifiers Just as spectral sparsifiers generalize cut sparsifiers in the standard graph setting, one can define an analogous notion of an augmented spectral sparsifier for hypergraph reductions. This can be accomplished using existing hypergraph generalizations of the Laplacian operator [14, 46, 47, 70] . However, although developing augmented spectral sparsifiers constitutes an interesting open direction for future research, it is unclear whether the techniques we develop here can be used or adapted to spectrally approximate generalized hypergraph cut functions. We include further discussion on hypergraph Laplacians and spectral sparsifiers in Section 7, and pose questions for future work. Our primary focus in this manuscript is to develop techniques for augmented cut sparsifiers.
Graph reduction techniques work by replacing a hyperedge with a small graph gadget modeling the same cut properties as the hyperedge splitting function. The simplest example of a graph reducible function is the quadratic splitting function, which we also refer to as the clique splitting function: This function can be modeled by replacing a hyperedge with a clique (Figure 1b ). Another function that can be modeled by a gadget is the linear penalty, which can be modeled by a star gadget [73] :
A star gadget ( Figure 1a ) contains an auxiliary node v e for each e ∈ E, which is attached to each v ∈ e with an undirected edge. In order to model the broader class of submodular cardinalitybased splitting functions, we previously introduced the cardinality-based gadget [66] (CB-gadget) ( Figure 1c ). This gadget is parameterized by positive scalars a and b, and includes two auxiliary nodes e and e . For each node v ∈ e, there is a directed edge from v to e and a directed edge from e to v, both of weight a. Lastly, there is a directed edge from e to e of weight a · b. This CB-gadget corresponds to the following splitting function:
Every submodular, cardinality-based (SCB) splitting function can be modeled by a combination of CB-gadgets with different edge weights [66] . A different reduction strategy for minimizing submodular energy functions with cardinality-based penalties was also previously developed by Kohli et al. [37] . Both techniques require up to O(k 2 ) directed edges for a k-node hyperedge.
Sparse Combinations of CB-gadgets Our work introduces a new framework for approximately modeling submodular cardinality-based (SCB) splitting functions using a small combinations of CB-gadgets. Figure 2 illustrates our sparsification strategy. We first associate an SCB splitting function with a set of points {(i, w i )}, where i represents the number of nodes on the "small side" of a cut hyperedge, and w i is the penalty for such a split. We show that when many of these points are collinear, they can be modeled with a smaller number of CB-gadgets. As an example, the star expansion penalties (6) can be modeled with a single CB-gadget (Figures 2a and 2d) , whereas modeling the quadratic penalty with previous techniques [66] requires many more (Figures 2b  and 2e ). Given this observation, we design new techniques for ε-approximating the set of points {(i, w i )} with a piecewise linear curve using a small number linear pieces. We then show how to translate the resulting piecewise linear curve back into a smaller combination of CB-gadgets that ε-approximates the original splitting function. Our piecewise linear approximation strategy allows us to find the optimal (i.e., minimum-sized) graph reduction in terms of CB-gadgets. When ε = 0, our approach finds the best way to exactly model an SCB splitting function, and requires only half the number of gadgets needed by previous techniques [66] . More importantly, for larger ε, we prove the following sparse approximation result, which is used to prove Theorem 1.1. (6) can be modeled by a sparse gadget (d). The quadratic splitting function (5) penalties (b) can be modeled by a dense gadget (e). A piecewise linear approximation for the quadratic splitting penalties (c) corresponds to a sparse gadget (f).
Theorem 1.2. For ε ≥ 0, any submodular cardinality-based splitting function on a k-node hyperedge can be ε-modeled by combining O(min{log k/ε, k}) CB-gadgets.
We show that a nearly matching lower bound of O(log k/ √ ε) CB-gadgets is required for modeling a square root splitting function. Despite worst case bounds, we prove that only O(ε −1/2 log log 1 ε ) CB-gadgets are needed to approximate the quadratic splitting function, independent of hyperedge size. This is particularly relevant for approximating the widely used clique expansion technique, as well as for modeling certain types of dense co-occurrence graphs. All of our sparse reduction techniques are combinatorial, deterministic, and very simple to use in practice.
When H is just a graph, augmented sparsifiers correspond to a generalization of standard cut sparsifiers that allow directed edges and auxiliary nodes. The auxiliary nodes in this case play a role analogous to Steiner nodes in finding minimum spanning trees. Just as adding Steiner nodes makes it possible to find a smaller weight spanning tree, it is natural to ask whether including an auxiliary node set might lead to better cut sparsifiers for a graph G. We show that the answer is yes for certain classes of dense co-occurrence graphs, which are graphs constructed by inducing a clique on a set of nodes that share a certain property or participate in a certain type of group interaction (equivalently, clique expansions of hypergraphs). Steiner nodes have in fact been previously used in constructing certain types of sparsifiers called vertex and flow sparsifiers [18] . However, these are concerned with preserving certain routing properties between distinguished terminal nodes in a graph, and are therefore distinct from our goal of obtaining ε-cut sparsifiers.
Sparsifying the complete graph Our ability to sparsify the clique splitting function (5) directly implies a new approach for sparsifying a complete graph. Cut sparsifiers for the complete graph provide a simple case study for understanding the differences in sparsification guarantees that can be obtained when we allow auxiliary nodes and directed edges. Furthermore, better sparsifiers for the complete graph can be used to design useful sparsifiers for co-occurrence graphs. We have the following result. Theorem 1.3. Let G = (V, E) be the complete graph on n = |V | nodes. There exists an εaugmented sparsifier for G with O(n) nodes and O(nε −1/2 log log 1 ε ) edges. By comparison, the best standard cut and spectral sparsifiers for the complete graph have exactly n nodes and O(n/ε 2 ) edges. This is tight for spectral sparsifiers [8] , as well as for degreeregular cut sparsifiers with uniform edge weights [3] . Thus, by adding a small number of auxiliary nodes, our sparsifiers enable us to obtain a significantly better dependence on ε when cut-sparsifying a complete graph. Our sparsifier is easily constructed deterministically in O(nε −1/2 log log 1 ε ) time. Standard undirected sparsifiers for the complete graph have received significant attention as they correspond to expander graphs [3, 8, 48, 51] . We remark that the directed augmented cut sparsifiers we produce are very different in nature and should not be viewed as expanders. In particular, unlike for expander graphs, random walks on our complete graph sparsifiers will converge to a very non-uniform distribution. We are interested in augmented sparsifiers for the complete graph simply for their ability to model cut properties in a different way, and the implications this has for sparsifying hypergraph clique expansions and co-occurrence graphs.
Sparsifying co-occurrence graphs Co-occurrence relationships are inherent in the construction of many types of graphs. Formally, consider a set of n = |V | nodes that are organized into a set of co-occurrence interactions C ⊆ 2 V . Interaction c ∈ C is associated with a weight w c > 0, and an edge between nodes i and j is created with weight w ij = c∈C:i,j∈c w c . When w c = 1 for every c ∈ C, w ij equals the number of interactions that i and j share. We use d avg to denote the average number of co-occurrence interactions in which nodes in V participate. The cut value in the resulting graph G = (V, E) for a set S ⊆ V is given by the following co-occurrence cut function:
Graphs with this co-occurrence cut function arise frequently as clique expansions of a hypergraph [10, 28, 71, 73] , or as projections of a bipartite graph [42, 52, 53, 57, 63, 69, 72] . Even when the underlying dataset is not first explicitly modeled as a hypergraph or bipartite graph, many approaches implicitly use this approach to generate a graph from data. When enough group interaction sizes are large, G becomes dense, even if |C| is small. We can significantly sparsify G by applying an efficient sparsifier to each clique induced by a co-occurrence relationship. Importantly, we can do this without ever explicitly forming G. By applying Theorem 1.3 as a black-box for clique sparsification, we obtain the following result.
Theorem 1.4. Let G = (V, E) be the co-occurrence graph for some C ⊆ 2 V and let n = |V |. For ε > 0, there exists an augmented sparsifierĜ with O(n + |C| · f (ε)) nodes and O(n · d avg · f (ε)) edges, where f (ε) = ε −1/2 log log 1 ε . In particular, if d avg is constant and for some δ > 0 we have c∈C |c| 2 = Ω(n 1+δ ), then forming G explicitly takes Ω(n 1+δ ) time, but an augmented sparsifier for G with O(nf (ε)) nodes and O(nf (ε)) edges can be constructed in O(nf (ε)) time.
Importantly, the average co-occurrence degree d avg is not the same as the average node degree in G, which will typically be much larger. Theorem 1.4 highlights that in regimes where d avg is a constant, our augmented sparsifiers will have fewer edges than the number needed by standard Table 1 : Runtimes for cardinality-based decomposable submodular function minimization, and bounds for special regimes. k = k avg = µ/R is the average hyperedge size. For IBFS when k = Θ(n), we simply list lower bounds indicating why these methods are not practical in this case.
IBFS Strong [20, 22] O(n 2 θ max e |e| 2 ) O(n 2 ) Ω(n 5 ) Ω(n 4 R) IBFS Weak [20, 22] Õ(n 2 θ max + n e |e| 4 )Õ(n 2 ) Ω(n 5 ) Ω(n e |e| 4 ) ACDM [20, 21] 
This paperÕ min Rk
ε-cut sparsifiers. In Section 5, we consider simple graph models that satisfy these assumptions. We also consider tradeoffs between our augmented sparsifiers and standard sparsification techniques for co-occurrence graphs. Independent of the black-box sparsifier we used, implicitly sparsifying G in this way will often lead to significant runtime improvements over forming G explicitly.
Typically in hypergraph cut problems it is natural to assume that splitting functions are symmetric and satisfy w e (∅) = w e (e) = 0. However, we show that our sparse reduction techniques apply even when these assumptions do not hold. This allows us to design fast algorithms for approximately solving cardinality-based decomposable submodular minimization problems. Formally a function f : 2 V → R + is a decomposable submodular function if it can be written as
where each f e is a submodular function defined on a set e ⊆ V . Following our previous notation and terminology, we say f e is cardinality-based if f e (S) = g e (|S|) for some concave function g e . This special case has also received some attention in previous literature on decomposable submodular function minimization [33, 37, 39, 64] . Existing approaches for minimizing these functions focus largely on finding exact solutions. Using our sparse reduction techniques, we develop the first fast algorithms for approximately solving the problem. Let n = |V |, R = |E|, and µ = e∈E |e|. In Appendix B, we show that a result similar to Theorem 1.1 also holds for more general cardinalitybased splitting functions. In Section 6, we combine that result with the s-t cut solvers of Goldberg and Rao [27] to prove the following theorem.
Theorem 1.5. Let ε > 0. Any cardinality-based decomposable submodular function can be minimized to within a multiplicative (1 + ε) factor inÕ(min{ε −3/2 µ 3/2 , ε −1 µ(n + ε −1 R) 2/3 }) time.
We compare this runtime against the best previous techniques for exactly minimizing sums of cardinality-based submodular functions. We summarize runtimes for competing approaches in Table 1 , which includes both strongly polynomial and weakly polynomial methods, the latter of which assume integer-valued functions. We again note that the runtimes for competing approaches are for finding exact minimizers, whereas our approach provides a (1+ε) guarantee. Our techniques enable us to highlight regimes of the problem where we can obtain significantly faster algorithms in cases where it is sufficient to solve the problem approximately. For example, whenever n = Ω(R), our algorithms for finding approximate solutions provide a runtime advantage -often a significant one -over approaches for computing an exact solution.
A generalized hypergraph cut function is defined as the sum of its splitting functions. Therefore, if we can design a technique for approximately modeling a single hyperedge with a sparse graph, this in turn provides a method for constructing an augmented sparsifier for the entire hypergraph. We now formalize the problem of approximating a submodular cardinality-based (SCB) splitting function using a combination of cardinality-based (CB) gadgets. We abstract this as the task of approximating a certain class of functions with integer inputs (equivalent to SCB splitting functions), using a small number of simpler functions (equivalent to cut properties of the gadgets). Let 
We denote the set of r-SCB integer functions by S r .
The value w(i) represents the splitting penalty for placing i nodes on the small side of a cut hyperedge. In previous work we showed that the inequalities given in Definition 2.1 are necessary and sufficient conditions for a cardinality-based splitting function to be submodular [66] . The r-SCB integer function for a CB-gadget with edge parameters (a, b) (see (7)) is
Combining J CB-gadgets produces a combined r-SCB integer function of special importance.
Definition 2.
2. An r-CCB ( Combined Cardinality-Based gadget) function of order J, is an r-SCB integer functionŵ with the form
where the t-dimensional vectors a = (a j ) and b = (v j ) parameterizingŵ satisfy:
We denote the set of r-CCB functions of order J by C J r .
The conditions on the vectors a and b come from natural observations about combining CBgadgets. Condition (15) ensures that we do not consider CB-gadgets where all edge weights are zero. The ordering in condition (16) is for convenience; the fact that b j values are all distinct implies that we cannot collapse two distinct CB-gadgets into a single CB-gadget with new weights.
For condition (17) , observe that for any b J ≥ r, min{i, b J } = i for all i ∈ [r]. For a helpful visual, note that the r-SCB function in (13) represents splitting penalties for the CB-gadget in Figure 1c . An r-CCB function corresponds to a combination of CB-gadgets, as in Figures 2c and 2f .
In previous work we showed that any combination of CB-gadgets produces a submodular and cardinality-based splitting function, which is equivalent to stating that C J r ⊆ S r for all J ∈ N [66] . Furthermore, C r r = S r , since any r-SCB splitting function can be modeled by a combination of r CB-gadgets. Our goal here is to determine how to approximate a function w ∈ S r with some functionŵ ∈ C J r where J r. This corresponds to modeling an SCB splitting function using a small combination of CB-gadgets. Definition 2.3. For a fixed w ∈ S r and an approximation tolerance parameter ε ≥ 0, the Sparse Gadget Approximation Problem ( Spa-GAP) is the following optimization problem:
Upper Bounding Approximations Problem (18) specifically optimizes over functionsŵ that upper bound w. This restriction simplifies several aspects of our analysis without any practical consequence. For example, we could instead fix some δ ≥ 1 and optimize over functionsw satisfying 1 δ w ≤w ≤ δw. However, this implies that the functionŵ = δw satisfies w ≤ŵ ≤ (1 + ε)w, with ε = δ 2 − 1. Thus, the problems are equivalent for the correct choice of δ and ε.
Motivation for Optimizing over CB-gadgets A natural question to ask is whether it would be better to search for a sparsest approximating gadget over a broader classes of gadgets. There are several key reasons why we restrict to combinations of CB-gadgets. First of all, we already know these can model any SCB splitting function, and thus they provide a very simple building block with broad modeling capabilities. Furthermore, it is clear how to define an optimally sparse combination of CB-gadgets: since all CB-gadgets for a k-node hyperedge have the same number of auxiliary nodes and directed edges, an optimally sparse reduction is one with a minimum number of CBgadgets. If we instead wish to optimize over all possible gadgets, it is likely that the best reduction technique will depend on the splitting function that we wish to approximate. Furthermore, the optimality of a gadget may not even be well-defined, since one must take into account both the number of auxiliary nodes as well as the number of edges that are introduced, and the tradeoff between the two is not always clear. Finally, as we shall see in the next section, by restricting to CB-gadgets, we are able to draw a useful connection between sparse gadgets and approximating piecewise linear curves with a smaller number of linear pieces.
We begin by defining the class of piecewise linear functions in which we are interested.
4. f is piecewise linear 5. f is concave (and hence, continuous).
It will be key to keep track of the number of linear pieces that make up a given function f ∈ F r . Let L be the set of linear functions with nonnegative slopes and intercept terms:
Every function f ∈ F r can be characterized as the lower envelope of a set of these linear functions.
We use |L| to denote the number of linear pieces of f . In order for (20) to properly characterize a function in F r , it must be constant for all x ≥ r (property 2 in Definition 3.1), and thus L must contain exactly one line of slope zero. The continuous extensionf of an r-CCB function w parameterized by (a, b) is defined aŝ
We prove that continuously extending any r-CCB function always produces a function in F r .
Conversely, every f ∈ F r is the continuous extension of some r-CCB function. Appendix A provides proofs for these results.
Lemma 3.1. Letf be the continuous extension for w, shown in (21) . This function is in the class F r , and has exactly J positive sloped linear pieces, and one linear piece of slope zero. 
Let w ∈ S r be an arbitrary SCB integer function. Lemma 3.2 implies that if we can find a piecewise linear function f that approximates w and has few linear pieces, we can extract from it a CCB functionŵ with a small order J that approximates w. Equivalently, we can find a sparse gadget that approximates an SCB splitting function of interest. Our updated goal is therefore to solve the following piecewise linear approximation problem, for a given w ∈ S r and ε ≥ 0:
The last constraint ensures that each linear piece g ∈ L we consider crosses through at least one point (j, w(j)). We can add this constraint without loss of generality; if any linear piece g is strictly greater than w at all integers, we could obtain an improved approximation by scaling g until it is tangent to w at some point. This constraint, together with the requirement f ∈ F r , implies that the constant function g (r) (x) = w(r) is contained in every set of linear functions L that is feasible Figure 3 : We restrict our attention to lines in L that coincide with w at at least one integer value. Thus, every function we consider is incident to two consecutive values of w (e.g., the solid line, g (1) ), or, it touches w at exactly one point (dashed line, g).
for (22) . Since all feasible solutions contain this constant linear piece, our focus is on determining the optimal set of positive-sloped linear pieces needed to approximate w. Optimal linear covers. Given a fixed ε ≥ 0 and i ∈ {0} ∪ [r − 1], we will say a set L ⊂ L is a linear cover for a function w ∈ S r over the range R = {i, i + 1, . . . , r}, if each g ∈ L upper bounds w at all points, and if for each j ∈ R there exists g ∈ L such that g(j) ≤ (1 + ε)w(j). The set L is an optimal linear cover if it contains the minimum number of positive-sloped linear pieces needed to cover R. Thus, an equivalent way of expressing (22) is that we wish to find an optimal linear cover for w over the interval {0} ∪ [r]. In practice there may be many different function f ∈ F r which solve (22) , but for our purposes it suffices to find one.
We solve problem (22) by iteratively growing a set of linear functions L ⊂ L one function at a time, until all of w is covered. Let f be the piecewise linear function we construct from linear pieces in L. In order for f to upper bound w, every function g ∈ L in problem (22) must upper bound w at every i ∈ {0} ∪ [r]. One way to obtain such a linear function is to connect two consecutive points of w. For i ∈ {0} ∪ [r − 1], we denote the line joining points (i, w(i)) and (i + 1, w(i + 1)) by
where the slope of the line is
In order for a line to upper bound w but only pass through a single point (i, w(i)) for some i ∈ [r − 1], it must have the form
where the slope m satisfies M i < m < M i−1 . The existence of such a line g is only possible when the points (i − 1, w(i − 1)), (i, w(i)), and (i + 1, w(i + 1)) are not collinear. To understand the strict bounds on m, note that if g passes through (i, w(i)) and has slope exactly M i−1 , then g is in fact the line g (i−1) and also passes through (i − 1, w(i − 1)). If g has slope greater than M i−1 , then g(i − 1) < w(i − 1) and does not upper bound w everywhere. We can similarly argue that the slope of g must be strictly greater than M i so that it does not touch or cross below the point (i + 1, w(i + 1)). We illustrate both types of functions (23) and (24) in Figure 3 . The following simple observation will later help in comparing approximation properties of different functions in L.
Observation 3.1. For a fixed w ∈ S r , let g, h ∈ L both upper bound w at all integers i ∈ {0} ∪ [r], and assume that for some j ∈ {0} ∪ [r], g(j) = h(j) = w(j). If m g and m h are the slopes of g and h respectively, and m g ≥ m h ≥ 0, then
In other words, if g and h are both tangent to w at the same point j, but g has a larger slope than h, then g provides a better approximation for values smaller than j, while h is the better approximation for values larger than j.
The first linear piece. Every set L solving (22) must include a linear piece that goes through the origin, so that f (0) = 0. We specifically choose (1)x to be the first linear piece in the set L we construct. Given this first linear piece, we can then compute the largest integer i ∈ [r] for which g (0) provides a (1 + ε)-approximation:
The integer = p + 1 therefore is the smallest integer for which we do not have a (1 + ε)approximation. If ≤ r, our task is then to find the smallest number of additional linear pieces in order to cover { , . . . , r} with (1 + ε)-approximations. By Observation 3.1, any other g ∈ L with g(0) = 0 and g(1) > w(1) will be a worse approximation to w at all integer values:
. Therefore, as long as we can find a minimum set of additional linear pieces which provides a (1 + ε)-approximation for all { , . . . , r}, our set of functions L will optimally solve objective (22) .
Iteratively finding the next linear piece. Consider now a generic setting in which we are given a left integer endpoint and we wish to find linear pieces to approximate the function w from to r. We first check whether the constant function g (r) (x) = w(r) provides the desired approximation:
If so, we augment L to include g (r) and we are done, since this implies that g (r) also provides at least a (1 + ε)-approximation at every i ∈ { , + 1, . . . , r}. If (25) is not true, we must add another positive-sloped linear function to L in order to get the desired approximation for all i ∈ [r]. We adopt a greedy approach that chooses the next line to be the optimizer of the following objective
In other words, solving problem (26) means finding a function that provides at least a (1 + ε)approximation from to as far towards r as possible in order to cover the widest possible contiguous interval with the same approximation guarantee. (There is always a feasible point by adding a line g tangent to w( ).) The following Lemma will help us prove that this greedy scheme produces an optimal cover for w. Lemma 3.3. Let p * the solution to (26) and g * be the function that achieves it. IfL ⊂ L is an optimal cover for w over the integer range {p * + 1, p * + 2, . . . r}, then {g * } ∪L is an optimal cover for { , + 1, . . . r}.
Proof. LetL be an arbitrary optimal linear cover for w over the range { , + 1, . . . , r}. This means that |L ∪ {g * }| ≥ |L|. We knowL must contain a function g such that g( ) ≤ (1 + ε)w( ). Let p g be the largest integer satisfying g(p g ) ≤ (1 + ε)w(p g ). By the optimality of p * and g * , we know p * ≥ p g . Therefore, the set of functionsL − {g} must be a cover for the set {p g + 1, p g + 2, . . . r} ⊇ {p * + 1, p * + 2, . . . r}. SinceL is an optimal cover for a subset of the integers covered byL − {g},
Therefore, |L ∪ {g * }| = |L|, so the result follows.
We illustrate a simple procedure for solving (26) in Figure 4 . The function g solving (26) must either join two consecutive points of w (the form given in (23)), or coincide at exactly one point of w (form given in (24)). We first identify the integer j * such that
In other words, the linear piece connecting (j * , w(j * )) and (j * + 1, w(j * + 1)) provides the needed approximation at the left endpoint , but g (i) for every i > j * does not. Therefore, the solution to (26) has a slope m ∈ [M j * , M j * +1 ), and passes through the point (j * , w(j * )). By Observation 3.1, the line passing through this point with the smallest slope is guaranteed to provide the best approximation for all integers p ≥ j * . To minimize the slope of the line while still preserving the needed approximation at w( ), we select the line passing through the points ( , (1 + ε)w( )) and (j * , w(j * )). This is given by
After adding this function g * to L, we find the largest integer p ≤ r such that g * (p) ≤ (1 + ε)w(p).
If p < r, then we still need to find more linear pieces to approximate w, so we continue with another iteration. If p = r exactly, then we do not need any more positive-sloped linear pieces to approximate w. However, we still add the constant function g (r) to L before terminating. This guarantees that the function f (x) = min g∈L (x) we return is in fact in F r . Furthermore, adding the constant function serves to improve the approximation, without affecting the order of the CCB function we will obtain from f by applying Lemma 3.2. Pseudocode for our procedure for constructing a set of function L is given in Algorithm 1, which relies on Algorithm 2 for solving (26) . We summarize with a theorem about the optimality of our method for solving (22) . Proof. The optimality of the algorithm follows by inductively applying Lemma 3.3 at each iteration of the algorithm. For the runtime guarantee, note first of all that we can compute and store all slopes and intercepts for linear pieces g (i) (as given in (23)) in O(r) time and space. As the algorithm progresses, we visit each integer i ∈ [r] once, either to perform a comparison of the form g (i) ( ) ≤ (1 + ε)w( ) for some left endpoint , or to check whether g * (i) ≤ (1 + ε)w(i) for some linear piece g * we added to our linear cover L. Each such g * can be computed in constant time, and as a loose bound we know we compute at most O(r) such linear pieces for any ε. : Given a left endpoint for which we do not yet have a (1 + ε)-approximate piece, we find the next linear piece by choosing a function g * that provides the desired approximation at , while also providing a good approximation for as large of an integer p > as possible.
By combining Algorithm 2 and Lemma 3.2, we are able to efficiently solve Spa-GAP.
Theorem 3.5. Let f be the solution to (22) , andŵ be the CCB function obtained from Lemma 3.2 based on f . Thenŵ optimally solves the sparse gadget approximation problem (18) .
Proof. Since f andŵ coincide at integer values, and f approximates w at integer values, we know w(i) ≤ŵ(i) ≤ (1 + ε)w(i) for i ∈ [r]. Thus,ŵ is feasible for objective (18) . If κ * is the number of positive-sloped linear pieces of f , then the order ofŵ is κ * by Lemma 3.2, and this must be optimal for (18) . If it were not optimal, this would imply that there exists some upper bounding CCB function w of order κ < κ * that approximates w to within 1 + ε. But by Lemma 3.1, this would imply that the continuous extension of w is some f ∈ F r with exactly κ positive-sloped linear pieces that is feasible for objective (22) , contradicting the optimality of f .
In our last section we showed an efficient strategy for finding the minimum number of linear pieces needed to approximate an SCB integer function. We now consider bounds on the number of needed linear pieces in different cases, and highlight implications for sparsifying hyperedges with SCB splitting functions. In the worst case, we show that we need O(log k/ε) gadgets, where k is the size of the hyperedge. Moreover, this is nearly tight for the square root splitting function. Finally, we show that we only need O(ε −1/2 log log 1 ε ) gadgets to approximate the clique splitting function. This result is useful for sparsifying co-occurrence graphs and clique expansions of hypergraphs.
We begin by showing that a logarithmic number of CB-gadgets is sufficient to approximate any SCB splitting function.
Algorithm 1 FindBest-PL-Approx(w, ε) (solves (22) )
Algorithm 2 FindNext(w, ε, ) (solves (26)) Proof. Let r = k/2 , and let w ∈ S r be the SCB integer function corresponding to w e , i.e., w(i) = w e (A) for A ⊆ e such that |A| ∈ {i, k − i}. If we join all points of the form (i, w(i)) for i ∈ [r] by a line, this results in a piecewise linear function f ∈ F r that is concave and increasing on the interval [0, r]. We first show that there exists a set of O(log 1+ε r) linear pieces that approximates f on the entire interval [1, r] to within a factor (1+ε). Our argument follows similar previous results for approximating a concave function with a logarithmic number of linear pieces [26, 50] .
For any value y ∈ [1, r], not necessarily an integer, f (y) lies on a linear piece of f which we will denote by g (y) (x) = M y · x + B y , where M y ≥ 0 is the slope and B y ≥ 0 is the intercept. When y = i is an integer, it may be the breakpoint between two distinct linear pieces, in which case we use the rightmost line so that g (y) = g (i) as in (23)
For any z ∈ (y, r), the line g (y) provides a z/y approximation to f (z) = g (z) (z),
Equivalently, the line g (y) provides a (1 + ε)-approximation for every z ∈ [y, (1 + ε)y]. Thus, it takes J linear pieces to cover the set of intervals [ 
for a positive integer J, and overall at most 1 + log 1+ε r linear pieces to cover all of [0, r].
Since Algorithm 1 finds the smallest set of linear pieces to (1 + ε)-cover the splitting penalties, this smallest set must also have at most O(log 1+ε r) linear pieces. Given this piecewise linear approximation, we can use Lemma 3.2 to extract a CCB functionŵ of order J = O(log 1+ε r)
. Thisŵ in turn corresponds to a set of J CB-gadgets that (1 + ε)-approximates the splitting function w e . Computing edge weights for the CB-gadgets using Algorithm 1 and Lemma 3.2 takes only O(r) time, so the total runtime for constructing the combined gadgets is equal to the number of individual edges that must be placed, which is O(k log 1+ε k).
Theorem 1.1 on augmented sparsifiers follows as a corollary of Theorem 4.1. Given a hypergraph H = (V, E) where each hyperedge has an SCB splitting function, we can use Theorem 4.1 to expand each e ∈ E into a gadget that has O(log 1+ε |e|) auxiliary nodes and O(|e| log 1+ε |e|) edges. Since log 1+ε n behaves as 1 ε log n as ε → 0, Theorem 1.1 follows. In Appendix B, we show that using a slightly different reduction, we can prove that Theorem 4.1 holds even when we do not require splitting functions to be symmetric or satisfy w e (∅) = w e (e) = 0. In Section 6 we use this fact to develop approximation algorithms for cardinality-based decomposable submodular function minimization.
Next we show that our upper bound is nearly tight for the square root r-SCB integer function,
For this result, we rely on a result previously shown by Magnanti and Stratila [50] on the number of linear pieces needed to approximate the square root function over a continuous interval. Lemma 4.2 is concerned with approximating the square root function for all values on a continuous interval. Therefore, it does not immediately imply any bounds on approximating a discrete set of splitting penalties. In fact, we know that when lower bounding the number of linear pieces needed to approximate any w ∈ S r , there is no lower bound of the form q(ε)f (r) that holds for all ε > 0, if q is a function such that q(ε) → ∞ as ε → 0. This is simply because we can approximate w by piecewise linear interpolation, leading to an upper bound of O(r) linear pieces even when ε = 0. Therefore, the best we can expect is a lower bound that holds for ε values that may still go to zero as r → ∞, but are bounded in such a way that we do not contradict the O(r) upper bound that holds for all SCB integer functions. We prove such a result for the square root splitting function, using Lemma 4.2 as a black box. When ε falls below the bound we assume in the following theorem statement, forming O(r) linear pieces will be nearly optimal. Theorem 4.3. Let ε > 0 and w(i) = √ i be the square root r-SCB integer function. If ε ≥ r −δ for some constant δ ∈ (0, 2), then any piecewise linear function providing a (1 + ε)-approximation for w contains Ω(log γ(ε) r) linear pieces, which behaves as Ω(ε −1/2 log r) as ε → 0.
Proof. Let L * be the optimal set of linear pieces returned by running Algorithm 1. In order to show |L * | = Ω(log γ(ε) r), we will construct a new set of linear pieces L that has asymptotically the same number of linear pieces as L * , but also provides a (1 + ε)-approximation for all x in an interval [r β , r] for some constant β < 1. Invoking Lemma 4.2 will then guarantee the final result.
Recall that L * includes only two types of linear pieces: either linear pieces g satisfying g(j) = √ j for exactly one integer j (see (24) ), or linear pieces formed by joining two points of w (see (23)). For the square root splitting function, the latter type of linear piece is of the form
for some positive integer t less than r. This is the linear interpolation of the points (t, √ t) and (t + 1, √ t + 1). Both types of linear pieces bound φ(x) = √ x above at integer points, but they may cross below φ at non-integer values of x. To apply Lemma 4.2, we would like to obtain a set of linear pieces that are all tangent lines to φ. We accomplish this by replacing each linear piece in L * with two or three linear pieces that are tangent to φ at some point. For a positive integer j, let g j denote the line tangent to φ(x) = √ x at x = j, which is given by
We form a new set of linear pieces L made up of lines tangent to φ using the following replacements:
• If L * contains a linear piece g that satisfies g(j) = √ j for exactly one integer j, add lines g j−1 , g j , and g j+1 to L.
• If for an integer t, L * contains the line g (t) as given by Eq. (29), add lines g t and g t+1 to L.
By Observation 3.1, this replacement can only improve the approximation guarantee at integer points. Therefore, L provides a (1 + ε)-approximation at integer values, is made up strictly of lines that are tangent to φ, and contains at most three times the number of lines in L * . Due to the concavity of φ, if a single line g ∈ L provides a (1 + ε)-approximation at consecutive integers i and i+1, then g provides the same approximation guarantee for all x ∈ [i, i+1]. However, if two integers i and i + 1 are not both covered by the same line in L, then L does not necessarily provide a (1 + ε)-approximation for every x ∈ [i, i + 1]. There can be at most |L| intervals of this form, since each interval defines an "intersection" at which one line g ∈ L ceases to be a (1 + ε)approximation, and another line g ∈ L "takes over" as the line providing the approximation.
By Lemma 4.2, we can cover an entire interval [i, i+1] for any integer i using a set of log γ(ε) 1+ 
interval [i, i + 1] can be covered by a single linear piece if i ≥ r δ/2 . Therefore, for each interval [i, i + 1], with i ≥ r δ/2 , that is not already covered by a single linear piece in L, we add one more linear piece to L to cover this interval. This at most doubles the size of L.
The resulting set L will have at most 6 times as many linear pieces as L * , and is guaranteed to provide a (1 + ε)-approximation for all integers, as well as the entire continuous interval [r δ/2 , r]. Since δ is a fixed constant strictly less than 2, applying Lemma 4.2 shows that L has at least log γ(ε) r r δ/2 = Ω(log γ(ε) r 1−δ/2 ) = Ω(log γ(ε) r) linear pieces. Therefore, |L * | = Ω(log γ(ε) r) as well.
When approximating the clique expansion splitting function, Algorithm 1 will in fact find a piecewise linear curve with at most O(ε −1/2 log log 1 ε ) linear pieces. We prove this by highlighting a different approach for constructing a piecewise linear curve with this many linear pieces, which upper bounds the number of linear pieces in the optimal curve found by Algorithm 1.
Clique splitting penalties for a k-node hyperedge correspond to nonnegative integer values of the continuous function ζ(x) = x · (k − x). As we did in Section 3.3, we want to build a set of linear pieces L that provides and upper bounding (1 + ε)-cover of ζ at integer values in [0, r], where r = k/2 . We start by adding the line g (0) (x) = (w(1) − w(0))x + w(0) = (k − 1) · x to L, which perfectly covers the first two splitting penalties w(0) = 0 and w(1) = k − 1. In the remainder of our new procedure we will find a set of linear pieces to (1 + ε)-cover ζ at every value of x ∈ [1, k/2], even non-integer x.
We apply a greedy procedure similar to Algorithm 1. At each iteration we consider a leftmost endpoint z i which is the largest value in [1, k/2] for which we already have a (1 + ε)-approximation. In the first iteration, we have z 1 = 1. We then would like to find a new linear piece that provides a (1 + ε)-approximation for all values from z i to some z i+1 , where the value of z i+1 is maximized. We restrict to linear pieces that are tangent to ζ. The line tangent to ζ at t ∈ [1, k/2] is given by
We find z i+1 in two steps:
1.
Step 1: Find the maximum value t such that g t (z i ) = (1 + ε)ζ(z i ).
Step 2: Given t, find the maximum z i+1 such that g t (z i+1 ) = (1 + ε)ζ(z i+1 ).
After completing these two steps, we add the linear piece g t to L, knowing that it covers all values in [z i , z i+1 ] with a (1 + ε)-approximation. At this point, we will have a cover for all values in [0, z i+1 ], and we begin a new iteration with z i+1 being the largest value covered. We continue until we have covered all values up until z i+1 ≥ k/2. If t > k/2 in Step 1 of the last iteration, we adjust the last linear piece to instead be the line tangent to ζ at x = k/2, so that we only include lines that have a nonnegative slope. 
Proof. The proof simply requires solving two different quadratic equations. For Step 1:
Algorithm 3 Find a (1 + ε)-cover L for the clique splitting function.
Input: Hyperedge size k, ε ≥ 0 Output: (1 + ε) cover for clique splitting function.
Taking the larger solution to maximize t:
For
Step 2:
We again take the larger solution to this quadratic equation since we want to maximize z i+1 :
Algorithm 3 summarizes the new procedure for covering the clique splitting function. Since
so after one step we have covered the entire interval [1, k/2]. We can therefore focus on ε < 1.
Theorem 4.5. For ε < 1, if L is the output from Algorithm 3, then |L| = O(ε −1/2 log log 1 ε ). Proof. We get a loose bound for the value of t in Lemma 4.4 by noting that (k − z i ) ≥ k/2 ≥ z i :
Since we assumed ε < 1, we know that
Therefore, from (33) we see that
From this we see that at each iteration, we cover an additional interval of length z i+1 − z i > kε 1+ε , and therefore we know it will take at most O(1/ε) iterations to cover all of [1, k/2]. This upper bound is loose, however. The value of z i+1 − z i in fact increases significantly with each iteration, allowing the algorithm to cover larger and larger intervals as it progresses.
Since z 1 = 1 and z i+1 − z i ≥ kε 1+ε , we see that z j ≥ kε for all j ≥ 3. For the remainder of the proof, we focus on bounding the number of iterations it takes to cover the interval [kε, k/2]. We separate the progress made by Algorithm 3 into different rounds. Round j refers to the set of iterations that the algorithm spends to cover the interval
For example, Round 1 starts with the iteration i such that z i ≥ kε, and terminates when the algorithm reaches an iteration i where z i ≥ kε 1/2 . A key observation is that it takes less than 4/ √ ε iterations for the algorithm to finish Round j for any value of j. To see why, observe that from the bound in (36) we have
For each iteration i in Round j, we know that
where C = √ 2/(2(1 + ε)) is a constant larger than 1/4. Since each iteration of Round j covers an interval of length at least C ·k ·ε
, and the right endpoint for Round j is kε ( 1 2 ) j , the maximum number of iterations needed to complete Round j is
Therefore, after p rounds, the algorithm will have performed O(p · ε −1/2 ) iterations, to cover the interval [1, kε ( 1 2 ) p ]. Since we set out to cover the interval [1, k/2], this will be accomplished as soon as p satisfies ε ( 1 2 ) p ≥ 1/2, which holds as long as p ≥ log 2 log 2 1 ε :
This means that the number of iteration of Algorithm 3, and therefore the number of linear pieces in L, is bounded above by O(ε −1/2 log log 1 ε ). We obtain a proof of Theorem 1.3 on sparsifying the complete graph as a corollary.
Proof of Theorem 1.3. A complete graph on n nodes can be viewed as a hypergraph with a single n-node hyperedge with a clique expansion splitting function. Theorem 1.3 says that the clique expansion integer function w(i) = i · (n − i) can be covered with O(ε −1/2 log log ε −1 ) linear pieces, which is equivalent to saying the clique expansion splitting function can be modeled using this many CB-gadgets. Each CB-gadget has two auxiliary nodes and (2n + 1) directed edges. This results in an augmented sparsifier for the complete graph with O(nε −1/2 log log ε −1 ) edges. This is only meaningful if ε is small enough so that O(ε −1/2 log log ε −1 ) is asymptotically less than n, so our sparsifier has O(n + ε −1/2 log log ε −1 ) = O(n) nodes.
Recall from the introduction that a co-occurrence graph is formally defined by a set of nodes V and a set of subsets C ⊆ 2 V . In practice, each c ∈ C could represent some type of group interaction involving nodes in c or a set of nodes sharing the same attribute. We define the co-occurrence graph G = (V, E) on C to be the graph where nodes i and j share an edge with weight w ij = c∈C w c , where w c ≥ 0 is a weight associated with co-occurrence set c ∈ C. The case when w c = 1 is standard and is an example of a common practice of "one-mode projections" of bipartite graphs or affiliation networks [11, 40, 42, 52, 53, 57, 72 ] -a graph is formed on the nodes from one side of a bipartite graph by connecting two nodes whenever they share a common neighbor on the other side, where edges are weighted based on the number of shared neighbors.
A co-occurrence graph G has the following co-occurrence cut function:
In this sense, the co-occurrence graph is naturally interpreted as a weighted clique expansion of a hypergraph H = (V, C), which itself is a special case of reducing a submodular, cardinality-based hypergraph to a graph. However, this type of graph construction is by no means restricted to literature on hypergraph clustering. In many applications, the first step in a larger experimental pipeline is to construct a graph of this type from a large dataset. The resulting graph is often quite dense, as numerous domains involve large hyperedges [56, 67] . This makes it expensive to form, store, and compute over co-occurrence graphs in practice.
Solving cut problems on these dense co-occurrence graphs arises naturally in many settings. For example, any hypergraph clustering application that relies on a clique expansion involves a graph with a co-occurrence cut function [1, 28-30, 44, 58, 65, 67, 68, 71, 73] . Clustering social networks is another use case, as online platforms have many ways to create groups of users (e.g., events, special interest groups, businesses, organizations, etc.), that can be large in practice. Furthermore, cuts in co-occurrence graphs of students on a university campus (based on, e.g., common classes, living arrangements, or physical proximity) are relevant to preventing the spread of infectious diseases such as COVID-19.
In these cases, it would be more efficient to sparsify the graph without ever forming it explicitly, by sparsifying large cliques induced by co-occurrence relationships. Although this strategy seems intuitive, it is often ignored in practice. We therefore present several theoretical results that highlight the benefits of this implicit approach to sparsification. Our focus is on results that can be achieved using augmented sparsifiers for cliques, though many of the same benefits could also be achieved with standard sparsification techniques.
Let C be a set of nonempty co-occurrence groups on a set of n nodes, V , and let G = (V, E) be the corresponding co-occurrence graph on C. For c ∈ C, let k c = |c| be the number of nodes in c. For v ∈ V , let d v be the co-occurrence degree of v: the number of sets c containing v. Let d avg = 1 n v∈V d v be the average co-occurrence degree. We re-state and prove Theorem 1.4, first presented in the introduction. The proof holds independent of the weight w c we associate with each c ∈ C, since we can always scale our graph reduction techniques by an arbitrary positive weight.
Theorem. Let ε > 0 and f (ε) = ε −1/2 log log 1 ε . There exists an augmented sparsifier for G with O(n + |C| · f (ε)) nodes and O(n · d avg · f (ε)) edges. In particular, if d avg is constant and for some δ > 0 we have c∈C |c| 2 = Ω(n 1+δ ), then forming G explicitly takes Ω(n 1+δ ) time, but an augmented sparsifier for G with O(nf (ε)) nodes and O(nf (ε)) edges can be constructed in O(nf (ε)) time.
Proof. The set c induces a clique in the co-occurrence graph with O(k 2 c ) edges. Therefore, the runtime for explicitly forming G = (V, E) by expanding cliques and placing all edges equals O( c∈C k 2 c ) = Ω(n 1+δ ). By Theorem 1.3, for each c ∈ C we can produce an augmented sparsifier with O(k c f (ε)) directed edges and O(f (ε)) new auxiliary nodes. Sparsifying each clique in this way will produce an augmented sparsifierĜ = (V ,Ê) where
Observe that n · d avg = v∈V d v = c∈C k c . If d avg is a constant, this implies that c∈C k c = O(n), and furthermore that |C| = O(n), since each k c ≥ 1. Therefore |Ê| and |V | are both O(nf (ε)).
Only O(f (ε)) edge weights need to be computed for the clique, so the overall runtime is just the time it takes to explicitly place the O(nf (ε)) edges.
The above theorem and its proof includes the case where |C| = o(n), meaning that C is made up of a sublinear number of large co-occurrence interactions. In this case, our augmented sparsifier will have fewer than O(nf (ε)) nodes. When |C| = ω(n), the average degree will no longer be a constant and therefore it becomes theoretically beneficial to sparsify each clique in C using standard undirected sparsifiers. For each c ∈ C, standard cut sparsification techniques will produce an εcut sparsifier of c with O(k c ε −2 ) undirected edges and exactly k c nodes. If two nodes appear in multiple co-occurrence relationships, the resulting edges can be collapsed into a weighted edge between the nodes, meaning that the number of edges in the resulting sparsifier does not depend on d avg . We discuss tradeoffs between different sparsification techniques in depth in a later subsection. Regardless of the sparsification technique we apply in practice, implicitly sparsifying a co-occurrence graph will often lead to a significant decrease in runtime compared to forming the entire graph prior to sparsifying it.
We now consider a simple model for co-occurrence graphs with a power-law group size distribution, that produces graphs satisfying the conditions of Theorem 1.4 in a range of different parameter settings. Such distributions have been observed for many types of co-occurrence graphs constructed from real-world data [11, 19] . More formally, let V be a set of n nodes, and assume a co-occurrence set c is randomly generated by sampling a set of size K from a discrete power-law distribution where for k ∈ [1, n]:
Here, C is a normalizing constant for the distribution, and γ and is a parameter of the model. Once K is drawn from this model, a co-occurrence set c is generated with a set of K nodes from V chosen uniformly at random. This procedure can be repeated an arbitrary number of times (drawing all sizes K independently) to produce a set of co-occurrence sets C. This C can then be used to generate a co-occurrence graph G = (V, E). (The end result of this procedure is a type of random intersection graph [12] .) We first consider a parameter regime where set sizes are constant on average but large enough to produce a dense co-occurrence graph that is inefficient to explicitly form in practice. The regime has an exponent γ ∈ (2, 3), which is common in real-world data [19] .
Theorem 5.1. Let C be a set of O(n) co-occurrence sets obtained from the power-law model with γ ∈ (2, 3) . The expected degree of each node will be constant and E c∈C |c| 2 = O(n 4−γ ).
Proof. Let K be the size of a randomly generated co-occurrence set. We compute:
Therefore,
For a node v ∈ V and a randomly generated set c, the probability that v will be selected to be in c is
Since there are O(n) co-occurrence sets in C and they each are generated independently, in expectation, v will have a constant degree.
We similarly consider another regime of co-occurrence graphs where the number of co-occurrence sets is asymptotically smaller than n, but the co-occurrence sets are larger on average. Theorem 5.2. Let C be a set of O(n β ) co-occurrence sets, where β ∈ (0, 1), obtained from the power-law co-occurrence model with γ = 1 + β. Then the expected degree of each node will be a constant and E c∈C |c| 2 = O(n 3 ).
Proof. Again let K be a random variable representing the co-occurrence set size. We have
For a node v ∈ V and a randomly generated set c, the probability that v will be in c is
Since there are O(n β ) co-occurrence sets in C, the expected degree of v is a constant.
In Theorem 5.2, the exponent of the power-law distribution is assumed to be directly related to the number of co-occurrence sets in C. This assumption is included simply to ensure that we are in fact considering co-occurrence graphs with O(n) nodes. We could alternatively consider a power-law distribution with exponent γ ∈ (1, 2) and generate O(n β ) co-occurrence sets for any β < 1 − γ. We simply note that in this regime, the expected average degree will be o(1). Assuming we exclude isolated nodes, this will produce a co-occurrence graph with o(n) nodes in expectation. Our techniques still apply in this setting, and we can produce augmented sparsifiers with O(|C|·f (ε)) nodes and O(n · d avg · f (ε)) = o(n · f (ε)) edges. When |C| = Ω(n), then d avg = Ω(1) and the number of edges in our augmented sparsifiers will have worse than linear dependence on n. However, in this regime we can still quickly obtain sparsifiers with O(nε −2 ) edges via implicit sparsification by using standard undirected sparsifiers.
More sophisticated models for generating co-occurrence graphs can also be derived from existing models for projections of bipartite graphs [11] [12] [13] . These make it possible to set different distributions for node degrees in V and highlight other classes of co-occurrence graphs satisfying the assumptions of Theorem 1.4. Here we have chosen to focus on the simplest model for illustrating classes of power-law co-occurrence graphs that satisfy the assumptions of the theorem.
There are several tradeoffs to consider when using different black-box sparsifiers for implicit cooccurrence sparsification. Standard sparsification techniques involve no auxiliary nodes, and have undirected edges, which is beneficial in numerous applications. Also, the number of edges they require is independent of d avg . Therefore, in cases where the average co-occurrence degree is larger than a constant, we obtain better theoretical improvements using standard sparsifiers.
On the other hand, in many settings, it is natural to assume the number of co-occurrences each node belongs to is a constant, even if some co-occurrences are very large. In these regimes, our augmented sparsifiers will have fewer edges that traditional sparsifiers due to a better dependence on ε. Our techniques are also deterministic and our sparsifiers are very easy to construct in practice. Edge weights for our sparsifiers are easy to determine in O(f (ε)) time for each co-occurrence group using Algorithm 1 (or Algorithm 3) coupled with Lemma 3.2. The bottleneck in our construction is simply visiting each node in a set c to place edges between it and the auxiliary nodes. Even in cases where there are no asymptotic reductions in theoretical runtime, our techniques provide a simple and highly practical tool for solving cut problems on co-occurrence data.
6 Approximate Cardinality-based DSFM Appendix B shows how our sparse reduction techniques can be adjusted to apply even when splitting functions are asymmetric and are not required to satisfy w e (∅) = w e (e) = 0 (the non-cut ignoring property). Section 3 addresses the special case of symmetric and non-cut ignoring functions, as these assumptions are more natural for hypergraph cut problems [44, 46, 66] , and provide the clearest exposition of our main techniques and results. Furthermore, applying the generalized asymmetric reduction strategy in Appendix B to a symmetric splitting function would introduce twice as many edges as applying the reduction from Section 3 designed explicitly for the symmetric case. Nevertheless, the same asymptotic upper bound of O( 1 ε log k) edges holds for approximately modeling the more general splitting function on a k-node hyperedge. By dropping the symmetry and non-cut ignoring assumptions, our techniques lead to the first approximation algorithms for the more general problem of minimizing cardinality-based decomposable submodular functions.
Any submodular function can be minimized in polynomial time [31, 32, 55] , but the runtimes for general submodular functions are impractical in most cases. A number of recent papers have developed faster algorithms for minimizing submodular functions that are sums of simpler submodular functions [20, 21, 33, 34, 39, 45, 54, 64] . This is also know as decomposable submodular function minimization (DSFM). Many energy minimization problems from computer vision correspond to DSFM problems [24, 37, 38] .
Let f : 2 V → R + be a submodular function, such that for S ⊆ V ,
where for each e ∈ E, f e is a simpler submodular function with support only on a subset e ⊆ V . We can assume without loss of generality that every f e is a non-negative function. The goal of DFSM is to find arg min S f (S). The terminology used for problems of this form differs depending on the context. We will continue to refer to E as a hyperedge set, V as a node set, f e as generalized splitting functions, and f as some type of generalized hypergraph cut function. Much previous research explicitly considers the case where each function f e is given by f e (S) = g e (|S|) for some concave function g e [33, 34, 37, 39, 64] . Unlike existing work on generalized hypergraph cut functions [44, 46, 66] , research on DFSM does not typically assume that the functions f e are symmetric, and also do not assume that f e (∅) = f e (e) = 0.
Let n = |V |, R = |E|, µ = e∈E |e|, and let k avg = µ R denote the average hyperedge size. Note that e∈E log |e| ≤ R log n e∈E |e| log |e| ≤ µ log n max{n, R} ≤ µ ≤ n · R.
We primarily focus on how our techniques enable us to obtain runtimes that are strictly better in terms of number of nodes, number of edges, and average hyperedge size, by producing an approximate solution. We useÕ notation to hide logarithmic factors of n and R. In order to compare weakly polynomial runtimes, in some cases we restrict to the case where f e has integer outputs. For this case, we let F max = max S⊆V f (S), and assume log F max is small enough that it can also be absorbed byÕ notation. We also consider strongly polynomial runtimes that can be obtained for arbitrary edge weights. Previous research on DFSM has focused largely on runtimes for finding exact solutions. 2 Our goal is to highlight improved runtimes that can be obtained if we are content with solutions that are within a factor (1 + ε) of optimality.
Appendix B shows how our reduction techniques enable us to approximately minimize a cardinalitybased DFSM problem. This can be accomplished by solving a directed minimum s-t cut problem on a reduced graph with N = O(n + ε −1 R log n) nodes and M = O(ε −1 µ log n) edges. We use this to obtain the strongly polynomial runtime guarantee ofÕ(min{ε −3/2 µ 3/2 , ε −1 µ(n + ε −1 R) 2/3 }) given in Theorem 1.5, which we now prove.
Proof of Theorem 1.5
Proof. The runtime comes from applying the directed s-t cut solvers of of Goldberg and Rao [27] . Although Goldberg and Rao assume integer edge weights and report weakly polynomial runtimes for exact s-t cut solution, as long as we are content with approximate solutions, slight adjustments allow us to obtain a strongly polynomial runtime for arbitrary weights. If ε is a constant greater than one, we can decrease it to equal 1 and get a better approximation with the same asymptotic runtime. In the remainder of the proof, we therefore assume ε ≤ 1. Define ε 0 = ε/7 and letĜ = (V ,Ê) be the directed graph resulting from our approximate reduction techniques with parameter ε 0 . This graph has N = O(n+ε −1 R log n) nodes and M = O(ε −1 µ log n) edges, and distinguished source and sink nodes s and t so that the minimum s-t cut corresponds to a (1 + ε)-approximation for DFSM. Begin by scaling the edge weights so that the minimum s-t cut inĜ is at least one. This can be done by finding an augmenting flow path from s to t and scaling edge weights so that the path has a capacity of at least 1 on all edges.
If the graph has irrational edge weights, we can perform a standard scaling procedure to turn it into a directed graph with integer edge weights, in a way that guarantees we do not lose much in the approximation factor. This is done by adjusting all edge weights by up to an additive term ε 0 /M to reach a nearby rational number, producing a graphG = (V ,Ẽ). Let cutĜ and cutG be cut functions ofĜ andG respectively. The graphs have the same set of nodes and edges, but may have different edge weights. Let w ij > 0 be the weight of an edge (i, j) inĜ. For any S ⊆V , let ∂S be the set of edges cut by S. We have
Finally, since all edge weights inG are rational, we can scale them up to be integers. Goldberg and Rao [27] provide a method for finding a (1 + ε 0 )-approximate minimum s-t cut in a directed graph with N nodes and M edges in time O(M · min{M 1/2 , N 2/3 } log(M 2 /N ) log M/ε 0 ), which does not depend on the largest edge weight. Overall we performed three levels of approximation: approximately reducing the hypergraph, approximating the cut properties ofĜ withG, and approximating the s-t cut solution inG. Since ε 0 = ε/7, the overall approximation factor is (1 + ε 0 ) 3 ≤ (1 + ε). Plugging in the appropriate values for M and N yields the runtime guarantee.
Our approximate solution techniques will always be faster than runtimes obtained by methods that perform an exact reduction to a graph s-t cut problem [37, 66] , since these introduce O(|e| 2 ) edges for each hyperedge e. Kolmogorov [39] presented an algorithm for minimizing sums of submodular functions based on submodular flows. Although the approach provides a way to also solve more general variants of the problem, the algorithm has a runtime of O((n + µ) 2 log F max ) =Õ(µ 2 ) specifically in the case of cardinality-based functions with integer-valued weights, which is slower than our approximate techniques by at least a factor of µ 1/2 .
Recently, Ene et al. [20] presented improved runtime analyses for optimization techniques for solving DFSM. The runtimes depend on the time it takes to evaluate oracle functions that correspond to solving a submodular minimization problem at a single splitting function. Let θ e be the time it take to evaluate the oracle at e ∈ E, and define θ max = max e∈E θ e and θ avg = 1 R e∈E θ e . For a cardinality-based function f e , such an oracle can be queried in O(|e| log |e|) time [33] , and so θ avg = O( 1 R e∈E |e| log |e|). Combing this oracle with the runtimes presented by Ene at al. [20] produces the fastest known runtimes for cardinality-based DFSM. For methods based on discrete optimization, Ene et al. [20] note that the incremental breadth first search (IBFS) algorithm of Fix et al. [22] can be implemented with a strongly polynomial runtime of O(n 2 θ max e∈E |e| 2 ), or a weakly polynomial runtime of O(n 2 θ max log F max + n e∈E |e| 3 θ i ) =Õ(n 2 θ max + n e∈E |e| 4 ). Among continuous optimization approaches, the best runtime presented by Ene et al. [20] is achieved by the accelerated random coordinate descent method (ACDM) [21] . The method has a weakly polynomial runtime of O(nRθ avg log(nF max )) =Õ(nµ).
The hyperedge e defines the support of the function f e . Previous research has addressed both the case of functions f e of large support and the case of small support (see discussion and experiments in [20, 39, 45, 59] ). Functions of small support are common in computer vision applications, though the case of large support has also been studied [59] . In hypergraph cut problems, large hyperedges are natural for modeling large-scale multiway interactions (as discussed in Section 5 with respect to co-occurrence data). Table 1 summarizes runtimes for the methods we have considered here, with specialized runtimes highlighted for different regimes. The table shows runtimes for small support, k avg = O(1), in which case R = Ω(n) and also runtimes for k avg = Θ(n), which highlights the slowest possible runtime for each method in terms of nodes and hyperedges. For the latter case, Table 1 additionally distinguishes between subcases where R = Ω(n) and n = Ω(R).
For subcases of each of these regimes, our sparsification techniques lead to improved runtimes when searching for approximately optimal solutions. When k avg = O(1), our runtime is the fastest as long as R = o(n 2 ). When k avg = Θ(n) and R = Ω(n), the ACDM algorithm has the best performance whenever R = Ω(n 3/2 ), though we provide a faster approximate alternative below this threshold. Most importantly, our method provides a significantly faster runtime for the case where n = Ω(R), independent of k avg . Thus, in hypergraphs with a sublinear (in n) number of large hyperedges (equivalently, a sum of sublinearly many functions of large support), obtaining an approximately optimal solution is much faster than solving the problem exactly with existing techniques.
We have introduced the notion of an augmented cut sparsifier, which approximates a generalized hypergraph cut function with a sparse directed graph on an augmented node set. Our approach relies on a connection we highlight between graph reduction strategies and piecewise linear approximations to concave functions. Our framework leads to more efficient techniques for approximating hypergraph s-t cut problems via graph reduction, improved sparsifiers for co-occurrence graphs, and fast algorithms for approximately minimizing cardinality-based decomposable submodular functions.
As noted in Section 1.2, an interesting open question is to establish and study analogous notions of augmented spectral sparsification, given that spectral sparsifiers provide a useful generalization of cut sparsifiers in graphs [61] . One way to define such a notion is to apply existing definitions of submodular hypergraph Laplacians [46, 70] to both the original hypergraph and its sparsifier. This requires viewing our augmented sparsifier as a hypergraph with splitting functions of the form w e (A) = a · min{|A|, |e\A|, b}, corresponding to hyperedges with cut properties that can be modeled by a cardinality-based gadget. From this perspective, augmented spectral sparsification means approximating a generalized hypergraph cut function with another hypergraph cut function involving simplified splitting functions. While this provides one possible definition for augmented spectral sparsification, it is not clear whether the techniques we have developed can be used to satisfy this definition. Furthermore, it is not clear whether obtaining such a sparsifier would imply any immediate runtime benefits for approximating the spectra of generalized hypergraph Laplacians, or for solving generalized Laplacian systems [25, 43] . We leave these as questions for future work.
While our work provides the optimal reduction strategy in terms of cardinality-based gadgets, this is more restrictive than optimizing over all possible gadgets for approximately modeling hyperedge cut penalties. Optimizing over a broader space of gadgets poses another interesting direction for future work, but is more challenging in several ways. First of all, it is unclear how to even define an optimal reduction when optimizing over arbitrary gadgets, since it is preferable to avoid both adding new nodes and adding new edges, but the tradeoff between these two goals is not clear. Another challenge is that the best reduction may depend heavily on the splitting function we wish to reduce, which makes developing a general approach difficult. A natural next step would be to at least better understand lower bounds on the number of edges and auxiliary nodes needed to model different cardinality-based splitting functions. While we do not have any concrete results, there are several indications that cardinality-based gadgets may be nearly optimal in many settings. For example, star expansions and clique expansions provide a more efficient way to model linear and quadratic splitting functions respectively, but modeling these functions with cardinality-based gadgets only increases the number of edges by roughly a factor two.
Finally, we find it interesting that using auxiliary nodes and directed edges makes it possible to sparsify the complete graph using only O(nε −1/2 log log 1 ε ) edges, whereas standard sparsifiers require O(nε −2 ). We would like to better understand whether both directed edges and auxiliary nodes are necessary for making this possible, or whether improved approximations are possible using only one or the other.
Proof of Lemma 3.1
Lemma. Letf be the continuous extension for a function w ∈ S r , shown in (21) . This function is in the class F r , and has exactly J positive-sloped linear pieces, and one linear piece of slope zero.
Proof. Define b 0 = 0 for notational convenience. The first three conditions in Definition 3.1 can be seen by inspection, recalling that 0 < a j and 0 < b j ≤ r for all j ∈ [J]. Observe thatf is linear
In other words, the ith linear piece off , defined over
where the intercept and slope terms are given by Proof. Since f is in F r , it has J positive-sloped linear pieces and one flat linear piece, and therefore it has exactly J breakpoints: 0 < b 1 < b 2 < . . . < b J . Let b = (b j ) be the vector storing these breakpoints. For convenience we define b 0 = 0, though b 0 is not stored in b. By definition, f is constant for all x ≥ r, which implies that b J ≤ r.
Let
, the positive slope of the ith linear piece of f , which occurs in the range [b i−1 , b i ], is given by
The ith linear piece of f is given by
The last linear piece of f is a flat line over the interval x ∈ [b J , ∞), i.e., m J+1 = 0. Since f has positive and strictly decreasing slopes, we can see that a i = m i − m i+1 > 0 for all i ∈ [J].
Let w be the order-J CCB function constructed from vectors (a, b), and letf be its resulting continuous extension:f
We must check thatf = f . By Lemma 3.1, we know thatf is in F r and has exactly J + 1 linear pieces. The functions will be the same, therefore, if they share the same values at breakpoints. Evaluatingf at an arbitrary breakpoint b i gives:
We first confirm that the functions coincide at the first breakpoint:
For any fixed i ∈ {2, 3, . . . , J},
. Therefore, f andf are the same piecewise linear function.
In Sections 2 and 3 we focused on sparsification techniques for representing splitting functions that are symmetric and penalize only cut hyperedges:
w e (S) = w(e\S) for all S ⊆ e w e (e) = w e (∅) = 0.
These assumptions are standard for generalized hypergraph cut problems [44, 46, 66] , and lead to the clearest exposition of our main results. In this appendix, we extend our sparse approximation techniques so that they apply even if we remove these restrictions. This will allow us to obtain improved techniques for approximately solving a certain class of decomposable submodular functions (see Section 6). Formally, our goal is to minimize
where each w e is a submodular cardinality-based function, that is not necessarily symmetric and does not need to equal zero when the hyperedge e is uncut. Our proof strategy for reducing this more general problem to a graph s-t cut problem closely follows the same basic set of steps used in Section 3 for the special case.
We first provide a convenient characterization of general cardinality-based submodular functions. By general we mean the splitting function does not need to be symmetric nor does it need to have a zero penalty when the hyperedge is uncut.
Lemma B.1. Let w e be a general submodular cardinality-based splitting function on a k-node hyperedge e, and let w i denote the penalty for any A ⊆ e with |A| = i. Then for i ∈ {1, 2, . . . , k − 1} To simplify our analysis, as we did for the symmetric case, we will define a set of functions that is virtually identical to these splitting functions on k-node hyperedges, but are defined over integers from 0 to k rather than on subsets of a hyperedge.
Our goal is to show how to approximate k-GSCB integer functions using piecewise linear functions with few linear pieces. This in turn corresponds to approximating a hyperedge splitting function with a sparse gadget. In order for this to work for our more general class of splitting functions, we use a slight generalization of an asymmetric gadget we introduced in previous work [66] .
Definition B.2. The asymmetric cardinality-based gadget (ACB-gadget) for a k-node hyperedge e is parameterized by scalars a and b and constructed as follows:
• Introduce an auxiliary vertex v e .
• For each v ∈ e, introduce a directed edge from v to v e with weight a · (k − b), and a directed edge from v e to v with weight a · b.
The ACB-gadget models the following k-GSCB integer function:
To see why, consider where we must place the auxiliary node v e when solving a minimum s-t cut problem involving the ACB-gadget. If we place i nodes on the s-side, then placing v e on the s-side has a cut penalty of ab(k − i), whereas placing v e on the t-side gives a penalty of ai(k − b). To minimize the cut, we choose the smaller of the two options. Previously we showed that asymmetric splitting functions can be modeled exactly by a combination of k − 1 ACB-gadgets [66] . As we did in Section 3 for symmetric splitting functions, we will show here that a much smaller number of gadgets suffices if we are content to approximate the cut penalties of an asymmetric splitting function. In our previous work we enforced the constraint w e (∅) = w e (0) = 0 even for asymmetric splitting functions, but we remove this constraint here. In order to model the cut properties of an arbitrary GSCB splitting function, we define a combined gadget involving multiple ACB-gadgets, as well as edges from each node v ∈ e to the source and sink nodes of the graph. The augmented cut function for the resulting directed grapĥ G = (V ∪ A ∪ {s, t},Ê) will then be given by cutĜ(S) = min T ⊆A dircutĜ({s} ∪ S ∪ T ) for a set S ⊆ V , where dircut is the directed cut function onĜ. Finding a minimum s-t cut inĜ will solve objective (49) , or equivalently, the cardinality-based decomposable submodular function minimization problem. Definition B.3. A k-CG function (k-node, combined gadget function)ŵ of order J is a k-GSCB integer function that is parameterized by scalars z 0 , z k , and (a j , b j ) for j ∈ [J]. The function has the form:ŵ
The scalars parameterizingŵ satisfy
Conceptually, the function shown in (52) represents a combination of J ACB-gadgets for a hyperedge e, where additionally for each node v ∈ e we have place a directed edge from a source node s to v of weight z 0 , and an edge from v to a sink node t with weight z k .
The continuous extension of the k-CG function (52) is defined to be:
Lemma B.2. The continuous extensionf ofŵ is nonnegative over the interval [0, k], piecewise linear, concave, and has exactly J + 1 linear pieces.
Proof. Nonnegativity follows quickly from the positivity of z 0 , z k , and (a i , b i ) for i ∈ [J], and b J < k. For other properties, we begin by re-writing the function aŝ
= kz 0 + x(z k − z 0 ) + kx · j:x<b j a j + k · j:x≥b j
Define β = J j=1 a j b j , β t = t j=1 a j b j , α t = J j=t+1 a j , and observe that β t is strictly increasing with t, and α t is strictly decreasing with t. Define b 0 = 0 and b J+1 = k for notational convenience. For any t ∈ {0} ∪ [J], the function is linear over the interval [b t , b t+1 ), since for x ∈ [b t , b t+1 ), we havê f (x) = kz 0 + x(z k − z 0 ) + kx · j:x<b j a j + k · j:x≥b j
Thus,f is piecewise linear. Furthermore, the slope of the line over the interval [b t , b t+1 ) is (z k − z 0 − β + kα t ), which strictly decreases as t increases. The fact that all slopes are distinct means that there are exactly J + 1 linear pieces, and the fact that these slopes are decreasing means that the function is concave over the interval [0, k].
For every function f that is nonnegative, piecewise linear with J + 1 linear pieces, and concave over the interval [0, k], there exists some k-CG function w of order J such that f is the continuous extension of w.
Proof. The function w will be defined by choosing parameters z 0 , z k , and (a j , b j ) for j ∈ [J]. Letf denote the continuous extension of the function w that we will build. From the proof of Lemma B.2, we know that the parameter b j will correspond to the jth breakpoint off . Therefore, given f , we set b j to be the jth breakpoint of the function f , so that the functions match at breakpoints. For convenience, we also set b 0 = 0 and b J+1 = k. We then set z 0 = f (0)/k and z k = f (k)/k, to guarantee thatf (0) = f (0) andf (k) = f (k). In order to set the a j values, we first compute the slopes of each line of f . Let f j = f (b j ) for j ∈ {0} ∪ [J + 1]. The jth linear piece of f has the slope:
Finally, for j ∈ [J] we set a j = 1 k (m j − m j+1 ). All of our chosen parameters satisfy the conditions of Definition B.3, so it simply remains to check that f andf coincide at breakpoints.
Let t ∈ [J]. Using (56) to evaluatingf at breakpoint b t , we get
Similarly, we see that J j=1 a j b j = 1 k (f J − f 0 − m J+1 b J ). Plugging this into (57), we get
So we see that f =f at breakpoints, and therefore these be the same piecewise linear function.
As we did for symmetric splitting functions, we can quickly find the best piecewise linear (1 + ε)approximation to a k-GSCB integer function w using a greedy approach. We omit proof details, as they exactly mirror arguments provided for the symmetric case. The submodularity constraint 2w(i) ≥ w(i+1)+w(i−1) for i ∈ {0}∪[k] can be viewed as a discrete version of concavity, and will ensure that the piecewise linear function returned by such a procedure will also be nonnegative and concave. After obtaining the piecewise linear approximation, we can apply Lemma B.3 to reverse engineer a k-CG function of a small order that approximates w. We obtain the same asymptotic upper bound on the number of linear pieces needed to approximate w. 
Recall that k-CG functions correspond to combinations of ACB-gadgets for a hyperedge e as well as directed edges between nodes in e and the source and sink nodes in some minimum s-t cut problem. Each ACB-gadget involves one new auxiliary node and 2|e| directed edges, and the number of ACB-gadgets is equal to the order of the k-CG function (the number of linear pieces minus one). Let H = (V, E) be a hypergraph with n = |V | nodes, where each splitting function is submodular, cardinality-based, and is not required to be symmetric or penalize only cut hyperedges. Finding the minimum cut in H corresponds to solving the sum of submodular splitting functions given in (49) . For ε ≥ 0, we can preserve cuts in H to within a factor (1 + ε) by introducing a source and sink node s and t and applying our sparse reduction techniques to each hyperedge to obtain a directed graphĜ = (V 