  We study estimation of piecewise smooth signals over a graph. We propose a
$\ell_{2,0}$-norm penalized Graph Trend Filtering (GTF) model to estimate
piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness
across the nodes. We prove that the proposed GTF model is simultaneously a
k-means clustering on the signal over the nodes and a minimum graph cut on the
edges of the graph, where the clustering and the cut share the same assignment
matrix. We propose two methods to solve the proposed GTF model: a spectral
decomposition method and a method based on simulated annealing. In the
experiment on synthetic and real-world datasets, we show that the proposed GTF
model has a better performances compared with existing approaches on the tasks
of denoising, support recovery and semi-supervised classification. We also show
that the proposed GTF model can be solved more efficiently than existing models
for the dataset with a large edge set.
