Sparse signal processing on graphs arises in several applications including IP networks, wireless sensor networks (WSN) and infection propagation. For instance, in IP and WSNs a key problem is to identify a sparse subset of congested links and/or failing sensor nodes from path measurements. We develop sample complexity bounds for the number of path measurements required to recover such sparse subsets associated with the graph. To develop sample complexity scaling bounds we consider random path measurements associated with random walks on large graphs. Our main result is that sample complexity, namely, the number of path measurements required for sparse signal processing on expander-type graphs with path measurements is similar to that required when no such constraints---as in compressive sensing with random projections --- are imposed on the measurements.