# Consistency of spectral seriation

Amine<EMAIL_ADDRESS>[ Aaron
<EMAIL_ADDRESS>[  Département de Mathématiques et
Statistiques
Université de Montréal
Mila - Quebec Artificial Intelligence Institute
6666 St Urbain St, Montreal, Canada.
Department of Mathematics and Statistics
University of Ottawa
585 King Edward Ave, Ottawa, Canada.

###### Abstract

Consider a random graph $G$ of size $N$ constructed according to a graphon
$w\,:\,[0,1]^{2}\mapsto[0,1]$ as follows. First embed $N$ vertices
$V=\\{v_{1},v_{2},\ldots,v_{N}\\}$ into the interval $[0,1]$, then for each
$i<j$ add an edge between $v_{i},v_{j}$ with probability $w(v_{i},v_{j})$.
Given only the adjacency matrix of the graph, we might expect to be able to
approximately reconstruct the permutation $\sigma$ for which
$v_{\sigma(1)}<\ldots<v_{\sigma(N)}$ if $w$ satisfies the following linear
embedding property introduced in [25]: for each $x$, $w(x,y)$ decreases as $y$
moves away from $x$. For a large and non-parametric family of graphons, we
show that (i) the popular spectral seriation algorithm [2] provides a
consistent estimator $\hat{\sigma}$ of $\sigma$, and (ii) a small amount of
post-processing results in an estimate $\tilde{\sigma}$ that converges to
$\sigma$ at a nearly-optimal rate, both as $N\rightarrow\infty$.

62M30,

62G20,

Statistical seriation,

Permutation learning,

Spectral embedding,

Graphon,

###### keywords:

[class=MSC]

###### keywords:

,

##  1 Introduction

In this paper, we study a statistical version of the seriation problem, first
introduced by Robinson in [35] as a combinatorial problem. In this problem, we
get to observe a graph, and our goal is to order the vertices in such a way
that more similar items are placed near to each other. The pioneer of
seriation is considered to be Flinders Petrie, an Egyptologist, who called it
sequence dating in [31]. While the seriation originates from archaeology, it
has recent applications to ecology, sociology, biology, and other topics. See
[27] for a historical overview on the seriation problem.

We relate the seriation problem from [31] to the notation used in this
article. We begin with a collection of $N\in\mathbb{N}$ objects, with the
$i$’th object associated with an unobserved point $v_{i}\in[0,1]$. In [31],
these objects corresponds to a set of graves, with $v_{i}$ the age of the
$i$’th grave. We then get to observe a symmetric graph $G=(V,E)$ with vertex
set $V=\\{v_{1},v_{2},\ldots,v_{N}\\}$. Informally, we expect that an edge is
more likely to appear between vertices $v_{i}$ and $v_{j}$ that are closer
together. Continuing the example of [31], the observed graph is constructed by
putting an edge between $v_{i}$ and $v_{j}$ if we find the same type of
artifacts in both the $i$’th and $j$’th graves. This co-occurrence is more
likely when the two graves have similar ages. The goal in seriation is then to
find an ordering $\sigma\,:\,V\mapsto\\{1,2,\ldots,N\\}$ for which
$v_{\sigma(1)}<v_{\sigma(2)}<\ldots<v_{\sigma(N)}$. In [31], this means
inferring a chronological ordering of the true ages of the set of graves by
observing the different types of archaeological finds on each grave.

Many versions of the seriation problem have been studied. Perhaps the simplest
occurs when the observed graph satisfies the following property: for all
$v_{i}<v_{j}<v_{k}$,

$(v_{i},v_{k})\in E\implies(v_{i},v_{j})\in E\ \text{and}\ (v_{j},v_{k})\in
E.$ (1.1)

Graphs satisfying this property are called Robinsonian, named after Robinson
who first introduced this property in [35]. We call this the noiseless
seriation problem, as there will never be any “missing" edges and a perfect
ordering exists.

######  Remark 1.1 (Reversals and Recovery).

Since we can only observe the graph $G$, there is no way to distinguish
between an ordering $\sigma$ and its reversal $\mathrm{rev}(\sigma)$, defined
by

$\mathrm{rev}(\sigma)(i)=N+1-\sigma(i).$ (1.2)

This means that, although we say that we wish to find an ordering
$\hat{\sigma}$ that is close to the ordering $\sigma$ that satisfies
$v_{\sigma(1)}<v_{\sigma(2)}<\ldots<v_{\sigma(N)}$, the best that we can hope
for is an ordering $\hat{\sigma}$ that is close to either $\sigma$ or
$\mathrm{rev}(\sigma)$. We expect that this non-identifiability is rarely a
problem in practical applications: even a small amount of additional
information lets you distinguish between the extremely different estimates
$\hat{\sigma}$ and $\mathrm{rev}(\hat{\sigma})$.

To avoid repeatedly discussing this small non-identifiability issue, we
usually hide it by the following small abuse of notation. For any metric $d$
that can be applied to orders, we always intend the symmetrized version

$d(\sigma_{1},\sigma_{2})=\min(d(\sigma_{1},\sigma_{2}),d(\mathrm{rev}(\sigma_{1}),\sigma_{2}))$
(1.3)

unless we explicitly say otherwise. We only need to pay attention to this
issue in step 3 of our post-processing algorithm (Algorithm 3), where we
consider several different estimated orderings and must “align" them.

This noiseless version of the seriation problem has been well-studied in the
computer science literature, and there are several algorithms that are known
to return a correct $\sigma$ very quickly; we believe that [9] is the fastest.
Of the provably-correct algorithms, one of the simplest and best-known is the
spectral seriation algorithm (see Algorithm 1 below) introduced in [2]. This
algorithm is based on the spectrum of the Laplacian of the observed graph.

In realistic examples, the data is noisy and (1.1) will not hold exactly. This
motivates the statistical seriation problem, in which the edges of the graph
$G$ are seen as random and (1.1) only holds “on average.” We study the
following natural generalization introduced in [7]: for all
$v_{i}<v_{j}<v_{k}$,

$\mathbb{P}\left((v_{i},v_{k})\in
E\right)\leq\min\left(\mathbb{P}\left((v_{i},v_{j})\in
E\right),\,\mathbb{P}\left((v_{j},v_{k})\in E\right)\right).$ (1.4)

In this situation we typically can’t recover $\sigma$ exactly, and so the goal
becomes estimating $\sigma$. Algorithm 1, the spectral seriation algorithm, is
commonly applied to the statistical seriation problem as well as the noiseless
seriation problem.

We give the usual spectral algorithm below, but first set notation. For any
integer $n\in\mathbb{N}$ define $[n]=\\{1,2,\ldots,n\\}$. For any set $S$ and
any function $f\,:\,S\mapsto\mathbb{R}$, define the associated ordering
$\sigma_{f}\,:\,S\mapsto\left[|S|\right]$ by the formula

$\sigma_{f}(i)=|\\{j\in S\,:\,f(j)\leq f(i)\\}|,$ (1.5)

breaking ties in $f$ arbitrarily to make the resulting function bijective. If
$S=[N]$ and $f$ does not contain any repeated values, it is clear that
$f(\sigma_{f}(1))\leq f(\sigma_{f}(2))\leq\cdots\leq f(\sigma_{f}(N))$.

The spectral seriation algorithm is based on the eigenvalues of a related
Laplacian matrix, rather than the adjacency matrix itself. We recall that the
(unnormalized) Laplacian matrix of a graph with $N$ vertices and adjacency
matrix $A=(a_{i,j})_{1\leq i,j\leq N}$ is given by $L_{A}=(D-A)$, where the
degree matrix $D=(d_{ij})_{1\leq i,j\leq N}$ is the diagonal matrix with
entries $d_{ii}=\sum_{j=1}^{N}a_{ij}$. The spectral seriation algorithm
introduced in [2] is as follows:

1

Input : A graph $G$.

2 Compute the adjacency matrix $A$ of the graph $G$.

3 Compute the Laplacian matrix $L_{A}$.

4 Find the eigenvector $\phi$ of $L$ with second-smallest eigenvalue, called
the Fiedler vector.

5 Compute the permutation $\sigma_{\phi}$ according to Equation (1.5).

Output : The permutation $\sigma_{\phi}$.

Algorithm 1 The spectral seriation algorithm.

As shown in [2], under the satisfying property (1.1) this algorithm always
returns a correct permutation. The same algorithm also gives a popular
estimator for the statistical seriation problem. The main contribution of this
paper is the study of the performance of this algorithm for the statistical
seriation problem under fairly general conditions, which we now introduce.

A graphon is a measurable function $w:[0,1]^{2}\to[0,1]$ which is symmetric
(i.e., $w(x,y)=w(y,x)$). See [28] for a general introduction to graphons, and
[7] for previous work on graphons in the context of seriation. In this paper,
we say that a random graph $G=(V,E)$ with $N$ vertices is sampled from a
graphon $w$ and write $G\sim w$ if: (i) the vertices of the graph
$V=\\{v_{1},v_{2},\ldots,v_{N}\\}$ are $v_{i}=\tfrac{i}{N}$ and (ii) the edges
of $G$ are sampled independently with probabilities: 111In the larger graphon
literature, it is more common to view $v_{i}$ as being i.i.d. samples taken
uniformly from $[0,1]$. This does not make a large difference in the types of
estimates we obtain in this paper. We use this embedding to more closely match
previous work on special cases of the seriation problem, such as [5, 4, 15].

$\mathbb{P}\left((v_{i},v_{j})\in E\right)=w\left(v_{i},v_{j}\right).$ (1.6)

Our paper includes two main results on this problem. We now give weak but-
easy-to-state versions of our main theorems, applying to the following family
of random graphs:

######  Definition 1.2 (“Nice" Random Graphs).

We say that a graphon $w$ is “nice" if $w$ can be written as
$w(x,y)=R(\left|x-y\right|)$ for all $x,y\in[0,1]$, where $R:[0,1]\to(0,1]$ is
a $\mathcal{C}^{1}$ function such that $R^{\prime}(x)<0$ for all $x\in(0,1)$.

To give a simple concrete family of examples: (i) the graphons
$w(x,y)=1-\alpha|x-y|^{\beta}$ belong to this family when $0<\alpha\leq 1$ and
$1\leq\beta<\infty$, and (ii) the graphons
$w(x,y)=\exp{\left(\frac{-(x-y)^{2}}{2\sigma^{2}}\right)}$ for any $\sigma>0$
(known as the RBF kernel) also belong to this family.

Denote by $id_{N}$ the identity permutation on $[N]$, and for all $\gamma>1$
and $N\geq 1$ define
$\varepsilon_{\gamma}(N):=\exp{\left(-\log^{\gamma}(N)\right)}$. The following
is an immediate consequence of Theorems 2 and 3, as we show in Section 7:

######  Theorem 1.

Let $w$ be a graphon of the form given in Definition 1.2. Consider a family of
random graphs $\\{G^{(N)}\\}_{N\in\mathbb{N}}$ where each $G^{(N)}$ has
exactly $N$ vertices, and is sampled from $w$ in the sense of Equation (1.6)
(i.e., $G^{(N)}\sim w$), and let $\hat{\sigma}^{(N)}$ be the output of
Algorithm 1 with input $G^{(N)}$. For any fixed $\varepsilon\in(0,1)$ and
$\eta\in(0,1/3)$, there exists a positive constant $C=C(w)<\infty$ and an
integer $N_{0}=N_{0}(w,\varepsilon,\eta)$ so that for all $N\geq N_{0}$

$\mathbb{P}\left(\left\|\hat{\sigma}^{(N)}-id_{N}\right\|_{1}\leq
CN^{2-\eta}\right)>1-\varepsilon.$ (1.7)

Furthermore, denote by $\tilde{\sigma}^{(N)}$ the “post-processed” estimate
obtained from Algorithm 3 with input $G^{(N)}$ and parameters $\alpha=0.05$,
$\beta=0.31$. Then for any $\gamma>1$ and $\epsilon>0$, there exist a positive
constant $\delta=\delta(w,\gamma,\epsilon)$ and an integer
$N_{0}=N_{0}(w,\gamma,\epsilon)$ so that

$\mathbb{P}\left(\left\|\tilde{\sigma}^{(N)}-id_{N}\right\|_{\infty}\leq\epsilon\,\sqrt{N\log^{\gamma}(N)}\right)>1-\varepsilon^{\delta}_{\gamma}(N)$
(1.8)

for all $N\geq N_{0}$.

We note that Inequality (1.8), which is a weak form of Theorem 3, is much
stronger than (1.7), which is a weak form of Theorem 2, in at least two ways:
the norm in which convergence is measured is much stronger, and the rate of
convergence is much faster (even after rescaling to account for the different
norms). We discuss the degree to which this is rate-optimal, and how to
further improve this results under some additional assumptions, in Section 8.

###  1.1 Previous Work and Main Contributions

Informally, the main results of our paper are that (i) the popular spectral
embedding algorithm gives reasonably good results for the seriation problem,
and (ii) a simple post-processing step can be added to obtain very good
results. We view this as important reassurance for practitioners: spectral
embedding algorithms are very popular, but there was little theoretical
support for using these algorithms to fit anything but a few small parametric
families of models. Our results provide evidence for the folk belief that
spectral algorithms, with appropriate coarse post-processing, are quite
insensitive to the details of the generating process $w$.

There are many papers in the literature that have either similar-looking
results or similar-looking methods, so we give a quick survey and then
summarize the most interesting differences.

####  1.1.1 Previous Work: Similar Algorithms and Proofs, Different Questions

Spectral embedding algorithms are very popular in many contexts, especially in
the spectral clustering literature (see e.g. [16, 40] and variants such as
[26, 6, 3]). The idea behind all these algorithms is to calculate the first
few eigenvectors of a matrix related to your data matrix, use these to embed
your data in a low-dimensional space, then use a popular clustering algorithm
such as $k$-means to cluster points in this representation. As with the
seriation problem, this is known to give exactly the desired answer in simple
“noiseless" situations.

In “noisy" situations, the most common analyses follow the approach of [41].
In that paper, the authors show that, under appropriate conditions, the
eigenvectors of the observed data matrix will converge to the eigenfunctions
of a certain limiting operator. When this convergence happens, the associated
spectral embedding will also converge to an embedding related to the limiting
operator. One can then bound the difference between the clustering associated
with the observed data and the limiting operator, obtaining a consistency
result.

The proof of our first main bound, Inequality (1.7), follows essentially this
approach. We emphasize two main differences:

  1. 1.

Definition of “correct" answer: In spectral clustering, it is often
straightforward to check that the clustering associated with the limiting
operator is “correct," and sometimes this clustering is even taken as the
definition of a “correct" clustering. In seriation, the correct ordering has
an independent definition in terms of the embedded positions
$v_{1},\ldots,v_{N}$. This means that we must check that the seriation
obtained from the limiting operator actually agrees with this ordering.
Checking this turns out to be non-trivial unless the generating graphon $w$ is
very special, and relating the limiting operator to the embedded positions
takes up most of Section 3.

  2. 2.

Difficulty of problem: In spectral clustering, the “correct" clustering maps
vertices to a finite set $\\{1,2,\ldots,k\\}$, where $k$ does not grow with
the size $N$ of the observed graph. In seriation, the “correct" ordering is a
permutation on $\\{1,2,\ldots,N\\}$. The fact that the seriation problem
attempts to estimate a much higher-dimensional object makes the problem
substantially messier in a few ways. For example, it is often possible to
perfectly recover the correct clustering with a finite sample size even
without precise information about the data-generating process (see e.g. [10]),
but it is usually not possible to perfectly recover the solution to the
seriation problem without having very accurate a priori knowledge of the
graphon $w$ (see e.g. [25]).

We next relate our second main result, Inequality (1.8), to the existing
literature.

Although analysis of the spectral embedding gives useful information, there
are many possible spectral embeddings and it is difficult to find and analyze
the “best" one (see e.g. the discussion of various Laplacians in [41]). An
alternative is to use a simple spectral embedding to obtain an initial rough
solution, then use a simple post-processing algorithm to refine it. This is
known to work well for the stochastic block model, the most popular toy model
for the spectral clustering problem [1].

We take a similar approach here to prove Inequality (1.8). The main novelty is
that we need to develop a post-processing algorithm, as the algorithms used
for spectral clustering are not appropriate. Again, the fact that exact
recovery is impossible adds some complication to our analysis.

####  1.1.2 Previous Work: Similar Questions

Our work was inspired by [36, 19], which studied random graphs that were very
similar, respectively, to the one-parameter graphon
$w(x,y)=p\,\mathbf{1}_{|x-y|\leq 0.5}$ for some $p\in[0,1]$ and the single
graphon $w(x,y)=1-|x-y|$. Like us, [36] follows in the footsteps of [41] and
analyzes the spectral seriation algorithm as a perturbation of a limiting
algorithm. The main differences between our paper and [36, 19] are:

  1. 1.

Inequality (1.7): We deal with a large nonparametric family of models, while
[36, 19] are both restricted to small parametric families. Furthermore, we
allow for sparser graphs than [36] and more noise than [19].

  2. 2.

Inequality (1.8): Using our post-processing algorithm, we obtain sharper
results than previous work (even in the special cases that were focused on).

  3. 3.

Technical differences: Both [36, 19] rely on detailed knowledge of the
spectrum of a limiting operator, which is only possible because they study
rather special families of graph models. Since we deal with the nonparametric
case, we do not have access to this information and need substantially
different arguments.

The results in this paper are also closely related to those in [25], which
share an author. Both papers study a large nonparametric family of graphons.
The main difference is that the present paper analyzes the very popular and
relatively simple spectral seriation algorithm, while [25] develops new and
rather complicated algorithms. As a secondary difference, the assumptions in
our papers are not comparable. In particular, [25] requires that the square of
the adjacency matrix satisfy a weaker version of the Robinsonian property, and
this does not always hold even for uniformly embedded graphons.

Finally, we note that there is a related literature on detecting and
recovering embeddings on the cycle rather than the path, such as [5, 4, 15].
These papers cover a wider range of algorithms than ours, including some
analyses (e.g. of row-correlation) that are quite different from ours.
However, they have essentially the same goal. The largest difference is that,
like [36, 19], the papers [5, 4, 15] are concerned with parametric families of
graph with few parameters, and take advantage of this in developing and
analyzing their algorithms.

####  1.1.3 Previous Work: Summary and Further Reading

Our work belongs to a very large literature on spectral embedding methods, and
a smaller literature on attempting to order or embed vertices on an interval
or cycle. The most important differences are:

  1. 1.

In contrast to most previous work on related questions, we consider a large
nonparametric family of graphons. In particular, while our assumptions appear
more technical than theirs, this is largely because we are considering a much
broader class of models - they are often straightforward to check for the most
common explicit parametric families.

  2. 2.

In contrast to previous work on spectral clustering, we must check that the
embeddings associated with our limiting operators actually give good solutions
to the original problem.

  3. 3.

In contrast to our own previous work [25], we consider both a large
nonparametric families of graphons and a simple, algorithm based on a widely-
used approach.

Finally, we mention recent work on several problems that have a similar feel
to seriation, but which are not directly comparable to our note. Several
papers, such as [18] and [33], have studied what amount to other relaxation of
the condition in Equation (1.1). These relaxations are also reasonable
versions of the “statistical" or “approximate" seriation problem, though the
details are quite different. There have also been many articles on the
closely-related problem of estimating a permutation from pairwise comparisons
(see e.g. [30]) or other estimates related to the entries of a random matrix
whose expected value is a Robinsonian matrix. See the longer paper [25] for a
longer section relating our statistical seriation question to this work.

###  1.2 Paper Guide

In Section 2, we introduce the main pieces of notation used throughout the
rest of the paper and formally state Theorems 2 and 3, stronger versions of
the first and second parts of Theorem 1.

In Section 3, we check that a conjectured limit of the graph Laplacian has
certain good properties - primarily that an associated eigenfunction is
monotone. In Section 4, we check that our graph Laplacian really does converge
to this conjectured limit in a sufficiently strong sense. In Section 5, we put
together the bounds in Section 3 and 4 to prove Theorem 2.

In Section 6, we introduce the new post-processing algorithm and prove Theorem
3.

In Section 7, we check that the assumptions of Theorems 2 and 3 are weaker
than the assumptions of Theorem 1. Finally, we have a short concluding
discussion in Section 8.

##  2 Notation and Main Results

###  2.1 Notation for Random Graphs

Let $w:[0,1]^{2}\to[0,1]$ be a graphon. For each integer $N$, consider the
partition $(\mathcal{I}_{i}^{N})_{i=1,\ldots,N}$ of the interval $[0,1]$
defined by $\mathcal{I}_{1}^{N}=[0,1/N]$ and
$\mathcal{I}_{i}^{N}=((i-1)/N,i/N]$ for $i=2,\ldots,N$. For a given graphon
$w$ we define the model matrix $P^{(N)}\in[0,1]^{N\times N}$ by
$P_{ij}^{(N)}:=w(i/N,j/N)$ for all $i,j\in\left\\{1,2,\ldots,N\right\\}$.

For each $N\in\mathbb{N}$, we consider the sequence of random graphs
$G^{(N)}\sim\rho_{N}w$, where $\rho_{N}\in(0,1]$ is a sequence regulating the
sparsity of the graph. We denote by $\widehat{P}^{(N)}$ the adjacency matrix
of the graph $G^{(N)}$. We recall that, the graph $G^{(N)}$ has $N$ vertices
and the edges are constructed as follows: for each $1\leq i<j\leq N$, we add
an undirected edge between the $i$’th and $j$’th vertices with probability
$\rho_{N}P_{ij}^{(N)}$; these edges are added independently. In other words,

$\widehat{P}^{(N)}_{ij}\stackrel{{\scriptstyle\text{ind}}}{{\sim}}\mathcal{B}\text{ernoulli}\left(\rho_{N}w(\frac{i}{N},\frac{j}{N})\right).$
(2.1)

We view the graphon $\rho_{N}w$ as the limit of the sampling matrices
$\widehat{P}^{(N)}$ under suitable rescaling (see [21] for an explanation of
how this notion of “graph limit" can be made precise). This motivates the
graphon analogue to property (1.4): for $x,y,z\in[0,1]$,

$\displaystyle y<z<x$ $\displaystyle\implies w(x,y)\leq w(x,z),$
$\displaystyle x<y<z$ $\displaystyle\implies w(x,y)\geq w(x,z).$

In analogy to (1.4), we call graphons with this property Robinsonian (these
are also what [7] calls diagonally increasing).

We define the sampled graphon $w_{N}$ by

$w_{N}(x,y):=\sum_{i=1}^{N}\sum_{j=1}^{N}P_{ij}^{(N)}1_{\mathcal{I}_{i}^{N}}(x)1_{\mathcal{I}_{j}^{N}}(y)$

for all $(x,y)\in[0,1]^{2}$.

Similarly, the random graphon $\widehat{w}_{N}$ is defined by:

$\widehat{w}_{N}(x,y):=\sum_{i=1}^{N}\sum_{j=1}^{N}\widehat{P}_{ij}^{(N)}1_{\mathcal{I}_{i}^{N}}(x)1_{\mathcal{I}_{j}^{N}}(y).$

###  2.2 Review of Relevant Facts from Spectral Theory

We next need some basic notation related to operators. We denote by
$L^{2}([0,1])$ the usual Hilbert space on (equivalence classes of) functions
$f\,:\,[0,1]\mapsto\mathbb{R}$, with inner product given by $\langle
f,g\rangle:=\int_{0}^{1}f(x)g(x)dx$ and norm denoted $\left\|f\right\|$. Let
$e\in L^{2}([0,1])$ denote the constant function, $e(x):=1$ for all
$x\in[0,1]$. We use blackboard bold symbols, such as $\mathbb{T}$, to denote
linear operators acting on $L^{2}([0,1])$. The induced (operator) norm is
defined as

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathbb{T}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}:=\sup_{f\in
L^{2}([0,1])\ \mathrm{s.t.}\ \left\|f\right\|=1}\left\|\mathbb{T}f\right\|.$

For a self-adjoint bounded linear operator $\mathbb{T}$ we denote
$\sigma(\mathbb{T})$ the spectrum of $\mathbb{T}$, which consists of the set
of all $\lambda\in\mathbb{R}$ such that $\mathbb{T}-\lambda\mathbb{I}$ is not
bijective. We recall some basic facts about the spectrum (see e.g. [34]). The
spectrum is always non-empty, closed and bounded. We define the discrete
spectrum $\sigma_{\mathrm{d}}(\mathbb{T})$ to be the part of
$\sigma(\mathbb{T})$ which consists of all isolated points with finite
algebraic multiplicity, which means that if $\lambda\in\sigma_{d}(\mathbb{T})$
then $\lambda$ is an eigenvalue of $\mathbb{T}$, that is there is some non-
zero $f\in L^{2}([0,1])$ such that $\mathbb{T}f=\lambda f$, moreover
$\cup_{r=1}^{\infty}\ker((\mathbb{T}-\lambda\mathbb{I})^{r})$ is finite
dimensional. We also define the essential spectrum
$\sigma_{\mathrm{ess}}(\mathbb{T})=\sigma(\mathbb{T})\setminus\sigma_{\mathrm{d}}(\mathbb{T})$.
According to [17] the essential spectrum $\sigma_{\mathrm{ess}}(\mathbb{T})$
is the set of all numbers $\lambda$ in the spectrum $\sigma(\mathbb{T})$ of
$\mathbb{T}$ such that at least one of the following conditions holds:

  1. (i)

the range $R(\mathbb{T}-\lambda\mathbb{I})$ of $\mathbb{T}-\lambda\mathbb{I}$
is not closed;

  2. (ii)

$\lambda$ is a limit point of $\sigma(\mathbb{T})$;

  3. (iii)

$\cup_{r=1}^{\infty}\ker((\mathbb{T}-\lambda\mathbb{I})^{r})$ is infinite
dimensional.

The essential spectrum is always closed, and the discrete spectrum can only
have accumulation points on the boundary to the essential spectrum. For more
results on the spectrum of linear operator we suggest [34]. Denote by
$\lambda_{\max}(\mathbb{T})$ the spectral radius of $\mathbb{T}$,

$\lambda_{\max}(\mathbb{T})=\sup\left\\{\left|\lambda\right|:\lambda\in\sigma(\mathbb{T})\right\\}.$

Note that
$\lambda_{\max}(\mathbb{T})\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathbb{T}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$.

###  2.3 Spectral Theory of the Graphon-Laplacian

We define the graphon-Laplacian operator $\mathbb{L}$ for a given graphon $w$
as

$\displaystyle(\mathbb{L}f)(x)$
$\displaystyle:=\int_{0}^{1}w(x,y)(f(x)-f(y))dy$ (2.2)
$\displaystyle=f(x)d(x)-\int_{0}^{1}w(x,y)f(y)dy,$

where

$d(x)=\int_{0}^{1}w(x,y)dy$

is the degree of $x$. The operator $\mathbb{L}$ for the graphon $w$ is the
analogous of the Laplacian matrix of a graph. Similarly, let $\mathbb{L}_{N}$
and $\widehat{\mathbb{L}}_{N}$ denote the Laplacian operators associated to
graphons $w_{N}$ and $\widehat{w}_{N}$ respectively, as defined in Equation
(2.2).

We make some remarks on the spectrum of $\mathbb{L}$. Note that the operator
$(\mathbb{W}f)(x):=\int_{0}^{1}w(x,y)f(y)dy$ is a Hilbert-Schmidt operator
(see e.g. [34]), thus $\mathbb{W}$ is compact. Nevertheless, $\mathbb{L}$ is
generally not compact since it is the sum of the compact operator $\mathbb{W}$
and the multiplication operator $f(x)\mapsto d(x)f(x)$. It is well known that
adding a compact operator does not change the essential spectrum (see e.g.,
[23]), so the essential spectrum of $\mathbb{L}$ is the same as the essential
spectrum of the multiplication operator $f(x)\mapsto d(x)f(x)$. The essential
spectrum of this operator is known to be the range of the degree function $d$,
i.e., $\sigma_{\mathrm{ess}}(\mathbb{L})=rg(d)$ (see, e.g., [41] ). Note that
the linear operator $\mathbb{L}$ is self-adjoint, bounded and positive.

It is easy to see that $\mathbb{L}e=0$, which means that $\lambda_{1}=0$ is an
eigenvalue of $\mathbb{L}$. In fact it is the smallest eigenvalue, as:

$\langle\mathbb{L}f,f\rangle=\frac{1}{2}\int_{0}^{1}\int_{0}^{1}w(x,y)(f(x)-f(y))^{2}dxdy\geq
0.$ (2.3)

If $\mathbb{L}f=0$ and $w(x,y)$ is strictly positive for almost all $x,y$,
then Inequality (2.3) implies that $f\in\mathrm{Vect}(e)$.222We note here that
any Robinsonian graphon $w$ that satisfies Assumption 2 will satisfy
$w(x,y)>0$ for all $x,y$. For that reason, the calculations in this paragraph
will hold wherever Assumption 2 holds. Thus, $\lambda_{1}=0$ is a simple
eigenvalue. Denote $\lambda_{1}=0<\lambda_{2}<\lambda_{3}<\cdots$ the
eigenvalues of $\mathbb{L}$ in increasing order (i.e.,
$\sigma_{\mathrm{d}}(\mathbb{L})=\\{\lambda_{1}=0,\lambda_{2},\lambda_{3},\ldots\\}$).
We call the Fiedler value the smallest non-zero eigenvalue (i.e.,
$\lambda_{2}$) and any corresponding eigenfunction $\phi$ a Fiedler function.

###  2.4 Statement of Main Results

The main results relies on the following conditions on the graphon:

######  Assumption 1 (Lipschitz graphon).

There exists a constant $K>0$ such that

$\left|w(x,y)-w(x^{\prime},y^{\prime})\right|\leq
K(\left|x-x^{\prime}\right|+\left|y-y^{\prime}\right|)$

for all pairs $(x,y)\in[0,1]^{2},(x^{\prime},y^{\prime})\in[0,1]^{2}$.

######  Assumption 2 (Differentiable graphon).

The partial derivative $\partial w(x,\cdot)/\partial x$ both exists and is
non-zero almost everywhere.

######  Remark 2.1.

We note that Assumption 2 is violated by the popular toy graphon model
$w(x,y)=p\mathbb{I}_{|x-y|\leq 0.5}$, and so Theorem 2 will not apply as-
written to these models. This is somewhat unsatisfying, as this model and very
similar ones were studied in [36, 5, 4].

Fortunately, this problem is easy to fix, and our arguments were written with
this in mind. The proof of Theorem 2 only uses Assumption 2 inside of the
proofs of the intermediate results Theorems 4 and 5. Thus, both the conclusion
and the proof of Theorem 2 remain correct if we assume the conclusions of
Theorems 4 and 5 directly.

More precisely, Theorem 2 remains true as stated if we substitute the
following pair of assumptions for Assumption 2:

  1. 1.

There exists a Fiedler function $\phi\in\mathcal{C}^{1}([0,1])$ and $L>0$ such
that $\inf_{x\in[0,1]}\phi^{\prime}(x)=L$ (this corresponds to Theorem 4).

  2. 2.

The eigenspace corresponding to eigenvalue $\lambda_{2}$ is one-dimensional
(this corresponds to Theorem 5).

These two assumptions can be checked directly for the toy model
$w(x,y)=p\mathbb{I}_{|x-y|\leq 0.5}$, and we expect this to be possible for
other very symmetric models. Due to perturbation bounds for the spectrum of
operators, it is also possible to check this condition for sufficiently small
perturbations of such symmetric models.

######  Assumption 3.

The derivative $d^{\prime}(x)$ exists for all $x\in[0,1]$ and the set
$N:=\left\\{x\in[0,1]:d^{\prime}(x)=0\right\\}$ is countable.

######  Assumption 4.

Let

$\mathcal{H}=\left\\{f\in L^{2}([0,1]):\int_{0}^{1}f(t)dt=0\text{ and
}\int_{0}^{1}f^{2}(t)dt=1\right\\},$

and $\mathbb{L}$ be the graphon-Laplacian operator associated with $w$. Assume
that

$\inf_{f\in\mathcal{H}}\langle\mathbb{L}f,f\rangle<\inf_{x\in[0,1]}d(x).$

Note that $\inf(\sigma_{\mathrm{ess}}(\mathbb{L}))=\inf_{x\in[0,1]}d(x)$.
Applying this with the mini-max principle for self-adjoint operators (see
[39]), Assumption 4 ensures that the Fiedler value satisfies
$\lambda_{2}<\inf_{x\in[0,1]}d(x)$.

Although these assumptions may seem complicated, especially Assumption 4, all
“nice” graphons in the sense of Definition 1.2 satisfy these assumptions. For
the proof of this result, see Section 7.

Our main result is the following consistency result for spectral seriation
algorithm:

######  Theorem 2.

Fix $\tau\in[0,1)$, $\eta<\frac{1-\tau}{3}$ and $\varepsilon\in(0,1)$. Let
$\rho_{N}=N^{-\tau}$. Fix a graphon $w$ satisfying Assumptions 1 to 4.
Consider a family of random graphs $\\{G^{(N)}\\}_{N\in\mathbb{N}}$ where
$G^{(N)}\sim\rho_{N}w$ according to Equation (2.1). Let $\hat{\sigma}^{(N)}$
be the output of Algorithm 1 with input $G^{(N)}$. Then there exists a
positive constants $C=C(w)$ and an integer
$N_{0}=N_{0}(w,\tau,\eta,\varepsilon)$ so that

$\mathbb{P}\left(\left\|\hat{\sigma}^{(N)}-id_{N}\right\|_{1}\leq
CN^{2-\eta}\right)\geq 1-\varepsilon$ (2.4)

for all $N\geq N_{0}$.

Moreover, for any $\gamma>1$ there exists a positive constants
$C^{\prime}=C^{\prime}(w)$ and
$N^{\prime}_{0}=N^{\prime}_{0}(w,\tau,\eta,\gamma)$ so that

$\mathbb{P}\left(\left\|\hat{\sigma}^{(N)}-id_{N}\right\|_{1}\leq
C^{\prime}N^{2-\eta}\right)\geq 1-\varepsilon_{\gamma}(N)$ (2.5)

for all $N\geq N^{\prime}_{0}$.

Note that Inequality (2.5) looks very similar to Inequality (2.4) if we choose
$\varepsilon=\varepsilon_{\gamma}(N)$. Although the two are very similar, the
result in (2.5) can not be obtained as a consequence of (2.4). In fact, the
values of $N$ for which the first inequality is satisfied depend on $N_{0}$
which itself depend on $\varepsilon$.

With appropriate post-processing and some additional assumptions, we can
achieve tighter estimates. For fixed $0<\alpha<0.5$, define the functions
$\Psi_{R},\Psi_{L}$ by

$\Psi_{R}(x):=\int_{1-\alpha}^{1}w(x,y)dy\,\text{ and
}\,\Psi_{L}(x):=\int_{0}^{\alpha}w(x,y)dy.$ (2.6)

These functions count the expected number of neighbours in the right- and
left-most $\alpha$ percent of vertices. Assume:

######  Assumption 5.

There exists some constants $0<\alpha<\beta<1/2$ such that:

  1. 1.

Mean distance inequality:

$\inf_{x\in[1-\alpha,1]}\Psi_{R}(x)>\Psi_{R}(1-\beta),\qquad\inf_{x\in[0,\alpha]}\Psi_{L}(x)>\Psi_{L}(\beta),$
(2.7)

and

  2. 2.

Distinguishability inequality: There exists some $d_{1}>0$ such that

$\\{\min(|x-z|,|y-z|)\geq\frac{\beta-\alpha}{2}\\}\Rightarrow\\{|w(y,z)-w(x,z)|\geq
d_{1}|x-y|\\}$ (2.8)

for $x,y,z\in[0,1]$.

This assumption holds also for all graphons that are “nice” in the sense of
Definition 1.2. For the proof of this result, see Section 7. When a graphon
satisfies Inequality (2.7) for some pair $(\alpha,\beta)$ and also satisfies
our other assumptions, it is possible to quickly find the pair
$(\alpha,\beta)$; see Remark 6.7.

The following theorem gives a much faster convergence rate under Assumption 5:

######  Theorem 3.

Let $\rho_{N}=1$, fix a graphon $w$ satisfying Assumptions 1 to 5. Consider a
family of random graphs $\\{G^{(N)}\\}_{N\in\mathbb{N}}$ where $G^{(N)}\sim w$
according to Equation (2.1). Let $\hat{\sigma}^{(N)}$ be the output of
Algorithm 3 with input $G^{(N)}$ and parameters $\alpha,\beta$ as in
assumption 5. Then for any $\gamma>1$ and $\epsilon>0$ there exists a positive
constant $\delta=\delta(w,\gamma,\epsilon)$ and an integer
$N_{0}=N_{0}(w,\gamma,\epsilon)$ so that

$\mathbb{P}\left(\left\|\hat{\sigma}^{(N)}-id_{N}\right\|_{\infty}\leq\epsilon\sqrt{N\log^{\gamma}(N)}\right)\geq
1-\varepsilon_{\gamma}^{\delta}(N)$

for all $N\geq N_{0}$.

######  Remark 2.2.

Although we give specific functions $\Psi_{R},\Psi_{L}$ in Equation (2.6), our
proofs only rely on three properties of this pair of functions: they (i)
satisfy Assumption 5, (ii) have derivatives bounded away from 0 on
$[0,1-\beta]$ and $[\beta,1]$ respectively, and (iii) can be estimated with
error roughly $O\left(\sqrt{\frac{\log(N)}{N}}\right)$ from a graph of size
$N$. We state our results in terms of the specific functions
$\Psi_{R},\Psi_{L}$ because it is easy to (i) compute them and (ii) verify our
assumptions for the most popular graphon families.

##  3 Properties of the Fiedler value and the Fiedler function

In this section we establish basic facts about the spectrum of the graphon-
Laplacian operator $\mathbb{L}$. Throughout this section, we fix a graphon $w$
satisfying Assumptions 1 to 4, then define $\mathbb{L}$ as in Equation (2.2).
We also denote by $\lambda_{2}$ its Fiedler eigenvalue. For $x\in\mathbb{R}$,
define $D_{x}=d^{-1}(\\{x\\})$. The following lemma ensures that most of the
eigenfunctions of $\mathbb{L}$ are $\mathcal{C}^{1}$.

######  Lemma 3.1.

Let $\lambda$ be any eigenvalue of $\mathbb{L}$ and $f$ any eigenfunction
associated to the eigenvalue $\lambda$. Then the set $D_{\lambda}$ is discrete
and $f$ is $\mathcal{C}^{1}$ in $D_{\lambda}^{c}$.

In particular, if $\lambda\notin rg(d)$, then $f$ is $\mathcal{C}^{1}$ in
$[0,1]$.

###### Proof.

First we show that under Assumption 3 the set $D_{\lambda}$ is discrete. Let
$N=\\{x\in[0,1]:d^{\prime}(x)=0\\}$ as in Assumption 3. Since $N$ is discrete,
it is enough to show that $D^{\prime}=D_{\lambda}\setminus N$ is discrete. Let
$x\in D^{\prime}$, so that $d(x)=\lambda$ and $d^{\prime}(x)\neq 0$. Moreover,
$d(x+h)-\lambda=d(x+h)-d(x)=d^{\prime}(x)h+o(h)$, hence $d(y)\neq\lambda$ for
all $y\neq x$ in some neighborhood $U_{x}$ of $x$. Consequently every point
$x\in D^{\prime}$ has a neighborhood $U_{x}$ such that $D^{\prime}\cap
U_{x}=\\{x\\}$ as required.

Now take $x\in D_{\lambda}^{c}$ and $\Delta>0$ such that $x+\delta\notin
D_{\lambda}$ for all $\delta\in[0,\Delta]$. Recalling the definition of the
operator $\mathbb{L}$ from Equation (2.2),

$f(x)d(x)-\int_{0}^{1}f(y)w(x,y)dy=\lambda f(x).$

Plugging $x$ and $x+\delta$ in the previous equation and taking the difference
yields, for $\delta\in[0,\Delta]$ sufficiently small,

$\displaystyle\frac{f(x+\delta)-f(x)}{\delta}$
$\displaystyle=\frac{1}{d(x+\delta)-\lambda}\left(\int_{0}^{1}(f(y)-f(x))\left(\frac{w(x+\delta,y)-w(x,y)}{\delta}\right)dy\right)$
$\displaystyle\xrightarrow[\delta\to
0]{}~{}\frac{1}{d(x)-\lambda}\left(\int_{0}^{1}(f(y)-f(x))\frac{\partial
w(x,y)}{\partial x}\right)dy.$

For the integral convergence, we apply the dominated convergence theorem. This
is justified by the fact that, by Assumption 2, the partial derivative exists
everywhere, and by Assumption 1, we have that $(w(x+\delta,y)-w(x,y))/\delta$
is uniformly bounded by $K<\infty$. Therefore $f$ is differentiable in
$D_{\lambda}^{c}$ and for all $x\in D_{\lambda}^{c}$

$f^{\prime}(x)=\frac{1}{d(x)-\lambda}\left(\int_{0}^{1}(f(y)-f(x))\frac{\partial
w(x,y)}{\partial x}\right)dy.$ (3.1)

By a similar argument we can show that $f^{\prime}(x+\delta)\to f^{\prime}(x)$
as $\delta\to 0$, consequently $f$ is $\mathcal{C}^{1}$ on $D_{\lambda}^{c}$.

∎

Now we introduce the two theorems whose proofs will take the rest of the
section:

######  Theorem 4.

There exists a Fiedler function $\phi\in\mathcal{C}^{1}([0,1])$ and $L>0$ such
that $\inf_{x\in[0,1]}\phi^{\prime}(x)=L$.

######  Theorem 5.

The eigenspace corresponding to eigenvalue $\lambda_{2}$ is one-dimensional.

To prove Theorem 4, we introduce the linear operator

$(\mathbb{M}f)(x)=d(x)f(x)-\int_{0}^{1}\int_{0}^{1}\left(f(z)\frac{\partial
w(x,y)}{\partial x}\mathbf{1}_{\\{x\leq z\leq y\\}}\right)dzdy.$ (3.2)

Note that similarly to $\mathbb{L}$, the operator $\mathbb{M}$ is a self-
adjoint, positive and bounded operator. Moreover, it is the sum of a
multiplication operator and a compact operator, which means that
$\sigma_{\mathrm{ess}}(\mathbb{M})=rg(d)$. We will show that its spectral data
is closely related to that of $\mathbb{L}$:

######  Lemma 3.2.

The eigenvalues of $\mathbb{M}$ are $\lambda_{2}<\lambda_{3}<\cdots$, that is
the spectrum of $\mathbb{M}$ satisfies
$\sigma(\mathbb{M})=\sigma(\mathbb{L})\setminus\\{0\\}$. Moreover, for all
$\lambda\neq 0$, $(\lambda,f)$ is an eigenvalue-eigenfunction pair of
$\mathbb{L}$ if and only if there exists a function $g$ so that
$f^{\prime}(x)=g(x)$ for all $x\in D_{\lambda}^{c}$ and $(\lambda,g)$ is an
eigenvalue-eigenfunction pair of $\mathbb{M}$. 333We have seen already that
$D_{\lambda}$ is countable so in fact $f^{\prime}$ exists almost everywhere.
This means that the values of $f^{\prime}$ where they exist will uniquely
determine the element of $L^{2}([0,1])$ that is an eigenvalue-eigenfunction
pair of $\mathbb{M}$.

###### Proof.

Let $(\lambda,f)$ be an eigenvalue-eigenfunction pair of $\mathbb{L}$ for
which $\lambda\neq 0$. By Lemma 3.1, $f$ is differentiable at all $x\in
D_{\lambda}^{c}$, and by Assumption 2, the partial derivatives of $w$ exist
almost everywhere. This justifies the calculation

$\displaystyle(\mathbb{L}f)(x)=\lambda f(x)$ $\displaystyle\Rightarrow\lambda
f(x)=f(x)d(x)-\int_{0}^{1}f(y)w(x,y)dy$ $\displaystyle\Rightarrow\lambda
f^{\prime}(x)=f^{\prime}(x)d(x)+f(x)d^{\prime}(x)-\int_{0}^{1}f(y)\frac{\partial
w(x,y)}{\partial x}dy$ $\displaystyle\Rightarrow\lambda
f^{\prime}(x)=f^{\prime}(x)d(x)-\int_{0}^{1}(f(y)-f(x))\frac{\partial
w(x,y)}{\partial x}dy$ $\displaystyle\Rightarrow\lambda
f^{\prime}(x)=f^{\prime}(x)d(x)-\int_{0}^{1}\int_{0}^{1}\left(f^{\prime}(z)\frac{\partial
w(x,y)}{\partial x}\mathbf{1}_{\\{x\leq z\leq y\\}}\right)dzdy$
$\displaystyle\Rightarrow\lambda f^{\prime}(x)=(\mathbb{M}f^{\prime})(x).$

Conversely, let $(\lambda,g)$ be an eigenvalue-eigenfunction of $\mathbb{M}$.
Then for all $x\notin D_{\lambda}$, straightforward algebra gives

$g(x)=\frac{1}{d(x)-\lambda}\int_{0}^{1}\int_{0}^{1}\left(\frac{\partial
w(x,y)}{\partial x}g(z)\mathbf{1}_{\\{x\leq z\leq y\\}}\right)dzdy.$

Applying the dominated convergence theorem (this can be used because the
partial derivative of $w$ satisfies $\left|\frac{\partial w(x,y)}{\partial
x}\right|\leq K$ when it exists, by Assumption 1), we can see that $g$ is
continuous on $D_{\lambda}^{c}$.

Define $f(x)=\int_{0}^{x}g(t)dt$ for all $x\in[0,1]$. Then
$f^{\prime}(x)=g(x)$ for $x\in D_{\lambda}^{c}$, and furthermore

$\displaystyle(\mathbb{M}g)(x)=\lambda g(x)$ $\displaystyle\Rightarrow
d(x)f^{\prime}(x)+\int_{0}^{1}(f(x)-f(y))\frac{\partial w(x,y)}{\partial
x}dy=\lambda f^{\prime}(x)$
$\displaystyle\Rightarrow\int_{0}^{1}\left(\frac{\partial(f(x)-f(y))}{\partial
x}w(x,y)+(f(x)-f(y))\frac{\partial w(x,y)}{\partial x}\right)dy=\lambda
f^{\prime}(x)$ $\displaystyle\Rightarrow\int_{0}^{1}\frac{\partial}{\partial
x}\left((f(x)-f(y))w(x,y)\right)dy=\lambda f^{\prime}(x)$
$\displaystyle\Rightarrow\int_{0}^{1}(f(x)-f(y))w(x,y)dy=\lambda f(x)$
$\displaystyle\Rightarrow(\mathbb{L}f)(x)=\lambda f(x)$

as required.

Finally, we check that $0\notin\sigma(\mathbb{M})$. To see this, consider a
function $g$ such that $\mathbb{M}g=0$. Then by the above calculation
$\mathbb{L}f=0$, where $f(x)=\int_{0}^{x}g(t)dt$. Recalling from the paragraph
following (2.3) that $\lambda_{1}$ is a simple eigenvalue of $\mathbb{L}$,
this implies $f\in\mathrm{Vect}(e)$ and so $g=f^{\prime}=0$. We conclude that
$\sigma(\mathbb{M})=\sigma(\mathbb{L})\setminus\\{0\\}$. ∎

######  Lemma 3.3.

There exists $f^{*}\in L^{2}([0,1])$ such that
$\mathbb{M}f^{*}=\lambda_{2}f^{*}$ and $f^{*}(x)>0$ for all $x\in[0,1]$.

###### Proof.

Fix $\alpha>1+\lambda_{\max}(\mathbb{M})$. Define the operator
$\mathbb{M}_{\alpha}=\alpha\mathbb{I}-\mathbb{M}$ with $\mathbb{I}$ the
identity operator. It is obvious that
$\sigma(\mathbb{M}_{\alpha})=\alpha-\sigma(\mathbb{M})$, hence
$\lambda_{\max}(\mathbb{M}_{\alpha})>0$.

We next claim that $\mathbb{M}_{\alpha}$ sends the cone of nonnegative
functions,

$K=\left\\{f\in L^{2}([0,1]):f(x)\geq 0\ \text{for all}\ x\in[0,1]\right\\},$

to itself. To see this, we examine the following expression for $f\in K$ and
$x\in[0,1]$:

$\displaystyle(\mathbb{M}_{\alpha}f)(x)=(\alpha-d(x))f(x)+\int_{0}^{1}\left(\int_{x}^{y}f(z)dz\right)\frac{\partial
w(x,y)}{\partial x}dy.$

The first term $(\alpha-d(x))f(x)$ is non-negative since $\alpha>1\geq d(x)$.
For the second term, if $y>x$ then $\int_{x}^{y}f(z)dz\geq 0$ and
$\frac{\partial w(x,y)}{\partial x}\geq 0$ (because $w$ is Robinsonian).
Similarly, if $y<x$, both of these are negative and so their product is
positive. Hence, in either case,
$\left(\int_{x}^{y}f(z)dz\right)\frac{\partial w(x,y)}{\partial x}\geq 0$ for
all $y$. Therefore $\mathbb{M}_{\alpha}f\in K$, as required.

Consequently $\mathbb{M}_{\alpha}$ is a positive, bounded and self-adjoint
linear operator, with $\mathbb{M}_{\alpha}K\subseteq K$. The essential
spectrum of $\mathbb{M}_{\alpha}$ is
$\sigma_{\mathrm{ess}}(\mathbb{M}_{\alpha})=\alpha-rg(d)$ (because
$\sigma_{\mathrm{ess}}(\mathbb{M})=rg(d)$). Since
$\lambda_{\max}(\mathbb{M}_{\alpha})$ is the largest eigenvalue of
$\mathbb{M}_{\alpha}$ and
$\sigma(\mathbb{M}_{\alpha})=\alpha-\sigma(\mathbb{M})$, additionally
$\sigma(\mathbb{M})=\sigma(\mathbb{L})\setminus\\{0\\}$ by Lemma 3.2 and so
$\lambda_{\max}(\mathbb{M}_{\alpha})=\alpha-\lambda_{2}$.

In [17] the authors showed a version of the Krein-Rutman theorem for non-
compact operators, which applies here. In fact according to Theorem 1 from
[17], there exists $f^{*}\in K\setminus\\{0\\}$ such that
$\mathbb{M}_{\alpha}f^{*}=\lambda_{\max}(\mathbb{M}_{\alpha})f^{*}$, note also
that the conditions of this theorem are satisfied since
$\lambda_{\max}(\mathbb{M}_{\alpha})=\alpha-\lambda_{2}>\alpha-\min_{x\in[0,1]}d(x)=\sup\sigma_{\mathrm{ess}}(\mathbb{M}_{\alpha})$
according to Assumption 4. Note this is equivalent to
$\mathbb{M}f^{*}=\lambda_{2}f^{*}$ as required.

We must now check that $f^{*}(x)>0$ for all $x\in[0,1]$. Assume not; then
there exists some $a\in[0,1]$ for which $f^{*}(a)=0$. We then have
$(\mathbb{M}f^{*})(a)=\lambda_{2}f^{*}(a)=0$, which yields

$\int_{0}^{1}\left(\int_{a}^{y}f^{*}(z)dz\right)\frac{\partial
w(a,y)}{\partial x}dy=0.$ (3.3)

Thus, for almost all $y\in[0,1]$,

$\left(\int_{a}^{y}f^{*}(z)dz\right)\frac{\partial w(a,y)}{\partial x}=0.$
(3.4)

By Assumption 2, $\frac{\partial w(a,y)}{\partial x}\neq 0$ almost everywhere,
so Equation (3.4) implies $\int_{a}^{y}f^{*}(z)dz=0$ a.e. This means that
$f^{*}=0$ in $L^{2}([0,1])$, which contradicts the fact that $f^{*}$ is an
eigenfunction of $\mathbb{M}$. We conclude that no such $a\in[0,1]$ exists, so
$f^{*}(x)>0$ for all $x\in[0,1]$ as desired. ∎

######  Corollary 3.4.

The Fiedler value $\lambda_{2}\notin rg(d)$.

###### Proof.

Assume not, and let $\lambda_{2}=d(a)$ for some $a$. Let $f^{*}$ be as in the
statement of Lemma 3.3. Since $\mathbb{M}f^{*}(a)=\lambda_{2}f^{*}(a)$, we get

$\int_{0}^{1}\left(\int_{a}^{y}f^{*}(z)dz\right)\frac{\partial
w(a,y)}{\partial x}dy=0.$

Following the argument in the proof of Lemma 3.3 from Equation (3.3), this
implies $f^{*}=0$ in $L^{2}([0,1])$. But we have already seen that
$f^{*}(x)>0$ for all $x\in[0,1]$, so this is a contradiction. ∎

We can now prove Theorem 4:

###### Proof of Theorem 4.

By Corollary 3.4, $\lambda_{2}\notin rg(d)$, and so by Lemma 3.1 all
eigenfunctions of $\mathbb{L}$ associated with $\lambda_{2}$ are
$\mathcal{C}^{1}([0,1])$. Let $f^{*}$ be as in the statement of Lemma 3.3, and
define $\phi(x)=\int_{0}^{x}f^{*}(t)\mathrm{d}t$ for all $x\in[0,1]$. By Lemma
3.2 we know that $\mathbb{L}\phi=\lambda_{2}\phi$, thus
$\phi\in\mathcal{C}^{1}([0,1])$ is a Fiedler function with
$\phi^{\prime}(x)=f^{*}(x)>0$ for all $x\in[0,1]$.

Finally, since $\phi\in\mathcal{C}^{1}([0,1])$ and $\phi^{\prime}(x)>0$ for
all $x\in[0,1]$, we have $\inf_{x\in[0,1]}\phi^{\prime}(x)>0$. ∎

Finally, we present the proof of Theorem 5:

###### Proof of Theorem 5.

Let $\phi$ as in the statement of Theorem 4. We prove Theorem 5 by
contradiction. If the eigenspace is not one-dimensional, there exists some
other Fiedler function $\varphi\notin\mathrm{Vect}(\phi)$. Since
$\lambda_{2}\notin rg(d)$ by Corollary 3.4, we have that
$\varphi\in\mathcal{C}^{1}([0,1])$ as well. Let $a$ be such that

$\frac{\varphi^{\prime}(a)}{\phi^{\prime}(a)}=\min_{x\in[0,1]}\left(\frac{\varphi^{\prime}(x)}{\phi^{\prime}(x)}\right).$

Put $\psi=\phi^{\prime}(a)\varphi-\varphi^{\prime}(a)\phi$, so that $\psi$ is
an other Fiedler function and satisfies $\psi^{\prime}(x)\geq 0$ for all
$x\in[0,1]$ and $\psi^{\prime}(a)=0$. But this implies
$\mathbb{M}\psi^{\prime}(a)=\lambda_{2}\psi^{\prime}(a)=0$. Following the
argument in the proof of Lemma 3.3 from Equation (3.3), this implies that
$\psi=0$ in $L^{2}([0,1])$, which is a contradiction. ∎

##  4 Convergence of the Fiedler eigenfunction

We follow the conventions established at the start of Section 3, fixing a
graphon $w$ satisfying Assumptions 1 to 4 and defining the Laplacian
$\mathbb{L}$ as in Equation (2.2). We will also use the notation for random
graphs and their associated objects from Section 2.

In this section, we will check that the observed graph Laplacian converges to
the limiting Laplacian $\mathbb{L}$ in a strong enough sense to recover
spectral data about the Fiedler eigenfunction.

###  4.1 Convergence of Laplacian operator

The results in this section are very similar to the results in the paper [3].
In this section we prove that two approximations to $\mathbb{L}$ converge
quickly. But first, we set some notations. Define
$d_{\mathrm{MAX}}:=\max_{x\in[0,1]}d(x)$ and similarly
$d_{\mathrm{MAX}}^{(N)}:=\max_{i=1}^{N}\left(\sum_{j=1}^{N}P_{ij}^{(N)}\right)$.
Let $K$ be as in Assumption 1 and let $\gamma>1$. Define the integers
$N_{1}(w,\tau,\varepsilon)$ and $N^{\prime}_{1}(w,\tau,\gamma)$ as follows:

$\displaystyle N_{1}(w,\tau,\varepsilon)$
$\displaystyle=\min\left\\{n\in\mathbb{N}\,:\,N\geq n\Rightarrow
d_{\mathrm{MAX}}\geq\frac{4\log\left(4N/\varepsilon\right)}{9\rho_{N}N}+\frac{2K}{N}\right\\},$
(4.1) $\displaystyle N^{\prime}_{1}(w,\tau,\gamma)$
$\displaystyle=\min\left\\{n\in\mathbb{N}\,:\,N\geq n\Rightarrow
d_{\mathrm{MAX}}\geq\frac{4\log\left(4N/\varepsilon_{\gamma}(N)\right)}{9\rho_{N}N}+\frac{2K}{N}\right\\}.$
(4.2)

Recall that $\varepsilon_{\gamma}(N)=\exp{\left(-\log^{\gamma}(N)\right)}$.
Note that both $N_{1}$ and $N^{\prime}_{1}$ are well defined. In fact the term
$\frac{4\log\left(2N/\varepsilon\right)}{9\rho_{N}N}$ goes to 0 as
$N\to\infty$ and we also have

$\frac{4\log\left(4N/\varepsilon_{\gamma}(N)\right)}{9\rho_{N}N}=\frac{4\left(\log(4N)+\log^{\gamma}(N)\right)}{9\rho_{N}N}$

which goes to 0 as $N\to\infty$.

In order to prove the convergence of the Laplacian operator we need the
following simple technical lemma:

######  Lemma 4.1.

Fix $\varepsilon\in(0,1)$, $\gamma>1$. Put $N_{1}=N_{1}(w,\tau,\varepsilon)$
and $N^{\prime}_{1}=N^{\prime}_{1}(w,\tau,\gamma)$. Then for all $N\geq
N_{1}(w,\tau,\varepsilon)$ we have

$d_{\mathrm{MAX}}^{(N)}\geq\frac{4\log\left(4N/\varepsilon\right)}{9\rho_{N}}.$

Similarly, for all $N\geq N^{\prime}_{1}$ we have

$d_{\mathrm{MAX}}^{(N)}\geq\frac{4\log\left(4N/\varepsilon_{\gamma}(N)\right)}{9\rho_{N}}.$

###### Proof.

For $N\geq N_{1}$, let $x\in\mathcal{I}_{i}^{N}$ for some $i\in[N]$. Then

$\displaystyle\left|d(x)-d_{N}(x)\right|$
$\displaystyle=\left|\int_{0}^{1}\left(w(x,y)-w_{N}(x,y)\right)dy\right|$
$\displaystyle\leq\sum_{j=1}^{N}\int_{\mathcal{I}_{j}^{N}}\left|w(x,y)-w(\frac{i}{N},\frac{j}{N})\right|dy$
$\displaystyle\leq\frac{2K}{N},$

where the inequality from line two to line three follows from Assumption 1.
Therefore $d_{N}(x)\geq d(x)-\frac{2K}{N}$, so

$\displaystyle\max_{x\in[0,1]}d_{N}(x)$ $\displaystyle\geq
d_{\mathrm{MAX}}-\frac{2K}{N}$
$\displaystyle\geq\frac{4\log(4N/\varepsilon)}{9\rho_{N}N}.$

On the other hand,

$\displaystyle\max_{i=1}^{N}\left(\sum_{j=1}^{N}P_{ij}^{(N)}\right)$
$\displaystyle=N\max_{x\in[0,1]}\left(d_{N}(x)\right)$
$\displaystyle\geq\frac{4\log(4N/\varepsilon)}{9\rho_{N}}.$

As required. The proof of the second inequality for $N\geq
N^{\prime}_{1}(w,\tau,\gamma)$ is identical to the previous proof (replace
$\varepsilon$ by $\varepsilon_{\gamma}(N)$). ∎

######  Theorem 4.2 (Convergence of graphon Laplacian).

Let $K$ be as in Assumption 1. Then

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathbb{L}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq\frac{4K}{N}.$
(4.3)

Moreover, for all $\varepsilon\in(0,1)$ and all $N\geq
N_{1}(w,\tau,\varepsilon)$ as in Equation (4.1),

$\mathbb{P}\left({\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
4\sqrt{\frac{\log(4N/\varepsilon)}{\rho_{N}N}}+\frac{4K}{N}\right)\geq
1-\varepsilon.$ (4.4)

Additionally, for all $\gamma>1$ the same inequality holds for all $N\geq
N^{\prime}_{1}(w,\tau,\gamma)$ if we replace $\varepsilon$ by
$\varepsilon_{\gamma}(N)$, where $N^{\prime}_{1}$ is defined in (4.2).

###### Proof of Theorem 4.2.

We prove the two inequalities (4.3) and (4.4) in order.

###### Proof of Inequality (4.3).

Let $f\in L^{2}([0,1])$ such that $\left\|f\right\|=1$. Then

$\displaystyle\left\|\mathbb{L}_{N}f-\mathbb{L}f\right\|^{2}$
$\displaystyle=\int_{0}^{1}\left(\mathbb{L}_{N}f-\mathbb{L}f\right)^{2}(x)dx$
$\displaystyle=\int_{0}^{1}\left(\int_{0}^{1}(f(x)-f(y))(w_{N}(x,y)-w(x,y))dy\right)^{2}dx$
$\displaystyle\leq\int_{0}^{1}\left(\int_{0}^{1}(f(x)-f(y))^{2}dy\right)\left(\int_{0}^{1}(w_{N}(x,y)-w(x,y))^{2}dy\right)dx$
$\displaystyle=\sum_{i=1}^{N}\int_{\mathcal{I}_{i}^{N}}\left(\int_{0}^{1}(f(x)-f(y))^{2}dy\right)\left(\int_{0}^{1}(w_{N}(x,y)-w(x,y))^{2}dy\right)dx,$
(4.5)

where from line two to three we used Cauchy-Schwartz inequality. For fixed
$i\in[N]$ and $x\in\mathcal{I}_{i}^{N}$,

$\displaystyle\int_{0}^{1}(w_{N}(x,y)-w(x,y))^{2}dy$
$\displaystyle=\sum_{j=1}^{N}\int_{\mathcal{I}_{j}^{N}}(w(\frac{i}{N},\frac{j}{N})-w(x,y))^{2}dy$
$\displaystyle\leq\sum_{j=1}^{N}\int_{\mathcal{I}_{j}^{N}}K^{2}\left(\left|\frac{i}{N}-x\right|+\left|\frac{j}{N}-y\right|\right)^{2}dy$
$\displaystyle\leq\sum_{j=1}^{N}\int_{\mathcal{I}_{j}^{N}}\frac{4K^{2}}{N^{2}}dy$
$\displaystyle=\frac{4K^{2}}{N^{2}}.$

Furthermore,

$\displaystyle\int_{0}^{1}(f(x)-f(y))^{2}dy$
$\displaystyle\leq\int_{0}^{1}2(f(x)^{2}+f(y)^{2})dy$
$\displaystyle=2f(x)^{2}+2.$

Applying the last two calculations with Inequality (4.5),

$\displaystyle\left\|\mathbb{L}_{Nf}-\mathbb{L}f\right\|^{2}$
$\displaystyle\leq\frac{8K^{2}}{N^{2}}\sum_{i=1}^{N}\int_{\mathcal{I}_{i}^{N}}\left(f(x)^{2}+1\right)dx$
$\displaystyle=\frac{16K^{2}}{N^{2}}.$

This immediately implies (4.3). ∎

###### Proof of Inequality (4.4).

From the triangle inequality and Inequality (4.3),

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}_{N}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}+{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathbb{L}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}_{N}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}+\frac{4K}{N}.$
(4.6)

Since both $\widehat{\mathbb{L}}_{N}$ and $\mathbb{L}_{N}$ have finite rank,
it is not hard to see that

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}_{N}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle=\frac{1}{N}\lambda_{\mathrm{max}}\left(\rho_{N}^{-1}\widehat{L}^{(N)}-L^{(N)}\right)$
$\displaystyle=\frac{\rho_{N}^{-1}}{N}\left\|\widehat{L}^{(N)}-\rho_{N}L^{(N)}\right\|$
$\displaystyle\leq\frac{\rho_{N}^{-1}}{N}\left(\left\|\widehat{D}^{(N)}-\rho_{N}D^{(N)}\right\|+\left\|\widehat{P}^{(N)}-\rho_{N}P^{(N)}\right\|\right).$
(4.7)

Fix $N\geq N_{1}(w,\tau,\varepsilon)$ as in (4.1), then the maximum expected
degree of the random graph $G^{(N)}$ is
$\rho_{N}d_{\mathrm{MAX}}^{(N)}\geq\frac{4}{9}\log(4N/\varepsilon)$. Applying
Theorem 1 of [8],

$\mathbb{P}\left(\left\|\widehat{P}^{(N)}-\rho_{N}P^{(N)}\right\|\leq\sqrt{4\rho_{N}d_{\mathrm{MAX}}^{(N)}\log(4N/\varepsilon)}\right)\geq
1-\frac{\varepsilon}{2}.$ (4.8)

Now we give a similar bound for
$\left\|\widehat{D}^{(N)}-\rho_{N}D^{(N)}\right\|$. Let
$\Delta^{(N)}=\widehat{D}^{(N)}-\rho_{N}D^{(N)}$ and
$X^{(N)}=\widehat{P}^{(N)}-\rho_{N}P^{(N)}$.

We note that

$\sum_{j}\mathbb{V}\mathrm{ar}\left(X_{ij}\right)=\sum_{j}\rho_{N}P_{ij}^{(N)}(1-\rho_{N}P_{ij}^{(N)})\leq\rho_{N}\sum_{j}P_{ij}^{(N)}\leq\rho_{N}d_{\mathrm{MAX}}^{(N)}.$
(4.9)

Then by Bernstein’s inequality, for each $t>0$

$\displaystyle\mathbb{P}\left(|\Delta_{i}^{(N)}|>t\right)$
$\displaystyle=\mathbb{P}\left(\left|\sum_{j=1}^{N}X_{ij}^{(N)}\right|>t\right)$
$\displaystyle\leq
2\exp{\left(\frac{-\frac{1}{2}t^{2}}{\sum_{j}\mathbb{V}\mathrm{ar}\left(X_{ij}\right)+\frac{1}{3}t}\right)}$
$\displaystyle\stackrel{{\scriptstyle\text{Ineq.
(}\ref{IneqSimpleIneqForBern}\text{)}}}{{\leq}}2\exp{\left(\frac{-\frac{1}{2}t^{2}}{\rho_{N}d_{\mathrm{MAX}}^{(N)}+\frac{1}{3}t}\right)}.$

Taking a union bound,

$\mathbb{P}\left(\left\|\Delta^{(N)}\right\|>t\right)\leq
2N\exp{\left(\frac{-\frac{1}{2}t^{2}}{\rho_{N}d_{\mathrm{MAX}}^{(N)}+\frac{1}{3}t}\right)}.$

Choosing
$t=\sqrt{4\rho_{N}d_{\mathrm{MAX}}^{(N)}\log\left(4N/\varepsilon\right)}$,

$\displaystyle\mathbb{P}\left(\left\|\Delta^{(N)}\right\|>\sqrt{4\rho_{N}d_{\mathrm{MAX}}^{(N)}\log\left(4N/\varepsilon\right)}\right)$
$\displaystyle\leq
2N\exp{\left(-\frac{2\rho_{N}d_{\mathrm{MAX}}^{(N)}\log(4N/\varepsilon)}{\rho_{N}d_{\mathrm{MAX}}^{(N)}+\frac{1}{3}\sqrt{4\rho_{N}d_{\mathrm{MAX}}^{(N)}\log\left(4N/\varepsilon\right)}}\right)}$
$\displaystyle\leq
2N\exp{\left(-\frac{2\rho_{N}d_{\mathrm{MAX}}^{(N)}\log(4N/\varepsilon)}{\rho_{N}d_{\mathrm{MAX}}^{(N)}+\rho_{N}d_{\mathrm{MAX}}^{(N)}}\right)}$
$\displaystyle=\frac{\varepsilon}{2}.$

Recalling that
$\left\|\Delta^{(N)}\right\|=\left\|\widehat{D}^{(N)}-\rho_{N}D^{(N)}\right\|$
and $d_{\mathrm{MAX}}^{(N)}\leq N$, this implies

$\mathbb{P}\left(\left\|\widehat{D}^{(N)}-\rho_{N}D^{(N)}\right\|\leq\sqrt{4\rho_{N}N\log\left(4N/\varepsilon\right)}\right)\geq
1-\frac{\varepsilon}{2}.$ (4.10)

For $\varepsilon\in(0,1)$ we substitute (4.8) and (4.10) in (4.7) to get

$\mathbb{P}\left({\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}_{N}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
4\sqrt{\frac{\log(4N/\varepsilon)}{\rho_{N}N}}\right)\geq 1-\varepsilon.$
(4.11)

Finally, applying inequality (4.6), we get that for all $\varepsilon\in(0,1)$
and all $N\geq N_{1}(w,\tau,\varepsilon)$ in the sense of (4.1)

$\mathbb{P}\left({\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
4\sqrt{\frac{\log(4N/\varepsilon)}{\rho_{N}N}}+\frac{4K}{N}\right)\geq
1-\varepsilon,$

completing the proof. Again, replace in the $\varepsilon$ by
$\varepsilon_{\gamma}(N)$ in the above and get the same result for all $N\geq
N^{\prime}_{1}(w,\tau,\gamma)$ in the sense of (4.2). ∎

∎

###  4.2 Convergence of the Fiedler function

In order to prove the convergence of the Fiedler function we use a result by
Davis and Kahan [11] known as the $\sin(\theta)$-theorem for self-adjoint
operators.

######  Theorem 6 (Davis-Kahan).

Let $\mathbb{A}$ and $\widetilde{\mathbb{A}}$ be two self-adjoint operators
with eigenvalues $\lambda_{1}<\lambda_{2}<\lambda_{3}<\cdots$ and
$\tilde{\lambda}_{1}<\tilde{\lambda}_{2}<\tilde{\lambda}_{3}<\cdots$
respectively. Consider eigenfunctions $f$ and $\tilde{f}$ of $\mathbb{A}$ and
$\widetilde{\mathbb{A}}$ respectively with eigenvalues $\lambda_{2}$ and
$\tilde{\lambda}_{2}$ respectively, and normalized so that
$\left\|f\right\|=\|\tilde{f}\|=1$ and $\langle f,\tilde{f}\rangle\geq 0$. If
$0<\lambda_{2}<\lambda_{3}$ (i.e., $\lambda_{2}$ is isolated), then

$\left\|\tilde{f}-f\right\|\leq\frac{2\sqrt{2}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\widetilde{\mathbb{A}}-\mathbb{A}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}{\min\\{\lambda_{2}-\lambda_{1},\lambda_{3}-\lambda_{2}\\}}.$

Applying this to $\mathbb{L}$ and $\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}$
immediately gives:

######  Theorem 7.

Let $\phi$ and $\hat{\phi}_{N}$ be the Fiedler functions of $\mathbb{L}$ and
$\rho_{N}\widehat{\mathbb{L}}_{N}$ respectively, normalized so that
$\|\phi\|=\|\hat{\phi}_{N}\|=1$ and $\langle\phi,\hat{\phi}_{N}\rangle\geq 0$.
Fix $\eta<\frac{1-\tau}{3}$, then for all $\varepsilon\in(0,1)$ there exists a
positive constant $C=C(w)$ and an integer
$N_{0}=N_{0}(w,\tau,\eta,\varepsilon)$ so that

$\mathbb{P}\left(\left\|\hat{\phi}_{N}-\phi\right\|\leq
C\sqrt{N^{-3\eta}}\right)\geq 1-\varepsilon$

for all $N\geq N_{0}$.

Moreover, for any $\gamma>1$ there exists a positive constant
$C^{\prime}=C^{\prime}(w)$ and an integer
$N^{\prime}_{0}=N^{\prime}_{0}(w,\tau,\eta,\gamma)$ so that

$\mathbb{P}\left(\left\|\hat{\phi}_{N}-\phi\right\|\leq
C^{\prime}\sqrt{N^{-3\eta}}\right)\geq 1-\varepsilon_{\gamma}(N)$

for all $N\geq N^{\prime}_{0}$.

###### Proof.

Define $N_{0}=N_{0}(w,\tau,\eta,\varepsilon)$ and
$N^{\prime}_{0}=N^{\prime}_{0}(w,\tau,\eta,\gamma)$ by

$\displaystyle N_{0}(w,\tau,\eta,\varepsilon)=\min\left\\{n\geq
N_{1}(w,\tau,\varepsilon)\,:\,N\geq n\Rightarrow
4\sqrt{\frac{\log(4N/\varepsilon)}{\rho_{N}N}}+\frac{4K}{N}\leq\sqrt{N^{-3\eta}}\right\\}$
$\displaystyle N^{\prime}_{0}(w,\tau,\eta,\gamma)=\min\left\\{n\geq
N^{\prime}_{1}(w,\tau,\eta)\,:\,N\geq n\Rightarrow
4\sqrt{\frac{\log(4N/\varepsilon_{\gamma}(N))}{\rho_{N}N}}+\frac{4K}{N}\leq\sqrt{N^{-3\eta}}\right\\}$

where $N_{1}$ and $N^{\prime}_{1}$ are defined in (4.1), (4.2) respectively.
Note that both $N_{0}$ and $N^{\prime}_{0}$ are well defined since the left
hand sides of the inequalities inside $N_{0}$ and $N^{\prime}_{0}$
respectively are on the order of $\mathcal{O}(N^{-(1-\tau)/2}\log^{1/2}(N))$
and $\mathcal{O}(N^{-(1-\tau)/2}\log^{\gamma/2}(N))$ respectively, which
converges faster than the right hand sides of order
$\mathcal{O}(N^{-3\eta/2})$ (recall that
$\tfrac{3\eta}{2}<\tfrac{1-\tau}{2}$).

Take $N\geq N_{0}$, by Theorem 4.2 we know that with a probability of at least
$1-\varepsilon$

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle\leq
4\sqrt{\frac{\log(4N/\varepsilon)}{\rho_{N}N}}+\frac{4K}{N}$
$\displaystyle\leq\sqrt{N^{-3\eta}}.$

We apply the Davis-Kahan Theorem 6 to the Fiedler functions $\phi$ and
$\hat{\phi}_{N}$ (note that the theorem applies here since under our
assumptions $\lambda_{2}$ is simple by Theorem 5). We have with probability at
least $1-\varepsilon$

$\displaystyle\left\|\hat{\phi}_{N}-\phi\right\|$
$\displaystyle\leq\frac{2\sqrt{2}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\rho_{N}^{-1}\widehat{\mathbb{L}}_{N}-\mathbb{L}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}}{\min\\{\lambda_{2},\lambda_{3}-\lambda_{2}\\}}$
$\displaystyle\leq\frac{2\sqrt{2}}{\min\\{\lambda_{2},\lambda_{3}-\lambda_{2}\\}}\sqrt{N^{-3\eta}}$

as required. We get the same result for the case
$\varepsilon=\varepsilon_{\gamma}(N)$ and $N\geq N^{\prime}_{0}$. ∎

##  5 Error bound for the spectral seriation algorithm

In this section, we prove Theorem 2. The method we use to bound the errors of
the permutation are very similar to the method used in the paper [36]. We
follow the notation used in the statement of Theorem 2, denote by $\phi$ the
Fiedler eigenfunction of $\mathbb{L}$, and denote by $\hat{\phi}_{N}$ the
Fiedler vector appearing in step 3 of Algorithm 1 with input $G^{(N)}$. By a
small abuse of notation, for $i\in[N]$ we define $\hat{\phi}_{i}$ to be the
$i$’th element of ${\phi}_{N}$. Similarly, for $x\in[0,1]$, we define

$\hat{\phi}_{N}(x)=\sum_{i=1}^{N}\hat{\phi}_{i}1_{\mathcal{I}_{i}^{N}}(x).$

It is straightforward to check that $\hat{\phi}_{N}$ is exactly the Fiedler
vector of $\rho_{N}\widehat{\mathbb{L}}_{N}$. Note that we use the same
notation $\hat{\phi}_{N}$ to refer to both the Fiedler vector associated with
finite graph $G^{(N)}$ and the Fiedler function associated with the empirical
graphon $\rho_{N}\widehat{\mathbb{L}}_{N}$. This will not cause any ambiguity
in the following argument, as it is always clear if the argument for
$\hat{\phi}_{N}$ is a generic value $x\in[0,1]$ or a generic value
$i\in\\{1,2,\ldots,N\\}$. We repeat notation in this way because the two
objects take exactly the same values in the same order, and this allows us to
avoid some repetition of essentially identical calculations.

Let $\sigma=\sigma_{\hat{\phi}_{N}}$ as in Equation (1.5). Note that $\sigma$
is the output of Algorithm 1 with input $G^{(N)}$ and that we have
$\hat{\phi}_{\sigma(1)}\leq\hat{\phi}_{\sigma(2)}\leq\cdots\leq\hat{\phi}_{\sigma(N)}$.
Since $\phi$ is monotone and $\hat{\phi}_{N}$ is close to $\phi$ or $-\phi$
(by Theorem 7), we expect the permutation $\sigma$ to be close to the identity
permutation (or its reverse).

For any permutation $\pi\in\mathcal{S}_{N}$, define the Kendall tau distance
to be

$D_{N}(\pi)=\sum_{i<j}\mathbf{1}_{\\{\pi(i)>\pi(j)\\}}.$

In [13], it was shown that, for any $\pi\in\mathcal{S}_{N}$, we have
$D_{N}(\pi)\leq\|\pi-id_{N}\|_{1}\leq 2D_{N}(\pi)$. Thus, when $N\to\infty$,
these distances are of the same order.

We are now ready to prove Theorem 2:

###### Proof of Theorem 2.

Fix any $0<\eta<\frac{1-\tau}{3}$. We assume without loss of generality that
$\left\|\hat{\phi}_{N}-\phi\right\|\leq\left\|\hat{\phi}_{N}+\phi\right\|$ (if
not, simply replace $\phi$ with $-\phi$ in the following). Define

$\displaystyle E_{N}$ $\displaystyle:=\left\\{(i,j)\in[N]^{2}\,:\,i<j\text{
and }\sigma(j)<\sigma(i)\right\\}$ $\displaystyle E_{N}^{\eta}$
$\displaystyle:=\left\\{(i,j)\in[N]^{2}\,:\,i+N^{1-\eta}<j\text{ and
}\sigma(j)<\sigma(i)\right\\},$

We then have

$\displaystyle 2\left\|\hat{\phi}_{N}-\phi\right\|^{2}$
$\displaystyle=\int_{0}^{1}(\hat{\phi}_{N}(x)-\phi(x))^{2}dx+\int_{0}^{1}(\hat{\phi}_{N}(y)-\phi(y))^{2}dy$
$\displaystyle=\sum_{i=1}^{N}\int_{\mathcal{I}_{i}^{N}}(\hat{\phi}_{i}-\phi(x))^{2}dx+\sum_{j=1}^{N}\int_{\mathcal{I}_{j}^{N}}(\hat{\phi}_{j}-\phi(x))^{2}dx$
$\displaystyle=\frac{1}{N}\sum_{1\leq i,j\leq
N}\left(\int_{\mathcal{I}_{i}^{N}}(\hat{\phi}_{i}-\phi(x))^{2}dx+\int_{\mathcal{I}_{i}^{N}}(\hat{\phi}_{j}-\phi(x+\frac{j-i}{N}))^{2}dx\right)$
$\displaystyle\geq\frac{1}{N}\sum_{(i,j)\in
E_{N}^{\eta}}\int_{\mathcal{I}_{i}^{N}}\left((\hat{\phi}_{i}-\phi(x))^{2}+(\hat{\phi}_{j}-\phi(x+\frac{j-i}{N}))^{2}\right)dx.$

Since $\phi(x+\frac{j-i}{N})>\phi(x)$ and $\hat{\phi}_{j}<\hat{\phi}_{i}$ for
$(i,j)\in E_{N}$, we also have

$(\hat{\phi}_{i}-\phi(x))^{2}+(\hat{\phi}_{j}-\phi(x+\frac{j-i}{N}))^{2}\geq\frac{1}{2}\left(\phi(x+\frac{j-i}{N})-\phi(x)\right)^{2}.$

Combining the previous two estimates,

$\displaystyle 2\left\|\hat{\phi}_{N}-\phi\right\|^{2}$
$\displaystyle\geq\frac{1}{2N}\sum_{(i,j)\in
E_{N}^{\eta}}\int_{\mathcal{I}_{i}^{N}}\left(\phi(x+\frac{j-i}{N})-\phi(x)\right)^{2}dx$
$\displaystyle\stackrel{{\scriptstyle\text{Theorem
}\ref{thm:monotone}}}{{\geq}}\frac{L^{2}}{2N^{3}}\sum_{(i,j)\in
E_{N}^{\eta}}\int_{\mathcal{I}_{i}^{N}}(j-i)^{2}dx$
$\displaystyle\geq\frac{L^{2}}{2N^{1+2\eta}}\sum_{(i,j)\in
E_{N}^{\eta}}\int_{\mathcal{I}_{i}^{N}}dx$
$\displaystyle=\frac{L^{2}}{2N^{2+2\eta}}\left|E_{N}^{\eta}\right|,$

where the inequality from line two to three follows from the fact that
$j>i+N^{1-\eta}$ for $(i,j)\in E_{N}^{\eta}$. Consequently,

$\left|E_{N}^{\eta}\right|\leq\frac{4}{L^{2}}N^{2+2\eta}\left\|\hat{\phi}_{N}-\phi\right\|^{2}.$

On the other hand,

$E_{N}\setminus E_{N}^{\eta}=\left\\{(i,j)\in[N]^{2}:0<j-i\leq
N^{1-\eta}\text{ and }\sigma(j)<\sigma(i)\right\\},$

thus $\left|E_{N}\setminus E_{N}^{\eta}\right|\leq N^{2-\eta}$. By Theorem 7
there exists a positive constant $C=C(w)$ so that for all $N\geq
N_{0}(w,\tau,\eta,\varepsilon)$ we have with probability at least
$1-\varepsilon$

$\left\|\hat{\phi}_{N}-\phi\right\|^{2}\leq C^{2}N^{-3\eta}.$

Recall that $D_{N}(\sigma)=\left|E_{N}\right|$ and $\|\sigma-
id_{N}\|_{1}\leq\tfrac{1}{2}D_{N}(\sigma)$, therefore with probability at
least $1-\varepsilon$

$\displaystyle\|\sigma-id_{N}\|_{1}$
$\displaystyle\leq\frac{1}{2}\left(\left|E_{N}\setminus
E_{N}^{\eta}\right|+\left|E_{N}^{\eta}\right|\right)$
$\displaystyle\leq\frac{1}{2}N^{2-\eta}+\frac{2}{L^{2}}N^{2+2\eta}\left\|\hat{\phi}_{N}-\phi\right\|^{2}$
$\displaystyle\leq(\frac{1}{2}+\frac{2C^{2}}{L^{2}})N^{2-\eta}$

as required. The same inequality holds for
$\varepsilon=\varepsilon_{\gamma}(N)$ for all $N\geq
N^{\prime}_{0}(w,\tau,\eta,\gamma)$. ∎

##  6 Postprocessing and Tighter Error Bounds

The main goal of this section is to prove Theorem 3. We introduce a post-
processing algorithm of the estimate returned by Algorithm 1. This new
algorithm provides an estimate that is more robust to noise, with a nearly
optimal convergence rate.

###  6.1 Notation

We set notation that will be used throughout Section 6. Let $G=(V,E)$ be a
graph of size $N$. Denote by $V:=\left\\{v_{1},v_{2},\ldots,v_{N}\right\\}$
the vertices of $G$, with $v_{i}=i/N$. For any $S\subset V$, denote the
induced subgraph on $S$ by $G|_{S}$. Define the (restricted) neighbourhood of
a vertex $v\in V$ by $N_{S}(v)=\\{u\in S\,:\,(u,v)\in E\\}$. Denote by
$\sigma_{S}\,:\,S\to[|S|]$ the function that sends $s\in S$ to
$\left|\\{s^{\prime}\in S\,:\,s^{\prime}\leq s\\}\right|$; we think of this
ordering as being essentially the “identity” permutation on $S$.

Algorithm 3 involves partitioning up the vertices of $G$, estimating various
quantities on parts of the partition, and then combining them. We say that a
partition $(S_{1},S_{2},S_{3})$ of $V$ is “good” if
$n\leq|S_{3}|\leq|S_{2}|\leq|S_{1}|\leq n+1$, where
$n=\left\lfloor\frac{N}{3}\right\rfloor$.

Let $(S_{1},S_{2},S_{3})$ be a “good” partition of $V$ and let
$\sigma_{j}:S_{j}\to[|S_{j}|]$ be orderings of each part of the partition. We
define the “merged ordering” of $(\sigma_{1},\sigma_{2},\sigma_{3})$ as an
ordering $\sigma:[N]\to[N]$ defined by:

$\sigma^{-1}(3k+j)=N\sigma_{j}^{-1}(k+1),$ (6.1)

for all $k\in\\{0,1,\ldots,n\\}$ and $j\in\\{1,2,3\\}$ such that $3k+j\leq N$.
Note that Equation (6.1) does define a permutation, since for all $i\in[N]$
there is exactly one solution to the equation $i=3k+j$ with $j\in\\{1,2,3\\}$
and $k\in\\{0,1,\ldots,n\\}$. Note that the factor $N$ in the definition is
coming from the fact that the elements of $V$ are scaled by $v_{i}=i/N$.

Finally, for two orderings $\sigma_{1},\sigma_{2}$ on sets $S_{1},S_{2}$, say
that $\sigma_{1},\sigma_{2}$ are aligned if

$\max_{i\in S{1}\cap
S_{2}}\left|\frac{\sigma_{1}(i)}{|S_{1}|}-\frac{\sigma_{2}(i)}{|S_{2}|}\right|\leq\max_{i\in
S_{1}\cap
S_{2}}\left|\frac{\mathrm{rev}(\sigma_{1})(i)}{|S_{1}|}-\frac{\sigma_{2}(i)}{|S_{2}|}\right|,$
(6.2)

and that $\sigma_{1},\sigma_{2}$ not aligned otherwise. If $S_{1}\cap
S_{2}=\emptyset$, say that they are aligned. Moreover, if the left-hand side
of (6.2) is less than 0.001 and the right-hand side is more than 0.999, say
that $\sigma_{1},\sigma_{2}$ are closely aligned. Recall that
$\mathrm{rev}(\sigma)$ denotes the reversal of any ordering $\sigma$ defined
in Equation (1.2).

###  6.2 Algorithms and Informal Analysis

We are now ready to present our main algorithms.

1

Input : A graph $G=(V,E)$ of size $N$, a pair of disjoint sets $(T,S)\subset
V^{2}$ and parameters $0<\alpha<\beta<1/2$.

2

3Let $\hat{\sigma}_{T}$ be the result of running Algorithm 1 on $G|_{T}$.

4 Given $\hat{\sigma}_{T}$, estimate the set of right-most and left-most
vertices in $T$ by  $\displaystyle R=R_{\hat{\sigma}_{T}}(\alpha)$
$\displaystyle:=\left\\{u\in
T\,:\,\hat{\sigma}_{T}(u)\geq(1-\alpha)\,|T|\right\\},$ (6.3) $\displaystyle
L=L_{\hat{\sigma}_{T}}(\alpha)$ $\displaystyle:=\left\\{u\in
T\,:\,\hat{\sigma}_{T}(u)\leq\alpha\,|T|\right\\}.$ (6.4)

5 For each $v\in S$, estimate the neighbourhood-size functions
$\displaystyle\psi_{R}(v)$
$\displaystyle:=\frac{1}{|T|}\,\left|N_{R}(v)\right|=\frac{1}{|T|}\,\sum_{u\in
R}\mathbf{1}_{(u,v)\in E},$ (6.5) $\displaystyle\psi_{L}(v)$
$\displaystyle:=\frac{1}{|T|}\,\left|N_{L}(v)\right|=\frac{1}{|T|}\,\sum_{u\in
L}\mathbf{1}_{(u,v)\in E}.$ (6.6)

6 Compute the following empirical quantiles of $\psi_{L},\psi_{R}$:
$\displaystyle c_{R}$ $\displaystyle:=\inf\left\\{c\geq
0\,:\,\left|\left\\{v\in S\,:\,\psi_{R}(v)\leq
c\right\\}\right|\geq(1-\beta)|S|\right\\},$ (6.7) $\displaystyle c_{L}$
$\displaystyle:=\inf\left\\{c\geq 0\,:\,\left|\left\\{v\in
S\,:\,\psi_{L}(v)\leq c\right\\}\right|\geq(1-\beta)|S|\right\\}.$ (6.8)

7

8Compute the antisymmetric function $\hat{F}\,:\,S^{2}\mapsto\\{-1,0,1\\}$ by
the following rule for $u<v$:
$\hat{F}(u,v)=\left\\{\begin{array}[]{ll}1-2\cdot\mathbf{1}_{\psi_{R}(u)>\psi_{R}(v)}&\mbox{if
}\psi_{R}(u),\psi_{R}(v)<c_{R}\mbox{; otherwise,}\\\
1-2\cdot\mathbf{1}_{\psi_{L}(u)<\psi_{L}(v)}&\mbox{if
}\psi_{L}(u),\psi_{L}(v)<c_{L}\mbox{; otherwise,}\\\ 1&\mbox{if
}\mbox{$\psi_{R}(u)<c_{R}$}\mbox{; otherwise,}\\\ -1&\mbox{}\\\
\end{array}\right\\}.$ (6.9)

9

10For each $v\in S$ compute  $\hat{f}(v)=\sum_{u\in S}\hat{F}(u,v).$ (6.10)

11 Compute the ordering $\hat{\sigma}_{S}=\hat{\sigma}_{\hat{f}}$ on $S$
according to Equation (1.5), breaking ties arbitrarily. 444Note that the range
of $\hat{\sigma}_{S}$ is $\\{1,2,\ldots,|S|\\},$ which is generally not equal
to the set $S$ itself.

12

Output : The permutation $\hat{\sigma}_{S}$.

Algorithm 2 Initial Post-processing the output of spectral seriation.

We give an informal summary of what this algorithm is doing and why we expect
it to work well, eliding many details.

Steps 1-2 get a good estimate of the right-most and left-most vertices in $T$,
denoted $R$ and $L$ respectively. Using these estimated sets, steps 3-6 try to
compare vertices $u,v\in S$ by comparing the number of neighbours these
vertices have in $R$ and $L$. The Robinsonian property suggests the following
heuristic: if $u<v$, then $u$ should have more neighbours in $R$ while $v$
should have more neighbours in $L$. If this heuristic were exactly correct, we
would use only the first of four cases in the function $\hat{F}$ from Equation
(6.9). However, the heuristic isn’t quite correct: it can fail if (i) both of
$u,v$ are very close to either $0$ or $1$ (in which case many of the “right-
most” elements of $R$ are not actually to the right of $u,v$ or many of the
“left-most” elements of $L$ are not actually to the left of $u,v$) or (ii) if
$|u-v|$ is too small (in which case sampling error may dominate).

The four cases in Equation (6.9) deal with the first of these problems by
ensuring that we compare $u,v$ by counting either right- or left-most
neighbours as appropriate. To give a back-of-the-envelope analysis of the
sampling error that can cause the second problem, we note that there are
$\Theta(N)$ possible edges from $u,v$ to $R$ or $L$, and the presence or
absence of these edges are independent of the random variables used to
estimate $R$ and $L$ (the purpose of partitioning $V$ is exactly to obtain
this independence). This suggests that, as long as the error in the estimates
of $R$ and $L$ are “negligible”, the typical error in the estimates of
$\psi_{R},\psi_{L}$ should be $\mathcal{O}(\sqrt{N})$. In particular, this is
the step that lets us clean rough estimates of sets $R,L$ into much better
estimates of the averages $\psi_{R},\psi_{L}$. Although this may not be
obvious at first glance, the consistency result in Theorem 2 is strong enough
to guarantee that the error in the estimates of $R$, $L$ are “negligible” in
the sense that this argument requires. This calculations suggests that
$\hat{\sigma}_{S}$ should have a sup-norm error that is not too much larger
than $\mathcal{O}(\sqrt{N})$, which is the case.

We now give our overall post-processing algorithm :

1

Input : A graph $G=(V,E)$ of size $N$. Parameters $0<\alpha<\beta<1/2$.

2 Choose $(S_{1},S_{2},S_{3})$ a “good” partition of $V$, uniformly at random;
and independently choose another “good” partition
$(S_{1}^{\prime},S_{2}^{\prime},S_{3}^{\prime})$, uniformly at random.

3

4Use Algorithm 2 on pairs of subsets $(S_{3},S_{1})$, $(S_{1},S_{2})$ and
$(S_{2},S_{3})$ with parameters $\alpha,\beta$ to obtain estimated orders
$\hat{\sigma}_{1},\hat{\sigma}_{2},\hat{\sigma}_{3}$ on $S_{1},S_{2},S_{3}$
respectively. Also use Algorithm 2 on $(S_{1}^{\prime},S_{2}^{\prime})$ with
parameters $\alpha,\beta$ to obtain estimated order
$\hat{\sigma}_{\mathrm{ref}}$ on $S_{2}^{\prime}$.

5 For $j\in\\{1,2,3\\}$, replace $\hat{\sigma}_{j}$ by
$\mathrm{rev}(\hat{\sigma}_{j})$ if it is not aligned with
$\hat{\sigma}_{\mathrm{ref}}$ in the sense of Equation (6.2).

6 Compute $\hat{\sigma}$ the merged ordering of
$(\hat{\sigma}_{1},\hat{\sigma}_{2},\hat{\sigma}_{3})$ according to Equation
(6.1).

Output : The permutation $\hat{\sigma}$ .

Algorithm 3 Post-processing the output of spectral seriation.

Algorithm 3 largely consists of many calls to Algorithm 2, and so most of the
algorithm seems straightforward. The one possibly-mysterious part is step 3.
To explain the need for this step, recall that it is impossible to distinguish
between a vertex ordering $\sigma$ and its reverse $\mathrm{rev}(\sigma)$ by
looking only at the edges of a graph. Up to this point in the paper, this has
not posed a problem, as we always looked at an entire graph all at once.
However, in Algorithm 3, we use Algorithm 2 to repeatedly order different
subsets of the vertices. As a result, it is likely that some of the returned
orderings $\hat{\sigma}_{j}:S_{j}\to[|S_{j}|]$ will be aligned with
$\sigma_{S_{j}}$ (in the sense of Equation (6.2)) while others will be aligned
with $\mathrm{rev}(\sigma_{S_{j}})$. Fortunately, this problem is not
difficult to solve: each ordering will either be closely aligned with
$\sigma_{S_{j}}$ or its reverse, and so a single reference ordering
$\hat{\sigma}_{\mathrm{ref}}$ can be used to simultaneously align all other
orderings, as long as their supports have non-empty intersection.

###  6.3 Analysis of Algorithm 2

In this subsection, we prove the main bounds on the objects appearing in
Algorithm 3. We start by presenting the main theorem that provides a bound for
the error of the estimated ordering $\hat{\sigma}_{S}$ returned by Algorithm
2. Then the rest of this subsection will be dedicated to proving this theorem.

######  Theorem 8.

Let $G=(V,E)$ be a Robinsonian graph of size $N$ sampled according to a
graphon $w$ as in Theorem 3. Fix $s,t$ satisfying $n\leq s,t\leq n+1$ and let
$S,T\subset V$ be chosen uniformly at random from all disjoint subsets of size
$|S|=s$, $|T|=t$. Consider $\hat{\sigma}_{S}:S\to[|S|]$ to be the output of
Algorithm 2 with input $G$, the pair of random sets $(T,S)$ and parameters
$0<\alpha<\beta<1/2$ as in Assumption 5. For all $\gamma>1$ and $\epsilon>0$,
there exists a positive constant $\delta=\delta(w,\gamma,\epsilon)>0$ and an
integer $N_{0}=N_{0}(w,\gamma,\epsilon)$ so that

$\mathbb{P}\left(\left\|\hat{\sigma}_{S}-\sigma_{S}\right\|_{1}\leq\epsilon\sqrt{N\log^{\gamma}(N)}\right)\geq
1-\varepsilon_{\gamma}^{\delta}(N)$

for all $N\geq N_{0}$.

Throughout this subsection we use notation as in Theorem 8, let
$0<\alpha<\beta<1/2$ as in Assumption 5, and set $\mu=(\alpha+\beta)/2$.

We fix a constant $\gamma>1$ for the remainder of the section, and say that a
sequence of events $\\{\mathcal{E}_{N}\\}_{N\in\mathbb{N}}$ holds with extreme
probability if there exist a constant $\delta>0$ and an integer $N_{0}$, such
that

$\mathbb{P}\left(\mathcal{E}_{N}\right)\geq
1-\varepsilon_{\gamma}^{\delta}(N)$ (6.11)

for all $N\geq N_{0}$. We abbreviate this w.e.p. Note that for any $C>0$, the
intersection of $\mathcal{O}(N^{C})$ events that occur w.e.p for some
$\gamma>1$ also occur w.e.p with the same $\gamma$. We define the sequence
$\Delta_{N}=\sqrt{\tfrac{\log^{\gamma}(N)}{N}}$ for $N\geq 1$; this is
essentially the scale of the most important errors that occur in the
algorithm.

The first step in the proof is checking that the discrete functions
$\psi_{R},\psi_{L}$ are good approximations of the continuous functions
$\Psi_{R},\Psi_{L}$ respectively. We recall some facts about these functions.
For $v\in V$, recall

$\Psi_{R}(v)=\int_{1-\alpha}^{1}w(v,u)\,du.$

Denote by $\mathcal{F}_{T}$ the $\sigma$-algebra generated by the choice of
$T$ and the graph ${\left.\kern-1.2ptG^{(N)}\vphantom{\big{|}}\right|_{T}}$.
Since $\psi_{R}(v)$ and $\psi_{L}(v)$ are sums of Bernoulli random variables
sampled according to Equation (2.1) then

$\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]=\frac{1}{|T|}\,\sum_{u\in
R}w(u,v),\text{ and
}\,\mathbb{E}[\psi_{L}(v)|\mathcal{F}_{T}]=\frac{1}{|T|}\,\sum_{u\in
L}w(u,v);$

in particular $R,L$ are both $\mathcal{F}_{T}$-measurable, while the indicator
function of an edge $(u,v)$ with $u\in L\cup R$, $v\in S$ is independent of
$\mathcal{F}_{T}$ and has mean $w(u,v)$. This implies that for any fixed
$\epsilon>0$ the following holds w.e.p

$\max_{v\in S}\left|\psi_{R}(v)-\frac{1}{|T|}\,\sum_{u\in
R}w(u,v)\right|\leq\epsilon\,\Delta_{N}.$ (6.12)

The following Lemma shows that the graph-dependent functions
$\psi_{R},\psi_{L}$ approximate the graphon-dependent functions
$\Psi_{R},\Psi_{L}$

######  Lemma 6.1.

For any $\epsilon>0$, the inequalities

$\max_{v\in
S}\left|\psi_{R}(v)-\Psi_{R}(v)\right|\leq\epsilon\Delta_{N},\text{ and
}\max_{v\in S}\left|\psi_{L}(v)-\Psi_{L}(v)\right|\leq\epsilon\Delta_{N}$

hold w.e.p.

Similarly, the constants $c_{R}$ and $c_{L}$ are intended to estimate
$\Psi(1-\beta)$ and $\Psi(\beta)$ respectively.

######  Lemma 6.2.

For any $\epsilon>0$ the following inequalities

$\left|c_{R}-\Psi_{R}(1-\beta)\right|\leq\epsilon\Delta_{N},\,\text{ and
}\,\left|c_{L}-\Psi_{L}(\beta)\right|\leq\epsilon\Delta_{N}$

hold w.e.p.

###### Proof of Lemma 6.1.

We will present the proof only for $\psi_{R}$, since the proof for $\psi_{L}$
is identical. Denote by $T=\\{t_{(1)},\ldots,t_{(t)}\\}$ the elements of $T$
in order, so that $t_{(1)}<t_{(2)}<\ldots<t_{(t)}$. Note that
$\sigma_{T}(t_{(k)})=k$ for all $k$. For $v\in S$, we have

$\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]=\frac{1}{t}\sum_{k=\left\lceil(1-\beta)t\right\rceil}^{t}w(t_{(k)},v).$

Now define

$\Sigma:=\frac{1}{N}\sum_{k=\left\lceil(1-\beta)N\right\rceil}^{N}w(v_{k},v),$

and, for each $j=0,1,2$, define

$\Sigma_{j}:=\frac{1}{t}\sum_{k=\left\lceil(1-\beta)t\right\rceil}^{t}w(v_{3k+j},v).$

By the triangle inequality,

$\left|\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]-\Psi_{R}(v)\right|\leq\left|\Psi_{R}(v)-\Sigma\right|+\frac{1}{3}\sum_{j=0}^{2}\left|\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]-\Sigma_{j}\right|+\frac{1}{3}\left|\Sigma_{0}+\Sigma_{1}+\Sigma_{2}-3\Sigma\right|.$
(6.13)

We now bound each term of the right hand side in inequality (6.13). Recall the
constant $K$ from Assumption 1. We have

$\left|\Psi_{R}(v)-\Sigma\right|\leq\frac{\beta K}{N},$ (6.14)

by essentially the same argument as the proof of the first inequality in the
proof of Lemma 4.1. Next,

$\displaystyle|\Sigma_{0}+\Sigma_{1}+\Sigma_{2}-3\Sigma|$
$\displaystyle\leq\left|\Sigma_{0}+\Sigma_{1}+\Sigma_{2}-\frac{N}{t}\Sigma\right|+\frac{|N-3t|}{t}\Sigma$
$\displaystyle=\frac{1}{t}\underset{\leq(1-\beta)|N-3t|}{\underbrace{\left|\sum_{k=\left\lceil
3(1-\beta)t\right\rceil}^{N}w(v_{k},v)-\sum_{k=\left\lceil(1-\beta)N\right\rceil}^{N}w(v_{k},v)\right|}}+\underset{\leq\beta}{\underbrace{\Sigma}}\,\frac{|N-3t|}{t}$
$\displaystyle\leq\frac{|N-3t|}{t},$

where the bound in the first underbrace comes from the facts that (i) at most
$(1-\beta)|N-3t|$ terms appear in one sum but not the other and (ii) each
summands $w(v_{k},v)$ is bounded by 1, and the bound in the second underbrace
comes again from the fact that the summands of $\Sigma$ are bounded by 1.
Since $3t-3\leq N\leq 3t+2$ by assumption, we conclude

$|\Sigma_{0}+\Sigma_{1}+\Sigma_{2}-3\Sigma|\leq\frac{12}{N}.$ (6.15)

Finally, fixing $0\leq j\leq 2$, we calculate

$\displaystyle\left|\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]-\Sigma_{j}\right|$
$\displaystyle\leq\frac{1}{t}\sum_{k\geq(1-\beta)t}\left|w(t_{(k)},v)-w(v_{3k+j},v)\right|$
$\displaystyle\leq\frac{K}{t}\sum_{k\geq(1-\beta)t}|t_{(k)}-v_{3k+j}|.$

According to Lemma A.1,

$\max_{k\in T}|t_{(k)}-\frac{k}{t}|\leq\frac{\epsilon}{2\beta
K}\Delta_{N}\hskip 14.22636pt\textit{w.e.p.}$

Additionally, it is easy to check that $|\frac{k}{t}-v_{3k+j}|\leq 8/N$.
Therefore we have with extreme probability

$|t_{(k)}-v_{3k+j}|\leq\frac{\epsilon}{2\beta K}\Delta_{N}+\frac{8}{N}.$

We conclude

$\left|\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]-\Sigma_{j}\right|\leq\frac{\epsilon}{2}\Delta_{N}+\frac{8\beta
K}{N}\hskip 14.22636pt\textit{w.e.p.}$ (6.16)

We substitute Inequalities (6.14), (6.15) and (6.16) in Inequality (6.13) to
get

$\left|\mathbb{E}[\psi_{R}(v)|\mathcal{F}_{T}]-\Psi_{R}(v)\right|\leq\frac{\epsilon}{2}\Delta_{N}+\frac{9\beta
K+12}{N}\leq\epsilon\Delta_{N}\hskip 14.22636pt\textit{w.e.p.}$

Applying the concentration bound (6.12) completes the proof. ∎

Define

$M=\sup\limits_{x\in[0,1]}\Psi_{R}^{\prime}(x)>0;$ (6.17)

this exists by Assumption 2.

###### Proof of Lemma 6.2.

We give the proof only for $\Psi_{R}$, as the case $\Psi_{L}$ is identical.
Recall that by definition of $c_{R}$

$\left|\left\\{v\in S\,:\,\psi_{R}(v)\leq
c\right\\}\right|\geq(1-\beta)s\Leftrightarrow c\geq c_{R}$

for all $c>0$. For $v\in V$, we have

$\\{|v-(1-\beta)|\leq\frac{\epsilon\Delta_{N}}{2M}\\}\Rightarrow\\{|\Psi_{R}(v)-\Psi_{R}(1-\beta)|\leq\frac{\epsilon\Delta_{N}}{2}\\}.$

By Lemma 6.1, we have

$|\psi_{R}(v)-\Psi_{R}(v)|\leq\frac{\epsilon\Delta_{N}}{2}\hskip
14.22636pt\textit{w.e.p.}$

Combining the last two bounds,

$\displaystyle|v-(1-\beta)|\leq\frac{\epsilon\Delta_{N}}{2M}$
$\displaystyle\Rightarrow|\psi_{R}(v)-\Psi_{R}(1-\beta)|\leq\epsilon\Delta_{N}\hskip
14.22636pt\textit{w.e.p.}$

Let $\\{s_{(k)}\\}_{k=1}^{s}$ be the elements of $S$ in increasing order and
let $p=\left\lceil(1-\beta)s\right\rceil$. By Lemma A.1,

$|s_{(p)}-(1-\beta)|\leq|s_{(p)}-\frac{p}{s}|+|\frac{p}{s}-(1-\beta)|\leq\frac{\epsilon\Delta_{N}}{2M}\hskip
14.22636pt\textit{w.e.p.}$

By part 1 of Assumption 5,

$\psi_{R}(s_{(k)})\leq\Psi_{R}(1-\beta)+\epsilon\Delta_{N},\hskip
14.22636pt\textit{w.e.p},$

for all $1\leq k\leq p$ and

$\Psi_{R}(1-\beta)-\epsilon\Delta_{N}\leq\psi_{R}(s_{(k)})\hskip
14.22636pt\textit{w.e.p},$

for all $p\leq k\leq s$. Therefore

$\left|\left\\{v\in
S\,:\,\psi_{R}(v)\leq\Psi_{R}(1-\beta)+\epsilon\Delta_{N}\right\\}\right|\geq
p\geq(1-\beta)s,\hskip 14.22636pt\textit{w.e.p},$

which implies that

$c_{R}\leq\Psi_{R}(1-\beta)+\epsilon\Delta_{N}\hskip
14.22636pt\textit{w.e.p.}$ (6.18)

On the other hand,

$\left|\left\\{v\in
S\,:\,\psi_{R}(v)\geq\Psi_{R}(1-\beta)-\epsilon\Delta_{N}\right\\}\right|\geq
s-p+1>\beta s\hskip 14.22636pt\textit{w.e.p},$

this is equivalent to

$\left|\left\\{v\in
S\,:\,\psi_{R}(v)\leq\Psi_{R}(1-\beta)-\epsilon\Delta_{N}\right\\}\right|<(1-\beta)s\hskip
14.22636pt\textit{w.e.p},$

which implies that

$c_{R}>\Psi_{R}(1-\beta)-\epsilon\Delta_{N}\hskip 14.22636pt\textit{w.e.p.}$
(6.19)

Combining Inequalities (6.18) and (6.19), we deduce that

$|c_{R}-\Psi(1-\beta)|\leq\epsilon\Delta_{N}\hskip 14.22636pt\textit{w.e.p.}$

The proof for $c_{L}$ is identical to the proof of $c_{R}$. ∎

The following proposition states that if we have two vertices $u,v\in S$ such
that (i) $u$ and $v$ are not very close to each other, and (ii) both of them
belong to one of the intervals $[0,1-\mu]$ or $[\mu,1]$. Then these vertices
can be ordered accurately using the graph-dependent functions $\psi_{R}$ and
$\psi_{L}$ w.e.p.

######  Proposition 6.3.

Let $\epsilon>0$. With extreme probability, the events

$\displaystyle\\{0\leq u<v\leq 1-\mu,\,\text{ and
}\,v>u+\epsilon\Delta_{N}\\}\Rightarrow\\{\psi_{R}(v)\geq\psi_{R}(u)\\},$
$\displaystyle\\{\mu\leq u<v\leq 1,\,\text{ and
}\,v>u+\epsilon\Delta_{N}\\}\Rightarrow\\{\psi_{L}(v)\leq\psi_{L}(u)\\}$

hold for all pairs $(u,v)\in S^{2}$.

###### Proof of Proposition 6.3.

Recall that $\hat{\sigma}_{T}$ from Algorithm 2 is the ordering obtained from
Algorithm 1 with input ${\left.\kern-1.2ptG\vphantom{\big{|}}\right|_{T}}$. By
Theorem 2, we know that for any $\eta\in(0,1/3)$ there exists a constant $C>0$
such that

$\left\|\hat{\sigma}_{T}-\sigma_{T}\right\|_{1}\leq C\,t^{2-\eta}$ (6.20)

holds w.e.p. Note that the difference between $\sigma_{T}$ and its reverse is
on the order of $t^{2}$. This means that, when Inequality (6.20) holds and $N$
is sufficiently large (equivalently $t$ is sufficiently large),
$\hat{\sigma}_{T}$ will be much closer to one of $\sigma_{T}$ or its reverse
(nothing close to a tie can occur). To simplify notation, in what follows, we
assume without loss of generality that $\hat{\sigma}_{T}$ is closer to
$\sigma_{T}$.

Fix $(u,v)\in S^{2}$ such that $0\leq u<v\leq 1-\mu$ and
$v>u+\epsilon\Delta_{N}$. Choose any $\kappa_{1},\kappa_{2}$ such that
$\alpha<\kappa_{1}<\kappa_{2}<\mu$, recall the definition of
$R_{\sigma}(\kappa_{1})$ from Equation (6.3),

$\displaystyle\mathbb{E}[\psi_{R}(v)-\psi_{R}(u)|\mathcal{F}_{T}]$
$\displaystyle=\frac{1}{t}\sum_{r\in R}(w(v,r)-w(u,r))$
$\displaystyle=\frac{1}{t}\sum_{r\in
R_{\sigma_{T}}(\kappa_{1})}(w(v,r)-w(u,r))+\frac{1}{t}\sum_{r\in R\setminus
R_{\sigma_{T}}(\kappa_{1})}(w(v,r)-w(u,r)).$

In what follows we will provide a lower bound for the the two summations
appearing in $\mathbb{E}[\psi_{R}(v)-\psi_{R}(u)|\mathcal{F}_{T}]$. In fact
there are two cases:

  1. 1.

$r\in R\setminus R_{\sigma_{T}}(\kappa_{1})$ : Let $K>0$ be the constant from
Assumption 1.

$w(v,r)-w(u,r)\geq-K(v-u)$ (6.21)

  2. 2.

$r\in R_{\sigma_{T}}(\kappa_{1})$ : In this case, $r=t_{(k)}$ for some
$k>(1-\kappa_{1})t$, where $t_{(k)}$’s are the order statistics of the
elements in $T$. By Lemma A.1,

$r=t_{(k)}\geq\frac{k}{t}-\Delta_{N}>(1-\kappa_{1})-\Delta_{N}>(1-\kappa_{2})\hskip
14.22636pt\textit{w.e.p.}$

That is

$r\in R_{\sigma_{T}}(\kappa_{1})\Rightarrow 0\leq u<v\leq
1-\mu<1-\kappa_{2}<r\leq 1\hskip 14.22636pt\textit{w.e.p.}$

Therefore $\min(|v-r|,|u-r|)\geq\mu-\kappa_{2}>\frac{\beta-\alpha}{2}$ w.e.p.
Applying Inequality (2.8) from Assumption 5, there exists some $d_{1}>0$ such
that

$w(v,r)-w(u,r)\geq d_{1}(v-u)\hskip 14.22636pt\textit{w.e.p.}$ (6.22)

Combining Inequalities (6.21) and (6.22),

$\mathbb{E}[\psi_{R}(v)-\psi_{R}(u)|\mathcal{F}_{T}]\geq\frac{d_{1}}{t}\left|R_{\sigma_{T}}(\kappa_{1})\right|(v-u)-\frac{K}{t}\left|R\setminus
R_{\sigma_{T}}(\kappa_{1})\right|(v-u)\hskip 14.22636pt\textit{w.e.p.}$

Clearly $\left|R_{\sigma_{T}}(\kappa_{1})\right|\geq\kappa_{1}t$. Moreover, if
$r\in R\setminus R_{\sigma_{T}}(\kappa_{1})$ then
$\hat{\sigma}_{T}(r)-\sigma_{T}(r)\geq(\kappa_{1}-\alpha)\,t>0$, thus

$\left\|\hat{\sigma}_{T}-\sigma_{T}\right\|_{1}\geq(\kappa_{1}-\alpha)\,t\,\left|R\setminus
R_{\sigma_{T}}(\kappa_{1})\right|.$ (6.23)

Finally we have w.e.p.,

$\displaystyle\mathbb{E}[\psi_{R}(v)-\psi_{R}(u)|\mathcal{F}_{T}]$
$\displaystyle\geq\frac{d_{1}}{t}\left|R_{\sigma_{T}}(\kappa_{1})\right|(v-u)-\frac{K}{t}\left|R\setminus
R_{\sigma_{T}}(\kappa_{1})\right|(v-u)$
$\displaystyle\stackrel{{\scriptstyle\text{Ineq }\eqref{eq:inequality-
sigmaHatT-
sigmaT}}}{{\geq}}\kappa_{1}d_{1}(v-u)-\frac{K}{(\kappa_{1}-\alpha)t^{2}}\left\|\hat{\sigma}_{T}-\sigma_{T}\right\|_{1}(v-u)$
$\displaystyle\stackrel{{\scriptstyle\text{Ineq
}\eqref{IneqPostHeur1}}}{{\geq}}\left(\kappa_{1}d_{1}-\frac{CK}{\kappa_{1}-\alpha}t^{-\eta}\right)(v-u)$
$\displaystyle\geq\frac{\kappa_{1}d_{1}}{2}(v-u)$
$\displaystyle\geq\frac{\epsilon\kappa_{1}d_{1}}{2}\Delta_{N}.$

Now, since $\psi_{R}(v)-\psi_{R}(u)$ is a weighted sum of Bernoulli random
variables sampled without uniformly without replacement. We can use
Hoeffding’s inequality for sampling without replacement [38, 22] to see that
the conditional probability bound

$\displaystyle\mathbb{P}[\psi_{R}(v)\geq\psi_{R}(u)|\mathcal{F}_{T}]$
$\displaystyle\geq
1-\exp\left(-\frac{t^{2}}{2N}\left(\frac{\epsilon\kappa_{1}d_{1}}{2}\right)^{2}\Delta^{2}_{\gamma}(N)\right)$
$\displaystyle\geq 1-\exp(-\delta N\Delta^{2}_{\gamma}(N))$
$\displaystyle=1-\varepsilon_{\gamma}^{\delta}(N)$

holds w.e.p555When we say that an inequality holds w.e.p we must specify what
is being viewed as random. To readers unfamiliar with random measures, this
might not be obvious in the preceding string of inequalities. We emphasize
here that we are viewing the probability
$\mathbb{P}[\psi_{R}(j)<\psi_{R}(i)|\mathcal{F}_{T}]$ itself as an
$\mathcal{F}_{T}$-measurable random variable (and we are viewing
$\mathbb{P}[\cdot|\mathcal{F}_{T}]$ as a random measure). Since
$\mathcal{F}_{T}$ is generated by the random choice of $T$ and the many
independent Bernoulli random variables contained in $A|_{T}$, it is $T$ and
$A|_{T}$ that are viewed as random in this expression. for some $\delta>0$.
The proof for $\psi_{L}$ is identical to the proof of $\psi_{R}$. ∎

We now list some further facts about $\psi_{R},\psi_{L}$:

######  Proposition 6.4.

Fix $\epsilon>0$. The following events hold w.e.p:

  1. 1.

For all $v\in S$,

$\displaystyle\\{\psi_{R}(v)<c_{R}\\}\Rightarrow\\{v\leq 1-\mu\\},$
$\displaystyle\\{\psi_{L}(v)<c_{L}\\}\Rightarrow\\{v\geq\mu\\}.$

  2. 2.

For all pairs $(u,v)\in S^{2}$,

$\displaystyle\\{\psi_{R}(u)<c_{R},\,\psi_{R}(v)>c_{R}\\}$
$\displaystyle\Rightarrow\\{u<v\,\text{ or }\,|u-v|\leq\epsilon\Delta_{N}\\},$
$\displaystyle\\{\psi_{L}(u)<c_{L},\,\psi_{L}(v)>c_{L}\\}$
$\displaystyle\Rightarrow\\{u>v\,\text{ or }\,|u-v|\leq\epsilon\Delta_{N}\\}.$

###### Proof of Proposition 6.4.

  1. 1.

According to Lemmas 6.1 and 6.2, with extreme probability we have

$\Psi_{R}(v)\leq\Psi_{R}(1-\beta)+\Delta_{N}<\Psi_{R}(1-\mu)\hskip 14.22636pt$

for all $v\in S$ such that $\psi_{R}(v)<c_{R}$. By part 1 of Assumption 5,
this implies that w.e.p. we have $\max\\{v\in
S\,:\,\psi_{R}(v)<c_{R}\\}<1-\mu$. The proof for $\psi_{L}$ is very similar.

  2. 2.

Recall $M$ from Equation (6.17), define
$m=\inf_{x\in[0,1-\mu]}\Psi_{R}^{\prime}(x)$. Consider $u,v\in S$ such that
$\psi_{R}(u)<c_{R}$ and $\psi_{R}(v)>c_{R}$. If $u\geq v$ then according to
the previous proposition $0\leq v\leq u\leq 1-\mu$. Moreover, applying Lemma
6.1 and 6.2 with $\epsilon^{\prime}=\tfrac{\epsilon m}{2}$ we get

$\Psi_{R}(1-\beta)-\frac{\epsilon
m}{2}\Delta_{N}\leq\Psi_{R}(v)\leq\Psi_{R}(u)\leq\Psi_{R}(1-\beta)+\frac{\epsilon
m}{2}\Delta_{N}\hskip 14.22636pt\textit{w.e.p.}$

Therefore

$|u-v|\leq\frac{1}{m}\left|\Psi_{R}(u)-\Psi_{R}(v)\right|\leq\Delta_{N}\hskip
14.22636pt\textit{w.e.p.}$

The proof for $\psi_{L}$ is very similar.

∎

Define the sets

$\displaystyle\mathcal{E}_{1}$ $\displaystyle=\\{(u,v)\in
S^{2}\,:\,\psi_{R}(u),\psi_{R}(v)<c_{R}\\},$ $\displaystyle\mathcal{E}_{2}$
$\displaystyle=\\{(u,v)\in S^{2}\,:\,\psi_{L}(u),\psi_{L}(v)<c_{L}\\},$
$\displaystyle\mathcal{E}_{3}$ $\displaystyle=\\{(u,v)\in
S^{2}\,:\,\psi_{R}(u)<c_{R}\\}.$

Recall the antisymmetric function $\hat{F}:S^{2}\to\\{-1,0,1\\}$ defined in
Equation (6.9) by

$\hat{F}(u,v)=\left\\{\begin{array}[]{ll}1-2\cdot\mathbf{1}_{\psi_{R}(u)>\psi_{R}(v)}&\mbox{if
}(u,v)\in\mathcal{E}_{1},\\\
1-2\cdot\mathbf{1}_{\psi_{L}(u)<\psi_{L}(v)}&\mbox{if
}(u,v)\in\mathcal{E}_{2},\cap\mathcal{E}_{1}^{c},\\\ 1&\mbox{if
}(u,v)\in\mathcal{E}_{3}\cap\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c},\\\
-1&\mbox{if
}(u,v)\in\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}\cap\mathcal{E}_{3}^{c}.\\\
\end{array}\right.$ (6.24)

Define the antisymmetric function $F:S^{2}\to\\{-1,0,1\\}$ by
$F(u,v)=1-2\cdot\mathbf{1}_{u>v}$. Note that the function $\hat{F}$ appearing
in Equation (6.24) is intended to estimate the function $F$. Informally,
Proposition 6.3 tells us that the first two branches of $\hat{F}$ appearing in
Equation (6.24) would agree with $F$ for all pairs of vertices $u,v\in
S\cap[0,1-\mu]$ if $u$ and $v$ are not very close and all pairs $u,v\in
S\cap[\mu,1]$ if $u$ and $v$ are not very close. However, the function
$\hat{F}$ defined in Equation (6.24) does not “know” if $u,v$ are in
$[0,1-\mu]$ or $[\mu,1]$; it uses the four branches in its definition to
guess. The following Lemma shows that the function $\hat{F}(u,v)$ defined in
Equation (6.24) is equal to the function $F(u,v)$ for all pairs of vertices
$u,v$ that are not very close.

######  Lemma 6.5.

Let $\epsilon>0$. The event

$\\{v>u+\epsilon\Delta_{N}\\}\Rightarrow\\{\hat{F}(u,v)=F(u,v)\\}$ (6.25)

for all pairs $(u,v)\in S^{2}$ holds w.e.p.

###### Proof of Lemma 6.5.

Let $(u,v)\in S^{2}$ such that $v>u+\epsilon\Delta_{N}$. We prove Equation
(6.25) via a case-by-case analysis of the performance of $\hat{F}$ in its four
branches. In fact we have four cases:

  1. 1.

$\mathcal{E}_{1}$ holds: By the first part of Proposition 6.4, we have
$u,v<1-\mu$ w.e.p. Applying Proposition 6.3 completes the proof of Equation
(6.25) in this case.

  2. 2.

$\mathcal{E}_{2}\cap\mathcal{E}_{1}^{c}$ holds: By the first part of
Proposition 6.4, we have $u,v>\mu$ w.e.p. Applying Proposition 6.3 completes
the proof in this case.

  3. 3.

$\mathcal{E}_{3}\cap\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}$ holds: By the
second part of Proposition 6.4, there are two possibilities. Either $\hat{F}$
makes the correct decision, or $|u-v|\leq\epsilon\Delta_{N}$ w.e.p.

  4. 4.

$\mathcal{E}_{1}^{c}\cap\mathcal{E}_{2}^{c}\cap\mathcal{E}_{3}^{c}$ holds:
Again by the second part of Proposition 6.4, there are two possibilities.
Either $\hat{F}$ makes the correct decision, or $|u-v|\leq\epsilon\Delta_{N}$
w.e.p.

∎

Similarly, recall the function $\hat{f}$ defined in Equation (6.10). The
following Lemma shows that the function $\hat{f}$ makes the correct ordering
“guess” almost all the time; that is for $(u,v)\in S^{2}$ such that $u$ and
$v$ are not very close we have $(\hat{f}(v)-\hat{f}(u))(v-u)>0$.

######  Lemma 6.6.

Fix $\epsilon>0$. The event that

$\\{v>u+\epsilon\Delta_{N}\\}\Rightarrow\\{\hat{f}(v)>\hat{f}(u)\\}$

holds for all pairs $(u,v)\in S^{2}$ occurs w.e.p.

###### Proof Lemma 6.6.

Fix $(u,v)\in S^{2}$ with $v>u+\epsilon\Delta_{N}$. Define the set

$\mathcal{A}=\left\\{r\in
V\,:\,\min(|u-r|,|v-r|)>\frac{\epsilon}{8}\Delta_{N}\right\\}.$

By Lemma 6.5, for all $r\in\mathcal{A}$

$\hat{F}(r,v)=F(r,v)\,\text{ and }\,\hat{F}(r,u)=F(r,u)\hskip
14.22636pt\textit{w.e.p.}$

Therefore we have w.e.p.

$\displaystyle\hat{f}(v)-\hat{f}(u)$ $\displaystyle=\sum_{r\in
V}\mathbf{1}_{r\in S}\left(\hat{F}(r,v)-\hat{F}(r,u)\right)$
$\displaystyle=\sum_{r\in\mathcal{A}}\mathbf{1}_{r\in
S}\left(F(r,v)-F(r,u)\right)+\sum_{r\in\mathcal{A}^{c}}\mathbf{1}_{r\in
S}\left(\hat{F}(r,v)-\hat{F}(r,u)\right)$ $\displaystyle\geq
2\left|\left\\{r\in
S\,:\,u<r<v\right\\}\right|-2\left|S\cap\mathcal{A}^{c}\right|$
$\displaystyle=2(A-B),$

where

$A=\sum_{k\in E_{1}}\mathbf{1}_{v_{k}\in S},\,\,B=\sum_{k\in
E_{2}}\mathbf{1}_{v_{k}\in S},$

with $E_{1}=\left\\{k\in[N]\,:\,Nu<k<Nv\right\\}$ and
$E_{2}=\left\\{k\in[N]\,:\,\min(|k-Nu|,|k-Nv|)\leq\left\lfloor\frac{\epsilon}{8}N\Delta_{N}\right\rfloor\right\\}$.
Note that, $A$ and $B$ appearing in this bound are sums of Bernoulli random
variables sampled without replacement. That is $A,B$ are hypergeometric random
variables, with $A\sim\mathcal{HG}(N;Nv-Nu-1;s)$ and
$B\sim\mathcal{HG}(N;4\left\lfloor\frac{\epsilon}{8}N\Delta_{N}\right\rfloor+2;s)$.
We have

$\mathbb{E}[A-B]=\frac{s}{N}\left(N(v-u)-4\left\lfloor\frac{\epsilon}{8}N\Delta_{N}\right\rfloor-3\right)>\frac{\epsilon}{10}N\Delta_{N}\hskip
14.22636pt\textit{w.e.p.}$

Thus, by the usual analogue to Hoeffding’s inequality for hypergeometric
random variables [38, 22], we have

$\hat{f}(v)-\hat{f}(u)>0\hskip 14.22636pt\textit{w.e.p.}$ (6.26)

∎

We are now ready to prove Theorem 8.

###### Proof of Theorem 8.

Let $s_{(k)}$’s be the order statistics of the set $S$. Fix $1\leq k\leq s$,
recall that

$\hat{\sigma}_{S}(s_{(k)})=\left|\left\\{p\in[s]\,:\,\hat{f}(s_{(p)})\leq\hat{f}(s_{(k)})\right\\}\right|\,\text{
and }\,\sigma_{S}(s_{(k)})=k.$

For any integer $p\leq k-\frac{\epsilon}{2}N\Delta_{N}$ we have $s_{(p)}\leq
s_{(k)}-\frac{\epsilon}{2}\Delta_{N}$, thus by Lemma 6.6

$\forall p\leq\left\lfloor
k-\frac{\epsilon}{2}N\Delta_{N}\right\rfloor\,:\,\hat{f}(s_{p})<\hat{f}(s_{(k)})\hskip
14.22636pt\textit{w.e.p.}$

Therefore

$\hat{\sigma}_{S}(s_{(k)})\geq\left\lfloor
k-\frac{\epsilon}{2}N\Delta_{N}\right\rfloor\geq k-\epsilon N\Delta_{N}\hskip
14.22636pt\textit{w.e.p.}$

Similarly for any $p\geq k+\frac{\epsilon}{2}N\Delta_{N}$ we have $s_{(p)}\geq
s_{(k)}+\frac{\epsilon}{2}\Delta_{N}$, thus by Lemma 6.6

$\forall p\geq\left\lceil
k+\frac{\epsilon}{2}N\Delta_{N}\right\rceil\,:\,\hat{f}(s_{p})>\hat{f}(s_{(k)})\hskip
14.22636pt\textit{w.e.p.}$

Therefore

$\hat{\sigma}_{S}(s_{(k)})\leq\left\lceil
k+\frac{\epsilon}{2}N\Delta_{N}\right\rceil\leq k+\epsilon N\Delta_{N}\hskip
14.22636pt\textit{w.e.p.}$

Finally,

$\left(\forall v\in
S\right)\,:\,\left|\hat{\sigma}_{S}(v)-\sigma_{S}(v)\right|\leq\epsilon
N\Delta_{N}=\epsilon\sqrt{N\log^{\gamma}(N)}\hskip 14.22636pt\textit{w.e.p},$

as required. ∎

###  6.4 Proof of Theorem 3 and analysis of Algorithm 3

We now prove the main bounds on the objects appearing in Algorithm 3,
completing the proof of Theorem 3. Throughout this section, we use notation
from Algorithm 3 and make the same assumptions as in the statement of Theorem
3. By Theorem 8,

$\|\hat{\sigma}_{j}-\sigma_{S_{j}}\|_{\infty}\leq\frac{\epsilon}{12}\,\sqrt{N\log^{\gamma}(N)}$
(6.27)

holds for all $j\in\\{1,2,3\\}$ w.e.p.

We next discuss Step 3 of the algorithm. Recall the definition of aligned and
closely aligned from Inequality (6.2). Note that
$\\{\hat{\sigma}_{j}\\}_{j\in\\{1,2,3\\}}$ were computed in separate calls to
Algorithm 2 and so they may not be aligned - that is, some $\hat{\sigma}_{j}$
may be aligned with $\sigma_{S_{j}}$ while others may be aligned more with its
reverse $\mathrm{rev}(\sigma_{S_{j}})$. When $N$ is large enough all the
$\sigma_{S_{j}}$’s are closely aligned with $id_{N}$. Moreover, when
Inequality (6.27) holds and $N$ sufficiently large, $\hat{\sigma}_{j}$ will
either be closely aligned with $\sigma_{S_{j}}$ or with
$\mathrm{rev}(\sigma_{S_{j}})$. That is, $\hat{\sigma}_{j}$ will be be closely
aligned with $id_{N}$ or with its reverse for all $j\in\\{1,2,3\\}$. For the
same reason, for $N$ sufficiently large $\hat{\sigma}_{\mathrm{ref}}$ will
either be closely aligned with $id_{N}$ or with $\mathrm{rev}(id_{N})$. We
assume without loss of generality that $\hat{\sigma}_{\mathrm{ref}}$ is
closely aligned with $id_{N}$. Finally, note that w.e.p., $|S_{j}\cap
S^{\prime}_{2}|\geq 2$ for all $j\in\\{1,2,3\\}$. When all of these events
occur, for each $j\in\\{1,2,3\\}$, one of the following two cases must occur:

  1. 1.

$\hat{\sigma}_{j}$ is closely aligned with $id_{N}$. Since $|S_{j}\cap
S^{\prime}_{2}|\geq 2$ and $\hat{\sigma}_{j}$, $\hat{\sigma}_{\mathrm{ref}}$
are both closely aligned to $id_{N}$, they must also be closely aligned to
each other. Thus, in this case, $\hat{\sigma}_{j}$ is not reversed in step 3
of the algorithm and remains closely aligned to $id_{N}$ in step 4.

  2. 2.

$\hat{\sigma}_{j}$ is closely aligned with $\mathrm{rev}(id_{N})$. Since
$|S_{j}\cap S^{\prime}_{2}|\geq 2$ and $\mathrm{rev}(\hat{\sigma}_{j})$,
$\hat{\sigma}_{\mathrm{ref}}$ are both closely aligned to $id_{N}$, they must
also be aligned aligned to each other. Thus, in this case, $\hat{\sigma}_{j}$
is reversed in step 3 of the algorithm and becomes closely aligned to $id_{N}$
in step 4.

Thus, in both cases, by step 4 the ordering $\hat{\sigma}_{j}$ is closely
aligned to $id_{N}$ for all $j\in\\{1,2,3\\}$ w.e.p.

Denote by $s_{1}^{(k)},s_{2}^{(k)}$ and $s_{3}^{(k)}$ the order statistics of
the sets $S_{1},S_{2}$ and $S_{3}$ respectively. Then by Equation (6.1) we
have

$\displaystyle\left\|\hat{\sigma}-id_{N}\right\|_{\infty}$
$\displaystyle=\left\|\hat{\sigma}^{-1}-id_{N}\right\|_{\infty}$
$\displaystyle=N\max_{j\in\\{1,2,3\\}}\max_{k\in\\{1,\ldots,n+1\\}}\left|\hat{\sigma}_{j}^{-1}(k)-v_{3k+j-3}\right|$
$\displaystyle\leq
N\max_{j\in\\{1,2,3\\}}\max_{k\in\\{1,\ldots,n+1\\}}\left|\hat{\sigma}_{j}^{-1}(k)-v_{3k}\right|+2$
$\displaystyle=\max_{j\in\\{1,2,3\\}}\max_{k\in\\{1,\ldots,n+1\\}}\left|3\hat{\sigma}_{j}(s_{j}^{(k)})-Ns_{j}^{(k)}\right|+2$
$\displaystyle\leq
3\max_{j\in\\{1,2,3\\}}\left\|\hat{\sigma}_{j}-\sigma_{S_{j}}\right\|_{\infty}+N\max_{j\in\\{1,2,3\\}}\max_{k\in\\{1,\ldots,n+1\\}}\left|s_{j}^{(k)}-v_{3k}\right|+2.$

By Lemma A.1,

$\left|s_{j}^{(k)}-v_{3k}\right|\leq\frac{\epsilon}{4}\Delta_{N}\hskip
14.22636pt\textit{w.e.p},$ (6.28)

for all $j\in\\{1,2,3\\}$ and $k\in\\{1,\ldots,n+1\\}$ such that $3k+j\leq N$.
When $N$ is large enough, and when inequalities (6.27) and (6.28) hold, we get

$\left\|\hat{\sigma}-id_{N}\right\|_{\infty}\leq\epsilon\sqrt{N\log^{\gamma}(N)}\hskip
14.22636pt\textit{w.e.p.}$

which completes the proof.

######  Remark 6.7 (Learning $\alpha$ and $\beta$).

Algorithm 2 takes parameters $\alpha,\beta$ as given. However, our results
only apply if these parameters satisfy Assumption 5. In Theorem 1, we state
values of $(\alpha,\beta)$ for which the graphons satisfying Assumption 1.2
will also satisfy Assumption 5, and so there are no difficulties in that
setting.

However, for other graphons, it may not be obvious how to choose
$\alpha,\beta$. We note here that, when graphons satisfy a slightly
strengthened version of the assumption for some pair $\alpha,\beta$, it is not
difficult to learn this pair quickly. We now give details.

Note that the functions
$\Psi_{R}=\Psi_{R}^{(\alpha)},\Psi_{L}=\Psi_{L}^{(\alpha)}$ depend on the
parameter $\alpha$ (though this dependence is suppressed in our notation).
Recall that $\Psi_{R},\Psi_{L}$ are continuous functions. If $w$ satisfies
Inequality (2.7) for some $\alpha<\beta$, then there exists some $\delta>0$
and some other pair $\alpha^{\prime},\beta^{\prime}$ so that it satisfies the
slightly strengthened bound

$\inf_{x\in[1-\alpha^{\prime}-2\delta,1]}\Psi_{R}^{(\alpha^{\prime})}(x)>\Psi_{R}^{(\alpha^{\prime})}(1-\beta^{\prime})+2\delta,\qquad\inf_{x\in[0,\alpha^{\prime}+2\delta]}\Psi_{L}^{(\alpha^{\prime})}(x)>\Psi_{L}^{(\alpha^{\prime})}(\beta^{\prime})+2\delta,$
(6.29)

By Lemma 6.1 the estimates $\psi_{R}$, $\psi_{L}$ calculated in Equations
(6.5), (6.6) have error $\Delta_{N}$ going to 0 with $N$. Thus, for all $N$
sufficiently large, with extreme probability any pair
$(\alpha^{\prime},\beta^{\prime})$ satisfying (6.29) will also satisfy

$\inf_{x\in[1-\alpha^{\prime}-\delta,1]}\psi_{R}^{(\alpha^{\prime})}(x)>\psi_{R}^{(\alpha^{\prime})}(1-\beta^{\prime})+\delta,\qquad\inf_{x\in[0,\alpha^{\prime}+\delta]}\psi_{L}^{(\alpha^{\prime})}(x)>\psi_{L}^{(\alpha^{\prime})}(\beta^{\prime})+\delta.$
(6.30)

Applying Lemma 6.1 again, any pair satisfying the Inequality (6.30) will also
satisfy Inequality (2.7).

Thus, if a graphon satisfies (6.29) for some $\delta>0$ and some pair
$(\alpha,\beta)$, we can find the pair $(\alpha^{\prime},\beta^{\prime})$ by
using Inequality (6.30) as a test. Since the bound in Lemma 6.1 is a bound on
the maximum error, checking many pairs $(\alpha^{\prime},\beta^{\prime})$ from
a single observed graph does not present any obstacles.

##  7 Application

We show that Theorem 1 follows from Theorems 2 and 3. To do so, it is enough
to check that any graphon that is “nice" in the sense of Definition 1.2 will
also satisfy Assumptions 1 through 5.

We now check Assumptions 1 through 5 in order.

Assumption 1: Define $R_{\max}=\sup_{r\in(0,1]}R^{\prime}(r)<\infty$. We
calculate

$\displaystyle\left|w(x,y)-w(x^{\prime},y^{\prime})\right|$
$\displaystyle=\left|R(|x-y|)-R(|x^{\prime}-y^{\prime}|)\right|$
$\displaystyle\leq R_{\max}\left|\,|x-y|-|x^{\prime}-y^{\prime}|\,\right|$
$\displaystyle\leq R_{\max}\left|(x-y)-(x^{\prime}-y^{\prime})\right|$
$\displaystyle\leq R_{\max}(|x-y|+|x^{\prime}-y^{\prime}|).$

Assumption 2: We have $\frac{\partial w(x,y)}{\partial x}=R^{\prime}(y)$ for
$y\neq x$, so this follows immediately from Definition 1.2.

Assumption 3: We calculate

$\displaystyle d^{\prime}(x)$
$\displaystyle=\frac{d}{dx}\int_{0}^{1}R(|x-y|)dy$
$\displaystyle=\frac{d}{dx}\left(\int_{0}^{x}R(y)dy+\int_{0}^{1-x}R(y)dy\right)$
$\displaystyle=R(x)-R(1-x).$

Thus $d^{\prime}(x)$ exists for all $x\in[0,1]$. Since $R$ is monotone,
$d^{\prime}(x)>0$ for $x\in[0,0.5)$ and $d^{\prime}(x)<0$ for $x\in(0.5,0]$,
with $d^{\prime}(x)=0$ only for $x=0.5$.

Assumption 4: This is given in [32], with the function $h$ in that reference
replacing the function $R$ in this paper.

Assumption 5: To prove Inequality (2.7), we have

$\displaystyle\inf_{x\in[0,0.05]}\Psi_{L}(x)$
$\displaystyle=\inf_{x\in[0,0.05]}\int_{0}^{0.05}w(x,y)dy$
$\displaystyle=\inf_{x\in[0,0.05]}\int_{0}^{0.05}R(|x-y|)dy.$

Since $R$ is monotone, this infimum is achieved at $x=0$ and $x=0.05$.
Continuing the calculation,

$\displaystyle\inf_{x\in[0,0.05]}\Psi_{L}(x)$
$\displaystyle=\int_{0}^{0.05}R(y)dy$ $\displaystyle>\int_{0.26}^{0.31}R(y)dy$
$\displaystyle=\Psi_{L}(0.31),$

where the strict inequality in the second line comes from the assumption that
$R^{\prime}$ is continuous and strictly positive. This proves one of the four
inequalities in the first part Assumption 5; the remainder are essentially the
same.

To prove Inequality (2.8), recall that $\frac{\partial w(x,y)}{\partial
x}=R^{\prime}(y)>0$. Thus, this follows immediately from Gronwall’s
inequality.

##  8 Discussion

In this paper, we have written down a simple seriation algorithm and shown
that, for some fairly large class of model graphons, the result of the
algorithm is an estimated permutation $\hat{\sigma}$ with sup-norm error of
roughly $O(\sqrt{N})$. It is natural to ask whether either the rates of
convergence or our assumptions about the generating graphon are optimal.

The second question seems to have an easy answer: we are quite sure that our
conditions are not optimal, even for the type of analysis we use. In
particular, our main assumptions on $w$ imply that all vertices have a fairly
non-negligible chance of being connected (more precisely, our main assumptions
imply that $w(x,y)>0$ for all $x,y\in[0,1]$). We have already seen in Remark
2.1 that this property is not satisfied for many natural graphons, and also
that it can be substantially weakened.

We hypothesize that this global connection property can be replaced by a much
weaker assumption, saying roughly that some power of the adjacency matrix
should be globally connected. The main difficulties in carrying this out are
different for our two main results:

  * •

The main difficulty in extending Theorem 2 is carrying through the arguments
in Section 3, which show that the Fiedler eigenspace has dimension 1 and that
the Fiedler function is monotone.

As discussed in Remark 2.1, this can sometimes be checked directly for
particularly simple graphons. We also expect that certain generic techniques,
such as perturbation analysis, can be used to extend this to small
nonparametric families of graphons. However, we do not know how to get rid of
this assumption in any great generality.

  * •

The main difficulty in extending Theorem 3 is not merely technical: Algorithm
3 will not generally give a sensible answer without the global connectedness
property. This occurs because the functions $\psi_{R}(i),\psi_{L}(i)$ may both
be 0 for many $i\in[N]$. In [25], we introduce a “local" quantity $R(i,j)$
that is analogous to the “global" quantity $R$ used in the present paper. We
suspect that a similar approach would work in the present context.

We don’t know the optimal rate of convergence for this problem in very many
metrics, but we give a few related results largely drawn from our companion
paper [25]. Note that this paper studies a slightly different sampling scheme,
but very similar arguments apply:

  1. 1.

Under slightly different model conditions, the iterated post-processing
algorithm of [25] can obtain error of $O(N^{\epsilon})$ for any fixed
$\epsilon>0$, so the rate $N^{0.5}$ is certainly not optimal for all classes
of graphon models.

  2. 2.

On the other hand, we might ask to estimate the latent positions
$v_{1},\ldots,v_{N}$ of vertices in addition to the latent permutation
$\sigma$. The argument in Section 5 of [25] says that any such estimate must
suffer an error of at least $\Omega(N^{-0.5})$ for any sufficiently large
class of graphon models. Since the natural estimate

$\hat{v}_{i}=\frac{\hat{\sigma}(i)}{N}$

is so similar to $\hat{\sigma}$ itself, this suggests that one can’t do much
better in general.

Several other papers have recently studied the optimal rate of convergence for
“the" noisy seriation problem, including [29] and [18]. Their models and
versions of the noisy seriation problem are different enough from ours that it
is not possible to directly compare the results. We leave the question of
comparing these notions of noisy seriation to future work.

### Acknowledgements

We thank Iosif Pinelis for his detailed response [32] on MathOverflow. The
response was quite a bit of work, given without any request for reward, and
let us substantially simplify the assumptions appearing in Section 2.

## References

  * [1] [author] Abbe, EmmanuelE. (2018). Community Detection and Stochastic Block Models: Recent Developments. Journal of Machine Learning Research 18 1-86.
  * [2] [author] Atkins, Jonathan EJ. E., Boman, Erik GE. G. and Hendrickson, BruceB. (1998). A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing 28 297–310.
  * [3] [author] Avella-Medina, MarcoM., Parise, FrancescaF., Schaub, MichaelM. and Segarra, SantiagoS. (2018). Centrality measures for graphons: Accounting for uncertainty in networks. IEEE Transactions on Network Science and Engineering.
  * [4] [author] Bagaria, VivekV., Ding, JianJ., Tse, DavidD., Wu, YihongY. and Xu, JiamingJ. (2020). Hidden Hamiltonian Cycle Recovery via Linear Programming. Operations Research 68 53-70. 10.1287/opre.2019.1886
  * [5] [author] Cai, TonyT., Liang, TengyuanT. and Rakhlin, AlexanderA. (2017). On Detection and Structural Reconstruction of Small-World Random Networks. IEEE Transactions on Network Science and Engineering 4 165-176. 10.1109/TNSE.2017.2703102
  * [6] [author] Chatterjee, SouravS. (2015). Matrix estimation by universal singular value thresholding. The Annals of Statistics 43 177–214.
  * [7] [author] Chuangpishit, HudaH., Ghandehari, MahyaM., Hurshman, MatthewM., Janssen, JeannetteJ. and Kalyaniwalla, NauzerN. (2015). Linear embeddings of graphs and graph limits. Journal of Combinatorial Theory, Series B 113 162–184.
  * [8] [author] Chung, FanF. and Radcliffe, MaryM. (2011). On the spectra of general random graphs. Electronic Journal of Combinatorics 18 215\.
  * [9] [author] Corneil, Derek GD. G. (2004). A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Applied Mathematics 138 371–379.
  * [10] [author] Daniely, AmitA., Linial, NatiN. and Saks, MichaelM. (2012). Clustering is difficult only when it does not matter. arXiv preprint arXiv:1205.4891.
  * [11] [author] Davis, ChandlerC. and Kahan, William MortonW. M. (1970). The rotation of eigenvectors by a perturbation. SIAM Journal on Numerical Analysis 7 1–46.
  * [12] [author] de Haan, LaurensL. and Ferreira, AnaA. (2006). Extreme Value Theory. Springer-Verlag.
  * [13] [author] Diaconis, PersiP. and Graham, Ronald LR. L. (1977). Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological) 262–268.
  * [14] [author] Ding, ChrisC. (2004). A tutorial on spectral clustering. In Talk presented at ICML.(Slides available at http://crd.lbl.gov/~cding/Spectral/).
  * [15] [author] Ding, JianJ., Wu, YihongY., Xu, JiamingJ. and Yang, DanaD. (2020). Consistent recovery threshold of hidden nearest neighbor graphs. Proceedings of Thirty Third Conference on Learning Theory 125 1540–1553.
  * [16] [author] Donath, William EW. E. and Hoffman, Alan JA. J. (2003). Lower bounds for the partitioning of graphs. In Selected Papers Of Alan J Hoffman: With Commentary 437–442. World Scientific.
  * [17] [author] Edmunds, David ED. E., Potter, AJBA. and Stuart, Charles AlexanderC. A. (1972). Non-compact positive operators. Proc. R. Soc. Lond. A 328 67–81.
  * [18] [author] Flammarion, NicolasN., Mao, ChengC. and Rigollet, PhilippeP. (2019). Optimal rates of statistical seriation. Bernoulli 25 623–653.
  * [19] [author] Fogel, FajwelF., d’Aspremont, AlexandreA. and Vojnovic, MilanM. (2014). Serialrank: Spectral ranking using seriation. In Advances in Neural Information Processing Systems 900–908.
  * [20] [author] Gertzen, Thomas LT. L. and Grötschel, MartinM. (2012). Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology. Documenta Mathematica 199–210.
  * [21] [author] Glasscock, DanielD. (2015). What is… a Graphon? Notices of the AMS 62\.
  * [22] [author] Greene, EvanE. and Wellner, Jon AJ. A. (2017). Exponential bounds for the hypergeometric distribution. Bernoulli: official journal of the Bernoulli Society for Mathematical Statistics and Probability 23 1911\.
  * [23] [author] Gustafson, KK. and Weidmann, JoachimJ. (1969). On the essential spectrum. Journal of Mathematical Analysis and Applications 25 121–127.
  * [24] [author] Janssen, JeannetteJ. and Ghandehari, MahyaM. (2018). An optimization parameter for seriation of noisy data. arXiv preprint arXiv:1803.10354.
  * [25] [author] Janssen, JeannetteJ. and Smith, AaronA. (2019). Reconstruction of Linear Embeddings of Graphons. preprint.
  * [26] [author] Krzakala, FlorentF., Moore, CristopherC., Mossel, ElchananE., Neeman, JoeJ., Sly, AllanA., Zdeborová, LenkaL. and Zhang, PanP. (2013). Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences 110 20935–20940.
  * [27] [author] Liiv, InnarI. (2010). Seriation and matrix reordering methods: An historical overview. Statistical Analysis and Data Mining: The ASA Data Science Journal 3 70–91.
  * [28] [author] Lovász, LászlóL. (2012). Large networks and graph limits 60\. American Mathematical Soc.
  * [29] [author] Mao, ChengC., Pananjady, AshwinA. and Wainwright, Martin J.M. J. (2018). Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time. In Proceedings of the 31st Conference On Learning Theory (SébastienS. Bubeck, VianneyV. Perchet and PhilippeP. Rigollet, eds.). Proceedings of Machine Learning Research 75 2037–2042. PMLR.
  * [30] [author] Mao, ChengC., Weed, JonathanJ. and Rigollet, PhilippeP. (2019). Minimax Rates and Efficient Algorithms for Noisy Sorting. ALT.
  * [31] [author] Petrie, WM FlindersW. F. (1899). Sequences in prehistoric remains. Journal of the Anthropological Institute of Great Britain and Ireland 295–301.
  * [32] [author] Pinelis, IosefI. Infimum upper bound (answer). MathOverflow. URL:https://mathoverflow.net/questions/324561/infimum-upper-bound (visited on 2021-09-10).
  * [33] [author] Recanati, AntoineA., Servant, NicolasN., Vert, Jean-PhilippeJ.-P. and d’Aspremont, AlexandreA. (2018). Robust Seriation and Applications to Cancer Genomics. arXiv preprint arXiv:1806.00664.
  * [34] [author] Reed, MichaelM. (2012). Methods of modern mathematical physics: Functional analysis. Elsevier.
  * [35] [author] Robinson, William SW. S. (1951). A method for chronologically ordering archaeological deposits. American antiquity 16 293–301.
  * [36] [author] Rocha, IsraelI., Janssen, JeannetteJ. and Kalyaniwalla, NauzerN. (2018). Recovering the structure of random linear graphs. Linear Algebra and its Applications 557 234–264.
  * [37] [author] Seminaroti, MatteoM. (2016). Combinatorial algorithms for the seriation problem Technical Report, Tilburg University, School of Economics and Management.
  * [38] [author] Serfling, Robert JR. J. (1974). Probability inequalities for the sum in sampling without replacement. The Annals of Statistics 39–48.
  * [39] [author] Teschl, GeraldG. (2009). Mathematical methods in quantum mechanics. Graduate Studies in Mathematics 99 106\.
  * [40] [author] Von Luxburg, UlrikeU. (2007). A tutorial on spectral clustering. Statistics and computing 17 395–416.
  * [41] [author] Von Luxburg, UlrikeU., Belkin, MikhailM. and Bousquet, OlivierO. (2008). Consistency of spectral clustering. The Annals of Statistics 555–586.

##  Appendix A Appendix

######  Lemma A.1.

Let $V=\\{v_{1},v_{2},\ldots,v_{N}\\}$ with $v_{i}=i/N$ for all $i$. Let $S$
be a subset of $V$ chosen uniformly at random and with deterministic size
$m=|S|$ such that $\left\lfloor\tfrac{N}{3}\right\rfloor\leq
m\leq\left\lfloor\tfrac{N}{3}\right\rfloor+1$. Define
$s_{(1)}<s_{(2)}<\ldots<s_{(m)}$ to be the order statics of the elements of
$S$. Then for each $1\leq k\leq m$ and for any $c>0$, there exists a constant
$\delta>0$ and an integer $N_{0}$ such that

$\mathbb{P}\left(\left|s_{(k)}-\frac{k}{m}\right|>c\Delta_{N}\right)\leq\varepsilon_{\gamma}^{\delta}(N)$

for all $N\geq N_{0}$. In other words for each $1\leq k\leq m$ and $c>0$ the
event $\left|s_{(k)}-\frac{k}{m}\right|\leq c\Delta_{N}$ holds w.e.p.

###### Proof of Lemma A.1.

Let $1\leq k\leq N$ and $k\leq j\leq N-m+k$. Then $s_{(k)}=v_{j}$ if and only
if there is exactly $k-1$ elements from $S$ less than $v_{j}$ and exactly
$m-k$ elements from $S$ bigger than $v_{j}$. Therefore

$\mathbb{P}\left(s_{(k)}=v_{j}\right)=\frac{\binom{j-1}{k-1}\binom{N-j}{m-k}}{\binom{N}{m}}.$

Note that the distribution of $s_{(k)}$ looks very similar to a negative
hypergeometric distribution. In fact one can easily check that
$Ns_{(k)}-k\sim\mathcal{NHG}(N;N-m;k)$.

The paper [38] provides concentration inequalities for sampling without
replacement. According to [38, 22], for any $\lambda>0$ we have

$\mathbb{P}\left(|s_{(k)}-\mathbb{E}[s_{(k)}]|>\lambda\right)\leq
2\exp\left(\frac{-2N^{2}\lambda^{2}}{m(1-f_{m}^{*})}\right)$

with $f_{m}^{*}=(m-1)/N$. We can check that $1/4<f_{m}^{*}\leq 1/3$ for all
$N$ sufficiently large. Thus,

$\mathbb{P}\left(|s_{(k)}-\mathbb{E}[s_{(k)}]|>\lambda\right)\leq
2\exp\left(\frac{-8N^{2}\lambda^{2}}{3m}\right).$

Let $c>0$, we have

$\displaystyle|s_{(k)}-\frac{k}{m}|>c\Delta_{N}$
$\displaystyle\Rightarrow|s_{(k)}-\mathbb{E}[s_{(k)}]|>c\Delta_{N}-|\frac{k}{m}-\mathbb{E}[s_{(k)}]|$
$\displaystyle\Rightarrow|s_{(k)}-\mathbb{E}[s_{(k)}]|>c\Delta_{N}-\frac{(N-m)k}{Nm(m+1)}$
$\displaystyle\Rightarrow|s_{(k)}-\mathbb{E}[s_{(k)}]|>c\Delta_{N}-\frac{2}{N}.$

For $N$ large enough so that $4<cN\Delta_{N}$,

$|s_{(k)}-\frac{k}{m}|>c\Delta_{N}\Rightarrow|s_{(k)}-\mathbb{E}[s_{(k)}]|>\frac{c}{2}\Delta_{N}.$

Therefore

$\displaystyle\mathbb{P}\left(|s_{(k)}-\frac{k}{m}|>c\Delta_{N}\right)$
$\displaystyle\leq\mathbb{P}\left(|s_{(k)}-\mathbb{E}[s_{(k)}]|>\frac{c}{2}\Delta_{N}\right)$
$\displaystyle\leq 2\exp\left(\frac{-2c^{2}N^{2}\Delta_{N}^{2}}{3m}\right)$
$\displaystyle\leq 2\exp\left(-c^{2}N\Delta_{N}^{2}\right)$
$\displaystyle\leq\varepsilon_{\gamma}^{\delta}(N)$

for some $0<\delta<c^{2}$. ∎