大规模图计算系统综述

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

doi:10.1631/FITEE.1900127

Your Location：

Home >

Browse articles >

大规模图计算系统综述

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

- 大规模图计算系统综述
- 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
- 收稿：2019-03-05，
  
  修回：2019-11-12，
  
  纸质出版：2020-03
- 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

references

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

D Ajwani , , , R Dementiev , , , U Meyer . . A computational study of external-memory BFS algorithms . . Proc 17 th 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 7 th Scandinavian Workshop on Algorithm Theory , , 2000 . . p.433 - - 447 . . DOI: 10.1007/3-540-44985-X_37 http://doi.org/10.1007/3-540-44985-X_37 . .

J Atwood , , , D Towsley . . Diffusion-convolutional neural networks , , 2016 . . https://arxiv.org/abs/1511.02136 https://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 . . 26 th Annual Symp on Foundations of Computer Science , , 1985 . . p.250 - - 256 . . DOI: 10.1109/SFCS.1985.20 http://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.001 http://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.57 http://doi.org/10.1109/ICPP.2006.57 . .

NT Bao , , , T Suzumura . . Towards highly scalable pregelbased graph processing platform with x10 . . Proc 22 nd Int Conf on World Wide Web , , 2013 . . p.501 - - 508 . . DOI: 10.1145/2487788.2487984 http://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-6 http://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_3 http://doi.org/10.1007/11427995_3 . .

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

M Belkin , , , P Niyogi . . Laplacian eigenmaps and spectral techniques for embedding and clustering . . Proc 14 th 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.2904485 http://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.1183885 http://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.9990249 http://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.6203 https://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.1920881 http://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.2735477 http://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 65 DOI: 10.1145/2063384.2063471 http://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_4 http://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/08071990X http://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.2735486 http://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.1807297 http://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.2600233 http://doi.org/10.1145/2600212.2600233 . .

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

YZ Chen , , , XD Wei , , , JX Shi , , , 等 . . Fast and general distributed transactions using RDMA and HTM . . Proc 11 th European Conf on Computer Systems , , 2016 . . Article 26 DOI: 10.1145/2901318.2901349 http://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.234958 http://doi.org/10.1109/TSE.1983.234958 . .

Y Chi , , , G Dai , , , Y Wang , , , 等 . . NXgraph: an efficient graph processing system on a single machine . . IEEE 32 nd Int Conf on Data Engineering , , 2016 . . p.409 - - 420 . . DOI: 10.1109/ICDE.2016.7498258 http://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 13 th 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.1327492 http://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.09375 https://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 14 th Int Conf on World Wide Web , , 2005 . . p.1094 - - 1095 . . DOI: 10.1145/1062745.1062885 http://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 11 th 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 28 th Int Conf on Neural Information Processing Systems , , 2015 . . p.2224 - - 2232 . . . .

J Ekanayake , , , H Li , , , B Zhang , , , 等 . . Twister: a runtime for iterative MapReduce . . Proc 19 th 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 ): ): 180 DOI: 10.1088/1367-2630/9/6/180 http://doi.org/10.1088/1367-2630/9/6/180 . .

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

JE Gonzalez , , , Y Low , , , H Gu , , , 等 . . PowerGraph: distributed graph-parallel computation on natural graphs . . Proc 10 th 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 11 th 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 19 th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2013b . . p.77 - - 85 . . DOI: 10.1145/2487575.2487581 http://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.359141 http://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.6691574 http://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.1250974 http://doi.org/10.1109/ICDM.2003.1250974 . .

J Huan , , , W Wang , , , J Prins , , , 等 . . SPIN: mining maximal frequent subgraphs from graph databases . . 10 th Int Conf on Knowledge Discovery and Data Mining , , 2004 . . p.581 - - 586 . . DOI: 10.1145/1014052.1014123 http://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.2904486 http://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_2 http://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 4 DOI: 10.1145/2484425.2484429 http://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 . . 13 th 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 12 th Int Conf on World Wide Web , , 2003 . . p.261 - - 270 . . DOI: 10.1145/775152.775190 http://doi.org/10.1145/775152.775190 . .

U Kang , , , CE Tsourakakis , , , C Faloutsos . . PEGASUS: a peta-scale graph mining system implementation and observations . . 9 th IEEE Int Conf on Data Mining , , 2009 . . p.229 - - 238 . . DOI: 10.1109/ICDM.2009.14 http://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.02907 https://arxiv.org/abs/1609.02907 , , . .

TN Kipf , , , M Welling . . Variational graph auto-encoders , , 2016b . . https://arxiv.org/abs/1611.07308 https://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.625260 http://doi.org/10.1080/15427951.2012.625260 . .

M Kuramochi , , , G Karypis . . GREW: a scalable frequent subgraph discovery algorithm . . 4 th IEEE Int Conf on Data Mining , , 2003 . . p.439 - - 442 . . DOI: 10.1109/ICDM.2004.10024 http://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.33 http://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_27 http://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 . . 2019 https://doi.org/db_file/2004/12/1023.pdf https://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 . . 4 th 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 22 nd Annual ACM Symp on Parallelism in Algorithms and Architectures , , 2010 . . p.303 - - 314 . . DOI: 10.1145/1810479.1810534 http://doi.org/10.1145/1810479.1810534 . .

H Liu , , , HH Huang . . Graphene: fine-grained IO management for graph computing . . Proc 15 th 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-6 http://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.2041 https://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.2212354 http://doi.org/10.14778/2212351.2212354 . .

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

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

A Maheshwari , , , N Zeh . . I/O-efficient algorithms for graphs of bounded treewidth . . Proc 12 th 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 13 th Int Conf on High Performance Computing and Communications , , 2011 . . p.145 - - 152 . . DOI: 10.1109/HPCC.2011.28 http://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 ): ): 25 DOI: 10.1145/2818185 http://doi.org/10.1145/2818185 . .

X Miao . . DynaDiffuse: a dynamic diffusion model for continuous time constrained influence maximization . . Proc 29 th 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 20 DOI: 10.3115/1219044.1219064 http://doi.org/10.3115/1219044.1219064 . .

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

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

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

M Niepert , , , M Ahmed , , , K Kutzkov . . Learning convolutional neural networks for graphs , , 2016 . . https://arxiv.org/abs/1605.05273 https://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-7 http://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.04407 https://arxiv.org/abs/1802.04407 , , . .

R Power , , , JY Li . . Piccolo: building fast, distributed programs with partitioned tables . . Proc 9 th 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 ): ): 066114 DOI: 10.1103/PhysRevE.83.066114 http://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_15 http://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.2735493 http://doi.org/10.14778/2735479.2735493 . .

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

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

A Roy , , , L Bindschaedler , , , J Malicevic , , , 等 . . Chaos: scale-out graph processing from secondary storage . . Proc 25 th Symp on Operating Systems Principles , , 2015 . . p.410 - - 424 . . DOI: 10.1145/2815400.2815408 http://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_2 http://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.2005605 http://doi.org/10.1109/TNN.2008.2005605 . .

K Schloegel , , , G Karypis , , , V Kumar . . Parallel multilevel algorithms for multi-constraint graph partitioning . . Proc 6 th Int European Conf on Parallel Processing , , 2000 . . p.296 - - 310 . . DOI: 10.1007/3-540-44520-X_39 http://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.17 http://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.1453899 http://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.2467799 http://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.021 http://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.2735506 http://doi.org/10.14778/2735496.2735506 . .

JX Shi , , , YY Yao , , , R Chen , , , 等 . . Fast and concurrent RDF queries with RDMA-based distributed graph exploration . . Proc 12 th 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.2442530 http://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_38 http://doi.org/10.1007/978-3-319-09873-9_38 . .

I Stanton , , , G Kliot . . Streaming graph partitioning for large distributed graphs . . Proc 18 th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2012 . . p.1222 - - 1230 . . DOI: 10.1145/2339530.2339722 http://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.2809983 http://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 22 nd ACM Int Conf on Information and Knowledge Management , , 2013 . . p.781 - - 786 . . DOI: 10.1145/2505515.2505741 http://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.2732238 http://doi.org/10.14778/2732232.2732238 . .

JR Ullmann . . An algorithm for subgraph isomorphism . . J ACM , , 1976 . . 23 ( ( 1 ): ): 31 - - 42 . . DOI: 10.1145/321921.321925 http://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.79181 http://doi.org/10.1145/79173.79181 . .

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

P Velikovi , , , G Cucurull , , , A Casanova , , , 等 . . Graph attention networks , , 2017 . . https://arxiv.org/abs/1710.10903 https://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 22 nd Int Conf on Architectural Support for Programming Languages and Operating Systems , , 2017 . . p.237 - - 251 . . DOI: 10.1145/3037697.3037748 http://doi.org/10.1145/3037697.3037748 . .

DX Wang , , , P Cui , , , WW Zhu . . Structural deep network embedding . . 22 nd ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2016 . . p.1225 - - 1234 . . DOI: 10.1145/2939672.2939753 http://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.3037744 http://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 12 th 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 . . 44 th Annual IEEE/IFIP Int Conf on Dependable Systems and Networks , , 2014 . . p.562 - - 573 . . DOI: 10.1109/DSN.2014.58 http://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.959249 http://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.2688508 http://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.2556581 http://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.2733103 http://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.1184038 http://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.956784 http://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 25 DOI: 10.1109/SC.2005.4 http://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 2 nd 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.2688507 http://doi.org/10.1145/2858788.2688507 . .

MX Zhang , , , YW Wu , , , K Chen , , , 等 . . Exploring the hidden dimension in graph processing . . Proc 12 th 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.023 http://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 26 th Symp on Operating Systems Principles , , 2017 . . p.614 - - 630 . . DOI: 10.1145/3132747.3132777 http://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.2669215 http://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.2778737 http://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 ): ): 3 DOI: 10.1145/3289604 http://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.106 http://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.2735501 http://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.2213896 http://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 . . . .

浏览量

121

Downloads

CSCD

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

Submit

工具集

关联资源

暂无数据