A fundamental question in neuroscience is how neural networks generate behavior. The lack of genetic tools and unique promoters to functionally manipulate specific neuronal subtypes makes it challenging to determine the roles of individual subtypes in behavior. We describe a compressed sensing-based framework in combination with non-specific genetic tools to infer candidate neurons controlling behaviors with fewer measurements than previously thought possible. We tested this framework by inferring interneuron subtypes regulating the speed of locomotion of the nematode Caenorhabditis elegans. We developed a real-time stabilization microscope for accurate long-term, high-magnification imaging and targeted perturbation of neural activity in freely moving animals to validate our inferences. We show that a circuit of three interconnected interneuron subtypes, RMG, AVB and SIA control different aspects of locomotion speed as the animal navigates its environment. Our work suggests that compressed sensing approaches can be used to identify key nodes in complex biological networks.