tcb@breakable

# Lower Bounds on $0$-Extension with Steiner Nodes

Yu Chen EPFL, Lausanne, Switzerland. Email<EMAIL_ADDRESS>Supported by ERC
Starting Grant 759471. Zihan Tan Rutgers University, NJ, USA. Email:
<EMAIL_ADDRESS>Supported by a grant to DIMACS from the Simons
Foundation (820931).

In the _$0$ -Extension problem_, we are given an edge-weighted graph
$G=(V,E,c)$, a set $T\subseteq V$ of its vertices called terminals, and a
semi-metric $D$ over $T$, and the goal is to find an assignment $f$ of each
non-terminal vertex to a terminal, minimizing the sum, over all edges
$(u,v)\in E$, the product of the edge weight $c(u,v)$ and the distance
$D(f(u),f(v))$ between the terminals that $u,v$ are mapped to. Current best
approximation algorithms on $0$-Extension are based on rounding a linear
programming relaxation called the _semi-metric LP relaxation_. The integrality
gap of this LP, with best upper bound $O(\log|T|/\log\log|T|)$ and best lower
bound $\Omega((\log|T|)^{2/3})$, has been shown to be closely related to the
best quality of cut and flow vertex sparsifiers.

We study a variant of the $0$-Extension problem where Steiner vertices are
allowed. Specifically, we focus on the integrality gap of the same semi-metric
LP relaxation to this new problem. Following from previous work, this new
integrality gap turns out to be closely related to the quality achievable by
cut/flow vertex sparsifiers with Steiner nodes, a major open problem in graph
compression. Our main result is that the new integrality gap stays
superconstant $\Omega(\log\log|T|)$ even if we allow a super-linear
$O(|T|\log^{1-\varepsilon}|T|)$ number of Steiner nodes.

##  1 Introduction

In the _$0$ -Extension_ problem ($0$-Ext), we are given an undirected edge-
weighted graph $G=(V,E,c)$, a set $T\subseteq V$ of its vertices called
_terminals_ , and a metric $D$ on terminals, and the goal is to find a mapping
$f:V\to T$ that maps each vertex to a terminal in $T$, such that each terminal
is mapped to itself (i.e., $f(t)=t$ for all $t\in T$), and the sum
$\sum_{(u,v)\in E}c{(u,v)}\cdot D(f(u),f(v))$ is minimized.

The $0$-Ext problem was first introduced by Karzanov [Kar98]. It is a
generalization of the _multi-way cut_ problem (by setting $D(t,t^{\prime})=1$
for all pairs $t,t^{\prime}\in T$) [DJP+94, CKR98, FK00, BNS13, AMM17, BSW17,
BCKM20], and a special case of the _metric labeling_ problem [KT02, CKNZ04,
AFH+04, KKMR06, CN07]. Călinescu, Karloff and Rabani [CKR05] gave the first
approximation algorithm for $0$-Ext, achieving a ratio of $O(\log|T|)$, by
rounding the solution of a _semi-metric LP relaxation_ (LP-Metric), which is
presented below.

(LP-Metric) $\displaystyle\text{minimize}\quad\sum_{(u,v)\in
E}c(u,v)\cdot\delta(u,v)$ $\displaystyle s.t.\quad(V,\delta)\text{ is a semi-
metric space}$ $\displaystyle\delta(t,t^{\prime})=D(t,t^{\prime}),\quad\forall
t,t^{\prime}\in T$

Fakcharoenphol, Harrelson, Rao and Talwar [FHRT03] later gave a modified
rounding algorithm on the same LP, improving the ratio to
$O(\log|T|/\log\log|T|)$, which is the current best-known approximation. On
the other hand, this LP was shown to have integrality gap
$\Omega(\sqrt{\log|T|})$ [CKR05], and this was recently improved to
$\Omega((\log|T|)^{2/3})$ by Schwartz and Tur [ST21]. Another LP relaxation
called _earthmover distance relaxation_ (LP-EMD) was considered by Chekuri,
Khanna, Naor and Zosin [CKNZ04] and utilized to obtain an
$O(\log|T|)$-approximation of the metric labeling problem (and therefore also
the $0$-Ext problem). It has been shown [KKMR09] by Karloff, Khot, Mehta and
Rabani that this LP relaxation has an integrality gap
$\Omega(\sqrt{\log|T|})$. Manokaran, Naor, Raghavendra and Schwartz [MNRS08]
showed that the integrality gap of this LP relaxation leads to the same
hardness of approximation result, assuming the Unique Game Conjecture.

In addition to being an important problem on its own, the $0$-Ext problem and
its two LP relaxations are also closely related to the construction of
_cut/flow vertex sparsifiers_ , a central problem in the paradigm of graph
compression. Given a graph $G$ and a set $T\subseteq V(G)$ of terminals, a cut
sparsifier of $G$ with respect to $T$ is a graph $H$ with $V(H)=T$, such that
for every partition $(T_{1},T_{2})$ of $T$, the size of the minimum cut
separating $T_{1}$ from $T_{2}$ in $G$ and the size of the minimum cut
separating $T_{1}$ from $T_{2}$ in $H$, are within some small factor $q$,
which is also called the _quality_ of the sparsifier111flow sparsifiers has a
slightly more technical definition, which can be found in [HKNR98, LM10,
Chu12, AGK14].. Moitra [Moi09] first showed that every graph with $k$
terminals admits a cut sparsifier with quality bounded by the _integrality
gap_ of its LP-Metric (hence $O(\log k/\log\log k)$). Later on, Leighton and
Moitra [LM10], and Makarychev and Makarychev [MM10] concurrently obtained the
same results for flow sparsifiers, and then Charikar, Leighton, Li and Moitra
[CLLM10] showed that the best flow sparsifiers can be computed by solving an
LP similar to LP-EMD. On the lower bound side, it was shown after a line of
work [LM10, CLLM10, MM10] that there exist graphs with $k$ terminals whose
best flow sparsifier has quality $\tilde{\Omega}(\sqrt{\log k})$.

A major open question on vertex sparsifiers is:

<EMAIL_ADDRESS>Can better quality sparsifiers be achieved by
allowing a small number of Steiner vertices}?$

In other words, what if we no longer require that the sparsifier $H$ only
contain terminals, but just require that $H$ contain all terminals and its
size be bounded by some function $f$ on the number of terminals (for example,
$f(k)=2k,k^{2}$ or even $2^{k}$)? Chuzhoy [Chu12] constructed $O(1)$-quality
cut/flow sparsifiers with size dependent on the number of terminal-incident
edges in $G$. Andoni, Gupta and Krauthgamer [AGK14] showed the construction
for $(1+{\varepsilon})$-quality flow sparsifiers for quasi-bipartite graphs.
For general graphs, they constructed a sketch of size $f(k,{\varepsilon})$
that stores all feasible multicommodity flows up to a factor of
$(1+{\varepsilon})$, raising the hope for a special type of
$(1+{\varepsilon})$-quality flow sparsifier, called contraction-based flow
sparsifiers, of size $f(k,{\varepsilon})$ for general graphs, which was
recently invalidated by Chen and Tan [CT24], who showed that contraction-based
flow sparsifiers whose size are bounded by any function $f(k)$ must have
quality $1+\Omega(1)$. But it is still possible for such flow sparsifiers with
constant quality and finite size to exist. Prior to this work, Krauthgamer and
Mosenzon [KM23] showed that there exist $6$-terminal graphs $G$ whose
quality-$1$ flow sparsifiers must have an arbitrarily large size.

Given the concrete connection between the $0$-Ext problem and cut/flow
sparsifiers, it is natural to ask a similar question for $0$-Ext:

Q2. Can better approximation of $0$-Ext be achieved by allowing a small number
of Steiner vertices?

In this paper, we formulate and study the following variant of the $0$-Ext
problem, which we call the _0-Extension with Steiner Nodes_ problem
($\mathsf{0EwSN}$). (We note that a similar variant was mentioned in [AGK14],
and we provide a comparison between them in more detail in Appendix A.)
Upfront we are also given a function $f:\mathbb{Z}\to\mathbb{Z}$ with
$f(k)\geq k$ holds for all $k\in\mathbb{Z}$, specifying the number of Steiner
vertices allowed.

##### 0-Extension with Steiner Nodes.

In an instance of $\mathsf{0EwSN}(f)$, the input consists of an edge-weighted
graph $G=(V,E,c)$, a subset $T\subseteq V$ of $k$ vertices, that we call
_terminals_ , and a metric $D$ on terminals in $T$, which is exactly the same
as $0$-Ext. A solution to the instance $(G,T,D)$ consists of

  * •

a partition ${\mathcal{F}}$ of $V$ with $|{\mathcal{F}}|\leq f(k)$, such that
distinct terminals of $T$ belong to different sets in ${\mathcal{F}}$; we call
sets in ${\mathcal{F}}$ _clusters_ , and for each vertex $u\in V$, we denote
by $F(u)$ the cluster in ${\mathcal{F}}$ that contains it;

  * •

a semi-metric $\delta$ on the clusters in ${\mathcal{F}}$, such that for each
pair $t,t^{\prime}\in T$, $\delta(F(t),F(t^{\prime}))=D(t,t^{\prime})$.

We define the _cost_ of a solution $({\mathcal{F}},\delta)$ as
$\mathsf{cost}({\mathcal{F}},\delta)=\sum_{(u,v)\in
E}c(u,v)\cdot\delta(F(u),F(v))$, and its _size_ as $|{\mathcal{F}}|$. The goal
is to compute a solution $({\mathcal{F}},\delta)$ with size at most $f(k)$ and
minimum cost.

The difference between $\mathsf{0EwSN}(f)$ and $0$-Ext is that, instead of
enforcing every vertex to be mapped to a terminal, in $\mathsf{0EwSN}(f)$ we
allow vertices to be mapped $(f(k)-k)$ non-terminals (or Steiner nodes), which
are the clusters in ${\mathcal{F}}$ that do not contain terminals. We are also
allowed to manipulate the distances between these non-terminals, conditioned
on not destroying the induced metric $D$ on terminals. Clearly, when $f(k)=k$,
the $\mathsf{0EwSN}(f)$ problem degenerates to the $0$-Ext problem.

It is easy to see that (LP-Metric) is still an LP relaxation for
$\mathsf{0EwSN}(f)$, as each solution $({\mathcal{F}},\delta)$ to
$\mathsf{0EwSN}$ naturally corresponds to a semi-metric $\delta^{\prime}$ on
$V$ (where we can set
$\delta^{\prime}(u,u^{\prime})=\delta(F(u),F(u^{\prime}))$ for all pairs
$u,u^{\prime}\in V$). Denote by $\textsf{IG}_{f}(k)$ the worst integrality gap
for (LP-Metric) to any $\mathsf{0EwSN}(f)$ instance with at most $k$
terminals. In fact, similar to the connection between the integrality gap of
(LP-Metric) and the quality achievable by flow sparsifiers [Moi09, LM10], it
was recently shown by Chen and Tan [CT24] that the value of
$\textsf{IG}_{f}(k)$ is also closely related to the quality achievable by flow
sparsifiers with Steiner nodes. Specifically, for any function $f$, every
graph $G$ with $k$ terminals has a
quality-$\big{(}(1+{\varepsilon})\cdot\textsf{IG}_{f}(k)\big{)}$ flow
sparsifier with size bounded by $(f(k))^{(\log k/{\varepsilon})^{k^{2}}}$.
This means that any positive answer to question Q2 (by proving that
$\textsf{IG}_{f}(k)=o(\log k/\log\log k)$ for some $f$) also gives a positive
answer to question Q1.

This makes it tempting to study the $\mathsf{0EwSN}$ problem. Specifically,
can we prove any better-than-$O(\log k/\log\log k)$ upper bound for
$\textsf{IG}_{f}(k)$, for any function $f$? To the best of our knowledge, no
such bound is known for any $f$, leaving the problem wide open. In fact, no
non-trivial lower bound on $\textsf{IG}_{f}(k)$ is known for even very small
function like $f(k)=O(k)$.

###  1.1 Our Results

In this paper, we make a first step in investigating the value of
$\textsf{IG}_{f}(k)$, by giving a superconstant lower bound on
$\textsf{IG}_{f}(k)$ for near-linear functions $f$. Our main result is
summarized in the following theorem.

######  Theorem 1.1.

For any $0<{\varepsilon}<1$ and any size function
$f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ with $f(k)=O(k\log^{1-{\varepsilon}}k)$,
the integrality gap of the LP-relaxation (LP-Metric) is
$\textnormal{{IG}}_{f}(k)=\Omega({\varepsilon}\log\log k)$.

We remark that our lower bound for the integrality gap of $\mathsf{0EwSN}(f)$
does not imply a size lower bound for $O(\log\log k)$-quality flow
sparsifiers. However, if the same lower bound can be proved for a slightly
generalized version of $\mathsf{0EwSN}(f)$, that was proposed in [AGK14] and
analyzed in [CT24], then it will imply an $\Omega(k\log^{1-{\varepsilon}}k)$
size lower bound for $O(\log\log k)$-quality flow sparsifiers. We provide a
detailed discussion in Appendix A.

###  1.2 Technical Overview

We now discuss some high-level ideas in the proof of Theorem 1.1. Given any
$k$, we will construct an unweighted graph $G$ on $n$ vertices (where
$n\approx k\log k$) and $k$ terminals, and show that any solution of the
$\mathsf{0EwSN}$ problem with size $O(k\log^{1-{\varepsilon}}k)$ has cost
lower bounded by $\Omega(\log\log k)$ times the number of edges in $G$.

Our hard instance is a constant degree expander (with an arbitrary set of its
$k$ vertices as terminals). There are two main reasons to choose such a graph.
First, in the previous work [CKR05] for proving the $\Omega(\sqrt{\log k})$
integrality gap lower bound for the $0$-Extension problem, an graph called
“expander with tails” has been used. Though the tails in their construction
appear useless for our purpose, as we allow a super-linear number of Steiner
vertices which easily accomodate a single-edge tail for each terminal, the
expander graph turns out to be still the core structure that is hard to
compress. Second, in another previous work [AFH+04] it was shown that
$0$-Extension problem on minor-free graphs has integrality gap $O(1)$, so our
hard example has to contain large cliques as minor, which makes expanders, the
graphs with richest structure, a favorable choice. For technical reasons, we
need some additional properties like Hamiltonian and high-girth. See Section
3.1 for more details.

Next we want to lower bound the cost of an $\mathsf{0EwSN}$ solution of size
$O(k\log^{1-{\varepsilon}}k)$. This is done in two steps. We first consider a
special type of solutions that really “comes from the graph”. Recall that a
solution consists of a partition ${\mathcal{F}}$ of $V(G)$ into clusters and a
metric $\delta$ on clusters in ${\mathcal{F}}$. Specifically, in this special
type of solutions, we require that each cluster $F\in{\mathcal{F}}$
corresponds to a distinct vertex $v_{F}$ (called its _center_) in $G$, and for
all pairs $F,F^{\prime}$ the metric $\delta(F,F^{\prime})$ coincides with the
shortest-path distance between $v_{F},v_{F^{\prime}}$ in $G$. In the first
step, we show that all special solutions have cost
$\Omega(n\cdot{\varepsilon}\log\log k)$. Intuitively, as the graph is a
constant degree expander, every center $v_{F}$ is within distance
$({\varepsilon}/100)\cdot\log\log k$ to at most $(\log k)^{{\varepsilon}/10}$
other centers, but its cluster $F$ contains $(\log k)^{{\varepsilon}}$
vertices on average and so it has $\Omega((\log k)^{{\varepsilon}})$ inter-
cluster edges. Therefore, most edges will have new length at least
$({\varepsilon}/100)\cdot\log\log k$ (in $\delta$), making the total new edge
length $\Omega(n\cdot{\varepsilon}\log\log k)$ (as the number of inter-cluster
edges in a balanced expander partition is $\Omega(n)$). Careful calculations
are needed to turn these informal arguments into a rigorous proof. See Section
3.2 for more details.

In the second step, we show that the general solutions can actually be reduced
to the special type of solutions considered in the first step, losing only an
$O(1)$ factor in its cost. In fact, it has been recently shown in [CT24] that,
to analyze the cost of any $\mathsf{0EwSN}$ instance, it suffices to consider
$\mathsf{0EwSN}$ solutions whose metric $\delta$ is embeddable into a geodesic
structure of the terminal-induced shortest path distance metric called _tight
span_. Our main contribution here, on a conceptual level, is showing that _for
a graph with high girth, its tight span structure locally coincides with the
graph structure itself_. In this sense, we can compare any solution to some
special solution considered in Step 1. When the picture is lifted to the
global level, in such a comparison it turns out that we will loss a factor
approximately the _diameter-girth ratio_ , which we can manage to get $O(1)$
with an additional short-cycle-removing step in the construction of the
expander. We believe this diameter-girth ratio quantifies how “local” a graph
structure is, and should be of independent interest to other graph problems on
shortest-path distances. To carry out the technical steps, we employ a notion
called _continuazation_ of a graph recently studied in [CT23]. See Section 3.3
for more details.

##  2 Preliminaries

By default, all logarithms are to the base of $2$.

Let $G=(V,E,\ell)$ be an edge-weighted graph, where each edge $e\in E$ has
weight (or _length_) $\ell_{e}$. For a vertex $v\in V$, we denote by
$\textrm{deg}_{G}(v)$ the degree of $v$ in $G$. For each pair $S,T\subseteq V$
of disjoint subsets, we denote by $E_{G}(S,T)$ the set of edges in $G$ with
one endpoint in $S$ the other endpoint in $T$. For a pair $v,v^{\prime}$ of
vertices in $G$, we denote by $\textnormal{{dist}}_{G}(v,v^{\prime})$ (or
$\textnormal{{dist}}_{\ell}(v,v^{\prime})$) the shortest-path distance between
$v$ and $v^{\prime}$ in $G$. We define the _diameter_ of $G$ as
$\textnormal{{diam}}(G)=\max_{v,v^{\prime}\in
V}\left\\{\textnormal{{dist}}_{G}(v,v^{\prime})\right\\}$, and we define the
_girth_ of $G$, denoted by $\textnormal{{girth}}(G)$, as the minimum weight of
any cycle in $G$. We may omit the subscript $G$ in the above notations when
the graph is clear from the context.

Given a graph $G$, its _conductance_ is defined as

$\Phi(G)=\min_{S\subseteq V,S\neq\emptyset,S\neq
V}\left\\{\frac{|E_{G}(S,V\setminus S)|}{\min\left\\{\sum_{v\in
S}\textrm{deg}_{G}(v),\sum_{v\notin S}\textrm{deg}_{G}(v)\right\\}}\right\\}.$

We say that $G$ is a _$\phi$ -expander_ iff $\Phi(G)\geq\phi$.

##  3 Proof of Theorem 1.1

In this section we prove Theorem 1.1. We begin by describing the hard instance
in Section 3.1, which is essentially a high-girth expander with a subset of
vertices designated as terminals. Then in Section 3.2 we show that a special
type of solutions may not have small cost. Finally, in Section 3.3 we
generalize the arguments in Section 3.2 to analyze an arbitrary solution,
completing the proof of Theorem 1.1. Some technical details in Section 3.3 are
deferred to Section 3.4.

###  3.1 The Hard Instance

Let $k$ be a sufficiently large integer. Let $n>k$ be an integer such that
$k=\left\lceil\frac{n\log\log n}{\log n}\right\rceil$. Let $V$ be a set of $n$
vertices. Let $\Sigma$ be the set of all permutations on $V$. For a
permutation $\sigma\in\Sigma$, we define its corresponding edge set
$E_{\sigma}=\left\\{(v,\sigma(v))\mid v\in V\right\\}$.

We now define the hard instance $(G,T,D)$. Graph $G$ is constructed in two
steps. In the first step, we construct an auxiliary graph $G^{\prime}$. Its
vertex set is $V$. Its edge set is obtained as follows. We sample three
permutations $\sigma_{1},\sigma_{2},\sigma_{3}$ uniformly at random from
$\Sigma$, and then let $E(G^{\prime})=E_{\sigma_{1}}\cup E_{\sigma_{2}}\cup
E_{\sigma_{3}}$. In the second step, we remove all short cycles in
$G^{\prime}$ to obtain $G$. Specifically, we first compute a breath-first-
search tree $\tau$ starting from an arbitrary vertex of $G^{\prime}$. We then
iteratively modify $G^{\prime}$ as follows. While $G^{\prime}$ contains a
cycle $C$ of length at most $(\log n)/100$, we find an edge of
$C\setminus\tau$ (note that such an edge must exist, as $\tau$ is a tree), and
remove it from $G^{\prime}$. We continue until $G^{\prime}$ no longer contains
cycles of length at most $(\log n)/100$. We denote by $G$ the resulting graph.
The terminal set $T$ is an arbitrary subset of $V$ with size $k$. For each
edge $e\in E(G)$, its weight $c(e)$ is defined to be $1$, and its _length_
$\ell_{e}$ is also defined to be $1$. The metric $D$ on the set $T$ of
terminals is simply defined to be the shortest-path distance (in $G$) metric
on $T$ induced by edge length $\left\\{\ell_{e}\right\\}_{e\in E(G)}$.

We next show some basic properties of the graphs $G^{\prime}$ and $G$. We
start with the following observation.

######  Observation 3.1.

$G^{\prime}$ is a $6$-regular graph, so $|E(G)|\leq|E(G^{\prime})|\leq 3n$.

######  Observation 3.2.

$\textnormal{{girth}}(G)\geq(\log n)/100$.

######  Observation 3.3.

The probability that $|E(G^{\prime})\setminus E(G)|\geq n^{0.3}$ is at most
$O(n^{-0.2})$.

###### Proof.

Let $v_{1},\ldots,v_{L}$ be a sequence of $L\leq(\log n)/100$ distinct
vertices of $V$. We now show that the probability that the cycle
$(v_{1},\ldots,v_{L},v_{1})$ exists in $E(G^{\prime})$ is at most
$\big{(}6/(n-L)\big{)}^{L}$. Indeed, to realize the cycle edge
$(v_{i},v_{i+1}$, for some $\ell\in\\{1,2,3\\}$,
$\sigma_{\ell}(v_{i})=v_{i+1}$ or $\sigma_{\ell}(v_{i+1}=v_{i}$, where for
convenience we say $v_{L+1}=v_{1}$. There are $6$ possible events. In order to
form the cycle, we need to form $L$ edges, and each edge has $6$ possible
events, which means there are at most $6^{L}$ ways to form the cycle in total.
Consider any possible way, we have $\ell_{1}\dots,\ell_{L}\in\\{1,2,3\\}$ and
$j_{1},\dots,j_{L}\in\\{0,1\\}$ such that for any index $1\leq i\leq L$, we
have $\sigma_{\ell_{i}}(v_{i+j_{i}})=v_{i+1-j_{i}}$. Let $\mathcal{E}_{i}$
denote this event, we have
$\Pr[\mathcal{E}_{i}|\mathcal{E}_{1},\dots,\mathcal{E}_{i-1}]\leq 1/(n-i)$.
Thus the probability that all events $\mathcal{E}_{i}$ happen is at most
$1/(n-L)^{L}$. Applying union bound on all the ways to form the cycle, the
probability that the cycle exists in $E(G^{\prime})$ is at most
$\big{(}6/(n-L)\big{)}^{L}$.

Therefore, the expected number of cycles in $G^{\prime}$ with length at most
$(\log n)/100$ is at most

$\sum_{3\leq L\leq(\log
n)/100}\frac{n(n-1)\cdots(n-L+1)}{2L\cdot\big{(}\frac{n-L}{6}\big{)}^{L}}\leq\sum_{3\leq
L\leq(\log
n)/100}\frac{6^{L}}{2L}\cdot\bigg{(}1+\frac{L}{n-L}\bigg{)}^{L}\leq\sum_{3\leq
L\leq(\log n)/100}6^{L}\leq n^{0.1}.$

Note that we delete at most one edge per each cycle, so
$|E(G^{\prime})\setminus E(G)|$ is less than the number of cycles in
$G^{\prime}$ with length at most $(\log n)/100$. Therefore, from Markov Bound,
the observation follows. ∎

We use the following previous results on the conductance and the Hamiltonicity
of $G^{\prime}$.

######  Lemma 3.4 ([Pud15]).

With probability $1-o(1)$, $\Phi(G^{\prime})=\Omega(1)$.

######  Corollary 3.5.

With probability $1-o(1)$, the diameter of $G$ is at most $O(\log n)$.

###### Proof.

From the construction of $G$, $G$ contains a BFS tree of $G^{\prime}$, so the
diameter of $G$ is at most twice the diameter of $G^{\prime}$. Therefore, it
suffices to show that, if $\Phi(G^{\prime})\geq\Omega(1)$, then the diameter
of graph $G^{\prime}$ is at most $O(\log n)$, which we do next.

Let $v$ be an arbitrary vertex of $G^{\prime}$. For each integer $t$, we
define the set
$B_{t}=\left\\{v^{\prime}\mid\textnormal{{dist}}(v,v^{\prime})\leq
t\right\\}$, and
$\alpha_{t}=\sum_{v^{\prime}:\textnormal{{dist}}_{G^{\prime}}(v,v^{\prime})\leq
t}\textrm{deg}(v^{\prime})$, namely the sum of degrees of all vertices in
$B_{t}$.

Denote $t^{*}=\max\left\\{t\mid\alpha_{t}\leq|E(G^{\prime})|\right\\}$. Note
that, for each $1\leq t\leq t^{*}$, as $\Phi(G^{\prime})\geq\Omega(1)$,
$|E(B_{t},V\setminus B_{t})|\geq\Omega(\alpha_{t})$. Therefore,

$\alpha_{t+1}\geq\alpha_{t}+\sum_{v^{\prime}\in B_{t+1}\setminus
B_{t}}\textrm{deg}(v)\geq\alpha_{t}+|E(B_{t},V\setminus
B_{t})|\geq\alpha_{t}\cdot(1+\Omega(1)).$

It follows that $t^{*}\leq O(\log n)$. Therefore, for any pair
$v,v^{\prime}\in V$, the set of vertices that are at distance at most
$t^{*}+1$ from $v$ must intersect the set of vertices that are at distance at
most $t^{*}+1$ from $v^{\prime}$, as otherwise the sum of degrees in all
vertices in these two sets is greater than $2|E(G^{\prime})|$, a
contradiction. Consequently, the diameter of $G^{\prime}$ is at most
$2t^{*}+2\leq O(\log n)$. ∎

######  Lemma 3.6 ([Fri01]).

With probability $1-o(1)$, the subgraph of $G^{\prime}$ induced by edges of
$E_{\sigma_{1}}\cup E_{\sigma_{2}}$ is Hamiltonian.

Now if we consider the semi-metric LP relaxation (LP-Metric) of this instance
$(G,T,D)$, then clearly the graph itself gives a solution $\delta$ to (LP-
Metric). Specifically,
$\delta(u,u^{\prime})=\textnormal{{dist}}_{\ell}(u,u^{\prime})$, where
$\textnormal{{dist}}_{\ell}(\cdot,\cdot)$ the shortest-path (in $G$) distance
metric on $V$ induced by the lengths $\\{\ell_{e}\\}_{e\in E(G)}$. Such a
solution has cost $|E(G)|=O(n)$ (as all edges have weight $c(e)=1$).
Therefore, in order to prove Theorem 1.1, it suffices to show that any
solution $({\mathcal{F}},\delta)$ with size $O(k\log^{1-{\varepsilon}}k)$ has
cost at least $\Omega({\varepsilon}n\log\log n)=\Omega({\varepsilon}n\log\log
k)$.

Observe that, the graph $G$ constructed above is essentially a bounded-degree
high-girth expander, which is similar to the hard instance used in [LM10] for
proving the $\Omega(\log\log k)$ quality lower bound for flow vertex
sparsifier (without Steiner nodes). However, our proof in the following
subsections takes a completely different approach from the approach in [LM10].

###  3.2 Proof of Theorem 1.1 for a Special Class of Solutions

In this subsection, we prove the cost lower bound for a special type of
solutions to the $\mathsf{0EwSN}(f)$ instance $(G,T,D)$. Specifically, we only
consider the solutions $({\mathcal{F}},\delta)$ such that

  * •

each cluster $F\in{\mathcal{F}}$ corresponds to a distinct vertex of $V$, and
for each terminal $t\in T$, the unique cluster $F\in{\mathcal{F}}$ that
contains $t$ corresponds to $t$; and

  * •

for each pair $F,F^{\prime}$ of clusters in ${\mathcal{F}}$, if we denote by
$v$ ($v^{\prime}$, resp.) the vertex that cluster $F$ ($F^{\prime}$, resp.)
corresponds to, then
$\delta(F,F^{\prime})=\textnormal{{dist}}_{G}(v,v^{\prime})$.

We call such solutions _canonical solutions_. In this subsection, we show
that, with high probability, any canonical solution of size
$o(n/\log^{{\varepsilon}}n)$ has cost $\Omega({\varepsilon}n\log\log n)$.

Consider now a canonical solution $({\mathcal{F}},\delta)$ to the instance.
For each cluster $F\in{\mathcal{F}}$, we denote by $v(F)$ the vertex in $V$
that it corresponds to, and we call $v(F)$ the _center_ of $F$ (note however
that $v(F)$ does not necessarily lie in $F$). We say that $F\in{\mathcal{F}}$
is _large_ iff $|F|\geq n^{0.1}$, otherwise we say it is _small_. We
distinguish between the following cases, depending on the total size of large
clusters.

#### Case 1: The total size of large clusters is at most $0.1n$

Recall that $\mathsf{cost}({\mathcal{F}},\delta)=\sum_{(u,u^{\prime})\in
E(G)}\delta(F(u),F(u^{\prime}))$, where $F(u)$ ($F(u^{\prime})$, resp.) is the
unique cluster in ${\mathcal{F}}$ that contains $u$ ($u^{\prime}$, resp.). We
call $\delta(F(u),F(u^{\prime}))$ the _contribution_ of edge $(u,u^{\prime})$
to the cost $\mathsf{cost}({\mathcal{F}},\delta)$. As the solution
$({\mathcal{F}},\delta)$ is canonical,

$\delta(F(u),F(u^{\prime}))=\textnormal{{dist}}_{G}(v(F(u)),v(F(u^{\prime}))\geq\textnormal{{dist}}_{G^{\prime}}(v(F(u)),v(F(u^{\prime})),$

as $G$ is obtained from $G^{\prime}$ by only deleting edges. We say that a
pair $F,F^{\prime}$ of clusters are _friends_ (denoted as $F\sim F^{\prime}$),
iff
$\textnormal{{dist}}_{G^{\prime}}(v(F),v(F^{\prime}))\leq{\varepsilon}\log\log
n/30$. We say that an edge $(u,u^{\prime})$ is _unfriendly_ , iff the pair of
clusters that contain $u$ and $u^{\prime}$ are not friends. Therefore, in
order to show
$\mathsf{cost}({\mathcal{F}},\delta)=\Omega({\varepsilon}n\log\log n)$, it
suffices to show that there are $\Omega(n)$ unfriendly edges in $G^{\prime}$.
This is since graph $G$ is obtained from $G^{\prime}$ by deleting at most
$n^{0.3}$ edges, so there are $\Omega(n)$ edges contributing at least
${\varepsilon}\log\log n$ each to $\mathsf{cost}({\mathcal{F}},\delta)$. Note
that, as $G$ is a $6$-regular graph, each cluster is a friend to at most
$6^{{\varepsilon}\log\log n/30}<\log^{{\varepsilon}/10}n$ clusters in
${\mathcal{F}}$.

The following lemma completes the proof in this case.

######  Lemma 3.7.

With probability $1-o(1)$, the random graph $G^{\prime}$ satisfies that, for
any partition ${\mathcal{F}}$ of $V$ into $|{\mathcal{F}}|\leq
O(n/\log^{{\varepsilon}}n)$ clusters such that $\sum_{|F|\geq n^{0.1}}|F|\leq
0.1n$, and for any friendship relation on ${\mathcal{F}}$ in which each
cluster $F$ is a friend to at most $\log^{0.1{\varepsilon}}n$ other clusters,
$G^{\prime}$ contains at least $n/10$ unfriendly edges, i.e., $\sum_{F\not\sim
F^{\prime}}|E_{G^{\prime}}(F,F^{\prime})|\geq n/10$.

###### Proof.

Recall that $G^{\prime}$ is obtained by sampling three random permutations
$\sigma_{1},\sigma_{2},\sigma_{3}$ from $\Sigma$ and taking the union of their
corresponding edge sets $E_{\sigma_{1}},E_{\sigma_{2}},E_{\sigma_{3}}$. We
alternatively view $G^{\prime}$ as constructed in two steps. In the first
step, we obtain a graph $\hat{G}$ by sampling two random permutations
$\sigma_{1},\sigma_{2}$ from $\Sigma$ and letting
$\hat{G}=(V,E_{\sigma_{1}}\cup E_{\sigma_{2}})$. In the second step, we sample
a third permutation $\sigma_{3}$ from $\Sigma$ and let
$G^{\prime}=(V,E(\hat{G})\cup E_{\sigma_{3}})$. From Lemma 3.6, with high
probability, $\hat{G}$ contains a Hamiltonian cycle on $V$.

For convenience, we denote by $({\mathcal{F}},\sim)$ a pair of clustering
${\mathcal{F}}$ and the friendship relation on clusters of ${\mathcal{F}}$. We
say that the pair $({\mathcal{F}},\sim)$ is _valid_ , iff $|{\mathcal{F}}|\leq
O(n/\log^{{\varepsilon}}n)$, $\sum_{|F|\geq n^{0.1}}|F|\leq 0.1n$, and each
cluster $F$ is a friend to at most $\log^{{\varepsilon}/10}n$ other clusters.

######  Claim 3.8.

For any Hamiltonian cycle $C$ on $V$, there are at most $n^{n/4}$ valid pairs
$({\mathcal{F}},\sim)$ satisfying that $\sum_{F\not\sim
F^{\prime}}|E_{C}(F,F^{\prime})|<n/10$.

###### Proof.

Denote $L=c^{*}n/\log^{{\varepsilon}}n$, and let
${\mathcal{F}}=\left\\{F_{1},\ldots,F_{L}\right\\}$.

First, the number of possible friendship relations on ${\mathcal{F}}$ such
that each cluster of ${\mathcal{F}}$ is a friend to at most
$\log^{0.1{\varepsilon}}n$ other clusters is at most

$\binom{L}{\log^{0.1{\varepsilon}}n}^{L}\leq\binom{\frac{c^{*}n}{\log^{{\varepsilon}}n}}{\log^{0.1{\varepsilon}}n}^{\frac{c^{*}n}{\log^{{\varepsilon}}n}}\leq\bigg{(}\frac{c^{*}n}{\log^{{\varepsilon}}n}\bigg{)}^{\frac{c^{*}n}{\log^{{\varepsilon}}n}\cdot\log^{0.1{\varepsilon}}n}<n^{c^{*}n\log^{-0.05{\varepsilon}}n}.$

Assume now that we have a fixed friendship relation $\sim$ on the clusters in
${\mathcal{F}}$. We now count the number of clusterings ${\mathcal{F}}$ with
$\sum_{F\not\sim F^{\prime}}|E_{C}(F,F^{\prime})|<n/10$. Denote
$C=(v_{1},v_{2},\ldots,v_{n},v_{1})$. First, the number of possible unfriendly
edge set (which is a subset of $E(C)$ of size at most $0.1n$) is at most

$\sum_{i=0}^{n/10}\binom{n}{i}\leq
n\cdot\binom{n}{n/10}<n\cdot\bigg{(}\frac{en}{n/10}\bigg{)}^{n/10}<n^{n\log^{-0.5}n}.$

We now count the number of clusterings ${\mathcal{F}}$ that, together with the
fixed friendship relation $\sim$, realizes a specific unfriendly edge set. We
will sequentially pick, for each $i$ from $1$ to $n$, a set among
$\left\\{F_{1},\ldots,F_{L}\right\\}$ to add the vertex $v_{i}$ to. The first
vertex $v_{1}$ has $L$ choices. Consider now some index $1\leq i\leq n-1$ and
assume that we have picked sets for $v_{1},\ldots,v_{i}$. If $(v_{i},v_{i+1})$
is an unfriendly edge, then vertex $v_{i+1}$ has $L$ choices; if
$(v_{i},v_{i+1})$ is not an unfriendly edge, this means that $v_{i+1}$ must go
to some cluster that is a friend of the cluster we have picked for $v_{i}$ (or
$v_{i+1}$ can go to the same cluster as $v_{i}$), so $v_{i+1}$ has at most
$\log^{0.1{\varepsilon}}n+1$ choices. As there are no more than $0.1n$
unfriendly edges, the number of possible clusterings ${\mathcal{F}}$ is at
most

$n\cdot(\log^{0.1{\varepsilon}}n)^{n}\cdot\bigg{(}\frac{n}{\log^{{\varepsilon}}n}\bigg{)}^{0.1n}<n^{n/5}.$

Altogether, the number of valid pairs $({\mathcal{F}},\sim)$ satisfying that
$\sum_{F\not\sim F^{\prime}}|E_{C}(F,F^{\prime})|\geq n/10$ is at most

$n^{c^{*}n\log^{-0.05{\varepsilon}}n}\cdot n^{n\log^{-0.5}n}\cdot
n^{n/5}<n^{n/4}.$

∎

######  Claim 3.9.

For every valid pair $({\mathcal{F}},\sim)$, the probability that the edge set
$E_{\sigma_{3}}$ of a random permutation $\sigma_{3}$ contains at most $n/10$
unfriendly edges is at most $n^{-n/3}$.

###### Proof.

We say that a cluster $F\in{\mathcal{F}}$ is _bad_ if it does not have a
friend cluster of size at least $n^{0.4}$, otherwise we say it is _good_. We
first prove the following observation that most vertices lie in a bad cluster.

######  Observation 3.10.

$\sum_{F\text{:bad}}|F|\geq 0.8n$.

###### Proof.

As the pair $({\mathcal{F}},\sim)$ is valid, $\sum_{|F|\geq n^{0.1}}|F|\leq
0.1n$, so ${\mathcal{F}}$ contains at most $0.1\cdot n^{0.6}$ clusters with
size at least $n^{0.4}$. As each cluster is a friend to at most
$\log^{0.1{\varepsilon}}n$ other clusters, ${\mathcal{F}}$ contains at most
$\big{(}0.1\cdot n^{0.6}\cdot\log^{0.1{\varepsilon}}n\big{)}$ good sets.
Therefore, the total size of all good clusters is at most $0.1n+n^{0.1}\cdot
0.1\cdot n^{0.6}\cdot\log^{0.1{\varepsilon}}n<0.2n$. The observation now
follows. ∎

We alternatively construct the random permutation $\sigma_{3}$ as follows. We
arrange the vertices in $V$ into a sequence $(v_{1},\ldots,v_{n})$, such that
each of the first half $v_{1},\ldots,v_{n/2}$ lies in some bad set. Now
sequentially for each $1,2,\ldots,n$, we sample a vertex $u_{i}$ (without
replacement) from $V$ and designate it as $\sigma_{3}(v_{i})$. It is easy to
observe that the permutation $\sigma_{3}$ constructed in this way is a random
permutation from $\Sigma$.

The following observation completes the proof of 3.9.

######  Observation 3.11.

The probability that the number of unfriendly edges in
$\left\\{(v_{i},\sigma_{3}(v_{i}))\mid 1\leq i\leq 9n/10\right\\}$ is less
than $0.1n$ is at most $n^{-n/3}$.

###### Proof.

For any $v$ in a bad cluster, the number of vertices in its friend clusters is
at most $n^{0.4}\log^{0.1}n$. For each $1\leq i\leq 9n/10$, when we pick
$\sigma_{3}(v_{i})$, we have at least $n/10$ choices from the remaining
element in $V$, and as $v_{i}$ is in a bad set, at most $n^{0.4}\log^{0.1}n$
of them will not create an unfriendly edge. Therefore, the probability that
the edge we sample is not a bad edge is at most $\frac{1}{\sqrt{n}}$. Let
$X_{i}$ be the indicator random variable such that $X_{i}=1$ if
$(v_{i},\sigma_{3}(v_{i}))$ is not a bad edge. By Azuma’s Inequality (Chernoff
Bounds on martingales, see e.g., [KQ21]),

$\Pr\left[\sum_{i=1}^{2n/3}X_{i}>4n/5\right]<\left(\frac{5}{4\sqrt{n}}\right)^{4n/5}<n^{-n/3}.$

Thus, with probability at least $1-n^{-n/3}$, the set
$\\{(v_{i},\sigma_{3}(v_{i}))|1\leq i\leq 9n/10\\}$ contains at least
$9n/10-4n/5=n/10$ bad edges. ∎

∎

Combining 3.8 and 3.9, we get that, over the randomness in the construction of
$G^{\prime}$, the probability that there exists a pair $({\mathcal{F}},\sim)$
in which each cluster $F$ is a friend to at most $\log^{0.1{\varepsilon}}n$
other clusters, such that $G^{\prime}$ contains less than $n/10$ unfriendly
edges, is at most $n^{-n/3}\cdot n^{n/4}=n^{-n/12}$. This completes the proof
of Lemma 3.7. ∎

#### Case 2: The total size of large clusters is greater than $0.1n$

We denote by $V^{\prime}$ the union of all large clusters in ${\mathcal{F}}$.
We start by proving the following claim.

######  Claim 3.12.

There exists a collection of $k/4$ edge-disjoint paths in $G$, such that each
path connects a distinct terminal to a distinct vertex of $V^{\prime}$.

###### Proof.

We construct a graph $\hat{G}$ as follows. We start from graph $G^{\prime}$,
and add two vertices $s,t$ to it. We then connect $s$ to each terminal in $T$
by an edge, and connect each vertex in $V^{\prime}$ to $t$ by an edge. All
edges in $\hat{G}$ has unit capacity. We claim that there exists a collection
${\mathcal{P}}$ of $k/3$ edge-disjoint paths in $\hat{G}$, such that each path
connects a distinct terminal to a distinct vertex of $V^{\prime}$. Note that
this implies 3.12. This is because the number of edges in
$E(G^{\prime})\setminus E(G)$ is at most $n^{0.3}<k/12$, and each such edge is
contained in at most one path in ${\mathcal{P}}$ (since the paths in
${\mathcal{P}}$ are edge-disjoint), so at least $k/3-k/12\geq k/4$ paths in
${\mathcal{P}}$ are entirely contained in $G$. We now prove the claim. From
the max-flow min-cut theorem, it suffices to show that the minimum $s$-$t$ cut
in $\hat{G}$ contains at least $k/3$ edges.

Consider any $s$-$t$ cut $(S\cup\left\\{s\right\\},(V\setminus
S)\cup\left\\{t\right\\})$ in $\hat{G}$ and denote by $E^{\prime}$ the set of
edges in this cut. We distinguish between the following cases.

Case 1: $|S|\leq|V|/2$. Recall that $G$ is a $6$-regular graph, so $\sum_{v\in
S}\textrm{deg}(v)\leq\sum_{v\notin S}\textrm{deg}(v)$. Then from Lemma 3.4,
$|E^{\prime}|\geq\sum_{v\in S}\textrm{deg}(v)/2\geq\left|S\right|/2$. If
$\left|S\right|\geq 2k/3$, then $|E^{\prime}|\geq k/3$. If
$\left|S\right|<2k/3$, then at least $k/3$ terminals lie in $V\setminus S$. As
there is an edge connecting $s$ to each terminal, $|E^{\prime}|\geq k/3$.

Case 2: $|S|>|V|/2$. Via similar arguments, we can show that
$|E^{\prime}|\geq|V^{\prime}|/3\geq 0.1n/3>k/3$. ∎

We denote by ${\mathcal{P}}$ the collection of paths given by 3.12. We now use
these paths to complete the proof. Consider such a path
$P=(u_{1},\ldots,u_{r})$. Denote by $F_{i}$ the cluster that contains $u_{i}$,
then the contribution of $P$ to the cost $\mathsf{cost}({\mathcal{F}},\delta)$
is

$\sum_{(u_{i},u_{i+1})\in E(P)}\delta(F_{i},F_{i+1})=\sum_{1\leq i\leq
r-1}\textnormal{{dist}}_{G}(v(F_{i}),v(F_{i+1}))\geq\textnormal{{dist}}_{G}(v(F_{1}),v(F_{r}))\geq\textnormal{{dist}}_{G^{\prime}}(v(F_{1}),v(F_{r})).$

(We have used the property that for every pair $v,v^{\prime}\in V$,
$\textnormal{{dist}}_{G}(v,v^{\prime})\geq\textnormal{{dist}}_{G^{\prime}}(v,v^{\prime})$,
as $G$ is obtained from $G^{\prime}$ by only deleting edges.)

Recall $P$ connects a terminal to a vertex in $V^{\prime}$. Recall that each
large cluster has size at least $n^{0.1}$, so there are at most $n^{0.9}$ of
them. Therefore, if we denote by $V^{\prime\prime}$ the subset of vertices
that large clusters corresponds to, then $|V^{\prime\prime}|\leq n^{0.9}$. For
each path $P\in{\mathcal{P}}$, we denote by $t_{P}$ the terminal endpoint of
$P$ (that is, $u_{1}=v(F_{1})=t_{P}$), and by $v^{\prime\prime}_{P}$ the
vertex that the cluster containing $u_{r}$ corresponds to (that is,
$v^{\prime\prime}_{P}=v(F_{r})$), then $\sum_{(u_{i},u_{i+1})\in
E(P)}\delta(F_{i},F_{i+1})\geq\textnormal{{dist}}_{\ell}(t_{P},v^{\prime\prime}_{P})$.
As the paths in ${\mathcal{P}}$ are edge-disjoint, their contribution to
$\mathsf{cost}({\mathcal{F}},\delta)$ can be added up, i.e.,

$\mathsf{cost}({\mathcal{F}},\delta)\geq\sum_{P\in{\mathcal{P}}}\textnormal{{dist}}_{\ell}(t_{P},v^{\prime\prime}_{P}).$
(1)

On the one hand, as graph $G^{\prime}$ is $6$-regular, for each
$v^{\prime\prime}\in V^{\prime\prime}$, the number of vertices at distance at
most $\log n/100$ to $v^{\prime\prime}$ is at most $6^{\log n/100}\leq
n^{1/30}$. Therefore, there are at most $n^{1/30}\cdot n^{0.9}=n^{14/15}$
terms on the RHS of Equation 1 that at most $\leq\log n/100$. On the other
hand, there are at least $k/4=\Omega(\frac{n\log\log n}{\log n})$ terms on the
RHS of Equation 1, so at least $k/4-n^{14/15}\geq k/5$ terms as value at least
$\log n/100$. Consequently,
$\mathsf{cost}({\mathcal{F}},\delta)\geq(k/5)\cdot(\log n/100)=\Omega(k\log
n)=\Omega(n\log\log n)$.

###  3.3 Completing the Proof of Theorem 1.1

We have shown in Section 3.2 all canonical solutions with size
$O(k\log^{1-{\varepsilon}}n)$ have cost $\Omega({\varepsilon}n\log\log n)$. In
this subsection, we complete the proof of Theorem 1.1 by showing that,
intuitively, an arbitrary solution $({\mathcal{F}},\delta)$ to the instance
$(G,T,D)$ can be “embedded” into a canonical solution, without increasing its
cost by too much.

We start by introducing the notion of _continuization_.

##### Continuization of a graph.

Let $G=(V,E,\ell)$ be an edge-weighted graph. Its _continuization_ is a metric
space $(V^{\textnormal{{con}}},\ell^{\textnormal{{con}}})$, that is defined as
follows. Each edge $(u,v)\in E$ is viewed as a continuous line segment
$\textnormal{{con}}(u,v)$ of length $\ell_{(u,v)}$ connecting $u,v$, and the
point set $V^{\textnormal{{con}}}$ is the union of the points on all lines
$\left\\{\textnormal{{con}}(u,v)\right\\}_{(u,v)\in E}$. Specifically, for
each edge $(u,v)\in E$, the line $\textnormal{{con}}(u,v)$ is defined as

$\textnormal{{con}}(u,v)=\left\\{(u,\alpha)\mid
0\leq\alpha\leq\ell_{(u,v)}\right\\}=\left\\{(v,\beta)\mid
0\leq\beta\leq\ell_{(u,v)}\right\\},$

where $(u,\alpha)$ refers to the unique point on the line that is at distance
$\alpha$ from $u$, and $(v,\beta)$ refers to the unique point on the line that
is at distance $\beta$ from $v$, so $(u,\alpha)=(v,\ell_{(u,v)}-\alpha)$.

The metric $\ell^{\textnormal{{con}}}$ on $V^{\textnormal{{con}}}$ is
naturally induced by the shortest-path distance metric
$\textnormal{{dist}}_{\ell}(\cdot,\cdot)$ on $V$ as follows. For a pair
$p,p^{\prime}$ of points in $V^{\textnormal{{con}}}$,

  * •

if $p,p^{\prime}$ lie on the same line $(u,v)$, say $p=(u,\alpha)$ and
$p^{\prime}=(u,\alpha^{\prime})$, then
$\ell^{\textnormal{{con}}}(p,p^{\prime})=|\alpha-\alpha^{\prime}|$;

  * •

if $p$ lies on the line $(u,v)$ with $p=(u,\alpha)$ and $p^{\prime}$ lies on
the line $(u^{\prime},v^{\prime})$ with
$p^{\prime}=(u^{\prime},\alpha^{\prime})$, then

$\begin{split}\ell^{\textnormal{{con}}}(p,p^{\prime})=\min\\{&\textnormal{{dist}}_{\ell}(u,u^{\prime})+\alpha+\alpha^{\prime},\quad\textnormal{{dist}}_{\ell}(u,v^{\prime})+\alpha+(\ell_{(u^{\prime},v^{\prime})}-\alpha^{\prime}),\\\
&\textnormal{{dist}}_{\ell}(v,u^{\prime})+(\ell_{(u,v)}-\alpha)+\alpha^{\prime},\quad\textnormal{{dist}}_{\ell}(v,v^{\prime})+(\ell_{(u,v)}-\alpha)+(\ell_{(u^{\prime},v^{\prime})}-\alpha^{\prime})\\}.\end{split}$

Clearly, every vertex $u\in V$ also belongs to $V^{\textnormal{{con}}}$, and
for every pair $u,u^{\prime}\in V$,
$\textnormal{{dist}}_{\ell}(u,u^{\prime})=\ell^{\textnormal{{con}}}(u,u^{\prime})$.
For a path $P$ in $G$ connecting $u$ to $u^{\prime}$, it naturally corresponds
to a set $P^{\textnormal{{con}}}$ of points in $V^{\textnormal{{con}}}$, which
is the union of all lines corresponding to edges in $E(P)$. The set
$P^{\textnormal{{con}}}$ naturally inherits the metric
$\ell^{\textnormal{{con}}}$ restricted on $P^{\textnormal{{con}}}$. We will
also call $P^{\textnormal{{con}}}$ a path in the continuization
$(V^{\textnormal{{con}}},\ell^{\textnormal{{con}}})$.

We show that, for each graph $G$ with a set $T$ of terminals, then any other
metric $w$ on a set of points containing $T$, such that $w$ restricted on $T$
is identical to $\textnormal{{dist}}_{G}$ restricted on $T$, can be “embedded”
into the continuation of $G$, with expected stretch bounded by some structural
measure that only depends on $G$. Specifically, we prove the following main
technical lemma.

######  Lemma 3.13.

Let $(G,T,\ell)$ be any instance of $\mathsf{0EwSN}$ such that $G$ is not a
tree (so $\textnormal{{girth}}(G)<+\infty$), and let $({\mathcal{F}},\delta)$
be any solution to it. Let
$(V^{\textnormal{{con}}},\ell^{\textnormal{{con}}})$ be the continuization of
graph $G$. Then there exists a random mapping $\phi:{\mathcal{F}}\to
V^{\textnormal{{con}}}$, such that

  * •

for each terminal $t\in T$, if $F$ is the (unique) cluster in ${\mathcal{F}}$
that contains $t$, then $\phi(F)=t$; and

  * •

for every pair $F,F^{\prime}\in{\mathcal{F}}$,

${\mathbb{E}}\left[\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\right]\leq
O\bigg{(}\frac{\textnormal{{diam}}(G)}{\textnormal{{girth}}(G)}\bigg{)}\cdot\delta(F,F^{\prime}).$

Before we prove Lemma 3.13 in Section 3.4, we provide the proof of Theorem 1.1
using it.

_Proof of Theorem 1.1._ Consider any solution $({\mathcal{F}},\delta)$ to the
instance $(G,T,\ell)$ constructed in Section 3.1 with size
$|{\mathcal{F}}|\leq o(k\cdot\log^{1-{\varepsilon}}k)$. From 3.2 and Corollary
3.5, $\frac{\textnormal{{diam}}(G)}{\textnormal{{girth}}(G)}\leq\frac{O(\log
n)}{(\log n)/100}=O(1)$. From Lemma 3.13, there exists a random mapping
$\phi:{\mathcal{F}}\to V^{\textnormal{{con}}}$, such that for every pair
$F,F^{\prime}\in{\mathcal{F}}$,
${\mathbb{E}}\left[\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\right]\leq
O(1)\cdot\delta(F,F^{\prime})$.

Fix such a mapping $\phi$, we define a canonical solution
$({\mathcal{F}},\hat{\delta})$ based on $({\mathcal{F}},\delta)$ as follows.
The collection of clusters is identical to the collection ${\mathcal{F}}$. For
each $F\in{\mathcal{F}}$, recall that $\phi(F)$ is a point in
$V^{\textnormal{{con}}}$. Assume the point $\phi(F)$ lies on the line $(u,v)$
and is closer to $u$ than to $v$ (i.e.,
$\ell^{\textnormal{{con}}}(\phi(F),u)\leq\ell^{\textnormal{{con}}}(\phi(F),v)$),
then we let $u$ be the vertex in $V$ that it corresponds to. For each pair
$F,F^{\prime}\in{\mathcal{F}}$, with $F$ corresponding to $u_{F}$ and and
$F^{\prime}$ corresponding to $u_{F^{\prime}}$, we define
$\hat{\delta}(F,F^{\prime})=\textnormal{{dist}}_{\ell}(u_{F},u_{F^{\prime}})$.
As graph $G$ in the instance $(G,T,\delta)$ constructed in Section 3.1 is an
unweighted graph, it is easy to see that

$\hat{\delta}(F,F^{\prime})=\textnormal{{dist}}_{\ell}(u_{F},u_{F^{\prime}})\leq\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))+2.$

As the mapping $\phi$ is random, $\hat{\delta}$ is also random, and so
${\mathbb{E}}\left[\hat{\delta}(F,F^{\prime})\right]\leq
O(1)\cdot\delta(F,F^{\prime})+2$.

From the properties of mapping $\phi$ in Lemma 3.13, we are guaranteed that
such a solution $({\mathcal{F}},\hat{\delta})$ is a canonical solution.
Moreover, from linearity of expectation,

${\mathbb{E}}\left[\mathsf{cost}({\mathcal{F}},\hat{\delta})\right]={\mathbb{E}}\left[\sum_{(u,v)\in
E}\hat{\delta}(F(u),F(v))\right]=\sum_{(u,v)\in
E}O\bigg{(}\delta(F(u),F(v))\bigg{)}+2=O\bigg{(}\mathsf{cost}({\mathcal{F}},\delta)\bigg{)}+O(n).$

Therefore, it follows that there exists a canonical solution
$({\mathcal{F}},\hat{\delta})$, such that
$\mathsf{cost}({\mathcal{F}},\hat{\delta})\leq
O(\mathsf{cost}({\mathcal{F}},\delta)+n)$. As we have shown in Section 3.2
that any canonical solution $({\mathcal{F}},\hat{\delta})$ with
$|{\mathcal{F}}|\leq o(k\log^{1-{\varepsilon}}k)$ satisfies that
$\mathsf{cost}({\mathcal{F}},\hat{\delta})=\Omega({\varepsilon}n\log\log n)$,
it follows that
$\mathsf{cost}({\mathcal{F}},\delta)=\Omega({\varepsilon}n\log\log n)$. This
implies that the integrality gap of (LP-Metric) is at least
$\Omega({\varepsilon}\log\log n)$. ∎

###  3.4 Proof of Lemma 3.13

In this subsection, we provide the proof of Lemma 3.13. We first consider the
special case where $G$ is a tree, and then prove Lemma 3.13 for the general
case.

######  Lemma 3.14.

Let $(G,T,\ell)$ be an instance of $\mathsf{0EwSN}$ where $G$ is a tree. Let
$({\mathcal{F}},\delta)$ be an solution to it. Let
$(V^{\textnormal{{con}}},\ell^{\textnormal{{con}}})$ be the continuization of
$G$. Then there exists a mapping $\phi:{\mathcal{F}}\to
V^{\textnormal{{con}}}$, such that

  * •

for each terminal $t\in T$, if $F$ is the (unique) cluster in ${\mathcal{F}}$
that contains $t$, then $\phi(F)=t$; and

  * •

for every pair $F,F^{\prime}\in{\mathcal{F}}$,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq\delta(F,F^{\prime})$.

###### Proof.

For each terminal $t\in T$, we denote by $F_{t}$ the cluster in
${\mathcal{F}}$ that contains it, and set $\phi(F_{t})=t$. For each cluster
$F\in{\mathcal{F}}$ that does not contain any terminals, we define

$\nu(F)=\min\left\\{\frac{1}{2}\cdot\big{(}\delta(F,F_{t})+\delta(F,F_{t^{\prime}})-\delta(F_{t},F_{t^{\prime}})\big{)}\mid
t,t^{\prime}\in T\right\\}.$

Denote by $t_{1},t_{2}$ the pair of terminals $(t,t^{\prime})$ that minimizes
$(\delta(F,F_{t})+\delta(F,F_{t^{\prime}})-\delta(F_{t},F_{t^{\prime}}))/2$.
As $G$ is a tree, there is a unique shortest path connecting $t_{1}$ to
$t_{2}$ in $G$, and therefore there exists a unique point $p$ in
$V^{\textnormal{{con}}}$ (that lies on the $t_{1}$-$t_{2}$ shortest path in
$V^{\textnormal{{con}}}$) with
$\ell^{\textnormal{{con}}}(p,t_{1})=\delta(F,F_{t_{1}})-\nu(F)$ and
$\ell^{\textnormal{{con}}}(p,t_{2})=\delta(F,F_{t_{2}})-\nu(F)$. We set
$\phi(F)=p$.

######  Claim 3.15.

For every cluster $F\in{\mathcal{F}}$ and every terminal $t\in T$,
$\ell^{\textnormal{{con}}}(\phi(F),t)\leq\delta(F,F_{t})-\nu(F)$.

###### Proof.

Note that the point $\phi(F)$ lies on the (unique) shortest path between a
pair $t_{1},t_{2}$ of terminals. For $t\in\left\\{t_{1},t_{2}\right\\}$,
clearly the claim holds. Consider any other terminal $t$. Clearly $\phi(F)$
lies on either the path connecting $t$ to $t_{1}$ or the path connecting $t$
to $t_{2}$. Assume without lose of generality that $\phi(F)$ is on the path
connecting $t_{1}$ and $t$. Since $G$ is a tree,
$\ell^{\textnormal{{con}}}(\phi(F),t_{1})+\ell^{\textnormal{{con}}}(\phi(F),t)=\ell^{\textnormal{{con}}}(t_{1},t)=\textnormal{{dist}}_{\ell}(t_{1},t)$.
On the other hand, by definition of $\nu(F)$ and $\phi(F)$,
$\delta(F,F_{t_{1}})+\delta(F,F_{t})\geq\delta(F_{t_{1}},F_{t})+2\cdot\nu(F)$
holds, and
$\ell^{\textnormal{{con}}}(\phi(F),t_{1})=\delta(F,F_{t_{1}})-\nu(F)$.
Therefore, $\delta(F,F_{t})\geq\ell^{\textnormal{{con}}}(\phi(F),t)+\nu(F)$. ∎

We now show that, for every pair $F,F^{\prime}\in{\mathcal{F}}$,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq\delta(F,F^{\prime})$.
Denote by $t_{1},t_{2}$ the pair of terminals whose shortest path contains
$\phi(F)$, and by $t^{\prime}_{1},t^{\prime}_{2}$ the pair of terminals whose
shortest path contains $\phi(F^{\prime})$. Assume without lose of generality
that $\phi(F)$ is on the tree path between $\phi(F^{\prime})$ and $t_{1}$, so
$\ell^{\textnormal{{con}}}(\phi(F^{\prime}),\phi(F))+\ell^{\textnormal{{con}}}(\phi(F),{t_{1}})=\ell^{\textnormal{{con}}}(\phi(F^{\prime}),{t_{1}})$.
On the other hand, from the definition of $\phi(F)$ and 3.15,
$\ell^{\textnormal{{con}}}(\phi(F),{t_{1}})=\delta(F,F_{t_{1}})-\nu(F)$ and
$\ell^{\textnormal{{con}}}(\phi(F^{\prime}),{t_{1}})\leq\delta(F^{\prime},F_{t_{1}})-\nu(F^{\prime})$.
Therefore,

$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq\delta(F^{\prime},F_{t_{1}})-\delta(F,F_{t_{1}})-\nu(F^{\prime})+\nu(F)\leq\delta(F,F^{\prime})+\nu(F)-\nu(F^{\prime}).$

Similarly,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq\delta(F,F^{\prime})+\nu(F^{\prime})-\nu(F)$.
Altogether,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq\delta(F,F^{\prime})$.
∎

In the remainder of this subsection, we complete the proof of Lemma 3.13.
Denote $g=\textnormal{{girth}}(G)$. Let $r$ be a real number chosen uniformly
at random from the interval $[g/60,g/30]$, so $r\leq g/30$ always holds. For
each terminal $t\in T$, we denote by $F_{t}$ the cluster in ${\mathcal{F}}$
that contains it, and set $\phi(F_{t})=t$, so the first condition in Lemma
3.13 is satisfied.

For each cluster $F\in{\mathcal{F}}$, we define
$A_{F}=\min\left\\{\delta(F,F_{t})\mid t\in T\right\\}$. We first determine
the image $\phi(F)$ for all clusters $F$ with $A_{F}\leq r$, in a similar way
as Lemma 3.14 as follows.

Define

$\nu(F)=\min\left\\{\frac{1}{2}\cdot\bigg{(}\delta(F,F_{t})+\delta(F,F_{t^{\prime}})-\frac{\delta(F_{t},F_{t^{\prime}})}{2}\bigg{)}\mid
t,t^{\prime}\in T\right\\}.$

Denote by $t_{1},t_{2}$ the pair $(t,t^{\prime})$ that minimizes the above
formula. We prove the following claim.

######  Claim 3.16.

$\delta(F,F_{t_{1}})+\delta(F,F_{t_{2}})\leq 4\cdot A_{F}\leq 4r$.

###### Proof.

Let $t$ be the terminal such that $\delta(F,F_{t})=A_{F}$. By definition of
$\nu(F)$,

$\nu(F)\leq\frac{\delta(F,F_{t})+\delta(F,F_{t})-\frac{1}{2}\cdot\delta(F_{t},F_{t})}{2}=A_{F}.$

On the other hand, from triangle inequality,

$\nu(F)=\frac{\delta(F,F_{t_{1}})+\delta(F,F_{t_{2}})-\frac{1}{2}\cdot\delta(F_{t_{1}},F_{t_{2}})}{2}\geq\frac{\delta(F,F_{t_{1}})+\delta(F,F_{t_{2}})}{4}.$

Altogether, $\delta(F,F_{t_{1}})+\delta(F,F_{t_{2}})\leq 4\cdot A_{F}$. ∎

From 3.16,
$\delta(F_{t_{1}},F_{t_{2}})\leq\delta(F,F_{t_{1}})+\delta(F,F_{t_{2}})\leq
4r<g/3$. Therefore, there is a unique shortest path connecting $t_{1}$ to
$t_{2}$ in $G$, as otherwise $G$ must contain a cycle of length at most
$2g/3$, contradicting the fact that $\textnormal{{girth}}(G)=g$.

We then set $\phi(F)$ to be the point in $V^{\textnormal{{con}}}$ that lies in
the $t_{1}$-$t_{2}$ shortest path, such that
$\ell^{\textnormal{{con}}}(\phi(F),t_{1})=2\cdot(\delta(F,F_{t_{1}})-\nu(F))$
and
$\ell^{\textnormal{{con}}}(\phi(F),t_{2})=2\cdot(\delta(F,F_{t_{2}})-\nu(F))$.
Note that, by definition of $t_{1},t_{2}$,

$\ell^{\textnormal{{con}}}(\phi(F),t_{1})+\ell^{\textnormal{{con}}}(\phi(F),t_{2})=2\cdot\delta(F,F_{t_{1}})+2\cdot\delta(F,F_{t_{2}})-4\cdot\nu(F)=\delta(F_{t_{1}},F_{t_{2}}).$

We prove the following claim, that is similar to 3.15.

######  Claim 3.17.

For every terminal $t$ with $\delta(F,F_{t})\leq 6r$,
$\ell^{\textnormal{{con}}}(\phi(F),t)\leq 2\cdot(\delta(F,F_{t})-\nu(F))$.

###### Proof.

From 3.16,

$\begin{split}\delta(F_{t},F_{t_{1}})+\delta(F_{t},F_{t_{2}})+\delta(F_{t_{1}},F_{t_{2}})&\leq\bigg{(}2\cdot\delta(F,F_{t})+\delta(F,F_{t_{1}})+\delta(F,F_{t_{2}})\bigg{)}+\delta(F_{t_{1}},F_{t_{2}})\\\
&\leq 12r+4r+4r+4r<g.\end{split}$

Therefore, the point $\phi(F)$ must lie on either the $t$-${t_{1}}$ shortest
path or the $t$-${t_{2}}$ shortest path in $V^{\textnormal{{con}}}$, as
otherwise the union of $t$-${t_{1}}$ shortest path, $t$-${t_{2}}$ shortest
path, and $t_{1}$-${t_{2}}$ shortest path contains a cycle of length less than
$g$, a contradiction.

Assume without loss of generality that $\phi(F)$ lies on the $t$-${t_{1}}$
shortest path, so

$\ell^{\textnormal{{con}}}(\phi(F),t)=\delta(F_{t},F_{t_{1}})-\ell^{\textnormal{{con}}}(\phi(F),{t_{1}})=\delta(F_{t},F_{t_{1}})-2(\delta(F,F_{t_{1}})-\nu(F)).$

By definition of $\nu(F)$, $\delta(F_{t},F_{t_{1}})\leq
2\cdot(\delta(F,F_{t})+\delta(F,F_{t_{1}})-2\cdot\nu(F))$. Therefore,

$\ell^{\textnormal{{con}}}(\phi(F),t)\leq
2\bigg{(}\delta(F,t)+\delta(F,F_{t_{1}})-2\nu(F)-\big{(}\nu(F,F_{t_{1}})-\nu(F)\big{)}\bigg{)}=2(\delta(F,F_{t})-\nu(F)).$

∎

We now show in the next claim that the second condition in Lemma 3.13 holds
for pairs of clusters that are close in $\delta$.

######  Claim 3.18.

For every pair $F,F^{\prime}\in{\mathcal{F}}$ with
$A_{F},A_{F^{\prime}},\delta(F,F^{\prime})\leq r$,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq
2\cdot\delta(F,F^{\prime})$.

###### Proof.

Since $\delta(F,F^{\prime})<r$, from triangle inequality and 3.16,

$\delta(F^{\prime},F_{t_{1}})\leq\delta(F^{\prime},F)+\delta(F,F_{t_{1}})\leq
r+4r\leq 5r.$

Similarly, $\delta(F^{\prime},F_{t_{2}})\leq 5r$. Then from 3.17,

$\ell^{\textnormal{{con}}}(\phi(F^{\prime}),t_{1})\leq
2\cdot(\delta(F^{\prime},F_{t_{1}})-\nu(F^{\prime}))\leq
2\cdot\delta(F^{\prime},F_{t_{1}})\leq 10r,$

and symmetrically, $\ell^{\textnormal{{con}}}(\phi(F^{\prime}),t_{2})<10r$.
Therefore,

$\ell^{\textnormal{{con}}}(\phi(F^{\prime}),t_{1})+\ell^{\textnormal{{con}}}(\phi(F^{\prime}),t_{2})+\ell^{\textnormal{{con}}}(t_{1},t_{2})<20r+4r<g.$

Therefore, the point $\phi(F)$ must lie either on the
$\phi(F^{\prime})$-$t_{1}$ shortest path or the $\phi(F^{\prime})$-$t_{2}$
shortest path in $V^{\textnormal{{con}}}$, as otherwise the union of
$\phi(F^{\prime})$-${t_{1}}$ shortest path, $\phi(F^{\prime})$-${t_{2}}$
shortest path, and $t_{1}$-${t_{2}}$ shortest path in $V^{\textnormal{{con}}}$
contains a cycle of length less than $g$, a contradiction.

Assume without loss of generality that $\phi(F)$ lies on the
$\phi(F^{\prime})$-$t_{1}$ shortest path. Then

$\begin{split}\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))&=\ell^{\textnormal{{con}}}(\phi(F^{\prime}),t_{1}(F))-\ell^{\textnormal{{con}}}(\phi(F),t_{1}(F))\\\
&\leq
2\bigg{(}\delta(F^{\prime},t_{1}(F))-\nu(F^{\prime})\bigg{)}-2\bigg{(}\delta(F,t_{1}(F))-\nu(F)\bigg{)}\leq
2\bigg{(}\delta(F,F^{\prime})+\nu(F)-\nu(F^{\prime})\bigg{)}.\end{split}$

Similarly, $\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq
2\big{(}\delta(F,F^{\prime})+\nu(F^{\prime})-\nu(F)\big{)}$. Altogether,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq
2\delta(F,F^{\prime})$. ∎

We now complete the construction of the mapping $\phi$, by specifying the
images of all clusters $F\in{\mathcal{F}}$ with $A_{F}>r$. Let $t^{*}$ be an
arbitrarily chosen terminal in $T$. For all clusters $F\in{\mathcal{F}}$ with
$A_{F}>r$, we simply set $\phi(F)=t^{*}$.

It remains to show that the second condition in Lemma 3.13 holds for all pairs
$F,F^{\prime}\in{\mathcal{F}}$. Consider a pair $F,F^{\prime}$. Assume first
that $\delta(F,F^{\prime})>g/60$. Then

$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq\textsf{diam}(G)\leq\frac{60\cdot\textsf{diam}(G)}{\textnormal{{girth}}(G)}\cdot\delta(F,F^{\prime}).$

Assume now that $\delta(F,F^{\prime})\leq g/60$, and without loss of
generality that $A_{F}\leq A_{F^{\prime}}$. Note that, from triangle
inequality, for every terminal $t\in T$,
$\delta(F^{\prime},F_{t})\leq\delta(F,F_{t})-\delta(F,F^{\prime})$. This
implies that $A_{F^{\prime}}-A_{F}\leq\delta(F,F^{\prime})$. Therefore, the
probability that the random number $r$ takes value from the interval
$[A_{F},A_{F^{\prime}}]$ is at most $\frac{\delta(F,F^{\prime})}{g/60}$. Note
that, if $r\leq A_{F}$, then $\phi(F)=\phi(F^{\prime})=t^{*}$ and
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))=0$. And if $r\geq
A_{F^{\prime}}$, then from 3.18,
$\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\leq
2\delta(F,F^{\prime})$. Altogether,

${\mathbb{E}}\left[\ell^{\textnormal{{con}}}(\phi(F),\phi(F^{\prime}))\right]\leq\frac{60\cdot\textsf{diam}(G)}{\textnormal{{girth}}(G)}\cdot\delta(F,F^{\prime})+2\delta(F,F^{\prime})\leq
O\bigg{(}\frac{\textsf{diam}(G)}{\textnormal{{girth}}(G)}\bigg{)}\cdot\delta(F,F^{\prime}).$

##  Appendix A Comparison between $\mathsf{0EwSN}$ and the variant in [AGK14]

##### The Steiner node variant of $0$-Ext in [AGK14].

In [AGK14], the following problem (referred to as
$\mathsf{0EwSN}_{\textsf{AGK}}$) was proposed.

The input consists of

  * •

an edge-capacitated graph $G=(V,E,c)$, with length
$\left\\{\ell_{e}\right\\}_{e\in E}$ on its edges;

  * •

a set $T\subseteq V$ of $k$ terminals; and

  * •

a _demand_ ${\mathcal{D}}:T\times T\to\mathbb{R}^{+}$ on terminals.

A solution consists of

  * •

a partition ${\mathcal{F}}$ of $V$ with $|{\mathcal{F}}|$, such that distinct
terminals of $T$ belong to different sets in ${\mathcal{F}}$; for each vertex
$u\in V$, we denote by $F(u)$ the cluster in ${\mathcal{F}}$ that contains it;

  * •

a semi-metric $\delta$ on the clusters in ${\mathcal{F}}$, such that:
$\sum_{t,t^{\prime}}{\mathcal{D}}(t,t^{\prime})\cdot\delta(F(t),F(t^{\prime}))\geq\sum_{t,t^{\prime}}{\mathcal{D}}(t,t^{\prime})\cdot\textnormal{{dist}}_{\ell}(t,t^{\prime})$,
where $\textnormal{{dist}}_{\ell}(\cdot,\cdot)$ is the shortest-path distance
(in $G$) metric induced by edge length $\left\\{\ell_{e}\right\\}_{e\in
E(G)}$.

The cost of a solution $({\mathcal{F}},\delta)$ is
$\mathsf{cost}({\mathcal{F}},\delta)=\sum_{(u,v)\in
E}c(u,v)\cdot\delta(F(u),F(v))$, and its _size_ is $|{\mathcal{F}}|$.

From (LP1) and Proposition 4.2 in [AGK14], it is proved that:

######  Proposition A.1.

Given a graph $G$ and a subset $T$ of its terminals, and a function $f$, if
for every length $\left\\{\ell_{e}\right\\}_{e\in E(G)}$ and every demand $D$,
the instance $(G,T,\ell,{\mathcal{D}})$ of $\mathsf{0EwSN}_{\textsf{AGK}}$ has
a solution $({\mathcal{F}},\delta)$ with size $|{\mathcal{F}}|\leq f(k)$ and
cost

$\sum_{(u,v)\in E}c(u,v)\cdot\delta(F(u),F(v))\leq q\cdot\sum_{(u,v)\in
E}c(u,v)\cdot\textnormal{{dist}}_{\ell}(u,v),$

then there is a quality-$(1+{\varepsilon})q$ flow sparsifier $H$ for $G$ w.r.t
$T$ with $|V(H)|\leq(f(k))^{(\log k/{\varepsilon})^{k^{2}}}$.

##### The $\mathsf{0EwSN}$ problem.

In studying the integrality gap of (LP-Metric), we are essentially considering
the following problem.

The input consists of

  * •

an edge-capacitated graph $G=(V,E,c)$, with length
$\left\\{\ell_{e}\right\\}_{e\in E}$ on its edges; and

  * •

a set $T\subseteq V$ of $k$ terminals.

A solution consists of

  * •

a partition ${\mathcal{F}}$ of $V$ with $|{\mathcal{F}}|$, such that distinct
terminals of $T$ belong to different sets in ${\mathcal{F}}$; for each vertex
$u\in V$, we denote by $F(u)$ the cluster in ${\mathcal{F}}$ that contains it;

  * •

a semi-metric $\delta$ on the clusters in ${\mathcal{F}}$, such that for all
pairs $t,t^{\prime}\in T$,
$\delta(F(t),F(t^{\prime}))=\textnormal{{dist}}_{\ell}(t,t^{\prime})$, where
$\textnormal{{dist}}_{\ell}(\cdot,\cdot)$ is the shortest-path distance (in
$G$) metric induced by edge length $\left\\{\ell_{e}\right\\}_{e\in E(G)}$.

The cost and the size of a solution is defined in the same way as
$\mathsf{0EwSN}_{\textsf{AGK}}$.

The difference between two problems are underlined. Specifically, in
$\mathsf{0EwSN}_{\textsf{AGK}}$ it is only required that some “average
terminal distance” does not decrease, while in our problem it is required that
all pairwise distances between terminals are preserved. Clearly, our
requirement for a solution is stronger, which implies that any valid solution
to our instance is also a valid solution to the same
$\mathsf{0EwSN}_{\textsf{AGK}}$ instance (with arbitrary ${\mathcal{D}}$).
Therefore, we have the following corollary.

######  Corollary A.2.

Given a graph $G$ and a subset $T$ of its terminals, and a function $f$, if
for every length $\left\\{\ell_{e}\right\\}_{e\in E(G)}$, the instance
$(G,T,\ell)$ of $\mathsf{0EwSN}$ has a solution $({\mathcal{F}},\delta)$ with
size $|{\mathcal{F}}|\leq f(k)$ and cost

$\sum_{(u,v)\in E}c(u,v)\cdot\delta(F(u),F(v))\leq q\cdot\sum_{(u,v)\in
E}c(u,v)\cdot\textnormal{{dist}}_{\ell}(u,v),$

then there is a quality-$(1+{\varepsilon})q$ flow sparsifier $H$ for $G$ w.r.t
$T$ with $|V(H)|\leq(f(k))^{(\log k/{\varepsilon})^{k^{2}}}$.

On the other hand, the main result of our paper is a lower bound for the
$\mathsf{0EwSN}$ problem. As $\mathsf{0EwSN}$ has stronger requirement (for
solutions) than $\mathsf{0EwSN}_{\textsf{AGK}}$, our lower bound does not
immediately imply a lower bound for $\mathsf{0EwSN}_{\textsf{AGK}}$ or for the
flow sparsifier. However, if we can show that, for some function $f$, there
exists a graph $G$, a terminal set $T$ with size $k$, and a demand
${\mathcal{D}}$ on $T$, such that any solution $({\mathcal{F}},\delta)$ with
size $|{\mathcal{F}}|\leq f(k)$ has cost at least

$\sum_{(u,v)\in E}c(u,v)\cdot\delta(F(u),F(v))\geq q\cdot\sum_{(u,v)\in
E}c(u,v)\cdot\textnormal{{dist}}_{\ell}(u,v),$

then this, from the (LP1) and the discussion in [AGK14], implies that any
quality-$o(q)$ contraction-based flow sparsifier for $G$ has size at least
$f(k)$.

##### Acknowledgement.

We would like to thank Julia Chuzhoy for many helpful discussions. We wan to
thank Arnold Filtser for pointing to us some previous works on similar
problems.

## References

  * [AFH+04] Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Éva Tardos.  Approximate classification via earthmover metrics.  In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1079–1087. Society for Industrial and Applied Mathematics, 2004.
  * [AGK14] Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer.  Towards (1+$\varepsilon$)-approximate flow sparsifiers.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 279–293. SIAM, 2014.
  * [AMM17] Haris Angelidakis, Yury Makarychev, and Pasin Manurangsi.  An improved integrality gap for the călinescu-karloff-rabani relaxation for multiway cut.  In Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 39–50. Springer, 2017.
  * [BCKM20] Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Vivek Madan.  Improving the integrality gap for multiway cut.  Mathematical Programming, 183(1-2):171–193, 2020.
  * [BNS13] Niv Buchbinder, Joseph Naor, and Roy Schwartz.  Simplex partitioning via exponential clocks and the multiway cut problem.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 535–544, 2013.
  * [BSW17] Niv Buchbinder, Roy Schwartz, and Baruch Weizman.  Simplex transformations and the multiway cut problem.  In Proceedings of the twenty-eighth annual ACM-SIAM Symposium on Discrete Algorithms, pages 2400–2410. SIAM, 2017.
  * [Chu12] Julia Chuzhoy.  On vertex sparsifiers with steiner nodes.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 673–688, 2012.
  * [CKNZ04] Chandra Chekuri, Sanjeev Khanna, Joseph Naor, and Leonid Zosin.  A linear programming formulation and approximation algorithms for the metric labeling problem.  SIAM Journal on Discrete Mathematics, 18(3):608–625, 2004.
  * [CKR98] Gruia Călinescu, Howard Karloff, and Yuval Rabani.  An improved approximation algorithm for multiway cut.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 48–52, 1998.
  * [CKR05] Gruia Calinescu, Howard Karloff, and Yuval Rabani.  Approximation algorithms for the 0-extension problem.  SIAM Journal on Computing, 34(2):358–372, 2005.
  * [CLLM10] Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra.  Vertex sparsifiers and abstract rounding algorithms.  In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 265–274. IEEE, 2010.
  * [CN07] Julia Chuzhoy and Joseph Naor.  The hardness of metric labeling.  SIAM Journal on Computing, 36(5):1376–1386, 2007.
  * [CT23] Yu Chen and Zihan Tan.  Towards the characterization of terminal cut functions: a condition for laminar families.  arXiv preprint arXiv:2310.11367, 2023.
  * [CT24] Yu Chen and Zihan Tan.  On (1+ eps)-approximate flow sparsifiers.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1568–1605. SIAM, 2024.
  * [DJP+94] Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis.  The complexity of multiterminal cuts.  SIAM Journal on Computing, 23(4):864–894, 1994.
  * [FHRT03] Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar.  An improved approximation algorithm for the 0-extension problem.  In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 257–265. Society for Industrial and Applied Mathematics, 2003.
  * [FK00] Ari Freund and Howard Karloff.  A lower bound of $8/(7+\frac{1}{k-1})$ on the integrality ratio of the călinescu–karloff–rabani relaxation for multiway cut.  Information Processing Letters, 75(1-2):43–50, 2000.
  * [Fri01] Alan Frieze.  Hamilton cycles in the union of random permutations.  Random Structures & Algorithms, 18(1):83–94, 2001.
  * [HKNR98] Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde.  Characterizing multiterminal flow networks and computing flows in networks of small treewidth.  Journal of Computer and System Sciences, 57(3):366–375, 1998.
  * [Kar98] Alexander V Karzanov.  Minimum 0-extensions of graph metrics.  European Journal of Combinatorics, 19(1):71–101, 1998.
  * [KKMR06] Howard Karloff, Subhash Khot, Aranyak Mehta, and Yuval Rabani.  On earthmover distance, metric labeling, and 0-extension.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 547–556, 2006.
  * [KKMR09] Howard Karloff, Subhash Khot, Aranyak Mehta, and Yuval Rabani.  On earthmover distance, metric labeling, and 0-extension.  SIAM Journal on Computing, 39(2):371–387, 2009.
  * [KM23] Robert Krauthgamer and Ron Mosenzon.  Exact flow sparsification requires unbounded size.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2354–2367. SIAM, 2023.
  * [KQ21] William Kuszmaul and Qi Qi.  The multiplicative version of azuma’s inequality, with an application to contention analysis.  arXiv preprint arXiv:2102.05077, 2021.
  * [KT02] Jon Kleinberg and Eva Tardos.  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields.  Journal of the ACM (JACM), 49(5):616–639, 2002.
  * [LM10] F Thomson Leighton and Ankur Moitra.  Extensions and limits to vertex sparsification.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 47–56. ACM, 2010.
  * [MM10] Konstantin Makarychev and Yury Makarychev.  Metric extension operators, vertex sparsifiers and lipschitz extendability.  In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 255–264. IEEE, 2010.
  * [MNRS08] Rajsekar Manokaran, Joseph Seffi Naor, Prasad Raghavendra, and Roy Schwartz.  Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 11–20. ACM, 2008.
  * [Moi09] Ankur Moitra.  Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size.  In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on, pages 3–12. IEEE, 2009.
  * [Pud15] Doron Puder.  Expansion of random graphs: New proofs, new results.  Inventiones mathematicae, 201(3):845–908, 2015.
  * [ST21] Roy Schwartz and Nitzan Tur.  The metric relaxation for 0-extension admits an $\omega(\log^{2/3}k)$ gap.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1601–1614, 2021.


# Query-Utterance Attention with Joint modeling for Query-Focused Meeting
Summarization

###### Abstract

Query-focused meeting summarization (QFMS) aims to generate summaries from
meeting transcripts in response to a given query. Previous works typically
concatenate the query with meeting transcripts and implicitly model the query
relevance only at the token level with attention mechanism. However, due to
the dilution of key query-relevant information caused by long meeting
transcripts, the original transformer-based model is insufficient to highlight
the key parts related to the query. In this paper, we propose a query-aware
framework with joint modeling token and utterance based on Query-Utterance
Attention. It calculates the utterance-level relevance to the query with a
dense retrieval module. Then both token-level query relevance and utterance-
level query relevance are combined and incorporated into the generation
process with attention mechanism explicitly. We show that the query relevance
of different granularities contributes to generating a summary more related to
the query. Experimental results on the QMSum dataset show that the proposed
model achieves new state-of-the-art performance.

Index Terms—  QFMS, query-aware framework, Query-Utterance attention

##  1 Introduction

Meeting summarization aims to summarize the key parts of a meeting transcript
into a concise textual passage to improve the efficiency of access to
information. People are usually more interested in certain parts than the
whole meeting. Query-focused meeting summarization (QFMS) adopts a more
interactive approach that accepts user’s query and generates a summary in
response to the query [1, 2]. Therefore, QFMS can satisfy user’s need to focus
on specific topics and aspects of the meeting.

Early attempts [3, 4, 5] in the query-focused summarization (QFS) focused on
alleviating the data deficit problem. Early work [2] in multi-document
summarization models sentence-query score with token-level overlap and
introduces the score in the RNN-based model. Recently, introduction of the
high-quality dataset QMSUM [6] has significantly advanced the research of
QFMS.

Fig. 1:  Different topics are marked with different colors. Without explicit
modeling Query-Utterance relevance, the previous model generated summaries
that deviated from the query’s topic. In contrast, by explicitly modeling
Query-Utterance relevance, our model can better capture the topics of the
query.  Fig. 2: The overall model structure

Compared with the generic summary, QFMS is faced with the challenge of
generating a summary related to the query. Previous works typically
concatenate the query with meeting transcripts and implicitly model the query
relevance only at the token level with attention mechanism. However, it is not
enough to highlight the key parts related to the query in long meeting
transcripts. As shown in Figure 1, the user is wondering about the
disagreement between the industrial designer and the marketing regarding the
product’s future trend. The summary generated by previous work incorrectly
focuses on discussions about product shape. This is likely due to the fact
that the information related to the query will be diluted with the increase in
meeting length. The previous original transformer-based model does not
explicitly model the correlation with the query, but only models the
correlation between tokens with the attention mechanism, which does not
contain the complete semantic information as utterance. Existing work [6, 7]
takes a select-then-generate approach to process long input and feed the most
relevant parts to the generation model. A major drawback faced by the two-
stage approach is error propagation, some parts which are incorrectly filtered
out don’t appear in the generation stage at all, which even aggravates the
error that the generated summaries are not related to the query. Hence, we
believe it makes sense to explore an end-to-end approach that explicitly
integrates Query-Utterance relevance in the generation process.

To address the above challenges, in this paper, we propose a query-aware
framework by jointly modeling query relevance with token and utterance. First,
we use an additional dense retrieval module to calculate the similarity
between the query and each meeting utterance. Second, we adopt an end-to-end
model and replace the origin cross attention with token cross attention and
Query-Utterance cross attention. With a joint training framework with the
query relevance of different granularity, the model can generate summaries
that are more related to the query.

To summarize, our contributions are as follows: (1) Our work demonstrates the
effectiveness of the Query-Utterance relevance in generating a summary more
related to the query. (2) We propose a query-aware framework by jointly
modeling query relevance with both token and utterance. (3) Experimental
results show that our proposed model achieves new state-of-the-art
performance.

##  2 METHOD

The architecture of our method is illustrated in Figure 2. Our model mainly
consists of three components: Input chunking is designed for long meeting
transcripts. Query-Utterance relevance module is used to calculate the
similarity between each utterance and the query. Then by end-to-end training
of joint attention module, the summary is generated.

###  2.1 Input Chunking

In order to feed the whole meeting into the model, we follow the preprocessing
step [7] to split the source meeting into several fixed-length overlapping
chunks, which are 50% overlapping. As shown in Figure 2, each chunk is
concatenated with the query in front of it. These chunks are fed into a
standard Transformer encoder. Then we concatenate these encodings to get a
single embedding sequence and pass it to the modified decoder.

###  2.2 Query-Utterance Relevance

A typical meeting consists of multiple interactions with multiple members. We
consider one statement by a participant in the meeting transcript as an
utterance, the meeting transcript $U$ is the form of a sequence of utterances
$(u_{1},u_{2},...,u_{n})$. To get the Query-Utterance relevance, we calculate
the similarity between the embeddings between them.

SBERT [8] is proposed for dense retrieval, which adopts the siamese network
architecture to encode the sentence pair separately and uses cosine-similarity
to get the similarity between them.

For given query $q$ and utterance $u$, we use SBERT to encode them to sentence
embedding $e_{q}$ and $e_{u}$. The query $q$ contains $l_{q}$ tokens
$q=(w_{i},w_{2},...,w_{l_{q}})$, the utterance $u$ contains $l_{u}$ tokens
$u_{i}=(t_{1},t_{2},...,t_{l_{u}})$.

SBERT contains a pre-trained BERT for sentence pair regression task and a
mean-pooling layer. The sentence embedding $e_{q}$ and $e_{u}$ are as follows:

$e_{q}=\frac{1}{l_{q}}\sum_{i=1}^{l_{q}}(e_{q_{i}});\ \
e_{u}=\frac{1}{l_{u}}\sum_{i=1}^{l_{u}}(e_{u_{i}})$ (1)
$(e_{q_{1}},e_{q_{2}},...,e_{q_{l}})=BERT(w_{i},w_{2},...,w_{l_{q}})$ (2)
$(e_{u_{1}},e_{u_{2}},...,e_{u_{l}})=BERT(t_{i},t_{2},...,t_{l_{u}})$ (3)

The similarity of query $q$ and utterance $u$ is measured with cosine
similarity.

$s=cosine\raisebox{0.0pt}{-}sim(e_{q},e_{u})$ (4)

###  2.3 Joint Attention Module

After getting the Query-Utterance relevance, we propose a joint attention
module to fuse query relevance at different granularities and incorporate the
relevance with attention mechanism in the generation process. Since the
concatenation of the query and meeting transcript is used as the encoder’s
input, the query and utterance interact implicitly through the attention
mechanism at the token level.

While calculating similarity, the query and utterance interact explicitly
through the Query-Utterance relevance module at the sentence level. We believe
that paying attention to the different granularities of correlation does help
to better generate summaries related to the query.

In this module, query relevance at different granularities are fused by joint
attention mechanism. Then we incorporate the Query-Utterance relevance in the
generation process to generate summaries more related to the query.

Given a query $q$ and utterances $U=(u_{1},u_{2},...,u_{n})$, for each
utterance $u_{i}$, we can get the similarity $s_{i}$ of them according to the
Query-Utterance relevance module. The Query-Utterance relevance is
$S=(s_{1},s_{2},...,s_{n})$. As shown in Figure 2, to ensure the tokens in the
same utterance should be given the same Query-Utterance relevance score, if
$u_{i}$ contains $l_{i}$ tokens, $s_{i}$ should repeat $l_{i}$ times. Then all
the Query-Utterance relevance score will be expand to the same shape with
Encoder-Decoder cross attention weights $\alpha$, which is called Query-
Utterance attention weights $A_{Q\raisebox{0.0pt}{-}U}$. Finally, we apply
weighted-sum to Encoder-Decoder cross attention weights and Query-Utterance
attention weights to get the $l$-th transformer decoder layer’s attention
weights $\alpha^{l}$.

$Attention(Q,K,V,A_{Q\raisebox{0.0pt}{-}U})=softmax(\alpha^{l}\cdot V)$ (5)
$\alpha^{l}=(1-\beta)\cdot\frac{QK^{T}}{\sqrt{d}}+\beta\cdot
A_{Q\raisebox{0.0pt}{-}U}$ (6)

where $d$ is the dimension of the query matrix $Q$ and key matrix $K$, $\beta$
is a weight hyperparameter.

##  3 EXPERIMENTS

###  3.1 Setup

####  3.1.1 Implementation Details

Models are implemented using the PyTorch framework. We use the pre-trained
BART111The checkpoint is “facebook/bart-large”. from the Transformers library
as the base abstractive model, and dense retrieval model RoBERTa222The
checkpoint is ”sentence-transformers/all-roberta-large-v1”. from sentence-
transformers [8] library as the sentence similarity model.

All experiments are conducted on 2 NVIDIA RTX 3090 GPUs(24G memory). Each
model is trained for 10 epochs, the average running time is around 12 hours.
Weight hyperparameter $\beta$ is 0.6 in equation 6. Chunk size is 512, max
number of chunks is 32. Learning rate is 5e-6.

Models were evaluated using the ROUGE metrics [9] in the SummEval toolkit [10]
and each pair of results was subjected to t-test to confirm the effectiveness
of our method.

####  3.1.2 Datasets Details

QMSum [6] is a query-focused meeting summarization dataset, which consists of
1,808 query-summary pairs over 232 meetings from product design, academic, and
political committee meetings. QMSum also contains additional manual
annotations such as topic segmentation and relevant spans related to the
reference summary.

####  3.1.3 Baselines Details

We compare the proposed method with several baselines. TextRank [11] is a
graph-based ranking model to extract key information. PGN [12] uses pointer
mechanism to copy tokens from source texts. BART [13] is an encoder-decoder
Transformer model pre-trained using a denoising objective. HMNet [14] utilizes
a hierarchical attention structure and cross-domain pre-training for meeting
summarization. SUMMN [15] is a multi-stage summarization framework for long
input dialogues and documents. Point Network+PGNet and Point Network+BART [6]
adopt a two-stage approach of locate-then-summarize for long meeting
summarization. SBERT+BART is another two-stage baseline proposed in this
paper. Longformer [16] replaces the quadratic self-attention mechanism with a
combination of local attention and sparse global attention. SEGENC [7] splits
the meeting into fixed-length segments, then concatenates the segment
embeddings into a single sequence and passes it to the decoder. Without Query-
Utterance attention, our model can be regarded as the replication of SEGENC.

Models | ROUGE-1 | ROUGE-2 | ROUGE-L
---|---|---|---
TextRank [11] | 16.27 | 2.69 | 15.41
PGNet [12] | 28.74 | 5.98 | 25.13
BART [13] | 29.20 | 6.37 | 25.49
HMNet [14] | 32.29 | 8.67 | 28.17
SUMMN [15] | 34.03 | 9.28 | 29.48
DYLE [17] | 34.42 | 9.71 | 30.10
DialogLM [18] | 33.69 | 9.32 | 30.01
two-stage model |  |  |
Point Network + PGNet [6] | 31.37 | 8.47 | 27.08
Point Network + BART [6] | 31.74 | 8.53 | 28.21
SBERT + BART | 34.21 | 10.37 | 29.80
end-to-end model |  |  |
Longformer [16] | 34.18 | 10.32 | 29.95
SEGENC [7] | 37.05 | 13.03 | 32.62
Ours | 37.99 | 13.66 | 33.36
Ours(w/o Q-U Attention) | 37.03 | 12.93 | 32.47

Table 1:  ROUGE-F1 scores for different models on QMSum dataset.

###  3.2 Results & Analysis

The performances of our method and baselines are summarized in Table 1.
Experimental results show that our method significantly outperforms the
baselines (p <0.05) and achieves new state-of-the-art results on QMSum
dataset.

To feed the input into the fixed-length model like BART, we have to truncate
the source meeting to fixed length. Experimental results show that truncation
operations lead to decreased performance. For generic summarization, lead bias
reduces the impact of truncation operations on summarization. But for QFMS,
highlights related to the query may appear in different parts of the meeting
transcripts. Therefore QFMS is particularly affected by truncation operations.

Besides, We observe that in general end-to-end models perform better than the
two-stage models once the long input problem is solved. It shows that
benefiting from attention mechanism, existing end-to-end models have a certain
ability to concentrate on the parts related to the query and generate
summaries. Based on previous end-to-end models, our model achieves a higher
ROUGE score by incorporating Query-Utterance relevance in the generation
process.

To verify the effectiveness of Query-Utterance relevance, we conduct an
ablation experiment. Our model significantly outperformed the model without
Query-Utterance relevance (p <0.05). Experimental results show that the model
without Query-Utterance relevance reduces 0.96 ROUGE-1, 0.73 ROUGE-2, 0.89
ROUGE-L scores, which demonstrates the effectiveness of incorporating the
Query-Utterance relevance in end-to-end models.

Models | ROUGE-1 | ROUGE-2 | ROUGE-L
---|---|---|---
BART | 10.10 | 1.84 | 9.27
SBERT+BART | 13.21 | 3.36 | 12.25
SEGENC | 14.32 | 5.18 | 13.74
Ours | 16.06 | 5.90 | 15.33

Table 2:  ROUGE recall score between annotated query-relevant meeting
utterances and the summary.

###  3.3 Query-Relevant Information Recall

QMSum dataset contains annotations of utterances related to the query. We use
ROUGE recall score between annotated query-relevant meeting utterances and the
summary to evaluate the ability to capture the information related to the
query. Experimental result is shown in Table 2. It shows our model achieves
significant recall score improvement compared with the model without Query-
Utterance relevance, which demonstrates the effectiveness of the Query-
Utterance relevance in highlight the key information related to query (p
<0.01).

Models | Flu. | QR. | FC.
---|---|---|---
Gold | 4.88 | 4.90 | 4.92
BART | 4.48 | 3.78 | 3.64
SEGENC | 4.24 | 3.96 | 4.02
Ours | 4.32 | 4.44 | 4.28

Table 3:  Human evaluation on Fluency (Flu.), Query Relevance (QR.) and
Factual Consistency (FC.) for QMSum.

###  3.4 Human Evaluation

We further conduct a manual evaluation to assess the models. We randomly
select 50 samples from QMSum and ask 10 professional linguistic evaluators to
score the ground truth and summaries generated by 3 models according to 3
metrics: fluency, query relevance and factual consistency. Each metric is
rated by 3 evaluators from 1 (worst) to 5 (best) and the scores for each
summary are averaged.

As shown in Table 3. With Query-Utterance attention, our model significantly
outperforms original BART and SEGENC on query relevance, which shows the
effectiveness of joint training of query-token and token-utterance attention.
Results on factual consistency scores also demonstrate the contribution of
modeling query relevance to improving factual consistency. And it also shows
the fused attention mechanism results in a slight decrease in fluency scores.

##  4 Conclusion

This paper presents that query relevance at different granularities
complements each other and contributes to QFMS. To take different
granularities into consideration, we propose a query-aware framework by
jointly modeling token and utterance, which models explicit Query-Utterance
relevance and employs a joint attention module to incorporate the relevance in
the generation process with attention mechanism. Experiments demonstrate the
effectiveness of Query-Utterance relevance in generating summaries more
related to the query.

## References

  * [1] Marina Litvak and Natalia Vanetik,  “Query-based summarization using MDL principle,”  in Proceedings of the MultiLing 2017 Workshop on Summarization and Summary Evaluation Across Source Types and Genres, Valencia, Spain, Apr. 2017, pp. 22–31, Association for Computational Linguistics.
  * [2] Tal Baumel, Matan Eyal, and Michael Elhadad,  “Query focused abstractive summarization: Incorporating query relevance, multi-document coverage, and summary length constraints into seq2seq models,”  arXiv preprint arXiv:1801.07704, 2018.
  * [3] Md Tahmid Rahman Laskar, Enamul Hoque, and Jimmy Xiangji Huang,  “WSL-DS: Weakly supervised learning with distant supervision for query focused multi-document abstractive summarization,”  in Proceedings of the 28th International Conference on Computational Linguistics, Barcelona, Spain (Online), Dec. 2020, pp. 5647–5654, International Committee on Computational Linguistics.
  * [4] Yumo Xu and Mirella Lapata,  “Coarse-to-fine query focused multi-document summarization,”  in Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), Online, Nov. 2020, pp. 3632–3645, Association for Computational Linguistics.
  * [5] Yumo Xu and Mirella Lapata,  “Generating query focused summaries from query-free resources,”  in Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), Online, Aug. 2021, pp. 6096–6109, Association for Computational Linguistics.
  * [6] Ming Zhong, Da Yin, Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, and Dragomir Radev,  “QMSum: A new benchmark for query-based multi-domain meeting summarization,”  in Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Online, June 2021, pp. 5905–5921, Association for Computational Linguistics.
  * [7] Jesse Vig, Alexander R. Fabbri, Wojciech Kryściński, Chien-Sheng Wu, and Wenhao Liu,  “Exploring neural models for query-focused summarization,” 2021.
  * [8] Nils Reimers and Iryna Gurevych,  “Sentence-BERT: Sentence embeddings using Siamese BERT-networks,”  in Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), Hong Kong, China, Nov. 2019, pp. 3982–3992, Association for Computational Linguistics.
  * [9] Chin-Yew Lin,  “ROUGE: A package for automatic evaluation of summaries,”  in Text Summarization Branches Out, Barcelona, Spain, July 2004, pp. 74–81, Association for Computational Linguistics.
  * [10] Alexander R. Fabbri, Wojciech Kryściński, Bryan McCann, Caiming Xiong, Richard Socher, and Dragomir Radev,  “SummEval: Re-evaluating summarization evaluation,”  Transactions of the Association for Computational Linguistics, vol. 9, pp. 391–409, 2021.
  * [11] Rada Mihalcea and Paul Tarau,  “TextRank: Bringing order into text,”  in Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, Barcelona, Spain, July 2004, pp. 404–411, Association for Computational Linguistics.
  * [12] Abigail See, Peter J. Liu, and Christopher D. Manning,  “Get to the point: Summarization with pointer-generator networks,”  in Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Vancouver, Canada, July 2017, pp. 1073–1083, Association for Computational Linguistics.
  * [13] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer,  “BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension,”  in Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, Online, July 2020, pp. 7871–7880, Association for Computational Linguistics.
  * [14] Chenguang Zhu, Ruochen Xu, Michael Zeng, and Xuedong Huang,  “A hierarchical network for abstractive meeting summarization with cross-domain pretraining,”  in Findings of the Association for Computational Linguistics: EMNLP 2020, Online, Nov. 2020, pp. 194–203, Association for Computational Linguistics.
  * [15] Yusen Zhang, Ansong Ni, Ziming Mao, Chen Henry Wu, Chenguang Zhu, Budhaditya Deb, Ahmed H Awadallah, Dragomir Radev, and Rui Zhang,  “Summ^ n: A multi-stage summarization framework for long input dialogues and documents,”  in ACL 2022, 2022.
  * [16] Iz Beltagy, Matthew E. Peters, and Arman Cohan,  “Longformer: The long-document transformer,”  arXiv:2004.05150, 2020.
  * [17] Ziming Mao, Chen Henry Wu, Ansong Ni, Yusen Zhang, Rui Zhang, Tao Yu, Budhaditya Deb, Chenguang Zhu, Ahmed Awadallah, and Dragomir Radev,  “DYLE: Dynamic latent extraction for abstractive long-input summarization,”  in Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Dublin, Ireland, May 2022, pp. 1687–1698, Association for Computational Linguistics.
  * [18] Ming Zhong, Yang Liu, Yichong Xu, Chenguang Zhu, and Michael Zeng,  “Dialoglm: Pre-trained model for long dialogue understanding and summarization,”  in AAAI, 2022.