Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation

DOI10.1007/S10618-021-00802-3MaRDI QIDQ832666zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 25 March 2022

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.03879

zbMATH Keywords

graph miningMarkov chain Monte Carlomotif analysisrandom walkregenerative samplingsubgraph counting

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational methods in Markov chains (60J22)

Abstract: This work considers the general task of estimating the sum of a bounded function over the edges of a graph, given neighborhood query access and where access to the entire network is prohibitively expensive. To estimate this sum, prior work proposes Markov chain Monte Carlo (MCMC) methods that use random walks started at some seed vertex and whose equilibrium distribution is the uniform distribution over all edges, eliminating the need to iterate over all edges. Unfortunately, these existing estimators are not scalable to massive real-world graphs. In this paper, we introduce Ripple, an MCMC-based estimator that achieves unprecedented scalability by stratifying the Markov chain state space into ordered strata with a new technique that we denote {em sequential stratified regenerations}. We show that the Ripple estimator is consistent, highly parallelizable, and scales well. We empirically evaluate our method by applying Ripple to the task of estimating connected, induced subgraph counts given some input graph. Therein, we demonstrate that Ripple is accurate and can estimate counts of up to $12$-node subgraphs, which is a task at a scale that has been considered unreachable, not only by prior MCMC-based methods but also by other sampling approaches. For instance, in this target application, we present results in which the Markov chain state space is as large as $10^{43}$, for which Ripple computes estimates in less than $4$ hours, on average.

Recommendations

• Sequential Monte Carlo for counting vertex covers in general graphs
• Counting arbitrary subgraphs in data streams
• Estimating the number of connected components in a graph via subgraph sampling
• Fast low-cost estimation of network properties using random walks
• Utilizing network structure to accelerate Markov chain Monte Carlo algorithms

Cites work

• A New Approach to the Limit Theory of Recurrent Markov Chains
• A splitting technique for Harris recurrent Markov chains
• Exact estimation for Markov chain equilibrium expectations
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Fast Low-Cost Estimation of Network Properties Using Random Walks
• Geometric bounds for eigenvalues of Markov chains
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Markov Chains
• Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
• Monte Carlo sampling methods using Markov chains and their applications
• Peer counting and sampling in overlay networks, random walk methods
• Random sampling with a reservoir
• Regeneration in Markov Chain Samplers
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Unbiased Markov Chain Monte Carlo Methods with Couplings

Describes a project that uses

Uses Software

• Algorithm 447
• SNAP

This page was built for publication: Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832666)