# consistency_of_cheeger_and_ratio_graph_cuts__5e10cdc9.pdf

Journal of Machine Learning Research 17 (2016) 1-46 Submitted 11/14; Revised 2/16; Published 10/16

Consistency of Cheeger and Ratio Graph Cuts

Nicol as Garc ıa Trillos ngarciat@andrew.cmu.edu Dejan Slepˇcev slepcev@math.cmu.edu Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213, USA

James von Brecht James.von Brecht@csulb.edu Department of Mathematics and Statistics California State University, Long Beach Long Beach, CA 90840, USA

Thomas Laurent Thomas.Laurent@lmu.edu Department of Mathematics Loyola Marymount University 1 LMU Dr Los Angeles, CA 90045, USA

Xavier Bresson xavier.bresson@epfl.ch Institute of Electrical Engineering Swiss Federal Institute of Technology (EPFL) 1015 Lausanne, Switzerland

Editor: Matthias Hein

This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective functionals defined on proximity graphs of the given sample. Our focus is on functionals based on graph cuts like the Cheeger and ratio cuts. We show that minimizers of these cuts converge as the sample size increases to a minimizer of a corresponding continuum cut (which partitions the ground truth measure). Moreover, we obtain sharp conditions on how the connectivity radius can be scaled with respect to the number of sample points for the consistency to hold. We provide results for two-way and for multiway cuts. Furthermore we provide numerical experiments that illustrate the results and explore the optimality of scaling in dimension two.

Keywords: data clustering, balanced cut, consistency, graph partitioning

1. Introduction

Partitioning data clouds in meaningful clusters is one of the fundamental tasks in data analysis and machine learning. A large class of the approaches, relevant to high-dimensional data, relies on creating a graph out of the data cloud by connecting nearby points. This allows one to leverage the geometry of the data set and obtain high quality clustering. Many of the graph-clustering approaches are based on optimizing an objective function

c 2016 Nicol as Garc ıa Trillos, Dejan Slepˇcev, James von Brecht, Thomas Laurent, and Xavier Bresson.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

which measures the quality of the partition. The basic desire to obtain clusters which are well separated leads to the introduction of objective functionals which penalize the size of cuts between clusters. The desire to have clusters of meaningful size and for the approaches to be robust to outliers lead to the introduction of balance terms and objective functionals such as Cheeger cut and closely related edge expansion (Arora et al., 2009; Bresson and Laurent, 2012; Bresson et al., 2012; Kannan et al., 2004; Szlam and Bresson, 2010), ratio cut (Hagen and Kahng, 1992; Hein and Setzer, 2011; von Luxburg, 2007; Wei and Cheng, 1989), normalized cut (Arias-Castro et al., 2012; Shi and Malik, 2000; von Luxburg, 2007), and conductance (sparsest cut) (Arora et al., 2009; Kannan et al., 2004; Spielman and Teng, 2004). Such functionals have been extended by Bresson et al. (2013); Yu and Shi (2003) to treat multiclass partitioning. The balanced cuts above have been widely studied theoretically and used computationally. The algorithms of Andersen et al. (2006); Spielman and Teng (2004, 2013) use local clustering algorithms to compute balanced cuts of large graphs. Total variation based algorithms (Bresson et al., 2012, 2013; Hein and B uhler, 2010; Hein and Setzer, 2011; Szlam and Bresson, 2010) are also used to optimize either the conductance or the edge expansion of a graph. Closely related are the spectral approaches to clustering (Shi and Malik, 2000; von Luxburg, 2007) which can be seen as a relaxation of the normalized cuts.

In this paper we consider data clouds, Xn = {x1, . . . , xn}, which have been obtained as i.i.d. samples of a measure ν with density ρ on a bounded domain D. The measure ν represents the ground truth that Xn is a sample of. In the large sample limit, n , clustering methods should exhibit consistency. That is, the clustering of the data Xn should converge as n toward a specific clustering of the underlying ground-truth domain. In this paper we characterize in a precise manner when and how the minimizers of a ratio, Cheeger, sparsest, and normalized graph cuts, converge towards a suitable partition of the domain. We define the discrete and continuum objective functionals considered in Subsections 1.1 and 1.2 respectively, and informally state our result in Subsection 1.3. An important consideration when investigating consistency of algorithms is how graphs on Xn are constructed. In simple terms, when building a graph on Xn one sets a length scale εn such that edges between vertices in Xn are given significant weights if the distance of points they connect is εn or less. In some way this sets the length scale over which the geometric information is averaged when setting up the graph. Taking smaller εn is desirable because it is computationally less expensive and gives better resolution, but there is a price. Taking εn small increases the error due to randomness and in fact, if εn is too small, the resulting graph may not represent the geometry of D well, and consequently the discrete graph cut may be very far from the desired one. In our work we determine precisely how small εn can be taken for the consistency to hold. We obtain consistency results both for two-way and multi-way cuts. To prove our results we use the variational notion of convergence known as the Γconvergence. It is one of the standard tools of modern applied analysis that allows one to consider a limit of a family of variational problems (Braides, 2002; Dal Maso, 1993). In the recent work of Garc ıa Trillos and Slepˇcev (2016), this notion was developed in the random discrete setting designed for the study of consistency of minimization problems on random point clouds. In particular the proof of Γ-convergence of total variation on graphs proved there, provides the technical backbone of this paper. The approach we take is general and

Consistency of Cheeger and Ratio Graph Cuts

flexible and we believe suitable for the study of many problems involving large sample limits of minimization problems on graphs.

Background on consistency of clustering algorithms and related problems. Consistency of clustering algorithms has been considered for a number of approaches. Pollard (1981) has proved the consistency of k-means clustering. Consistency of k-means clustering for paths with regularization was recently studied by Thorpe et al. (2015), using a similar viewpoint to those of this paper. Consistency for a class of single linkage clustering algorithms was shown by Hartigan (1981). Arias-Castro and Pelletier (2013) have proved the consistency of low-dimensional embeddings via the maximum variance unfolding. Consistency of spectral clustering was rigorously considered by von Luxburg, Belkin, and Bousquet (2004, 2008). These works show the convergence of all eigenfunctions of the graph Laplacian for fixed length scale εn = ε which results in the limiting (as n ) continuum problem being a nonlocal one. Belkin and Niyogi (2006) consider the spectral problem (Laplacian eigenmaps) and show that there exists a sequence εn 0 such that in the limit the (manifold) Laplacian is recovered, however no rate at which εn can go to zero is provided. Consistency of normalized cuts was considered by Arias-Castro, Pelletier, and Pudlo (2012) who provide a rate on εn 0 under which the minimizers of the discrete cut functionals minimized over a specific family of subsets of Xn converge to the continuum Cheeger set. Our work improves on (Arias-Castro et al., 2012) in several ways. We minimize the discrete functionals over all discrete partitions on Xn as it is considered in practice and prove the result for the optimal, in terms of scaling, range of rates at which εn can go to zero as n for consistency to hold. There are also a number of works which investigate how well the discrete functionals approximate the continuum ones for a particular function. Among them are works by Belkin and Niyogi (2008), Gin e and Koltchinskii (2006), Hein, Audibert, and Von Luxburg (2005), Narayanan, Belkin, and Niyogi (2006), Singer (2006) and Ting, Huang, and Jordan (2010). Maier, von Luxburg, and Hein (2013) considered pointwise convergence for Cheeger and normalized cuts, both for the geometric and k NN graphs and obtained a range of scalings of graph construction on n for the convergence to hold. While these results are quite valuable, we point out that they do not imply that the minimizers of discrete objective functionals are close to minimizers of continuum functionals.

A notion of convergence suitable for showing the convergence of minimizers of approximating objective functionals converge towards a minimizer of the limit functional is the notion of Γ-convergence, which was introduced by De Giorgi in the 70 s and represents a standard notion of variational convergence. For detailed exposition of the properties of Γconvergence see the books by Braides (2002) and Dal Maso (1993). Particularly relevant to our investigation are works considering nonlocal functionals converging to the perimeter or to total variation which include works by Alberti and Bellettini (1998), Savin and Valdinoci (2012), and Esedo glu and Otto (2015). Also related are works of Ponce (2004), who showed the Γ-convergence of nonlocal functionals related to characterization of Sobolev spaces and of Gobbino (1998) and Gobbino and Mora (2001) who investigated nonlocal approximations of the Mumford-Shah functional. In the discrete deterministic setting, works related to the Γ-convergence of functionals to continuous functionals involving perimeter include works of

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Braides and Yip (2012), Chambolle, Giacomini, and Lussardi (2010), and van Gennip and Bertozzi (2012).

1.1 Graph partitioning

The balanced cut objective functionals we consider are relevant to general graphs (not just the ones obtained from point clouds). We introduce them here. Given a weighted graph G = (X, W) with vertex set X = {x1, . . . , xn} and weight matrix W = {wij}1 i,j n, the balanced graph cut problems we consider take the form

Minimize Cut(Y, Y c)

Bal(Y, Y c) :=

P xi Y P xj Y c wij Bal(Y, Y c) over all nonempty Y X. (1.1)

That is, we consider the class of problems with Cut(Y, Y c) as the numerator together with different balance terms. For Y X let |Y | be the ratio between the number of vertices in Y and the number of vertices in X, that is |Y | = Y

n . Well-known balance terms include

Bal R(Y, Y c) = 2|Y ||Y c| and Bal C(Y, Y c) = min(|Y |, |Y c|), (1.2)

which correspond to ratio cut (Hagen and Kahng, 1992; Hein and Setzer, 2011; von Luxburg, 2007; Wei and Cheng, 1989) and Cheeger cut (Arora et al., 2009; Cheeger, 1970; Chung, 1997; Kannan et al., 2004) respectively1, as well as

Bal S(Y, Y c) = 2deg(Y ) deg(Y c)

deg(X)2 and Bal N(Y, Y c) = min(deg(Y ), deg(Y c))

deg(X) , (1.3)

where deg(Y ) = Pn i=1 Pn j =i wij is the sum of weighted degrees of all vertices in Y , which correspond to sparsest cut (Arora et al., 2009; Kannan et al., 2004; Spielman and Teng, 2004) and normalized cut (Arias-Castro et al., 2012; Shi and Malik, 2000; von Luxburg, 2007) respectively. We refer to a pair {Y, Y c} that solves (1.1) as an optimal balanced cut of the graph. Note that a given graph G = (X, W) may have several optimal balanced cuts (although one expects that generically the optimal cut is unique, since a small perturbation of the weights of a graph with a non-unique minimal balanced cut, is almost sure to lead to only one of them having the least energy ). We are also interested in multi-class balanced cuts. Specifically, in order to partition the set X into R 3 clusters, we consider the following ratio cut functional:

Minimize (Y1,...,YR)

Cut(Yr, Y c r ) |Yr| , Yr Ys = if r = s,

r=1 Yr = X. (1.4)

1.2 Continuum partitioning

Given a bounded and connected open domain D Rd and a probability measure ν on D, with positive density ρ > 0, we define the class of balanced domain cut problems in an analogous way. A balanced domain-cut problem takes the form

Minimize Cutρ(A, Ac)

Balρ(A, Ac) , A D with 0 < ν(A) < 1. (1.5)

1. The factor of 2 in the definition of Bal R(Y, Y c) is introduced to simplify the computations in the remainder. We remark that when using Bal R, problem (1.1) is equivalent to the usual ratio cut problem.

Consistency of Cheeger and Ratio Graph Cuts

where Ac = D\A. Just as the graph cut term Cut(Y, Y c) in (1.1) provides a weighted (by W) measure of the boundary between Y and Y c, the cut term Cutρ(A, Ac) for a domain denotes a ρ2 weighted area of the boundary between the sets A and Ac. Assuming that DA := A D (the boundary between A and Ac) is a smooth curve (in 2d), surface (in 3d) or manifold (in 4d+), we can define

Cutρ(A, Ac) := ˆ

DA ρ2(x) d S(x). (1.6)

We only consider cuts with weight ρ2, since they appear as the limit of the discrete cuts we consider in this paper, as indicated in subsection 1.3. For our results and analysis we need the notion of continuum cut which is defined for sets with less regular boundary. We present the required notions of geometric measure theory and the rigorous and mathematically precise formulation of problem (1.5) in Subsection 3.1. If ρ(x) = 1 then Cutρ(A, Ac) simply corresponds to arc-length (in 2d) or surface area (in 3d). In the general case, the presence of ρ2(x) in (1.6) indicates that the regions of low density are easier to cut, so DA has a tendency to pass through regions in D of low density. As in the graph case, we consider balance terms

Balρ(A, Ac) = 2|A||Ac| and Balρ(A, Ac) = min(|A|, |Ac|), (1.7)

which correspond to weighted continuous equivalents of the ratio cut and the Cheeger cut. In the continuum setting |A| stands for the total ν-content of the set A, that is,

|A| = ν(A) = ˆ

A ρ(x) dx. (1.8)

We also consider balance terms

Balρ(A, Ac) = 2|A|ρ2|Ac|ρ2 and Balρ(A, Ac) = min(|A|ρ2, |Ac|ρ2), (1.9)

which correspond to weighted continuous equivalents of the sparsest cut and the normalized cut. Here |A|ρ2 stands for

A ρ2(x) dx. (1.10)

We refer to a pair {A, Ac} that solves (1.5) as an optimal balanced cut of the domain.

The continuum equivalent of the multiway cut problem (1.4) reads

Minimize (A1,...,AR)

Cutρ(Ar, Ac r) |Ar| , (1.11)

where (A1, . . . , AR) is an R-tuple of measurable subsets of D such that ν(Ar As) = 0 if r = s, and ν D \ SR r=1 Ar = 0.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

1.3 Consistency of partitioning of data clouds

Let x1, . . . , xn, . . . be a sequence of i.i.d random points drawn from an underlying groundtruth measure ν. Throughout the paper ν is a probability measure supported on a bounded, open set with Lipschitz boundary D. Furthermore we assume that ν has continuous density ρ : D R and that 0 < λ ρ Λ on D; in other words, ρ is bounded below and above by positive constants. We denote by Xn = {x1, . . . , xn}, the set consisting of the first n data points. To extract the desired information from the point cloud Xn, one builds a graph by connecting nearby points. More precisely, let η : Rd [0, ) be a radially symmetric kernel, radially decreasing, and decaying to zero sufficiently fast. We introduce a parameter ε which basically describes over which length scale the data points are connected. For i, j {1, . . . , n}, we consider the weight

wij = η xi xj

As more data points are available one takes smaller ε to obtain increased resolution. That is, one sets the length scale ε based on the number of available data points: ε = εn. We investigate under what scaling of εn on n the optimal balanced cuts (that is, minimizers of (1.1)) of the graph Gn = (Xn, Wn) converge towards optimal balanced cuts in the continuum setting (minimizers of (1.5)). On Figure 1, we illustrate the partitioning of a data cloud sampled from the uniform distribution on the given domain D.

Informal statement of (a part of) the main results. Consider d 2 and assume the continuum balanced cut (1.5) has a unique minimizer {A, Ac}. Consider εn > 0 such that limn εn = 0 and

lim n (log n)pd

n1/d 1 εn = 0, (1.13)

where pd = 1/d for d 3 and p2 = 3/4. Then almost surely the minimizers, {Yn, Y c n}, of the balanced cut (1.1) of the graph Gn , converge to {A, Ac}. Moreover, after appropriate rescaling, almost surely the minimum of problem (1.1) converges to the minimum of (1.5). The result also holds for multiway cuts. That is, the minimizers of (1.4) converge towards minimizers of (1.11).

Let us make the notion of convergence of discrete partitions {Yn, Y c n} to continuum partitions {A, Ac} precise. To be able to easily account for the invariance {Yn, Y c n} = {Y c n, Yn}, let Yn,1 = Yn and Yn,2 = Y c n. Let 1Yn,i : Xn {0, 1} for i = 1, 2 be the characteristic function of Yn,i (on the set Xn). We say that {Yn, Y c n} converge towards {A, Ac} as n if there is a sequence of indices I : N {1, 2} such that

i=1 1Yn,I(n)(xi)δxi w 1A ν (1.14)

where w denotes the weak convergence of measures (see Dudley (2002)). Since by assumption on the points xi it holds that 1

n Pn i=1 δxi w ν, the property (1.14) is equivalent

Consistency of Cheeger and Ratio Graph Cuts

(a) A sample of n = 120 points. (b) Geometric graph with ε = 0.3.

(c) Minimizer of Cheeger graph cut. (d) Minimizer of continuum Cheeger cut.

Figure 1: Given the sample of Figure (a), graph is constructed using η(z) = 1{|z| 1} and ε = 0.3, as illustrated on Figure (b). On Figure (c) we present the solution to the Cheeger graph-cut problem obtained using algorithm of Bresson et al. (2012). A solution to the continuum Cheeger-cut problem is illustrated in Figure (d).

i=1 1Yn,3 I(n)(xi)δxi w 1Ac ν

In Section 2 we discuss this topology in more detail and present a conceptually clearer framework, which applies to general functions (not just characteristic functions of sets). Let us also indicate briefly why the weight ρ2 present in the weighted perimeter (1.6) can be expected to appear in the limit of balanced graph cuts (1.1). Let νn = 1

n Pn i=1 δxi be the empirical measure of the sample Xn = {x1, . . . , xn}. Let A D be a set with smooth boundary and let An = A Xn. Then, using ηε(z) = η(z/ε)/εd we get

1 n2εd Cut(An, Ac n) = 1

1 εd η xi xj

D 1An(x)1Acn(y)ηε (x y) dνn(x)dνn(y)

D 1A(x)1Ac(y)ηε (x y) ρ(x)ρ(y)dydx

D A ρ2(x) d S(x).

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

The factor 1/(n2εd) in front of the cut above is accounted for in the way we scale the cuts, see (5.6). We remark that the above just provides a rough heuristic idea as to what weight should be expected. It does not serve as a basis for our proof, since the optimal balanced graph cuts {Yn, Y c n} (minimizer of (1.1)) could be rather different from {A Xn, Ac Xn} where {A, Ac} is the optimal balanced domain cut (minimizer of (1.5)). The reason for the presence of ρ in (1.8) is clear since the particles are drawn from the measure, ν, with density ρ, and thus the empirical measures of the sample, νn, converge to ν. Let us now indicate the reason for the presence of ρ2 in (1.10). Namely for the graph weights given by (1.12) and A, Xn, and An as above

1 n2εd deg(An) = 1

1 εd η xi xj

D 1An(x)ηε (x y) dνn(x)dνn(y)

D 1A(x)ηε (x y) ρ(x)ρ(y)dydx

D 1A(x)ρ2(x)dx.

Therefore, deg(An) deg(Xn) 1

D 1A(x)ρ2(x)dx = |A|ρ2.

Since the proofs are analogous in most of the paper, we only consider the ratio and Cheeger cuts in detail and only comment briefly on sparsest and normalized cuts.

Remark 1 (Optimality of scaling of εn for d 3) If d 3 then the rate presented in (1.13) is sharp in terms of scaling. Namely for D = (0, 1)d, and ν the Lebesgue measure on D and η compactly supported, it is known from graph theory (see (Goel et al., 2004; Gupta and Kumar, 1999; Penrose, 1999)) that there exists a constant c > 0 such that if

εn < c(log n)1/d

n1/d then the weighted graph associated to (Xn, Wn) is disconnected with high probability. The resulting optimal discrete cuts have zero energy, but may be very far from the optimal continuum cuts.

While the above example demonstrates the optimality of our results, we remark that the convergence fails because the lack of connectedness of random geometric graphs (with connectivity radius below the before mentioned threshold) leads to undesirable partitions. Considering different objective functionals which are still based on perimeter, but more strongly penalize existence of small connected components, or considering different graph constructions (for example by restricting attention to the giant component) could lead to convergence even for some scaling εn below the connectivity threshold 1 n1/d εn <

c(log n)1/d

Remark 2 In case d = 2 the connectivity threshold for a random geometric graph is εn = clog(n)1/2

n1/2 , which is below the rate for which we can establish the consistency of balanced cuts. Thus, an interesting open problem is to determine if the consistency results we present in

Consistency of Cheeger and Ratio Graph Cuts

this paper are still valid when the parameter εn is taken below the rate log(n)3/4

n1/2 we obtained the proof for, but above the connectivity rate. In particular we are interested in determining if connectivity is the determining factor in order to obtain consistency of balance graph cuts. We numerically explore this problem in Section 8.

1.4 Outline

In Section 2 we introduce the notion of convergence we use to bridge between discrete and continuum partitions. In particular this notion of convergence allows us to consider the discrete and continuum objective functionals in a common metric space, which we denote by TL1. This notion of convergence relies on some of the notions of the theory of optimal transportation which we recall. We also recall results on optimal min-max matching between the random sample and the underlying measure (Proposition 5), which are needed in the proof of the convergence. They represent the main estimates which account for randomness. The rest of the arguments in the paper are not probabilistic. In Section 3 we study more carefully the notion of continuum partitioning (1.5). We introduce the notion of total variation of functions on D in Subsection 3.1 and recall some of its basic properties. This enables us to introduce, in Subsection 3.2, the general setting for problem (1.5) where desirable properties such as lower semicontinuity and existence of minimizers hold. In Section 4 we give the precise statement of the consistency result, both for the two-way cuts (Theorem 9) and the multi-way cuts (Theorem 12). Proving that minimizers of discrete balanced cuts converge to optimal continuum balanced cuts is reduced to proving that the discrete balanced-cut objective functionals converge (in the sense of the notion of variational convergence known as Γ-convergence) to continuum balanced-cut objective functionals. In Section 5 we recall the definition of Γ-convergence and its basic properties. In Subsection 5.1 we recall the results on Γ-convergence of graph total variation which provide the backbone for our results. Section 6 contains the proof of the Theorem 9 and Section 7 the proof of Theorem 12. Finally, in Section 8 we present numerical experiments which illustrate our results; we also investigate the issues related to Remark 2.

2. From Discrete to Continuum

Let x1, . . . , xn, . . . be a sequence of i.i.d random points drawn from an underlying groundtruth measure ν. For the two-class case, our main result shows that a sequence of partitions {Yn, Y c n} of the point clouds Xn = {x1, . . . , xn} D converges toward a continuum partition {A, Ac} of the domain D. In this section we expand on the notion of convergence introduced in Subsection 1.3 to compare the discrete and continuum partitions. We give an equivalent definition for such type of convergence which turns out to be more useful for the computations in the remainder. Associated to the partitions {Yn, Y c n} are the characteristic functions of Yn and Y c n, namely 1Yn : Xn {0, 1} and 1Y c n : Xn {0, 1}. Let νn = 1

n Pn i=1 δxi be the empirical measures associated to Xn Note that 1Yn, 1Y c n L1(νn). Likewise a continuum partition of D by measurable sets A and Ac = D\A can be described via the characteristic functions 1A : D {0, 1} and 1Ac : D {0, 1}. These too can be considered as L1 functions, but with respect to the measure ν rather than νn.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

We compare the partitions {Yn, Y c n} and {A, Ac} by comparing the associated characteristic functions. To do so, we need a way of comparing L1 functions with respect to different measures. We follow the approach of Garc ıa Trillos and Slepˇcev (2016). We denote by B(D) the Borel σ-algebra on D and by P(D) the set of Borel probability measures on D. The set of objects of our interest is

TL1(D) := {(µ, f) : µ P(D), f L1(µ)}.

Note that (νn, 1Yn) and (ν, 1A) both belong to TL1. To compare functions defined with respect to different measures, say (µ, f) and (θ, g) in TL1, we need a way to say for which (x, y) supp(µ) supp(θ) should we compare f(x) and g(y). The notion of coupling (or transportation plan) between µ and θ, provides a way to do that. A coupling between µ, θ P(D) is a probability measure π on the product space D D, such that the marginal on the first variable is µ and the marginal on the second variable is θ. The set of couplings Γ(µ, θ) is thus

Γ(µ, θ) = {π P(D D) : ( U B(D)) π(U D) = µ(U) and π(D U) = θ(U)}.

For (µ, f) and (θ, g) in TL1(D) we define the distance

d TL1((µ, f), (θ, g)) = inf π Γ(µ,θ)

D D |x y| + |f(x) g(y)|dπ(x, y). (2.1)

This is the distance that we use to compare L1 functions with respect to different measures. It is motivated by optimal transportation distances (such as the Wasserstein distance and the earth-mover distance, see (Garc ıa Trillos and Slepˇcev, 2016, 2015; Villani, 2003) and references therein). Indeed, the distance (2.1) can be seen as an optimal transportation distance between measures supported on the graphs of the functions f and g, as discussed in Garc ıa Trillos and Slepˇcev (2016). To better understand it here, we focus on the case that one of the measures, say µ, is absolutely continuous with respect to the Lebesgue measure, as this case is relevant for us when passing from discrete to continuum. In this case, the convergence in TL1 space can be formulated in simpler ways using transportation maps instead of couplings to match the measures. Given a Borel map T : D D and µ P(D), the push-forward of µ by T, denoted by T µ P(D) is given by:

T µ(A) := µ T 1(A) , A B(D).

A Borel map T : D D is a transportation map between the measures µ P(D) and θ P(D) if θ = T µ. Associated to a transportation map T, there is a plan πT Γ(µ, θ) given by πT := (Id T) µ, where (Id T)(x) = (x, T(x)). We note that if θ = T µ, then the following change of variables formula holds for any f L1(θ) ˆ

D f(y)dθ(y) = ˆ

D f(T(x))dµ(x). (2.2)

In order to give the desired interpretation of convergence in TL1 we also need the notion of a stagnating sequence of transportation maps. Given µn P(D), for n = 1, . . .

Consistency of Cheeger and Ratio Graph Cuts

and µ P(D), a sequence {Tn}n N of transportation maps between µ and µn (meaning that Tn µ = µn) is stagnating if ˆ

D |x Tn(x)|dµ(x) 0 as n . (2.3)

This notion is relevant to our considerations because for the measure ν and its empirical measures νn there exists (with probability one) a sequence of stagnating transportation maps Tn ν = νn. The idea is that as n the mass from ν needs to be moved only very little to be matched with the mass of νn. We make this precise in Proposition 5 We now provide the desired interpretation of the convergence in TL1, which is a part of Proposition 3.12 of Garc ıa Trillos and Slepˇcev (2016).

Proposition 3 Consider a measure µ P(D) which is absolutely continuous with respect to the Lebesgue measure. Let (µ, f) TL1(D) and let {(µn, fn)}n N be a sequence in TL1(D). The following statements are equivalent:

(i) (µn, fn) TL1 (µ, f) as n . (ii) µn w µ and there exists a stagnating sequence of transportation maps Tn µ = µn such that: ˆ

D |f(x) fn (Tn(x))| dµ(x) 0, as n . (2.4)

(iii) µn w µ and for any stagnating sequence of transportation maps Tn µ = µn convergence (2.4) holds.

The previous proposition implies that in order to show that (µn, fn) converges to (µ, f) in the TL1-sense, it is enough to find a sequence of stagnating transportation maps Tn µ = µn and then show the L1 convergence of fn Tn to f in L1(µ) . An important feature of Proposition 3 is that there is complete freedom on what sequence of transportation maps {Tn}n N to take, as long as it is stagnating. In particular this shows that if µn = µ for all n then the convergence in TL1 is equivalent to convergence in L1(µ) .

Remark 4 Suppose that the sequence of probability measures {µn}n N is such that µn w µ.

Let fn L1(µn) and let f L1(µ). With a slight abuse of notation we say that fn TL1 f

whenever (µn, fn) TL1 (µ, f). In particular when we write fn TL1 f it should be clear what the corresponding measures µn, µ are.

To obtain the scaling of (1.13) we need a stagnating sequence of transportation maps between ν and {νn}n N with precise information on the rate at which convergence (2.3) occurs. More precisely for some of our considerations we need the control of Tn(x) x in the stronger L (ν)-norm, rather than in the L1(ν)-norm. Since the typical distance between nearby points is of order n 1/d the typical transportation distance, Tn(x) x, must be at least of that order. The optimal upper bound on the L (ν)-norm of Tn I however has an extra logarithmic correction. In particular in Garc ıa Trillos and Slepˇcev (2015) it was shown that:

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Proposition 5 Let D be an open, connected and bounded subset of Rd which has Lipschitz boundary. Let ν be a probability measure on D with density ρ which is bounded from below and from above by positive constants. Let x1, . . . , xn, . . . be a sequence of independent random points distributed on D according to measure ν and let νn = 1 n Pn i=1 δxi. Then there is a constant C > 0 (that depends on D and ρ) such that with probability one there exists a sequence of transportation maps {Tn}n N from ν to νn (Tn ν = νn) and such that:

n1/d Id Tn L (ν)

(log n)pd C, (2.5)

where the power pd is equal to 1/d if d 3 and equal to 3/4 if d = 2.

The optimality of the upper bound is discussed in Garc ıa Trillos and Slepˇcev (2015). If d 3 it follows from the fact that for n large, with large probability there exists a ball of radius comparable to ((ln n)/n)1/d which contains none of the points x1, . . . , xn.

Having defined the TL1-convergence for functions, we turn to the TL1-convergence for partitions. When defining a notion of convergence for sequences of partitions {Y n 1 , . . . , Y n R }, we need to address the inherent ambiguity that arises from the fact that both {Y n 1 , . . . , Y n R } and {Y n P(1), . . . , Y n P(R)} refer to the same partition for any permutation P of {1, . . . , R}. Having the previous observation in mind, the convergence of partitions is defined in a natural way.

Definition 6 The sequence {Y n 1 , . . . , Y n R }n N, where {Y n 1 , . . . , Y n R } is a partition of Xn, converges in the TL1-sense to the partition {A1, . . . , AR} of D, if there exists a sequence of permutations {Pn}n N of the set {1, . . . , R}, such that for every r {1, . . . , R},

νn, 1Y n Pn(r)

TL1 (ν, 1Ar) as n .

We note that the definition above is equivalent to

i=1 1Y n Pn(r)(xi)δxi w 1Ar ν (2.6)

for all r = 1, . . . , R which is analogous to the definition in (1.14) which we gave in Subsection (1.3) when discussing the main result. The equivalence follows from the fact that the TL1

metric (2.1) can be seen as the distance between the graphs of functions, considered as measures. Namely given (µ, f), (θ, g) TL1(D), let Γf = (Id f) µ and Γg = (Id g) θ be the measures representing the graphs. Consider d(Γf, Γg) := d TL1((µ, f), (θ, g). Proposition 3.3 in Garc ıa Trillos and Slepˇcev (2016) (also see the paragraph right after Remark 3.1) implies that this distance metrizes the weak convergence of measures on the family of graph measures. Therefore the convergence of partitions of Definition 6 is equivalent to one given in (2.6).

We end this section by making some remarks about why the TL1-metric is a suitable metric for considering consistency problems. On one hand if one considers a sequence of minimizers {Yn, Y c n} of the graph balanced cut (1.1) the topology needs to be weak enough

Consistency of Cheeger and Ratio Graph Cuts

for the sequence of minimizers to be guaranteed to converge (at least along a subsequence). Mathematically speaking the topology needs to be weak enough for the sequence to be pre-compact. On the other hand the topology has to be strong enough for one to be able to conclude that the limit of a sequence of minimizes is a minimizer of the continuum balanced cut energy. In Proposition 21 and Lemma 23 we establish that the TL1-metric satisfies both of the desired properties. Finally we point out that our approach from discrete to continuum can be interpreted as an extrapolation or extension approach, as opposed to restriction viewpoint. Namely when comparing (µn, fn) and (µ, f) where µn is discrete and µ is absolutely continuous with respect to the Lebesgue measure we end up comparing two L1 functions with respect to the Lebesgue measure, namely fn Tn and f, in (2.4). Therefore fn Tn used in Proposition 3 can be seen as a continuum representative (extrapolation) of the discrete fn. We think that this approach is more flexible and suitable for the task than the, perhaps more common, approach of comparing the discrete and continuum by restricting the continuum object to the discrete setting (this would correspond to considering f|supp(µn) and comparing it to fn).

3. Continuum partitioning: rigorous setting

We first recall the general notion of (weighted) total variation and some notions of analysis and geometric measure theory.

3.1 Total Variation

Let D be an open and bounded domain in Rd with Lipschitz boundary and let ρ : D (0, ) be a continuous density function. We let ν be the measure with density ρ. We assume that ρ is bounded above and below by positive constants, that is, λ ρ Λ on D for some Λ λ > 0. Given a function u L1(ν), we define the weighted (by weight ρ2) total variation of u by:

TV (u; ν) := sup ˆ

D u(x)div(Φ(x)) dx : Φ(x) C1 c (D : Rd), |Φ(x)| ρ2(x) , (3.1)

where in the above C1 c (D : Rd) denotes the set of C1-functions from D to Rd, whose support is compactly contained in D. If u is regular enough then the weighted total variation can be written as TV (u; ν) = ˆ

D | u|ρ2(x) dx. (3.2)

Also, given that ρ : D R is continuous, if u = 1A is the characteristic function of a set A Rd with C1 boundary, then

TV (1A; ν) = ˆ

A D ρ2(x) d Hd 1(x), (3.3)

where Hd 1 represents the (d 1)-dimensional Hausdorffmeasure in Rd. In case ρ is a constant (ν is the uniform distribution), the functional TV ( ; ν) reduces to a multiple of

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

the classical total variation and in particular (3.3) reduces to a multiple of the surface area of the portion of A contained in D. Since ρ is bounded above and below by positive constants, a function u L1(ν) has finite weighted total variation if and only if it has finite classical total variation. Therefore, if u L1(ν) with TV (u; ν) < , then u is a BV function and hence it has a distributional derivative Du which is a Radon measure (see Chapter 13 of Leoni (2009)). We denote by |Du| the total variation of the measure Du and denote by |Du|ρ2 the measure determined by d|Du|ρ2 = ρ2(x)d|Du|. (3.4)

By Theorem 4.1 of Baldi (2001)

TV (u; ν) = |Du|ρ2(D) = ˆ

D ρ2(x) d|Du|(x). (3.5)

A simple consequence of the definition of the weighted TV is its lower semicontinuity

with respect to L1-convergence. More precisely, if uk L1(ν) u then

TV (u; ν) lim inf k TV (uk; ν). (3.6)

Finally, for u BV (D), the co-area formula

TV (u; ν) = ˆ

R TV (1{u>t}; ν) dt,

relates the weighted total variation of u with the weighted total variation of its level sets. A proof of this formula can be found in Bellettini, Bouchitt e, and Fragal a (1999). For a proof of the formula in the case that ρ is constant see Leoni (2009). In the remainder of the paper, we write TV (u) instead of TV (u; ν) when the context is clear.

3.2 Continuum partitioning

We use the total variation to rigorously formulate the continuum partitioning problem (1.5). The precise definition of the Cutρ(A, Ac) functional in (1.5) is

Cutρ(A, Ac) = TV (1A; ν),

where TV (1A; ν) is defined in (3.1). We note that TV (1A; ν) is equal to TV (1Ac; ν), and is the perimeter of the set A in D weighted by ρ2. Recall that |D| = ν(D), as defined in (1.8). Given that ν is a probability measure supported on D we have |D| = 1. We now formulate the balance terms defined by (1.7) and (1.8) using characteristic functions. We start by extending the balance term to arbitrary functions u L1(ν):

D |u(x) meanρ(u)|ρ(x) dx and BC(u) = min c R

D |u(x) c|ρ(x) dx, (3.7)

Consistency of Cheeger and Ratio Graph Cuts

where meanρ(u) denotes the mean/expectation of u(x) with respect to the measure dν = ρdx. Analogously, using the symbol

D f(x)ρ2(x)dx := 1

D f(x)ρ2(x)dx, we define

D |u(x) meanρ2(u)|ρ2(x) dx and BN(u) = min c R ˆ

D |u(x) c|ρ2(x) dx, (3.8)

where mean2 ρ(u) =

D u(x)ρ2(x)dx. We have the desired relation with balance terms defined in (1.2) and (1.3)

BI(1A) = Bal I(A, Ac) for I = R, C, S, and N (3.9)

for every measurable subset A of D. From here on, we use B to represent BR, BC, BS, or BN, depending on the context. We also consider normalized indicator functions 1A given by 1A := 1A B(1A), A D,

and consider the set

Ind(D) := u L1(ν) : u = 1A for some measurable set A D with B(1A) = 0 . (3.10) Then for u = 1A Ind(D)

TV (u) = TV ( 1A) = TV 1A B(1A)

B(1A) = Cutρ(A, Ac)

Bal(A, Ac) . (3.11)

Consequently the problem (1.5) is equivalent to minimizing E : TL1(D) ( , ], given by

( TV (u) if µ = ν and u Ind(D) + otherwise. (3.12)

where µ is a probability measure on D, u L1(µ), TV (u) = TV (u; ν), is given by (3.5) and Ind(D) is defined by (3.10). Since the functional E is only non-trivial when µ = ν, from now on we write E(u) instead of E(ν, u). Before we show that both the continuum ratio cut and Cheeger cut indeed have a minimizer, we need the following lemma:

Lemma 7 (i) The balance functions BI are continuous on L1(ν).

(ii) The set Ind(D) is closed in L1(ν).

Proof Let us start by proving (i). We first consider the balance term BC(u) that corresponds to the Cheeger cut. Let u1, u2 L1(ν). Let ci be the median of ui for i = 1, 2, that is let ci be a minimizer of c 7

D |ui(x) c| ρ(x) dx. Then, by (3.7),

B(u1) B(u2) ˆ |u1 c2|ρ(x) dx ˆ |u2 c2| ρ(x) dx

ˆ |u1 u2|ρ(x) dx = u1 u2 L1(ν).

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Exchanging the role of u1 and u2 in this argument implies that |B(u1) B(u2)| u1 u2 L1(ν), which implies Lipschitz continuity of BC.

Now consider the balance term BR(u) that corresponds to the ratio cut. Let {uk}k=1,... be a sequence in L1(ν) converging to u. The inequality ||a| |b|| |a b| implies that

ˆ |uk meanρ(uk)|ρ(x) dx ˆ |u meanρ(u)|ρ(x) dx

ˆ |uk u|ρ(x) dx + ˆ | meanρ(uk) meanρ(u)|ρ(x) dx

ˆ |uk u|ρ(x) dx + | meanρ(uk) meanρ(u)|.

Since uk u in L1(ν) we have that meanρ(uk) meanρ(u) and therefore |BR(uk) BR(u)| uk u L1(ν) + | meanρ(uk) meanρ(u)| 0 as desired. In order to prove (ii) suppose that {uk}n N is a sequence in Ind(D) converging in L1(ν) to some u L1(ν), we need to show that u Ind(D). By (i) we know that B(uk) B(u) as k . Since uk Ind(D), in particular B(uk) = 1. Thus, B(u) = 1. On the other hand, uk Ind(D) implies that uk has the form uk = αk1Ak. Since this is true for every k, in particular we must have that u has the form u = α1Afor some real number α and some measurable subset A of D. Finally, the fact that B is 1-homogeneous implies that 1 = B(u) = αB(1A). In particular B(1A) = 0 and α = 1 B(1A). Thus u = 1A with B(1A) = 0 and hence u Ind(D).

Lemma 8 Let D and ν be as stated at the beginning of this section. There exists a measurable set A D with 0 < ν(A) < 1 such that 1A minimizes (3.12).

Proof The statement follows by the direct method of the calculus of variations. Since the functional is bounded from below it suffices to show that it is lower semicontinuous with respect to the L1(ν) norm and that a minimizing sequence is precompact in L1(ν). To show lower semi-continuity it is enough to consider a sequence un = 1An Ind(D) converging in L1(ν) to u L1(ν). From Lemma 7 it follows that u Ind(D) and hence u = 1A for some A with B(1A) > 0. Therefore 1An 1A as n in L1(ν). The lower semi-continuity then follows from the lower semi-continuity of the total variation (3.6), the continuity of B and the fact that since B(1A) > 0, 1/B(1An) 1/B(1A) as n . The pre-compactness of any minimizing sequence of (3.12) follows directly from Theorem 5.1 of Baldi (2001), which completes the proof.

4. Assumptions and statements of main results.

Here we present the precise hypotheses we use and state precisely the main results of this paper. Let D be an open, bounded, connected subset of Rd with Lipschitz boundary, and let ρ : D R be a continuous density which is bounded below and above by positive constants, that is, for all x D λ ρ(x) Λ (4.1)

Consistency of Cheeger and Ratio Graph Cuts

for some Λ λ > 0. We let ν be the measure dν = ρdx. Let η : [0, ) [0, ) be the radial profile of the similarity kernel, namely the function satisfying η(x) = η(|x|). We assume

(K1) η(0) > 0 and η is continuous at 0.

(K2) η is non-increasing.

Rd η(|x|)| x, e1 | dx < .

We refer to the quantity ση as the surface tension associated to η. In the above, x, e1 denotes the inner product of the vector x with the vector whose first entry is 1 and whose other entries are equal to zero. We remark that due to radial symmetry, the vector e1 can be replaced by any unit vector in Rd without changing the value of ση. The kernel η : Rd [0, ) is now given by η(x) = η(|x|)). These hypotheses on η hold for the standard similarity functions used in clustering contexts, such as the Gaussian similarity function η(r) = exp( r2) and the proximity similarity kernel (η(r) = 1 if r 1 and η(r) = 0 otherwise). For a sample x1, . . . , xn from the measure ν, we denote by νn the empirical measure associated to the sample. The main result of our paper is:

Theorem 9 (Consistency of cuts) Let domain D, probability measure ν,with density ρ, and kernel η satisfy the conditions above. Let εn denote any sequence of positive numbers converging to zero that satisfy

lim n 0 (log n)3/4

n1/2 1 εn = 0 (d = 2), lim n 0 (log n)1/d

n1/d 1 εn = 0 (d 3).

Let {xj}j N be an i.i.d. sequence of random points in D drawn from the measure ν and let Xn = {x1, . . . , xn}. Let Gn = (Xn, Wn) denote the graph whose edge weights are

wn ij := η |xi xj|

where η satisfies assumptions (K1)-(K3). Finally, let {Y n , Y n c} denote any optimal balanced cut of Gn (solution of problem (1.1)). If problem (3.12) has a unique solution {A , A c}, then with probability one the sequence {Y n , Y n c} converges to {A , A c} in the TL1-sense. If there is more than one optimal continuum balanced cut (3.12) then with probability one, {Y n , Y n c} converges along a subsequence to an optimal continuum balanced cut. Additionally, with probability one, Cn the minimum balanced cut of the graph Gn (the minimum of (1.1)), satisfies

lim n 2Cn n2εd+1 n = σηC, (4.2)

where ση is the surface tension associated to the kernel η and C is the minimum of (1.5).

As the proofs for sparsest and normalized cuts are analogous, in the remainder of the paper we only treat the ratio and Cheeger cuts in detail.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Remark 10 For simplicity of notation, from now on we make the assumption that problem (3.12) has a unique solution {A , A c}. In the general case, Theorem 9 follows using the same approach; the only difference is that the convergence of minimizers happens along subsequences (see Proposition 17 below).

As we discussed in Remark 1 for d 3 the scaling of ε = εn on n is essentially the best possible. The proof of Theorem 9 relies on establishing a variational convergence of discrete balanced cuts to continuum balanced cuts called the Γ-convergence which we recall in Subsection 5. The proof uses the results obtained of Garc ıa Trillos and Slepˇcev (2016), where the notion of Γ-convergence was introduced in the context of objective functionals on random data samples, and in particular the Γ-convergence of the graph total variation is considered. The Γ-convergence, together with a compactness result, provides sufficient conditions for the convergence of minimizers of a given family of functionals to the minimizers of a limiting functional.

Remark 11 A few remarks help clarify the hypotheses and conclusions of our main result. The scaling condition εn (log n)pdn 1/d comes directly from the existence of transportation maps from Proposition 5. This means that εn must decay more slowly than the maximal distance a point in D has to travel to match its corresponding data point in Xn. In other words, the similarity graph Gn must contain information on a larger scale than that on which the intrinsic randomness operates. Lastly, the conclusion of the theorem still holds if the partitions {Y n , Y n c} only approximate an optimal balanced cut, that is if the energies of {Y n , Y n c} satisfy

Cut(Yn , Y n c) Bal(Y n , Y n c) min Y Xn Cut(Y, Y c)

Bal(Y, Y c)

This important property follows from a general result on Γ-convergence which we recall in Proposition 17.

We also establish the following multi-class equivalent to Theorem 9.

Theorem 12 Let domain D, measure ν, kernel η, sequence {εn}n N, sample points {xi}i N, and graph Gn satisfy the assumptions of Theorem 9. Let (Y n 1, . . . , Y n R) denote any optimal balanced cut of Gn, that is a minimizer of (1.4). If (A 1, . . . , A R) is the unique optimal balanced cut of D (that is minimizer of (1.11)) then with probability one the sequence (Y n 1, . . . , Y n R) converges to (A 1, . . . , A R) in the TL1-sense. If the optimal continuum balanced cut is not unique then the convergence to a minimizer holds along subsequences. Additionally, Cn, the minimum of (1.4), satisfies

lim n 2Cn n2εd+1 n = σηC,

where ση is the surface tension associated to the kernel η and C is the minimum of (1.11).

The proof of Theorem 12 involves modifying the geometric measure theoretical results of Garc ıa Trillos and Slepˇcev (2016). This leads to a substantially longer and more technical proof than the proof of Theorem 9, but the overall spirit of the proof remains the same in the sense that the Γ-convergence plays the leading role. Finally, we remark that analogous observations to the ones presented in Remark 11 apply to Theorem 12.

Consistency of Cheeger and Ratio Graph Cuts

5. Background on Γ-convergence

We recall and discuss the notion of Γ-convergence. The usual Γ-convergence is defined for deterministic functionals. It extends to the random functionals that we consider in a natural way. Namely for almost every realization of the random event (in our case a sequence of random points in the domain) we require the Γ-convergence of resulting, deterministic, functionals. Such notion of Γ convergence has been used by Dirr and Orlandi (2009). We now define it precisely. Let (X, d X) be a metric space and let (Ω, F, P) be a probability space. Let Fn : X Ω [0, ] be a sequence of random functionals. For brevity, instead of writing Fn(x, ω) we simply write Fn(x) with understanding that an element ω Ωhas been fixed.

Definition 13 The sequence of random functionals {Fn}n N Γ-converges with respect to metric d X to the deterministic functional F : X [0, ] as n if for P-almost every ω, the following conditions hold simultaneously:

1. Liminf inequality: For every x X and every sequence {xn}n N converging to x,

lim inf n Fn(xn) F(x),

2. Limsup inequality: For every x X there exists a sequence {xn}n N converging to x satisfying lim sup n Fn(xn) F(x).

We say that F is the Γ-limit of the sequence of functionals {Fn}n N (with respect to the metric d X).

Remark 14 In most situations one does not prove the limsup inequality for all x X directly. Instead, one proves the inequality for all x in a dense subset X of X where it is somewhat easier to prove, and then deduce from this that the inequality holds for all x X. To be more precise, suppose that the limsup inequality is true for every x in a subset X

of X and the set X is such that for every x X there exists a sequence {xk}k N in X

converging to x and such that F(xk) F(x) as k , then the limsup inequality is true for every x X. The proof of the claim is straightforward, using, for example Theorem 1.17(iii) of Braides (2002). This property is not related to the randomness of the functionals in any way.

Definition 15 We say that the sequence of nonnegative random functionals {Fn}n N satisfies the compactness property if for P-almost every ω , the following statement holds: any sequence {xn}n N bounded in X and for which

lim sup n Fn(xn) < + ,

is relatively compact in X.

Remark 16 The boundedness assumption of {xn}n N in the previous definition is a necessary condition for relative compactness and so it is not restrictive.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

The notion of Γ-convergence is particularly useful when the functionals {Fn}n N satisfy the compactness property. This is because it guarantees that with P-probability one, minimizers (or approximate minimizers) of Fn converge to minimizers of F and it also guarantees convergence of the minimum energy of Fn to the minimum energy of F (this statement is made precise in the next proposition). This is the reason why Γ-convergence is said to be a variational type of convergence. The next proposition can be found in (Braides, 2002; Dal Maso, 1993) in the deterministic setting . We present its proof in this random setting for completeness and for the benefit of the reader. We also want to highlight the way this type of convergence works as ultimately this is one of the essential tools used to prove the main theorems of this paper.

Proposition 17 Let Fn : X Ω [0, ] be a sequence of random nonnegative functionals which are not identically equal to + , satisfying the compactness property and Γ-converging to the deterministic functional F : X [0, ] which is not identically equal to + . Suppose that for P almost every ω there is a bounded sequence {xn}n N (which may depend on ω) satisfying

Fn(xn) inf x X Fn(x) = 0. (5.1)

Then, with P-probability one,

lim n inf x X Fn(x) = min x X F(x), (5.2)

every bounded sequence {xn}n N in X satisfying (5.1) is relatively compact, and each of its cluster points is a minimizer of F. In particular, if F has a unique minimizer, a bounded sequence {xn}n N satisfying (5.1) converges to the unique minimizer of F.

Proof Consider Ω a set with P-probability one for which all the statements in the definition of Γ-convergence together with the statement of the compactness property hold. We also assume that for every ω Ω , there exists a bounded sequence {xn}n N satisfying (5.1). We fix such ω Ω . Let {xn}n N be a sequence as the one described above. Let x X be arbitrary. By the limsup inequality we know that there exists a sequence { xn}n N with xn x and such that

lim sup n Fn( xn) F( x).

By 5.1 we deduce that

lim sup n Fn(xn) = lim sup n inf x X Fn(x) lim sup n Fn( xn) F( x), (5.3)

and since x was arbitrary we conclude that

lim sup n Fn(xn) inf x X F(x). (5.4)

The fact that F is not identically equal to + implies that the term on the right hand side of the previous expression is finite and thus lim supn Fn(xn) < + . Since the

Consistency of Cheeger and Ratio Graph Cuts

sequence {xn}n N was assumed bounded, we conclude from the compactness property for the sequence of functionals {Fn}n N that {xn}n N is relatively compact. Now let x be any accumulation point of the sequence {xn}n N ( we know there exists at least one due to compactness), we want to show that x is a minimizer of F. Working along subsequences, we can assume without the loss of generality that xn x . By the liminf inequality, we deduce that

inf x X F(x) F(x ) lim inf n F(xn). (5.5)

The previous inequality and (5.3) imply that

F(x ) F( x),

where x is arbitrary. Thus, x is a minimizer of F and in particular infx X F(x) = minx X F(x). Finally, to establish (5.2) note that this follows from (5.4) and (5.5).

5.1 Γ-convergence of graph total variation

Of fundamental importance in obtaining our results is the Γ-convergence of the graph total variation proved in Garc ıa Trillos and Slepˇcev (2016). Let us describe this functional and also let us state the results we use. Given a point cloud Xn := {x1, . . . , xn} D where D is a domain in Rd, we denote by GTVn,εn : TL1(D) [0, ] the functional defined as follows: GTVn,εn(µ, un) = if µ = νn and

GTVn,εn(νn, un) := 1 n2εd+1 n

i,j=1 η |xi xj|

|un(xi) un(xj)|, (5.6)

where η is a kernel satisfying conditions (K1)-(K3). Since we consider GTVn,εn only for µ = νn, from now on we only write GTVn,εn(un), instead of GTVn,εn(νn, un). Using the empirical measure νn, we may alternatively write GTVn,εn(un) as

GTVn,εn(un) = 1 εd+1 n

ˆ ˆ η |x y|

|un(x) un(y)|dνn(x)dνn(y).

The connection of the functional GTVn,εn to problem (1.1) is the following: if Yn is a subset of Xn, then the graph total variation of the indicator function 1Yn is equal to a rescaled version of the graph cut of Yn, that is,

GTVn,εn(1Yn) = 2Cut(Yn, Y c n) n2εd+1 n ;

we recall that wij = η xi xj

. Now we recall the Theorems 1.1 and 1.2 of Garc ıa Trillos and Slepˇcev (2016).

Theorem 18 (Γ - Convergence) Let the domain D, measure ν, kernel η, sample points {xi}i N, sequence {εn}n N, and graph Gn satisfy the assumptions of Theorem 9. Then,

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

GTVn,εn, defined by (5.6), Γ-converge to σηTVν as n in the TL1 sense, where ση is the surface tension associated to the kernel η (see condition (K3)) and TVν is the extension to TL1(D) of weighted (by ρ2) total variation functional introduced in (3.1), defined as follows:

TVν((u, µ)) =

( σηTV (u) if µ = ν + else.

Moreover, we have the following compactness result.

Theorem 19 (Compactness) Under the hypothesis of Theorem 18, the sequence of functionals {GTVn,εn}n N satisfies the compactness property. Namely, for P-almost every ω the following holds: if a sequence {un}n N with un L1(νn) satisfies

lim sup n N un L1(νn) < ,

and lim sup n N GTVn,εn(un) < ,

then {un}n N is TL1-relatively compact.

To conclude this section, we present Corollary 1.3 in Garc ıa Trillos and Slepˇcev (2016), which allows us to restrict the functionals GTVn,εn and TV to characteristic functions of sets and still obtain Γ-convergence. Observe that the only subtle point is the limsup inequality as the liminf inequality and compactness statements are particular cases of Theorem 18 and Theorem 19.

Theorem 20 Under the assumptions of Theorem 18, with probability one the following statement holds: for every A D measurable, there exists a sequence of sets {Yn}n N with Yn Xn such that,

and lim sup n GTVn,εn(1Yn) σηTV (1A).

The results stated above are the main tools in order to establish our main theorems. In the next section we use them together with a careful treatment of the balance term appearing in the denominator of the Cheeger/ratio cut functional.

6. Consistency of two-way balanced cuts

Here we prove Theorem 9.

Consistency of Cheeger and Ratio Graph Cuts

6.1 Outline of the proof

Before proving that minimal balanced cuts {Y n , Y n c} converge to minimal continuum partitions {A , A c} in the sense of Definition 6, we first pause to outline the main ideas. Rather than work directly with the graph-cut-based functional defined on the sets of vertices we work with its relaxation defined on the set of functions from the graph to reals, L1(νn). The relaxed discrete functionals En are defined in (6.6) and the relaxed continuum one, E is defined in (3.12). We first show, by an explicit construction in Subsection 6.2, that the rescaled indicator functions of minimal balanced cuts, 1Yn(x) := αn1Yn(x), (for explicit coefficient αn that we will define later),

u n := 1Y n (x), u n := 1Y n c(x) minimize En(un) over all un L1(νn). (6.1)

Similarly, in Subsection 3.2 we showed that the normalized indicator functions

u := 1A (x), u := 1A c(x) minimize E(u) over all u L1(ν). (6.2)

In Subsection 6.3 we show that the approximating functionals En Γ-converge to σηE in the TL1-sense. In Lemma 23 we establish that u n and u n exhibit the required compactness. Thus, they must converge toward the normalized indicator functions 1A (x) and 1A c(x) up to relabeling (see Proposition 17). If {A , A c} is the unique minimizer, the convergence of the sequences (up to relabeling) {u n} , {u n } follows. The convergence of the partition {Y n , Y n c} toward the partition {A , A c} in the sense of Definition 6 is a direct consequence. The convergence (4.2) follows from (5.2) in Proposition 17.

6.2 Functional description of discrete cuts

We introduce functionals that describe the discrete ratio and Cheeger cuts in terms of functions on Xn, rather than in terms of subsets of Xn. This mirrors the description of continuum partitions provided in Subsection 3.2. For un L1(νn), we start by defining

Bn R(un) := 1

i=1 |un(xi) meann(un)| and Bn C(un) := min c R 1 n

i=1 |un(xi) c|. (6.3)

Here meann(un) = 1

n Pn i=1 un(xi). A straightforward computation shows that for Yn Xn

Bn R(1Yn) = Bal R(Yn, Y c n), Bn C(1Yn) = Bal C(Yn, Y c n). (6.4)

From here on we write Bn to represent either Bn R or Bn C depending on the context. Instead of defining En(un) simply as the ratio GTVn,εn(un)/Bn(un), which is the direct analogue of (1.1), it proves easier to work with suitably normalized indicator functions. Given Yn Xn with Bn(1Yn) = 0, the normalized indicator function 1Yn(x) is defined by

1Yn(x) = 1Yn(x)/Bn C(1Yn) or 1Yn(x) = 1Yn(x)/Bn R(1Yn).

Note that Bn( 1A) = 1. We also restrict the minimization of En(u) to the set

Indn(D) := {un L1(νn) : un = 1Yn for some Yn Xn with Bn(1Yn) = 0}. (6.5)

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Now, suppose that un Indn(D), in other words that un = 1Yn, for some set Yn with Bn(1Yn) > 0. Using (3.9) together with the fact that GTVn,εn (defined in (5.6)) is one-homogeneous implies, as in (3.11)

GTVn,εn(un) = 2 n2εd+1 n

Cut(Yn, Y c n) Bal(Yn, Y cn) . (6.6)

Thus, minimizing GTVn,εn over all un Indn(D) is equivalent to the balanced graph-cut problem (1.1) on the graph Gn = (Xn, Wn) constructed from the first n data points. We have therefore arrived at our destination, a proper reformulation of (1.1) defined over TL1(D) instead of subsets of Xn. The task is to

Minimize En(µ, un) :=

( GTVn,εn(un) if µ = νn and un Indn(D) + otherwise. (6.7)

Since the measure is clear from context, from now on we write En(un) for En(νn, un).

6.3 Γ-Convergence

Proposition 21 (Γ-Convergence) Let domain D, measure ν, kernel η, sequence {εn}n N, sample points {xi}i N, and graph Gn satisfy the assumptions of Theorem 9. Let En be as defined in (6.7) and E as in (3.12). Then

En Γ σηE with respect to TL1 metric as n

where ση is the surface tension defined in assumption (K3). This is implied by the following:

1. For any u L1(ν) and any sequence {un}n N with un L1(νn) that converges to u in TL1, σηE(u) lim inf n En(un). (6.8)

2. For any u L1(ν) there exists at least one sequence {un}n N with un L1(νn) which converges to u in TL1 and also satisfies

lim sup n En(un) σηE(u). (6.9)

We leverage Theorem 18 to prove this claim. We first need a preliminary lemma which allows us to handle the presence of the additional balance terms in (6.7) and (3.12).

Lemma 22 With probability one, the following hold:

(i) If {un}n N is a sequence with un L1(νn) and un TL1 u for some u L1(ν), then Bn(un) B(u).

(ii) If un = 1Yn, where Yn Xn, converges to u = 1A in the TL1-sense, then 1Yn converges to 1A in the TL1-sense.

Consistency of Cheeger and Ratio Graph Cuts

Proof To prove (i), suppose that un L1(νn) and that un TL1 u. Let us consider {Tn}n N a stagnating sequence of transportation maps between ν and {νn}n N (one such sequence

exists with probability one by Proposition 5) . Then, we have un Tn L1(ν) u and thus by Lemma 7, we have that B(un Tn) B(u). To conclude the proof we notice that B(un Tn) = Bn(un) for every n. Indeed, by the change of variables (2.2) we have that for every c R ˆ

D |un(x) c|dνn(x) = ˆ

D |un Tn(x) c|dν(x). (6.10)

In particular we have Bn C(un) = BC(un Tn). Applying the change of variables (2.2), we obtain meann(un) = meanρ(un Tn) and combining with (6.10) we deduce that Bn R(un) = BR(un Tn). The proof of (ii) is straightforward.

Now we turn to the proof or Proposition 21. Proof Liminf inequality. For arbitrary u L1(ν) and arbitrary sequence {un}n N with

un L1(νn) and with un TL1 u, we need to show that

lim inf n En(un) σηE(u).

First assume that u Ind(D). In particular E(u) = TV (u). Now, note that working along a subsequence we can assume that the liminf is actually a limit and that this limit is finite (otherwise the inequality would be trivially satisfied). This implies that for all n large enough we have En(un) < + , which in particular implies that En(un) = GTVn,εn(un). Theorem 18 then implies that

lim inf n En(un) = lim inf n GTVn,εn(un) σηTV (u) = σηE(u).

Now let as assume that u Ind(D). Let us consider a stagnating sequence of transportation

maps {Tn}n N between {νn}n N and ν. Since un TL1 u then un Tn L1(ν) u. By Lemma 7 , the set Ind(D) is a closed subset of L1(ν). We conclude that un Tn Ind(D) for all large enough n. From the proof of Lemma 22 we know that Bn(un) = B(un Tn) and from this fact, it is straightforward to show that un Tn Ind(D) if and only if un Indn(D). Hence, un Indn(D) for all large enough n and in particular lim infn N En(un) = + which implies that the desired inequality holds in this case. Limsup inequality. We now consider u L1(ν). We want to show that there exists a sequence {un}n N with un L1(νn) such that

lim sup n En(un) σηE(u).

Let us start by assuming that u Ind(D). In this case E(u) = + . From Theorem 18

we know there exists at least one sequence {un}n N with un L1(νn) such that un TL1 u. Since E(u) = + , the inequality is trivially satisfied in this case.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

On the other hand, if u Ind(D), we know that u = 1A for some measurable subset A of D with B(1A) = 0. By Theorem 20, there exists a sequence {Yn}n N with Yn Xn,

satisfying 1Yn TL1 1A and

lim sup n GTVn,εn(1Yn) σηTV (1A). (6.11)

Since 1Yn TL1 1A Lemma 22 implies that

Bn(1Yn) B(1A). (6.12)

In particular Bn(1Yn) = 0 for all n large enough, and thus we can consider the function

un := 1Yn Indn(D). From (6.12) it follows that un TL1 u and together with (6.11) it follows that

lim sup n GTVn,εn(un) = lim sup n 1 Bn(Yn)GTVn,εn(1Yn) 1 B(1A)σηTV (1A) = σηTV (u)

Since, un Indn(D) for all n large enough, in particular we have GTVn,εn(1Yn) = En(1Yn) and also since u Ind(D), we have E(u) = TV (u). These facts together with the previous chain of inequalities imply the result.

6.4 Compactness

Lemma 23 (Compactness) With probability one the following statement holds: Any sequence {un}n N with lim sup n En(un) < +

is precompact in TL1. In particular, any sequence {u n}n 1, of minimizers of En (defined in (6.1) and (6.2)) are precompact in the TL1-sense.

Proof Let un denote a sequence satisfying

lim sup n En(un) < .

To show that any subsequence of un has a convergent subsequence it suffices to show that both

lim sup n GTVn,εn(un) < + (6.13)

lim sup n un L1(νn) < + (6.14)

hold due to Theorem 19. Since the result is about asymptotic behavior, we can assume without loss of generality that supn N En(un) < + . Inequality (6.13) follows from the fact that En(un) = GTVn,εn(un). Note that En(un) < in particular implies that un has the form un = 1Yn Bn(Yn) for some Yn Xn.

Consistency of Cheeger and Ratio Graph Cuts

To show (6.14), consider first the balance term that corresponds to the Cheeger cut. Define a sequence vn as follows. Set vn := un if |Yn| |Y c n| and vn = 1Y c n Bn(Y c n) otherwise. It then follows that

vn L1(νn) = min{|Yn|, |Y c n|} min{|Yn|, |Y cn|} = 1.

Also, note that GTVn,εn(vn) = GTVn,εn(un). Thus (6.13) and (6.14) hold for vn, so that

any subsequence of vn has a convergent subsequence in the TL1-sense. Let vnk TL1 v denote a convergent subsequence. Thus, it follows from Proposition 21 , that

σηE(v) lim inf k Enk(vnk) < ,

and in particular v is a normalized characteristic function, that is, v = 1A/B(1A) for some

A D with B(1A) = 0. Since Bnk(1Ynk) = Bnk(1Y c nk), vnk TL1 v implies that

1 Bnk(Ynk) 1 B(A).

Therefore, for large enough k we have

unk L1(νnk) 1 Bnk(Ynk) 2 B(A)

We conclude that unk L1(νnk) remains bounded in L1, so that it satisfies (6.14) and (6.13) simultaneously. This yields compactness in the Cheeger cut case. Now consider the balance term B(u) = BR(u) that corresponds to the ratio cut. Define a sequence vn := un meann(un), and note that GTVn,εn(vn) = GTVn,εn(un) since the total variation is invariant with respect to translation. It then follows that

vn L1(ν) = ˆ

D |un(x) meanρ(un)|ρ(x) dx = B(un) = 1.

Thus the sequence {vn}n N is precompact in TL1. Let vnk TL1 v denote a convergent subsequence. Using a stagnating sequence of transportation maps {Tnk}k N between ν and

the sequence of measures {νnk}k N, we have that vnk Tnk L1(ν) v. By passing to a further subsequence if necessary, we may assume that vnk Tnk(x) v(x) for ν-almost every x in D. For any such x, we have that either Tnk(x) Ynk or Tnk(x) Y c nk so that either

vnk Tnk(x) = 1 2|Ynk| or vnk Tnk(x) = 1 2|Y cnk|.

Now, by continuity of the balance term, we have

B(v) = lim k Bnk(vnk) = 1,

and also meanρ(v) = lim k meannk(vnk) = 0.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

In particular the ν-measure of the region in which v is positive is strictly greater than zero, and likewise the ν-measure of the region in which v is negative is strictly greater than zero. It follows that both |Ynk| and |Y c nk| remain bounded away from zero for all k sufficiently large. As a consequence, the fact that

unk L1(νnk) = 1 2|Y cnk|,

implies that both (6.13) and (6.14) hold along a subsequence, yielding the desired compactness.

6.5 Conclusion of the proof of Theorem 9

We may now turn to the final step of the proof. From Proposition 17, we know that any limit point of {u n}n N ( in the TL1 sense) must equal u or u . As a consequence, for

any subsequence u nk that converges to u we have that 1Y nk

TL1 1A by lemma 22, while

TL1 1A c if the subsequence converges to u instead. Moreover, in the first case we

would also have 1Y c nk

TL1 1A c and in the second case 1Y c nk

TL1 1A . Thus in either case we have

Y nk, Y c nk TL1 {A , A c}

Thus, for any subsequence of {Y n , Y c n }n N it is possible to obtain a further subsequence converging to {A , A c}, and thus the full sequence converges to {A , A c}.

7. Consistency of multiway balanced cuts

Here we prove Theorem 12.

Just as what we did in the two-class case, the first step in the proof of Theorem 12 involves a reformulation of both the balanced graph-cut problem (1.4) and the analogous balanced domain-cut problem (1.11) as equivalent minimizations defined over spaces of functions and not just spaces of partitions or sets.

We let Bn(un) := meann(un) for un L1(νn) and B(u) := meanρ(u) for u L1(ν), to be the corresponding balance terms. Given this balance terms, we let Indn(D) and Ind(D) be defined as in (6.5) and (3.10) respectively.

We can then let the sets Mn(D) and M(D) consist of those collections U = (u1, . . . , u R) comprised of exactly R disjoint, normalized indicator functions that cover D. The sets Mn(D) and M(D) are the multi-class analogues of Indn(D) and Ind(D) respectively.

Consistency of Cheeger and Ratio Graph Cuts

Specifically, we let

(un 1, . . . , un R) : un r Indn(D), ˆ

D un r (x)un s (x) dνn(x) = 0 if r = s,

r=1 un r > 0

(u1, . . . , u R) : ur Ind(D), ˆ

D ur(x)us(x) dν(x) = 0 if r = s,

Note for example that if U = (u1, . . . , u R) M(D), then the functions ur are normalized indicator functions, ur = 1Ar/|Ar| for 1 r R, and the orthogonality constraints imply that {A1, . . . , AR} is a collection of pairwise disjoint sets (up to Lebesgue-null sets). Additionally, the condition that PR r=1 ur > 0 holds almost everywhere implies that the sets {A1, . . . , AR} cover D up to Lebesgue-null sets. We proceed to define the functionals on the space of R-tuples of L1 functions, namely

TL1(D, R) := (µ, U) : µ P(D), U = (u1, . . . , u R), ui L1(µ) for i = 1, . . . , R .

We note that convergence in TL1(D, R) is equivalent to convergence of the R components in TL1(D). One may follow the same argument in the two-class case to conclude that the minimization

Minimize En(µ, Un) :=

(PR r=1 GTVn,εn(un r ) if µ = νn and Un Mn(D) + otherwise (7.3)

is equivalent to the balanced graph-cut problem (1.4), while the minimization

Minimize E(µ, U) :=

(PR r=1 TV (ur) if µ = ν and U M(D) + otherwise (7.4)

is equivalent to the balance domain-cut problem (1.11). As in the two-class case we omit the first argument of En and E, when it is clear from context. At this stage, the proof of Theorem 12, is completed by following the same steps as in the two-class case. In particular we want to show that En defined in (7.3) Γ-converges in the TL1-sense to σηE, where E is defined in (7.4).

Proposition 24 (Γ-Convergence) Let domain D, measure ν, kernel η, sequence {εn}n N, sample points {xi}i N, and graph Gn satisfy the assumptions of Theorem 9. Consider functionals En of (7.3) and E of (7.4). Then

En Γ σn E with respect to TL1(D, R) metric as n .

That is, with probability one, all of the following statements hold

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

1. For any U [L1(ν)]R and any sequence Un (L1(νn))R that converges to U in the TL1 sense, E(U) lim inf n En(Un). (7.5)

2. For any U [L1(ν)]R there exists a sequence Un (L1(νn))R that both, converges to U in the TL1-sense, and also satisfies

lim sup n En(Un) E(U). (7.6)

The following lemma follows in a straightforward way. We omit its proof since it follows analogous arguments to the ones used in the proof of Lemma 23.

Lemma 25 (Compactness) With probability one the following statement holds: Any sequence {Un}n N with Un [L1(νn)]R satisfying

lim sup n En(Un) < + ,

is precompact in the TL1-sense. In particular, any subsequence of {U n}n 1 of minimizers to (7.3) has a further subsequence that converges in the TL1-sense.

Finally, due to Proposition 24 and Lemma 25, the arguments presented in Subsections 6.1 and 6.5 can be adapted in a straightforward way to complete the proof of Theorem 12. So we focus on the proof of Proposition 24, where arguments not present in the two-class case are needed. On one hand, this is due to the presence of the orthogonality constraints in the definition of Mn(D) and M(D), and on the other hand, from a geometric measure theory perspective, due to the fact that an arbitrary partition of the domain D into more than two sets can not be approximated by smooth partitions as multiple junctions appear when more than two sets in the partition meet.

7.1 Proof of Proposition 24

The next lemma is the multiclass analogue of Lemmas 7 and 22 combined.

Lemma 26 (i) If Uk U in (L1(ν))R then B(uk r) B(ur) for all 1 r R. (ii) The

set M(D) is closed in L1(ν). (iii) If {Un} is a sequence with Un (L1(νn))R and Un TL1 U for some U (L1(ν))R, then Bn(un r ) B(ur) for all 1 r R. (iv) If un = 1Yn, where Yn Xn, converges to u = 1A in the TL1-sense, then 1Yn converges to 1A in the TL1-sense.

Proof Statements (i), (iii) follow directly from the proof of Proposition 22. Statement (iv) is exactly as in Proposition 22. In order to prove the second statement, suppose that a sequence {Uk}k N in M(D) converges to some U in (L1(ν))R. We need to show that U M(D). First of all note that

for every 1 r R, uk r L1(ν) ur. Since uk r Ind(D) for every k N, and since Ind(D) is a closed subset of L1(ν) (by Proposition 22), we deduce that ur Ind(D) for every r.

Consistency of Cheeger and Ratio Graph Cuts

The orthogonality condition follows from Fatou s lemma. In fact, working along a subsequence we can without the loss of generality assume that for every r, uk r ur for almost every x in D. Hence, for r = s we have

D ur(x)us(x)dν(x) = ˆ

D lim inf k (uk r(x)uk s(x))dν(x) lim inf k

D uk r(x)uk s(x)dν(x) = 0

Now let us write uk r = 1Akr/B(1Akr) and ur = 1Akr/B(1Ar). As in the proof of Proposition 22 we must have B(1Akr) B(1Ar) as k . Thus, for almost every x D

r=1 ur(x) = lim k

r=1 uk r(x) lim k min r=1,...,R 1 B(1Akr) = min r=1,...,R 1 B(1Ar) > 0.

Proof [of Proposition 24] Liminf inequality. The proof of (7.5) follows the approach used in the two-class case.

Let Un TL1 U denote an arbitrary convergent sequence. As M(D) is closed, if U / M(D) then as in the two-class case, it is easy to see that Un / Mn(D) for all n sufficiently large. The inequality (7.5) is then trivial in this case, as both sides of it are equal to infinity. Conversely, if U M(D) then we may assume that Un Mn(D) for all n, since only those terms with Un Mn(D) can make the limit inferior less than infinity. In this case we easily have

lim inf n En(Un) = lim inf n

r=1 GTVn,εn (un r )

r=1 lim inf n GTVn,εn(un r )

r=1 TV (ur) = σηE(U).

The last inequality follows from Theorem 18. This establishes the first statement in Proposition 24. Limsup inequality. We now turn to the proof of (7.6), which is significantly more involved than the two-class argument due to the presence of the orthogonality constraints. It proves useful to consider an extension of ρ to the whole Rd by setting ρ(x) = λ for x Rd \ D. This extension is a lower semi-continuous function and has the same lower and upper bounds that the original ρ has. Borrowing terminology from the Γ-convergence literature, we say that U (L1(ν))R has a recovery sequence when there exists a sequence Un (L1(νn))R such that (7.6) holds. To show that each U (L1(ν))R has a recovery sequence, we first remark that due to general properties of the Γ-convergence, it is enough to verify (7.6) for U belonging to a dense subset of M(D) with respect to the energy E (see Remark 14). We furthermore remark that it is enough to consider U = (u1, . . . , u R) (L1(D))R for which E(U) < , as the other case is trivial. So we can consider U M(D) that satisfy

r=1 TV (ur) < .

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Let ur = 1Ar/B(1Ar) and let c0 := max{B(1A1), . . . , B(1AR)} denote the size of the largest set in the collection. The fact that E(U) < then implies that for every s = 1, . . . , R,

TV (1As) c0 TV (us) c0

r=1 TV (ur) < ,

so that all sets {A1, . . . , AR} in the collection defining U have finite perimeter. Additionally because U M(D) implies that any two sets Ar, As with r = s have empty intersection up to a Lebesgue-null set, we may freely assume without the loss of generality that the sets {A1, . . . , AR} are mutually disjoint. We say that a subset of Rd has a piecewise (PW) smooth boundary if the boundary is a subset of the union of finitely many open d 1-dimensional manifolds embedded in Rd. We first construct a recovery sequence for U, as above, whose defining sets {A1, . . . , AR} are of the form Ar = Br D, where Br has piecewise smooth boundary and satisfies |D1Br|ρ2( D) = 0. We say that such U is induced by piecewise smooth sets. We later prove that such partitions are dense among partitions of D by sets of finite perimeters. 2

Constructing a recovery sequence for U induced by sets with piecewise smooth boundary. Let Y n r = Ar Xn denote the restriction of Ar to the first n data points. Now, let us consider the transportation maps {Tn}n N from Proposition 5. We let Ar n be the set for which 1Anr = 1Y r n Tn. We first notice that the fact that Br has a piecewise smooth boundary in Rd and the fact that 1Anr 1Ar is nontrivial only within the tubular neighborhood of Br of radius || Id Tn|| , imply that

1Anr 1Ar L1(ν) C0(Br) || Id Tn|| , (7.7)

where C0(Br) denotes some constant that depends on the set Br. This inequality follows from the formulas for the volume of tubular neighborhoods (see Weyl (1939), page 461). In particular, note that by the change of variables (2.2) we have, |Y n r | = |An r | |Ar| as n , so that in particular we can assume that |Y n r | = 0. We define un r := 1Y n r /|Y n r | as the corresponding normalized indicator function. We claim that Un := (un 1, . . . , un R) furnishes the desired recovery sequence. To see that Un Mn(D) we first note that each un r Indn(D) by construction. On the other hand, the fact that {A1, . . . , AR} forms a partition of D implies that {Y n 1 , . . . , Y n R } defines a partition of Xn. As a consequence,

r=1 GTVn,εn(un r )

by definition of the En functionals. Using (7.7), we can proceed as in remark 5.1 in Garc ıa Trillos and Slepˇcev (2016). In particular, we can assume that η has the form η(|z|) = a for |z| < b and η(z) = 0 otherwise; the general case follows in a straightforward way by using an approximating procedure with

2. Note that unlike in the two-class case, due to multiple junctions , one cannot approximate a general partition by a partition with sets with smooth boundaries. This makes the construction more complicated.

Consistency of Cheeger and Ratio Graph Cuts

kernels that are a finite sum of step functions like the one considered previously (see the proof of Theorem 1.1 in Garc ıa Trillos and Slepˇcev (2016)) . We set εn := εn + 2

b|| Id Tn|| . Recall that by assumption || Id Tn|| εn (see the statement of Theorem 9 and Proposition 5), and thus εn is a small perturbation of εn. Define the non-local total variation g TV εn of an integrable function u L1(ν) as

g TV εn(u) := 1 εd+1 n

D D η |x y|

|u(x) u(y)|ρ(x)ρ(y) dxdy.

Using the definition of εn, and the form of the kernel η, we deduce that for all n N, and almost every x, y D we have

η |Tn(x) Tn(y)|

This inequality an a change of variables (see 2.2) implies that

εd+1 n εd+1 n GTVn,εn(1Y n r ) g TV εn(1Anr ).

A straightforward computation shows that there exists a constant K0 such that

|g TV εn(1Anr ) g TV εn(1Ar)| K0

εn 1Anr 1Ar L1(ν) K0C0(Br)|| Id Tn||

εn 1, the previous inequalities imply that

lim sup n N GTVnεn(1Y n r ) lim sup n N g TV εn(1Anr ) = lim sup n N g TV εn(1Ar).

Finally, from remark 4.3 in Garc ıa Trillos and Slepˇcev (2016) we deduce that

lim sup n g TV εn(1Anr ) σηTV (1Ar),

and thus we conclude that lim supn GTVn,εn(1Ar) σηTV (1Ar). As a consequence we have

lim sup n GTVn,εn(un r ) = lim sup n

GTVn,εn(1Y n r ) Bn(1Y n r ) ση TV (1Ar)

for each r, by continuity of the balance term. From the previous computations we conclude that En(Un) E(U), and from (7.7), we deduce that Un U in the TL1-sense, so that Un does furnish the desired recovery sequence. Density. To prove Proposition 24, we show that for any U = ( 1A1, . . . , 1AR) where each of the sets Ar has finite perimeter, there exists a sequence Um = ( 1Am 1 , . . . , 1Am R )

m N, where each of the Um is induced by piecewise smooth sets, and such that for every r {1, . . . , R}

1Am r L1(ν) 1Ar,

and lim m TV (1Am r ; ν) = TV (1Ar; ν).

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Note that in fact, by establishing the existence of such approximating sequence, it immediately follows that Um U in (L1(ν))R and that limm E(Um) = E(U) ( by continuity of the balance terms). We provide the construction of the approximating sequence {Um}m N through the sequence of three lemmas presented below.

Lemma 27 Let {A1, . . . , AR} denote a collection of open and bounded sets with smooth boundary in Rd that satisfy

Hd 1( Ar As) = 0 , r = s. (7.8)

Let D denote an open and bounded set. Then there exists a permutation π : {1, . . . , R} {1, . . . , R} such that

TV (1Aπ(r)\SR s=r+1 Aπ(s); ν) TV (1Aπ(r); ν), r {1, . . . , R} .

Proof The proof is by induction on R. Base case: Note that if R = 1 there is nothing to prove. Inductive Step: Suppose that the result holds when considering any R 1 sets as described in the statement. Let A1, . . . , AR be a collection of open, bounded sets with smooth boundary satisfying (7.8) . By the induction hypothesis it is enough to show that we can find r {1, . . . , R} such that

TV (1Ar\S s =r As; ν) TV (1Ar; ν). (7.9)

To simplify notation, denote by Γi the set Ai and define aij as the quantity

Γi (Aj\S k =i,k =j Ak) D ρ2(x) d Hd 1(x).

Hypothesis (7.8) and (3.3) imply that the equality

TV (1Ar\S s =r As; ν) = ˆ

(Ar\S s =r As) D ρ2 d Hd 1 = ˆ

Γr (S s =r As)c D ρ2 d Hd 1 + X

s: s =r asr

(7.10) holds for every r {1, . . . , R} , as does the inequality

TV (1Ar; ν) ˆ

Γr (S s =r As)c D ρ2(x) d Hd 1 + X

s: s =r ars. (7.11)

If TV (1Ar\S s =r As; ν) > TV (1Ar; ν) for every r then (7.11) and (7.10) would imply that X

s: s =r asr > X

s: s =r ars, r,

which after summing over r would imply

s: s =r asr >

s: s =r ars =

s: s =r asr.

This would be a contradiction. Hence there exists at least one r for which (7.9) holds.

Consistency of Cheeger and Ratio Graph Cuts

Lemma 28 Let D denote an open, bounded domain in Rd with Lipschitz boundary and let (B1, . . . , BR) denote a collection of R bounded and mutually disjoint subsets of Rd that satisfy

(i) TV (1Br; Rd) < + , (ii) |D1Br|ρ2( D) = 0 and (iii) D R r=1Br.

Then there exists a sequence of mutually disjoint sets {Am 1 , . . . , Am R} with piecewise smooth boundaries which cover D and satisfy

1Am r L1(Rd) 1Br and lim m TV (1Am r ; ν) = TV (1Br; ν) (7.12)

for all 1 r R.

Proof The proof of this lemma follows very similar ideas to those used when proving that sets with smooth boundary approximate sets with finite perimeter (see Theorem 13.46 in Leoni (2009)). Since our goal is to approximate partitions of more than two sets, we need to modify the arguments slightly. We highlight the important steps in the proof and refer to Leoni (2009) and Ambrosio et al. (2000) for details. First of all note that TV (1Br; Rd) and |D1Br|ρ2( D) are defined considering ρ as a function from Rd into R. We are using the extension considered when we introduced the weighted total variation at the beginning of subsection 3.1. Given that ρ2 : Rd (0, ) is lower semi-continuous and bounded below and above by positive constants then, it belongs to the class of weights considered in Baldi (2001) where the weighted total variation is studied. For r = 1, . . . , R, we consider sequences of functions uk r C (Rd, [0, 1]) satisfying

uk r L1(Rd) 1Br and TV (uk r; ν) TV (1Br; ν), as k . (7.13)

This can be achieved by using standard, radially symmetric mollifiers Jk and setting ur k = Jk 1Br, where stands for convolution. The functions Jk have the form Jk(x) = kd J (k|x|), where J : [0, ) [0, ) is a smooth, decreasing function satisfying

Rd J(|x|)dx = 1. See Theorem 13.46 in Leoni (2009) for more details. The (uk 1, . . . , uk R) also satisfy one additional property that will prove useful: there exists a constant α > 0 so that

r=1 uk r(x) = 1D Jk(x) α > 0 for all x D.

To see this, note that the fact that D is an open and bounded set with Lipschitz boundary implies that (see Grisvard (1985), Theorem 1.2.2.2) there exists a cone C Rd with nonempty interior and vertex at the origin, a family of rotations {Rx}x D and a number ζ > 0 such that for every x D, x + Rx(C B(0, ζ)) D.

The isotropy of Jk implies that ˆ

D Jk(x y)dy ˆ

x+Rx(C B(0,ζ)) Jk(x y)dy = ˆ

C B(0,ζ) Jk(y)dy = ˆ

C B(0,kζ) J(|y|)dy

C B(0,ζ) J(|y|)dy =: α > 0,

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

for some positive constant α. The summation Σk(x) of all uk r therefore satisfies the pointwise estimate

r=1 uk r(x) = ˆ

r=1 1Br(y) dy ˆ

D Jk(x y)dy α

for all x D as claimed. Now, for k N, t (0, 1) and r = 1, . . . , R, we let Bk r (t) := x : uk r(x) > t . From (7.13), Sard s lemma (see Corollary 13.45 of Leoni (2009)), the lower semi-continuity of the total variation and the coarea formula for total variation, it follows that for almost every t (0, 1),

Bk r (t) is smooth k, lim k TV (1Bkr (t); ν) = TV (1Br; ν), 1Bkr (t) L1(ν) 1Br, (7.14)

for all r = 1, . . . , R. Combining (7.14) with Lemma 2.95 in Ambrosio et al. (2000), we can find positive numbers t1, . . . , t R strictly smaller than α/R, such that for every r = 1, . . . , R

Bk r (tr) is smooth k, lim k TV (1Bkr (tr); ν) = TV (1Br; ν), 1Bkr (tr) L1(ν) 1Br, (7.15)

and such that for r = s,

Hd 1 Bk r (tr) Bk s (ts) = 0, k N.

We let Bk r := Bk r (tr) for r = 1, . . . , R and k N. We claim that for every k N, the sets Bk 1, . . . , Bk R cover D. To see this, suppose there exists x D \ SR r=1 Bk r . This

would imply that uk r(x) tr for all r. In turn, Σk(x) PR r=1 tr < α, which contradicts the estimate on Σk obtained earlier. For every k N, we can now use the sets (Bk 1, . . . , Bk R) as input in Lemma (27) to obtain a partition (Ak 1, . . . , Ak R) of D, defined by

Ak r := Bk r \

s=π 1 k (r)+1 Bk πk(s)

where πk is a permutation of {1, . . . , R} guaranteeing that for every r = 1, . . . , R

TV 1Akr; ν TV (1Bkr ; ν). (7.16)

Each Ak r has a piecewise smooth boundary due to the fact that each Bk r has a smooth boundary. The disjointness of (B1, . . . , BR) combines with the L1-convergence of 1Bkr to

1Br to show that 1Am r L1(Rd) 1Br as well. Finally, the lower semi-continuity of the total variation together with (7.16) and (7.15) imply (7.12).

To complete the construction, and therefore to conclude the proof of Lemma 24, we need to verify the hypotheses (i) (ii) of the previous lemma. This is the content of our final lemma.

Consistency of Cheeger and Ratio Graph Cuts

Lemma 29 Let D be an open bounded domain with Lipschitz boundary and let {A1, . . . , AR} denote a disjoint collection of sets that satisfy

Ar D and TV (1Ar; ν) < .

Then, there exists a disjoint collection of bounded sets (B1, . . . , BR) that satisfy Br D = Ar together with the properties

(i) TV (1Br; Rd) < + and (ii) |D1Br|ρ2( D) = 0.

The proof follows from Remark 3.43 in Ambrosio et al. (2000) (which with minimal modifications applies to total variation with weight ρ2).

8. Numerical Experiments

We now present numerical experiments to provide a concrete demonstration and visualization of the theoretical results developed in this paper. We conduct all of our experiments using the Cheeger cut algorithm of Bresson et al. (2012); we omit the ratio cut for the sake of brevity and to avoid redundancy. These experiments focus on elucidating when and how minimizers of the graph-based Cheeger cut problem,

u n argmin u L1(νn) En(u) with Bn(u) := min c R 1 n

i=1 |u(xi) c|, (8.1)

converge in the appropriate sense to a minimizer of the continuum Cheeger cut problem

u argmin u L1(ν) E(u) with B(u) := min c R

D |u(x) c| dx. (8.2)

We always take ρ(x) := 1/vol(D) as the constant density. The data points Xn := {x1, . . . , xn} therefore represent i.i.d. samples from the uniform distribution. We consider the following two rectangular domains

D1 := (0, 1) (0, 4) and D2 := (0, 1) (0, 1.5)

in our experiments. We may easily compute the optimal continuum Cheeger cut for these domains. The characteristic function

1A1(x) for A1 := {(x, y) D1 : y > 2} ,

when appropriately normalized, provides a minimizer u 1 L1(ν) of the continuum Cheeger cut in the former case, while the characteristic function

1A2(x) for A2 := {(x, y) D2 : y > 0.75}

analogously furnishes a minimizer u 2 L1(ν) in the latter case. Figure 2 provides an illustration of a sequence of discrete partitions, computed from the graph-based Cheeger cut problem, converging to the optimal continuum Cheeger cut.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Figure 2: Visualization of the convergence process. Each figure depicts a computed optimal partition Y n (in black) of one random realization of the random geometric graph Gn = (Xn, Wn) for each k {0, 1, . . . , 7}, where n = 1000 2k, ε = n 0.3 and the domain considered is D1. Note that the scaling of ε with respect to n falls within the context of our theoretical results. The red line indicates the optimal cut, that is the boundary of the set A1 := {(x, y) D1 : y > 2} , at the continuum level.

Each of our experiments use the kernel η(z) = 1{|z| 1} for the computation of the similarity weights, wi,j = 1{ xi xj εn},

so that the graphs Gn = (Xn, Wn) correspond to random geometric graphs (see Penrose (2003)). We use the domain D1 only for the illustrations in Figure 2; all other experiments are conducted on the domain D2. We use the steepest descent algorithm of Bresson et al. (2012) to solve the graph-based Cheeger cut problem on these graphs. This algorithm relies upon a non-convex minimization, and its solutions depend upon the choice of initialization. We initialize it with the ground-truth partition Y i n := Ai Xn in an attempt to avoid sub-optimal solutions and to bias the algorithm towards the correct continuum cut. We terminate the algorithm once three consecutive iterates show 0% change in the corresponding partition of the graph. We let Y n denote the partition of Gn returned by the algorithm, which we view as the optimal solution of the graph-based Cheeger cut problem. Finally, we quantify the error between the optimal continuum partition Ai Di and the nth optimal graph-based partition Y n of Gn simply by using the percentage of misclassified data points,

i=1 |1Y in(xi) 1Y n (xi)|, 1

i=1 |1Y in(xi) 1(Y n )c(xi)|

The rationale for this choice comes from the following observation. If Tn(x) denotes a sequence of transportation maps between νn and ν that satisfy || Id Tn|| = o(1), then by

Consistency of Cheeger and Ratio Graph Cuts

(a) εn = n 0.3

(b) εn = 2(log n/(πn))1/2

Figure 3: Graph regularity. We work with the domain D2. For each scaling of εn with n, the corresponding plot depicts two measures of regularity for the sequence of random geometric graphs. The first measure (in red) is the average E(max(di)/min(di)), the average ratio of the maximal degree max(di) of Gn to the minimal degree. For each n, the average is computed over 1, 440 independent graph realizations. The second measure (in green) corresponds to the ratio of the average maximal degree to the average minimal degree, computed over 1, 440 independent trials as before. The graphs with εn = n 0.3 become increasingly regular while the graphs with εn = 2(log n/(πn))1/2 become increasingly irregular.

the change of variables (2.2) (and ignoring the min for simplicity) we have

D |1Ai Tn(x) 1Y n Tn(x)| dx.

By the triangle inequality, we therefore obtain

1Ai 1Y n Tn L1(ν) := ˆ

D |1Ai(x) 1Y n Tn(x)| dx

D |1Ai(x) 1Ai Tn(x)| dx en + O (|| Id Tn|| ) .

The last inequality follows since each Ai has a piecewise smooth boundary. In this way, if || Id Tn|| = o(1) then verifying en = o(1) suffices to show that TL1 convergence of minimizers holds. Under the assumption that || Id Tn|| = o(1), a similar argument shows that en = o(1) is equivalent to TL1 convergence. This equivalence motivates using en as a quantitative measure of TL1 convergence in our experiments. To check convergence, and to explore the issues related to Remark (2), we perform exhaustive numerical experiments for three distinct scalings of εn with respect to the total

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

number of sample points on the domain D2. Specifically, we consider the scalings

εn = n 0.3, εn = 2 log n

1/2 , and εn = log n

These scalings correspond to three distinct types of random geometric graphs. The first scaling falls well within the acceptable bounds for εn covered by our consistency theorems. Random graph theory shows that Gn is almost surely connected in this regime: the probability that Gn is disconnected vanishes in the n limit. The second scaling also gives rise to a sequence Gn of connected random geometric graphs for n sufficiently large (see Gupta and Kumar (1999), Penrose (2003)). However, the geometric graphs Gn exhibit rather different structural properties in this case; if εn = n 0.3 then the graphs Gn become increasingly regular as n , while if πε2 n = 2(log n)/n then the graphs Gn become increasingly irregular. See Figure 3 for an illustration. The final scaling corresponds to a scaling bellow the connectivity threshold of random geometric graphs (see Gupta and Kumar (1999), Penrose (2003)). The graphs Gn are disconnected for large enough n under this scaling. However, in this regime each Gn has a giant component (a connected subgraph Hn of Gn) that contains all but a small handful of vertices (see Figure 4 at right). We designed our experiments to explore the extent to which a lack of graph-regularity or graph-connectivity might cause inconsistency of balanced cuts. The first scaling εn = n 0.3

serves as a benchmark or control. It falls within the context of our consistency theorems, and so provides a means of determining the typical behavior of balanced cut algorithms when consistency holds. The second scaling, which falls outside the realm of our consistency results, tests whether connected graphs with different structural properties still lead to consistent results. The final scaling probes the realm where connectivity fails, but in a mild and easily correctible way. As the theory outlined above indicates, if we pose the balanced cut minimization over the full graph Gn then we can no longer expect consistency to hold. These graphs pose no practical difficulty, however, as we may simply extract the giant component Hn of each Gn and then minimize the balanced cut over this connected subgraph. We simply assign each vertex in Gn \ Hn to one of the two classes uniformly at random. Our last experiment explores whether consistency might still hold using this modified approach. Table 1 and Figure 4 report the results of these experiments. In all cases, we measure error by using the expected number of misclassified points (8.3) averaged over the number of trials indicated in Table 1. We used a smaller number of trials for large n simply due to the overwhelming computational burden. In general, we observe that sparser graphs lead to larger error (see Table 1). We caution that the corresponding rates reported in Figure 4 may not coincide with the true asymptotic rate of convergence, since we expect that as n the denser graph will still produce lower error. We furthermore remark that the measure of error we consider in Table 1 is also too weak to show convergence in the almost sure sense as provided by our consistency theorems. It does, however, indicate consistency in the weaker sense of convergence in probability (via Markov s inequality). The algorithm we use to optimize the discrete Cheeger cut also relies upon a non-convex minimization (Bresson et al., 2012), so we cannot say with certainty that the corresponding computed optimizers are global. Instead, initializing the algorithm with the ground truth partition biases the

Consistency of Cheeger and Ratio Graph Cuts

n = 1k 2k 4k 8k 16k 32k 64k

εn = n 0.3 :

E(en) .0776 .0616 .0495 .0391 .0320 .0238 .0205

Trials 104 104 104 104 1008 1008 192

εn = 2(log n/(πn))1/2 :

E(en) .0710 .0603 .0509 .0427 .0366 .0303 .0256

Trials 104 104 104 104 1008 1008 192

εn = (log n/(πn))1/2 :

E(en) .3221 0.1984 .1216 .0883 .0672 .0528 .0424

Trials 104 104 104 104 1008 1008 192

Table 1: Average error E(en) between partitions. For each n and each scaling of εn, we obtained an estimate of the error E(en) by computing the mean of (8.3) over the indicated number of independent trials. Figure 4 provides a corresponding error plot.

algorithm toward the correct cut. If the algorithm were to fail under these circumstances, it would provide strong numerical evidence against consistency.

The results appear rather similar regardless of whether εn lies in the strongly connected (εn = n 0.3), weakly connected (εn = 2(log n/(πn))1/2) or weakly disconnected (εn = (log n/(πn))1/2) regimes. Indeed, in each case the error E(en) decays to zero with a polynomial rate. The varying degree properties of the random geometric graphs in these regimes do not seem to play much of a role. A disconnected graph, while more problematic, is not an insurmountable obstacle provided Gn contains a giant component. A naive handling of the disconnected vertices still leads to plausibly consistent results. While certainly not conclusive evidence, it seems reasonable to conjecture that consistency should hold, perhaps in the weaker probabilistic sense, for εn as small as the critical scaling for connectivity. We leave a further exploration of this for future research.

Acknowledgments

The authors are grateful to the editor and the referees for many valuable suggestions.

They are also grateful to ICERM, where part of the research was done during the research cluster: Geometric analysis methods for graph algorithms. DS and NGT are grateful to NSF (grants DMS-1211760 and DMS-1516677) for its support. Jv B was supported by NSF grant DMS 1312344/DMS 1521138. TL was supported by NSF (grant DMS-1414396). The authors would like to thank the Center for Nonlinear Analysis of the Carnegie Mellon University for its support.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

Figure 4: At left: a log-log plot of the relative expected errors E(en)/E(e1000) computed in Table 1 together with a corresponding linear approximation for n large. The solid red line corresponds to the scaling εn = n 0.3, the dashed green line corresponds to the scaling εn = 2(log n/(πn))1/2 and the dotted blue line corresponds to the scaling εn = (log n/(πn))1/2 of the disconnected regime. The linear approximation for the scaling εn = (log n/(πn))1/2 is given for those graphs Gn that, in expectation, have more than 90% of vertices in the giant component. At right: the expected fraction of vertices that lie in the giant component Hn of the disconnected random geometric graph Gn.

G. Alberti and G. Bellettini. A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies. European J. Appl. Math., 9(3):261 284, 1998. ISSN 0956-7925. doi: 10.1017/S0956792598003453. URL http://dx.doi.org/10.1017/ S0956792598003453.

L. Ambrosio, N. Fusco, and D. Pallara. Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 2000. ISBN 0-19-850245-1.

R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. In Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS 06), pages 475 486, 2006.

E. Arias-Castro and B. Pelletier. On the convergence of maximum variance unfolding. The Journal of Machine Learning Research, 14(1):1747 1770, 2013.

E. Arias-Castro, B. Pelletier, and P. Pudlo. The normalized graph cut and Cheeger constant: from discrete to continuous. Advances in Applied Probability, 44:907 937, 2012.

Consistency of Cheeger and Ratio Graph Cuts

S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2):5, 2009.

A. Baldi. Weighted BV functions. Houston J. Math., 27(3):683 705, 2001. ISSN 0362-1588.

M. Belkin and P. Niyogi. Convergence of Laplacian eigenmaps. Advances in Neural Information Processing Systems (NIPS), 2006.

M. Belkin and P. Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods. J. Comput. System Sci., 74(8):1289 1308, 2008. ISSN 0022-0000. doi: 10.1016/ j.jcss.2007.08.006. URL http://dx.doi.org/10.1016/j.jcss.2007.08.006.

G. Bellettini, G. Bouchitt e, and I. Fragal a. BV functions with respect to a measure and relaxation of metric integral functionals. J. Convex Anal., 6(2):349 366, 1999. ISSN 0944-6532.

A. Braides. Gamma-Convergence for Beginners. Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, 2002.

A. Braides and N. K. Yip. A quantitative description of mesh dependence for the discretization of singularly perturbed nonconvex problems. SIAM J. Numer. Anal., 50(4): 1883 1898, 2012. ISSN 0036-1429. doi: 10.1137/110822001. URL http://dx.doi.org/ 10.1137/110822001.

X. Bresson and T. Laurent. Asymmetric Cheeger cut and application to multi-class unsupervised clustering. CAM report 12-27, UCLA, 2012.

X. Bresson, T. Laurent, D. Uminsky, and J. von Brecht. Convergence and energy landscape for Cheeger cut clustering. In Advances in Neural Information Processing Systems (NIPS), pages 1394 1402, 2012.

X. Bresson, T. Laurent, D. Uminsky, and J. von Brecht. Multiclass total variation clustering. In Advances in Neural Information Processing Systems (NIPS), 2013.

A. Chambolle, A. Giacomini, and L. Lussardi. Continuous limits of discrete perimeters. M2AN Math. Model. Numer. Anal., 44(2):207 230, 2010. ISSN 0764-583X. doi: 10.1051/ m2an/2009044. URL http://dx.doi.org/10.1051/m2an/2009044.

J. Cheeger. A Lower Bound for the Smallest Eigenvalue of the Laplacian. Problems in Analysis, pages 195 199, 1970.

F. R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.

G. Dal Maso. An Introduction to Γ-convergence. Springer, 1993.

N. Dirr and E. Orlandi. Sharp-interface limit of a Ginzburg-Landau functional with a random external field. SIAM J. Math. Anal., 41(2):781 824, 2009. ISSN 0036-1410. doi: 10.1137/070684100. URL http://dx.doi.org/10.1137/070684100.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

R. M. Dudley. Real analysis and probability, volume 74 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2002. ISBN 0-521-00754-2. doi: 10.1017/CBO9780511755347. URL http://dx.doi.org/10.1017/CBO9780511755347. Revised reprint of the 1989 original.

S. Esedo glu and F. Otto. Threshold dynamics for networks with arbitrary surface tensions. Comm. Pure Appl. Math., 68(5):808 864, 2015. ISSN 0010-3640. doi: 10.1002/cpa.21527. URL http://dx.doi.org/10.1002/cpa.21527.

N. Garc ıa Trillos and D. Slepˇcev. On the rate of convergence of empirical measures in -transportation distance. Canad. J. Math., 67(6):1358 1383, 2015. ISSN 0008-414X. doi: 10.4153/CJM-2014-044-6. URL http://dx.doi.org/10.4153/CJM-2014-044-6.

N. Garc ıa Trillos and D. Slepˇcev. Continuum limit of total variation on point clouds. Arch. Ration. Mech. Anal., 220(1):193 241, 2016. ISSN 0003-9527. doi: 10.1007/ s00205-015-0929-z. URL http://dx.doi.org/10.1007/s00205-015-0929-z.

E. Gin e and V. Koltchinskii. Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results. In High dimensional probability, volume 51 of IMS Lecture Notes Monogr. Ser., pages 238 259. Inst. Math. Statist., Beachwood, OH, 2006. doi: 10. 1214/074921706000000888. URL http://dx.doi.org/10.1214/074921706000000888.

M. Gobbino. Finite difference approximation of the Mumford-Shah functional. Comm. Pure Appl. Math., 51(2):197 228, 1998. ISSN 0010-3640. doi: 10.1002/(SICI) 1097-0312(199802)51:2 197::AID-CPA3 3.3.CO;2-K. URL http://dx.doi.org/10. 1002/(SICI)1097-0312(199802)51:2<197::AID-CPA3>3.3.CO;2-K.

M. Gobbino and M. G. Mora. Finite-difference approximation of free-discontinuity problems. Proc. Roy. Soc. Edinburgh Sect. A, 131(3):567 595, 2001. ISSN 0308-2105. doi: 10.1017/S0308210500001001. URL http://dx.doi.org/10.1017/S0308210500001001.

A. Goel, S. Rai, and B. Krishnamachari. Sharp thresholds for monotone properties in random geometric graphs. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 580 586, New York, 2004. ACM. doi: 10.1145/1007352.1007441. URL http://dx.doi.org/10.1145/1007352.1007441.

P. Grisvard. Elliptic problems in nonsmooth domains, volume 24 of Monographs and Studies in Mathematics. Pitman (Advanced Publishing Program), Boston, MA, 1985. ISBN 0273-08647-2.

P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In Stochastic analysis, control, optimization and applications, Systems Control Found. Appl., pages 547 566. Birkh auser Boston, Boston, MA, 1999.

L. Hagen and A. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE Trans. Computer-Aided Design, 11:1074 1085, 1992.

J. Hartigan. Consistency of single linkage for high density clusters. J. Amer. Statist. Assoc., 76:388 394., 1981.

Consistency of Cheeger and Ratio Graph Cuts

M. Hein and T. B uhler. An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA. In Advances in Neural Information Processing Systems (NIPS), pages 847 855, 2010.

M. Hein and S. Setzer. Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts. In Advances in Neural Information Processing Systems (NIPS), 2011.

M. Hein, J.-Y. Audibert, and U. Von Luxburg. From graphs to manifolds weak and strong pointwise consistency of graph Laplacians. In Learning theory, pages 470 485. Springer, 2005.

R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 51(3):497 515, 2004.

G. Leoni. A first course in Sobolev spaces, volume 105 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2009. ISBN 978-0-8218-4768-8.

M. Maier, U. von Luxburg, and M. Hein. How the result of graph clustering methods depends on the construction of the graph. ESAIM: Probability and Statistics, 17:370 418, 1 2013. ISSN 1262-3318. doi: 10.1051/ps/2012001. URL http://www.esaim-ps. org/article_S2810012000018.

H. Narayanan, M. Belkin, and P. Niyogi. On the relation between low density separation, spectral clustering and graph cuts. In Advances in Neural Information Processing Systems (NIPS), pages 1025 1032, 2006.

M. Penrose. A strong law for the longest edge of the minimal spanning tree. Ann. Probab., 27(1):246 260, 1999. ISSN 0091-1798. doi: 10.1214/aop/1022677261. URL http://dx. doi.org/10.1214/aop/1022677261.

M. Penrose. Random geometric graphs, volume 5 of Oxford Studies in Probability. Oxford University Press, Oxford, 2003. ISBN 0-19-850626-0. doi: 10.1093/ acprof:oso/9780198506263.001.0001. URL http://dx.doi.org/10.1093/acprof:oso/ 9780198506263.001.0001.

D. Pollard. Strong consistency of k-means clustering. ann. statist. 9 135 140. Annals of Statistics, 9:135 140, 1981.

A. C. Ponce. A new approach to Sobolev spaces and connections to Γ-convergence. Calc. Var. Partial Differential Equations, 19(3):229 255, 2004. ISSN 0944-2669. doi: 10.1007/ s00526-003-0195-z. URL http://dx.doi.org/10.1007/s00526-003-0195-z.

O. Savin and E. Valdinoci. Γ-convergence for nonlocal phase transitions. Ann. Inst. H. Poincar e Anal. Non Lin eaire, 29(4):479 500, 2012. ISSN 0294-1449. doi: 10.1016/j. anihpc.2012.01.006. URL http://dx.doi.org/10.1016/j.anihpc.2012.01.006.

J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22(8):888 905, 2000.

Garc ıa Trillos, Slepˇcev, von Brecht, Laurent, and Bresson

A. Singer. From graph to manifold Laplacian: the convergence rate. Appl. Comput. Harmon. Anal., 21(1):128 134, 2006. ISSN 1063-5203. doi: 10.1016/j.acha.2006.03.004. URL http://dx.doi.org/10.1016/j.acha.2006.03.004.

D. Spielman and S. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81 90, 2004.

D. Spielman and S. Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on Computing, 42(1):1 26, 2013.

A. Szlam and X. Bresson. Total variation and Cheeger cuts. In International Conference on Machine Learning (ICML), pages 1039 1046, 2010.

M. Thorpe, F. Theil, A. M. Johansen, and N. Cade. Convergence of the k-means minimization problem using Γ-convergence. SIAM J. Appl. Math., 75(6):2444 2474, 2015. ISSN 0036-1399. doi: 10.1137/140974365. URL http://dx.doi.org/10.1137/140974365.

D. Ting, L. Huang, and M. I. Jordan. An analysis of the convergence of graph Laplacians. In Proceedings of the 27th International Conference on Machine Learning, 2010.

Y. van Gennip and A. L. Bertozzi. Γ-convergence of graph Ginzburg-Landau functionals. Adv. Differential Equations, 17(11-12):1115 1180, 2012. ISSN 1079-9389.

C. Villani. Topics in Optimal Transportation. Graduate Studies in Mathematics. American Mathematical Society, 2003. ISBN 9780821833124. URL http://books.google.com/ books?id=q6ky E2Zkxrc C.

U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395 416, 2007.

U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. Technical Report TR 134, Max Planck Institute for Biological Cybernetics, 2004.

U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. The Annals of Statistics, 36(2):555 586, 2008.

Y.-C. Wei and C.-K. Cheng. Towards efficient hierarchical designs by ratio cut partitioning. In Computer-Aided Design, 1989. ICCAD-89. Digest of Technical Papers., 1989 IEEE International Conference on, pages 298 301. IEEE, 1989.

H. Weyl. On the Volume of Tubes. Amer. J. Math., 61(2):461 472, 1939. ISSN 0002-9327. doi: 10.2307/2371513. URL http://dx.doi.org/10.2307/2371513.

S. X. Yu and J. Shi. Multiclass spectral clustering. In Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, pages 313 319. IEEE, 2003.