  We study recovery of piecewise-constant signals on graphs by the estimator
minimizing an $l_0$-edge-penalized objective. Although exact minimization of
this objective may be computationally intractable, we show that the same
statistical risk guarantees are achieved by the $\alpha$-expansion algorithm
which computes an approximate minimizer in polynomial time. We establish that
for graphs with small average vertex degree, these guarantees are minimax
rate-optimal over classes of edge-sparse signals. For spatially inhomogeneous
graphs, we propose minimization of an edge-weighted objective where each edge
is weighted by its effective resistance or another measure of its contribution
to the graph's connectivity. We establish minimax optimality of the resulting
estimators over corresponding edge-weighted sparsity classes. We show
theoretically that these risk guarantees are not always achieved by the
estimator minimizing the $l_1$/total-variation relaxation, and empirically that
the $l_0$-based estimates are more accurate in high signal-to-noise settings.
