# Metastable Mixing of Markov Chains: Efficiently Sampling
Low Temperature Exponential Random Graphs

Guy Bresler
MIT
<EMAIL_ADDRESS>Dheeraj Nagaraj
Google Research
<EMAIL_ADDRESS>Eshaan Nichani
Princeton University
<EMAIL_ADDRESS>
###### Abstract

In this paper we consider the problem of sampling from the low-temperature
exponential random graph model (ERGM). The usual approach is via Markov chain
Monte Carlo, but Bhamidi et al. showed that any local Markov chain suffers
from an exponentially large mixing time due to metastable states. We instead
consider _metastable mixing_ , a notion of approximate mixing relative to the
stationary distribution, for which it turns out to suffice to mix only within
a collection of metastable states. We show that the Glauber dynamics for the
ERGM at any temperature – except at a lower-dimensional critical set of
parameters – when initialized at $G(n,p)$ for the right choice of $p$ has a
metastable mixing time of $O(n^{2}\log n)$ to within total variation distance
$\exp(-\Omega(n))$.

##  1 Introduction

Given a vector of real-valued parameters
$\beta:=(\beta_{0},\beta_{1},\dots,\beta_{K})\in\mathbb{R}\times(\mathbb{R}^{+})^{K}$
, the exponential random graph model $\mathsf{ERGM}(n,\beta)$ is defined to be
the probability measure over all simple graphs with $n$ vertices

$\mu_{\beta}(X)=\frac{1}{Z_{\beta}}\exp\bigg{(}\sum_{i=0}^{K}n^{2}\beta_{i}N_{i}(X)\bigg{)}\,.$

The $N_{i}$ are subgraph counts corresponding to finite graphs
$G_{0},G_{1},\dots,G_{K}$ (such as edges, triangles, 4-cycles, 5-cycles,
2-stars, etc.) and $Z(\beta)$ denotes the normalizing constant. This is an
exponential family where the sufficient statistics are the subgraph counts.
The model significantly generalizes the Erdős-Rényi random graph and is used
to model a variety of complex networks like social networks and biological
networks [10, 16, 8, 9, 31]. Early analysis was carried out by statistical
physicists [24, 25, 4], and probabilists and statisticians have further
studied various questions about these models including sampling, estimation,
large deviations theory, concentration of measure, and phase transitions [1,
5, 26, 7, 11, 23, 32, 27].

The basic problem we consider in this work is that of producing a sample from
the $\mathsf{ERGM}$ probability distribution in polynomial time. A popular
approach to sampling is to use the Glauber dynamics, a simple reversible
Markov chain with the desired stationary distribution, and to run it for
sufficiently long that it is close to stationarity.

######  Definition 1.1 (Glauber Dynamics).

Given any probability distribution $\pi$ over
$\Omega=\\{0,1\\}^{{{n}\choose{2}}}$ with $\pi(x)>0$ for all $x\in\Omega$, the
Glauber dynamics with respect to $\pi$ is the discrete time Markov chain over
$\Omega$ with single step transition from $X$ to $X^{\prime}$ as follows:

  1. 1.

Pick a coordinate $E\in\left[{{n}\choose{2}}\right]$ uniformly at random.

  2. 2.

Form $X^{\prime}$ by keeping all edges except for $E$ the same as in $X$ and
sample $X^{\prime}_{E}\sim\pi(\cdot|X_{\sim E})$ conditional on the other
edges.

The Glauber dynamics with respect to $\pi$ is reversible for $\pi$ ([20]), so
in particular $\pi$ is stationary.

The mixing time of the Glauber dynamics, i.e., the time until the distribution
is within total variation $1/4$ of stationarity, determines whether the
approach is feasible and as shown by Bhamidi et al. [1] turns out to be
essentially characterized by the function $L_{\beta}:[0,1]\to\mathbb{R}$
defined as

$L_{\beta}(p)=\sum_{i=0}^{K}\beta_{i}p^{|E_{i}|}-I(p)$ (1)

where $I(p):=\frac{1}{2}p\log p+\frac{1}{2}(1-p)\log(1-p)$. (Bhamidi et al.
[1] actually formulated their results in an equivalent way in terms of the
function $\phi_{\beta}$ defined in Section 2.2, while $L_{\beta}$ was studied
by [6].)

######  Theorem 1.2 ([1]).

Consider the $\mathsf{ERGM}(n,\beta)$ distribution. There are three regimes
for $\beta$:

  1. 1.

High temperature: If $L_{\beta}$ has a unique local maximum with a non-
vanishing second derivative, then the Glauber dynamics Markov chain for
$\mathsf{ERGM}(n,\beta)$ mixes in time $O(n^{2}\log n)$.

  2. 2.

Low temperature: If $L_{\beta}$ has multiple local maxima with non-vanishing
second derivatives, then any local Markov chain with stationary distribution
$\mathsf{ERGM}(n,\beta)$ must suffer a mixing time of $\exp(\Omega(n))$.

  3. 3.

Critical temperature: If any local maxima of $L_{\beta}$ has a vanishing
second derivative.

In this work, we use a loose and intuitive notion of metastability since this
is not important in order to state our technical results: consider subsets of
the state space $A,B\subseteq\Omega$ such that $A\subseteq B$. We will call
$B$ to be metastable with respect to a given markov dynamics if the markov
dynamics initialized inside the set $A$ takes a long time to exit the set $B$.
In this work, we interpret ‘long time’ as being exponential in $n$. Slow
mixing in the low-temperature phase is due to the existence of multiple,
disconnected metastable states from which it takes the Glauber dynamics
exponential time to leave. The question is therefore: can one efficiently
produce a sample from the $\mathsf{ERGM}$ in the low temperature regime?

An important insight into the structure of the $\mathsf{ERGM}$ distribution
was developed by Chatterjee and Diaconis [6], and this will constitute a
useful step towards our goal. They showed that the $\mathsf{ERGM}$
distribution is close to a finite mixture of constant graphons with respect to
the cut-metric:

######  Theorem 1.3 (Theorem 4.2 of [6]).

Denote by $M_{\beta}$ the set of global maxima of $L_{\beta}$. The
$\mathsf{ERGM}(n,\beta)$ distribution converges, in probability with respect
to the cut-metric, to a mixture of $G(n,p^{*})$ for $p^{*}\in M_{\beta}$.
Formally, let $X_{n}\sim\mathsf{ERGM}(n,\beta)$ and $\tilde{X}_{n}$ be its
corresponding graphon and $\tilde{M}_{\beta}$ be the set of all constant
graphons with value $p^{*}$ for some $p^{*}\in M_{\beta}$. For every fixed
$\eta>0$, there are constants $C(\eta),c(\eta)>0$ such that

$\mathbb{P}(\delta_{\square}(\tilde{X}_{n},\tilde{M}_{\beta})>\eta)\leq
C(\eta)\exp(-c(\eta)n^{2})\,.$

Graphons and the cut metric are reviewed in Section 2.1.

Given the approximation results of Chatterjee and Diaconis, can one simply
find $p^{*}$ and obtain a sufficiently accurate approximation of the
$\mathsf{ERGM}$ by sampling $G(n,p^{*})$? Unfortunately, no: Theorem 1.3 is in
_cut metric_ , which turns out to be too weak to control total variation
distance. Indeed, the paper [3] shows that
$d_{\mathsf{TV}}(\mathsf{ERGM},G(n,p^{*}))\to 1$ even for the simple
$\mathsf{ERGM}$ consisting of edges and 2-stars. The approximation results of
Eldan and Gross [7] show that even in the low-temperature regime, the
$\mathsf{ERGM}$ can be approximated in a certain Wasserstein metric by an
appropriate mixture of stochastic block models, endowing it with richer
structure compared to $G(n,p^{*})$. However, these results also do not imply
approximation in the total variation distance.

The $\mathsf{ERGM}$ is closely related to the ferromagnetic Ising model and,
in fact, the $\mathsf{ERGM}$ with the 2-star can be written as an Ising model.
Just as for the $\mathsf{ERGM}$, the Glauber dynamics is known to mix
exponentially slowly for the Ising model at low temperatures. Nevertheless,
there are Markov chains mixing in polynomial-time which can sample efficiently
from arbitrary ferromagnetic Ising models based on random cluster dynamics
[15] and the Swendsen-Wang dynamics [29, 30]. For the $\mathsf{ERGM}$ it is
not at all clear how to write down the corresponding random cluster model such
that the associated random cluster dynamics mixes rapidly. We instead pursue a
more direct approach.

The starting point of our approach is the observation that if our aim is only
to produce a sample from nearly the correct distribution, then there is no
need for the dynamics to transition between all metastable states. In order to
implement this intuition, it is necessary to slightly modify the standard
definition of mixing time of a Markov chain. The usual definition measures the
distance to stationarity starting from a worst-possible initial state.
Instead, we use the following definition.

######  Definition 1.4.

Given a Markov transition kernel $P$ with stationary $\pi^{*}$ we start from
some initial distribution $\pi_{0}$ and say that $P$ is
$(\pi_{0},\pi^{*},\tau,\delta)$-mixing if for every $t\geq\tau$

$d_{\mathsf{TV}}(\pi_{0}P^{t},\pi^{*})\leq\delta\,.$ (2)

Note that an immediate consequence of the data processing inequality for total
variation is that $P$ is $(\pi_{0},\pi^{*},\tau,\delta)$-mixing if and only if
$d_{\mathsf{TV}}(\pi_{0}P^{\tau},\pi^{*})\leq\delta$.

The role of $\delta_{0}$ merits some discussion. Incorporating the starting
distribution into the definition of mixing time invalidates one of the basic
lemmas: it is no longer true that the total variation decreases exponentially
fast once the mixing time is exceeded. The basic reason is that in a Markov
chain with multiple metastable states requiring exponential time to leave, any
initial error in probability assigned to the metastable states might persist
for exponential time. Thus, one might think of $\delta_{0}$ as capturing this
initial (possibly unavoidable) error. Gheissari and Sinclair’s work [14] on
mixing in low-temperature Ising models also considers mixing up to a TV
distance of $\delta_{0}$.

Our main result, Theorem 3.1 given in Section 3, shows that whenever
$\delta\geq\delta_{0}=\exp(-\Omega_{\beta}(n))$, with $\pi_{0}$ being a
mixture of $G(n,p^{*})$ for some carefully chosen distribution $p^{*}$, the
Glauber dynamics for $\mathsf{ERGM}$ is
$(\pi_{0},\pi^{*},C_{\beta}n^{2}\log\frac{n}{\delta},\delta)$-mixing even in
the low temperature regime. That is, as long as as the target TV distance is
$\geq\delta_{0}$, then the mixing time of the Glauber dynamics is $O(n^{2}\log
n)$. This gives a counterpoint to the criticism of these models in [1] based
on the difficulty of sampling these models at low temperature. The following
is a corollary of Theorem 3.1.

######  Theorem 1.5.

Suppose that $p^{*}$ is the unique global maximizer of $L_{\beta}$ and
moreover that $L_{\beta}$ has nonzero second derivative at $p^{*}$. Let
$\pi_{0}:=G(n,p^{*})$. There exist positive constants $c_{\beta},C_{\beta}$
and $n_{0}(\beta)$, such that if $n>n_{0}(\beta)$, then whenever
$\delta\geq\exp(-c_{\beta}n)$, the Glauber dynamics for $\mu_{\beta}$ is
$\big{(}\pi_{0},\mu,C_{\beta}n^{2}\log({n^{2}}/{\delta}),\delta\big{)}$-mixing.

In fact, Theorem 3.1 is richer and shows that even when there are multiple
global maximizers in the low temperature regime, we can sample efficiently
from the conditional distribution of being close to any of these maximizers.
In Theorem 3.3, we establish a surprising richness which can be present in the
$\mathsf{ERGM}$ at low temperature. Even within a small cut-metric
neighborhood of the constant $p^{*}$ graphon where the $\mathsf{ERGM}$ measure
concentrates (and looks very close to $G(n,p^{*})$) [6], we establish the
existence of metastable states for certain choices of $\beta$ whose total
probability is $\exp(-\Theta(n))$. The Glauber dynamics takes an exponentially
long time to escape this set of metastable states. In contrast, Bhamidi et al.
[1] constructed metastable states as sets of graphs similar to $G(n,p)$, where
$p$ was a local maximizer of $L_{\beta}$, and these have a total probability
of $\exp(-\Omega(n^{2}))$.

###  1.1 Overview and Proof Sketch

We now give a high level overview of the ideas behind the main results, which
are stated in Section 3.

#### Sufficient Conditions for Path Coupling

The large deviations results in [6] stated here as Theorem 1.3 show that a
sample from the $\mathsf{ERGM}$ is w.h.p. close in cut-metric to some constant
graphon with value $p^{*}$. Sufficient conditions established in [1] for the
path coupling argument to work requires much stronger control on small
subgraph counts than provided by the cut-metric: the increase in homomorphism
density of $G$ in $X$ formed by adding any edge $e$ to $X$ (denoted by
$\Delta^{e}_{G}(X)$) must be approximately ${2n^{-2}|E(G)|}(p^{*})^{|E(G)|-1}$
for every fixed subgraph $G$. We will show that $\Delta^{e}_{G}(X)$ indeed
concentrates close to this value with probability
$1-\exp(-\Omega_{\beta}(n))$. The coupling argument showing how this statement
implies our main theorem is contained in Sections 4 and 5.

#### Fixed Point Equations for Subgraph Concentration

Theorem 1.3 shows that $X\sim\mu$ is close to the constant graphon with value
$p^{*}$. Section 6 reduces the task of showing concentration of
$\Delta^{e}_{G}(X)$ to show additionally that: (1) every node degree uniformly
concentrates close to $p^{*}$ and (2) that the number of common neighbors of
any two vertices $u$ and $v$ is close $n(p^{*})^{2}$. We show these two
properties as follows. First, concentration of degrees is established using
the cavity method, discussed momentarily. For the second property, we make use
of the concentration of degrees to derive a fixed point equation for the
common neighbor counts and use the concentration results for fixed point
equations established in [5, Theorem 1.5]. We note that the concentration
results given by [5, Theorem 1.5] in themselves do not seem to be sufficient
to establish the concentration of $\Delta^{e}_{G}(X)$ and the concentration of
degrees as established by the cavity method is essential.

#### Cavity Method for Degrees

We use the cavity method as developed in Section 8 to first show that
conditioned on the exponential random graph $X$ being close to the constant
$p^{*}$ graphon, the normalized degree of _every_ vertex concentrates close to
$p^{*}$. Graphon convergence can show that _most_ vertices have degree close
to $p^{*}$ (see Lemma 7.2). To obtain the uniform concentration, we look at
the law of the the edges emanating from a single vertex (called the cavity)
conditioned on the rest of the graph being close to the constant graphon
$p^{*}$. We show that the “mean field” generated by the rest of the graph
forces the cavity vertex to have degree close to $p^{*}$ with high
probability. This is established in Theorem 8.9 and Corollary 8.10 and is our
main technical innovation.

###  1.2 Discussion and Future Work

Fast mixing of a Markov chain can be used to establish concentration of
measure, central limit theorems, and estimation of the partition function.
Concentration of measure, CLTs and approximation by $G(n,p)$ ([11, 27]) have
been explored in the literature for high-temperature $\mathsf{ERGM}$ models.
It would be interesting to consider their extension to low-temperature
$\mathsf{ERGM}$ via the approximate mixing established in this work. Maximum
likelihood estimation often involves estimation of the partition function.
There are multiple works ([17, 28, 12, 13, 18]) that efficiently approximate
partition functions of a parametric family with a given parameter $\beta$ by
efficiently generating samples from the distribution for every choice of the
parameter $\beta^{\prime}$. We leave open the problem of estimating the
partition function of the low-temperature $\mathsf{ERGM}$.

###  1.3 Related Work

Polynomial or quasipolynomial time mixing from a well-chosen initial
distribution has been explored for the mean field Ising model by Levin et al.
[19] and more recently for the Ising model on the lattice $\mathbb{Z}^{d}$ by
Gheissari and Sinclair [14]. Lubetzky and Sly [22] consider mixing from
specific initial conditions for the $1$-dimensional Ising model and identify
initial states which allow faster mixing than the worst case by constant
factors. The work [21] considers an idea similar to ours in isolating the
‘modes’ of a probability distribution in order to aid sampling. Their approach
consider multiple, coupled, random instantiations of the Markov chains, which
are all allowed to interact as the evolve, whereas our work considers a single
instance of such a Markov chain.

##  2 Background and Notation

This section contains the basic definitions and notation for graphons and the
Glauber dynamics.

###  2.1 Graphon Theory

Our work relies heavily on the theory of graph limits and graphons; our
notation follows [6]. Let $\mathcal{W}$ denote the space of symmetric
measurable functions $f:[0,1]^{2}\rightarrow[0,1]$, where the space
$[0,1]^{2}$ is endowed with the uniform probability measure. For
$f,g\in\mathcal{W}$, define their _cut distance_ to be

$\delta_{\square}(f,g)=\sup_{S,T\subset[0,1]}\left|\int_{S\times
T}\big{(}f(x,y)-g(x,y)\big{)}dxdy\right|\,,$

where the supremum is over Borel measurable sets $S,T$. Define the equivalence
relation $\sim$ on $\mathcal{W}$ by $f\sim g$ iff there exists a measure
preserving bijection $\sigma:[0,1]\rightarrow[0,1]$ such that $f(x,y)=g(\sigma
x,\sigma y):=g_{\sigma}(x,y)$. Let $\tilde{\mathcal{W}}$ be the quotient space
with respect to this equivalence relation. For $f\in\mathcal{W}$, let
$\tilde{f}$ denote its orbit in $\mathcal{W}$. A metric $\delta_{\square}$ on
$\tilde{\mathcal{W}}$ can now be defined as

$\delta_{\square}(\tilde{f},\tilde{g})=\inf_{\sigma}\delta_{\square}(f,g_{\sigma})\,.$

An important fact in the theory of graph limits is that
$(\tilde{\mathcal{W}},\delta_{\square})$ is a compact metric space.

For a graph $X$ with vertex set $[n]$, we can associate the function
$f^{X}\in\mathcal{W}$ where $f^{X}(x,y)=\mathds{1}_{(\lfloor nx\rfloor,\lfloor
ny\rfloor)\in E(X)}=X_{\lfloor nx\rfloor,\lfloor ny\rfloor}$. We define its
corresponding graphon to be $\tilde{X}=\tilde{f}^{X}\in\tilde{\mathcal{W}}.$
Note that under this mapping, vertex isomorphic graphs correspond to the same
element of $\tilde{\mathcal{W}}$. We will denote the graphon with the constant
value $p\in[0,1]$ by $p\mathbf{1}$.

For a finite simple graph $H$ with vertex set $[k]$ for some $k\in\mathbb{N}$
and a graphon $h\in\tilde{W}$, we define the homomorphism density $t(H,h)$ as

$t(H,h)=\int_{[0,1]^{k}}\prod_{(i,j)\in E(H)}h(x_{i},x_{j})dx_{1}\dots
dx_{k}\,.$

In particular, the subgraph counts $N_{i}(X)$ appearing in the Hamiltonian
$\mathcal{H}_{\beta}(X)$ are defined as the homomorphism densities

$N_{i}(X):=t(G_{i},\tilde{f}^{X})\,.$ (3)

When emphasizing a particular graph $G$ we will also use the notation
$N_{G}(X)$.

The classical theory of graph limits is too coarse to understand convergence
of Markov chains because the cut metric does not control degrees of individual
vertices (or neighborhoods of two vertices), which can have a large impact on
the evolution of the Glauber dynamics. The following quantities will allow us
to establish a fine-grained understanding of the measure $\mu$. Given a graph
$X$ with $n$ vertices, whenever $u\in[n]$, we define the normalized degree

$p_{u}(X):=\frac{\text{degree of vertex
}u}{n}=n\int_{0}^{1}\int^{\frac{u}{n}}_{\frac{u-1}{n}}f^{X}(x,y)dxdy\,.$ (4)

Similarly, define the normalized wedge count for nodes $u,v$ by

$\displaystyle p_{uv}(X)$ $\displaystyle:=\frac{\text{number of vertices to
which both $u$ and $v$ have edges}}{n}$
$\displaystyle=n^{2}\int_{0}^{1}\int_{\frac{u-1}{n}}^{\frac{u}{n}}\int_{\frac{v-1}{n}}^{\frac{v}{n}}f^{X}(x,z)f^{X}(y,z)dxdydz\,.$
(5)

###  2.2 Glauber Dynamics for the ERGM

As described in the introduction, at each step of the Glauber dynamics for
$\mu$ a pair of vertices $e=\\{u,v\\}$ is chosen uniformly at random from the
$n\choose 2$ possibilities and the variable $X_{e}$ indicating presence of
edge $e$ is updated according to the conditional probability

$\phi_{e}(X_{\sim e}):=\mathbb{E}_{X\sim\mu}\left[X_{e}\bigr{|}X_{\sim
e}\right]\,.$ (6)

It will be useful to express the update probability in terms of subgraph
counts. For any graph $G=(V,E)$ define

$\Delta^{e}_{G}(X)=N_{G}(X^{+e})-N_{G}(X^{-e})$ (7)

and let

$r_{G}(X,e):=\left(\frac{n^{2}\Delta^{e}_{G}(X)}{2|E|}\right)^{\tfrac{1}{|E|-1}}\,.$

The update probability can be expressed as

$\phi_{e}(X_{\sim e})=\mathbb{E}_{X\sim\mu}[X_{e}|X_{\sim
e}]=\frac{\exp(2\beta_{0}+\sum_{l=1}^{K}2\beta_{l}|E_{l}|r_{G_{l}}(X,e)^{|E_{l}|-1})}{1+\exp(2\beta_{0}+\sum_{l=1}^{K}2\beta_{l}|E_{l}|r_{G_{l}}(X,e)^{|E_{l}|-1})}\,.$

It follows from the definitions that if $X\sim G(n,p)$, then
$r_{G}(X,e)\approx p$ with high probability. If, conversely, it were the case
that $r_{G}(X,e)=p$ for all $G_{1},\dots,G_{K}$, then the update probability
takes the following simpler form (with some abuse of notation) given by
$\phi_{\beta}:[0,1]\to[0,1]$ with

$\phi_{\beta}(p)=\frac{\exp(\sum_{i=0}^{K}2\beta_{i}|E_{i}|p^{|E_{i}|-1})}{1+\exp(\sum_{i=0}^{K}2\beta_{i}|E_{i}|p^{|E_{i}|-1})}\,.$
(8)

Let $M_{\beta}$ denote the set of global maximizers of $L_{\beta}$. Let
$U_{\beta}\subset M_{\beta}$ be the global maximizers where the second
derivative of $L_{\beta}$ is nonzero. It can be shown that $p^{*}\in
U_{\beta}$ only if $p^{*}=\phi_{\beta}(p^{*})$ and
$\phi^{\prime}_{\beta}(p^{*})<1$. What this implies is that $p^{*}$ is a
_stable fixed point_ : if the chain is started at $X$ where $r_{G}(X,e)\approx
p^{*}$ for all $G\in{G_{1},\dots,G_{K}}$, then that continues to hold for
exponentially many steps. This was shown in Lemma 17 from [1] and is stated in
our paper as Lemma 4.8.

We will also need to consider the Glauber dynamics for distributions $\pi$
that assign zero probability to some graphs.

######  Definition 2.1 (Glauber Dynamics).

Given any probability distribution $\pi$ over
$\Omega=\\{0,1\\}^{{{n}\choose{2}}}$, we define the Glauber dynamics with
respect to $\pi$ to be the discrete time Markov chain over $\Omega$ with
single step transitions (to obtain $X^{\prime}$) as follows:

  1. 1.

Pick a coordinate $E\in\left[{{n}\choose{2}}\right]$ uniformly at random.

  2. 2.

Given the coordinate $E$, define $X^{\oplus E}$ to be $X$ with edge $E$
flipped, and let

$X^{\prime}=\begin{cases}X^{\oplus E}\text{ with probability
}\frac{\pi(X^{\oplus E})}{\pi(X^{\oplus E})+\pi(X)}&\text{ if }\pi(X)\neq 0\\\
X^{\oplus E}\text{ with probability $1$}&\text{ if }\pi(X)=0\\\ X\text{ with
probability }\frac{\pi(X)}{\pi(X^{\oplus E})+\pi(X)}\end{cases}$ (9)

The Glauber dynamics with respect to $\pi$ is reversible for $\pi$ ([20]), so
in particular $\pi$ is stationary. When $\pi(X)>0$ for every $X$, this reduces
to the definition given in Definition 1.1

###  2.3 Notation

For any simple graph $X$, we denote by $V(X)$ its vertex set and by $E(X)$ its
edge set. Given an unordered pair $e=(u,v)$ for some $u,v\in V(X)$, we define
$X_{e}=X_{uv}=X_{vu}=\mathds{1}(e\in E(X))$. Without loss of generality, we
take $V(X)=[n]$, where $|V(X)|=n$, and identify the space of finite simple
graphs on $n$ vertices with the space $\Omega:=\\{0,1\\}^{{{n}\choose{2}}}$,
where the coordinates are indexed by tuples $(u,v)$ for $u<v$, $u,v\in[n]$.
Throughout, we will reserve $u,v,w$ to denote vertices of size $n$ random
graphs for large $n$ and $i,j,l$ to denote vertices of fixed graphs like
$G_{0},G_{1},\dots$ above.

By $X_{\sim e}$ we denote the graph formed by all edges other than the edge
$e$. Given $X\in\Omega$, define $X^{+e}\in\Omega$ (resp. $X^{-e}\in\Omega$) by
$(X^{+e})_{\sim e}=X_{\sim e}$ (resp. $(X^{-e})_{\sim e}=X_{\sim e}$) and
$(X^{+e})_{e}=1$ (resp. $(X^{-e})_{e}=0$) i.e., we add (resp. remove) edge $e$
to the graph $X$.

We use the standard asymptotic notation $O(\,\cdot\,),\Omega(\,\cdot\,)$, and
$\Theta(\,\cdot\,)$. For $x,y\in\mathbb{R}^{+}$ $y=O_{\gamma}(x)$, we mean
$y\leq C_{\gamma}x$ for some constant $C_{\gamma}$ which depends only on
$\gamma$ (and similarly for $\Omega_{\gamma}$ and $\Theta_{\gamma}$). In the
statement of the results, expressions of the form $\epsilon<c(\gamma)$ mean
“$\epsilon$ smaller than a constant depending only on $\gamma$” and
$n>n_{0}(\gamma)$ means “$n$ larger than a constant depending only on
$\gamma$”.

We will occasionally use the function $I:[0,1]\to-[1/2,0]$ given by
$I(p):=\frac{1}{2}p\log p+\frac{1}{2}(1-p)\log(1-p)$. This is just $-1/2$
times the binary entropy function.

##  3 Main Results

Fix $\beta\in\mathbb{R}\times\left(\mathbb{R}^{+}\right)^{K}$, and recall that
$M_{\beta}$ denotes the set of global maximizers of $L_{\beta}$. Let
$U_{\beta}\subset M_{\beta}$ be the global maximizers where the second
derivative of $L_{\beta}$ is nonzero. Throughout, we will always take
$p^{*}\in U_{\beta}$. When $|U_{\beta}|=|M_{\beta}|=1$, our main result,
stated below in Theorem 3.1, shows that the Glauber dynamics for
$\mathsf{ERGM}$ when initialized at the $G(n,p^{*})$ distribution rapidly
approximately mixes as long as the target total variation distance
$\delta_{0}\geq\exp(-c_{\beta}n)$ (see Definition 1.4). Note that
$|U_{\beta}|=|M_{\beta}|=1$ even in the low temperature regime for Lebesgue
almost all $\beta$.

In the case that $|U_{\beta}|>1$, we show that Glauber dynamics with the same
initialization as above can efficiently and approximately sample from the
$\mathsf{ERGM}$ conditioned on being close in cut metric to the constant
$p^{*}$ graphon. Note that Theorem 1.3 shows that with a very large
probability, a sample from the $\mathsf{ERGM}$ is close to the constant $p$
graphon for some $p\in U_{\beta}$. If the probability of being close in cut-
metric to each $p\in U_{\beta}$ under the measure $\mu$ is known, then we can
initialize the Glauber dynamics to the correct mixture of $(G(n,p))_{p\in
U_{\beta}}$ and show that it mixes rapidly as long as the target total
variation distance $\delta_{0}\geq\exp(-c_{\beta}n)$. In this work, we do not
consider the problem of estimating these mixture probabilities.

For $\eta>0$ denote the $\eta$-ball in cut metric around $p^{*}$ by

$B^{\square}_{\eta}(p^{*}):=\\{X\in\Omega:\delta_{\square}(X,p^{*}\mathbf{1})\leq\eta\\}\,.$

Let $P_{\eta}$ be the kernel of the Glauber dynamics with respect to the
measure $\mu(\,\cdot\,|B^{\square}_{\eta}(p^{*}))$ and let $P$ be the kernel
of the Glauber dynamics with respect to the measure $\mu$.

######  Theorem 3.1.

Let $\pi_{0}:=G(n,p^{*})$ for any $p^{*}\in U_{\beta}$. Let
$\bar{X}_{0}\sim\pi_{0},\bar{X}_{1},\bar{X}_{2},\dots,$ evolve according to
$P_{\eta}$ and $X_{0}\sim\pi_{0},X_{1},X_{2},\dots$ evolve according to $P$.
There exist positive constants $\eta_{0}(\beta)$,
$c_{\beta,\eta},C_{\beta,\eta}$ and $n_{0}(\beta,\eta)$ such that whenever
$\eta<\eta_{0}(\beta)$ and $n>n_{0}(\beta,\eta)$, the following hold:

  1. 1.

$(X_{0},X_{1},\dots,X_{T})$ can be coupled with
$(\bar{X}_{0},\dots,\bar{X}_{T})$ such that with probability at least
$1-TC(\beta,\eta)\exp(-c_{\beta,\eta}n)$, we have

$(X_{0},X_{1},\dots,X_{T})=(\bar{X}_{0},\bar{X}_{1},\dots,\bar{X}_{T})\,.$

  2. 2.

Whenever $\delta\geq\exp(-c_{\beta,\eta}n)$, $P_{\eta}$ is
$(\pi_{0},\mu(\cdot|B^{\square}_{\eta}(p^{*})),C_{\beta,\eta}n^{2}\log({n^{2}}/{\delta}),\delta)$-mixing.

  3. 3.

If $|U_{\beta}|=|M_{\beta}|=1$, then whenever
$\delta\geq\exp(-c_{\beta,\eta}n)$, $P$ is
$(\pi_{0},\mu,C_{\beta,\eta}n^{2}\log({n^{2}}/{\delta}),\delta)$-mixing.

This theorem shows that we can achieve metastable mixing by disregarding a
portion of the state space of probability $\exp(-c_{\beta,\eta}n)$ under the
measure $\mu(\cdot|B^{\square}_{\eta}(p^{*}))$. One might wonder if this is
necessary, and in particular whether it is possible to improve the second item
due to $B^{\square}_{\eta}(p^{*})$ being possibly well-connected. We next
answer this question in the negative and gain insight into the structure of
the $\mathsf{ERGM}$ measure at low temperature.

The paper [1] constructs metastable states where the graph is close to
$G(n,p)$ for some $p$ which is a local maximizer of $L_{\beta}$, from which
any local Markov chain takes $\exp(\Omega(n))$ time to escape. The large
deviations theory based results established in [6] show that when $p$ is not
the global minimizer of $L_{\beta}$, then these metastable states collectively
have mass $\exp(-\Omega(n^{2}))$. One might hypothesize that the metastable
states can be fully characterized by the behavior of local maximizers of
$L_{\beta}$ and the cut-metric neighborhoods, and moreover that they have
total mass $\exp(-\Omega(n^{2}))$ .

Perhaps surprisingly, it turns out instead that the low-temperature
$\mathsf{ERGM}$ landscape is remarkably intricate even within the neighborhood
$B^{\square}_{\eta}(p^{*})$ around the global optimizer $p^{*}$. We show by
construction that this set can contain multiple metastable states which
collectively have mass $\exp(-\Theta(n))$ and from which the Glauber dynamics
takes $\exp(\Omega(n))$ time to escape. These states are close in cut-metric
to the constant graphon $p^{*}$ and it follows that cut-metric based large
deviations analysis cannot capture the intricacies of Markov chain mixing in
the $\mathsf{ERGM}$ at low-temperatures.

######  Example 3.2.

Suppose $K=1$ and let $G_{1}$ be the triangle graph (i.e, the $3$ clique). Let
$\sigma(x):=e^{x}/(1+e^{x})$. There exist parameters
$\beta_{0},\beta_{1}\in\mathbb{R}\times\mathbb{R}^{+}$ and real numbers
$p_{1}^{*}\neq p_{2}^{*}$ such that:

  1. 1.

$p_{1}^{*}$ and $p_{2}^{*}$ satisfy
$p_{i}^{*}=\sigma(2\beta_{0}+6\beta_{1}(p_{i}^{*})^{2})$,
$U_{\beta}=\\{p_{1}^{*}\\}$, and $p_{2}^{*}$ is a local maximizer of
$L_{\beta}$;

  2. 2.

There exists $q^{*}\in[0,1]$, $q^{*}\notin\\{p_{1}^{*},p_{2}^{*}\\}$, such
that $q^{*}=\sigma(2\beta_{0}+6\beta_{1}q^{*}p_{1}^{*})$;

  3. 3.

Taking $f(x)=\sigma(2\beta_{0}+6\beta_{1}x^{2})$ and
$g(x)=\sigma(2\beta_{0}+6\beta_{1}xp_{1}^{*})$, we have
$f^{\prime}(p_{1}^{*})<1$ and $g^{\prime}(q^{*})<1$.

We numerically check that the choice $\beta_{0}=-1.8$ and $\beta_{1}=2$ has
$p_{1}^{*},p_{2}^{*}$, and $q^{*}$ satisfying the relations above. As shown
next, this turns out to imply metastability.

######  Theorem 3.3.

Consider Example 3.2 given above. Let $\eta>0$ be any small enough constant.
Let the initial state $X_{0}$ be such that
$(X_{0})_{1j}\sim\mathsf{Ber}(q^{*})$ and
$(X_{0})_{ij}\sim\mathsf{Ber}(p_{1}^{*})$ for $i,j\neq 1$ and $i<j$ are
independently distributed. Suppose $X_{0},X_{1},\dots$ is the trajectory of
the Glauber dynamics with respect to $\mu$ with $\beta$ as given in Example
3.2. Define the set of graphs $\Omega_{q,p}(\eta)$ for $q,p\in[0,1]$ by

$\Omega_{q,p}(\eta):=\\{X\in\Omega:\delta_{\square}(X,p)\leq{\eta}/{2}\text{
and }|p_{1}(X)-q|\leq\eta\\}\,.$

Then the following hold:

  1. 1.

The set $\Omega_{q^{*},p_{1}^{*}}(\eta)$ is metastable: There is a constant
$\alpha>0$ such that

$\mathbb{P}\left(\cap_{t\leq\exp(\alpha
n)}\\{X_{t}\in\Omega_{q^{*},p_{1}^{*}}(\eta)\\}\right)\geq
1-\exp(-\Omega_{\eta}(n))\,.$

  2. 2.

The set $\Omega_{q^{*},p_{1}^{*}}(\eta)$ has sizable probability:

$\mu(\Omega_{q^{*},p_{1}^{*}}(\eta))=\exp(-\Theta_{\eta}(n))\,.$

  3. 3.

Most of the mass lies in $\Omega_{p_{1}^{*},p_{1}^{*}}(\eta)$:

$\mu(\Omega_{p_{1}^{*},p_{1}^{*}}(\eta))\geq 1-\exp(-\Omega_{\eta}(n))\,.$

The theorem is proved in Section 9.

In order to see why the set of states described in the theorem above are
metastable, consider the first step of Glauber dynamics taking $X_{0}$ to
$X_{1}$. The number of triangles formed by including an edge $e=(1,j)$ is
approximately $nq^{*}p_{1}^{*}$ (which is $6np_{1}^{*}q^{*}$ after counting
re-labelings), i.e.,
$\Delta^{e}_{G_{1}}(X_{0})\approx\frac{6p^{*}_{1}q^{*}}{n^{2}}$. Thus, the
Glauber dynamics updates this coordinate to $1$ with probability
$\approx\sigma(2\beta_{0}+6\beta_{1}q^{*}p_{1}^{*})=q^{*}$. Similarly, if an
edge $e=(i,j)$ is to be updated with $i,j\neq 1$, then the number of triangles
formed is $n(p_{1}^{*})^{2}$ (which is $6np_{1}^{*}q^{*}$ after counting re-
labelings) i.e.,
$\Delta^{e}_{G_{1}}(X_{0})\approx\frac{6(p_{1}^{*})^{2}}{n^{2}}$, and the
probability of setting this coordinate to $1$ is
$\approx\sigma(2\beta_{0}+6\beta_{1}(p_{1}^{*})^{2})=p_{1}^{*}$. Therefore,
the Glauber dynamics update still makes $X_{1}$ look approximately like the
initial distribution. Not only that, but this is a stable fixed point, which
follows from the conditions $f^{\prime}(p_{1}^{*})<1$ and
$g^{\prime}(q^{*})<1$.

##  4 Showing Metastable Mixing for Glauber Dynamics

###  4.1 Couplings, Contraction, and Mixing

Consider a Markov chain over the finite state space $\mathcal{X}$ and with
transition kernel $P$. Let $d:\mathcal{X}\times\mathcal{X}\to\mathbb{R}^{+}$
be such that $\sup_{x,y\in\mathcal{X}}d(x,y)\leq d_{\mathrm{max}}$ and
$\inf_{x\neq y}d(x,y)\geq d_{\mathrm{min}}$. We will use the following lemma
to establish metastable mixing, proved in Appendix C.

######  Lemma 4.1.

Let $A\subseteq\mathcal{X}\times\mathcal{X}$ be such that for $(x,y)\in A$
there exists a $\gamma$-contractive coupling $Q_{xy}$ of $P(x,\cdot)$ and
$P(y,\cdot)$, i.e. for $(X^{\prime},Y^{\prime})\sim Q_{xy}$ we have

$\mathbb{E}d(X^{\prime},Y^{\prime})\leq(1-\gamma)d(x,y)\,.$

Then, given any jointly distributed
$(X_{0},Y_{0})\in\mathcal{X}\times\mathcal{X}$, there exists a coupling
between the trajectories $(X_{k})_{k\geq 0}$ and $(Y_{k})_{k\geq 0}$ of the
Markov chain $P$ such that

$\mathbb{E}d(X_{k+1},Y_{k+1})\leq(1-\gamma)\mathbb{E}d(X_{k},Y_{k})+d_{\mathrm{max}}p_{k}\,,$

where $p_{k}:=\mathbb{P}((X_{k},Y_{k})\in A^{\complement})$. Unrolling this
recursion, we conclude that

$\mathbb{E}d(X_{K},Y_{K})\leq
d_{\mathrm{max}}\Big{[}(1-\gamma)^{K}+\frac{\sup_{k\leq
K}p_{k}}{\gamma}\Big{]}\,.$

The following corollary is immediate from the coupling characterization of
total variation.

######  Corollary 4.2.

In the setting of Lemma 4.1, if additionally $\inf_{x\neq y}d(x,y)\geq
d_{\mathrm{min}}$, then
$d_{\mathsf{TV}}(X_{K},Y_{K})\leq\frac{d_{\mathrm{max}}}{d_{\mathrm{min}}}\big{[}(1-\gamma)^{K}+\gamma^{-1}\sup_{k\leq
K}p_{k}\big{]}$.

In essence, the result above shows that whenever two trajectories can be
coupled such that with high probability they lie in a set $A$ where a
contractive coupling exists, then the laws of their iterates converge until a
certain lower threshold. In particular, taking $Y_{0}$ to be drawn from the
stationary distribution of $P$, we can establish metastable mixing for
$X_{0},X_{1},\dots$.

We will use the monotone coupling, defined next.

######  Definition 4.3 (Monotone coupling).

When $P$ is the kernel of the Glauber dynamics with respect to $\mu$, the
following coupling between $P(x,\cdot)$ and $P(y,\cdot)$ is called the
monotone coupling. For any two $x,y\in\Omega$, we obtain the one step Glauber
dynamics updates $X^{\prime},Y^{\prime}$ as follows:

  1. 1.

Pick the update edge $E\in{{[n]}\choose{2}}$ uniformly at random to be the
same for both $X^{\prime}$ and $Y^{\prime}$.

  2. 2.

Draw $U\sim\mathsf{Unif}([0,1])$ independent of everything else and set

$X^{\prime}=\begin{cases}x^{+E}\text{ if }U\in[0,\phi_{E}(x_{\sim E}))\\\
x^{-E}\text{ otherwise}\end{cases}\qquad\text{and}\qquad
y^{\prime}=\begin{cases}y^{+E}\text{ if }U\in[0,\phi_{E}(y_{\sim E}))\\\
y^{-E}\text{ otherwise.}\end{cases}$ (10)

For any two graphs $X,Y\in\Omega$, the relation $X\preceq Y$ denotes that
$X_{e}\leq Y_{e}$ for every $e\in{{[n]}\choose{2}}$. It follows immediately
from the definition of the monotone coupling that given $X\preceq Y$, if
$X^{\prime},Y^{\prime}$ are obtained via the monotone coupling, then
$X^{\prime}\preceq Y^{\prime}$ almost surely. We next identify a region of the
state space over which the coupling is contractive (as required by Lemma 4.1).

###  4.2 Control of Subgraph Counts Implies Contraction

We will now follow the results established in [1] to show the path coupling of
Glauber dynamics and use the notations they introduced. Recall that the update
probability under the Glauber dynamics for $\mu$ is given by

$\phi_{e}(X_{\sim
e})=\frac{\exp(\beta_{0}+\sum_{l=1}^{K}2\beta_{l}|E_{l}|r_{G_{l}}(X,e)^{|E_{l}|-1})}{1+\exp(\beta_{0}+\sum_{l=1}^{K}2\beta_{l}|E_{l}|r_{G_{l}}(X,e)^{|E_{l}|-1})}\,,$

where

$r_{G}(X,e):=\Big{(}\frac{n^{2}\Delta^{e}_{G}(X)}{2|E(G)|}\Big{)}^{\tfrac{1}{|E(G)|-1}}$

and $\Delta^{e}_{G}(X)=N_{G}(X^{+e})-N_{G}(X^{-e})$.

Let $\mathbb{G}_{L}$ denote the set of finite simple graphs with at most $L$
vertices (omitting the graph with $1$ edge and $2$ vertices), where $L$ is a
fixed constant satisfying $L>\max_{i\leq K}|V_{i}|$. Define the set

$\Gamma_{p^{*},\epsilon}:=\big{\\{}X:r_{G}(X,e)\in[p^{*}-\epsilon,p^{*}+\epsilon]\text{
for all }e\in\textstyle{[n]\choose 2}\text{ and
}G\in\mathbb{G}_{L}\big{\\}}\,.$ (11)

Note that whenever $X\in\Gamma_{p^{*},\epsilon}$, $\phi_{e}(X_{\sim
e})\approx\phi_{\beta}(p^{*})\approx p^{*}$. That is, each edge updates
approximately like $G(n,p^{*})$. The significance of $\Gamma_{p^{*},\epsilon}$
is that in this set the monotone coupling is contractive, as shown in [1,
Lemma 18] and stated next. We will additionally state a theorem in the next
subsection that $\Gamma_{p^{*},\epsilon}$ has high probability under
$\mu(\cdot|B^{\square}_{\eta}(p^{*}))$.

######  Lemma 4.4 (Contraction within $\Gamma_{p^{*},\epsilon}$, [1]).

Let $p^{*}\in U_{\beta}$, $\epsilon>0$ small enough as a function of $\beta$,
and $n$ large enough as a function of $\beta,\epsilon$. Let
$\mathcal{A}:=\\{(x,y)\in\Gamma_{p^{*},\epsilon}\times\Gamma_{p^{*},\epsilon}:x\preceq
y\\}$. Let $X^{\prime},Y^{\prime}$ be obtained from $x,y$ via one step of the
Glauber dynamics under the monotone coupling. There is a constant
$c(\beta,\epsilon)>0$ such that if $(x,y)\in\mathcal{A}$, then

$\mathbb{E}d_{H}(X^{\prime},Y^{\prime})\leq\Big{(}1-\frac{c(\beta,\epsilon)}{n^{2}}\Big{)}d_{H}(x,y)\,,$

and moreover, $X^{\prime}\preceq Y^{\prime}$ almost surely.

###  4.3 Key Theorem

We first recall Theorem 1.3 which state that $\cup_{p^{*}\in
U_{\beta}}B^{\square}_{\eta}(p^{*})$ has probability $1-\exp(-\Omega(n^{2}))$
under the measure $\mu$, that is, most of the mass of $\mu$ is concentrated in
the cut-metric balls $B^{\square}_{\eta}(p^{*})$. The following theorem shows
that $\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$ concentrates
over the set $\Gamma_{p^{*},\epsilon}$, where path coupling is possible (as
per Lemma 4.4).

######  Theorem 4.5.

Suppose $p^{*}\in U_{\beta}$. Given $\epsilon>0$, we can pick
$\eta<c(\beta,\epsilon)$ such that

$\mu\big{(}\Gamma_{p^{*},\epsilon}\big{|}B^{\square}_{\eta}(p^{*})\big{)}\geq
1-C(\eta,\epsilon,\beta)\exp\big{(}-\Omega_{\beta,\epsilon,\eta}(n)\big{)}\,.$

We prove the theorem in Section 6, modulo lemmas proved via the cavity method
in Section 8.

######  Remark 4.6.

Notice that $r_{G}(X,e)\in[p^{*}-\epsilon,p^{*}+\epsilon]$ uniformly for every
$e$ is not implied by $\delta_{\square}(\tilde{X},p^{*})<\eta$ (for any
constant $\eta>0$). An example is given in Theorem 3.3, where metastability
occurs despite being close to the $p^{*}$ graphon with high probability: The
edges emanating from a single vertex prevent uniform concentration of
$r_{G}(X,e)$ in the set $[p^{*}-\epsilon,p^{*}+\epsilon]$, but the single
vertex neighborhood has a vanishingly small impact on
$\delta_{\square}(\tilde{X},p^{*})$.

While it can easily be proved directly, the following is also a corollary of
the above theorem.

######  Corollary 4.7.

Fix any $\epsilon>0$. Then there exists $\delta_{0}(\epsilon)>0$ such that for
all $0<\delta<\delta_{0}(\epsilon)$, if $Z\sim G(n,p^{*}+\delta)$, then
$\mathbb{P}(Z\in\Gamma_{p^{*},\epsilon})\geq 1-\exp(\Omega_{\epsilon}(n))$.

###  4.4 Metastability

We intend to invoke Lemma 4.1 to show approximate mixing and prove Theorem
3.1. The prior subsection shows that $G(n,p^{*})$ and at
$\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$ are both within the
set $\Gamma_{p^{*},\epsilon}$ with high probability. We show that the Glauber
chains with these initializations do not leave $\Gamma_{p^{*},\epsilon}$ with
probability $1-\exp(-\Omega(n))$ until time $\exp(\Omega(n))$. Some intuition
behind this was given in Section 2.2.

We next state Lemma 17 from [1], after adapting it to our situation.

######  Lemma 4.8 (Staying in $\Gamma_{p^{*},\epsilon}$).

Let $\epsilon>0$ be a small enough constant independent of $n$ and suppose
$p^{*}\in U_{\beta}$. Let $X_{0},X_{1},\dots$ evolve according Glauber
dynamics with respect to the measure $\mu$. If
$X_{0}\in\Gamma_{p^{*},\epsilon}$, then for some
$\alpha=\alpha(\beta,\epsilon,L)$, we have

$\mathbb{P}\big{(}X_{t}\in\Gamma_{p^{*},2\epsilon}\text{ for all }t\leq
e^{\alpha n}\big{)}\geq 1-\exp\big{(}-\Omega_{\beta,L,\epsilon}(n)\big{)}\,.$

The proofs of the following lemmas are given in Appendix C.

######  Lemma 4.9 ($G(n,p^{*}\pm\epsilon)$ sandwich).

Let $p^{*}\in U_{\beta}$. Let constants $\epsilon,\eta>0$ be such that
$\epsilon<\epsilon_{0}(\beta)$, $\eta<\eta_{0}(\beta,\epsilon)$, and
$n>n_{0}(\beta,\epsilon,\eta)$. Let
$X\sim\mu(\cdot|B^{\square}_{\eta}(p^{*}))$, $\bar{Y}\sim
G(n,p^{*}+\epsilon)$, and $\underline{Y}\sim G(n,p^{*}-\epsilon)$. Then, there
exists a coupling between $X,\bar{Y}$, and $\underline{Y}$ such that with
probability at least $1-\exp(-\Omega_{\beta,\eta,\epsilon}(n))$

$\underline{Y}\preceq X\preceq\bar{Y}\,.$

######  Lemma 4.10 (Staying in $B^{\square}_{\eta/{2}}(p^{*})$).

Suppose $p^{*}\in U_{\beta}$, $\eta>0$ such that $\eta<\eta_{0}(\beta)$ and
$n>n_{0}(\eta,\beta)$. Let $X_{0}\sim G(n,p^{*})$ and generate the trajectory
$X_{0},\dots,X_{T}$ via Glauber dynamics with respect to $\mu$. The entire
trajectory $X_{0},\dots,X_{T}$ stays within the ball
$B^{\square}_{\eta/{2}}(p^{*})$ with probability at least
$1-TC(\beta,\eta)\exp(-c(\beta,\eta)n)$.

##  5 Proof of Main Result, Theorem 3.1

We now show how the main theorem follows from the various lemmas stated in the
last section. Recall that $\pi_{0}:=G(n,p^{*})$,
$\bar{X}_{0}\sim\pi_{0},\bar{X}_{1},\bar{X}_{2},\dots,$ is a trajectory of the
Markov chain $P_{\eta}$ and $X_{0}\sim\pi_{0},X_{1},X_{2},\dots$ is a
trajectory of the Markov chain $P$.

###  5.1 Proof of Theorem 3.1, Part 1

We will couple the trajectories $\bar{X}_{0},\dots,\bar{X}_{T}$ and
$X_{0},\dots,X_{T}$ such that the event
$E:=\\{(\bar{X}_{0},\bar{X}_{1},\dots,\bar{X}_{T})\neq(X_{0},\dots,X_{T})\\}$
satisfies
$E\subseteq\cup_{t=0}^{T}\big{\\{}X_{t}\in\big{(}B^{\square}_{\eta/{2}}(p^{*})\big{)}^{\complement}\big{\\}}$.
We can then conclude the result from Lemma 4.10. The main observation is that
whenever $n$ is large enough as a function of $\eta$, if $X\in
B^{\square}_{\eta/{2}}(p^{*})$, then $P_{\eta}(X,\cdot)=P(X,\cdot)$. We
construct the following coupling:

  1. 1.

$X_{0}=\bar{X}_{0}$ almost surely.

  2. 2.

$X_{t+1},\bar{X}_{t+1}$ are drawn from the TV optimal coupling between
$P(X_{t},\cdot)$ and $P_{\eta}(\bar{X}_{t},\cdot)$.

It is clear that
$\\{X_{t+1}\neq\bar{X}_{t+1}\\}\subseteq\\{X_{t}\neq\bar{X}_{t}\\}\cup\big{\\{}X_{t}\in\big{(}B^{\square}_{\eta/{2}}(p^{*})\big{)}^{\complement}\big{\\}}$.
Now, noting that $\\{X_{0}\neq\bar{X}_{0}\\}$ is the empty event, we conclude
that
$\\{X_{1}\neq\bar{X}_{1}\\}\subseteq\bigr{\\{}X_{0}\in\big{(}B^{\square}_{\eta/{2}}(p^{*})\big{)}^{\complement}\bigr{\\}}$.
An induction argument with the same basic step shows that
$E\subseteq\cup_{t=0}^{T}\bigr{\\{}X_{t}\in\big{(}B^{\square}_{\eta/{2}}(p^{*})\big{)}^{\complement}\bigr{\\}}$.
∎

###  5.2 Proof of Theorem 3.1, Part 2

Let $\bar{Y}_{0}\sim\mu\left(\cdot\bigr{|}B^{\square}_{\eta}(p^{*})\right)$
and consider the trajectory $\bar{Y}_{0},\bar{Y}_{1},\dots,\bar{Y}_{T}$ with
respect to the transition kernel $P_{\eta}$. Similarly, let
$Y_{0}\sim\mu\left(\cdot\bigr{|}B^{\square}_{\eta}(p^{*})\right)$, but with
the trajectory $Y_{1},\dots,Y_{T}$ generated with respect to the transition
kernel $P$. Using Lemma 7.1 to bound $\mathbb{P}(\bar{Y}_{t}\in
B^{\square}_{\eta}(p^{*}))$, a similar proof as in Item 1 shows that

$d_{\mathsf{TV}}\big{(}(\bar{Y}_{0},\dots,\bar{Y}_{T}),(Y_{0},\dots,Y_{T})\big{)}\leq
T\exp\big{(}-\Omega_{\beta,\eta}(n^{2})\big{)}\,.$ (12)

From Item 1, we have

$d_{\mathsf{TV}}((\bar{X}_{0},\dots,\bar{X}_{T}),(X_{0},\dots,X_{T}))\leq
T\exp(-\Omega_{\beta,\eta}(n))\,.$ (13)

These last two displays allow us to consider the total variation distance
between the distributions of $X_{T}$ and $Y_{T}$ instead of $\bar{X}_{T}$ and
$\bar{Y}_{T}$. Let $\epsilon>0$ be small enough to satisfy the conditions in
Lemma 4.8. By Lemma 4.9 and Theorem 4.5, we conclude that for some
$0<\delta<\delta_{0}(\beta,\epsilon,\eta)$,
$\eta<\eta_{0}(\delta,\epsilon,\beta)$, and
$n>n_{0}(\delta,\beta,\eta,\epsilon)$, we can couple $Z_{0}\sim
G(n,p^{*}+\delta)$ with $X_{0}$ and $Y_{0}$ such that with probability at
least $1-\exp(-\Omega_{\beta,\delta,\eta,\epsilon}(n))$, the following hold:

  1. 1.

$X_{0}\preceq Z_{0}$ and $Y_{0}\preceq Z_{0}$, and

  2. 2.

$X_{0},Y_{0},Z_{0}\in\Gamma_{p^{*},\epsilon}$ .

Now, we consider the Markov chain $Z_{0},Z_{1},\dots,Z_{T}$ with respect to
$P$. We consider the monotone coupling between $Y_{0},\dots,Y_{T}$ and
$Z_{0},\dots,Z_{T}$ as in Definition 4.3: conditional on $Y_{0}\preceq Z_{0}$,
we have $Y_{t}\preceq Z_{t}$ almost surely for every $t\leq T$. Recall
$\Gamma_{p^{*},\epsilon}$ from (11) and the set
$\mathcal{A}:=\\{(x,y)\in\Gamma_{p^{*},\epsilon}\times\Gamma_{p^{*},\epsilon}:x\preceq
y\\}$ defined in Lemma 4.4. Now, $(Y_{t},Z_{t})\in\mathcal{A}^{\complement}$
implies either $Y_{0}\not\preceq Z_{0}$,
$Y_{t}\not\in\Gamma_{p^{*},\epsilon}$, or
$Z_{t}\not\in\Gamma_{p^{*},\epsilon}$. The first of these is ruled out by
monotonicity of the coupling. For the latter two, Lemma 4.8 shows that
starting in $\Gamma_{p^{*},\epsilon}$ the trajectory stays there for some
time, and it follows that

$\mathbb{P}\big{(}(Y_{t},Z_{t})\in\mathcal{A}^{\complement}\big{)}\leq\exp\big{(}-\Omega_{\beta,\delta,\epsilon,\eta}(n)\big{)}\,.$

Applying Lemmas 4.1 and 4.4 with Hamming distance $d_{H}$ over $\Omega$, we
conclude that whenever $T\leq\exp(c_{0}n)$ for small enough $c_{0}$ as a
function of $\epsilon,\delta,\eta,\beta$

$\mathbb{E}d(Y_{T},Z_{T})\leq\frac{n^{2}}{2}\left[\Big{(}1-\frac{c(\epsilon,\beta)}{n^{2}}\Big{)}^{T}+\frac{n^{2}}{c(\epsilon,\beta)}\exp(-\Omega_{\eta,\beta,\epsilon,\delta}(n))\right]\,.$

Similarly, we have

$\mathbb{E}d(X_{T},Z_{T})\leq\frac{n^{2}}{2}\left[\Big{(}1-\frac{c(\epsilon,\beta)}{n^{2}}\Big{)}^{T}+\frac{n^{2}}{c(\epsilon,\beta)}\exp(-\Omega_{\eta,\beta,\epsilon,\delta}(n))\right]\,.$

Combining the two displays above, the coupling characterization of TV distance
implies

$\displaystyle d_{\mathsf{TV}}(X_{T},Y_{T})$
$\displaystyle\leq\mathbb{P}(X_{T}\neq Y_{T})\leq\mathbb{P}(X_{T}\neq
Z_{T})+\mathbb{P}(Z_{T}\neq Y_{T})$
$\displaystyle\leq\mathbb{P}(d(X_{T},Z_{T})>1)+\mathbb{P}(d(Y_{T},Z_{T})>1)$
$\displaystyle\leq\mathbb{E}d(X_{T},Z_{T})+\mathbb{E}d(Y_{T},Z_{T})$
$\displaystyle\leq
n^{2}\left[\Big{(}1-\frac{c(\epsilon,\beta)}{n^{2}}\Big{)}^{T}+\frac{n^{2}}{c(\epsilon,\beta)}\exp\big{(}-\Omega_{\eta,\beta,\epsilon,\delta}(n)\big{)}\right]\,.$
(14)

Now, we will allow $\epsilon,\delta$ to be small enough constants as a
function of $\beta$ such that Lemmas 4.8 and 4.4 hold. Whenever $\eta$ is
small enough as a function $\beta$ and $n$ is large enough, combining
Equations (12), (13), and (14), yields

$d_{\mathsf{TV}}(\bar{X}_{T},\bar{Y}_{T})\leq
n^{2}\left[\Big{(}1-\frac{c(\epsilon,\beta)}{n^{2}}\Big{)}^{T}+\frac{n^{2}T}{c(\epsilon,\beta)}\exp\big{(}-\Omega_{\eta,\beta}(n)\big{)}\right]\,.$

This yields the second part of the theorem statement by considering
$T=C_{\beta,\eta}n^{2}\log(n^{2}/\delta)$. ∎

###  5.3 Proof of Theorem 3.1, Part 3

Whenever $|U_{\beta}|=1$, the concentration result of [6] (stated here as
Theorem 1.3) implies that

$d_{\mathsf{TV}}\big{(}\mu,\mu\big{(}\cdot|B^{\square}_{\eta}(p^{*})\big{)}\big{)}\leq\exp\big{(}-\Omega_{\beta,\eta}(n^{2})\big{)}\,.$

Meta-stable mixing to $\mu$ follows from the second part and the triangle
inequality. ∎

##  6 Uniform Subgraph Concentration and Proof of Theorem 4.5

In this section we reduce the proof of Theorem 4.5 on the concentration of
$\Delta^{e}_{G}(X):=N_{G}(X^{+e})-N_{G}(X^{-e})$ to control of both the vertex
degrees $p_{u}(X)$ and common neighbors $p_{uv}(X)$. The latter are stated
here as corollaries and will be proved via the cavity method in Section 8.

Theorem 4.5 states that if we sample
$X\sim\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$, then
$X\in\Gamma_{p^{*},\epsilon}$ with probability
$1-C(\beta,\epsilon,\eta)\exp\big{(}-\Omega_{\beta,\epsilon,\eta}(n)\big{)}$.
Unpacking the definitions, it suffices to show that for some small enough
$h(\epsilon,L)$,

$\Big{|}\Delta^{e}_{G}(X)-\frac{2|E(G)|(p^{*})^{|E(G)|-1}|}{n^{2}}\Big{|}\leq\frac{h(\epsilon,L)}{n^{2}}$
(15)

for every $G\in\mathbb{G}_{L}$ and $e\in{{[n]}\choose{2}}$, with probability
at least $1-C(\beta,\eta,\epsilon,L)\exp(-\Omega_{\beta,\eta,\epsilon,L}(n))$.

We start with a lemma (proved in Appendix A) which shows that (15) (and hence
Theorem 4.5) follows from uniform control of both the vertex degrees
$p_{u}(X)$ and common neighbors $p_{uv}(X)$. Some notation is needed. Given a
fixed graph $G=([k],E)$ and vertices $i,j\in[k]$ such that $(i,j)\in E$, let

$E_{ij}(G):=\big{\\{}l:l\in[k],l\neq i,l\neq j,(l,i)\in E,(l,j)\in
E\big{\\}}\quad\text{and}\quad d_{ij}(G)=|E_{ij}(G)|\,.$ (16)

In words, $d_{ij}(G)$ is the number of common neighbors of vertices $i$ and
$j$ in $G$.

######  Lemma 6.1.

Suppose $X\in\Omega$, $e=(u,v)$, and $p^{*}\in[0,1]$ are such that
$\sup_{u\in[n]}|p_{u}(X)-p^{*}|\leq\epsilon$. For any fixed graph $G$ and for
some constant $C_{G}$ depending only on $G$, we have

$\Big{|}\Delta^{e}_{G}(X)-\frac{2}{n^{2}}\sum_{(i,j)\in
E(G)}\Big{(}\frac{p_{uv}(X)}{(p^{*})^{2}}\Big{)}^{d_{ij}}(p^{*})^{|E(G)|-1}\Big{|}\leq\frac{C_{G}}{n^{2}}\left(\epsilon+\delta_{\square}(\tilde{X},p^{*})+n^{-1}\right)\,.$

######  Corollary 6.2.

Let $C(L)=\max_{G\in\mathbb{G}_{L}}C_{G}$ for $C_{G}$ in Lemma 6.1 and
$h(\epsilon,L)$ be as in (15). Let $a(\epsilon,L)=h(\epsilon,L)/3C(L)$. Then
$X\in\Gamma_{p^{*},\epsilon}$ holds if

  1. 1.

$X$ is $a(\epsilon,L)$-close to the constant graphon $p^{*}$ in the cut-
metric,

  2. 2.

$p_{u}(X)$ is uniformly close to $p^{*}$ for every vertex $u$, i.e.,
$\sup_{u}|p_{u}(X)-p^{*}|\leq a(\epsilon,L)$, and

  3. 3.

$p_{uv}(X)$ is close to $(p^{*})^{2}$ uniformly for every pair of vertices
$u\neq v$, i.e.,

$\sup_{\begin{subarray}{c}u\neq v\end{subarray}}|p_{uv}(X)-(p^{*})^{2}|\leq
p^{*}a(\epsilon,L)/3L\,.$ (17)

It follows that Theorem 4.5 is proved if these conditions are each shown to
hold for $X\sim\mu(\cdot|B^{\square}_{\eta}(p^{*}))$ with probability at least
$1-C(\beta,\epsilon,\eta,L)\exp(-\Omega_{\beta,\epsilon,\eta,L}(n))$

Item 1 holds by Theorem 1.3. We address Items 2 and 3 below.

###  6.1 Uniform Control of Degrees

Section 8 develops the cavity method for the $\mathsf{ERGM}$ and demonstrates
the following uniform control on vertex degrees.

######  Corollary 8.10.

Suppose $p^{*}\in U_{\beta}$ and let $\epsilon>0$ be an arbitrary fixed
constant. Then, we can take $0<\eta<c(\beta,\epsilon)$ and
$n>n_{0}(\beta,\epsilon,\eta)$ such that

$\mu\Big{(}\sup_{u\in[n]}|p_{u}(X)-p^{*}|\leq\epsilon\,\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}\geq
1-\exp(-\Omega_{\beta,\epsilon}(n))\,.$

We take $\eta<c(\beta,a(\epsilon,L)$ in Corollary 8.10, implying that if we
sample $X\sim\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$ then Item
2 of Corollary 6.2 holds with probability
$1-C(\beta,\epsilon,\eta,L)\exp(-\Omega_{\beta,\epsilon,\eta,L}(n))$.

It remains to show Item 3 of Corollary 6.2. As a step towards this, it turns
out that if $p_{u}(X)$ is close to $p^{*}$ uniformly for _every_ vertex $u$
(as stated in Corollary 8.10) and $X$ is close to the constant graphon
$p^{*}$, then _most_ of the common neighbor counts $p_{uv}(X)$ are close to
$(p^{*})^{2}$. This follows from the definition of cut-metric.

######  Corollary 8.11.

Suppose that $p^{*}\in U_{\beta}$. Given arbitrary $\epsilon,\delta>0$,
suppose $\eta<c(\beta,\epsilon,\delta)$ and
$n>n_{0}(\delta,\epsilon,\beta,\eta)$. Then, for every $u\in[n]$, there exists
a random set $S_{u}\subseteq[n]\setminus\\{u\\}$ such that $|S_{u}|\leq\delta
n$ and

$\mu\Big{(}\sup_{u\in[n]}\sup_{v\in
S^{\complement}_{u}}|p_{uv}(X)-(p^{*})^{2}|\leq\epsilon\,\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}\geq
1-\exp(-\Omega_{\beta,\epsilon}(n))\,.$

We refer to Appendix D.1 for the proof.

Next, to establish Equation (17), we boost control of $p_{uv}(X)$ from most
pairs $u,v$ to all pairs.

###  6.2 Uniform Control of Common Neighbors

Let $X^{\prime}$ be obtained from
$X\sim\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$ via one step of
the Glauber dynamics with respect to
$\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$, so that we also have
$X^{\prime}\sim\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$. As
shown in Lemma 7.1, with high probability $X$ is $\eta/2$ away from the
boundary of $B^{\square}_{\eta}(p^{*})$ and the expected Glauber update for
$p_{uv}$ with respect to
$\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$ is the same as with
respect to $\mu(\cdot)$, which is

$\displaystyle\mathbb{E}\left[p_{uv}(X^{\prime})\big{|}X\right]$
$\displaystyle\quad=\Big{(}1-\frac{2}{N}\Big{)}p_{uv}(X)+\frac{1}{N}\Big{(}n^{-1}\sum_{w\in[n]\setminus\\{u,v\\}}\phi_{uw}(X_{\sim
uw})X_{vw}+n^{-1}\sum_{w\in[n]\setminus\\{u,v\\}}\phi_{vw}(X_{\sim
vw})X_{uw}\Big{)}\,.$

The next lemma shows that under the conditions shown in Corollaries 8.10 and
8.11 to hold with high probability for
$X\sim\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$, each of the
normalized sums in the last displayed equation is close to $(p^{*})^{2}$
uniformly for every $u\neq v$. The Glauber dynamics with respect to
$\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$, therefore, tries to
regress every $p_{uv}(X)$ close to $(p^{*})^{2}$.

######  Lemma 6.3.

Suppose $X\in\Omega$, $p^{*}\in[0,1]$ are such that the following conditions
hold:

  1. 1.

$\sup_{u\in[n]}|p_{u}(X)-p^{*}|\leq\epsilon$, and

  2. 2.

For every $u\in[n]$, there exist sets $S_{u}\subseteq[n]$ such that
$|S_{u}|\leq\delta n$ and

$\sup_{u\in[n]}\sup_{w\in
S^{\complement}_{u}}|p_{uw}(X)-(p^{*})^{2}|\leq\epsilon\,.$

Then, for every $u,v\in[n]$, we have

$\Big{|}n^{-1}\sum_{w\in[n]\setminus\\{u,v\\}}\phi_{uw}(X_{\sim
uw})X_{vw}-(p^{*})^{2}\Big{|}\leq
C_{\beta}\left(\epsilon+\delta+\delta_{\square}(X,p^{*})+n^{-1}\right)\,.$

The lemma is proved in the next subsection.

Intuitively, this suggests that the stationary distribution of the Glauber
dynamics, $\mu\big{(}\cdot\big{|}B^{\square}_{\eta}(p^{*})\big{)}$, should be
such that $p_{uv}(X)\approx(p^{*})^{2}$ for every $u\neq v$ with high
probability. The next lemma formalizes this sentiment using Stein’s method for
concentration developed in [5, Theorem 1.5].

######  Lemma 6.4.

For any $u,v\in[n]$ such that $u\neq v$, define

$g_{uv}(X):=p_{uv}(X)-\frac{1}{2n}\sum_{w\in[n]\setminus\\{u,v\\}}\Big{(}\phi_{uw}(X_{\sim
uw})X_{vw}+\phi_{vw}(X_{\sim vw})X_{uw}\Big{)}\,.$

Then, for any $\gamma>0$ which is independent of $n$, we have

$\mu\Big{(}\\{|g_{uv}(X)|>\gamma\\}\cup(B^{\square}_{\eta/2}(p^{*}))^{\complement}\,\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}\leq
C(\eta,\beta)\exp(-\Omega_{\gamma,\eta,\beta}(n))\,.$ (18)

######  Corollary 6.5.

Item 3 of Corollary 6.2 holds with the desired probability.

###### Proof.

Combining the last two lemmas with Corollary 8.10 proves (17). ∎

###  6.3 Proof of Lemma 6.3

First, note that by definition

$\phi_{uw}(X_{\sim
uw})=\frac{\exp(\sum_{i=0}^{K}n^{2}\beta_{i}\Delta^{uw}_{i}(X))}{1+\exp(\sum_{i=0}^{K}n^{2}\beta_{i}\Delta^{uw}_{i}(X))}\,.$

Now, suppose $w\in S^{\complement}_{u}$. Then, using Lemma 6.1, we conclude
that

$\sum_{i=0}^{K}n^{2}\beta_{i}\Delta^{uw}_{i}(X)=\sum_{i=0}^{K}2|E_{i}|\beta_{i}(p^{*})^{|E_{i}|-1}\pm
O_{\beta}\left(\epsilon+\delta_{\square}(X,p^{*})+{n^{-1}}\right)\,.$

Using the fact that the function $x\to\frac{e^{x}}{1+e^{x}}$ is $1$-Lipschitz,
we have for $w\in S^{\complement}_{u}$ that

$\phi_{uw}(X_{\sim
uw})=\frac{\exp(\sum_{i=0}^{K}2|E_{i}|\beta_{i}(p^{*})^{|E_{i}|-1})}{1+\exp(\sum_{i=0}^{K}2|E_{i}|\beta_{i}(p^{*})^{|E_{i}|-1})}\pm
O_{\beta}\left(\epsilon+\delta_{\square}(X,p^{*})+n^{-1}\right)\,.$

Now, the fact that $p^{*}\in U_{\beta}$ implies that
$L_{\beta}^{\prime}(p^{*})=0$. It can be easily checked that this implies
$p^{*}=\phi_{\beta}(p^{*})$. It follows that whenever $w\in
S^{\complement}_{u}$,

$\phi_{uw}(X_{\sim uw})=p^{*}\pm
O_{\beta}\left(\epsilon+\delta_{\square}(X,p^{*})+n^{-1}\right)\,.$

An application of the triangle inequality now shows that

$\Big{|}n^{-1}\sum_{\begin{subarray}{c}w\in[n]\setminus\\{u,v\\}\end{subarray}}\phi_{uw}(X_{\sim
uw})X_{vw}-p^{*}p_{v}(X)\Big{|}\leq\frac{|S_{u}|}{n}+O_{\beta}\left(\epsilon+\delta_{\square}(X,p^{*})+n^{-1}\right)\,.$

The assumption that $|S_{u}|\leq\delta n$ and the fact that
$|p_{v}(X)-p^{*}|\leq\epsilon$ imply the result. ∎

##  7 Some Graphon Estimates

In this section, we state several technical results that will be needed later.
Results from other works are stated without proof and otherwise the proofs are
given in the appendix.

Even though Theorem 3.2 in [6] considers the probability over the entire space
of graphons, we can easily adapt its proof to show the following lemma which
considers only the neighborhood $B^{\square}_{\eta+\delta}(p^{*})$ for
$p^{*}\in U_{\beta}$.

######  Lemma 7.1.

Suppose $p^{*}\in U_{\beta}$. Then, there exists a constant $c_{\beta}>0$ such
that whenever $\eta,\delta\in(0,c_{\beta})$ are fixed constants independent of
$n$, we have

$\frac{\mu(\eta\leq\delta_{\square}(X,p^{*})\leq\eta+\delta)}{\mu(\delta_{\square}(X,p^{*})\leq\eta)}\leq
C(\eta,\delta)\exp(-c(\eta,\delta)n^{2})\,.$

We state three technical lemmas below, whose proofs appear in Appendix A.

######  Lemma 7.2.

For any graph $X$ over $n$ vertices, $p\in[0,1]$, and $\delta>0$, there exists
a set $S\subseteq[n]$ such that $|S|\leq\delta n$ and

$\sup_{u\in
S^{\complement}}|p_{u}(X)-p|\leq\frac{2\delta_{\square}(\tilde{X},p\mathbf{1})}{\delta}\,.$
(19)

It follows as an application that for $X\sim\mathsf{ERGM}(n,\beta)$ and any
given fixed constants $\delta,\eta>0$, with probability at-least
$1-C(\eta)\exp(-c(\eta)n^{2})$, there exists a (random) set $S\subseteq[n]$
such that $|S|\leq\delta n$ and

$\inf_{p^{*}\in U_{\beta}}\sup_{u\in
S^{\complement}}|p_{u}(X)-p^{*}|\leq\frac{2\eta}{\delta}\,.$

######  Lemma 7.3.

If $Y\preceq X\preceq Z$, then
$\delta_{\square}(\tilde{X},p\mathbf{1})\leq\max\big{(}\delta_{\square}(\tilde{Y},p\mathbf{1}),\delta_{\square}(\tilde{Z},p\mathbf{1})\big{)}$.

######  Lemma 7.4.

Consider any fixed graph $G=(V,E)$. For any vertex $i$, let $d_{i}$ denote the
degree of the vertex $i$. Suppose $p,q\in[0,1]$. If $G=G_{0}$, the graph
consisting of a single edge, then

$\sum_{i=1}^{|V|}q^{d_{i}}p^{|E|-d_{i}}=2q^{|E|}+(|V|-2)p^{|E|}\,.$ (20)

If $G$ is connected and $G\neq G_{0}$, then there is a constant $C$ depending
only on $(d_{i})_{i\in V}$ and $|E|$ such that

$\displaystyle 2q^{|E|}+(|V|-2)p^{|E|}-C|p-q|$
$\displaystyle\qquad\qquad\leq\sum_{i=1}^{|V|}q^{d_{i}}p^{E-d_{i}}\leq
2q^{|E|}+(|V|-2)p^{|E|}-\zeta(|p-q|)\,,$

where $\zeta:[0,1]\to\mathbb{R}^{+}$ is a continuous function depending only
on $G$ such that $\zeta(x)>0$ for $x\neq 0$.

##  8 The Cavity Method

In this section we address the degrees and show that every vertex $u$ has
nearly the same degree $p_{u}(X)\approx p^{*}\in U_{\beta}$ with high
probability for $X\sim\mu(\cdot|B^{\square}_{\eta}(p^{*}))$. While the cut-
metric based convergence does not allow us to control all the degrees, it is
nevertheless possible to conclude that a large portion of the vertices have
degree $p_{u}(X)\approx p^{*}$. We boost this to a uniform statement, in
Theorem 8.9 and Corollary 8.10, via the _cavity method_ : most of the vertices
and the corresponding edges are conditioned on being close to the constant
graphon $p^{*}\mathbf{1}$, which generates the _mean field_ with which the
remaining cavity vertices interact. We can then reason about the behavior of
the cavity vertices.

We start by adapting several of the graphon definitions to incorporate a
cavity.

###  8.1 Restricted Homomorphism Densities and Restricted Cut Metric

Recall from Section 2.1 the function representative $f^{X}(x,y)$ of a graph
$X$ over $n$ vertices. We will need the homomorphism density of a graph forced
to contain a particular vertex $u$ of $X$. To that end, for every $u\in[n]$,
define the event

$A^{k,i}_{u}:=\Big{\\{}x\in[0,1]^{k}:x_{i}\in\Big{[}\frac{u-1}{n},\frac{u}{n}\Big{)}\Big{\\}}$

and

$A^{k}_{u}=\Big{\\{}x\in[0,1]^{k}:x_{i}\in\Big{[}\frac{u-1}{n},\frac{u}{n}\Big{)}\text{
for some }i\in[k]\Big{\\}}=\bigcup_{i\in[k]}A^{k,i}_{u}\,.$ (21)

For the sake of clarity in the results below, given a fixed graph $G$, we take
its vertex set $V(G)=[k]$ during calculations.

######  Definition 8.1 (Homomorphism density w.r.t. a vertex).

Define the homomorphism density of $G$ in $X$ with respect to vertex $u$
(which counts only homomorphisms which include the vertex $u$) as

$N_{G}(X;u):=\int_{[0,1]^{k}}\mathbbm{1}(A^{k}_{u})\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}\,.$ (22)

For ease of computation, we also introduce the quantity

$N^{0}_{G}(X;u):=\sum_{l=1}^{k}\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}\,.$ (23)

The next lemma follows from elementary arguments; see Appendix A.

######  Lemma 8.2.

$0\leq N_{G}^{0}(X,u)-N_{G}(X,u)\leq{|V(G)|^{3}}/{n^{2}}$.

We will now show that whenever the graphon corresponding to $X$ is close to a
constant graphon $p\mathbf{1}$, then $N_{G}(X,u)$ can be approximated as a
polynomial of $p_{u}(X)$ and $p$. This will allow us to control the fine-
grained structure of $X$ in terms of the counts $N_{G}(X,u)$ just based on
nearness to a constant graphon and the normalized degrees of the vertices of
$X$. The proof, given in Appendix A, follows from a slight modification of the
proof technique of [2, Lemma 4.4], which establishes the continuity of
homomorphism densities with respect to the graphon metric via a repeated
application of the triangle inequality.

######  Lemma 8.3.

Suppose $D_{G}=(d_{1},\dots,d_{|V(G)|})$ is the degree sequence of the fixed
graph $G$ considered above. For any graph $X$ with vertex set $[n]$ and
$u\in[n]$, we have

$\Big{|}N_{G}(X;u)-n^{-1}\sum_{d\in
D_{G}}p_{u}(X)^{d}p^{|E(G)|-d}\Big{|}\leq|V(G)||E(G)|\frac{\delta_{\square}(\tilde{X},p)}{n}+\frac{|V(G)|^{3}}{n^{2}}\,.$

Let $S\subset[n]$ be the “cavity set”. Define

$A_{S}^{k}:=\cup_{u\in S}A_{u}^{k}\quad\text{and}\quad A_{S}^{k,i}:=\cup_{u\in
S}A_{u}^{k,i}\,.$

We have that

$\displaystyle N_{G}(X)$
$\displaystyle=N_{G}(X;S)+\int_{[0,1]^{k}}\mathbbm{1}\big{\\{}(A_{S}^{k})^{\complement}\big{\\}}\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}\,,$

where the subgraph count $N_{G}(X;S)$ restricts to subgraphs containing a
cavity vertex,

$N_{G}(X;S):=\int_{[0,1]^{k}}\mathbbm{1}\big{\\{}A_{S}^{k}\big{\\}}\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}\,.$

The proofs of the next two lemmas are deferred to Appendix A.

######  Lemma 8.4.

Let $X$ be any simple graph with vertex set $[n]$ and let $S\subset[n]$ be
arbitrary. Then

$\Big{|}N_{G}(X;S)-\sum_{u\in
S}N_{G}(X;u)\Big{|}\leq\frac{k^{3}|S|^{2}}{n^{2}}\,.$

We now define the graphon metric restricted to $S^{\complement}$.

######  Definition 8.5 (Restricted Graphon Metric).

Let $p^{*}\in[0,1]$. Define

$f^{X,S,p^{*}}(x_{1},x_{2})=\begin{cases}f^{X}(x_{1},x_{2})\text{ if }\lceil
nx_{1}\rceil,\lceil nx_{2}\rceil\in S^{\complement}\\\ p^{*}\text{
otherwise}\,,\end{cases}$ (24)

and let $\tilde{X}^{S,p^{*}}$ be the graphon corresponding to $f^{X,S,p^{*}}$.
We define the restricted cut metric to be

$\delta_{\square}^{S,p^{*}}(\tilde{X},p^{*}):=\delta_{\square}(\tilde{X}^{S,p^{*}},p^{*})\,.$

The restricted graphon distance to $p^{*}$ can be approximated in terms of the
unrestricted distance:

######  Lemma 8.6.

For any $S\subseteq[n]$, we have

$\delta_{\square}(\tilde{X},p^{*})-\frac{|S|(2n-|S|)}{n^{2}}\leq\delta_{\square}^{S,p^{*}}(\tilde{X},p^{*})\leq\delta_{\square}(\tilde{X},p^{*})\,.$

We are now ready to establish the cavity decomposition of the Hamiltonian.

###  8.2 Cavity Decomposition of the Hamiltonian

It will be convenient to let $r:=|S|$. Given a simple graph $X$ over $n$
vertices, we define $\bar{p}_{u}(X)$ to be the number of edges from vertex
$u\in[n]$ to the set $S^{\complement}$, normalized by $n$:

$\bar{p}_{u}(X)=\frac{1}{n}{\sum_{v\in S^{\complement}}X_{uv}}\,.$

Here and throughout we hide the dependence on $S$ to streamline the notation.
Additionally, whenever it is clear, we will denote $\bar{p}_{u}(X)$ by
$\bar{p}_{u}$. Note that $|\bar{p}_{u}(X)-p_{u}(X)|\leq{|S|}/{n}$.

Denote the portion of the Hamiltonian associated to the cavity by

$\mathcal{H}^{\mathsf{cav}}_{\beta}(X;S):=\sum_{i=0}^{K}n^{2}\beta_{i}N_{i}(X;S)\,,$

which is the same as $\mathcal{H}_{\beta}$ except that the homomorphism
densities are restricted to have at least one vertex in the set $S$. Denote
the rest of the Hamiltonian by

$\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)=\mathcal{H}_{\beta}(X)-\mathcal{H}^{\mathsf{cav}}_{\beta}(X;S)\,.$

We next bound the difference between $\mathcal{H}_{\beta}(X)$ and
$\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)$.

######  Lemma 8.7 (Cavity Decomposition).

Assume that $\beta_{i}>0$ for some $i=1,\dots,K$. We have the following upper
and lower bounds.

  1. 1.

Upper Bound:

$\displaystyle\mathcal{H}_{\beta}(X)$
$\displaystyle\leq\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)+O_{\beta}(nr\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})+r^{2})+\sum_{i=0}^{K}\beta_{i}nr|V_{i}|(p^{*})^{|E_{i}|}$
$\displaystyle\qquad+2n\sum_{u\in
S}\Big{[}L_{\beta}(\bar{p}_{u})+I(\bar{p}_{u})-L_{\beta}(p^{*})-I(p^{*})-\zeta_{\beta}(|\bar{p}_{u}-p^{*}|)\Big{]}$
(25)

  2. 2.

Lower Bound:

$\displaystyle\mathcal{H}_{\beta}(X)$
$\displaystyle\geq\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)-O_{\beta}(nr\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})+r^{2})+\sum_{i=0}^{K}\beta_{i}nr|V_{i}|(p^{*})^{|E_{i}|}$
$\displaystyle\qquad+2n\sum_{u\in
S}\Big{[}L_{\beta}(\bar{p}_{u})+I(\bar{p}_{u})-L_{\beta}(p^{*})-I(p^{*})-C_{\beta}|\bar{p}_{u}-p^{*}|\Big{]}$
(26)

Here $\zeta_{\beta}$ is a function with the same properties of the function
$\zeta$ in Lemma 7.4

###### Proof.

Let $D_{i}$ be the tuple of the degrees of vertices in $G_{i}$ (as in Lemma
8.3). In the equations below, we will take $\sum_{d_{i}\in D_{i}}$ to mean
summation over all elements of the tuple. We have

$\displaystyle\mathcal{H}_{\beta}(X)$
$\displaystyle=\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)+\mathcal{H}^{\mathsf{cav}}_{\beta}(X;S)$
$\displaystyle=\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)+\sum_{u\in
S}\sum_{i=0}^{K}\beta_{i}n^{2}N_{i}(X;u)\pm O_{\beta}(r^{2})$
$\displaystyle=\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)+\sum_{u\in
S}\sum_{i=0}^{K}\sum_{d_{i}\in
D_{i}}\beta_{i}np_{u}^{d_{i}}(p^{*})^{E_{i}-d_{i}}\pm
O_{\beta}(nr\delta_{\square}(\tilde{X},p^{*})+r^{2})$
$\displaystyle=\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)+\sum_{u\in
S}\sum_{i=0}^{K}\sum_{d_{i}\in
D_{i}}\beta_{i}n\bar{p}_{u}^{d_{i}}(p^{*})^{E_{i}-d_{i}}\pm
O_{\beta}(nr\delta_{\square}(\tilde{X},p^{*})+r^{2})\,.$ (27)

The first step is by the definition of the cavity Hamiltonian. The second step
uses Lemma 8.4 to approximate $N(G;S)$ and the third step uses Lemma 8.3 to
approximate $N_{i}(X;u)$. In the fourth step, we have used the fact that
$|\bar{p}_{u}-p_{u}|\leq{r}/{n}$.

We now apply Lemma 7.4 to the second term of Equation (27), yielding

$\displaystyle\sum_{i=0}^{K}\sum_{d_{i}\in
D_{i}}\beta_{i}\bar{p}_{u}^{d_{i}}(p^{*})^{E_{i}-d_{i}}\leq\sum_{i=0}^{K}\beta_{i}\Big{[}2\bar{p}_{u}^{|E_{i}|}+(|V_{i}|-2)(p^{*})^{|E_{i}|}\Big{]}-\zeta_{\beta}(|\bar{p}_{u}-p^{*}|)$
$\displaystyle=\sum_{i=0}^{K}\beta_{i}|V_{i}|(p^{*})^{|E_{i}|}+2\Big{[}L_{\beta}(\bar{p}_{u})+I(\bar{p}_{u})-L_{\beta}(p^{*})-I(p^{*})-\zeta_{\beta}(|\bar{p}_{u}-p^{*}|)\Big{]}\,.$
(28)

In the first step we have used Lemma 7.4 and the fact that for $G_{0}$ the
inequality is an equality which allows for all $\beta_{0}\in\mathbb{R}$. For
$i>0$, notice that $\beta_{i}\geq 0$ and the inequality goes in the right
direction. The function $\zeta_{\beta}$ is as defined in the statement of
Lemma 7.4 and exists since $\beta_{i}>0$ for some $i\in[K]$. To see this,
observe that the Equation 20 is an equality when $G=G_{0}$. Therefore, in
order to establish the strict inequality involving $\zeta$ as shown in Lemma
7.4, we need at-least one of the $\beta_{i}>0$.

The upper bound in the lemma statement follows by combining Equations (27) and
(28) along with Lemma 8.6 to show that

$nr\delta_{\square}(\tilde{X},p^{*})\leq
nr\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})+2r^{2}\,.$

The lower bound on the Hamiltonian follows from a similar argument by
replacing the upper bound in Lemma 7.4 with the lower bound. ∎

###  8.3 Controlling Degrees of Cavity Vertices

Given a sequence $\bar{q}_{u}\in\\{0,1/n,2/n,\dots,1\\}$ for $u\in S$, we
define the tuple $\mathbf{q}_{S}=(\bar{q}_{u})_{u\in S}$. Given arbitrary and
fixed $\eta>0$, $p^{*}\in[0,1]$, we define the events

$A(S,\mathbf{q}_{S},p^{*},\eta)=\\{X:\bar{p}_{u}(X)=\bar{q}_{u}\text{ for
}u\in S\\}\cap\\{\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})\leq\eta\\}$ (29)

and

$B(S,p^{*},\eta):=\\{\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})\leq\eta\\}\,.$
(30)

Note that by definition, $B(\emptyset,p^{*},\eta)=B^{\square}_{\eta}(p^{*})$.
We want to show that whenever $p^{*}\in U_{\beta}$, if $\mathbf{q}_{S}$ is not
close to $p^{*}$, then the event $A(S,\mathbf{q}_{S},p^{*},\eta)$ has
exponentially small probability compared to the event $B(S,p^{*},\eta)$,
whenever $\eta$ and $S$ are small enough.

We now note that $\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)$ and
$\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})$ depend only on $X_{uv}$ for
$u,v\in S^{\complement}$. Therefore, whenever $|S|$ is small, we will think of
$\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S)$ as the mean field which controls
the behavior of the cavity, i.e., the edges emanating from the vertices in
$S$. Now, fixing $X$ such that
$\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})\leq\eta$, we look at the joint
law of $(X_{uv})$ such that at least one of $u$ or $v$ is in the set $S$. By
$X_{\mathsf{mean}}(S)$ we denote the coordinates $(X_{uv})_{u,v\in
S^{\complement}}$. We denote the rest of the coordinates by
$X_{\mathsf{cav}}(S)$. Therefore, we want to understand the conditional law
$X_{\mathsf{cav}}(S)|X_{\mathsf{mean}}(S)$ under the measure $\mu$. We first
record the following combinatorial lemma, whose proof can be found in Appendix
A.

######  Lemma 8.8.

Suppose ${r}/{n}\leq{1}/{2}$ and $X_{\mathsf{mean}}(S)$ is fixed. Let the
count of $X_{\mathsf{cav}}(S)$ such that $\bar{p}_{u}(X)=q_{u}$ for $u\in S$
be denoted by $H_{\mathsf{cav}}(\mathbf{q}_{S})$.
$H_{\mathsf{cav}}(\mathbf{q}_{S})$ satisfies

$\exp\left(-r^{2}\left[4+2\log(\tfrac{n}{r})\right]-\frac{r}{2}\log(2n)\right)\leq
H_{\mathsf{cav}}(\mathbf{q}_{S})\exp\Big{(}2n\sum_{u\in S}I(q_{u})\Big{)}\leq
1\,.$

Below we present the main result of this section.

######  Theorem 8.9.

Let $p^{*}\in U_{\beta}$ be such that ${r}/{n}<p^{*}<1-{r}/{n}$ and
$r<{n}/{2}$. Given any $\mathbf{q}_{S}=(\bar{q}_{u})_{u\in S}$ as defined
above for $n$ sufficiently large as a function of $\beta,\eta$, we have

$\displaystyle\frac{\mu(A(S,\mathbf{q}_{S},p^{*},\eta))}{\mu(B(S,p^{*},\eta))}\leq\exp\bigg{(}2n\sum_{u\in
S}\Big{(}L_{\beta}(\bar{q}_{u})-L_{\beta}(p^{*})-\zeta_{\beta}(|\bar{q}_{u}-p^{*}|)\Big{)}+\text{lower
order}\bigg{)}\,,$

where $\text{lower order}=O_{\beta}(nr\eta+r^{2}\log({n}/{r})+r\log n)$.

###### Proof.

Fix a $p^{*}\in U_{\beta}$. For the sake of convenience, only in this proof,
we will denote $A(S,\mathbf{q}_{S},p^{*},\eta)$ by $A$, $B(S,p^{*},\eta)$ by
$B$ and $O_{\beta}$ by $O$. Let $C$ be the event
$\\{X:\bar{p}_{u}(X)=\bar{q}_{u}\text{ for }u\in S\\}$. Let $n$ be large
enough so that the sets $A,B$ and $C$ are non-empty. Note that
$\mathbbm{1}\\{X\in B\\}$ is a function of $X_{\mathsf{mean}}$ and
$\mathbbm{1}\\{X\in C\\}$ is a function of $X_{\mathsf{cav}}$. Therefore we
write $X_{\mathsf{mean}}\in B$ and $X_{\mathsf{cav}}\in C$ in place of $X\in
B$ and $X\in C$, respectively.

With this notation in place, we have

$\displaystyle\mu(A)=\frac{1}{Z_{\beta}}\sum_{X_{\mathsf{cav}}\in
C}\sum_{X_{\mathsf{mean}}\in B}\exp(\mathcal{H}_{\beta}(X))$
$\displaystyle\leq\frac{1}{Z_{\beta}}\sum_{X_{\mathsf{cav}}\in
C}\sum_{X_{\mathsf{mean}}\in
B}\exp(\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S))\exp\left(O(nr\eta+r^{2})+\Gamma(p^{*})+\bar{\Delta}(\mathbf{q}_{S},p^{*})\right)$
$\displaystyle=\frac{H_{\mathsf{cav}}(\mathbf{q}_{S})}{Z_{\beta}}\sum_{X_{\mathsf{mean}}\in
B}\exp(\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S))\exp\left(O(nr\eta+r^{2})+\Gamma(p^{*})+\bar{\Delta}(\mathbf{q}_{S},p^{*})\right)$
$\displaystyle\leq\frac{Z^{\mathsf{mean}}_{\beta}}{Z_{\beta}}\exp\Big{(}O(nr\eta+r^{2})+2n\sum_{u\in
S}\Big{[}L_{\beta}(\bar{q}_{u})-L_{\beta}(p^{*})-\zeta_{\beta}(|\bar{q}_{u}-p^{*}|)\Big{]}\Big{)}\,,$
(31)

where

$\Gamma(p^{*}):=\sum_{i=0}^{K}\beta_{i}nr|V_{i}|(p^{*})^{|E_{i}|}\,,$
$\bar{\Delta}(\mathbf{q}_{S},p^{*}):=2n\sum_{u\in
S}\Big{[}L_{\beta}(\bar{q}_{u})+I(\bar{q}_{u})-L_{\beta}(p^{*})-I(p^{*})-\zeta_{\beta}(|\bar{q}_{u}-p^{*}|)\Big{]}\,,$

and

$Z_{\beta}^{\mathsf{mean}}:=\sum_{X_{\mathsf{mean}}\in
B}\exp(\mathcal{H}^{\mathsf{mean}}_{\beta}(X;S))\exp(-2n|S|I(p^{*})+\Gamma(p^{*}))\,.$

In the second step of (31) we have applied the cavity decomposition from Lemma
8.7. In the third step, we have used the fact that
$|C|=H_{\mathsf{cav}}(\mathbf{q}_{S})$ and in the fourth step, we have used
Lemma 8.8 to upper bound this count.

Now, note that under the condition $p^{*}<1-|S|/n$, there exists an admissible
restricted degree $\bar{q}\in\\{0,1/n,\dots,1-{|S|}/{n}\\}$ such that
$|\bar{q}-p^{*}|\leq{1}/{n}$. Denote by $\mathbf{\bar{q}}$ the degree tuple
with $\mathbf{\bar{q}}_{u}=\bar{q}$ for every $u\in S$. Clearly,
$\mu(B)\geq\mu(A(S,\mathbf{\bar{q}},p^{*},\eta))$. Repeating the calculation
in Equation (31), but with corresponding lower bounds instead of upper bounds,
we conclude that

$\mu(B)\geq\frac{Z^{\mathsf{mean}}_{\beta}}{Z_{\beta}}\exp(-O(nr\eta+r^{2}\log(\tfrac{n}{r})+r\log
n)+\underline{\Delta}(\mathbf{\bar{q}},p^{*}))\,,$ (32)

where

$\underline{\Delta}(\mathbf{q}_{S},p^{*})=2n\sum_{u\in
S}\Big{[}L_{\beta}(\bar{q}_{u})-L_{\beta}(p^{*})-C_{\beta}|\bar{q}_{l}-p^{*}|\Big{]}\,.$

Using the properties of the Shannon entropy (i.e,
$\sup_{p\in[0,1-{1}/{n}]}|H(p)-H(p+{1}/{n})|=|H(0)-H({1}/{n})|\leq
n^{-1}({1+\log n})$), we have that

$\sup_{p\in[0,1-1/n]}\Big{|}L_{\beta}(p)-L_{\beta}\Big{(}p+\frac{1}{n}\Big{)}\Big{|}\leq
C_{\beta}\frac{\log n}{n}$

for some positive constant $C_{\beta}$. This implies that
$\underline{\Delta}(\mathbf{\bar{q}},p^{*})\leq C_{\beta}r\log(n)$. Plugging
this into the lower bound on $\mu(B)$ in Equation (32), and then combining it
with the upper bound on $\mu(A)$ in Equation (31), we obtain the claim. ∎

From this result we derive the following corollary, which establishes that
$\sup_{u\in[n]}|p_{u}(X)-p^{*}|$ must be close to zero with high probability
under the measure $\mu\big{(}\cdot\bigr{|}B^{\square}_{\eta}(p^{*})\big{)}$.
Observe that in the statement of Theorem 8.9, the term in the exponent,
$L_{\beta}(\bar{q}_{u})-L_{\beta}(p^{*})-\zeta_{\beta}(|\bar{q}_{u}-p^{*}|)<-\delta_{0}<0$
whenever $|\bar{q}_{u}-p^{*}|$ is large. Therefore, this the event where
$|\bar{q}_{u}-p^{*}|$ is large incurs an exponentially small probability. We
refer to Section D for its complete proof.

######  Corollary 8.10.

Suppose $p^{*}\in U_{\beta}$ and let $\epsilon>0$ be an arbitrary fixed
constant. Then, we can take $0<\eta<c(\beta,\epsilon)$ and
$n>n_{0}(\beta,\epsilon,\eta)$ such that

$\mu\Big{(}\sup_{u\in[n]}|p_{u}(X)-p^{*}|\leq\epsilon\,\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}\geq
1-\exp(-\Omega_{\beta,\epsilon}(n))\,.$

Recall that in Lemma 7.2, we showed that whenever $X$ is close to the constant
graphon $p^{*}$, then _most_ of the degrees concentrate close to $p^{*}$. In
the result below we show that when $p_{u}(X)$ is close to $p^{*}$ uniformly
for _every_ vertex $u$ (as shown in Corollary 8.10) and $X$ is close to the
constant graphon $p^{*}$, most of the degrees $p_{uv}(X)$ concentrate close to
$(p^{*})^{2}$. This will be useful in Section 6, where we will prove Theorem
4.5, which is the important component behind the proof of Theorem 3.1.

######  Corollary 8.11.

Suppose that $p^{*}\in U_{\beta}$. Given arbitrary $\epsilon,\delta>0$,
suppose $\eta<c(\beta,\epsilon,\delta)$ and
$n>n_{0}(\delta,\epsilon,\beta,\eta)$. Then, for every $u\in[n]$, there exists
a random set $S_{u}\subseteq[n]\setminus\\{u\\}$ such that $|S_{u}|\leq\delta
n$ and

$\mu\Big{(}\sup_{u\in[n]}\sup_{v\in
S^{\complement}_{u}}|p_{uv}(X)-(p^{*})^{2}|\leq\epsilon\,\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}\geq
1-\exp(-\Omega_{\beta,\epsilon}(n))\,.$

We refer to Appendix D.1 for the proof.

##  9 Proof of Theorem 3.3

Before proceeding with the proof of Theorem 3.3, we will establish
generalizations of [1, Lemma 12 and Lemma 17]. Therefore, we will not
instantiate to the model parameters given in Example 3.2 but consider a
general ERGM with parameter $\beta$. We need to treat the vertex $1$
separately from the other vertices. Following the notation preceding Lemma 12
in [1], we define for some fixed, finite set of graphs $\mathcal{G}$:

$\bar{r}_{\max}(X):=\max\Big{(}\max_{u:u\neq
1}p_{u}(X),\sup_{\begin{subarray}{c}e=(u,v):u,v\neq 1\\\
G\in\mathcal{G}\end{subarray}}r_{G}(X,e)\Big{)}$

and

$\bar{r}_{\min}(X):=\min\Big{(}\min_{u:u\neq
1}p_{u}(X),\inf_{\begin{subarray}{c}e=(u,v):u,v\neq 1\\\
G\in\mathcal{G}\end{subarray}}r_{G}(X,e)\Big{)}\,.$

Here, we consider the evolution of the vertices $2,\dots,n-1$ when they are
close to $G(n-1,p^{*})$ in terms of the subgraph counts and the edges
connecting vertex $1$ are arbitrary. Notice that we have included the degrees
$p_{u}(X)$ here in addition to $r_{G}(X,e)$, which will be useful to us later
in the proof. The lemma below follows from a rewriting of the proof of Lemma
17 in [1], by noting that the edges connected to vertex $1$ do not influence
the evolution of $\Delta^{e}_{G}(X)$ in the leading order term as considered
in [1, Lemma 12 and Lemma 14] and a straightforward tweak to also consider
$p_{u}(X)$. Therefore, we skip the proof.

######  Lemma 9.1.

Suppose $\mathcal{G}=\mathbb{G}_{L}$ (the set of all graphs with at-most $L$
vertices) and let $\epsilon>0$ be a small enough constant independent of $n$.
Suppose $p^{*}\in U_{\beta}$ and let $X_{0},X_{1},\dots$ are drawn from the
Glauber dynamics with respect to the measure $\mu$. For some large enough
$L\in\mathbb{N}$, independent of $n$, if $X_{0}$ is such that
$p^{*}-\epsilon\leq\bar{r}_{\min}(X_{0})\leq\bar{r}_{\max}(X_{0})\leq
p^{*}+\epsilon$, then for some $\alpha$ depending only on $\beta,\epsilon,L$,
we have

$\mathbb{P}\Big{(}\sup_{t\leq e^{\alpha n}}\bar{r}_{\max}(X_{t})\geq
p^{*}+2\epsilon\Big{)}\leq\exp(-\Omega_{\beta,L,\epsilon}(n))$

and

$\mathbb{P}\Big{(}\inf_{t\leq e^{\alpha n}}\bar{r}_{\min}(X_{t})\leq
p^{*}-2\epsilon\Big{)}\leq\exp(-\Omega_{\beta,L,\epsilon}(n))\,.$

We now instantiate our discussion to the case of the exponential random graph
model defined in Example 3.2 and use the notation established in this example.
Recall $p_{1}(X)$ and $p_{1u}(X)$. Define

$p^{(1)}_{\max}(X)=\max\Big{(}p_{1}(X),\max_{\begin{subarray}{c}u\neq 1\\\
u\in[n]\end{subarray}}\frac{p_{1u}(X)}{p_{1}^{*}}\Big{)}\qquad\text{and}\qquad
p^{(1)}_{\min}(X)=\min\Big{(}p_{1}(X),\min_{\begin{subarray}{c}u\neq 1\\\
u\in[n]\end{subarray}}\frac{p_{1u}(X)}{p_{1}^{*}}\Big{)}\,.$

######  Lemma 9.2.

Consider the same setting as Lemma 9.1 instantiated to the parameter $\beta$
given in Example 3.2, with $p^{*}=p_{1}^{*}$. Given $\epsilon_{1}>0$, we can
pick $\epsilon$ in Lemma 9.1 small enough such that the following holds:
Suppose $q^{*}-\epsilon_{1}\leq p_{\min}^{(1)}(X_{0})\leq
p_{\max}^{(1)}(X_{0})\leq q^{*}+\epsilon_{1}$, then for some $\alpha$
depending only on $\beta,\epsilon,\epsilon_{1},L$, we have

$\mathbb{P}\Big{(}\sup_{t\leq e^{\alpha n}}p_{\max}^{(1)}(X_{t})\geq
q^{*}+2\epsilon_{1}\Big{)}\leq\exp(-\Omega_{\beta,L,\epsilon}(n))$

and

$\mathbb{P}\Big{(}\inf_{t\leq e^{\alpha n}}p^{(1)}_{\min}(X_{t})\leq
q^{*}-2\epsilon_{1}\Big{)}\leq\exp(-\Omega_{\beta,L,\epsilon}(n))\,.$

###### Proof.

Let $N:={{n}\choose{2}}$. Recall the function $g$ defined in Example 3.2 and
$\phi_{\beta}$ as defined in Section 2. It is easy to show using similar
techniques as in [1, Lemma 12] that

$-\frac{p_{1}(X_{t})}{N}+\frac{g(p^{(1)}_{\min})}{N}\leq\mathbb{E}\left[p_{1}(X_{t+1})-p_{1}(X_{t})|X_{t}\right]\leq-\frac{p_{1}(X_{t})}{N}+\frac{g(p^{(1)}_{\max})}{N}\,.$

Similarly, for every $u\in[n]$ and $u\neq 1$, denoting
$\bar{r}_{\max}(X_{t}),\bar{r}_{\min}(X_{t})$ by
$\bar{r}_{\max},\bar{r}_{\min}$ respectively,

$\mathbb{E}\left[p_{1u}(X_{t+1})-p_{1u}(X_{t})|X_{t}\right]\leq-\frac{2p_{1u}(X_{t})}{N}+\frac{g(p^{(1)}_{\max})\bar{r}_{\max}}{N}+\frac{p^{(1)}_{\max}\phi(\bar{r}_{\max})}{N}$

and

$\mathbb{E}\left[p_{1u}(X_{t+1})-p_{1u}(X_{t})|X_{t}\right]\geq-\frac{2p_{1u}(X_{t})}{N}+\frac{g(p^{(1)}_{\min})\bar{r}_{\min}}{N}+\frac{p^{(1)}_{\min}\phi(\bar{r}_{\min})}{N}\,.$

Now, notice that by Lemma 9.1, $\bar{r}_{\max}(X_{t})/p_{1}^{*}\leq
1+2\frac{\epsilon}{p_{1}^{*}}$ and $\bar{r}_{\min}(X_{t})/p_{1}^{*}\geq
1-2\frac{\epsilon}{p_{1}^{*}}$ with probability at-least $\exp(-\Omega(n))$
whenever $t\leq\exp(\alpha n)$. Therefore, we can consider the evolution of
$\frac{p_{1u}(X_{t})}{p_{1}^{*}}$ akin to the evolution of $p_{1}(X_{t})$ with
$g(x)$ replaced by $\frac{g(x)+x}{2}$. Notice that the functions $g$ and
$\frac{1}{2}(g(x)+x)$ play the role of $\phi()$ in the proof of [1, Lemma 12]
and satisfy the relationship $g(q^{*})=q^{*}$ and $g^{\prime}(q^{*})<1$ (same
for $\frac{g(x)+x}{2}$). This allows us to conclude the statement of the lemma
with minor modifications to the proof of Lemma 17 in [1] ∎

###### Proof of Theorem 3.3.

Let the initial state $X_{0}$ be sampled as in the theorem statement.

  1. 1.

Recall $\delta_{\square}^{S,p^{*}}$ given in Definition 8.5. Consider this
with $S=\\{1\\}$. By Lemma 8.6, in order to show that $X_{t}\in
B^{\square}_{\eta}(p^{*})$ it is sufficient to show that
$\delta_{\square}^{{1},p^{*}}(X_{t},p^{*})\leq{\eta}/{4}$ with high
probability. With similar arguments as in the proof of Lemma 4.10 with
$r_{\min},r_{\max}$ replaced with $\bar{r}_{\min},\bar{r}_{\max}$ we conclude
that with probability at-least $1-T\exp(-\Omega_{\eta,\beta}(n))$, we have
that every point in the trajectory $X_{0},X_{1},\dots,X_{T}\in
B^{\square}_{\eta}(p^{*})$. Using Lemma 9.2 and the result above we conclude
the statement.

  2. 2.

This follows from a straightforward application of Theorem 8.9 along with
Theorem 1.3 and the fact that $p_{1}^{*}$ is the unique global maximizer of
$U_{\beta}$.

  3. 3.

This follows from the same considerations as the proof of Item 2.

∎

## Acknowledgements

G.B. and D.N. gratefully acknowledge the hospitality of the Simons Institute
for Theoretical Computer Science during Fall 2020 and Fall 2021. This work was
supported in part by NSF CAREER award CCF-1940205 and NSF Award DMS-2022448.

## References

  * [1] Bhamidi, S., Bresler, G., Sly, A.: Mixing time of exponential random graphs.  Annals of Applied Probability 21(6), 2146–2170 (2011)
  * [2] Borgs, C., Chayes, J., Lovász, L., Sós, V.T., Szegedy, B., Vesztergombi, K.: Graph limits and parameter testing.  In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 261–270 (2006)
  * [3] Bresler, G., Nagaraj, D.: Optimal single sample tests for structured versus unstructured network data.  In: Conference On Learning Theory, pp. 1657–1690. PMLR (2018)
  * [4] Burda, Z., Jurkiewicz, J., Krzywicki, A.: Network transitivity and matrix models.  Physical Review E 69(2), 026106 (2004)
  * [5] Chatterjee, S.: Stein’s method for concentration inequalities.  Probability theory and related fields 138(1-2), 305–321 (2007)
  * [6] Chatterjee, S., Diaconis, P.: Estimating and understanding exponential random graph models.  The Annals of Statistics 41(5), 2428–2461 (2013)
  * [7] Eldan, R., Gross, R.: Exponential random graphs behave like mixtures of stochastic block models.  The Annals of Applied Probability 28(6), 3698–3735 (2018)
  * [8] Fienberg, S.E.: Introduction to papers on the modeling and analysis of network data.  The Annals of Applied Statistics pp. 1–4 (2010)
  * [9] Fienberg, S.E.: Introduction to papers on the modeling and analysis of network data—ii.  The Annals of Applied Statistics 4(2), 533–534 (2010)
  * [10] Frank, O., Strauss, D.: Markov graphs.  Journal of the american Statistical association 81(395), 832–842 (1986)
  * [11] Ganguly, S., Nam, K.: Sub-critical exponential random graphs: concentration of measure and some applications.  To appear in Transactions of the AMS. arXiv preprint arXiv:1909.11080 (2019)
  * [12] Gelman, A., Meng, X.L.: Simulating normalizing constants: From importance sampling to bridge sampling to path sampling.  Statistical science pp. 163–185 (1998)
  * [13] Geyer, C.J., Thompson, E.A.: Constrained monte carlo maximum likelihood for dependent data.  Journal of the Royal Statistical Society: Series B (Methodological) 54(3), 657–683 (1992)
  * [14] Gheissari, R., Sinclair, A.: Low-temperature Ising dynamics with random initializations.  arXiv preprint arXiv:2106.11296 (2021)
  * [15] Guo, H., Jerrum, M.: Random cluster dynamics for the Ising model is rapidly mixing.  In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1818–1827. SIAM (2017)
  * [16] Holland, P.W., Leinhardt, S.: An exponential family of probability distributions for directed graphs.  Journal of the american Statistical association 76(373), 33–50 (1981)
  * [17] Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the ising model.  SIAM Journal on computing 22(5), 1087–1116 (1993)
  * [18] Kou, S., Zhou, Q., Wong, W.H.: Equi-energy sampler with applications in statistical inference and statistical mechanics.  The annals of Statistics 34(4), 1581–1619 (2006)
  * [19] Levin, D.A., Luczak, M.J., Peres, Y.: Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability.  Probability Theory and Related Fields 146(1), 223–265 (2010)
  * [20] Levin, D.A., Peres, Y.: Markov chains and mixing times, vol. 107.  American Mathematical Soc. (2017)
  * [21] Lindsey, M., Weare, J., Zhang, A.: Ensemble Markov chain Monte Carlo with teleporting walkers.  arXiv preprint arXiv:2106.02686 (2021)
  * [22] Lubetzky, E., Sly, A.: Fast initial conditions for Glauber dynamics.  Probability Theory and Related Fields 181(1), 647–667 (2021)
  * [23] Mukherjee, S., Xu, Y.: Statistics of the two-star ergm.  arXiv preprint arXiv:1310.4526 (2013)
  * [24] Park, J., Newman, M.E.: Solution of the two-star model of a network.  Physical Review E 70(6), 066146 (2004)
  * [25] Park, J., Newman, M.E.: Solution for the properties of a clustered network.  Physical Review E 72(2), 026136 (2005)
  * [26] Radin, C., Yin, M.: Phase transitions in exponential random graphs.  The Annals of Applied Probability pp. 2458–2471 (2013)
  * [27] Reinert, G., Ross, N.: Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs.  The Annals of Applied Probability 29(5), 3201–3229 (2019)
  * [28] Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing markov chains.  Information and Computation 82(1), 93–133 (1989)
  * [29] Swendsen, R.H., Wang, J.S.: Nonuniversal critical dynamics in Monte carlo simulations.  Physical review letters 58(2), 86 (1987)
  * [30] Ullrich, M.: Swendsen–wang is faster than single-bond dynamics.  SIAM Journal on Discrete Mathematics 28(1), 37–48 (2014)
  * [31] Wasserman, S., Faust, K.: Social network analysis: Methods and applications (1994)
  * [32] Yin, M., Zhu, L.: Asymptotics for sparse exponential random graph models.  Brazilian Journal of Probability and Statistics 31(2), 394–412 (2017)

##  Appendix A Proofs of Technical Lemmas

###  A.1 Proof of Lemma 7.2

Fix any $p\in[0,1]$ and $\delta>0$ and consider the sets
$S^{+}:=\bigr{\\{}u:p_{u}(X)-p>{2\delta_{\square}(\tilde{X},p\mathbf{1})}/{\delta}\bigr{\\}}$
and
$S^{-}:=\\{u:p_{u}(X)-p<-{2\delta_{\square}(\tilde{X},p\mathbf{1})}/{\delta}\\}$.
By the definition of the cut-metric it follows that

$\delta_{\square}(\tilde{X},p\mathbf{1})\geq\frac{1}{n}\sum_{u\in
S^{+}}p_{u}(X)-p\geq\frac{2|S^{+}|\delta_{\square}(\tilde{X},p\mathbf{1})}{n\delta}\,.$

Thus, $|S^{+}|\leq{\delta n}/{2}$ and similarly $|S^{-}|\leq{\delta n}/{2}$.
Therefore, $|S^{+}\cup S^{-}|\leq\delta n$, which allows us to conclude the
first inequality by taking $S=S^{+}\cup S^{-}$. The second inequality follows
by directly applying Theorem 1.3 to Equation (19). ∎

###  A.2 Proof of Lemma 7.3

We note that when considering distance from any constant graphon $p\mathbf{1}$
we have
$\delta_{\square}(\tilde{X},p\mathbf{1})=\delta_{\square}(f^{X},p\mathbf{1})$,
since measure-preserving operators do not affect the constant graphon. Now,
notice that since $f^{Y}(x_{1},x_{2})-p\leq f^{X}(x_{1},x_{2})-p\leq
f^{Z}(x_{1},x_{2})-p$, for any Borel measurable sets $S,T\subseteq[0,1]$ we
have

$\int_{S\times T}(f^{X}(x_{1},x_{2})-p)dx_{1}dx_{2}\leq\int_{S\times
T}(f^{Z}(x_{1},x_{2})-p)dx_{1}dx_{2}\leq\delta_{\square}(\tilde{Z},p)\,.$

Similarly,

$\int_{S\times T}(f^{X}(x_{1},x_{2})-p)dx_{1}dx_{2}\geq\int_{S\times
T}(f^{Y}(x_{1},x_{2})-p)dx_{1}dx_{2}\geq-\delta_{\square}(\tilde{Y},p)\,.$

These together establish that

$\Big{|}\int_{S\times
T}(f^{X}(x_{1},x_{2})-p)dx_{1}dx_{2}\Big{|}\leq\max(\delta_{\square}(\tilde{Y},p),\delta_{\square}(\tilde{Z},p))\,.$

Taking the suprememum over $S,T$ yields the lemma. ∎

###  A.3 Proof of Lemma 7.4

In case $d_{i}<|E|$ for some $i$, we start with Young’s product inequality,
which states that for every $a,b\geq 0$ and $\alpha,\beta>0$ such that
${\alpha}^{-1}+{\beta}^{-1}=1$, we have
$ab\leq{\alpha}^{-1}{a^{\alpha}}+{\beta}^{-1}{b^{\beta}}$. We take
$a=q^{d_{i}}$, $b=p^{|E|-d_{i}}$, $\alpha={|E|}/{d_{i}}$ and
$\beta={|E|}/{(|E|-d_{i})}$. In case $d_{i}=|E|$, we check that the
inequalities below hold trivially. Hence

$\displaystyle\sum_{i=1}^{|V|}q^{d_{i}}p^{|E|-d_{i}}$
$\displaystyle\leq\sum_{i=1}^{|V|}\frac{d_{i}}{|E|}q^{|E|}+\frac{|E|-d_{i}}{|E|}p^{|E|}$
$\displaystyle=\frac{\sum_{i=1}^{|V|}d_{i}}{|E|}q^{|E|}+\frac{|V||E|-\sum_{i=1}^{|V|}d_{i}}{|E|}p^{|E|}$
$\displaystyle=2q^{|E|}+(|V|-2)p^{|E|}\,.$ (33)

In the last step, we have used the fact that for any finite simple graph $G$,
$\sum_{i=1}^{|V|}d_{i}=2|E|$. Equality when $G=G_{0}$ follows by a
straightforward calculation.

Now suppose that $G\neq G_{0}$. Then, it is easy to show that there exists a
vertex $j$ such that $d_{j}<|E|$. We note that Young’s product inequality is
strict whenever $a^{\alpha}\neq b^{\beta}$. For the choice of
$a,b,\alpha,\beta$ above, this condition means $p\neq q$. Now, consider the
function:
$f(p,q)=-q^{d_{j}}p^{|E|-d_{j}}+\frac{d_{i}}{|E|}q^{|E|}+\frac{|E|-d_{i}}{|E|}p^{|E|}$.
This is continuous over the set $[0,1]^{2}$. Define
$A_{\delta}:=\\{(p,q)\in[0,1]^{2}:|p-q|\geq\delta\\}$. Clearly, $A_{\delta}$
is a compact set for every $\delta\geq 0$. Define
$\zeta(\delta)=\inf_{(p,q)\in A_{\delta}}f(p,q)$. It is clear from the
strictness of the Young’s inequality that $f(p,q)>0$ for every $(p,q)\in
A_{\delta}$ whenever $\delta>0$. Therefore, we conclude by compactness of
$A_{\delta}$ and continuity of $f$ that $\zeta(\delta)>0$ whenever $\delta>0$.
The continuity of $\zeta$ follows from the continuity of $f$. Therefore, we
conclude that there exists $\zeta$ as in the statement of the lemma such that:

$-C|p-q|\leq
q^{d_{j}}p^{|E|-d_{j}}-\frac{d_{i}}{|E|}q^{|E|}-\frac{|E|-d_{i}}{|E|}p^{|E|}\leq-\zeta(|p-q|)\,.$

The inequality above holds with $\zeta=0$ for every $i$, even when
$d_{i}=|E|$. This allows us to sum the inequality above and conclude the
result. ∎

###  A.4 Proof of Lemma 8.2

Since the proof is elementary, we only provide a brief sketch. The statement
$N_{G}^{0}(X,u)\geq N_{G}(X,u)$ follows from the fact that
$A_{u}^{k}=\cup_{l=1}^{k}A^{k,l}_{u}$ and the union bound. Now, note that
$0\leq\sum_{l=1}^{k}\mathbbm{1}(A^{k,l}_{u})-\mathbbm{1}(A_{u}^{k})\leq k$ and
the sum is non zero only when the event $A_{u}^{k,l}\cap A_{u}^{k,m}$ holds
for some $l\neq m$, $l,m\in[k]$. Noting that under the uniform measure over
$[0,1]^{k}$ the measure of $A_{u}^{k,l}\cap A_{u}^{k,m}$ is ${n^{-2}}$ and
using the union bound, we conclude the result. ∎

###  A.5 Proof of Lemma 8.3

Suppose $d_{i}$ is the degree of vertex $i\in[k]$. In light of Lemma 8.2 we
may replace $N_{G}(X,u)$ in the lemma statement by $N_{G}^{0}(X;u)$ and then
by considering a specific term in the sums we see that it is sufficient to
prove that

$\biggr{|}\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}-\frac{p_{u}(X)^{d_{l}}p^{|E(G)|-d_{l}}}{n}\biggr{|}\leq|E(G)|\frac{\delta_{\square}(\tilde{X},p)}{n}\,.$

Notice that

$\displaystyle\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}$
$\displaystyle=\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\prod_{(l,i)\in
E(G)}f^{X}(x_{l},x_{i})\prod_{\begin{subarray}{c}(i,j)\in E(G)\\\ i,j\neq
l\end{subarray}}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}\,.$ (34)

A simple computation shows that

$\displaystyle\frac{p_{u}(X)^{d_{l}}p^{|E(G)|-d_{l}}}{n}$
$\displaystyle=\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\bigg{(}\prod_{\begin{subarray}{c}i:(l,i)\in
E(G)\end{subarray}}f^{X}(x_{l},x_{i})\bigg{)}p^{E(G)-d_{l}}\prod_{i=1}^{k}dx_{i}\,.$
(35)

Therefore,

$\displaystyle\biggr{|}\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}-\frac{p_{u}(X)^{d_{l}}p^{|E(G)|-d_{l}}}{n}\biggr{|}$
$\displaystyle=\biggr{|}\int_{[0,1]^{k}}\mathbbm{1}(A^{k,l}_{u})\prod_{(l,i)\in
E(G)}f^{X}(x_{l},x_{i})\bigg{[}\prod_{\begin{subarray}{c}(i,j)\in E(G)\\\
i,j\neq
l\end{subarray}}f^{X}(x_{i},x_{j})-p^{|E(G)|-d_{l}}\bigg{]}\prod_{i=1}^{k}dx_{i}\biggr{|}\,.$
(36)

Following the proof of [2, Lemma 4.4] with minor modifications, consider any
ordering among the set of edges $(i,j)\in E(G)$ such that $i,j\neq l$ and
index these ordered edges by $(i_{1},j_{1}),\dots,(i_{h},j_{h})$ where
$h=|E(G)|-d_{l}$. Then

$\displaystyle\bigg{[}\prod_{\begin{subarray}{c}(i,j)\in E(G)\\\ i,j\neq
l\end{subarray}}f^{X}(x_{i},x_{j})-p^{|E(G)|-d_{l}}\bigg{]}$
$\displaystyle\qquad=\sum_{r=0}^{|E(G)|-d_{l}-1}p^{r}\prod_{m=r+1}^{|E(G)|-d_{l}}f^{X}(x_{i_{m}},x_{j_{m}})-p^{r+1}\prod_{m=r+2}^{|E(G)|-d_{l}}f^{X}(x_{i_{m}},x_{j_{m}})\,.$

Now, we use the above decomposition in Equation (36) and consider the terms in
the summation one by one. We then follow the technique used in the proof of
[2, Lemma 4.4] along with the fact that $A^{k,l}_{u}$ depends only on $x_{u}$
and the fact that the measure of the event $A^{k,l}_{u}$ under the uniform
measure over $[0,1]^{k}$ is ${1}/{n}$ to conclude the result. ∎

###  A.6 Proof of Lemma 8.4

Only in this proof, we will take the probability space to be $[0,1]^{k}$
equipped with the Borel sigma algebra and the uniform measure $P$.

First, note that by the union bound, $\sum_{u\in S}N_{G}(X;u)\geq N_{G}(X;S)$.
Now, almost surely

$\sum_{u\in S}\mathbbm{1}(A^{k}_{u})\leq k\,,$

since there are at most $k$ vertices in the graph $G$. We conclude that almost
surely

$\sum_{u\in S}\mathbbm{1}(A^{k}_{u})-\mathbbm{1}(A^{k}_{S})\leq k-1\,.$

Now let $B^{k}_{S}$ be the event that
$\sum_{l}\mathbbm{1}(A^{k}_{u})\neq\mathbbm{1}(A^{k}_{S})$. This can happen
only when two events $A^{k,i}_{u}$ and $A^{k,j}_{v}$ hold simultaneously for
some $i,j\in[k]$, $u,v\in S$, $i\neq j$ and $u\neq v$. Therefore, we have

$B^{k}_{S}=\bigcup_{\begin{subarray}{c}u,v\in S\\\ u\neq
v\end{subarray}}\bigcup_{\begin{subarray}{c}i,j\in[k]\\\ i\neq
j\end{subarray}}A_{u}^{k,i}\cap A_{v}^{k,j}\,.$

By the union bound,

$P(B^{k}_{S})\leq|S|^{2}k^{2}P(A_{l}^{k,i}\cap
A_{m}^{k,j})=\frac{|S|^{2}k^{2}}{n^{2}}\,.$

Now combining the considerations above, we have

$\displaystyle\sum_{l\in S}N_{G}(X;l)-N_{G}(X;S)$
$\displaystyle=\int_{[0,1]^{k}}\left[-\mathbbm{1}\left(A_{S}^{k}\right)+\sum_{l\in
S}\mathbbm{1}(A_{l}^{k})\right]\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}$
$\displaystyle\leq(k-1)\int_{[0,1]^{k}}\mathbbm{1}(B^{k}_{S})\prod_{(i,j)\in
E(G)}f^{X}(x_{i},x_{j})\prod_{i=1}^{k}dx_{i}$ $\displaystyle\leq
kP(B^{k}_{S})\leq\frac{|S|^{2}k^{3}}{n^{2}}\,.$ (37)

The lemma statement follows. ∎

###  A.7 Proof of Lemma 8.6

In this proof alone, we will abuse notation to denote the set $\cup_{u\in
S}[\frac{u-1}{n},\frac{u}{n})\subseteq[0,1]$ also by $S$ (and similarly for
$S^{\complement}$). Since we are considering the cut-metric between
$\tilde{X}$ and a constant graphon, we can write

$\displaystyle\delta_{\square}^{S,p^{*}}(\tilde{X},p^{*})$
$\displaystyle=\sup_{A,B\subset[0,1]}\biggr{|}\int_{A\times
B}\left[f^{X,S,p^{*}}(x_{1},x_{2})-p^{*}\right]dx_{1}dx_{2}\biggr{|}$
$\displaystyle=\sup_{A,B\subset[0,1]}\biggr{|}\int_{A\cap
S^{\complement}\times B\cap
S^{\complement}}\left[f^{X}(x_{1},x_{2})-p^{*}\right]dx_{1}dx_{2}\biggr{|}$
$\displaystyle=\sup_{A,B\subset S^{\complement}}\biggr{|}\int_{A\times
B}\left[f^{X}(x_{1},x_{2})-p^{*}\right]dx_{1}dx_{2}\biggr{|}\,.$ (38)

From the last equality above, we conclude that
$\delta_{\square}^{S,p^{*}}(\tilde{X},p^{*})\leq\delta_{\square}(\tilde{X},p^{*})$.
To conclude the lower bound, note that

$\delta_{\square}(\tilde{X},p)\leq\delta_{\square}(\tilde{X},\tilde{X}^{S,p^{*}})+\delta_{\square}(\tilde{X}^{S,p^{*}},p^{*})=\delta_{\square}(\tilde{X},\tilde{X}^{S,p^{*}})+\delta^{S,p^{*}}_{\square}(\tilde{X},p^{*})\,.$

It is now easy to show that
$\delta_{\square}(\tilde{X},\tilde{X}^{S,p^{*}})\leq
1-{|S^{\complement}|^{2}}/{n^{2}}$, which when combined with the last display
above proves the lower bound. ∎

###  A.8 Proof of Lemma 8.8

By Stirling’s formula, we have that for any $k\in\mathbb{N}$ and $p\in[0,1]$
such that $kp$ is an integer,

$\frac{\exp(-2kI(p))}{\sqrt{2k}}\leq{{k}\choose{kp}}\leq\exp(-2kI(p))\,.$

A counting argument shows that $N_{\mathsf{cav}}(\mathbf{q}_{S})=\prod_{u\in
S}{{n-|S|}\choose{q_{u}n}}$. For the upper bound, note that

$\displaystyle\prod_{u\in S}{{n-|S|}\choose{q_{u}n}}$
$\displaystyle\leq\prod_{u\in
S}{{n}\choose{q_{u}n}}\leq\exp\Big{(}-2n\sum_{u\in S}I(q_{u})\Big{)}\,.$ (39)

Now, for the lower bounds, we note that whenever $q_{u}\leq q\leq 1$ and
$q\geq 1/2$: $|2qI({q_{u}}/{q})-2I(q_{u})|\leq(2+\log({1}/({1-q})))(1-q)$.
Taking $q=({n-|S|})/{n}=1-{r}/{n}$ below, we have

$\displaystyle\prod_{u\in S}{{n-|S|}\choose{q_{u}n}}$
$\displaystyle\geq\frac{\exp\Big{(}-\sum_{u\in
S}2(n-|S|)I(\tfrac{nq_{u}}{n-|S|})\Big{)}}{\left(\sqrt{2n}\right)^{r}}$
$\displaystyle\geq\exp\Big{(}-\sum_{u\in
S}2nI(q_{u})-r^{2}\left[4+2\log(\tfrac{n}{r})\right]-\frac{r}{2}\log(2n)\Big{)}\,.$
(40)

∎

##  Appendix B Proofs of lemmas from Section 6

###  B.1 Proof of Lemma 6.1

Before proving the lemma, we derive an estimate for $\Delta^{e}_{G}(X)$.

Recall the event $A^{k}_{u}$ in (21) in Section 8. Suppose the fixed graph $G$
has the vertex set $[k]$. We now define for $u,v\in[n]$,

$A^{kG}_{uv}:=\big{\\{}x\in[0,1]^{k}:(\lfloor nx_{i}\rfloor,\lfloor
nx_{j}\rfloor)\in\\{(u,v),(v,u)\\}\text{ for some }(i,j)\in E(G)\big{\\}}\,.$

For $i,j\in[k]$ define

$A^{kij}_{uv}:=\big{\\{}x\in[0,1]^{k}:(\lfloor nx_{i}\rfloor,\lfloor
nx_{j}\rfloor)\in\\{(u,v),(v,u)\\}\big{\\}}\,.$

Now, the definition of homomorphism density yields

$\displaystyle\Delta^{e}_{G}(X)$ $\displaystyle=N_{G}(X^{+e})-N_{G}(X^{-e})$
$\displaystyle=\int\prod_{(i,j)\in
E(G)}f^{X^{+e}}(x_{i},x_{j})\prod_{t=1}^{k}dx_{t}-\prod_{(i,j)\in
E(G)}f^{X^{-e}}(x_{i},x_{j})\prod_{t=1}^{k}dx_{t}$
$\displaystyle=\int\mathbbm{1}(A^{kG}_{uv})\prod_{(i,j)\in
E(G)}f^{X^{+e}}(x_{i},x_{j})\prod_{t=1}^{k}dx_{t}\,.$ (41)

A computation similar to the proof of Lemma 8.2 shows that

$\int\Big{|}\mathbbm{1}(A^{kG}_{uv})-\sum_{(i,j)\in
E(G)}\mathbbm{1}(A^{kij}_{uv})\Big{|}\prod_{t=1}^{k}dx_{t}\leq\frac{E(G)^{3}}{n^{3}}\,.$

Using this in Equation (41), we conclude that

$\displaystyle\Delta^{e}_{G}(X)$ $\displaystyle=\int\sum_{(i,j)\in
E(G)}\mathbbm{1}(A^{kij}_{uv})\prod_{(a,b)\in
E(G)}f^{X^{+e}}(x_{a},x_{b})\prod_{t=1}^{k}dx_{t}\pm
O\Big{(}\frac{E(G)^{3}}{n^{3}}\Big{)}$ $\displaystyle=\sum_{(i,j)\in
E(G)}\int\mathbbm{1}(A^{kij}_{uv})\prod_{\begin{subarray}{c}(a,b)\in E(G)\\\
(a,b)\neq(i,j)\end{subarray}}f^{X^{+e}}(x_{a},x_{b})\prod_{t=1}^{k}dx_{t}\pm
O\Big{(}\frac{E(G)^{3}}{n^{3}}\Big{)}\,.$ (42)

We are now ready for the proof.

###### Proof.

We will prove the result by replacing $p_{uv}(X),p_{u}(X)$, and
$\delta_{\square}(X,p^{*})$ with $p_{uv}(X^{+e}),p_{u}(X^{+e})$, and
$\delta_{\square}(X^{+e},p^{*})$, noting that
$\delta_{\square}(X,X^{+e})\leq{2}/{n^{2}}$,
$|p_{uv}(X)-p_{uv}(X^{+e})|\leq{1}/{n}$, and
$|p_{u}(X)-p_{u}(X^{+e})|\leq{1}/{n}$.

We will use $E$ and $E(G)$ interchangeably in this proof. For $(i,j)\in E(G)$,
first consider the quantity

$\displaystyle\int\mathbbm{1}(A^{kij}_{uv})\prod_{\begin{subarray}{c}(a,b)\in
E\\\
(a,b)\neq(i,j)\end{subarray}}f^{X^{+e}}(x_{a},x_{b})\prod_{t=1}^{k}dx_{t}$
$\displaystyle=\int\mathbbm{1}(A^{kij}_{uv})\prod_{\begin{subarray}{c}(i,l)\in
E\\\ l\neq
j\end{subarray}}f^{X^{+e}}(x_{i},x_{l})\prod_{\begin{subarray}{c}(j,l)\in E\\\
l\neq
i\end{subarray}}f^{X^{+e}}(x_{j},x_{l})\prod_{\begin{subarray}{c}(a,b)\in E\\\
a,b\notin\\{i,j\\}\end{subarray}}f^{X^{+e}}(x_{a},x_{b})\prod_{t=1}^{k}dx_{t}$
$\displaystyle=(p^{*})^{|E|-d_{i}-d_{j}+1}\int\mathbbm{1}(A^{kij}_{uv})\prod_{\begin{subarray}{c}(i,l)\in
E\\\ l\neq
j\end{subarray}}f^{X^{+e}}(x_{i},x_{l})\prod_{\begin{subarray}{c}(j,l)\in E\\\
l\neq i\end{subarray}}f^{X^{+e}}(x_{j},x_{l})\prod_{t=1}^{k}dx_{t}$
$\displaystyle\quad\pm\frac{2|E(G)|\delta_{\square}(\tilde{X^{+e}},p^{*})}{n^{2}}\,.$
(43)

In the last step we have used a similar peeling argument as in Lemma 8.3.
Recalling the sets $A_{u}^{ki}$ from Section 8, we note that whenever $i\neq
j$, $\mathbbm{1}(A^{kij}_{uv})=\mathbbm{1}(A^{ki}_{u}\cap
A^{kj}_{v})+\mathbbm{1}(A^{kj}_{u}\cap A^{ki}_{v})$. Now,

$\displaystyle\int\mathbbm{1}(A^{ki}_{u}\cap
A^{kj}_{v})\prod_{\begin{subarray}{c}(i,l)\in E\\\ l\neq
j\end{subarray}}f^{X^{+e}}(x_{i},x_{l})\prod_{\begin{subarray}{c}(j,l)\in E\\\
l\neq i\end{subarray}}f^{X^{+e}}(x_{j},x_{l})\prod_{t=1}^{k}dx_{t}$
$\displaystyle=\int\mathbbm{1}(A^{ki}_{u}\cap
A^{kj}_{v})\prod_{\begin{subarray}{c}(i,l)\in E\\\ l\neq j\\\ l\not\in
E_{ij}(G)\end{subarray}}f^{X^{+e}}(x_{i},x_{l})\prod_{\begin{subarray}{c}(j,l)\in
E\\\ l\neq i\\\ l\in E_{ij}(G)\end{subarray}}f^{X^{+e}}(x_{j},x_{l})\times$
$\displaystyle\quad\qquad\qquad\qquad\qquad\qquad\prod_{l\in
E_{ij}(G)}f^{X^{+e}}(x_{i},x_{l})f^{X^{+e}}(x_{j},x_{l})\prod_{t=1}^{k}dx_{t}$
$\displaystyle=\frac{1}{n^{2}}(p_{u}(X^{+e}))^{d_{i}-1-d_{ij}}(p_{v}(X^{+e}))^{d_{j}-1-d_{ij}}(p_{uv}(X^{+e}))^{d_{ij}}\,.$
(44)

In the last step, we have used the definitions of degrees $p_{u}$ and $p_{uv}$
given in Equations (4) and (5) in terms of integrals over $f^{X}$. Using this
in Equation (43), and shortening $p_{u}(X_{e}^{+}),p_{v}(X_{e}^{+})$ and
$p_{uv}(X_{e}^{+})$ to $p_{u},p_{v}$ and $p_{uv}$, we obtain

$\displaystyle
n^{2}\int\mathbbm{1}(A^{kij}_{uv})\prod_{\begin{subarray}{c}(a,b)\in E\\\
(a,b)\neq(i,j)\end{subarray}}f^{X^{+e}}(x_{a},x_{b})\prod_{t=1}^{k}dx_{t}$
$\displaystyle=(p^{*})^{|E|-d_{i}-d_{j}+1}(p_{u})^{d_{i}-1-d_{ij}}(p_{v})^{d_{j}-1-d_{i}j}(p_{uv})^{d_{ij}}$
$\displaystyle\quad+(p^{*})^{|E|-d_{i}-d_{j}+1}(p_{v})^{d_{i}-1-d_{ij}}(p_{u})^{d_{j}-1-d_{ij}}(p_{uv})^{d_{ij}}\pm
2|E(G)|\delta_{\square}(\tilde{X^{+e}},p^{*})\,.$ (45)

Using the condition $\sup_{u}|p_{u}(X)-p^{*}|<\epsilon$, Equation (42), and
the equation above, we conclude the statement of the lemma. ∎

###  B.2 Proof of Lemma 6.4

We first state a simple modification of [5, Theorem 1.5] below, which follows
by essentially rewriting its proof with minor changes.

######  Lemma B.1 (Modification of Theorem 1.5 in [5]).

Under the same notation as [5, Theorem 1.5], we suppose the same conditions as
the original theorem hold, except condition (ii), where we replace the
assumption $\Delta(X)\leq Bf(X)+C$, with

  1. 1.

$\Delta(X)\leq\alpha\mathbbm{1}(A)+\gamma\mathbbm{1}(A^{\complement})$ for
some event $A\in\sigma(X)$, $\alpha,\gamma\in\mathbb{R}^{+}$

  2. 2.

$|f(X)|\leq M$ almost surely.

Then, we have

$\mathbb{P}(|f(X)|>t)\leq\Big{(}1+\frac{\gamma\exp(\theta_{0}M)\mathbb{P}(A^{\complement})}{\alpha}\Big{)}\inf_{\theta\in[0,\theta_{0}]}\exp\Big{(}\frac{\theta^{2}\alpha}{2}-\theta
t\Big{)}\,.$

###### Proof.

In the proof of [5, Theorem 1.5], in the display below Equation (7), we have
for $\theta\in[0,\theta_{0}]$

$\displaystyle|m^{\prime}(\theta)|$
$\displaystyle\leq|\theta|\mathbb{E}\exp^{\theta f(X)}\Delta(X)$
$\displaystyle\leq|\theta|\alpha
m(\theta)+|\theta|\gamma\exp(|\theta|M)\mathbb{P}(A^{\complement})$
$\displaystyle\leq|\theta|\alpha
m(\theta)+|\theta|\gamma\exp(|\theta_{0}|M)\mathbb{P}(A^{\complement})\,.$

In the second step we have used the hypothesis that
$\Delta(X)\leq\alpha\mathbbm{1}(A)+\gamma\mathbbm{1}(A^{\complement})$ and
$|f(X)|\leq M$. Therefore

$\frac{d}{d\theta}\log\left(m(\theta)+\tfrac{\gamma\exp(\theta_{0}M)\mathbb{P}(A^{\complement})}{\alpha}\right)\leq\theta\alpha\,.$

The result then follows by an application of Gronwall’s lemma and the Chernoff
bound. ∎

We will consider Glauber dynamics with respect to the measure
$\mu(\cdot|B^{\square}_{\eta}(p^{*}))$ (Definition 1.1) in order to generate
the exchangeable pairs required by [5, Theorem 1.5] (and Lemma B.1), where the
event $B^{\square}_{\eta}(p^{*})$ is as defined in Equation (30). In the
notation of [5, Theorem 1.5], we consider

$F_{uv}(X,X^{\prime}):=\sum_{\begin{subarray}{c}w\in[n]\\\
w\notin\\{u,v\\}\end{subarray}}X_{uw}X_{vw}-\sum_{\begin{subarray}{c}w\in[n]\\\
w\notin\\{u,v\\}\end{subarray}}X^{\prime}_{uw}X^{\prime}_{vw}\,.$

With the help of Lemma B.1, we will now prove Lemma 6.4.

###### Proof of Lemma 6.4.

By Lemma 7.1, we conclude that whenever $p^{*}\in U_{\beta}$ and $\eta>0$ is
small enough,

$\mu\Big{(}B^{\square}_{\eta/2}(p^{*}))\Big{|}{B^{\square}_{\eta}(p^{*})}^{\complement}\Big{)}\leq
C(\beta,\eta)\exp(-c(\beta,\eta)n^{2})\,.$

Let $X$ be drawn from the distribution $\mu(\cdot|B^{\square}_{\eta}(p^{*}))$
and let $X^{\prime}$ be obtained by taking a single step of Glauber dynamics
with respect to the measure $\mu(\cdot|B^{\square}_{\eta}(p^{*}))$. Clearly,
$(X,X^{\prime})$ form an exchangeable pair. Let

$f_{uv}(X):=\mathbb{E}\left[F_{uv}(X,X^{\prime})|X\right]\,.$

Notice that $|f_{uv}(X)|\leq 1$ almost surely since
$|F_{uv}(X,X^{\prime})|\leq 1$. For $n$ large enough as a function of $\eta$,
whenever $X\in B^{\square}_{\eta/2}(p^{*})$, the Glauber dynamics over
$\mu(\bigr{|}{B^{\square}_{\eta}(p^{*})})$ is exactly equal to the Glauber
dynamics w.r.t. $\mu$. Therefore, a simple calculation yields the following
for $X\in B^{\square}_{\eta/2}(p^{*})$:

$f_{uv}(X)=\frac{4p_{uv}(X)}{n-1}-{{{n}\choose{2}}^{-1}}\sum_{\begin{subarray}{c}w\in[n]\\\
w\notin\\{u,v\\}\end{subarray}}\phi_{uw}(X_{\sim uw})X_{vw}+\phi_{vw}(X_{\sim
vw})X_{uw}\,.$ (46)

For any edge $e$, we consider $\phi_{e}(X_{\sim
e})=\frac{\exp(\sum_{i=1}^{K}n^{2}\beta_{i}\Delta^{e}_{i}(X))}{1+\exp(\sum_{i=1}^{K}n^{2}\beta_{i}\Delta^{e}_{i}(X))}$.
Note that

$|\phi_{e}(X_{\sim e})-\phi_{e}(X^{\prime}_{\sim e})|\leq
C(\beta)n^{2}\sup_{i\in[K]}|\Delta^{e}_{i}(X)-\Delta^{e}_{i}(X^{\prime})|\,.$
(47)

Now, $X_{\sim e}$ and $X_{\sim e}^{\prime}$ can differ at most in one edge, by
construction. Suppose this edge is $h$. When $e=h$, then
$\Delta^{e}_{i}(X)=\Delta^{e}_{i}(X^{\prime})$. Now suppose $e\neq h$.
Invoking Equation (41) with $k=|V_{i}|$, we obtain

$\displaystyle|\Delta^{e}_{i}(X)-\Delta^{e}_{i}(X^{\prime})|$
$\displaystyle=\biggr{|}\int\mathbbm{1}(A^{kG_{i}}_{e})\Big{[}\prod_{(a,b)\in
E(G)}f^{X_{e}^{+}}(x_{a},x_{b})-\prod_{(a,b)\in
E(G)}f^{(X^{\prime}_{e})^{+}}(x_{a},x_{b})\Big{]}\prod_{t=1}^{k}dx_{t}\biggr{|}$
$\displaystyle\leq\int\mathbbm{1}(A^{kG_{i}}_{e})\mathbbm{1}(A^{kG_{i}}_{h})\prod_{t=1}^{k}dx_{t}\leq\frac{|E(G_{i})|^{2}}{n^{3}}\,.$
(48)

Combining Equations (46), (47) and (48), we conclude that whenever $X\in
B^{\square}_{{\eta}/{2}}(p^{*})$,

$|f_{uv}(X)-f_{uv}(X^{\prime})|\leq\frac{C(\beta)}{n^{2}}\,.$ (49)

Observe that whenever the Glauber dynamics does not update an edge of the form
$(u,w)$ or $(v,w)$, $F_{uv}(X,X^{\prime})=0$. Let $A^{\mathsf{upd}}$ denote
the event where $F_{uv}(X,X^{\prime})\neq 0$. Clearly,
$\mathbb{P}(A^{\mathsf{upd}}|X)\leq{4}/{n}$. It is also clear that
$|F_{uv}(X,X^{\prime})|\leq 1$ almost surely. Therefore, we have for any
$X\in\Omega$

$|f(X)|\leq\mathbb{E}\left[|F(X,X^{\prime})||X\right]\leq\mathbb{P}\big{(}A^{\mathsf{upd}}|X\big{)}\leq\frac{4}{n}\,.$
(50)

Now consider the local variance proxy $\Delta_{uv}(X)$ (where the notation is
once again derived from [5, Theorem 1.5]) whenever $X\in
B^{\square}_{\eta/2}(p^{*})$,

$\displaystyle\Delta_{uv}(X)$
$\displaystyle:=\frac{1}{2}\mathbb{E}\left[\left(f_{uv}(X)-f_{uv}(X^{\prime})\right)F_{uv}(X,X^{\prime})\bigr{|}X\right]$
$\displaystyle\leq\frac{C(\beta)}{n^{2}}\mathbb{E}\big{[}\mathbbm{1}(A^{\mathsf{upd}})\bigr{|}X\big{]}\leq\frac{C(\beta)}{n^{3}}\,.$
(51)

Here, we have used Equation (49). Whenever, $X\notin
B^{\square}_{\eta/2}(p^{*})$, we will use the crude bound

$\Delta_{uv}(X)\leq\frac{C}{n^{2}}\,,$

obtained by plugging in
$|f(X)-f(X^{\prime})|\leq|f(X)|+|f(X^{\prime})|\leq{8}/{n}$ (which follows
from Equation (50)) into the the definition of $\Delta_{uv}$. Combining these
bounds, we get that

$\Delta_{uv}(X)\leq\frac{C(\beta)}{n^{3}}\mathbbm{1}(X\in
B^{\square}_{\eta/2}(p^{*}))+\frac{C(\beta)}{n^{2}}\mathbbm{1}(X\not\in
B^{\square}_{\eta/2}(p^{*}))\,.$

By Lemma 7.1,

$\mu\Big{(}X\not\in
B^{\square}_{\eta/2}(p^{*})\Big{|}B^{\square}_{\eta/2}(p^{*})\Big{)}\leq
C_{\beta,\eta}\exp(-c(\beta,\eta)n^{2})\,.$

Now, applying Lemma B.1, with $M={4}/{n}$, and $\theta_{0}=C_{\beta}n^{2}$ for
some large enough $C_{\beta}$ and $t={4\gamma}/({n-1})$, we conclude the
result. ∎

##  Appendix C Deferred Proofs for Path Coupling

###  C.1 Proof of Lemma 4.1

Consider the following coupling between the trajectories $X_{0},\dots,X_{K}$
and $Y_{0},\dots,Y_{K}$:

  1. 1.

Generate $(X_{0},Y_{0})$ from the specified initial distribution.

  2. 2.

Given $X_{k},Y_{k}$, we generate $X_{k+1},Y_{k+1}$ as follows:

$(X_{k+1},Y_{k+1})\sim\begin{cases}Q_{X_{k},Y_{k}}&\quad\text{ if
}(X_{k},Y_{k})\in A\\\ P(X_{k},\cdot)\times P(Y_{k},\cdot)&\quad\text{
otherwise}\end{cases}$ (52)

Now we consider the distance $d(X_{k+1},Y_{k+1})$. We have

$\displaystyle\mathbb{E}d(X_{k+1},Y_{k+1})$
$\displaystyle=\mathbb{E}d(X_{k+1},Y_{k+1})\mathbbm{1}((X_{k},Y_{k})\in
A\times A)$
$\displaystyle\quad+\mathbb{E}d(X_{k+1},Y_{k+1})\mathbbm{1}((X_{k},Y_{k})\in
A^{\complement})$
$\displaystyle\leq\mathbb{E}(1-\gamma)d(X_{k},Y_{k})\mathbbm{1}((X_{k},Y_{k})\in
A)$
$\displaystyle\quad+\mathbb{E}d(X_{k+1},Y_{k+1})\mathbbm{1}((X_{k},Y_{k})\in
A^{\complement})$
$\displaystyle\leq(1-\gamma)\mathbb{E}d(X_{k},Y_{k})+\mathbb{E}d(X_{k+1},Y_{k+1})\mathbbm{1}((X_{k},Y_{k})\in
A^{\complement})$
$\displaystyle\leq(1-\gamma)\mathbb{E}d(X_{k},Y_{k})+\bar{D}\mathbbm{P}((X_{k},Y_{k})\in
A^{\complement})$
$\displaystyle\leq(1-\gamma)\mathbb{E}d(X_{k},Y_{k})+\bar{D}p_{k}\,.$ (53)

We conclude the result by unrolling the recursion. ∎

###  C.2 Proof of Lemma 4.9

In both this and the next proof, we let

$r_{\min}(X):=\inf_{\begin{subarray}{c}e\in{{n}\choose{2}}\\\
G\in\mathbb{G}_{L}\end{subarray}}r_{G}(X,e)\qquad\text{and}\qquad
r_{\max}(X):=\sup_{\begin{subarray}{c}e\in{{n}\choose{2}}\\\
G\in\mathbb{G}_{L}\end{subarray}}r_{G}(X,e)\,.$

###### Proof.

We will only prove the coupling for $G(n,p^{*}+\epsilon)$. The other coupling
follows analogously. Let $N={{n}\choose{2}}$. Let $e_{1},\dots,e_{N}$ be any
enumeration of ${{[n]}\choose{2}}$. Let
$X_{0}\sim\mu(\cdot|B^{\square}_{\eta}(p^{*}))$ and obtain the sequence
$X_{0},\dots,X_{N}$ by updating as follows: Given $X_{i-1}$, define
$(X_{i})_{e}=(X_{i-1})_{e}$ whenever $e\neq e_{i}$ and let $(X_{i})_{e_{i}}$
be independently re-sampled from the conditional distribution
$(X_{i-1})_{e_{i}}\bigr{|}(X_{i-1})_{\sim e_{i}}$. In other words, we obtain
$X_{i}$ by re-sampling the coordinate $e_{i}$ in $X_{i-1}$. Clearly,
$X_{N}\sim\mu(\cdot|B^{\square}_{\eta}(p^{*}))$.

Now, consider $Y_{0}=0\in\Omega$ almost surely. Let $e_{1},\dots,e_{N}$ be the
same as before. We will construct $Y_{1},\dots,Y_{N}$ as follows: Given
$Y_{i-1}$, we construct $Y_{i}$ such that $(Y_{i})_{\sim
e_{i}}=(Y_{i-1})_{\sim e_{i}}$ and $(Y_{i})_{e_{i}}$ is freshly drawn from
$\mathsf{Ber}(p^{*}+\epsilon)$. It is clear that $Y_{N}\sim
G(n,p^{*}+\epsilon)$.

By Theorem 4.5, we have that $p^{*}-\epsilon\leq r_{\min}(X_{i})\leq
r_{\max}(X_{i})\leq p^{*}+\epsilon$ with probability at-least
$1-C(\eta,\beta,\epsilon)\exp(-c(\eta,\beta,\epsilon)n)$. Recall the
definition of $\phi_{\beta}$ from Section 2 and note that
$\mathbb{P}((X_{i})_{e_{i}}=1|X_{i-1})\leq\phi_{\beta}(r_{\max}(X_{i-1}))\leq
p^{*}+\epsilon$. Therefore the fresh draws can be coupled such that
$(X_{i})_{e_{i}}\leq(Y_{i})_{e_{i}}$ with probability at least
$1-C(\eta,\beta,\epsilon)\exp(-c(\eta,\beta,\epsilon)n)$. Since
$(X_{i})_{e_{i}}=(X_{N})_{e_{i}}$ and $(Y_{i})_{e_{i}}=(Y_{N})_{e_{i}}$, we
conclude via a union bound over $i\leq N$ that $X_{N}\preceq Y_{N}$ with
probability at least $1-C(\eta,\beta,\epsilon)\exp(-c(\eta,\beta,\epsilon)n)$.
This gives the desired coupling by taking $X=X_{N}$ and $\bar{Y}=Y_{N}$ in the
statement of the lemma. ∎

###  C.3 Proof of Lemma 4.10

We first show that with probability at-least $1-C(\eta)\exp(-c(\eta)n)$, we
must have $p^{*}-{\eta}/{4}\leq r_{\min}(X_{0})\leq r_{\max}(X_{0})\leq
p^{*}+{\eta}/{4}$.

This can be shown for example by using Lemma 6.1 and simple concentration
bounds for the degrees $p_{u}(X_{0})$ and $p_{uv}(X_{0})$. The fact that
$\delta_{\square}(\tilde{X}_{0},p^{*})$ is small follows from Theorem 1.3
since $G(n,p^{*})$ is also (a very special case of) an exponential random
graph. Now, invoking Lemma 4.8, we conclude that with probability at least
$1-TC(\beta,\eta)\exp(-c(\beta,\eta)n)$, we have for every $t\leq T$ that

$p^{*}-\frac{\eta}{2}\leq r_{\min}(X_{t})\leq r_{\max}(X_{t})\leq
p^{*}+\frac{\eta}{2}\,.$ (54)

Now consider Markov chains $Y_{0},\dots,Y_{T}$ and $Z_{0},\dots,Z_{T}$ where
$Y_{0}\sim G(n,p^{*}-{\eta}/{2})$ and $Z_{0}\sim G(n,p^{*}+\frac{\eta}{2})$.
Here, we generate the respective trajectories by Glauber dynamics with respect
to $G(n,p^{*}-{\eta}/{2})$ (resp. $G(n,p^{*}+\frac{\eta}{2})$ ) We couple the
trajectories as follows:

  1. 1.

At step $0$, we pick $X_{0},Y_{0},Z_{0}$ such that almost surely

$Y_{0}\preceq X_{0}\preceq Z_{0}\,.$

  2. 2.

At step $t$, pick the same edge
$E_{t}\sim\mathsf{unif}\big{(}{{[n]}\choose{2}}\big{)}$ to update for each
$X_{t-1},Y_{t-1}$ and $Z_{t-1}$.

  3. 3.

Pick $u_{t}\sim\mathsf{unif}([0,1])$ independently of everything else and set

$(X_{t})_{E_{t}}=\mathbbm{1}(u_{t}\leq\phi_{E_{t}}((X_{t})_{\sim
E_{t}}));\quad(Y_{t})_{E_{t}}=\mathbbm{1}(u_{t}\leq
p^{*}-\tfrac{\eta}{2});\quad(Z_{t})_{E_{t}}=\mathbbm{1}(u_{t}\leq
p^{*}+\tfrac{\eta}{2})\,.$

For $\eta$ small enough, we verify that under the event in Equation (54)

$p^{*}-\frac{\eta}{2}\leq\phi_{\beta}(r_{\max}(X_{t}))\leq\phi_{E_{t}}((X_{t})_{\sim
E_{t}})\leq\phi_{\beta}(r_{\max}(X_{t}))\leq p^{*}+\frac{\eta}{2}\,.$

This implies that $(Y_{t})_{E_{t}}\leq(X_{t})_{E_{t}}\leq(Z_{t})_{E_{t}}$. We
conclude that with probability at least
$1-TC(\beta,\eta)\exp(-c(\beta,\eta)n)$ we have $Y_{t}\preceq X_{t}\preceq
Z_{t}$. Now, we will apply Theorem 7.3 to obtain

$\delta_{\square}(\tilde{X}_{t},p^{*})\leq\max\big{(}\delta_{\square}(\tilde{Y}_{t},p^{*}),\delta_{\square}(\tilde{Z}_{t},p^{*})\big{)}\,.$
(55)

Now, since $Y_{t}\sim G(n,p^{*}-{\eta}/{2})$ and $Z_{t}\sim
G(n,p^{*}+{\eta}/{2})$, we have

$\mathbb{P}\Big{(}\max\big{(}\delta_{\square}(\tilde{Y}_{t},p^{*}),\delta_{\square}(\tilde{Z}_{t},p^{*})\big{)}>\eta\Big{)}\leq
1-C(\eta)\exp(-c(\eta)n^{2})\,.$

Using this in Equation (55), we conclude the statement of the claim. ∎

##  Appendix D Proof of Corollary 8.10

###### Proof.

Let $\delta>0$ and $\eta>0$. We are given $X\in\Omega$ such that $X\in
B^{\square}_{\eta}(p^{*})$, i.e., $\delta_{\square}(\tilde{X},p^{*})<\eta$.
Consider the set $S(X):=\\{u:|p_{u}(X)-p^{*}|>{2\eta}/{\delta}\\}$. By Lemma
7.2, we note that $|S(X)|\leq\delta n$, so

$\\{S(X)\neq\emptyset\\}=\bigcup_{\begin{subarray}{c}S\subseteq[n]\\\
1\leq|S|\leq\delta n\end{subarray}}\\{S(X)=S\\}\,.$

By the union bound,

$\displaystyle\mu\big{(}|S(X)|\neq\emptyset\bigr{|}B^{\square}_{\eta}(p^{*})\big{)}$
$\displaystyle\leq\sum_{r=1}^{\delta
n}\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=r\end{subarray}}\mu\big{(}S(X)=S|B^{\square}_{\eta}(p^{*})\big{)}$
$\displaystyle=\sum_{r=1}^{\delta
n}{{n}\choose{r}}\mu\big{(}S(X)=[r]|B^{\square}_{\eta}(p^{*})\big{)}\,.$ (56)

Here, the second step follows from the permuation invariance of the vertices
with respect to the measure $\mu$. In order to evaluate the upper bound in
Equation (56), we will consider the measure of the event $\\{S(X)=[r]\\}$ for
$r\leq\delta n$.

Consider the restricted degrees $\bar{p}_{u}$ with respect to the set $[r]$
and suppose that $\delta^{2}<2\eta$. Let the set
$D(p^{*},\alpha,S):=\\{\mathbf{q}_{S}:\inf_{u\in
S}|\bar{q}_{u}-p^{*}|>\alpha\\}$ and note that

$\displaystyle\\{S(X)=[r]\\}$
$\displaystyle=\\{|p_{u}(X)-p^{*}|>{2\eta}/{\delta},\forall u\in[r]\\}$
$\displaystyle\subseteq\\{|\bar{p}_{u}(X)-p^{*}|>{2\eta}/{\delta}-\delta,\forall
u\in[r]\\}$ $\displaystyle=\bigcup_{\mathbf{q}_{[r]}\in
D(p^{*},\frac{2\eta}{\delta}-\delta,[r])}\\{\bar{p}_{u}(X)=\bar{q}_{u},\forall
u\in[r]\\}\,.$ (57)

Therefore whenever $\delta,\eta$ satisfy
${\epsilon}/{2}={2\eta}/{\delta}-\delta$, we have

$\displaystyle\\{S(X)=[r]\\}\cap\\{X\in
B([r],p^{*},\eta)\\}\subseteq\bigcup_{\mathbf{q}_{[r]}\in
D(p^{*},\tfrac{\epsilon}{2},[r])}A([r],\mathbf{q}_{[r]},p^{*},\eta)\,.$ (58)

Note that with the above choice of $\eta$ in the definition of $S(X)$, we can
take $\delta<{\epsilon}/{2}$ to conclude that for all $u\in
S(X)^{\complement}$, $|p_{u}(X)-p^{*}|\leq\epsilon$. We will note a simple
result which follows from standard arguments in calculus.

######  Lemma D.1.

Suppose $p^{*}\in U_{\beta}$ and $q\in[0,1]$ is such that
$|q-p^{*}|>\epsilon/2$. Then,
$L_{\beta}(q)-L_{\beta}(p^{*})-\zeta_{\beta}(|q-p^{*}|)<-C(\beta,\epsilon)<0$.

Pick $\delta$ to be small enough such that $p^{*}\in(\delta,1-\delta)$.
Combining Lemma D.1 with Equation (58) and Theorem 8.9 we conclude that
whenever $r\leq n\delta$:

$\displaystyle\frac{\mu(\\{S(X)=r\\}\cap
B([r],p^{*},\eta))}{\mu(B([r],p^{*},\eta))}\leq\sum_{\mathbf{q}_{[r]}\in
D(p^{*},\tfrac{\epsilon}{2},[r])}\frac{\mu(A([r],\mathbf{q}_{[r]},p^{*},\eta))}{\mu(B([r],p^{*},\eta))}$
$\displaystyle\leq|D(p^{*},\tfrac{\epsilon}{2},[r])|\exp(-nrC(\beta,\epsilon)+O_{\beta}(nr\eta+r^{2}\log(\tfrac{n}{r})+r\log
n))$
$\displaystyle\leq\exp(-2nrC(\beta,\epsilon)+O_{\beta}(nr\eta+r^{2}\log(\tfrac{n}{r})+r\log
n))$
$\displaystyle=\exp\left(-nr\left(2C(\beta,\epsilon)-O_{\beta}(\eta+\delta\log(\tfrac{1}{\delta})+\tfrac{\log
n}{n})\right)\right)$
$\displaystyle=\exp\left(-\Omega_{\beta,\epsilon}(nr)\right)\,.$ (59)

The first step follows from the union bound on Equation (58) and in the second
step we used Theorem 8.9 along with Lemma D.1. In the third step, we used that
$|D(p^{*},\epsilon,[r])|\leq n^{r}$. In the last step, we have picked
$\eta,\delta$ small enough (as functions of $\epsilon,\beta$) so that
${2\eta}/{\delta}-\delta={\epsilon}/{2}$, $\delta<{\epsilon}/{2}$,
$\eta<\eta_{0}(\epsilon,\beta)$ and $n$ large enough as a function of
$\epsilon,\beta$ such that
$O_{\beta}(\eta+\delta\log(1/{\delta})+{n}^{-1}{\log n}))<C(\beta,\epsilon)$.

By Lemma 8.6, whenever $r\leq\delta n$, we must have
$B^{\square}_{\eta}(p^{*})=B(\emptyset,p^{*},\eta)\subseteq
B([r],p^{*},\eta)\subseteq B(\emptyset,p^{*},\eta+\delta)$. Along with Lemma
7.1, we conclude that whenever $\eta,\delta$ are smaller than some constant
$c_{\beta}>0$, we have

$\mu(B^{\square}_{\eta}(p^{*}))\geq
c(\beta,\eta,\delta)\mu(B([r],p^{*},\eta))\,.$

Therefore whenever $n$ is larger than a constant depending only on
$\beta,\epsilon$ and $\eta_{0}$, we have

$\displaystyle\frac{\mu(\\{S(X)=[r]\\}\cap
B(\emptyset,p^{*},\eta))}{\mu(B(\emptyset,p^{*},\eta))}$
$\displaystyle\leq\frac{\mu(\\{S(X)=r\\}\cap
B([r],p^{*},\eta))}{\mu(B(\emptyset,p^{*},\eta))}$ $\displaystyle\leq
C(\beta,\eta,\delta)\frac{\mu(\\{S(X)=r\\}\cap
B([r],p^{*},\eta))}{\mu(B([r],p^{*},\eta))}$
$\displaystyle\leq\exp(-\Omega_{\beta,\epsilon}(nr))\,.$ (60)

Using the fact that ${{n}\choose{r}}\leq n^{r}$, it follows using Equations
(56) and (60) that

$\displaystyle\mu\big{(}|S(X)|\neq\emptyset\bigr{|}B^{\square}_{\eta}(p^{*})\big{)}$
$\displaystyle\leq\sum_{r=1}^{n\delta}n^{r}\exp(-\Omega_{\beta,\epsilon}(nr))$
$\displaystyle\leq\exp(-\Omega_{\beta,\epsilon}(n))\,,$

which proves the corollary. ∎

###  D.1 Proof of Corollary 8.11

Recall the sets
$A^{k,i}_{u}:=\\{x\in[0,1]^{k}:x_{i}\in[\frac{u-1}{n},\frac{u}{n})\\}$. Let
$\eta>0$ be arbitrary for now. Suppose that $X\in B^{\square}_{\eta}(p^{*})$.
We have by definition

$p_{uv}(X)=n^{2}\int
f^{X}(x_{1},x_{3})f^{X}(x_{2},x_{3})\mathbbm{1}(A^{3,1}_{u})\mathbbm{1}(A^{3,2}_{v})dx_{1}dx_{2}dx_{3}\,.$

A simple calculation reveals that

$p_{uv}(X)-p_{u}(X)p^{*}=n^{2}\int
f^{X}(x_{1},x_{3})\left(f^{X}(x_{3},x_{2})-p^{*}\right)\mathbbm{1}(A^{3,1}_{u})\mathbbm{1}(A^{3,2}_{v})dx_{1}dx_{2}dx_{3}\,.$

Now, define $S_{u}^{+}:=\\{v:p_{uv}(X)-p^{*}p_{u}(X)>{\epsilon}/{2}\\}$ and
$S_{u}^{-}:=\\{v:p_{uv}(X)-p^{*}p_{u}(X)<-{\epsilon}/{2}\\}$. Summing the
display above for $v\in S^{+}_{u}$, we have

$\displaystyle\frac{|S_{u}^{+}|\epsilon}{2n^{2}}$ $\displaystyle<\sum_{v\in
S_{u}^{+}}\int
f^{X}(x_{1},x_{3})\left(f^{X}(x_{3},x_{2})-p^{*}\right)\mathbbm{1}(A^{3,1}_{u})\mathbbm{1}(A^{3,2}_{v})dx_{1}dx_{2}dx_{3}$
$\displaystyle=\int_{x_{2}\in
A_{u}^{+}}f^{X}(x_{1},x_{3})\left(f^{X}(x_{3},x_{2})-p^{*}\right)\mathbbm{1}(A^{3,1}_{u})dx_{1}dx_{2}dx_{3}$
$\displaystyle=\int_{x_{1}\in[\tfrac{u-1}{n},\tfrac{u}{n})}\Big{[}\int_{\begin{subarray}{c}x_{2}\in
A_{u}^{+}\\\ x_{3}\in
C(x_{1})\end{subarray}}\left(f^{X}(x_{3},x_{2})-p^{*}\right)dx_{2}dx_{3}\Big{]}dx_{1}$
$\displaystyle\leq\frac{\delta_{\square}(\tilde{X},p^{*})}{n}\,,$ (61)

where $A_{u}^{+}:=\cup_{v\in S_{u}^{+}}[\tfrac{v-1}{n},\tfrac{v}{n})$ and
$C(x_{1}):=\\{x\in[0,1]:f^{X}(x_{1},x)=1\\}$.

Taking $\eta<{\delta\epsilon}/{2}$, we conclude that

$|S_{u}^{+}|\leq\frac{2n\delta_{\square}(\tilde{X},p^{*})}{\epsilon}\leq\frac{\delta
n}{2}$

and similarly

$|S_{u}^{-}|\leq\frac{2n\delta_{\square}(\tilde{X},p^{*})}{\epsilon}\leq\frac{\delta
n}{2}\,.$

Therefore, whenever
$\delta_{\square}(\tilde{X},p^{*})<\eta<{\delta\epsilon}/{2}$, the sets
$S_{u}:=S_{u}^{+}\cup S_{u}^{-}$ are such that

$\sup_{u\in[n]}\sup_{v\in
S^{\complement}_{u}}|p_{uv}(X)-p^{*}p_{u}(X)|\leq\frac{\epsilon}{2}\,.$ (62)

Now, invoking Corollary 8.10, we conclude that for any
$\eta<c(\beta,\epsilon,\delta)$ and whenever $n$ is larger than a constant
depending only on $\beta,\epsilon,\eta$ and $\delta$ we have

$\mu\Big{(}\sup_{u\in[n]}|p_{u}(X)-p^{*}|\leq\frac{\epsilon}{2}\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}\geq
1-\exp(-\Omega_{\beta,\epsilon}(n))$

and from Equation (62), we have

$\mu\Big{(}\sup_{u\in[n]}\sup_{v\in
S^{\complement}_{u}}|p_{uv}(X)-p^{*}p_{u}(X)|\leq\frac{\epsilon}{2}\Big{|}B^{\square}_{\eta}(p^{*})\Big{)}=1\,.$

Combining the two displays above, the statement of the corollary follows. ∎