Network reconstruction via the minimum description length principle

Abstract

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 $L_1$ 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 $10^4$ to $10^5$ species, and demonstrate how the inferred model can be used to predict the outcome of interventions in the system.

arXiv comment18 pages, 9 figures. Code and documentation are available at https://graph-tool.skewed.de/static/doc/demos/reconstruction_indirect/reconstruction.html

References in corpus (27)

• Community structure in social and biological networks
• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional graphs and variable selection with the Lasso
• Stochastic blockmodels and community structure in networks
• Sparse and compositionally robust inference of microbial ecological networks
• Rank-normalization, folding, and localization: An improved $\hat{R}$ for assessing convergence of MCMC
• Identification of direct residue contacts in protein-protein interaction by message passing
• Sparse permutation invariant covariance estimation
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Inverse statistical problems: from the inverse Ising problem to data science
• Inverse Statistical Physics of Protein Sequences: A Key Issues Review
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Causal Network Inference by Optimal Causation Entropy
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Inverse Ising inference using all the data
• Network reconstruction and community detection from dynamics
• Bayesian Structure Learning in Sparse Gaussian Graphical Models
• Transfer Entropy reconstruction and labeling of neuronal connections from simulated calcium imaging
• Scaling It Up: Stochastic Search Structure Learning in Graphical Models
• Pseudolikelihood Decimation Algorithm Improving the Inference of the Interaction Network in a General Class of Ising Models
• Merge-split Markov chain Monte Carlo for community detection
• Thresholding normally distributed data creates complex networks
• Network reconstruction from infection cascades
• Consistent inference of a general model using the pseudo-likelihood method
• A statistical physics perspective on criticality in financial markets
• L1-Penalized Censored Gaussian Graphical Model
• Random graphical model of microbiome interactions in related environments

Cited by in corpus (2)

• Emergence of network communities driven by local rules
• Structured Interactions Drive Abrupt Transitions in the Spatial Organization of Microbial Communities