The observed functional behavior of a wide variety of large-scale systems is often the result of a network of pairwise interactions. However, in many cases these interactions are hidden from us, because they are either impossible or very costly to be measured directly. In such situations, we are required to infer the network of interactions from indirect information.

Network reconstruction is an important problem with a long history, but most approaches so far proposed suffer from serious limitations, such as poor scalability and statistical inconsistency.

In this talk, I present a principled Bayesian framework to perform network reconstruction that lifts two major limitations: 1. It removes a seemingly unavoidable quadratic algorithmic complexity — corresponding to the putative requirement of each possible pairwise coupling being contemplated at least once — in favor of a subquadratic log-linear complexity; 2. We introduce a nonparametric regularization scheme based on weight quantization that does not rely on weight shrinkage to promote sparsity.

Our approach follows the minimum description length (MDL) principle, and uncovers the network structure and weight distribution that allows for the most compression of the data, thus avoiding overfitting without requiring time-consuming and suboptimal cross-validation.

Taken together both advances yield an overall approach that is not only substantially faster and simpler to employ than the current state of the art, but is also statistically principled and extensible to specialized generative models.

Throughout the talk, I will illustrate applications of the method in uncovering political alliances, stock market dynamics, and ecological interactions.