text: 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, @math , 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 @math , where we learn the graph @math as the @math -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.
  @cite_27: We propose a nonparametric framework for the analysis of networks, based on a natural limit object termed a graphon. We prove consistency of graphon estimation under general conditions, giving rates which include the important practical setting of sparse networks. Our results cover dense and sparse stochastic blockmodels with a growing number of classes, under model misspecification. We use profile likelihood methods, and connect our results to approximation theory, nonparametric function estimation, and the theory of graph limits.
  @cite_26: 
  @cite_23: Exchangeable graph models (ExGM) subsume a number of popular network models. The mathematical object that characterizes an ExGM is termed a graphon. Finding scalable estimators of graphons, provably consistent, remains an open issue. In this paper, we propose a histogram estimator of a graphon that is provably consistent and numerically efficient. The proposed estimator is based on a sorting-and-smoothing (SAS) algorithm, which first sorts the empirical degree of a graph, then smooths the sorted graph using total variation minimization. The consistency of the SAS algorithm is proved by leveraging sparsity concepts from compressed sensing.
summary: We next turn our attention to graphon estimation using the PGFL on a learned graph. The statistical limits of graphon estimation have been well characterized for smooth graphons, and it was found that computationally intractable profile likelihood maximization is minimax optimal for H "older graphons, @cite_27 @cite_26 . One tractable approach to graphon estimation is to order the vertices according to some graph statistics, such as the degrees of @math , and then treat the resulting re-ordered matrix @math as an image and applying image segmentation tools ( @math is the permutation associated with this sorting). This methodology is called sorting and smoothing (SAS), and in @cite_23 they use TV denoising to perform the image segmentation. The implicit assumption is that the degree is a decent proxy for the latent variable, @math , which does not hold for most graphons.