Divisive Clustering

In divisive clustering, we split using bisection $k$-means (or sparsest cut), recursing on each part. In effect, working our way from the top down through the graph.