  This paper introduces new techniques for sampling attributed networks to
support standard Data Mining tasks. The problem is important for two reasons.
First, it is commonplace to perform data mining tasks such as clustering and
classification of network attributes (attributes of the nodes, including social
media posts). Furthermore, the extraordinarily large size of real-world
networks necessitates that we work with a smaller graph sample. Second, while
random sampling will provide an unbiased estimate of content, random access is
often unavailable for many networks. Hence, network samplers such as Snowball
sampling, Forest Fire, Random Walk, Metropolis-Hastings Random Walk are widely
used; however, these attribute-agnostic samplers were designed to capture
salient properties of network structure, not node content. The latter is
critical for clustering and classification tasks. There are three contributions
of this paper. First, we introduce several attribute-aware samplers based on
Information Theoretic principles. Second, we prove that these samplers have a
bias towards capturing new content, and are equivalent to uniform sampling in
the limit. Finally, our experimental results over large real-world datasets and
synthetic benchmarks are insightful: attribute-aware samplers outperform both
random sampling and baseline attribute-agnostic samplers by a wide margin in
clustering and classification tasks.
