Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81386
Title: Network Motif Discovery: A GPU Approach
Authors: Lin, Wenqing
Xiao, Xiaokui
Xie, Xing
Li, Xiao-Li
Keywords: Network motif
GPU
Issue Date: 2016
Source: Lin, W., Xiao, X., Xie, X., & Li, X.-L. (2017). Network Motif Discovery: A GPU Approach. IEEE Transactions on Knowledge and Data Engineering, 29(3), 513-528.
Series/Report no.: IEEE Transactions on Knowledge and Data Engineering
Abstract: The identification of network motifs has important applications in numerous domains, such as pattern detection in biological networks and graph analysis in digital circuits. However, mining network motifs is computationally challenging, as it requires enumerating subgraphs from a real-life graph, and computing the frequency of each subgraph in a large number of random graphs. In particular, existing solutions often require days to derive network motifs from biological networks with only a few thousand vertices. To address this problem, this paper presents a novel study on network motif discovery using Graphical Processing Units (GPUs). The basic idea is to employ GPUs to parallelize a large number of subgraph matching tasks in computing subgraph frequencies from random graphs, so as to reduce the overall computation time of network motif discovery. We explore the design space of GPU-based subgraph matching algorithms, with careful analysis of several crucial factors (such as branch divergences and memory coalescing) that affect the performance of GPU programs. Based on our analysis, we develop a GPU-based solution that (i) considerably differs from existing CPU-based methods in how it enumerates subgraphs, and (ii) exploits the strengths of GPUs in terms of parallelism while mitigating their limitations in terms of the computation power per GPU core. With extensive experiments on a variety of biological networks, we show that our solution is up to two orders of magnitude faster than the best CPU-based approach, and is around 20 times more cost-effective than the latter, when taking into account the monetary costs of the CPU and GPUs used.
URI: https://hdl.handle.net/10356/81386
http://hdl.handle.net/10220/43474
ISSN: 1041-4347
DOI: 10.1109/TKDE.2016.2566618
Rights: © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [ttp://dx.doi.org/10.1109/TKDE.2016.2566618].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Network Motif Discovery - A GPU Approach.pdf343.77 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 10

27
Updated on Jul 5, 2022

PublonsTM
Citations 10

26
Updated on Jul 6, 2022

Page view(s) 50

475
Updated on Aug 8, 2022

Download(s) 20

183
Updated on Aug 8, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.