Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling

Chul-Ho Lee; Xin Xu; Do Young Eun

Source-linked AI summary

Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling

Chul-Ho Lee, Xin Xu, Do Young Eun

arXiv:1204.4140v1Apr 18, 2012stat.MEcs.DScs.NIcs.SIphysics.data-anphysics.soc-ph

TL;DR

Large networks make direct independent uniform sampling infeasible, while SRW-rw and MH can diffuse slowly and backtrack, hurting estimation efficiency. The paper proposes NBRW-rw and MHDA, proving that they retain unbiased sampling while achieving higher efficiency than their respective baselines. Simulations support these theoretical findings and show MHDA’s broader applicability to non-uniform sampling.

Problem
Large, unknown networks make direct independent uniform sampling infeasible, while SRW-rw and MH can suffer slow diffusion and backtracking that reduce estimation efficiency.
Method
The paper develops NBRW-rw and MHDA by avoiding backtracking while preserving the relevant stationary distributions and unbiased estimators.
Results
NBRW-rw and MHDA theoretically guarantee unbiased graph sampling with higher efficiency than SRW-rw and MH, respectively; NBRW-rw yields about 35% cost savings and MHDA about 14% on AS-733.
Takeaways & Limitations
MHDA is applicable to arbitrary non-uniform node sampling, while the proposed methods improve sampling efficiency without sacrificing unbiasedness.
Takeaways & Limitations
The non-backtracking extension must avoid backtracking only as far as possible to preserve an arbitrarily specified stationary distribution, making MHDA more involved than NBRW.

Abstract

from arXiv · show

Graph sampling via crawling has been actively considered as a generic and important tool for collecting uniform node samples so as to consistently estimate and uncover various characteristics of complex networks. The so-called simple random walk with re-weighting (SRW-rw) and Metropolis-Hastings (MH) algorithm have been popular in the literature for such unbiased graph sampling. However, an unavoidable downside of their core random walks -- slow diffusion over the space, can cause poor estimation accuracy. In this paper, we propose non-backtracking random walk with re-weighting (NBRW-rw) and MH algorithm with delayed acceptance (MHDA) which are theoretically guaranteed to achieve, at almost no additional cost, not only unbiased graph sampling but also higher efficiency (smaller asymptotic variance of the resulting unbiased estimators) than the SRW-rw and the MH algorithm, respectively. In particular, a remarkable feature of the MHDA is its applicability for any non-uniform node sampling like the MH algorithm, but ensuring better sampling efficiency than the MH algorithm. We also provide simulation results to confirm our theoretical findings.

1 Introduction

Large complex networks are difficult to measure directly, so crawling-based random-walk samplers provide practical unbiased estimation. This paper targets the slow diffusion and backtracking of SRW-rw and MH by developing non-backtracking alternatives with theoretical efficiency guarantees.

Direct independent uniform sampling is infeasible for large, unknown networks, motivating graph crawling for estimating nodal and topological properties.
SRW-rw and MH are popular because they are implementable and provide unbiased graph sampling under network constraints.
Backtracking and slow diffusion in the core random walks produce duplicate samples and can reduce estimation accuracy.
NBRW-rw and MHDA preserve unbiased sampling while achieving smaller asymptotic variance than SRW-rw and MH, respectively.MHDA also applies to arbitrary stationary distributions under graph-topological constraints.
Prior approaches improved SRW-rw or Markov-chain speed but generally lacked direct implications for unbiased graph sampling or did not accommodate graph-topological constraints.

2 Background on Markov Chain Samplers

Markov-chain samplers estimate expectations under a stationary distribution, with re-weighting enabling uniform graph estimation when the chain is non-uniform. The paper uses asymptotic variance, rather than mixing time alone, to assess estimator efficiency.

2.1 Unbiased Graph Sampling: Unbiased graph sampling estimates nodal or topological properties from uniform node samples obtained by crawling a target graph.
2.1 Unbiased Graph Sampling: Finite irreducible Markov chains with stationary distribution π support asymptotically unbiased estimates of Eπ(f), and re-weighting can target Eu(f).
Multiple irreducible chains can share a stationary distribution, creating a need to compare their sampling efficiency.
2.2 Central Limit Theorem and Asymptotic Variance: After burn-in, graph sampling primarily requires efficient estimation from subsequent samples, making estimator efficiency more relevant than convergence speed alone.
2.2 Central Limit Theorem and Asymptotic Variance: Temporal correlation affects asymptotic variance, and reducing that correlation can improve estimator accuracy.
2.2 Central Limit Theorem and Asymptotic Variance: The paper therefore treats asymptotic variance as its primary metric and seeks samplers with smaller variance than current counterparts.

3 Random Walk-based Graph Sampling

SRW-rw and MH obtain unbiased graph estimates through re-weighting or a uniform stationary distribution, but their consecutive samples can backtrack. These methods establish the baselines that the paper’s proposed samplers seek to improve.

SRW-rw: SRW-rw combines a simple random walk with re-weighting to correct the degree-dependent stationary distribution.
SRW-rw: Using weights proportional to 1/d(i), SRW-rw provides a practical asymptotically unbiased estimator for uniform graph expectations.
Metropolis-Hastings: MH constructs a reversible chain with a desired stationary distribution by proposing neighbor transitions and accepting or rejecting them.
Metropolis-Hastings: With SRW proposal probabilities, MHRW has uniform stationary distribution, so its sample-based estimator is unbiased for uniform expectations.
Sampling inefficiency: SRW and MHRW can backtrack to recently visited nodes, especially in low-degree regions, temporarily trapping walks and increasing duplicate samples.

4 Avoid Backtracking To Previously Visited Node

The paper constructs non-reversible chains that preserve the original stationary distribution while avoiding backtracking, then applies this framework to NBRW-rw and MHDA. Both methods retain unbiased sampling and achieve no larger asymptotic variance than their conventional counterparts, with MHDA extending to arbitrary target distributions.

4.1 From Reversible To Non-reversible Chains: The proposed construction transforms a reversible chain into a non-reversible chain that preserves its stationary distribution while reducing backtracking.The new walk uses the previous node as memory, so it is Markovian on an augmented state space rather than on nodes alone.
4.1 From Reversible To Non-reversible Chains: The augmented-state construction yields node-level steady-state probabilities equal to the original stationary distribution.The construction assigns augmented states a stationary distribution based on π(i)P(i,j), then recovers π(j) after projecting back to nodes.
4.2 Non-backtracking Random Walk with Re-weighting: For NBRW-rw, the unbiased estimator has asymptotic variance no larger than the corresponding SRW-rw estimator.The result follows by applying the non-backtracking variance comparison after the same degree-based re-weighting used by SRW-rw.
4.2 Non-backtracking Random Walk with Re-weighting: NBRW-rw replaces SRW with a walk that avoids returning to the previous node whenever possible while retaining SRW’s stationary distribution and re-weighting scheme.This removes backtracking without changing the stationary distribution used for unbiased estimation.
4.3 Metropolis-Hastings Algorithm with Delayed Acceptance: MHDA preserves the desired stationary distribution and improves MH by redirecting some backtracking probability toward alternative transitions.It keeps the same node sojourn times as MH while reducing bias toward the previous node; the resulting transition can be larger by P(j, i)Q′(eij, ejk)A′(eij, ejk).
4.3 Metropolis-Hastings Algorithm with Delayed Acceptance: MHDA applies to any desired stationary distribution, and its graph-sampling specialization produces unbiased samples with higher efficiency than the corresponding MHRW.The only additional overhead identified is remembering the node from which the walk came.

5 Simulation Results

Simulations on four real-world graphs compare NBRW-rw with SRW-rw and MHRW-DA with MHRW for degree-distribution estimation. Across graph structures, the proposed methods generally reduce the samples needed for comparable accuracy, including non-stationary starts.

Experimental setup: The experiments evaluate degree-distribution pdf and ccdf estimation using NRMSE on AS-733, HEP-TH, Road-PA, and Web-Google graph datasets.The simulations use functions for P{DG = d} and P{DG > d}, with stationary starts unless otherwise specified.
AS-733: 35% and 14% average cost savings are reported for NBRW-rw and MHRW-DA, respectively, on AS-733 versus their corresponding baselines.The comparison concerns the number of samples required to achieve the same estimation error for P{DG = d}.
Non-stationary starts: NBRW-rw and MHRW-DA remain more accurate than their respective baselines when walks do not start in the stationary regime.This pattern is reported for AS-733, HEP-TH, and Road-PA, although one MHRW-DA ratio outlier appears in an asymptotic comparison.
HEP-TH: 22% and 12% average sample savings are reported for NBRW-rw and MHRW-DA, respectively, on HEP-TH versus SRW-rw and MHRW.The methods also surpass their respective baselines for estimating P{DG = d}, while NRMSE curves support the theoretical findings for P{DG > d}.
Road-PA: About 60% and 54% average cost savings are reported for NBRW-rw and MHRW-DA, respectively, on Road-PA.The baselines require more than twice as many samples to attain the same accuracy for P{DG = d}; the improvement remains under non-stationary starts.

6 Concluding Remarks

The paper reports that NBRW-rw and MHDA preserve unbiased graph sampling while improving sampling efficiency over SRW-rw and MH, respectively. The concluding evidence includes simulation figures for Web-Google estimation tasks.

NBRW-rw and MHDA guarantee unbiased graph sampling and higher sampling efficiency than SRW-rw and MH, respectively.The efficiency comparison is stated as an outcome demonstrated in theory and simulation.
MHDA is applicable beyond unbiased graph sampling to non-uniform node sampling and is reported to improve efficiency over MH.The paper highlights intentionally creating known bias toward preferable nodes as an example.
Figure 18 evaluates NRMSE per degree d when estimating P{DG > d} on the Web-Google graph with 5 · 105 samples.
Figure 19 evaluates degree-probability estimation using NRMSE averaged over all possible d when walks do not start in the stationary regime.

A Proof of Proposition 1

The proof constructs delayed-acceptance transitions on directed edges and shows that suitable acceptance probabilities preserve the required conditions. Choosing the Metropolis form yields the proposed transition rule.

The proof analyzes transitions on directed-edge states eij and ejk, including transitions that avoid immediate backtracking.The construction uses an embedded chain and its reversibility to relate directed-edge transitions.
Any acceptance probability satisfying the stated relation produces a transition matrix satisfying the two required conditions.The result holds for any given proposal kernel Q′(eij, ejk).
The acceptance probability can be written as F(T(eij, ejk)), where F(x)=F(1/x)/x and 0≤F≤1.The proof identifies infinitely many admissible choices of F.
Choosing F(x)=min{1,x} yields the acceptance rule used in the proposed construction.

B Proof of Theorem 6

The proof of Theorem 6 establishes convergence and compares the asymptotic variance of the proposed estimator with that of the MH estimator. It uses stationary distributions on directed-edge states, geometric holding times, and ratio-estimator arguments.

The proof maps node functions f to directed-edge functions g(eij)=f(j) and holding parameters γ′(eij)=γ(j).This allows the directed-edge process to represent the corresponding node-level estimator.
The stationary distribution of the directed-edge construction is related to the node distribution through π(i) ∝ ˜π(i)/γ(i).The proof uses this relation to identify matching expectations for node and edge functions.
Geometric holding times and renewal-process arguments establish the relevant almost-sure convergence for the estimator.The proof invokes the strong law for i.i.d. variables and renewal processes.
The variance proof compares the first variance term with the MH quantity and then applies a semi-Markov-chain representation to the proposed process.
The proposed estimator’s asymptotic variance is no larger than the MH estimator’s, σ′2(f) ≤ σ2(f), and likewise σ′2(h) ≤ σ2(h).The comparison is obtained after relating the directed-edge and node-level asymptotic variances.