  As the popularity of graph data increases, there is a growing need to count
the occurrences of subgraph patterns of interest, for a variety of
applications. Many graphs are massive in scale and also fully dynamic (with
insertions and deletions of edges), rendering exact computation of these counts
to be infeasible. Common practice is, instead, to use a small set of edges as a
sample to estimate the counts. Existing sampling algorithms for fully dynamic
graphs sample the edges with uniform probability. In this paper, we show that
we can do much better if we sample edges based on their individual properties.
Specifically, we propose a weighted sampling algorithm called WSD for
estimating the subgraph count in a fully dynamic graph stream, which samples
the edges based on their weights that indicate their importance and reflect
their properties. We determine the weights of edges in a data-driven fashion,
using a novel method based on reinforcement learning. We conduct extensive
experiments to verify that our technique can produce estimates with smaller
errors while often running faster compared with existing algorithms.
