Distributed Cartesian Power Graph Segmentation for Graphon Estimation
This work addresses graphon estimation for network analysis, representing an incremental improvement over existing methods.
The paper tackles the problem of estimating non-parametric network models by extending total variation denoising to Cartesian power graphs, showing that the proposed method achieves the same mean-square error rate as 2D total variation denoising under subGaussian noise.
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.