  We study an extention of total variation denoising over images to over
Cartesian power graphs and its applications to estimating non-parametric
network models. The power graph fused lasso (PGFL) segments a matrix by
exploiting a known graphical structure, $G$, over the rows and columns. Our
main results shows that for any connected graph, under subGaussian noise, the
PGFL achieves the same mean-square error rate as 2D total variation denoising
for signals of bounded variation. We study the use of the PGFL for denoising an
observed network $H$, where we learn the graph $G$ as the $K$-nearest
neighborhood graph of an estimated metric over the vertices. We provide
theoretical and empirical results for estimating graphons, a non-parametric
exchangeable network model, and compare to the state of the art graphon
estimation methods.
