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_1: The estimation of probabilities of network edges from the observed adjacency matrix has important applications to predicting missing links and network denoising. It has usually been addressed by estimating the graphon, a function that determines the matrix of edge probabilities, but this is ill-defined without strong assumptions on the network structure. Here we propose a novel computationally efficient method, based on neighborhood smoothing to estimate the expectation of the adjacency matrix directly, without making the structural assumptions that graphon estimation requires. The neighborhood smoothing method requires little tuning, has a competitive mean-squared error rate, and outperforms many benchmark methods on link prediction in simulated and real networks.
  @cite_16: Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that defines an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.
  @cite_25: Consider the problem of estimating the entries of a large matrix, when the observed entries are noisy versions of a small random fraction of the original entries. This problem has received widespread attention in recent times, especially after the pioneering works of Emmanuel Cand e s and collaborators. This paper introduces a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that works for any matrix that has "a little bit of structure." Surprisingly, this simple estimator achieves the minimax error rate up to a constant factor. The method is applied to solve problems related to low rank matrix estimation, blockmodels, distance matrix completion, latent space models, positive definite matrix completion, graphon estimation and generalized Bradley--Terry models for pairwise comparison.
  @cite_21: 
summary: Another related approach to segment the dyads is to group the vertices via a community detection method. The stochastic block model is a special instance of the graphon model which assumes that there are latent communities for the vertices and the probability of attachment between two vertices is a function only of the communities to which the vertices belong. This can be thought of as segmenting the dyads by taking the Cartesian product of the vertex communities, but this type of segmentation is restrictive because of this specialized structure. Heuristic or greedy methods for fitting the SBM for graphon estimation have been proposed in @cite_16 @cite_21 , but little is known about the statistical performance and whether these can achieve minimax performance. In another approach, @cite_25 proposed a spectral method that thresholds singular values and provided some MSE consistency guarantees. Currently, the best rate guarantee for a computationally tractable estimator of Lipschitz graphons is achieved by the aforementioned neighborhood smoothing method of @cite_1 , and the MSE scales like @math , which is significantly worse than the minimax rate of @math .