A Consistent Histogram Estimator for Exchangeable Graph Models
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.
Cite
Text
Chan and Airoldi. "A Consistent Histogram Estimator for Exchangeable Graph Models." International Conference on Machine Learning, 2014.Markdown
[Chan and Airoldi. "A Consistent Histogram Estimator for Exchangeable Graph Models." International Conference on Machine Learning, 2014.](https://mlanthology.org/icml/2014/chan2014icml-consistent/)BibTeX
@inproceedings{chan2014icml-consistent,
title = {{A Consistent Histogram Estimator for Exchangeable Graph Models}},
author = {Chan, Stanley and Airoldi, Edoardo},
booktitle = {International Conference on Machine Learning},
year = {2014},
pages = {208-216},
volume = {32},
url = {https://mlanthology.org/icml/2014/chan2014icml-consistent/}
}