An iterative step-function estimator for graphons
This work addresses graphon estimation for exchangeable graphs, which is incremental as it builds on existing step-function frameworks.
The authors tackled the problem of estimating graphons from a single sampled graph by proposing an iterative step-function estimator (ISFE) that clusters nodes based on edge densities, and demonstrated its performance compared to other techniques.
Exchangeable graphs arise via a sampling procedure from measurable functions known as graphons. A natural estimation problem is how well we can recover a graphon given a single graph sampled from it. One general framework for estimating a graphon uses step-functions obtained by partitioning the nodes of the graph according to some clustering algorithm. We propose an iterative step-function estimator (ISFE) that, given an initial partition, iteratively clusters nodes based on their edge densities with respect to the previous iteration's partition. We analyze ISFE and demonstrate its performance in comparison with other graphon estimation techniques.