research-article

Open access

cuTS: scaling subgraph isomorphism on distributed multi-GPU systems using trie based data structure

Authors:

Mahantesh Halappanavar,

Aravind Sukumaran-RajamAuthors Info & Claims

SC '21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 69, Pages 1 - 14

https://doi.org/10.1145/3458817.3476214

Published: 13 November 2021 Publication History

Abstract

Subgraph isomorphism is a pattern-matching algorithm widely used in many domains such as chem-informatics, bioinformatics, databases, and social network analysis. It is computationally expensive and is a proven NP-hard problem. The massive parallelism in GPUs is well suited for solving subgraph isomorphism. However, current GPU implementations are far from the achievable performance. Moreover, the enormous memory requirement of current approaches limits the problem size that can be handled. This work analyzes the fundamental challenges associated with processing subgraph isomorphism on GPUs and develops an efficient GPU implementation. We also develop a GPU-friendly trie-based data structure to drastically reduce the intermediate storage space requirement, enabling large benchmarks to be processed. We also develop the first distributed sub-graph isomorphism algorithm for GPUs. Our experimental evaluation demonstrates the efficacy of our approach by comparing the execution time and number of cases that can be handled against the state-of-the-art GPU implementations.

Supplementary Material

MP4 File (cuTS Scaling Subgraph Isomorphism on Distributed Multi-GPU Systems Using Trie Based Data Structure 232 Afternoon 6.mp4.mp4)

Presentation video

Download
231.09 MB

References

[1]

Fei Bi, Lijun Chang, Xuemin Lin, Lu Qin, and Wenjie Zhang. 2016. Efficient subgraph matching by postponing cartesian products. In Proceedings of the 2016 International Conference on Management of Data. 1199--1214.

Digital Library

[2]

Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC bioinformatics 14, 7 (2013), 1--13.

[3]

Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. 2017. Introducing VF3: A new algorithm for subgraph isomorphism. In International Workshop on Graph-Based Representations in Pattern Recognition. Springer, 128--139.

Digital Library

[4]

Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence 26, 10 (2004), 1367--1372.

[5]

Wenfei Fan. 2012. Graph Pattern Matching Revised for Social Network Analysis. (2012).

[6]

Fred G. Gustavson. 1978. Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition. ACM Trans. Math. Softw. 4, 3 (1978), 250--269.

Digital Library

[7]

Huahai He and Ambuj K Singh. 2008. Graphs-at-a-time: query language and access methods for graph databases. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data. 405--418.

Digital Library

[8]

Fuad Jamour, Ibrahim Abdelaziz, Yuanzhao Chen, and Panos Kalnis. 2019. Matrix algebra framework for portable, scalable and efficient query engines for rdf graphs. In Proceedings of the Fourteenth EuroSys Conference 2019. 1--15.

Digital Library

[9]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[10]

Amine Mhedhbi and Semih Salihoglu. 2019. Optimizing subgraph queries by combining binary and worst-case optimal joins. arXiv preprint arXiv:1903.02076 (2019).

[11]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. 2002. Network Motifs: Simple Building Blocks of Complex Networks. Science (2002).

[12]

Haichuan Shang, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2008. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proceedings of the VLDB Endowment 1, 1 (2008), 364--375.

Digital Library

[13]

Ha-Nguyen Tran, Jung-jae Kim, and Bingsheng He. 2015. Fast subgraph matching on large graphs using graphics processors. In International Conference on Database Systems for Advanced Applications. Springer, 299--315.

[14]

JR ULLMANN. 1976. An Algorithm for Subgraph Isomorphism. (1976).

[15]

Leyuan Wang and John D Owens. 2020. Fast Gunrock Subgraph Matching (GSM) on GPUs. arXiv preprint arXiv:2003.01527 (2020).

[16]

Siyuan Wang, Chang Lou, Rong Chen, and Haibo Chen. 2018. Fast and concurrent {RDF} queries using RDMA-assisted {GPU} graph exploration. In 2018 {USENIX} Annual Technical Conference ({USENIX}{ATC} 18). 651--664.

[17]

L. Zeng, L. Zou, M. T. Özsu, L. Hu, and F. Zhang. 2020. GSI: GPU-friendly Subgraph Isomorphism. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 1249--1260.

[18]

Shijie Zhang, Shirong Li, and Jiong Yang. 2009. GADDI: distance index based subgraph matching in biological networks. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. 192--203.

Digital Library

[19]

Peixiang Zhao and Jiawei Han. 2010. On graph query optimization in large networks. Proceedings of the VLDB Endowment 3, 1--2 (2010), 340--351.

Digital Library

Cited By

Li GZhang HSun XLuo QZhu Y(2024)TenGraph: A Tensor-Based Graph Query EngineProceedings of the VLDB Endowment10.14778/3704965.370496717:13(4571-4584)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.14778/3704965.3704967
Meng LShao YYuan LLai LCheng PLi XYu WZhang WLin XZhou J(2024)A Survey of Distributed Graph Algorithms on Massive GraphsACM Computing Surveys10.1145/3694966Online publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1145/3694966
Chen CShen LChen Y(2024)A Distributed Framework for Subgraph Isomorphism Leveraging CPU and GPU Heterogeneous ComputingProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673134(433-442)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673134
Show More Cited By

Index Terms

cuTS: scaling subgraph isomorphism on distributed multi-GPU systems using trie based data structure

Index terms have been assigned to the content through auto-classification.

Recommendations

Cuts leaving components of given minimum order

For a connected graph G, the restricted edge-connectivity @l"p(G) is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that each component of G-S contains at least p vertices. In the present paper we introduce the more general ...
An Anti-Ramsey Theorem of k-Restricted Edge-Cuts
Abstract
Given a graph G (with multiple edges allowed), a k-restricted edge-cut of G is an edge-cut $R \subseteq E (G)$ of G such that every connected component in $G - R$ has order at least k. A graph G is $λ_{k}$ -connected if k-restricted edge cuts exist. Given an edge-... $_{}$ $_{}$ $_{}$
Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2021

1493 pages

ISBN:9781450384421

DOI:10.1145/3458817

General Chair:
Bronis R. de Supinski,
Program Chairs:
Mary Hall,
Todd Gamblin

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Check for updates

Badges

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SC '21

Sponsor:

SIGHPC

SC '21: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 14 - 19, 2021

Missouri, St. Louis

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
1,216
Total Downloads

Downloads (Last 12 months)347
Downloads (Last 6 weeks)68

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li GZhang HSun XLuo QZhu Y(2024)TenGraph: A Tensor-Based Graph Query EngineProceedings of the VLDB Endowment10.14778/3704965.370496717:13(4571-4584)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.14778/3704965.3704967
Meng LShao YYuan LLai LCheng PLi XYu WZhang WLin XZhou J(2024)A Survey of Distributed Graph Algorithms on Massive GraphsACM Computing Surveys10.1145/3694966Online publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1145/3694966
Chen CShen LChen Y(2024)A Distributed Framework for Subgraph Isomorphism Leveraging CPU and GPU Heterogeneous ComputingProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673134(433-442)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673134
Cai STian BZhang HGao M(2024)PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory HardwareProceedings of the ACM on Management of Data10.1145/36549642:3(1-25)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654964
Zhang ZLu YZheng WLin X(2024)A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and InteractionProceedings of the ACM on Management of Data10.1145/36393152:1(1-29)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639315
Yan DYuan LAhmad AZheng CChen HCheng JBaeza-Yates RBonchi F(2024)Systems for Scalable Graph Analytics and Machine Learning: Trends and MethodsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671472(6627-6632)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671472
Cao HWang QLi XNajafi MChang KCheng R(2024)Large Subgraph Matching: A Comprehensive and Efficient Approach for Heterogeneous Graphs2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00231(2972-2985)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00231
Benachour AYahiaoui SBouhenni SKheddouci HNouali-Taboudjemat N(2024)GPU-accelerated relaxed graph pattern matching algorithmsThe Journal of Supercomputing10.1007/s11227-024-06283-780:15(21811-21836)Online publication date: 16-Jun-2024
https://doi.org/10.1007/s11227-024-06283-7
Bhowmick SBell PTaufer M(2023)A Survey of Graph Comparison Methods with Applications to Nondeterminism in High-Performance ComputingThe International Journal of High Performance Computing Applications10.1177/1094342023116661037:3-4(306-327)Online publication date: 5-Apr-2023
https://doi.org/10.1177/10943420231166610
Xiang LKhan AFerdous SAravind SHalappanavar M(2023)cuAlign: Scalable Network Alignment on GPU AcceleratorsProceedings of the SC '23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis10.1145/3624062.3625129(747-755)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3624062.3625129
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten