This work considers the general task of estimating the sum of a bounded function over the edges of a graph that is unknown a priori, where graph vertices and edges are built on-the-fly by an algorithm and the resulting graph is too large to be kept in memory or disk. Prior work proposes Markov Chain Monte Carlo (MCMC) methods that simultaneously sample and generate the graph , eliminating the need for storage . Unfortunately, these existing methods are not scalable to massive real-world graphs. In this paper, we introduce Ripple, an MCMC-based estimator which achieves unprecedented scalability in this task by stratifying the MCMC Markov chain state space  with a new technique that we denote {\em ordered sequential stratified Markov regenerations}. We show that the Ripple estimator is consistent, highly parallelizable, and scales well. In particular, applying Ripple to the task of estimating connected  induced subgraph counts on large graphs, we empirically demonstrate that Ripple is accurate and is able to estimate counts of up to 12-node subgraphs,  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 where the Markov chain state space is as large as 10^{43}, for which Ripple computes estimates in less than 4 hours  on average.
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.
R
that is unknown a priori, where graph vertices and edges are built on-the-fly by an algorithm and the resulting graph is too large to be kept in memory or disk. Prior
, given neighborhood query access and where access to the entire network is prohibitively expensive. To estimate this sum, prior
R
Chain
chain
R
simultaneously sample and generate the graph
use random walks started at some seed vertex and whose equilibrium distribution is the uniform distribution over all edges
R
for storage
to iterate over all edges
R
methods
estimators
R
which
that
D
in this task
D
MCMC
A
into ordered strata
R
ordered sequential stratified Markov
sequential stratified
R
In particular,
We empirically evaluate our method by
A
,
R
on large graphs, we empirically
given some input graph. Therein, we
R
is able to
can
A
which is
D
,
R
where
in which
A
,