Title: Estimating Graphlet Statistics via Lifting,
Abstract: Exploratory analysis over network data is often limited by our ability to
efficiently calculate graph statistics, which can provide a model-free
understanding of macroscopic properties of a network. This work introduces a
framework for estimating the graphlet count - the number of occurrences of a
small subgraph motif (e.g. a wedge or a triangle) in the network. For massive
graphs, where accessing the whole graph is not possible, the only viable
algorithms are those which act locally by making a limited number of vertex
neighborhood queries.
We introduce a Monte Carlo sampling technique for graphlet counts, called
lifting, which can simultaneously sample all graphlets of size up to $k$
vertices. We outline three variants of lifted graphlet counts: the ordered,
unordered, and shotgun estimators. We prove that our graphlet count updates are
unbiased for the true graphlet count, have low correlation between samples, and
have a controlled variance. We compare the experimental performance of lifted
graphlet counts to the state-of-the art graphlet sampling procedures: Waddling
and the pairwise subgraph random walk.