"A Consistent Histogram Estimator for Exchangeable Graph Models" is accepted to ICML 2014

February 3, 2014

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.

Accepted to International Conference on Machine Learning 2014 (1st round acceptance rate: 85/577 = 15.7%).

Paper is available at http://jmlr.org/proceedings/papers/v32/chan14.html

Reproducible MATLAB code is available at https://github.com/airoldilab/SAS