Graph sampling is a technique to pick a subset of vertices and/ or edges from
original graph. It has a wide spectrum of applications, e.g. survey hidden
population in sociology [54], visualize social graph [29], scale down Internet
AS graph [27], graph sparsification [8], etc. In some scenarios, the whole
graph is known and the purpose of sampling is to obtain a smaller graph. In
other scenarios, the graph is unknown and sampling is regarded as a way to
explore the graph. Commonly used techniques are Vertex Sampling, Edge Sampling
and Traversal Based Sampling. We provide a taxonomy of different graph sampling
objectives and graph sampling approaches. The relations between these
approaches are formally argued and a general framework to bridge theoretical
analysis and practical implementation is provided. Although being smaller in
size, sampled graphs may be similar to original graphs in some way. We are
particularly interested in what graph properties are preserved given a sampling
procedure. If some properties are preserved, we can estimate them on the
sampled graphs, which gives a way to construct efficient estimators. If one
algorithm relies on the perserved properties, we can expect that it gives
similar output on original and sampled graphs. This leads to a systematic way
to accelerate a class of graph algorithms. In this survey, we discuss both
classical text-book type properties and some advanced properties. The landscape
is tabularized and we see a lot of missing works in this field. Some
theoretical studies are collected in this survey and simple extensions are
made. Most previous numerical evaluation works come in an ad hoc fashion, i.e.
evaluate different type of graphs, different set of properties, and different
sampling algorithms. A systematical and neutral evaluation is needed to shed
light on further graph sampling studies.

本文系统总结了图采样的目标和方法，并对其关系进行了形式化论证，提供了将理论分析与实际应用桥接的通用框架。通过研究哪些图属性在采样过程中得以保留，展现了一种构造高效估算器的方法，并可以加速一类图算法的实现。此外，文章还讨论了一些高级属性，同时指出了该领域中尚有许多未被探索的问题及未来的研究方向。