Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2020

Abstract

Subgraph enumeration is important for many applications such as network motif discovery and community detection. Recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration, but they can only handle graphs that fit into the GPU memory. In this paper, we propose a new approach for GPU-accelerated subgraph enumeration that can efficiently scale to large graphs beyond the GPU memory. Our approach divides the graph into partitions, each of which fits into the GPU memory. The GPU processes one partition at a time and searches the matched subgraphs of a given pattern (i.e., instances) within the partition as in the small graph. The key challenge is on enumerating the instances across different partitions, because this search would enumerate considerably redundant subgraphs and cause the expensive data transfer cost via the PCI-e bus. Therefore, we propose a novel shared execution approach to eliminate the redundant subgraph searches and correctly generate all the instances across different partitions. The experimental evaluation shows that our approach can scale to large graphs and achieve significantly better performance than the existing single-machine solutions.

Keywords

GPU, Partitioned graph, Subgraph enumeration

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

SIGMOD '20: Proceedings of the ACM SIGMOD International Conference on Management of Data, Portland, June 14-19

First Page

1067

Last Page

1082

ISBN

9781450367356

Identifier

10.1145/3318464.3389699

Publisher

ACM

City or Country

New York

Embargo Period

5-24-2021

Copyright Owner and License

Publisher

Additional URL

https://doi.org/10.1145/3318464.3389699

Download

Share

COinS