Title: On Sampling from Massive Graph Streams,
Abstract: We propose Graph Priority Sampling (GPS), a new paradigm for order-based
reservoir sampling from massive streams of graph edges. GPS provides a general
way to weight edge sampling according to auxiliary and/or size variables so as
to accomplish various estimation goals of graph properties. In the context of
subgraph counting, we show how edge sampling weights can be chosen so as to
minimize the estimation variance of counts of specified sets of subgraphs. In
distinction with many prior graph sampling schemes, GPS separates the functions
of edge sampling and subgraph estimation. We propose two estimation frameworks:
(1) Post-Stream estimation, to allow GPS to construct a reference sample of
edges to support retrospective graph queries, and (2) In-Stream estimation, to
allow GPS to obtain lower variance estimates by incrementally updating the
subgraph count estimates during stream processing. Unbiasedness of subgraph
estimators is established through a new Martingale formulation of graph stream
order sampling, which shows that subgraph estimators, written as a product of
constituent edge estimators are unbiased, even when computed at different
points in the stream. The separation of estimation and sampling enables
significant resource savings relative to previous work. We illustrate our
framework with applications to triangle and wedge counting. We perform a
large-scale experimental study on real-world graphs from various domains and
types. GPS achieves high accuracy with less than 1% error for triangle and
wedge counting, while storing a small fraction of the graph with average update
times of a few microseconds per edge. Notably, for a large Twitter graph with
more than 260M edges, GPS accurately estimates triangle counts with less than
1% error, while storing only 40K edges.