GPU-accelerated subgraph enumeration on partitioned graphs

• Main Authors: GUO, Wentian, LI, Yuchen, SHA, Mo, HE, Bingsheng, XIAO, Xiaokui, TAN, Kian-Lee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: GPU; Partitioned graph; Subgraph enumeration; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/5961; https://ink.library.smu.edu.sg/context/sis_research/article/6964/viewcontent/GPU_Accelerated_Subgraph_Enumeration.pdf
• Institution: Singapore Management University

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.