ESTIMATING PERIMETER USING GRAPH CUTS

arXiv:1602.04102v2 [] 14 Aug 2016

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

A BSTRACT. We investigate the estimation of the perimeter of a set by a graph cut of a
random geometric graph. For Ω ⊂ D = (0, 1)d , with d ≥ 2, we are given n random
i.i.d. points on D whose membership in Ω is known. We consider the sample as a random
geometric graph with connection distance ε > 0. We estimate the perimeter of Ω (relative
to D) by the, appropriately rescaled, graph cut between the vertices in Ω and the vertices in
D\Ω. We obtain bias and variance estimates on the error, which are optimal in scaling with
respect to n and ε. We consider two scaling regimes: the dense (when the average degree of
the vertices goes to ∞) and the sparse one (when the degree goes to 0). In the dense regime
there is a crossover in the nature of approximation at dimension d = 5: we show that in
low dimensions d = 2, 3, 4 one can obtain confidence intervals for the approximation error,
while in higher dimensions one can only obtain error estimates for testing the hypothesis
that the perimeter is less than a given number.

1. I NTRODUCTION
This paper investigates the use of random-graph cuts to obtain empirical estimates of
the perimeter of a domain Ω ⊂ D := (0, 1)d for d ≥ 2. Let x1 , . . . , xn , . . . denote a
sequence of independent random points uniformly distributed on the unit cube D and let
Vn := {x1 , . . . , xn }.
The problem of estimating the perimeter of Ω based on knowing which points of Vn
belong to Ω is a classical question, see [4, 8, 9, 17, 23, 24] for recent contributions, and see
Subsection 1.2 below which contains a discussion about related work. Here we consider an
estimator of the perimeter that is based on a geometric graph constructed from the point
cloud Vn . More precisely, we select εn > 0, and connect two points in the cloud if they are
within distance εn of each other; then we consider an appropriately scaled ‘cut’ determined
by the number of edges in the graph that connect points in Ω with points that belong to
Ωc . This type of estimator is natural to consider, since graph cuts arise as a discretization
of the perimeter in many applications such as clustering [3, 7, 14, 15, 18, 25, 26, 27, 28].
Our choice of the estimator is therefore based on its use in various statistical and machine
learning applications.
We focus on estimating the approximation error of the perimeter of an arbitrary (but
fixed) set Ω; the error estimates that we obtain are uniform on a class of sets where certain
geometric quantities are controlled (see Remark 1.7 below). One of the important features
of our estimator is that it has a small bias. Indeed, the expectation of our estimator provides
a second order approximation (in terms of the natural parameter εn ) of the true perimeter of
Ω under some regularity conditions on the boundary of the set (see (8) below); this turns
out to be a sharp estimate for the bias. We also obtain precise estimates for the variance
of the estimator; for these estimates to hold, we do not need any regularity assumptions
Date: August 16, 2016.
Key words and phrases. perimeter, nonparametric estimation, graph cut, point cloud, random geometric graph,
concentration inequality.
1

2

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

on the boundary of the set Ω except that it has finite perimeter in the most general sense.
Furthermore, we show that our estimator converges a.s. for remarkably sparse graphs (and
indeed in settings which are sparser than for previously considered estimators). The a.s.
convergence holds with no regularity assumptions on Ω (other than the fact that it has finite
perimeter in the most general sense). Finally, assuming some smoothness on the boundary
1
of Ω, we are able to establish (in the dense graph regime n1/d
 ε  1) the asymptotic
distribution of the error. These estimates lead to asymptotic confidence intervals (which
we refer to simply as confidence intervals) and bounds on the type I and type II errors for
hypothesis tests associated to the perimeter of a set.
1.1. Set-up and main results. Let us now be more precise about the setting we consider
in this paper. We consider random geometric graphs with vertex set Vn and radius εn > 0.
That is, graphs where xi and xj are connected by an edge if ||xi − xj || ≤ εn . The graph
cut between A ⊆ Vn and Ac is given by
X X
Cutεn (A, Ac ) :=
1{kxi −xj k≤εn } .
xi ∈A xj ∈V \A

We define the graph perimeter as a rescaling of the graph cut: For any Ω ⊆ D
2
(1)
GPern,εn (Ω) :=
Cut(Vn ∩ Ω, Vn ∩ Ωc ).
n(n − 1)εd+1
n
See Figure 1 for an illustration of this construction. The scaling is chosen so that GPern,εn (Ω)
becomes a consistent estimator for the true (continuum) perimeter.

Ω

Ωc

F IGURE 1. Edges of the cut between Ω and Ωc are represented by bold
lines, while other edges are dashed lines. Total number of vertices is
n = 200 and connectivity radius ε = 0.13.
One of our interests lies in determining how well does GPern,εn (Ω) estimate the relative
perimeter of Ω in D. We first investigate for which scaling of εn on n does the convergence

ESTIMATING PERIMETER USING GRAPH CUTS

3

hold almost surely as n → ∞. In other words, we want to understand the relation between
edge-sparsity of random geometric graphs and point-wise convergence of the graph perimeter to the continuum perimeter in the almost sure sense. We consider this question for a very
broad family of sets Ω ⊂ D, which are only assumed to have finite relative perimeter in D
in the general sense of [2]. That is, we define the relative perimeter of Ω with respect to D
to be
Z

∞
d
(2)
Per(Ω) = sup
div(v) dx : (∀x ∈ D) kv(x)k ≤ 1, v ∈ Cc (D, R ) .
Ω

If Ω has a smooth relative boundary then Per(Ω) is nothing but the surface area of ∂Ω ∩ D.
We remark that the notion of the perimeter we use is more general than the notion of
Hausdorff measure of the boundary, Hd−1 (∂Ω ∩ D), and than the Minkowski content,
which are the ones more typically used in the statistics literature [4, 8, 9]. In particular, as
we see below, we work with consistent nonparametric estimators in the most general setting
available.
As we recall below in (17 –19), it is known that when εn → 0 as n → ∞ then the bias
of the estimator vanishes in the limit:
(3)

E(GPern,εn (Ω)) → σd Per(Ω)

as

n → ∞.

The scaling factor σd satisfies
Z
(4)

|z1 | dz =

σd :=
||z||≤1

2sd−2
,
(d + 1)(d − 1)

where z1 denotes the first component of the vector z ∈ Rd and sd−2 is the area of the
(d − 2)-dimensional unit sphere (the boundary of the unit ball in Rd−1 ). We refer to the
normalizing quantity σd as the surface tension.
We obtain the following estimates on the deviation of the graph perimeter GPern,εn (Ω)
from its mean. Let

1
1
 √nε
if n1/d
≤ εn
n
(5)
f (n, εn ) :=
1
1
1
 (d+1)/2
if n2/(d+1)
≤ εn ≤ n1/d
.
nεn

Theorem 1.1. Let p ≥ 1 and let Ω ⊆ D be a set with finite perimeter. Assume εn → 0 as
n → ∞. Then,
(6)

E(| GPern,εn (Ω) − E(GPern,εn (Ω))|p ) ≤ Cp,d (max{1, Per(Ω)}f (n, εn ))p

where Cp,d is a constant that depends only on p and dimension d. In particular, if
2
n− (d+1)  εn  1, then
GPern,εn (Ω) → σd Per(Ω), almost surely as n → ∞.

The last part of the previous theorem follows from (3), the moment estimates (6),
Markov’s inequality, and Borel-Cantelli Lemma which imply that
GPern,εn (Ω) − E (GPern,εn (Ω)) → 0

a.s.

Remark 1.2. We note that the a.s. convergence holds for rather sparse graphs (see Figure 2).
Namely the typical degree of a node is ωd nεd , where ωd is the volume of the unit ball in d
2
1
dimensions. When n− (d+1)  εn  n− d the a.s. convergence holds, while the average

4

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

(a) n = 400 and ε = 0.045

(b) n = 1000 and ε = 0.027

F IGURE 2. Here we illustrate the “sparse” regime when 1/n1/d  ε 
(1/n)2/d+1 when the average degree goes to zero. Nevertheless since the
number of edges in the cut still increases as n does the convergence of
the cut to the perimeter still holds.
degree of a vertex converges to zero. The convergence is still possible because the expected
number of edges crossing ∂Ω is still a quantity converging to infinity.
Remark 1.3. Given that we show the almost-sure consistency of our estimators for any
arbitrary (but fixed) set for which the perimeter is finite, our construction provides a universal
strongly convergent estimator which was the desired property listed as an open problem in
[8] (for the estimator they considered).
We turn to estimating the bias of the empirical approximation: |E(GPern,εn (Ω)) −
σd Per(Ω)|. We first characterize the mean of the graph perimeter, E(GPern,εn (Ω)), as the
non-local perimeter Perεn (Ω) of Ω, defined as
Z Z
2
(7)
Perε (Ω) := d+1
1{kx−yk≤ε} dxdy.
ε
Ω D\Ω
The non-local nature of the functional essentially has to do with the fact that it involves
averages of finite differences as opposed to a local approach where one considers derivatives.
We then proceed to estimate |Perεn (Ω) − σd Per(Ω)| explicitly. It proves straightforward
to check that |Perεn (Ω) − σd Per(Ω)| = O (εn ) for general subsets Ω ⊆ D with smooth
relative boundary. However, we show that the error is actually quadratic in εn
(8)

|E(GPern,εn (Ω)) − σd Per(Ω)| = |Perεn (Ω) − σd Per(Ω)| = O(ε2n )

under the extra condition that dist(Ω, ∂D) > 0. This is the content of the next lemma,
whose proof may be found in Appendix A.
Lemma 1.4. Let Ω be a set with smooth boundary, such that dist(Ω, ∂D) > 0. Let
0 < ε < dist(Ω, ∂D) and let Perε (Ω) be defined by (7). Then
(9)

Perε (Ω) = σd Per(Ω) + O(ε2 ).

ESTIMATING PERIMETER USING GRAPH CUTS

5

Remark 1.5. The assumption dist(Ω, ∂D) > 0 in the above Lemma is needed in order to
obtain bias of order ε2 . If Ω touches the boundary ∂D the error of order ε2 is not expected, as
can be seen for example by considering the rectangle Ω := {x = (x1 , . . . , xd ) ∈ D : x1 ≤ 1/2},
for which the error is of order ε; in this situation the error is completely due to the region
where ∂Ω meets ∂D transversally. Thus, in general, for Ω ⊆ D with smooth relative
boundary, the bias is of order ε. On the other hand, the smoothness of the boundary of Ω is
only needed in the previous lemma to guarantee that curvature and its derivatives are well
defined. Finally, the constant involved in the term O(ε2 ) depends on the reach of the set
Ω, and the intrinsic curvature of ∂Ω together with its derivatives; this can be seen from our
computations in Appendix A.
Combining the bias and variance of estimates allows us to obtain the rates of convergence
for the error |GPern,εn (Ω) − σd Per(Ω)|. In particular we estimate the ‘standard deviation’
1/2
std(n) := E (GPern,εn (Ω) − σd Per(Ω))2
,
which we may quantify precisely by using the variance-bias decomposition
2

std2 (n) = Var(GPern,εn (Ω)) + (E(GPern,εn (Ω)) − σd Per(Ω)) .
Using the special case p = 2 of Theorem 1.1 to estimate the variance and using Lemma 1.4
to estimate the bias we obtain the following.
2

Theorem 1.6. Let Ω ⊂ D be an open set with smooth boundary. Assume n− d+1 
εn  1 and consider f (n, εn ) defined via (5). The error of approximating σd Per(Ω) by
GPern,εn (Ω) satisfies
std(n) = O(f (n, εn ) + εn ).
If we furthermore assume that Ω does not touch the boundary of D, that is dist(Ω, ∂D) > 0,
then a better estimate holds:
std(n) = O(f (n, εn ) + ε2n ).
A simple calculation using (5) allows one to choose a scaling of εn on n so that the error
of the approximation is as small as possible. In particular, for a set Ω which touches the
boundary (dist(Ω, ∂D) = 0) the optimal scaling of εn is
(
(
n−1/3
if d ≤ 3
n−1/3
if d ≤ 3
εn ∼
giving
std(n)
=
−2/(d+3)
−2/(d+3)
n
if d ≥ 3
n
if d ≥ 3.
We note that for d < 3 the optimal εn is achieved in the regime n−1/d . εn  1, while if
d > 3 it is in the sparse regime. If we consider sets Ω with smooth boundary but such that
dist(Ω, ∂D) > 0, then the optimal scaling of εn on n is as follows
(
(
n−2/5
if d ≤ 5
n−1/5
if d ≤ 5
εn ∼
giving
std(n)
=
−4/(d+5)
−2/(d+5)
n
if d ≥ 5
n
if d ≥ 5.
Again we note that the optimal εn is in the sparse regime if d > 5. This has implications to
how well is the perimeter estimated by graph cuts in the graphs considered in most machine
learning applications. Namely if d ≥ 5 and the graph has average degree bounded from
below, that is when n−1/d . εn  1, then, since the bias bound is sharp, most of the error
is due to the bias term.

6

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

Remark 1.7. The constant appearing in the moment estimates of Theorem 1.1 depends
exclusively on the power p, the dimension d, and the true perimeter of the set Ω; in
particular, taking p = 2 we see that the estimates for the variance of GPern,εn (Ω) are
uniform on the class of sets Ω whose perimeter is bounded above by some fixed constant.
For general sets with large perimeter we obtain uniform estimates for moments of relative
error | GPern,εn (Ω) − E(GPern,εn (Ω))|/ Per(Ω) instead of the absolute error. Thus, by
combining Theorem 1.1 and the proof of Lemma 1.4 one can derive that the corresponding
error estimates for |GPern,εn (Ω) − σd Per(Ω)| (either relative or absolute) are uniform on
the class of sets Ω with smooth boundary satisfying the following conditions: The reach
of Ω is bounded below by a fixed positive constant; The distance to the boundary ∂D is
bounded below by a fixed positive constant; The curvature and first derivatives of curvature
are bounded from above by a fixed constant. This last requirement comes from the O(ε2 )
terms following Taylor’s theorem in the proof of our bias estimates.
We now consider obtaining confidence intervals for the value of the true perimeter Per(Ω)
based on the estimator σ1d GPern,εn (Ω). We focus on the dense regime (See Figures 3
1
and 4), n1/d
 εn  1, and first obtain the asymptotic distribution of GPern,εn (Ω) −
E(GPern,εn (Ω)).

(a) n = 100, ε = 0.17

(b) n = 300 and ε = 0.12

F IGURE 3. Here we illustrate the “very dense” regime, 1  ε 
(ln(n)/n)1/d , when the graphs are connected with high probability.
Since the term E (GPern,εn (Ω)) = Perεn (Ω) depends on the set Ω itself, which is
unknown (we only assume we have an oracle access to it), we need the bias to be negligible
compared to the standard deviation of our estimator. This allows us to construct confidence
intervals for Per(Ω) without using any additional information about the bias (e.g. upper
1
bounds). From (6) the standard deviation of GPern,εn (Ω) scales as √nε
while by (8) the
n
2
bias scales as εn ; these estimates lead to restrictions on the dimensions for which the bias is
negligible with respect to the standard deviation. Namely this is possible for d = 2, 3, and
4.

ESTIMATING PERIMETER USING GRAPH CUTS

(a) n = 100 and ε = 0.12

7

(b) n = 400 and ε = 0.07

F IGURE 4. Here we illustrate an intermediate, ”dense”, regime
(ln(n)/n)1/d  ε  (1/n)1/d . The average degree still increases,
but the graphs are disconnected with high probability.

Theorem 1.8. Let Ω ⊆ D be an open set with smooth boundary such that dist(Ω, ∂D) > 0.
Let εn be such that
1
 εn  1
1/d
n
Then,
r
nεn
w
(GPern,εn (Ω) − Perεn (Ω)) −→ N (0, 1),
4Cd Per(Ω)
where Cd is given by
Z 1

2
(10)
Cd := 2
Bd (0, 1) ∩ x = (x1 , . . . , xd ) ∈ Rd : xd ≥ t
dt.
0

If in addition the dimension d is either 2, 3 or 4 and if
1

(11)

n1/d

 εn 

1
n1/5

then,
r
(12)

nεn
w
(GPern,εn (Ω) − σd Per(Ω)) −→ N (0, 1).
4Cd Per(Ω)

Naturally, the previous theorem implies that one can obtain confidence intervals for the
value of Per(Ω) when the dimension d is 2, 3 or 4. Let us fix α ∈ (0, 0.5) and let Zα be the
1 − α quantile of the standard normal distribution. That is, Zα is such that
P (N (0, 1) ≤ Zα ) = 1 − α.
Then provided that
1
n1/d

 εn 

1
n1/5

,

8

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

+
it follows that with probability converging to 1 − α, Per(Ω) ∈ (a−
n , an ), where
s
4Cd Per(Ω)
1
a±
(GPern,εn (Ω) ±
Zα/2 ).
n :=
σd
nεn

For d ≥ 5, the confidence intervals can not be obtained unless one has some extra quantitative information on the smoothness of ∂Ω, such as curvature bounds or upper bounds on the bias. Nevertheless, since it is known that the nonlocal perimeter
Perεn (Ω) = E(GPern,εn (Ω)) is less than σd Per(Ω) (see (30)), one can construct a test for
the hypothesis that Per(Ω) is less than a certain number ρ without using any quantitative
estimates on the smoothness of ∂Ω. In this case, we have automatic upper bounds for the
bias and may consider the hypothesis testing of
(13)

H0 : Per(Ω) ≤ ρ,

vs HA : Per(Ω) > ρ,

based on our estimator GPern,εn (Ω). We consider the statistic:
r
nεn
(14)
ln :=
(GPern,εn (Ω) − σd ρ) .
4Cd ρ
The test consists on
(15)

Accept H0 if ln ≤ Zα ,

Proposition 1.9. Assume d ≥ 2 and

1
n1/d

reject otherwise.

 εn  1. Then, the type I error satisfies

lim sup PH0 (ln > Zα ) ≤ α,
n→∞

i.e., the type I error is asymptotically below α. The type II error satisfies


1
PHA (ln ≤ Zα ) = O √
.
nεn
Remark 1.10 (Extensions). The estimates obtained in Theorem 1.1 and Theorem 1.6 are
not exclusive to the case where the points are uniformly distributed in the unit cube and
to geometric graphs. In fact, with slight modifications to the proofs of Theorem 1.1 and
Theorem 1.6, we can extend these results to more general situations. For example, if the
data points are distributed according to some smooth density p that is supported on a regular,
bounded domain D ⊂ Rd with p bounded below and above by positive constants, then the
results still hold. In this case, the limiting value of GPern,εn (Ω) is a weighted perimeter
Per(Ω, p2 ) (see for example [10]). Convergence is guaranteed for the same scaling for εn
as in the uniform case. The fact that the weight is p2 and not p (as may be a priori expected)
ultimately comes from the fact that a graph cut is a double sum.
Furthermore if instead of weights 1{kxi −xj k≤εn } in the definition of the graph cut,
one considers edge weights η(kxi − xj k/εn ) where η is nonnegative, integrable and nonincreasing, the results still hold, provided we change the surface tension σd with a surface
tension associated to η defined as in [10].
Remark 1.11. The previous results allow us to construct asymptotic confidence intervals
for Per(Ω) for an arbitrary set Ω with smooth boundary and dist(Ω, ∂D) > 0, using the
estimator GPern,εn (Ω). Nevertheless, since very small sets (in the sense of volume) may
have very large perimeter the error estimates are not uniform in Ω and thus the asymptotic
confidence intervals may not be of direct practical use. This issue is unavoidable without
further assumptions on the set Ω or a change of framework for testing. One possible way

ESTIMATING PERIMETER USING GRAPH CUTS

9

to restrict the class of Ω considered is pointed out in Remark 1.7. In the class of sets Ω to
which Remark 1.7 applies, the error of approximation is uniformly controlled.
Alternatively, one may consider the property testing framework used in [23, 21], where
one could test the property “the set Ω is close to a set whose perimeter is less than ρ” reliably.
In that framework we would not be using the estimator GPern,εn (Ω) to test whether Per(Ω)
is below ρ or not, but rather whether Ω is close to a set whose perimeter is below ρ or not.
We notice that in this paper we have taken the classical hypothesis testing approach.
Outline. In Subsection 1.3 we establish (3) and give an outline of the argument behind
our main results. We present the proof of Theorem 1.1 in Section 2, while in Subsection
2.1 we show that the scaling is sharp (up to logarithmic corrections) in the sense that
if n2 εd+1
→ 0 then GPern,εn (Ω) converges in probability to zero and hence does not
n
converge almost surely to the (rescaled) relative perimeter. In Section 3 we prove the results
on the asymptotic distribution of the error stated in Theorem 1.8. In Subsection 3.1 we study
the type I and type II errors of the hypothesis test of Proposition 1.9. Finally, Appendix A
deals with the bias estimate from Lemma 1.4.
1.2. Discussion. Here we discuss the connections between our work and related works
in the literature. First we relate it to other estimators of perimeter based on a random
sample. Then we contrast the type of the convergence and the scaling regimes considered in
this paper with the ones needed for the convergence of graph-cut based machine learning
algorithms for clustering and related tasks.
The problem of estimating the perimeter of a set, Ω, based on knowing which points
of a random sample Vn belong to Ω, has been considered by a number of works. Cuevas,
Fraiman, and Rodrı́guez-Casaet [9], considered estimators of the Minkowksi content, which
agrees with perimeter for regular enough sets, but is a less general notion of the perimeter
than the one we consider, (2). Their estimator is based on counting the vertices near the
boundary (relative to a parameter εn ), while we “count” edges of a graph. The error bound
obtained was of order O(n−1/2d ). Pateiro-López and Rodrı́guez-Casal [24] consider a
similar estimator and improve the bounds to O((ln n/n)1/(d+1) ) under qualitative regularity
conditions (rolling ball conditions). Cuevas, Fraiman, and Györfi [8], obtain the convergence
of estimators similar to those of [9], when εn  1/n1/d and under weaker conditions on
the regularity of Ω, although still not in the full generality we consider in this paper.
Armendáriz, Cuevas, and Fraiman [4] consider a similar set-up to that in [9, 24] but
with different sampling rates for Ω and Ωc : let n denote the number of sample points in
Ω and k the number of sample points in Ωc . Under mild assumptions on the regularity
of ∂Ω, and under some conditions on n and k which include 1  εn,k  (1/n1/3 ) and
k  (n/εn,k )d/2 they obtain the asymptotic distribution of the error, under the same
scaling in n and ε that we consider in Theorem 1.8. We notice that our estimator is different,
and also that in [4] a very large number of points k in Ωc is needed for the consistency
to hold. This allows the authors to obtain the asymptotic distribution of the total error
in any dimension, while in our setting we only obtain it in low dimensions. A further
difference between their work and ours, is that we allow for a wider range in ε, namely
1  εn  (1/n)2/(d+1) .
Jiménez and Yukich [17] give a different use to the point cloud and instead of considering
a parameter ε to count points close to the boundary of the set or to define a geometric graph,
they consider a new estimator based on the Delaunay triangulation induced by the cloud.
They obtain results not only on estimating the perimeter of the set, but also integrals of
functions over ∂Ω.

10

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

Kothari, Nayyeri, and O’Donnell [21] and Neeman [23] consider an estimator essentially
based on the following procedure: pick n random points uniformly distributed on D and to
each point associate a random direction for a ‘needle’ based at the point with length of order
√
εn ; then count how many of the needles touch the boundary of Ω. Their main motivation
is to consider the perimeter estimation from the viewpoint of property testing as introduced
in [19]. In that setting, the idea is to produce an algorithm that requires a small number
of samples (essentially independent of the dimension d) in order to determine if a given
set has a small perimeter or is ‘far away’ from a set that has small perimeter. The authors
show completeness and soundness of the test they design (the notion of completeness and
soundness is as in [19, 21]). The notion of testing used in their work is one of the main
differences with our work since we consider the perimeter testing in the more classical
framework of hypothesis testing (Proposition 1.9). We note that the completeness of [21] is
analogous to the type I error, but the soundness is fundamentally different from estimating
the type II error.
It is also worth mentioning the work of Belkin, Narayanan and Niyogi [5] where they
consider an algorithm that requires as few samples as possible in order to estimate the
perimeter of a convex body. Their results show that there is an algorithm that uses O(d4 γ −2 )
samples to obtain an estimator for the true perimeter of the convex set, with an error of
approximation of γ; this statement holds with high probability. We notice the polynomial
dependence on dimension in their estimates.
Let us now contrast the type of the convergence and the scaling regimes that we consider
in this paper with the ones needed for the convergence of graph-cut based machine learning
algorithms for clustering and related tasks.
Graph-cut based algorithms for tasks such as clustering have played an important role in
machine learning [3, 7, 14, 15, 18, 25, 26, 27, 28]. Data clustering algorithms are called
consistent if as the sample size n → ∞ their outputs converge to a desired partitioning of
the underlying measure being sampled. It is of interest to understand under what scaling
of εn on n does the consistency hold. Here we showed that for a fixed set Ω the value of
graph perimeter (and indeed of the graph-cut-based objective functionals such as Cheeger,
ratio, or normalized cuts) converges to the perimeter of Ω; this result holds even for rather
sparse graphs (Theorem 1.6). In particular, partitioning such sparse graphs (as on Figure
2) does not provide almost any information about the clusters present in the data. We
conclude that the convergence of the graph perimeter of a fixed set towards the continuum
perimeter does not provide the needed information on the asymptotic properties of graphcut based clustering algorithms. To obtain consistency of such algorithms one needs a
stronger notion of convergence of graph based functionals towards continuum functionals.
Recently the authors [10], and together with Laurent and Bresson [11] have developed the
appropriate notion of convergence (based on Γ-convergence from the calculus of variations),
and have applied it to consistency of Cheeger, ratio, sparsest, and normalized cut based
point cloud clustering. More specifically, in [11] it is shown that consistency holds if
(log(n))1/d
 ε  1 (for d ≥ 3), in that regime the graphs are connected with high
n1/d
probability as n → ∞.
1.3. Outline of the argument. In order to understand the asymptotic behavior of the graph
perimeter, following [3] we first define a symmetric kernel φε : D × D → (0, ∞) by
φεn (x, y) =

1{||x−y||≤εn }
εd+1
n

|1Ω (x) − 1Ω (y)|.

ESTIMATING PERIMETER USING GRAPH CUTS

11

Using the kernel φεn , we can then write GPern,εn (Ω) as
(16)

n
n
X
X
2
GPern,εn (Ω) =
φε (xi , xj ),
n(n − 1) i=1 j=i+1 n

which is a U-statistic in the terminology of [16]. A simple computation shows that the mean
of this U -statistic, is the non-local perimeter Perε (Ω) defined in (7), that is,
Z Z
(17)
E(GPern,εn (Ω)) = Perεn (Ω) =
φε (x, y) dxdy.
D

D

Additionally, Remark 4.3 in [10] establishes that the non-local perimeter Perεn (Ω) approaches a constant multiple of the relative perimeter of Ω as the parameter εn goes to zero.
More precisely, if εn → 0 as n → ∞ then
(18)

Perεn (Ω) → σd Per(Ω)

as n → ∞

for σd the surface tension (4). This convergence also follows from the estimates in Appendix
A in the special case that Ω has a smooth boundary. Combining (18) with (17) we conclude
that if εn converges to zero as n → ∞ then
(19)

E(GPern,εn (Ω)) → σd Per(Ω)

as n → ∞.

Since the graph perimeter GPern,εn (Ω) is a U -statistic of order two we can use the general
theory of U -statistics to obtain moment estimates for GPern,εn (Ω). Let us first note that
Hoeffding’s decomposition theorem for U -statistics of order two (see [20]) implies that
GPern,εn (Ω) can be written as:
(20)

GPern,εn (Ω) − Perεn (Ω) = 2Un,1 + Un,2 ,

where Un,1 is a U-statistic of order one ( just a sum of centered independent random
variables) and Un,2 is a U-statistic of order two which is canonical or completely degenerate
(see [20]). In order to define the variables Un,1 and Un,2 , let us introduce the functions
Z
φ̄εn (x) :=
φεn (x, z) dz,
x ∈ D,
D

(21)

gn,1 (x) := φ̄εn (x) − Perεn (Ω),

x ∈ D,

gn,2 (x, y) := φεn (x, y) − φ̄εn (x) − φ̄εn (y) + Perεn (Ω),

x, y ∈ D.

With the previous definitions, we can now define
n

Un,1 =
(22)
Un,2 =

1X
gn,1 (xi ),
n i=1
X
2
n(n − 1)

gn,2 (xi , xj ).

1≤i<j≤n

R
R
We remark that D gn,1 (z)dz = 0 and that D gn,2 (x, z)dz = 0 for all x ∈ D. Because
of this, Un,1 and Un,2 are said to be canonical statistics of order one and two respectively
(see [20]). Now, Bernstein’s inequality [6] implies that
Cp
p 
,
(23)
E(|Un,1 |p ) ≤ p max Apn,1 , Bn,1
n
where
√
(24)
An,1 := ||gn,1 ||∞ , Bn,1 := n||gn,1 ||2 .

12

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

and Cp is a universal constant. See also [12] for a slight generalization of the previous
result.
On the other hand some of the moment estimates in [12] for canonical U -statistics of
order two can be used to prove that
(25)

E (|Un,2 |p ) ≤

Cp
p 
p
, Cn,2
,
max Apn,2 , Bn,2
2p
n

where
(26)

An,2 := ||gn,2 ||∞ ,

Bn,2 := n||gn,2 ||2 ,

(Cn,2 )2 := n||

Z

2
gn,2
(·, y) dy||∞ .

D

and Cp is a universal constant. From the decomposition (20) it follows that for p ≥ 1
E (| GPern,εn (Ω) − Perεn (Ω)|p ) ≤ Cp (E (|Un,1 |p ) + E (|Un,2 |p )).
Thus in order to obtain the moment estimates for GPern,εn (Ω) in Theorem 1.1, we focus
on finding estimates for the quantities in (24) and (26).
Remark 1.12. The estimates on Un,1 and Un,2 exhibit a crossover in the nature when the
1
1
 εn  n1/d
parameter εn transitions between the sparse ( n2/(d+1)
) and the dense regime
1
( n1/d  εn  1). From the theory of U -statistics the crossover in the nature of the bounds,
is connected to the different nature of the two components in the canonical decomposition
for U -statistics. Under the dense regime the biggest source of error comes from the term
Un,1 while in the sparse regime the biggest source of error comes from the term Un,2 . The
two variables Un,1 and Un,2 exhibit a different nature. In fact, one can think that Un,1
is a global quantity as it is the sum of averages, while Un,2 is simply the sum of pure
interactions concentrating on the boundary of the set Ω. We believe that there is a deeper
geometric and analytic reason for the scaling of the error that appears in the sparse regime
1
1
( n2/(d+1)
 εn  n1/d
). Moreover, we believe that such understanding would allow us to
complete the study of the asymptotic distribution in Theorem 1.8 for the sparse regime. We
expect such distribution to be of the Gaussian chaos type.
The bias estimates in Appendix A are obtained by a series of computations whose
starting point is writing Perε (Ω) in terms of an iterated integral, the outer one taken over
the manifold ∂Ω and the inner one taken along the normal line to ∂Ω at an arbitrary point
x ∈ ∂Ω. Such computations show that the first order term of Perεn (Ω) on εn vanishes.
Finally, Theorem 1.8 is obtained by using the canonical decomposition of U -statistics
1
and by noticing that in the dense regime n1/d
 εn  1, the variable Un,2 is negligible in
relation to Un,1 . We make use of the CLT for triangular arrays after computing the variances
of the involved variables.
2. P ROOF OF T HEOREM 1.1
We first compute the moments of Un,1 and so we start computing the quantities An,1
and Bn,1 from (24). Denote by Tε the ε-tube around ∂Ω, that is, consider the set

(27)
Tε := x ∈ Rd : dist(x, ∂Ω) ≤ ε .
We also consider the half tubes Tε− and Tε+ ,
(28)

Tε− := {x ∈ Ω : dist(x, ∂Ω) ≤ ε} ,

Tε+ := {x ∈ Ωc : dist(x, ∂Ω) ≤ ε} .

ESTIMATING PERIMETER USING GRAPH CUTS

With these definitions it is straightforward to check that

d+1

 |Bd (x, εn ) ∩ Ω|/εn
c
(29)
φ̄εn (x) = |Bd (x, εn ) ∩ Ω |/εd+1
n


0

13

if x ∈ Tε+n
if x ∈ Tε−n
if x 6∈ Tεn .

Since |Bd (x, εn ) ∩ Ω| and |Bd (x, εn ) ∩ Ωc | are bounded by αd εdn , where αd is the volume
of the d-dimensional unit ball, we deduce that
 
1
An,1 = O
.
εn
In order to compute the quantity Bn,1 we use the following lemma, whose proof may be
found in Appendix B.
Lemma 2.1. Let p ≥ 1 and let Ω ⊆ D, be a set with finite perimeter. Then, for all ε > 0
we have
Z
αp−1 σd
φ̄pεn (x)dx ≤ dp−1 Per(Ω).
ε
D
In particular, taking p = 1 in the previous expression, we obtain
Perε (Ω) ≤ σd Per(Ω).

(30)

 
R
Using the previous lemma with p = 2 we deduce that D φ̄2εn (x)dx = O ε1n , and
since
Z
Z
2
2
gn,1 (x)dx =
φ̄2εn (x)dx − (Perεn (Ω)) ,
D

D

we conclude that
r
Bn,1 = O

n
εn


.

From the previous computations, we deduce that
p



p

E(|Un,1 | ) ≤ Cp,d max{1, Per(Ω)} max

1
1
p ,
p
n εn , np/2 εp/2
n

where Cp,d depends on p and d, but is independent of the set Ω. If
in particular nε1n is o(1), then
(31)

E(|Un,1 |p ) ≤

Cp,d max{1, Per(Ω)}p
p/2

np/2 εn



1
n2/(d+1)

,
≤ εn , so that

.

R
Remark 2.2. Later on, in Lemma 3.1, we provide an explicit computation of D φ̄2εn (x)dx
up to order ε1n , which is useful when studying the asymptotic distribution of a rescaled
version of Un,1 .
Now we turn to the task of obtaining moment estimates for Un,2 . We estimate the
quantities An,2 , Bn,2 and Cn,2 from (26). Let us start by estimating An,2 . Note that for
any (x, y) ∈ D × D, φ̄εn (x) and φ̄εn (y) are of order ε1n and that Perεn (Ω) is of order one.
Thus, it is clear from the definition of gn,2 in (21) that


1
An,2 = O
.
εd+1
n

14

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

1
φεn (x, y), we obtain that for every x ∈ D,
On the other hand, using φ2εn (x, y) = εd+1
n
Z
Z
2
gn,2
(x, y)dy =
φ2εn (x, y)dy − φ̄2εn (x) + 2θn φεn (x)
D
D
Z
Z
− 2 φεn (x, y)φ̄εn (y)dy +
φ̄2εn (y)dy − θn2
D
D
(32)
1
= d+1 φ̄εn (x) − φ̄2εn (x) + 2θn φεn (x)
εn
Z
Z
−2
φεn (x, y)φ̄εn (y)dy +
φ̄2εn (y)dy − θn2 ,
D

D

where we are using θn := Perεn (Ω). From this, it follows that

r
n
Cn,2 = O
.
εd+2
n
Finally, upon integration of (32) and direct computations, we obtain
Z
θn
2
||gn,2 ||2 = d+1 − 2
φ̄2εn (y)dy + θn2 ,
εn
D
which implies that


n
Bn,2 = O
.
(d+1)/2
εn
Thus, from (25) we deduce that


1
1
1
p
E(|Un,2 | ) ≤ Kp,d max
,
,
,
p(d+1)
p(d+1)/2
p(d+2)/2
n2p εn
np εn
n3p/2 εn
where Kp,d = Cp,d (max{1, Per(Ω)})p for Cp,d some constant that does not depend on the
1
set Ω. Hence, if n2/(d+1)
≤ εn , we have
E(|Un,2 |p ) ≤

(33)

Kp,d
p(d+1)/2
np εn

.

Combining (31) and (33) and using the canonical decomposition (20), we obtain (6).
2.1. Sharpness of the Rate in Theorem 1.1. A very simple argument shows that the rates
for εn that guarantee the almost sure convergence of the graph perimeter to the actual
perimeter in Theorem 1.1 are optimal in terms of scaling, up to logarithmic corrections.
In fact, suppose n2 εd+1
= o(1) and let en denote the random variable that counts the
n
number of edges that cross in the interface between Ω and its complement. In other words,
we define
n
n
X
X
en := εd+1
φεn (xi , xj ).
n
i=1 j=i+1

As a consequence, if Ω has finite perimeter then we have
(34)

GPern,εn (Ω) =

2
en ,
n(n − 1)εd+1
n

E(en ) =

n(n − 1)εd+1
n
Perεn (Ω).
2

Note that en takes integer values in the range {0, 1, . . . , N } for N = n(n − 1)/2, so
that
N
X
E(en ) =
kpnk
pnk := P(en = k).
k=1

ESTIMATING PERIMETER USING GRAPH CUTS

15

The fact that pn0 + · · · + pnN = 1 implies
E(en ) =

N
X

kpnk ≥

k=1

N
X

pnk = (1 − pn0 ).

k=1

In particular, from (34) and (18) we deduce that if n2 εd+1
→ 0 and Ω has finite perimeter
n
then
(1 − pn0 ) ≤ E(en ) = o(1).
On the other hand, note that for any given γ > 0 it is true that GPern,εn (Ω) > γ implies
that en 6= 0. In turn
P (GPern,εn (Ω) > γ) ≤ P (en 6= 0) = 1 − pn0 = o(1).
We conclude that if n2 εd+1
→ 0 then GPern,εn (Ω) converges in probability to zero.
n
Therefore, if Ω has a non-zero, finite perimeter then GPern,εn (Ω) does not converge to
σd Per(Ω) in probability (nor almost surely, either).
3. P ROOF OF T HEOREM 1.8
The proof of Theorem 1.8 relies on the following lemma, whose proof may be found in
Appendix C.
Lemma 3.1. Asssume that εn → 0 as n → ∞, and that Ω ⊂ D is an open set with smooth
boundary so that dist(Ω, ∂D) > 0. Then
(35)

Var(gn,1 (X1 )) =

Cd Per(Ω)
+ O(1),
εn

where Cd is given by (10).
Now we turn our attention to the proof of Theorem 1.8.
Proof of Theorem 1.8. Note that from (20), (21) and (22) we obtain
r
r
n
X
nεn
εn
(GPern,εn (Ω) − Perεn (Ω)) =
gn,1 (xi )
4Cd Per(Ω)
nCd Per(Ω) i=1
r
nεn
+
Un,2 .
4Cd Per(Ω)
From the moment estimates (33), we deduce that
r
nεn
P
(36)
Un,2 → 0.
4Cd Per(Ω)
On the other hand, we note that from (35)
√
std(gn,1 (x1 )) εn
p
→ 1,
Cd Per(Ω)

as n → ∞,

where std(gn,1 (x1 )) is the standard deviation of gn,1 (x1 ). Lyapunov’s condition which is
sufficient to allow us to use the central limit theorem for triangular arrays is easily checked
from Lemma 2.1. We deduce that
r
n
X
εn
w
gn,1 (Xi ) −→ N (0, 1).
nCd Per(Ω) i=1

16

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

Combining with (36) and the Slutsky’s theorem, we obtain the desired result. Finally, to
obtain the last statement in the theorem, we note that from the bias estimates in Lemma 1.4,
√
nεn | Perεn (A) − σd Per(A)| = O(n1/2 ε5/2
n )
√
Under the condition (11), we conclude that nεn | Perεn (A) − ση Per(A)| → 0. This
implies (12).

3.1. Application to Perimeter Testing. Here we prove Proposition 1.9. We assume that
Ω ⊆ D is an open set with smooth boundary such that Ω ⊂ D. Note that under the null
hypothesis, if ln > Zα , then,
r
nεn
(37)
Zα < ln ≤
(GPern,εn (Ω) − Perεn (Ω)) ,
4Cd Per(Ω)
where we used that Perεn (Ω) ≤ σd Per(Ω) by Lemma 2.1. Thus, using Theorem 1.8, we
deduce that asymptotically, the type I error of our test is
r

nεn
PH0 (ln > Zα ) ≤ P
(GPern,εn (Ω) − Perεn (Ω)) > Zα
4Cd Per(Ω)
−→ P (N (0, 1) > Zα ) = α,
which establishes the first part of Proposition 1.9. In order to compute the type II error of
our test, suppose that Per(Ω) = ρ0 where ρ0 > ρ. In that case,
(38)
r


nεn
(σd ρ − Pern,εn (Ω)) ≥ −Zα
PHA (ln ≤ Zα ) = PHA
4Cd ρ

r
r
nεn
nεn
= PHA
(Perεn (Ω) − Pern,εn (Ω)) ≥ −Zα +
(Perεn (Ω) − σd ρ) ,
4Cd ρ
4Cd ρ
Now recall that limn→∞ Perεn (Ω) = σd Per(Ω) = σd ρ0 > σd ρ. In particular, we deduce
that
r
nεn
lim
(Perεn (Ω) − σd ρ) = +∞.
n→∞
4Cd ρ
Thus, for large enough n,
r
r
nεn
1
nεn
−Zα +
(Perεn (Ω) − σd ρ) ≥
(σd ρ0 − σd ρ).
4Cd ρ
2 4Cd ρ
Hence, for large enough n,
r

r
nεn
1
nεn
PHA (ln ≤ Zα ) ≤ PHA
(Perεn (Ω) − Pern,εn (Ω)) ≥
(σd ρ0 − σd ρ).
4Cd ρ
2 4Cd ρ
Using the moment estimates from Theorem 1.1, and Markov’s inequality, we deduce that


1
.
PHA (ln ≤ Zα ) = O √
nεn
That is, the type II error is of order

√1 .
nεn

ESTIMATING PERIMETER USING GRAPH CUTS

17

A PPENDIX A. P ROOF OF L EMMA 1.4
Since Ω ⊂⊂ D and Ω has smooth boundary the relative perimeter of Ω with respect to
D in the generalized sense (2) simply corresponds to the usual perimeter of ∂Ω in the sense
that
Z
dHd−1 = Hd−1 (∂Ω).

Per(Ω) =
∂Ω

Additionally, for all ε ≤ δ := dist(Ω, ∂D) we have that
Z
2
Perε (Ω) = d+1
|Bd (x, ε) ∩ Ωc | dx,
ε
Ω
where Bd (x, r) denotes the ball of radius r in Rd centered at x and Ωc denotes the complement of Ω in all of space. Moreover, since ∂Ω is a compact smooth manifold, we can
assume without the loss of generality ( by taking ε small enough) that for every x ∈ Tε
there is a unique point P (x) in ∂Ω closest to x. Furthermore, we can assume that the map
P is smooth. We may further write
Perε (Ω) =

2
εd+1

Z
Tε−

|Bd (x, ε) ∩ Ωc | dx,

where Tε− is defined in (28). This reformulation makes it natural to write the previous
integral as an iterated integral; the outer integral is taken over the manifold ∂Ω and the inner
integral is taken along the normal line to ∂Ω at an arbitrary point x along the boundary.
To make this idea precise, we first let N(x) denote the outer unit normal to ∂Ω at x ∈ ∂Ω
and then consider the transformation (x, t) ∈ ∂Ω×(0, 1) 7→ x−tεN(x) for all ε sufficiently
small. The Jacobian of this transformation equals ε det(I + tεSx ), where Sx denotes the
shape operator (or second fundamental form) of ∂Ω at x, see [13] for instance. For all ε
sufficiently small, we may therefore conclude that

Z
Z Z 1
1
|Bd (x, ε)∩Ωc | dx =
|Bd (x − tεN(x), ε) ∩ Ωc | det(I + tεSx )dt dHd−1 (x).
ε Tε−
∂Ω
0
As a consequence, we also have that
(39)

Z Z 1
2
|Bd (x − tεN(x), ε) ∩ Ωc | det(I + tεSx ) dt dHd−1 (x).
Perε (Ω) = d
ε ∂Ω
0
With the expression (39) in hand, we may now proceed to establish (9) by expanding
Perε (Ω) in terms of ε and appealing to some elementary computations that show that the
first order term in ε vanishes.
For a fixed x ∈ ∂Ω, we first wish to understand the behavior of the function
Z 1

1
gx (ε) := d
|Bd (x − tεN(x), ε) ∩ Ωc | det(I + tεSx ) dt
ε
0
for ε in a neighborhood of zero. Without loss of generality, we may assume that x = 0,
that N(x) = ed and that around x the boundary ∂Ω coincides with the graph x̂ =
(x1 , . . . , xd−1 ) 7→ (x̂, f (x̂)) ∈ Rd of a smooth function f (x̂) that satisfies both f (0) = 0
and ∇f (0) = 0 simultaneously. By symmetry of the shape operator Sx , there exists an orthonormal basis for Rd−1 (where we identify Rd−1 with the hyperplane {(x̂, xd ) : xd = 0})
consisting of eigenvectors of the shape operator. We let v1 , . . . , vd−1 denote the eigenvectors of Sx and κ1 , . . . , κd−1 the corresponding eigenvalues ( also known as principal

18

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

curvatures). In particular, whenever kx̂k ≤ ε we have that
d−1

f (x̂) =

(40)

1X
κi hx̂, vi i2 + O(ε3 )
2 i=1

where curvatures κi = κi (x) and the O(ε3 ) error term canp
be uniformly bounded.
With these reductions in place, we first define u(ŷ) := ε2 − kŷk2 and then let


if f (ŷ) + εt < −u(ŷ)
2u(ŷ)
h(ŷ, t; ε) := u(ŷ) − εt − f (ŷ) if − u(ŷ) ≤ f (ŷ) + εt ≤ u(ŷ)


0
otherwise.
A direct calculation then shows that
(41)

c

Z

|Bd (x − tεN(x), ε) ∩ Ω | =

h(ŷ, t; ε) dŷ,
Bd−1 (0,ε)

p
and an application of (40) shows that h(ŷ, t; ε) = 2 ε2 − kŷk2 only if
kŷk2 = ε2 − O(ε4 )
It therefore follows that
Z

h(ŷ, t; ε) dŷ ≤ O(ε2 )

Bd−1 (0,ε)∩{f (ŷ)+εt<−u(ŷ)}

u(ŷ) = O(ε2 ).

and

Z
√

Bd−1 (0,ε)∩{kŷk≥

dŷ = O(εd+3 ).
ε2 −O(ε4 )}

We then let Aεt denote the set Aεt := {ŷ ∈ Bd−1 (0, ε) : −u(ŷ) ≤ f (ŷ) + εt ≤ u(ŷ)} and
use the previous estimate in (41) to uncover
Z
(42) |Bd (x − tεN(x), ε) ∩ Ωc | =
(u(ŷ) − εt − f (ŷ)) dŷ + O(εd+3 ).
Bd−1 (0,ε)∩Aεt

We may then note that
det(I + εtSx ) = (1 + tεκ1 ) . . . (1 + tεκd−1 ) = 1 + tεHx + O(ε2 ),
Pd−1
where Hx := i=1 κi represents the mean curvature. Using this fact in (42) then yields
!
Z 1 Z
1
gx (ε) = d
u(ŷ) − εt − f (ŷ) dŷ (1 + tεHx ) dt + O(ε2 ).
ε 0
Bd−1 (0,ε)∩Aεt
Now let f ε (z) := 1ε f (εz) and define the corresponding subset Ctε of (0, 1) × Bd−1 (0, 1) as
n
o
p
p
Ctε := (t, z) ∈ (0, 1) × Bd−1 (0, 1) : − 1 − kzk2 ≤ f ε (z) + t ≤ 1 − kzk2 ,
then make the change of variables ŷ = εz to see that
Z p

gx (ε) =
1 − kzk2 − t − f ε (z) (1 + tεHx ) dzdt + O(ε2 ).
Ctε

Recalling (40) shows that
d−1

(43)

f ε (z) =

εX
κi hz, vi i2 + O(ε2 ),
2 i=1

ESTIMATING PERIMETER USING GRAPH CUTS

19

which then allows us to obtain an expansion of gx (ε) in terms of ε according to the relation
Z p

gx (ε) =
1 − kzk2 − t dtdz
Ctε
d−1
p
1X
tHx ( 1 − kzk2 − t) −
κi hz, vi i2
2 i=1

Z
(44)

+ε
Ctε

!
dtdz + O(ε2 ).

The bias estimate (9) then directly follows after computing each of these terms individually.
We begin by considering the first term in the expansion, i.e.
Z p

I :=
1 − kzk2 − t dtdz.
Ctε

p
Given ε > 0 p
and z ∈ Bd−1 (0, 1) define c(z) := max{− 1 − kzk2 − f ε (z), 0} and
C(z) := min{ 1 − kzk2 − f ε (z), 1}, so that we may easily write


Z
p
C(z) + c(z)
I=
(C(z) − c(z))
1 − kzk2 −
dz.
2
Bd−1 (0,1)
As the set where c(z) 6= 0 has measure at most O(ε2 ), we easily conclude that


Z
p
C(z)
I=
C(z)
1 − kzk2 −
dz + O(ε2 ).
2
Bd−1 (0,1)
p
If C(z) = 1 then 1 − kzk2 − C(z)
= 12 (1 − kzk2 ) + O(ε2 ) as well. In any case, it
2
follows that
Z
1
σd
I=
(45)
(1 − kzk2 ) dz + O(ε2 ) =
+ O(ε2 ).
2 Bd−1 (0,1)
2
We now proceed to compute the second term in the expansion
Z p

II :=Hx
t 1 − kzk2 − t2 dtdz
Ctε

Z
=Hx

p
2

C (z)
Bd−1 (0,1)

1 − kzk C(z)
−
2
3

!
dz + O(ε2 )

and the third term in the expansion
Z
Z
d−1
d−1
1X
1X
III :=
κi
hz, vi i2 dtdz =
κi
hz, vi i2 C(z) dz + O(ε2 )
2 i=1
2 i=1
Ctε
Bd−1 (0,1)
p
in a similar fashion. We always have C(z) = 1 − kzk2 + O(ε), so that
Z
Hx
(46)
II =
(1 − kzk2 )3/2 dz + O(ε)
6 Bd−1 (0,1)
Z
Hx vol(S d−2 ) 1
(47)
=
(1 − r2 )3/2 rd−2 dr + O(ε)
6
0
The third term follows similarly by appealing to spherical coordinates, in that we have
Z
d−1
p
1X
III =
κi
1 − kzk2 hz, vi i2 dz + O(ε)
2 i=1
Bd−1 (0,1)
Z
Hx vol(S d−2 ) 1 p
=
1 − r2 rd dr + O(ε) = II + O(ε)
2(d − 1)
0

20

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

thanks to an integration by parts in the final term. We therefore have that I = σd /2 + O(ε2 )
and II − III = O(ε), so that gx (ε) = σd /2 + O(ε2 ) and
Z
Perε (Ω) = 2
gx (ε) dHd−1 = σd Per(Ω) + O(ε2 )
∂Ω

as desired.
We may also show that when Ω is a fixed ball, say Ω = Bd (xc , 31 ) for xc ∈ Rd the
center point of D, that the absolute value of the difference between Perε (Ω) and σd Per(Ω)
remains bounded from below by cε2 for c > 0 some positive constant. The proof proceeds
similarly to the proof of the bias estimate above. In particular, this shows that the bound in
Lemma 1.4 is optimal in terms of scaling for general sets with smooth boundary.
A PPENDIX B. P ROOF OF L EMMA 2.1
The proof follows the same argument used in the proof of Theorem 4.1 in [10] or
Theorem 6.2 in [1]. We assume that dist(Ω, ∂D) > 0. Such assumption implies that the
perimeter of Ω with respect to D, that is Per(Ω) defined in (2), is equal to the perimeter
of Ω with respect to Rd . We remark that a slight modification of the argument we present
below proves the result in the general case and hence we omit the details (see for example
the proof of Theorem 4.1 in [10]).
First we prove that for any function u : Rd → [0, 1] with u ∈ W 1,1 (Rd ) ∩ C ∞ (Rd ) and
for all ε > 0 we have
p
Z
Z Z
1kx−yk≤ε
αdp−1 σd
|u(y) − u(x)|dy dx ≤ p−1
k∇u(x)kdx,
(48)
εd+1
ε
Rd
Rd
Rd
Inequality (48) follows from
p
Z Z
1kx−yk≤ε
|u(y)
−
u(x)|dy
dx
εd+1
Rd
Rd
!p
Z
Z
1
|u(x + εh) − u(x)|dh dx
= p
ε Rd
Bd (0,1)
Z Z
αp−1
≤ dp
|u(x + εh) − u(x)|p dh dx
ε
Rd Bd (0,1)
Z Z
αp−1
≤ dp
|u(x + εh) − u(x)|dh dx
ε
Rd Bd (0,1)
Z Z
Z 1
αdp−1
= p−1
∇u(x + tεh) · hdt dh dx
ε
Rd Bd (0,1)
0
Z Z
Z 1
αdp−1
|∇u(x + tεh) · h|dt dh dx
≤ p−1
ε
Rd Bd (0,1) 0
Z Z
Z
αdp−1 1
= p−1
|∇u(x) · h|dx dh dt
ε
0
Bd (0,1) Rd
Z Z
Z
αdp−1 1
∇u(x)
= p−1
k∇u(x)k
· h dh dx dt
ε
0
Rd
Bd (0,1) k∇u(x)k
Z
αdp−1 σd
= p−1
k∇u(x)kdx
ε
Rd

ESTIMATING PERIMETER USING GRAPH CUTS

21

where in the first equation we used the change of variables h = x−y
ε , in the first inequality
we used Jensen’s inequality and in the second inequality the fact that u takes values in [0, 1].
Now, for any set Ω ⊆ D as in the statement, we can find a sequence of functions
{uk }k∈N with uk : Rd → [0, 1] , uk ∈ W 1,1 (Rd ) ∩ C ∞ (Rd ) and such that
Z
L1 (Rd )
(49)
uk −→ 1Ω , lim
k∇uk (x)kdx = Per(Ω).
k→∞

Rd

Such sequence can be obtained for example with the aid of standard mollifiers (see Theorem
13.9 in [22]). It follows from (48) and from (49) that
p
Z Z
1kx−yk≤ε
αdp−1 σd
dx
≤
|1
(y)
−
1
(x)|dy
Per(Ω).
Ω
Ω
εd+1
εp−1
Rd
Rd
Finally, notice that
Z
Z
φ̄pεn (x)dx ≤
D

Rd

Z
Rd

1kx−yk≤ε
|1Ω (y) − 1Ω (x)|dy
εd+1

p
dx ≤

αdp−1 σd
Per(Ω).
εp−1

A PPENDIX C. P ROOF OF L EMMA 3.1
The proof is based on similar computations to the ones in Appendix A and thus we
simply highlight the main ideas. First of all note that
Z
2
Var (gn,1 (X1 )) =
φ̄2εn (x)dx − (Perεn (Ω)) .
D

Since Perεn (Ω) = O(1), our task reduces to computing the integral in the above expression.
It follows from (29) that for all εn small enough (so that Tεn ⊆ D),
Z
Z
Z
1
1
|Bd (x, εn ) ∩ Ωc |2 dx + 2(d+1)
|Bd (x, εn ) ∩ Ω|2 dx.
φ̄2εn (x)dx = 2(d+1)
Tε−n
Tε+n
D
εn
εn
We compute the first of the integrals from the above expression. As in the proof of Lemma
1.4, we write
Z
1
|Bd (x, εn ) ∩ Ωc |2 dx
2(d+1)
Tε−n
εn

Z 
Z 1
1
1
c 2
=
|B
(x
−
tε
N(x),
ε
)
∩
Ω
|
det(I
+
tε
S
)
dt
dHd−1 (x).
d
n
n
n x
εn ∂Ω ε2d
0
n
For x ∈ ∂Ω we study the expression
Z 1
|Bd (x − tεn N(x), εn ) ∩ Ωc |2
det(I + tεn Sx )dt.
hεn (x) :=
ε2d
0
n
Note that det(I +tεn Sx ) = (1+tεn κ1 )···(1+tεn κd−1 ) = 1+O(εn ), where κ1 , . . . , κd−1
are the principal curvatures (eigenvalues of the shape operator Sx ). Hence,
Z 1
|Bd (x − tεn N(x), εn ) ∩ Ωc |2
hεn (x) =
dt + O(εn ).
ε2d
0
n
Without loss of generality, we may assume that x = 0, that N(x) = ed and that around x the
boundary ∂Ω coincides with the graph x̂ = (x1 , . . . , xd−1 ) 7→ (x̂, f (x̂)) ∈ Rd of a smooth
function f (x̂) that satisfies both f (0) = 0 and ∇f (0) = 0 simultaneously, and we denote by
v1 , . . . , vd−1 the eigenvectors of Sx (just as in Appendix A). Then, f : Bd−1 (0, εn ) → R,
Pd−1
2
satisfies f (x̂) = i=1 κi hx̂, vi i + O(ε3n ).

NICOLÁS GARCÍA TRILLOS1 , DEJAN SLEPČEV2 AND JAMES VON BRECHT3

22

Now for fixed t ∈ [0, 1] we define H1−t to be the hyperplane
H1−t := {x = (x̂, xd ) : xd ≥ 1 − t} ,
and we let
At := |Bd (0, 1) ∩ H1−t |.
With these definitions we can write
(50)
Z
d−1
X
|Bd (x − tεn N(x), εn ) ∩ Ωc | = εdn At +
κi
= εdn At +

Bd−1 (0,εn
i=1
Pd−1 Z
i=1 κi

d−1

2

√

hx̂, vi i dx̂ + O(εd+2
n )
1−t)

Bd−1 (0,εn

√

kx̂k2 dx̂ + O(εd+2
n )
1−t)

= εdn At + O(εd+1
n ),
where the second
equality holds due to symmetry, and where the last equality follows after
R
computing Bd−1 (0,εn √1−t) kx̂k2 dx̂ using polar coordinates. From the above, it follows
that
|Bd (x − tεn N(x), εn ) ∩ Ωc |2
= A2t + O(εn ).
ε2d
n
We conclude that
Z
1

A2t dt + O(εn ).

hεn (x) =
0

Therefore,
1
2(d+1)
εn

Z
Tε−n

|Bd (x, εn ) ∩ Ωc |2 dx =

1
εn

Analogously, we can obtain a similar expression for
from this we deduce (35).

Z

1

A2t dt Per(Ω) + O(1).

0
1
2(d+1)

εn

R

Tε+n

|Bd (x, εn ) ∩ Ω|2 dx and

Acknowledgements. DS and NGT are grateful to NSF for its support (grants DMS1211760 and DMS-1516677). JvB was supported by NSF grant DMS 1312344/DMS
1521138. The authors are grateful to ICERM (supported by NSF grant 0931908), where
part of the research was done during the research cluster: Geometric analysis methods for
graph algorithms. Furthermore they are grateful to Ki-Net (NSF Research Network Grant
RNMS11-07444) for opportunities provided. The authors would like to thank the Center
for Nonlinear Analysis of the Carnegie Mellon University for its support.
R EFERENCES
[1] G. A LBERTI AND G. B ELLETTINI, A non-local anisotropic model for phase transitions: asymptotic
behaviour of rescaled energies, European J. Appl. Math., 9 (1998), pp. 261–284.
[2] L. A MBROSIO , N. F USCO , AND D. PALLARA, Functions of bounded variation and free discontinuity
problems, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York,
2000.
[3] E. A RIAS -C ASTRO , B. P ELLETIER , AND P. P UDLO, The normalized graph cut and Cheeger constant: from
discrete to continuous, Adv. in Appl. Probab., 44 (2012), pp. 907–937.
[4] I. A RMEND ÁRIZ , A. C UEVAS , AND R. F RAIMAN, Nonparametric estimation of boundary measures and
related functionals: asymptotic results, Adv. in Appl. Probab., 41 (2009), pp. 311–322.
[5] M. B ELKIN , H. NARAYANAN , AND P. N IYOGI, Heat flow and a faster algorithm to compute the surface
area of a convex body, in FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of
Computer Science (FOCS’06), Washington, DC, USA, 2006, IEEE Computer Society, pp. 47–56.

ESTIMATING PERIMETER USING GRAPH CUTS

23

[6] S. B ERNSTEIN, On a modification of Chebyshev’s inequality and of the error formula of Laplace, Ann. Sci.
Inst. Sav. Ukraine, Sect. Math, 1 (1924), pp. 38–49.
[7] X. B RESSON , T. L AURENT, D. U MINSKY, AND J. H. VON B RECHT, Convergence and energy landscape
for cheeger cut clustering, in Advances in Neural Information Processing Systems (NIPS), P. L. Bartlett,
F. C. N. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, eds., 2012, pp. 1394–1402.
[8] A. C UEVAS , R. F RAIMAN , AND L. G Y ÖRFI, Towards a universally consistent estimator of the Minkowski
content, ESAIM Probab. Stat., 17 (2013), pp. 359–369.
[9] A. C UEVAS , R. F RAIMAN , AND A. RODR ÍGUEZ -C ASAL, A nonparametric approach to the estimation of
lengths and surface areas, Ann. Statist., 35 (2007), pp. 1031–1051.
[10] N. G ARC ÍA T RILLOS AND D. S LEP ČEV, Continuum limit of total variation on point clouds, Archive for
Rational Mechanics and Analysis, (2015), pp. 1–49. online first.
[11] N. G ARC ÍA T RILLOS , D. S LEP ČEV, J. VON B RECHT , T. L AURENT, AND X. B RESSON, Consistency of
Cheeger and ratio graph cuts. to appear in Journal of Machine Learning Research, 2015.
[12] E. G IN É , R. L ATAŁA , AND J. Z INN, Exponential and moment inequalities for U -statistics, in High
dimensional probability, II (Seattle, WA, 1999), vol. 47 of Progr. Probab., Birkhäuser Boston, Boston, MA,
2000, pp. 13–38.
[13] A. G RAY, Tubes, Progress in Mathematics, Birkhäuser Basel, 2004.
[14] L. H AGEN AND A. K AHNG, New spectral methods for ratio cut partitioning and clustering., IEEE Trans.
Computer-Aided Design, 11 (1992), pp. 1074 –1085.
[15] M. H EIN AND S. S ETZER, Beyond spectral clustering - tight relaxations of balanced graph cuts, in Advances
in Neural Information Processing Systems (NIPS), J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and
K. Weinberger, eds., 2011, pp. 2366–2374.
[16] W. H OEFFDING, Probability inequalities for sums of bounded random variables, Journal of the American
statistical association, 58 (1963), pp. 13–30.
[17] R. J IM ÉNEZ AND J. E. Y UKICH, Nonparametric estimation of surface integrals, Ann. Statist., 39 (2011),
pp. 232–260.
[18] R. K ANNAN , S. V EMPALA , AND A. V ETTA, On clusterings: Good, bad and spectral, Journal of the ACM
(JACM), 51 (2004), pp. 497–515.
[19] M. K EARNS AND D. RON, Testing problems with sublearning sample complexity, Journal of Computer and
System Sciences, 61 (2000), pp. 428 – 456.
[20] V. S. KOROLJUK AND Y. V. B OROVSKICH, Theory of U -statistics, vol. 273 of Mathematics and its
Applications, Kluwer Academic Publishers Group, Dordrecht, 1994. Translated from the 1989 Russian
original by P. V. Malyshev and D. V. Malyshev and revised by the authors.
[21] P. KOTHARI , A. NAYYERI , R. O’D ONNELL , AND C. W U, Testing surface area, in Proceedings of the
Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, SIAM, 2014, pp. 1204–
1214.
[22] G. L EONI, A first course in Sobolev spaces, vol. 105 of Graduate Studies in Mathematics, American
Mathematical Society, Providence, RI, 2009.
[23] J. N EEMAN, Testing surface area with arbitrary accuracy, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, New York, NY, USA, 2014, ACM, pp. 393–397.
[24] B. PATEIRO -L ÓPEZ AND A. RODR ÍGUEZ -C ASAL, Length and surface area estimation under smoothness
restrictions, Adv. in Appl. Probab., 40 (2008), pp. 348–358.
[25] J. S HI AND J. M ALIK, Normalized cuts and image segmentation, Pattern Analysis and Machine Intelligence,
IEEE Transactions on, 22 (2000), pp. 888–905.
[26] A. S ZLAM AND X. B RESSON, Total variation and cheeger cuts., in ICML, J. Faenkranz and T. Joachims,
eds., Omnipress, 2010, pp. 1039–1046.
[27] U. VON L UXBURG, A tutorial on spectral clustering, Statistics and computing, 17 (2007), pp. 395–416.
[28] Y.-C. W EI AND C.-K. C HENG, Towards efficient hierarchical designs by ratio cut partitioning, in ComputerAided Design, 1989. ICCAD-89. Digest of Technical Papers., 1989 IEEE International Conference on, IEEE,
1989, pp. 298–301.
1

D IVISION OF A PPLIED M ATHEMATICS , P ROVIDENCE , RI, 02912, USA., EMAIL : NICOLAS GARCIA TRILLOS @ BROWN . EDU

2

D EPARTMENT OF M ATHEMATICAL S CIENCES , C ARNEGIE M ELLON U NIVERSITY, P ITTSBURGH , PA,
15213, USA., TEL . +412 268-2545, EMAIL : SLEPCEV @ MATH . CMU . EDU
3 D EPARTMENT OF M ATHEMATICS AND S TATISTICS , C ALIFORNIA S TATE U NIVERSITY, L ONG B EACH
L ONG B EACH , CA 90840, USA., EMAIL : JAMES . VON B RECHT @ CSULB . EDU

