PaperlayerView exact revision on arXiv

Source-linked AI summary

Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks

M. Kurant, M. Gjoka, C. T. Butts, A. Markopoulou

arXiv:1101.5463v2cs.SIcs.NIphysics.soc-phstat.ME

TL;DR

Large online graphs are difficult to measure completely, while independence sampling requires a sampling frame that is often unavailable. The paper uses a stratified weighted random walk to balance measurement-focused sampling with convergence, and reports that it needs 13–15 times fewer samples than a simple random walk for the same estimation accuracy in a Facebook college-size study.

  • Problem

    Large online networks are too big to measure in full, and independence sampling requires a sampling frame that is typically unavailable.

    Source: §1 · p. 1

  • Method

    S-WRW sets edge weights for a random walk to balance WIS-optimal sampling probabilities with fast convergence, using node properties relevant to the measurement goal.

    Source: §1 · pp. 1–2

  • Results

    13–15 times fewer samples than a simple random walk achieved the same estimation accuracy in the Facebook college-size case study.

    Source: §6.3 · p. 11

  • Takeaways & Limitations

    S-WRW is presented as an efficient way to sample large, static, undirected graphs via crawling using minimal information.

    Source: §8 · p. 12

    S-WRW remains an intuitive heuristic, and finding an optimal solution to the identified problems is left for future work.

    Source: §8 · p. 12

Abstract

from arXiv · show

Our objective is to sample the node set of a large unknown graph via crawling, to accurately estimate a given metric of interest. We design a random walk on an appropriately defined weighted graph that achieves high efficiency by preferentially crawling those nodes and edges that convey greater information regarding the target metric. Our approach begins by employing the theory of stratification to find optimal node weights, for a given estimation problem, under an independence sampler. While optimal under independence sampling, these weights may be impractical under graph crawling due to constraints arising from the structure of the graph. Therefore, the edge weights for our random walk should be chosen so as to lead to an equilibrium distribution that strikes a balance between approximating the optimal weights under an independence sampler and achieving fast convergence. We propose a heuristic approach (stratified weighted random walk, or S-WRW) that achieves this goal, while using only limited information about the graph structure and the node properties. We evaluate our technique in simulation, and experimentally, by collecting a sample of Facebook college users. We show that S-WRW requires 13-15 times fewer samples than the simple re-weighted random walk (RW) to achieve the same estimation accuracy for a range of metrics.

1. INTRODUCTION

The introduction frames graph crawling as a way to sample large networks when a representative sample is needed but a complete sampling frame is unavailable. It motivates S-WRW as a heuristic that balances measurement-focused sampling with walk convergence, and reports a Facebook college-size estimation result.

1. INTRODUCTION

  • Online networks are too large to measure in full, and access to their information is often limited, making small representative samples desirable.Source: §1 · p. 1
  • A uniform sample can waste effort on irrelevant groups and miss small target groups, as illustrated by comparing China and Vatican residents.The example motivates sampling categories at different rates for a fixed budget.Source: §1 · p. 1
  • Stratified sampling allocates independent draws across non-overlapping categories to reduce uncertainty, with probabilities chosen for the measurement goal.WIS represents this allocation with appropriately chosen sampling probabilities.Source: §1 · p. 1
  • A weighted random walk can approximate WIS-optimal sampling probabilities, but those weights may cause slow mixing or no convergence, motivating a balance with fast convergence.In the illustrative example, the WIS-constrained weighted graph is disconnected.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • S-WRW combines stratified sampling with graph exploration, using node properties relevant to the measurement goal as well as graph structure.The proposed practical heuristic sets edge weights while operating with limited information.Source: §1 · p. 2
  • S-WRW required 13–15 times fewer samples than a simple random walk for the same estimation accuracy when estimating Facebook college sizes.The comparison is reported as a case study.Source: §1 · p. 2

2. SAMPLING TECHNIQUES

The section reviews independent and crawling-based ways to sample graph nodes, then explains how reweighting corrects their known sampling bias. Weighted random walks provide the basic building block for choosing crawl transitions.

2.1 Notation

  • Graph samples may contain repeated nodes, and the section sets notation for graph structure, sampling, and node values.The sample is drawn with replacement.Source: §2.1 · p. 2

2.2 Independence Sampling

  • UIS and WIS draw nodes independently from the full node set, with WIS probabilities proportional to node weights; online networks often lack the sampling frame these methods require.The paper presents them as baselines for comparison with random walks.Source: §2.2 · pp. 2–3

2.3 Sampling via Crawling

  • Crawling selects new nodes through observed links; RW, MHRW, and WRW provide alternatives, with WRW choosing transitions in proportion to edge weights.The paper focuses on RW comparisons rather than MHRW because prior work found reweighted RW outperformed MHRW for most applications.Source: §2.3 · p. 3

2.4 Correcting the bias

  • Hansen-Hurwitz reweighting corrects the known bias in RW, WRW, and WIS samples, using each node’s stationary sampling probability.In practice, sampling probabilities may be known only up to a constant through node weights; the paper presents results after reweighting where needed.Source: §2.4 · p. 3

3. STRATIFIED SAMPLING

Stratified sampling partitions nodes into categories and allocates a fixed sample budget among them. The allocation can be proportional or tailored to the estimation objective, with optimal allocations differing across objectives and settings.

3. STRATIFIED SAMPLING

  • Stratified sampling partitions nodes into non-overlapping categories and allocates a fixed sample budget among them; proportional allocation assigns samples in proportion to category size.An optimal allocation instead minimizes estimator variance for the specific measurement problem.Source: §3 · p. 3

3.1.1 Estimating the mean across the entire V

  • For estimating the overall population mean, the section compares proportional allocation with Neyman allocation, which minimizes the estimator variance.The gain measures how much longer proportional allocation must be to match optimal allocation’s variance.Source: §3.1.1 · p. 4

3.1.2 Highest precision for all categories

  • When the goal is equal precision across categories or average precision of pairwise category comparisons, the section gives distinct variance objectives and allocations.The supplied passages identify the objectives but do not provide complete allocation formulas.Source: §3.1.2 · p. 4, §3.1.3 · p. 4

3.1.4 Relative sizes of node categories

  • If category sizes are unknown and must also be estimated, the section treats the optimal allocation and WIS gain separately for that setting.The supplied passage points to an Appendix C result for two categories.Source: §3.1.4 · p. 4

3.1.5 Irrelevant category C⊖(aggregated)

  • When some categories are irrelevant to the measurement, they can be aggregated as one irrelevant category; the total gain combines avoiding those nodes with optimal allocation among relevant categories.The section also considers allocation objectives for the remaining categories.Source: §3.1.5 · p. 4

3.1.6 Practical Guideline

  • For comparisons among relevant categories, the practical guideline is to take equal numbers of samples from each category.The section frames this guidance around comparing category properties rather than estimating a property across the entire population.Source: §3.1.6 · p. 4

4. EDGE WEIGHT SETTING UNDER WRW

The section develops S-WRW, a heuristic for setting edge weights when the general WRW error-minimization problem is difficult under limited graph knowledge. It starts from WIS-optimal category weights and modifies them to address crawling constraints.

4. EDGE WEIGHT SETTING UNDER WRW

  • S-WRW heuristically sets edge weights for WRW by starting from WIS-optimal weights and adjusting for practical graph-exploration issues.The general objective is to minimize measurement error for a given measurement goal and sample budget.Source: §4 · p. 5

4.1.1 Category-level granularity

  • The method works at category-level granularity, targeting expected sample counts per category rather than controlling individual node probabilities.Category information is used because it matches the estimation properties of interest and is relatively easy to obtain or infer.Source: §4.1.1 · p. 5, §4.1.2 · p. 5

4.1.3 Main guideline

  • The main guideline sets category edge weights in proportion to WIS-optimal category weights divided by category volume; a pilot RW estimates volumes and the estimation objective determines WIS weights.The method modifies these terms in later steps to address graph-structure constraints.Source: §4.1.3 · p. 5, Step 5: Edge Conflict Resolution · p. 5, §4.2.1 · p. 5

4.2.3 Step 3: Irrelevant Categories

  • WIS-optimal weights can leave relevant categories disconnected under WRW when irrelevant nodes receive zero weight, so the method recommends occasional visits to irrelevant nodes.The parameter controls the desired fraction of visits to the aggregated irrelevant category.Source: §4.2.3 · p. 6

4.2.4 Step 4: Tiny and Unknown Categories

  • Very large weights for tiny categories can make them act as sinks in finite WRW runs, so S-WRW limits their edge weights and assigns a minimum estimated volume to undiscovered categories.For the cited two-node example, a lower weight was optimal for a walk of length 50 than the WIS-optimal weight.Source: §4.2.4 · p. 6

4.2.5 Step 5: Edge Conflict Resolution

  • Conflicting desired weights at the ends of inter-category edges are resolved by a hybrid assignment that favors inter-category edges to improve mixing without over-weighting irrelevant nodes.The hybrid assignment was the one the authors found to work best in practice.Source: §4.2.5 · p. 6

4.3 Discussion

S-WRW uses neighbor-category information and a pilot random walk to set weights, then tunes parameters to balance category targeting against connectivity and mixing. The authors describe the approach as conservative relative to WIS and state that reweighted estimates are unbiased once convergence is attained.

4.3.1 Information needed about the neighbors

  • The pilot and main walks assume that visiting a node reveals its neighbors’ categories, but not their degrees.The paper notes that this information is often available in online networks; its Facebook example uses neighbors’ college memberships.Source: §4.3.1 · pp. 6–7

4.3.2 Cost of pilot RW

  • A pilot RW can be only a small fraction of the later WRW because its volume estimator is efficient and S-WRW is robust to estimation errors.The Facebook measurements used a pilot RW of 6.5% of the later WRW.Source: §4.3.2 · p. 7

4.3.3 Setting the parameters

  • The irrelevant-node visit parameter should reflect connectivity among relevant categories, while γ sets the size resolution and may under-sample categories smaller than the chosen scale.The authors recommend positive irrelevant-node visits and finite γ; very large γ may cause the black-hole problem.Source: §4.3.3 · p. 7

4.3.4 Conservative approach

  • By shaping WIS category weights toward RW, S-WRW allocates category weight between those two extremes and is therefore conservative relative to WIS.The comparison assumes reasonable parameter settings and conflict resolution.Source: §4.3.4 · p. 7

4.3.5 S-WRW is unbiased

  • After correction by actual sampling weights, S-WRW estimation is unbiased if convergence is attained, while suboptimal weights can increase mixing time or estimator variance.The simulations and Facebook experiments report robustness to suboptimal weight choices.Source: §4.3.5 · p. 7

5. SIMULATION RESULTS

In simulation, weighted random walks reduce sampling costs by avoiding irrelevant categories and allocating samples among relevant ones, but tight communities can create a black-hole effect. The results show that conservative parameter choices retain gains despite imperfect parameter or volume estimates.

5.1 Setup

  • The simulation uses 101K nodes in two categories, Ctiny (1K) and Cbig (100K), under random and clustered category assignments.It estimates relative category sizes using NRMSE; Figure 4 compares RW and S-WRW across the two scenarios.Source: §5.1 · p. 7, §5.2 · p. 7, Figure 4 · p. 8

5.3.1 Estimating volumes is usually cheap

  • The neighbor-based volume estimator is more efficient than the naive estimator, with its advantage growing with graph density and degree-distribution skewness.In clustered graphs, neighbors mostly share a category, reducing the neighbor-based estimator to the naive one; even severalfold volume errors are unlikely to affect results significantly.Source: §5.3.1 · p. 8

5.3.2 Visiting the tiny category

  • WRW with w > 1 is more likely than RW to visit Ctiny, while the probability of visiting it at least once also increases with sample length.Figure 4(e,l) presents the empirical visit probability.Source: §5.3.2 · p. 8

5.3.3 Optimal w and γ

  • For n = 500, error is U-shaped in w; WRW is optimized near w ≃20 rather than WIS’s wopt ≃100.The black-hole effect is stronger in clustered communities and diminishes with longer samples, vanishing as n →∞.Source: §5.3.3 · p. 8

5.3.4 Gain α

  • Under WIS, α ≃25: 500 samples achieve NRMSE ≃0.1, matching UIS with about 25 times more samples.For the clustered scenario, WRW still may significantly reduce sampling cost, particularly for longer samples.Source: §5.3.4 · p. 9
  • 500 hops with WRW at w ≃20 match the NRMSE ≃0.3 of 2,000-hop RW, a sampling-cost reduction of α ≃4.Under the clustered scenario both methods perform worse, though WRW may reduce sampling cost, especially for longer samples.Source: §5.3.4 · p. 9

5.3.5 Robustness to γ and volume estimation

  • With γ fixed at 5, S-WRW still reduces sampling cost about three-fold, although performance somewhat drops versus optimized γ.In the random scenario, Ctiny’s volume would need to be overestimated by more than 20 times to affect edge weights and results.Source: §5.3.5 · p. 9

5.4 Summary

  • 75%: WRW can reduce sampling cost by 75% even when there are no irrelevant nodes, through better allocation among relevant categories.Avoiding irrelevant nodes is a separate source of gain; tight communities make the allocation benefit harder to achieve.Source: §5.4 · p. 9

6. IMPLEMENTATION IN FACEBOOK

The Facebook study tests whether S-WRW can improve college sampling and size estimation over RW. Across the measured settings, S-WRW collects more college samples and estimates college sizes more accurately.

6.1 Measurement Setup

  • The study crawled Facebook’s static, undirected graph, using a 65K-sample pilot to choose parameters before collecting 1 million unique users per crawl type.The main phase compared three S-WRW edge-weight conflict rules—hybrid, geometric, and arithmetic—with an RW baseline.Source: §6 · p. 9, §6.1 · p. 9

6.2.1 Avoiding irrelevant categories

  • RW samples came from colleges only 9% of the time, while S-WRW’s college-sample shares were 86% for hybrid, 79% for geometric, and 58% for arithmetic.College users average about three times as many friends as Facebook users overall, helping explain why RW’s 9% share exceeds their 3.5% population share.Source: §6.2.1 · p. 10

6.2.2 Stratification

  • S-WRW collected roughly 100 samples per college, while RW’s sample counts tracked college size, producing up to 100-fold differences for smaller colleges.College sizes span more than two orders of magnitude; the figure compares the 5,331 colleges discovered by RW.Source: §6.2.2 · p. 10, Figure 5 · p. 10

6.2.3 College size estimation

  • For MIT, Caltech, and Eindhoven University of Technology, S-WRW produced more reliable size estimates than RW, with typically 5–50 times more samples per college.RW estimates were unreliable in most cases except MIT in the two longest walks; the comparison used 4K-, 20K-, and 40K-sample walks.Source: §6.2.3 · p. 10
  • 13–15 times fewer samples let S-WRW match RW’s college-size estimation error across all 5,331 RW-discovered colleges.The comparison uses average NRMSE across colleges as a function of walk length.Source: §6.2.3 · p. 10, Figure 5 · p. 10

6.2.4 The effect of the choice of γ

  • Both γ settings performed orders of magnitude better than same-length RW, while γ=100 collected fewer samples in the smallest colleges than γ=1000.The curves diverge for colleges about 100 times smaller than the biggest college, matching the γ=100 resolution boundary.Source: §6.2.4 · pp. 10–11

6.3 Summary

  • The summary attributes an approximately 8-fold gain to a higher college-sample fraction and an approximately 1.5-fold gain to oversampling smaller colleges; the three S-WRW implementations differed only slightly.Including the initial pilot reduces the reported overall gain from 13–15 times to 12–14 times.Source: §6.3 · p. 11

7. RELATED WORK

Prior graph-crawling work includes BFS and random-walk methods, while other weighted walks prioritize mixing time or operate on known graphs. This paper distinguishes its approach by weighting walks for measurement of unknown graphs.

Graph Sampling by Exploration

  • Incomplete BFS can bias samples toward high-degree nodes in ways that cannot generally be corrected, while Metropolis-Hastings RW removes walk bias and RW has a known, correctable bias.RW was reported to outperform MHRW empirically in measurement accuracy and is described as state of the art.Source: §7 · p. 11

Fast Mixing Markov Chains

  • Other fast-mixing techniques treat all nodes as equally important, making them orthogonal to this paper’s measurement-focused weighting.These include multiple dependent walks for disconnected or loosely connected graphs and walks with jumps.Source: §7 · p. 11
  • A fastest-mixing WRW method requires graph knowledge and a target distribution, which can inherit poor convergence and “black holes” from WIS-optimal weights.The paper says this method can also assign zero self-loop weights, potentially disconnecting the graph.Source: §7 · p. 11

Weighted Random Walks for Sampling

  • Prior OSN WRWs optimize mixing time or operate on known graphs, whereas this work designs weights to estimate features of unknown graphs.The authors describe the closest OSN methods as complementary and distinguish their goal from WRW applications.Source: §7 · p. 11

Graph Sampling by Exploration

  • Focused crawling follows pages of specified interest, but priority-queue BFS retains regular BFS’s dependence on its starting point and inability to unbias samples.The cited approach uses page relevancy to prioritize the queue.Source: §7 · pp. 11–12

8. CONCLUSION

The paper introduces S-WRW as a practical way to sample large, static, undirected graphs through crawling with minimal information. Its Facebook evaluation reports that it outperforms simple re-weighted random walk.

8. CONCLUSION

  • S-WRW is an efficient crawling method for large, static, undirected graphs that uses minimal information.Its weighted random-walk weights are determined by the estimation problem.Source: §8 · p. 12
  • On Facebook, S-WRW greatly outperformed the state-of-the-art simple re-weighted random walk.The authors identify optimal solutions, combinations with orthogonal techniques, dynamic graphs, and non-stratified data as future work.Source: §8 · p. 12

Appendix A: Achieving Arbitrary Node Weights

The appendix examines when edge weights can realize a desired distribution of node weights. Self-loops make arbitrary positive node weights achievable in an undirected graph.

Appendix A: Achieving Arbitrary Node Weights

  • Without self-loops, arbitrary node weights may be impossible; in a two-node path, the two nodes cannot have different weights.The appendix contrasts this with the construction for graphs containing a self-loop at every node.Source: Appendix A · p. 13
  • With a self-loop at every node, suitable positive edge weights can achieve any distribution of positive node weights.The construction sets non-self-loop weights using the minimum target weight, then chooses self-loop weights to meet each target.Source: Appendix A · p. 13

Appendix B: Estimating Category Volumes

The section derives estimators of category volume ratios from independent samples and from sampled-node neighborhoods. Star sampling uses neighbors of sampled nodes and performed better in the reported simulations and implementations.

Appendix B: Estimating Category Volumes

  • For uniform independent samples, the volume-ratio estimator is a straightforward application of the classic ratio estimator.For weighted independent samples, the estimator corrects for linear bias toward higher-weight nodes.Source: Appendix B · p. 13
  • Star sampling applies the volume-ratio estimation formula to the neighbors of sampled nodes, which are asymptotically sampled with probabilities proportional to degree.Under weighted independent sampling, the linear bias toward higher-weight nodes is corrected.Source: Appendix B · p. 13
  • Using all neighbors of each sampled node in Eq.(33–35) performed much better than using one node per sample in Eq.(30–32) across simulations and implementations.The comparison is attributed to the formulas’ use of all deg(v) neighbors rather than one node per sample.Source: Appendix B · p. 13
  • Assuming the average degree in C matches that in V makes vol(C)/vol(V) equal |C|/N, reducing Eq.(32) to the core scale-up formula.The section also notes that Eq.(33) generalizes the scale-up method.Source: Appendix B · p. 13

Appendix C: Relative sizes of node categories

This section compares uniform and weighted independent sampling for estimating the relative sizes of two node categories. Under weighted sampling, equal weighted mass across the categories minimizes the variance of estimates for both category shares.

Appendix C: Relative sizes of node categories

  • UIS estimates f1 from the number of C1 selections in n uniform draws, where X1 follows a binomial distribution with parameters f1 and n.Equal weights w1 = w2 recover the UIS case, though that need not be the variance-minimizing WIS choice.Source: Appendix C · p. 14
  • WIS selects nodes with probabilities determined by their weights, and its category-share estimator uses the known category weights w1 and w2.The section derives the estimator using the Hansen–Hurwitz estimator separately for numerator and denominator.Source: Appendix C · p. 14
  • For the two-category setting, the section approximates the WIS estimate’s variance using second-order Taylor expansions, or the Delta method.The derivation uses the stated expectation and variance of X1, which follows a binomial distribution.Source: Appendix C · p. 14
  • Equal total weighted mass for C1 and C2 minimizes the variance of the WIS estimators of both category shares and implies equal expected sample allocation.The condition is w1 f1 = f2 w2.Source: Appendix C · p. 14
  • The gain α of WIS over UIS is always at least 1 and grows quickly as the difference between f1 and f2 increases.The section defines this gain by comparing the sample lengths needed to achieve the same variance.Source: Appendix C · p. 14

Appendix D: Optimal WRW weights in Fig. 3(a)

In the Fig. 3(a) setup, the walk alternates between visits to the white category and runs in a selected red or green category. The variance of the red-category share estimator is minimized at p = 1.

Appendix D: Optimal WRW weights in Fig. 3(a)

  • Each white-category visit is followed by a uniformly selected red or green category visited for a geometrically distributed number of rounds with parameter p = w2/(w1+w2).The process then returns to the white category and repeats; the red-visit estimator is defined relative to white-category visits.Source: Appendix D · p. 14
  • At p = 1, corresponding to w1 = 0 and w2 > 0, the variance of the red-category share estimator is minimized, with nwh = n/2.The variance is expressed in terms of white-category visits nwh, which decreases as p decreases.Source: Appendix D · p. 14
Loading 1101.5463v2…