Improved mixing time for k-subgraph sampling*

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)

Authors

Date

2020

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

9

Series

Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020, pp. 568-576

Abstract

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+.

Description

| openaire: EC/H2020/654024/EU//SoBigData

Keywords

Other note

DOI

10.1137/1.9781611976236.64

Citation

Matsuno, R & Gionis, A 2020, Improved mixing time for k-subgraph sampling* . in C Demeniconi & N Chawla (eds), Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020 . Society for Industrial and Applied Mathematics, pp. 568-576, SIAM International Conference on Data Mining, Cincinnati, Ohio, United States, 07/05/2020 . https://doi.org/10.1137/1.9781611976236.64

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202102262093

Collections

[article-cris] Perustieteiden korkeakoulu / SCI