  This work considers the general task of estimating the sum of a bounded
function over the edges of a graph, given neighborhood query access and where
access to the entire network is prohibitively expensive. To estimate this sum,
prior work proposes Markov chain Monte Carlo (MCMC) methods that use random
walks started at some seed vertex and whose equilibrium distribution is the
uniform distribution over all edges, eliminating the need to iterate over all
edges. Unfortunately, these existing estimators are not scalable to massive
real-world graphs. In this paper, we introduce Ripple, an MCMC-based estimator
that achieves unprecedented scalability by stratifying the Markov chain state
space into ordered strata with a new technique that we denote {\em sequential
stratified regenerations}. We show that the Ripple estimator is consistent,
highly parallelizable, and scales well.
  We empirically evaluate our method by applying Ripple to the task of
estimating connected, induced subgraph counts given some input graph. Therein,
we demonstrate that Ripple is accurate and can estimate counts of up to
$12$-node subgraphs, which is a task at a scale that has been considered
unreachable, not only by prior MCMC-based methods but also by other sampling
approaches. For instance, in this target application, we present results in
which the Markov chain state space is as large as $10^{43}$, for which Ripple
computes estimates in less than $4$ hours, on average.
