Publisher = {JMLR Workshop and Conference Proceedings},

Title = {A Consistent Histogram Estimator for Exchangeable Graph Models},

Url = {http://jmlr.org/proceedings/papers/v32/chan14.pdf},

Abstract = {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.},

Author = {Stanley Chan and Edoardo Airoldi},

Editor = {Tony Jebara and Eric P. Xing},

Year = {2014},

Booktitle = {Proceedings of the 31st International Conference on Machine Learning (ICML-14)},

Pages = {208-216}

}