Review of Key Technologies in Graph Processing Architectures and Systems Software

Zhang Yu; Jiang Xinyu; Yu Hui; Zhao Jin; Qi Hao; Liao Xiaofei; Jin Hai; Wang Biao; Yu Ting

doi:10.7544/issn1000-1239.202220778

Journal of Computer Research and Development > 2024 > 61(1): 20-42. > DOI: 10.7544/issn1000-1239.202220778

Zhang Yu, Jiang Xinyu, Yu Hui, Zhao Jin, Qi Hao, Liao Xiaofei, Jin Hai, Wang Biao, Yu Ting. Review of Key Technologies in Graph Processing Architectures and Systems Software[J]. Journal of Computer Research and Development, 2024, 61(1): 20-42. DOI: 10.7544/issn1000-1239.202220778

Citation:

PDF (1854 KB)

Review of Key Technologies in Graph Processing Architectures and Systems Software

Zhang Yu^{1, 2, 3, 4,},
Jiang Xinyu^{1, 2, 3, 4},
Yu Hui^{1, 2, 3, 4},
Zhao Jin^{1, 2, 3, 4, ,},
Qi Hao^{1, 2, 3, 4},
Liao Xiaofei^{1, 2, 3, 4},
Jin Hai^{1, 2, 3, 4},
Wang Biao⁵,
Yu Ting⁵

1.
National Engineering Research Center for Big Data Technology and System (Huazhong University of Science and Technology), Wuhan 430074
2.
Services Computing Technology and System Lab (Huazhong University of Science and Technology), Ministry of Education, Wuhan 430074
3.
Cluster and Grid Computing Lab (Huazhong University of Science and Technology), Wuhan 430074
4.
School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074
5.
Zhejiang Lab, Hangzhou 311121

Funds: This work was supported by the National Key Research and Development Program of China (2022YFB2404202), the National Natural Science Foundation of China (62072193), the Open Research Projects of Zhejiang Lab (2021KD0AB01), and the Major Scientific Research Project of Zhejiang Lab (2022PI0AC03).

More Information

Author Bio:
Zhang Yu: born in 1987. PhD, associate professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, system software, and high-performance graph processing

Jiang Xinyu: born in 1998. Master. His main research interests include graph processing and graph neural network

Yu Hui: born in 1993. PhD candidate. His main research interests include graph processing and graph neural network

Zhao Jin: born in 1996. PhD. His main research interests include graph processing system and accelerator design

Qi Hao: born in 1996. PhD. His main research interests include graph processing, graph neural network system design

Liao Xiaofei: born in 1978. PhD, professor, PhD supervisor. Distinguished member of CCF, member of ACM and IEEE. His main research interests include system software, P2P system, cluster computing, and streaming services

Jin Hai: born in 1966. PhD, professor, PhD supervisor. CCF fellow, IEEE fellow, life member of ACM. His main research interests include computer architecture and virtualization

Wang Biao: born in 1990. PhD. His main research interests include large-scale graph data mining and anomaly detection

Yu Ting: born in 1989. PhD. Her main research interests include graph mining algorithms and parallel graph computing
Received Date: August 31, 2022
Revised Date: June 12, 2023
Available Online: September 19, 2023

Graphical Abstract

Abstract

Abstract

In recent years, some progress has been made in the key technologies of the architecture and systems software for graph processing. Large-scale graph processing has also been widely used in many fields, including scientific computing, machine learning, social networks, intelligent transportation, bioinformatics, etc. However, most real-world graph computations have characteristics such as dynamic changes and complex and diverse application requirements. This poses new demands and challenges for graph processing in terms of basic theory, architecture, and key technologies of systems software. To address these challenges, researchers have proposed a series of graph processing systems and accelerators, which optimize the graph processing process through technologies such as high-performance computing and parallel computing. Furthermore, in order to meet the demands of practical application scenarios, various graph processing frameworks and algorithms are constantly being innovated and optimized, thus enhancing the practical value of graph processing in terms of processing large-scale graph data and improving computational efficiency. We review the research and development status of key technologies in graph processing architecture and systems software, and summarize, compare, analyze the latest progress of research at home and abroad, and select fields closely related to national economy and people’s livelihood in combination with national development strategies and major application requirements. The industry progress of graph processing-related technologies is analyzed and summarized from typical applications. Finally, the future technical challenges and research directions are prospected.
- graph processing,
- architecture,
- systems software,
- graph traversal,
- graph mining,
- graph neural network,
- single machine system,
- distributed system,
- accelerator,
- industry applications

FullText(HTML)

References (156)

References

[1]	Cheng R, Hong Ji, Kyrola A, et al. Kineograph: Taking the pulse of a fast-changing and connected world[C]//Proc of the 7th ACM European Conf on Computer Systems. New York: ACM, 2012: 85−98
[2]	赵进,姜新宇,张宇,等. 一种高效的面向高并发图分析任务的存储系统[J]. 中国科学:信息科学,2022,52(1):111−128 Zhao Jin, Jiang Xinyu, Zhang Yu, et al. An efficient storage system for high concurrency graph analysis tasks[J]. SCIENTIA SINCIA Informationis, 2022, 52(1): 111−128 (in Chinese)
[3]	Qiu Xiafei, Cen Wubin, Qian Zhengping, et al. Real-time constrained cycle detection in large dynamic graphs[J]. Proceedings of the VLDB Endowment, 2018, 11(12): 1876−1888 doi: 10.14778/3229863.3229874
[4]	廖小飞,陈意诚,张宇,等. 一种高效的面向动态有向图的增量强连通分量算法[J]. 中国科学:信息科学,2019,49(8):988−1004 doi: 10.1360/N112018-00125 Liao Xiaofei, Chen Yicheng, Zhang Yu, et al. An efficient incremental strongly connected component algorithm for dynamic directed graphs[J]. SCIENTIA SINCIA Informationis, 2019, 49(8): 988−1004 (in Chinese) doi: 10.1360/N112018-00125
[5]	Eswaran D, Faloutsos C, Guha S, et al. Spotlight: Detecting anomalies in streaming graphs[C]//Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 1378−1386
[6]	Eksombatchai C, Jindal P, Liu J, et al. Pixie: A system for recommending 3+ billion items to 200+ million users in real-time[C]//Proc of the 17th World Wide Web Conf. New York: ACM, 2018: 1775−1784
[7]	Faust K. A puzzle concerning triads in social networks: Graph constraints and the triad census[J]. Social Networks, 2010, 32(3): 221−233 doi: 10.1016/j.socnet.2010.03.004
[8]	Granovetter M. The strength of weak ties: A network theory revisited[J]. Sociological Theory, 1983, 2(1): 201−233
[9]	Zhao Jin, Zhang Yu, He Ligang, et al. GraphTune: An efficient dependency-aware substrate to alleviate irregularity in concurrent graph processing[J]. ACM Transactions on Architecture and Code Optimization, 2023, 20(3): 37:1−37:24
[10]	Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs: Simple building blocks of complex networks[J]. Science, 2002, 298(5594): 824−827 doi: 10.1126/science.298.5594.824
[11]	Alon N, Dao P, Hajirasouliha I, et al. Biomolecular network motif counting and discovery by color coding[J]. Bioinformatics, 2008, 24(13): i241−i249 doi: 10.1093/bioinformatics/btn163
[12]	Cho Y R, Zhang Aidong. Predicting protein function by frequent functional association pattern mining in protein interaction networks[J]. IEEE Transactions on Information Technology in Biomedicine, 2009, 14(1): 30−36
[13]	Milenković T, Ng W L, Hayes W, et al. Optimal network alignment with graphlet degree vectors[J]. Cancer Informatics, 2010, 9(9): 121−137
[14]	Milenković T, Pržulj N. Uncovering biological network function via graphlet degree signatures[J]. Cancer Informatics, 2008, 6: 257−273
[15]	Deshpande M, Kuramochi M, Wale N, et al. Frequent substructure-based approaches for classifying chemical compounds[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(8): 1036−1050 doi: 10.1109/TKDE.2005.127
[16]	Gaüzere B, Brun L, Villemin D. Two new graphs kernels in chemoinformatics[J]. Pattern Recognition Letters, 2012, 33(15): 2038−2047 doi: 10.1016/j.patrec.2012.03.020
[17]	Kashima H, Saigo H, Hattori M, et al. Graph kernels for chemoinformatics[M/OL]//Chemoinformatics and Advanced Machine Learning Perspectives: Complex Computational Methods and Collaborative techniques. 2011[2022-06-14].https://doi.org/10.48550/arXiv.2208.04929
[18]	Chen Hanhua, Jin Hhai, Cui Xiaolong. Hybrid followee recommendation in microblogging systems[J]. Science China Information Sciences, 2017, 60(1): 1−14
[19]	LeCun Y, Bengio Y. Convolutional networks for images, speech, and time series[G]//LNCS 3361: The Handbook of Brain Theory and Neural Networks. Berlin: Springer, 1998: 255−258
[20]	Grnarova P, Levy K Y, Lucchi A, et al. A domain agnostic measure for monitoring and evaluating GANs[J]. Advances in Neural Information Processing Systems, 2019, 3(24): 32−44
[21]	Wu Zonghan, Pan Shirui, Chen Fengwen, et al. A comprehensive survey on graph neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 32(1): 4−24
[22]	Sperduti A, Starita A. Supervised neural networks for the classification of structures[J]. IEEE Transactions on Neural Networks, 1997, 8(3): 714−735 doi: 10.1109/72.572108
[23]	Welling M, Kipf T N. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint, arXiv: 1609. 02907, 2016
[24]	Fout A, Byrd J, Shariat B, et al. Protein interface prediction using graph convolutional networks[J]. Advances in Neural Information Processing Systems, 2017, 2(8): 12−30
[25]	Ying R, He Ruining, Chen Kaifeng, et al. Graph convolutional neural networks for web-scale recommender systems[C]//Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2018: 974−983
[26]	Ying Z, You Jiaxuan, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[J/OL]. Advances in Neural Information Processing Systems, 2018, 19−31.[2022-10-03].https://proceedings.neurips.cc/paper/2018/hash/e77dbaf6759253c7c6d0efc5690369c7-Abstract.html
[27]	Dai Hanjun, Kozareva Z, Dai Bo, et al. Learning steady-states of iterative algorithms over graphs[C/OL]//Proc of the 35th Int Conf on Machine Learning. 2018: 1106−1114. [2022-07-03].https://proceedings.mlr.press/v80/dai18a.html
[28]	Ediger D, McColl R, Riedy J, et al. STINGER: High performance data structure for streaming graphs[C/OL]// Proc of the 9th IEEE Conf on High Performance Extreme Computing. Piscataway, NJ: IEEE, 2012[2022-10-14]. https://doi.org/10.1109/HPEC.2012.6408680
[29]	Winter M, Zayer R, Steinberger M. Autonomous, independent management of dynamic graphs on GPUs[C/OL]// Proc of the 14th IEEE High Performance Extreme Computing Conf. Piscataway, NJ: IEEE, 2017[2022-10-14].https://doi.org/10.1109/HPEC.2017.8091058
[30]	Awad M A, Ashkiani S, Porumbescu S D, et al. Dynamic graphs on the GPU[C]// Proc of the 17th IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2020: 739−748
[31]	Ashkiani S, Farach-Colton M, Owens J D. A dynamic Hash table for the GPU[C]// Proc of the 15th IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2018: 419−429
[32]	Bender M A, Hu Haodong. An adaptive packed-memory array[J]. ACM Transactions on Database Systems, 2007, 32(4): 26−37 doi: 10.1145/1292609.1292616
[33]	Wheatman B, Xu H. Packed compressed sparse row: A dynamic graph representation[C/OL]// Proc of the 2018 IEEE High Performance Extreme Computing Conf. Piscataway, NJ: IEEE, 2018[2022-07-14].https://doi.org/10.1109/HPEC.2018.8547566
[34]	Wheatman B, Xu H. A parallel packed memory array to store dynamic graphs[C/OL]// Proc of the 2021 Workshop on Algorithm Engineering and Experiments. 2021: 31−45. [2022-08-07].https://people.csail.mit.edu/hjxu/papers/ppcsr-alenex.pdf
[35]	Sha Mo, Li Yuchen, He Bingsheng, et al. Technical report: Accelerating dynamic graph analytics on GPUs[J]. arXiv preprint, arXiv: 1709.05061, 2017
[36]	Macko P, Marathe V J, Margo D W, et al. LLAMA: Efficient graph analytics using large multiversioned arrays[C]// Proc of the 31st IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 363−374
[37]	Dhulipala L, Blelloch G E, Shun J. Low-latency graph streaming using compressed purely-functional trees[C]//Proc of the 40th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2019: 918−934
[38]	Iyer A P, Pu Qifan, Patel K, et al. TEGRA: Efficient ad-hoc analytics on evolving graphs[C]// Proc of the 18th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 337−355
[39]	De Leo D, Boncz P. Teseo and the analysis of structural dynamic graphs[J]. Proceedings of the VLDB Endowment, 2021, 14(6): 1053−1066 doi: 10.14778/3447689.3447708
[40]	Iyer A P, Pu Qifan, Patel K, et al. TEGRA: Efficient ad-hoc analytics on evolving graphs [C]//Proc of the 18th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 337−355
[41]	Dave A, Gonzalez J E, Franklin M J, et al. Persistent adaptive radix trees: Efficient fine-grained updates to immutable data[J/OL]. 2013, 12: 1−15. [2022-04-25].https://ankurdave.com/dl/part-tr.pdf
[42]	Leis V, Kemper A, Neumann T. The adaptive radix tree: ARTful indexing for main-memory databases[C]// Proc of the 29th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 38−49
[43]	Sengupta D, Sundaram N, Zhu Xia, et al. GraphIn: An online high performance incremental graph processing framework[C]// Proc of the European Conf on Parallel Processing. New York: ACM, 2016: 319−333
[44]	Kumar P, Howie H. GraphOne: A data store for real-time analytics on evolving graphs[J]. ACM Transactions on Storage, 2020, 15(4): 1−40
[45]	Iwabuchi K, Sallinen S, Pearce R, et al. Towards a distributed large-scale dynamic graph data store[C]// Proc of the 17th IEEE Int Parallel and Distributed Processing Symp Workshops. Piscataway, NJ: IEEE, 2016: 892−901
[46]	Pandey P, Wheatman B, Xu H, et al. Terrace: A hierarchical graph container for skewed dynamic graphs[C]//Proc of the 2021 Int Conf on Management of Data. New York: ACM, 2021: 1372−1385
[47]	Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal[J]. ACM SIGPLAN Notices, 2012, 47(8): 117−128 doi: 10.1145/2370036.2145832
[48]	Wang Yangzihao, Davidson A, Pan Yuechao, et al. Gunrock: A high-performance graph processing library on the GPU[C/OL]//Proc of the 21st ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2016[2022-02-17].https://doi.org/10.1145/3016078.2851145
[49]	Han Wei, Mawhirter D, Wu Bo, et al. Graphie: Large-scale asynchronous graph traversals on just a GPU[C]// Proc of The 26th Int Conf on Parallel Architectures and Compilation Techniques. Piscataway, NJ: IEEE, 2017: 233−245
[50]	Ben-Nun T, Sutton M, Pai S, et al. Groute: An asynchronous multi-GPU programming model for irregular computations[J]. ACM SIGPLAN Notices, 2017, 52(8): 235−248 doi: 10.1145/3155284.3018756
[51]	Sabet A H N, Qiu Junqiao, Zhao Zhijia. Tigr: Transforming irregular graphs for GPU-friendly graph processing[J]. ACM SIGPLAN Notices, 2018, 53(2): 622−636 doi: 10.1145/3296957.3173180
[52]	Sabet A H N, Zhao Zhijia, Gupta R. Subway: Minimizing data transfer during out-of-GPU-memory graph processing[C/OL]//Proc of the 15th European Conf on Computer Systems. New York: ACM, 2020[2022-07-13].https://doi.org/10.1145/3342195.3387537
[53]	DeLorimier M, Kapre N, Mehta N, et al. GraphStep: A system architecture for sparse-graph algorithms[C]//Proc of the 14th Annual IEEE Symp on Field-Programmable Custom Computing Machines. Piscataway, NJ: IEEE, 2006: 143−151
[54]	Attia O G, Johnson T , Townsend K , et al. CyGraph: A reconfigurable architecture for parallel breadth-First search[C/OL]//Proc of the 14th Parallel & Distributed Processing Symp Workshops. Piscataway, NJ: IEEE, 2014[2022-06-14].https://doi.org/10.1109/IPDPSW.2014.30
[55]	Zhou Shijie, Kannan R, Prasanna V K, et al. HitGraph: High-throughput graph processing framework on FPGA[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(10): 2249−2264 doi: 10.1109/TPDS.2019.2910068
[56]	Ham T J, Wu Lisa, Sundaram N, et al. Graphicionado: A high-performance and energy-efficient accelerator for graph analytics[C/OL]//Proc of the 49th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2016[2022-07-18].https://doi.org/10.1109/MICRO.2016.7783759
[57]	Ozdal M M, Yesil S, Kim T, et al. Energy efficient architecture for graph analytics accelerators[J]. ACM SIGARCH Computer Architecture News, 2016, 44(3): 166−177 doi: 10.1145/3007787.3001155
[58]	Kalinsky O, Kimelfeld B, Etsion Y. The TrieJax architecture: Accelerating graph operations through relational joins[C]//Proc of the 25th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2020: 1217−1231
[59]	Chen Xuhao, Huang Tianhao, Xu Shuotao, et al. FlexMiner: A pattern-aware accelerator for graph pattern mining[C]// Proc of the 48th Annual Int Symp on Computer Architecture. New York: ACM, 2021: 581−594
[60]	Rao Gengyu, Chen Jingji, Yik J, et al. SparseCore: Stream ISA and processor specialization for sparse computation[C]//Proc of the 27th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2022: 186−199
[61]	Besta M, Kanakagiri R, Kwasniewski G, et al. Sisa: Set-centric instruction set architecture for graph mining on processing-in-memory systems[C]// Proc of the 54th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2021: 282−297
[62]	Talati N, Ye Haojie, Yang Yichen, et al. NDMiner: Accelerating graph pattern mining using near data processing[C]//Proc of the 49th Annual Int Symp on Computer Architecture. New York: ACM, 2022: 146−159
[63]	Zeng Hanqing, Prasanna V. GraphACT: Accelerating GCN training on CPU-FPGA heterogeneous platforms[C]//Proc of the 28th ACM/SIGDA Int Symp on Field-Programmable Gate Arrays. New York: ACM, 2020: 255–265
[64]	Geng Tong, Li Ang, Shi Runbin, et al. AWB-GCN: A graph convolutional network accelerator with runtime workload rebalancing[C]//Proc of the 53rd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2020: 922−936
[65]	Li Jiajun, Louri A, Karanth A, et al. GCNAX: A flexible and energy-efficient accelerator for graph convolutional neural networks[C]//Proc of the 27th IEEE Int Symp on High-Performance Computer Architecture. Piscataway, NJ: IEEE, 2021: 775−788
[66]	Geng Tong, Wu Chunshu, Zhang Yongan, et al. I-GCN: A graph convolutional network accelerator with runtime locality enhancement through islandization[C]// Proc of the 54th Annual IEEE/ACM Int Symp on Microarchitecture. Piscataway, NJ: IEEE, 2021: 1051−1063
[67]	You Haoran, Geng Tong, Zhang Yongan, et al. GCoD: Graph convolutional network acceleration via dedicated algorithm and accelerator co-design[C]// Proc of the 28th IEEE Int Symp on High-Performance Computer Architecture. Piscataway, NJ: IEEE, 2021, 460−474
[68]	Auten A, Tomei M, Kumar R. Hardware acceleration of graph neural networks[C/OL]//Proc of the 57th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2020[2022-05-13].https://doi.org/10.48550/arXiv.2209.02916
[69]	Zhang Bingyi, Kannan R, Prasanna V. BoostGCN: A framework for optimizing GCN inference on FPGA[C]// Proc of the 29th IEEE Annual Int Symp on Field-Programmable Custom Computing Machines. Piscataway, NJ: IEEE, 2021: 29−39
[70]	Kang M, Hwang R, Lee J, et al. GROW: A row-stationary sparse-dense GEMM accelerator for memory-efficient graph convolutional neural networks[J]. arXiv preprint, arXiv: 2203.00158, 2022
[71]	Rahman S, Afarin M, Abu-Ghazaleh N, et al. JetStream: Graph analytics on streaming data with event-driven hardware accelerator[C]// Proc of the 54th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2021: 1091−1105
[72]	Sundaram N, Satish N R, Patwary M M A, et al. GraphMat: High performance graph analytics made productive[J]. arXiv preprint, arXiv: 1503.07241, 2015
[73]	Shun Julian, Blelloch G E. Ligra: A lightweight graph processing framework for shared memory[C]//Proc of the 18th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2013: 135−146
[74]	Nguyen D, Lenharth A, Pingali K. A lightweight infrastructure for graph analytics[C]//Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 456−471
[75]	Wang Guozhang, Xie Wenlei, Demers A, et al. Asynchronous large-Scale graph processing made easy[C/OL]//Proc of the 6th Biennial Conf on Innovative Data Systems Research. 2013[2022-08-12].https://doi.org/10.1002/spe.2979
[76]	Perez Y, Sosič R, Banerjee A, et al. Ringo: Interactive graph analytics on big-memory machines[C]//Proc of the 2015 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 1105−1110
[77]	Kyrola A, Blelloch G, Guestrin C. GraphChi: Large-scale graph computation on just a PC[C]//Proc of the 10th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 31−46
[78]	Roy A, Mihailovic I, Zwaenepoel W. X-Stream: Edge-centric graph processing using streaming partitions[C]//Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 472−488
[79]	Maass S, Min C, Kashyap S, et al. Mosaic: Processing a trillion-edge graph on a single machine[C]//Proc of the 12th European Conf on Computer Systems. New York: ACM, 2017: 527−543
[80]	Jun S W, Wright A, Zhang S, et al. GraFBoost: Using accelerated flash storage for external graph analytics[C]//Proc of the 45th Annual Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 2018: 411−424
[81]	Vora K. LUMOS: Dependency-driven disk-based graph processing[C]// Proc of the 24th USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2019: 429−442
[82]	Malewicz G, Austern M H, Bik A J C, et al. Pregel: A system for large-scale graph processing[C]//Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 135−146
[83]	Low Y, Gonzalez J E, Kyrola A, et al. Graphlab: A new framework for parallel machine learning[J]. arXiv preprint, arXiv: 1408.2041, 2014
[84]	Gonzalez J E, Low Y, Gu Haijie, et al. PowerGraph: Distributed graph-parallel computation on natural graphs[C]//Proc of the 10th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 17−30
[85]	Roy A, Bindschaedler L, Malicevic J, et al. Chaos: Scale-out graph processing from secondary storage[C]//Proc of the 25th Symp on Operating Systems Principles. New York: ACM, 2015: 410−424
[86]	Yu Jiping, Qin Wei, Zhu Xiaowei, et al. DFOGraph: An I/O-and communication-efficient system for distributed fully-out-of-core graph processing[C]//Proc of the 26th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2021: 474−476
[87]	Teixeira C H C, Fonseca A J, Serafini M, et al. Arabesque: A system for distributed graph mining[C]//Proc of the 25th Symp on Operating Systems Principles. New York: ACM, 2015: 425−440
[88]	Abdelhamid E, Abdelaziz I, Kalnis P, et al. Scalemine: Scalable parallel frequent subgraph mining in a single large graph[C]//Proc of the 28th Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2016: 716−727
[89]	Chen Hongzhi, Liu Miao, Zhao Yunjian, et al. G-miner: An efficient task-oriented graph mining system[C/OL]//Proc of the 13th ACM European Conf on Computer Systems. New York: ACM, 2018[2022-07-20].https://dl.acm.org/doi/10.1145/3190508.3190545
[90]	Wang Kai, Zuo Zhiqiang, Thorpe J, et al. RStream: Marrying relational algebra with streaming for efficient graph mining on a single machine[C]// Proc of the 13th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2018: 763−782
[91]	Dias V, Teixeira C H C, Guedes D, et al. Fractal: A general-purpose graph pattern mining system[C/OL]//Proc of the 2019 Int Conf on Management of Data. 2019[2022-09-17].https://dl.acm.org/doi/10.1145/3299869.3319875
[92]	Yan Da, Guo Guimu, Chowdhury M M R, et al. G-thinker: A distributed framework for mining subgraphs in a big graph[C]//Proc of the 36th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2020: 1369−1380
[93]	Chen Xuhao, Dathathri R, Gill G, et al. Pangolin: An efficient and flexible graph mining system on CPU and GPU[J]. Proceedings of the VLDB Endowment, 2020, 13(8): 1190−1205 doi: 10.14778/3389133.3389137
[94]	Trigonakis V, Lozi J P, Faltín T, et al. aDFS: An almost depth-first-search distributed graph-querying system[C]//Proc of the 26th USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2021: 209−224
[95]	Mawhirter D, Wu Bo. Automine: Harmonizing high-level abstraction and high performance for graph mining[C]//Proc of the 27th ACM Symp on Operating Systems Principles. New York: ACM, 2019: 509−523
[96]	Mawhirter D, Reinehr S, Holmes C, et al. Graphzero: Breaking symmetry for efficient graph mining[J]. arXiv preprint, arXiv: 1911.12877, 2019
[97]	Jamshidi K, Mahadasa R, Vora K. Peregrine: A pattern-aware graph mining system[C/OL]//Proc of the 15th European Conf on Computer Systems. New York: ACM, 2020[2022-05-13].https://doi.org/10.1145/3342195.3387548
[98]	Shi Tianhui, Zhai Mingshu, Xu Yi, et al. Graphpi: High performance graph pattern matching through effective redundancy elimination[C]. arXiv preprint, arXiv: 2009.10955, 2020
[99]	Wang Minjie, Yu Lingfan. Deep graph library: Towards efficient and scalable deep learning on graphs[C]. arXiv preprint, arXiv: 1909.01315, 2019
[100]	Fey M, Lenssen J E. Fast graph representation learning with PyTorch Geometric[J]. arXiv preprint, arXiv: 1903.02428, 2019
[101]	Kaler T, Stathas N, Ouyang A, et al. Accelerating training and inference of graph neural networks with fast sampling and pipelining[J]. Proceedings of Machine Learning and Systems, 2022, 4: 172−189
[102]	Min S W, Wu Kun, Huang Sitao, et al. Pytorch-direct: Enabling GPU centric data access for very large graph neural network training with irregular accesses[J]. arXiv preprint, arXiv: 2101.07956, 2021
[103]	Liu Husong, Lu Shengliang, Chen Xinyu, et al. G³: When graph neural networks meet parallel graph processing systems on GPUs[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 2813−2816 doi: 10.14778/3415478.3415482
[104]	Gemawat A. GraphGem: Optimized scalable system for graph convolutional networks[C]//Proc of the 2021 Int Conf on Management of Data. Berkeley, CA: USENIX Association, 2021: 2920−2922
[105]	Chen Zhaodong, Yan Mingyu, Zhu Maohua, et al. FuseGNN: Accelerating graph convolutional neural network training on GPGPU[C/OL]//Proc of the 41st IEEE/ACM Int Conf on Computer Aided Design. New York: ACM, 2020[2022-11-03].https://doi.org/10.1145/3400302.3415610
[106]	Hamilton W, Ying Zhitao, Leskovec J. Inductive representation learning on large graphs[J]. Advances in Neural Information Processing Systems, 2017, 30: 12−30
[107]	Fey M, Lenssen J E, Weichert F, et al. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings[C]// Proc of the 38th Int Conf on Machine Learning. New York: ACM, 2021: 3294−3304
[108]	Tailor S A, Opolka F L, Lio P, et al. Adaptive filters and aggregator fusion for efficient graph convolutions[J]. arXiv preprint, arXiv: 2104.01481, 2021
[109]	Waleffe R, Mohoney J, Rekatsinas T, et al. Marius++: Large-scale training of graph neural networks on a single machine[J]. arXiv preprint, arXiv: 2202.02365, 2022
[110]	Khan N A, Khalaf O I, Romero C A T, et al. Application of Euler neural networks with soft computing paradigm to solve nonlinear problems arising in heat transfer[J]. Entropy, 2021, 23(8): 1053
[111]	Hoang L, Chen Xuhao, Lee H, et al. Efficient distribution for deep learning on large graphs[J]. Update, 2021, 4(5): 1−10
[112]	Jia Zhihao, Lin Sina, Gao Mingyu, et al. Improving the accuracy, scalability, and performance of graph neural networks with roc[J]. Proceedings of Machine Learning and Systems, 2020, 2: 187−198
[113]	Gandhi S, Iyer A P. P3: Distributed deep graph learning at scale[C]// Proc of the 15th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 551−568
[114]	Mariappan M, Vora K. Graphbolt: Dependency-driven synchronous processing of streaming graphs[C]//Proc of the 14th European Conf on Computer Systems. New York: ACM, 2019[2022-02-09].https://doi.org/10.1145/3302424.3303974
[115]	Mariappan M, Che J, Vora K. DZiG: Sparsity-aware incremental processing of streaming graphs[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 83−98
[116]	Jiang Xiaolin, Xu Chengshuo, Yin Xizhe, et al. Tripoline: Generalized incremental graph processing via graph triangle inequality[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 17−32
[117]	Vora K, Gupta R, Xu Guoqing. KickStarter: Fast and accurate computations on streaming graPhs via trimmed approximations[C]//Proc of the 22nd Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM , 2017: 237−251
[118]	Feng Guanyu, Ma Zixuan, Li Daixuan, et al. RisGraph: A real-time streaming system for evolving graphs to support sub-millisecond per-update analysis at millions ops/s[C]//Proc of the 2021 Int Conf on Management of Data. New York: ACM, 2021: 513−527
[119]	Zhu Xiaowei, Feng Guanyu, Serafini M, et al. LiveGraph: A transactional graph storage system with purely sequential adjacency list scans[J]. arXiv preprint, arXiv: 1910.05773, 2019
[120]	Wang Qinggang, Zheng Long, Huang Yu, et al. GraSU: A fast graph update library for FPGA-based dynamic graph processing[C]// Proc of the 30th Int Symp on Field-Programmable Gate Arrays. New York: ACM, 2021: 149−159
[121]	Zhang Yu, Liao Xiaofei, Jin Hai, et al. DiGraph: An efficient path-based iterative directed graph processing system on multiple GPUs[C/OL]//Proc of the 24th Int Conf on Architectural Support for Programming Languages and Operating Systems. 2019[2022-03-12].https://dl.acm.org/doi/10.1145/3297858.3304029
[122]	Zhang Yu, Liao Xiaofei, Gu Lin, et al. AsynGraph: Maximizing data parallelism for efficient iterative graph processing on GPUS[J]. ACM Transactions on Architecture and Code Optimization, 2020, 17(4): 1−21
[123]	Zhang Yu, Peng Da, Liao Xiaofei, et al. LargeGraph: An efficient dependency-aware GPU-accelerated large-scale graph processing[J]. ACM Transactions on Architecture and Code Optimization, 2021, 18(4): 1−24
[124]	Zhang Yu, Liang Yuxuan, Zhao Jin, et al. EGraph: Efficient concurrent GPU-based dynamic graph processing[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(6): 1−13
[125]	Engelhardt N, So H K H. GraVF: A vertex-centric distributed graph processing framework on FPGAs[C/OL]// Proc of the 26th Int Conf on Field Programmable Logic and Applications. Piscataway, NJ: IEEE, 2016[2022-11-14].https://doi.org/10.1109/FPL.2016.7577360
[126]	Dai Guohao, Huang Tianhao, Chi Yuze, et al. ForeGraph: Exploring large-scale graph processing on multi-FPGA architecture[C]//Proc of the 26th ACM/SIGDA Int Symp on Field-Programmable Gate Arrays. New York: ACM, 2017: 217−226
[127]	Zhang Yu, Liao Xiaofei, Jin Hai, et al. DepGraph: A dependency-driven accelerator for efficient iterative graph processing[C]// Proc of the 48th IEEE Int Symp on High-Performance Computer Architecture. Piscataway, NJ: IEEE, 2021: 371−384
[128]	Jin Xin, Yang Zhengyi, Lin Xuemin, et al. Fast: FPGA-based subgraph matching on massive graphs[C]//Proc of the 37th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2021: 1452−1463
[129]	Chen Qihang, Tian Boyu, Gao Mingyu. FINGERS: Exploiting fine-grained parallelism in graph mining accelerators[C]//Proc of the 27th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2022: 43−55
[130]	Dai Guohao, Zhu Zhenhua, Fu Tianyu, et al. DIMMining: Pruning-efficient and parallel graph mining on near-memory-computing[C]//Proc of the 49th Annual Int Symp on Computer Architecture. New York: ISCA, 2022: 130−145
[131]	Yan Mingyu, Deng Lei, Hu Xing, et al. Hygcn: A GCN accelerator with hybrid architecture[C]// Proc of the 26th IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2020: 15−29
[132]	Liang Shengwen, Wang Ying, Liu Cheng, et al. Engn: A high-throughput and energy-efficient accelerator for large graph neural networks[J]. IEEE Transactions on Computers. Piscataway, NJ: IEEE, 2020, 70(9): 1511−1525
[133]	Liang Shengwen, Liu Cheng, Wang Ying, et al. DeepBurning-GL: An automated framework for generating graph neural network accelerators[C/OL]//Proc of the 41st IEEE/ACM Int Conf on Computer Aided Design. Piscataway, NJ: IEEE, 2020[2022-11-12].https://doi.org/10.1145/3400302.3415645
[134]	Zhao Jin, Yang Yun, Zhang Yu, et al. TDGraph: A topology-driven accelerator for high-performance streaming graph processing[C]//Proc of the 49th Annual Int Symp on Computer Architecture. New York: ISCA, 2022: 116−129
[135]	Zhao Jin, Zhang Yu, Liao Xiaofei, et al. LCCG: A locality-centric hardware accelerator for high throughput of concurrent graph processing[C/OL]//Proc of the 33rd Int Conf for High Performance Computing, Networking, Storage and Analysis. 2021[2022-11-08].https://doi.org/10.1145/3458817.3480854
[136]	Zhang Yu, Liao Xiaofei, Jin Hai, et al. HotGraph: Efficient asynchronous processing for real-world graphs[J]. IEEE Transactions on Computers, 2016, 66(5): 799−809
[137]	Zhang Yu, Liao Xiaofei, Jin Hai, et al. CGraph: A correlations-aware approach for efficient concurrent iterative graph processing[C]// Proc of the 16th USENIX Annual Technical Conf (USENIX ATC 18). Berkeley, CA: USENIX Association, 2018: 441−452
[138]	Zhang Yu, Zhao Jin, Liao Xiaofei, et al. CGraph: A distributed storage and processing system for concurrent iterative graph analysis jobs[J]. ACM Transactions on Storage, 2019, 15(2): 1−26
[139]	Yuan Pingpeng, Xie Changfeng, Liu Ling, et al. PathGraph: A path centric graph processing system[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(10): 2998−3012 doi: 10.1109/TPDS.2016.2518664
[140]	Zhang Yu, Liao Xiaofei, Shi Xiang, et al. Efficient disk-based directed graph processing: A strongly connected component approach[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 29(4): 830−842
[141]	Zhang Mingxing, Wu Yongwei, Zhuo Youwei, et al. Wonderland: A novel abstraction-based out-of-core graph processing system[J]. ACM SIGPLAN Notices, 2018, 53(2): 608−621 doi: 10.1145/3296957.3173208
[142]	Zhao Jin, Zhang Yu, Liao Xiaofei, et al. GraphM: An efficient storage system for high throughput of concurrent graph processing[C/OL]//Proc of the 31st Int Conf for High Performance Computing, Networking, Storage and Analysis. 2019[2022-10-25].https://doi.org/10.1145/3295500.3356143
[143]	Liao Xiaofei, Zhao Jin, Zhang Yu, et al. A structure-aware storage optimization for out-of-core concurrent graph processing[J]. IEEE Transactions on Computers, 2021, 71(7): 1612−1625
[144]	Xie Chennning, Chen Rong, Guan Haibing, et al. Sync or async: Time to fuse for distributed graph-parallel computation[J]. ACM SIGPLAN Notices, 2015, 50(8): 194−204 doi: 10.1145/2858788.2688508
[145]	Chen Rong, Shi Jiaxin, Chen Yanzhe, et al. Powerlyra: Differentiated graph computation and partitioning on skewed graphs[J]. ACM Transactions on Parallel Computing, 2019, 5(3): 1−39
[146]	Zhu Xiaowei, Chen Wenguang, Zheng Weimin, et al. Gemini: A computation-centric distributed graph processing system[C]//Proc of the 12th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 301−316
[147]	Zhang Yanfeng, Gao Qixin, Gao Lixin, et al. Maiter: An asynchronous graph processing framework for delta-based accumulative iterative computation[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(8): 2091−2100
[148]	Wang Qiange, Zhang Yanfeng, Wang Hao, et al. Automating incremental and asynchronous evaluation for recursive aggregate data processing[C]//Proc of the 2020 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2020: 2439−2454
[149]	Ma Lingxiao, Yang Zhi, Miao Youshan, et al. NeuGraph: Parallel deep neural network computation on large graphs[C]// Proc of the 15th USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2019: 443−458
[150]	Wu Yidi, Ma Kaihao, Cai Zhenkun, et al. Seastar: Vertex-centric programming for graph neural networks[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 359−375
[151]	Wang Yuke, Feng Boyuan, Li Gushu, et al. GNNAdvisor: An adaptive and efficient runtime system for GNN acceleration on GPUs[C]// Proc of the 15th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2021: 515−531
[152]	Yang Jianbang, Tang Dahai, Song Xiaoniu, et al. GNNLab: A factored system for sample-based GNN training over GPUs[C]//Proc of the 17th European Conf on Computer Systems. New York: ACM, 2022: 417−434
[153]	Dai Guohao, Huang Guyue, Yang Shang, et al. Heuristic adaptability to input dynamics for SpMM on GPUs[J]. arXiv preprint, arXiv: 2202.08556, 2022
[154]	Zhu Rong, Zhao Kun, Yang Hongxia, et al. Aligraph: A comprehensive graph neural network platform[J]. arXiv preprint, arXiv: 1902.08730, 2019
[155]	Cai Zhenkun, Yan Xiao, Wu Yidi, et al. DGCL: An efficient communication library for distributed GNN training[C]//Proc of the 16th European Conf on Computer Systems. New York: ACM, 2021: 130−144
[156]	Wang Qiange, Zhang Yanfeng, Wang Hao, et al. NeutronStar: Distributed GNN training with hybrid dependency management[C]//Proc of the 2022 Int Conf on Management of Data. New York: ACM, 2022: 1301−1315

[1]	Cao Yiran, Zhu Youwen, He Xingyu, Zhang Yue. Utility-Optimized Local Differential Privacy Set-Valued Data Frequency Estimation Mechanism[J]. Journal of Computer Research and Development, 2022, 59(10): 2261-2274. DOI: 10.7544/issn1000-1239.20220504
[2]	Hong Jinxin, Wu Yingjie, Cai Jianping, Sun Lan. Differentially Private High-Dimensional Binary Data Publication via Attribute Segmentation[J]. Journal of Computer Research and Development, 2022, 59(1): 182-196. DOI: 10.7544/issn1000-1239.20200701
[3]	Wu Wanqing, Zhao Yongxin, Wang Qiao, Di Chaofan. A Safe Storage and Release Method of Trajectory Data Satisfying Differential Privacy[J]. Journal of Computer Research and Development, 2021, 58(11): 2430-2443. DOI: 10.7544/issn1000-1239.2021.20210589
[4]	Zhang Yuxuan, Wei Jianghong, Li Ji, Liu Wenfen, Hu Xuexian. Graph Degree Histogram Publication Method with Node-Differential Privacy[J]. Journal of Computer Research and Development, 2019, 56(3): 508-520. DOI: 10.7544/issn1000-1239.2019.20170886
[5]	Zhu Weijun, You Qingguang, Yang Weidong, Zhou Qinglei. Trajectory Privacy Preserving Based on Statistical Differential Privacy[J]. Journal of Computer Research and Development, 2017, 54(12): 2825-2832. DOI: 10.7544/issn1000-1239.2017.20160647
[6]	Wu Yingjie, Zhang Liqun, Kang Jian, Wang Yilei. An Algorithm for Differential Privacy Streaming Data Adaptive Publication[J]. Journal of Computer Research and Development, 2017, 54(12): 2805-2817. DOI: 10.7544/issn1000-1239.2017.20160555
[7]	Wang Liang, Wang Weiping, Meng Dan. Privacy Preserving Data Publishing via Weighted Bayesian Networks[J]. Journal of Computer Research and Development, 2016, 53(10): 2343-2353. DOI: 10.7544/issn1000-1239.2016.20160465
[8]	Lu Guoqing, Zhang Xiaojian, Ding Liping, Li Yanfeng, Liao Xin. Frequent Sequential Pattern Mining under Differential Privacy[J]. Journal of Computer Research and Development, 2015, 52(12): 2789-2801. DOI: 10.7544/issn1000-1239.2015.20140516
[9]	Ouyang Jia, Yin Jian, Liu Shaopeng, Liu Yubao. An Effective Differential Privacy Transaction Data Publication Strategy[J]. Journal of Computer Research and Development, 2014, 51(10): 2195-2205. DOI: 10.7544/issn1000-1239.2014.20130824
[10]	Ni Weiwei, Chen Geng, Chong Zhihong, Wu Yingjie. Privacy-Preserving Data Publication for Clustering[J]. Journal of Computer Research and Development, 2012, 49(5): 1095-1104.

Cited By

Cited by

Periodical cited type(5)

1.	张涵，于航，周继威，白云开，赵路坦. 面向隐私计算的可信执行环境综述. 计算机应用. 2025(02): 467-481 .
2.	付裕，林璟锵，冯登国. 虚拟化与密码技术应用:现状与未来. 密码学报(中英文). 2024(01): 3-21 .
3.	徐传康，李忠月，刘天宇，种统洪，杨发雪. 基于可信执行环境的汽车域控系统安全研究. 汽车实用技术. 2024(15): 18-25+73 .
4.	徐文嘉，岑孟杰，陈亮. 隐私保护下单细胞RNA测序数据细胞分类研究. 医学信息学杂志. 2024(10): 86-89 .
5.	孙钰，熊高剑，刘潇，李燕. 基于可信执行环境的安全推理研究进展. 信息网络安全. 2024(12): 1799-1818 .