research-article

Network Motif Discovery: A GPU Approach

Authors:

Xiao-Li LiAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 29, Issue 3

Pages 513 - 528

https://doi.org/10.1109/TKDE.2016.2566618

Published: 01 March 2017 Publication History

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.

References

[1]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “ Network motifs: Simple building blocks of complex networks,” Science, vol. Volume 298, no. Issue 5594, pp. 824–827, 2002.

[2]

R. Sole and S. Valverde, “ Are network motifs the sprandrels of cellular complexity?” Trends Ecol. Evoltion, vol. Volume 21, no. Issue 8, pp. 419–422, 2006.

[3]

S. Itzkovitz, R. Levitt, N. Kashtan, R. Milo, M. Itzkovitz, and U. Alon, “ Coarse-graining and self-dissimilarity of complex networks,” Phys. Rev. E, vol. Volume 71, p. pp.016127, 2005.

[4]

O. Sporns and R. Ktter, “ Motifs in brain networks,” PLoS Biol., vol. Volume 2, no. Issue 11, p. pp.e369, 2004.

[5]

S. Wernicke and F. Rasche, “ Fanmod: A tool for fast network motif detection,” Bioinformatics, vol. Volume 22, no. Issue 9, pp. 1152–1153, 2006.

Digital Library

[6]

J. A. Grochow and M. Kellis, “ Network motif discovery using subgraph enumeration and symmetry-breaking,” in Proc. 11th Annu. Int. Conf. Res. Comput. Molecular Biol., 2007, pp. 92–106.

[7]

S. Omidi, F. Schreiber, and A. Masoudi-Nejad, “ MODA: An efficient algorithm for network motif discovery in biological networks,” Genes Genetic Syst., vol. Volume 84, no. Issue 5, pp. 385–395, 2009.

[8]

Z. R. M. Kashani, H. Ahrabian, E. Elahi, A. Nowzari-Dalini, E. S. Ansari, S. Asadi, S. Mohammadi, F. Schreiber, and A. Masoudi-Nejad, “ Kavosh: A new algorithm for finding network motifs,” BMC Bioinf., vol. Volume 10, p. pp.318, 2009.

[9]

P. M. P. Ribeiro and F. M. A. Silva, “ g-tries: An efficient data structure for discovering network motifs,” in Proc. ACM Symp. Appl. Comput., 2010, pp. 1559–1566.

Digital Library

[10]

S. Khakabimamaghani, I. Sharafuddin, N. Dichter, I. Koch, and A. Masoudi-Nejad, “ Quatexelero: An accelerated exact network motif detection algorithm,” PLoS ONE, vol. Volume 8, no. Issue 7, p. pp.e68073, 2013.

[11]

X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu, and G. Wang, “ Netmode: Network motif detection without nauty,” PLoS ONE, vol. Volume 7, no. Issue 12, p. pp.e50093, 2012.

[12]

P. M. P. Ribeiro, F. M. A. Silva, and L. M. B. Lopes, “ Parallel discovery of network motifs,” J. Parallel Distrib. Comput., vol. Volume 72, no. Issue 2, pp. 144–154, 2012.

Digital Library

[13]

T. Wang, J. W. Touchman, W. Zhang, E. B. Suh, and G. Xue, “ A parallel algorithm for extracting transcription regulatory network motifs,” in Proc. 5th IEEE Symp. Bioinf. Bioeng., 2005, pp. 193–200.

[14]

B. D. McKay and A. Piperno, “ Practical graph isomorphism, ii,” J. Symbolic Comput., vol. Volume 60, pp. 94–112, 2014.

Digital Library

[15]

E. Sintorn and U. Assarsson, “ Fast parallel GPU-sorting using a hybrid algorithm,” J. Parallel Distrib. Comput., vol. Volume 68, no. Issue 10, pp. 1381–1388, 2008.

Digital Library

[16]

W. Fang, M. Lu, X. Xiao, B. He, and Q. Luo, “ Frequent itemset mining on graphics processors,” in Proc. 5th Int. Workshop Data Manag. New Hardw., 2009, pp. 34–42.

Digital Library

[17]

T. D. Han and T. S. Abdelrahman, “ Reducing branch divergence in GPU programs,” in Proc. 4th Workshop General Purpose Process. Graph. Process. Units, 2011, Art. no. 3.

Digital Library

[18]

X. Yan and J. Han, “ gSpan: Graph-based substructure pattern mining,” in Proc. IEEE Int. Conf. Data Mining, 2002, pp. 721–724.

Digital Library

[19]

W.-S. Han, J. Lee, and J.-H. Lee, “ Turbo $_{\mbox{iso}}$ : Towards ultrafast and robust subgraph isomorphism search in large graph databases,” in Proc. ACM SIGMOD Conf. Manage. Data, 2013, pp. 337–348.

[20]

J. R. Ullmann, “ An algorithm for subgraph isomorphism,” J. ACM, vol. Volume 23, no. Issue 1, pp. 31–42, 1976.

Digital Library

[21]

H. Shang, Y. Zhang, X. Lin, and J. X. Yu, “ Taming verification hardness: An efficient algorithm for testing subgraph isomorphism,” Proc. VDLB Endowment, vol. Volume 1, no. Issue 1, pp. 364–375, 2008.

[22]

[Online]. Available: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/compressed_sparse_row .html

[23]

W. Lin, X. Xiao, J. Cheng, and S. S. Bhowmick, “ Efficient algorithms for generalized subgraph query processing,” in Proc. ACM Int. Conf. Inf. Knowl. Manage., 2012, pp. 325–334.

Digital Library

[24]

J. Chen, W. Hsu, M.-L. Lee, and S.-K. Ng, “ Nemofinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs,” in Proc. 12th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2006, pp. 106–115.

Digital Library

[25]

[Online]. Available: http://thrust.github.com

[26]

W. Lin, X. Xiao, and G. Ghinita, “ Large-scale frequent subgraph mining in mapreduce,” in Proc. Int. Conf. Data Eng., 2014, pp. 844–855.

[27]

[Online]. Available: http://lbb.ut.ac.ir/Download/LBBsoft/QuateXelero/networks/

[28]

[Online]. Available: http://genemania.org

[29]

C. Jiang, F. Coenen, and M. Zito, “ A survey of frequent subgraph mining algorithms,” Knowl. Eng. Rev., vol. Volume 28, no. Issue 1, pp. 75–105, 2013.

[30]

N. Kashtan, S. Itzkovitz, R. Milo, and U. Alon, “ Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs,” Bioinformatics, vol. Volume 20, no. Issue 11, pp. 1746–1758, 2004.

Digital Library

[31]

I. Bordino, D. Donato, A. Gionis, and S. Leonardi, “ Mining large networks with subgraph counting,” in Proc. IEEE 11th Int. Conf. Data Mining, 2008, pp. 737–742.

Digital Library

[32]

N. Alon, P. Dao, I. Hajirasouliha, F. Hormozdiari, and S. C. Sahinalp, “ Biomolecular network motif counting and discovery by color coding,” Bioinformatics, vol. Volume 24, pp. 241–249, 2008.

Digital Library

[33]

Z. Zhao, M. Khan, V. S. A. Kumar, and M. V. Marathe, “ Subgraph enumeration in large social contact networks using parallel color coding and streaming,” in Proc. 39th Int. Conf. Parallel Process., 2010, pp. 594–603.

Digital Library

[34]

F. N. Afrati, D. Fotakis, and J. D. Ullman, “ Enumerating subgraph instances using map-reduce,” in Proc. Int. Conf. Data Eng., 2013, pp. 62–73.

Digital Library

[35]

Y. Shao, B. Cui, L. Chen, L. Ma, J. Yao, and N. Xu, “ Parallel subgraph listing in a large-scale graph,” in Proc. ACM SIGMOD Conf. Manage. Data, 2014, pp. 625–636.

Digital Library

[36]

S. Ranu and A. K. Singh, “ Graphsig: A scalable approach to mining significant subgraphs in large graph databases,” in Proc. Int. Conf. Data Eng., 2009, pp. 844–855.

Digital Library

[37]

X. Yan, H. Cheng, J. Han, and P. S. Yu, “ Mining significant graph patterns by leap search,” in Proc. ACM SIGMOD Conf. Manage. Data, 2008, pp. 433–444.

Digital Library

[38]

H. He and A. K. Singh, “ Graphrank: Statistical modeling and mining of significant subgraphs in the feature space,” in Proc. IEEE 11th Int. Conf. Data Mining, 2006, pp. 885–890.

Digital Library

[39]

W. Lin, X. Xiao, X. Xie, and X. Li, “ Network motif discovery: A GPU approach,” in Proc. Int. Conf. Data Eng., 2015, pp. 831–842.

Cited By

Ye CLi YHe BLi ZSun J(2024)Large-Scale Graph Label Propagation on GPUsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.333632936:10(5234-5248)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3336329
Sun XLuo Q(2023)Efficient GPU-Accelerated Subgraph MatchingProceedings of the ACM on Management of Data10.1145/35893261:2(1-26)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589326
Huang LZhu YGao YLiu TChang CLiu CTang YWang C(2023)Hybrid-Order Anomaly Detection on Attributed NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.311784235:12(12249-12263)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TKDE.2021.3117842
Show More Cited By

Recommendations

An Ultrafast Scalable Many-Core Motif Discovery Algorithm for Multiple GPUs
IPDPSW '11: Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum

The identification of genome-wide transcription factor binding sites is a fundamental and crucial problem to fully understand the transcriptional regulatory processes. However, the high computational cost of many motif discovery algorithms heavily ...
Biomolecular network motif counting and discovery by color coding

Protein–protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of ...
Network motif discovery using subgraph enumeration and symmetry-breaking
RECOMB'07: Proceedings of the 11th annual international conference on Research in computational molecular biology

The study of biological networks and network motifs can yield significant new insights into systems biology. Previous methods of discovering network motifs - network-centric subgraph enumeration and sampling - have been limited to motifs of 6 to 8 nodes,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 29, Issue 3

March 2017

217 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2017.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 March 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ye CLi YHe BLi ZSun J(2024)Large-Scale Graph Label Propagation on GPUsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.333632936:10(5234-5248)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3336329
Sun XLuo Q(2023)Efficient GPU-Accelerated Subgraph MatchingProceedings of the ACM on Management of Data10.1145/35893261:2(1-26)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589326
Huang LZhu YGao YLiu TChang CLiu CTang YWang C(2023)Hybrid-Order Anomaly Detection on Attributed NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.311784235:12(12249-12263)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TKDE.2021.3117842
Yuan ZShao MYan Q(2023)Motif-Level Anomaly Detection in Dynamic GraphsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327273118(2870-2882)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3272731
Almasri MHajj INagi RXiong JHwu WRauchwerger LCameron KNikolopoulos DPnevmatikatos D(2022)Parallel K-clique counting on GPUsProceedings of the 36th ACM International Conference on Supercomputing10.1145/3524059.3532382(1-14)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1145/3524059.3532382
Huang LTang YFu CWang JWang C(2022)GHOCInternational Journal of Intelligent Systems10.1002/int.2298037:11(9055-9079)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1002/int.22980
Xie GChen JLi Y(2021)Hybrid-order Network Consensus for Distributed Multi-agent SystemsJournal of Artificial Intelligence Research10.1613/jair.1.1206170(389-407)Online publication date: 25-Jan-2021
https://dl.acm.org/doi/10.1613/jair.1.12061
Sha MLi YTan KLi GLi ZIdreos SSrivastava D(2021)Self-adaptive Graph Traversal on GPUsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457279(1558-1570)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457279
Gui CLiao XZheng LYao PWang QJin H(2021)SumPA: Efficient Pattern-Centric Graph Mining with Pattern AbstractionProceedings of the 30th International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT52795.2021.00030(318-330)Online publication date: 26-Sep-2021
https://dl.acm.org/doi/10.1109/PACT52795.2021.00030
Li PHuang LWang CLai JHuang D(2020)Community Detection by Motif-Aware Label PropagationACM Transactions on Knowledge Discovery from Data10.1145/337853714:2(1-19)Online publication date: 9-Feb-2020
https://dl.acm.org/doi/10.1145/3378537
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents