Improved mixing time for k-subgraph sampling*

Ryuta Matsuno, Aristides Gionis

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Downloads (Pure)


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 analyse 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 provably faster than the existing approaches. We conduct experiments and verify the uniformity of samples and the efficiency of RSS and RSS+.

Original languageEnglish
Title of host publicationProceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020
EditorsCarlotta Demeniconi, Nitesh Chawla
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages9
ISBN (Electronic)9781611976236
Publication statusPublished - 2020
MoE publication typeA4 Article in a conference publication
EventSIAM International Conference on Data Mining - Cincinnati, United States
Duration: 7 May 20209 May 2020


ConferenceSIAM International Conference on Data Mining
Abbreviated titleSDM
CountryUnited States

Fingerprint Dive into the research topics of 'Improved mixing time for k-subgraph sampling*'. Together they form a unique fingerprint.

Cite this