Reproduce “Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Chul-Ho Lee, Xin Xu, Do Young Eun
The authors introduce two graph-crawling methods that remember the previous node to redirect some immediate reversals while preserving the sampling target. One adapts a non-backtracking walk, and the other delays accepted reversals in a Metropolis–Hastings walk. Theory guarantees no-greater asymptotic variance than each matched baseline; on Road-PA, simulations report about 60% and 54% fewer samples, respectively, at equal degree-distribution accuracy.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.