Sequential stratified regeneration: MCMC for large state spaces with an application to subgraph count estimation
Sequential stratified regeneration: MCMC for large state spaces with an application to subgraph count estimation
复制标题
DOI：
10.1007/s10618-021-00802-3
复制
发表时间：
2022-01
影响因子：
4.8
通讯作者：
Carlos H. C. Teixeira;Mayank Kakodkar;Vinícius Dias;Wagner Meira Jr;Bruno Ribeiro
中科院分区：
文献类型：
--
作者：
Carlos H. C. Teixeira;Mayank Kakodkar;Vinícius Dias;Wagner Meira Jr;Bruno Ribeiro
这项工作考虑了估计图边缘上有界函数和的一般任务，给定邻域查询访问，并且访问整个网络的代价非常昂贵。为了估计这个总和，先前的工作提出了马尔可夫链蒙特卡罗（MCMC）方法，该方法使用从某些种子顶点开始的随机行走，其平衡分布是所有边的均匀分布，从而消除了在所有边上迭代的需要。不幸的是，这些现有的估计器不能扩展到大量的真实世界的图形。在本文中，我们介绍了Ripple，一个基于mcmc的估计器，它通过将马尔可夫链状态空间分层为有序层来实现前所未有的可扩展性，我们使用了一种新技术，我们表示为等量分层再生。我们证明了波纹估计器是一致的，高度并行的，并且很好地扩展。我们通过将Ripple应用于给定输入图的连通、诱导子图计数的估计任务，对我们的方法进行了经验评估。其中，我们证明了Ripple是准确的，可以估计多达12个节点子图的计数，这是一项在规模上被认为是不可达的任务，不仅是基于priormcmc的方法，而且是其他采样方法。例如，在这个目标应用程序中，我们给出了马尔可夫链状态空间与的结果，Ripple平均在不到4小时的时间内计算估计。
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, anMCMC-based estimator that achieves unprecedented scalability by stratifying the Markov chain state space into ordered strata with a new technique that we denotesequential 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 priorMCMC-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, for which Ripple computes estimates in less than 4 h, on average.