Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
arXiv:1805.07042
Abstract
We propose a class of methods for graphon estimation based on exploiting connections with nonparametric regression. The idea is to construct an ordering of the nodes in the network, similar in spirit to Chan and Airoldi (2014). However, rather than only considering orderings based on the empirical degree as in Chan and Airoldi (2014), we use the nearest neighbor algorithm which is an approximating solution to the traveling salesman problem. This in turn can handle general distances between the nodes, something that allows us to incorporate rich information of the network. Once an ordering is constructed, we formulate a 2D grid graph denoising problem that we solve through fused lasso regularization. For particular choices of the metric , we show that the corresponding two-step estimator can attain competitive rates when the true model is the stochastic block model, and when the underlying graphon is piecewise Hölder or it has bounded variation.
References in corpus (11)
- Matrix estimation by Universal Singular Value Thresholding
- Rate-optimal graphon estimation
- Nonparametric graphon estimation
- Modular proximal optimization for multidimensional total-variation regularization
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- A Consistent Histogram Estimator for Exchangeable Graph Models
- Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
- The DFS Fused Lasso: Linear-Time Denoising over General Graphs
- Hitting and commute times in large graphs are often misleading
- Estimating network edge probabilities by neighborhood smoothing
- Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing