BEEP: Balanced Efficient subgraph Enumeration in Parallel
Authors: 
Samiran Kawtikwar, Mohammad Almasri, Wen-Mei Hwu, Rakesh Nagi, Jinjun XiongAuthors Info & Claims
Pages 142 - 152
Abstract
BEEP is a state-of-the-art subgraph enumerator that delivers high performance through a combination of balanced, parallel GPU processing and novel algorithmic improvements. With a rapidly increasing demand for fast tools on large graphs, GPU-based subgraph enumerators are of growing interest. Most existing GPU enumerators are based on Breadth First Search (BFS), which often impose limitations on hardware resources due to excessive memory requirements. PARSEC [12] was the first GPU enumerator to adopt Depth First Search (DFS) that demonstrated impressive speedups and its adaptability to hardware with limited memory resources. However, PARSEC’s DFS implementation suffers from computational inefficiencies and load imbalances. BEEP introduces novel search space reduction techniques and load balancing strategies to tackle these challenges in DFS-based parallelization and achieves exceptional performance and scalability. Experimental results indicate that BEEP outperforms PARSEC with geometric mean speedups of up to 10.52 × across disparate data graphs and up to 7.28 × across various queries with maximum speedups of 33.46 ×. This makes BEEP the fastest subgraph enumerator to date. Furthermore, a multi-GPU implementation is developed that exhibits almost linear scalability with the number of devices.
References
[1]
Mohammad Almasri, Omer Anjum, Carl Pearson, Zaid Qureshi, Vikram S. Mailthody, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2019. Update on k-truss Decomposition on GPU. In 2019 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, Waltham, USA, 1–7. https://doi.org/10.1109/HPEC.2019.8916285
[2]
Mohammad Almasri, Yen-Hsiang Chang, Izzat El Hajj, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2022. Parallelizing Maximal Clique Enumeration on GPUs. https://doi.org/10.48550/ARXIV.2212.01473
[3]
Mohammad Almasri, Izzat El Hajj, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2022. Parallel K-Clique Counting on GPUs. In Proceedings of the 36th ACM International Conference on Supercomputing (Virtual Event) (ICS ’22). ACM, New York, USA, Article 21, 14 pages. https://doi.org/10.1145/3524059.3532382
[4]
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics (Oxford, England) 24, 13 (01 Jul 2008), i241–i249. https://doi.org/10.1093/bioinformatics/btn163
[5]
Roberto Alonso and Stephan Günnemann. 2018. Mining Contrasting Quasi-Clique Patterns. CoRR abs/1810.01836 (2018). http://arxiv.org/abs/1810.01836
[6]
Bibek Bhattarai, Hang Liu, and H. Howie Huang. 2019. CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands). ACM, New York, USA, 1447–1462. https://doi.org/10.1145/3299869.3300086
[7]
Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. 2018. Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3. IEEE Transactions on Pattern Analysis and Machine Intelligence 40, 4 (2018), 804–818. https://doi.org/10.1109/TPAMI.2017.2696940
[8]
Xuhao Chen and Arvind. 2021. Efficient and Scalable Graph Pattern Mining on GPUs. https://doi.org/10.48550/ARXIV.2112.09761
[9]
L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. 2004. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 10 (2004), 1367–1372. https://doi.org/10.1109/TPAMI.2004.75
[10]
James M. Crawford, Matthew L. Ginsberg, Eugene M. Luks, and Amitabha Roy. 1996. Symmetry-Breaking Predicates for Search Problems. In Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (Cambridge, Massachusetts, USA) (KR’96). ACM, San Francisco, CA, USA, 148–159.
[11]
Aarzoo Dhiman and S.K. Jain. 2016. Optimizing Frequent Subgraph Mining for Single Large Graph. Procedia Computer Science 89 (2016), 378–385. https://doi.org/10.1016/j.procs.2016.06.085
[12]
Vibhor Dodeja, Mohammad Almasri, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2022. PARSEC: PARallel Subgraph Enumeration in CUDA. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, Lyon, France, 168–178. https://doi.org/10.1109/IPDPS53621.2022.00025
[13]
Pasquale Foggia, Carlo Sansone, and Mario Vento. 2001. An Improved Algorithm for Matching Large Graphs. In 3rd IAPR-TC-15 International Workshop on Graph-based Representation. springer, Ischia, Italy, 149–159.
[14]
Joshua A Grochow and Manolis Kellis. 2007. Network motif discovery using subgraph enumeration and symmetry-breaking. In Annual International Conference on Research in Computational Molecular Biology. Springer, San Francisco, CA, USA, 92–106.
[15]
Wentian Guo, Yuchen Li, Mo Sha, Bingsheng He, Xiaokui Xiao, and Kian Tan. 2020. GPU-Accelerated Subgraph Enumeration on Partitioned Graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, Portland, Oregon, USA, 1067–1082. https://doi.org/10.1145/3318464.3389699
[16]
Wentian Guo, Yuchen Li, and Lee Tan. 2020. Exploiting Reuse for GPU Subgraph Enumeration. IEEE Transactions on Knowledge and Data Engineering PP (2020), 1–1. https://doi.org/10.1109/TKDE.2020.3035564
[17]
Ivan Gutman, Christoph Rücker, and Gerta Rücker‡. 2001. On Walks in Molecular Graphs. Journal of chemical information and computer sciences 41 (05 2001), 739–45. https://doi.org/10.1021/ci000149u
[18]
Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013. Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data(SIGMOD ’13). ACM, New York, USA, 337–348. https://doi.org/10.1145/2463676.2465300
[19]
George Karypis and Vipin Kumar. 1997. METIS—A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes and Computing Fill-Reducing Ordering of Sparse Matrices. University of Minnesota Digital Conservancy. https://hdl.handle.net/11299/215346
[20]
Longbin Lai, Lu Qin, Xuemin Lin, and Lijun Chang. 2015. Scalable Subgraph Enumeration in MapReduce. Proc. VLDB Endow. 8, 10 (jun 2015), 974–985. https://doi.org/10.14778/2794367.2794368
[21]
Longbin Lai, Lu Qin, Xuemin Lin, Ying Zhang, Lijun Chang, and Shiyu Yang. 2016. Scalable Distributed Subgraph Enumeration. Proc. VLDB Endow. 10, 3 (nov 2016), 217–228. https://doi.org/10.14778/3021924.3021937
[22]
Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford large network dataset collection.
[23]
Vikram S. Mailthody, Ketan Date, Zaid Qureshi, Carl Pearson, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2018. Collaborative (CPU + GPU) Algorithms for Triangle Counting and Truss Decomposition. In 2018 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, Waltham, USA, 1–7. https://doi.org/10.1109/HPEC.2018.8547517
[24]
Brendan D McKay and Adolfo Piperno. 2014. Practical graph isomorphism, II. Journal of Symbolic Computation 60 (2014), 94–112.
[25]
Tijana Milenković and Natasa Przulj. 2008. Uncovering biological network function via graphlet degree signatures. Cancer informatics 6 (2008), 257–273. https:// .ncbi.nlm.nih.gov/19259413
[26]
NVIDIA Corporation. 2017. NVIDIA Tesla V100 GPU Architecture, Data Center GPU. NVIDIA. https://www.nvidia.com/en-us/data-center/v100/
[27]
Xuguang Ren and Junhu Wang. 2015. Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs. Proc. VLDB Endow. 8 (2015), 617–628. https://doi.org/10.14778/2735479.2735493
[28]
Carlos R. Rivero and Hasan M. Jamil. 2016. Efficient and scalable labeled subgraph matching using SGMatch. Knowledge and Information Systems 51 (2016), 61–87.
[29]
Yingxia Shao, Bin Cui, Lei Chen, Lin Ma, Junjie Yao, and Ning Xu. 2014. Parallel Subgraph Listing in a Large-Scale Graph. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (Snowbird, Utah, USA). ACM, New York, USA, 625–636. https://doi.org/10.1145/2588555.2588557
[30]
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics, Vol. 5. PMLR, San Francisco, CA. USA, 488–495.
[31]
Christine Solnon. 2010. AllDifferent-based filtering for subgraph isomorphism. Artificial Intelligence 174, 12 (2010), 850–864. https://doi.org/10.1016/j.artint.2010.05.002
[32]
Shixuan Sun, Yulin Che, Lipeng Wang, and Qiong Luo. 2019. Efficient Parallel Subgraph Enumeration on a Single Machine. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, Macau SAR, China, 232–243. https://doi.org/10.1109/ICDE.2019.00029
[33]
Ha-Nguyen Tran, Jung-jae Kim, and Bingsheng He. 2015. Fast Subgraph Matching on Large Graphs using Graphics Processors. In Database Systems for Advanced Applications. Springer International Publishing, Cham, 299–315.
[34]
J. R. Ullmann. 1976. An Algorithm for Subgraph Isomorphism. J. ACM 23, 1 (jan 1976), 31–42. https://doi.org/10.1145/321921.321925
[35]
Ingo Wegener. 2005. Complexity Theory - Exploring the Limits of Efficient Algorithms. Springer, Berlin, Heidelberg.
[36]
Lizhi Xiang, Arif Khan, Edoardo Serra, Mahantesh Halappanavar, and Aravind Sukumaran-Rajam. 2021. CuTS: Scaling Subgraph Isomorphism on Distributed Multi-GPU Systems Using Trie Based Data Structure. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (St. Louis, Missouri) (SC ’21). Association for Computing Machinery, New York, NY, USA, Article 69, 14 pages. https://doi.org/10.1145/3458817.3476214
[37]
Shuo Yu, Yufan Feng, Da Zhang, Hayat Dino Bedru, Bo Xu, and Feng Xia. 2020. Motif discovery in networks: A survey. Computer Science Review 37 (2020), 100267. https://doi.org/10.1016/j.cosrev.2020.100267
Recommendations
Efficient Maximal Biclique Enumeration on GPUs
SC '23: Proceedings of the International Conference for High Performance Computing, Networking, Storage and AnalysisMaximal biclique enumeration (MBE) in bipartite graphs is an important problem in data mining with many real-world applications. All existing solutions for MBE are designed for CPUs. Parallel MBE algorithms for GPUs are needed for MBE acceleration ...
Efficient GPU-Accelerated Subgraph Matching
PACMMODSubgraph matching is a basic operation in graph analytics, finding all occurrences of a query graph Q in a data graph G. A common approach is to first filter out non-candidate vertices in G, and then order the vertices in Q to enumerate results. Recent ...
GPU-Accelerated Subgraph Enumeration on Partitioned Graphs
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of DataSubgraph 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2023
858 pages
ISBN:9798400708435
DOI:10.1145/3605573
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 September 2023
Check for updates
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Delta research computing project
Conference
ICPP 2023
ICPP 2023: 52nd International Conference on Parallel Processing
August 7 - 10, 2023
UT, Salt Lake City, USA
Acceptance Rates
Overall Acceptance Rate 91 of 313 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 158Total Downloads
- Downloads (Last 12 months)120
- Downloads (Last 6 weeks)12
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format