The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models
Lee M. Gunderson, Gecia Bravo-Hermsdorff, Peter Orbanz
Abstract
In this work, we describe a method that determines an exact map from a finite set of subgraph densities to the parameters of a stochastic block model (SBM) matching these densities. Given a number K of blocks, the subgraph densities of a finite number of stars and bistars uniquely determines a single element of the class of all degree-separated stochastic block models with K blocks. Our method makes it possible to translate estimates of these subgraph densities into model parameters, and hence to use subgraph densities directly for inference. The computational overhead is negligible; computing the translation map is polynomial in K, but independent of the graph size once the subgraph densities are given.
BibTeX
@inproceedings{
gunderson2023the,
title={The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models},
author={Lee M. Gunderson and Gecia Bravo-Hermsdorff and Peter Orbanz},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=uN71BdBEG8}
}