Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

4-2021

Abstract

In this paper, we study the problem of efficient motif-based graph partitioning (MGP). We observe that existing methods require to enumerate all motif instances to compute the exact edge weights for partitioning. However, the enumeration is prohibitively expensive against large graphs. We thus propose a sampling-based MGP (SMGP) framework that employs an unbiased sampling mechanism to efficiently estimate the edge weights while trying to preserve the partitioning quality. To further improve the effectiveness, we propose a novel adaptive sampling framework called SMGP+. SMGP+ iteratively partitions the input graph based on up-to-date estimated edge weights, and adaptively adjusts the sampling distribution so that edges that are more likely to affect the partitioning outcome will be prioritized for weight estimation. To our best knowledge, this is the first attempt to solve the MGP problem without employing exact edge weight computations, which gives hope for existing MGP methods to perform on complicated motifs in a scalable yet effective manner. Extensive experiments on seven real-world datasets have validated that our framework delivers competitive partitioning quality compared to existing workflows based on exact edge weights, while achieving orders of magnitude speedup.

Discipline

Databases and Information Systems | Data Storage Systems

Research Areas

Data Science and Engineering

Publication

Proceedings of 2021 IEEE 37th International Conference on Data Engineering (ICDE 2021), Chania, Greece, April 19-22

First Page

528

Last Page

539

Identifier

10.1109/ICDE51399.2021.00052

Publisher

IEEE

City or Country

Virtual Conference

Download

Share

COinS