Gunderson, lee M;
Bravo-Hermsdorff, Gecia;
Orbanz, Peter;
(2023)
The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models.
In:
Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS 2023).
(pp. pp. 1-11).
NeurIPS
(In press).
Preview |
Text
12523_the_graph_pencil_method_mappin.pdf - Accepted Version Download (629kB) | Preview |
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.
| Type: | Proceedings paper |
|---|---|
| Title: | The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models |
| Event: | 37th Conference on Neural Information Processing Systems (NeurIPS 2023) |
| Location: | New Orleans, LA, USA |
| Dates: | 10th-16th December 2023 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://openreview.net/forum?id=uN71BdBEG8 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | Stochastic block model, SBM, graphons, matrix pencil method, method of moments |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Gatsby Computational Neurosci Unit |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10181235 |
Archive Staff Only
 |
View Item |
