UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models

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). Green open access

[thumbnail of 12523_the_graph_pencil_method_mappin.pdf]
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
Downloads since deposit
24Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item