The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models
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.
Cite
Text
Gunderson et al. "The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models." Neural Information Processing Systems, 2023.Markdown
[Gunderson et al. "The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/gunderson2023neurips-graph/)BibTeX
@inproceedings{gunderson2023neurips-graph,
title = {{The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models}},
author = {Gunderson, Lee and Bravo-Hermsdorff, Gecia and Orbanz, Peter},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/gunderson2023neurips-graph/}
}