Graph sketching-based Space-efficient Data Clustering
Anne Morvan∗†‡
anne.morvan@cea.fr

Krzysztof Choromanski§
kchoro@google.com

Cédric Gouy-Pailler∗
cedric.gouy-pailler@cea.fr

arXiv:1703.02375v4 [cs.LG] 20 Dec 2017

Jamal Atif†
jamal.atif@dauphine.fr
Abstract
In this paper, we address the problem of recovering
arbitrary-shaped data clusters from datasets while facing
high space constraints, as this is for instance the case in many
real-world applications when analysis algorithms are directly
deployed on resources-limited mobile devices collecting the
data. We present DBMSTClu a new space-efficient densitybased non-parametric method working on a Minimum Spanning Tree (MST) recovered from a limited number of linear
measurements i.e. a sketched version of the dissimilarity
graph G between the N objects to cluster. Unlike k-means,
k-medians or k-medoids algorithms, it does not fail at distinguishing clusters with particular forms thanks to the property of the MST for expressing the underlying structure of
a graph. No input parameter is needed contrarily to DBSCAN or the Spectral Clustering method. An approximate
MST is retrieved by following the dynamic semi-streaming
model in handling the dissimilarity graph G as a stream of
edge weight updates which is sketched in one pass over the
data into a compact structure requiring O(N polylog(N ))
space, far better than the theoretical memory cost O(N 2 ) of
G. The recovered approximate MST T as input, DBMSTClu then successfully detects the right number of nonconvex
clusters by performing relevant cuts on T in a time linear in
N . We provide theoretical guarantees on the quality of the
clustering partition and also demonstrate its advantage over
the existing state-of-the-art on several datasets.

1

Introduction

Clustering is one of the principal data mining tasks consisting in grouping related objects in an unsupervised
manner. It is expected that objects belonging to the
same cluster are more similar to each other than to objects belonging to different clusters. There exists a variety of algorithms performing this task. Methods like k∗ CEA,

LIST, 91191 Gif-sur-Yvette, France.
Paris-Dauphine, PSL Research University, CNRS,
LAMSADE, 75016 Paris, France.
‡ Partly supported by the DGA (French Ministry of Defense).
§ Google Brain Robotics, New York, USA.
† Université

means [1], k-medians [2] or k-medoids [3] are useful unless the number and the shape of clusters are unknown
which is unfortunately often the case in real-world applications. They are typically unable to find clusters with
a nonconvex shape. Although DBSCAN [4] does not
have these disadvantages, its resulting clustering still
depends on the chosen parameter values.
One of the successful approaches relies on a graph
representation of the data. Given a set of N data points
{x1 , . . . , xN }, a graph can be built based on the dissimilarity of data where points of the dataset are the vertices
and weighted edges express distances between these objects. Besides, the dataset can be already a graph G
modeling a network in many fields, such as bioinformatics - where gene-activation dependencies are described
through a network - or social, computer, information,
transportation network analysis. The clustering task
consequently aims at detecting clusters as groups of
nodes that are densely connected with each other and
sparsely connected to vertices of other groups. In this
context, Spectral Clustering (SC) [9] is a popular tool
to recover clusters with particular structures for which
classical k-means algorithm fails. When dealing with
large scale datasets, a main bottleneck of the technique
is to perform the partial eigendecomposition of the associated graph Laplacian matrix, though. Another inherent difficulty is to handle the huge number of nodes
and edges of the induced dissimilarity graph: storing all
edges can cost up to O(N 2 ) where N is the number of
nodes. Over the last decade, it has been established that
the dynamic streaming model [5] associated with linear
sketching techniques [6] - also suitable for distributed
processing -, is a good way for tackling this last issue. In
this paper, the addressed problem falls within a framework of storage limits allowing O(N polylog(N )) space
complexity but not O(N 2 ).
Contributions. The new clustering algorithm
DBMSTClu presented in this paper brings a solution
to these issues: 1) detecting arbitrary-shaped data clusters, 2) with no parameter, 3) in a time linear to the
number of points, 4) in a space-efficient manner by
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

working on a limited number of linear measurements, a
sketched version of the streamed dissimilarity graph G.
DBMSTClu returns indeed a partition of the N points
to cluster relying only on a Minimum Spanning Tree
(MST) of the dissimilarity graph G taking O(N ) space.
This MST can be space-efficiently approximatively retrieved in the dynamic semi-streaming model by handling G as a stream of edge weight updates sketched
in only one pass over the data into a compact structure taking O(N polylog(N )) space. DBMSTClu then
automatically identifies the right number of nonconvex
clusters by cutting suitable edges of the resulting approximate MST in O(N ) time.
The remaining of this paper is organized as follows.
In §2 the related work about graph clustering and other
space-efficient clustering algorithms is described. §3
gives fundamentals of the sketching technique that can
be used to obtain an approximate MST of the dissimilarity graph. DBMSTClu (DB for Density-Based), the
proposed MST-based algorithm for clustering is then
explained in §4.1, its theoretical guarantees discussed
in §4.2 and the implementation enabling its scalability
detailed in §4.3. §5 presents the experimental results
comparing the proposed clustering algorithm to other
existing methods. Finally, §6 concludes the work and
discusses future directions.
2

pected clusters, consists in deleting the heaviest edges
from the Euclidean MST of the considered graph but
this completely fails when the intra-cluster distance is
lower than the inter-clusters one. For decades since
MST-based clustering methods [20, 21] have been developed and can be classified into the group of densitybased methods. MSDR [21] relies on the mean and the
standard deviation of edge weights within clusters but
will encourage clusters with points far from each other
as soon as they are equally “far”. Moreover, it does not
handle clusters with less than three points.
2.3 Space-efficient
clustering
algorithms.
Streaming k-means [23] is a one-pass streaming method
for the k-means problem but still fails to detect clusters
with nonconvex shapes since only the centroid point
of each cluster is stored. This is not the case of
CURE algorithm [24] which represents each cluster as
a random sample of data points contained in it but
this offline method has a prohibitive time complexity
of O(N 2 log(N )) not suitable for large datasets. More
time-efficient, CluStream [25] and DenStream [26]
create microclusters based on local densities in an
online fashion and aggregate them later to build bigger
clusters in offline steps. Though, only DenStream can
capture non-spherical clusters but needs parameters
like DBSCAN from which it is inspired.

Related work

2.1 General graph clustering. The approach of
graph representation of the data has led to an extensive
literature over graph clustering related to graph partitioning [7]. From the clustering methods point of view,
DenGraph [10] proposes a graph version of DBSCAN
which is able to deal with noise while work from [11]
focuses on the problem of recovering clusters with considerably dissimilar sizes. Recent works include also approaches from convex optimization using low-rank decomposition of the adjacency matrix [12, 13, 14, 15].
These methods bring theoretical guarantees about the
exact recovery of the ground truth clustering for the
Stochastic Block Model [16, 17, 18] but demand to
compute the eigendecomposition of a N × N matrix
(resp. O(N 3 ) and O(N 2 ) for time and space complexity). Moreover they are restricted to unweighted graphs
(weights in the work from [15] refer to likeliness of existence of an edge, not a distance between points).
2.2 MST-based graph clustering. The MST is
known to help recognizing clusters with arbitrary
shapes. Clustering algorithms from this family identify
clusters by performing suitable cuts among the MST
edges. The first algorithm, called Standard Euclidean
MST (SEMST) is from [19] and given a number of ex-

3

Context, notations and graph sketching
preprocessing step

Consider a dataset with N points. Either the underlying network already exists, or it is assumed that a
dissimilarity graph G between points can be built where
points of the dataset are the vertices and weighted edges
express distances between these objects. For instance,
this can be the Euclidean distance. In both cases, the
graphs considered here should follow this definition:
Definition 3.1. (graph G = (V, E)) A graph G =
(V, E) consists in a set of nodes V and a set of edges
E ⊆ V × V . The graph is undirected but weighted.
The weight w on an edge between node i and j - if this
edge exists - corresponds to the normalized predefined
distance between i and j, s.t. 0 < w ≤ 1. |V | = N
and |E| = M stand resp. for the cardinality of sets V
and E. E = {e1 , ..., eM } and for all edges ei a weight
wi represents a distance between two vertices. In the
sequel, E(G) describes the set of edges of a graph G.
Freely of any parameter, DBMSTClu performs the
nodes clustering from its unique input: an MST of
G. So an independent preprocessing is required for
its recovery by any existing method. To respect our
space restrictions though, the use of a graph sketching
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

technique is motivated here: from the stream of its edge
weights, a sketch of G is built and then an approximate
MST is retrieved exclusively from it.
Streaming graph sketching and approximate MST recovery. Processing data in the dynamic
streaming model [5] for graph sketching implies: 1) The
graph should be handled as a stream s of edge weight
updates: s = (a1 , ... aj , ...) where aj is the j-th update in the stream corresponding to the tuple aj =
(i, wold,i , ∆wi ) with i denoting the index of the edge to
update, wold,i its previous weight and ∆wi the update to
perform. Thus, after reading aj in the stream, the i-th
edge is assigned the new weight wi = wold,i + ∆wi ≥ 0.
2) The method should make only one pass over this
stream . 3) Edges can be both inserted or deleted (turnstile model), i.e. weights can be increased or decreased
(but have always to be nonnegative). So weights change
regularly, as in social networks where individuals can be
friends for some time then not anymore.
The algorithm in [6] satisfies these conditions and is
used here to produce in an online fashion a limited number of linear measurements summarizing edge weights
of G, as new data aj are read from the stream s of
edge weight updates. Its general principle is briefly described here. For a given small 1 , G is seen as a set of
unweighted subgraphs Gk containing all the edges with
weight lower than (1 + 1 )k , hence Gk ⊂ Gk+1 . The Gk
are embodied as N virtual vectors v (i) ∈ {−1, 0, 1}M for
i ∈ [N ]1 expressing for each node the belonging to an
(i)
existing edge: for j ∈ [M ], vj equals to 0 if node i is not
in ej , 1 (resp. −1) if ej exists and i is its left (resp. right)
node. All v (i) are described at L different “levels”, i.e. L
virtual copies of the true vectors are made with some entries randomly set to zero s.t. the v (i),l get sparser as the
corresponding level l ∈ [L] increases. The v (i),l for each
level are explicitly coded in memory by three counters:
PM (i),l
PM
PM (i),l j
(i),l
φ = j=1 vj ; ι = j=1 j vj ; τ = j=1 vj
z
mod p, with p a suitably large prime and z ∈ Zp . The
resulting compact data structure further named a sketch
enables to draw almost uniformly at random a nonzero
weighted edge among Gk at any time among the levels vectors v (i),l which are 1-sparse (with exactly one
nonzero coefficient) thanks to `0 -sampling [27]:

practice only one pass over the data is needed and the
space cost is significantly lower than the theoretical
O(N 2 ) bound. The time cost for each update of
the sketch is polylog(N ). The authors from [6] also
proposed an algorithm to compute in a single-pass the
approximate weight W̃ of an MST T - the sum of all
its edge weights - by appropriate samplings from the
sketch in O(N polylog(N )) time. They show that W ≤
W̃ ≤ (1+1 ) W where W stands
Pr for the true weight and
W̃ = N −(1+1 )r+1 cc(Gr )+ k=0 λk cc(Gk ) with λk =
(1 + 1 )k+1 − (1 + 1 )i , r = dlog1+1 (wmax )e s.t. wmax is
the maximal weight of G and cc denotes the number
of connected components of the graph in parameter.
Here an extended method is applied for obtaining rather
an approximate MST - and not simply its weight - by
registering edges as they are sampled. Referring to
the proof of Lemma 3.4 in [6], the approach is simply
justified by applying Kruskal’s algorithm where edges
with lower weights are first sampled2 .
Note that the term MST is kept in the whole paper
for the sake of simplicity, but the sketching technique
and so does our algorithm enables to recover a Minimum
Spanning Forest if the initial graph is disconnected.
4

The proposed MST-based graph clustering
method: DBMSTClu

4.1 Principle. Let us consider a dataset with N
points. After the sketching phase, an approximate MST
further named T has been obtained with N − 1 edges
s.t. ∀i ∈ [N − 1], 0 < wi ≤ 1. Our density-based
clustering method DBMSTClu exclusively relies on this
object by performing some cuts among the edges of the
tree s.t. K − 1 cuts result in K clusters. Note that
independently of the technique used to obtain an MST
(the sketching method is just a possible one), the space
complexity of the algorithm is O(N ) which is better
than the O(N 2 ) of Spectral Clustering (SC). The time
complexity of DBMSTClu is O(N K) which is clearly
less than the O(N 3 ) one implied by SC. After a cut,
obtained clusters can be seen as subtrees of the initial
T and the analysis of their qualities is only based on
edges contained in those subtrees. In the sequel, all
clusters Ci , i ∈ [K], are assimilated to their associated
subtree of T and for instance the maximal edge of a
Definition 3.2. (`0 -sampling) An (, δ) `0 -sampler cluster will refer to the edge with the maximum weight
for a nonzero vector x ∈ Rn fails with a probability from the subtree associated to this cluster.
at most δ or returns some i ∈ [n] with probability
Our algorithm is a parameter-free divisive top1
where
supp
x
=
{i
∈
[n]
|
x
=
6
0}.
(1 ± ) | supp
down
procedure: it starts from one cluster containing
i
x|
the whole dataset and at each iteration, a cut which
The sketch requires O(N log3 (N )) space. It follows
that the sketching is technically semi-streamed but in
2
1 In

the sequel, for a given integer a, [a] = {1, . . . , a}.

We would like to thank Mario Lucic for the fruitful private
conversation and for coauthoring with Krzysztof Choromanski the
MSE sketching extension during his internship at Google.

Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

maximizes some criterion is performed. The criterion
for identifying the best cut to do (if any should be
made) at a given stage is a measure of the validity of
the resulting clustering partition. This is a function of
two positive quantities defined below: Dispersion and
Separation of one cluster. The quality of a given cluster
is then measured from Dispersion and Separation while
the quality of the clustering partition results from the
weighted average of all cluster validity indices. Finally,
all those measures are based on the value of edge weights
and the two latter ones lie between −1 and 1.
Definition 4.1. (Cluster Dispersion) The
Dispersion of a cluster Ci (DISP) is defined as the
maximum edge weight of Ci . If the cluster is a
singleton (i.e. contains only one node), the associated
Dispersion is set to 0. More formally:
(4.1)
(
6 0
max wj if |E(Ci )| =
j, ej ∈Ci
∀i ∈ [K], DISP(Ci ) =
0
otherwise.
Definition 4.2. (Cluster Separation) The Separation of a cluster Ci (SEP) is defined as the minimum
distance between the nodes of Ci and the ones of all
other clusters Cj , j 6= i, 1 ≤ i, j ≤ K, K 6= 1 where K
is the total number of clusters. In practice, it corresponds to the minimum weight among all already cut
edges from T comprising a node from Ci . If K = 1, the
Separation is set to 1. More formally, with Cuts(Ci )
denoting cut edges incident to Ci ,
(4.2)
(
min
wj if K 6= 1
j, ej ∈Cuts(Ci )
∀i ∈ [K], SEP(Ci ) =
1
otherwise.

b
b
b

DISP(C1 )

b

b

b

b

b

b

b

b

b

SEP(C1 )
C1

Figure 1: SEP and DISP definitions with N = 12,
K = 3 for dashed cluster C1 in the middle.
Fig. 1 sums up the introduced definitions. The
higher the Separation, the farther is the cluster separated from the other clusters, while low values suggest
that the cluster is close to the nearest one.
Definition 4.3. (Validity Index of a Cluster)
The Validity Index of a cluster Ci is defined as:
(4.3)

VC (Ci ) =

SEP(Ci ) − DISP(Ci )
max(SEP(Ci ), DISP(Ci ))

The Validity Index of a Cluster (illustration in Fig. 2)
is defined s.t. −1 ≤ VC (Ci ) ≤ 1 where 1 stands for the

best validity index and −1 for the worst one. No division
by zero (i.e. max(DISP(Ci ), SEP(Ci )) = 0) happens
because Separation is always strictly positive. When
Dispersion is higher than Separation, −1 < VC (Ci ) < 0.
Conversely, when Separation is higher than Dispersion,
0 < VC (Ci ) < 1. So our clustering algorithm will
naturally encourage clusters with a higher Separation
over those with a higher Dispersion.
ϵ
b

1
b

ϵ
VC (Clef
t)

b

ϵ

1
VC (Clef
t)

b

b

ϵ
)
VC (Cright

1
b

1
VC (Cright
)

Figure 2: Validity Index of a Cluster’s example with
N = 3. For a small , cutting edge with weight  or 1

gives resp. left and right partitions. (up) VC (Clef
t ) = 1;

1
VC (Cright
) = −1 < 0. (bottom) VC (Clef
)
=
1−
> 0;
t
1
VC (Cright ) = 1. The bottom partition, for which
validity indices of each cluster are positive, is preferred.
Definition 4.4. (Validity Index of a Clustering
Partition) The Density-Based Validity Index of a
Clustering partition Π = {Ci }, 1 ≤ i ≤ K, DBCVI(Π)
is defined as the weighted average of the Validity Indices
of all clusters in the partition where N is the number of
points in the dataset.
K
X
|Ci |
(4.4)
DBCVI(Π) =
VC (Ci )
N
i=1
The Validity Index of Clustering lies also between
−1 and 1 where 1 stands for an optimal density-based
clustering partition while −1 stands for the worst one.
Our defined quantities are significantly distinct
from the separation and sparseness defined in [28]. Indeed, firstly, their quantities are not well defined for
special cases when clusters have less than four nodes or
a partition containing a lonely cluster. Secondly, the
way they differentiate internal and external nodes or
edges does not properly recover easy clusters like convex blobs. Moreover, our DBCVI differs from the Silhouette Coefficient [29]. It does not perform well with
nonconvex-shaped clusters and although this is based
on close concepts like tightness and also separation, the
global coefficient is based on the average values of Silhouette coefficients of each point, while our computation
of DBCVI begins at the cluster level.
DBMSTClu is summarized in Algorithm 1. It starts
from a partition with one cluster containing the whole
dataset whereas the associated initial DBCVI is set to
the worst possible value: −1. As long as there exists
a cut which makes the DBCVI greater from (or equal
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

to) the one of the current partition, a cut is greedily
chosen by maximizing the obtained DBCVI among all
the possible cuts. When no direct improvement is
possible, the algorithm stops. It is guaranteed that
the cut edge locally maximizes the DBCVI at each
iteration since by construction, the algorithm will try
each possible cut. In practice, the algorithm stops
after a reasonable number of cuts, getting trapped in a
local maximum corresponding to a meaningful cluster
partition. This prevents from obtaining a partition
where all points are in singleton clusters. Indeed, such
a result (K = N ) is not desirable, although it is
optimal in the sense of the DBCVI, since in this case,
∀i ∈ [K], DISP(Ci ) = 0 and VC (Ci ) = 1. Moreover,
the non-parametric characteristic helps achieving stable
partitions. In Algorithm 1, evaluateCut(.) computes the
DBCVI when the cut in parameter is applied to T .
Algorithm 1 Clustering algorithm DBMSTClu
1: Input: T , the MST
2: dbcvi← − 1.0; clusters = [ ]; cut list←[E(T )]
3: while dbcvi < 1.0 do
4:
cut tp←N one; dbcvi tp←dbcvi
5:
for each cut in cut list do
6:
newDbcvi← evaluateCut(T , cut)
7:
if newDbcvi ≥ dbcvi tp then
8:
cut tp←cut; dbcvi tp←newDbcvi
9:
if cut tp 6= N one then
10:
clusters← cut(clusters, cut tp)
11:
dbcvi←dbcvi tp; remove(cut list, cut tp)
12:
else
13:
break
14: return clusters, dbcvi

Proof. For the first cut, both separations of obtained
clusters C1 and C2 are equal to the weight of the
considered edge for cut. Here, this is the one with
the highest weight. Thus, for i = 1, 2, DISP(Ci ) ≤
SEP(Ci ) =⇒ VC (Ci ) ≥ 0. Finally, the DBCVI of
the partition, as a convex sum of two nonnegative
quantities, is clearly nonnegative.
Lemma 4.2. Lowest weighted edge case Let T be
an MST of the dissimilarity data graph. If the first
cut from E(T ) done by DBMSTClu is the one with the
lowest weight, then resulting DBCVI is negative or zero.
Proof. Same reasoning in the opposite case s.t.
SEP(Ci ) − DISP(Ci ) ≤ 0 for i ∈ {1, 2}.
Proposition 4.1. When the first cut is not the
heaviest Let T be an MST of the dissimilarity data
graph with N nodes. Let us consider this specific case:
all edges have a weight equal to w except two edges e1
and e2 resp. with weight w1 and w2 s.t. w1 > w2 >
w > 0. DBMSTClu does not cut any edge with weight
w and cuts e2 instead of e1 as a first cut iff:
p
2n2 w1 − n1 + n21 + 4w1 (n22 w1 + N 2 − N n1 − n22 )
w2 >
2(N − n1 + n2 )
where n1 (resp. n2 ) is the number of nodes in the
first cluster resulting from the cut of e1 (resp. e2 ).
Otherwise, e1 gets cut.
Proof. See supplementary material.

This proposition emphasizes that the algorithm is
cleverer than simply cutting the heaviest edge first.
Indeed, although w2 < w1 , cutting e2 could be preferred
4.2 Quality of clusters. An analysis of the algo- over e . Moreover, no edge with weight w can get
1
rithm and the quality of the recovered clusters is now cut at the first iteration as they have the minimal
given. The main results are: 1) DBMSTClu differs sig- weight in the tree. Indeed it really happens since an
nificantly from the naive approach of SEMST by pre- approximate MST with discrete rounded weights is used
ferring cuts which do not necessarily correspond to the when sketching is applied.
heaviest edge (Prop. 4.1 and 4.2). 2) As long as the
current partition contains at least one cluster with a Proposition 4.2. First cut on the heaviest edge
negative validity index, DBMSTClu will find a cut im- in the middle Let T be an MST of the dissimilarity
proving the global index (Prop. 4.3). 3) Conditions are data graph with N nodes. Let us consider this specific
given to determine in advance if and which cut will be case: all edges have a weight equal to w except two
performed in a cluster with a positive validity index edges e1 and e2 resp. with weight w1 and w2 s.t.
(Prop. 4.4 and 4.5 ). All are completely independent of w1 > w2 > w > 0. Denote n1 (resp. n2 ) the number
the sketching phase. Prop. 4.1 and 4.2 rely on the two of nodes in the first cluster resulting from the cut of e1
basic lemmas regarding the first cut in the MST:
(resp. e2 ). In the particular case where edge e1 with
maximal weight w1 stands between two subtrees with the
Lemma 4.1. Highest weighted edge case Let T be same number of points, i.e. n1 = N/2, e1 is always
an MST of the dissimilarity data graph. If the first cut preferred over e2 as the first optimal cut.
from E(T ) made by DBMSTClu is the heaviest edge,
Proof. See supplementary material.
then resulting DBCVI is nonnegative.
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

b

S1

S2
b

b
b

Remark 4.1. Let us consider the MST in Fig. 3 with
S
N = 8, w1 = 1, w2 = w3 = 1 − , and other weights
e
set to . Clearly, it is not always preferred to cut e1
in the middle since for  = 0.1, DBCV I2 ≈ 0.27 >
DBCV I1 =  = 0.1. So, it is a counter-example to a Figure 5: Illustration of the recursive relationship for
possible generalization of Prop. 4.2 where there would be left and right Dispersions resulting from the cut of
edge e: DISPlef t (e) = max(w(S1 )), DISPright (e) =
more than three possible distinct weights in T .
max(w(S2 ), w(S3 )) where w(.) returns the edge weights.
Separation
works analogically.
w2
w1
w3
ϵ
ϵ
ϵ
ϵ
3

b

b

b

b

b

b

b

b

b

b

b

b

b

Figure 3: Counter-example for Remark 4.1
These last propositions hold for every iteration in the
algorithm.
Proposition 4.3. Fate of negative VC cluster
Let K = t + 1 be the number of clusters in the clustering
partition at iteration t. If for some i ∈ [K], VC (Ci ) < 0,
then DBMSTClu will cut an edge at this stage.
Proof. See supplementary material.
Ci
l
wsep

Cil

wmax

Cir

r
wsep

Figure 4: Generic example of Prop. 4.3 and 4.5’s proofs.
Thus, at the end of the clustering algorithm, each
cluster will have a nonnegative VC so at each step of
the algorithm, this bound holds for the final DBCVI:
PK
DBCV I ≥ i=1 |CNi | max(VC (Ci ), 0).
Proposition 4.4. Fate of positive VC cluster I
Let T be an MST of the dissimilarity data graph and C
a cluster s.t. VC (C) > 0 and SEP(C) = s. DBMSTClu
does not cut an edge e of C with weight w < s if
both resulting clusters have at least one edge with weight
greater than w.
Proof. See supplementary material.
Proposition 4.5. Fate of positive VC cluster II
Consider a partition with K clusters s.t. some cluster
Ci , i ∈ [K] with VC (Ci ) > 0 is in the setting of Fig. 10
i.e. cutting the heaviest edge e with weight wmax results
in two clusters: the left (resp. right) cluster Cil (resp.
Cir ) with n1 points (resp. n2 ) s.t. DISP(Cil ) = d1 ,
l
r
SEP(Cil ) = wsep
, DISP(Cir ) = d2 and SEP(Cir ) = wsep
.
l
r
Assuming w.l.o.g. wsep > wsep , e gets cut iff:


n1 d1 +n2 d2
n1 +n2

wmax


wmax
≤ r .
wsep

Proof. See supplementary material.

4.3 Implementation for linear time and space
complexities. Algorithm 1 previously described could
lead to a naive implementation. We now briefly explain how to make the implementation efficient in order to achieve the linear time and space complexities in N (code on https://github.com/annemorvan/
DBMSTClu/). The principle is based on two tricks. 1)
As observed in §4.2: for a performed cut in cluster
Ci , VC (Cj ) for any j 6= i remain unchanged. Hence,
if VC (Cj ) are stored for each untouched cluster after a
given cut, only the edges of Cl and Cr resp. the left
and right clusters induced by e’s cut need to be evaluated again to determine the DBCVI in case of cut.
Thus the number of operations to find the optimal cut
decreases drastically over time as the clusters become
smaller through the cuts. 2) However finding the first
cut already costs O(N ) time hence paying this price for
each cut evaluation would lead to O(N 2 ) operations.
Fortunately, this can be avoided as SEP and DISP exhibit some recurrence relationship in T : when knowing
these values for a given cut, we can deduce the value
for a neighboring cut (cf. Fig. 5). To determine the
first cut, T should be hence completely crossed following the iterative version of the Depth-First Search. The
difficulty though is that the recursive relationship between the quantities to update is directional: left and
right w.r.t. the edge to cut. So we develop here double
Depth-First search (see principle in Algorithm 2): from
any given edge of T , edges left and right are all visited consecutively with a Depth-First search, and SEP
and DISP are updated recursively thanks to a carefully
defined order in the priority queue of edges to handle.
5

Experiments

Tight lower and upper bounds are given in §3 for the
weight of the approximate MST retrieved by sketching.
First experiments in §5.1 show that the clustering
results do not suffer from the use of an approximate
MST instead of a real one. Experiments from §5.2 prove
then the scalability of DBMSTClu for large values of N .
5.1 Safety of the sketching. The results of DBMSTClu are first compared with DBSCAN [4] because it
can compete with DBMSTClu as 1) nonconvex-shaped
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

Algorithm 2 Generic Double Depth-First Search
1: Input: T , the MST; e, the edge of T where the
search starts; n src, source node of e
2: Q = deque() //Empty priority double-ended queue
3: for incident edges to n src do
4:
pushBack(Q, (incident e, n src, F ALSE))
5: pushBack(Q, (e, n src, T RU E))
6: for incident edges to n trgt do
7:
pushBack(Q, (incident e, n trgt, F ALSE))
8: pushBack(Q, (e, n trgt, T RU E))
9: while Q is not empty do
10:
e, node, marked = popFront(Q)
11:
opposite node = getOtherNodeEdge(e, node)
12:
if not marked then
13:
for incident edges to node do
14:
pushBack(Q, (incident e, node, F ))
15:
pushBack(Q, (e, node, T ))
16:
pushFront(Q, (e, opposite node, T ))
17:
else
18:
doTheJob(e) //Perform here the task
19: return

clusters are recognized, 2) it does not require explicitly
the number of expected clusters, 3) it is both time and
space-efficient (resp. O(N log N ) and O(N )). Then,
the results of another MST-based algorithm are shown
for comparison. The latter called Standard Euclidean
MST (SEMST) [19] cuts the K − 1 heaviest edges of
a standard Euclidean MST given a targeted number of
clusters K. For DBMSTClu, the dissimilarity graph
is built from computing the Euclidean distance between
data points and passed into the sketch phase to produce
an approximate version of the exact MST.
Synthetic datasets. Experiments were performed
on two classic synthetic datasets from the Euclidean
space: noisy circles and noisy moons. Each dataset
contains 1000 data points in 20 dimensions: the first
two dimensions are randomly drawn from predefined
2D-clusters, as shown in Fig. 6 and 7, while the other
18 dimensions are random Gaussian noise.
Real dataset.
DBMSTClu performances are
also measured on the mushroom dataset (https://
archive.ics.uci.edu/ml/datasets/mushroom).
It
contains 8124 records of 22 categorical attributes corresponding to 23 species of gilled mushrooms in the
Agaricus and Lepiota family. 118 binary attributes are
created from the 22 categorical ones, then the complete
graph (about 33 millions of edges) is built by computing
the normalized Hamming distance (i.e. the number of
distinct bits) between points.
Results. Fig. 6, 7 and 8 show the results for all
previously defined datasets and aforementioned meth-

ods. The synthetic datasets were projected onto 2D
spaces for visualization purposes. They were produced
with a noise level such that SEMST fails and DBSCAN
does not perform well without parameters optimization.
In particular, for DBSCAN all the cross points correspond to noise. With the concentric circles, SEMST
does not cut on the consistent edges, hence leads to an
isolated singleton cluster. DBSCAN classifies the same
point plus a near one as noise while recovering the two
circles well. Finally, DBMSTClu finds the two main
clusters and also creates five singleton clusters which
can be legitimately considered as noise as well. With
noisy moons, while DBSCAN considers three outliers,
DBMSTClu detects the same as singleton clusters. As
theoretically proved above, experiments emphasize the
fact that our algorithm is more subtle than simply cutting the heaviest edges as the failure of SEMST shows.
Moreover our algorithm exhibits an ability to detect
outliers, which could be labeled as noise in a postprocessing phase. Another decisive advantage of our algorithm is the absence of any required parameters, contrarily to DBSCAN. For the mushroom dataset, if suitable parameters are given to SEMST and DBSCAN,
the right 23 clusters get found while DBMSTClu retrieves them without tuning any parameter. Quantitative results for the synthetic datasets are shown in Table 3: the achieved silhouette coefficient (between −1
and 1), Adjusted Rand Index (ARI) (between 0 and 1)
and DBCVI. For all the indices, the higher, the better.
Further analysis can be read in supplementary material.
For the mushroom dataset, the corresponding DBCVI
and silhouette coefficient are resp. 0.75 and 0.47.
SEMST
DBSCAN
DBMSTClu

Silhouette coeff.
0.16 -0.12
0.02
0.26
-0.26 0.26

ARI
0
0.99
0.99

0
0.99
0.99

DBCVI
0.001 0.06
-0.26 0.15
0.18 0.15

Table 1: Silhouette coefficients, ARI and DBCVI for the
noisy circles (left) and noisy moons (right) datasets.
5.2 Scalability of the clustering. For mushroom
dataset, DBMSTClu’s execution time (avg. on 5 runs)
is 3.36s while DBSCAN requires 9.00s. This gives a
first overview of its ability to deal with high number
of clusters. Further experiments on execution time
were conducted on large-scale random weighted graphs
generated from the Stochastic Block Model with varying
equal-sized number of clusters K and N . The scalability
of DBMSTClu is shown in Fig. 9 and Table 2 by
exhibiting the linear time complexity in N . Graphs with
1M of nodes and 100 clusters were easily clustered. In
Table 2, the row with the execution time ratio between
K = 100 and K = 5 illustrates the first trick from
§4.3 as the observed time ratio is around 2/3 of the
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

1.5

1.5

1.5

1.0

1.0

1.0

0.5

0.5

0.5

0.0

0.0

0.0

0.5

0.5

0.5

1.0

1.0

1.0

1.5

1.5

2

1

0

1

2

2

1

0

1

1.5

2

2

1

0

1

2

Figure 6: Noisy circles: SEMST, DBSCAN ( = 0.15, minP ts = 5), DBMSTClu with an approximate MST.
1.5

1.5

1.5

1.0

1.0

1.0

0.5

0.5

0.5

0.0

0.0

0.0

0.5

0.5

0.5

1.0

1.0

0.5

0.0

0.5

1.0

1.5

2.0

1.0

1.0

0.5

0.0

0.5

1.0

1.5

1.0

2.0

1.0

0.5

0.0

0.5

1.0

1.5

2.0

Figure 7: Noisy moons: SEMST, DBSCAN ( = 0.16, minP ts = 5), DBMSTClu with an approximate MST.

4 3 2
1 0 1
2 3 4
5

3

2

1

0

1

2

3

3
2
1
0
1
2
3
4 3 2
1 0 1
2 3 4
5

3

2

1

0

1

2

3

3
2
1
0
1
2
3
4 3 2
1 0 1
2 3 4
5

3

2

1

0

1

2

3

3
2
1
0
1
2
3

Figure 8: Mushroom dataset: SEMST, DBSCAN ( = 1.5, minP ts = 2), DBMSTClu with an approximate MST
(projection on the first three principal components).
Clu is non-parametric, unlike most existing clustering
methods: it automatically determines the right number
4000
of nonconvex clusters. Although the approach is funK=5
K=20
3500
damentally independent from the sketching phase, its
K=100
3000
robustness has been assessed by using as input an ap2500
proximate MST of the sketched G rather than an exact
2000
one. The graph sketch is computed dynamically on the
1500
1000
fly as new edge weight updates are read in only one
500
pass over the data. This brings a space-efficient solu0
0
200000
400000
600000
800000
1000000
tion for finding an MST of G when the O(N 2 ) edges
Number of points
cannot fit in memory. Hence, our algorithm adapts to
Figure 9: DBMSTClu’s execution time with values of
the semi-streaming setting with O(N polylog N ) space.
N ∈ {1K, 10K, 50K, 100K, 250K, 500K, 750K, 1M}.
Our approach shows promising results, as evidenced by
the experimental part regarding time and space scala6 Conclusion
bility and clustering performance even with sketching.
In this paper we introduced DBMSTClu a novel space- Further work would consist in using this algorithm in
efficient Density-Based Clustering algorithm which only privacy issues, as the lost information when sketching
relies on a Minimum Spanning Tree (MST) of the dis- might ensure data privacy. Moreover, as it is already the
similarity graph G: the spatial and time costs are resp. case for the graph sketching, we could look for adaptO(N ) and O(N K) with N the number of data points ing both the MST recovery and DBMSTClu to the fully
and K the number of clusters. This enables to deal eas- online setting, i.e. to be able to modify dynamically curily with graphs of million of nodes. Moreover, DBMSTTime (s)

theoretical one 100/5 = 20.

Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

K\N
5
20
100
“100/5”

1000
0.34
0.95
4.36
12.82

10000
2.96
8.73
40.25
13.60

50000
14.37
43.71
201.76
14.04

100000
28.91
88.51
398.41
13.78

250000
73.04
223.18
995.42
13.63

500000
148.85
449.37
2011.79
13.52

750000
218.11
669.29
3015.61
13.83

1000000
292.25
889.88
4016.13
13.74

Table 2: Numerical values for DBMSTClu’s execution time (in s) varying N and K (avg. on 5 runs). The last
row shows the execution time ratio between K = 100 and K = 5.
rent MST and clustering partition as a new edge weight
update from the stream is seen.
[16]

References
[1] S. Lloyd, Least Squares Quantization in PCM, IEEE
Trans. Inf. Theor., 28 (1982), pp. 129–137.
[2] A. Jain and R. Dubes, Algorithms for Clustering Data,
Prentice Hall, Upper Saddle River, NJ, USA, 1988.
[3] L. Kaufman and P. Rousseeuw, Clustering by means
of medoids, Statistical Data Analysis Based on the
L1 Norm and Related Methods, pp. 405–416, 1987.
[4] M. Ester, H. Kriegel, J. Sander, X. Xu, A densitybased algorithm for discovering clusters in large spatial
databases with noise, AAAI Press (1996), pp. 226–231.
[5] S. Muthukrishnan, Data Streams: Algorithms and
Applications, Found. Trends Theor. Comput. Sci., 1
(2005), pp. 117–236.
[6] K. Ahn, S. Guha and A. McGregor, Analyzing Graph
Structure via Linear Measurements, ACM-SIAM Symposium on Discrete Algorithms, 2012, Kyoto, Japan,
pp. 459–467.
[7] S. Schaeffer, Survey: Graph Clustering, Comput. Sci.
Rev., 1 (2007), pp. 27–64.
[8] M. Girvan and M. Newman, Community Structure
in Social and Biological Networks, Proceedings of the
National Academy of Sciences of the United States of
America, 99 (2012), pp.7821-7826.
[9] M. Nascimento and A. de Carvalho, Spectral methods
for graph clustering - A survey, European Journal of
Operational Research, 211 (2011), pp.221-231.
[10] T. Falkowski, A. Barth and M. Spiliopoulou, DENGRAPH: A Density-based Community Detection Algorithm, IEEE/WIC/ACM International Conference on
Web Intelligence, pp. 112–115, 2007.
[11] N. Ailon, Y. Chen and H. Xu, Breaking the Small Cluster Barrier of Graph Clustering, CoRR, abs/1302.4549,
2013.
[12] S. Oymak and B. Hassibi, Finding Dense Clusters
via ”Low Rank + Sparse” Decomposition, CoRR,
abs/1104.5186, 2011.
[13] Y. Chen, S. Sanghavi and H. Xu, Clustering Sparse
Graphs, Advances in Neural Information Processing
Systems, 25 (2012), pp. 2204–2212.
[14] Y. Chen, A. Jalali, S. Sanghavi and H. Xu, Clustering
Partially Observed Graphs via Convex Optimization, J.
Mach. Learn. Res., 15 (2014), pp. 2213–2238.
[15] Y. Chen, and S. Lim and H. Xu, Weighted Graph Clustering with Non-uniform Uncertainties, International

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

Conference on Machine Learning, 32 (2014), Beijing,
China, pp. II-1566–II-1574.
P. Holland, K. Laskey and S. Leinhardt, Stochastic
blockmodels: First steps, Social Networks, 5 (1983),
pp.109–137.
A. Condon and R. Karp, Algorithms for Graph Partitioning on the Planted Partition Model, Random
Struct. Algorithms, 18 (2001), pp.116–140.
K. Rohe, S. Chatterjee and B. Yu, Spectral clustering
and the high-dimensional stochastic blockmodel, Ann.
Statist., 39 (2011), pp. 1878–1915.
C. Zahn, Graph-Theoretical Methods for Detecting and
Describing Gestalt Clusters, IEEE Trans. Comput., 20,
(1971), pp. 68–86.
T. Asano, B. Bhattacharya, M. Keil, F. Yao, Clustering
Algorithms Based on Minimum and Maximum Spanning Trees, Symposium on Computational Geometry,
Urbana-Champaign, IL, USA, pp. 252–257, 1988.
O. Grygorash, Y. Zhou and Z. Jorgensen, Minimum
Spanning Tree Based Clustering Algorithms, IEEE
Int.Conference on Tools with Artificial Intelligence,
pp. 73-81, 2006.
K. Ahn, S.Guha and A. McGregor, Graph Sketches:
Sparsification, Spanners, and Subgraphs, ACM
SIGMOD-SIGACT-SIGAI Symposium on Principles
of Database Systems, Scottsdale, AZ, USA, pp. 5–14,
2012.
N. Ailon, R. Jaiswal, C. Monteleoni, Streaming kmeans approximation, Advances in Neural Information
Processing Systems, 22 (2009), pp. 10–18.
S. Guha, R. Rastogi and K. Shim, Cure: An Efficient
Clustering Algorithm for Large Databases, Inf. Syst.,
26 (2001), pp. 35–58.
C. Aggarwal, J. Han, J. Wang, and P. Yu, A Framework
for Clustering Evolving Data Streams, International
Conference on Very Large Data Bases, 29 (2003),
Berlin, Germany, pp.81–92.
F. Cao, M. Ester, W. Qian and A. Zhou, Density-based
clustering over an evolving data stream with noise,
SIAM Conference on Data Mining (2006), pp. 328–339.
G. Cormode and D. Firmani, A unifying framework
for `0 -sampling algorithms, Distributed and Parallel
Databases, 32 (2014), pp. 315–335.
D. Moulavi, P. Jaskowiak, R. Campello, A. Zimek and
J. Sander, Density-Based Clustering Validation, SIAM
ICDM, Philadelphia, PA, USA, pp. 839–847, 2014.
P. Rousseeuw, Silhouettes: A graphical aid to the
interpretation and validation of cluster analysis, J.
Comput. and Appl. Math., 20 (1987), pp. 53–65.

Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

7

Proofs.

7.1

maximal weight w1 stands between two subtrees with the
same number of points, i.e. n1 = N/2, e1 is always
preferred over e2 as the first optimal cut.

Proof of Prop. 4.1.

Proposition 4.1. When the first cut is not the
heaviest Let T be an MST of the dissimilarity data
graph with N nodes. Let us consider this specific case:
all edges have a weight equal to w except two edges e1
and e2 resp. with weight w1 and w2 s.t. w1 > w2 >
w > 0. DBMSTClu does not cut any edge with weight
w and cuts e2 instead of e1 as a first cut iff:
p
2n2 w1 − n1 + n21 + 4w1 (n22 w1 + N 2 − N n1 − n22 )
w2 >
2(N − n1 + n2 )
where n1 (resp. n2 ) is the number of nodes in the
first cluster resulting from the cut of e1 (resp. e2 ).
Otherwise, e1 gets cut.
Proof. Let DBCV I1 (resp. DBCV I2 ) be the DBCVI
after cut of e1 (resp. e2 ). As w (resp. w1 ) is the
minimum (resp. maximal) weight, the algorithm does
not cut e since the resulting DBCVI would be negative
(cf. Lemma 4.2) while DBCV I1 is guaranteed to be
positive (cf. Lemma 4.1). So, the choice will be
between e1 and e2 but e2 gets cut iff DBCV I2 >
DBCV I1 . DBCV I1 and DBCV I2 expressions are
simplified w.l.o.g. by scaling the weights by w s.t.
w ← 1, w1 ← w1 /w, w2 ← w2 /w, hence w1 > w2 > 1.
Then,
DBCV I2 > DBCV I1 > 0
1
n2 w 2
n2
(
)(1 −
⇐⇒
− 1) + (1 −
)
N w1
N
w2
n1
1
w2
n1
−
(1 −
)(1 −
) + (1 −
)>0
N
w1
N
w1
⇐⇒ w22 (N + n2 − n1 ) +w2 (n1 − 2n2 w1 )
{z
}
|
{z
}
|
a

+ (n2 − N )w1 > 0.
|
{z
}

b

Proof. A reductio ad absurdum is made by showing that
cutting edge e2 i.e. DBCV I2 > DBCV I1 leads to the
contradiction w1 /w < 1. With the scaling process from
Prop. 4.1’proof:
1
1
w2
1
w2
1
(1 −
) + (1 −
)=1−
−
2
w1
2
w1
2w1
2w1
n2 w2
n2
1
DBCV I2 =
(
− 1) + (1 −
)(1 −
)
N w1
N
w2
1
n2 w2
1
=1−
+
(
+
− 2)
w2
N w1
w
|
{z 2 }
DBCV I1 =

=A

There is w2 > w = 1, so w12 < 1. Besides w2 < w1 so
w2
w1 < 1 thus, A < 0. Let now consider w.l.o.g. that
edge e2 is on the ”right side” (right cluster/subtree) of
e1 (similar proof if e2 is on the left side of e1 ). Hence,
it is clear that for maximizing DBCV I2 as a function
of n2 , we need n2 = n1 + 1. Then,
DBCV I2 > DBCV I1
1
1
1 w2
1
1
w2
⇐⇒ −
+ ( + )(
−2+
)>−
−
w2
2 N w1
w2
w1
w1
1
1
1
1
2
⇐⇒ (
+
+
+
)w2 − 1 −
2w1
N w1
2w1
N
2w1
1
1 1
+ (−1 + + )
>0
2 N w2
2
1
1
⇐⇒ (1 + ) w22 + w2 ( − w1 (1 + ))
N
2
N
| {z }
|
{z
}
a>0

b<0

1
+ w1 ( −
| N {z

c<0

1
)>0
2}

As c/a < 0 and w2 > 0, w2 > 2(NN+1) [ w1 (1 + N2 ) − 12 +
√
∆ ] with ∆ = (w1 (1 + N2 ) − 12 )2 + 4(1 + N1 )( 12 − N1 )w1 .
Clearly, ∆ = b2 − 4ac is positive
and
c/a
is
negative.
This inequality is incompatible with w1 > w2 since:
√
b2 −4ac
But w2 > 0, then w2 > −b+ 2a
which gives the
N
2
1 √
final result after some simplifications.
w1 > w2 ⇐⇒ w1 >
[ w1 (1 + ) − + ∆ ]
2(N + 1)
N
2
√
1
7.2 Proof of Prop. 4.2.
⇐⇒ w1 + > ∆
2
Proposition 4.2. First cut on the heaviest edge
4 2
1
4
1
⇐⇒
w (1 + ) + w1 (−1 − ) < 0
in the middle Let T be an MST of the dissimilarity
N 1
N
N
N
data graph with N nodes. Let us consider this specific
⇐⇒ w1 < 1 : ILLICIT
case: all edges have a weight equal to w except two
edges e1 and e2 resp. with weight w1 and w2 s.t. Indeed, after the scaling process, w1 < 1 = w is not
w1 > w2 > w > 0. Denote n1 (resp. n2 ) the number possible since by hypothesis, w1 > w. Finally, it is not
of nodes in the first cluster resulting from the cut of e1 allowed to cut e2 , the only remaining possible edge to
(resp. e2 ). In the particular case where edge e1 with cut is e1 .
c<0

Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

7.4

Ci
l
wsep

Cil

wmax

Cir

r
wsep

Proof of Prop. 4.4.

Proposition 4.4. Fate of positive VC cluster I
Let T be an MST of the dissimilarity data graph and C
a cluster s.t. VC (C) > 0 and SEP(C) = s. DBMSTClu
does not cut an edge e of C with weight w < s if
both resulting clusters have at least one edge with weight
greater than w.

Proof. Let us consider clusters C1 and C2 resulting
from the cut of edge e. Assume that in the associated
subtree of C1 (resp. C2 ), there is an edge e1 (resp.
Figure 10: Generic example for proof of Prop. 4.3 and e2 ) with a weight w1 (resp. w2 ) higher than w s.t.
without loss of generality, w1 > w2 . Since VC (C) > 0,
4.5.
s > w1 > w2 > w. But cutting edge e implies that
for i ∈ {1, 2}, DISP(Ci ) > SEP(Ci ) = w, and thus
7.3 Proof of Prop. 4.3.
VC (Ci ) < 0. Cutting edge e would therefore mean to
Proposition 4.3. Fate of negative VC cluster replace a cluster C s.t. VC (C) > 0 by two clusters s.t.
Let K = t + 1 be the number of clusters in the clustering for i ∈ {1, 2}, VC (Ci ) < 0 which obviously decreases the
partition at iteration t. If for some i ∈ [K], VC (Ci ) < 0, current DBCVI. Thus, e does not get cut at this step of
the algorithm.
then DBMSTClu will cut an edge at this stage.
Proof. Let i ∈ [K] s.t. VC (Ci ) < 0 i.e. SEP(Ci ) <
l
DISP(Ci ). We denote wsep
the minimal weight outing
cluster Ci and wmax the maximal weight in subtree Si
def
def
l
of Ci i.e. SEP(Ci ) = wsep
and DISP(Ci ) = wmax .
l
< wmax . By cutting the cluster Ci on the
Hence, wsep
edge with weight wmax , we define Cil and Cir resp. the
left and right resulting clusters.
Let us look at VC (Cil ). If SEP(Cil ) ≥ DISP(Cil )
SEP(C l )

then VC (Cil ) ≥ 0 ≥ VC (Ci ) else VC (Cil ) = DISP(Cil ) − 1.
i
The definition of the Separation as a minimum and our
cut imply that
SEP(Cil ) ≥ min(SEP(Ci ), wmax ) ≥ SEP(Ci ).

7.5

Proof of Prop. 4.5.

Proposition 4.5. Fate of positive VC cluster II
Consider a partition with K clusters s.t. some cluster
Ci , i ∈ [K] with VC (Ci ) > 0 is in the setting of Fig. 10
i.e. cutting the heaviest edge e with weight wmax results
in two clusters: the left (resp. right) cluster Cil (resp.
Cir ) with n1 points (resp. n2 ) s.t. DISP(Cil ) = d1 ,
r
l
.
, DISP(Cir ) = d2 and SEP(Cir ) = wsep
SEP(Cil ) = wsep
l
r
Assuming w.l.o.g. wsep > wsep , e gets cut iff:


n1 d1 +n2 d2
n1 +n2

wmax


≤

wmax
.
r
wsep

Also the definition of the Dispersion as a maximum
implies that DISP(Cil ) ≤ DISP(Ci ). Hence we get that

r
Proof. As VC (Ci ) > 0, there is SEP(Ci ) = wsep
>
w
.
Then,
the
DBCVI
before
(K
clusters)
and
after
max
− 1 i.e. VC (Cil ) ≥ VC (Ci ) in
−1 ≥
cut of wmax (K + 1 clusters) are:
r
this case too. The same reasoning holds for Ci showing
that VC (Cir ) ≥ VC (Ci ). Finally,


K
X
n1 + n2
wmax
DBCV
I
=
V
(C
)
+
1
−
K
C
j
r
X nj
N
wsep
nl
nr
j6=i
DBCV Iaf tercut =
VC (Cj ) + i VC (Cil ) + i VC (Cir )
N
N
N


K
X
j6=i
n1
d1
DBCV
I
=
V
(C
)
+
1
−
K+1
C
j
X nj
nl
nr
N
wmax
j6=i
≥
VC (Cj ) + i VC (Ci ) + i VC (Ci )


N
N
N
j6=i
n2
d2
+
1−
= DBCV Ibef orecut .
N
wmax
SEP(Cil )
DISP(Cil )

SEP(Ci )
DISP(Ci )

Hence cutting the edge with maximal weight in Ci
improves the resulting DBCVI.

DBMSTClu cuts wmax iff DBCV IK+1 ≥ DBCV IK .
So the result after simplification.
Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

8

Complements on experiments.

Experiments were conducted using Python and scikitlearn library [1] on a single-thread process on an intel
processor based node.
8.1 Safety of the sketching. Fig. 11 shows another
result on a synthetic dataset: three blobs generated
from three Gaussian distributions. With the three
blobs, each method SEMST, DBSCAN and DBMSTClu
performs well: they all manage to retrieve three clusters.
Quantitative results for the three synthetic datasets
are shown in Table 3: the achieved silhouette coefficient, Adjusted Rand Index (ARI) and DBCVI. For all
the indices, the higher, the better. Silhouette coefficient (between −1 and 1) is used to measure a clustering partition without any external information. For
DBSCAN it is computed by considering noise points as
singletons. We see that this measure is not very suitable
for nonconvex clusters like noisy circles or moons. The
ARI (between 0 and 1) measures the similarity between
the experimental clustering partition and the known
groundtruth. DBSCAN and DBMSTClu give similar
almost optimal results. Finally, the obtained DBCVIs
are consistent, since the best ones are reached for DBMSTClu.
References
[1] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel,
B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer,
R. Weiss, V. Dubourg, J. Vanderplas, A. Passos,
D. Cournapeau, M. Brucher, M. Perrot and E. Duchesnay, Scikit-learn: Machine Learning in Python, Journal
of Machine Learning Research, 12 (2011), pp. 2825–
2830.

Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

15

15

15

10

10

10

5

5

5

0

0

0

5

5

5

10

10

10

15

15

20

15

10

5

0

5

10

15

20

25

20

15

10

5

0

5

10

15

20

25

15

20

15

10

5

0

5

10

15

20

25

Figure 11: Three blobs: SEMST, DBSCAN ( = 1.4, minP ts = 5), DBMSTClu with an approximate MST.

SEMST
DBSCAN
DBMSTClu

Silhouette coeff.
0.84 0.16 -0.12
0.84 0.02
0.26
0.84 -0.26 0.26

Adjusted Rand Index
1 0
0
1 0.99 0.99
1 0.99 0.99

DBCVI
0.84 0.001
0.84 -0.26
0.84 0.18

0.06
0.15
0.15

Table 3: Silhouette coefficients, Adjusted Rand Index and DBCVI for the blobs, noisy circles and noisy moons
datasets with SEMST, DBSCAN and DBMSTClu.

Copyright c 2018 by SIAM
Unauthorized reproduction of this article is prohibited

