Let $(\Omega_{n},\mathbb{P}_{n})$ be probability spaces, and let
$\widehat{L}_{n}\coloneqq\widehat{L}_{n}(\cdot\mid\omega_{n})$ be random
distributions on the metric space $(\mathcal{D},d)$, that is,
$\widehat{L}_{n}$ is a probability distribution on $\mathcal{D}$ for
$\mathbb{P}_{n}$-almost all $\omega_{n}\in\Omega_{n}$. Then, $\widehat{L}_{n}$
is defined to _converge weakly in probability_ towards a Borel distribution
$L$ on $\mathcal{D}$ if

$\mathbb{E}_{Z_{n}\sim\widehat{L}_{n}}\bigl{[}f(Z_{n})\bigr{]}\stackrel{{\scriptstyle\mathbb{P}_{n}}}{{\longrightarrow}}\mathbb{E}_{Z\sim
L}\bigl{[}f(Z)\bigr{]}\quad\text{for all }f\in C(\mathcal{D},[0,1]),$ (A.2)

where $C(\mathcal{D},[0,1])$ denotes the set of continuous functions from
$\mathcal{D}$ to $[0,1]$, and
$\stackrel{{\scriptstyle\mathbb{P}_{n}}}{{\longrightarrow}}$ is the
convergence in probability w.r.t. $\mathbb{P}_{n}$.

By the Portmanteau theorem, the above convergence of expectations of
continuous functions could also be expressed as convergence in distribution of
$\widehat{L}_{n}$ to $L$, although the fact that this only needs to hold in
probability w.r.t. $L_{n}$ necessitates the slightly more inconvenient
notation in terms of all $f\in C(\mathcal{D},[0,1])$ as presented above.

With this definition we are ready to state the necessary auxiliary results for
Theorem 3.4.

######  Proposition A.5.

Let (M1)–(M3) hold and assume that the law of
$\sqrt{M_{n}}({\bm{Y}}^{*}/M_{n}-{\bm{Y}}/n)$ (conditioned on ${\bm{Y}}$)
converges weakly in probability towards
${\bm{Z}}\sim\mathcal{N}_{m}({\bm{0}},{\bm{\Sigma}})$. Also let
$f:\mathbb{R}^{m}\to\mathbb{R}$ be any function that is Hadamard directionally
differentiable at ${\bm{p}}$ in almost any direction. Then, there exists a
sequence of sets $(A_{n})_{n\in\mathbb{N}}\subseteq\mathbb{R}^{d}$ with
$\mathbb{P}({\bm{Y}}\in A_{n})\to 1$ as $n\to\infty$ such that the following
holds:

  1. (i)

Let $M_{n}\to\infty$ as $n\to\infty$ with $M_{n}=o(n)$. Then

$\sqrt{M_{n}}\Bigl{(}f\bigl{(}{\bm{Y}}^{*}/M_{n}\bigr{)}-f({\bm{Y}}/n)\Bigl{)}\quad\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\quad f^{\prime}_{{\bm{p}}}({\bm{Z}})$ (A.3)

where
${\bm{Z}}^{\operatorname{\mathrm{XC}}}=(Z_{S}^{\operatorname{\mathrm{XC}}})_{S\in\mathcal{S}}$
is the limiting distribution from Theorem 3.1.

  2. (ii)

Let $M_{n}\coloneqq n$ and assume that $f$ is fully Hadamard differentiable at
${\bm{p}}$ (in almost any direction). Then (A.3) still holds.

###### Proof.

For A.3 and (ii) see Dümbgen (1993, Propositions 2 and 1, respectively). Note
that all their basic assumptions are satisfied in our case:

  * •

Their assumption A1 is satisfied by the central limit theorem:
$\sqrt{n}({\bm{Y}}/n-{\bm{p}})$ converges in distribution towards the tight
Borel distribution $\mathcal{N}_{m}({\bm{0}},{\bm{\Sigma}})$ on
$\mathbb{R}^{m}$.

  * •

Their assumption A2 is equivalent to our assumption of weak convergence in
probability here.

  * •

Their assumption B1 is trivially satisfied since ${\bm{p}}$ does not depend on
$n$.

  * •

Their assumption B2 is a slightly weaker version of our assumption on Hadamard
directional differentiability at ${\bm{p}}$.

Notice that, as the proof of Dümbgen (1993, Propositions 1 and 2) reveals,
both claims only hold on a sequence of sets
$(A_{n})_{n\in\mathbb{N}}\subset\mathbb{R}^{d}$ s.t.
$\mathbb{P}({\bm{Y}}\notin A_{n})\to 0$ as $n\to\infty$. ∎

######  Proposition A.6.

Let (M1)–(M3) hold and let $M_{n}\to\infty$. Obtain ${\bm{Y}}^{*}$ by sampling
$M_{n}$ times out of ${\bm{Y}}$. Then, for almost every sample ${\bm{Y}}$, the
distribution of $\sqrt{M_{n}}({\bm{Y}}^{*}/M_{n}-{\bm{Y}}/n)$, conditioned on
${\bm{Y}}$, converges weakly in probability towards
$\mathcal{N}_{m}({\bm{0}},{\bm{\Sigma}})$.

###### Proof.

See Politis et al. (1999, Proposition 1.4.2 (iii)). Note that the covariance
convergence condition they impose is trivially satisfied in our case since we
sample from a constant distribution $\nu$ (or rather $n$ times from
$\mathrm{Bin}(1,{\bm{p}})$) which does not depend on $n$.

Also notice that their Proposition 1.4.2 (iii) even yields weak convergence
_almost surely_ (i.e. Equation A.2 with almost sure convergence replacing
convergence in probability in (A.2)) which obviously implies weak convergence
in probability. For our purposes, the latter will be sufficient. A more
accessible version of this theorem can be found in Bickel and Freedman (1981,
Theorem 2.2 (a)) who also show almost sure convergence. ∎

###### Proof of Theorem 3.4.

Under (M1)–(M3) , the weak convergence assumption of Proposition A.5 is
satisfied by Proposition A.6. Note that the XCut functional
$g_{S}^{\operatorname{\mathrm{XC}}}$ as defined in (2.2) is Hadamard
directionally differentiable at ${\bm{p}}$ in any direction by Assumption
(M3), and the minimum function
$\operatorname{min}:\mathbb{R}^{|S|}\to\mathbb{R}$ is Hadamard directionally
differentiable anywhere in any direction, see Lemma A.2 (iii). Consequently,
the functional

$f:\mathbb{R}^{m}\to\mathbb{R},\quad{\bm{x}}=(x_{1},\ldots,x_{m})\mapsto\min_{S\in\mathcal{S}}\sum_{{i\in
S,j\in{S}^{\mathsf{c}},\;i\sim
j}}\frac{x_{i}x_{j}}{\operatorname{bal}_{S}^{\operatorname{\mathrm{XC}}}(x_{1},\ldots,x_{m})}$

is Hadamard directionally differentiable at ${\bm{p}}$ in ${\bm{X}}$-almost
any direction. Thus, by Proposition A.5 A.3,

$\Bigl{(}\sqrt{M_{n}}\bigl{(}{\operatorname{\mathrm{XC}}}_{S}(\mathcal{G}_{M_{n}}^{*})-\operatorname{\mathrm{XC}}_{S}(\mathcal{G}_{n})\bigr{)}\Bigr{)}_{S\in\mathcal{S}}\quad\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\quad{\bm{Z}}^{\operatorname{\mathrm{XC}}}$

and therefore Theorem 3.4 3.3. Analogously, claim (ii) follows from
Proposition A.5 (ii), because $f$ is fully Hadamard directionally
differentiable at ${\bm{p}}$ if and only if the balancing terms
$\operatorname{bal}_{S}^{\operatorname{\mathrm{XC}}}$ is, too, _and_ the
partition that attains the minimum XCut value is unique (see Lemma A.2 (iii)).
∎

###  A.4 Behaviour of the asymptotic variance

Consider the variance
$\operatorname{Var}(Z_{S,t}^{\operatorname{\mathrm{XC}}})$ of the limiting
distribution for a fixed $S\in\mathcal{S}$. We are interested in its behaviour
as a function of $t$, i.e. of whether there is a discernible attribute
characterizing its course, such as monotonicity. For this, again consider the
regular $3\times 3$ grid and define four distributions and the partition $S$
as in Figure 10. These distributions were picked to exemplify cases where the
variance of the limiting distribution $Z_{S,t}^{\operatorname{\mathrm{XC}}}$
corresponding to a “reasonable” partition $S\in\mathcal{S}$ behaves in
completely different ways when considered as a function of $t$. In fact, $S$
attains the minimal RCut value for all the distributions is displayed in (b),
(c) and (d) if $t=1$.

$\bm{\varepsilon}$$\bm{\varepsilon}$$\bm{\varepsilon}$$\bm{2}$$\bm{2}$$\bm{\varepsilon}$$\bm{\varepsilon}$
(a) “Strange” distrib.

$\bm{\varepsilon}$$\bm{1}$$\bm{\varepsilon}$$\bm{\varepsilon}$$\bm{1}$$\bm{\varepsilon}$$\bm{\varepsilon}$$\bm{1}$$\bm{\varepsilon}$
(b) Unimodal distrib.

$\bm{1}$$\bm{\varepsilon}$$\bm{1}$$\bm{1}$$\bm{\varepsilon}$$\bm{1}$$\bm{1}$$\bm{\varepsilon}$$\bm{1}$
(c) Bimodal distrib.

$\bm{1}$$\bm{1}$$\bm{1}$$\bm{1}$$\bm{1}$$\bm{1}$$\bm{1}$$\bm{1}$$\bm{1}$ (d)
Uniform distrib.

Figure 10: Neighbourhood graph of four distributions on a $3\times 3$ grid (on
$D=[1,3]^{2}$ for convenience) with $m=9$ nodes ($m=7$ in (a)), $t=1$ and
$\varepsilon=0.4$. The blue nodes represent the fixed partition $S$ which
minimizes the RCut value. The number inside of a node represents its weight in
the underlying probability distribution without normalization to better
showcase their relation. The vertex and edge widths are proportional to their
respective weights.

Figure 11 shows that even in the simple case of a very small grid the limiting
variance follows no clear pattern as the neighbourhood distance $t$ increases.
It should be mentioned, however, that finding an example of a distribution
(and partition thereon) where the variance increased from $t=1$ to
$t=\sqrt{2}$ was more difficult and resulted in a more artificial example.
This could be an indication that a choice of $t=1$ is sufficient to obtain a
graph that can be cut to obtain reasonably “good” partitions. It would
certainly be an interesting avenue for further research to assess whether and
how the quality of a cut is related to its asymptotic variance. On another
note, in Figure 11 we only addressed the case of RCut here for simplicity,
though similar examples of distributions can be easily found for the other
cuts as well.

Figure 11: Variance of the limiting distribution of
$\smash{\sqrt{n}\big{(}\operatorname{\mathrm{RC}}_{S}(\mathcal{G}_{n})-\operatorname{\mathrm{RC}}_{S}(\mathcal{G})\big{)}}$
for the four distributions and the partition $S$ displayed in Figure 10,
plotted as a function over the neighbourhood distance $t$, whereupon
$\mathcal{G}_{n}$ and $\mathcal{G}$ depend by means of the graph structure,
see Definition 2.

###  A.5 Revisiting Example 1

In this section we revisit Example 1 and fill in all the details properly that
have been previously omitted. First, however, we require a small auxiliary
result that is also called upon in the main section to argue that
asymptotically, the components of a multinomial distribution are almost surely
distinct, namely the following Lemma A.7.

######  Lemma A.7.

Let ${\bm{Y}}\sim\operatorname{Mult}(n,{\bm{p}})$ for $n\in\mathbb{N}$ and
some probability vector ${\bm{p}}\in\mathbb{R}^{m}$, $m\in\mathbb{N}_{\geq
2}$. Then, for any $i,j\in V$, $i\neq j$, with $p_{i},p_{j}\in[0,1]$ (but not
both zero), it holds that $\mathbb{P}(Y_{i}=Y_{j})\to 0$ as $n\to\infty$.

###### Proof.

Let $i,j\in V$, $i\neq j$, be arbitrary, but fixed. If $p_{i}\neq p_{j}$, the
claim holds simply by the law of large numbers, so w.l.o.g. let $p_{i}=p_{j}$.
We apply the continuous mapping theorem on the function
$\langle{\bm{e}}_{i}-{\bm{e}}_{j},\cdot\rangle$ and obtain

$\frac{Y_{i}-Y_{j}}{\sqrt{n}}=\left\langle{\bm{e}}_{i}-{\bm{e}}_{j},\sqrt{n}\bigl{(}\tfrac{{\bm{Y}}}{n}-{\bm{p}}\bigr{)}\right\rangle\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\mathcal{N}\bigl{(}0,({\bm{e}}_{i}-{\bm{e}}_{j})^{\top}{\bm{\Sigma}}({\bm{e}}_{i}-{\bm{e}}_{j})\bigr{)}.$

Note that
$({\bm{e}}_{i}-{\bm{e}}_{j})^{\top}{\bm{\Sigma}}({\bm{e}}_{i}-{\bm{e}}_{j})=p_{i}(1-p_{i})+p_{j}(1-p_{j})+2p_{i}p_{j}>0$
since $0<p_{i},p_{j}<1$ (if $p_{i}$ or $p_{j}$ were equal to $1$, the claim
would be trivial) and not both are equal to zero by assumption. This shows
that the limiting distribution above is non-degenerate. Consequently, for any
$\varepsilon>0$

$\displaystyle\mathbb{P}(Y_{i}=Y_{j})\leq\mathbb{P}\left(-\varepsilon<\frac{Y_{i}-Y_{j}}{\sqrt{n}}\leq\varepsilon\right)$
$\displaystyle=F_{n}(\varepsilon)-F_{n}(-\varepsilon)$
$\displaystyle\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}F(\varepsilon)-F(-\varepsilon)=\mathbb{P}(-\varepsilon<Z_{ij}\leq\varepsilon),$

where $F_{n}$ and $F$ denote the cdf of $(Y_{i}-Y_{j})/\sqrt{n}$ and its
limiting distribution
$Z_{ij}:\sim\mathcal{N}\bigl{(}0,p_{i}+p_{j}-(p_{i}-p_{j})^{2}\bigr{)}$,
respectively. Since the right hand side of the above equation becomes
arbitrarily small as $\varepsilon\to 0$, we have $\mathbb{P}(Y_{i}=Y_{j})\to
0$ as $n\to\infty$ for any $i,j\in V$, $i\neq j$. ∎

We are ready to provide the full details of Example 1. Consider the graph
$\mathcal{G}=(V,E,{\bm{W}})$ depicted in Figure 3, i.e.
$V\coloneqq\\{1,2,3,4\\}$ and
$E\coloneqq\bigl{\\{}\\{1,2\\},\\{1,3\\},\\{2,4\\},\\{3,4\\}\bigr{\\}}$, where
the probability vector ${\bm{p}}=(1/4,1/4,1/4,1/4)$ (see also Figure 3 for an
illustration).

Before computing any limits, it is important to consider the case of
$|\operatorname{V^{\mathrm{loc}}}|=1$, where Xist does not return any
clustering. We seek to calculate the asymptotic probability of this event.
Note that

$\displaystyle\mathbb{P}(\operatorname{V^{\mathrm{loc}}}=\\{Y_{1}\\})$
$\displaystyle=\mathbb{P}\bigl{(}Y_{1}>Y_{2},Y_{1}>Y_{3},\max(Y_{2},Y_{3})>Y_{4}\bigr{)}$
$\displaystyle=\mathbb{P}\bigl{(}\\{Y_{1}>Y_{2},Y_{1}>Y_{3}\\}\setminus\\{Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2},Y_{4}>Y_{3}\\}\bigr{)}$
$\displaystyle=\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3})-\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2},Y_{4}>Y_{3}),$
(A.4)

where we used that $\mathbb{P}(Y_{i}=Y_{j})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}0$ by Lemma A.7. (In the following, this fact
will be used implicitly.) We calculate the first probability in (A.4) by
defining

${\bm{A}}\coloneqq\begin{bmatrix}-1&1&0&0\\\ -1&0&1&0\\\
\end{bmatrix}\quad\text{s.t.}\quad\frac{1}{\sqrt{n}}\begin{bmatrix}Y_{2}-Y_{1}\\\
Y_{3}-Y_{1}\end{bmatrix}={\bm{A}}\sqrt{n}\left(\frac{{\bm{Y}}}{n}-{\bm{p}}\right)\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\mathcal{N}({\bm{0}},{\bm{A}}^{\top}{\bm{\Sigma}}{\bm{A}})$

by the central limit theorem for ${\bm{Y}}/n$, where ${\bm{\Sigma}}$ is the
covariance matrix of $\operatorname{Mult}(1,{\bm{p}})$. Consequently, denoting
the distribution function of
$\mathcal{N}({\bm{0}},{\bm{A}}^{\top}{\bm{\Sigma}}{\bm{A}})$ by
$F_{{\bm{A}}{\bm{Z}}}$ and setting
${\bm{B}}\coloneqq\bigl{(}{\bm{A}}^{\top}{\bm{\Sigma}}{\bm{A}}\bigr{)}^{-1}$,

$\displaystyle\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3})=$
$\displaystyle\mathbb{P}\biggl{(}\frac{1}{\sqrt{n}}\begin{bmatrix}Y_{2}-Y_{1}\\\
Y_{3}-Y_{1}\end{bmatrix}<{\bm{0}}\biggr{)}$
$\displaystyle\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}F_{{\bm{A}}{\bm{Z}}}({\bm{0}})$
$\displaystyle=\int_{(-\infty,0)^{2}}\frac{1}{2\pi\sqrt{\det{\bm{A}}^{\top}{\bm{\Sigma}}{\bm{A}}}}\exp\Bigl{(}-\tfrac{1}{2}\bigl{(}{\bm{x}}^{\top}\bigl{(}{\bm{A}}^{\top}{\bm{\Sigma}}{\bm{A}}\bigr{)}^{-1}{\bm{x}}\bigr{)}\Bigr{)}d{\bm{x}}$
$\displaystyle=\int_{-\infty}^{0}\int_{-\infty}^{0}\frac{1}{2\pi\sqrt{\tfrac{16}{3}}}\exp\Bigl{(}-\tfrac{1}{2}\bigl{(}\tfrac{8}{3}x_{1}^{2}-\tfrac{8}{3}x_{1}x_{2}+\tfrac{8}{3}x_{2}^{2}\bigr{)}\Bigr{)}dx_{1}dx_{2}$
$\displaystyle=\frac{1}{3}.$

To compute the second term in (A.4), rewrite

$\displaystyle\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2},Y_{4}>Y_{3})$
$\displaystyle\qquad=\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2})-\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2},Y_{3}>Y_{4})$
$\displaystyle\qquad=\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2})-\mathbb{P}(Y_{1}>Y_{3},Y_{3}>Y_{4},Y_{4}>Y_{2})$
(A.5)

and compute both probabilities separately. This can be done by choosing

${\bm{A}}\coloneqq\begin{bmatrix}-1&1&0&0\\\ -1&0&1&0\\\
0&1&0&-1\end{bmatrix}\,\text{ for the first term, and
}\,{\bm{A}}\coloneqq\begin{bmatrix}-1&0&1&0\\\ 0&1&0&-1\\\
0&0&-1&1\end{bmatrix}$

for the second, and then proceeding as shown above. For brevity, we will omit
the corresponding calculations as they are analogous to the above. Putting
everything together, we arrive at

$\mathbb{P}(\operatorname{V^{\mathrm{loc}}}=\\{Y_{1}\\})=\mathbb{P}(Y_{1}>Y_{2},Y_{1}>Y_{3})\\\
-\bigl{(}P(Y_{1}>Y_{2},Y_{1}>Y_{3},Y_{4}>Y_{2})-\mathbb{P}(Y_{1}>Y_{3},Y_{3}>Y_{4},Y_{4}>Y_{2})\bigr{)}\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\frac{1}{6}.$

Analogously, any of the other vertices could be the sole local maximum, so
that finally

$\mathbb{P}(|\operatorname{V^{\mathrm{loc}}}|=1)=\sum_{i=1}^{4}\mathbb{P}(\operatorname{V^{\mathrm{loc}}}=\\{Y_{i}\\})=4\,\mathbb{P}(\operatorname{V^{\mathrm{loc}}}=\\{Y_{1}\\})\stackrel{{\scriptstyle
n\to\infty}}{{\longrightarrow}}\frac{2}{3}.$

Consequently, it makes no sense to use the standard version of Xist for such a
simple example; instead redefine $\operatorname{V^{\mathrm{loc}}}\coloneqq V$
(i.e. simply iterate over all vertices instead of only local maxima).

Consider the fact that the $12$-MinCut of the population graph is attained by
$S_{1}\coloneqq\\{1\\}$, $S_{2}\coloneqq\\{2\\}$ and
$S_{13}\coloneqq\\{1,3\\}$, although only the latter yields the output
$\operatorname{\mathrm{Xist}}(\mathcal{G})=2$ of the Xist algorithm for NCut.
In this simple case, we can compute the (asymptotic) probabilities that the
minimum is attained by either of the above partitions manually: As
$n\to\infty$,

$\displaystyle\mathbb{P}\bigl{(}\operatorname{\mathrm{MC}}(S_{13})<\operatorname{\mathrm{MC}}(S_{1}),\operatorname{\mathrm{MC}}(S_{13})<\operatorname{\mathrm{MC}}(S_{2})\bigr{)}$
$\displaystyle\qquad=\mathbb{P}(Y_{1}Y_{2}+Y_{3}Y_{4}<Y_{1}Y_{2}+Y_{1}Y_{3},Y_{1}Y_{2}+Y_{3}Y_{4}<Y_{1}Y_{2}+Y_{2}Y_{4})$
$\displaystyle\qquad=\mathbb{P}(0<Y_{4}<Y_{1},\,\,0<Y_{3}<Y_{2})\to\frac{1}{4},$
$\displaystyle\mathbb{P}\bigl{(}\operatorname{\mathrm{MC}}(S_{1})<\operatorname{\mathrm{MC}}(S_{2}),\operatorname{\mathrm{MC}}(S_{1})<\operatorname{\mathrm{MC}}(S_{13})\bigr{)}$
$\displaystyle\qquad=\mathbb{P}(\operatorname{\mathrm{MC}}(S_{2})<\operatorname{\mathrm{MC}}(S_{1}),\operatorname{\mathrm{MC}}(S_{2})<\operatorname{\mathrm{MC}}(S_{13}))\to\frac{3}{8},$

by symmetry and the fact that all three have to sum up to $1$ since
$\mathbb{P}(Y_{i}=Y_{j})\to 0$ for any $i,j\in V$, $i\neq j$, by Lemma A.7.

Returning to the $st$-MinCut probabilities, one obtains the same probabilities
(for the appropriately re-indexed partitions) for the $13$-, $24$\- and
$34$-MinCuts. The diagonal partitions, i.e. the $14$\- and $23$-MinCuts, can
be computed similarly, e.g. for the for the $23$-MinCut, $S_{2}=\\{2\\}$ and
$S_{3}=\\{3\\}$ occur with probability $1/2$ each, and
$S_{12}\coloneqq\\{1,2\\}$ and $S_{13}=\\{1,3\\}$ are almost surely not
attained for large $n$.

In order to determine the limiting distribution notice that under the
condition that $Y_{i}\neq Y_{j}$ for $i\neq j$ (which is satisfied
asymptotically by Lemma A.7), either the partition $S_{12}=\\{1,2\\}$ or
$S_{13}=\\{1,3\\}$ attains the $ij$-MinCut for at least one pair
$i,j\in\\{1,2,3,4\\}$, $i\neq j$, that is considered by Xist. To see why,
assume w.l.o.g. that Xist starts with the $21$-MinCut. We distinguish four
cases:

  * •

$Y_{1}>Y_{3},Y_{2}>Y_{4}$: Xist computes the $21$-MinCut partition
$\\{1,3\\}$, updates $\tau=(1,2,2,1)$, then the $32$-MinCut partition
$\\{3\\}$, updates $\tau=(1,2,3,1)$, and finally the $41$-MinCut partition
$\\{4\\}$.

  * •

$Y_{1}>Y_{3},Y_{2}<Y_{4}$: Xist computes the $21$-MinCut partition $\\{2\\}$,
updates $\tau=(1,2,1,1)$, then the $31$-MinCut partition $\\{3\\}$, updates
$\tau=(1,2,3,1)$, and finally the $41$-MinCut partition $\\{1,2\\}$.

  * •

$Y_{1}<Y_{3},Y_{2}>Y_{4}$: Xist computes the $21$-MinCut partition $\\{1\\}$,
updates $\tau=(1,2,2,2)$, then the $32$-MinCut partition $\\{1,2\\}$, updates
$\tau=(1,2,3,3)$, and finally the $43$-MinCut partition $\\{4\\}$.

  * •

$Y_{1}<Y_{3},Y_{2}<Y_{4}$: If $Y_{1}Y_{4}>Y_{2}Y_{3}$, Xist computes the
$21$-MinCut partition $\\{2\\}$, updates $\tau=(1,2,1,1)$, then the
$31$-MinCut partition $\\{1\\}$, then updates $\tau=(1,2,3,3)$. Otherwise,
i.e. if $Y_{1}Y_{4}<Y_{2}Y_{3}$, Xist computes the $21$-MinCut partition
$\\{1\\}$, updates $\tau=(1,2,2,2)$, then the $32$-MinCut partition $\\{2\\}$,
then updates $\tau=(1,2,3,3)$. Finally, in both cases (so also if
$Y_{1}Y_{4}=Y_{2}Y_{3}$), the $43$-MinCut partition $\\{1,4\\}$ is computed.

Hence, Xist considers either $S_{12}\coloneqq\\{1,2\\}$ or
$S_{13}\coloneqq\\{1,3\\}$ in either case, and, asymptotically, both are
returned with probability $1/2$ each as all the above cases have the same
probability of occurring. Since both $S_{12}$ and $S_{13}$ yield the same
minimal NCut value, Xist must return the empirical equivalent of the optimal
population NCut value
$\operatorname{\mathrm{NC}}_{S_{12}}(\mathcal{G})=\operatorname{\mathrm{NC}}_{S_{13}}(\mathcal{G})=2$.
As a side note, the basic Xvst algorithm from Suchan et al. (2023) that will
be introduced in the following Section A.6 returns the same output as Xist, so
both algorithms attain the same limiting distribution in this example.

Continuing, it thus suffices to consider the limiting distribution of
$\operatorname{\mathrm{NC}}_{S_{12}}(\mathcal{G}_{n})$ and
${\operatorname{\mathrm{NC}}}_{S_{13}}(\mathcal{G}_{n})$. Together, they
converge in distribution to
${\bm{Z}}^{\operatorname{\mathrm{NC}}}:\sim\mathcal{N}_{2}({\bm{0}},{\bm{0}})=\delta_{(0,0)}$
(and thus also in probability), where the degenerate covariance matrix
${\bm{0}}\in\mathbb{R}^{2\times 2}$ consists of zeros only. By the Hadamard
delta method (i.e. Theorem A.3), the limiting distribution of
$\sqrt{n}(\operatorname{\mathrm{NC}}(\mathcal{G}_{n})-\operatorname{\mathrm{NC}}(\mathcal{G}))$
is $\min{\bm{Z}}^{\operatorname{\mathrm{NC}}}=\delta_{0}$.

Note that in this scenario we may not apply Theorem A.9 since (A4) is
violated: Both $S_{12}$ and $S_{13}$ satisfy $q_{i,S_{12}}=q_{i,S_{13}}$ for
all $i\in V$, and both $S_{12}$ and $S_{13}$ attain the $14$-MinCut.
Interestingly, despite this, neither $S_{12}$ nor $S_{13}$ can ever attain the
empirical $14$-MinCut since (by Lemma A.7)

$\displaystyle\operatorname{\mathrm{MC}}_{S_{12}}(\mathcal{G}_{n})=\operatorname{\mathrm{MC}}^{14}(\mathcal{G}_{n})$
$\displaystyle\iff Y_{1}Y_{3}+Y_{2}Y_{4}<Y_{1}Y_{3}+Y_{1}Y_{2}$
$\displaystyle\phantom{\iff}\qquad\text{ and
}Y_{1}Y_{3}+Y_{2}Y_{4}<Y_{3}Y_{4}+Y_{2}Y_{4}$ $\displaystyle\iff
Y_{4}<Y_{1},Y_{1}<Y_{4}$

which can never be satisfied. By symmetry, the same result holds for $S_{13}$.

Since the limiting distribution of
$\sqrt{n}\bigl{(}\operatorname{\mathrm{NC}}(\mathcal{G}_{n})-\operatorname{\mathrm{NC}}(\mathcal{G})\bigr{)}$
is degenerate, it is natural to increase the scaling, i.e. by considering
$n\bigl{(}\operatorname{\mathrm{NC}}(\mathcal{G}_{n})-\operatorname{\mathrm{NC}}(\mathcal{G})\bigr{)}$.
For this, however, we require the second-order delta method (see e.g.
(Serfling, 1980, Theorem 3.3B)). Let $S$ now denote either $S_{12}$ or
$S_{13}$. The Taylor expansion of the NCut functional
$g_{S}^{\operatorname{\mathrm{NC}}}(\cdot)$ (recall its definition in (2.2))
around ${\bm{Y}}/n$ is given by

$g_{S}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}\bigr{)}=g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})+(\nabla
g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}}))^{\top}\bigl{(}\tfrac{{\bm{Y}}}{n}-{\bm{p}}\bigr{)}+\frac{1}{2}\bigl{(}\tfrac{{\bm{Y}}}{n}-{\bm{p}}\bigr{)}^{\top}{\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}-{\bm{p}}\bigr{)}+{\scriptstyle\mathcal{O}}_{P}\bigl{(}\left\lVert\tfrac{{\bm{Y}}}{n}-{\bm{p}}\right\rVert^{2}\bigr{)},$

with ${\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}\in\mathbb{R}^{m\times m}$ the
Hessian of the function $g_{S}^{\operatorname{\mathrm{NC}}}$. As $\nabla
g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})=-4\cdot{\bm{1}}$, we have
$\bigl{(}g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})\bigr{)}^{\top}({\bm{Y}}/n-{\bm{p}})=0$
by ${\bm{Y}}^{\top}{\bm{1}}=n$ and ${\bm{p}}^{\top}{\bm{1}}=1$. Then, the
convergence of
$g_{S}^{\operatorname{\mathrm{NC}}}({\bm{Y}}/n)-g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})$
depends on the square term in the above Taylor expansion. Scaling by $n$
(instead of the usual $\sqrt{n}$) now yields a convergence to a nondegenerate
distribution: Since $\sqrt{n}({\bm{Y}}/n-{\bm{p}})$ converges in distribution
to $\widetilde{{\bm{Z}}}:\sim\mathcal{N}({\bm{0}},{\bm{\Sigma}})$ and
${\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}$ is symmetric, by the
aforementioned second-order delta method we obtain

$n\bigl{(}g_{S}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}\bigr{)}-g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})\bigr{)}=\frac{1}{2}\bigl{(}\tfrac{{\bm{Y}}}{n}-{\bm{p}}\bigr{)}^{\top}{\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}-{\bm{p}}\bigr{)}+{\scriptstyle\mathcal{O}}_{\mathbb{P}}\bigl{(}\left\lVert\tfrac{{\bm{Y}}}{n}-{\bm{p}}\right\rVert^{2}\bigr{)}\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\frac{1}{2}\widetilde{{\bm{Z}}}^{\top}{\bm{H}}g_{S_{12}}^{\operatorname{\mathrm{NC}}}\widetilde{{\bm{Z}}}.$
(A.6)

For any $S\in\mathcal{S}$, the Hessian
${\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})$ evaluates to

$\displaystyle\bigl{(}{\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}\bigr{)}_{k,\ell}$
$\displaystyle=\frac{\mathbbm{1}_{k\in
S_{\not\ni\ell},k\sim\ell}-\Bigl{(}\frac{\partial}{\partial
p_{\ell}}d_{k,S}\Bigr{)}\operatorname{\mathrm{NC}}_{S}(\mathcal{G})-d_{k,S}\,q_{\ell,S}}{\operatorname{vol}S\operatorname{vol}{S}^{\mathsf{c}}}$
$\displaystyle\quad-\frac{(q_{k,S}-d_{k,S}\operatorname{\mathrm{NC}}_{S}(\mathcal{G}))d_{\ell,S}}{(\operatorname{vol}S\operatorname{vol}{S}^{\mathsf{c}})^{2}}$
$\displaystyle\text{for}\quad d_{r,S}$
$\displaystyle\coloneqq\frac{\partial}{\partial
p_{r}}\operatorname{vol}S\operatorname{vol}{S}^{\mathsf{c}}=q_{r,S}(\operatorname{vol}S_{\ni
r}-\operatorname{vol}S_{\not\ni r})+2\operatorname{vol}S_{\not\ni
r}a_{r}\quad\text{for }r\in V$
$\displaystyle\text{s.t.}\quad\frac{\partial}{\partial p_{\ell}}d_{k,S}$
$\displaystyle=\begin{cases}2(q_{k,S}(a_{\ell}-q_{\ell,S})+q_{\ell,S}a_{k}+\operatorname{vol}S_{\not\ni
k}\mathbbm{1}_{\ell\sim k}),&S_{\ni k}=S_{\ni\ell}\\\
(2a_{k}-q_{k,S})(2a_{\ell}-q_{\ell,S})+q_{k,S}q_{\ell,S}+\operatorname{vol}V\mathbbm{1}_{\ell\sim
k},&S_{\ni k}=S_{\not\ni\ell},\end{cases}$

where we used the previously introduced abbreviation
$a_{r}\coloneqq\sum_{j\sim r}p_{j}$. Plugging in
${\bm{p}}=\tfrac{1}{4}\cdot\mathbf{1}$ yields
$\operatorname{vol}S=\tfrac{1}{4}$, $d_{r,S}=\tfrac{1}{4}$,
$\tfrac{\partial}{\partial
p_{\ell}}d_{k,S}=\tfrac{3}{16}+\tfrac{1}{4}\mathbbm{1}_{k\sim\ell}$ if $k\in
S_{\ni\ell}$ and $\tfrac{10}{16}+\tfrac{1}{2}\mathbbm{1}_{k\sim\ell}$
otherwise, everything for both $S=S_{12}$ and $S=S_{13}$. With this, we obtain
the two Hessians

${\bm{H}}g_{S_{12}}^{\operatorname{\mathrm{NC}}}=\begin{bmatrix}9&1&35&-5\\\
1&9&-5&35\\\ 35&-5&9&1\\\
-5&35&1&9\end{bmatrix}\quad\text{and}\quad{\bm{H}}g_{S_{13}}^{\operatorname{\mathrm{NC}}}=\begin{bmatrix}9&35&1&-5\\\
35&9&-5&1\\\ 1&-5&9&35\\\ -5&1&35&9\end{bmatrix}$

of $S_{12}$ and $S_{13}$, respectively. We first derive the asymptotic
distribution of a single partition $S\in\\{S_{12},S_{13}\\}$ by noticing that
$\widetilde{{\bm{Z}}}\sim\mathcal{N}({\bm{0}},{\bm{\Sigma}})$ can be written
as $\widetilde{{\bm{Z}}}={\bm{L}}{\bm{Z}}$ for
${\bm{Z}}\sim\mathcal{N}({\bm{0}},{\bm{I}}_{4})$ and the lower triangular
matrix ${\bm{L}}$ resultant from the Cholesky decomposition of
${\bm{\Sigma}}={\bm{L}}{\bm{L}}^{\top}$ (see (Tanabe and Sagae, 1992,
Corollary 3) for a general formula of ${\bm{L}}$ for any multinomial
covariance matrix $\Sigma$). Hence, (A.6) becomes

$\displaystyle
n\bigl{(}\operatorname{\mathrm{NC}}_{S_{12}}(\mathcal{G}_{n})-\operatorname{\mathrm{NC}}_{S_{12}}(\mathcal{G})\bigr{)}$
$\displaystyle\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\frac{1}{2}\widetilde{{\bm{Z}}}^{\top}{\bm{H}}g_{S_{12}}^{\operatorname{\mathrm{NC}}}\widetilde{{\bm{Z}}}=\frac{1}{2}{\bm{Z}}^{\top}{\bm{L}}^{\top}{\bm{H}}g_{S_{12}}^{\operatorname{\mathrm{NC}}}{\bm{L}}{\bm{Z}}$
$\displaystyle\begin{split}&=-\tfrac{1}{6}Z_{1}^{2}-\tfrac{4}{3}Z_{2}^{2}+Z_{3}^{2}\\\
&\quad-\sqrt{\tfrac{98}{9}}\,Z_{1}Z_{2}+\sqrt{\tfrac{200}{3}}\,Z_{1}Z_{3}-\sqrt{\tfrac{100}{3}}\,Z_{2}Z_{3}.\end{split}$
(A.7) Analogously, $\operatorname{\mathrm{NC}}_{S_{13}}(\mathcal{G}_{n})$
follows an asymptotic distribution of
$\displaystyle\begin{split}n\bigl{(}\operatorname{\mathrm{NC}}_{S_{13}}(\mathcal{G}_{n})-\operatorname{\mathrm{NC}}_{S_{13}}(\mathcal{G})\bigr{)}&\stackrel{{\scriptstyle
D}}{{\longrightarrow}}-\tfrac{1}{6}Z_{1}^{2}+\tfrac{35}{12}Z_{2}^{2}-\tfrac{13}{4}Z_{3}^{2}\\\
&\quad+\sqrt{\tfrac{1369}{18}}\,Z_{1}Z_{2}+\sqrt{\tfrac{3}{2}}\,Z_{1}Z_{3}-\sqrt{\tfrac{3}{4}}\,Z_{2}Z_{3},\end{split}$
(A.8)

so, asymptotically, both
$\operatorname{\mathrm{NC}}_{S_{12}}(\mathcal{G}_{n})$ and
$\operatorname{\mathrm{NC}}_{S_{13}}(\mathcal{G}_{n})$ follow a generalized
chi-squared distribution with 3 degrees of freedom. Notice that the asymptotic
distributions (A.7) and (A.8) of
$\operatorname{\mathrm{NC}}_{S_{12}}(\mathcal{G}_{n})$ and
$\operatorname{\mathrm{NC}}_{S_{13}}(\mathcal{G}_{n})$ are equal by symmetry.

We can extend these results to obtain an asymptotic distribution for Xist by
considering the terms in (A.6) jointly over $S\in\\{S_{12},S_{13}\\}$, such
that

$\displaystyle\begin{bmatrix}n\bigl{(}g_{S_{12}}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}\bigr{)}-g_{S_{12}}^{\operatorname{\mathrm{NC}}}({\bm{p}})\bigr{)}\\\
n\bigl{(}g_{S_{13}}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}\bigr{)}-g_{S_{13}}^{\operatorname{\mathrm{NC}}}({\bm{p}})\bigr{)}\end{bmatrix}$
$\displaystyle\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\frac{1}{2}\begin{bmatrix}{\bm{Z}}^{\top}{\bm{H}}g_{S_{12}}^{\operatorname{\mathrm{NC}}}{\bm{Z}}\\\
{\bm{Z}}^{\top}{\bm{H}}g_{S_{13}}^{\operatorname{\mathrm{NC}}}{\bm{Z}}\end{bmatrix}.$

Finally, using the delta method for Hadamard directionally differentiable
functions (Theorem A.3) on the $\min(\cdot)$ functional via Lemma A.2 (iii)
yields

$\displaystyle
n\bigl{(}\operatorname{\mathrm{Xist}}(\mathcal{G}_{n})-\operatorname{\mathrm{Xist}}(\mathcal{G})\bigr{)}$
$\displaystyle=\min_{S\in\\{S_{12},\,S_{13}\\}}n\bigl{(}g_{S}^{\operatorname{\mathrm{NC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}\bigr{)}-g_{S}^{\operatorname{\mathrm{NC}}}({\bm{p}})\bigr{)}$
$\displaystyle\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\min_{S\in\\{S_{12},\,S_{13}\\}}\frac{1}{2}{\bm{Z}}^{\top}{\bm{H}}g_{S}^{\operatorname{\mathrm{NC}}}{\bm{Z}},$

where explicit expressions for
$\tfrac{1}{2}{\bm{Z}}^{\top}{\bm{H}}g_{S_{12}}^{\operatorname{\mathrm{NC}}}{\bm{Z}}$
and
$\tfrac{1}{2}{\bm{Z}}^{\top}{\bm{H}}g_{S_{13}}^{\operatorname{\mathrm{NC}}}{\bm{Z}}$
are derived in (A.7) and (A.8).

###  A.6 Consistency of the Xist algorithm

In the following we derive a limiting distribution for the Xist algorithm by
showing Theorem 4.1. In order to showcase the idea behind the proof of Theorem
4.1, we first briefly introduce the basic Xvst algorithm from Suchan et al.
(2023) and proof a CLT-type result for it in Theorem A.9. After then deriving
the limiting distribution of Xist, the proof of Theorem 4.2 is presented.

input : weighted graph $G=(V,E,{\bm{W}})$

output : XC value $c_{\min}$ with associated partition $S_{\min}$

1

2set $c_{\min}\leftarrow\infty$ and $S_{\min}\leftarrow\emptyset$

3

4for  _$\\{s,t\\}\subset V$ with $s\neq t$_ do

5 compute an $st$-MinCut partition $S_{st}$ on $G$

6 compute the graph cut value
$\operatorname{\mathrm{XC}}_{{S}^{\mathsf{c}}_{st}}(G)$ of partition $S_{st}$

7 if  _$\operatorname{\mathrm{XC}}_{S_{st}}(G) <c_{\min}$_ then

8 $c_{\min}\leftarrow\operatorname{\mathrm{XC}}_{S_{st}}(G)$

9 $S_{\min}\leftarrow S_{st}$

10

11 end if

12

13 end for

Basic Xvst algorithm 2 $\operatorname{\mathrm{XC}}(G)$ via $st$-MinCuts

The basic Xvst algorithm contains the essence of Xist, namely the principle of
choosing the best XCut out of a subset of (or, in this case, all)
$st$-MinCuts. In contrast to Xist, however, the basic Xvst algorithm does not
restrict itself to $\operatorname{V^{\mathrm{loc}}}$, and it does not contain
any Gomory–Hu-type construction to improve its computational complexity. By
Suchan et al. (2023, Theorem 3.2), the basic Xvst algorithm runs in
$\mathcal{O}(|V|^{3}|E|)$, so one order of magnitude slower than Xist if $|V|$
and $|\operatorname{V^{\mathrm{loc}}}|$ are of the same order, e.g. if
$p_{1}=\cdots=p_{m}$ for $\mathcal{G}$. In practice, however, this case is not
likely to happen, especially since $\mathbb{P}(Y_{i}=Y_{j})\to 0$ for any
$i\neq j$ as $n\to\infty$ by Lemma A.7.

In order to gauge the computational impact that the restriction to
$\operatorname{V^{\mathrm{loc}}}$ has on Xist compared to the basic Xvst
algorithm, the expected number of local maxima is of interest, particularly if
an underlying discretized distribution exhibits $p_{i}=p_{j}$ for many
connected vertex pairs $i,j\in V$. This quantity is difficult to compute
exactly in general, however, due to ${\bm{\Sigma}}$ being non-invertible,
meaning that the limiting distribution of $\sqrt{n}({\bm{Y}}/n-{\bm{p}})$ has
no density. While this could be alleviated by restriction onto a subspace, it
does not help with the second issue of having to compute a large number of
integrals since the information whether vertex $i$ is local maximum has a
“cascading effect”, i.e. it introduces a dependency structure in the form of
$Y_{i}$ on all connected vertices. Consequently, the only feasible way to
gauge the advantages of Xist is via Monte Carlo simulation. Consider a
$\ell\times\ell$ grid with $p_{1}=\cdots=p_{m}=1/m$ for $m=\ell^{2}$ — the law
of large numbers allows us to ignore any non-uniform distributions — with
edges only between directly horizontally and vertically adjacent vertices.
Simulations show that the expected number of local maxima is approximately
$4/3$ for $\ell=2$, $8.6$ for $\ell=5$, $22.5$ for $\ell=10$ and $49.4$ for
$\ell=15$, meaning that it seems to scale linearly with $m$, and, on average,
Xist only considers around one fifth of all vertices, leading to a runtime
that is 25 times faster than the basic Xvst algorithm, notably on a uniform
distribution which is can be considered the “worst-case scenario” for the
improved algorithm. Moreover, when the number of edges increases, the number
of local maxima decreases, meaning Xist performs even better compared to the
basic Xvst algorithm. Exemplified on the $\ell\times\ell$-grid with uniform
distribution above, adding edges between directly diagonally adjacent vertices
decreases the expected number of local maxima to around an eighth of all
vertices. For a more thorough comparison of Xist and the basic Xvst algorithm,
in particular regarding the impact of and explanation behind the $st$-MinCut
selection procedure through $\tau$, see Suchan et al. (2023).

Before deriving the limiting distribution of basic Xvst algorithm, we require
a small auxiliary result that reformulates Assumption (A4) to make it better
usable in the following proofs.

######  Lemma A.8.

Assumption (A4) holds if and only if the all components corresponding to
elements in each $\mathcal{S}_{st}$, $s,t\in V$, $s\neq t$, of the MCut
limiting distribution ${\bm{Z}}^{\operatorname{\mathrm{MC}}}$ are almost
surely non-equal, i.e.

$q_{i,S}=q_{i,T}\;\text{ for all }i\in
V\iff\mathbb{P}(Z_{S}^{\operatorname{\mathrm{MC}}}=Z_{T}^{\operatorname{\mathrm{MC}}})=0.$

###### Proof.

By Theorem 4.2 (ii) the MCut limit ${\bm{Z}}^{\operatorname{\mathrm{MC}}}$ is
distributed according to the Gaussian
$\mathcal{N}_{|\mathcal{S}|}({\bm{0}},{\bm{\Sigma}}^{\operatorname{\mathrm{MC}}})$
with
$\Sigma_{S,T}^{\operatorname{\mathrm{MC}}}=\sum_{i=1}^{n}p_{i}q_{i,S}q_{i,T}-4\operatorname{\mathrm{MC}}_{S}(\mathcal{G})\operatorname{\mathrm{MC}}_{T}(\mathcal{G})$.
Fix now $s,t\in V$, $s\neq t$ as well as $S,T\in\mathcal{S}_{st}$ (although
the following holds for any two partitions $S$ and $T$). Consider the vector
${\bm{a}}\coloneqq{\bm{e}}_{S}-{\bm{e}}_{T}\in\mathbb{R}^{|S|}$, where
${\bm{e}}_{S}$ and ${\bm{e}}_{T}$ are unit vectors in $\mathbb{R}^{|S|}$ with
one in the $S$-th and $T$-th component, respectively. Then,
${\bm{a}}^{\top}{\bm{X}}^{\operatorname{\mathrm{MC}}}\sim\mathcal{N}(0,{\bm{a}}^{\top}{\bm{\Sigma}}^{\operatorname{\mathrm{MC}}}{\bm{a}}).$
This, however, means that
$\mathbb{P}(Z_{S}^{\operatorname{\mathrm{MC}}}=Z_{T}^{\operatorname{\mathrm{MC}}})=\mathbb{P}(Z_{S}^{\operatorname{\mathrm{MC}}}-Z_{T}^{\operatorname{\mathrm{MC}}}=0)$
is zero if and only if the variance of the Gaussian above is zero as well. We
rewrite this as follows:

$\displaystyle
0\stackrel{{\scriptstyle!}}{{=}}{\bm{a}}^{\top}{\bm{\Sigma}}^{\operatorname{\mathrm{MC}}}{\bm{a}}$
$\displaystyle=\Sigma_{S,S}^{\operatorname{\mathrm{MC}}}-2\Sigma_{S,T}^{\operatorname{\mathrm{MC}}}+\Sigma_{T,T}^{\operatorname{\mathrm{MC}}}$
$\displaystyle=\sum_{i=1}^{m}p_{i}(q_{i,S}^{2}-2q_{i,S}q_{i,T}+q_{i,T}^{2})$
$\displaystyle\qquad-4\bigl{(}\operatorname{\mathrm{MC}}_{S}(\mathcal{G})^{2}-2\operatorname{\mathrm{MC}}_{S}(\mathcal{G})\operatorname{\mathrm{MC}}_{T}(\mathcal{G})+\operatorname{\mathrm{MC}}_{T}(\mathcal{G})^{2}\bigr{)}$
$\displaystyle=\biggl{(}\sum_{i=1}^{m}p_{i}(q_{i,S}-q_{i,T})^{2}\biggr{)}-\left(\biggl{(}\sum_{i=1}^{m}p_{i}q_{i,S}\biggr{)}-\biggl{(}\sum_{i=1}^{m}p_{i}q_{i,T}\biggr{)}\right)^{2},$

where in the last step we used the fact that
$\sum_{i=1}^{m}p_{i}q_{i,R}=2\operatorname{\mathrm{MC}}(R)$ for any partition
$R\in\mathcal{S}$. As the $p_{i}$’s are all positive and sum up to 1, and
$x\mapsto x^{2}$ is convex, Jensen’s inequality dictates that

$\sum_{i=1}^{m}p_{i}(q_{i,S}-q_{i,T})^{2}\geq\biggl{(}\sum_{i=1}^{m}p_{i}(q_{i,S}-q_{i,T})\biggr{)}^{2}$

with equality if and only if $q_{i,S}-q_{i,T}=q_{j,S}-q_{j,T}$ for all $i,j\in
V$. This new condition is now obviously satisfied if $q_{i,S}=q_{i,T}$, so it
remains to show the converse.

To show this assume that $q_{i,S}-q_{i,T}=q_{j,S}-q_{j,T}$ for all $i,j\in V$,
and consider the fact that by Assumption (A4) both $S$ and $T$ attain the
minimal $st$-MinCut. Define $\lambda\coloneqq q_{i,S}-q_{i,T}$, which is by
assumption is independent of $i\in V$. Thus

$\displaystyle
0=2\operatorname{\mathrm{MC}}(S)-2\operatorname{\mathrm{MC}}(T)$
$\displaystyle=\bigl{(}\sum_{i=1}^{m}p_{i}q_{i,S}\bigr{)}-\bigl{(}\sum_{i=1}^{m}p_{i}q_{i,T}\bigr{)}$
$\displaystyle=\sum_{i=1}^{m}p_{i}(q_{i,S}-q_{i,T})=\lambda\sum_{i=1}^{m}p_{i}=\lambda,$

showing $q_{i,S}=q_{i,T}$ for all $i\in V$, and finishing the proof. ∎

With this, we are ready to derive an asymptotic distribution for Xist. The
idea behind the following proof is loosely based on a more general result by
Klatt et al. (2022, Lemma 5.5), who show existence of a limiting distribution
within the framework of basis solutions for linear programs.

######  Theorem A.9.

Assume the same setup as in Theorem 4.1, and let
$\operatorname{\mathrm{Xvst}}(\cdot)$ denote the output of the basic Xvst
algorithm.

  1. (i)

Then

$\displaystyle\sqrt{n}\bigl{(}\operatorname{\mathrm{Xvst}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{*,n}}(\mathcal{G})\bigr{)}$
$\displaystyle\qquad\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\min_{(s,t,S)\in\mathcal{S}_{*}^{\operatorname{\mathrm{MC}}}}\bigl{\\{}Z_{S}^{\operatorname{\mathrm{XC}}}:Z_{S}^{\operatorname{\mathrm{MC}}}<Z_{T}^{\operatorname{\mathrm{MC}}}\;\text{
for all }T\in\mathcal{S}_{st}\setminus\\{S\\}\bigr{\\}},$ (A.9)

where $S_{*,n}\in\mathcal{S}$ denotes the partition that attains the output
$\operatorname{\mathrm{Xvst}}(\mathcal{G}_{n})$ of the basic Xvst algorithm
applied to the empirical graph $\mathcal{G}_{n}$.

  2. (ii)

If additionally Assumption (A5) without the restriction to
$\mathrm{V}_{\mathcal{G}}^{\mathrm{loc}}$ (i.e. setting $s,t\in V$ instead of
$s,t\in\mathrm{V}_{\mathcal{G}}^{\mathrm{loc}}$) holds,
$\sqrt{n}\bigl{(}\operatorname{\mathrm{Xvst}}(\mathcal{G}_{n})-\operatorname{\mathrm{Xvst}}(\mathcal{G})\bigr{)}\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\mathcal{N}\bigl{(}0,\Sigma_{S_{*},S_{*}}^{\operatorname{\mathrm{XC}}}\bigr{)}$,
where the variance $\Sigma_{S_{*},S_{*}}^{\operatorname{\mathrm{XC}}}$ is
given by Corollary 3.2 (i), for the (unique) minimizing partition $S_{*}$ of
$\operatorname{\mathrm{Xvst}}(\mathcal{G})$.

###### Proof of Theorem A.9.

We first show part (i). Set $d\coloneqq|\mathcal{S}|=2^{m-1}-1$. A slightly
modified version of Theorem 3.1 (i) shows that the combined XCut and MCut
vectors converge toward a limiting distribution:

${\bm{v}}_{n}\coloneqq\begin{bmatrix}{\bm{v}}^{\operatorname{\mathrm{XC}}}\\\
{\bm{v}}^{\operatorname{\mathrm{MC}}}\end{bmatrix}\coloneqq\begin{bmatrix}\sqrt{n}(\operatorname{\mathrm{XC}}_{S_{1}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{1}}(\mathcal{G}))\\\
\vdots\\\
\sqrt{n}(\operatorname{\mathrm{XC}}_{S_{d}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{d}}(\mathcal{G}))\\\
\sqrt{n}(\operatorname{\mathrm{MC}}_{S_{1}}(\mathcal{G}_{n})-\operatorname{\mathrm{MC}}_{S_{1}}(\mathcal{G}))\\\
\vdots\\\
\sqrt{n}(\operatorname{\mathrm{MC}}_{S_{d}}(\mathcal{G}_{n})-\operatorname{\mathrm{MC}}_{S_{d}}(\mathcal{G}))\end{bmatrix}\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\begin{bmatrix}{\bm{Z}}^{\operatorname{\mathrm{XC}}}\\\
{\bm{Z}}^{\operatorname{\mathrm{MC}}}\end{bmatrix}=:{\bm{Z}}.$

This fact can be easily seen by considering the Hadamard directionally
differentiable functional
${\bm{x}}\mapsto(g_{S}^{\operatorname{\mathrm{XC}}}({\bm{x}}),g_{S}^{\operatorname{\mathrm{MC}}})({\bm{x}})$
and applying the delta method as outlined in the proof of Theorem 3.1.
Consequently, the random variables ${\bm{Z}}^{\operatorname{\mathrm{MC}}}$ and
${\bm{Z}}^{\operatorname{\mathrm{XC}}}$ are the same as in Theorem 3.1; they
are (in general) not independent, however. The marginal distribution of
${\bm{Z}}^{\operatorname{\mathrm{MC}}}$ is the multivariate Gaussian
$\mathcal{N}_{d}({\bm{0}},{\bm{\Sigma}}^{\operatorname{\mathrm{MC}}})$ by
Corollary 3.2 (i).

Define the map
${\bm{\varphi}}:\mathbb{R}^{2d}\to\mathbb{R}^{m},{\bm{v}}\mapsto{\bm{e}}_{{\bm{v}},\mathcal{U}}$,
where ${\bm{e}}_{{\bm{v}},\mathcal{U}}$ is defined as

$({\bm{e}}_{{\bm{v}},\mathcal{U}})_{k}\coloneqq\begin{cases}1,&\text{if}\;v_{k}^{\operatorname{\mathrm{MC}}}<v_{j}^{\operatorname{\mathrm{MC}}}\;\text{
for all }j\in\mathcal{U}\;\text{and}\;k\in\mathcal{U},\\\
0,&\text{else.}\end{cases}$

By Lemma A.8, under Assumption (A4) it holds that
$P(Z_{S}^{\operatorname{\mathrm{MC}}}=Z_{T}^{\operatorname{\mathrm{MC}}})=0$
for any $S,T\in\mathcal{S}_{st}$, meaning that asymptotically, the $st$-MinCut
partition $S_{st}\in\mathcal{S}_{st}$ is unique. This implies that
${\bm{\varphi}}$ is continuous at $Z$-a.e. ${\bm{v}}\in\mathbb{R}^{2d}$ since
each such ${\bm{v}}$ has exactly one component
${\bm{v}}_{S}^{\operatorname{\mathrm{MC}}}$ satisfying
$v_{S}^{\operatorname{\mathrm{MC}}}<v_{T}^{\operatorname{\mathrm{MC}}}$ for
all $T\in\mathcal{U},T\neq S$. Consequently, the corresponding
${\bm{e}}_{{\bm{v}},\mathcal{U}}$ is uniquely determined by ${\bm{v}}$ to be
equal to the unit vector in $\mathbb{R}^{d}$ corresponding to the partition
$S\in\mathcal{S}$. Since the condition that
$v_{S}^{\operatorname{\mathrm{MC}}}<v_{T}^{\operatorname{\mathrm{MC}}}$ for
all $T\in\mathcal{U},T\neq S$ still holds if any component of ${\bm{v}}$ is
perturbed by a small enough $\varepsilon>0$, ${\bm{\varphi}}$ is continuous at
each such ${\bm{v}}$.

This also means that the function
$\widetilde{{\bm{\varphi}}}:\mathbb{R}^{2d}\to\mathbb{R}^{3d},{\bm{v}}\mapsto({\bm{e}}_{{\bm{v}},\mathcal{U}},{\bm{v}})$
is continuous as well (where we abused notation slightly to denote the image
vector in $\mathbb{R}^{3d}$ more easily). Setting
$\mathcal{U}\coloneqq\mathcal{S}_{st}$ we use the continuous mapping theorem
to establish that $\widetilde{{\bm{\varphi}}}({\bm{v}}_{n})$ converges in
distribution towards
$\widetilde{{\bm{\varphi}}}({\bm{Z}})=({\bm{e}}_{{\bm{Z}},\mathcal{U}},{\bm{Z}})^{\top}$.
We then define the functional
$\psi:\mathbb{R}^{3d}\to\mathbb{R},\,\,(x_{1},\ldots,x_{3d})^{\top}\mapsto\sum_{i=1}^{d}x_{i}x_{d+i}$
and apply continuous mapping again to receive

$\sqrt{n}\big{(}\operatorname{\mathrm{XC}}_{\mathcal{S}_{st}^{(n)}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{n,st}}(\mathcal{G})\big{)}=\psi(\widetilde{{\bm{\varphi}}}({\bm{v}}_{n}))\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\psi(\widetilde{{\bm{\varphi}}}({\bm{Z}}))=:\widetilde{Z}_{st}^{\operatorname{\mathrm{Xvst}}},$

where $S_{n,st}$ is the (${\bm{Z}}$-a.s. unique) partition attaining the
empirical $st$-MinCut of $\mathcal{G}_{n}$. Repeating this procedure for all
pairs $s,t\in V$, $s\neq t$, and applying Theorem A.3 to the minimum
functional (using Lemma A.2 (iii) to obtain its Hadamard directional
derivative) finally yields the desired result:

$\displaystyle\sqrt{n}\bigl{(}\operatorname{\mathrm{Xvst}}(\mathcal{G}_{n})-\min_{{s,t\in
V,\;s\neq t}}\operatorname{\mathrm{XC}}_{S_{n,st}}(\mathcal{G})\bigr{)}$
$\displaystyle\qquad\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\min_{{s,t\in V,\;s\neq
t}}\Bigl{\\{}\widetilde{Z}_{st}^{\operatorname{\mathrm{Xvst}}}\bigm{|}\operatorname{\mathrm{MC}}_{S}(\mathcal{G})=\operatorname{\mathrm{MC}}^{st}(\mathcal{G})\Bigr{\\}}$
$\displaystyle\qquad=\min_{{s,t\in V,\;s\neq
t}}\Bigl{\\{}Z_{S}^{\operatorname{\mathrm{XC}}}\bigm{|}\operatorname{\mathrm{MC}}_{S}(\mathcal{G})=\operatorname{\mathrm{MC}}^{st}(\mathcal{G}),Z_{S}^{\operatorname{\mathrm{MC}}}<Z_{T}^{\operatorname{\mathrm{MC}}}\;\text{
for all }T\in\mathcal{S}_{st}\Bigr{\\}},$

where $\operatorname{\mathrm{MC}}^{st}(\mathcal{G})$ denotes the $st$-MinCut
value of the underlying graph $\mathcal{G}$.

We can derive Theorem A.9 (ii) directly from part (i) using (A5), where the
latter is not restricted to $\mathrm{V}_{\mathcal{G}}^{\mathrm{loc}}$. It
asserts that, for large enough $n$, $|\mathcal{S}_{st}|=1$, so that
asymptotically,
$\\{Z_{S}^{\operatorname{\mathrm{XC}}}:Z_{S}^{\operatorname{\mathrm{MC}}}<Z_{T}^{\operatorname{\mathrm{MC}}}\;\text{
for all }T\in\mathcal{S}_{st}\setminus\\{S\\}\bigr{\\}}=\\{S_{*}\\}$ almost
surely. Additionally, (A5) states that as $n\to\infty$, $S_{*}$ uniquely
attains the minimum XCut value over all $st$-MinCuts. In part (i), the
convergence (A.9) was shown, whence the limiting distribution reduces to the
component $Z_{S_{*}}^{\operatorname{\mathrm{XC}}}$. From Corollary 3.2 (i) the
claim follows as it has already been shown there that
$Z_{S_{*}}^{\operatorname{\mathrm{XC}}}\sim\mathcal{N}(0,\Sigma_{S_{*},S_{*}}^{\operatorname{\mathrm{XC}}})$.
∎

We now show Theorem 4.1. Although Xist is a modified version of the basic Xvst
algorithm, we require a slightly different proof strategy compared to Theorem
A.9, namely the Portmanteau theorem to characterize distributional
convergence.

###### Proof of Theorem 4.1.

We first show (i). Xist takes into account those vertices $i$ that are local
maxima, i.e. such that $Y_{j}\leq Y_{i}$ for all $j\sim i$. By Lemma A.7 this
can be reduced to a strict inequality since $\mathbb{P}(Y_{i}=Y_{j})\to 0$ as
$n\to\infty$. If $p_{i}>p_{j}$ for all $j$ with $j\sim i$, $Y_{i}>Y_{j}$ for
all $n\geq N$ (for some $N\in\mathbb{N}$) and all $j$ with $j\sim i$. Denote
the set of vertices that satisfy this by $V_{1}\subset V$. Additionally, we
have to consider those $i\in V$ with $p_{i}\geq p_{j}$ for all $j\sim i$ and
$p_{i}=p_{k}$ for some $k\sim i$. Denote this set of vertices by
$V_{2}\subseteq V$, so that together

$\displaystyle V_{1}$ $\displaystyle\coloneqq\\{r\in V:p_{r}>p_{i}\;\text{for
all }i\sim r\\}\quad\text{and}$ $\displaystyle\widehat{V}_{2}$
$\displaystyle\coloneqq\\{r\in V\setminus V_{1}:p_{r}>p_{i}\text{ or
}p_{r}=p_{i}\text{ and }Z_{r}^{{\bm{p}}}>Z_{i}^{{\bm{p}}}\;\text{ for all
}i\sim r\\}.$

Consequently, the set of local maxima is contained in $V_{1}\cup V_{2}$ for
large enough $n$. Note that as $n\to\infty$, every $s\in V_{1}$ is almost
surely a local maximum. The same cannot be said for $V_{2}$, although all
$i,j\in V_{2}$ satisfy $p_{i}=p_{j}$ if $i\sim j$. This means that
$Y_{i}>Y_{j}$ is equivalent to $\sqrt{n}(Y_{i}-p_{i})>\sqrt{n}(Y_{j}-p_{j})$
for all $i,j\in V_{2}$ with $i\sim j$. Since we know that any $i\in V_{2}$ are
guaranteed to be local maxima for large $n$, only consider those in
$V_{2}\coloneqq\\{i_{1},\ldots,i_{|V_{2}|}\\}$.

Now, enumerating $\mathcal{S}\coloneqq\\{S_{1},\ldots,S_{d}\\}$, a slightly
modified version of the proof of Theorem 3.1 shows the following convergence:

${\bm{v}}_{n}\coloneqq\begin{bmatrix}{\bm{v}}^{\operatorname{\mathrm{XC}}}\\\
{\bm{v}}^{\operatorname{\mathrm{MC}}}\\\
{\bm{v}}^{{\bm{p}}}\end{bmatrix}\coloneqq\begin{bmatrix}\sqrt{n}(\operatorname{\mathrm{XC}}_{S_{1}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{1}}(\mathcal{G}))\\\
\vdots\\\
\sqrt{n}(\operatorname{\mathrm{XC}}_{S_{d}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{d}}(\mathcal{G}))\\\
\sqrt{n}(\operatorname{\mathrm{MC}}_{S_{1}}(\mathcal{G}_{n})-\operatorname{\mathrm{MC}}_{S_{1}}(\mathcal{G}))\\\
\vdots\\\
\sqrt{n}(\operatorname{\mathrm{MC}}_{S_{d}}(\mathcal{G}_{n})-\operatorname{\mathrm{MC}}_{S_{d}}(\mathcal{G}))\\\
\sqrt{n}(Y_{1}-p_{1})\\\ \vdots\\\ \sqrt{n}(Y_{m}-p_{m})\\\
\end{bmatrix}\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\begin{bmatrix}{\bm{Z}}^{\operatorname{\mathrm{XC}}}\\\
{\bm{Z}}^{\operatorname{\mathrm{MC}}}\\\
{\bm{Z}}^{{\bm{p}}}\end{bmatrix}=:{\bm{Z}},$ (A.10)

where the random variable ${\bm{Z}}$ can be expressed It should be noted that
when the balancing term $\operatorname{Bal}_{S}(\cdot)$ is differentiable at
${\bm{p}}$, ${\bm{Z}}$ will be a multivariate (centered) Gaussian whose
covariance matrix we can compute explicitly (analogously to the aforementioned
proof). For now, however, we are content with the above limit, remembering
that its components ${\bm{Z}}^{\operatorname{\mathrm{MC}}}$,
${\bm{Z}}^{\operatorname{\mathrm{XC}}}$ and ${\bm{Z}}^{{\bm{p}}}$ are
dependent.

Referring back to our above comments regarding the definitions of $V_{1}$ and
$V_{2}$, for $s,t\in V$, $s\neq t$, a partition $S\in\mathcal{S}_{st}$ is
considered by Xist (when applied to the empirical graph $\mathcal{G}_{n}$) if
and only if
$\operatorname{\mathrm{MC}}_{S}(\mathcal{G}_{n})\leq\operatorname{\mathrm{MC}}_{T}(\mathcal{G}_{n})$
for all $T\in\mathcal{S}_{st}\setminus\\{T\\}$ and, for $r=s,t$, $r\in V_{1}$
or $r\in V_{2}$ and $Y_{r}>Y_{i}$ for all $i\in V_{2}$ with $i\sim r$. Note
that we may disregard the cases
$\operatorname{\mathrm{MC}}_{S}(\mathcal{G}_{n})=\operatorname{\mathrm{MC}}_{T}(\mathcal{G}_{n})$
and $Y_{i}=Y_{j}$ by Corollary 3.2 (i) and Lemma A.7: By definitions of
$\mathcal{S}_{st}$, $V_{1}$ and $V_{2}$ we have the equivalence

$\displaystyle\operatorname{\mathrm{MC}}_{S}(\mathcal{G}_{n})<\operatorname{\mathrm{MC}}_{T}(\mathcal{G}_{n})\iff
v_{S}^{\operatorname{\mathrm{MC}}}<v_{T}^{\operatorname{\mathrm{MC}}}\quad\text{and}\quad
Y_{r}>Y_{i}\iff v_{r}^{{\bm{p}}}>v_{i}^{{\bm{p}}}$

for $S,T\in\mathcal{S}_{st}$ and $r,i\in V_{2}$ with $i\sim r$. Set
$\mathcal{S}^{\operatorname{\mathrm{MC}}}\coloneqq\\{(s,t,S)\in V\times
V\times\mathcal{S}\,\,|\,\,s\neq
t,\operatorname{\mathrm{MC}}_{S}(\mathcal{G})=\operatorname{\mathrm{MC}}^{st}(\mathcal{G})\\}$
and define the random variable

$\displaystyle
Z^{\operatorname{\mathrm{Xvst}}}\coloneqq\min_{(s,t,S)\in\mathcal{S}^{\operatorname{\mathrm{MC}}}}\biggl{\\{}Z_{S}^{\operatorname{\mathrm{XC}}}:$
$\displaystyle\operatorname{\mathrm{MC}}_{S}(\mathcal{G})=\operatorname{\mathrm{MC}}^{st}(\mathcal{G}),Z_{S}^{\operatorname{\mathrm{MC}}}<Z_{T}^{\operatorname{\mathrm{MC}}}\;\text{
for all }T\in\mathcal{S}_{st}\setminus\\{S\\},$
$\displaystyle\operatorname{\mathrm{XC}}_{S}(\mathcal{G})=\min_{(u,v,T)\in\mathcal{S}^{\operatorname{\mathrm{MC}}}}\operatorname{\mathrm{XC}}_{T}(\mathcal{G}),\;\text{
and, for }r=s,t:$ $\displaystyle\;r\in V_{1}\;\text{ or }\;(r\in V_{2}\,\text{
and }\,Z_{r}^{{\bm{p}}}>Z_{i}^{{\bm{p}}}\;\text{ for all }i\in V_{2},i\sim
r)\biggr{\\}},$

and let $G\in B(\mathbb{R})$ be an arbitrary
$Z^{\operatorname{\mathrm{Xvst}}}$-continuity set. Further, for fixed $s,t\in
V$, $s\neq t$, and $S\in\mathcal{S}$ set

$\displaystyle H_{s,t,S}$
$\displaystyle\coloneqq\Bigl{\\{}{\bm{u}}\coloneqq({\bm{u}}^{\operatorname{\mathrm{XC}}},{\bm{u}}^{\operatorname{\mathrm{MC}}},{\bm{u}}^{{\bm{p}}})\in\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}^{m}:u_{S}^{\operatorname{\mathrm{MC}}}<u_{T}^{\operatorname{\mathrm{MC}}}\;\text{
for all }T\in\mathcal{S}_{st}\setminus\\{S\\},$ $\displaystyle\hskip
42.67912ptr\in V_{1}\,\text{ or }\,(r\in V_{2}\,\text{ and
}\,u_{r}^{{\bm{p}}}>u_{i}^{{\bm{p}}}\;\text{ for all }i\in V_{2}\text{ with
}i\sim r)\;\text{ for }r=s,t\Bigr{\\}}$ $\displaystyle
A_{s,t,S}^{\operatorname{\mathrm{XC}}}$
$\displaystyle\coloneqq\Bigl{\\{}{\bm{u}}^{\operatorname{\mathrm{XC}}}\in\mathbb{R}^{d}:u_{S}^{\operatorname{\mathrm{XC}}}\leq
u_{T}^{\operatorname{\mathrm{XC}}}\;\text{ for all
}(v,w,T)\in\mathcal{S}^{\operatorname{\mathrm{MC}}}\text{ with }T\neq S\text{
and }{\bm{u}}\in H_{v,w,T}\Bigr{\\}},$ $\displaystyle G_{s,t,S}$
$\displaystyle\coloneqq\Bigl{\\{}{\bm{u}}\in\mathbb{R}^{2d+m}:{\bm{u}}\in
H_{s,t,S},\,{\bm{u}}_{S}^{\operatorname{\mathrm{XC}}}\in G\cap
A_{s,t,S}^{\operatorname{\mathrm{XC}}}\Bigr{\\}}.$

Naturally, $H_{s,t,S}$, $A_{s,t,S}$ and $G_{s,t,S}$ are Borel-measurable on
$\mathbb{R}^{2d+m}$. The boundary of $H_{s,t,S}$ satisfies

$\displaystyle\partial H_{s,t,S}$
$\displaystyle\subseteq\Bigl{(}\bigcup_{T\in\mathcal{S}_{st}\setminus\\{S\\}}\bigl{\\{}u_{S}^{\operatorname{\mathrm{MC}}}=u_{T}^{\operatorname{\mathrm{MC}}}\bigr{\\}}\Bigr{)}\cup\Bigl{(}\bigcup_{\begin{subarray}{c}i:i\sim
r\\\
r=s,t\end{subarray}}\bigl{\\{}u_{r}^{{\bm{p}}}=u_{i}^{{\bm{p}}}\bigr{\\}}\Bigr{)},$
meaning that we can capture the boundary of $G_{s,t,S}$ as follows:
$\displaystyle\partial G_{s,t,S}$ $\displaystyle\subseteq\partial
H_{s,t,S}\;\cup\;\partial\bigl{(}G\cap
A_{s,t,S}^{\operatorname{\mathrm{XC}}}\bigr{)}\times\mathbb{R}^{d+m}\;\cap
H_{s,t,S}.$

Since
$\\{Z_{S}^{\operatorname{\mathrm{XC}}}=Z_{T}^{\operatorname{\mathrm{XC}}}\\}\subseteq\\{Z^{\operatorname{\mathrm{Xvst}}}\in\partial
G\\}$ for any $(s,t,S),(u,v,T)\in\mathcal{S}^{\operatorname{\mathrm{MC}}}$
with $S\neq T$ and $Z\in H_{s,t,S}\cap H_{u,v,T}$, the inclusion above
establishes $\bigl{\\{}{\bm{Z}}\in\partial
G_{s,t,S}\bigr{\\}}\subseteq\bigl{\\{}{\bm{Z}}\in\partial
H_{s,t,S}\bigr{\\}}\cup\bigl{\\{}Z^{\operatorname{\mathrm{Xvst}}}\in\partial
G\bigr{\\}}.$ Consequently,

$\displaystyle\mathbb{P}({\bm{Z}}\in\partial G_{s,t,S})$
$\displaystyle\quad\leq\mathbb{P}\Bigl{(}\bigl{\\{}Z^{\operatorname{\mathrm{Xvst}}}\in\partial
G\bigr{\\}}\cup\Bigl{\\{}{\bm{Z}}\in\bigcup_{T\in\mathcal{S}_{st}\setminus\\{S\\}}\bigl{\\{}u_{S}^{\operatorname{\mathrm{MC}}}=u_{T}^{\operatorname{\mathrm{MC}}}\bigr{\\}}\cup\bigcup_{\begin{subarray}{c}i:i\sim
r\\\
r=s,t\end{subarray}}\bigl{\\{}u_{r}^{{\bm{p}}}=u_{i}^{{\bm{p}}}\bigr{\\}}\Bigr{\\}}\Bigr{)}$
$\displaystyle\quad=\mathbb{P}\Bigl{(}\bigl{\\{}Z^{\operatorname{\mathrm{Xvst}}}\in\partial
G\bigr{\\}}\cup\bigcup_{T\in\mathcal{S}_{st}\setminus\\{S\\}}\bigl{\\{}Z_{S}^{\operatorname{\mathrm{MC}}}=Z_{T}^{\operatorname{\mathrm{MC}}}\bigr{\\}}\cup\bigcup_{\begin{subarray}{c}i:i\sim
r\\\
r=s,t\end{subarray}}\bigl{\\{}Z_{r}^{{\bm{p}}}=Z_{i}^{{\bm{p}}}\bigr{\\}}\Bigr{)}$
$\displaystyle\quad\leq\mathbb{P}\bigl{(}{\bm{Z}}^{\operatorname{\mathrm{Xvst}}}\in\partial
G\bigr{)}+\sum_{T\in\mathcal{S}_{st}\setminus\\{S\\}}\mathbb{P}\bigl{(}Z_{S}^{\operatorname{\mathrm{MC}}}=Z_{T}^{\operatorname{\mathrm{MC}}}\bigr{)}+\sum_{\begin{subarray}{c}i:i\sim
r\\\
r=s,t\end{subarray}}\mathbb{P}\bigl{(}Z_{r}^{{\bm{p}}}=Z_{i}^{{\bm{p}}}\bigr{)}=0,$

where in the last step we used the following facts: Firstly, $G$ is a
${\bm{Z}}^{\operatorname{\mathrm{Xvst}}}$-continuity set, secondly,
$\mathbb{P}(Z_{S}^{\operatorname{\mathrm{MC}}}=Z_{T}^{\operatorname{\mathrm{MC}}})=0$
for any two distinct partitions $S,T\in\mathcal{S}$ by Assumption (A4) and
Lemma A.8, and thirdly $\mathbb{P}(Z_{i}^{{\bm{p}}}=Z_{j}^{{\bm{p}}})=0$ holds
for any $i,j\in V$ by the proof of Lemma A.7. Hence, $G_{s,t,S}$ is a
${\bm{Z}}$-continuity set.

To finish the proof, define $S_{*,n}$ to be the partition that attains the
output $\operatorname{\mathrm{Xist}}(\mathcal{G}_{n})$ of Xist applied to
$\mathcal{G}_{n}$. We first apply the Portmanteau theorem, then the law of
total probability and afterwards Portmanteau a second time, yielding (for
fixed $s,t\in V$, $s\neq t$):

$\mathbb{P}(\sqrt{n}(\operatorname{\mathrm{Xist}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{*,n}}(\mathcal{G})))\in
G)=\sum_{\begin{subarray}{c}s,t\in V\\\ s\neq
t\end{subarray}}\sum_{S\in\mathcal{S}_{st}}\mathbb{P}({\bm{v}}_{n}\in
G_{s,t,S})\\\ \stackrel{{\scriptstyle
D}}{{\longrightarrow}}\sum_{\begin{subarray}{c}s,t\in V\\\ s\neq
t\end{subarray}}\sum_{S\in\mathcal{S}_{st}}\mathbb{P}({\bm{Z}}\in
G_{s,t,S})=\mathbb{P}(Z^{\operatorname{\mathrm{Xvst}}}\in G)$

due to the definition of $Z^{\operatorname{\mathrm{Xvst}}}$. This shows
Theorem 4.1 (i) since $G$ was arbitrary.

Now Theorem 4.1 (ii) follows directly from part (i) using Assumption (A5). The
latter asserts that the set
$\\{Z_{S}^{\operatorname{\mathrm{XC}}}:Z_{S}^{\operatorname{\mathrm{MC}}}<Z_{T}^{\operatorname{\mathrm{MC}}}\;\text{
for all }T\in\mathcal{S}_{st}\setminus\\{S\\}\bigr{\\}}$ contains exactly one
element for large enough $n$, namely $Z_{S_{*}}^{\operatorname{\mathrm{XC}}}$
because it is the unique XCut minimizer, and it uniquely attains its
corresponding $st$-MinCut, such that $\mathcal{S}_{st}=\\{S_{*}\\}$. Moreover,
under Assumption (A5), the minimum XCut value over $st$-MinCuts for vertices
in $V_{1}\cap\widehat{V}_{2}$ is asymptotically almost surely attained by
$S_{*}$. Consequently, the limit from part (i) simplifies to the component
$Z_{S_{*}}^{\operatorname{\mathrm{XC}}}$ which, by Corollary 3.2 (i), is
normally distributed with variance
$\Sigma_{S_{*},S_{*}}^{\operatorname{\mathrm{XC}}}$. ∎

Lastly, we show Theorem 4.2 which is merely an extension of Theorem 3.1 for
the multiway cut that separates the nodes of the graph into $k\geq 2$
partitions.

###### Proof of Theorem 4.2.

We prove this using the same procedure we showed Theorem 3.1 with. First,
recall again that $\sqrt{n}({\bm{Y}}/n-{\bm{p}})\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\mathcal{N}_{m}({\bm{0}},{\bm{\Sigma}})$, where
${\bm{\Sigma}}=(\Sigma_{i,j})\in\mathbb{R}^{m\times m}$ is the covariance
matrix of the multinomial distribution $\operatorname{Mult}(1,{\bm{p}})$. Now,
for XCut and any partition $S\in\mathcal{S}$ we define the function

$\displaystyle{\bm{g}}^{\operatorname{\mathrm{kXC}}}:\mathbb{R}^{m}\to\mathbb{R}^{|\mathcal{S}|},\quad$
$\displaystyle{\bm{x}}\,\mapsto\,\left(g_{S}^{\operatorname{\mathrm{kXC}}}({\bm{x}})\right)_{S\in\mathcal{S}}$
for $\displaystyle
g_{S}^{\operatorname{\mathrm{kXC}}}:\mathbb{R}^{m}\to\mathbb{R},$
$\displaystyle{\bm{x}}\,\mapsto\,\frac{1}{2}\sum_{\ell=1}^{k}g_{S_{\ell}}^{\operatorname{\mathrm{XC}}}({\bm{x}}),$

where ${\bm{x}}=(x_{1},\ldots,x_{m})$,
$S=\\{S_{1},\ldots,S_{k}\\}\in\mathcal{S}^{k}$, and
$g_{S}^{\operatorname{\mathrm{XC}}}:\mathbb{R}^{m}\to\mathbb{R}$ is the XCut
functional we used throughout this paper.

(i): If $g_{S}^{\operatorname{\mathrm{XC}}}$ is Hadamard differentiable, we
apply the delta method for Hadamard directionally differentiable functions
(Theorem A.3) to receive:

$\sqrt{n}\Big{(}\operatorname{\mathrm{kXC}}_{S}(\mathcal{G}_{n})-\operatorname{\mathrm{kXC}}_{S}(\mathcal{G})\Big{)}=\sqrt{n}\left(g_{S}^{\operatorname{\mathrm{kXC}}}\left(\tfrac{{\bm{Y}}}{n}\right)-g_{S}^{\operatorname{\mathrm{kXC}}}({\bm{p}})\right)\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\left((g_{S}^{\operatorname{\mathrm{kXC}}})_{{\bm{p}}}^{\prime}({\bm{Z}})\right)_{S\in\mathcal{S}},$

where ${\bm{Z}}\sim\mathcal{N}_{m}({\bm{0}},{\bm{\Sigma}})$. It is evident
from Definition 7 that taking the Hadamard directional derivative at any fixed
point in any fixed direction is a linear operator. Consequently, we receive a
limiting distribution of

$(g_{S}^{\operatorname{\mathrm{kXC}}})_{{\bm{p}}}^{\prime}({\bm{Z}})=\frac{1}{2}\sum_{\ell=1}^{k}(g_{S_{\ell}}^{\operatorname{\mathrm{XC}}})_{{\bm{p}}}^{\prime}({\bm{Z}})=\frac{1}{2}\sum_{\ell=1}^{k}Z_{S_{\ell}}^{\operatorname{\mathrm{XC}}}\quad\text{for
any}\quad S=\\{S_{1},\ldots,S_{k}\\}\in\mathcal{S}^{k}.$

Here $Z_{S_{\ell}}^{\operatorname{\mathrm{XC}}}$ is the limiting distribution
of
$\sqrt{n}(\operatorname{\mathrm{XC}}_{S_{\ell}}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{S_{\ell}}(\mathcal{G}))$
from Theorem 3.1.

(ii): If $g_{S}^{\operatorname{\mathrm{XC}}}$ is
$\mathbb{R}^{m}$-differentiable, we may apply the standard delta method:

$\displaystyle\Bigl{(}\sqrt{n}\bigl{(}\operatorname{\mathrm{kXC}}_{R}(\mathcal{G}_{n})-\operatorname{\mathrm{kXC}}_{R}(\mathcal{G})\bigr{)}\Bigr{)}_{R\in\mathcal{S}}$
$\displaystyle=\Bigl{(}\sqrt{n}\bigl{(}g_{R}^{\operatorname{\mathrm{kXC}}}\bigl{(}\tfrac{{\bm{Y}}}{n}\bigr{)}-g_{R}^{\operatorname{\mathrm{kXC}}}({\bm{p}})\bigr{)}\Bigr{)}_{R\in\mathcal{S}}$
$\displaystyle\stackrel{{\scriptstyle
D}}{{\longrightarrow}}\mathcal{N}_{|\mathcal{S}|}\bigl{(}{\bm{0}},{\bm{\Sigma}}^{\operatorname{\mathrm{kXC}}}\bigr{)},$

so that for
$T=\\{T_{1},\ldots,T_{k}\\},\,S=\\{S_{1},\ldots,S_{k}\\}\in\mathcal{S}^{k}$
the limiting covariance matrix $\Sigma^{\operatorname{\mathrm{kXC}}}$ is given
by

$\displaystyle\bigl{(}{\bm{\Sigma}}^{\operatorname{\mathrm{kXC}}}\bigr{)}_{T,S}$
$\displaystyle=\nabla
g_{T}^{\operatorname{\mathrm{kXC}}}({\bm{p}})^{\top}{\bm{\Sigma}}\,\,\nabla
g_{S}^{\operatorname{\mathrm{kXC}}}({\bm{p}})$
$\displaystyle=\frac{1}{4}\sum_{i=1}^{k}\sum_{j=1}^{k}g_{T_{i}}^{\operatorname{\mathrm{XC}}}({\bm{p}})^{\top}{\bm{\Sigma}}\,\,\nabla
g_{S_{j}}^{\operatorname{\mathrm{XC}}}({\bm{p}})$
$\displaystyle=\frac{1}{4}\sum_{i=1}^{k}\sum_{j=1}^{k}\operatorname{Cov}(Z_{T_{i}}^{\operatorname{\mathrm{XC}}},Z_{S_{j}}^{\operatorname{\mathrm{XC}}}),$

where, for any $R\in\mathcal{S}$, $Z_{R}^{\operatorname{\mathrm{XC}}}$ denotes
the limiting distribution of
$\sqrt{n}\bigl{(}\operatorname{\mathrm{XC}}_{R}(\mathcal{G}_{n})-\operatorname{\mathrm{XC}}_{R}(\mathcal{G})\bigr{)}$
that we have already computed in Theorem 3.1. ∎

## Acknowledgements

LS is supported by the DFG (German Research Foundation) under project GRK
2088: “Discovering Structure in Complex Data”, subproject A1. HL is funded and
AM is supported by the DFG under Germany’s Excellence Strategy, project EXC
2067: “Multiscale Bioimaging: from Molecular Machines to Networks of Excitable
Cells” (MBExC). AM and HL are supported by DFG CRC 1456 “Mathematics of
Experiment”, and AM is supported by DFG RU 5381 “Mathematical Statistics in
the Information Age – Statistical Efficiency and Computational Tractability”.
The authors especially thank Max Wardetzky (University of Göttingen) for
various helpful discussions and comments.

## References

  * Andreev and Räcke [2004] Konstantin Andreev and Harald Räcke.  Balanced graph partitioning.  In _Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures_ , SPAA ’04, page 120–124. Association for Computing Machinery, 2004.  ISBN 1581138407.  10.1145/1007912.1007931.
  * Bickel and Freedman [1981] Peter J. Bickel and David A. Freedman.  Some Asymptotic Theory for the Bootstrap.  _Ann. Stat._ , 9(6):1196 – 1217, 1981.  10.1214/aos/1176345637.
  * Breiman [1992] Leo Breiman.  _Probability_ , volume 7 of _Classics in Applied Mathematics_.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992.  ISBN 0-89871-296-3.  10.1137/1.9781611971286.  Corrected reprint of the 1968 original.
  * Bui and Jones [1992] Thang Nguyen Bui and Curt Jones.  Finding good approximate vertex and edge partitions is np-hard.  _Inf. Process. Lett._ , 42(3):153 – 159, 1992\.  ISSN 0020-0190.  10.1016/0020-0190(92)90140-Q.
  * Cárcamo et al. [2020] Javier Cárcamo, Antonio Cuevas, and Luis-Alberto Rodríguez.  Directional differentiability for supremum-type functionals: statistical applications.  _Bernoulli_ , 26(3):2143–2175, 2020.  10.3150/19-BEJ1188.
  * Cheeger [1971] Jeff Cheeger.  _A lower bound for the smallest eigenvalue of the laplacian_ , pages 195–200.  Princeton University Press, Princeton, 1971.  ISBN 9781400869312.  doi:10.1515/9781400869312-013.
  * Chuzhoy and Khanna [2019] 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_ , STOC’19, pages 389–400. ACM, New York, 2019.  10.1145/3313276.3316320.
  * Chuzhoy et al. [2020] 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_ , pages 1158–1167. IEEE Computer Soc., Los Alamitos, CA, 2020.  10.1109/FOCS46700.2020.00111.
  * Cook et al. [1998] William Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver.  _Minimum cuts in undirected graphs_ , chapter 3.5, pages 71–84.  John Wiley & Sons, 1998.  ISBN 9781118033142.  10.1002/9781118033142.ch3.
  * Dahlhaus et al. [1994] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis.  The complexity of multiterminal cuts.  _SIAM J. Comput._ , 23(4):864–894, 1994.  10.1137/S0097539792225297.
  * Dümbgen [1993] Lutz Dümbgen.  On nondifferentiable functions and the bootstrap.  _Probab. Theory Related Fields_ , 95(1):125–140, 1993.  10.1007/BF01197342.
  * Feldmann and Foschini [2012] Andreas Emil Feldmann and Luca Foschini.  Balanced partitions of trees and applications.  In _29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)_ , volume 14, pages 100–111. 2012.  ISBN 978-3-939897-35-4.  10.4230/LIPIcs.STACS.2012.100.
  * Fetaya et al. [2015] Ethan Fetaya, Ohad Shamir, and Shimon Ullman.  Graph approximation and clustering on a budget.  In _Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics_ , volume 38, pages 241–249. PMLR, 2015\.  URL http://proceedings.mlr.press/v38/fetaya15.html.
  * Flake et al. [2004] Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis.  Graph clustering and minimum cut trees.  _Internet Math._ , 1(4):385–408, 2004.  10.1080/15427951.2004.10129093.
  * García Trillos et al. [2016] Nicolás García Trillos, Dejan Slepčev, James von Brecht, Thomas Laurent, and Xavier Bresson.  Consistency of Cheeger and ratio graph cuts.  _J. Mach. Learn. Res._ , 17:Paper No. 181, 46, 2016.  ISSN 1532-4435.
  * García Trillos et al. [2020] Nicolás García Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepčev.  Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator.  _Found. Comput. Math._ , 20(4):827–887, 2020\.  ISSN 1615-3375.  10.1007/s10208-019-09436-w.
  * García Trillos et al. [2022] Nicolás García Trillos, Ryan Murray, and Matthew Thorpe.  From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds.  _Arch. Ration. Mech. Anal._ , 244(3):541–598, 2022.  ISSN 0003-9527.  10.1007/s00205-022-01770-8.
  * Goldschmidt and Hochbaum [1994] Olivier Goldschmidt and Dorit S. Hochbaum.  A polynomial algorithm for the $k$-cut problem for fixed $k$.  _Math. Oper. Res._ , 19(1):24–37, 1994.  10.1287/moor.19.1.24.
  * Gomory and Hu [1961] R. E. Gomory and T. C. Hu.  Multi-terminal network flows.  _J. Soc. Indust. Appl. Math._ , 9:551–570, 1961.  ISSN 0368-4245.
  * Guattery and Miller [1998] Stephen Guattery and Gary L. Miller.  On the quality of spectral separators.  _SIAM J. Matrix Anal. Appl._ , 19(3):701–719, 07 1998.
  * Gusfield [1990] Dan Gusfield.  Very simple methods for all pairs network flow analysis.  _SIAM J. Comput._ , 19(1):143–155, 1990.  ISSN 0097-5397.  10.1137/0219009.
  * Hagen and Kahng [1992] Lars Hagen and Andrew B. Kahng.  A new approach to effective circuit clustering.  In _Proceedings of the 1992 IEEE/ACM International Conference on Computer-Aided Design_ , ICCAD ’92, page 422–427. IEEE Computer Society Press, 1992.  ISBN 0897915402.
  * Huang et al. [2009] S. Huang, Y. Chu, S. Lai, and C. L. Novak.  Learning-based vertebra detection and iterative normalized-cut segmentation for spinal MRI.  _IEEE T. Med. Imaging_ , 28(10):1595–1605, 2009\.  10.1109/TMI.2009.2023362.
  * Klatt et al. [2022] Marcel Klatt, Axel Munk, and Yoav Zemel.  Limit laws for empirical optimal solutions in random linear programs.  _Ann. Oper. Res._ , 315(1):251–278, 2022.  ISSN 0254-5330.  10.1007/s10479-022-04698-0.
  * Long et al. [2022] Zhiguo Long, Yang Gao, Hua Meng, Yuqin Yao, and Tianrui Li.  Clustering based on local density peaks and graph cut.  _INf. Sci._ , 600(C):263–286, jul 2022.  ISSN 0020-0255.  10.1016/j.ins.2022.03.091.
  * Maier et al. [2013] Markus Maier, Ulrike von Luxburg, and Matthias Hein.  How the result of graph clustering methods depends on the construction of the graph.  _ESAIM: PS_ , 17:370–418, 2013.  10.1051/ps/2012001.
  * Mohar [1989] Bojan Mohar.  Isoperimetric numbers of graphs.  _J. Comb. Theory Ser. B_ , 47(3):274 – 291, 1989\.  ISSN 0095-8956.  10.1016/0095-8956(89)90029-4.
  * Mulas [2021] Raffaella Mulas.  A Cheeger cut for uniform hypergraphs.  _Graphs Combin._ , 37(6):2265–2286, 2021.  ISSN 0911-0119.  10.1007/s00373-021-02348-z.
  * Nadler and Galun [2007] Boaz Nadler and Meirav Galun.  Fundamental limitations of spectral clustering.  In _Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference_ , pages 1017–1024. The MIT Press, 09 2007\.  ISBN 9780262256919.  10.7551/mitpress/7503.003.0132.
  * On et al. [2020] Kyoung-Woon On, Eun-Sol Kim, Yu-Jung Heo, and Byoung-Tak Zhang.  Cut-based graph learning networks to discover compositional structure of sequential video data.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):5315–5322, 04 2020.  10.1609/aaai.v34i04.5978.
  * Paulhac et al. [2012] L. Paulhac, V. Ta, and R. Mégret.  Relaxed Cheeger cut for image segmentation.  In _Proceedings of the 21st International Conference on Pattern Recognition (ICPR2012)_ , pages 3321–3324. 2012.
  * Politis et al. [1999] Dimitris N. Politis, Joseph P. Romano, and Michael Wolf.  _Subsampling_.  Springer Series in Statistics. Springer-Verlag, New York, 1999.  ISBN 0-387-98854-8.  10.1007/978-1-4612-1554-7.
  * Rahimian et al. [2015] Fatemeh Rahimian, Amir H. Payberah, Sarunas Girdzijauskas, Mark Jelasity, and Seif Haridi.  A distributed algorithm for large-scale graph partitioning.  _ACM Trans. Auton. Adapt. Syst._ , 10(2), jun 2015.  ISSN 1556-4665.  10.1145/2714568.
  * Römisch [2006] Werner Römisch.  _Delta method, infinite dimensional_ , pages 132–142.  2006\.  10.1002/0471667196.ess3139.
  * Saranurak and Wang [2019] Thatchaphol Saranurak and Di Wang.  Expander decomposition and pruning: faster, stronger, and simpler.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2616–2635. SIAM, Philadelphia, PA, 2019.  10.1137/1.9781611975482.162.
  * Serfling [1980] Robert J. Serfling.  _Approximation Theorems of Mathematical Statistics_.  John Wiley & Sons, Inc., New York, 1980.  ISBN 0-471-02403-1.
  * Shapiro [1990] A. Shapiro.  On concepts of directional differentiability.  _J. Optim. Theory Appl._ , 66(3):477–487, 08 1990.  ISSN 0022-3239.  10.1007/BF00940933.
  * Shapiro [1991] Alexander Shapiro.  Asymptotic analysis of stochastic programs.  _Ann. Oper. Res._ , 30(1-4):169–186, 1991.  ISSN 0254-5330.  10.1007/BF02204815.
  * Shi and Malik [2000] Jianbo Shi and J. Malik.  Normalized cuts and image segmentation.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 22(8):888–905, 08 2000.  ISSN 1939-3539.  10.1109/34.868688.
  * Šíma and Schaeffer [2006] Jiří Šíma and Satu Elisa Schaeffer.  On the NP-completeness of some graph cluster measures.  In _Proceedings of the 32nd Conference on Current Trends in Theory and Practice of Computer Science_ , SOFSEM’06, page 530–537. 2006.  ISBN 354031198X.  10.1007/11611257_51.
  * Suchan [2023] Leo Suchan.  R and Python implementations of the Xist algorithm, 2023.  https://github.com/leosuchan/Xist.
  * Suchan et al. [2023] Leo Suchan, Housen Li, and Axel Munk.  A scalable clustering algorithm to approximate graph cuts.  _arXiv:2308.09613_ , 2023.
  * Tanabe and Sagae [1992] Kunio Tanabe and Masahiko Sagae.  An exact Cholesky decomposition and the generalized inverse of the variance–covariance matrix of the multinomial distribution, with applications.  _J. R. Stat. Soc. B_ , 54(1):211–219, 1992.  10.1111/j.2517-6161.1992.tb01875.x.
  * Tao et al. [2007] W. Tao, H. Jin, and Y. Zhang.  Color image segmentation based on mean shift and normalized cuts.  _IEEE Trans. Syst. Man. Cybern. B Cybern._ , 37(5):1382–1389, 2007.  10.1109/TSMCB.2007.902249.
  * Tsay et al. [1999] A. Tsay, W. Lovejoy, and David Karger.  Random sampling in cut, flow, and network design problems.  _Math. Oper. Res._ , 24:383–413, 02 1999.  10.1287/moor.24.2.383.
  * von Luxburg [2007] Ulrike von Luxburg.  A tutorial on spectral clustering.  _Stat. Comput._ , 17:395–416, 08 2007.  10.1007/s11222-007-9033-z.
  * von Luxburg et al. [2008] Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet.  Consistency of spectral clustering.  _Ann. Statist._ , 36(2):555–586, 04 2008.  10.1214/009053607000000640.
  * Wagner and Wagner [1993] Dorothea Wagner and Frank Wagner.  Between min cut and graph bisection.  In _Proceedings of the 18th International Symposium on Mathematical Foundations of Computer Science_ , MFCS ’93, page 744–750. Springer-Verlag, Berlin, Heidelberg, 1993.  ISBN 3540571825.
  * Xing and Karp [2001] Eric P. Xing and Richard M. Karp.  Cliff: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts.  _Bioinformatics_ , 17(suppl1):S306–S315, 06 2001.  10.1093/bioinformatics/17.suppl_1.S306.
  * Yang et al. [2014] Yan T. Yang, Barak Fishbain, Dorit S. Hochbaum, Eric B. Norman, and Erik Swanberg.  The supervised normalized cut method for detecting, classifying, and identifying special nuclear materials.  _INFORMS J. Comput._ , 26(1):45–58, 2014.  10.1287/ijoc.1120.0546.
  * Zabih and Kolmogorov [2004] Ramin Zabih and Vladimir Kolmogorov.  Spatially coherent clustering using graph cuts.  In _Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , volume 2, pages II–II. 2004.  10.1109/CVPR.2004.1315196.
  * Zhou and Burges [2007] Dengyong Zhou and Christopher J. C. Burges.  Spectral clustering and transductive learning with multiple views.  In _Proceedings of the 24th International Conference on Machine Learning_ , ICML ’07, page 1159–1166. 2007.  ISBN 9781595937933.  10.1145/1273496.1273642.