The importance of dilution in the inference of biological networks

One of the crucial tasks in many inference problems is the extraction of an underlying sparse graphical model from a given number of high-dimensional measurements. In machine learning, this is frequently achieved using, as a penalty term, the L
_p
norm of the model parameters, with p ¿ 1 for efficient dilution. Here we propose a statistical-mechanics analysis of the problem in the setting of perceptron memorization and generalization. Using a replica approach, we are able to evaluate the relative performance of naive dilution (obtained by learning without dilution, following by applying a threshold to the model parameters), L
₁
dilution (which is frequently used in convex optimization) and L
₀
dilution (which is optimal but computationally hard to implement). Whereas both L
_p
diluted approaches clearly outperform the naive approach, we find a small region where L
₀
works almost perfectly and strongly outperforms the simpler to implement L
₁
dilution. In the second part we propose an efficient message-passing strategy in the simpler case of discrete classification vectors, where the norm L
₀
norm coincides with the L
₁
. Some examples are discussed.