PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey and Taxonomy of Graph Sampling

Pili Hu, Wing Cheong Lau

arXiv:1308.5865v1cs.SImath.PRstat.ME

TL;DR

Graph sampling seeks efficient smaller or exploratory graph representations while preserving properties useful for estimation and graph algorithms. This survey organizes sampling objectives and approaches, examines property preservation and estimation, and identifies open evaluation gaps while illustrating problem-oriented preservation with min-cut.

  • Problem

    Graph properties are important for understanding networks, but evidence on their preservation and estimation under different sampling procedures remains limited and ad hoc.

  • Method

    The survey connects sampling procedures with property estimation and problem-oriented property preservation, including bias correction when sampling does not preserve properties directly.

  • Results

    The survey identifies comprehensive, neutral evaluation as an open need and uses a simple min-cut improvement to illustrate problem-oriented property preservation.

  • Takeaways & Limitations

    Preserved or correctable graph properties can support efficient estimators and may enable probabilistic acceleration of graph-algorithm classes with bounded loss of optimality.

  • Takeaways & Limitations

    Random-walk-based traversal sampling can require substantially more probes, including burn-in and sampling gaps, when mimicking vertex or edge sampling.

Abstract

from arXiv · show

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.

1 Introduction

Graph sampling reduces graph size by selecting vertices or edges, supporting applications from hidden-population surveys and visualization to sparsification and lower testing costs. The survey organizes sampling objectives and approaches while highlighting the cost and information-access limits of more complex alternatives.

  • Motivation: Graph sampling selects subsets of vertices or edges to transform large or inaccessible graphs efficiently.Its value depends on whether the sampled graph preserves properties useful for estimation or downstream algorithms.
  • Applications: Applications include hidden-population surveys, graph sparsification, interaction testing, and social-graph visualization.These settings differ in mathematical depth and whether the original graph is fully accessible.
  • Common characteristics: Sampling reduces graph size while seeking outputs that remain representative or similar to the original graph.The expected output properties provide common ground across otherwise different applications.
  • Why simple sampling: Complex optimization-based transformations can be costly; graph cut sparsification is NP-Hard, and even polynomial approximations may remain too complex.Such methods may also require global graph knowledge unavailable in decentralized or partially observed settings.
  • Survey scope: The survey covers a taxonomy of objectives, graph types, and sampling approaches, followed by property analyses, theoretical results, and future directions.It emphasizes that prior numerical evaluations were ad hoc and calls for systematic, neutral evaluation.

2 Common Notations and Definitions

The paper defines graph properties as functions of graphs and formalizes the sampled graph, graph variants, neighborhoods, boundaries, and probing costs used throughout the survey.

  • Graph notation: The default graph is unweighted and undirected, G = <V, E>, with n = |V| and m = |E|.Weighted and directed variants are defined separately.
  • Sampled graphs: For a sampled graph Gs = <Vs, Es>, validity conditions ensure sampled elements come from the original graph and form a valid graph.The sampled sizes are denoted ns = |Vs| and ms = |Es|.
  • Probing: A probing operation obtains graph information, such as a buddy list or referrals, with budget B and typically unit cost b.Both cost and information depend on the application scenario.
  • Properties: A graph property is defined as a function f(G), which may be vector-valued and may differ from an indicator-based random-graph definition.For example, connectedness can be represented by the number of connected components.

3 A Taxonomy of Sampling

The taxonomy organizes graph sampling by objectives, graph models, and approaches, linking preservation, estimation, and algorithm support. It also formalizes how traversal methods relate to classical sampling and the practical costs of those relations.

  • Objectives: The survey distinguishes representative-subset selection, property preservation, property estimation, algorithm support, and graph generation as sampling-related objectives.Its main focus is property preservation, while also discussing estimation and problem-oriented property preservation.
  • Preservation and use: Preserved properties can support estimators and similar algorithm outputs on sampled graphs, while efficient methods can accelerate classes of graph algorithms.The paper names this algorithm-focused perspective Problem Oriented Property Preservation (POPP).
  • Preservation versus estimation: Property preservation can yield estimation, but estimation results cannot generally be converted easily into preservation results.Direct estimation may be simpler because preservation requirements are often stronger than needed.
  • Graph types: Theoretical analyses commonly assume Erdos-Renyi, power-law, small-world, or fixed-degree-distribution random graph models because arbitrary real networks lack a common generation model.Evaluations span social, biological, Internet AS, and P2P networks.
  • Approaches: Vertex Sampling and Edge Sampling are classical building blocks, while Traversal Based Sampling forms a broad class discussed in greater depth.The survey also studies relations between sampling approaches and connects theoretical analysis with practical implementation.
  • Traversal relations: Random Walk yields uniform edge distribution on undirected graphs, whereas Metropolis-Hastings Random Walk yields uniform vertex distribution.These properties bridge traversal-based implementation and vertex- or edge-sampling analyses.
  • Traversal costs: Mimicking vertex or edge sampling with traversal methods can waste probes through burn-in and spacing between samples.Direct traversal-based estimation can instead exploit correlated samples for some properties, including clustering coefficient.

4 Traversal Based Sampling

Traversal Based Sampling explores graphs through topology, using walks, breadth/depth expansion, snowball procedures, and related methods. The section emphasizes sampling distributions, estimator bias, and practical costs.

  • Traversal Based Sampling, also called topology-based sampling or sampling by exploration, includes classical and recent graph-exploration techniques.
  • Traversal frameworks: BFS, DFS, and random-first search differ primarily in how they dequeue queued vertices, while sampled vertices are the visited set.
  • Snowball Sampling: Snowball Sampling begins with seed vertices and repeatedly collects named neighbors for a fixed number of stages, producing a sampled graph.
  • Random Walk: Random Walk samples edges uniformly on connected, non-bipartite undirected graphs, but visits vertices with probability proportional to degree.
  • Metropolis-Hastings Random Walk: MHRW can tailor the stationary distribution to a desired vertex distribution, including uniform sampling, by enforcing detailed balance.
  • Costs and limitations: Traversal sampling can require burn-in, spacing between samples, and additional probes; random walks may also become trapped in dense local regions.
  • Respondent Driven Sampling: RDS combines snowball or random-walk sampling with Hansen-Hurwitz estimation to correct sampling bias when estimating vertex-label means.

5 Graph Properties

The survey formalizes graph properties as functions or label distributions and catalogs structural measures ranging from degree and density to paths, centrality, clustering, and assortativity. It also notes that theoretical preservation results remain sparse.

  • A graph property is a function f(G), while vertex and edge label distributions provide general frameworks for defining properties and constructing estimators.
  • Label distributions: Uniform sampling of vertices or edges is central to preserving label-distribution properties and estimating them from sampled graphs.
  • Label distributions: The label-distribution framework assumes labels can be efficiently acquired after sampling, but acquisition differs across algorithms and properties.
  • Classical properties: The catalog includes network size, degree distribution, average degree, power-law exponent, density, path matrices, shortest paths, and centrality measures.
  • Classical properties: It also covers path length, radius, diameter, betweenness, assortativity, clustering coefficients, and self-similarity.
  • Many properties have been studied numerically, but relatively few have received theoretical analysis in the surveyed literature.
  • Additional criteria: Adjacency-matrix and quadratic degree-matrix criteria are proposed as alternatives because adjacency captures association information not readily available from the Laplacian.
  • Scope boundary: Properties defined on the full vertex set are difficult to interpret when vertex sets differ, so they are commonly studied with edge sampling.

6 Property Preservation/ Estimation Results

The survey reviews estimators for graph size, density, coverage, and sampling efficiency, while emphasizing that preservation and estimation results are incomplete and often ad hoc. Coverage depends strongly on the sampling mechanism.

  • Network-size estimation has received relatively little graph-specific study, despite prior population-estimation methods that can estimate related quantities.
  • Network size: Estimating average degree, density, or network size can enable estimation of the remaining quantities through graph identities.
  • Average degree: Random-walk samples favor high-degree vertices, so RDS can correct this bias when estimating average degree.
  • Population estimation: Classical population estimators include capture-recapture, unique-element counting, and collision counting, with accuracy itself requiring further analysis.
  • Coverage: With replacement, observing the whole vertex set requires Θ(nlnn+c n) samples, while observing 1−ε coverage follows a coupon-collector threshold.
  • Coverage: Without replacement, uniform vertex sampling needs at least (1−ε)n samples to observe 1−ε of the vertices.
  • Neighborhood sampling: Uniform neighborhood sampling is ⟨d⟩ times more efficient than vertex sampling because each sampled vertex reveals neighbors.
  • Traversal coverage: For small-world graphs, random-walk coverage of 1−ε of vertices takes 2m ln n log2(1/ε) steps under the stated analysis.

6.3 Degree Distribution

The degree-distribution analysis compares vertex, edge, neighborhood, and traversal sampling. Sampling generally lowers observed degrees, but weighting or neighborhood information can recover the original distribution asymptotically.

  • The sampled degree distribution is defined by the probability that a randomly selected sampled vertex has degree k.
  • Vertex and edge sampling: Under independent vertex sampling with fixed fraction α, the degree distribution follows a limiting expression as the graph grows.
  • Vertex and edge sampling: Edge sampling yields the same asymptotic degree-distribution result as the corresponding vertex-sampling expression.
  • Degree estimation: Sampled vertices generally have lower degree than original vertices, while inverse-probability edge weighting can estimate the original degree distribution.
  • Neighborhood sampling: Neighborhood sampling provides precise degrees for crawled vertices, and its estimated degree distribution is asymptotically the original distribution.
  • Bias correction: For edge sampling, degree observations can be biased toward high-degree edges, but a normalized correction produces an asymptotically matching distribution.
  • Traversal sampling: Breadth First Sampling has been reported to exhibit bias toward high-degree vertices.
  • Graph classes: The discussion covers general graphs and notes separate results for scale-free and Erdős-Rényi graph families.

6.4 Minimum Cut

This section studies edge sampling with contraction (ESC) as a way to preserve the minimum cut while reducing the graph, then runs a deterministic min-cut algorithm on the sampled graph. Early stopping enables a framework whose repeated experiments recover the min-cut with high probability and can improve the O(n^4) randomized baseline.

  • Complexity: The resulting min-cut algorithm has complexity below O(n^3), improving on the best deterministic O(n^3) algorithm and the O(n^4) randomized contraction algorithm.The contraction procedure and sampled-graph min-cut computation are combined into the stated complexity result.
  • Framework: The framework uses simple graph reduction to preserve a property and then applies an algorithm that depends on that property to obtain approximately the same result.This is presented as the core objective of the sampling framework.
  • Edge Sampling with Contraction: ESC repeatedly contracts arbitrary edges until r vertices remain, then runs a deterministic min-cut algorithm on the resulting sampled graph.The framework repeats this process and returns the smallest cut found.
  • Probability of Preservation: Repeating ESC sufficiently often yields the minimum cut with high probability, extending the basic contraction approach that stops at two vertices.The r=2 case has high failure probability and therefore requires Θ(n^2) repetitions to obtain the real minimum cut with high probability.
  • Probability of Preservation: The method preserves the minimum cut when no contracted edge belongs to that cut, and its preservation probability is analyzed after n−r contraction rounds.The analysis defines events for avoiding the minimum-cut edges and derives the corresponding survival probability.
  • Extensions and Scope: The analysis leaves extensions for graph sparsity and vertex sampling, while the vertex-sampling-with-contraction complexity is much larger than ESC.For sparse graphs, an O(nm) deterministic algorithm may already be better than O(n^3), and the approximate-min-cut extension is deferred.

6.5 Cut

The section surveys edge-sampling methods for preserving graph cuts and Laplacian quadratic forms, including uniform and effective-resistance-based schemes. Uniform sampling preserves all cuts with high probability under stated conditions, while non-uniform methods relax constraints or provide ε-approximations.

  • Uniform Edge Sampling: Uniform edge sampling selects each edge with probability p and assigns sampled edges weight 1/p.This weighting preserves the expected size and weight of every cut.
  • Uniform Edge Sampling: The failure probability for preserving cut S is at most 2e^(-p|δG(S)|ε^2/3).The analysis combines this bound with a count of cuts by size and a union bound.
  • Uniform Edge Sampling: All cuts are preserved with high probability under the sampling conditions.The result follows from applying the union bound over cuts.
  • Non-uniform Edge Sampling: Non-uniform edge sampling increases sampling probabilities on sparse cuts and decreases them on dense cuts, reducing the edge count to O(n ln n).This approach relaxes the constraint that the minimum cut c must satisfy c = Ω(ln n).
  • Scope: Several parts of the sampling and sparsification discussion remain incomplete and are deferred to a future version.The text repeats this limitation for multiple sections.
  • Effective-Resistance Sampling: Effective-resistance sampling sets edge probabilities using effective resistance and yields an ε-approximation for Laplacian quadratic forms.The method samples edges with probability p_e and increases their weights by w_e / p_e.
  • Effective-Resistance Sampling: Effective resistance is defined through voltage difference under a one-Ampere injection and removal, with edge conductance equal to inverse resistance.The section also relates effective resistance to graph Laplacians through a pseudoinverse expression.

7 Conclusion and Future Works

The conclusion identifies graph sampling as broadly useful but finds that property-preservation theory and numerical evaluation remain fragmented. It calls for systematic evaluation, synthesized-data studies, stronger theoretical analysis, and further development of problem-oriented property preservation.

  • Current Gaps: Graph sampling has broad applications, but theoretical analyses of property preservation and numerical evaluations remain limited and ad hoc.Prior evaluations vary across criteria, algorithms, graphs, and properties.
  • Future Evaluation: A comprehensive neutral evaluation should cover combinations of properties, algorithms, criteria, and graph models.The survey identifies a large vacancy across this combination space.
  • Future Evaluation: Synthesized datasets are underused, although they may reveal relationships between sampling algorithms and graph properties.Real-network evaluations remain useful for judging practical applicability.
  • Theory: Only a few theoretical studies exist, with degree distribution and its derivatives being the best-understood properties.The survey notes that some easier properties remain analytically tractable.
  • Traversal Based Sampling: Traversal Based Sampling is popular and promising for large-graph crawling, but most works lack theoretical analyses of estimator variance and efficiency.The survey points to existing analyses as a foundation for future applications.
  • Problem Oriented Property Preservation: Problem Oriented Property Preservation remains in its infancy but may support probabilistic acceleration of graph algorithms with bounded loss of optimality.The survey presents a min-cut improvement as an example and calls for further investigation.

Appendix A Useful Probability Results

The appendix collects Chernoff bounds for heterogeneous Bernoulli variables and a cut-counting lemma used in the survey’s sampling analyses.

  • Chernoff Bounds: For heterogeneous coin flips, the sum X has expectation determined by the individual head probabilities.The theorem considers variables X_i with potentially different probabilities p_i.
  • Chernoff Bounds: For 0 < δ < 1, the upper-tail probability satisfies Pr{X ≥ (1 + δ)µ} < e^(-δ^2µ/3).This is presented as one of the specific Chernoff-bound forms.
  • Chernoff Bounds: For 0 < δ < 1, the two-sided deviation probability satisfies Pr{|X − µ| ≥ δµ} ≤ e^(-µδ^2/3).The appendix describes this as a frequently used form derived from one-sided bounds.
  • Extensions: The same probability results extend to variables uniformly distributed on [0, 1] with E[X_i] = p_i.This is identified as Hoeffding’s extension.
  • Cut Counting: There are at most n^(2α) cuts with αc edges, where c is the minimum-cut value.This lemma supports union-bound arguments over cuts.

Appendix C Other Works

The appendix briefly lists related graph-sampling studies that were not systematically covered in the survey. These works address directed graphs, streaming edge sampling, graph induction after edge sampling, and problem-oriented property preservation.

  • Scope: Several related graph-sampling works were identified but deferred for fuller organization in a future version.The appendix presents them as briefly mentioned related work rather than a systematic treatment.
  • Related Approaches: The cited studies include sampling on directed graphs, streaming large edge samples from social activity graphs, and topology induction after edge sampling.The topology-induction setting processes activity edges in temporal order and samples the topology in one pass.
  • Problem-Oriented Preservation: One cited work applies Problem Oriented Property Preservation to make a sampled graph mimic the original graph.The passage identifies it as a PPOP work without providing further methodological detail.
Loading 1308.5865v1…