Graphon estimation via nearest-neighbour algorithm and two-dimensional fused-lasso denoising

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 & Airoldi (2014). However, rather than considering orderings based only on the empirical degree as in Chan & Airoldi (2014), we use the nearest-neighbour algorithm which is an approximative solution to the travelling salesman problem. This algorithm in turn can handle general distances $\widehat{d}$ between the nodes, allowing us to incorporate rich information from the network. Once an ordering is constructed, we formulate a two-dimensional-grid graph-denoising problem that we solve through fused-lasso regularization. For particular choices of the metric $\widehat{d}$, 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 has bounded variation.