# Efficient Flow-based Approximation Algorithms
for Submodular Hypergraph Partitioning
via a Generalized Cut-Matching Game

Konstantinos Ameranis
<EMAIL_ADDRESS>
University of Chicago  Antares Chen
<EMAIL_ADDRESS>
University of Chicago  Lorenzo Orecchia
<EMAIL_ADDRESS>
University of Chicago  Erasmo Tani
<EMAIL_ADDRESS>
University of Chicago

###### Abstract

In the past 20 years, increasing complexity in real world data has lead to the
study of higher-order data models based on partitioning hypergraphs. However,
hypergraph partitioning admits multiple formulations as hyperedges can be cut
in multiple ways. Building upon a class of hypergraph partitioning problems
introduced by Li & Milenkovic [36], we study the problem of minimizing ratio-
cut objectives over hypergraphs given by a new class of cut functions,
_monotone submodular cut functions_ (mscfs), which captures hypergraph
expansion and conductance as special cases.

We first define the ratio-cut improvement problem, a family of local
relaxations of the minimum ratio-cut problem. This problem is a natural
extension of the Andersen & Lang cut improvement problem [5] to the hypergraph
setting. We demonstrate the existence of efficient algorithms for
approximately solving this problem. These algorithms run in almost-linear time
for the case of hypergraph expansion, and when the hypergraph rank is at most
$O(1)$.

Next, we provide an efficient $O(\log n)$-approximation algorithm for finding
the minimum ratio-cut of $G$. We generalize the cut-matching game framework of
Khandekar et al. [31] to allow for the cut player to play unbalanced cuts, and
matching player to route approximate single-commodity flows. Using this
framework, we bootstrap our algorithms for the ratio-cut improvement problem
to obtain approximation algorithms for minimum ratio-cut problem for all
mscfs. This also yields the first almost-linear time $O(\log n)$-approximation
algorithms for the case of hypergraph expansion, and constant hypergraph rank.

Finally, we extend a result of Louis & Makarychev [41] to a broader set of
objective functions by giving a polynomial time $O\big{(}\sqrt{\log
n}\big{)}$-approximation algorithm for the minimum ratio-cut problem based on
rounding $\ell_{2}^{2}$-metric embeddings.

##  1 Introduction

Consider an undirected graph
$G=(V,E,\mathbf{w}\in\mathbb{Z}^{E}_{>0},\bm{\mu}\in\mathbb{Z}^{V}_{\geq 0})$
with positive edge weights $\mathbf{w}$ and non-negative vertex weights
$\bm{\mu}$. For an edge $\\{i,j\\}\in E$ and a subset $S\subseteq V$, the edge
cut-function $\delta_{ij}:2^{\\{i,j\\}}\to\\{0,1\\}$ takes value $0$ if $i$
and $j$ are either both in $S$ or both in $\bar{S}$ and value $1$ otherwise,
i.e. $\delta_{ij}(S\cap\\{i,j\\})=\lvert{\bf 1}^{S}_{i}-{\bf
1}^{S}_{j}\rvert$. For $S\subseteq V,$ the graph cut function
$\delta_{G}:2^{V}\to\mathbb{Z}$ is then defined as
$\delta_{G}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sum_{e\in E}w_{e}\delta_{e}(S\cap e)$ and the ratio-cut objective
function $\Psi_{G}:2^{V}\to\mathbb{Q}$ is

$\Psi_{G}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\delta_{G}(S)}{\min\\{\bm{\mu}(S),\bm{\mu}(\bar{S})\\}}.$ (1)

The ratio-cut problem requires finding the cut $S\subseteq V$ minimizing
$\Psi_{G}(S)$. We denote its optimum value
$\Psi_{G}^{\star}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min_{S\subseteq V}\Psi_{G}(S)$. The minimum ratio-cut problem is
$\mathsf{NP}$-hard as it captures the classical $\mathsf{NP}$-hard problems of
minimizing graph expansion ($\bm{\mu}=\boldsymbol{1}$) and graph conductance
($\bm{\mu}$ equal to the weighted degree measure) as special cases [43].

Most algorithmic work in graph partitioning has thus focused on producing
efficient and accurate approximation algorithms. These typically fall into two
categories. The first category leverages the discrete Cheeger’s inequality [4,
52] relating the conductance of a graph to the spectrum of its Laplacian
matrix. In particular, if the graph conductance is $\phi$, and the second
eigenvalue of the normalized Laplacian is $\lambda_{2}$, then
$\frac{\lambda_{2}}{2}\leq\phi(G)\leq O(\sqrt{\lambda_{2}})$. Spectral-based
graph partitioning algorithms are known to be efficiently implementable,
running in nearly-linear time [53], and are heavily used across a number of
practical domains. However, spectral methods also suffer from poor
approximation guarantees, particularly in the case where $\phi$ is small as
using the discrete Cheeger inequality to approximate $\phi$ produces an
$O(\sqrt{\phi})$-approximation.

The second category of algorithms rely on solving metric relaxations of the
ratio-cut problem via convex programming and rounding the fractional solutions
back to cuts via metric embeddings. Leighton and Rao [34] obtain a polynomial
time $O(\log n)$-approximation by relaxing to general metrics and solving a
linear program. The current best known approximation of $O(\sqrt{\log n})$ is
due to Arora, Rao and Vazirani [7] using a positive semidefinite relaxation to
metrics of negative-type, i.e., $\ell_{2}^{2}$-metrics.

Despite enjoying excellent approximation guarantees and applying to all ratio-
cut problems, rather than just conductance, metric embedding methods did not a
priori find broad practical use because of the high computational complexity
of solving the metric relaxation problems, which originally required solving
maximum multicommodity flow problems with $\Omega(n^{2})$ demands over the
instance graph. This situation was significantly ameliorated by Khandekar et
al. [32], who introduced the cut-matching game framework to reduce the
approximate solution of metric relaxations of graph partitioning to a
polylogarithmic number of single-commodity maximum flow problems over the
instance graph. While Khandekar et al. only achieved a $O(\log^{2}n)$
approximation ratio, a subsequent series of papers based on the same framework
yielded a $O(\log n)$-approximation in polylogarithmic single-commodity
maxflow computations [49] and a $O\Big{(}\sqrt{\tfrac{\log
n}{\epsilon}}\Big{)}$-approximation111This relies on a more complex framework
than the original cut-matching game. in $O(n^{\epsilon})$ single-commodity
maxflow computations [51]. All these algorithms now run in time equal or close
to almost-linear, thanks to recent advances on the computation of exact
maximum flows [18].

The cut-matching game has itself become a fundamental primitive in the design
of graph algorithms [22, 20, 16, 17, 38] and, in particular, for deterministic
algorithms that are crucial in the dynamic setting [21]. However, a number of
unresolved issues with the current formulation of the cut-matching game have
hindered its wider deployment and application as an algorithmic design
framework. We highlight major ones here.

  * •

The standard cut-matching approach only applies to expansion ($\bm{\mu}=1$).
Saranurak and Wang [50] extend it to conductance by a direct reduction that
turns every edge into a vertex. However, no cut-matching game is known for
general vertex measures $\bm{\mu}$.

  * •

Currently, the reduction from the minimum ratio-cut problem to the cut-
matching game requires exact single-commodity flow computations over the
instance graph. While almost-linear-time algorithms for this task are now
available [19], it remains an interesting question, and a promising avenue
towards simpler and faster algorithms, to develop a version of the cut-
matching game for which approximate flow solvers suffice without compromising
the approximation guarantee by additional logarithmic factor, as is the case
in [22].

  * •

The cut-matching game only applies to edge-based graph partitioning problems.
To tackle vertex-based objectives [22] and mixed-vertex-edge objectives [46],
it is necessary to develop algorithms for the hypergraph partitioning problem
[36]. While hypergraph partitioning, both from the perspective of spectral
techniques [15] and metric relaxations [41], has been well studied, we
currently have no fast algorithms for these tasks, as existing results rely on
generic semidefinite solvers.

In this paper, we resolve the above issues. We propose a simple generalization
of the cut-matching game that supports approximate flow computation, while
still achieving a $O(\log n)$-approximation (Section 5). In the process, we
develop a novel perspective on the cut-matching game based on local convex
relaxations of the non-convex ratio-cut objective (Section 4). We also start a
methodical investigation of fast flow-based algorithms for general submodular
hypergraph ratio-cut problems and identify a natural class of hypergraph
models that is amenable to this approach (Section 3). As the rest of the paper
builds language and theory for constructing algorithms on general submodular
hypergraphs, we dedicate the next subsection towards introducing these
objects. We then discuss our contributions in detail in Section 1.2.

###  1.1 Submodular Cut Functions over Hypergraphs

A hypergraph is a tuple $G=(V,E),$ where $E\subseteq 2^{V}$ is a set of
hyperedges. The rank of a hyperedge $h\in E$ is its cardinality $|h|$. The
sparsity of a hypergraph $G$ is defined as $\mathsf{sp}(G)=\sum_{h\in E}\lvert
h\rvert$. Note that the input size required to specify a hypergraph is
$O\big{(}\lvert V\rvert+\mathsf{sp}(G)\big{)}$. If every $h\in E$ satisfies
$|h|=k$, the hypergraph $G$ is called $k$-uniform. In this way, an undirected
graph is simply a $2$-uniform hypergraph. A key step to formalize a hypergraph
cut problem is the definition of a suitable cut function
$\delta_{h}:2^{h}\to[0,1]$ of a hyperedge $h\in E$. Li and Milenkovic [35, 36]
propose the following general definition.

######  Definition 1 (Cut Function).

A function $\delta_{h}:2^{h}\to[0,1]$ is a cut function if it is symmetric
($\forall S\subseteq h,\delta_{h}(S)=\delta_{h}(\bar{S})$), it satisfies
$\delta_{h}(\varnothing)=\delta_{h}(h)=0$, and it achieves value $1$ ($\exists
T\subset h,\delta_{h}(T)=1$).

While the canonical edge-cut function $\delta_{ij}(S\cap\\{i,j\\})=\lvert{\bf
1}^{S}_{i}-{\bf 1}^{S}_{j}\rvert$ is the unique cut function respecting for
rank-$2$ hyperedges, higher-rank hyperedges support other choices of cut
functions. A natural additional requirement is that the cut functions be
submodular. This sufficiently restricts the intractability of the problem,
while preserving some of the crucial analytical and features of cut problems
over graphs, such as Cheeger’s inequality [37], connectivity-based
decompositions and flow-cut duality, which we strongly exploit in this work.

Indeed, all examples of cut functions in previous work on hypergraph
partitioning, both theoretical and applied as far as we are aware, fall in the
class of submodular cut functions:

  * •

Clique-expansion cut function [1, 57]: $\delta_{h}(S)=|S|\cdot|h\setminus
S|=\delta_{K_{h}}(S)$, where $K_{h}$ is the (2-uniform) complete graph over
hyperedge $h$. This version reduces to the standard graph version by replacing
each hyperedge $h$ with the complete graph $K_{h}$. The same reduction applies
when $\delta_{h}$ is the cut function of any 2-uniform graph over $h.$

  * •

Star-expansion cut function[1, 57]: $\delta_{h}(S)=\min\\{|S|,|h\setminus
S|\\}$. This version reduces to the standard graph version by adding an
auxiliary vertex for each hyperedge $h$, connected to each vertex $i\in h$ by
a unit weight edge.

  * •

Standard hypergraph cut function [14, 39]:
$\delta^{\mathsf{cut}}_{h}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{1,|S|,|h\setminus S|\\}$. Analogously to the graph case,
this function takes value $1$ if the hyperedge is cut and $0$ otherwise. This
is taken to be the standard notion of hypergraph partitioning in the existing
literature. It cannot be expressed as the cut function of any undirected
graph, even if partial minimization over auxiliary nodes is allowed.

In the following, we let a weighted submodular hypergraph $G$ be a weighted
hypergraph
$(V,E,\mathbf{w}\in\mathbb{Z}^{E}_{>0},\bm{\mu}\in\mathbb{Z}^{V}_{\geq 0})$
with positive edge weights $\mathbf{w}$ and non-negative vertex weights
$\bm{\mu},$ together with a choice of submodular cut functions
$\\{\delta_{h}\\}_{h\in E}$. In the special case when all cut functions are
standard, we refer to $G$ as a weighted standard hypergraph. The ratio-cut
objective on $G$ is defined analogously to Equation (1), i.e. for all
$S\subseteq V$:

$\Psi_{G}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\delta_{G}(S)}{\min\\{\mu(S),\mu(\bar{S})\\}}=\frac{\sum_{h\in
E}w_{h}\delta_{h}(S\cap h)}{\min\\{\mu(S),\mu(\bar{S})\\}}\,.$

Analogous to the graph case, we use the terms hypergraph expansion
($\bm{\mu}=\boldsymbol{1}$) and hypergraph conductance ($\forall i\in
V,\mu_{i}=\sum_{h\in E:i\in h}w_{h}$) to refer to specific choice of vertex
measures.

##### Previous Work

The standard hypergraph partitioning problem was first studied in the contexts
of parallel numerical algorithms [13] and scientific computing [23]. Louis and
Makarychev [41] provided the first randomized polynomial-time
$O\big{(}\sqrt{\log n}\big{)}$-approximation algorithm, matching the best
known approximation for the graph version of the problem [7] by using the same
relaxation to negative-type metrics. In more recent work, Louis [39] and Chan
et al. [14] developed a spectral approach to the conductance version of the
problem, achieving a Cheeger-like approximation guarantee: their algorithms
return a partition with ratio-cut at most
$O\big{(}\sqrt{\Psi^{\star}_{G}\log\max_{h\in E}|h|}\big{)},$ which is shown
to be tight under the small-set expansion conjecture. Their approach is based
on defining a variational quantity analogue to the spectral gap of a graph,
whose optimizer, just like the Fielder vector of the graph, can be rounded to
a cut of ratio-cut at most $O(\sqrt{\Psi_{G}^{\star}}).$ Unfortunately, in the
hypergraph case, such vector is itself $\mathsf{NP}$-hard to compute [42],
requiring a SDP relaxation which must provably lose a factor of
$\log\max_{h\in E}|h|$ under the Small-Set-Expansion Conjecture [39].

Much less is known about the approximability of hypergraph ratio-cut
objectives for general submodular cut functions. For submodular hypergraph
conductance, Li and Milenkovic [36] show that the same SDP approach yields
cuts with objective $O\big{(}\sqrt{\Psi^{\star}_{G}\cdot\max_{h\in
E}|h|}\big{)}$. They also conjecture that improving on such linear dependence
on hypergraph rank is $\mathsf{NP}$-hard. It is important to note that
algorithms for the above settings require solving SDP relaxations over
$|V|\times|V|$ symmetric matrices, with at least $|E|$ constraints. No faster
algorithms are currently known beyond generic SDP solvers [30], which run in
$\Omega\big{(}|V|^{2}|E|\big{)}$ 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
[29].

###  1.2 Our Contributions

##### Novel Hypergraph Partitioning Objectives

Our first contribution is to define monotone submodular cut functions, a
subclass of submodular cut functions given by the infimal symmetrizations of
non-decreasing submodular functions:

######  Definition 2 (Monotone Submodular Cut Function).

A cut function $\delta_{h}:2^{h}\to\mathbb{R}_{\geq 0}$ is mscf if, for all
$S\subseteq h$, it can be expressed as

$\delta_{h}(S)=\min\big{\\{}F_{h}(S),F_{h}(h\setminus S)\big{\\}},$

where $F_{h}:2^{h}\rightarrow\mathbb{R}$ is a non-decreasing submodular
function such that $F_{h}(\varnothing)=0$.

It is clear that both the star-expansion cut function ($F_{h}(S)=|S|$) and the
standard hypergraph cut function ($F_{h}(S)=\min\\{1,|S|\\}$) are monotone
submodular cut functions. However, this class extends beyond these two
examples. We highlight two additional examples that are relevant in
applications:

  * •

$F_{h}$ is a cardinality-based non-decreasing submodular function [56], 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 $h,$ e.g., by taking
$\delta_{h}(S)=\min\big{\\{}|S|^{p},|h\setminus S|^{p}\big{\\}}$ for
$p\in(0,1).$

  * •

$F_{h}$ is the entropy of a subset of random variables associated with
vertices of $h$. When the hypergraph $G$ is the factor graph of an undirected
graphical model, this yields a variant of the minimum information partition
[27, 44].

We refer to weighted submodular hypergraphs with mscf cut functions as mscf-
hypergraphs. Section 3 establishes the fundamental properties of mscfs. The
following primal-dual properties are critical to our subsequent results:

  1. 1.

Primal property [Theorem 5 in Section 3]: the Lovász extension of a mscf can
be approximated within a constant by an absolute norm222A norm $\|\cdot\|$
over $\mathbb{R}^{n}$ is absolute if, for all $\mathbf{x}\in\mathbb{R}^{n}$ we
have $\|\mathbf{x}\|=\||\mathbf{x}|\|$. See Definition 3 and related
discussion in Section 2. over $\mathbb{R}^{h}\perp{\bf 1}$. The main use of
this property will be in rounding $\ell_{2}^{2}$-metric relaxations for ratio-
cut problems over mscf-hypergraphs in Section 6.

  2. 2.

Dual property [Theorems 6 and 7 in Section 3.1]: dual vectors in the base
polytopes of mscfs can be extrapolated to construct flow embeddings of graphs
into hypergraphs. The main use of this property will be in Section 5, where we
establish the proving the viability of the cut-matching approach for
constructing approximation algorithms for ratio-cut problems over mscf-
hypergraphs.

These properties allow us to leverage metric and flow arguments to obtain
$\operatorname{polylog}(|V|)$-approximation algorithms for ratio-cut problems
over mscf-hypergraphs. To the best of our knowledge, this paper is the first
to draw attention to this class of symmetrized submodular functions. The most
common notion of symmetrization in submodular optimization is the standard
additive symmetrization
($F_{\textrm{sym}}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}F(S)+F(\bar{S})-F(h)$ for every $S\subseteq h$) [9]. However, the
fundamental primal-dual properties above fail for such symmetrization.

##### Local Relaxations and Cut Improvement

Our next contribution is a new perspective on the cut-matching game. We
interpret the cut-matching game as a generic approach for minimizing a (non-
convex) ratio of submodular functions [10] via a sequence of local convex
relaxations. We introduce the _ratio-cut improvement_ objective, a local
convex objective parametrized by a seed $\mathbf{s}$ satisfying $\sum_{i\in
V}\mu_{i}\mathbf{s}_{i}=0$ and $\|\mathbf{s}\|_{\infty}\leq 1$:

$\Psi_{G,\mathbf{s}}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\delta_{G}(S)}{\big{\lvert}\sum_{i\in
S}\mu_{i}s_{i}\big{\rvert}},$

This problem can be thought of as attempting to find a cut $(S,\overline{S})$
that simultaneously has both a small boundary, and high correlation with the
input seed $\mathbf{s}$ simultaneously. Indeed, Appendix B.1 demonstrates that
the problem of minimizing $\Psi_{G,\mathbf{s}}$ is precisely the
generalization of the cut-improvement problem of Andersen and Lang [5] to
weighted submodular hypergraphs and fractional seeds.

We give algorithms that minimize this objective under different assumptions
(see Theorem 8 and Table 8). If $G$ has constant rank, or $\delta_{G}$ is the
sum of standard hypergraph cut functions, the algorithm outputs an
$\epsilon$-approximate primal-dual solution to the ratio-cut improvement
problem in time that is almost-linear with respect to the input size of $G$
(Section 4.3). Furthermore, these results do not require the cut functions to
be monotone, and apply to all weighted submodular hypergraphs.

Efficient algorithms for the hypergraph ratio-cut improvement problem are of
particular interest as they allow us to locally probe the cut space of the
instance hypergraph $G$ and find sparse cuts near the input seed $\mathbf{s}$.
Concurrently, these algorithms, via a dual solution, provide local lower
bounds on the cut function $\delta_{G}$. Crucially, by the dual property of
mscf cut functions, such lower bounds yield flow embeddings of a (2-uniform)
demand graph $D$ into the hypergraph $G$, so that
$\delta_{D}(S)\leq\delta_{G}(S)$ for all $S\subseteq V$. Consequently, if one
wishes to boost the local ratio-cut improvement procedure to produce a global
approximation for the global ratio-cut problem, then one need only find an
adaptive sequence of $T$ cut-improvement problems such that the cut function
of the sum $\sum_{t=1}^{T}D_{t}$ of local demand graphs yields a global lower
bound on $\delta_{G}$. This is precisely the problem solved by the cut-
matching framework of Khandekar et al. [32]

##### Generalized Cut-Matching Game

The classical cut-matching game of Khandekar et al. [31] is a two-player game
between a cut player $\mathcal{C}$ and a matching player $\mathcal{M}$. At
every iteration, $\mathcal{C}$ outputs a balanced bipartition, and
$\mathcal{M}$ outputs a matching across the bipartition. The goal of the cut
player is to construct an expander, in as few rounds as possible, using only
matchings returned by $\mathcal{M}$. This cut-matching game was originally
intended to guarantee lower bounds to graph expansion. Consequently, the
intended matching player $\mathcal{M}$ can be cast as an exact solution to the
ratio-cut improvement problem for vertex weighting $\bm{\mu}={\bf 1}$, and
seed vector $\mathbf{s}={\bf 1}_{S}-{\bf 1}_{\bar{S}}$ for $S$ the cut played
by $\mathcal{C}$.

A main contribution of our work is to define a generalized cut-matching game
where the matching strategy can be replaced with an approximate solver for the
ratio-cut improvement problem. Even in the restricted case where $\bm{\mu}=1$,
replacing an exact solver with an approximate solver presents insurmountable
issues: an $\epsilon$-approximate solver can be modeled as a matching player
that is allowed to drop an $\epsilon$-fraction of matching edges (see
Definition 10 in Section 5 for more details). Subsequently, the matching
player could select a set $T$ with $|T|=\Theta(\epsilon n)$ and always drop
matching edges adjacent to $T$. Even if the cut player can quickly identify
such set $T$, it would have no action that can add edges to it, as it is
restricted to play bisections.

For this reason, for approximate matching players, we define in Section 5 a
generalized cut-matching game that allows the cut player to play unbalanced
cuts. Widening the set of cut actions also solves another immediate difficulty
in generalizing the cut-matching game from expansion ($\bm{\mu}={\bf 1}$) to
generic ratio-cut objectives: the fact that no $\bm{\mu}$-bisection of $V$ may
exist when considering $\bm{\mu}$-conductance. We demonstrate how to use our
generalized cut-matching game to approximate arbitrary ratio-cut objectives.

######  Theorem 1 (Informal).

Let $V=[n]$. There exists an algorithm approx-rc which, on input of a mscf-
hypergraph $G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$, and ratio cut-
improvement error parameter $\epsilon>0$, outputs a $O\big{(}\frac{\log
n}{1-\epsilon}\big{)}$-approximation to the minimum ratio-cut. Furthermore
approx-rc requires at most $O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}$ calls
to an $\epsilon$-approximate solver333See Section 4 for an exact definition.
for the ratio-cut improvement problem.

This theorem is given in Section 5 where the exact form of the statement is
captured via Theorem 9, then proven in Corollary 1.

To the best of our knowledge, this is the first formal generalization of the
cut-matching game to ratio-cut objectives beyond expansion. Previous work [50]
had generalized the cut-matching game to conductance via a sophisticated,
recursive combinatorial reduction. Our approach shows how to generalize the
original analytical argument of Orecchia et al. [49].

Restricting to the case of the standard hypergraph cut function, and constant
rank mscfs, we also note that this theorem yields an $O(\log n)$ approximation
algorithm whose running time is dominated by a polylogarithmic number of
$s$-$t$ approximate maximum flow computations. Leveraging [12] produces the
first almost-linear time algorithm for the minimum ratio-cut problem. If we
wish to only route exact $s$-$t$ maximum flows, then recent advances due to
[19] still recovers an almost-linear time algorithm. In general, the
generalized cut-matching game provides a fast approximation algorithm for
minimum ratio-cut provided a fast approximate ratio-cut improvement algorithm
exists.

Our description of the generalized cut-matching game abstracts what is
required from the cut player to yield an approximation algorithm. In section
5, we define a so-called $\big{(}f(n),g(n,\epsilon)\big{)}$_-good cut
strategy_ , and prove

######  Theorem 2.

Given a $\big{(}f(n),g(n,\epsilon)\big{)}$_-good cut strategy_ , there exists
an algorithm which, on input of a mscf-hypergraph $G$, and $\epsilon>0$,
outputs an $O\Big{(}\frac{g(n,\epsilon)}{f(n)}\Big{)}$-approximate minimum
ratio-cut to $G$.

restated in Theorem 9. Theorem 1, in fact, follows from then demonstrating the
following result.

######  Theorem 3.

There exists a randomized cut strategy $\mathcal{C}$ where, for any
$\epsilon\geq 0$, $\mathcal{C}$ is $\Big{(}\Omega(\log
n),O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}\Big{)}$-good with probability
$1-o_{n}(1)$. Furthermore, $\mathcal{C}$ outputs a cut in time that is nearly-
linear in $n$.

which is restated in Theorem 10. The proof of this Theorem extracts a robust
separation property that allows for the matching strategy to play approximate
primal-dual solutions to the ratio-cut improvement problem.

##### Metric Embedding Relaxations for mscf cut functions

In Section 6, we investigate the polynomial-time approximability of ratio-cut
problems over submodular hypergraphs with mscf cut functions. We leverage the
primal property of mscfs to prove the following theorem.

######  Theorem 4.

There exists a randomized polynomial-time $O\big{(}\sqrt{\log
n}\big{)}$-approximation algorithm for solving the minimum ratio-cut problem
on weighted submodular hypergraphs equipped with monotone submodular cut
functions.

This result is restated in Theorem 13 and proved in Section 6. It extends the
$O\big{(}\sqrt{\log n}\big{)}$-approximation of Louis and Makarychev [41] for
standard hypergraph sparsest cut to all ratio-cut problems for the more
general class of monotone submodular cut functions.

Our algorithm for Theorem 4 solves an $\ell_{2}^{2}$-metric relaxation of the
ratio-cut problem for weighted submodular hypergraphs, given by the program
RC-Metric. This relaxation crucially exploits the geometric connection between
a monotone submodular cut function $\delta_{h}$ and the norm induced by the
associated non-decreasing submodular function $F_{h}.$ We note that our
techniques can be applied in a straightforward manner to the sparsest cut
problem with general demands to yield rank-independent $O(\sqrt{\log
k})$-approximation ratios, where $k$ is the number of demands. This improves
on previous work by Louis [40], which achieves a
$O\Big{(}\sqrt{\log(k)\cdot\log\big{(}\max_{h\in
E}|h|\big{)}}\Big{)}$-approximation also via an $\ell^{2}_{2}$-metric
relaxation, by removing the dependence on the hypergraph rank.

###  1.3 Additional Remarks and Open Problems

Introducing mscf helps provide a finer-grained picture of submodular cut
functions by highlighting a meaningful subclass where it is possible to obtain
approximations in time, and quality, independent of hypergraph rank. It would
be interesting to understand whether such approximations exist for cut
functions whose Lovász extensions are not closely approximated by an absolute
norm. The results in this paper are not immediately generalizable as the flow-
decomposition statement strongly depends on this property.

The rounding analysis for our metric relaxation also relies on the
monotonicity of absolute norms, but it is uncertain if this is necessary for
producing roundable $\ell_{2}^{2}$-metric relaxations for ratio-cut problems
over hypergraphs in general. Is there a natural, larger, class of submodular
hypergraph cut functions for which rounding negative-type metric relaxations
produce good approximation algorithms?

It would be interesting to see if techniques developed in this paper can help
in formalizing, and extending recent flow-based algorithms for local graph
partitioning [55, 28] to the setting of submodular hypergraphs.

Finally, implementations of the cut-matching game [47, 33], and decomposable
submodular minimization [24] are readily available. Consequently, the
algorithmic framework presented here may be deployable in practice. How
effective is this framework when applied to real world test loads?

In general, we hope that this work assists in pursuing a more methodical
investigation, both theoretical and practical, of hypergraph partitioning and
the rich landscape of submodular cut functions.

##  2 Preliminaries

##### Linear Algebra

Throughout this paper, we adopt the convention of representing scalars $x$ in
unbolded lowercase, vectors $\mathbf{x}$ in boldface lowercase, and matrices
$\mathbf{X}$ as boldface uppercase.

Given vectors $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$, we use
$\mathbf{x}\circ\mathbf{y}$ to denote the Hadamard (entry-wise) product
between $\mathbf{x}$ and $\mathbf{y}$. We also use $\lvert\mathbf{x}\rvert$ to
denote the vector whose entries are the absolute value of the entries in
$\mathbf{x}$. We let $\langle\mathbf{x},\mathbf{y}\rangle$ denote the standard
Euclidean inner product, $\lVert\cdot\rVert$ the Euclidean norm, and
$\lVert\cdot\rVert_{p}$ the $\ell_{p}$-norm. We define an inner product
between $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ weighted by a non-negative
vector $\bm{\mu}\in\mathbb{R}^{n}_{\geq 0}$ as follows:

$\langle\mathbf{x},\mathbf{y}\rangle_{\bm{\mu}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sum_{i=1}^{n}\mu_{i}\cdot x_{i}\cdot y_{i}\,.$

The quantity
$\lVert\mathbf{x}\rVert_{\bm{\mu}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sqrt{\langle\mathbf{x},\mathbf{x}\rangle_{\bm{\mu}}}$ denotes the
norm induced by the inner product $\langle\cdot,\cdot\rangle_{\bm{\mu}}$,
while for any $p>0$, we use $\lVert\mathbf{x}\rVert_{\bm{\mu},p}$ to denote
the $\ell_{p}$-norm weighted by $\bm{\mu}$

$\lVert\mathbf{x}\rVert_{\bm{\mu},p}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\left(\sum_{i=1}^{n}\mu_{i}\cdot\lvert
x_{i}\rvert^{p}\right)^{1/p}\,.$

Note consequently that
$\lVert\mathbf{x}\rVert_{\bm{\mu}}=\lVert\mathbf{x}\rVert_{\bm{\mu},2}$. Given
a vector $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$, we write
$\mathbf{x}\perp\mathbf{y}$ to indicate the relation:
$\langle\mathbf{x},\mathbf{y}\rangle=0$. We also define the following notation
for the orthogonal complement (in $\mathbb{R}^{V}$) of the span of the all-one
vector:
$\boldsymbol{1}^{\perp}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\operatorname{span}\\{\boldsymbol{1}\\}^{\perp}$.

If $\mathbf{X},\mathbf{Y}\in\mathbb{R}^{n\times n}$, then
$\langle\mathbf{X},\mathbf{Y}\rangle=\sum_{i,j=1}^{n}X_{ij}Y_{ij}$ denotes the
Frobenius inner product. We denote by $\mathbf{X}\succeq 0$ the statement that
$\mathbf{X}$ is positive semidefinite, and by $\mathbf{X}\preceq\mathbf{Y}$
the relation $0\preceq\mathbf{Y}-\mathbf{X}$. We use
$\operatorname{diag}(\mathbf{x})\in\mathbb{R}^{n\times n}$ to denote the real
matrix with the coordinates of $\mathbf{x}$ placed along its diagonal. We
reserve specifically the matrix
$\mathbf{M}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\operatorname{diag}(\bm{\mu})$ for the non-negative vector
$\bm{\mu}\in\mathbb{R}^{n}_{\geq 0}$. We assume that $\min_{i\in
V}\big{\\{}\frac{\mu_{i}}{\bm{\mu}(V)}\big{\\}}\geq\frac{1}{\mathsf{poly}(n)}$.

Given a finite set $V$, a vector $\mathbf{x}\in\mathbb{R}^{V}$, and a subset
$S\subseteq V$, we let $\mathbf{x}(S)=\sum_{v\in S}x_{v}$. We also denote by
$\mathbf{x}^{S}\in\mathbb{R}^{V}$, the restriction of $\mathbf{x}$ to
coordinates in $S$:

$\mathbf{x}^{S}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sum_{i\in S}x_{i}\mathbf{e}_{i}$

where $\mathbf{e}_{i}$ is the $i$-th standard unit vector. In this way, the
vector $\boldsymbol{1}^{S}$ denotes the $\\{0,1\\}$-indicator of set $S$.

##### Absolute and Monotonic Norms

We often refer to the following properties for norms over $\mathbb{R}^{V}$.

######  Definition 3.

A norm $\|\cdot\|$ over $\mathbb{R}^{V}$ is absolute  if
$\|\mathbf{x}\|=\|\lvert\mathbf{x}\rvert\|$ for all
$\mathbf{x}\in\mathbb{R}^{V}$ .

######  Definition 4.

A norm $\|\cdot\|$ over $\mathbb{R}^{V}$ is monotonic  if, for all
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{V}$,
$\lvert\mathbf{x}\rvert\leq\lvert\mathbf{y}\rvert$ implies
$\|\mathbf{x}\|\leq\|\mathbf{y}\|$.

We also use the following basic facts about absolute and monotonic norms.

######  Fact 1.

If a norm $\|\cdot\|$ over $\mathbb{R}^{V}$ is absolute, then it is monotonic.

######  Fact 2.

The dual norm $\|\cdot\|_{*}$ of an absolute norm $\|\cdot\|$ over
$\mathbb{R}^{V}$ is also absolute.

######  Fact 3.

The following stronger form of Hölder’s Inequality holds for absolute norms:

$\langle|\mathbf{x}|,|\mathbf{y}|\rangle\leq\|\mathbf{x}\|_{*}\cdot\|\mathbf{y}\|$

Proofs of these facts can be found in [11]. We remark that absoluteness and
monotonicity are not true for general norms, as can be seen by considering the
norm induced by an ellipsoid whose axis are not coordinate-parallel.

##### Submodular Functions

A set function $F:2^{V}\rightarrow\mathbb{R}$ is submodular if for all
$A,B\subseteq V$, we have:

$F(A\cup B)\leq F(A)+F(B)-F(A\cap B).$

From the above, one can see that the set of submodular functions is closed
under taking conic combinations. Following standard conventions, we always
assume that $F(\varnothing)=0$ unless specified otherwise.

Any submodular set function $F$ can be associated with a convex body
$\mathcal{B}(F)$, known as its base polytope, which is defined as follows:

$\mathcal{B}(F)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\big{\\{}\mathbf{x}\in\mathbb{R}^{V}\,:\,\langle\mathbf{x},\boldsymbol{1}\rangle=F(V)\,\wedge\,\langle\mathbf{x},\boldsymbol{1}_{S}\rangle\leq
F(S)\quad\forall S\subseteq V\big{\\}}.$

Crucially, a submodular set function $F$ can be extended to its convex
closure, known as its Lovász extension and denoted by
$\bar{F}:\mathbb{R}^{V}\rightarrow\mathbb{R}.$ There are a number of
equivalent characterizations of the Lovász extension (Propositions 3.1 and 3.2
in [9]).

######  Fact 4.

For any submodular function $F:2^{V}\rightarrow\mathbb{R}$ such that
$F(\varnothing)=0$, $\bar{F}:\mathbb{R}^{V}\rightarrow\mathbb{R}$ satisfies
the following.

  1. 1.

$\bar{F}$ is the conjugate dual function of the indicator of $\mathcal{B}(F)$,
i.e.,

$\bar{F}(\mathbf{x})=\max_{\mathbf{y}\in\mathcal{B}(F)}\langle\mathbf{x},\mathbf{y}\rangle.$

  2. 2.

Given a vector $\mathbf{x}\in[0,1]^{V}$, let $S_{t}(\mathbf{x})=\\{i\in
V:x_{i}\geq t\\}$. Then

$\bar{F}(\mathbf{x})=\operatorname*{\mathbb{E}}_{t}\big{[}F\big{(}S_{t}(\mathbf{x})\big{)}\big{]},$

where $t$ is sampled uniformly from $[0,1]$.

  3. 3.

Given $\mathbf{x}\in\mathbb{R}^{V}$, order the coordinates of $\mathbf{x}$ by
$x_{1}\geq\ldots\geq x_{n}$ and define $S_{i}=[i]$. Then

$\bar{F}(\mathbf{x})=\sum_{i=1}^{n}\big{(}x_{i}-x_{i+1}\big{)}\cdot
F(S_{i})=\sum_{i=1}^{n}x_{i}\cdot\big{(}F(S_{i})-F(S_{i-1})\big{)}.$

From these facts, one can also see that the Lovász extension of a conic
combination of submodular functions is the same conic combination of the
Lovász extensions of those functions. That is, given $F=\sum_{i\in
I}a_{i}F_{i}$ for some index set $I$, where each $F_{i}$ is submodular and
$a_{i}\in\mathbb{R}_{>0}$, we have:

$\bar{F}=\sum_{i\in I}a_{i}\bar{F}_{i}.$

As we will be dealing with cut functions that are symmetric, we make use of
the following fact.

######  Fact 5.

For any submodular symmetric function $F:2^{V}\to\mathbb{R}$ such that
$F(\varnothing)=0$, the Lovász extension $\bar{F}$ is an even function, i.e.,
$\forall\mathbf{x}\in\mathbb{R}^{V},\;\bar{F}(x)=\bar{F}(-x).$

##### Monotone Submodular Functions and Associated Norms

A submodular function is (monotone) non-decreasing if $F(S)\geq F(T)$ for all
$T\subseteq S$. From Fact 4, one can see that the Lovász extension $\bar{F}$
of such a function in also non-decreasing. We often work with a submodular
non-decreasing function by considering the following associated norm. Any non-
decreasing submodular function $F:2^{V}\rightarrow\mathbb{R}$, with
$F(\emptyset)=0$ and $F(\\{i\\})>0$ for all singleton sets $i,$ gives rise to
the norm $\|\cdot\|_{F}$ on $\mathbb{R}^{V}$ (see Propositions 3.5 and 5.2 in
[9]):

$\|\mathbf{x}\|_{F}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\bar{F}(\lvert\mathbf{x}\rvert)$

The unit ball of the dual norm to $\|\cdot\|_{F}$ defines a polyhedron known
as the symmetric submodular polyhedron of $F$ and denoted
$\mathcal{P}_{\mathsf{sym}}(F)$, so that we can write:

$\lVert\mathbf{x}\rVert_{F}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\max_{\mathbf{y}\in\mathcal{P}_{\mathsf{sym}}(F)}\langle\mathbf{y},\mathbf{x}\rangle\qquad\textrm{
and
}\qquad\forall\mathbf{y}\in\mathbb{R}^{V},\;\|\mathbf{y}\|_{*,F}=\min\\{\lambda\geq
0:\lambda\mathbf{y}\in\mathcal{P}_{\mathsf{sym}}(F)\\}.$

Like the base polytope, the symmetric submodular polyhedron admits an
alternative characterization (Proposition 3.5 in [9]):

$\mathcal{P}_{\mathsf{sym}}(F)=\bigg{\\{}\mathbf{x}\in\mathbb{R}^{V}\,:\,\sum_{i\in
S}\lvert x_{i}\rvert\leq F(S)\quad\forall S\subseteq V\bigg{\\}}\,.$

The following fact is crucial in establishing our main theorems. It is an
immediate consequence of the definition of $\|\cdot\|_{F}$ and of Facts 1 and
2.

######  Fact 6.

The norms $\|\cdot\|_{F}$ and $\|\cdot\|_{*,F}$ are both absolute and
monotonic.

##### Graphs

We represent a weighted graph with a measure placed on its vertices as the
tuple $G=\big{(}V,E_{G},\mathbf{w}_{G},\bm{\mu}\big{)}$. Here,
$\mathbf{w}_{G}\in\mathbb{R}^{E_{G}}_{\geq 0}$ is a vector of edge weights,
and $\bm{\mu}\in\mathbb{Z}^{V}_{\geq 0}$ is a vector of vertex weights. We may
omit the subscript $G$ whenever the graph in reference is clear from context.

Given a graph $G$, we use $\mathbf{L}(G)$ to denote its combinatorial
Laplacian:

$\mathbf{L}(G)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\mathbf{D}(G)-\mathbf{A}(G),$

where the $\mathbf{D}(G)$ is the diagonal matrix of the weighted degrees of
the vertices, and $\mathbf{A}(G)$ is the graph adjacency matrix. We denote
$\mathcal{L}_{\mu}(G)$ as its Laplacian matrix normalized by the vertex
measure $\bm{\mu}$:

$\mathcal{L}_{\mu}(G)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\mathbf{M}^{-1/2}\,\mathbf{L}(G)\,\mathbf{M}^{-1/2},$

where $\mathbf{M}=\operatorname{diag}(\bm{\mu})$. Observe that, if $G$ is
$\bm{\mu}$-regular, meaning $\sum_{j:ij\in E_{G}}w_{ij}=\bm{\mu}_{i}$ for
every $i\in V$, then $\mathbf{0}\preceq\mathcal{L}_{\bm{\mu}}(G)\preceq
2\mathbf{I}_{n}$. We call a cut $S\subseteq V$ a $\bm{\mu}$-bisection if
$\mu(S)=\mu(\bar{S})$.

##### Hypergraph Flows

Given a weighted submodular hypergraph
$G=(V,E,\mathbf{w}\in\mathbb{Z}^{E}_{>0},\bm{\mu}\in\mathbb{Z}^{V}_{\geq 0})$,
a hyperedge flow over a hyperedge $h\in E$ is a vector
$\mathbf{y}_{h}\in\mathbb{R}^{h}\perp{\bf 1}_{h}.$ A hypergraph flow
$\mathbf{Y}\in\bigoplus\mathbb{R}^{h}\perp{\bf 1}_{h}$ is a direct sum of
hyperedge flows $\mathbf{Y}=(\mathbf{y}_{h})_{h\in E}.$ The demand vector
$\operatorname{dem}(\mathbf{Y})\in\mathbb{R}^{V}\perp{\bf 1}$ of a hypergraph
flow $\mathbf{Y}=(\mathbf{y}_{h})_{h\in E}$ is defined as:

$\operatorname{dem}_{i}(\mathbf{Y})=\sum_{h\in E:h\ni i}(\mathbf{y}_{h})_{i}$

We use the vector space structure inherited from
$\mathbf{Y}\in\bigoplus\mathbb{R}^{h}\perp{\bf 1}_{h}$ to define linear
combinations of hypergraph flows $c\mathbf{Y}_{1}+\mathbf{Y}_{2}$ for any
$c\in\mathbb{R}.$ The demand vector also behaves linearly as
$\operatorname{dem}(c\mathbf{Y}_{1}+\mathbf{Y}_{2})=c\cdot\operatorname{dem}(\mathbf{Y}_{1})+\operatorname{dem}(\mathbf{Y}_{2}).$

Finally, notice that hypergraph flows over hyperedges of rank $2$ are
equivalent to graph flows as, for an edge $\\{i,j\\}\in E$,
$(\mathbf{y}_{ij})_{i}$ represents the flow from $i$ to $j$, while
$(\mathbf{y}_{ij})_{j}=-(\mathbf{y}_{ij})_{j}$ is the flow from $j$ to $i$.

##### Factor Graphs

A hypergraph $G=(V,E_{G},\mathbf{w},\bm{\mu})$ is naturally associated with
its factor graph, an unweighted graph $\hat{G}=(V\cup E_{G},\hat{E}_{G})$ that
is bipartite between the _variable_ vertices representing vertices $i\in V$,
and _factor_ vertices representing hyperedges $h\in E_{G}$. For $i\in V$ and
$h\in E_{G}$, the edge $\\{i,h\\}$ belongs to $\hat{E}_{G}$ if and only if
$i\in h$.

$\hat{E}_{G}=\\{\\{i,h\\}\in V\times E_{G}:i\in h\\}$

A hypergraph flow $\mathbf{Y}$ over $G$ can now be equivalently interpreted as
a graph flow over the factor graph $\hat{G}$, where the flow from vertex $i$
to factor vertex $h$ over the edge $\\{i,h\\}$ is given by
$(\mathbf{Y}^{h})_{i}.$

Figure 1: A hypergraph (left) and its factor graph (right). In the factor
graph, variable vertices are shown in solid black, while factor vertices are
shown as empty circles.

##  3 Monotone Submodular Cut Functions

We start by verifying that any mscf is indeed symmetric and submodular. A
proof of this fact can be found in Appendix A:

######  Fact 7.

Let $V$ be an arbitrary finite set and $F:2^{V}\to\mathbb{R}$ be a monotone
non-decreasing submodular function. If $\delta:2^{V}\to\mathbb{R}$ is the
function defined by:

$\delta(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{F(S),F(V\setminus S)\\}\,,$

then $\delta$ is symmetric (in the sense of Definition 1) and submodular.

We next establish the primal property of mscf. This will allow us to
approximate the Lovász extension $\bar{\delta}(\mathbf{x})$ by the $F$-norm of
the projection of $\mathbf{x}$ onto $\mathbb{R}^{h}\perp{\bf 1}$. The
following theorem proves a stronger property stating that the base polytope
$\mathcal{B}(\delta_{h})$ is closely approximated by the symmetric polytope
$\mathcal{P}_{\mathsf{sym}}(F_{h})$ of the non-decreasing function $F_{h}$
inducing $\delta_{h}$. Its proof can also be found in Appendix A.

######  Theorem 5.

Suppose $\delta_{h}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{F_{h}(S),F_{h}(\bar{S})\\}$ where
$F_{h}:2^{h}\rightarrow\mathbb{R}$ is a non-decreasing submodular function
such that $F(\varnothing)=0$ and $F(\\{i\\})>0$ for all $i\in V$. We have:

$\big{(}\mathcal{P}_{\textup{sym}}(F_{h})\cap{\bf
1}^{\perp}\big{)}\subseteq\;\mathcal{B}(\delta_{h})\;\subseteq
2\cdot\big{(}\mathcal{P}_{\textup{sym}}(F_{h})\cap{\bf 1}^{\perp}\big{)}.$

In particular, for all $\mathbf{x}\in\mathbb{R}^{h}$

$\min_{u}\|\mathbf{x}-u{\bf 1}\|_{F_{h}}\leq\bar{\delta}_{h}(\mathbf{x})\leq
2\min_{u}\|\mathbf{x}-u{\bf 1}\|_{F_{h}}.$

It is instructive to consider how the previous results are instantiated for
the standard hypergraph cut function
$\delta^{\mathsf{cut}}_{h}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{F^{\mathsf{cut}}(S),F^{\mathsf{cut}}(\bar{S})\\}$ with
$F^{\mathsf{cut}}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{1,\lvert S\rvert\\}$. In this case, the norm $\|\cdot\|_{F}$
is the $\ell_{\infty}$-norm and the symmetric submodular polyhedron
$\mathcal{P}_{\mathsf{sym}}(F^{\mathsf{cut}})$ is the unit $\ell_{1}$-ball.
Hence the relaxation in Theorem 5 is equivalent to:

$\min_{u}\|\mathbf{x}-u{\bf 1}\|_{\infty}\leq\bar{\delta}_{h}(\mathbf{x})\leq
2\min_{u}\lVert\mathbf{x}-u\boldsymbol{1}\rVert_{\infty}.$

Note that, in this case, the right-hand side is actually tight, as can be seen
by letting $\mathbf{x}={\bf 1}^{S}$ and $u=\nicefrac{{1}}{{2}}$ for a non-
trivial $S\subset h.$

By comparison, the denominator of the ratio-cut function is given by the cut
function
$\delta_{\bm{\mu}}(S)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min\\{\bm{\mu}(S),\bm{\mu}(\bar{S})\\}$. In this case, the
$\mathcal{P}_{\mathsf{sym}}(\bm{\mu})$ is given by the unit
$\ell_{\infty}$-ball, and the relaxation is given by the $\ell_{1}$-norm.

$\min_{u}\|\mathbf{x}-u{\bf
1}\|_{\bm{\mu},1}\leq\bar{\delta}_{V}(\mathbf{x})\leq
2\min_{u}\lVert\mathbf{x}-u\boldsymbol{1}\rVert_{\bm{\mu},1}$

In this case, plugging in $\mathbf{x}={\bf 1}^{S}$ shows that the left hand
side is tight. Hence, the coefficients in Theorem 5 cannot be improved.

###  3.1 Flow Embedding of Graphs into Weighted Submodular Hypergraphs

Let us now introduce a mechanism for flow embedding graphs into weighted
submodular hypergraphs with mscf cut function. We will show how 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. It is in this step that we crucially make use of the
absoluteness of the norms $\|\cdot\|_{F_{h}}$ associated with a mscf cut
function $\delta_{h}$.

##### Hypergraph Flow Embeddings

We begin with a notion of congestion for hypergraph flows over mscf-
hypergraphs.

######  Definition 5.

Given a weighted submodular hypergraph
$G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$ equipped with a collection
of mscfs $\\{\delta_{h}\\}_{h\in E_{G}}$ and a hypergraph flow
$\mathbf{Y}=(\mathbf{y}_{h}\in\mathbb{R}^{h}\perp{\bf 1}_{h})_{h\in E}$, the
congestion of $\mathbf{Y}$ over a hyperedge $h\in E$ is defined as

$\operatorname{cong}_{h}(\mathbf{Y})\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\|\mathbf{y}_{h}\|_{*,F_{h}}}{w_{h}}\,.$

The congestion of hypergraph flow $\mathbf{Y}$ over the hypergraph $G$ is:

$\operatorname{cong}_{G}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min_{h\in E}\operatorname{cong_{h}}(\mathbf{Y})\,.$

The following definition then captures what is meant by a weighted graph being
flow-embeddable into a given weighted submodular hypergraph.

######  Definition 6 (Hypergraph Flow Embedding).

Let $G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$ be a weighted hypergraph
equipped with a collection of mscfs $\\{\delta_{h}\\}_{h\in E_{G}}$. We say a
weighted graph $H=\big{(}V,E^{H},\mathbf{w}^{H}\big{)}$ embeds into $G$ as a
flow with congestion $\rho\geq 0$, denoted $H\preceq_{\rho}G$, if there exist
hypergraph flows $\\{\mathbf{Y}^{e}\\}_{e\in E^{H}}$ such that:

  1. 1.

For all $e=\\{i,j\\}\in E^{H}$, the flow $\mathbf{Y}^{e}$ routes $w^{H}_{e}$
units of flow between vertex $i$ and vertex $j$, i.e.

$\big{\lvert}\operatorname{dem}(\mathbf{Y}^{e})\big{\rvert}=w^{H}_{e}\cdot({\bf
1}_{i}+{\bf 1}_{j})\,.$

  2. 2.

For each $h\in E_{G}$, we have:

$\left\|\sum_{e\in
E_{H}}\big{|}\mathbf{y}^{e}_{h}\big{|}\right\|_{*,F_{h}}\leq\rho\cdot
w^{G}_{h}\,.$

There is a slight subtlety in this definition. One may be inclined, by analogy
with graphs, to replace the last condition in the definition with the more
natural bound on the total congestion $\sum_{e\in
E_{H}}\operatorname{cong}_{h}(\mathbf{Y}^{e})\leq\rho.$ However, for
hypergraphs of rank larger than $2$, this latter quantity can be significantly
larger than the former quantity in the definition, preventing the proof of
Theorem 7.

We will use this notion of embeddability to certify lower bounds to the ratio-
cut objective for general monotone submodular cut functions, and not just
standard cut functions. We will crucially make use of this theorem in our
development of the cut-matching game for solving ratio-cut problems over
weighted submodular hypergraphs.

######  Theorem 6.

Let $G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$ be a weighted hypergraph
equipped with a collection of monotone submodular cut functions
$\\{\delta_{h}\\}_{h\in E_{G}}$, and $H=\big{(}V,E_{H},\mathbf{w}^{H}\big{)}$
be a weighted graph. If $H\preceq_{\rho}G$, then

$\sum_{\\{i,j\\}\in
E_{H}}w^{H}_{ij}\cdot\lvert\mathbf{x}_{i}-\mathbf{x}_{j}\rvert\leq\rho\cdot\sum_{h\in
E_{G}}w^{G}_{h}\cdot\min_{u\in\mathbb{R}}\lVert\mathbf{x}_{h}-u\boldsymbol{1}\rVert_{F_{h}}$

for all $\mathbf{x}\in\mathbb{R}^{V}$. In particular, setting $\mathbf{x}={\bf
1}^{S}$ yields a lower bound on the hypergraph cut in terms of the graph cut
function of $H$ for any $S\subseteq V$:

$\delta_{H}(S)\leq\rho\cdot\delta_{G}(S)\,.$

###### Proof.

Consider the hypergraph flows $\\{\mathbf{Y}^{e}\\}_{e\in E^{H}}$ associated
with the embedding $H\preceq_{\rho}G$ and let
$\mathbf{u}\in\mathbb{R}^{E}_{G}$ be an arbitrary vector over the hyperedges.
As each $\mathbf{Y}^{e}$ routes demand $w^{H}_{e}$ between the endpoints of
$e=\\{u,v\\}\in E_{H}$, we have

$w^{H}_{e}\cdot\big{|}\mathbf{x}_{u}-\mathbf{x}_{v}\big{|}=\left\lvert\big{\langle}\operatorname{dem}(\mathbf{Y}^{e}),\mathbf{x}\big{\rangle}\right\rvert=\left\lvert\sum_{h\in
E_{G}}\big{\langle}\mathbf{y}^{e}_{h},\mathbf{x}_{h}\big{\rangle}\right\rvert=\left\lvert\sum_{h\in
E_{G}}\big{\langle}\mathbf{y}^{e}_{h},\mathbf{x}_{h}-u_{h}{\bf
1}_{h}\big{\rangle}\right\rvert\leq\sum_{h\in
E_{G}}\big{\langle}\lvert\mathbf{y}^{e}_{h}\rvert,\lvert\mathbf{x}_{h}-u_{h}{\bf
1}_{h}\rvert\big{\rangle}\,,$

where the last equality relied on the fact that
$\mathbf{y}^{e}_{h}\in\mathbb{R}^{h}\perp{\bf 1}_{h}$. Summing over all edges
in $E_{h}$ yields:

$\displaystyle\sum_{e=\\{u,v\\}\in
E_{H}}w^{H}_{uv}\cdot|\mathbf{x}_{u}-\mathbf{x}_{v}|$
$\displaystyle\leq\sum_{e\in E_{H}}\sum_{h\in
E_{G}}\big{\langle}|\mathbf{y}^{e}_{h}|,|\mathbf{x}_{h}-u_{h}{\bf
1}_{h}|\big{\rangle}$ $\displaystyle=\sum_{h\in E_{G}}\left\langle\sum_{e\in
E_{H}}|\mathbf{y}^{e}_{h}|,|\mathbf{x}_{h}-u_{h}{\bf 1}_{h}|\right\rangle$
$\displaystyle\leq\sum_{h\in E_{G}}\;\left\|\sum_{e\in
E_{H}}|\mathbf{y}^{e}_{h}|\right\|_{*,F_{h}}\cdot\;\|\mathbf{x}_{h}-u_{h}{\bf
1}_{h}\|_{F_{h}}$ $\displaystyle\leq\rho\cdot\sum_{h\in
E_{G}}w^{G}_{h}\cdot\lVert\mathbf{x}_{h}-u\boldsymbol{1}\rVert_{F_{h}}\,.$

The first inequality is an application of Fact 3. The second inequality
follows from Definition 5. Finally, the first statement in the theorem follows
by setting the arbitrary $\mathbf{u}$ to be the required minimizer. The
specialization to cuts follows by plugging in $\mathbf{x}={\bf 1}^{S}$ and
applying Theorem 5. ∎

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, with the additional complication that we
need to appeal to the absoluteness of the $\|\cdot\|_{F_{h}}$-norms to derive
the required congestion bounds. The proof appears in Appendix A.

######  Theorem 7.

Let $G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$ be a weighted hypergraph
equipped with a collection of mscfs $\\{\delta_{h}\\}_{h\in E_{G}}$. Given a
hypergraph flow $\mathbf{Y}$ over $G$, there is an algorithm that, in time
$\tilde{O}\big{(}\mathsf{sp}(G)\big{)}$, computes a weighted graph
$H=\big{(}V,E_{h},\mathbf{w}^{H}\big{)}$ such that
$H\preceq_{\operatorname{cong}_{G}(\mathbf{Y})}G$. Furthermore, the following
hold:

  1. 1.

The graph $H$ is bipartite over the partition $\big{(}\\{i\in
V:\operatorname{dem}_{i}(\mathbf{Y})\geq 0\\},\\{i\in
V:\operatorname{dem}_{i}(\mathbf{Y})<0\\}\big{)}$.

  2. 2.

The degree of vertex $i$ in $H$ equals $\operatorname{dem}_{i}(\mathbf{Y})$.

##  4 Local Relaxations of Minimum Ratio-cut Over Hypergraphs

Next, we introduce a family of locally-biased convex relaxations and study how
it approximates the minimum ratio-cut problem. Prior to this, we state an
equivalent formulation of minimum ratio-cut as a continuous optimization
problem. Given a weighted submodular hypergraph $G=(V,E,\mathbf{w},\bm{\mu})$,
and cut functions $\\{\delta_{h}\\}_{h\in E}$, we define (RC-NonCvx) as the
optimization problem $\bar{\Psi}_{G}^{*}$ over $\mathbb{R}^{V}$:

$\displaystyle\bar{\Psi}_{G}(\mathbf{x})$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\overline{\delta}_{G}(\mathbf{x})}{\overline{\delta}_{V}(\mathbf{x})}=\frac{\overline{\delta}_{G}(\mathbf{x})}{\min_{u}\|\mathbf{x}-u{\bf
1}\|_{\bm{\mu},1}}$ $\displaystyle\bar{\Psi}_{G}^{*}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min_{\mathbf{x}\in\mathbb{R}^{V}}\bar{\Psi}_{G}(\mathbf{x})$ (RC-
NonCvx)

The fact that $\bar{\Psi}_{G}^{*}$ is equivalent to solving the minimum ratio-
cut problem (expressed in the following lemma) is a direct consequence of Fact
4. It is proved in full in Appendix A.

######  Lemma 1.

Given a weighted hypergraph $G^{*}=(V,E,\bm{\mu},\mathbf{w})$, we have
$\Psi_{G}^{*}=\bar{\Psi}_{G}^{*}$. Furthermore, there exists an algorithm
that, given any $\mathbf{x}\in\mathbb{R}^{V}$, recovers a cut $S\subseteq V$
satisfying

$\Psi_{G}(S)\leq\bar{\Psi}_{G}(\mathbf{x})$

in time $O\big{(}|V|\log|V|+\mathsf{sp}(G)\big{)}$.

###  4.1 The ratio-cut improvement problem

The impetus for studying a family of local convex relaxations for the minimum
ratio-cut problem lies in the fact that $\bar{\Psi}^{*}_{G}$ is non-convex:
the denominator is not concave. Consequently, it is unclear that this problem
can be solved to near-optimality in polynomial time.

Our family of relaxations is parameterized by a _seed vector_
$\mathbf{s}\in\mathbb{R}^{V}$. We first define this relaxation, _the ratio-cut
improvement problem_ , as a combinatorial problem over cuts.

######  Definition 7 (Ratio-Cut Improvement Problem).

Given a weighted submodular hypergraph $G=(V,E,\mathbf{w},\bm{\mu})$, cut
functions $\\{\delta_{h}\\}_{h\in E}$, and a _seed vector_
$\mathbf{s}\in\mathbb{R}^{V}$ with
$\langle\mathbf{s},\boldsymbol{1}\rangle_{\mu}=0$ and
$\lVert\mathbf{s}\rVert_{\infty}\leq 1,$ the ratio-cut improvement objective
$\Psi_{G,s}$ is defined for all $S\subset V$ as:

$\displaystyle\Psi_{G,\mathbf{s}}(S)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\delta_{G}(S)}{\lvert\langle\mathbf{s},\boldsymbol{1}^{S}\rangle_{\mu}\rvert}=\frac{\sum_{h\in
E}w_{h}\cdot\delta_{h}(S\cap
h)}{\lvert\langle\mathbf{s},\boldsymbol{1}^{S}\rangle_{\mu}\rvert}$
$\displaystyle\Psi^{*}_{G,\mathbf{s}}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min_{S\subseteq V}\Psi_{G,\mathbf{s}}(S)$

The ratio-cut improvement problem asks to find $S\subseteq V$ achieving
$\Psi^{*}_{G,\mathbf{s}}=\Psi_{G,\mathbf{s}}(S)$.

The combinatorial formulation is equivalent to a continuous, convex
optimization problem where the non-concave denominator of $\bar{\Psi}_{G}^{*}$
is replaced with the correlation
$\lvert\langle\mathbf{s},\mathbf{x}\rangle_{\mu}\rvert$. We define
$\bar{\Psi}^{*}_{G,\mathbf{s}}$ to be this objective:

$\displaystyle\bar{\Psi}_{G,\mathbf{s}}(\mathbf{x})$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\frac{\bar{\delta}_{G}(\mathbf{x})}{\lvert\langle\mathbf{s},\mathbf{x}\rangle_{\bm{\mu}}\rvert},\hskip
28.45274pt\text{ and }\hskip
28.45274pt\bar{\Psi}_{G,\mathbf{s}}^{*}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\min_{\mathbf{x}\in\mathbb{R}^{V}}\bar{\Psi}_{G,\mathbf{s}}(\mathbf{x}).$

The fact that the ratio-cut improvement problem $\Psi_{G,\mathbf{s}}^{*}$ is a
relaxation of the minimum ratio-cut problem over hypergraphs $\Psi_{G}^{*}$
follows immediately from observing
$\bar{\Psi}_{G}^{*}\leq\bar{\Psi}_{G,\mathbf{s}}^{*}$ when the seed satisfies
conditions derived from duality of conjugate norms.

######  Lemma 2.

For all $\mathbf{x}\in\mathbb{R}^{V}$, and seeds $\mathbf{s}\in\mathbb{R}^{V}$
satisfying $\lVert\mathbf{s}\rVert_{\infty}\leq 1$ and
$\langle\mathbf{s},\boldsymbol{1}\rangle_{\bm{\mu}}=0$, we have:

$\bar{\Psi}_{G}(\mathbf{x})\leq\bar{\Psi}_{G,\mathbf{s}}(\mathbf{x})\,.$

In particular, setting $\mathbf{x}=\boldsymbol{1}^{S}$ yields
$\Psi_{G,\mathbf{s}}^{*}$ is a relaxation of $\Psi_{G}^{*}$ for any $S\subset
V$:

$\Psi_{G}(S)\leq\Psi_{G,\mathbf{s}}(S)\,.$

###### Proof.

By the duality of conjugate norms, we have

$\min_{u\in\mathbb{R}}\lVert\mathbf{x}-u\boldsymbol{1}\rVert_{1,\bm{\mu}}=\min_{u\in\mathbb{R}}\max_{\lVert\mathbf{y}\rVert_{\infty}\leq
1}\langle\mathbf{y},\mathbf{x}-u\boldsymbol{1}\rangle_{\bm{\mu}}=\max_{\begin{subarray}{c}\lVert\mathbf{y}\rVert_{\infty}\leq
1\\\
\langle\mathbf{y},\boldsymbol{1}\rangle_{\bm{\mu}}=0\end{subarray}}\langle\mathbf{y},\mathbf{x}\rangle\geq\lvert\langle\mathbf{s},\mathbf{x}\rangle_{\bm{\mu}}\rvert$

for all $\mathbf{x}\in\mathbb{R}^{V}$. Consequently,

$\bar{\Psi}_{G}(\mathbf{x})=\frac{\sum_{h\in
E}w_{h}\bar{\delta}_{h}(\mathbf{x})}{\min_{u\in\mathbb{R}}\lVert\mathbf{x}-u\boldsymbol{1}\rVert_{1,\bm{\mu}}}\leq\frac{\sum_{h\in
E}w_{h}\bar{\delta}_{h}(\mathbf{x})}{\lvert\langle\mathbf{s},\mathbf{x}\rangle\rvert_{\bm{\mu}}}=\bar{\Psi}_{G,\mathbf{s}}(\mathbf{x})$

as required. ∎

Typically, we will be interested in the case where the seed vector
$\mathbf{s}$ is given by

${\bf 1}^{A,\overline{A}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}{\bf 1}^{A}-\frac{\mu(A)}{\mu(\overline{A})}\cdot{\bf
1}^{\overline{A}}\,.$ (3)

for a cut $A\subseteq V$. This choice of seed vector certainly satisfies
$\langle\mathbf{s},\boldsymbol{1}\rangle_{\bm{\mu}}=0$ and
$\lVert\mathbf{s}\rVert_{\infty}\leq 1$. Using this seed vector for the ratio-
cut improvement problem also immediately recovers the cut improvement problem
of Andersen and Lang [5] as discussed in Appendix B.1.

Of critical, algorithmic, consequence is the fact that computing the value of
$\bar{\Psi}_{G,\mathbf{s}}^{*}$ can be written as a convex program. We refer
to this program as (CI-Primal):

$\displaystyle\underset{\mathbf{x}\in\mathbb{R}^{V}}{\min}$
$\displaystyle\sum_{h\in E}w_{h}\cdot\bar{\delta}_{h}(\mathbf{x})$ (CI-Primal)
s.t. $\displaystyle\langle\mathbf{s},\mathbf{x}\rangle_{\mu}=1$

The following lemma is a simple consequence of the submodularity and symmetry
of $\delta_{G}.$

######  Lemma 3.

The optimum value of (CI-Primal) equals $\Psi^{*}_{G,\mathbf{s}}$.

With this convex program, one can leverage convex duality to construct lower
bounds for $\bar{\Psi}^{*}_{G,\mathbf{s}}$, and consequently
$\Psi^{*}_{G,\mathbf{s}}$. We consider a dual formulation of (CI-Primal) as a
problem over hypergraph flows:

$\displaystyle\underset{\begin{subarray}{c}\alpha\in\mathbb{R},\\\
\\{\mathbf{Y}=\\{\mathbf{y}_{h}\\}_{h\in E}\in\bigoplus_{h\in
E}\mathbb{R}^{h}\\}\end{subarray}}{\max}$ $\displaystyle\alpha$ (CI-Dual) s.t.
$\displaystyle\operatorname{dem}(\mathbf{Y})=\alpha\cdot\big{(}\bm{\mu}\circ\mathbf{s}\big{)}$
$\displaystyle\mathbf{y}_{h}\in w_{h}\cdot\mathcal{B}(\delta_{h})$
$\displaystyle\forall\,h\in E$

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 B.2.

######  Lemma 4.

The programs (CI-Primal) and (CI-Dual) are dual to each other. Strong duality
holds.

###  4.2 From Primal-Dual Solutions to Hypergraph Flow Embeddings

One of our main contributions will be to apply a generalized cut-matching game
to combine local lower bounds into global lower bounds for the non-convex
problem $\bar{\Psi}^{*}_{G}$. Our local certificate is computed using an
approximate solutions to (CI-Primal) and (CI-Dual). Let us define an
$\epsilon$-approximate primal-dual solution as a cut $A\subseteq V$ paired
with a hypergraph flow $\mathbf{Y}\in\bigoplus_{h\in
E}w_{h}\cdot\mathcal{B}(\delta_{h})$ that approximately satisfies the demand
constraint in (CI-Dual) up to multiplicative $\ell_{1}$-error.

######  Definition 8 ($\epsilon$-approximate primal-dual solution).

Let $G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$ be a mscf-hypergraph
equipped with cut functions $\\{\delta_{h}\\}_{h\in E}$, and
$\mathbf{s}\subseteq V$ a seed vector satisfying $\mathbf{s}\in\mathbb{R}^{V}$
with $\langle\mathbf{s},\boldsymbol{1}\rangle_{\mu}=0$ and
$\lVert\mathbf{s}\rVert_{\infty}\leq 1$. An $\epsilon$-_approximate primal-
dual solution_ for $(G,\mathbf{s})$ is a pair

$\bigg{(}A\subseteq V,\;\mathbf{Y}\in\bigoplus_{h\in
H}\big{(}\mathbb{R}^{h}\perp\boldsymbol{1}_{h}\big{)}\bigg{)}$

such that the following hold simultaneously.

  1. 1.

$\mathbf{y}_{h}\in w_{h}\cdot\mathcal{B}(\delta_{h})$ for all $h\in E_{G}$,

  2. 2.

$\big{\lVert}\operatorname{dem}(\mathbf{Y})-\Psi^{*}_{G,\mathbf{s}}\cdot(\bm{\mu}\circ\mathbf{s})\big{\rVert}_{1}\leq\frac{\epsilon}{8}\cdot\big{\lVert}\Psi^{*}_{G,\mathbf{s}}\cdot(\bm{\mu}\circ\mathbf{s})\big{\rVert}_{1}$,

  3. 3.

$\operatorname{dem}(\mathbf{Y})\leq\Psi_{G,\mathbf{s}}^{*}\cdot(\bm{\mu}\circ\mathbf{s})$
in an entry-wise sense,

  4. 4.

$\Psi_{G,\mathbf{s}}(A)\leq 2\cdot\Psi^{*}_{G,\mathbf{s}}$,

  5. 5.

$\operatorname{dem}(\mathbf{Y})_{i}\cdot\mathbf{s}_{i}\geq 0$ for every $i\in
V$.

The local certificate then takes the form of a demand graph given by running a
flow-path decomposition on the hypergraph flow in an $\epsilon$-approximate
primal-dual solutions yields a hypergraph flow embedding. The fact that the
demand graph certifies a lower bound to the minimum ratio-cut objective
$\Psi_{G}^{*}$ is a direct consequence of the algorithmic result in Section 3,
Theorem 7.

######  Lemma 5.

Given an $\epsilon$-approximate primal-dual solution $(A,\mathbf{Y})$ to the
ratio-cut improvement problem on $(G,\mathbf{s})$, let $H$ be the graph
obtained by applying the flow-path decomposition algorithm of Theorem 7 to the
hypergraph embedding $\mathbf{Y}$. Then

$H\preceq_{2}G$

Furthermore, graph $H$ is bipartite over the partition $\big{(}\\{i\in
V:\mathbf{s}_{i}(\mathbf{Y})\geq 0\\},\\{i\in V:\mathbf{s}_{i}<0\\}\big{)}$,
and the degree of vertex $i$ in $H$ equals
$\operatorname{dem}_{i}(\mathbf{Y})$.

###### Proof.

The statements on the bipartiteness and degree distribution of $H$ follow
directly from by Theorem 7. By the same theorem, we also have
$H_{t}\preceq_{\operatorname{cong}_{G}(\mathbf{Y}^{t})}G$ for each $t$, so it
only remains to bound $\operatorname{cong}_{G}(\mathbf{Y}^{t})$.

Since $\mathbf{Y}^{t}$ is part of an $\epsilon$-approximate primal-dual
definition output, Definition 8 and Theorem 5 imply that, for all $h\in
E_{G},$

$\mathbf{y}^{t}_{h}\in w_{h}\cdot\mathcal{B}(\delta_{h})\subseteq
2w_{h}\cdot\big{(}\mathcal{P}_{\textup{sym}}(F_{h})\cap{\bf
1}^{\perp}\big{)}.$

Because $\mathcal{P}_{\textup{sym}}(F_{h})$ is the unit-norm polytope for the
dual norm $\|\cdot\|_{*,F_{h}}$, this yields, for all $h\in E_{G}$:

$\operatorname{cong}_{h}(\mathbf{Y}^{t})=\frac{\|\mathbf{y}^{t}_{h}\|_{*,F_{h}}}{w_{h}}\leq
2$

as required. ∎

###  4.3 Approximation algorithms for the ratio-cut improvement problem

Let us now discuss algorithms for approximating (CI-Primal) and (CI-Dual). For
convenience, we introduce the following oracle to abstract algorithmic details
in the rest of the paper.

######  Definition 9.

An approximate primal-dual oracle for the ratio-cut improvement problem is an
algorithm $\mathcal{A}_{\textup{{CI}}}$ which outputs an
$\epsilon$-approximate primal-dual solution when given a mscf-hypergraph $G$
equipped with $\\{\delta_{h}\\}_{h\in E}$, a seed
$\mathbf{s}\in\mathbb{R}^{V}$ satisfying
$\langle\mathbf{s},\boldsymbol{1}\rangle_{\mu}=0$ and
$\lVert\mathbf{s}\rVert_{\infty}\leq 1$, and an $\epsilon>0$.

We can now state our main theorem on efficient approximation algorithms for
the ratio-cut improvement problem on weighted submodular hypergraphs. The
running time of approximating ratio-cut improvement depends on what
assumptions are made regarding the hypergraph $G$, and the cut functions
$\\{\delta_{h}\\}_{h\in E}$. The running time also leverages different known
results on computing approximate solutions to maximum flow and decomposable
submodular minimization. Its proof is given in Appendix B.3.

######  Theorem 8.

Given a mscf-hypergraph $G=(V,E,\mathbf{w},\bm{\mu})$ with
$\\{\delta_{h}\\}_{h\in E}$, let $T_{\epsilon}\big{(}G,\\{\delta_{h}\\}_{h\in
E}\big{)}$ be the time required by an approximate primal-dual oracle
$\mathcal{A}_{\textup{{CI}}}$ to output an $\epsilon$-approximate primal-dual
solution for seed $\mathbf{s}$. For each set of assumptions in the table
below, there exists $\mathcal{A}_{\textup{{CI}}}$ with the stated bounds on
$T_{\epsilon}\big{(}G,\\{\delta_{h}\\}_{h\in E}\big{)}$.

Assumptions on $G$ and $\\{\delta_{h}\\}_{h\in E}$ |  Upperbound on $T_{\epsilon}(G,\\{\delta_{h}\\}_{h\in E})$ | Relevant Results
---|---|---
$\forall\,h\in E,$ $\delta_{h}=\delta_{h}^{\mathsf{cut}}$ | $\tilde{O}\Big{(}\big{(}|V|+\mathsf{sp}(G)^{1+o(1)}\big{)}\cdot\log\big{(}\max_{h\in E}w_{h}\big{)}\Big{)}$ |  Appendix B.3 and [12]
$\forall\,h\in E,|h|=O(1)$ | $\tilde{O}\Big{(}\sum_{h\in E}T_{h}+T_{\mathsf{flow}}\left(n,n+|E|\right)\Big{)}$ |  Axiotis et al. [8]
General $G$ and $\\{\delta_{h}\\}_{h\in E}$ | $\tilde{O}\Big{(}|V|\cdot\sum_{h\in E}\Theta_{h}\cdot\log\big{(}{|V|\cdot\max_{h\in E}w_{h}}\big{)}\Big{)}$ |  Ene et al. [24]

Here, $T_{h}$ is the running time of a linear optimization oracle for
$\delta_{h}$, $\Theta_{h}$ is the running time for a quadratic optimization
oracle for $\delta_{h}$, and $T_{\mathsf{flow}}(n,m)$ is the running time
required to solve a maximum flow problem on an undirected graph with $n$
vertices and $m$ edges.

##  5 An $O(\log n)$-Approximation via Generalized Cut-Matching Games

We now describe a generalized version of the cut-matching game, and discuss
how it can be used to design an approximation algorithm for the minimum ratio-
cut problem.

A key aspect of our cut-matching game is the possibility for the cut player to
play unbalanced cuts. This is really a consequence of wanting the matching
player to be implementable by an approximate solver for the ratio-cut
improvement problem. Let us formally define a valid action from such a
matching player as follows.

######  Definition 10 ($\epsilon$-approximate matching action).

Given $\epsilon>0$, an _$\epsilon$ -approximate matching action_ with respect
to a cut $S\subseteq V$ is a weighted bipartite graph
$D=\big{(}S\cup\bar{S},E_{D},\mathbf{w}^{D},\bm{\mu}\big{)}$ such that the
following hold:

  1. 1.

$\big{\lVert}\mathbf{d}-\bm{\mu}\circ\lvert\mathbf{s}\rvert\big{\rVert}_{1}\leq\epsilon\cdot\big{\lVert}\bm{\mu}\circ\lvert\mathbf{s}\rvert\big{\lVert}_{1}$,

  2. 2.

$d_{i}\leq(\bm{\mu}\circ\lvert\mathbf{s}\rvert)_{i}$ for each $i\in V$,

where $\mathbf{d}\in\mathbb{R}^{V}$ is the vector of vertex degrees in $D$,
i.e. $\mathbf{d}_{i}=\deg_{D}(i)$ and $\mathbf{s}={\bf 1}^{S,\overline{S}}$ as
defined in equation 3.

Notice that Lemma 5 demonstrates such a graph $D$ is immediately obtained via
the demand graph of a hypergraph flow given by an approximate primal-dual
solution to the ratio-cut improvement problem on the seed
$\boldsymbol{1}^{S,\overline{S}}$. Since $D$ certifies a local lower bound to
the ratio-cut objective, it is natural to use the cut-matching games framework
compose different certificates $D$. The hope is that this will produce a
certificate that globally lower bounds the ratio-cut objective with a quantity
depending only on the number of vertices.

Now, applying the standard cut-matching game is insufficient as an approximate
solution to the cut-improvement problem may produce $D$ that is not a perfect
matching. In fact, $D$ may even fail to contain a matching between a constant
fraction of vertex pairs, and thus recursive application of the standard cut-
matching game may not suffice for fast algorithms either. We amend the
standard cut-matching games framework to allow for the cut player to play
potentially unbalanced cuts.

######  Definition 11 (Generalized cut-matching game).

Let $n>0$, $\epsilon>0$, and $\bm{\mu}\in\mathbb{R}^{V}_{\geq 0}$ be a
weighting over a set of vertices $V$ such that $\lvert V\rvert=n$. An
$(n,\epsilon,\bm{\mu})$_-generalized cut-matching game_ is a two-player game
between a cut strategy $\mathcal{C}$, and a matching strategy $\mathcal{M}$
that proceeds as follows. In the $t$-th round of the game:

  1. 1.

$\mathcal{C}$ plays a cut $S_{t}\subset V$ such that $S_{t}\neq\varnothing$,
and $\bm{\mu}(S_{t})\leq\frac{1}{2}\cdot\bm{\mu}(V)$, and

  2. 2.

$\mathcal{M}$ responds with an $\epsilon$-approximate matching action $D_{t}$.

Note that this definition also allows for the specification of an arbitrary
vertex weighting $\bm{\mu}$. Consequently, algorithms built on this notion of
the cut-matching game can approximate not only expansion, but arbitrary ratio-
cut objectives, such as $\bm{\mu}$-conductance, without the need for
recursion.

Even though the cut player is given more power in the generalized cut-matching
game, it must also produce $S$ with stronger structural guarantees in order
for the cut-matching game to produce an approximation algorithm for the
minimum ratio-cut problem. The next definition formalizes what is required of
the cut strategy so that one may leverage this cut-matching game to
approximate minimum ratio-cut.

######  Definition 12 ($\big{(}f(n),g(n,\epsilon)\big{)}$-good cut strategy).

Let $f(n)$ and $g(n,\epsilon)$ be non-decreasing functions, and suppose
$\mathcal{C}$ plays the sequence of cuts
$S_{1},\ldots,S_{g(n,\epsilon)}\subseteq V$. We say that $\mathcal{C}$ is
$\big{(}f(n),g(n,\epsilon)\big{)}$-good if, for any sequence weighted graphs
$D_{1},\ldots,D_{g(n,\epsilon)}$ such that each $D_{t}$ is an
$\epsilon$-approximate matching action with respect to $S_{t}$, the graph
$H=\sum_{t=1}^{g(n,\epsilon)}D_{t}$ (taken in an edge-wise manner) satisfies

$\Psi_{H}\geq f(n)\,.$

Using this requirement, we can now state the first main result concerning cut-
matching games.

######  Theorem 9.

Let $f(n)$ and $g(n,\epsilon)$ be non-decreasing functions. Given an
$\big{(}f(n),g(n,\epsilon)\big{)}$-good cut strategy, there exists an
algorithm approx-rc which, on input of a mscf-hypergraph
$G=\big{(}V,E_{G},\mathbf{w},\bm{\mu}\big{)}$, and $\epsilon>0$, outputs a cut
$A\subseteq V$ that is an
$O\left(\frac{g(n,\epsilon)}{f(n)}\right)$-approximate minimum ratio-cut:

$\Psi_{G}^{*}\leq\Psi_{G}(A)\leq
O\bigg{(}\frac{g(n,\epsilon)}{f(n)}\bigg{)}\cdot\Psi_{G}^{*}\,.$

We prove this theorem in Section 5.1. We then show a good cut strategy exists.
Doing so illuminates what additional structure is required from the cut player
in the generalized cut-matching game, and yields

######  Theorem 10.

There exists a randomized cut strategy $\mathcal{C}$ where, for any
$\epsilon>0$, $\mathcal{C}$ is $\left(\Omega(\log
n),O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}\right)$-good with probability
$1-o_{n}(1)$. Furthermore, $\mathcal{C}$ outputs a cut in time that is nearly-
linear in $n$.

Its proof is given in Section 5.2. Finally, taking the two aforementioned
results in conjunction demonstrates our algorithmic guarantee for the minimum
ratio-cut problem.

######  Corollary 1.

Given an approximate primal-dual oracle $\mathcal{A}_{\textup{{CI}}}$ for the
ratio-cut improvement problem, there exists an algorithm $\mathcal{A}$ which,
on input of a mscf-hypergraph $G=\big{(}V,E_{G},\mathbf{w},\bm{\mu}\big{)}$,
and $\epsilon>0$, outputs a $O\big{(}\frac{\log
n}{1-\epsilon}\big{)}$-approximate minimum ratio-cut. Furthermore,
$\mathcal{A}$ requires at most $O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}$
calls to $\mathcal{A}_{\textup{{CI}}}$.

###### Proof.

Theorem 10 yields a cut strategy that is
$\big{(}f(n),g(n,\epsilon)\big{)}$-good cut strategy where
$O\left(\frac{g(n,\epsilon)}{f(n)}\right)=O\big{(}\frac{\log
n}{1-\epsilon}\big{)}$. Applying Theorem 9 then gives the desired
approximation ratio. For the running time, note $\mathcal{A}$ requires only
$g(n,\epsilon)=O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}$ iterations. ∎

In light of the results of Theorem 8, the above corollary gives an algorithm
to solve the minimum ratio-cut problem over any weighted hypergraph with cut
function $\delta_{h}=\delta_{h}^{\mathsf{cut}}$ for every $h\in E$ in time:

$\tilde{O}\left(\big{(}\lvert
V\rvert+\mathsf{sp}(G)^{1+o(1)}\big{)}\cdot\log\max_{h\in E}w_{h}\right)\,,$

and similarly, the running times appearing in the table in Theorem 8 yield
equivalent (up to constant factors) running times for approximation algorithm
for the minimum ratio-cut problem in their respective settings.

###  5.1 Proof of Theorem 9: the cut-matching game reduction

We now prove that, given a $\big{(}f(n),g(n,\epsilon)\big{)}$-good cut
strategy, there exists an algorithm that outputs an
$O\Big{(}\frac{g(n,\epsilon)}{f(n)}\Big{)}$-approximation for minimum ratio-
cut. The reduction is given by the algorithm approx-rc which is summarized in
Algorithm 5.1 below.

Algorithm 1 approx-rc Parameters:
$G=\big{(}V,E_{G},\mathbf{w}^{G},\bm{\mu}\big{)}$, $\epsilon>0$,
$\mathcal{A}_{\textup{{CI}}}$ an approximate primal-dual cut-improvement
oracle, and $\mathcal{C}$ an $\big{(}f(n,\epsilon),g(n)\big{)}$-good cut
strategy. Initialize: $D_{0}=(V,\varnothing,{\bf 0})$ the empty graph. For:
$t=1,\ldots,g(n)$, do the following: 1. Run
$\mathcal{C}(G,D_{0},\ldots,D_{t-1})$ to receive cut $S_{t}\subseteq V$. 2.
Set the seed vector
$\mathbf{s}_{t}=\bm{\mu}(S_{t})\cdot\boldsymbol{1}^{S_{t}}-\frac{\bm{\mu}(S_{t})}{\bm{\mu}(\overline{S_{t}})}\cdot\boldsymbol{1}^{\overline{S_{t}}}$.
3. Compute $\mathcal{A}_{\textup{{CI}}}(G,\mathbf{s}_{t},\epsilon)$ from
Theorem 8 to receive an $\epsilon$-approximate primal-dual solution
$\bigg{(}A_{t}\subseteq V,\;\mathbf{Y}^{t}\in\bigoplus_{h\in
E_{G}}(\mathbb{R}^{h}\perp{\bf 1}_{h})\bigg{)}\,.$ 4. Apply the flow-path
decomposition algorithm of Theorem 7 on $\mathbf{Y}^{t}$ to obtain a graph
$H_{t}$. 5. Denote $\alpha_{t}=\Psi_{G,\mathbf{s}_{t}}(A_{t})$, and compute
the graph $D_{t}=\frac{1}{\alpha_{t}}\cdot H_{t}$ Output: $A_{t^{*}}$ for
$t^{*}=\operatorname*{\arg\\!\min}_{t=1,\ldots,T}\,\Psi_{G,\mathbf{s}_{t}}(A_{t})$.

###### Proof of Theorem 9.

Consider the cut $A_{t^{*}}$ returned by approx-rc, and let
$\alpha_{t}=\Psi_{G,\mathbf{s}_{t}}(A_{t})$ be the ratio-cut improvement
objective of $A_{t}$ returned by $\mathcal{A}_{\textup{{CI}}}$ for each
$t=1,\ldots,g(n)$. The lower bound
$\Psi_{G}\big{(}A_{t^{*}}\big{)}\geq\Psi_{G}^{*}$ follows by $\Psi_{G}^{*}$
being a minimum. For the upper bound, we obtain from Lemma 5, the following
guarantee:

$D_{t}\preceq_{\frac{2}{\alpha_{t}}}G.$

If we let $H=\sum_{t=1}^{g(n)}D_{t}$, then $H$ must satisfy $H\preceq_{\rho}G$
for $\rho=\sum_{t=1}^{g(n)}\frac{2}{\alpha_{t}}$. Theorem 6 then implies:

$\Psi_{H}^{*}\leq\rho\cdot\Psi_{G}^{*}\,.$

However, $\mathcal{C}$ is $\big{(}f(n,\epsilon),g(n)\big{)}$-good and hence

$f(n,\epsilon)\leq\Psi_{H}^{*}\leq\rho\cdot\Psi_{G}^{*}\qquad\Longleftrightarrow\qquad\frac{1}{\rho}\leq\frac{1}{f(n,\epsilon)}\cdot\Psi_{G}^{*}$

Focusing on $\rho$, we can upper bound an average by its largest element

$\rho=g(n)\cdot\frac{1}{g(n)}\cdot\sum_{t=1}^{g(n)}\frac{2}{\alpha_{t}}\leq
g(n)\cdot\max_{t=1,\ldots,g(n)}\,\bigg{\\{}\frac{2}{\alpha_{t}}\bigg{\\}}=\frac{2\cdot
g(n)}{\alpha_{t^{*}}}=\frac{2\cdot
g(n)}{\Psi_{G,\mathbf{s}_{t^{*}}}(A_{t^{*}})}\,,$

and thus conclude

$\Psi_{G,\mathbf{s}_{t^{*}}}(A_{t^{*}})\leq
2\cdot\frac{g(n)}{f(n,\epsilon)}\cdot\Psi_{G}^{*}\,.$

Finally, Lemma 2 implies that the ratio-cut improvement problem is a
relaxation of the minimum ratio-cut problem for any seed
$\mathbf{s}\in\mathbb{R}^{V}$ satisfying
$\langle\mathbf{s},\boldsymbol{1}\rangle_{\bm{\mu}}=0$, and
$\lVert\mathbf{s}\rVert_{\infty}\leq 1$. Hence,

$\Psi_{G}(A_{t^{*}})\leq\Psi_{G,\mathbf{s}_{t^{*}}}(A_{t^{*}})\leq
O\bigg{(}\frac{g(n)}{f(n,\epsilon)}\bigg{)}\cdot\Psi_{G}^{*}$

as required. ∎

###  5.2 Proof of Theorem 10: an $\left(\Omega(\log
n),O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}\right)$-good cut strategy

We now turn our attention towards constructing a good cut strategy. In the
standard cut-matching game, the cut player seeks to construct a certificate
graph that has large expansion in as few rounds as possible. To do this, cut
strategies typically maintain a vector embedding of the vertices in the
current certificate graph. The cut strategy then plays a cut rounded from the
embedding using spectral methods. Our cut strategy adopts an analogous
approach, and we further discuss how the embedding is updated in Section
5.2.2.

The novelty in our construction lies in extracting a robust separation
property which allows for updates to the certificate to be given by the demand
graph of a flow produced by approximately solving a ratio-cut improvement
problem. We discuss this property in detail in Section 5.2.3. The final
construction of the cut strategy is given in Section 5.2.4. Before proceeding,
we introduce some notation and facts that will be relevant when analyzing a
vector embedding.

####  5.2.1 Facts about vector embeddings

We denote a _vector embedding_ of a set of vertices $V=[n]$ into dimension
$d>0$ as the set $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$. When
provided a vertex weighting $\bm{\mu}\in\mathbb{R}^{V}_{\geq 0}$, one can
consider the _expected embedding vector_
$v_{\mathsf{avg}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sum_{i\in V}\frac{\mu_{i}}{\bm{\mu}(V)}\cdot\mathbf{v}_{i}$, and
the _variance of the embedding_ under when $i$ is randomly sampled
proportionally to $\bm{\mu}$:

$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sum_{i\in
V}\frac{\mu_{i}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{\mathsf{avg}}\rVert_{2}^{2}\,.$

When $\mathbf{v}_{\mathsf{avg}}={\bf 0}$, the variance is just the expectation
of $\ell_{2}^{2}$-lengths $\lVert\mathbf{v}_{i}\rVert_{2}^{2}$. In such a
case, we use the following fact to lower bound the average
$\ell_{2}^{2}$-lengths when $i$ is restricted to be contained in some set. We
remark that [48] writes this in terms of trace inner products with the Gram
matrix associated with $\\{\mathbf{v}_{i}\\}_{i\in V}$.

######  Lemma 6 (Fact 5.19 from [48]).

Let $\\{\mathbf{v}_{i}\\}_{i\in V}$ be a vector embedding such that
$\sum_{i\in V}\mu_{i}\mathbf{v}_{i}={\bf 0}$. We have:

$\sum_{i\in\overline{S}}\frac{\mu_{i}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}\rVert_{2}^{2}\geq\frac{\bm{\mu}(S)}{\bm{\mu}(V)}\bigg{(}\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})-\frac{1}{\bm{\mu}(V)}\cdot\sum_{i,j\in\binom{S}{2}}\frac{\mu_{i}\mu_{j}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\bigg{)}\,.$

####  5.2.2 Updating the vector embedding via mirror descent

Khandekar et al. [32] describe a vector embedding update based on computing
the matrix exponential of the current certificate graph’s normalized
Laplacian.

It is convenient to cast this update using mirror descent. Suppose at time
$t$, the cut player has received the sequence of matching actions
$D_{0},\ldots,D_{t}$. In this setting, the update takes in a sequence of
“feedback” matrices corresponding to
$\mathcal{L}_{\bm{\mu}}(D_{0}),\ldots,\mathcal{L}_{\bm{\mu}}(D_{t})$, then
computes a matrix $\mathbf{X}_{t}$ given by the mirror descent step over the
set of density matrices $\Delta_{n\times
n}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\big{\\{}\mathbf{X}\succeq\mathbf{0}:\operatorname*{\textup{tr}}\mathbf{X}=1\big{\\}}$
using the Von Neumann entropy, $-\langle\mathbf{X},\log\mathbf{X}\rangle$, as
a regularizer. We summarize this update in update-embedding below.

Algorithm 2 update-embedding Parameters: Graph Laplacians
$\mathcal{L}_{\bm{\mu}}(D_{0}),\ldots,\mathcal{L}_{\bm{\mu}}(D_{t})$, and step
size $\eta>0$. Do: The following: 1. Compute the matrix multiplicative update:
$\mathbf{X}_{t}=\frac{\exp\big{(}-\eta\sum_{k=0}^{t}\mathcal{L}_{\bm{\mu}}(D_{k})\big{)}}{\operatorname*{\textup{tr}}\exp\big{(}-\eta\sum_{k=0}^{t}\mathcal{L}_{\bm{\mu}}(D_{k})\big{)}}$
Output: the matrix $\mathbf{X}_{t}$

It is important to note that our cut strategy ultimately does not use update-
embedding as an explicit computational step; if one hopes for a cut strategy
that runs in nearly-linear time, then the matrix exponential cannot be
computed in full dimension. Instead, we use fast matrix exponentiation
algorithms with Johnson–Lindenstrauss to compute the embedding given by low-
dimensional approximations of $\mathbf{X}_{t}\mathbf{u}$ for
$\mathbf{u}\in\mathbb{R}^{V}$ a unit vector. We describe this in more detail
when we summarize our cut strategy in section 5.2.4

Contextualizing this update using mirror descent is convenient for analytic
purposes: one can leverage regret bounds to lower bound the spectral gap, and
subsequently the expansion, of the certificate graph. The following is a
straightforward application of the regret bound given by Theorem 3.1 from [3].
Further exposition on mirror descent, and a full proof of the following lemma
are provided in Appendix C.1.

######  Lemma 7.

Let $T>0$, and $D_{1},\ldots,D_{T}$ be any sequence of $\epsilon$-approximate
matching actions. For each $t\in[T]$, suppose update-embedding outputs
$\mathbf{X}_{t}\in\Delta_{n\times n}$ when given the feedback matrices
$\mathcal{L}_{\bm{\mu}}(D_{0}),\ldots,\mathcal{L}_{\bm{\mu}}(D_{t})$. Finally,
consider the graph $H=\frac{1}{T}\sum_{t=1}^{T}D_{t}$. Then for any $\eta>0$,

$\lambda_{2}\big{(}\mathcal{L}_{\bm{\mu}}(H_{T})\big{)}\geq\frac{1-2\eta}{T}\sum_{t=1}^{T}\big{\langle}\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\big{\rangle}-\frac{\log
n}{T\eta}.$

Finally, we require a fact regarding the vector embedding whose Gram matrix is
the output of update-embedding. The following lemma determines where the
average embedding vector, and what the variance of the embedding is. Its proof
is also in Appendix C.1.

######  Lemma 8.

Suppose update-embedding outputs $\mathbf{X}_{t}$ when given the feedback
matrices $\mathcal{L}_{\bm{\mu}}(D_{0}),\ldots,\mathcal{L}_{\bm{\mu}}(D_{t})$.
If $\big{\\{}\mathbf{v}_{i}\big{\\}}_{i\in V}$ is the vector embedding whose
Gram matrix is $\mathbf{X}_{t}$, then the following hold:

  1. 1.

$\sum_{i\in V}\big{\lVert}\mathbf{v}_{i}\big{\rVert}^{2}=1$,

  2. 2.

$\sum_{i\in V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i}={\bf 0}$.

####  5.2.3 Rounding a robustly separated set

Recall that the cut player seeks to make the expansion of
$\sum_{t=1}^{T}D_{t}$ large, in as few rounds as possible. The regret bound
given by Lemma 7 implies that it suffices for the cut player to compute an
embedding such that the term
$\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle$ is large for each
$t$. It is illuminating to rewrite
$\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle$ using the vector
embedding whose Gram matrix is $\mathbf{X}_{t}$. Supposing that
$\mathbf{X}_{t}=\mathbf{V}_{t}\mathbf{V}_{t}^{\top}$ where the $i$-th row of
$\mathbf{V}_{t}$ is given by $\mathbf{v}_{i}$ for each $i\in V$, we have

$\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle=\langle\mathbf{L}(D_{t}),\mathbf{M}^{-1/2}\mathbf{V}_{t}\mathbf{V}_{t}^{\top}\mathbf{M}^{-1/2}\rangle=\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\bigg{\lVert}\frac{\mathbf{v}_{i}}{\sqrt{\mu_{i}}}-\frac{\mathbf{v}_{j}}{\sqrt{\mu_{j}}}\bigg{\rVert}_{2}^{2}\,.$
(6)

The term $\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle$ must be
large regardless of what $\epsilon$-approximate matching action is returned by
the matching strategy. Recall that our matching strategy is to output the
demand graph corresponding to a hypergraph flow computed from an
$\epsilon$-approximate solution to the ratio-cut improvement problem. Our cut
strategy must then output a cut such that, no matter what approximate flow the
matching player routes, $D$ will be forced to route a large amount of flow
between vertices whose embedding vectors are far apart.

If the cut player is not careful in choosing $S\subseteq V$, then $D$ being
the demand graph of an _approximate_ solution may, in the worst-case, possess
no flow routed between vertices whose embedding vectors are far in
$\ell_{2}^{2}$-distance. Our fix is to round a set $S$ such that a constant
fraction of the total flow routed across $S$ will route into another subset of
vertices $T\subseteq\overline{S}$ whose embedding vectors are well separated,
_independent_ of what $(1-\epsilon)$-fraction of vertices in $S$ possess flow
routed from it. We capture this property using a $(\sigma,c)$-robustly
separated set.

######  Definition 13 ($(\sigma,c)$-robustly separated set).

Let $\sigma,c>0$. We say $S\subseteq V$ is a $(\sigma,c)$_-robustly separated_
set with respect to a vector embedding $\\{\mathbf{v}_{i}\\}_{i\in
V}\subseteq\mathbb{R}^{d}$ if there exists $T\subseteq\overline{S}$ satisfying
the following conditions.

  1. 1.

$\bm{\mu}(T)\geq c\cdot\bm{\mu}(V)$.

  2. 2.

$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\frac{\sigma}{\bm{\mu}(S)}$
for all $i\in S$ and $j\in T$.

The rest of this section is devoted to demonstrating how to round a robustly
separated set from a vector embedding $\\{\mathbf{v}_{i}\\}_{i\in
V}\subseteq\mathbb{R}^{d}$. Before proceeding, we remark on how the embedding
is normalized. In light of the calculation in (6), we can focus our attention
on the vector embeddings of the form
$\hat{\mathbf{v}}_{i}=\frac{\mathbf{v}_{i}}{\sqrt{\mu_{i}}}$ where
$\mathbf{v}_{i}$ comes from update-embedding. Lemma 8 then implies that
$\hat{\mathbf{v}}_{\mathsf{avg}}={\bf 0}$, and
$\operatorname*{Var}_{\bm{\mu}}(\hat{\mathbf{v}}_{i})=\frac{1}{\bm{\mu}(V)}$.
Consequently, the statements in this section assume that
$\mathbf{v}_{\mathsf{avg}}={\bf 0}$, and
$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})=\frac{1}{\mu(V)}$.

Our algorithm for rounding a robustly separated set is split between two
cases: (1) when the vector embedding is _balanced_ , and (2) when it is
_unbalanced_. Given a $\\{\mathbf{v}_{i}\\}_{i\in V}$, we define the sweep cut
$R_{t}\subseteq V$

$R_{t}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\Big{\\{}i\in V:\lVert\mathbf{v}_{i}\rVert_{2}^{2}\leq
t\cdot\operatorname*{\mathbb{E}}_{i\sim\bm{\mu}}\big{[}\lVert\mathbf{v}_{i}\rVert_{2}^{2}\big{]}\Big{\\}}\,.$

We then say that an embedding is $(t,b)$-balanced if the variance due to
vertices in $R_{t}$ captures a $b$-fraction of the total embedding variance.

######  Definition 14 ($(t,b)$-Balanced Embedding).

Given $t>0$, and $b>0$, a vector embedding $\\{\mathbf{v}_{i}\\}_{i\in
V}\subseteq\mathbb{R}^{d}$ is $(t,b)$-_balanced_ if cut $R_{t}$ satisfies

$\frac{1}{\bm{\mu}(V)}\cdot\sum_{i,j\in\binom{R_{t}}{2}}\frac{\mu_{i}\mu_{j}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq
b\cdot\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})\,.$

We remark that, given $t$ and $b$, one can check if the embedding is
$(t,b)$-balanced in $O(nd)$ time by computing distances to the average vector
in $R_{t}$, and $V$.

Let us now describe our rounding algorithm round-cut summarized below. The
constants in what follows are chosen for convenience and could, otherwise, be
further optimized.

Algorithm 3 round-cut. Parameters: $d>0$, a vector embedding
$\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ such that
$\mathbf{v}_{\mathsf{avg}}={\bf 0}$, and
$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})=\frac{1}{\bm{\mu}(V)}$. Do:
the following 1. If $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ is
$\big{(}3,\frac{1}{10}\big{)}$-balanced, do the following. • Sample
$\mathbf{g}$ uniformly at random from $\mathcal{S}^{d-1}$. • Compute the
projections $r_{i}=\sqrt{d}\cdot\langle\mathbf{g},\mathbf{v}_{i}\rangle$ for
each $i\in V$. • Sort $r_{i}$. Assume without loss of generality that
$r_{1}\geq\ldots\geq r_{n}$ and define sweep cuts $S_{t}=\\{i\in V:r_{i}\geq
r_{t}\\}$ • Output $\big{(}S_{t},\overline{S_{t}}\big{)}$ such that
$\bm{\mu}(S_{t})\geq\frac{1}{3}\cdot\bm{\mu}(V)$ and
$\big{(}r_{t}-r_{t+1}\big{)}\geq\frac{r}{\bm{\mu}(V)}$ for the constant $r>0$
guaranteed by Lemma 19. 2. If $\\{\mathbf{v}_{i}\\}_{i\in
V}\subseteq\mathbb{R}^{d}$ is not $\big{(}3,\frac{1}{10}\big{)}$-balanced, do
the following. • Compute $\ell_{i}=\lVert\mathbf{v}_{i}\rVert_{2}^{2}$. • Sort
$\ell_{i}$. Assume without loss of generality that
$\ell_{1}\geq\ldots\geq\ell_{n}$ and define sweep cuts $S_{t}=\\{i\in
V:\ell_{i}\geq\ell_{t}\\}$ • Output $(S_{t},\overline{S_{t}})$ as guaranteed
by Lemma 10 Output: The cut $S_{t}\subseteq V$.

In the balanced case, $R_{3}$ captures a constant fraction of the vector
embedding’s variance. $R_{3}$, a set of short vectors, also captures a large
fraction of the total volume $\bm{\mu}(V)$ 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 are well separated from
one another. The balanced case analysis is thus very similar to the analysis
of SDP-based approximation algorithms for balanced separator. In fact, it is
simpler as one does not need to bound the conductance of such a cut. We leave
the proof of the following lemma to Appendix C.2.

######  Lemma 9.

Given $V=[n]$, let $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ be a
vector embedding satisfying $\mathbf{v}_{\mathsf{avg}}={\bf 0}$ and
$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})=\frac{1}{\bm{\mu}(V)}$. If
$\\{\mathbf{v}_{i}\\}_{i\in V}$ is $\big{(}3,\frac{1}{10}\big{)}$-balanced
embedding, then algorithm round-cut outputs $S$ that is
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated set with probability $1-o_{n}\big{(}\frac{1}{n}\big{)}$ over the
uniformly random choice of $\mathbf{g}\in\mathcal{S}^{d-1}$.

In the unbalanced case, $R_{3}$ fails to capture a constant fraction of the
variance. $R_{3}$ is a set of long vectors with small volume and so one might
hope that $R_{3}$ and $\overline{R_{3}}$ are already robustly separated.
However, this is not always the case as there may be many vertex pairs near
the defining threshold of $R_{3}$ whose embedding vectors are close to each
other. Routing an approximate flow may thus route only between such pairs
causing $\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle$ to be
small.

The key insight is that picking a smaller threshold, say $R_{3/2}$, and
performing a region growing argument demonstrates the existence of another
sweep cut $\overline{R_{t}}$ contained within $\overline{R_{3}}$ that is
robustly separated from $R_{3/2}$.

######  Lemma 10.

Given $V=[n]$, let $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ be a
vector embedding satisfying $\mathbf{v}_{\mathsf{avg}}={\bf 0}$ and
$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})=\frac{1}{\bm{\mu}(V)}$. If
$\\{\mathbf{v}_{i}\\}_{i\in V}$ is not
$\big{(}3,\frac{1}{10}\big{)}$-balanced, then round-cut deterministically
outputs a $\Big{(}\Omega\big{(}\frac{1}{\log
n}\big{)},\frac{1}{3}\Big{)}$-robustly separated set $S$.

###### Proof.

Fix $T=R_{3/2}$ where $R_{t}=\Big{\\{}i\in
V:\lVert\mathbf{v}_{i}\rVert_{2}^{2}\leq\frac{t}{\bm{\mu}(V)}\Big{\\}}$. We
first demonstrate that there exists an $S\subseteq\overline{R_{3}}$ that is
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated with respect to $T$. The first requirement for any
$S\subseteq\overline{R_{3}}$ to be a robustly separated,
$\bm{\mu}(T)\geq\frac{1}{3}\cdot\bm{\mu}(V)$, is satisfied since Markov’s
inequality dictates:

$\bm{\mu}(T)=\bm{\mu}(R_{3/2})\geq\bigg{(}1-\frac{1}{3/2}\bigg{)}\cdot\bm{\mu}(V)=\frac{1}{3}\cdot\bm{\mu}(V).$

All that remains to show is that there exists some $S$ where every $i\in S$,
$j\in T$ satisfies
$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\frac{\sigma}{\bm{\mu}(S)}$
for $\sigma\geq\Omega\big{(}\frac{1}{\log n}\big{)}$. Call such an $S$ valid.

We begin by making two observations. First, the average length of vectors in
$\overline{R_{3}}$ is at least as large as a constant. By Lemma 6, we have
that:

$\sum_{i\in\overline{R_{3}}}\frac{\mu_{i}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}\rVert_{2}^{2}\geq\frac{\bm{\mu}(R_{3})}{\bm{\mu}(V)}\bigg{(}\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})-\frac{1}{\bm{\mu}(V)}\cdot\sum_{i,j\in\binom{R_{3}}{2}}\frac{\mu_{i}\mu_{j}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\bigg{)}.$

By Markov’s inequality, we have that
$\frac{\bm{\mu}(R_{3})}{\bm{\mu}(V)}\geq\frac{2}{3}$. Furthermore, since the
vector embedding $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ is not
$\big{(}3,\frac{1}{10}\big{)}$-balanced, we have:

$\frac{1}{\bm{\mu}(V)}\cdot\sum_{i,j\in\binom{R_{3}}{2}}\frac{\mu_{i}\mu_{j}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}<\frac{1}{10}\cdot\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i}).$

Combining the three inequalities above, and using that
$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})=\frac{1}{\bm{\mu}(V)}$, we
derive:

$\sum_{i\in\overline{R_{3}}}\frac{\mu_{i}}{\bm{\mu}(V)}\cdot\lVert\mathbf{v}_{i}\rVert_{2}^{2}\geq\frac{2}{3}\cdot\bigg{(}1-\frac{1}{10}\bigg{)}\cdot\frac{1}{\bm{\mu}(V)}\qquad\Longleftrightarrow\qquad\sum_{i\in\overline{R_{3}}}\mu_{i}\cdot\lVert\mathbf{v}_{i}\rVert_{2}^{2}\geq\frac{3}{5}\,.$
(7)

Second, consider any $t\geq 3$, and note that not only
$\overline{R_{t}}\subseteq\overline{R_{3}}$, but also that we can lower bound
$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}$ for any
$i\in\overline{R_{t}}$ and $j\in T$ as follows. Since $i\in\overline{R_{t}}$,
we have $\lVert\mathbf{v}_{i}\rVert_{2}^{2}\geq\frac{t}{\bm{\mu}(V)}$.
Similarly as $j\in T$, we have
$\lVert\mathbf{v}_{j}\rVert_{2}^{2}\leq\frac{3/2}{\bm{\mu}(V)}$. Hence, the
triangle inequality implies:

$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}\geq\lVert\mathbf{v}_{i}\rVert_{2}-\lVert\mathbf{v}_{j}\rVert_{2}\geq\sqrt{\frac{t}{\bm{\mu}(V)}}-\sqrt{\frac{3/2}{\bm{\mu}(V)}}\qquad\Longleftrightarrow\qquad\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\frac{(\sqrt{t}-\sqrt{3/2})^{2}}{\bm{\mu}(V)}$
(8)

Now, fix $\sigma$, and for the sake of contradiction, suppose no valid
$S\subseteq\overline{R_{3}}$ exists. That is, for every
$S\subseteq\overline{R_{3}}$, there exists $i\in S,j\in T$ such that
$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}<\frac{\sigma}{\bm{\mu}(S)}$.
Since $\overline{R_{t}}\subseteq\overline{R_{3}}$ for every $t\geq 3$, this
implies

$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}<\frac{\sigma}{\bm{\mu}(\overline{R_{t}})}\,.$

for some $i\in\overline{R_{t}}$ and $j\in T$. However, inequality (8) holds
for every $t\geq 3$, $i\in\overline{R_{t}}$, and $j\in T$. Consequently,

$\frac{(\sqrt{t}-\sqrt{3/2})^{2}}{\bm{\mu}(V)}\leq\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}<\frac{\sigma}{\bm{\mu}(\overline{R_{t}})}\qquad\Longleftrightarrow\qquad\bm{\mu}(\overline{R_{t}})<\frac{\sigma}{(\sqrt{t}-\sqrt{3/2})^{2}}\cdot\bm{\mu}(V)\leq\frac{30\sigma}{\sqrt{t}}\cdot\bm{\mu}(V)$
(9)

where we use the fact that $(\sqrt{t}-\sqrt{3/2})^{2}\geq\frac{t}{30}$ for all
$t\geq 3$. Using this, we can strike the following upper bound on
$\sum_{i\in\overline{R_{3}}}\mu_{i}\cdot\lVert\mathbf{v}_{i}\rVert$. If we let
$M\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\max_{i\in
V}\big{\\{}\bm{\mu}(V)\cdot\lVert\mathbf{v}_{i}\rVert_{2}^{2}\big{\\}}$, then
we can write

$\displaystyle\sum_{i\in\overline{R_{3}}}\mu_{i}\cdot\lVert\mathbf{v}_{i}\rVert$
$\displaystyle=\frac{1}{\bm{\mu}(V)}\cdot\int_{3}^{M}\bm{\mu}(\overline{R_{t}})\,dt+\frac{3}{\bm{\mu}(V)}\cdot\bm{\mu}(\overline{R_{3}})$
$\displaystyle<30\sigma\cdot\bigg{(}\int_{3}^{M}\frac{1}{t}\,dt+\frac{1}{\sqrt{3}}\bigg{)}$
$\displaystyle=30\sigma\cdot\bigg{(}\ln\bigg{(}\frac{M}{3}\bigg{)}+\frac{1}{\sqrt{3}}\bigg{)}$

Because $\sum_{i\in V}\mu_{i}\cdot\lVert\mathbf{v}_{i}\rVert_{2}^{2}=1$, we
have $M\leq\max_{i\in
V}\,\big{\\{}\frac{\bm{\mu}(V)}{\mu_{i}}\big{\\}}\leq\mathsf{poly}(n)$.
Consequently,

$\sum_{i\in\overline{R_{3}}}\mu_{i}\cdot\lVert\mathbf{v}_{i}\rVert<\sigma\cdot
O(\log n)\,.$

However, inequality (7) implied that
$\sum_{i\in\overline{R_{3}}}\mu_{i}\cdot\lVert\mathbf{v}_{i}\rVert\geq\Omega(1)$
which reaches a contradiction unless $\sigma\geq\Omega\big{(}\frac{1}{\log
n}\big{)}$.

Consequently, there exists some $S\subseteq\overline{R_{3}}$ that is
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated from $T$. Furthermore, $S=\overline{R_{t}}$ for some $t\geq 3$, and
since round-cut step (2) searches through all of at most $n$ such cuts, we
conclude that round-cut outputs the required robustly separated set in the
unbalanced case. ∎

This section concludes with a lemma capturing both the fact that round-cut
produces a $\Big{(}\Omega\big{(}\frac{1}{\log
n}\big{)},\frac{1}{3}\Big{)}$-robustly separated set in all cases, and the
running time of round-cut.

######  Lemma 11.

Given $V=[n]$, let $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ be a
vector embedding satisfying $\mathbf{v}_{\mathsf{avg}}={\bf 0}$ and
$\operatorname*{Var}_{\bm{\mu}}(\mathbf{v}_{i})=\frac{1}{\bm{\mu}(V)}$. Then
round-cut outputs a $\Big{(}\Omega\big{(}\frac{1}{\log
n}\big{)},\frac{1}{3}\Big{)}$-robustly separated set $S$ with
$1-o_{n}\big{(}\frac{1}{n}\big{)}$ probability over the uniformly random
choice of $\mathbf{g}\in\mathcal{S}^{d-1}$. Furthermore, round-cut runs in
time $\tilde{O}(nd)$.

###### Proof.

If $\\{\mathbf{v}_{i}\\}_{i\in V}$ is $\big{(}3,\frac{1}{10}\big{)}$-balanced,
then Lemma 9 implies round-cut outputs a $\Big{(}\Omega\big{(}\frac{1}{\log
n}\big{)},\frac{1}{3}\Big{)}$-robustly separated set with probability
$1-o_{n}\big{(}\frac{1}{n}\big{)}$. Otherwise, Lemma 10 provides the same
guarantee deterministically.

To bound the running time, consider the following. Checking if the embedding
is balanced takes $O(nd)$ time. Computing $\ell_{2}^{2}$-distances and vector
projections takes $O(d)$ time per vector, of which there are $n$. Sorting
takes $\tilde{O}(n)$ time. There are at most $O(n)$ sweep cuts to check in
both the balanced and unbalanced case, and finding the appropriate cut in both
cases takes $O(1)$ time per cut. ∎

####  5.2.4 Completing the cut strategy

As alluded to in Section 5.2.2, the matrix exponential required to compute the
mirror descent update cannot be computed in full if one wants a nearly-linear
time algorithm. Here, we can take advantage of the fact that each feedback
matrix provided to mirror descent is given by the Laplacian of a sparse graph
$D_{t}$. So long as at most $\operatorname*{\textup{polylog}}(n)$ iterations
of mirror descent are required, the sum of all $D_{t}$, throughout the
lifetime of the algorithm, will remain sparse. We denote algorithm ExpV as
some generic algorithm that computes the matrix vector product
$\mathbf{X}_{t}\mathbf{u}$ for $\mathbf{u}$ some unit vector. One can find an
explicit description of this algorithm in Theorem 3.2 of [48] which takes
advantage of the Laplacian system solver of Spielman and Teng [54].

Next, we use Johnson–Lindenstrauss to project the embedding into
$O\big{(}\frac{\log n}{\delta^{2}}\big{)}$ dimensions for $\delta=O(1)$,

######  Lemma 12 (Johnson–Lindenstrauss).

Given an embedding $\\{\mathbf{v}_{i}\\}_{i\in V}\subseteq\mathbb{R}^{d}$ for
$V=[n]$, and $\delta>0$, let $k>\Omega\big{(}\frac{\log n}{\delta^{2}}\big{)}$
and $\mathbf{U}\in\mathbb{R}^{k\times d}$ be a matrix where the $i$-th row is
a vector sampled independently and uniformly from the $(n-1)$-dimensional
sphere of radius $\sqrt{\frac{n}{k}}$. Let
$\tilde{\mathbf{v}}_{i}=\mathbf{U}\mathbf{v}_{i}$ for each $i\in V$. With
probability $1-o_{n}\big{(}\frac{1}{n}\big{)}$, the following holds for all
$i,j\in V$:

$(1-\delta)\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert^{2}\leq\lVert\tilde{\mathbf{v}}_{i}-\tilde{\mathbf{v}}_{j}\rVert^{2}\leq(1+\delta)\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert^{2}\,.$

allowing us to compute $\ell_{2}^{2}$-distances and projections in logarithmic
time. Since the error is multiplicative in terms of pairwise
$\ell_{2}^{2}$-distances, picking $\delta$ to be constant only causes a
constant factor loss in the number of cut strategy plays, and the final
approximation ratio.

Once we compute the low-dimensional vector embedding, we use round-cut, to
produce a robustly separated set and output that as the cut strategy’s action.
This procedure is summarized in algorithm 5.2.4 $\mathcal{C}_{\textup{{MD}}}$.

Algorithm 4 $\mathcal{C}_{\textup{{MD}}}$. Parameters: $\epsilon$-approximate
matching actions $D_{0},\ldots,D_{t}$, step size $\eta>0$,
$1>\delta\geq\frac{1}{10}$. Do: The following. 1. Pick $d=O\big{(}\frac{\log
n}{\delta^{2}}\big{)}$ random unit vectors
$\mathbf{u}_{1},\ldots,\mathbf{u}_{d}\in\mathbb{R}^{V}$. 2. Denote
$\mathbf{X}_{t}$ as the matrix update specified in update-
embedding$\big{(}\mathcal{L}_{\bm{\mu}}(D_{0}),\ldots,\mathcal{L}_{\bm{\mu}}(D_{t}),\eta\big{)}$,
and use ExpV to compute embedding
$\big{\\{}\tilde{\mathbf{v}}_{i}\big{\\}}_{i\in V}$ given by
$\big{(}\tilde{\mathbf{v}}_{i}\big{)}_{j}=\sqrt{\frac{n}{d}}\cdot\langle\mathbf{X}_{t}\mathbf{u}_{j},\mathbf{e}_{i}\rangle\qquad\qquad\forall\,i\in
V\;j\in[d]$ 3. Scale the embedding
$\hat{\mathbf{v}}^{(t)}_{i}=\frac{\tilde{\mathbf{v}}^{(t)}_{i}}{\sqrt{\mu_{i}}}$
for each $i\in V$. 4. Execute round-
cut$\big{(}d,\big{\\{}\hat{\mathbf{v}}^{(t)}_{i}\big{\\}}_{i\in V}\big{)}$ to
produce the cut $S_{t}\subseteq V$. Output: The cut $S_{t}$.

Let us proceed with the analysis. First, we demonstrate that returning a
robustly separated set forces
$\langle\mathcal{L}_{\bm{\mu}}(D),\mathbf{X}\rangle$ to be large for any
$\epsilon$-approximate matching action $D$.

######  Lemma 13.

Let $S\subseteq V$ be a $\big{(}\sigma,c\big{)}$-robustly separated set with
respect to a vector embedding $\\{\mathbf{v}_{i}\\}_{i\in
V}\subseteq\mathbb{R}^{d}$. For any $\epsilon>0$, if
$D=\big{(}S\cup\overline{S},E_{D},\mathbf{w}^{D}\big{)}$ is an
$\epsilon$-approximate matching action with respect to $S$, then

$\sum_{i\in
S,j\in\overline{S}}w_{ij}^{D}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\sigma\cdot\bigg{(}\frac{1}{3}-4\epsilon\bigg{)}\,.$

###### Proof.

Since $S\subseteq V$ is $\big{(}\sigma,c\big{)}$-robustly separated, there
exists $T\subseteq\overline{S}$ such that $\bm{\mu}(T)\geq c\cdot\bm{\mu}(V)$
and
$\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\frac{\sigma}{\bm{\mu}(S)}$
for all $i\in S$ and $j\in T$. Thus we can bound

$\sum_{i\in
S,j\in\overline{S}}w_{ij}^{D}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\sum_{i\in
S,j\in
T}w_{ij}^{D}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\frac{\sigma}{\bm{\mu}(S)}\cdot\sum_{i\in
S,j\in T}w_{ij}^{D}\,.$ (10)

Observing that $D$ is bipartite between $(S,\overline{S})$, we have

$\sum_{i\in S,j\in T}w_{ij}^{D}=\sum_{i\in
S}\deg_{i}(D)-\sum_{i\in\overline{S}\setminus T}\deg_{i}(D)\,.$ (11)

Now we can lower bound the first term in the RHS of (11) like so. Notice that

$\sum_{i\in S}\big{(}\mu_{i}\cdot\lvert
s_{i}\rvert-\deg_{i}(D)\big{)}\leq\sum_{i\in S}\big{\lvert}\mu_{i}\cdot\lvert
s_{i}\rvert-\deg_{i}(D)\big{\rvert}\leq\lVert\bm{\mu}\circ\lvert\mathbf{s}\rvert-\mathbf{d}\rVert_{1}\leq\epsilon\cdot\lVert\mathbf{s}\rVert_{1,\bm{\mu}},$

where the last inequality follows as $D$ is an $\epsilon$-approximate matching
action. Consequently,

$\sum_{i\in S}\deg_{i}(D)\geq\sum_{i\in S}\mu_{i}\cdot\lvert
s_{i}\rvert-\epsilon\cdot\lVert\mathbf{s}\rVert_{1,\bm{\mu}}=\bm{\mu}(S)-2\epsilon\cdot\bm{\mu}(S)\,.$
(12)

Meanwhile, the second term in the RHS of (11) can be upper bounded via the
following.

$\sum_{i\in\overline{S}\setminus T}\big{(}\deg_{i}(D)-\mu_{i}\cdot\lvert
s_{i}\rvert\big{)}\leq\sum_{i\in\overline{S}\setminus
T}\big{\lvert}\deg_{i}(D)-\mu_{i}\cdot\lvert
s_{i}\rvert\big{\rvert}\leq\big{\lVert}\mathbf{d}-\big{(}\bm{\mu}\circ\lvert\mathbf{s}\rvert\big{)}\big{\rVert}_{1}\leq\epsilon\cdot\lVert\mathbf{s}\rVert_{1,\bm{\mu}}$

where the last inequality again comes from $D$ being an $\epsilon$-approximate
matching action. Re-arranging gives

$\sum_{i\in\overline{S}\setminus
T}\deg_{i}(D)\leq\sum_{i\in\overline{S}\setminus T}\mu_{i}\cdot\lvert
s_{i}\rvert+\epsilon\cdot\lVert\mathbf{s}\rVert_{1,\bm{\mu}}=\frac{\bm{\mu}(S)}{\bm{\mu}(\overline{S})}\cdot\bm{\mu}\big{(}\overline{S}\setminus
T\big{)}+2\epsilon\cdot\bm{\mu}(S)\leq\frac{2}{3}\cdot\bm{\mu}(S)+2\epsilon\cdot\bm{\mu}(S)\,.$
(13)

The last inequality comes from the fact that
$\bm{\mu}(T)\geq\frac{1}{3}\cdot\bm{\mu}(V)\geq\frac{1}{3}\bm{\mu}(\overline{S})$,
and the fact that $T\subseteq\overline{S}$ and hence
$\bm{\mu}(\overline{S}\setminus T)=\bm{\mu}(\overline{S})-\bm{\mu}(T)$.
Substituting inequalities (12) and (13) into (11) then implies

$\sum_{i\in S,j\in
T}w_{ij}^{D}\geq\bigg{(}\frac{1}{3}-4\epsilon\bigg{)}\cdot\bm{\mu}(S)\,.$

Inequality (10) then reduces to:

$\sum_{i\in
S,j\in\overline{S}}w_{ij}^{D}\cdot\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\geq\sigma\cdot\bigg{(}\frac{1}{3}-4\epsilon\bigg{)}$

as required. ∎

Using Lemma 13 to analyze the regret bound in Lemma 7 yields a proof a main
theorem, Theorem 10.

###### Proof of Theorem 10.

Let $T=g(n)$, and suppose $\mathcal{C}_{\textup{{MD}}}$ plays the cuts
$S_{1},\ldots,S_{T}$. Consider any sequence of weighted graphs
$D_{1},\ldots,D_{T}$ such that $D_{t}$ is an $\epsilon$-approximate matching
action with respect to $S_{t}$ for each $t=1,\ldots,T$. Define
$\mathcal{E}_{t}$ to be the event where the following occurs in iteration $t$:

  1. 1.

the random projection in step (2) of $\mathcal{C}_{\textup{{MD}}}$ produces an
embedding satisfying the Johnson–Lindenstrauss error bounds, and

  2. 2.

calling round-cut in step (4) of $\mathcal{C}_{\textup{{MD}}}$ produces a
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated set.

First, we prove that if $\mathcal{E}_{t}$ occur jointly over all
$t=1,\ldots,T$, then $\mathcal{C}_{\textup{{MD}}}$ is an $\Big{(}\Omega(\log
n),\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}\Big{)}$-good cut strategy. For
the graph $H=\sum_{t=1}^{T}D_{t}$, Lemma 7 implies the lower bound on the
spectral gap of $\frac{1}{T}H$

$\lambda_{2}\Big{(}\mathcal{L}_{\bm{\mu}}\big{(}\tfrac{1}{T}\cdot
H\big{)}\Big{)}\geq\frac{1-2\eta}{T}\sum_{t=1}^{T}\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle-\frac{\log
n}{T\eta}\,.$

Let us now consider the $t$-th cut played by $\mathcal{C}_{\textup{{MD}}}$.
Suppose $\mathbf{X}_{t}$, the matrix update specified by step (2) in
$\mathcal{C}_{\textup{{MD}}}$, is also the Gram matrix of an embedding
$\big{\\{}\mathbf{v}^{(t)}_{i}\big{\\}}_{i\in V}$. Denote $\mathbf{V}_{t}$ to
be the matrix whose $i$-th row is $\mathbf{v}^{(t)}_{i}$. We can then write
$\mathbf{X}_{t}=\mathbf{V}_{t}\mathbf{V}_{t}^{\top}$ and hence

$\langle\mathcal{L}_{\bm{\mu}}(D_{t}),\mathbf{X}_{t}\rangle=\langle\mathbf{L}(D_{t}),\mathbf{M}^{-1/2}\mathbf{V}_{t}\mathbf{V}_{t}^{\top}\mathbf{M}^{-1/2}\rangle=\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\bigg{\lVert}\frac{\mathbf{v}_{i}}{\sqrt{\mu_{i}}}-\frac{\mathbf{v}_{j}}{\sqrt{\mu_{j}}}\bigg{\rVert}_{2}^{2}.$

Using Lemma 12, we have

$\displaystyle\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\bigg{\lVert}\frac{\mathbf{v}_{i}}{\sqrt{\mu_{i}}}-\frac{\mathbf{v}_{j}}{\sqrt{\mu_{j}}}\bigg{\rVert}_{2}^{2}$
$\displaystyle\geq\frac{1}{1+\delta}\cdot\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\bigg{\lVert}\frac{\tilde{\mathbf{v}}_{i}}{\sqrt{\mu_{i}}}-\frac{\tilde{\mathbf{v}}_{j}}{\sqrt{\mu_{j}}}\bigg{\rVert}_{2}^{2}$
$\displaystyle=\frac{1}{1+\delta}\cdot\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\big{\lVert}\hat{\mathbf{v}}_{i}-\hat{\mathbf{v}}_{j}\big{\rVert}_{2}^{2}\geq\frac{1}{2}\cdot\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\big{\lVert}\hat{\mathbf{v}}_{i}-\hat{\mathbf{v}}_{j}\big{\rVert}_{2}^{2}\,.$

with the last inequality following as $\delta<1$. Focusing on the embedding
$\\{\hat{\mathbf{v}}_{i}\\}_{i\in V}$, note that it satisfies

$\sum_{i\in
V}\frac{\mu_{i}}{\bm{\mu}(V)}\cdot\lVert\hat{\mathbf{v}}_{i}\rVert_{2}^{2}=\frac{1}{\bm{\mu}(V)}\sum_{i\in
V}\cdot\lVert\hat{\mathbf{v}}_{i}\rVert_{2}^{2}=\frac{1}{\bm{\mu}(V)}$

where the last equality follows by Lemma 8 item (1). Furthermore,

$\sum_{i\in V}\mu_{i}\cdot\hat{\mathbf{v}}_{i}=\sum_{i\in
V}\sqrt{\mu_{i}}\cdot\mathbf{v}_{i}={\bf 0}$

where the last equality follows by Lemma 8 item (2). Consequently, the
embedding that is passed into round-cut in iteration $t$ is centered
appropriately. Lemma 11 then implies that round-cutand
$\mathcal{C}_{\textup{{MD}}}$ output $S_{t}\subseteq V$ that is
$\Big{(}\Omega\big{(}\frac{1}{\log n}\big{)},\frac{1}{3}\Big{)}$-robustly
separated with respect to $\\{\hat{\mathbf{v}}_{i}\\}_{i\in V}$. Lemma 13 then
implies

$\frac{1}{2}\cdot\sum_{\\{i,j\\}\in
E_{D_{t}}}w^{D_{t}}_{ij}\cdot\big{\lVert}\hat{\mathbf{v}}_{i}-\hat{\mathbf{v}}_{j}\big{\rVert}_{2}^{2}=\frac{1}{2}\cdot\sum_{i\in
S,j\in\overline{S}}w^{D_{t}}_{ij}\cdot\big{\lVert}\hat{\mathbf{v}}_{i}-\hat{\mathbf{v}}_{j}\big{\rVert}_{2}^{2}\geq\Omega\bigg{(}\frac{1}{\log
n}\bigg{)}\cdot\bigg{(}\frac{1-12\epsilon}{6}\bigg{)}=\Omega\bigg{(}\frac{1-\epsilon}{\log
n}\bigg{)}.$

Returning to our regret bound, this implies that there exists an absolute
constant $C>0$ such that

$\lambda_{2}\Big{(}\mathcal{L}_{\bm{\mu}}\big{(}\tfrac{1}{T}\cdot
H\big{)}\Big{)}\geq\frac{1-2\eta}{T}\sum_{t=1}^{T}C\cdot\frac{1-\epsilon}{\log
n}-\frac{\log n}{T\eta}=C\cdot(1-2\eta)\cdot\frac{1-\epsilon}{\log
n}-\frac{\log n}{T\eta}.$

Choosing $\eta=\sqrt{\frac{\log^{2}n}{2C\cdot T\cdot(1-\epsilon)}}$ and
$T=\frac{32}{C}\cdot\frac{\log^{2}n}{1-\epsilon}$, we derive:

$\lambda_{2}\Big{(}\mathcal{L}_{\bm{\mu}}\big{(}\tfrac{1}{T}\cdot
H\big{)}\Big{)}\geq\frac{C}{2}\cdot\frac{1-\epsilon}{\log n}.$

This implies the following bound on the spectral gap of $H$:

$\lambda_{2}\big{(}\mathcal{L}_{\bm{\mu}}(H)\big{)}\geq
T\cdot\frac{C}{2}\cdot\frac{1-\epsilon}{\log n}=16\cdot\log n=\Omega(\log n).$

Finally, Cheeger’s inequality implies
$\Psi_{H}\geq\frac{\lambda_{2}(\mathcal{L}_{\bm{\mu}}(H))}{2}\geq\Omega(\log
n)$ hence $\mathcal{C}_{\textup{{MD}}}$ is a $\Big{(}\Omega(\log
n),O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}\Big{)}$-good cut strategy as
required.

Now, to show that $\mathcal{C}_{\textup{{MD}}}$ is a $\Big{(}\Omega(\log
n),O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}\Big{)}$-good cut strategy with
probability $1-o_{n}(1)$, note that $\mathcal{C}_{\textup{{MD}}}$ requires at
most $O\big{(}\frac{\log^{2}n}{1-\epsilon}\big{)}$ iterations. By Lemma 12,
the random projection step fails to satisfy the requisite error bound with
probability smaller than $o_{n}\big{(}\frac{1}{n}\big{)}$, while by Lemma 9
states that round-cut fails to output a $\Big{(}\Omega\big{(}\frac{1}{\log
n}\big{)},\frac{1}{3}\Big{)}$-robustly separated set in the balanced case with
probability smaller than $o_{n}\big{(}\frac{1}{n}\big{)}$. Performing a union
bound over all iterations of $\mathcal{C}_{\textup{{MD}}}$ implies
$\mathcal{C}_{\textup{{MD}}}$ is a good cut strategy with $1-o_{n}(1)$
probability. ∎

##  6 An $O\big{(}\sqrt{\log n}\big{)}$-Approximation via Metric Embeddings

Finally, we prove Theorem 4: there exists a polynomial time randomized
$O\big{(}\sqrt{\log n}\big{)}$-approximation algorithm for the minimum ratio-
cut problem over hypergraphs.

We begin by constructing a convex relaxation of the minimum ratio-cut problem
that embeds the vertex set $V$ into a metric space of negative type. Recall
that a metric space $(\mathcal{X},d)$ is said to be of negative type if there
exists a function $f:\mathcal{X}\to\mathbb{R}^{n}$ such that:

$d(x,y)=\|f(x)-f(y)\|_{2}^{2}\,.$

Given a weighted hypergraph $G=(V,E,\mathbf{w},\bm{\mu})$ equipped with mscfs
$\\{\delta_{h}\\}_{h\in E}$, we define two types of variables:

  1. 1.

_Embedding variables_ – the program assigns a vector variable
$\mathbf{v}_{i}\in\mathbb{R}^{n}$ to each vertex $i\in V$. Each
$\mathbf{v}_{i}$ represents the position of $i$ embedded into the metric space
$(\mathbb{R}^{n},\|.\|^{2}_{2})$.

  2. 2.

_Length variables_ – the program also assigns a vector variable
$\bm{\ell}^{h}\in\mathbb{R}^{h}$ to each hyperedge $h\in E$. The coordinates
$\ell^{h}_{i}$ can be interpreted as giving a length to the edge $\\{i,h\\}$
in the factor graph representation $\hat{G}$ of $G$.

Given a weighted submodular hypergraph $G=(V,E,\mathbf{w},\bm{\mu})$, we
consider the following convex program:

$\displaystyle\underset{\mathbf{v}_{i},\bm{\ell}^{h}}{\min}$
$\displaystyle\sum_{h\in E}w_{h}\cdot\|\bm{\ell}^{h}\|_{F_{h}}$ (RC-Metric)
s.t. $\displaystyle\sum_{\\{i,j\\}\subseteq
V}{\mu_{i}\mu_{j}\over\mu(V)}\cdot\|\mathbf{v}_{i}-\mathbf{v}_{j}\|_{2}^{2}\geq
1$ $\displaystyle\|\mathbf{v}_{i}-\mathbf{v}_{j}\|_{2}^{2}\leq\sum_{(u,h,w)\in
p}\bm{\ell}^{h}_{u}+\bm{\ell}^{h}_{w}$
$\displaystyle\forall\,\\{i,j\\}\in\binom{V}{2},\forall\,p\in\mathcal{P}_{ij}(G)$
$\displaystyle\|\mathbf{v}_{i}-\mathbf{v}_{j}\|^{2}_{2}\leq\|\mathbf{v}_{i}-\mathbf{v}_{k}\|_{2}^{2}+\|\mathbf{v}_{k}-\mathbf{v}_{j}\|_{2}^{2}$
$\displaystyle\forall\,i,j,k\in V$
$\displaystyle\mathbf{v}_{i}\in\mathbb{R}^{n},\bm{\ell}^{h}\in\mathbb{R}^{h}$
$\displaystyle\forall\,i\in V,\,\forall\,h\in E$

Here, $\mathcal{P}_{ij}$ is the set of all paths in the factor graph
$\hat{G}$. We note that even though the number of paths is exponential, the
program has an equivalent characterization with a polynomial number of
constraints. This is obtained by replacing the set of constraints

$\displaystyle\|\mathbf{v}_{i}-\mathbf{v}_{j}\|_{2}^{2}\leq\sum_{(u,h,w)\in
p}\bm{\ell}^{h}_{u}+\bm{\ell}^{h}_{w}$ $\displaystyle\hskip
28.45274pt\forall\,\\{i,j\\}\in\binom{V}{2},\forall\,p\in\mathcal{P}_{ij}(G)$

with

$\displaystyle\lVert\mathbf{v}_{i}-\mathbf{v}_{j}\rVert_{2}^{2}\leq\bm{\ell}_{i}^{h}+\bm{\ell}_{j}^{h}\hskip
28.45274pt\forall h\in E,\forall\\{i,j\\}\in\binom{h}{2}\,,$

which are equivalent whenever the triangle inequality constraints are
enforced.

The vector constraints can alternatively be represented as positive
semidefinite constraints using the Gram matrix of the vector embedding
$\\{\mathbf{v}_{i}\\}_{i\in V}$. The program (RC-Metric) is, up to a constant
factor, a relaxation of the minimum ratio cut problem, as expressed in the
following theorem. This is proved in Appendix D.

######  Theorem 11.

The (RC-Metric) vector program is, up to a constant, a relaxation of the
minimum ratio-cut program for the hypergraph
$G=\big{(}V,E,\mathbf{w},\bm{\mu}\big{)}$ with mscfs $\\{\delta_{h}\\}_{h\in
E}.$

###  6.1 Rounding the Metric Embedding Relaxation

The crucial property we rely on for rounding the program is that any feasible
set of vectors $\\{\mathbf{v}_{i}\\}_{i\in V}$ produces a metric of negative
type. Our argument then uses the following theorem from [7], which guarantees
the existence of an efficient algorithm to embed a metric of negative type
onto $\mathbb{R}$. This version of the theorem is given by Feige, Hajiaghayi
and Lee [25].

######  Theorem 12 (Theorem 3.3 from [25] ).

If $(\mathcal{X},d)$ is a $n$-point metric space of negative type
$d:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$, then for every product weight
$\omega_{0}:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{+}$ there exists an
efficiently computable $1$-Lipschitz444Recall that, given a metric space
$(X,d)$, a function $f:X\to\mathbb{R}$ is said to be $K$-Lipschitz for some
constant $K$ if $|f(x)-f(y)|\leq K\cdot d(x,y)$ for every $x,y\in X$. map
$\phi:\mathcal{X}\to\mathbb{R}$ satisfying:

$\frac{\sum_{\mathbf{x},\mathbf{y}\in\mathcal{X}}\omega_{0}(\mathbf{x},\mathbf{y})\cdot
d(\mathbf{x},\mathbf{y})}{\sum_{\mathbf{x},\mathbf{y}\in\mathcal{X}}\omega_{0}(\mathbf{x},\mathbf{y})\cdot|\phi(\mathbf{x})-\phi(\mathbf{y})|}=O\big{(}\sqrt{\log
n}\big{)}$

Before analyzing our rounding algorithm , we require a technical lemma that is
proved Appendix D.

######  Lemma 14.

Let $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ be such that $\mathbf{y}\geq 0$
and $|x_{i}-x_{j}|\leq y_{i}+y_{j}$ for all ${i,j}\subseteq[n]$. Then, there
exists some $\nu\in\mathbb{R}$ such that, for every $i\in[n]$:

$\lvert x_{i}-\nu\rvert\leq y_{i}\,.$

Let us now show the main theorem of this section: rounding the convex program
(RC-Metric) produces a $O(\sqrt{\log n})$-approximation for finding the
minimum ratio-cut of a hypergraph.

######  Theorem 13.

There is a polynomial-time algorithm that, given an optimal solution
$\big{(}\\{\bm{\ell}^{h}\\}_{h\in E},\\{\mathbf{v}_{i}\\}_{i\in V}\big{)}$ to
(RC-Metric) with objective value
$\mathsf{opt}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\sum_{h\in E}w_{h}\cdot\|\bm{\ell}^{h}\|_{F_{h}}$, returns a cut
$S\subseteq V$ such that

$\Psi_{G}(S)\leq\mathsf{opt}\cdot O\big{(}\sqrt{\log n}\big{)}\,.$

###### Proof.

The vectors $\\{\mathbf{v}_{i}\\}$ form a metric space of negative type.
Hence, we can efficiently find an embedding $\phi:\\{\mathbf{v}_{i}\\}_{i\in
V}\to\mathbb{R}$ with the guarantees of Theorem 12, where $\omega_{0}$ is
taken to be:

$\omega_{0}(i,j)={\mu_{i}\mu_{j}\over\mu(V)}\,.$

Let $\mathbf{x}\in\mathbb{R}^{n}$ be the vector given by
$x_{i}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\phi(\mathbf{v}_{i})$. Since $\big{(}\\{\bm{\ell}^{h}\\}_{h\in
E},\\{\mathbf{v}_{i}\\}_{i\in V}\big{)}$ is feasible, $1$-lipschitzness of
$\phi$ guarantees:

$\lvert\phi(\mathbf{v}_{i})-\phi(\mathbf{v}_{j})\rvert=|x_{i}-x_{j}|\leq\ell_{i}^{h}+\ell_{j}^{h}\,.$

Hence, by Lemma 14, for every hyperedge $h\in E$, there exists some choice of
$\nu_{h}\in\mathbb{R}$, such that:

$(\mathbf{x}-\nu_{h}\boldsymbol{1})_{i}\leq\ell^{h}_{i}\,,$

for every $i\in V$. By the monotonicity of the $\|.\|_{F_{h}}$ norm (Fact 6),
we have:

$\sum_{h\in
E}w_{h}\cdot\min_{\nu\in\mathbb{R}}\|\mathbf{x}-\nu\boldsymbol{1}\|_{F_{h}}\leq\sum_{h\in
E}w_{h}\cdot\|\mathbf{x}-\nu_{h}\boldsymbol{1}\|_{F_{h}}\leq\sum_{h\in
E}w_{h}\cdot\|\bm{\ell}^{h}\|_{F_{h}}=\mathsf{opt}\,.$ (15)

We now proceed to obtain a lower bound on the denominator of the objective.
Begin by choosing

$\gamma^{*}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle
def}}}{{=}}\operatorname{argmin}_{\gamma\in\mathbb{R}}\|\mathbf{x}-\gamma\boldsymbol{1}\|_{1,\bm{\mu}}$

and let $\hat{\mathbf{x}}:=\mathbf{x}-\gamma^{*}\boldsymbol{1}$. We can write
the denominator as the expectation of $\lvert\hat{x}_{i}\rvert$ where $i\in V$
are sampled randomly with probability proportional to $\bm{\mu}$ like so.

${\min_{\gamma\in\mathbb{R}}\|\mathbf{x}-\boldsymbol{1}\gamma\|_{1,\bm{\mu}}}=\|\hat{\mathbf{x}}\|_{1,\bm{\mu}}=\mu(V)\operatorname*{\mathbb{E}}_{i\sim\bm{\mu}}[|\hat{x}_{i}|]$

Notice $\operatorname*{\mathbb{E}}_{i\sim\bm{\mu}}[|\hat{x}_{i}|]$ can then be
bounded below by the following inequality:

$\mu(V)\operatorname*{\mathbb{E}}_{i\sim\bm{\mu}}[|\hat{x}_{i}|]=\frac{\mu(V)}{2}\cdot\Big{(}\operatorname*{\mathbb{E}}_{i\sim\bm{\mu}}[|\hat{x}_{i}|]+\operatorname*{\mathbb{E}}_{j\sim\bm{\mu}}[|\hat{x}_{j}|]\Big{)}=\frac{\mu(V)}{2}\cdot\operatorname*{\mathbb{E}}_{i,j\sim\bm{\mu}\times\bm{\mu}}[|\hat{x_{i}}|+|\hat{x_{j}}|]\geq\frac{\mu(V)}{2}\cdot\operatorname*{\mathbb{E}}_{i,j\sim\bm{\mu}\times\bm{\mu}}[|\hat{x_{i}}-\hat{x_{j}}|].$

This expectation evaluates to:

$\frac{\mu(V)}{2}\cdot\operatorname*{\mathbb{E}}_{i,j\sim\bm{\mu}\times\bm{\mu}}[|\hat{x_{i}}-\hat{x_{j}}|]={1\over
2}{\sum_{i,j\in
V}{\mu_{i}\mu_{j}\over\mu(V)}\cdot|\hat{x_{i}}-\hat{x_{j}}|}={1\over
2}{\sum_{i,j\in V}{\mu_{i}\mu_{j}\over\mu(V)}\cdot|x_{i}-x_{j}|}\,.$

Consequently, the above calculation gives the following bound.

${\min_{\gamma\in\mathbb{R}}\|\mathbf{x}-\boldsymbol{1}\gamma\|_{1,\bm{\mu}}}\geq{1\over
2}{\sum_{i,j\in V}{\mu_{i}\mu_{j}\over\mu(V)}\cdot|x_{i}-x_{j}|}\geq
O\left({1\over\sqrt{\log n}}\right){\sum_{i,j\in
V}{\mu_{i}\mu_{j}\over\mu(V)}\|\mathbf{v}_{i}-\mathbf{v}_{j}\|^{2}_{2}}\geq
O\left({1\over\sqrt{\log n}}\right)$ (16)

Finally, Theorem 5, together with Equations (15) and (16), yields:

${\sum_{h\in
E}w_{h}\bar{\delta}_{h}(\mathbf{x})\over\min_{\gamma\in\mathbb{R}}\|\mathbf{x}-\gamma\boldsymbol{1}\|_{1,\bm{\mu}}}\leq
2\cdot{\sum_{h\in E}w_{h}\min_{\nu\in\mathbb{R}}\|\mathbf{x}-\nu
1\|_{F_{h}}\over\min_{\gamma\in\mathbb{R}}\|\mathbf{x}-\gamma\boldsymbol{1}\|_{1,\bm{\mu}}}\leq\mathsf{opt}\cdot
O\big{(}\sqrt{\log n}\big{)}\,.$

The vector $\mathbf{x}$ can then be efficiently rounded to a subset
$S\subseteq V$ with:

$\Psi_{G}(S)\leq{\sum_{h\in
E}w_{h}\bar{\delta}_{h}(\mathbf{x})\over\min_{\gamma\in\mathbb{R}}\|\mathbf{x}-\gamma\boldsymbol{1}\|_{1,\bm{\mu}}}\,,$

as per Lemma 1. ∎

##  7 Acknowledgements

AC is supported by NSF DGE 1746045. AC would like to thank Luca Trevisan for
his support while visiting Bocconi University; part of this work was completed
while AC was a visiting student at Bocconi. LO is supported by NSF CAREER
1943510. The authors would like to thank Jeffrey Negrea for assisting on
topics related to online learning.

## References

  * [1] Sameer Agarwal, Kristin Branson, and Serge Belongie.  Higher order learning with graphs.  In Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, pages 17–24, New York, NY, USA, June 2006\. Association for Computing Machinery.
  * [2] Ahuja, Ravindra K and Magnanti, Thomas L and Orlin, James B.  Network Flows: Theory, Algorithms, and Applications.  Prentice Hall, 1993.
  * [3] 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.
  * [4] Noga Alon and Vitali D Milman.  Eigenvalues, expanders and superconcentrators.  In 25th Annual Symposium onFoundations of Computer Science, 1984., pages 320–322. IEEE, 1984.
  * [5] 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.
  * [6] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of computing, 8(1):121–164, 2012.
  * [7] Sanjeev Arora, Satish Rao, and Umesh Vazirani.  Expander flows, geometric embeddings and graph partitioning.  Journal of the ACM, 56(2):5:1–5:37, April 2009.
  * [8] Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Adrian Vladu.  Decomposable Submodular Function Minimization via Maximum Flow.  In Proceedings of the 38th International Conference on Machine Learning, pages 446–456. PMLR, July 2021.
  * [9] Francis Bach.  Learning with Submodular Functions: A Convex Optimization Perspective, October 2013.
  * [10] Wenruo Bai, Rishabh Iyer, Kai Wei, and Jeff Bilmes.  Algorithms for Optimizing the Ratio of Submodular Functions.  In Proceedings of The 33rd International Conference on Machine Learning, pages 2751–2759. PMLR, June 2016.
  * [11] F. L. Bauer, J. Stoer, and C. Witzgall.  Absolute and monotonic norms.  Numerische Mathematik, 3(1):257–264, December 1961.
  * [12] 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.
  * [13] U.V. Catalyurek and C. Aykanat.  Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication.  IEEE Transactions on Parallel and Distributed Systems, 10(7):673–693, July 1999.
  * [14] T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang.  Spectral Properties of Hypergraph Laplacian and Approximation Algorithms.  arXiv:1605.01483 [cs], May 2016.
  * [15] 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.
  * [16] Chandra Chekuri and Alina Ene.  Poly-logarithmic approximation for maximum node disjoint paths with constant congestion.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 326–341. SIAM, 2013.
  * [17] Chandra Chekuri, Alina Ene, and Marcin Pilipczuk.  Constant congestion routing of symmetric demands in planar directed graphs.  SIAM Journal on Discrete Mathematics, 32(3):2134–2160, 2018.
  * [18] 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, April 2022.
  * [19] 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, April 2022.
  * [20] Julia Chuzhoy.  Routing in undirected graphs with constant congestion.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 855–874, 2012.
  * [21] 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.
  * [22] 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.
  * [23] K.D. Devine, E.G. Boman, R.T. Heaphy, R.H. Bisseling, and U.V. Catalyurek.  Parallel hypergraph partitioning for scientific computing.  In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, pages 10 pp.–, April 2006.
  * [24] Alina Ene, Huy L. Nguyen, and László A. Végh.  Decomposable Submodular Function Minimization: Discrete and Continuous, March 2017.
  * [25] Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee.  Improved approximation algorithms for minimum-weight vertex separators.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 563–572, 2005.
  * [26] Elad Hazan et al.  Introduction to online convex optimization.  Foundations and Trends® in Optimization, 2(3-4):157–325, 2016.
  * [27] Shohei Hidaka and Masafumi Oizumi.  Fast and exact search for the partition with minimal information loss.  PLOS ONE, 13(9):e0201126, September 2018.
  * [28] Rania Ibrahim and David F. Gleich.  Local hypergraph clustering using capacity releasing diffusion.  PLOS ONE, 15(12):e0243485, December 2020.
  * [29] Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian.  Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent, July 2021.
  * [30] 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, November 2020.
  * [31] 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.
  * [32] Rohit Khandekar, Satish Rao, and Umesh Vazirani.  Graph partitioning using single commodity flows.  Journal of the ACM, 56(4):19:1–19:15, July 2009.