PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating and Sampling Graphs with Multidimensional Random Walks

Bruno Ribeiro, Don Towsley

arXiv:1002.1751v2cs.DScs.NI

TL;DR

Estimating large-graph characteristics is difficult because exhaustive queries are costly and random walks can be distorted by disconnected or loosely connected components. The paper proposes Frontier Sampling, an m-dimensional walk using dependent walkers, and reports lower errors than regular random walks while retaining regular-walk properties and comparable accuracy to random edge sampling for degree-distribution tails. Its estimators also include asymptotically unbiased procedures for selected graph characteristics.

  • Problem

    Graph sampling must estimate characteristics under resource constraints, while random walks can suffer large errors when disconnected or loosely connected components trap walkers.

  • Method

    Frontier Sampling uses m mutually dependent random walkers initialized from uniformly sampled vertices and represents their process as an m-dimensional random walk.

  • Results

    Frontier Sampling has smaller Mean Squared Errors than single and multiple independent random walkers, with comparable accuracy to random edge sampling in real-world simulations.

  • Takeaways & Limitations

    Frontier Sampling is more robust for estimating characteristics in disconnected or loosely connected graphs and is suitable for large-scale parallel, asynchronous experiments.

  • Takeaways & Limitations

    Independent random walkers are not suited to sample loosely connected graphs when starting vertices are selected uniformly at random.

Abstract

from arXiv · show

Estimating characteristics of large graphs via sampling is a vital part of the study of complex networks. Current sampling methods such as (independent) random vertex and random walks are useful but have drawbacks. Random vertex sampling may require too many resources (time, bandwidth, or money). Random walks, which normally require fewer resources per sample, can suffer from large estimation errors in the presence of disconnected or loosely connected graphs. In this work we propose a new $m$-dimensional random walk that uses $m$ dependent random walkers. We show that the proposed sampling method, which we call Frontier sampling, exhibits all of the nice sampling properties of a regular random walk. At the same time, our simulations over large real world graphs show that, in the presence of disconnected or loosely connected components, Frontier sampling exhibits lower estimation errors than regular random walks. We also show that Frontier sampling is more suitable than random vertex sampling to sample the tail of the degree distribution of the graph.

1. INTRODUCTION

Large-graph characterization relies on sampling because querying every vertex or edge is costly. Random vertex sampling can waste resources, while random walks are cheaper but may produce distorted estimates when walkers become trapped in disconnected or loosely connected regions.

  • Characterizing graph labels requires vertex or edge queries, each carrying costs in time, bandwidth, or money.
  • Random vertex sampling can be resource-intensive when user-id spaces are sparsely populated or queries are rate-limited.MySpace had fewer than 10% of user-ids occupied between its highest and lowest valid user-ids.
  • Random edge sampling may be impractical when edges lack unique, randomly queryable identifiers.
  • Random walks often provide a cheaper alternative by moving a walker between neighboring vertices and sampling both vertices and edges.The paper focuses on random walks that sample edges uniformly.
  • Random-walk accuracy depends on graph structure and the characteristic being estimated, with disconnected components able to trap the walker and distort estimates.

Contributions

The paper introduces Frontier Sampling, an m-dimensional walk with dependent walkers that preserves regular random-walk properties while improving sampling across difficult graph structures. Simulations report lower estimation errors than regular random-walk variants and comparable accuracy to random edge sampling for degree-distribution tails.

  • Frontier Sampling uses m dependent random walkers initialized from uniformly sampled vertices and preserves regular random-walk statistical properties.Vertices are visited with probability proportional to their degree.
  • Frontier Sampling’s joint steady-state distribution is closer to the uniform starting distribution than that of m independent random walkers.The paper states this holds for any m > 0 and may reduce random-walk transients.
  • Frontier Sampling produces smaller Mean Squared Errors than single and multiple independent random walkers across varied scenarios involving disconnected or loosely connected components.
  • Random edge sampling analytically estimates the degree-distribution tail better than random vertex sampling, while Frontier Sampling has comparable accuracy in real-world simulations.
  • The paper presents asymptotically unbiased random-walk estimators for assortative mixing and the global clustering coefficient.

Outline

The paper develops its sampling framework from notation and comparisons of vertex and edge sampling through random-walk estimation, Frontier Sampling, experiments, and discussion.

  • Section 2 introduces the notation used throughout the paper.
  • Section 3 contrasts random vertex sampling with random edge sampling.
  • Section 4 revisits single and multiple independent random-walk sampling and estimation.
  • Section 5 introduces Frontier Sampling with m dependent random walkers to mitigate errors from disconnected or loosely connected components.
  • Sections 6 and 7 present experiments and related work, while Section 8 discusses the findings and future work.

2. DEFINITIONS

The paper models the network as a labeled directed graph, constructs a symmetric counterpart for random walks, and defines graph volume, estimation errors, and a fixed-budget setting.

  • The original network is a labeled directed graph Gd = (V, Ed), where ordered vertex pairs represent directed connections.Vertices and edges may carry labels, such as degree or other network attributes.
  • Vertex in-degree counts distinct incoming edges, while out-degree counts distinct outgoing edges.
  • Random-walk queries retrieve incoming and outgoing edges, allowing construction of a symmetric directed graph on the fly.Vertices are assumed distinguishable.
  • The symmetric graph may be disconnected, and deg(v) denotes equal in-degree and out-degree; vol(S) sums degrees over vertices in S.
  • The paper evaluates estimates with normalized root mean square error and normalized CCDF error metrics.
  • Unless stated otherwise, vertex and edge queries have unit cost and sampling uses a fixed budget B.

3. VERTEX V.S. EDGE SAMPLING

Random edge sampling is more accurate than random vertex sampling for estimating the tail of degree distributions, although it is rarely practical; random walks can offer similar statistical properties on connected graphs.

  • Random edge sampling samples vertices with probability proportional to out-degree, whereas random vertex sampling samples them according to θi.
  • For out-degree i > d, random edge sampling has smaller NMSE than random vertex sampling when estimating the tail of the out-degree distribution.Here d is the average out-degree; random edge sampling is more accurate above the average degree, while vertex sampling is more accurate below it.
  • The same accuracy pattern extends to in-degree distributions and degree distributions of undirected networks.
  • Random edge sampling is rarely practical, while random walks exhibit similar statistical properties when the graph is connected.

4. RANDOM WALK SAMPLING

Random walks sample graph edges through successive neighbor transitions and, under stationarity, support asymptotically unbiased estimators of several graph characteristics. Multiple walkers and Frontier Sampling address trapping and disconnectedness while retaining useful random-walk properties.

  • 4. RANDOM WALK SAMPLING: A random walk samples edges by repeatedly moving from a vertex to a uniformly selected outgoing neighbor under a fixed sampling budget.The sampled edge sequence may contain repeated edges.
  • 4. RANDOM WALK SAMPLING: A stationary random walk samples edges uniformly, samples vertex v with probability deg(v)/vol(V), and obeys the strong law of large numbers.These properties are shared with random edge sampling.
  • 4. RANDOM WALK SAMPLING: Theorem 4.1 provides the convergence basis for estimators built from random-walk samples as the number of samples tends to infinity.The theorem is applied to graph characteristics by restricting attention to selected edge subsets when needed.
  • 4. RANDOM WALK SAMPLING: Random-walk estimators are presented for edge-label density, assortative mixing, vertex-label density, and global clustering coefficient.The construction replaces the full edge set in a characteristic's definition with edges sampled by a stationary random walk.
  • 4. RANDOM WALK SAMPLING: The edge-label density estimator converges almost surely to the true density and is unbiased whenever the number of selected samples is positive.
  • 4. RANDOM WALK SAMPLING: The assortative-mixing estimator is asymptotically unbiased when σin > 0 and σout > 0, and the clustering-coefficient estimator is asymptotically unbiased.
  • 4. RANDOM WALK SAMPLING: A single walker can become trapped in a local subgraph, increasing estimation bias or mean squared error, especially when the graph is disconnected or loosely connected.
  • 4. RANDOM WALK SAMPLING: Frontier Sampling uses m dependent walkers to seek uniform edge sampling while benefiting from walkers initialized at uniformly sampled vertices.Multiple independent walkers can be initialized at a cost of mc sampling units, but the paper motivates dependent walkers to address the single-walker limitation.

5. FRONTIER SAMPLING (FS)

Frontier Sampling (FS) is an m-dimensional random walk using m dependent walkers initialized at uniformly sampled vertices. It preserves key random-walk properties while improving behavior in loosely connected graphs and approaching uniform vertex-set sampling as m grows.

  • 5. FRONTIER SAMPLING (FS): FS maintains m dependent random walkers, initialized at uniformly sampled vertices, and centrally coordinates their sampled-edge sequence.At each step, it selects a listed vertex with probability proportional to its degree, follows a uniformly chosen outgoing edge, and replaces that vertex.
  • 5. FRONTIER SAMPLING (FS): FS is less likely than a single random walker to become stuck in loosely connected components, while its steady-state behavior is closer to uniform sampling than MultipleRW.The paper attributes this comparison to the joint steady-state distribution of FS and evaluates the effect through graph-component occupancy.
  • 5. FRONTIER SAMPLING (FS): FS is equivalent to a single random walker on the m-th Cartesian power G^m of the original graph.The state is an m-tuple of vertices, and one coordinate changes at each transition according to the frontier sampling rule.
  • 5. FRONTIER SAMPLING (FS): Under connected, non-bipartite directed-symmetric graphs, FS samples edges uniformly at random and satisfies the Strong Law of Large Numbers.These properties establish that FS retains important statistical guarantees of ordinary random walks.
  • 5.2 FS Steady State v.s. Uniform Distribution: lim_m→∞ P[Kfs(m) = k] = lim_m→∞ P[Kun(m) = k] for every k ≥ 0.Thus, with uniformly sampled starting vertices, the FS count in a vertex subset converges to the count from m uniformly sampled vertices.
  • 5.3 Distributed FS: FS can be implemented in fully distributed, parallel, asynchronous settings through an equivalent MultipleRW process with exponentially distributed vertex-sampling costs.The equivalence uses exponential sampling costs with parameter deg(v), together with Markov-chain uniformization and Poisson decomposition.

6. RESULTS

Experiments across real-world graphs compare Frontier Sampling (FS) with single and multiple random walks, random vertex sampling, and random edge sampling. FS is consistently more accurate, especially for disconnected or loosely connected graphs and for degree-distribution tails.

  • Experimental setup: FS estimates are consistently more accurate than SingleRW and MultipleRW across the evaluated real-world graphs.The experiments use Flickr, Livejournal, and YouTube graphs, with estimates compared under fixed sampling budgets.
  • Assortative mixing: A sevenfold smaller bias and one-order-of-magnitude smaller NMSE were observed for FS than for both random-walk baselines on Flickr assortative-mixing estimates.The Internet graph was the only studied graph showing little difference between FS and MultipleRW.
  • In-degree distribution: On complete Flickr, the CNMSE gap between FS and both SingleRW and MultipleRW increased relative to the largest connected component.The LCC contained 94% of Flickr’s vertices, and FS also outperformed both baselines there.
  • In-degree distribution: FS quickly converged near the correct θ10 value, while SingleRW varied across runs and MultipleRW often converged to an incorrect underestimated fraction.The comparison concerns four simulation runs estimating the in-degree distribution.
  • Initialization: Starting vertices sampled uniformly at random produced large random-walk errors, whereas initializing SingleRW and MultipleRW in steady state reduced those errors, especially for MultipleRW.SingleRW improved slightly, while the benefit of steady-state initialization was greatest for MultipleRW.
  • Random independent sampling: With a 10% valid-user-id hit ratio, FS outperformed random edge sampling and random vertex sampling except at the three smallest in-degrees.This result indicates greater robustness to low hit ratios under the stated Livejournal experiment.

7. RELATED WORK

Prior work applies MCMC and random-walk methods to graph and network sampling, but does not address using multiple random walks to estimate characteristics of disconnected or loosely connected graphs. Existing alternatives often rely on structured or fully known graphs, while this work assumes graphs can be crawled and vertex degrees queried.

  • MCMC methods have been used to estimate populations, peer-to-peer content density, and uniformly sample Web pages.
  • The reviewed literature mainly studies walks that seek uniform vertex samples, including Metropolized Random Walks and Metropolis-RW.
  • Prior work does not use multiple random walks to estimate characteristics of disconnected or loosely connected graphs.
  • Independent walkers used as convergence tests are not suited to sample loosely connected graphs when starting vertices are chosen uniformly at random.
  • Many MCMC solutions assume highly structured or completely known graphs, making them inapplicable to the paper’s setting.
  • The paper assumes graphs can be crawled and vertex degrees queried, which admits a random walk with an unbiased estimator.

8. DISCUSSION AND FUTURE WORK

The paper presents Frontier sampling, a multidimensional random-walk method designed to reduce estimation errors caused by trapping in graph subgraphs. It reports robustness across graph characteristics and suitability for degree-distribution tails, with a distributed implementation requiring no coordination or communication costs.

  • Frontier sampling uses m mutually dependent random walkers initialized from uniformly sampled vertices.
  • Frontier sampling mitigates estimation errors caused by subgraphs that trap a random walker.
  • Simulations show Frontier sampling is more robust than single and multiple independent walkers for estimating in-degree distributions and social-group membership fractions.
  • Analytical and simulation evidence indicates random walks, particularly Frontier sampling, better estimate degree-distribution tails than random vertex sampling.
  • Frontier sampling can be implemented fully distributed without coordination or communication costs.
  • The ideas behind Frontier sampling may inform estimation of dynamic networks and new MCMC-based approximation algorithms.

A. PROOF OF THE FRONTIER SAMPLING THEOREM

The proof models Frontier sampling as a single random walk on the m-th Cartesian power of the graph. Under the theorem’s connectivity and non-bipartiteness conditions, its edge samples are uniform, stationary, and satisfy the Strong Law of Large Numbers.

  • Under connected and non-bipartite directed symmetric G, Frontier sampling edges uniformly and its sampled-edge sequence satisfies the Strong Law of Large Numbers.
  • Frontier sampling transitions between m-vertex states by selecting an edge from the current edge frontier.
  • The state space is V^m, and two states are adjacent when one coordinate follows an edge while all others remain unchanged.
  • The induced walk over G^m is shown to be aperiodic and recurrent non-null, hence ergodic with a unique stable steady-state distribution.
  • Each edge of G is copied m|V|^(m−1) times into G^m, preserving uniform edge sampling in the induced walk.
  • The sampled vertices also form a stationary sequence and follow the Strong Law of Large Numbers.

B. CONVERGENCE TO UNIFORM EDGE SAMPLING

The convergence experiment compares Frontier sampling with single and multiple independent random walkers on three graph datasets. Frontier sampling’s transient edge-sampling probabilities are consistently closer to stationarity and converge faster.

  • The experiment evaluates K ∈ {1, 10} independent walkers and Frontier sampling with dimension m = 10 on Internet RLT, YouTube, and Hep-th.
  • Convergence is measured by the largest relative difference between stationary edge probability 1/|E| and the probability p(B) after sampling budget B.
  • 5 to 42 times larger differences separate independent walkers from Frontier sampling in transient versus stationary edge-sampling probabilities.
  • Frontier sampling converges faster to the stationary edge-sampling probability, with closer probabilities in all evaluated graphs.
Loading 1002.1751v2…