  Reconstructing the causal network in a complex dynamical system plays a
crucial role in many applications, from sub-cellular biology to economic
systems. Here we focus on inferring gene regulation networks (GRNs) from
perturbation or gene deletion experiments. Despite their scientific merit, such
perturbation experiments are not often used for such inference due to their
costly experimental procedure, requiring significant resources to complete the
measurement of every single experiment. To overcome this challenge, we develop
the Robust IDentification of Sparse networks (RIDS) method that reconstructs
the GRN from a small number of perturbation experiments. Our method uses the
gene expression data observed in each experiment and translates that into a
steady state condition of the system's nonlinear interaction dynamics. Applying
a sparse optimization criterion, we are able to extract the parameters of the
underlying weighted network, even from very few experiments. In fact, we
demonstrate analytically that, under certain conditions, the GRN can be
perfectly reconstructed using $K = \Omega (d_{max})$ perturbation experiments,
where $d_{max}$ is the maximum in-degree of the GRN, a small value for
realistic sparse networks, indicating that RIDS can achieve high performance
with a scalable number of experiments. We test our method on both synthetic and
experimental data extracted from the DREAM5 network inference challenge. We
show that the RIDS achieves superior performance compared to the
state-of-the-art methods, while requiring as few as ~60% less experimental
data. Moreover, as opposed to almost all competing methods, RIDS allows us to
infer the directionality of the GRN links, allowing us to infer empirical GRNs,
without relying on the commonly provided list of transcription factors.
