  A key problem in statistics and machine learning is the determination of
network structure from data. We consider the case where the structure of the
graph to be reconstructed is known to be scale-free. We show that in such cases
it is natural to formulate structured sparsity inducing priors using submodular
functions, and we use their Lov\'asz extension to obtain a convex relaxation.
For tractable classes such as Gaussian graphical models, this leads to a convex
optimization problem that can be efficiently solved. We show that our method
results in an improvement in the accuracy of reconstructed networks for
synthetic data. We also show how our prior encourages scale-free
reconstructions on a bioinfomatics dataset.
