  The Normalized Cut (NCut) objective function, widely used in data clustering
and image segmentation, quantifies the cost of graph partitioning in a way that
biases clusters or segments that are balanced towards having lower values than
unbalanced partitionings. However, this bias is so strong that it avoids any
singleton partitions, even when vertices are very weakly connected to the rest
of the graph. Motivated by the B\"uhler-Hein family of balanced cut costs, we
propose the family of Compassionately Conservative Balanced (CCB) Cut costs,
which are indexed by a parameter that can be used to strike a compromise
between the desire to avoid too many singleton partitions and the notion that
all partitions should be balanced. We show that CCB-Cut minimization can be
relaxed into an orthogonally constrained $\ell_{\tau}$-minimization problem
that coincides with the problem of computing Piecewise Flat Embeddings (PFE)
for one particular index value, and we present an algorithm for solving the
relaxed problem by iteratively minimizing a sequence of reweighted Rayleigh
quotients (IRRQ). Using images from the BSDS500 database, we show that image
segmentation based on CCB-Cut minimization provides better accuracy with
respect to ground truth and greater variability in region size than NCut-based
image segmentation.
