Distributed Cartesian Power Graph Segmentation for Graphon Estimation

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.