MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

arXiv:1608.03860v1 [math.CO] 12 Aug 2016

PETER DIAO1 , DOMINIQUE GUILLOT2 , APOORVA KHARE3 , AND BALA RAJARATNAM3
Abstract. In this paper, we exploit the theory of dense graph limits to provide a new framework
to study the stability of graph partitioning methods, which we call structural consistency. Both
stability under perturbation as well as asymptotic consistency (i.e., convergence with probability 1 as
the sample size goes to infinity under a fixed probability model) follow from our notion of structural
consistency. By formulating structural consistency as a continuity result on the graphon space,
we obtain robust results that are completely independent of the data generating mechanism. In
particular, our results apply in settings where observations are not independent, thereby significantly
generalizing the common probabilistic approach where data are assumed to be i.i.d.
In order to make precise the notion of structural consistency of graph partitioning, we begin by
extending the theory of graph limits to include vertex colored graphons. We then define continuous
node-level statistics and prove that graph partitioning based on such statistics is consistent. Finally,
we derive the structural consistency of commonly used clustering algorithms in a general model-free
setting. These include clustering based on local graph statistics such as homomorphism densities,
as well as the popular spectral clustering using the normalized Laplacian.
We posit that proving the continuity of clustering algorithms in the graph limit topology can
stand on its own as a more robust form of model-free consistency. We also believe that the mathematical framework developed in this paper goes beyond the study of clustering algorithms, and will
guide the development of similar model-free frameworks to analyze other procedures in the broader
mathematical sciences.

Contents
1. Introduction
1.1. Informal statements of results
2. Review of dense graph limits
3. Colored graph limit theory
3.1. Colored graphs
3.2. Colored graphons and homomorphism densities
3.3. Cut metric
4. Clustering by continuous node-level statistics
4.1. Structural consistency of clustering by homomorphism densities
4.2. Sensitivity of clustering based on node-level statistics
5. Spectral clustering
5.1. Convergence of eigenvalues and eigenvectors
5.2. Convergence of Laplacians
5.3. The normalized Laplacian

2
3
5
7
7
7
8
9
12
14
15
16
17
20

Date: August 15, 2016.
2010 Mathematics Subject Classification. 05C50, 47B34, 62H30, 47B38, 62G20.
Key words and phrases. Graph partitioning, consistency, graphons, colored graph limits, node-level statistic, spectral clustering, normalized Laplacian.
P.D., D.G., A.K., and B.R. are partially supported by the following: US Air Force Office of Scientific Research
grant award FA9550-13-1-0043, US National Science Foundation under grant DMS-0906392, DMS-CMG 1025465,
AGS-1003823, DMS-1106642, DMS-CAREER-1352656, Defense Advanced Research Projects Agency DARPA YFA
N66001-11-1-4131, the UPS Foundation, SMC-DBNKY, an NSERC postdoctoral fellowship, and the University of
Delaware Research Foundation.
1

2

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

5.4. Structural consistency of spectral clustering (normalized Laplacian)
Appendix A. Proofs for dense S-colored graph limit theory
Appendix B. Riesz–Fischer theorem for metric space-valued maps
References

25
27
31
32

1. Introduction
In this paper, we characterize continuity of certain maps from graphon space to colored graphon
space defined by popular graph clustering algorithms such as spectral clustering. Grouping or
clustering objects according to their similarity is a fundamental problem in many areas of modern
science. The objective of clustering is to identify such clusters in data, where objects assigned to
the same cluster look roughly similar, whereas objects belonging to different clusters are different.
Various strategies have been proposed to formulate and solve clustering problems in a rigorous way
(see e.g. [9]). Nevertheless, despite the tremendous importance of this problem, very little is known
about the theoretical properties of many popular clustering techniques. Two such fundamental
properties are: (i) stability under perturbation of the data; and (ii) asymptotic consistency under
specific data generating mechanisms (i.e., convergence with probability 1 as the sample size goes
to infinity under a fixed probability model). Previous attempts to give theoretical justifications for
both of these properties have relied on a choice of a particular probability model.
In the present paper, we address these problems in a model-free way, by recognizing both problems as following from the continuity of certain maps on graphon space [16]. To elaborate, clustering
data can naturally be formulated as a graph partitioning problem. Indeed, in applications, one generally uses a similarity function f : X × X → R to construct a similarity matrix W = (wij ) where
wij = f (xi , xj ) measures the similarity between two data points xi , xj in a suitable space X . The
matrix W is naturally identified with a weighted graph. Another common approach is to use W
to build an unweighted graph, where nodes are adjacent if and only if they are similar enough (see
e.g. [22, Section 2.2] for more details). The problem of identifying clusters within data can thus
be reduced to partitioning the vertices of a graph, in such a way that nodes belonging to the same
cluster are well-connected together, whereas different clusters share fewer edges. In particular, all
of the above algorithms are examples of graph partitioning algorithms, that take a finite graph
G = (V (G), E(G)) and yield a partition of the vertices V (G). Formally, we can describe this as a
map from finite graphs (V (G), E(G)) to S-colored graphs (V (G), E(G), cG : V (G) → S), where S
is a finite set.
Giving theoretical justification for a choice of graph partitioning algorithm is a notoriously illdefined problem, and a satisfactory solution has been elusive to the broader mathematics community. In this paper we propose that such a graph partitioning algorithm ought to satisfy a form of
model-free structural consistency: if the structures of the input graphs converge then the structures
of the partitioned graphs should also converge. Such structural consistency subsumes both stability
under perturbation as well as asymptotic consistency as special cases. Formally, the aforementioned
map from graphs to S-colored graphs should be continuous under the canonical dense graph limit
topologies, developed over graphs in [5, 6, 7, 17], and generalized by us to S-colored graphs. We
characterize continuity for a broad class of graph partitioning algorithms, and prove model-free
structural consistency for popular graph partitioning algorithms such as spectral clustering.
To explain how our approach relaxes the assumptions in previous work in the area, consider the
case of spectral clustering. The asymptotic consistency of spectral clustering has been studied in
many papers [1, 2, 10, 11, 12, 13, 23, 24]. As far as we are aware, all of these results assume that the
similarity graph Gn is being generated according to the following general procedure: pick (xi )∞
i=1
i.i.d. from some probability space (X , µ) and then compute the similarity between node i and j to
be f (xi , xj ) for some function f : X × X → R. The aforementioned papers have worked to prove

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

3

consistency of spectral clustering for more and more general probability spaces X and similarity
functions f , usually exploiting some underlying geometric structure, and to our knowledge with
the most general results established in [23].
Compared to previous work in the area, our approach provides a way to establish the consistency of clustering algorithms without making any assumption about the exact form of the data
generating mechanism. Our only assumption is that data is provided in a coherent way. More
precisely, we assume the graphs converge structurally in the sense of the theory of dense graph
limits. In particular, when graphs are constructed from an i.i.d. sequence (xi )∞
i=1 using a similarity
function as above, it is known that the resulting graphs converge almost surely to a limiting object
(see Remark 2.6). Therefore, the present paper extends previous results from the literature. We
remark that the theory of graphons is indispensable to this paper for two reasons: (i) it provides a
language to formulate model-free structural consistency as a continuity result; and (ii) its canonical
topology ensures the broad applicability of the framework, as we now explain.
Replacing the i.i.d. assumption by the significantly weaker paradigm of dense graph convergence,
allows us to provide a novel statistical framework to help handle two common problems in modern data analysis: lack of a plausible data generating mechanism for complex data, and lack of a
mathematical representation space for inferred objects with no linear structure. For these reasons,
we believe our approach has an important advantage in network analysis. Indeed, finding models
that reflect the complex heterogeneities of massive real-world networks still remains an important
challenge [14]. The assumption that observations are independent is also rarely verified in practice. In contrast, our model-free approach provides consistency results in a setting that is broadly
applicable.
The rest of the paper is structured as follows. In Section 1.1, we provide an informal description of our main results. We briefly review the theory of graph limits in Section 2, and show in
Section 3 how the classical theory of graph limits can naturally be extended to study the space
of colored graph sequences and their limit objects. In Section 4, we study a common method of
clustering the vertices of a graph by computing some statistic for each vertex such as its degree.
We term these node-level statistics, and prove a general theorem about the structural consistency
of such clustering algorithms. Finally, in Section 5, we study the structural consistency of spectral
clustering in the graph limit framework. We demonstrate that normalized spectral clustering is
structurally consistent under mild assumptions. We also demonstrate problems with the analogous
unnormalized procedure, as was previously observed in [23]. Proofs of technical results in Section
3 are provided in Appendix A, and in Appendix B we extend the Riesz–Fischer Theorem to any
complete metric space, as it is required to formulate one of our main results, Theorem A.
1.1. Informal statements of results. In this subsection, we explain informally the main results
in the present paper. The technical details and the results are discussed in full, in later sections.
We begin by introducing the ingredients used to state and prove the main results. The first
notion is that of graphons, which are limiting objects of graph sequences. Graphons are measurable
functions W : [0, 1]2 → [0, 1] that are symmetric, i.e., W (x, y) = W (y, x). Every graph is naturally
identified with a graphon (see Equation (2.1)).
The space of graphons is equipped with a canonical topology. Suppose (Gn )n≥1 is a sequence of
graphs. Let t(K2 , Gn ) denote the edge density of Gn , i.e., the proportion of pairs of vertices of Gn
that are adjacent. More generally, given a simple graph H, we denote by t(H, Gn ) the proportion
of maps H → Gn that are edge preserving. We say that a sequence of graphs Gn is left-convergent
if t(H, Gn ) is a convergent sequence of real numbers for every simple graph H. The motivation
behind left-convergence comes from the notion that graphs become more and more similar if their
edge densities, triangle densities, etc., are all convergent. A left-convergent sequence of graphons
(Gn )n≥1 is naturally identified with a limit graphon. In order to do so, one first extends the notion
of homomorphism density to graphons (see Equation (2.4)), and then show that there exists a

4

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

graphon W ∈ W[0,1] such that t(H, Gn ) → t(H, W ). The resulting topology is metrizable by the
cut-norm (see Equation (2.2)). The cut-norm provides a natural way of comparing graphs, even
if they have different numbers of vertices. Moreover, under the cut-norm, the space W[0,1] is a
compact pseudo-metric space.
For more details, the reader is referred to Section 2, and to [6, 16] for a comprehensive introduction to the theory of graphons.
In this paper, we introduce a new mathematical framework to study the structural consistency of
clustering algorithms. Given a graph G, we identify a clustering of the vertices of G with a coloring
of G, i.e., a map cG : V (G) → S that assigns a “color” to every vertex of G. We say that the
clustering procedure is structurally consistent if for every left-convergent sequence of graphs Gn ,
the resulting sequence of colored graphs is also convergent (under an appropriate topology similar
to the canonical topology in the graphon space). Note that in previous work in the literature,
a clustering procedure is consistent if the graphs Gn with their colorings converge whenever the
graphs Gn are generated i.i.d. from a probability model. By the theory of dense graph limits, one
can show that each such sequence (Gn )n≥1 is convergent almost surely (see Remark 2.6). Our
approach thus significantly generalizes previous work by establishing structural consistency in a
“model-free” way, and without assuming independence of the samples.
We now discuss our first main result, a very general clustering recipe. Given a graph, there
are several ways to cluster its nodes based on local statistics. For instance, a simple clustering
procedure involves clustering nodes according to whether their degree (or edge-density) is above
or below a certain threshold value. More generally, one can work with a finite collection of local
statistics such as edge-densities, triangle counts, and other graph homomorphism densities, where
the images of these graph morphisms involve the given node. Now the nodes are clustered based
on the tuple of values of such local statistics; note that such tuples lie in Euclidean space.
In our first main result, we distill the essence of these clustering recipes into the notion of a
node-level statistic. This is a continuous map that sends a pair – a graph(on) and a node on it –
to a tuple in Euclidean space as above, or in full generality, to an arbitrary metric space X. Our
first main result establishes the structural consistency of such general clustering procedures.
Theorem A. (See Section 4.) Fix a metric space (X, dX ). Clustering according to any continuous
X-valued node-level statistic f is structurally consistent with respect to graph convergence. Namely,
if a sequence of graphs is convergent in the cut-norm, then clustering according to f yields a sequence
of colored graphs that is also convergent.
As a concrete example, Theorem A implies the structural consistency of degree-based clustering
as described above – see Theorem 4.8 for a precise formulation.
We remark here that partitioning a graph according to the degree statistic was previously studied
in the context of nonparametric graphon estimation; see e.g. [4]. In that work, the partitioning of
nodes is an intermediary step towards graphon estimation. In contrast, in the present paper, we are
chiefly concerned with the structural consistency of the graph partitioning step itself. Furthermore,
we do not take the graphon as a nonparametric generating mechanism for graphs, but rather as a
general limit object for graphs in the graphon topology.
Note that Theorem A decouples the clustering recipe from any graph generating mechanism,
i.i.d. or not, and assumes only that the graph sequence converges in a canonical topology. Thus,
Theorem A provides a very general and broadly applicable recipe for clustering.
As special cases of Theorem A, we mention two algorithms studied in the paper: (a) the aforementioned instances of clustering according to tuples of homomorphism densities (see Section 4.1);
and (b) spectral clustering according to the normalized Laplacian (see Section 5). We believe
the result should also be broadly applicable to other popular clustering algorithms, with minimal
assumptions on the graph generation process.

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

5

The remaining two main results of the paper involve the structural consistency of spectral clustering. The spectral clustering procedure involves working with the normalized Laplacian of a
graph, and more generally, of a graphon. Our second main result demonstrates that the normalized Laplacians of a convergent sequence of graphons are also convergent.
Theorem B. (See Section 5.3.) Suppose Wn is a sequence of graphons that converges in cut-norm
to a graphon W0 , whose degree function d0 (x) is positive for almost every x ∈ [0, 1]. Let L′Wn denote
the corresponding normalized Laplacian for n ≥ 0. Then L′Wn converges to L′W0 .
Theorem B extends the corresponding result in [23] without the assumption that the degree
functions are bounded below by a positive constant, and without the assumption that the graphs
Gn are generated by an i.i.d. mechanism.
It may be wondered if the assumption that d0 (x) > 0 a.e. x, is itself required in Theorem B. In
Example 5.21, we will show that this is indeed the case in order to obtain a reasonable theory of
consistency of spectral clustering.
Finally, we turn to our last main result, which proves structural consistency of normalized spectral
clustering in the model-free setting of graph limits.
Theorem C. (See Section 5.4.) Under appropriate assumptions, if Wn is a convergent sequence
of graphons, and (Wn , cn ) is a coloring of Wn obtained via normalized spectral clustering, then
(Wn , cn ) is also convergent.
Theorem C establishes the structural consistency of the widely used normalized spectral clustering technique, without making any assumptions on the data generating model. Note that this
implies the classical notion of statistical consistency for normalized spectral clustering.
We believe the approach we provide in this paper can also be applied to other clustering procedures. More generally, it is our hope that the philosophy and framework developed in the paper
will be used as an inspiration to establish model-free consistency results for statistical estimation
and machine learning procedures coming from various areas.
2. Review of dense graph limits
We now briefly review dense graph limit theory [6, 16]. This section serves to set notation, as well
as to motivate the next section on colored graph limit theory. The reader who is already familiar
with the theory of dense graph limits can safely skip this section.
A graphon is a bounded symmetric measurable function f : [0, 1]2 → [0, 1]. Each finite simple
labelled graph G with vertex set V (G) = {1, 2, . . . , n} can be naturally identified with the following
graphon f G :
(
1, if (⌈nx⌉, ⌈ny⌉) is an edge in G,
f G (x, y) := 1(⌈nx⌉,⌈ny⌉)∈E(G) =
(2.1)
0, otherwise.
The topology on isomorphism classes of finite simple graphs can be described as follows. The
graphon space W[0,1] sits inside W, the vector space of bounded symmetric measurable functions
f : [0, 1]2 → R. Recall that W is equipped with a seminorm called the cut-norm
Z
(2.2)
f (x, y) dx dy
kf k := sup
A,B⊂[0,1]

A×B

where the supremum is taken over all Lebesgue measurable subsets A, B ⊂ [0, 1]. The group of
measure-preserving bijections S[0,1] acts on W[0,1] as follows: given σ ∈ S[0,1] and f ∈ W[0,1] , define
f σ (x, y) := f (σ(x), σ(y)). Now define
δ (f, g) :=

inf

ψ∈S[0,1]

kf − gψ k .

6

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM
′

Observe that δ (f G , f G ) = 0 whenever G, G′ are isomorphic finite simple graphs, so δ metrizes
convergence of isomorphism classes of finite graphs (up to blowups).
The topology induced by δ can also be described using homomorphism densities. Given graphs
G = (V (G), E(G)), H = (V (H), E(H)), denote by Hom(H, G) the set of edge-preserving maps
from V (H) into V (G), and define the homomorphism densities as follows:
t(H, G) :=

| Hom(H, G)|
.
|V (G)||V (H)|

(2.3)

Now a sequence of finite simple graphs (Gn )∞
n=1 is said to left-converge if for all finite simple graphs
H, the sequence t(H, Gn ) converges as n → ∞. Intuitively, a graph sequence (Gn ) left-converges if
the graphs Gn become more and more similar, in that their edge densities, triangle densities, and
so on, all converge.
Observe that the definition of homomorphism densities extends to arbitrary graphons f as follows:
Z
Y
f (xi , xj ) dx1 · · · dxk ,
k = |V (H)|.
(2.4)
t(H, f ) :=
[0,1]k (i,j)∈E(H)

This is compatible with the graph statistics t(H, G), in that t(H, f G ) = t(H, G) for all finite simple
graphs H, G. An important result in the theory of graphons is that δ metrizes left-convergence [6,
Theorem 3.8]. More precisely, upon identifying graphons W ∼ W ′ whenever δ (W, W ′ ) = 0, the
space W[0,1] / ∼ of equivalence classes of graphons is a metric space. The following result explains
how graphons are limiting objects for left-convergent dense graph sequences.
Theorem 2.5 (Borgs–Chayes–Lovász–Sós–Vesztergombi, [6]). Let (Wn )∞
n=1 ⊂ W[0,1] be a sequence
of graphons. Then the following are equivalent:
(1) t(H, Wn ) converges for all finite simple graphs H, i.e., Wn is left-convergent.
(2) Wn is a Cauchy sequence in the δ metric.
(3) There exists W ∈ W[0,1] such that t(H, Wn ) → t(H, W ) for all finite simple graphs H.

Furthermore, t(H, Wn ) → t(H, W ) for all finite simple graphs H for some W ∈ W[0,1] if and only
if δ (Wn , W ) → 0.

Sampling. In addition to the cut metric and left-convergence, a third, equivalent way to think of
graph convergence is via sampling. Given a graphon W , let H(n, W ) denote a random weighted
graph generated by sampling i.i.d. variables (Xi )ni=1 uniformly on [0, 1], and then setting W (Xi , Xj )
to be the weight between nodes i and j. Given a weighted graph H with n vertices, let G(H) denote
the graph G on n vertices where for i > j, (i, j) ∈ E(G) with probability H(i, j) and G is made
symmetric. Now let G(n, W ) := G(H(n, W )). Then the probabilities P(G(n, W ) = H) can be
computed from the homomorphism densities t(H, W ) by inclusion-exclusion formulas [16, Section
5.2.3]. Therefore, the left-convergence of a graphon sequence Wn is equivalent to convergence of
the sampling densities G(k, Wn ) for all k.
Remark 2.6. The sampling distributions H(n, W ) and G(n, W ) are used as nonparametric generative models for networks. Here we remark that both models G(n, W ) and H(n, W ) concentrate
around W in the cut-distance (see [16, Lemma 10.16]). In particular, G(n, W ) and H(n, W ) converge almost surely to W . Note that the general data generating mechanism employed in [23]
falls within the class {H(n, W ) : W ∈ W[0,1] }, because an arbitrary probability distribution on
a compact metric measure space X can always be mapped in a measure-preserving fashion onto
[0, 1] with the Lebesgue measure. Under this mapping, the continuous (symmetric) similarity function k : X × X → [0, ∞) defines an associated kernel Wk ∈ W, bounded above uniformly by
mk := maxx,y∈X k(x, y) > 0. Therefore, graphs Gn generated i.i.d. in this model satisfy:
Gn
∼ H(n, m−1
m−1
k Wk ),
k f

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

7

whence the random weighted graph sequence m−1
k Gn converges almost surely to the graphon
−1
mk Wk ∈ W[0,1] as n → ∞. Thus the framework in the present paper applies to the general
setting of [23].
We conclude with two additional facts about the metric space (W[0,1] / ∼, δ ):

(1) (See [17].) The countable set of graphons f G (running over all finite simple graphs G) is
dense in (W[0,1] / ∼, δ ).
(2) As a consequence of the Weak Regularity Lemma in graph theory, Lovász and Szegedy
showed in [18] that (W[0,1] / ∼, δ ) is a compact metric space.
3. Colored graph limit theory

We begin by showing how the theory of dense graph limits can be extended to colored graph
sequences and their limits. The proofs of the results stated in this section are given in Appendix
A, and leverage the approach of [16].
3.1. Colored graphs. Let S be a finite set. Define an S-colored graph G to be a triple
(V (G), E(G), cG : V (G) → S),

where V (G) and E(G) ⊂ V (G)2 are finite sets. (We assume that G does not have multiple edges
or self-loops.) Now let GS denote the set of S-colored graphs.
Given G ∈ GS and s ∈ S, we let Vs (G) := {v ∈ V (G) : cG (v) = s} denote the set of vertices of G
of color s. For H, G ∈ GS , we define the colored homomorphism density by:
tS (H, G) :=

| HomS (H, G)|
,
|V (G)||V (H)|

where HomS (H, G) denotes the set of edge preserving maps φ : V (H) → V (G) such that cH = cG ◦φ.

For instance, if H denotes the graph with one vertex, colored s, then tS (H, G) precisely equals
|Vs (G)|/|V (G)|.
Note that the colored homomorphism densities naturally generalize the usual homomorphism
densities (see Equation (2.3)) in the case where the graphs are uncolored.

3.2. Colored graphons and homomorphism densities. We now come to the limiting objects
of sequences of colored graphs. We define an S-colored graphon to be a pair of measurable maps
(fW , cW ) where fW : [0, 1]2 → [0, 1] is symmetric and cW : [0, 1] → S. We denote the set of
S-colored graphons by WS . Given H ∈ GS and W ∈ WS , we let
Z
Y
Y
Y
fW (xes , xet )
dxv .
(3.1)
1cW (xv )=cH (v)
tS (H, W ) :=
[0,1]V (H) e∈E(H)

v∈V (H)

v∈V (H)

In other words, the integration is carried out only over the sub-rectangle given by:
xv ∈ c−1
W (cH (v)),

∀v ∈ V (H).

The space of S-colored graphs GS naturally embeds into WS in the following way. Let k := |S|,
and enumerate S = {s1 , . . . , sk } in some fixed order. Given G ∈ GS and j ∈ {1, . . . , k}, let p0 := 0,
Pj−1 Pj
pj := |Vsj (G)|/|V (G)|, and let Ij denote the interval Ij := ( l=0
pl , l=0 pl ]. Now define the
S-colored graphon G
WG ∈ WS , via:
cWG (Ij ) := j, cWG (1) = k,

fWG (Ij × Ij ′ ) := 1(j,j ′ )∈E(G) ,

and fWG = 0 otherwise. The graphon WG is related to the original graph G as follows.
Lemma 3.2. For all S-colored graphs H, G ∈ GS , we have tS (H, G) = tS (H, WG ).

8

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

Recall that in the uncolored case, homomorphism densities are used to construct a topology on
the space of graphons (see Equation (2.3) and the subsequent paragraph). In a similar way, we use
colored homomorphisms to construct a topology on the space of colored graphons.
Definition 3.3. A sequence of S-colored graphons Wn ∈ WS is said to left-converge (to a graphon
W ∈ WS ) if the corresponding sequence of colored homomorphism densities tS (H, Wn ) converges
(to tS (H, W )) for every fixed S-colored graph H.
Note that when the nodes of a sequence of graphs all have the same color, the above notion of
left-convergence reduces to the usual uncolored notion of left-convergence.
3.3. Cut metric. Recall that in the uncolored dense limit theory, the topology induced by homomorphism densities can be metrized using the cut-norm (see Equation (2.2)). We now extend the
definition of the cut-norm to WS :
X
−1
(3.4)
kW − W ′ kS := kW − W ′ k +
µL (c−1
W (s)∆cW ′ (s)),
s∈S

where µL denotes the usual Lebesgue measure. Notice k · kS is not an actual norm when |S| > 1;
however, we retain the present notation to maintain consistency with the uncolored case |S| = 1.
Using this definition, we can naturally extend the usual Counting Lemma to WS .
Lemma 3.5 (Counting Lemma). Let H ∈ GS and W, W ′ ∈ WS . Then
X
−1
|tS (H, W ) − tS (H, W ′ )| ≤ |E(H)| · kW − W ′ k +
µL (c−1
W (s)∆cW ′ (s)).
s∈S

In particular, |tS (H, W ) − tS (H, W ′ )| ≤ |E(H)| · kW − W ′ kS .
Measure preserving maps σ ∈ S[0,1] naturally act on WS : if (W, cW ) ∈ WS , then we let
W σ (x, y) := W (σ(x), σ(y))

and

cσW (x) := cW (σ(x)).

(3.6)

S for W , W , ∈ W by the formula
As in the uncolored case, we define the distance δ
1
2
S
S
δ
(W1 , W2 ) :=

inf

σ∈S[0,1]

kW1 − W2σ kS ,

S (W , W ) = 0. Observe that (W / ∼, δ S ) is a metric space. It
As usual, we will say W1 ∼ W2 if δ
1
2
S

is in fact compact, as in the classical case where the vertices are not colored.
S ) is compact.
Theorem 3.7. The space (WS / ∼, δ

Moreover, the colored cut-distance provides a way to metrize the topology induced by the colored
homomorphism densities.
Theorem 3.8. Let Wn be a sequence of S-colored graphons. Then the sequence Wn left-converges
S metric.
(see Definition 3.3) if and only if it is Cauchy in the δ
Finally, the colored finite graphs are dense in the completion WS / ∼.
Theorem 3.9. Colored graphs are dense in WS / ∼.
Using an inclusion-exclusion argument, it is also not hard to show that convergence in this
topology is equivalent to convergence in a sampling topology for S-colored graphs. Therefore, this
topology is the canonical topology for convergence of dense S-colored graphs.

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

9

4. Clustering by continuous node-level statistics
One general class of graph partitioning algorithms proceed as follows: compute a statistic defined
on the set of nodes and then partition the nodes based on the value of that statistic. For example,
this includes clustering based on the degree, local clustering coefficient, and spectral clustering. In
this section, we call such statistics node-level statistics. We introduce the notion of a continuous
node-level statistic, which is broad enough to apply to commonly used node-level statistics (such
as the degree or local clustering coefficient). We then show a general consistency result for graph
partitioning algorithms based on continuous node-level statistics. We also verify continuity of
node-level statistics defined based on local graph statistics, thereby showing structural consistency
of graph partitioning based on such statistics. The same general theorem is applied in Section
5 to show structural consistency of spectral clustering, though such a result requires additional
machinery.
We begin by defining the notion of a node-level statistic and a continuous node-level statistic.
Definition 4.1. Let G denote the set of labelled finite simple graphs. A node-level statistic in Rm
is a collection of maps {fG : V (G) → Rm , G ∈ G}.

Notice that node-level statistics can be summarized also as a map f : G → L1 ([0, 1], Rm ), with
the restriction that if we label V (G) := {1, . . . , n} then
f (G)(y) = fG (⌈ny⌉),

G ∈ G, y ∈ [0, 1].

Well-known examples of node-level statistics include the degree of a node, or the local clustering
coefficient, i.e., the proportion of pairs of neighboring nodes that are adjacent.
Definition 4.2. We say that a node-level statistic in Rm is continuous if whenever Gn → W0 in
the cut-norm, the family of functions f (Gn ) ∈ L1 ([0, 1], Rm ) is convergent in L1 .
Our notion of continuity above was defined so that natural node-level statistics such as the degree
would be continuous. For example, the degree distribution does not necessarily converge pointwise
as a sequence of graphs converges in the cut-norm, but as we will show later, it converges in L1 .
Another candidate notion of convergence for functions f : [0, 1] → Rm could be convergence with
respect to a generalized cut-norm
Z
kf k := sup
f (y)dy .
B⊂[0,1]

B

However, as we now show, convergence in the generalized cut-norm is equivalent to convergence
in the L1 norm, since the function is defined on the interval as opposed to a higher dimensional
hypercube. To explain the equivalence, for every tuple c = (c1 , . . . , cm ) ∈ {0, 1}m , let Bc :=
f −1 ((−1)c1 R≥0 × · · · × (−1)cm R≥0 ). Then,
Z
X
f (y)dy ≤ 2m kf k ,
kf k ≤ kf k1 =
c∈{0,1}m

Bc

so the cut-norm and the L1 norm are equivalent.
Another advantage of using the notion of L1 is that it generalizes naturally to node-level statistics
taking values in arbitrary metric spaces (X, dX ). In the following definition, L1 ([0, 1], X) is the set
of measurable functions
Z 1
1
dX (x0 , g(y)) dy < ∞}
L ([0, 1], X) := {g : ([0, 1], µL ) → (X, BX ) :
0

for any choice of point x0 ∈ X, and equipped with the metric
Z 1
′
dX (g(y), g′ (y)) dy.
d1 (g, g ) :=
0

10

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

Here, µL stands for Lebesgue measure, and BX for the Borel σ-algebra on X. As usual, we identify
functions in L1 ([0, 1], X) that are equal almost everywhere on [0, 1].
Definition 4.3. Given a metric space (X, dX ), a node-level statistic in X is f : G → L1 ([0, 1], X),
such that f (G)(y) = fG (⌈ny⌉) for all G ∈ G, y ∈ [0, 1]. We say that an X-valued node-level statistic
f : G → L1 ([0, 1], X) is continuous if whenever Gn → W0 in the cut-norm,
lim d1 (f (Gn ), f (Gm )) = 0,

m,n→∞

i.e., the sequence of functions f (Gn ) ∈ L1 ([0, 1], X) is Cauchy.
Note that this definition reduces to Definition 4.2 when X = Rm (equipped with the usual
Euclidean distance). In fact this is true for any complete metric space (X, dX ): continuous X-valued
node-level statistics f : G → L1 ([0, 1], X) continuously extend to functions f : W[0,1] → L1 ([0, 1], X).
See Corollary B.2 in Appendix B for details.
In the remainder of the paper, we will only deal with continuous node-level statistics. Hence,
from now on we take such a statistic to denote a continuous function f : W[0,1] → L1 ([0, 1], X).
With a slight abuse in notation we shall also write f (W, y) instead of f (W )(y).
Our next theorem provides a general consistency result when clustering is performed using a
continuous node-level statistic f : W[0,1] → L1 ([0, 1], X). We use f to color the vertices of W ∈
W[0,1] . More precisely, suppose there exists a collection of disjoint open sets (Aj )N
j=1 ⊂ X such that
f (W, y) ∈

N
[

Aj

j=1

for a.e. y ∈ [0, 1].

Then it is natural to define a coloring cW : [0, 1] → {1, . . . , N } by letting cW (y) be the unique j such
that f (W, y) ∈ Aj . Note that cW is well-defined for almost every y ∈ [0, 1]. Letting S = {1, . . . , N },
this operation induces a map F : W[0,1] → WS defined by
F (W ) := (W, cW ).
Structural consistency of the above coloring is equivalent to continuity of the map F . Our next
result provides a useful sufficient condition for the map F to be continuous. In what follows, we
identify functions f : W[0,1] → L1 ([0, 1], X) with functions f : [0, 1]2 × [0, 1] → [0, 1] × X.
Theorem A. Let (X, dX ) be a metric space, and f : W[0,1] → L1 ([0, 1], X) a continuous node-level
statistic in X. Given a collection of disjoint open sets A1 , . . . AN ⊂ X, define
D := {W ∈ W[0,1] : f (W, y) ∈

N
[

j=1

Aj

for a.e. y ∈ [0, 1]}.

(4.4)

Define S = {1, . . . , N } and for W ∈ D, let cW : [0, 1] → S be the coloring defined for almost every
y by letting cW (y) = j, where j is the unique color in S such that f (W, y) ∈ Aj . Then the map
F : (D, k · k ) → (WS , k · kS ) given by F (W ) = (W, cW ) is continuous.
Note, the theorem has a technical assumption about working with a subset D rather than the
full graphon space W[0,1] . In fact this assumption is required, as we explain in Example 4.15.
We now show that under a supplementary invariance assumption, a similar result holds on the
quotient graphon spaces.
Definition 4.5. Let (X, dX ) be a metric space. We say that a continuous node-level statistic
f : W[0,1] → L1 ([0, 1], X) is S[0,1] -invariant if
f (W σ , y) := f (W, σ(y)),

∀G ∈ G, σ ∈ S[0,1] , a.e. y ∈ [0, 1].

(4.6)

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

11

In particular, for a graph G with vertex set {1, . . . , n}, and a permutation σ ∈ Sn , we have
f (Gσ , y) = f (G, σ(y)), where σ acts on [0, 1] under the usual embedding Sn ֒→ S[0,1] .1
Corollary 4.7. In the setting of Theorem A, if in addition D is S[0,1] -stable and f is S[0,1] -invariant
so that f (W σ , y) = f (W, σ(y)) for all σ ∈ S[0,1] and almost every y ∈ [0, 1], then the map F : (D/ ∼
S ) given by F (W ) = (W, c ) is continuous.
, δ ) → (WS / ∼, δ
W
We now prove Theorem A, and using it, Corollary 4.7.
Proof of Theorem A. Suppose Wn → W0 as n → ∞, with Wn ∈ D for all n ≥ 0. For j = 1, . . . , N
and n ≥ 0, let
For k ≥ 1 and j = 1, . . . , N , let
Aj,k

En,j := {y ∈ [0, 1] : f (Wn , y) ∈ Aj }.

:= x ∈ Aj :

1
1
≤ dX (x, Acj ) <
k+1
k



,

n
o
and let Aj,0 := x ∈ Aj : dX (x, Acj ) ≥ 1 , where we denote dX (x, A) := inf{dX (x, a) : a ∈ A}.
Note that Aj = ∪∞
k=0 Aj,k since Aj is open. For k ≥ 0, define
Fj,k := {y ∈ [0, 1] : f (W0 , y) ∈ Aj,k } .

By the definition of Aj,k and assumption 4.4, we have
c
E0,j

=

∞
N [
[

l=1 k=0
l6=j

Fl,k ∪ Z

for some set Z ⊂ [0, 1] with µL (Z) = 0. Moreover, the sets Fl,k are disjoint. Thus,
µL (En,j \ E0,j ) =

N X
∞
X
l=1 k=0
l6=j

µL (En,j ∩ Fl,k ).

Now fix k ≥ 0 and distinct colors j 6= l ∈ S. For every n ≥ 1, we have by the definitions of En,j
and Fl,k that
1
∀y ∈ En,j ∩ Fl,k .
dX (f (Wn , y), f (W0 , y)) ≥
k+1
Therefore, by the continuity of the node-level statistic f ,
Z
1
dX (f (Wn , y), f (W0 , y)) dy
· µL (En,j ∩ Fl,k ) ≤
k+1
En,j ∩Fl,k
Z
dX (f (Wn , y), f (W0 , y)) dy → 0
≤
[0,1]

as n → ∞. It follows that µL (En,j ∩ Fl,k ) → 0 as n → ∞ for each fixed k ≥ 0 and l 6= j. Moreover,
µL (En,j ∩ Fl,k ) ≤ µL (Fl,k ),

∞
XX
l6=j k=0

c
µL (Fl,k ) = µL (E0,j
) < ∞.

Therefore, by the dominated convergence theorem,
∞
XX
µL (En,j \ E0,j ) =
µL (En,j ∩ Fl,k ) → 0
l6=j k=1

1Specifically, each σ ∈ S acts on [0, 1] by fixing 1, and sending y ∈ ((i − 1)/n, i/n] to y + (σ(i) − i)/n.
n

12

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

as n → ∞. By a similar argument, we also obtain µL (E0,j \ En,j ) → 0 as n → ∞. Therefore,
µL (En,j ∆E0,j ) → 0 as n → ∞. Since kWn − W0 k → 0 as n → ∞, this implies kWn − W0 kS → 0.
This concludes the proof of the theorem.

Proof of Corollary 4.7. Suppose δ (Wn , W0 ) → 0 as n → ∞. Then there exists (σn )n≥1 ⊂ S[0,1]
such that kWnσn → W0 k → 0 as n → ∞. By Theorem A, k(Wnσn , cWnσn ) − (W0 , cW0 )kS → 0. Now
observe that by the invariance assumption on f , we have
cWnσn (y) = j ⇔ f (Wnσn , y) ∈ Aj ⇔ f (Wn , σn (y)) ∈ Aj ⇔ cWn (σn (y)) = j.
It follows that the coloring defined by f is consistent with the S[0,1] action on WS (see (3.6)). We
S ((W , c
therefore conclude that δ

n Wn ), (W0 , cW0 )) → 0 as n → ∞.
4.1. Structural consistency of clustering by homomorphism densities. Our next goal is to
provide a broad family of functions that satisfy the hypotheses of Theorem A. Let H be a k-labelled
graph with labelled vertices 1, . . . , k. Recall that for W ∈ W and x1 , . . . , xk ∈ [0, 1], we define
Z
Y
Y
W (xes , xet )
dxv .
tx1 ,...,xk (H, W ) =
[0,1]V (H)\{1,...,k} e∈E(H)

In particular, if K2 has one labelled vertex, then
Z 1
W (x, y) dy,
tx (K2 , W ) =
0

v6∈{1,...,k}

x ∈ [0, 1].

The following result is a consequence of Lemma 4.10 and Theorem A.
Theorem 4.8. Fix 0 < α < 1 and a 1-labelled graph H, and define
D = DH,α := {W ∈ W[0,1] : µL ({y ∈ [0, 1] : ty (H, W ) = α}) = 0}.

(4.9)

Let (Wn )n≥1 ⊂ D such that Wn → W0 ∈ W[0,1] , with W0 ∈ D. Let S = {1, 2} and let cn : [0, 1] → S
be defined for n ≥ 0 by
(
1, if ty (H, Wn ) < α,
cn (y) :=
2, if ty (H, Wn ) ≥ α.
Then the sequence (Wn , cn ) converges to (W0 , c0 ) in WS .
In order to show the result, we first prove a generalization of the usual Counting Lemma (see
[16, Lemma 10.24]).
Lemma 4.10. Fix a finite simple graph H, graphons We , We′ ∈ W[0,1] for all edges e ∈ E(H), and
measurable subsets Fv ⊂ [0, 1] for all vertices v ∈ V (H). Now define
W := (We )e∈E(H) ,

W′ := (We′ )e∈E(H) ,

F := ×v∈V (H) Fv ⊂ [0, 1]|V (H)| ,

as well as the following “generalized homomorphism density”:
Z
Y
Y
We (xes , xet ) ·
dxv .
tF (H, W) :=
F e∈E(H)

(4.11)

v∈V (H)

Then,
tF (H, W) − tF (H, W′ ) ≤

X

e∈E(H)




Y

v6=es ,et




µL (Fv ) min µL (Fes )µL (Fet ), kWe − We′ k . (4.12)

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

13

Proof. We adapt the proof of [16, Lemma 10.24]. We first claim that for every edge (u, v) ∈ E(H),


Z
Y
Y
′
Wij (xi , xj )(Wuv (xu , xv ) − Wuv
(xu , xv )) dx ≤ 
µL (Fw ) ×
F (i,j)∈E(H)
(i,j)6=(u,v)

w6=u,v

min(µL (Fu )µL (Fv ), kWe − We′ k ).

Indeed, note that the left-hand side of the expression can be written as
Z
′
(xu , xv )) dx ,
f (x)g(x)(Wuv (xu , xv ) − Wuv
F

where

Y

f (x) :=

Wij (xi , xj ),

g(x) :=

(i,j)∈∇(u)\(u,v)

Y

Wij (xi , xj ).

(i,j)∈E(H)\∇(u)

Here ∇(u) denotes the set of edges with one endpoint equal to u. Note that f (x) does not depend
on xv and g(x) does not depend on xu . Thus, by [16, Lemma 8.10],
Z
′
f (x)g(x)(Wuv (xu , xv ) − Wuv
(xu , xv )) dxu dxv ≤ min(µL (Fu )µL (Fv ), kWe − We′ k ).
Fu ×Fv

The claim follows by integrating with respect to the remaining variables. We immediately obtain
the desired result by writing |tF (H, W) − tF (H, W′ )| as a telescoping sum where each term is as
in the claim.

We now show that clustering according to homomorphism densities is structurally consistent.
Proof of Theorem 4.8. Let f (W, y) := ty (H, W ). By Lemma 4.10, for every sequence Wn → W0
and every measurable subset B ⊂ [0, 1],
Z
[f (Wn , y) − f (W0 , y)] dy ≤ |E(H)| · kWn − W0 k .
B

Set B± := {y ∈ [0, 1] : ±(f (Wn , y) − f (W0 , y)) > 0}. Then by the discussion after Definition 4.2,
Z
Z
1
1
1
(f (Wn , y) − f (W0 , y)) dy +
(f (Wn , y) − f (W0 , y)) dy
kf (Wn ) − f (W0 )k1 =
2
2 B+
2 B−
≤ |E(H)| · kWn − W0 k .

It follows that f is a continuous node-level statistic : W[0,1] → L1 ([0, 1], [0, 1]). The result now
follows by Theorem A, with A1 = [0, α) and A2 = (α, 1].

Remark 4.13. Theorem 4.8 easily extends to any finite set H1 , . . . , Hk of 1-labelled graphs, and
any collection of disjoint open sets A1 , . . . , AN in the cube [0, 1]k . Namely, define
D := {W ∈ W[0,1] : (ty (Hi , W ))ki=1 ∈

N
[

j=1

Aj for a.e. y ∈ [0, 1]}.

(4.14)

Given W ∈ D, define cW : [0, 1] → S := {1, . . . , N } via: cW (y) = j if (ty (Hi , W ))ki=1 ∈ Aj . Then
the clustering map W 7→ (W, cW ) is continuous on D.
Example 4.15. We briefly explain why the assumption Wn ∈ D is required in Theorem A (instead
of allowing all of W[0,1] ). Consider the case of edge-density, where H = K2 consists of an edge.
Suppose Y ⊂ [0, 1] has positive measure, and W0 ∈ W[0,1] is such that
W0 (x, y) ∈ (0, 1) ∀x, y ∈ [0, 1],

ty (H, W0 ) = α ∀y ∈ Y.

14

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

Fix any partition Y = Y ′ ⊔ Y ′′ into sets of positive measure, and ǫ ∈ [0, 1], define WY ′ ,ǫ ∈ W[0,1]
via:


if x, y ∈ Y ′ ;
ǫ + (1 − ǫ)W0 (x, y),
WY ′ ,ǫ (x, y) = (1 − ǫ)W0 (x, y),
if x, y ∈ Y ′′ ;


W0 (x, y),
otherwise.

For each Y ′ , note that as ǫ → 0+ , we have WY ′ ,ǫ → W0 in L1 , hence in cut-norm. On the other
hand, it is easily verified that for the graphon WY ′ ,ǫ ,
Z
(1 − W0 (x, y)) dx > α,
∀y ∈ Y ′ ,
deg(y) = α + ǫ
′
ZY
W0 (x, y) dx
< α,
∀y ∈ Y ′′ .
deg(y) = α − ǫ
Y ′′

Therefore different choices of Y ′ would give inconsistent limit clusters.

4.2. Sensitivity of clustering based on node-level statistics. We conclude this section by
discussing the sensitivity of the clustering in Theorem A. A more sensitive notion of clustering
would be obtained if one could show that the function F : W 7→ (W, cW ) is Lipschitz on D, as
doing so would yield a greater understanding of approximation errors. However, the following
simple example shows this is not always true.
Example 4.16. Suppose H is any 1-labelled graph with at least one edge, and consider the
clustering procedure in Theorem 4.8, for some α ∈ (0, 1). Now one can choose Erdös–Rényi graphs
|E(H)|
|E(H)|
W1 ≡ p1 , W2 ≡ p2 where p1
< α < p2
. Then the clustering algorithm shows that all
S (W , W ) = 1. On the
vertices of W1 are colored 0, while all vertices of W2 are colored 1, whence δ
1
2
other hand, p1 , p2 can be chosen arbitrarily close to one another, whence δ (W1 , W2 ) can be made
as small as desired. It follows that W 7→ (W, cW ) is not Lipschitz on DH,α (see Equation (4.9)).
We now show that the problem in the previous example lies in the fact that the sets Aj are not
necessarily separated. If instead they were separated, in some sense “discretizing” the situation,
then the clustering map F is Lipschitz, as long as the node-level statistic is. More precisely, we
have:
Theorem 4.17. Fix dmin > 0, and suppose A1 , . . . , AN are disjoint open sets in a metric space
(X, dX ), such that distinct sets Aj are at least dmin distance apart. Also fix a continuous node-level
statistic f : W[0,1] → L1 ([0, 1], X), and define D ⊂ W[0,1] and the clustering map F : (D, k · k ) →
(WS , k · kS ) as in Equation (4.4).
Now if the node-level statistic f is Lipschitz, then so is the clustering map F . More generally,
suppose ϕ : [0, ∞) → [0, ∞) satisfies
d1 (f (W ), f (W ′ )) ≤ ϕ(kW − W ′ k ),

∀W, W ′ ∈ D.

Then kF (W ) − F (W ′ )kS ≤ ϕ1 (kW − W ′ k ), where ϕ1 (y) := y +

ϕ(y)
.
dmin

For certain continuous (even Lipschitz) node-level statistics f , Theorem 4.17 also has a converse:
the clustering map F is Lipschitz if and only if the sets Aj are separated. This is the case, for
example, for any 1-labelled homomorphism density, for which this converse was shown in Example
4.16.
Proof. Define g : [0, 1] → [0, ∞) via: g(y) := dX (f (W, y), f (W ′ , y)). Note that if f (W, y), f (W ′ , y)
belong to distinct sets Aj , then their distance is at least dmin . Hence, we compute using Markov’s

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

15

inequality:
kF (W ) − F (W ′ )kS = kW − W ′ k +
′

X

−1
µL (c−1
W (s)∆cW ′ (s))

s∈S

≤ kW − W k + µL {y ∈ [0, 1] : g(y) ≥ dmin }
Z 1
1
g(y) dy
≤ kW − W ′ k +
dmin 0
1
= kW − W ′ k +
d1 (f (W ), f (W ′ ))
dmin
1
≤ kW − W ′ k +
ϕ(kW − W ′ k ) = ϕ1 (kW − W ′ k ),
dmin
as desired.



Remark 4.18. The proof also demonstrates that if we merely know f is continuous, then so is F .
To see why, simply stop the preceding calculation before the final inequality, and take W ′ → W .
This provides a second, easier proof of the continuity of F (when f is continuous), in the simpler
setting where the open sets Aj are separated in X.
5. Spectral clustering
One of the most popular algorithms for graph partitioning is spectral clustering (see e.g. [22]).
The algorithm proceeds by constructing the graph Laplacian LG from a graph G by taking a
diagonal matrix DG of the degrees of G and subtracting the adjacency matrix of G from it. This
is known as the unnormalized Laplacian. In practice, it is also common to work with a normalized
version of the Laplacian L′G , which is derived from the unnormalized Laplacian by normalizing
−1/2
both the rows and columns by DG , and tends to give better results (see [22] for more details).
Note that the Laplacian LG always has a constant eigenvector of eigenvalue 0. Moreover, the
matrix LG is positive semidefinite as it is diagonally dominant. Barring multiplicity issues, the
first m associated eigenvectors of the smallest non-zero eigenvalues of LG define an embedding of
V (G) → Rm by their coordinates, and spectral clustering partitions the vertices of G by how they
cluster in Rm . The same procedure can be carried out for the normalized Laplacian L′G . To prove
structural consistency of spectral clustering, we introduce the notion of the Laplacian of a graphon
W . We then determine when the normalized and unnormalized Laplacians L′W , LW are continuous
constructions under the cut topology. Finally, we evaluate how the convergence of the spectrum to
that of the limit operators leads to structural consistency. As we will show, in general, normalized
spectral clustering has better consistency properties than unnormalized clustering. Our results thus
confirm previous findings from [23].
As explained in [16, Section 7.5], a graphon W ∈ W[0,1] can be thought of as a self-adjoint integral
operator TW , where
Z 1
W (x, y)f (y) dy.
(5.1)
TW (f ) =
0

When we think of TW as an operator TW : L∞ ([0, 1]) → L1 ([0, 1]), then the operator norm of TW
is equivalent to the cut-norm ([16, Lemma 8.11]):
kW k ≤ kTW k∞→1 ≤ 4kW k .
L2

L2 .

(5.2)

We also often see TW as an operator TW :
→
In that case, the resulting operator is Hilbert–
Schmidt. In particular, TW has a countable spectrum, and can only have 0 as an accumulation
point. We can therefore define the eigenvalues of W to be the eigenvalues of the associated Hilbert–
Schmidt operator TW : L2 → L2 . We shall denote these eigenvalues by λ1 (W ), λ2 (W ), etc., where
|λ1 (W )| ≥ |λ2 (W )| ≥ · · · .

16

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

Since W is symmetric, the operator is self-adjoint. Therefore we can choose an orthonormal basis
fi ∈ L2 of eigenfunctions associated to λi (W ) with appropriate multiplicities so that
W (x, y) =

∞
X

λi (W )fi (x)fi (y),

(5.3)

i=1

where kfi k2 = 1, and where (5.3) converges in the L2 sense.
5.1. Convergence of eigenvalues and eigenvectors. We now examine the behavior of the
eigenvalues of a sequence of graphons.
Definition 5.4 ([21, Definition 1.1]). Let W ∈ W[0,1] have spectral decomposition as in (5.3) with
eigenvalues λi = λi (W ). Given λ ≥ 0, we define a cutoff graphon [W ]λ by
X
[W ]λ (x, y) :=
λi fi (x)fi (y).
{i:|λi |>λ}

Notice that for any sequence of graphons such that kWn − W0 k → 0 as n → ∞, we have
W0 = lim lim [Wn ]αk
n→∞ k→∞

in L2 , whenever αk → 0 as k → ∞. The following theorem characterizes the convergence of
graphons in the cut-norm, in terms of the convergence of its cutoffs [Wn ]λ .
Theorem 5.5 (see [21, Proposition 1.1]). Let {Wn }n≥1 ⊂ W[0,1] and let W0 ∈ W[0,1] . Then the
following are equivalent:
(1) kWn − W0 k → 0 as n → ∞.
(2) There is a decreasing sequence {αk }k≥1 ⊂ (0, ∞) with limk→∞ αk = 0 such that k[Wn ]αk −
[W0 ]αk k2 → 0 as n → ∞ for every j.
Furthermore, if (2) holds, then
W0 = lim lim [Wn ]αk
k→∞ n→∞

in the

L2

sense.

Using the above result, we can now understand the behavior of the eigenvalues and eigenvectors
of a sequence of graphons.
Theorem 5.6. Fix α > 0. Let (Wn )n≥1 ⊂ W be uniformly bounded in L∞ by α, and suppose
kWn − W0 k → 0 as n → ∞. Denote by λ1 (Wn ), λ2 (Wn ), . . . the sequence of nonzero eigenvalues
of Wn in decreasing absolute value. For k ≥ 1, let Pk (Wn ) : L2 ([0, 1]) → L2 ([0, 1]) denotes the
projection on the eigenspace of Wn associated to {λk (Wn ), −λk (Wn )}. Define λk (W0 ) and Pk (W0 )
similarly. Then for all k ≥ 1,
(1) λk (Wn ) → λk (W0 ) as n → ∞;
(2) kPk (Wn ) − Pk (W0 )kB(L2 ([0,1]) → 0 as n → ∞, where kT kB(L2 [0,1]) := supkf k2 =1 kT f k2 denotes the operator norm of T : L2 ([0, 1]) → L2 ([0, 1]).
In particular, suppose for each k ≥ 1 that λk (W0 ) is a simple eigenvalue with associated eigenvector
f0 ∈ L2 ([0, 1]), and let fn ∈ L2 ([0, 1]) be an eigenvector associated to λk (Wn ). Define pn (x, y) :=
fn (x)fn (y), and p0 (x, y) := f0 (x)f0 (y). Then λk (Wn ) is simple for n large enough and kpn −
p0 kL2 ([0,1]2 ) → 0 as n → ∞.
Proof. The first part of the theorem is [16, Theorem 11.54]. To prove the second part, recall that the
only accumulation point of the eigenvalues of a compact self-adjoint operator is 0. Let n1 < n2 < · · ·
be the set of indices such that |λnk (W0 )| =
6 |λnk+1 (W0 )|. Define αk := (|λnk (W0 )| + |λnk+1 (W0 )|)/2
for k ≥ 1. By part (1) and Theorem 5.5, which we can apply by the uniform boundedness condition

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

17

on Wn , we have that Pn1 (Wn ) = [Wn ]α1 /λn1 (Wn ) converges to Pn1 (W0 ) = [W0 ]α1 /λn1 (W0 ) in
operator norm on L2 . Similarly, for k ≥ 1,


1
1
Pnk (Wn ) =
[Wn ]αk+1 − [Wn ]αk →
[W0 ]αk+1 − [W0 ]αk = Pnk (W0 )
λnk (Wn )
λnk (W0 )
in the operator norm on L2 as n → ∞.



Lemma 5.7. Let {fi }i≥1 ⊂ L2 ([0, 1]) and fix g ∈ L∞ ([0, 1]). Suppose fi (x)fi (y) → f (x)f (y) in
L2 ([0, 1]2 ). Moreover, suppose the fi and f are normalized so that hfi , gi > 0 and hf, gi > 0. Then
fi → f in L2 ([0, 1]).
Proof. By Jensen’s inequality,
2
Z
Z 1 Z 1
[fi (x)fi (y) − f (x)f (y)] g(y) dy dx ≤
0

0

0

1Z 1
0

([fi (x)fi (y) − f (x)f (y)] g(y))2 dxdy

≤ kgk2∞ kfi (x)fi (y) − f (x)f (y)k2
→0

as i → ∞. Thus,
in L2 ([0, 1]). Equivalently,

Z

1
0

fi (x)fi (y)g(y) dy →

Z

1

f (x)f (y)g(y) dy
0

hfi , gifi (x) → hf, gif (x)

Using a similar argument, we conclude that
Z 1Z 1
Z
2
hfi , gi =
fi (x)fi (y)g(x)g(y) dxdy →
0

0

0

in L2 ([0, 1]).
1Z 1
0

f (x)f (y)g(x)g(y) dxdy = hf, gi2 .

Since by assumption hfi , gi > 0 and hf, gi > 0, it follows that fi → f in L2 ([0, 1]).



5.2. Convergence of Laplacians. Given a graphon W ∈ W[0,1] , let d : [0, 1] → R denote its
degree function:
Z 1
W (x, y) dy.
d(x) :=
0

We identify d with a multiplication operator Md : L∞ ([0, 1]) → L1 ([0, 1]) defined by
Md (f )(x) = d(x)f (x).

Definition 5.8. We define the Laplacian of W ∈ W[0,1] to be the operator LW : L∞ ([0, 1]) →
L1 ([0, 1]) given by
LW := Md − TW .
(5.9)
The next lemma shows that the corresponding sequence of Laplacians of a convergent sequence
of graphons is convergent in the L∞ → L1 operator norm.
Lemma 5.10. Let (Wn )n≥1 ⊂ W[0,1] and W0 ∈ W[0,1] . Suppose kWn − W0 k → 0 as n → ∞.
Then kLWn − LW0 k∞→1 → 0 as n → ∞.
Proof. We have
kLWn − LW0 k∞→1 = kMdn − TWn − Md0 + TW0 k∞→1

≤ kMdn − Md0 k∞→1 + kTW0 − TWn k∞→1

≤ kMdn − Md0 k∞→1 + 4kTW0 − TWn k .

18

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

It therefore suffices to show that kMdn − Md0 k∞→1 → 0 as n → ∞. Now,
kMdn − Md0 k∞→1 = sup kMdn (f ) − Md0 (f )k1
kf k∞ =1

Z

= sup

1

kf k∞ =1 0

|(dn (x) − d0 (x))f (x)| dx

= kdn − d0 k1
Z 1 Z 1
[Wn (x, y) − W0 (x, y)] dy dx
=
0

0

= k(TWn − TW0 )(1)k1

≤ kTWn − TW0 k∞→1

≤ 4kWn − W0 k .
It follows that kLWn − LW0 k∞→1 as n → ∞.



As Theorem 5.6 shows, if kWn − W0 k → 0, then the eigenvalues and eigenvectors of Wn
converge to those of W0 . However, the same result does not hold in general if Tn : L∞ → L1
is an arbitrary sequence of operators such that kTn − T0 k∞→1 → 0. In particular, even though
kLWn − LW0 k∞→1 → 0 when kWn − W0 k → 0, in general the eigenvalues and eigenvectors of
LWn may not converge. Such a phenomenon was previously observed in [23], where it is shown
problems can occur with unnormalized clustering in examples which are highly relevant to practical
applications (see Result 3 and the subsequent discussion, as well as Section 8.2, in [23]).
We now provide a family of examples to illustrate some of the problems that can occur in our
framework, when working with the unnormalized Laplacian. We first recall some preliminaries
on the essential spectrum. Let X be a Hilbert space, and denote the spectrum of an operator
T : X → X by
σ(T ) := {λ ∈ C : T − λI is not invertible}.
Recall that the discrete spectrum of T , denoted σdiscr (T ), is the set of isolated eigenvalues of T
of finite multiplicity. Denote by σess (T ) := σ(T ) \ σdiscr (T ) the essential spectrum of T ; this is a
closed subset of C. Moreover, σess (T + K) = σess (T ) for any compact operator K, i.e., the essential
spectrum is closed under compact perturbation. Recall that λ ∈ σ(T ) if and only if there exists a
sequence (ψk )k≥1 ⊂ X such that kψk k = 1 for all k, and
lim kT ψk − λψk k = 0.

k→∞

Moreover, λ ∈ σess (T ) if such a sequence (ψk )k≥1 with no convergent subsequence exists. See [8]
for more details on the essential spectrum.
Proposition 5.11. Given a continuous function g : [0, 1] → [0, 1], define the graphon Wg by:
Wg (x, y) := g(x)g(y),

Let E0 :=

g−1 (0).

x, y ∈ [0, 1].

Then the only eigenvalue for LWg is 0, with eigenspace given by
ker LWg = {f ∈ L2 ([0, 1]) : f is constant on [0, 1] \ E0 }.

However, σess (LWg ) = d([0, 1]) where d(x) := hg, 1ig(x) denotes the degree function of Wg .
Proof. In this proof, let 1 denote the constant function 1 on [0, 1], and denote by hg, f i the inner
product of g with f ∈ L2 ([0, 1]).
Notice that Wg has degree function d(y) = hg, 1ig(y). Now if (LWg f )(y) ≡ λf (y) on [0, 1] for
some eigenfunction f ∈ L2 ([0, 1]), then
f (y)(hg, 1ig(y) − λ) = (TWg f )(y) = g(y)hg, f i.

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

19

First notice, if g ≡ 0 then λ = 0 (since f 6≡ 0) and the result is easily shown. Thus, we assume
henceforth that g 6≡ 0, whence hg, 1i > 0. Now solve for f to obtain:
f (y) =

hg, f ig(y)
.
hg, 1ig(y) − λ

(5.12)

Notice that hg, f i =
6 0 since f 6≡ 0.
There are now several cases. If λ = 0 then f is constant on [0, 1] \ E0 (and a priori arbitrary on
E0 ). In this case the result is not hard to show.
We now show that the remaining values of λ cannot be eigenvalues for LWg . Indeed, first
suppose λ/hg, 1i ∈ g([0, 1]); then the preceding equation shows that f 6∈ L2 ([0, 1]), since λ 6= 0. For
all other values of λ, i.e. λ 6∈ hg, 1ig([0, 1]) ∪ {0}, evaluate both sides of Equation (5.12) against
g(y)hg, 1i2 /hg, f i and compute:
Z 1
Z 1
Z 1
λ2 dy
hg, 1i2 g(y)2
2
(hg, 1ig(y) + λ) dy +
dy =
.
hg, 1i =
0 hg, 1ig(y) − λ
0
0 hg, 1ig(y) − λ
Cancel hg, 1i2 , and simplify using that λ 6= 0, to obtain:
Z 1
λ dy
.
1=
0 λ − hg, 1ig(y)

(5.13)

There are now three cases. First if λ < 0, then since supy g(y) > 0 and g is continuous, hence
the integrand always lies in [0, 1], and is bounded above by
|λ|
∈ (0, 1)
|λ| + hg, 1i(supy g(y)/2)

on a set of positive measure. Therefore it cannot integrate to 1 on [0, 1].
The remaining cases are similar. First suppose λ/hg, 1i ∈ (0, inf y g(y)) (assuming g(y) is always
positive on [0, 1]). In this case, the integrand in Equation (5.13) is always negative, which is
impossible. The only other possibility for λ is λ/hg, 1i > supy g(y), since g([0, 1]) is an interval by
the continuity of g. In this case, the integrand always lies in [1, ∞), and is bounded below by
λ
∈ (1, ∞)
λ − hg, 1i(supy g(y)/2)

on a set of positive measure. Therefore it cannot integrate to 1 on [0, 1]. It follows that λ = 0 is
the only eigenvalue for the Laplacian of Wg .
Finally, since TWg is compact, σess (LWg ) = σess (Md ). Clearly, σ(Md ) ⊂ d([0, 1]). Now, let
λ ∈ d([0, 1]), say λ = d(x0 ). Since g is continuous, there exists a sequence ǫk → 0 such that
|d(x) − d(x0 )| < ǫk if |x − x0 | < 1/k. Now define
1
1x∈Ik .
Ik := B(x0 , 1/k) ∩ [0, 1],
ψk (x) := p
µL (Ik )
Note that kψk k2 = 1. Now,
kMd ψk −

λψk k22

=

Z

1
0

[(d(x) − d(x0 ))ψk (x)]2 dx ≤ ǫ2k · kψk k22 = ǫ2k → 0

as k → ∞. Clearly (ψk )k≥1 has no convergent subsequence in L2 ([0, 1]). Therefore, λ ∈ σess (Md ).

Proposition 5.11 above as well as the work in [23] demonstrate that significant problems can
occur when working with the unnormalized Laplacian in clustering applications. We now study
in detail the properties of the normalized Laplacian, and prove the structural consistency of the
resulting clustering algorithm under broad assumptions.

20

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

5.3. The normalized Laplacian. As in the unnormalized Laplacian case, we now extend the
normalized Laplacian of graphs to graphons. Recall that the normalized Laplacian L′G of a graph
G with n vertices is given by
L′G = D −1/2 LG D −1/2 = I − D −1/2 AD −1/2 ,

where D = diag(d1 , . . . , dn ) is a diagonal matrix with the degrees of the vertices on the diagonal,
and A is the adjacency matrix of G. The normalized Laplacian naturally arises in spectral clustering
when relaxing the Normalized Cut problem instead of the Ratio Cut problem (see [22, Section 5]
for more details). Akin to the unnormalized Laplacian, we extend the definition of the normalized
Laplacian by viewing it as an operator from L∞ to L1 .
Definition 5.14. Let W ∈ W[0,1] be a graphon with degree function d. We define the normalized
kernel W ′ by
( W (x,y)
√
, if d(x), d(y) 6= 0,
d(x)d(y)
W ′ (x, y) :=
0,
otherwise.
We define the normalized Laplacian of W to be the operator L′W : L∞ ([0, 1]) → L1 ([0, 1]) given by
L′W := M1d(x)6=0 − TW ′ .

(5.15)

Note that W ′ is not necessarily bounded. However, as we now show, if W ∈ W[0,1] , then
kW ′ k = kW ′ k1 is uniformly bounded. We will deduce this from the following technical lemma,
which will also be useful later for analyzing the convergence of normalized Laplacians.
Lemma 5.16. Let W ∈ W[0,1] with degree function d, and let W ′ denote the associated normalized
kernel as in Definition 5.14. Then for every measurable A, B ⊂ [0, 1],
Z
W ′ (x, y) dxdy ≤ µL (A)1/2 · µL (B)1/2 ,
(5.17)
A×B

and moreover,

Z

A×B

W ′ (x, y) dxdy ≤ 2 min(µL (A), µL (B)).

(5.18)

Proof. To prove the inequality (5.17), let P := {x ∈ [0, 1] : d(x) > 0}. Then
Z
Z
W (x, y)
′
p
dxdy.
W (x, y) dxdy =
d(x)d(y)
(A∩P )×(B∩P )
A×B

By the Cauchy–Schwarz inequality,
s
Z
Z 1Z 1s
W (x, y)
W (x, y)
W (x, y)
p
1A∩P (x)
1B∩P (y) dxdy
dxdy =
d(x)
d(y)
d(x)d(y)
(A∩P )×(B∩P )
0
0
1/2 Z 1 Z 1
1/2
Z 1 Z 1
W (x, y)
W (x, y)
1A∩P (x) dxdy
1B∩P (y) dxdy
≤
d(x)
d(y)
0
0
0
0
Z
1/2 Z
1/2
d(x)
d(y)
=
dx
dy
A∩P d(x)
B∩P d(y)
≤ µL (A)1/2 · µL (B)1/2 .

To prove the inequality (5.18), we may assume without loss of generality that the degree function
d is non-decreasing (otherwise, replace W by W σ for an appropriate σ ∈ S[0,1] ). Note that if
d(x) = 0, then W ′ (x, y) = 0 for almost every y ∈ [0, 1]. Thus,
Z
Z
Z
W (x, y)
p
dxdy.
W ′ (x, y) dxdy =
W ′ (x, y) dxdy =
d(x)d(y)
(A∩P )×B
(A∩P )×B
A×B

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

21

where P was defined above. Now,
Z
Z 1
Z
W (x, y)
W (x, y)
p
p
dxdy ≤
dxdy
d(x)d(y)
d(x)d(y)
A∩P 0
(A∩P )×B
Z
Z 1
W (x, y)
p
=2
dxdy
d(x)d(y)
y∈A∩P y
Z
Z 1
1
W (x, y) dxdy
≤2
y∈A∩P d(y) y
Z
Z 1
1
≤2
W (x, y) dxdy
y∈A∩P d(y) 0
= 2 · µL (A ∩ P )

≤ 2 · µL (A).

The result follows by carrying out a similar computation using B ∩ P instead of A ∩ P .



Corollary 5.19. Let W ∈ W[0,1] with degree function d, and let W ′ be the normalized kernel
associated to W as in Definition 5.14. Then
kW ′ k ≤ 1,
Moreover, the bound is sharp.
Proof. The bound kW ′ k ≤ 1 follows immediately from Equation (5.17). Using W ≡ 1, it follows
that the bound is sharp.

Corollary 5.20. The operator L′W : L∞ ([0, 1]) → L1 ([0, 1]) is bounded.
Proof. Recall that L′W = M1d(x)6=0 − TW ′ and that by Corollary 5.19, W ′ ∈ L1 ([0, 1]2 ). Thus, by
Fubini’s theorem, L′W is a well-defined operator from L∞ to L1 . The operator being bounded
follows from from the fact that the operator norm of TW ′ is equivalent to the cut-norm of W ′ (see
Equation (5.2)).

In the remainder of this subsection, our goal is to understand when the normalized Laplacians
converge. Doing so will allow us to derive the convergence of the eigenvectors and eigenvalues, and
conclude convergence of the spectral clustering derived from those Laplacians. The only assumption
that we will need is d0 > 0; in other words, the limit graphon does not have any isolated sparse
regions. In the case of finite graphs this is just asking for no isolated nodes. The following example
explains why the assumption that d0 > 0 is indeed necessary going forward in the paper. However,
once we make this assumption, we are able to show convergence of the normalized Laplacian in full
generality. See Theorem B.
Example 5.21. Consider first the case W0 = 0. Then any sparse sequence of graphons
Wn
Pm
converges to W0 in cut-norm. For example, let {Pi }m
1
P
×P
i
i.
i=1 be a partition of [0, 1]. Let U =
i=1
Let U δ be a small perturbation of U so that it maintains the same block diagonal structure as U
but has m simple eigenvalues in (1 − δ, 1) with eigenvectors that are small perturbations of 1Pi .
Then Wn = n1 U δ → W0 in cut-norm. Now, L′Wn = L′W1 = I − TW1′ for all n. Therefore, the limit
coloring will be defined by the partitions {Pi }m
i=1 . As this procedure applies for arbitrary partitions
of the unit interval [0, 1], any partition can be derived from Wn → 0 and spectral clustering fails to
be well-defined in the limit. In addition, the same argument shows that the normalized Laplacians
do not converge when the underlying graphons converge.
More generally, let W0 be a general graphon whose degree function d0 takes the value 0 on a
set of positive measure. Given W0 , we may permute it by σ ∈ S[0,1] and assume without loss of

22

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

+
generality that d0 (x) = 0 if and only if x ∈ E0 := [0, a] for some
 1]. Let W0 denote the
 a ∈ [0,
0
0
graphon restricted to E0c × E0c ; thus the graphon is of the form
0 W0+


0
0
+′
2
Let the normalized kernel be W0′ =
+′ . Under the assumption W0 ∈ L , we can say
0 W0
that W0′ is a symmetric, Hilbert–Schmidt operator, with a discrete spectrum of real eigenvalues
and only possible accumulation point at 0.
Pm
δ
Now let {Pi }m
i=1 be a partition of [0, a], and define U :=
i=1 1Pi ×Pi . Let U be a small
perturbation of U so that it maintains the same block diagonal structure as U , but has m simple
eigenvalues in (1−δ, 1) with eigenvectors that are small perturbations of 1Pi . This timewe pick δ >0
1 δ
U
0
to be less than the gap between 1 and the next largest eigenvalue of W0′ . Let Wn = n
,
0
W0+
then Wn → W0 . Once again, because of the normalization occurring in L′Wn , we find that the limit
+
clusters will be defined by the {Pi }m
i=1 irrespective of the structure of the dense part W0 of W0 .

Theorem B. Let (Wn )n≥1 ⊂ W[0,1] such that kWn − W0 k → 0. Let dn and d0 denote the degree
functions of Wn and W0 respectively. Assume that d0 (x) > 0 for almost every x. Define Wn′ and
W0′ as in Definition 5.14. Then
kWn′ − W0′ k → 0

as n → ∞.

Moreover, we have kL′Wn − L′W0 k∞→1 → 0 as n → ∞.

Proof. Let ǫ > 0. Since d0 (x) > 0 for almost every x, we can pick λ ∈ (0, 1] be such that
−1
µL (d−1
0 ([0, 2λ))) < ǫ. Suppose dn (x) < λ. Then either x ∈ d0 ([0, 2λ)), or x ∈ {w ∈ [0, 1] :
|dn (w) − d0 (w)| > λ}. Since dn → d0 in L1 (see the proof of Lemma 5.10), there exists Nǫ such
that for n ≥ Nǫ ,
µL {x ∈ [0, 1] : |dn (x) − d0 (x)| ≥ λ} ≤ ǫ.
(5.22)

It follows that for n ≥ Nǫ ,
Now, for n ≥ 0, define
and let Z :=

[0, 1]2

µL (d−1
n ([0, λ))) ≤ 2ǫ.

(5.23)

Pn := {x ∈ [0, 1] : dn (x) > 0},

\ (Pn × Pn ). We claim that for n ≥ Nǫ ,
Wn′ (x, y)

k(Wn′ − W0′ )1Z k ≤ 8ǫ.

(5.24)

= 0 for almost all y ∈ [0, 1] and so, for A ⊂
Indeed, if dn (x) = 0, then
Z
Z
′
′
[Wn (x, y) − W0 (x, y)] dxdy ≤
Wn′ (x, y) dxdy

Pnc

and B ⊂ [0, 1],

Pnc ×[0,1]

A×B

=

Z

Pnc ×[0,1]

W (x, y)
p n
dxdy.
dn (x)dn (y)

For n ≥ Nǫ , we have by (5.22) that µL (Pnc ) ≤ 2ǫ. It follows by Equation (5.17) that
Z
[Wn′ (x, y) − W0′ (x, y)] dxdy ≤ 4ǫ.
A×B

This proves (5.24).
We will now prove that k(Wn′ − W0′ )1Pn ×Pn k ≤ 8ǫ for n is large enough. To do so, define:
−1
Qn := d−1
0 ((0, λ)) ∪ dn ((0, λ)),
Sn := Rn × Rn ,

Rn := Pn \ Qn ,
Tn := (Pn × Pn ) \ Sn .

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

23

We will first prove that k(Wn′ − W0′ )1Tn k ≤ 16ǫ if n ≥ Nǫ . Indeed, If A, B ⊂ Tn , then
!
Z
Z
W0 (x, y)
Wn (x, y)
′
′
p
−p
dxdy
[Wn (x, y) − W0 (x, y)] dxdy =
dn (x)dn (y)
d0 (x)d0 (y)
A×B
A×B
Z
Z
Wn (x, y)
W (x, y)
p
p 0
≤
dxdy +
dxdy
dn (x)dn (y)
d0 (x)d0 (y)
Tn
Tn
≤ 8ǫ + 8ǫ = 16ǫ.
where the last inequality was obtained by Equations
√ (5.18) and (5.23).
′
′
Finally, we show that k(Wn − W0 )1Sn k ≤ ǫ(2/ λ+ 1) for n large enough. Note that for x ∈ Rn ,
we have |dn (x)−1/2 − d0 (x)−1/2 | ≤ 1/λ1/2 . Since x−1/2 is Lipschitz in [λ, 1] with Lipschitz constant
C for some C > 0, we have
Z
Z
−1/2
−1/2
|dn (x) − d0 (x)| < ǫ
|dn (x) − d0 (x)|dx ≤ C ·
Rn

Rn

for n ≥ Mǫ since dn → d0 in L1 . Now, for x, y ∈ P0 ∩ Pn , we have
Wn′ (x, y) − W0′ (x, y)

Wn (x, y)
W0 (x, y)
=p
−p
dn (x)dn (y)
d0 (x)d0 (y)
=

+

W (x, y)
Wn (x, y)
p n
−p
dn (x)dn (y)
dn (x)d0 (y)

!

W0 (x, y)
W (x, y)
p 0
−p
dn (x)d0 (y)
d0 (x)d0 (y)

+

!

.

W0 (x, y)
W (x, y)
p n
−p
dn (x)d0 (y)
dn (x)d0 (y)

!

We will bound the integral of each term separately.
First, for A, B ⊂ Rn ,
!
Z
Z
1
Wn (x, y)
Wn (x, y)
1
Wn (x, y)
p
p
p
−p
dxdy ≤
−p
dxdy
dn (x)dn (y)
dn (x)d0 (y)
dn (y)
d0 (x)
dn (x)
A×B
A×B
1
≤ǫ· √ .
λ
For the second term, we have
Z

A×B

W0 (x, y)
W (x, y)
p n
−p
dn (x)d0 (y)
dn (x)d0 (y)

!

dxdy

1
dxdy
(Wn (x, y) − W0 (x, y)) p
dn (x)d0 (y)
A×B
Z
1
(Wn (x, y) − W0 (x, y)) f (x)g(y) dxdy
sup
≤
λ f,g:[0,1]→[0,1] [0,1]2

=

Z

supp f,g⊂Rn

1
1
≤ k(Wn − W0 )1Sn k ≤ kWn − W0 k ≤ ǫ
λ
λ
for n ≥ Nǫ′ .

24

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

For the third term, we have
Z

A×B

1
≤√
λ

Z

W0 (x, y)
W (x, y)
p 0
−p
dn (x)d0 (y)
d0 (x)d0 (y)

A×B

1
≤ǫ· √ .
λ

1

p

dn (x)

−p

1

d0 (x)

!

dxdy

W0 (x, y) dxdy

Putting everything together, we conclude that
1
k(Wn′ (x, y) − W0′ (x, y))1Sn k ≤ 2ǫ · √ + ǫ
λ
for n ≥ max(Nǫ , Mǫ , Nǫ′ ). Finally, combining all the inequalities, we obtain that
√
kWn′ − W0′ k ≤ (25 + 2/ λ) · ǫ.

We conclude that Wn′ → W0′ in cut-norm. To complete the proof of the theorem, note that for
n ≥ max(Nǫ , Mǫ , Nǫ′ ),
||L′Wn − L′W0 ||∞→1 ≤ ||M1dn (x)6=0 − M1d0 (x)6=0 ||∞→1 + ||TWn′ − TW0′ ||∞→1 .
≤ µL ({x : dn (x) = 0}) + 4kWn′ − W0′ k
≤ 2ǫ + 4kWn′ − W0′ k

by (5.22), and this approaches 0.



We conclude this subsection by observing that the usual eigenvalue bounds hold for our generalized version of the normalized Laplacian:
Proposition 5.25. Given W ∈ W[0,1] with degree function d, all eigenvalues of the normalized
Laplacian L′W lie in [0, 2].
Proof. We provide a proof-sketch for completeness, as our setting is slightly more general than is
usually found in the literature (although the argument is more or less standard). Define D+ :=
{x ∈ [0, 1] : d(x) > 0}; now if L′W g = λg for some (nonzero) eigenfunction g, then evaluating
against g yields:
Z Z
Z 1
Z 1
W (x, y)
2
2
g(y) dy dx.
g(x) p
g(x) d(x)1d(x)>0 dx −
g(x) dx =
λ
d(x)d(y)
D+ D+
0
0
p
Define h(x) := g(x)/ d(x) on D+ , and 0 otherwise. Then one verifies that the above equation
translates to:
Z Z
Z 1
1
2
W (x, y)(h(x) − h(y))2 dydx ≥ 0,
λ
g(x) dx =
2
D+ D+
0
whence λ ≥ 0. On the other hand,
Z Z
Z Z
1
1
2
W (x, y)(h(x) − h(y)) dydx ≤
W (x, y)(2h(x)2 + 2h(y)2 ) dydx
2 D+ D+
2 D+ D+
Z 1
Z
g(x)2 dx,
h(x)2 d(x) dx ≤ 2
=2
D+

from which it follows that λ ≤ 2.

0



MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

25

5.4. Structural consistency of spectral clustering (normalized Laplacian). We now examine the convergence of the eigenvalues and eigenvectors of the normalized Laplacian of a convergent
sequence of graphons.
Given a graphon W ∈ W[0,1] , we will denote by µ1 (W ), . . . , µk (W ) the k smallest nonzero
1 , . . . , f k ∈ L2 ([0, 1]) associated eigenveceigenvalues of L′W (see Proposition 5.25), and by fW
W
tors/eigenfunctions.
Theorem C. Fix m ≥ 1, let Dm,α be the set of graphons W such that, W ′ ∈ L∞ ([0, 1]2 ) is
uniformly bounded above by α > 0, and µ1 (W ), . . . , µm (W ) are all simple. Let (Wn )n≥1 ⊂ Dm,α
and W0 ∈ Dm,α such that kWn − W0 k → 0 as n → ∞. Assume that
Z 1
W0 (x, y) dy > 0
for a.e. y ∈ [0, 1].
0

Normalize the associated eigenvectors of the smallest m eigenvalues µ1 (Wn ), . . . , µm (Wn ) so that
1
m
hfW
, hi > 0, . . . , hfW
, hi > 0
n
n

for some h ∈ L∞ ([0, 1]) and all n ≥ 0. Define f : {Wn : n ≥ 0} × [0, 1] → Rm by
m
1
(y))T .
(y), . . . , fW
f (Wn , y) := (fW
n
n

m be a collection of disjoint open sets such that for all
Moreover, let N ≥ 1 and let (Aj )N
j=1 ⊂ R
n ≥ 0,
N
[
Aj
for a.e. y ∈ [0, 1].
f (Wn , y) ∈
j=1

Then we have:
(1) f (W σ , y) = f (W, σ(y)) for all σ ∈ S[0,1] , W ∈ Dm,α , and almost every y ∈ [0, 1].
(2) Set S := {1, . . . , N }, and for n ≥ 0, define F (Wn ) := (Wn , cWn ), where cWn (y) is the unique
j ∈ {1, . . . , N } such that f (Wn , y) ∈ Aj . Then kF (Wn ) − F (W0 )kS → 0 as n → ∞.
Remark 5.26. It is useful to examine how Theorem C above compares to the theorems in [23] on
convergence of spectral clustering using normalized Laplacians. Firstly, in that work, the degree
functions dn satisfy dn ≥ λ > 0. We make a more general assumption about the normalized
Laplacians (see Example 5.27). Secondly and very importantly, we do not make a specific modeling
assumption about the data generating mechanism for the graphs. We merely assume that the
graphs come to us in a way that is convergent in the graph topology. This subsumes the mechanism
assumed in [23] as a special case and includes many others. As a consequence, our arguments require
different techniques which are suitable to the graphon topology.
Example 5.27. We illustrate with an example how Theorem C allows working outside the setting
in [23], in which the degree was assumed to be bounded away from zero. Fix α > 1, and consider
distinct measurable functions g1 , . . . , gk : [0, 1] → [0, 1] such that
Z 1
gi (x) dx ≥ α−1 ∀i.
k(g1 , . . . , gk )k∞ ≤ 1,
0

Define

W (x, y) :=

k
X
i=1

gi (x)gi (y) ∈ W[0,1] .

Using the notation h·, ·i for the inner product in L2 , the degree function is dW (y) =
and this is not necessarily bounded away from 0. Now the normalized kernel is
P
i gi (x)gi (y)
.
W ′ (x, y) = pP
P
i hgi , 1igi (x) ·
i hgi , 1igi (y)

P

i hgi , 1igi (y),

26

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

Now note that since gi (y) ∈ [0, 1], by choice of α we have
k
X
i=1

gi (y)2 ≤

k
X
i=1

gi (y) · hgi , 1iα,

∀y ∈ [0, 1].

Hence by the Cauchy–Schwarz inequality,
P
P
gi (x)2
gi (y)2
′
2
i
W (x, y) ≤ P
·P i
≤ α2 ,
hg
,
1ig
(x)
hg
,
1ig
(y)
i
i
i
i
i
i

whence W ′ (x, y) ∈ [0, α], satisfying the corresponding hypothesis in Theorem C.
We now prove Theorem C.
Proof of Theorem C. To verify (1), suppose λ is an eigenvalue of TW for some symmetric W ∈
L2 ([0, 1]2 ). Let fW ∈ L2 ([0, 1]) be an associated eigenfunction. Then for σ ∈ S[0,1] ,
Z 1
Z 1
W σ (x, y)fW (σ(y)) dy.
W (σ(x), y)fW (y) dy =
λfW (σ(x)) =
0

0

Therefore λ is also an eigenvalue of TW σ with associated eigenfunction fW σ (x) = fW (σ(x)). This
proves (1).
Now suppose kWn − W0 k → 0. By Theorem B, kWn′ − W0′ k → 0, where Wn′ and W0′ denote the
normalized kernels as in Equation (5.14). By Proposition 5.25, the smallest m nonzero eigenvalues
µ1 (Wn ), . . . , µm (Wn ) of L′Wn are in bijection with the largest eigenvalues λ1 (Wn′ ), . . . , λm (Wn′ ) of
Wn′ that are not equal to 1. By Theorem 5.6, these eigenvalues converge to λ1 (W0′ ), . . . , λm (W0′ ).
Moreover, since Wn ∈ Dm,α ∀n, the eigenvectors associated to λ1 (Wn′ ), . . . , λm (Wn′ ) are the same as
the eigenvectors of L′Wn associated to 1 − λ1 (Wn′ ), . . . , 1 − λm (Wn′ ). Now since the Wn′ are uniformly
bounded by α, apply Theorem 5.6(2) and Lemma 5.7 to obtain
i
i
− fW
k →0
kfW
n
0 2

as n → ∞

(i = 1, . . . , m).

Since [0, 1] has finite measure, by Cauchy–Schwarz it follows that
i
i
− fW
k →0
kfW
n
0 1

as n → ∞

(i = 1, . . . , m).

Now since
kf (Wn ) − f (W0 )k1 ≤

m
X
i=1

i
i
kfW
− fW
k ,
n
0 1

it follows that f (Wn ) → f (W0 ) as n → ∞. The result now follows by Theorem A.



Remark 5.28. The assumption that Wn′ are uniformly bounded guarantees a well behaved spectrum in the limit. To illustrate
the difficulty of working without some regularity hypothesis, consider
F
any partition of [0, 1] = ∞
I
j=1 j into countably many measurable subsets with positive measures.
Define the graphon
∞
X
1Ij ×Ij .
W0 (x, y) =
j=1

In this case,

W0′

=

∞
X
j=1

1
1I ×I ,
µL (Ij ) j j

so

kW0′ k22

=

∞
X
j=1

1 = ∞.

In particular, W0′ is not bounded either. If we now compute the eigenvalues and eigenvectors of W0′ ,
we find that the spectrum consists of just 0 and 1, both with infinite multiplicity. In particular,
1Ij is an eigenvector of eigenvalue 1 for all j.

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

27

We can now perturb W0 to W1 while preserving the block structure, so that there will be one
eigenvalue of W1′ in (1 − ǫj , 1) corresponding to one eigenvector which is a small perturbation of
1Ij . If the ǫj → 0 then the eigenvalues of W1′ converge to 1. It is no longer clear how to properly
define the clustering for the limit of the corresponding normalized Laplacian sequence in that case.
Appendix A. Proofs for dense S-colored graph limit theory
Proof of Theorem 3.5:
Before proving the result, we explain the general idea of the proof on an example. We adapt
the idea in [15, Lemma 10.24]. Suppose H is a path on 4 vertices, V (H) = {1, 2, 3, 4}, E(H) =
{(1, 2), (2, 3), (3, 4)}. Then,
tS (H, W ) − tS (H, W ′ ) =
Z
4
Y
1cW (xi )=cH (i) dxi
fW (x1 , x2 )fW (x2 , x3 )fW (x3 , x4 ) ·
[0,1]4

−

Z

=

Z

+

+

+

Z
Z
Z

i=1

[0,1]4

fW ′ (x1 , x2 )fW ′ (x2 , x3 )fW ′ (x3 , x4 ) ·

4
Y

1cW ′ (xi )=cH (i) dxi

i=1

4
Y

[0,1]4

[fW (x1 , x2 )fW (x2 , x3 )fW (x3 , x4 ) − fW (x1 , x2 )fW (x2 , x3 )fW ′ (x3 , x4 )] ·

[0,1]4

[fW (x1 , x2 )fW (x2 , x3 )fW ′ (x3 , x4 ) − fW (x1 , x2 )fW ′ (x2 , x3 )fW ′ (x3 , x4 )] ·

[0,1]4

[fW (x1 , x2 )fW ′ (x2 , x3 )fW ′ (x3 , x4 ) − fW ′ (x1 , x2 )fW ′ (x2 , x3 )fW ′ (x3 , x4 )] ·

[0,1]4

fW ′ (x1 , x2 )fW ′ (x2 , x3 )fW ′ (x3 , x4 ) ·

4
Y
i=1

1cW (xi )=cH (i) −

4
Y

1cW (xi )=cH (i) dxi

i=1
4
Y

1cW ′ (xi )=cH (i)

i=1

1cW (xi )=cH (i) dxi

i=1
4
Y

1cW (xi )=cH (i) dxi

i=1

!

4
Y

dxi

i=1

Thus, to prove the Counting Lemma, it suffices to obtain a bound for integrals of the form:
Z
4
Y
Y
1cW (xi )=cH (i) dxi ,
We (xes , xet ) ·
(fW (x1 , x2 ) − fW ′ (x1 , x2 ))
[0,1]4

i=1

e∈E(H)\(1,2)

where 0 ≤ We (x, y) ≤ 1 are arbitrary functions, and a bound for
! 4
Z
4
4
Y
Y
Y
dxi .
1cW ′ (xi )=cH (i)
1cW (xi )=cH (i) −
fW ′ (x1 , x2 )fW ′ (x2 , x3 )fW ′ (x3 , x4 ) ·
[0,1]4

i=1

i=1

i=1

We now provide such bounds.

Proof. As explained above, to prove the lemma, it suffices to provide a bound for
Z
Y
Y
Y
dxv (A.1)
We (xes , xet )
(fW (xα , xβ ) − fW ′ (xα , xβ ))
1cW (xv )=cH (v)
[0,1]V (H)

e∈E(H)\(α,β)

v∈V (H)

v∈V (H)

where 0 ≤ We ≤ 1 are arbitrary functions, and a bound for


Z
Y
Y
Y
Y
fW ′ (xes , xet ) 
1cW (xv )=cH (v) −
1cW ′ (xv )=cH (v) 
dxv . (A.2)
[0,1]|V (H)| e∈E(H)

v∈V (H)

v∈V (H)

v∈V (H)

28

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

Given v ∈ V (H), denote by ∇(v) := {(es , et ) ∈ E(H) : es = v or et = v}, and let
Y
Y
We (es , et )
dxv ,
f (xα ) :=
e∈∇(α)\(α,β)

Y

g(xβ ) :=

v∈V (H)\{α,β}

We (es , et )

e∈E(H)\∇(α)

Y

dxv ,

v∈V (H)\{α,β}

f1 (xα ) := 1cW (xα )=cH (α)

Y

1cW (xv )=cH (v) dxv ,

v∈V (H)\{α,β}

g1 (xβ ) := 1cW (xβ )=cH (β) .

Using this notation, we obtain the following bound for (A.1)
Z

[0,1]|V (H)|

≤

Z

≤

Z

(fW (xα , xβ ) − fW ′ (xα , xβ ))f (xα )g(xβ )f1 (xα )g1 (xβ )

[0,1]|V (H)|−2

[0,1]|V (H)|−2

Z

[0,1]2

Y

dxv

v∈V (H)

(fW (xα , xβ ) − fW ′ (xα , xβ ))f (xα )g(xβ )f1 (xα )g1 (xβ ) dxα dxβ

kW − W ′ k

′

= kW − W k ,

Y

Y

dxv

v∈V (H)\{α,β}

dxv

v∈V (H)\{α,β}

since 0 ≤ f (xα )f1 (xα ) ≤ 1 and 0 ≤ g(xβ )g1 (xβ ) ≤ 1. For (A.2), we have


Z
Y
Y
Y
Y
dxv
1cW (xv )=cH (v) −
1cW ′ (xv )=cH (v) 
fW ′ (xes , xet ) 
[0,1]|V (H)| e∈E(H)

≤

Z

Y

[0,1]|V (H)| v∈V (H)
|S|



v∈V (H)

1cW (xv )=cH (v) −

Y

v∈V (H)

 

−1
(s)
∆
×
c
(s)
× c−1
W
W′

v∈V (H)

v∈V (H)

1cW ′ (xv )=cH (v)

Y

dxv

v∈V (H)

= µL
s∈S
s∈S
X
−1
−1
≤
µL (cW (s)∆cW ′ (s)).
s∈S

The result now follows by a telescoping argument as the one provided before the proof.



Proof of Theorem 3.7. Let (Wn )n≥1 ⊂ WS be a sequence of colored graphons. We will show that
(Wn )n≥1 has a convergent subsequence. Note that there exist measure preserving maps σn : [0, 1] →
[0, 1] such that the partitions defined by the c−1
(s) for s ∈ S are intervals ordered in a fixed
Wnσn
arbitrary ordering of colors S. Without loss of generality, we will assume that such transformations
have been applied to the Wn so that the c−1
Wn (s) are ordered intervals. Moreover, since the vector
−1
of measures (µL (cWn (s)))s∈S sits on the simplex which is compact, we can also assume that this
vector also converges as n → ∞. It follows that the limit c0 (x) := limn→∞ cWn (x) exists almost
−1
everywhere on [0, 1] and µL (c−1
Wn (s)∆c0 (s)) → 0 as n → ∞ for every s ∈ S.
The proof now proceeds as in [16, Theorem 9.23]. Note that the original partitions Pn,1 can always
be chosen to respect the partition defined by c−1
Wn (s) for s ∈ S. Since the successive partitions Pn,k
are refinements of Pn,1 , they will also respect the coloring. Proceeding as in [16, Theorem 9.23],
we obtain a subsequence Wnk and W0 ∈ W such that kWnk − W0 k → 0. Finally, since cW0 = c0

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

29

−1
S
and µL (c−1
Wnk (s)∆c0 (s)) → 0, then kWnk − W0 k → 0 as well. This concludes the proof of the
theorem.


Proof of Theorem 3.8. We adapt a proof of L. Schrijver [20] to the colored graphon case.
Let GS be the set of isomorphism classes of S-colored finite simple graphs with no isolated vertices.
S ) → [0, 1]GS defined by setting the H component of M (W ) to
Then there is a map M : (WS / ∼, δ
be equal to tS (H, W ). This map is continuous and well-defined by the Counting Lemma for colored
S ) is compact (Theorem 3.7) and [0, 1]GS is Hausdorff, it
graphons (Lemma 3.5). Since (WS / ∼, δ
suffices to show that the map M is injective in order to conclude that it is a homeomorphism onto
its image, thereby concluding the proof.
To show the injectivity of M , assume that two colored graphons U, V ∈ WS have equal homoS (U, V ) = 0 we work with a few sampling
morphism densities for all H ∈ GS . To show that δ
distributions.
Let HS (n, U ) denote a random weighted graph sampled from U by sampling (Xi )ni=1 i.i.d. from
the uniform distribution on [0, 1], and then taking U (Xi , Xj ) to be the weight between nodes i
and j. The coloring is defined by cHS (n,U ) (i) := cU (Xi ). Given an S-colored weighted graph H
with n vertices, let GS (H) denote the finite S-colored graph G on n vertices where for i > j,
(i, j) ∈ E(G) with probability H(i, j) and G is made symmetric. The coloring cG (i) := cH (i).
Lastly, let GS (n, U ) := GS (HS (n, U )), so that the HS (n, U ) and GS (n, U ) are coupled in this way.
Note that GS (n, U ) = GS (n, V ) in law for every n, because the probabilities P(GS (n, W ) = H)
can be derived from the homomorphism densities tS (H, W ) by inclusion-exclusion.
S (U, V ) ≤ δ S (U, G (n, U )) + δ S (V, G (n, U )). Thus,
By the triangle inequality, δ
S
S


S
S
S
δ
(U, V ) ≤ E(δ
(U, GS (n, U ))) + E(δ
(V, GS (n, U )))

S
S
= E(δ
(U, GS (n, U ))) + E(δ
(V, GS (n, V ))).

S (G (n, W ), W )) → 0 for any graphon
To conclude the proof, it therefore suffices to show that E(δ
S
W ∈ WS as n → ∞. We first show that HS (n, W ) and GS (n, W ) are close when coupled in the
obvious way. Let H be a weighted graph with n vertices. We claim that there exists some fixed
constant C > 0 so that
2 2
P(dS (GS (H), H) > ǫ) ≤ e−ǫ n /C ,

where dS (W, W ′ ) = kW − W ′ kS . To bound the cut-norm of a step function W ,
Z
W (x, y)dxdy ,
kW k = sup
A,B⊂[0,1]

A×B

it suffices to consider only the sets A, B which are composed of unions of steps. Therefore we
consider for any subsets A, B ⊂ {1, . . . , n} the random variable
X
1((i, j) ∈ E(GS (H))) − βij (H).
i∈A,j∈B

The Chernoff Inequality yields




X
−ǫ2 n4
P
1((i, j) ∈ E(GS (H))) − βij (H) > ǫn2  ≤ 2 exp
C|A||B|
i∈A,j∈B

n
for some fixed constant C > 0. There are only
√ 4 pairs of sets A, B so our claim follows by the
union bound. We conclude, by picking ǫ = C/ n, that

C
E(dS (GS (H), H)) ≤ √ + e−Cn
n
which goes to zero as n → ∞.

30

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

For graphons W, W ′ ∈ WS , define

dS1 (W, W ′ ) := kW − W ′ k1 +

and let

δ1S (W, W ′ )

:= inf σ∈S[0,1]

dS1 (W, W ′ ).

Clearly,

X

−1
µL (c−1
W (s)∆cW ′ (s)),

s∈S

S
δ
(W, W ′ ) ≤ δ1S (W, W ′ ).

We will now show that E(δ1S (HS (n, W ), W ))) → 0. Let P be a finite partition of [0, 1] which is a
refinement of the fibers of the coloring cW . Then define WP to be the graphon obtained from W
by averaging over the rectangles defined by the partitions P with cWP := cW .
The triangle inequality yields
E(δ1S (W, HS (n, W ))) ≤ δ1S (W, WP ) + E(δ1S (WP , HS (n, WP )))
+ E(δ1S (HS (n, W ), HS (n, WP )))

where HS (n, W ) and HS (n, WP ) are coupled by the joint choice of Xi when sampling.
Note that the first term is small for sufficiently fine P. The second term is small for sufficiently
large n, since we need only count the number of points in each partition in P. For the third term,
we claim that
E(dS1 (HS (n, W ), HS (n, V ))) = dS1 (W, V )
when HS (n, W ) and HS (n, V ) are coupled by the joint choice of Xi when sampling. Indeed, let
X1 , . . . , Xn be independent random variables uniformly distributed on [0, 1]. Then


n
X
1
|W (Xi , Xj ) − V (Xi , Xj )|
E(kHS (n, W ) − HS (n, V )k1 ) = E  2
n
i,j=1

1
= 2
n

n
X

Z

2
i,j=1 [0,1]

|W (xi , xj ) − V (xi , xj )| dxi dxj

= kW − V k1 .

i
To compute the other terms of dS1 , we examine which color is assigned to each interval ( i−1
n , n ] of
the two graphons. Indeed, for each s ∈ S,
n
 1X

−1
−1
(s))
=
(s)∆c
E µL (c−1
P(Xi ∈ c−1
W (s)∆cV (s))
HS (n,V )
HS (n,W )
n

=

i=1
−1
µL (c−1
W (s)∆cV (s)).

We conclude that

E(dS1 (HS (n, W ), HS (n, V ))) = dS1 (W, V ).
Finally, by the triangle inequality,
S
S
E(δ
(GS (n, W ), W ))) ≤ E(δ
(GS (n, W ), HS (n, W ))) + E(δ1S (W, HS (n, W ))),

and both terms on the right converge to zero as shown above. We therefore have that
S
lim E(δ
(GS (n, W ), W ))) = 0,

n→∞

as desired. This concludes the proof.



Proof of Theorem 3.9. Without loss of generality, assume S = {1, . . . , N } and let (W, cW ) ∈ WS .
There exist a partition of [0, 1] into intervals I1 , . . . , IN and a measure preserving bijection σ ∈
S[0,1] such that cW (σ(x)) ≡ i for a.e. x ∈ Ii . Without loss of generality, we will assume W has
this property (otherwise, replace W by W σ ). By the density of graphs in W[0,1] , there exists a
sequence of graphs (Gn )n≥1 such that kWGn − W k → 0 as n → ∞. Let vn := |V (Gn )| and

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

31

assume without loss of generality that V (Gn ) = {1, . . . , vn }. We will also assume, without loss
of generality, that vn → ∞. Note that for n large enough, almost every point in the interval
((i − 1)/vn , i/vn ] is contained in one of the Ij , say in IJ(i) . Define cGn (i) = J(i). It follows easily
that k(WGn , cWGn ) − (W, cW )kS → 0 as n → ∞.

Appendix B. Riesz–Fischer theorem for metric space-valued maps
Recall the Riesz–Fischer theorem, which says that Rm -valued Lp functions form a complete
(pseudo)metric space. In order to formulate one of the main results of this paper (Theorem A)
in complete generality, it is of interest to understand if the Riesz–Fischer theorem holds for more
general spaces, such as Banach spaces or even metric spaces. We now show the result holds for any
complete metric space. We provide a proof, as we were unable to find it in the literature.
Theorem B.1 (Riesz–Fischer for metric spaces). Suppose (Ω, µ) is a finite measure space, and
(X, dX ) is a metric space. Given 1 ≤ p < ∞, let Lp (Ω, X) denote the Borel-measurable functions
f : Ω → X such that for any (equivalently, every) x ∈ X,
Z
dX (f (ω), x)p dµ < ∞,
Ω

and given f, g ∈ Lp (Ω, X), define

dp (f, g) :=

Z

p

dX (f (ω), g(ω)) dµ
Ω

1/p

.

Now if (X, dX ) is a complete metric space, then dp equips Lp (Ω, X) with the structure of a complete
metric space.
As usual, we identify functions in Lp (Ω, X) that are equal almost everywhere on Ω.
Proof. First we reduce the situation to Banach spaces. Fix a point x0 ∈ X, and recall that the
Kuratowski embedding Φx0 : X → Cb (X) given by
Φx0 (x)(y) := dX (x, y) − dX (x0 , y)

is an isometric embedding. Therefore, we may identify X with its image inside the Banach space
Cb (X) via Φx0 . Now suppose fn is a Cauchy sequence in Lp (Ω, Φx0 (X)) ⊂ Lp (Ω, Cb (X)). Note
that the Riesz–Fischer theorem for maps in Lp (Ω, Cb (X)) is stated in [3], for instance, and can
Lp

be applied to show that fn −→ f for some f ∈ Lp (Ω, Cb (X)). However, it is not immediate that
f ∈ Lp (Ω, Φx0 (X)), whence we provide a proof for completeness.
The proof follows [19, Theorem 3.11]. Since fn is Cauchy, there exists a sequence of integers
n1 < n2 < · · · , such that if m, n ≥ nk then dp (fn , fm ) < 2−k . Now define
gk (ω) :=

k
X

dX (fnj (ω), fnj+1 (ω)),

g(ω) :=

∞
X

dX (fnj (ω), fnj+1 (ω)),

j=1

j=1

(x′ )k

=: kx − x′ k for x, x′ ∈ X. Now integrating
where we will identify dX
= kΦx0 (x) − Φx0
p
on Ω, we obtain by Minkowski inequality in L ([0, 1], R) (and the choice of nk ) that kgk kp < 1 for
all k. It follows that kgkp ≤ 1 by Fatou’s Lemma. In particular, g(ω) is finite a.e. µ, whence the
series
∞
X
f (ω) := fn1 (ω) +
(fnk+1 (ω) − fnk (ω))
(x, x′ )

k=1

= Φx0 (fn1 (ω)) +

∞
X
k=1


Φx0 (fnk+1 (ω)) − Φx0 (fnk (ω))

32

PETER DIAO, DOMINIQUE GUILLOT, APOORVA KHARE, AND BALA RAJARATNAM

converges absolutely a.e. µ. Set f (ω) := 0 = Φx0 (x0 ) on the remaining null set; then f converges
absolutely on all of Ω, hence converges on all of Ω in the Banach space Cb (X). Moreover, f (ω) is
the pointwise limit of fnk (ω) ∈ Φx0 (X) ⊂ Cb (X). Since X and hence Φx0 (X) is complete, it follows
that f has image in Φx0 (X).
Lp

It remains to show that fn −→ f and f ∈ Lp (Ω, Φx0 (X)). Fixing ǫ > 0, there exists N such that
kfn − fm kp < ǫ for n, m > N . Hence if m > N , then by Fatou’s Lemma,
Z
Z
p
kfnk (ω) − fm (ω)kp dµ ≤ ǫp .
kf (ω) − fm (ω)k dµ ≤
lim inf
k→∞

Ω

Ω

Lp (Ω, C

p
p
It follows that f − fm ∈
b (X)), whence f ∈ L (Ω, Cb (X)) (and hence in L (Ω, Φx0 (X)) from
above). The preceding computation also shows that kf − fm kp → 0 as m → ∞, which concludes
the proof.


As an immediate consequence of Theorem B.1, we obtain that continuous metric-valued nodelevel statistics automatically extend to W[0,1] .
Corollary B.2. Let (X, dX ) be a metric space and let f : G → L1 ([0, 1], X) be a continuous
node-level statistic (see Definition 4.3). Then f extends to a continuous function f : W[0,1] →
L1 ([0, 1], X).
Note that the proof of Theorem B.1 also implies the following result, which may be interesting
in its own right.
Proposition B.3. With (Ω, µ) and (X, dX ) as above, every Cauchy sequence in Lp (Ω, X) converging to f ∈ Lp (Ω, X), has a subsequence that converges a.e. µ to f .
References
[1] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation.
Neural computation, 15(6):1373–1396, 2003.
[2] Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. In
Learning theory, pages 486–500. Springer, 2005.
[3] Salomon Bochner and Angus E. Taylor. Linear functionals on certain spaces of abstractly-valued functions. Ann.
of Math. (2), 39(4):913–944, 1938.
[4] Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Shirshendu Ganguly. Consistent nonparameteric estimation for heavy-tailed sparse graphs. Preprint, available at http://arxiv.org/abs/1508.06675, 2015.
[5] Christian Borgs, Jennifer T. Chayes, and László Lovász. Moments of two-variable functions and the uniqueness
of graph limits. Geom. Funct. Anal., 19(6):1597–1619, 2010.
[6] Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv. Math., 219(6):1801–1851,
2008.
[7] Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2), 176(1):151–219, 2012.
[8] David E. Edmunds and William D. Evans. Spectral theory and differential operators. Oxford Mathematical
Monographs. The Clarendon Press, Oxford University Press, New York, 1987. Oxford Science Publications.
[9] Brian S. Everitt, Sabine Landau, Morven Leese, and Daniel Stahl. Cluster analysis. Wiley Series in Probability
and Statistics. John Wiley & Sons, Ltd., Chichester, fifth edition, 2011.
[10] Evarist Giné, Vladimir Koltchinskii, et al. Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results. In High dimensional probability, pages 238–259. Institute of Mathematical Statistics,
2006.
[11] Matthias Hein. Uniform convergence of adaptive graph-based regularization. In Learning Theory, pages 50–64.
Springer, 2006.
[12] Matthias Hein, Jean-Yves Audibert, and Ulrike Von Luxburg. From graphs to manifolds–weak and strong
pointwise consistency of graph Laplacians. In Learning theory, pages 470–485. Springer, 2005.
[13] Stéphane Lafon. Diffusion maps and geometric harmonics. PhD thesis, Yale University, 2004.
[14] Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. Community structure in large
networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math., 6(1):29–123, 2009.

MODEL-FREE CONSISTENCY OF GRAPH PARTITIONING

33

[15] László Lovász. Very large graphs. In Current developments in mathematics, 2008, pages 67–128. Int. Press,
Somerville, MA, 2009.
[16] László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical
Society, Providence, 2012.
[17] László Lovász and Balázs Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B, 96(6):933–957,
2006.
[18] László Lovász and Balázs Szegedy. Szemerédi’s lemma for the analyst. Geom. Funct. Anal., 17(1):252–270, 2007.
[19] Walter Rudin. Real and complex analysis. McGraw-Hill Book Co., New York, third edition, 1987.
[20] Lex Schrijver. On the graphon space. Preprint, available at http://homepages.cwi.nl/∼lex/files/one a.pdf.
[21] Balázs Szegedy. Limits of kernel operators and the spectral regularity lemma. European J. Combin., 32(7):1156–
1167, 2011.
[22] Ulrike von Luxburg. A tutorial on spectral clustering. Stat. Comput., 17(4):395–416, 2007.
[23] Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. Ann. Statist.,
36(2):555–586, 2008.
[24] Ulrike Von Luxburg, Olivier Bousquet, and Mikhail Belkin. On the convergence of spectral clustering on random
samples: the normalized case. In Learning Theory, pages 457–471. Springer, 2004.
1

Statistical and Applied Mathematical Sciences Institute, Research Triangle Park, NC, USA;
email: peter.z.diao@gmail.com (P. Diao)
2
Department of Mathematical Sciences, University of Delaware, Newark, DE, USA;
email: dguillot@udel.edu
3

Departments of Mathematics and Statistics, Stanford University, Stanford, CA, USA; email:
khare@stanford.edu (A. Khare), brajaratnam01@gmail.com (B. Rajaratnam)

