This paper presents a stochastic clustering algorithm which uses
pairwise similarity of elements. The problem is viewed as a graph
partitioning problem, where nodes represent data elements and the
weights of the edges represent pairwise similarities. We generate
samples of cuts in this graph, by using David Karger's contraction
algorithm, and compute an "average" cut which is our solution to the
clustering problem. The stochastic nature of our method makes it
robust against noise, including accidental edges and small spurious
clusters. The complexity of our algorithm is very low: O(N log^2 N)
for a fixed accuracy level. In addition, and without additional
computational cost, our algorithm provides a hierarchy of nested
partitions.  We demonstrate the superiority of our method for image
segmentation on a few synthetic and real images, B&W and color, where
some other recently proposed methods (such as normalized-cut) fail or
perform less well.