# Network reconstruction via the minimum description length principle

arXiv: https://arxiv.org/abs/2405.01015 · HTML: https://mlsanity.com/paper/2405.01015/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 90 references that are in the map.
- First posted on arXiv 2 May 2024.

## Builds on (most cited first, 22 of 22)

- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Rank-normalization, folding, and localization: An improved widehatR for assessing convergence of MCMC](https://mlsanity.com/paper/1903.08008/) (2019)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Inverse statistical problems: from the inverse Ising problem to data science](https://mlsanity.com/paper/1702.01522/) (2017)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [Optimal structure and parameter learning of Ising models](https://mlsanity.com/paper/1612.05024/) (2016)
- [Nonparametric Bayesian inference of the microcanonical stochastic block model](https://mlsanity.com/paper/1610.02703/) (2016)
- [Network reconstruction and community detection from dynamics](https://mlsanity.com/paper/1903.10833/) (2019)
- [Merge-split Markov chain Monte Carlo for community detection](https://mlsanity.com/paper/2003.07070/) (2020)
- [The Graphical Horseshoe Estimator for Inverse Covariance Matrices](https://mlsanity.com/paper/1707.06661/) (2017)
- [Network reconstruction from infection cascades](https://mlsanity.com/paper/1609.00432/) (2016)
- [Scaling It Up: Stochastic Search Structure Learning in Graphical Models](https://mlsanity.com/paper/1505.01687/) (2015)
- [Bayesian Structure Learning in Undirected Gaussian Graphical Models: Literature Review with Empirical Comparison](https://mlsanity.com/paper/2307.02603/) (2023)
- [Transfer Entropy reconstruction and labeling of neuronal connections from simulated calcium imaging](https://mlsanity.com/paper/1309.4287/) (2013)
- [L1-Penalized Censored Gaussian Graphical Model](https://mlsanity.com/paper/1801.07981/) (2018)
- [Bayesian Joint Spike-and-Slab Graphical Lasso](https://mlsanity.com/paper/1805.07051/) (2018)
- [Scalable network reconstruction in subquadratic time](https://mlsanity.com/paper/2401.01404/) (2024)
- [Thresholding normally distributed data creates complex networks](https://mlsanity.com/paper/1902.08278/) (2019)
- [Random graphical model of microbiome interactions in related environments](https://mlsanity.com/paper/2304.01956/) (2023)

## Built on by (most cited first, 5 of 5)

- [Uncertainty quantification and posterior sampling for network reconstruction](https://mlsanity.com/paper/2503.07736/) (2025)
- [REGE: A Method for Incorporating Uncertainty in Graph Embeddings](https://mlsanity.com/paper/2412.05735/) (2024)
- [Variational Physics-Informed Ansatz for Reconstructing Hidden Interaction Networks from Steady States](https://mlsanity.com/paper/2512.13708/) (2025)
- [DynaSTy: A Framework for SpatioTemporal Node Attribute Prediction in Dynamic Graphs](https://mlsanity.com/paper/2601.05391/) (2026)
- [GraIP: A Benchmarking Framework For Neural Graph Inverse Problems](https://mlsanity.com/paper/2601.18917/) (2026)

## Abstract (arXiv)

A fundamental problem associated with the task of network reconstruction from dynamical or behavioral data consists in determining the most appropriate model complexity in a manner that prevents overfitting, and produces an inferred network with a statistically justifiable number of edges. The status quo in this context is based on L1 regularization combined with cross-validation. However, besides its high computational cost, this commonplace approach unnecessarily ties the promotion of sparsity with weight "shrinkage". This combination forces a trade-off between the bias introduced by shrinkage and the network sparsity, which often results in substantial overfitting even after cross-validation. In this work, we propose an alternative nonparametric regularization scheme based on hierarchical Bayesian inference and weight quantization, which does not rely on weight shrinkage to promote sparsity. Our approach follows the minimum description length (MDL) principle, and uncovers the weight distribution that allows for the most compression of the data, thus avoiding overfitting without requiring cross-validation. The latter property renders our approach substantially faster to employ, as it requires a single fit to the complete data. As a result, we have a principled and efficient inference scheme that can be used with a large variety of generative models, without requiring the number of edges to be known in advance. We also demonstrate that our scheme yields systematically increased accuracy in the reconstruction of both artificial and empirical networks. We highlight the use of our method with the reconstruction of interaction networks between microbial communities from large-scale abundance samples involving in the order of 104 to 105 species, and demonstrate how the inferred model can be used to predict the outcome of interventions in the system.