Title: Counting Motifs with Graph Sampling,
Abstract: Applied researchers often construct a network from a random sample of nodes
in order to infer properties of the parent network. Two of the most widely used
sampling schemes are subgraph sampling, where we sample each vertex
independently with probability $p$ and observe the subgraph induced by the
sampled vertices, and neighborhood sampling, where we additionally observe the
edges between the sampled vertices and their neighbors.
In this paper, we study the problem of estimating the number of motifs as
induced subgraphs under both models from a statistical perspective. We show
that: for any connected $h$ on $k$ vertices, to estimate $s=\mathsf{s}(h,G)$,
the number of copies of $h$ in the parent graph $G$ of maximum degree $d$, with
a multiplicative error of $\epsilon$, (a) For subgraph sampling, the optimal
sampling ratio $p$ is $\Theta_{k}(\max\{ (s\epsilon^2)^{-\frac{1}{k}}, \;
\frac{d^{k-1}}{s\epsilon^{2}} \})$, achieved by Horvitz-Thompson type of
estimators. (b) For neighborhood sampling, we propose a family of estimators,
encompassing and outperforming the Horvitz-Thompson estimator and achieving the
sampling ratio $O_{k}(\min\{ (\frac{d}{s\epsilon^2})^{\frac{1}{k-1}}, \;
\sqrt{\frac{d^{k-2}}{s\epsilon^2}}\})$. This is shown to be optimal for all
motifs with at most $4$ vertices and cliques of all sizes.
The matching minimax lower bounds are established using certain algebraic
properties of subgraph counts. These results quantify how much more informative
neighborhood sampling is than subgraph sampling, as empirically verified by
experiments on both synthetic and real-world data. We also address the issue of
adaptation to the unknown maximum degree, and study specific problems for
parent graphs with additional structures, e.g., trees or planar graphs.