A survey on dynamic graph processing on GPUs: concepts, terminologies and systems

Abstract

Graphs that are used to model real-world entities with vertices and relationships among entities with edges, have proven to be a powerful tool for describing real-world problems in applications. In most real-world scenarios, entities and their relationships are subject to constant changes. Graphs that record such changes are called dynamic graphs. In recent years, the widespread application scenarios of dynamic graphs have stimulated extensive research on dynamic graph processing systems that continuously ingest graph updates and produce up-to-date graph analytics results. As the scale of dynamic graphs becomes larger, higher performance requirements are demanded to dynamic graph processing systems. With the massive parallel processing power and high memory bandwidth, GPUs become mainstream vehicles to accelerate dynamic graph processing tasks. GPU-based dynamic graph processing systems mainly address two challenges: maintaining the graph data when updates occur (i.e., graph updating) and producing analytics results in time (i.e., graph computing). In this paper, we survey GPU-based dynamic graph processing systems and review their methods on addressing both graph updating and graph computing. To comprehensively discuss existing dynamic graph processing systems on GPUs, we first introduce the terminologies of dynamic graph processing and then develop a taxonomy to describe the methods employed for graph updating and graph computing. In addition, we discuss the challenges and future research directions of dynamic graph processing on GPUs.

Graphical abstract

Keywords

dynamic graphs / graph processing / graph algorithms / GPUs

References

[1] Shi X, Zheng Z, Zhou Y, Jin H, He L, Liu B, Hua Q S . Graph processing on GPUs: a survey. ACM Computing Surveys, 2018, 50( 6): 81

[2] Li B, Gao S, Liang Y, Kang Y, Prestby T, Gao Y, Xiao R . Estimation of regional economic development indicator from transportation network analytics. Scientific Reports, 2020, 10( 1): 2647

[3] Alkhamees M, Alsaleem S, Al-Qurishi M, Al-Rubaian M, Hussain A . User trustworthiness in online social networks: a systematic review. Applied Soft Computing, 2021, 103: 107159

[4] Karamati S, Young J, Vuduc R. An energy-efficient single-source shortest path algorithm. In: Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium. 2018, 1080−1089

[5] Yang J, McAuley J, Leskovec J. Community detection in networks with node attributes. In: Proceedings of the 13th International Conference on Data Mining. 2013, 1151−1156

[6] Zhong J, He B . Medusa: simplified graph processing on GPUs. IEEE Transactions on Parallel and Distributed Systems, 2014, 25( 6): 1543–1552

[7] Ammar K. Techniques and systems for large dynamic graphs. In: Proceedings of 2016 on SIGMOD’16 PhD Symposium. 2016, 7−11

[8] Brailovskaia J, Margraf J . The relationship between active and passive Facebook use, Facebook flow, depression symptoms and Facebook addiction: a three-month investigation. Journal of Affective Disorders Reports, 2022, 10: 100374

[9] Muin M A, Kapti K, Yusnanto T . Campus website security vulnerability analysis using Nessus. International Journal of Computer and Information System, 2022, 3( 2): 79–82

[10] Gowda S R S, King R, Kumar M R P. Real-time tweets streaming and comparison using naïve Bayes classifier. In: Proceedings of the 3rd International Conference on Data Science, Machine Learning and Applications. 2023, 103−110

[11] Qiu X, Cen W, Qian Z, Peng Y, Zhang Y, Lin X, Zhou J . Real-time constrained cycle detection in large dynamic graphs. Proceedings of the VLDB Endowment, 2018, 11( 12): 1876–1888

[12] Ye C, Li Y, He B, Li Z, Sun J. GPU-accelerated graph label propagation for real-time fraud detection. In: Proceedings of 2021 International Conference on Management of Data. 2021, 2348−2356

[13] Kent A D, Liebrock L M, Neil J C . Authentication graphs: analyzing user behavior within an enterprise network. Computers & Security, 2015, 48: 150–166

[14] Wheatman B, Xu H. Packed compressed sparse row: a dynamic graph representation. In: Proceedings of 2018 IEEE High Performance Extreme Computing Conference. 2018, 1−7

[15] Kumar P, Huang H H . GraphOne: a data store for real-time analytics on evolving graphs. ACM Transactions on Storage, 2019, 15( 4): 29

[16] Zhu X, Feng G, Serafini M, Ma X, Yu J, Xie L, Aboulnaga A, Chen W . LiveGraph: a transactional graph storage system with purely sequential adjacency list scans. Proceedings of the VLDB Endowment, 2020, 13( 7): 1020–1034

[17] De Leo D, Boncz P . Teseo and the analysis of structural dynamic graphs. Proceedings of the VLDB Endowment, 2021, 14( 6): 1053–1066

[18] Cheng R, Hong J, Kyrola A, Miao Y, Weng X, Wu M, Yang F, Zhou L, Zhao F, Chen E. Kineograph: taking the pulse of a fast-changing and connected world. In: Proceedings of the 7th ACM European Conference on Computer Systems. 2012, 85−98

[19] Shi X, Cui B, Shao Y, Tong Y. Tornado: a system for real-time iterative analysis over evolving data. In: Proceedings of 2016 International Conference on Management of Data. 2016, 417−430

[20] Vora K, Gupta R, Xu G. KickStarter: fast and accurate computations on streaming graphs via trimmed approximations. In: Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems. 2017, 237−251

[21] Sheng F, Cao Q, Cai H, Yao J, Xie C. GraPU: accelerate streaming graph analysis through preprocessing buffered updates. In: Proceedings of the ACM Symposium on Cloud Computing. 2018, 301−312

[22] Mariappan M, Vora K. GraphBolt: dependency-driven synchronous processing of streaming graphs. In: Proceedings of the 14th EuroSys Conference 2019. 2019, 25

[23] Shi X, Luo X, Liang J, Zhao P, Di S, He B, Jin H . Frog: asynchronous graph processing on GPU with hybrid coloring model. IEEE Transactions on Knowledge and Data Engineering, 2018, 30( 1): 29–42

[24] Sengupta D, Sundaram N, Zhu X, Willke T L, Young J, Wolf M, Schwan K. GraphIn: an online high performance incremental graph processing framework. In: Proceedings of the 22nd International Conference on Parallel and Distributed Computing. 2016, 319−333

[25] Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms. 3rd ed. Cambridge: MIT Press, 2009

[26] Shao Z, Li R, Hu D, Liao X, Jin H. Improving performance of graph processing on FPGA-DRAM platform by two-level vertex caching. In: Proceedings of 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 2019, 320−329

[27] Goodrich M T, Tamassia R. Algorithm Design and Applications. Hoboken: Wiley Hoboken, 2015

[28] Green O, Yalamanchili P, Munguía L M. Fast triangle counting on the GPU. In: Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms. 2014, 1−8

[29] Park S, Lee W, Choe B, Lee S G . A survey on personalized PageRank computation algorithms. IEEE Access, 2019, 7: 163049–163062

[30] Boldi P, Santini M, Vigna S. PageRank as a function of the damping factor. In: Proceedings of the 14th International Conference on World Wide Web. 2005, 557−566

[31] Ohsaka N, Maehara T, Kawarabayashi K I. Efficient PageRank tracking in evolving networks. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 875−884

[32] Brin S, Page L . The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 1998, 30( 1-7): 107–117

[33] Kamvar S D, Haveliwala T H, Manning C D, Golub G H. Extrapolation methods for accelerating PageRank computations. In: Proceedings of the 12th International Conference on World Wide Web. 2003, 261−270

[34] Hou G, Chen X, Wang S, Wei Z . Massively parallel algorithms for personalized PageRank. Proceedings of the VLDB Endowment, 2021, 14( 9): 1668–1680

[35] Mandal A, Al Hasan M. A distributed k-core decomposition algorithm on spark. In: Proceedings of 2017 IEEE International Conference on Big Data. 2017, 976−981

[36] Victor F, Akcora C G, Gel Y R, Kantarcioglu M. Alphacore: data depth based core decomposition. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021, 1625−1633

[37] Esfandiari H, Lattanzi S, Mirrokni V S. Parallel and streaming algorithms for K-core decomposition. In: Proceedings of the 35th International Conference on Machine Learning. 2018, 1396−1405

[38] Alvarez-Hamelin J I, Dall’Asta L, Barrat A, Vespignani A. Large scale networks fingerprinting and visualization using the k-core decomposition. In: Proceedings of the 18th International Conference on Neural Information Processing Systems. 2005, 41−50

[39] Zeng L, Zou L, Özsu M T, Hu L, Zhang F. GSI: GPU-friendly subgraph isomorphism. In: Proceedings of the 36th International Conference on Data Engineering. 2020, 1249−1260

[40] Zaki A, Attia M, Hegazy D, Amin S . Comprehensive survey on dynamic graph models. International Journal of Advanced Computer Science and Applications, 2016, 7( 2): 573–582

[41] Li D, Li W, Chen Y, Lin M, Lu S. Learning-based dynamic graph stream sketch. In: Proceedings of the 25th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. 2021, 383−394

[42] Margan D, Pietzuch P. Large-scale stream graph processing: doctoral symposium. In: Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems. 2017, 378−381

[43] Harary F, Gupta G . Dynamic graph models. Mathematical and Computer Modelling, 1997, 25( 7): 79–87

[44] Sengupta D, Song S L. EvoGraph: on-the-fly efficient mining of evolving graphs on GPU. In: Proceedings of the 32nd International Conference on High Performance Computing. 2017, 97−119

[45] Iyer A P, Pu Q, Patel K, Gonzalez J E, Stoica I. TEGRA: efficient Ad-Hoc analytics on evolving graphs. In: Proceedings of the 18th USENIX Symposium on Networked Systems Design and Implementation. 2021, 337−355

[46] Aggarwal C, Subbian K . Evolutionary network analysis: a survey. ACM Computing Surveys, 2014, 47( 1): 10

[47] Van Vlasselaer V, Akoglu L, Eliassi-Rad T, Snoeck M, Baesens B. Guilt-by-constellation: fraud detection by suspicious clique memberships. In: Proceedings of the 48th Hawaii International Conference on System Sciences. 2015, 918−927

[48] Xu S, Liao X, Shao Z, Hua Q, Jin H . Maximal clique enumeration problem on graphs: status and challenges. SCIENTIA SINICA Informationis, 2022, 52( 5): 784–803

[49] McGregor A . Graph stream algorithms: a survey. ACM SIGMOD Record, 2014, 43( 1): 9–20

[50] Vora K, Gupta R, Xu G . Synergistic analysis of evolving graphs. ACM Transactions on Architecture and Code Optimization, 2016, 13( 4): 32

[51] Sheng F, Cao Q, Yao J . Exploiting buffered updates for fast streaming graph analysis. IEEE Transactions on Computers, 2021, 70( 2): 255–269

[52] Zhang J. A survey on streaming algorithms for massive graphs. In: Aggarwal C C, Wang H X, eds. Managing and Mining Graph Data. New York: Springer, 2010, 393−420

[53] Bar-Yossef Z, Kumar R, Sivakumar D. Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 2002, 623−632

[54] Zhao P, Aggarwal C C, Wang M . gSketch: on query estimation in graph streams. Proceedings of the VLDB Endowment, 2011, 5( 3): 193–204

[55] Zhang H, Lofgren P, Goel A. Approximate personalized PageRank on dynamic graphs. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016, 1315−1324

[56] Shin K, Oh S, Kim J, Hooi B, Faloutsos C . Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data, 2020, 14( 2): 12

[57] Basak A, Lin J, Lorica R, Xie X, Chishti Z, Alameldeen A, Xie Y. SAGA-bench: software and hardware characterization of streaming graph analytics workloads. In: Proceedings of 2020 IEEE International Symposium on Performance Analysis of Systems and Software. 2020, 12−23

[58] Ren C, Lo E, Kao B, Zhu X, Cheng R . On querying historical evolving graph sequences. Proceedings of the VLDB Endowment, 2011, 4( 11): 726–737

[59] Khurana U, Deshpande A. Efficient snapshot retrieval over historical graph data. In: Proceedings of the 29th International Conference on Data Engineering. 2013, 997−1008

[60] Han W, Miao Y, Li K, Wu M, Yang F, Zhou L, Prabhakaran V, Chen W, Chen E. Chronos: a graph engine for temporal graph analysis. In: Proceedings of the 9th European Conference on Computer Systems. 2014, 1

[61] Steer B, Cuadrado F, Clegg R . Raphtory: streaming analysis of distributed temporal graphs. Future Generation Computer Systems, 2020, 102: 453–464

[62] Rossetti G, Cazabet R . Community discovery in dynamic networks: a survey. ACM Computing Surveys, 2019, 51( 2): 35

[63] Holme P . Modern temporal network theory: a colloquium. The European Physical Journal B, 2015, 88( 9): 234

[64] Holme P, Saramäki J . Temporal networks. Physics Reports, 2012, 519( 3): 97–125

[65] Sha M, Li Y, He B, Tan K L . Accelerating dynamic graph analytics on GPUs. Proceedings of the VLDB Endowment, 2017, 11( 1): 107–120

[66] Mariappan M, Che J, Vora K. DZiG: sparsity-aware incremental processing of streaming graphs. In: Proceedings of the 16th European Conference on Computer Systems. 2021, 83−98

[67] King J, Gilray T, Kirby R M, Might M. Dynamic sparse-matrix allocation on GPUs. In: Proceedings of the 31st International Conference on High Performance Computing. 2016, 61−80

[68] Winter M, Zayer R, Steinberger M. Autonomous, independent management of dynamic graphs on GPUs. In: Proceedings of 2017 IEEE High Performance Extreme Computing Conference. 2017, 1−7

[69] Green O, Bader D A. cuSTINGER: supporting dynamic graph algorithms for GPUs. In: Proceedings of 2016 IEEE High Performance Extreme Computing Conference. 2016, 1−6

[70] Winter M, Mlakar D, Zayer R, Seidel H P, Steinberger M. faimGraph: high performance management of fully-dynamic graphs under tight memory constraints on the GPU. In: Proceedings of the SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. 2018, 754−766

[71] Awad M A, Ashkiani S, Porumbescu S D, Owens J D. Dynamic graphs on the GPU. In: Proceedings of 2020 IEEE International Parallel and Distributed Processing Symposium. 2020, 739−748

[72] Busato F, Green O, Bombieri N, Bader D A. Hornet: an efficient data structure for dynamic sparse graphs and matrices on GPUs. In: Proceedings of 2018 IEEE High Performance extreme Computing Conference. 2018, 1−7

[73] Ediger D, McColl R, Riedy J, Bader D A. STINGER: high performance data structure for streaming graphs. In: Proceedings of 2012 IEEE Conference on High Performance Extreme Computing. 2012, 1−5

[74] Makkar D, Bader D A, Green O. Exact and parallel triangle counting in dynamic graphs. In: Proceedings of the 24th International Conference on High Performance Computing. 2017, 2−12

[75] Guo W, Li Y, Sha M, Tan K L . Parallel personalized PageRank on dynamic graphs. Proceedings of the VLDB Endowment, 2017, 11( 1): 93–106

[76] Jaiyeoba W, Skadron K. GraphTinker: a high performance data structure for dynamic graph processing. In: Proceedings of 2019 IEEE International Parallel and Distributed Processing Symposium. 2019, 1030−1041

[77] Ashkiani S, Li S, Farach-Colton M, Amenta N, Owens J D. GPU LSM: a dynamic dictionary data structure for the GPU. In: Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium. 2018, 430−440

[78] Zhang F, Zou L, Yu Y. LPMA - an efficient data structure for dynamic graph on GPUs. In: Proceedings of the 22nd International Conference on Web Information Systems Engineering 2021. 2021, 469−484

[79] Ediger D, Riedy J, Bader D A, Meyerhenke H. Computational graph analytics for massive streaming data. In: Sarbazi-Azad H, Zomaya A Y, eds. Large Scale Network-Centric Distributed Systems. Hoboken: John Wiley & Sons, Inc., 2013, 619−648

[80] Bender M A, Hu H . An adaptive packed-memory array. ACM Transactions on Database Systems, 2007, 32( 4): 26–es

[81] Ashkiani S, Farach-Colton M, Owens J D. A dynamic hash table for the GPU. In: Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium. 2018, 419−429

[82] Zhang T. Efficient incremental PageRank of evolving graphs on GPU. In: Proceedings of 2017 International Conference on Computer Systems, Electronics and Control. 2017, 1232−1236

[83] Tripathy A, Hohman F, Chau D H, Green O. Scalable K-core decomposition for static graphs using a dynamic graph data structure. In: Proceedings of 2018 IEEE International Conference on Big Data. 2018, 1134−1141

[84] Tödling D, Winter M, Steinberger M. Breadth-first search on dynamic graphs using dynamic parallelism on the GPU. In: Proceedings of 2019 IEEE High Performance Extreme Computing Conference. 2019, 1−7

[85] Giri H K, Haque M, Banerjee D S. HyPR: hybrid page ranking on evolving graphs. In: Proceedings of the 27th International Conference on High Performance Computing, Data, and Analytics. 2020, 62−71

[86] Khanda A, Srinivasan S, Bhowmick S, Norris B, Das S K . A parallel algorithm template for updating single-source shortest paths in large-scale dynamic networks. IEEE Transactions on Parallel and Distributed Systems, 2022, 33( 4): 929–940

[87] Zhang T, Zhang J, Shu W, Wu M Y, Liang X . Efficient graph computation on hybrid CPU and GPU systems. The Journal of Supercomputing, 2015, 71( 4): 1563–1586

[88] Desikan P, Pathak N, Srivastava J, Kumar V. Incremental page rank computation on evolving graphs. In: Proceedings of the Special Interest Tracks and Posters of the 14th International Conference on World Wide Web. 2005, 1094−1095

[89] Ediger D, Jiang K, Riedy J, Bader D A. Massive streaming data analytics: a case study with clustering coefficients. In: Proceedings of 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum. 2010, 1−8

[90] Hanauer K, Henzinger M, Schulz C. Recent advances in fully dynamic graph algorithms. In: Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks. 2022, 1.11

[91] Fournier-Viger P, He G, Cheng C, Li J, Zhou M, Lin J C W, Yun U . A survey of pattern mining in dynamic graphs. WIREs Data Mining and Knowledge Discovery, 2020, 10( 6): e1372

[92] O’Connell T C. A survey of graph algorithms under extended streaming models of computation. In: Ravi S S, Shukla S K, eds. Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz. Dordrecht: Springer, 2009, 455−476

[93] Skarding J, Gabrys B, Musial K . Foundations and modeling of dynamic networks using dynamic graph neural networks: a survey. IEEE Access, 2021, 9: 79143–79168

[94] Kazemi S M, Goel R, Jain K, Kobyzev I, Sethi A, Forsyth P, Poupart P . Representation learning for dynamic graphs: a survey. The Journal of Machine Learning Research, 2020, 21( 1): 70

[95] Besta M, Fischer M, Kalavri V, Kapralov M, Hoefler T . Practice of streaming processing of dynamic graphs: concepts, models, and systems. IEEE Transactions on Parallel and Distributed Systems, 2021,

[96] Ren Z, Gu Y, Li C, Li F, Yu G . GPU-based dynamic hyperspace hash with full concurrency. Data Science and Engineering, 2021, 6( 3): 265–279

[97] Green O . HashGraph-scalable hash tables using a sparse graph data structure. ACM Transactions on Parallel Computing, 2021, 8( 2): 11

[98] Awad M A, Ashkiani S, Johnson R, Farach-Colton M, Owens J D. Engineering a high-performance GPU B-tree. In: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. 2019, 145−157

[99] Yan Z, Lin Y, Peng L, Zhang W. Harmonia: a high throughput B+tree for GPUs. In: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. 2019, 133−144

[100] Zhang Y, Liang Y, Zhao J, Mao F, Gu L, Liao X, Jin H, Liu H, Guo S, Zeng Y, Hu H, Li C, Zhang J, Wang B . EGraph: efficient concurrent GPU-based dynamic graph processing. IEEE Transactions on Knowledge and Data Engineering, 2022,

RIGHTS & PERMISSIONS

Higher Education Press