Source-linked AI summary
Graph Sample and Hold: A Framework for Big-Graph Analytics
Nesreen K. Ahmed, Nick Duffield, Jennifer Neville, Ramana Kompella
TL;DR
The paper addresses how to estimate multiple properties of massive graphs when exact computation and property-specific sampling are impractical. It proposes Graph Sample and Hold, a one-pass edge-stream framework with small state and unbiased estimators. Experiments report low relative error across graph types, while the clustering treatment and component sampling retain explicit scope limitations.
Problem
The paper addresses the limited availability of one sampling scheme for estimating diverse graph properties efficiently and accurately in massive, connected graphs.
Method
Graph Sample and Hold samples graph edges sequentially in one pass, maintains typically less than 1% of the graph's edges as state, and derives unbiased estimators and variance estimates.
Results
Relative error ranges from 0.02% to 0.95% for samples with ≤40K edges across different graph types, with centered sampling distributions and tighter error bounds as sample size increases.
Takeaways & Limitations
gSH provides a generic framework for estimating multiple graph quantities and their accuracy from a small streaming sample, while supporting parallel variance computation.
Takeaways & Limitations
Sampling disconnections can split an original connected component depending on omitted edges and edge arrival order, and clustering estimation relies on a delta-method approximation whose large-graph asymptotics are deferred.
Abstract
from arXiv · showhide
Sampling is a standard approach in big-graph analytics; the goal is to efficiently estimate the graph properties by consulting a sample of the whole population. A perfect sample is assumed to mirror every property of the whole population. Unfortunately, such a perfect sample is hard to collect in complex populations such as graphs (e.g. web graphs, social networks etc), where an underlying network connects the units of the population. Therefore, a good sample will be representative in the sense that graph properties of interest can be estimated with a known degree of accuracy. While previous work focused particularly on sampling schemes used to estimate certain graph properties (e.g. triangle count), much less is known for the case when we need to estimate various graph properties with the same sampling scheme. In this paper, we propose a generic stream sampling framework for big-graph analytics, called Graph Sample and Hold (gSH). To begin, the proposed framework samples from massive graphs sequentially in a single pass, one edge at a time, while maintaining a small state. We then show how to produce unbiased estimators for various graph properties from the sample. Given that the graph analysis algorithms will run on a sample instead of the whole population, the runtime complexity of these algorithm is kept under control. Moreover, given that the estimators of graph properties are unbiased, the approximation error is kept under control. Finally, we show the performance of the proposed framework (gSH) on various types of graphs, such as social graphs, among others.
1. INTRODUCTION
The paper motivates gSH as a generic, streaming framework for estimating diverse graph properties under computational constraints. It combines one-pass edge sampling with unbiased subgraph estimators and variance estimates.
- Big-graph analytics is important for understanding massive online networks, but brute-force computation can be too costly, slow, or inefficient.
- Streaming graphs motivate one-pass sampling because edges arrive over time, and one-pass processing is more efficient than arbitrary-order processing.
- gSH maintains a small state while processing every edge sequentially, with edge-selection probabilities able to depend on previously sampled adjacency structure.
- The framework uses Horvitz-Thompson weighting to obtain unbiased estimates for counts of arbitrary subgraphs and their variances or covariances.
- Applications include links, triangles, length-two paths, global clustering, and node counts, while the paper does not claim exhaustive query coverage.
- Because adjacency replaces flow-key equivalence from classic Sample and Hold, accuracy for some graph properties depends on edge ordering.
2. FRAMEWORK FOR GRAPH SAMPLING
The framework models edges as an ordered stream with history-dependent selection probabilities. Horvitz-Thompson-style estimators then provide unbiased estimates and variance-related guarantees for sampled edges and subsets.
- Edges arrive in an explicitly defined order, and adjacency may be directed or undirected depending on whether edges share an endpoint.
- Each edge is selected through a random process whose probability may depend on the sampling outcomes of preceding edges.
- The selection estimator bS_i = H_i/p_i is a Horvitz-Thompson estimator of unity for the presence of edge k_i.
- For any ordered subset, the product estimator preserves conditional and unconditional expectation through the sequence of edge selections.
- For disjoint subsets, multilinear polynomials of subset estimators have expectation equal to evaluation at all-one arguments.
- The framework supplies nonnegative unbiased covariance estimators, with variance estimation obtained as the special case of identical subsets.
3. SUBGRAPH SUM ESTIMATION
The paper extends the framework from sampled edges to general subgraph sums and derives unbiased estimators for graph counts, variance, clustering, and node selection. The clustering treatment is explicitly approximate without established large-graph asymptotics.
- Subgraph sums cover weighted counts of nodes, links, paths, triangles, and selected subgraphs satisfying criteria such as node labels.
- For a selected subgraph collection, summing f(J)bS(J) over sampled objects gives an unbiased estimator of the corresponding total.
- The framework also provides an unbiased estimator of the estimator variance, with non-overlapping subgraph pairs contributing zero under the stated convention.
- Specializations estimate link counts, triangle counts, and connected length-two path counts, together with unbiased variance estimates based on shared edges.
- The global clustering coefficient is defined as α = 3N_T/N_Λ, but its ratio estimator is treated through a delta-method approximation rather than as an unbiased estimator.
- Node selection is represented by a polynomial over incident-edge selection indicators, yielding an unbiased node estimator.
4. GRAPH SAMPLE AND HOLD
Graph Sample and Hold (gSH) processes an edge stream in one pass, sampling unmatched edges with p and matching edges with q while retaining sampling probabilities for estimation. The framework also includes a triangle-oriented variant, but sampled connected components may split depending on edge order.
- gSH(p, q): gSH(p, q) processes edges in a single pass, sampling matching edges with probability q and otherwise storing unmatched edges with probability p.Edges not sampled are discarded permanently, while selected edges retain their sampling probabilities for estimation.
- gSH(p, q): The algorithm retains selected edges and their sampling probabilities to support later graph-property estimation.The supplied algorithm description specifies appending an edge and its probability to the stored set with probability r.
- Sampling limitation: A single connected component can appear as multiple sampled components when omitted edges disconnect it, and edge order determines whether this occurs.This is a sampling limitation described for gSH's treatment of connected components.
- Triangle variant: gSHT modifies gSH to favor the selection of triangles by treating an arriving edge that would complete a triangle specially.The passage introduces gSHT as a simple illustrative modification of gSH for triangle selection.
- Illustration with gSH(p,1): For a path of length 3 under gSH(p, 1), the example examines different edge-arrival orders and reports unbiased weight and degree estimates.The example states that the random graph distribution depends on edge order, while the probability-weighted sums of weight estimators equal 1 and degree estimators recover true node degree.
5. EXPERIMENTS AND EVALUATION
The experiments evaluate gSH on social and web graphs, measuring unbiased estimates, confidence coverage, sampling fractions, computational cost, and comparison with prior triangle counting. Across the tested settings, estimates have low relative error, confidence intervals achieve approximately nominal coverage, and sampling fraction depends on q and graph density.
- Experimental setup: Experiments use undirected social and web graphs with 250K–7M edges, randomly permuting edges into streams.The graphs include Facebook networks from three US schools and web graphs; edge weights and self-loops are discarded.
- Experimental setup: The procedure samples with gSH(p,q), then estimates edge, triangle, length-two path, and global clustering counts and their variances.Each parameter setting is evaluated independently across 100 experiments.
- 5.1 Performance Analysis: Relative errors range from 0.03%–0.5% for edges, 0.03%–0.95% for triangles, 0.02%–0.6% for length-two paths, and 0.02%–0.76% for clustering.The highest observed error is for triangle counts and remains ≤1%; denser graphs show higher errors than sparse graphs.
- 5.2 Confidence Bounds: The 95% confidence intervals achieve coverage γ ≈95% across all graphs, and the reported bounds contain the actual statistics.As sample size increases, the bounds become more concentrated around the actual statistic, indicating decreasing variance.
- 5.3 Comparison to Previous Work: Across three web graphs, gSH has relative error orders of magnitude lower than Streaming-Triangles with smaller storage overhead in most graphs.The comparison uses results reported in the prior work.
- 5.2 Confidence Bounds: With q ≤0.01, sampled edges comprise 0.5%–2.5% of each graph, while q from 0.01 to 0.03 yields 2.75%–5%.For larger q, sampling fractions depend on graph density and reach 31% for socfb-CMU over q=0.03–0.1.
6. RELATED WORK
Prior graph-stream research developed sampling methods for specific tasks, but generic sampling schemes for estimating multiple graph properties remained less understood. The paper positions gSH within streaming graph analytics and network-sampling research.
- The paper’s streaming context builds on broader data-stream methods such as reservoir sampling, frequency counting, load shedding, and concept-drift mining.
- Graph-stream research has addressed triangle counting, common-neighborhood discovery, PageRank estimation, and degree-sequence characterization.
- Most existing sampling schemes target particular graph properties, leaving generic estimation of various properties under one scheme less understood.
- Earlier triangle-counting methods include single-pass and semi-streaming algorithms, but some are specialized, impractical, or produce large error.
- Related work also includes static graph algorithms, Horvitz-Thompson estimation for vertex sampling, and network sampling for representative subgraphs, community structure, and A/B testing.
7. CONCLUSION
The conclusion presents gSH as a single-pass, small-state framework with unbiased estimation and variance procedures for several graph quantities. Experiments report low relative error, balanced sampling distributions, and computational reductions across real-world graphs.
- gSH processes graph edges sequentially in one pass while maintaining a state typically smaller than 1% of the graph’s total edges.
- The framework produces unbiased estimators and variance estimates for four graph quantities, enabling confidence bounds from the variance estimators.
- For samples of ≤40K edges, experiments report relative error from 0.02% to 0.95% across different real-world graph types, with tighter bounds as sample size increases.
- The study examines how p and q affect the proportion of sampled edges.
- Compared with Streaming-Triangles, gSH achieves relative error orders of magnitude less with smaller overhead storage in most graphs.
- Parallel variance-estimator computation and graph counting reduce computation time within the gSH framework.