Hypergraph reconstruction from uncertain pairwise observations

Simon Lizotte; Jean-Gabriel Young; Antoine Allard

doi:10.1038/s41598-023-48081-w

Hypergraph reconstruction from uncertain pairwise observations

Sci Rep. 2023 Dec 4;13(1):21364. doi: 10.1038/s41598-023-48081-w.

Authors

Simon Lizotte^{1

2}, Jean-Gabriel Young^{1

3

4}, Antoine Allard^{5

6

7}

Affiliations

¹ Département de Physique, de génie Physique et d'optique, Université Laval, Québec, G1V 0A6, Canada.
² Centre Interdisciplinaire en Modélisation Mathématique, Université Laval, Québec, G1V 0A6, Canada.
³ Department of Mathematics and Statistics, University of Vermont, Burlington, VT, 05405, USA.
⁴ Vermont Complex Systems Center, University of Vermont, Burlington, VT, 05405, USA.
⁵ Département de Physique, de génie Physique et d'optique, Université Laval, Québec, G1V 0A6, Canada. antoine.allard@phy.ulaval.ca.
⁶ Centre Interdisciplinaire en Modélisation Mathématique, Université Laval, Québec, G1V 0A6, Canada. antoine.allard@phy.ulaval.ca.
⁷ Vermont Complex Systems Center, University of Vermont, Burlington, VT, 05405, USA. antoine.allard@phy.ulaval.ca.

Abstract

The network reconstruction task aims to estimate a complex system's structure from various data sources such as time series, snapshots, or interaction counts. Recent work has examined this problem in networks whose relationships involve precisely two entities-the pairwise case. Here, using Bayesian inference, we investigate the general problem of reconstructing a network in which higher-order interactions are also present. We study a minimal example of this problem, focusing on the case of hypergraphs with interactions between pairs and triplets of vertices, measured imperfectly and indirectly. We derive a Metropolis-Hastings-within-Gibbs algorithm for this model to highlight the unique challenges that come with estimating higher-order models. We show that this approach tends to reconstruct empirical and synthetic networks more accurately than an equivalent graph model without higher-order interactions.