大规模图计算系统综述

刘苧; 李东升; 张一鸣; 李雄略

doi:10.1631/FITEE.1900127

Your Location：

Home >

Browse articles >

大规模图计算系统综述

常规文章 | Updated：2022-05-19

- 大规模图计算系统综述
  Enhanced Publication
- Large-scale graph processing systems: a survey
- 信息与电子工程前沿（英文） 2020年21卷第3期页码：384-404
- Affiliations：
  
  Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology, Changsha 410000, China
- Author bio：
  
  [ "Ning LIU, E-mail: liuning17a@nudt.edu.cn" ]
  [ "", "Dr. Dong-sheng LI, corresponding author of this invited review article, received the BS degree (with honors) and PhD degree (with honors) in computer science from College of Computer Science, National University of Defense Technology (NUDT), Changsha, China, in 1999 and 2005, respectively. He was awarded the prize of National Excellent Doctoral Dissertation by the Ministry of Education of China in 2008. He is now a full professor at the National Lab for Parallel and Distributed Processing, NUDT. He is a corresponding expert of Frontiers of Information Technology & Electronic Engineering. His research interests include parallel and distributed computing, cloud computing, and large-scale data management" ]
  [ "Yi-ming ZHANG, E-mail: zhangyiming@nudt.edu.cn" ]
  [ "Xiong-lve LI, E-mail: lixionglve17@nudt.edu.cn" ]
- Funds：
  
  Project supported by the National Key Program of China (No. 2018YFB2101100), the National Natural Science Foundation of China (Nos. 61932001 and 61872376), and the Major State Research Development Program of China (No. 2016YFB0201305)
- DOI：10.1631/FITEE.1900127
  中图分类号： TP391.41
- 纸质出版日期：2020-03，
  
  收稿日期：2019-03-05，
  
  修回日期：2019-11-12，
- Accepted：
Scan QR Code
刘苧, 李东升, 张一鸣, 等. 大规模图计算系统综述[J]. 信息与电子工程前沿（英文）, 2020,21(3):384-404.

NING LIU, DONG-SHENG LI, YI-MING ZHANG, et al. Large-scale graph processing systems: a survey. [J]. Frontiers of information technology & electronic engineering, 2020, 21(3): 384-404.
刘苧, 李东升, 张一鸣, 等. 大规模图计算系统综述[J]. 信息与电子工程前沿（英文）, 2020,21(3):384-404. DOI： 10.1631/FITEE.1900127.

NING LIU, DONG-SHENG LI, YI-MING ZHANG, et al. Large-scale graph processing systems: a survey. [J]. Frontiers of information technology & electronic engineering, 2020, 21(3): 384-404. DOI： 10.1631/FITEE.1900127.

摘要

图是描述实体之间关系的一种重要数据结构。现实世界中许多应用领域非常依赖图数据。然而，由于图计算应用与传统应用的显著差异，利用通用平台处理图计算应用是低效的，这极大推动了专用图计算系统的研究。本综述系统地对图算法和图计算应用进行分类，将现有图计算系统划分为通用和专用系统，并详细总结。深入分析图计算系统的实现技术，包括编程模型、分区策略、通信模型、执行模型和容错机制。最后，分析图计算领域最新进展，并提出有待进一步研究的4个问题。

Abstract

Graph is a significant data structure that describes the relationship between entries. Many application domains in the real world are heavily dependent on graph data. However

graph applications are vastly different from traditional applications. It is inefficient to use general-purpose platforms for graph applications

thus contributing to the research of specific graph processing platforms. In this survey

we systematically categorize the graph workloads and applications

and provide a detailed review of existing graph processing platforms by dividing them into general-purpose and specialized systems. We thoroughly analyze the implementation technologies including programming models

partitioning strategies

communication models

execution models

and fault tolerance strategies. Finally

we analyze recent advances and present four open problems for future research.

关键词

图算法图计算应用图计算系统

Keywords

Graph workloadsGraph applicationsGraph processing systems

references

A Abou-Rjeili, , , G Karypis. . Multilevel algorithms for partitioning power-law graphs. . Proc 20th IEEE Int Parallel and Distributed Processing Symp, , 2006. . Article 10DOI:10.1109/IPDPS.2006.1639360http://doi.org/10.1109/IPDPS.2006.1639360..

D Ajwani, , , R Dementiev, , , U Meyer. . A computational study of external-memory BFS algorithms. . Proc 17th Annual ACM-SIAM Symp on Discrete Algorithm, , 2006. . p.601--610. . ..

D Ajwani, , , U Meyer, , , V Osipov. . Improved external memory BFS implementations. . Proc Meeting on Algorithm Engineering and Expermiments, , 2007. . p.3--12. . ..

L Arge, , , GS Brodal, , , L Toma. . On external-memory MST, SSSP, and multi-way planar graph separation. . Proc 7th Scandinavian Workshop on Algorithm Theory, , 2000. . p.433--447. . DOI:10.1007/3-540-44985-X_37http://doi.org/10.1007/3-540-44985-X_37..

J Atwood, , , D Towsley. . Diffusion-convolutional neural networks, , 2016. . https://arxiv.org/abs/1511.02136https://arxiv.org/abs/1511.02136, , ..

C Avery. . Giraph: large-scale graph processing infrastructure on Hadoop. . Proc Hadoop Summit, , 2011. . p.5--9. . ..

B Awerbuch, , , RG Gallager. . Distributed BFS algorithms. . 26th Annual Symp on Foundations of Computer Science, , 1985. . p.250--256. . DOI:10.1109/SFCS.1985.20http://doi.org/10.1109/SFCS.1985.20..

DA Bader, , , G Cong. . Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. . J Parall Distr Comput, , 2006. . 66((11):):1366--1378. . DOI:10.1016/j.jpdc.2006.06.001http://doi.org/10.1016/j.jpdc.2006.06.001..

DA Bader, , , K Madduri. . Parallel algorithms for evaluating centrality indices in real-world networks. . Int Conf on Parallel Processing, , 2006. . p.539--550. . DOI:10.1109/ICPP.2006.57http://doi.org/10.1109/ICPP.2006.57..

NT Bao, , , T Suzumura. . Towards highly scalable pregelbased graph processing platform with x10. . Proc 22nd Int Conf on World Wide Web, , 2013. . p.501--508. . DOI:10.1145/2487788.2487984http://doi.org/10.1145/2487788.2487984..

O Batarfi, , , R El Shawi, , , AG Fayoumi, , , 等. . Large scale graph processing systems: survey and an experimental evaluation. . Clust Comput, , 2015. . 18((3):):1189--1213. . DOI:10.1007/s10586-015-0472-6http://doi.org/10.1007/s10586-015-0472-6..

J Baumes, , , M Goldberg, , , M Magdon-Ismail. . Efficient identification of overlapping communities. . IEEE Int Conf on Intelligence and Security Informatics, , 2005. . p.27--36. . DOI:10.1007/11427995_3http://doi.org/10.1007/11427995_3..

L Becchetti, , , P Boldi, , , C Castillo, , , 等. . Efficient semi-streaming algorithms for local triangle counting in massive graphs. . Proc 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, , 2008. . p.16--24. . DOI:10.1145/1401890.1401898http://doi.org/10.1145/1401890.1401898..

M Belkin, , , P Niyogi. . Laplacian eigenmaps and spectral techniques for embedding and clustering. . Proc 14th Int Conf on Neural Information Processing Systems, , 2001. . p.585--591. . ..

C Binnig, , , A Crotty, , , A Galakatos, , , 等. . The end of slow networks: it's time for a redesign. . Proc VLDB Endowm, , 2016. . 9((7):):528--539. . DOI:10.14778/2904483.2904485http://doi.org/10.14778/2904483.2904485..

C Borgelt, , , MR Berthold. . Mining molecular fragments: finding relevant substructures of molecules. . IEEE Int Conf on Data Mining, , 2002. . p.51--58. . DOI:10.1109/ICDM.2002.1183885http://doi.org/10.1109/ICDM.2002.1183885..

U Brandes. . A faster algorithm for betweenness centrality. . J Math Sociol, , 2001. . 25((2):):163--177. . DOI:10.1080/0022250X.2001.9990249http://doi.org/10.1080/0022250X.2001.9990249..

J Bruna, , , W Zaremba, , , A Szlam, , , 等. . Spectral networks and locally connected networks on graphs, , 2014. . https://arxiv.org/abs/1312.6203https://arxiv.org/abs/1312.6203, , ..

YY Bu, , , B Howe, , , M Balazinska, , , 等. . HaLoop: efficient iterative data processing on large clusters. . Proc VLDB Endowm, , 2010. . 3((1-2):):285--296. . DOI:10.14778/1920841.1920881http://doi.org/10.14778/1920841.1920881..

YY Bu, , , V Borkar, , , J Jia, , , 等. . Pregelix: big(ger) graph analytics on a dataflow engine. . Proc VLDB Endowm, , 2014. . 8((2):):161--172. . DOI:10.14778/2735471.2735477http://doi.org/10.14778/2735471.2735477..

A Bulu, , , K Madduri. . Parallel breadth-first search on distributed memory systems. . Proc Int Conf for High Performance Computing, Networking, Storage and Analysis, , 2011. . Article 65DOI:10.1145/2063384.2063471http://doi.org/10.1145/2063384.2063471..

A Bulu, , , H Meyerhenke, , , I Safro, , , 等. . Recent advances in graph partitioning. . In: Kliemann L, Sanders P (Eds.), Algorithm Engineering. Springer, Cham, , 2016. . p.117--158. . DOI:10.1007/978-3-319-49487-6_4http://doi.org/10.1007/978-3-319-49487-6_4..

TM Chan. . More algorithms for all-pairs shortest paths in weighted graphs. . SIAM J Comput, , 2010. . 39((5):):2075--2089. . DOI:10.1137/08071990Xhttp://doi.org/10.1137/08071990X..

LJ Chang, , , XM Lin, , , WJ Zhang, , , 等. . Optimal enumeration: efficient top-k tree matching. . Proc VLDB Endowm, , 2015. . 8((5):):533--544. . DOI:10.14778/2735479.2735486http://doi.org/10.14778/2735479.2735486..

R Chen, , , X Weng, , , B He, , , 等. . Large graph processing in the cloud. . Proc ACM SIGMOD Int Conf on Management of Data, , 2010. . p.1123--1126. . DOI:10.1145/1807167.1807297http://doi.org/10.1145/1807167.1807297..

R Chen, , , X Ding, , , P Wang, , , 等. . Computation and communication efficient graph processing with distributed immutable view. . Proc 23rd Int Symp on High-Performance Parallel and Distributed Computing, , 2014. . p.215--226. . DOI:10.1145/2600212.2600233http://doi.org/10.1145/2600212.2600233..

R Chen, , , J Shi, , , Y Chen, , , 等. . PowerLyra: differentiated graph computation and partitioning on skewed graphs. . 10th European Conf on Computer Systems, , 2015. . Article 1..

YZ Chen, , , XD Wei, , , JX Shi, , , 等. . Fast and general distributed transactions using RDMA and HTM. . Proc 11th European Conf on Computer Systems, , 2016. . Article 26DOI:10.1145/2901318.2901349http://doi.org/10.1145/2901318.2901349..

TY Cheung. . Graph traversal techniques and the maximum flow problem in distributed computation. . IEEE Trans Softw Eng, , 1983. . 9((4):):504--512. . DOI:10.1109/TSE.1983.234958http://doi.org/10.1109/TSE.1983.234958..

Y Chi, , , G Dai, , , Y Wang, , , 等. . NXgraph: an efficient graph processing system on a single machine. . IEEE 32nd Int Conf on Data Engineering, , 2016. . p.409--420. . DOI:10.1109/ICDE.2016.7498258http://doi.org/10.1109/ICDE.2016.7498258..

Z Da, , , D Mhembere, , , R Burns, , , 等. . FlashGraph: processing billion-node graphs on an array of commodity SSDS. . Proc 13th USENIX Conf on File and Storage Technologies, , 2015. . p.45--58. . ..

J Dean, , , S Ghemawat. . MapReduce: simplified data processing on large clusters. . Commun ACM, , 2008. . 51((1):):107--113. . DOI:10.1145/1327452.1327492http://doi.org/10.1145/1327452.1327492..

M Defferrard, , , X Bresson, , , P Vandergheynst. . Convolutional neural networks on graphs with fast localized spectral filtering, , 2016. . https://arxiv.org/abs/1606.09375https://arxiv.org/abs/1606.09375, , ..

P Desikan, , , N Pathak, , , J Srivastava, , , 等. . Incremental page rank computation on evolving graphs. . Special Interest Tracks and Posters of the 14th Int Conf on World Wide Web, , 2005. . p.1094--1095. . DOI:10.1145/1062745.1062885http://doi.org/10.1145/1062745.1062885..

N Doekemeijer, , , AL Varbanescu. . A Survey of Parallel Graph Processing Frameworks. . Technical Report No. PDS-2014-003, Delft University of Technology, the Netherlands, , 2014. ..

A Dragojevi, , , D Narayanan, , , O Hodson, , , 等. . FaRM: fast remote memory. . Proc 11th USENIX Conf on Networked Systems Design and Implementation, , 2014. . p.401--414. . ..

D Duvenaud, , , D Maclaurin, , , J Aguilera-Iparraguirre, , , 等. . Convolutional networks on graphs for learning molecular fingerprints. . Proc 28th Int Conf on Neural Information Processing Systems, , 2015. . p.2224--2232. . ..

J Ekanayake, , , H Li, , , B Zhang, , , 等. . Twister: a runtime for iterative MapReduce. . Proc 19th ACM Int Symp on High Performance Distributed Computing, , 2010. . p.810--818. . ..

IJ Farkas, , , D bel, , , G Palla, , , 等. . Weighted network modules. . New J Phys, , 2007. . 9((6):):180DOI:10.1088/1367-2630/9/6/180http://doi.org/10.1088/1367-2630/9/6/180..

MR Garey, , , DS Johnson, , , L Stockmeyer. . Some simplified NP-complete problems. . Proc 6th Annual ACM Symp on Theory of Computing, , 1974. . p.47--63. . DOI:10.1145/800119.803884http://doi.org/10.1145/800119.803884..

JE Gonzalez, , , Y Low, , , H Gu, , , 等. . PowerGraph: distributed graph-parallel computation on natural graphs. . Proc 10th USENIX Conf on Operating Systems Design and Implementation, , 2012. . p.17--30. . ..

JE Gonzalez, , , RS Xin, , , A Dave, , , 等. . GraphX: graph processing in a distributed dataflow framework. . Proc 11th USENIX Conf on Operating Systems Design and Implementation, , 2014. . p.599--613. . ..

WS Han, , , J Lee, , , JH Lee. . TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases. . Proc Int Conf on Management of Data, , 2013a. . p.337--348. . ..

WS Han, , , S Lee, , , K Park, , , 等. . TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC. . Proc 19th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, , 2013b. . p.77--85. . DOI:10.1145/2487575.2487581http://doi.org/10.1145/2487575.2487581..

P Harish, , , V Vineet, , , P Narayanan. . Large graph algorithms for massively multithreaded architectures. . Technical Report No. IIIT/TR/2009/74. Centre for Visual Information Technology, University of Hyderabad, India, , 2009. ..

DS Hirschberg, , , AK Chandra, , , DV Sarwate. . Computing connected components on parallel computers. . Commun ACM, , 1979. . 22((8):):461--464. . DOI:10.1145/359138.359141http://doi.org/10.1145/359138.359141..

LY Ho, , , TH Li, , , JJ Wu, , , 等. . Kylin: an efficient and scalable graph data processing system. . IEEE Int Conf on Big Data, , 2013. . p.193--198. . DOI:10.1109/BigData.2013.6691574http://doi.org/10.1109/BigData.2013.6691574..

LB Holder, , , DJ Cook, , , S Djoko. . Substructure discovery in the SUBDUE system. . Proc 3rd Int Conf on Knowledge Discovery and Data Mining, , 1994. . p.169--180. . ..

J Huan, , , W Wang, , , J Prins. . Efficient mining of frequent subgraphs in the presence of isomorphism. . 3rd IEEE Int Conf on Data Mining, , 2003. . p.549--552. . DOI:10.1109/ICDM.2003.1250974http://doi.org/10.1109/ICDM.2003.1250974..

J Huan, , , W Wang, , , J Prins, , , 等. . SPIN: mining maximal frequent subgraphs from graph databases. . 10th Int Conf on Knowledge Discovery and Data Mining, , 2004. . p.581--586. . DOI:10.1145/1014052.1014123http://doi.org/10.1145/1014052.1014123..

J Huang, , , DJ Abadi. . Leopard: lightweight edge oriented partitioning and replication for dynamic graphs. . Proc VLDB Endowm, , 2016. . 9((7):):540--551. . DOI:10.14778/2904483.2904486http://doi.org/10.14778/2904483.2904486..

A Inokuchi, , , T Washio, , , H Motoda. . An Apriori-based algorithm for mining frequent substructures from graph data. . European Conf on Principles of Data Mining and Knowledge Discovery, , 2000. . p.13--23. . DOI:10.1007/3-540-45372-5_2http://doi.org/10.1007/3-540-45372-5_2..

N Jain, , , G Liao, , , TL Willke. . GraphBuilder: scalable graph ETL framework. . 1st Int Workshop on Graph Data Management Experiences and Systems, , 2013. . Article 4DOI:10.1145/2484425.2484429http://doi.org/10.1145/2484425.2484429..

V Kalavri, , , J Liagouris, , , M Hoffmann, , , 等. . Three steps is all you need: fast, accurate, automatic scaling decisions for distributed streaming dataflows. . 13th USENIX Symp on Operating Systems Design and Implementation, , 2018. . p.783--798. . ..

SD Kamvar, , , TH Haveliwala, , , CD Manning, , , 等. . Extrapolation methods for accelerating PageRank computations. . Proc 12th Int Conf on World Wide Web, , 2003. . p.261--270. . DOI:10.1145/775152.775190http://doi.org/10.1145/775152.775190..

U Kang, , , CE Tsourakakis, , , C Faloutsos. . PEGASUS: a peta-scale graph mining system implementation and observations. . 9th IEEE Int Conf on Data Mining, , 2009. . p.229--238. . DOI:10.1109/ICDM.2009.14http://doi.org/10.1109/ICDM.2009.14..

S Kelley. . The existence and discovery of overlapping communities in large-scale networks. . PhD Thesis, Rensselaer Polytechnic Institute, Troy, NY, USA, , 2009. ..

TN Kipf, , , M Welling. . Semi-supervised classification with graph convolutional networks, , 2016a. . https://arxiv.org/abs/1609.02907https://arxiv.org/abs/1609.02907, , ..

TN Kipf, , , M Welling. . Variational graph auto-encoders, , 2016b. . https://arxiv.org/abs/1611.07308https://arxiv.org/abs/1611.07308, , ..

MN Kolountzakis, , , GL Miller, , , R Peng, , , 等. . Efficient triangle counting in large graphs via degree-based vertex partitioning. . Int Math, , 2012. . 8((1-2):):161--185. . DOI:10.1080/15427951.2012.625260http://doi.org/10.1080/15427951.2012.625260..

M Kuramochi, , , G Karypis. . GREW: a scalable frequent subgraph discovery algorithm. . 4th IEEE Int Conf on Data Mining, , 2003. . p.439--442. . DOI:10.1109/ICDM.2004.10024http://doi.org/10.1109/ICDM.2004.10024..

M Kuramochi, , , G Karypis. . An efficient algorithm for discovering frequent subgraphs. . IEEE Trans Knowl Data Eng, , 2004. . 16((9):):1038--1051. . DOI:10.1109/TKDE.2004.33http://doi.org/10.1109/TKDE.2004.33..

K Kutzkov, , , R Pagh. . Triangle counting in dynamic graph streams. . Scandinavian Workshop on Algorithm Theory, , 2014. . p.306--318. . DOI:10.1007/978-3-319-08404-6_27http://doi.org/10.1007/978-3-319-08404-6_27..

A Kyrola, , , GE Blelloch, , , C Guestrin. . GraphChi: largescale graph computation on just a PC. . Proc USENIX Symp on Operating Systems Design and Implementation, , 2012. . p.31--46. . ..

A Lancichinetti, , , S Fortunato, , , J KertȦsz. . Detecting the overlapping and hierarchical community structure in complex networks. . N J Phys, , 2009. . 11((3):):19--44. . ..

K Lang. . Finding good nearly balanced cuts in power law graphs. . Yahoo Research Labs, CA, USA., , 2004. . 2019https://doi.org/db_file/2004/12/1023.pdfhttps://doi.org/db_file/2004/12/1023.pdf, , [Assessed on Sept. 16, 2019]..

C Lee, , , F Reid, , , A Mcdaid, , , 等. . Detecting highly overlapping community structure by greedy clique expansion. . 4th SNA-KDD Workshop on Social Network Mining and Analysis, , 2010. . p.1--10. . ..

CE Leiserson, , , TB Schardl. . A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). . Proc 22nd Annual ACM Symp on Parallelism in Algorithms and Architectures, , 2010. . p.303--314. . DOI:10.1145/1810479.1810534http://doi.org/10.1145/1810479.1810534..

H Liu, , , HH Huang. . Graphene: fine-grained IO management for graph computing. . Proc 15th USENIX Conf on File and Storage Technologies, , 2017. . p.285--300. . ..

Z Lotker, , , B Patt-Shamir, , , D Peleg. . Distributed MST for constant diameter graphs. . Distr Comput, , 2006. . 18((6):):453--460. . DOI:10.1007/s00446-005-0127-6http://doi.org/10.1007/s00446-005-0127-6..

Y Low, , , JE Gonzalez, , , A Kyrola, , , 等. . GraphLab: a new framework for parallel machine learning, , 2010. . https://arxiv.org/abs/1408.2041https://arxiv.org/abs/1408.2041, , ..

Y Low, , , D Bickson, , , J Gonzalez, , , 等. . Distributed GraphLab: a framework for machine learning and data mining in the cloud. . Proc VLDB Endowm, , 2012. . 5((8):):716--727. . DOI:10.14778/2212351.2212354http://doi.org/10.14778/2212351.2212354..

H Ma, , , H Yang, , , MR Lyu, , , 等. . Mining social networks using heat diffusion processes for marketing candidates selection. . Proc 17th ACM Conf on Information and Knowledge Management, , 2008. . p.233--242. . DOI:10.1145/1458082.1458115http://doi.org/10.1145/1458082.1458115..

S Maass, , , C Min, , , S Kashyap, , , 等. . Mosaic: processing a trillion-edge graph on a single machine. . Proc 20th European Conf on Computer Systems, , 2017. . p.527--543. . DOI:10.1145/3064176.3064191http://doi.org/10.1145/3064176.3064191..

A Maheshwari, , , N Zeh. . I/O-efficient algorithms for graphs of bounded treewidth. . Proc 12th Annual ACMSIAM Symp on Discrete Algorithms, , 2001. . p.89--90. . ..

G Malewicz, , , MH Austern, , , AJ Bik, , , 等. . Pregel: a system for large-scale graph processing. . Proc ACM SIGMOD Int Conf on Management of Data, , 2010. . p.135--146. . ..

K Matsumoto, , , N Nakasato, , , SG Sedukhin. . Blocked all-pairs shortest paths algorithm for hybrid CPU-GPU system. . IEEE 13th Int Conf on High Performance Computing and Communications, , 2011. . p.145--152. . DOI:10.1109/HPCC.2011.28http://doi.org/10.1109/HPCC.2011.28..

RR McCune, , , T Weninger, , , G Madey. . Thinking like a vertex: a survey of vertex-centric frameworks for largescale distributed graph processing. . ACM Comput Surv, , 2015. . 48((2):):25DOI:10.1145/2818185http://doi.org/10.1145/2818185..

X Miao. . DynaDiffuse: a dynamic diffusion model for continuous time constrained influence maximization. . Proc 29th AAAI Conf on Artificial Intelligence, , 2015. . p.346--352. . ..

R Mihalcea. . Graph-based ranking algorithms for sentence extraction, applied to text summarization. . Proc ACL on Interactive Poster and Demonstration Sessions, , 2004. . Article 20DOI:10.3115/1219044.1219064http://doi.org/10.3115/1219044.1219064..

DG Murray, , , F McSherry, , , R Isaacs, , , 等. . Naiad: a timely dataflow system. . Proc 24th ACM Symp on Operating Systems Principles, , 2013. . p.439--455. . ..

D Nanongkai. . Distributed approximation algorithms for weighted shortest paths. . Proc 46th Annual ACM Symp on Theory of Computing, , 2014. . p.565--573. . DOI:10.1145/2591796.2591850http://doi.org/10.1145/2591796.2591850..

D Nguyen, , , A Lenharth, , , K Pingali. . A lightweight infrastructure for graph analytics. . Proc 24th ACM Symp on Operating Systems Principles, , 2013. . p.456--471. . DOI:10.1145/2517349.2522739http://doi.org/10.1145/2517349.2522739..

M Niepert, , , M Ahmed, , , K Kutzkov. . Learning convolutional neural networks for graphs, , 2016. . https://arxiv.org/abs/1605.05273https://arxiv.org/abs/1605.05273, , ..

E Nuutila, , , E Soisalon-Soininen. . On finding the strongly connected components in a directed graph. . Inform Process Lett, , 1994. . 49((1):):9--14. . DOI:10.1016/0020-0190(94)90047-7http://doi.org/10.1016/0020-0190(94)90047-7..

SR Pan, , , RQ Hu, , , GD Long, , , 等. . Adversarially regularized graph autoencoder for graph embedding, , 2018. . https://arxiv.org/abs/1802.04407https://arxiv.org/abs/1802.04407, , ..

R Power, , , JY Li. . Piccolo: building fast, distributed programs with partitioned tables. . Proc 9th USENIX Conf on Operating Systems Design and Implementation, , 2010. . p.293--306. . ..

I Psorakis, , , S Roberts, , , M Ebden, , , 等. . Overlapping community detection using Bayesian non-negative matrix factorization. . Phys Rev E, , 2011. . 83((2):):066114DOI:10.1103/PhysRevE.83.066114http://doi.org/10.1103/PhysRevE.83.066114..

F Rahimian, , , AH Payberah, , , S Girdzijauskas, , , 等. . Distributed vertex-cut partitioning. . IFIP Int Conf on Distributed Applications and Interoperable Systems, , 2014. . p.186--200. . DOI:10.1007/978-3-662-43352-2_15http://doi.org/10.1007/978-3-662-43352-2_15..

XG Ren, , , JH Wang. . Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. . Proc VLDB Endowm, , 2015. . 8((5):):617--628. . DOI:10.14778/2735479.2735493http://doi.org/10.14778/2735479.2735493..

MA Rodriguez. . The Gremlin graph traversal machine and language (invited talk). . Proc 15th Symp on Database Programming Languages, , 2015. . p.1--10. . DOI:10.1145/2815072.2815073http://doi.org/10.1145/2815072.2815073..

A Roy, , , I Mihailovic, , , W Zwaenepoel. . X-Stream: edgecentric graph processing using streaming partitions. . Proc 24th ACM Symp on Operating Systems Principles, , 2013. . p.472--488. . DOI:10.1145/2517349.2522740http://doi.org/10.1145/2517349.2522740..

A Roy, , , L Bindschaedler, , , J Malicevic, , , 等. . Chaos: scale-out graph processing from secondary storage. . Proc 25th Symp on Operating Systems Principles, , 2015. . p.410--424. . DOI:10.1145/2815400.2815408http://doi.org/10.1145/2815400.2815408..

KM Sabrin, , , Z Lin, , , DHP Chau, , , 等. . MMap: Mining Billion-Scale Graphs on a PC with Fast, Minimalist Approach via Memory Mapping. . Technical Report No. GT-CSE-2013-04, Georgia Institute of Technology, Atlanta, USA, , 2013. ..

S Sakr, , , F Bajaber, , , A Barnawi, , , 等. . Big data processing systems: state-of-the-art and open challenges. . Int Conf on Cloud Computing, , 2015. . p.1--8. . ..

AD Sarma, , , AR Molla, , , G Pandurangan, , , 等. . Fast distributed PageRank computation. . Int Conf on Distributed Computing and Networking, , 2013. . p.11--26. . DOI:10.1007/978-3-642-35668-1_2http://doi.org/10.1007/978-3-642-35668-1_2..

F Scarselli, , , M Gori, , , AC Tsoi, , , 等. . The graph neural network model. . IEEE Trans Neur Netw, , 2009. . 20((1):):61--80. . DOI:10.1109/TNN.2008.2005605http://doi.org/10.1109/TNN.2008.2005605..

K Schloegel, , , G Karypis, , , V Kumar. . Parallel multilevel algorithms for multi-constraint graph partitioning. . Proc 6th Int European Conf on Parallel Processing, , 2000. . p.296--310. . DOI:10.1007/3-540-44520-X_39http://doi.org/10.1007/3-540-44520-X_39..

S Seo, , , EJ Yoon, , , J Kim, , , 等. . HAMA: an efficient matrix computation with the MapReduce framework. . IEEE Second Int Conf on Cloud Computing Technology and Science, , 2010. . p.721--726. . DOI:10.1109/CloudCom.2010.17http://doi.org/10.1109/CloudCom.2010.17..

HC Shang, , , Y Zhang, , , XM Lin, , , 等. . Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. . Proc VLDB Endowm, , 2008. . 1((1):):364--375. . DOI:10.14778/1453856.1453899http://doi.org/10.14778/1453856.1453899..

B Shao, , , HX Wang, , , YT Li. . Trinity: a distributed graph engine on a memory cloud. . Proc ACM SIGMOD Int Conf on Management of Data, , 2013. . p.505--516. . DOI:10.1145/2463676.2467799http://doi.org/10.1145/2463676.2467799..

HW Shen, , , XQ Cheng, , , K Cai, , , 等. . Detect overlapping and hierarchical community structure in networks. . Phys A, , 2008. . 388((8):):1706--1712. . DOI:10.1016/j.physa.2008.12.021http://doi.org/10.1016/j.physa.2008.12.021..

YY Shen, , , G Chen, , , HV Jagadish, , , 等. . Fast failure recovery in distributed graph processing systems. . Proc VLDB Endowm, , 2014. . 8((4):):437--448. . DOI:10.14778/2735496.2735506http://doi.org/10.14778/2735496.2735506..

JX Shi, , , YY Yao, , , R Chen, , , 等. . Fast and concurrent RDF queries with RDMA-based distributed graph exploration. . Proc 12th USENIX Conf on Operating Systems Design and Implementation, , 2016. . p.317--332. . ..

JL Shun, , , GE Blelloch. . Ligra: a lightweight graph processing framework for shared memory. . ACM SIGPLAN Not, , 2013. . 48((8):):135--146. . DOI:10.1145/2442516.2442530http://doi.org/10.1145/2442516.2442530..

Y Simmhan, , , A Kumbhare, , , C Wickramaarachchi, , , 等. . GoFFish: a sub-graph centric framework for large-scale graph analytics. . European Conf on Parallel Processing, , 2014. . p.451--462. . DOI:10.1007/978-3-319-09873-9_38http://doi.org/10.1007/978-3-319-09873-9_38..

I Stanton, , , G Kliot. . Streaming graph partitioning for large distributed graphs. . Proc 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, , 2012. . p.1222--1230. . DOI:10.1145/2339530.2339722http://doi.org/10.1145/2339530.2339722..

N Sundaram, , , N Satish, , , MMA Patwary, , , 等. . GraphMat: high performance graph analytics made productive. . Proc VLDB Endowm, , 2015. . 8((11):):1214--1225. . DOI:10.14778/2809974.2809983http://doi.org/10.14778/2809974.2809983..

Y Taleb, , , R Stutsman, , , G Antoniu, , , 等. . Tailwind: fast and atomic RDMA-based replication. . USENIX Annual Technical Conf, , 2018. . p.850--863. . ..

K Tangwongsan, , , A Pavan, , , S Tirthapura. . Parallel triangle counting in massive streaming graphs. . Proc 22nd ACM Int Conf on Information and Knowledge Management, , 2013. . p.781--786. . DOI:10.1145/2505515.2505741http://doi.org/10.1145/2505515.2505741..

YY Tian, , , A Balmin, , , SA Corsten, , , 等. . From "think like a vertex" to "think like a graph". . Proc VLDB Endowm, , 2013. . 7((3):):193--204. . DOI:10.14778/2732232.2732238http://doi.org/10.14778/2732232.2732238..

JR Ullmann. . An algorithm for subgraph isomorphism. . J ACM, , 1976. . 23((1):):31--42. . DOI:10.1145/321921.321925http://doi.org/10.1145/321921.321925..

LG Valiant. . A bridging model for parallel computation. . Commun ACM, , 1990. . 33((8):):103--111. . DOI:10.1145/79173.79181http://doi.org/10.1145/79173.79181..

A Vaswani, , , N Shazeer, , , N Parmar, , , 等. . Attention is all you need, , 2017. . https://arxiv.org/abs/1706.03762https://arxiv.org/abs/1706.03762, , ..

P Velikovi, , , G Cucurull, , , A Casanova, , , 等. . Graph attention networks, , 2017. . https://arxiv.org/abs/1710.10903https://arxiv.org/abs/1710.10903, , ..

K Vora, , , GH Xu, , , R Gupta. . Load the edges you need: a generic I/O optimization for disk-based graph processing. . USENIX Annual Technical Conf, , 2016. . p.507--522. . ..

K Vora, , , R Gupta, , , GQ Xu. . KickStarter: fast and accurate computations on streaming graphs via trimmed approximations. . Proc 22nd Int Conf on Architectural Support for Programming Languages and Operating Systems, , 2017. . p.237--251. . DOI:10.1145/3037697.3037748http://doi.org/10.1145/3037697.3037748..

DX Wang, , , P Cui, , , WW Zhu. . Structural deep network embedding. . 22nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, , 2016. . p.1225--1234. . DOI:10.1145/2939672.2939753http://doi.org/10.1145/2939672.2939753..

K Wang, , , GH Xu, , , Z Su, , , 等. . GraphQ: graph query processing with abstraction refinement-scalable and programmable analytics over very large graphs on a single PC. . USENIX Annual Technical Conf, , 2015. . p.387--401. . ..

K Wang, , , A Hussain, , , ZQ Zuo, , , 等. . Graspan: a single-machine disk-based graph system for interprocedural static analyses of large-scale systems code. . ACM SIGPLAN Not, , 2017. . 52((4):):389--404. . DOI:10.1145/3093336.3037744http://doi.org/10.1145/3093336.3037744..

K Wang, , , ZQ Zuo, , , J Thorpe, , , 等. . RStream: marrying relational algebra with streaming for efficient graph mining on a single machine. . Proc 12th USENIX Conf on Operating Systems Design and Implementation, , 2018. . p.763--782. . ..

P Wang, , , K Zhang, , , R Chen, , , 等. . Replication-based fault-tolerance for large-scale graph processing. . 44th Annual IEEE/IFIP Int Conf on Dependable Systems and Networks, , 2014. . p.562--573. . DOI:10.1109/DSN.2014.58http://doi.org/10.1109/DSN.2014.58..

T Washio, , , H Motoda. . State of the art of graph-based data mining. . ACM SIGKDD Explor Newsl, , 2003. . 5((1):):59--68. . DOI:10.1145/959242.959249http://doi.org/10.1145/959242.959249..

CN Xie, , , R Chen, , , HB Guan, , , 等. . SYNC or ASYNC: time to fuse for distributed graph-parallel computation. . ACM SIGPLAN Not, , 2015. . 50((8):):194--204. . DOI:10.1145/2858788.2688508http://doi.org/10.1145/2858788.2688508..

WL Xie, , , GZ Wang, , , D Bindel, , , 等. . Fast iterative graph computation with block updates. . Proc VLDB Endowm, , 2013. . 6((14):):2014--2025. . DOI:10.14778/2556549.2556581http://doi.org/10.14778/2556549.2556581..

D Yan, , , J Cheng, , , Y Lu, , , 等. . Blogel: a block-centric framework for distributed computation on real-world graphs. . Proc VLDB Endowm, , 2014. . 7((14):):1981--1992. . DOI:10.14778/2733085.2733103http://doi.org/10.14778/2733085.2733103..

XF Yan, , , JW Han. . gSpan: graph-based substructure pattern mining. . Proc IEEE Int Conf on Data Mining, , 2002. . p.721--724. . DOI:10.1109/ICDM.2002.1184038http://doi.org/10.1109/ICDM.2002.1184038..

XF Yan, , , JW Han. . CloseGraph: mining closed frequent graph patterns. . Proc ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining, , 2003. . p.286--295. . DOI:10.1145/956750.956784http://doi.org/10.1145/956750.956784..

A Yoo, , , E Chow, , , K Henderson, , , 等. . A scalable distributed parallel breadth-first search algorithm on BlueGene/L. . Proc ACM/IEEE Conf on Supercomputing, , 2005. . Article 25DOI:10.1109/SC.2005.4http://doi.org/10.1109/SC.2005.4..

PP Yuan, , , WY Zhang, , , CF Xie, , , 等. . Fast iterative graph computation: a path centric approach. . Proc Int Conf for High Performance Computing, Networking, Storage and Analysis, , 2014. . p.401--412. . ..

M Zaharia, , , M Chowdhury, , , MJ Franklin, , , 等. . Spark: cluster computing with working sets. . Proc 2nd USENIX Conf on Hot Topics in Cloud Computing, , 2010. . Article 10..

KY Zhang, , , R Chen, , , HB Chen. . NUMA-aware graphstructured analytics. . ACM SIGPLAN Not, , 2015. . 50((8):):183--193. . DOI:10.1145/2858788.2688507http://doi.org/10.1145/2858788.2688507..

MX Zhang, , , YW Wu, , , K Chen, , , 等. . Exploring the hidden dimension in graph processing. . Proc 12th USENIX Conf on Operating Systems Design and Implementation, , 2016. . p.285--300. . ..

S Zhang, , , RS Wang, , , XS Zhang. . Identification of overlapping community structure in complex networks using fuzzy c-means clustering. . Phys A, , 2007. . 374((1):):483--490. . DOI:10.1016/j.physa.2006.07.023http://doi.org/10.1016/j.physa.2006.07.023..

Y Zhang, , , XF Liao, , , H Jin, , , 等. . CGraph: a correlations-aware approach for efficient concurrent iterative graph processing. . USENIX Annual Technical Conf, , 2018. . p.1--12. . ..

YH Zhang, , , R Chen, , , HB Chen. . Sub-millisecond stateful stream querying over fast-evolving linked data. . Proc 26th Symp on Operating Systems Principles, , 2017. . p.614--630. . DOI:10.1145/3132747.3132777http://doi.org/10.1145/3132747.3132777..

YM Zhang, , , DS Li, , , CX Guo, , , 等. . CubicRing: exploiting network proximity for distributed in-memory key-value store. . IEEE/ACM Trans Netw, , 2017a. . 25((4):):2040--2053. . DOI:10.1109/TNET.2017.2669215http://doi.org/10.1109/TNET.2017.2669215..

YM Zhang, , , DS Li, , , CX Zhang, , , 等. . GraphA: efficient partitioning and storage for distributed graph computation. . IEEE Trans Serv Comput, online, , 2017b. . DOI:10.1109/TSC.2017.2778737http://doi.org/10.1109/TSC.2017.2778737..

YM Zhang, , , DS Li, , , L Liu. . Leveraging glocality for fast failure recovery in distributed RAM storage. . ACM Trans Stor, , 2019. . 15((1):):3DOI:10.1145/3289604http://doi.org/10.1145/3289604..

Y Zhao, , , K Yoshigoe, , , M Xie, , , 等. . LightGraph: lighten communication in distributed graph-parallel processing. . IEEE Int Congress on Big Data, , 2014. . p.717--724. . DOI:10.1109/BigData.Congress.2014.106http://doi.org/10.1109/BigData.Congress.2014.106..

C Zhou, , , J Gao, , , B Sun, , , 等. . MOCgraph: scalable distributed graph processing using message online computing. . Proc VLDB Endowm, , 2014. . 8((4):):377--388. . DOI:10.14778/2735496.2735501http://doi.org/10.14778/2735496.2735501..

G Zhu, , , X Lin, , , K Zhu, , , 等. . TreeSpan: efficiently computing similarity all-matching. . Proc ACM SIGMOD Int Conf on Management of Data, , 2012. . p.529--540. . DOI:10.1145/2213836.2213896http://doi.org/10.1145/2213836.2213896..

XW Zhu, , , WT Han, , , WG Chen. . GridGraph: largescale graph processing on a single machine using 2-level hierarchical partitioning. . USENIX Annual Technical Conf, , 2015. . p.375--386. . ..

XW Zhu, , , WG Chen, , , WM Zheng, , , 等. . Gemini: a computation-centric distributed graph processing system. . USENIX Symposium on Operating Systems Design and Implementation, , 2016. . p.301--316. . ..

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据