Inferring connectivity in neuronal networks remains a key challenge in statistical neuroscience. The common input problem presents a major roadblock: it is difficult to reliably distinguish causal connections between pairs of observed neurons versus correlations induced by common input from unobserved neurons. Available techniques allow us to simultaneously record, with sufficient temporal resolution, only a small fraction of the network. Consequently, naive connectivity estimators that neglect these common input effects are highly biased. In a recent work [1] we propose a shotgun experimental design, in which we observe multiple subnetworks briefly, in a serial manner. Thus, while the full network cannot be observed simultaneously at any given time, we may be able to observe much larger subsets of the network over the course of the entire experiment, thus ameliorating the common input problem. To perform network inference given this type of data, in which only a small fraction of the network is observed in each time bin, we developed a scalable Bayesian method. The method is derived using a cavity-style approximation to the gradient of the expected loglikelihood - in a generalized linear model for a spiking recurrent neural network. Simulation demonstrated that the shotgun experimental design can eliminate the biases induced by common input effects. Networks with thousands of neurons, in which only a small fraction of the neurons is observed in each time bin, can be quickly and accurately estimated, achieving orders of magnitude speed up over previous approaches.