论文标题
改善了K-Subgraph采样的混合时间
Improved mixing time for k-subgraph sampling
论文作者
论文摘要
了解图的局部结构提供了有关该图产生的基本现象的宝贵见解。采样和检查K-Subgraphs是一种广泛使用的方法，可以理解图形的局部结构。在本文中，我们研究了从给定图表中统一的k-subgraphs取样的问题。我们分析了Markov链蒙特卡洛（MCMC）方法的一些不同的方法，并在其混合时间上获得分析结果，从而显着改善了技术的状态。特别是，我们使用规范性路径参数改善了标准MCMC方法的混合时间和最先进的MCMC采样方法PSRW的结合。此外，我们提出了一种新型的采样方法，我们称之为递归子图采样，RSS及其优化的变体RSS+。所提出的方法，RSS和RSS+的速度明显比现有方法快得多。
Understanding the local structure of a graph provides valuable insights about the underlying phenomena from which the graph has originated. Sampling and examining k-subgraphs is a widely used approach to understand the local structure of a graph. In this paper, we study the problem of sampling uniformly k-subgraphs from a given graph. We analyze a few different Markov chain Monte Carlo (MCMC) approaches, and obtain analytical results on their mixing times, which improve significantly the state of the art. In particular, we improve the bound on the mixing times of the standard MCMC approach, and the state-of-the-art MCMC sampling method PSRW, using the canonical-paths argument. In addition, we propose a novel sampling method, which we call recursive subgraph sampling, RSS, and its optimized variant RSS+. The proposed methods, RSS and RSS+, are significantly faster than existing approaches.
