Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game
Abstract
Despite there being significant work on developing spectral [16, 39, 38], and metric embedding [48] based approximation algorithms for hypergraph generalizations of conductance, little is known regarding the approximability of hypergraph partitioning objectives beyond this.
This work proposes algorithms for a general model of hypergraph partitioning that unifies both undirected and directed versions of many well-studied partitioning objectives. The first contribution of this paper introduces polymatroidal cut functions, a large class of cut functions amenable to approximation algorithms via metric embeddings and routing multicommodity flows. We demonstrate an -approximation, where is the number of vertices in the hypergraph, for these problems by rounding relaxations to metrics of negative-type.
The second contribution of this paper generalizes the cut-matching game framework of Khandekar et al. [35] to tackle polymatroidal cut functions. This yields the first almost-linear time -approximation algorithm for standard versions of undirected and directed hypergraph partitioning [38]. A technical consequence of our construction is that a cut-matching game which greatly relaxes the set of allowed actions for both players can be used to partition hypergraphs with negligible impact on the approximation ratio. We believe this to be of independent interest.
1 Introduction
In the past 20 years, increasing complexity in real-world data has necessitated generalizing graph models to represent higher order relations [3, 15]. Hypergraphs have served as the quintessential object to model relations involving multiple objects, and, as a consequence, the study of hypergraph algorithms has featured prominently in recent practical [12, 57] and theoretical developments [16, 17, 47, 48].
Hypergraph partitioning is a fundamental algorithmic problem in this broader landscape. From an unsupervised machine learning perspective, hypergraph partitioning enables detecting significant clusters in complex higher-order networks, such as social [57, 61] or biological networks [28, 37]. From a theoretical perspective, partitioning algorithms are a fundamental primitive to be exploited in the development of divide-and-conquer methods for other hypergraphs problems. In contrast to graphs, where there is only one way for a partition to intersect an edge, hypergraphs admit multiple definitions for the cost of cutting a hyperedge. This yields a broad spectrum partitioning objectives, and allows the end-user to better design partitioning problems that fit specific applications. While there has been significant work on developing spectral approximation algorithms for hypergraph generalizations of conductance [16, 39, 38], with few exceptions [48], little is known about the approximability of large classes of hypergraph partitioning objectives beyond this. Even less is known regarding fast algorithms for these tasks.
This paper proposes a general model for partitioning hypergraphs. The first half of this paper identifies a large class of hypergraph partitioning objectives, which we call polymatroidal cut functions. This class is a subset of submodular cut functions previously considered by [43, 44] and captures both undirected and directed versions of almost all partitioning measures found in prior theoretical work. We show that these objectives possess properties that imply they are particularly well-suited for approximation methods based on metric embeddings and routing multi-commodity flows. This leads us to polynomial time -approximations for these objectives based on rounding -metric relaxations. The second half of this paper constructs fast algorithms that achieve similar -approximations by generalizing the cut-matching framework of Khandekar et al. [35]. This produces the first almost-linear time polylogarithmic approximation for both undirected and directed hypergraph conductance.
Let us now define concepts relevant to hypergraph partitioning. A hypergraph is a tuple , where is a set of hyperedges. The rank of a hyperedge is its cardinality . If every satisfies , the hypergraph is called -uniform. Hence, an undirected graph is a -uniform hypergraph. A key step in formalizing hypergraph cut problems is to define a suitable cut function on each hyperedge . This expresses the cost incurred when is cut by into and . Central to our work are submodular cut functions, defined by [43, 44]:
Definition 1 (Submodular Cut Function).
A function is a submodular cut function if it is submodular and satisfies .
The space of cut functions for an edge is spanned by the undirected edge cut function and the directed edge cut function , giving a complete classification of cut functions for rank- hyperedges. Higher-rank hyperedges support broader choices of cut functions. The most common example is the standard hypergraph cut function [16, 47]: , which takes value if is cut by and otherwise. If the hypergraph is associated with positive hyperedge weights , we can succintly write the cut function for the entire graph as .
With these definitions, we are interested in minimizing the submodular hypergraph ratio-cut objective.
Definition 2 (Submodular Hypergraph Ratio-Cut).
Given a hypergraph with positive hyperedge weights , non-negative vertex weights , and a collection of submodular cut functions , the ratio-cut objective on is defined for all as:
The ratio-cut of is .
When specialized to graphs111In the rest of the paper, for any undirected (resp. directed) graphs , unless otherwise specified, we assume that and are formed using the undirected (resp. directed) cut functions. ratio-cut objectives include both graph expansion (), graph conductance (). It also captures their directed counterparts, by replacing the undirected cut function with its directed analogue .
Previous Work on Submodular Hypergraph Partitioning
The standard hypergraph partitioning problem was first studied in the contexts of parallel numerical algorithms [15] and scientific computing [25].
Since then, many high-quality approximation algorithms have been developed for approximating hypergraph expansion and conductance. Louis and Makarychev [48] gave the first randomized polynomial-time -approximation algorithm for hypergraph expansion. This matches the best known approximation for the graph expansion [10], and uses the same relaxation to metrics of negative-type. Louis [47] and Chan et al. [16] developed a spectral approach towards approximation hypergraph conductance, achieving Cheeger-like guarantees. Their algorithms require solving semidefinite programs (SDP) to approximate the hypergraph spectral gap, returning a partition with conductance at most . Their results are known to be tight under the small-set expansion conjecture. In more recent work, Lau et al. used a similar approach to obtain a guarantee for directed graph conductance [39].
Much less is known about the approximability of hypergraph ratio-cut objectives for general submodular cut functions. Following the work of Yoshida [62], Li and Milenkovic [43, 44] proposed submodular cut functions. For submodular hypergraph conductance, rounding an SDP relaxation yields algorithms with conductance guarantees [62] and [44]. Li and Milenkovic [44] further conjecture that improving the dependence on hypergraph rank is -hard. The work of Yoshida [62] and the survey by Veldt et al. [60] provide excellent discussions of submodular cut functions and their applications.
Previous Work on Cut-Matching Games
Algorithms for the above settings require solving SDP relaxations over symmetric matrices, with at least constraints. No faster algorithms are currently known beyond generic SDP solvers [32], which run in time. Even for the simplest form of standard hypergraph partitioning, the resulting SDP relaxation is a mixed packing-and-covering program for which no almost-linear time algorithm is currently known [31].
In order to develop fast approximation algorithms, one then considers primal-dual methods that solve the dual to metric relaxations for ratio-cut problems. This poses an immediate issue; the dual to these relaxations are given by multi-commodity flow problems whose demands are encoded by a -weighted complete graph. Such problems may require quadratic time to solve [8] due to the large number of demands. The cut-matching game [36] was originally a method of approximately reducing this multi-commodity flow to a polylogarithmic number of exact single-commodity flow computations. Each single-commodity flow problem would route a perfect matching in the graph, until the union of matchings approximates the desired demand graph.
Through the cut-matching game, Khandekar et al. [36] obtained a -approximation to undirected graph expansion by exactly solving maximum flow problems. Later, Orecchia et al. [54] reduced both of these measures by . Subsequent works have vastly generalized the applicability of the cut-matching game: Louis [46] extends [36] to approximate directed graph expansion, Long and Saranurak extend [35] to approximate vertex and hypergraph expansion, and [49] demonstrate how to use the cut-matching game using approximate single-commodity flow solves. The cut-matching game has since become ubiquitous in designing fast deterministic algorithms for various static, and dynamic graph problems [13, 21, 22, 23].
Our Contributions
In this paper, we achieve the following.
-
•
We identify the class of polymatroidal cut functions, a subset of submodular cut functions amenable to metric and flow techniques. For this class, we develop notions of hypergraph flows and flow-embeddings of graphs into hypergraphs which certify lower bounds to the ratio-cut objective.
-
•
Using metric embedding techniques, we give polynomial-time -approximation algorithms for the minimum ratio-cut problem over submodular hypergraphs with polymatroidal cut functions. Our algorithms generalize the seminal result of Arora, Rao and Vazirani [8] for sparsest cut to the largest class of problems to date.
-
•
We extend the cut-matching game framework to approximate minimum ratio-cuts on submodular hypergraphs with polymatroidal cut functions. Our approach is based on approximating a continuous non-convex formulation of the minimum ratio-cut via a family of “local” convex submodular minimization problems. We then use the cut-matching framework to “boost” solutions to problems in this family, producing an -approximation algorithm for minimum ratio-cut that only requires a polylogarithmic number of approximate submodular minimization solves. This amounts to the first almost-linear time polylogarithmic approximation for both undirected, and directed hypergraph conductance.
A technical byproduct of our cut-matching game is that it allows for a cut player to play arbitrary disjoint vertex sets, and requires only a single -approximate submodular minimization solve per round. This may impact the deployment of cut-matching games in practice by lowering the required precision for the current running-time bottleneck of algorithms based on this framework [52, 58] as previous applications required either a single -approximate solves, or a polylogarithmic number of -approximate solves.
Our cut-matching game additionally avoids combinatorial restrictions found in previous applications of the framework. For example, the submodular minimization problem present in approximating hypergraph conductance is equivalent to a single-commodity flow whose demand graph is neither a perfect matching in the undirected case, nor Eulerian in the directed case. This may simplify the analyses of down-stream applications of the cut-matching game such as those found in [13, 21, 22, 23, 45, 49].
Concurrent Work
Subsequent to initial versions of this paper [6], Veldt [58] provided a generalization of the cut-matching framework to approximate minimum ratio-cut problems specified by cardinality-based symmetric submodular cut functions, a subset of polymatroidal cut functions. Their approach utilizes exact maximum flow solves to compute hypergraph cut preservers, a gadget which lower bounds the ratio-cut objective only when the cut function is cardinality-based [60, 59]. Unlike this work, [58] provides compelling empirical evaluations which should certainly be considered.
Independent of this work, Lau et al. [40] give an almost-linear time -approximation for standard undirected and directed hypergraph cut functions. Their algorithm solves the dual to a relaxation of hypergraph conductance given by adding -metric constraints to a minimum reweighted eigenvalue problem [39]. This yields a multi-commodity flow problem, which they demonstrate to be approximable using a sequence of single-commodity flows via an interesting generalization of Sherman’s algorithmic chaining [55]. Their algorithm is not based on the cut-matching game, and require similar combinatorial restrictions when routing the single-commodity flow as found in previous works.
Paper Organization
The paper is organized as follows:
-
•
Section 2 provides a technical overview of the results, and proof techniques found in this paper.
-
•
Section 3 outlines preliminary tools and notation.
-
•
Section 4.1 introduces polymatroidal cut functions, and provides key examples of functions in this class.
- •
-
•
Section 5 details our -approximation for minimum ratio-cut given polymatroidal cut functions, describing the -metric relaxation, and embedding results required to round an integral solution.
-
•
Section 6 describes our non-convex approach to the minimum ratio-cut problem and its connection to the cut-matching game.
-
•
Section 7 describes our cut-matching game framework and uses it to construct an -approximation algorithm to the minimum ratio-cut problem with polymatroidal cut functions.
The proof of several technical statements encountered throughout the paper are postponed to the appendix.
2 Our Results
2.1 The Metric Approach to Submodular Hypergraph Ratio-Cut
The best polynomial-time approximation algorithms for graph ratio-cut problems are obtained by combining metric relaxations, either to general metrics [42] or -metrics [10], with metric embedding results for rounding. They achieve respectively an and a -approximation ratio. We study the applicability of this approach to the submodular hypergraph ratio-cut problem. At the outset, we remark that we should not hope to obtain polylogarithmic approximation for general submodular cut functions without further assumptions, as Svitkina and Fisher (Section 3 in [56]) exhibit a submodular cut function for which any -approximation requires exponentially many queries to a value oracle.
Given this negative result, it is necessary to restrict the problem to a smaller class of cut functions. At a high level, for a metric relaxation to work, the cut function must exhibit some kind of monotonicity, so that its value is preserved under low-distortion metric embeddings. However, a cut function cannot be monotone without being equal to , so the monotone structure must appear in some other way. To solve this issue, we introduce the class of polymatroidal cut functions, which are the infimal symmetrization of monotone non-decreasing submodular functions (see below). We believe that this new class captures most cut functions that are amenable to approximation via metric relaxation. As partial evidence to this statement, we show in Section 4 that the fractional dual objects associated with polymatroidal cut functions are closely related to polymatroidal flows, a well-studied generalization of network flows with many of the same favorable flow-cut gap properties [19].
Polymatroidal Cut Functions and Metric Embeddings
Our first contribution is to define polymatroidal cut functions, a subclass of submodular cut functions given by the infimal convolutions of non-decreasing submodular functions.
Definition 3 (Polymatroidal Cut Function).
A cut function is polymatroidal if, for all , it can be expressed as
where the associated functions are non-decreasing submodular functions such that When the associated functions and are identical, we refer to the cut function as symmetric polymatroidal.
Note that penalizes a cut intersecting in a directed manner, with penalizing and penalizing . For a symmetric polymatroidal cut function , such penalty is the same, so that , generalizing the cut function of undirected graphs and hypergraphs. We show in Section 4 that Definition 3 captures most of the cut functions proposed in previous work, including all directed and undirected standard hypergraph cut functions. Moreover, our setup also captures possible combinations of all these types of cut functions into a single framework. We highlight two additional examples that are relevant in applications:
-
•
is a cardinality-based non-decreasing submodular function [59], i.e., a non-decreasing concave function of the cardinality. This is useful when we wish to modify the star-expansion cut function by diminishing the penalty on balanced partitions of e.g., by taking for
- •
In Section 5, we investigate the polynomial-time approximability of ratio-cut problems over submodular hypergraphs with polymatroidal cut functions. In particular, we prove the following result.
Theorem 1.
There exists a randomized polynomial-time -approximation algorithm for solving the minimum ratio-cut problem on weighted submodular hypergraphs equipped with polymatroidal cut functions.
This result extends the -approximation of Louis and Makarychev [48] for standard hypergraph sparsest cut to all ratio-cut problems for the more general class of polymatroidal functions. Our algorithm for Theorem 1 solves a novel -metric relaxation of the ratio-cut problem for weighted submodular hypergraphs (see the program RC-Directed-Semimetric in Section 5). This relaxation crucially exploits the form of the Lovász extension of polymatroidal cut functions. To the best of our knowledge, our results constitutes the broadest known generalization of the seminal result of Arora, Rao and Vazirani for sparsest cut, capturing a wealth of partitioning objectives, including directed and undirected graph ratio-cut, vertex-based ratio cut and hypergraph ratio-cut within a single simple analysis. It also improves on the best known approximation ratio for many other objectives in this class, such as cardinality-based cut functions [59].
Polymatroidal Cut Functions and Hypergraph Flows
In the second part of the paper, we explore the efficient solution of the minimum submodular hypergraph ratio cut problem via flow methods based on the cut-matching game. We start by developing the notions of flow-cut duality and flow embeddings over hypergraphs. For this purpose, in Section 4.2, we define a novel notion of hypergraph flows for weighted submodular hypergraphs equipped with polymatroidal cut functions. Specifically, for a weighted submodular hypergraph , we show that the subgradients of polymatroidal cut functions behave like network flows over the factor graph, a graph analogue of the input submodular hypergraph that includes an auxiliary vertex for each hyperedge and an edge for each For each hyperedge , the monotone functions and define capacity constraints on the flows entering and leaving the corresponding auxiliary node. In this process, we highlight new connections between submodular hypergraphs and the polymatroidal flows described by Lawler and Martell [41] and extended to the multi-commodity flow setting by Chekuri et al. [19]. The main algorithmic result in this part of the paper is a flow decomposition result for hypergraph flows (Theorem 6) which allows us to construct flow embeddings of directed and undirected graphs into hypergraphs while lower bounding the size of the hypergraph cut with the size of the corresponding graph cut. This will become a fundamental building block for our cut-matching game construction.
2.2 A Non-Convex Optimization Approach To Minimum Ratio-Cut
To generalize the cut-matching game framework to the setting of submodular hypergraphs with polymatroidal cut functions, we devise a novel optimization approach based on a continuous non-convex formulation (RC-NonCvx) of the submodular hypergraph ratio-cut problem. Given a weighted submodular hypergraph , and cut functions with Lovász extensions , we define (RC-NonCvx) as the following non-convex optimization problem over :
| (RC-NonCvx) |
The fact that solving (RC-NonCvx) is equivalent to solving the minimum ratio-cut problem (expressed in the following lemma) is a direct consequence of the submodularity of the cut functions. It is proved in full in Appendix A.
Lemma 1.
Given a weighted hypergraph , we have . Furthermore, there exists an algorithm that, given any , recovers a cut satisfying
in time , where the sparsity of is defined as
The main idea in our approach is to address the non-convexity of the objective by replacing the non-concave denominator with a linear lower bound. In particular, we can exploit the dual characterization of the -norm in the lower bound to write:
| (2) |
This calculation directly leads us to define a novel localized, convex formulation of the (RC-NonCvx) problem for each vector with and which we call a seed:
| (Local-RC) |
Intuitively, the program (Local-RC) seeks a distribution over cuts with small expected cut size and high correlation with the seed In Section 6, we investigate the properties of this formulation, including its equivalence with an integral cut problem, the ratio-cut improvement problem (Definition 10 in Section 6), which generalizes the cut improvement problem of Andersen and Lang [7] to submodular hypergraphs. For polymatroidal cut functions, we show that the natural notion of a dual solution for the convex problem Local-RC is exactly a hypergraph flow with demand vector By applying our flow decomposition result, we can turn such a hypergraph flow into a dual graph certificate, a graph such that for all To construct these objects, we prove the following algorithmic result:
Theorem 2 (Informal. See Theorems 9 and 10).
An approximate primal-dual solution to can be computed by solving -many decomposable submodular minimization problems for general polymatroidal cut functions or -many -approximate maximum flow problems over a graph of size
Finally, and crucially for our purposes, for all we have by Equation 2. Hence, any (not necessarily optimal) solution to (Local-RC) for a seed yields a solution to (RC-NonCvx) of value at most and, via Lemma 1, a cut with In other words, if we can somehow find a seed such that , then solving the (Local-RC) will yield an -approximation algorithm for
This reduction may not seem very useful, as finding the required seed may be as hard as solving the original problem. However, we can now exploit the dual feedback obtained when solving (Local-RC) for a sequence of seeds to effectively guide our search for a good seed and boost our approximation ratio. In particular, suppose we can adaptively construct a sequence of seeds such that the sum of the corresponding dual demand graphs has large ratio-cut, i.e., Then, it is easy to show (see Theorem 11 and its proof) that we must have Hence, solving (Local-RC) for one of the seeds in the sequence must yield a -approximation to the minimum ratio-cut problem. It turns out that the problem of constructing such sequence is precisely the task addressed by the cut-matching framework of Khandekar et al. [36], which we generalize and strengthen in our next contribution.
2.3 An Improved Cut-Matching Game
We now describe our new definition of the cut-matching game. A key distinction between our setup and the previous lies in what constitutes admissible actions played by the cut and matching players.
Definition 4.
Let be a set of vertices with vertex weights . A cut action is a pair of non-empty disjoint subsets such that
The cut player is no longer restricted to returning a partition of the vertex set, let alone a bisection. The set of valid actions for a matching player is similarly relaxed, as the edges of the response do not need to form a perfect matching. It is only required that enough of the available degree is routed across the cut action.
Definition 5.
An approximate matching response to a cut action is an weighted bipartite graph satisfying the following conditions.
-
1.
Bounded degree: for all
-
2.
Largeness: .
We may emphasize that is a directed approximate matching response, if the edges of are directed from to
This definition is motivated by the fact that an approximate matching response naturally arises from the dual graph certificate obtained by approximately solving the (Local-RC) program above. The matching response will be undirected when we wish to approximate the minimum ratio-cut of a hypergraph with symmetric cut functions and directed in the general case of asymmetric cut functions. Let us now define the cut-matching game.
Definition 6.
Let , and be a weighting over a set of vertices where . A -generalized cut-matching game is a multi-round, two-player game between a cut player , and a matching player that proceeds as follows. In the -th round of the game, following definitions 4 and 5:
-
1.
plays a cut action ,
-
2.
responds with an approximate matching response to .
The state graph after rounds is the edge-wise sum of the matching response seen thus far.
For comparison, the original cut-matching game of [36] is captured by the above definition when one specifically considers graph expansion , restricts cut actions to be exact bisections where , and requires exact matching responses: .
To approximate minimum ratio-cut using our cut-matching games, we seek a cut player that outputs a sequence of cuts which, in as few cuts as possible, forces the matching player to place edges that make the minimum ratio-cut objective for the state graph large. We call a cut player good if it can achieve this.
Definition 7.
A cut strategy is a randomized algorithm that takes as input the current state graph , and outputs a cut action . A cut strategy is -good if a cut player using at every iteration, achieves:
with constant probability, for any (potentially adaptive) sequence of approximate matching responses .
Note that, when dealing with symmetric cut functions, will be undirected, so that refers to the undirected ratio-cut objective. If the cut functions are asymmetric, then is naturally replaced with the directed ratio-cut objective.
These definitions reveal the mechanism by which the cut-matching framework adaptively constructs a sequence of seeds to (Local-RC): the seed we choose at every iteration of cut-matching game is just a -weighted indicator vector for the cut action of that round. A good strategy guarantees that, no matter what dual graph certificates we receive for each seed, at the end of the game at iterations, we can guarantee has ratio-cut objective at least . This shows that a good strategy yields an approximation ratio of for minimum ratio cut. In Section 7, we formalize this result as Theorem 11. Our main technical theorem (Theorem 12) regarding the new cut-matching game shows the existence of good strategies for the cut-player that yield -approximation algorithms for the minimum ratio-cut problem over submodular hypergraphs, for both the cases of symmetric and general polymatroidal cut functions. The proof of this theorem is based on a new geometric result about separated sets in vector embeddings, which we discuss below. Together with Theorem 2, our results on good cut-player strategies directly imply the following results for the solution of the minimum ratio-cut problem. Their short proof appear in Appendix A.5.
Corollary 1.
There exists an -approximation algorithm for the minimum ratio-cut problem over submodular hypergraphs with polymatroidal cut functions whose running time is dominated by the solution of a polylogarthmic number of decomposable submodular minimization problems over the hypergraph cut function.
Corollary 2.
There exists an -approximation algorithm for the minimum ratio-cut problem over submodular hypergraphs equipped with the directed or standard hypergraph cut function whose running time is almost linear in the hypergraph sparsity.
Separated Sets
In our new cut-matching game, the cut player must pay considerable more care in choosing a cut action than in the original version, as the approximate nature of the matching response means that the matching player may easily keep some small subset of vertices disconnected from the rest of the graph. Suppose for instance that the cut player restricted itself to play -bisections. Then, the matching player could select a small cut , with and never place any edge across the boundary of The only way the cut player can force progress on is to depart from playing bisections and play a cut action where is close or equal to
Let us see how this intuition is formalized in our design of cut-player strategies. As in the analysis of Orecchia et al. [54], our cut strategy maintains at each iteration a spectral embedding for the current state graph . We make progress if we can force the matching player to connect vertices that are far away in this embedding. We show that we can achieve this, even against an approximate matching player, by choosing a cut action coming from the following notion of separated sets:
Definition 8 (-separated sets).
Given an embedding and a measure we say two sets are -separated if:
This definition generalizes the idea of well-separated sets [10], which was applied only to large balanced sets, to possibly unbalanced sets, as long as and contribute a -fraction to the total variance of the embedding. In Section 8, we show how to efficiently find separated sets and prove the following result.
Theorem 3.
Given an embedding and a measure , with , there exists a randomized algorithm running in time that outputs -separated sets and for with high probability.
3 Preliminaries
Hypergraphs
The sparsity of a hypergraph is defined as Throughout the paper, we assume that the edge weights and vertex weights of our instance submodular hypergraph are polynomials in In particular, we have
Linear Algebra Notation
Throughout this paper, we adopt the convention of representing scalars in unbolded lowercase, vectors in boldface lowercase, and matrices as boldface uppercase. Given vectors , we will use to denote the Hadamard (entry-wise) product between and . We will use to denote the vector whose entries are the absolute value of the entries in . We let denote the standard Euclidean inner product, the Euclidean norm, and the -norm.
We define an inner product between weighted by a non-negative vector as The quantity will denote the norm induced by the inner product , while for any , we use to denote the -norm weighted by Note consequently that . For , we write to indicate the relation: .
Given any vector , we define the positive and negative parts of as the vectors with and
If , then denotes the Frobenius inner product. We let be the set of by symmetric matrices. Given we denote by the statement that is positive semidefinite, and by the relation . We use to denote the real matrix with the coordinates of placed along its diagonal. We will reserve specifically the matrix for the non-negative vector .
Given a finite set , a vector , and a subset , we let . We also denote by , the restriction of to coordinates in . In this way, the vector denotes the -indicator of set .
Preliminaries on Graphs
Given a graph , denote its combinatorial Laplacian as :
If is directed, then we will associate with it a directed Laplacian given by
where is the Laplacian of an undirected graph , and is on -th entry and everywhere else. We will denote as the symmetrization of , i.e. the weighted undirected graph formed by taking the edge-wise sum of and its reverse graph.
Factor Graphs
A hypergraph is naturally associated with its factor graph, an unweighted graph that is bipartite between the variable vertices representing vertices , and factor vertices representing hyperedges . For and , the edge belongs to if and only if , i.e.:
Submodular Functions
A set function is submodular if for all , we have:
From the above, one can easily see that the set of submodular functions is closed under taking conic combinations. Following standard conventions, we will always assume that unless specified otherwise.
Any submodular set function can be associated with a convex body , known as its base polytope:
| (4) |
When is monotone non-decreasing and it is convenient to employ the positive submodular polyhedron:
Crucially, a submodular set function can be extended to its convex closure, known as its Lovász extension and denoted by There are a number of equivalent characterizations of the Lovász extension and its connection to the base polytope and the positive polyhedron . Rather than listing them here, we will refer directly to the results in Chapter 3 and 4 of the excellent reference by Bach [11]. We make an exception for the following fact, which plays a crucial role in the analysis of our approximation algorithms based on metric embeddings. See Proposition 4.8 in [11] for a proof.
Fact 1.
Let be a monotone non-decreasing submodular function with . Its Lovász extension is monotone, non-decreasing over
Online Linear Optimization and Regret Minimization
Fix a convex set of actions . The setting of online linear optimization over symmetric matrices considers the following multi-round game: in each round , a player plays an action , receives a feedback matrix , and suffers a loss of . The goal of the player is to play actions which minimize total loss incurred. In general, one cannot hope for a strategy that is competitive against an arbitrary, adaptive adversary. Thus, one instead seeks to minimize regret: the difference, up to a time horizon , between total loss and the loss suffered by the best fixed action in hindsight.
We will require a regret minimization strategy to produce a sequence of for this setting. Fortunately, many prior results [9, 5, 29, 34, 51, 53] have studied this, and a Matrix Multiplicative Weight Update algorithm works off-the-shelf.
Theorem 4 (Theorem 3.3.3 in [51]).
Fix , and a weight vector . Let be a sequence of feedback matrices such that there exists where for every . For any step size , define to be given by the matrix multiplicative weight update
| (matrix-mwu) | ||||
Then, the following inequalities hold for any . We have:
| (6) |
Furthermore, if for every (i.e. ), and there exist such that , then:
| (7) |
4 Polymatroidal Cut Functions and Hypergraph Flows
In this section, we establish the main properties of the polymatroidal cut functions in Definition 3. In the second part of the section, we introduce the dual notion of hypergraph flows as natural lower bounds to polymatroidal cut functions and highlight their connection with previously studied polymatroidal flows [19]. Finally, we define the notion of flow embedding of a graph into a hypergraph.
4.1 Properties and Examples
We start by verifying that any polymatroidal cut function is submodular. A proof of the following fact can be found in Appendix A:
Fact 2.
Let be an arbitrary finite set and be monotone non-decreasing submodular functions. If is the function defined by:
for all , then is submodular.
Examples of Polymatroidal Cut Functions
We now show that the class of polymatroidal cut functions encompasses many popular cut objectives. Our first example is the directed edge cut function in graphs. This function is defined on a directed edge as:
It is easy to check that this function is polymatroidal, since it can be rewritten as:
for all . Next, we consider the standard hyperedge cut function. Given a hyperedge , this function is defined as:
Note that the undirected cut function in graphs is a special case of . This function is symmetric polymatroidal, as we can let for any to obtain:
which is if and only if intersects non-trivially, and zero otherwise.
Moreover, the class of directed hypergraph cut functions recently introduced by Lau et al. (Section 6.2 of [40]) to define directed hypergraph expansion is also a sub-class of polymatroidal cut functions, as we now show. Given a hyperedge and a partition of into a tail set and a headset , we can capture the directed cut function of Lau et al., by letting and .
Finally, Veldt et al. [59] consider a class of cut functions which are cardinality-based and submodular. In Appendix B.2 of their paper, they argue that every such cut function can be written as:
for some concave and monotonically increasing function . Since is monotonically increasing, the above gives:
and hence all functions in this class are also examples of polymatroidal cut functions (note that the composition of a monotone, concave function with the cardinality function is always monotone and submodular).
Lovász Extensions of Polymatroidal Cut Functions
We next establish the form of the Lovász extension of a polymatroidal cut function. We will make heavy use of this form in building our metric relaxations and in rounding them via low-distortion metric embeddings in Section 5. The proof of the following fact is found in Appendix A:
Fact 3.
Given a polymatroidal cut function , we have, for all :
It is instructive to consider how the previous results are instantiated for the two canonical examples of the directed edge cut function and the standard hypergraph cut function. For the former on an arc , we have and so that:
For the latter, on a hyperedge :
In the case of a symmetric polymatroidal cut function, the characterization of Fact 3 can take a more compact form, as shown in Appendix A:
Fact 4.
Given a symmetric polymatroidal cut function with , we have, for all :
4.2 Base Polytope, Hypergraph Flows and Polymatroidal Networks
It is natural to attempt to lower bound the cost of cuts in a submodular hypergraph by considering collections of vectors , where each vector belongs to the base polytope of the polymatroidal cut function under consideration. In this section, we interpret these vectors as hypergraph flows over and show that they take the form of polymatroidal flows [41, 19] over the factor graph .
Base Polytope of Polymatroidal Cut Function
We start by characterizing the base polytope for a polymatroidal cut function By the definition of base polytope in Equation 4.2, we have
The first constraint implies that for all we must have Hence, we can rewrite:
| (8) | ||||
We will interpret an element of as a flow over the neighborhood of factor vertex in the factor graph , with indicating flow going from to and flow going from to . The constraint simply represents flow conservation at With this setup, for each set the function (resp. ) constrains the amount of flow that can be routed from the set to (resp. to the set from ).
Example: Base Polytope for Standard Hypergraph Cut Function
Consider the case of the standard hypergraph cut function defined in the previous section. Then, it is easy to see that:
As discussed above, we can think of each entry of for , as the amount of flow flowing into from vertex , and the constraint enforces that the total amount of flow through the hyperedge is no more than . This is equivalent to a vertex capacity constraint on the factor vertex corresponding to the hyperedge in the factor graph .
Example: Base Polytope for Directed Hypergraph Cut Functions
Consider the class of directed hypergraph cut functions defined by Lau et al. in Section 6.2 of [40]. Each of these cut functions has an associated head set and an associated tail set and has value one if and only if the head set intersects and . Their base polytope is then given by:
The notion of hypergraph flow, which we introduce next, formalizes the network flow interpretation for all hyperedges
Hypergraph Flows
Given a weighted submodular hypergraph , a hyperedge flow over a hyperedge is a vector A hypergraph flow is a direct sum of hyperedge flows Analogous to the case for graph flows, we define a notion of congestion based on the maximum violation of the polymatroidal constraints defining each :
| (9) |
The demand vector of a hypergraph flow is
| (10) |
We will make use of the vector space structure inherited from to define linear combinations of hypergraph flows for any The demand vector also behaves linearly as
Finally, notice that hypergraph flows over hyperedges of rank are equivalent to graph flows as, for an edge , represents the flow from to , while is the flow from to .
Connection to Polymatroidal Flows
In the polymatroidal network flow model [19, 41], one has a directed (2-uniform) graph representing a flow network where the edges are not individually capacitated, but rather for every vertex , there are monotone submodular functions and constraining the amount of flow entering and exiting a vertex respectively.
Given an hypergraph flow over , one can interpret it as a graph flow over the factor graph , where the flow from vertex to factor vertex over the edge is given by . When the congestion (as defined in (9)) is required to be at most one, the constraints imposed on this flow on can be cast as constraints defining a flow in a polymatroidal network supported on . Here, each constraint on the hyperedge flow for hyperedge defined by its base polytope, can be encoded as polymatroidal constraints on the graph flow into and out of the vertex in .
Despite this connection with polymatroidal network, we remark that, to the best of our knowledge, the hypergraph partitioning problems studied in this paper cannot be expressed in the setup proposed by Chekuri [19] for defining sparsest cut problems over polymatroidal networks.
4.3 Hypergraph Flow Embeddings
To construct efficient flow-based algorithms for the minimum ratio-cut problem in the second part of this paper, we will need a way to generalize the notion of flow embedding of a demand graph into a graph to the setting of hypergraphs. In this section, we leverage the definition of hypergraph flows to provide this generalization. In particular, we define the flow embedding of a (directed) graph into a weighted submodular hypergraphs with polymatroidal cut functions. We also show that these embeddings yield lower bounds on the hypergraph cut functions in terms of the graph cuts of the embedded graph. Analogously to graphs, we also show that any hypergraph flow can be converted into a flow embedding via flow-path decompositions.
Definition 9 (Hypergraph Flow Embedding).
Let be a weighted submodular hypergraph equipped with a collection of polymatroidal cut functions and let be a weighted directed graph on the same vertex set. We say that the graph embeds into as a flow with congestion , denoted if there exist hypergraph flows such that:
-
1.
For all , the flow routes units of flow from vertex to vertex , i.e.,
-
2.
For each , the flows respect the polymatroidal capacity constraints, i.e., for all :
The capacity constraints can be understood by analogy with the capacity constraints for multi-commodity flows over a graph. As in that case, the constraints in the definition ensure that flows from different commodity along the same arc do not cancel out.
We will use this notion of embeddability to certify lower bounds to the ratio-cut objective for general polymatroidal cut functions. We will crucially make use of the following theorem in our development of the cut-matching game for solving ratio-cut problems over weighted submodular hypergraphs. Its proof is in Section A.
Theorem 5.
Let be a weighted hypergraph equipped with a collection of polymatroidal cut functions , and be a weighted directed graph. If , then
For symmetric polymatroidal cut functions , then implies the following bound on the undirected symmetrization :
We now state the main algorithmic result of this section, which allows us to construct hypergraph flow embedding from any single hypergraph flow. Just like in the case of graphs, this result is based on constructing a flow-path decomposition of the original flow. The particular form of polymatroidal cut functions plays monotonicity of the functions and plays a crucial role in bounding the congestion of the embedding, which cannot be controlled in the same way for general submodular cut functions. The proof appears in Appendix A.
Theorem 6.
Let be a weighted hypergraph equipped with a collection of polymatroidal cut functions . Given a hypergraph flow over , there is an algorithm that, in time , computes a weighted directed bipartite graph such that and . Furthermore, all vertices with non-negative (resp. negative) demand are source nodes (resp. sink nodes) in , each with out-degree (resp. in-degree) equal
5 An -Approximation via -Metric Embeddings
In this section, we prove Theorem 1 by giving an -metric relaxation and rounding argument yielding a randomized polynomial-time -approximation algorithm for the minimum ratio-cut problem over submodular hypergraphs equipped with polymatroidal cut functions. As a warm-up, we give the simpler argument for symmetric polymatroidal cut functions, before proving the result for general polymatroidal cut functions in Section 5.2
5.1 Warm-up: Symmetric Polymatroidal Cut Functions
We begin by providing a relaxation for the symmetric version of the problem, in which for every . All the results in this subsection will focus exclusively on this special case, but they will be extended to the general case of all polymatroidal cut functions in the following subsection.
Given a weighted submodular hypergraph , we construct a vector-program relaxation of the continuous non-convex formulation in Equation (RC-NonCvx) by associating to each vertex of the factor graph a vector . For a hyperedge and we can then relax the terms , which make up the argument of in Fact 4, with the distance We obtain the following semidefinite program in its vector embedding form:
| (RC-Metric) | ||||||
| s.t. | ||||||
The following simple lemma is proved in Appendix A.
Lemma 2.
The (RC-Metric) vector program is, up to a constant, a relaxation of the minimum ratio-cut program for the hypergraph with symmetric polymatroidal cut functions
Rounding via Metric Embedding
To round the convex program (RC-Metric), we apply the following well-known embedding result, which is implicit in the seminal work of Arora, Rao and Vazirani [10].
Theorem 7 ([10]).
Let be a feasible solution to the -metric relaxation (RC-Metric). Then, there exists an efficiently computable -Lipschitz222Recall that, given a metric space , a function is said to be -Lipschitz for some constant if for every . map satisfying:
To complete the proof of Theorem 1 for the special case of symmetric polymatroidal cut functions, we make use of the embedding in Theorem 7. The proof crucially relies on the monotonicity of the Lovász extension (Fact 1). The ability to perform this step can be taken as a justification for our definition of polymatroidal cut functions.
Lemma 3.
There is a polynomial-time algorithm that given a solution to (RC-Metric) of objective value , returns a cut such that:
Proof.
Apply Theorem 7 to obtain and with for all and . The -Lipschitzness of guarantees, for every and :
By the monotonicity of in Fact 1, we have:
| (12) |
It now suffices to obtain a lower bound on the denominator in the continuous formulation (RC-NonCvx):
| (13) |
Finally, Equations (12) and (13), yield, together with Fact 4:
The vector can then be efficiently rounded to a subset by Lemma 1. ∎
5.2 General Polymatroidal Cut Functions
For the case of general polymatroidal cut function, our metric relaxation must be able to capture the signed terms and that appear in the Lovász extension in Fact 3. For this purpose, we will use the directed -semimetrics introduced by Charikar, Makarychev and Makarychev [18] and, for every and , relax to and to . We obtain the following semidefinite program:
| (RC-Directed-Semimetric) | ||||||
| s.t. | ||||||
We have the following lemma, which we prove in Appendix A.
Lemma 4.
The (RC-Directed-Semimetric) vector program is, up to a constant, a relaxation of the minimum submodular hypergraph ratio-cut problem for the hypergraph with polymatroidal cut functions
Rounding via Metric Embedding
To round a solution to the program (RC-Directed-Semimetric) to a solution of the original ratio-cut problem (RC-NonCvx), we require a version of the embedding result of Theorem 7 for directed semimetrics. The following result is a simple consequence of the rounding algorithm of Agarwal et al. [2] for a similar relaxation of directed expansion. We prove it for completeness in Appendix A.
Theorem 8.
Given a feasible solution to RC-Directed-Semimetric and a measure , there exists a polynomial-time computable map such that:
-
1.
for all ,
-
2.
and:
We can now complete the proof of Theorem 1 for the general polymatroidal case by showing that the map in Theorem 8 yields a -approximate solution to the minimum ratio-cut problem.
Lemma 5.
Given a solution to RC-Directed-Semimetric of value , we can produce in polynomial time a set such that:
Proof.
Let be the map whose existence is guaranteed by Theorem 8. Let and be the vector given by for all and for all By the first condition in Theorem 8, we have, for all and :
We can now exploit the monotonicity of the functions and associated with the polymatroidal cut functions . By Fact 3 and Fact 1, we have:
We can now lower bound the denominator in the objective of Equation (RC-NonCvx) as in Equation 13. Finally, we have:
The vector can then be efficiently rounded to a subset by Lemma 1. ∎
6 Localized Convex Formulations and Ratio-Cut Improvement
In this section, we consider the localized formulation (Local-RC) introduced in Section 2.2, which we rewrite as a convex program. We show that the dual solutions to this problem are hypergraph flows, which can be used to obtain hypergraph flow embeddings into the input graph. Finally, we give algorithms that construct approximate primal-dual solutions for the (Local-RC) problem. These algorithms will play an important part in our cut-matching game.
We start by introducing the ratio-cut improvement objective, a local partitioning objective parametrized by a seed , which is the integral analogue of the (Local-RC) problem:
Definition 10 (Ratio-Cut Improvement Problem).
Given a weighted submodular hypergraph , cut functions , and a seed vector with and the ratio-cut improvement objective is defined for all as:
The ratio-cut improvement problem asks to find achieving .
The ratio-cut improvement problem can be thought of as attempting to find a cut which has both a small boundary and high correlation with the input seed simultaneously. In Appendix B, we demonstrate that the problem of minimizing is precisely the generalization of the cut-improvement problem of Andersen and Lang [7] to weighted submodular hypergraphs and fractional seeds.
The relation between the minimum ratio-cut problem, the ratio-cut improvement problem and their continuous formulations (RC-NonCvx) and (Local-RC) is formalized in the following lemma.
Lemma 6.
For all , and seeds satisfying and , we have:
In particular, setting yields is a relaxation of for any :
Proof.
By the duality of conjugate norms, we have
for all . Consequently,
as required. ∎
Of critical, algorithmic, consequence is the fact that computing the value of can be written as a convex program. We refer to this program as (CI-Primal):
| (CI-Primal) | ||||||
| s.t. |
The following lemma is a simple consequence of the positive homogeneity of the Lovász extensions of submodular functions (Proposition 3.1 in [11]).
Lemma 7.
The optimum value of (CI-Primal) equals .
With this convex program, one can leverage convex duality to construct lower bounds for , and consequently . We consider a dual formulation of (CI-Primal) as a problem over hypergraph flows:
| (CI-Dual) | ||||||
| s.t. | ||||||
In this setting, strong duality between (CI-Primal) and (CI-Dual) holds by virtue of the (CI-Primal) having a finite number of polyhedral constraints. The full proof of the following lemma can be found in Appendix A.
From this point onwards, we restrict our attention to the kind of seed vectors that we will encounter in our application to the cut-matching game. For this purpose, we define the following notation for disjoint sets with :
Notice that is a valid seed for the local formulation of the minimum ratio-cut problem as and For this kind of seed, the dual problem can be interpreted as a maximum concurrent single-commodity flow over the hypergraph , in which we each vertex is asked to route demand to and each vertex in is asked to receive demand from . For a solution of value , each vertex will be able to route an fraction of its demand and the total demand routed from to will be Notice that, in the graph case, for , this construction specializes exactly to the undirected maximum concurrent flow problem used by Andersen and Lang [7] to solve the ratio-cut improvement problem.
Approximate Solutions
In Section 6.2, we will discuss how, for many kinds of polymatroidal cut functions, approximately feasible dual solutions to (CI-Dual) can be obtained by approximately solving a maximum flow problem over the factor graph or an augmented version of it. For this purpose, it is convenient to introduce a notion of approximate dual solution of value to (CI-Dual).
Definition 11 (Approximate dual solution).
Let be a weighted submodular hypergraph equipped with polymatroidal cut functions , and disjoint sets with . An approximate dual solution of value for is a hypergraph flow such that the following hold simultaneously:
-
1.
has unit congestion, i.e., ,
-
2.
routes a -fraction of the required flow from to , i.e., at least flow,
-
3.
does not exceed the require demand at every vertex, i.e., .
6.1 Graph Certificates from Approximate Dual Solutions
As discussed in Section 2.2, our plan is to apply the cut-matching game to combine local lower bounds given by approximately optimal solutions to (CI-Dual) into global lower bounds for the non-convex problem . To carry out this plan, we need to express our local lower bounds, i.e. dual solutions to (CI-Dual) in terms of hypergraph embeddings of graphs into the instance hypergraph.
Definition 12.
Let be a weighted submodular hypergraph equipped with polymatroidal cut functions , and disjoint sets with Let An approximate dual graph certificate of value for the (Local-RC) problem with seed is a directed graph with the following properties:
-
1.
is sparse, i.e.,
-
2.
embeds into with congestion , or equivalently
-
3.
is bipartite from to , i.e. all arcs of go from to ,
-
4.
for all , we have the degree bounds and ,
-
5.
is large, i.e., .
Following Theorem 5, we may assume that is undirected if all cut functions are symmetric.
In the cut-matching game framework, we will use dual graph certificates to iteratively construct lower bounds to through the application of Theorem 5. For example, given an approximate dual graph certificate of value , Theorem 5 yields the lower bound:
As we built from a dual solution for (CI-Dual) with seed , this lower bound is tighter for cuts that are well-correlated with , reaching its maximum when
We can now apply the flow-path decomposition of Theorem 6 to show how to efficiently construct an approximate dual graph certificate from an approximate dual solution. The straightforward proof is found in Appendix A.
Lemma 9.
Under the same assumptions of Definition 12, consider an approximate dual solution of value to the ratio-cut improvement problem on Let be the directed graph obtained by applying the flow-path decomposition algorithm of Theorem 6 to the hypergraph flow . Then, the scaled graph is an approximate dual graph certificate of value
6.2 Approximately Solving (Local-RC)
In this section, we discuss algorithms that construct approximate solutions to (CI-Primal) and (CI-Dual), the primal and dual convex formulations of (Local-RC) . Our specific focus is to describe algorithms that implement the following specification:
Definition 13.
Given a weighted submodular hypergraph with polymatroidal cut functions and disjoint sets with , an approximate primal-dual oracle problem is an algorithm that takes as input and the seed vector . For some the algorithm outputs both:
-
1.
a cut with
-
2.
an approximate dual graph certificate of value
We prove the following two theorems in Appendix C by a simple application of binary search over The first thereom bounds the complexity of constructing an approximate primal-dual oracle for general polymatroidal cut functions.
Theorem 9.
For submodular hypergraphs with general polimatroidal cut functions, an approximate primal-dual oracle can be implemented in time where is the running time for a quadratic optimization oracle for by solving -many decomposable submodular minimization problems.
Our second theorem shows how this result can be significantly improved in the case of the standard hypergraph cut functions by relying on almost-linear-time maximum flow solvers [13, 20].
Theorem 10.
For a submodular hypergraph equipped with the directed or standard hypergraph cut functions, an approximate primal-dual oracle can be implemented in almost linear-time by solving -many -approximate maximum flow problems over a directed, vertex-capacitated version of the factor graph
7 An -Approximation via Generalized Cut-Matching Games
We now describe how to use our cut-matching game to approximate minimum ratio-cut. Let us begin by stating the precise approximation guarantee garnered by running a game between a good cut strategy, and an approximate primal-dual solver for the ratio-cut improvement problem (Local-RC).
Theorem 11.
Let be an input submodular hypergraph equipped with polymatroidal cut functions. Consider an execution of the cut-matching game in which the cut player plays an -good cut strategy, while the matching player plays the dual graph certificates output by an approximate primal-dual oracle (Definition 13) on . Let be the cuts output by . Then, with constant probability, we have the following approximation result:
This is a standard result for cut-matching games and its proof does not deviate too far from that in previous work. We give its proof in Appendix D for completeness.
Theorem 11 reduces the task of approximating minimum ratio-cut to constructing a good cut strategy. Hence, this section is devoted towards proving the following theorem.
Theorem 12.
Let be the state graph for an -generalized cut-matching game. There exists a cut strategy satisfying the following:
-
1.
If is undirected, then is -good with probability .
-
2.
If is directed, then is -good with probability .
Furthermore, outputs a cut action in time .
To prove this theorem, we give an optimization-based analysis of the cut-matching game by using regret minimization techniques from online optimization to construct and analyze . This approach is very natural: the goal of online optimization is to adaptively produce a sequence of actions that will lead to some terminal outcome despite the presence of adversarial response. For the cut-matching game, the cut player’s goal is to produce a short sequence of cut actions such that, no matter what approximate dual responses are given by , the state graph will have large ratio-cut objective.
This approach also provides insight into why earlier combinatorial restrictions on valid cut and matching responses are not necessary when using the cut-matching game to partition (hyper)graphs. An interesting byproduct of our construction, in the case where are asymmetric, is that does not necessarily route Eulerian demand graphs. Additionally, no further reductions are required to enforce these combinatorial restrictions when approximating ratio-cut objectives beyond expansion.
To prove Theorem 12, we first describe our construction of for the case where the cut functions defining the ratio-cut objective are symmetric, and is undirected. Simply considering this case already demonstrates a large fraction of our technical contributions. We then consider asymmetric cut functions and directed , highlighting key differences from the symmetric case.
7.1 An -good Cut Strategy for Symmetric Cut Functions
We first consider the case where the polymatroidal cut functions are symmetric.
Let us start by instantiating the online linear optimization setting in the context of our cut-matching game. For an instance of a -generalized cut-matching game, fix the action set to be where
At the end of round , the matching player will have produced approximate matching responses . Choose the -th feedback matrix to be . The loss incurred during round is then
We instantiate online linear optimization in this way because any bound on regret now translates to a lower bound on the ratio-cut objective for the state graph . When are symmetric, is an undirected graph, and is simply the undirected ratio-cut objective, which has the following trivial SDP relaxation:
Lemma 10.
Given any undirected graph , we have where is the optimal objective value for the following semidefinite program.
| (cond-sdp) | ||||||
| s.t. | ||||||
Our choice of action set thus coincides with the feasible set for (cond-sdp), while the feedback matrices are chosen so that the sum of the losses give the SDP objective for the state graph. This is as intended; we want the cut player to force a state graph with large ratio-cut objective, thus it is crucial to have some lower bound on the ratio-cut objective that is a function of both cut, and matching responses. This is also to be expected; if we wanted regret minimizing strategies to produce approximate solutions for (cond-sdp), then we would have defined the action set and losses in exactly the same way.
Three issues remain if we wish to use a regret bound from Theorem 4 to analyze a good cut strategy:
-
(1)
Ensuring Small Width: We need to ensure that the width term is small given any approximate matching response .
-
(2)
Ensuring Large Loss: For our cut strategy to be good, we will need to specify how to produce a cut action such that the loss regardless of what approximate matching response is played.
-
(3)
Implementing in Nearly-linear Time: If we want our cut player to run in nearly-linear time, then we will (a) need to compute the update in nearly-linear time, and (b) ensure that queries on the vector embedding given by the Gram matrix of the update can be computed in sublinear time.
Let us address these issues now.
7.1.1 Ensuring Small Width
The width term is constant for any approximate matching response. This follows simply from the fact that the degree of any vertex is bounded by .
Lemma 11.
Any approximate matching response satisfies .
Notice that, since , the regret guarantee in Theorem 4 holds for any step-size .
7.1.2 Ensuring Large Loss
Let be a vector embedding of whose Gram matrix is . If is the approximate matching response at time , then the loss is equivalent to
For our cut strategy to be good, we need to produce a cut action such that, no matter how is played, the edges of will always be placed across pairs of embedding vectors , that are well-separated under the -norm. This can be difficult to guarantee if the flow routed is approximate. If the primal-dual solver can only route a constant factor approximate flow, then an adversarially chosen constant fraction of the demand may be dropped. If one naively rounds using a random 1-dimensional projection, as in [9, 53], then the rounding can produce an unbalanced cut, upon which the adversary can choose to drop a fraction of demand that routes between all vertex pairs whose embedding vectors are far apart in -distance.
Previous works [23, 22, 49] have addressed this issue by routing a polylogarithmic number of -factor approximate maximum flows during a single iteration of the cut-matching game However, a technical contribution of this construction is that a single approximate primal-dual solve of (Local-RC) suffices, provided are -separated in the sense of Definition (8).
The following lemma shows that any approximate matching response routing demand across -separated must always route a large amount of flow between embedding vectors that are well separated in -distance. Using as the cut action will thus always result in large loss.
Lemma 12.
Given , let and be the vector embedding whose Gram matrix is . If is -well separated with respect to and , then for any approximate matching response with respect to , we have:
Proof.
Since are -separated we have for all and :
Here, we use to deduce . Rearranging the above inequality then implies
where the last inequality follows by . Finally, any approximate matching response is bipartite across , and has large total weight. Thus we can conclude
as required. ∎
In section 8, we give an algorithm round-cut that produces -separated . This algorithm will subsequently be used in our cut strategy construction for the symmetric case.
7.1.3 Implementing MMWU in Nearly-linear Time
Computing in nearly-linear time, along with -distances and projections in logarithmic time are standard techniques. We briefly sketch them here.
Lemma 6 in [9] states one can compute a matrix-vector product with a matrix exponential by truncating its Taylor expansion. Given any and , one can compute such that
in time where is matrix-vector product time. To compute in nearly-linear time, we take advantage of two details.
First, each loss matrix provided to MMWU is given by the Laplacian of a graph . Consequently, the sparsity of the matrix being exponentiated in MMWU is bounded by . Consequently, matrix-vector product time satisfies where is the total number of cut-matching game rounds. Second, Lemma 11 implies that for every , and thus
If we run at most iterations of the cut-matching game, we can compute an -additive approximation to MMWU by truncating the Taylor expansion up to a number of terms.
To compute -distances, and projections in logarithmic time, one can use the Johnson–Lindenstrauss transform [33] to project the embedding into dimensions for (See, e.g. [24, 1, 14]). Since the error is multiplicative in terms of pairwise -distances, picking to be constant only causes a constant factor loss in the number of cut strategy plays, and the final approximation ratio. We will ignore this constant in the subsequent calculations 333Picking loses a factor in the final bound on when proving Theorem 12.
7.1.4 Completing the Analysis for Symmetric Cut Functions
We are now ready to describe the cut strategy which we call . Fix a step size to be chosen subsequently, and consider round of a -generalized cut-matching game. Up to this point, the matching player will have produced approximate matching responses .
The cut strategy is straightforward: use Johnson-Lindenstrauss and the truncated Taylor expansion, as in Lemma 6 of [9], to compute a low-dimensional projection of the embedding whose Gram matrix is given by , execute round-cut on the resulting embedding to produce -separated sets , and output as the cut action. Our strategy is summarized in Algorithm 2.
Algorithm 1 . Input: vertex measure , and approximate matching responses . Parameters: step size . Do: The following. 1. Sample random unit vectors . 2. Denote , and compute given by using the truncated Taylor series via [9]. 3. Execute to produce the cut . Output: The cut .
Let us now demonstrate that is a -good cut strategy.
Lemma 13.
Let be an input submodular hypergraph equipped with symmetric polymatroidal cut functions such that . Then is -good with probability .
Proof.
Let , and for any sequence of weighted undirected approximate matching responses , suppose plays cut actions in response. To show that is a -good cut strategy, we first show that after rounds of the cut-matching game.
Fix to be the state graph of the cut-matching game. For every , the feedback matrix satisfies , hence we can use the regret bound given by (7) in Theorem 4. Lemma 11 ensures
Consequently, we have for every and :
Next, for fixed , let be the vector embedding whose Gram matrix is . Theorem 3 implies round-cut outputs -separated sets . Lemma 12 then implies
for some absolute constant . Let be constant satisfying , then with choice of , and , we have that:
and thus establishing for every
| (18) |
Now choose , the minimizer to the semidefinite relaxation (cond-sdp) for . Certainly , since is feasible. If is the optimal objective value of (cond-sdp), then by inequality (18)
Finally, Lemma 10 implies the required
To ensure that we obtain the above guarantee with good probability, note that the randomizes Johnson-Lindenstrauss transform fails to produce an embedding with the necessary distortion guarantees with probability . By the union bound, the probability that this procedure fails at all over any iteration is then . The only other randomized part of the algorithm is the balanced case of Algorithm 4. We know from Theorem 3 that one obtains a -separated set with probability at each iteration, which again by the union bound guarantees that this procedure will fail during the algorithm with probability . Hence the algorithm will produce the desired output with probability . ∎
7.2 An -good Cut Strategy for Asymmetric Cut Functions
Let us now consider the case where are asymmetric. We describe our setup for the online linear optimization setting.
Given an instance of a -generalized cut-matching game, we again fix the set of actions to be . For round of the online optimization setting, we now define the feedback matrix to be the directed Laplacian of the approximate matching response : so that the losses become
Similar to the symmetric case, our choices of action set and loss functions are guided by the trivial spectral relaxation for the directed ratio-cut of a graph.
Lemma 14.
Given any weighted, directed graph , we have where is the optimal objective value for the following semidefinite program.
| (dir-cond-sdp) | ||||||
| s.t. | ||||||
In order to use a regret bound from Theorem 4, we need only address the first two issues presented in the symmetric case:
-
(1)
Ensuring Small Width: We need to ensure that the width is small given any approximate matching response . Similar to the symmetric case, we show this is bounded by a constant.
-
(2)
Ensuring Large Loss: We now need to ensure that is large. A key difference present in the cut strategy for the asymmetric case is that ensuring large loss requires an additional step in rounding algorithm to control for terms in the loss that correspond to the embedding vector lengths.
To compute the matrix exponential update in nearly-linear time, we can reuse the sketch provided in Section 7.1.3.
7.2.1 Ensuring Small Width
Whe width in the asymmetric case is still bounded by an absolute constant given any directed approximate matching response. We prove the following Lemma in Appendix A.5
Lemma 15.
Suppose is an approximate matching response with respect to cut action . Then .
This lemma implies that the regret guarantee of Theorem 4 only for step-size when the losses are . We will subsequently choose an satisfying this.
7.2.2 Ensuring Large Loss
In the asymmetric case, we wish to produce a cut action such that no matter how the matching player plays , the edges of will be weighted such that the loss
is large. The critical distinction from the symmetric case is the presence of the embedding vector lengths.
This is where one might be inclined to require that valid matching responses be Eulerian directed graphs. If the matching response is Eulerian, then the graph can be split into two parts where the edges are all oriented from to , and from to . One can then cancel the embedding vector lengths in the loss using the fact that the in- and out-degrees are identical for each vertex. This reduces the problem of constructing a good cut strategy back to that present in the symmetric case: one need only round a cut such that a large amount of flow is always routed between vertex pairs whose embedding vectors are far in -distance.
Absent of this trick, one then needs to control the length of the embedding vectors. A priori this seems difficult. To ensure that an approximation algorithm based on cut-matching games runs in nearly-linear time, some low-dimensional projection needs to be applied to the embedding. One then cannot hope to simultaneously control for both the distortion of the projected embedding, and the length of the projected vectors, suggesting that the matching response must be an Eulerian graph. We remark that if one tries to directly adapt the potential analysis of [36] or [54], then the same terms in the loss appear in lower bounding the potential progress made when the matching player routes a large flow. This might suggest why current works generalizing the cut-matching game to directed settings [46, 40] require the matching player to play Eulerian graphs.
However, if one is cognizant of the underlying SDP being used to certify lower bounds on the directed conductance of the state graph, then it is natural to consider rounding algorithms which directly target the SDP. Indeed, applying the rounding algorithm present in [2] (Algorithm 4) augments a -separated cut into a cut action such that any matching response across must have large loss. We describe this rounding procedure in Algorithm 7.2.2 directed-round-cut.
Algorithm 2 directed-round-cut. Input: A cut of , and vector embedding . 1. Find such that and . 2. Define the following sets. 3. If , then let and . Else, let and . Output: the cut
The intuition for directed-round-cut is this: one does not need to route the flow bidirectionally across , and subsequently produce an Eulerian demand graph. The SDP solution, and specifically the position of the median embedding vector, should dictate which direction flow needs to be routed in a given round the cut-matching game. We now prove our lower bound on the loss
Lemma 16.
Let , , and be a vector embedding whose Gram matrix is . For , suppose directed-round-cut is given that are -separated with respect to and as input, and outputs . Then, any approximate directed matching response with respect to satisfies the following:
Proof.
We assume, without loss of generality, that directed-round-cut outputs such that and as the analysis for the case where and is identical.
In step (1) of directed-round-cut, is chosen to be the length of the median element in with respect to measure , we have . Furthermore, if and , then and hence . Consequently,
Using the fact that are -separated, we derive for all :
Because , we have and
Combining the above two calculations, we have the inequality
where we have used the fact that . Finally, because any approximate directed matching response is bipartite across , and the total weight is large, we conclude
as required. ∎
We also bound the running time of directed-round-cut.
Lemma 17.
directed-round-cut runs in time for .
Proof.
Computing the norm of a vector takes time , so all norm computations take time overall. The vectors then need to be sorted by norm value, which takes time . After that, completing the algorithm takes time. This yield the desired runtime. ∎
7.2.3 Completing the Analysis for Asymmetric Cut Functions
We are now ready to give our good cut strategy
Algorithm 3 . Input: vertex measure , and directed approximate matching responses . Parameters: step size . Do: The following. 1. Sample random unit vectors . 2. Denote , and compute given by using the truncated Taylor series via [9]. 3. Execute to produce the cut 4. Execute to produce the cut . Output: The cut .
Lemma 18.
Let be an input submodular hypergraph equipped with asymmetric polymatroidal cut functions such that . Then is -good with probability .
Proof.
We demonstrate that after rounds of the cut-matching game. Since the feedback matrices are not positive semidefinite, we use regret bound (6) from Theorem 4. Lemma 15 guarantees for every , thus
holding for every .
Next, consider the -th round, and let be the vector embedding whose Gram matrix is . Theorem 3 implies round-cut outputs -separated sets . Consequently, Lemma 16 implies that directed-round-cut produces a cut action such that satisfies
for some absolute constant . Consequently, the regret bound becomes
Let be a constant satisfying: . Choosing and , we have that:
This implies that every satisfies:
Now, choosing to be the minimizer to (dir-cond-sdp), and the optimal objective value for (dir-cond-sdp), we have
Finally, Lemma 14 implies the required
These guarantees can be shown to hold with super-constant probability by following the same argument as in Lemma 13. ∎
7.3 Completing the Cut Strategy: Proof of Theorem 12
For the sake of completion, let us now prove Theorem 12.
See 12
Proof.
Items (1) and (2) of statement are given by Lemmas 13, and 18 respectively. To bound the running time, notice that by the sketch in Section 7.1.3, the matrix multiplicative weight update can be computed in time bounded by . Meanwhile, the round-cut and directed-round-cut steps run in time as given by Theorem 3, and lemma 17. Since for both and , the total runtime is dominated by as required. ∎
8 Constructing Separated Sets: Proof of Theorem 3
This section is devoted to proving Theorem 3 on the construction of separated sets. We will show that the algorithm round-cut in Figure 4 satisfies the requirements of the theorem. We denote by the index set for the vector embedding in the theorem statement and define the following notions of expected vector and total variance of the embedding:
To simplify our proof, we will assume, without loss of generality, that our embedding is both centered, i.e., and normalized, i.e., Under these assumptions, we will make use of the following lemma, which relates the contribution to the total variance of a set to the that of its complement .
Lemma 19 (Fact 5.19 from [53]).
Let be a centered and normalized vector embedding. We have:
Our algorithm handles two cases, depending on whether there exist a set of small measure that contributes most of the variance of the embedding or not. To distinguish these two cases, we consider long vectors, i.e. vectors with large contributions to the variance of the embedding, and in particular we define the set of vertices with long vector embeddings:
We then say that an embedding is -balanced if the variance due to vertices in captures a -fraction of the total embedding variance, as per the following definition.
Definition 14 (-Balanced Embedding).
Given , and , a centered normalized vector embedding is -balanced if the set satisfies:
We distinguish the two cases based on whether the vector embedding is -balanced. We remark that, given and , one can check if the embedding is -balanced in time by computing distances to the average vector of . We start by describing the unbalanced case, which is where our main technical contribution lies.
Algorithm 4 round-cut. Input: A centered normalized vector embedding 1. If is -balanced: • Sample uniformly at random from and compute for each . • Sort . Assume without loss of generality that and define sweep cuts • Let and • Output . 2. If is not -balanced: • Sort the vectors by their length. Relabel vertices so that . • Let • Define sweep cuts For each sweep cut with : – if the following condition holds(see Equation 20 and Equation 21), output -separated sets
The unbalanced case
In the unbalanced case, the round-cut algorithm sorts the embedding vectors according to their length and outputs separated sets and from the set of threshold cuts in this ordering. In particular, the set is always chosen to equal , while the set is chosen by sweeping through all cuts in the ordering to find one that satisfies the required separation guarantee. We show that such a cut always exists. The following lemma, which is implicit in previous works [10, 2], follows from Markov’s Inequality and Lemma 19. We prove it for completeness in Appendix A.
Lemma 20.
Let be a centered normalized vector embedding that is not -balanced. Then:
Setting , it remains to that there exists some such that all pairs , satisfy
| (20) |
where For sake of contradiction, assume that no such exists. Then, for every there exists a pair such that the squared distance between and is less than At the same time, we can lower bound such squared distance as follows:
| (21) |
This yields, for all :
Integrating over where , we have:
At the same time, Lemma 20 lower bounds the right hand side:
which implies yielding the required contradiction.
On the right hand side, by the normalization assumption and the fact that , we have This completes the proof that a set with the required separation guarantee exists. To find such cut, the round-cut algorithm avoids computing the minimum distance between and for each threshold cut by noticing that the guarantee holds if we replace such minimum distance with the quantity , as we did in Equation 21.
The balanced case
In the balanced case, the set of short vectors captures a constant fraction of the vector embedding’s variance and a large fraction of the total volume via Markov’s inequality. One can subsequently expect that random projection coupled with a search for a balanced sweep cut will work as a bulk of the vectors will be well separated from one another. The balanced case analysis is thus very similar to the analysis of SDP-based approximation algorithms for balanced separator [53]. In fact, it is simpler as one does not need to bound the conductance of such a cut and so we leave the proof of the following lemma to Appendix A.6.
Lemma 21.
Given , let be a centered normalized vector embedding. If is a -balanced embedding, then algorithm round-cut outputs a pair of -separated sets with high probability. m
Running Time
To bound the running time, consider the following. Checking if the embedding is -balanced takes time. This can seen by noting that the inequality in Definition 14 can be rewritten as:
Computing -distances and vector projections takes time per vector, of which there are . Sorting takes time. There are at most sweep cuts to check in both the balanced and unbalanced case, and finding the appropriate cut in both cases takes time per cut. Checking the condition:
requires time per cut. Hence the overall running time is at most .
This completes the proof of Theorem 3.
9 Acknowledgements
AC is supported by NSF DGE 2140001. Part of this work was also done while AC was a visiting student at Bocconi University. LO is supported by NSF CAREER 1943510. The authors would like to thank anonymous reviewers for suggesting related work on polymatroidal networks, Thatchaphol Saranurak for suggesting related work on the use of cut-matching games beyond partitioning graphs, and Jeffrey Negrea for assisting on topics related to online learning. AC would like to thank Luca Trevisan for discussion regarding HDX construction, flow embedding techniques for certifying expansion of random regular graphs, and support while visiting Bocconi.
References
- [1] Dimitris Achlioptas. Database-friendly random projections. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 274–281, 2001.
- [2] Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. -approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 573–581, 2005.
- [3] Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In Proceedings of the 23rd international conference on machine learning, pages 17–24. Association for Computing Machinery, 2006.
- [4] Ravindra K Ahujia, Thomas L Magnanti, and James B Orlin. Network Flows: Theory, Algorithms and Applications. Prentice-Hall, 1993.
- [5] Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 237–245, 2015.
- [6] Konstantinos Ameranis, Antares Chen, Lorenzo Orecchia, and Erasmo Tani. Efficient flow-based approximation algorithms for submodular hypergraph partitioning via a generalized cut-matching game. arXiv preprint arXiv:2301.08920, 2023.
- [7] Reid Andersen and Kevin J. Lang. An algorithm for improving graph partitions. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, page 651–660, USA, 2008. Society for Industrial and Applied Mathematics.
- [8] Sanjeev Arora, Elad Hazan, and Satyen Kale. -Approximation to SPARSEST CUT in Time. SIAM Journal on Computing, 39(5):1748–1771, January 2010.
- [9] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 227–236, 2007.
- [10] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):1–37, 2009.
- [11] Francis Bach et al. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning, 6(2-3):145–373, 2013.
- [12] Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295):163–166, 2016.
- [13] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1000–1008. IEEE, 2022.
- [14] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. Cambridge University Press, 2020.
- [15] Umit V Catalyurek and Cevdet Aykanat. Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Transactions on parallel and distributed systems, 10(7):673–693, 1999.
- [16] T-H Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. Spectral properties of hypergraph laplacian and approximation algorithms. Journal of the ACM (JACM), 65(3):1–48, 2018.
- [17] Yuk Hei Chan and Lap Chi Lau. On linear and semidefinite programming relaxations for hypergraph matching. Mathematical programming, 135(1-2):123–148, 2012.
- [18] Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Directed metrics and directed graph partitioning problems. In SODA, volume 6, pages 51–60, 2006.
- [19] Chandra Chekuri, Sreeram Kannan, Adnan Raja, and Pramod Viswanath. Multicommodity flows and cuts in polymatroidal networks. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 399–408, 2012.
- [20] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623. IEEE, 2022.
- [21] Julia Chuzhoy. A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 2122–2213. Society for Industrial and Applied Mathematics, January 2023.
- [22] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1158–1167. IEEE, 2020.
- [23] Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 389–400, 2019.
- [24] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60–65, 2003.
- [25] Karen D Devine, Erik G Boman, Robert T Heaphy, Rob H Bisseling, and Umit V Catalyurek. Parallel hypergraph partitioning for scientific computing. In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, pages 10–pp. IEEE, 2006.
- [26] Alina Ene and Huy Nguyen. Random coordinate descent methods for minimizing decomposable submodular functions. In International Conference on Machine Learning, pages 787–795. PMLR, 2015.
- [27] Alina Ene, Huy Nguyen, and László A Végh. Decomposable submodular function minimization: discrete and continuous. Advances in neural information processing systems, 30, 2017.
- [28] Song Feng, Emily Heath, Brett Jefferson, Cliff Joslyn, Henry Kvinge, Hugh D Mitchell, Brenda Praggastis, Amie J Eisfeld, Amy C Sims, Larissa B Thackray, et al. Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC bioinformatics, 22(1):1–21, 2021.
- [29] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. In Conference on Learning Theory, pages 38–1. JMLR Workshop and Conference Proceedings, 2012.
- [30] Shohei Hidaka and Masafumi Oizumi. Fast and exact search for the partition with minimal information loss. PLoS One, 13(9):e0201126, 2018.
- [31] Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian. Positive semidefinite programming: mixed, parallel, and width-independent. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 789–802, 2020.
- [32] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pages 910–918. IEEE, 2020.
- [33] William Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Conference in Modern Analysis and Probability, 26:189–206, 01 1982.
- [34] Satyen Kale. Efficient algorithms using the multiplicative weights update method. Princeton University, 2007.
- [35] Rohit Khandekar, Subhash Khot, Lorenzo Orecchia, and Nisheeth K Vishnoi. On a cut-matching game for the sparsest cut problem. Univ. California, Berkeley, CA, USA, Tech. Rep. UCB/EECS-2007-177, 6(7):12, 2007.
- [36] Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. Journal of the ACM (JACM), 56(4):1–15, 2009.
- [37] Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. Hypergraphs and cellular networks. PLoS computational biology, 5(5):e1000385, 2009.
- [38] Tsz Chiu Kwok, Lap Chi Lau, and Kam Chuen Tung. Cheeger inequalities for vertex expansion and reweighted eigenvalues. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 366–377. IEEE, 2022.
- [39] Lap Chi Lau, Kam Chuen Tung, and Robert Wang. Cheeger inequalities for directed graphs and hypergraphs using reweighted eigenvalues. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1834–1847, 2023.
- [40] Lap Chi Lau, Kam Chuen Tung, and Robert Wang. Fast algorithms for directed graph partitioning using flows and reweighted eigenvalues. arXiv preprint arXiv:2306.09128, 2023.
- [41] Eugene L Lawler and Charles U Martel. Computing maximal “polymatroidal” network flows. Mathematics of Operations Research, 7(3):334–347, 1982.
- [42] Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787–832, 1999.
- [43] Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. Advances in neural information processing systems, 30, 2017.
- [44] Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-laplacians, cheeger inequalities and spectral clustering. In International Conference on Machine Learning, pages 3014–3023. PMLR, 2018.
- [45] Yaowei Long and Thatchaphol Saranurak. Near-optimal deterministic vertex-failure connectivity oracles. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1002–1010. IEEE, 2022.
- [46] Anand Louis. Cut-matching games on directed graphs. arXiv preprint arXiv:1010.1047, 2010.
- [47] Anand Louis. Hypergraph markov operators, eigenvalues and approximation algorithms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 713–722, 2015.
- [48] Anand Louis and Yury Makarychev. Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion. Theory of Computing, 12(1):1–25, 2016.
- [49] Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and -time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122–1129, 2017.
- [50] Mukund Narasimhan, Nebojsa Jojic, and Jeff A Bilmes. Q-clustering. Advances in Neural Information Processing Systems, 18, 2005.
- [51] Lorenzo Orecchia. Fast Approximation Algorithms for Graph Partitioning using Spectral and Semidefinite-Programming Techniques. PhD thesis, EECS Department, University of California, Berkeley, May 2011.
- [52] Lorenzo Orecchia, Konstantinos Ameranis, Charalampos Tsourakakis, and Kunal Talwar. Practical almost-linear-time approximation algorithms for hybrid and overlapping graph clustering. In International Conference on Machine Learning, pages 17071–17093. PMLR, 2022.
- [53] Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K Vishnoi. Approximating the exponential, the lanczos method and an -time spectral algorithm for balanced separator. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1141–1160, 2012.
- [54] Lorenzo Orecchia, Leonard J Schulman, Umesh V Vazirani, and Nisheeth K Vishnoi. On partitioning graphs via single commodity flows. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 461–470, 2008.
- [55] Jonah Sherman. Breaking the multicommodity flow barrier for -approximations to sparsest cut. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 363–372. IEEE, 2009.
- [56] Zoya Svitkina and Lisa Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal on Computing, 40(6):1715–1737, 2011.
- [57] Charalampos E Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. In Proceedings of the 26th International Conference on World Wide Web, pages 1451–1460, 2017.
- [58] Nate Veldt. Cut-matching games for generalized hypergraph ratio cuts. In Proceedings of the ACM Web Conference 2023, WWW ’23, page 694–704, New York, NY, USA, 2023. Association for Computing Machinery.
- [59] Nate Veldt, Austin R Benson, and Jon Kleinberg. Approximate decomposable submodular function minimization for cardinality-based components. Advances in Neural Information Processing Systems, 34:3744–3756, 2021.
- [60] Nate Veldt, Austin R Benson, and Jon Kleinberg. Hypergraph cuts with general splitting functions. SIAM Review, 64(3):650–685, 2022.
- [61] Wenyin Yang, Guojun Wang, Md Zakirul Alam Bhuiyan, and Kim-Kwang Raymond Choo. Hypergraph partitioning for social networks based on information entropy modularity. Journal of Network and Computer Applications, 86:59–71, 2017.
- [62] Yuichi Yoshida. Cheeger inequalities for submodular transformations. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2582–2601. SIAM, 2019.
Appendix A Omitted Proofs
In this section, we prove some technical lemmata used in the body of the paper.
A.1 Our Results
See 1
Proof of Lemma 1.
Observe that the denominator of the ratio-cut objective is a monotone submodular cut function applied over the entire vertex set
Consequently, for every :
which gives:
We now prove the opposite inequality by showing the second part of the lemma. Notice that the value of the ratio in the right-hand side of (RC-NonCvx) is invariant under shifting all the coordinates by a fixed constant. Furthermore, both the numerator and the denominator of the right-hand side of (RC-NonCvx) are homogeneous and hence their ratio is invariant under scaling by a constant, i.e., for any :
Hence, for any , by letting be defined as:
we have , , and:
We then have, as per Propositions 3.1 and 3.1 in [11]:
Hence, there must exist some such that:
This gives:
as needed for the first part of the lemma. Moreover, computing and checking all of the sets only requires time for sorting the entries of and time for evaluating the numerator and denominator. ∎
A.2 Polymatroidal Cut Functions and Hypergraph Flows
See 2
Proof.
Let and denote with and their complements in . We consider four possible cases, corresponding to four ways of determining and . In the first two cases, we exploit the submodularity of and .
- Case 1:
-
and , which implies and We have:
- Case 2:
-
and , which implies and We have:
In the last two cases, we rely on the monotonocity of and .
- Case 3:
-
and , which implies and . We have:
- Case 4:
-
and , which implies and . We have:
It follows that is submodular, as we have shown that for every :
∎
See 3
Proof.
Since and are monotone, for any there exists a value such that:
for all , and:
for all . We then have, by Proposition 3.1(c) in [11]:
as needed. ∎
See 4
Proof.
Since is submodular, its Lovász extension is convex, and hence, by Fact 3:
where in the above we applied Jensen’s Inequality and the fact that is positive homogenous (Proposition 3.1 (e) from [11]). On the other hand, since is monotone, we have:
where the inequality follow from Fact 1. This completes the proof. ∎
See 5
Proof.
Consider the hypergraph flows associated with the embedding and let be an arbitrary vector over the hyperedges. As each routes demand between the endpoints of , we have
where the last equality relies on the fact that Summing over all edges in yields:
The second inequality follows from Definition 9 and the characterization of Lovász extensions by the positive submodular polytope (see Proposition 3.4 in [11]). Finally, the first statement in the theorem follows by setting the arbitrary to be the required minimizer. The specialization to cuts follows by plugging in .
In the symmetric case, the capacity constraints in the definition become simply, for all :
As a result, the orientation of each arc can be discarded in this case, as the flow can be oriented arbitrarily while satisfying the capacity constraint. Therefore, we can repeat the same analysis for the flow embedding given by . Summing the positive and negative parts, we obtain the required statement. ∎
See 6
Proof Theorem 6.
Consider the hypergraph flow as a flow over the factor graph By a standard application of dynamic trees (see for example Lemma 3.8 in [55]) to the computation of flow-path decompositions [4] over , we can compute, in time , a graph such that and there exist hypergraph flows in with the following properties:
-
•
-
•
For any , for any factor graph edge , the flow has the same sign as . In particular, for all :
(22) -
•
For all , we have and The flow routes units of flow between vertex and vertex , i.e.,
The last point proves the required statements about the bipartiteness of and its degrees. To complete the proof, we verify that . By the definition of congestion in Equation 9, we have that, for all
By the characterization of the base polytope in Equation 4.2, this implies that:
Together with Equation 22 and Definition 9, this completes the proof. ∎
A.3 An -Approximation via -Metric Embeddings
See 2
Proof.
Given any cut with , for each , set the vector embedding of the vertices to
And for each hyperedge :
We then have:
It is easy to see that these vector embedding satisfies the triangle inequality constraints. For the variance constraint, we have:
Furthermore, this solution has objective value:
This shows that the combinatorial solution can be mapped to a feasible solution to the RC-Metric while preserving the objective to within a factor of two. ∎
See 4
Proof.
Let be a candidate solution to the minimum hypergraph ratio-cut problem satisfying , with objective value , i.e.:
We can construct a solution to the RC-Directed-Semimetric program with a objective value as follows. Partition into where:
We can consider:
and for any let and be defined in terms of and so as to satisfy the equality constraints in the RC-Directed-Semimetric program. One can check that:
It easy to see that all the triangle inequality constraints are satisfied. We can also verify that the variance constraint is satisfied:
Hence, the vectors defined above form a feasible solution to the RC-Directed-Semimetric program. The objective value of this solution is:
completing the proof. ∎
See 8
Proof.
Since the relaxation is invariant to translations, we will assume, without loss of generality, that:
| (23) |
and that:
| (24) |
We divide the proof in two cases corresponding to the case in which the embedding is balanced and unbalanced respectively. In Case 1, the embedding satisfies:
where:
In this case, it is implicit in the results of Arora Rao and Vazirani [10], that there exists polynomial-time computable sets satisfying , and:
| (25) |
We construct the map explicitly as follows. Let and be the sets satisfying (25). Let be a value such that:
and define:
and:
Suppose, without loss of generality, that 444If this condition does not hold, the rest of the argument still holds by exchanging the roles of with and with .. Note, in particular, that this implies that and . Let:
As a simple consequence of the triangle inequality constraints, we have, for any :
Let be the vector given by . Then:
Giving that:
Hence, the map satisfies conditions 1 and 2 in the statement of the lemma. Moreover, it is easy to see that this map can be computed in polynomial time. This completes the proof for Case 1.
For Case 2, we consider what happens when Case 1 doesn’t hold, i.e.:
Here, we have:
Where the first inequality follows by (23), (24) and Markov’s inequality. Let and . Consider the embedding:
Again, it is easy to see that the map satisfies condition 1 of the lemma. Moreover, note that, for any :
for some and hence:
Let be the vector given by . We then have:
Note that the bound obtained in this case is tighter, i.e. has been replaced by a constant. ∎
A.4 Localized Convex Formulations and Ratio-Cut Improvement
See 8
Proof of Lemma 8.
Let us proceed with taking the conjugate dual. Starting with (CI-Primal):
Recall that the Lovász extension is given by
and hence:
Strong duality always holds when the feasible region is polyhedron. Hence, we have:
which is equivalent to the required linear program by the definition of congestion (Equation 9) and demand (Equation 10)for hypergraph flows. ∎
See 9
Proof.
Let The sparsity of also follows directly from Theorem 6. By the same theorem, we have , as by Property 1 of approximate dual solutions. Hence, the scaled graph embeds into with congestion as required. Taking into account the same scaling by , the statements on the bipartiteness and degree bounds of follow directly from Property 2 and 3 of approximate dual solutions via Theorem 6. Similarly, the largeness of follows form Property 2. ∎
A.5 An -Approximation via Generalized Cut-Matching Games
See 1
See 2
Proof.
By Definition 12, each dual graph certificate played by the matching player has edges. Hence, has at most edges for all iterations It follows that the running time of the cut strategy at every round is bound by . On the matching side, the running time of the approximate primal-dual oracle is given by Theorem 9 and 10. Both dominate or are asymptotically equivalent to . ∎
See 15
Proof.
Fix any such that . We can write the quadratic form as
For the lower bound, note that
Using the fact that the degrees of in is bounded above by , we have
For the upper bound, note that
Let’s then exactract the dependence on the degree of each vertex.
Finally, using the fact that the degrees are bounded by , we have
thus establishing the required bound. ∎
See 20
Proof.
Because the embedding is normalized, the expect squared length of a vector is . Markov’s inequality then yields:
For the second part, by Lemma 19 and the definition of balanced embedding, we have that:
∎
A.6 Constructing Separated Sets: Proof of Theorem 3
We now complete the argument that round-cut outputs separated sets when the given vector embedding is balanced. We begin by recalling a fact about uniformly sampled vectors on the sphere.
Lemma 22.
Given , and a uniformly sampled random vector in , the following hold.
-
1.
-
2.
For any , we have .
We also require a lemma proved in [51] which states that, with constant probability, one can extract two balanced partitions where projection lengths are well separated when projecting along a random direction.
Lemma 23 (Lemma 5.5.6 item (3) of [51]).
Given a set such that , and a -balanced embedding , let for a and each . Assume, without loss of generality, that . Then, there exists an absolute constant such that, with probability over a uniformly random choice of , there exists satisfying the following:
-
1.
,
-
2.
,
-
3.
.
Using the above two lemmata, we can now prove that round-cut produces a robustly separated set in the balanced case.
See 21
Proof.
Define to be the event that there exist such that the following hold simultaneously: (1) , (2) , and (3) . Next, for a constant to be chosen subsequently, and any , define the event as
To begin, we observe that if and occur jointly, then the cuts and are -separated set and, consequently, round-cut outputs the required separated set in the balanced case. Event implies that
holds for all , and . Item (3) defining event then determines:
Finally, item (1) in event implies that and hence, for all :
which establishes the separation guarantee.
Let us next bound the probability that and occur jointly. By Lemma 23, there exists a constant such that and hence . By Lemma 22, we have
Performing a union bound over and for each derives
for large enough. We conclude that with constant probability, a single execution of step (1) in round-cut outputs -separated sets.
Note that upon computing candidate sets, it is possible to check whether these are in fact -separated. One can therefore boost the probability of success and obtain a high probability guarantee by repeating this procedure up to many times. Note that this clearly affects the runtime of this procedure by at most a logarithmic factor. ∎
Appendix B Comparison to the cut-Improvement of Andersen & Lang
In this section, we briefly show that our formulation of the ratio-cut improvement problem in Definition 10 generalizes the definition of the modified quotient cut score, introduced by Andersen and Lang [7], to potentially non-integral seed vectors (rather than cut seeds) and to arbitrary hypergraphs (rather than graphs). Consider the following seed vector. Let be a cut, and define the vector to be
| (26) |
Assuming , note that and , so that is a valid seed vector. With this choice of seed vector, the ratio-cut improvement objective on a graph gives:
which is exactly equal to the modified quotient cut score of cut as considered by Andersen and Lang.
Appendix C Proofs of Theorems 9 and 10
Suppose we have an algorithm that, on input either outputs a cut with a cut with or an approximate dual solution of value Then, can be used to construct an approximate primal-dual oracle by performing binary search on and converting the final approximate dual solution to an approximate dual graph certificate via the flow decomposition of Theorem 6. Since the range of possible values for is , which we assume is polynomial in it suffices to run for iterations. Hence, in the rest of the section, we focus on implementing for both cases in the theorems.
General Polymatroidal Cut Functions
For a fixed we consider the integral version of the feasibility problem for (CI-Primal):
The left-hand side of this equation can be minimized exactly by the proximal algorithms for decomposable submodular minimization (DSM) of Ene et al. [26, 27] when run with and rounded to integral solutions. If the resulting minimum is less than , the minimizer must have as required. Otherwhise, the DSM algorithm produces a matching dual solution, which takes exactly the form of a feasible solution to (CI-Dual) with value . Applying the best result of Ene et al. , achieved by the accelerated coordinated descent method under the assumption that a quadratic optimization oracle is given for each cut function the running time to implement an approximate primal-dual oracle becomes where is the running time for a quadratic optimization oracle for .
Graph-Reducible Polymatroidal Cut Functions
As we have shown in Section 4, for directed and standard hypergraph cut functions, the congestion constraint in the hyperflow problem CI-Dual corresponds to vertex capacities on the hyperedge nodes of the factor graph To implement the primitive described above for a fixed , we construct a network flow problem from this vertex-capacitated factor graph by adding an auxiliary source vertex and an auxiliary vertex . The vertex is connected to every vertex in with an arc of capacity , while the vertex is connected to every vertex with an arc of capacity It is easy to see that the capacity of a cut of in this new network is, for every :
| (27) |
Now, apply a -approximate maximum flow solver to this network flow problem to obtain a flow a value and an - cut of capacity We have two cases:
-
1.
If then the flow routed is an approximate dual solution of value , as required.
-
2.
If the - cut has capacity strictly less then As a result, we have by Equation 27:
This implies that are required for
The almost-linear time result follows by applying the almost-linear time algorithm of Chen et al. [20] as our approximate maximum flow solver. For the standard hypergraph cut function, as the edges in the factor graph are undirected, it suffices to use the almost-linear time solver of Bernstein et al. [13] for undirected vertex-capacitated graphs.
Appendix D Proof of Theorem 11: the cut-matching game reduction
See 11
Proof of Theorem 11.
First, we check that the dual graph certificates output by conform to the definition of an approximate matching response. Then, the bipartiteness of across follows from requirement 3 in Definition 12, while the degree and largeness properties follow from requirements 4 and 5 in the same definition. In the symmetric case, we may assume each is undirected.
In the following, let the value of achieved by the -invocation of and
By Lemma 6 and the definition of approximate primal-dual oracle and, we have that
By property 1 in Definition 12, we have that embeds in with congestion for all Averaging this guarantee over all , we have:
Applying Theorem 5 and the definition of good strategy, we obtain the following lower bound on cuts of , for all
In particular, this applies to the minimum-ratio cut in , so that we have:
This completes the proof. ∎