中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
SOOP: Efficient Distributed Graph Computation Supporting Second-Order Random Walks

文献类型：期刊论文

作者Niu, Songjie1,2; Zhou, Dongyan3
刊名JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
出版日期2021-10-01
卷号36期号:5页码:985-1001
关键词second-order random walk (SOW) Node2Vec second-order PageRank distributed graph computation SOOP (second-order random walks with on-demand probability computation)
ISSN号1000-9000
DOI10.1007/s11390-021-1234-y
英文摘要The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks. Existing work mainly focuses on centralized second-order random walk (SOW) algorithms. SOW algorithms rely on edge-to-edge transition probabilities to generate next random steps. However, it is prohibitively costly to store all the probabilities for large-scale graphs, and restricting the number of probabilities to consider can negatively impact the accuracy of graph analysis tasks. In this paper, we propose and study an alternative approach, SOOP (second-order random walks with on-demand probability computation), that avoids the space overhead by computing the edge-to-edge transition probabilities on demand during the random walk. However, the same probabilities may be computed multiple times when the same edge appears multiple times in SOW, incurring extra cost for redundant computation and communication. We propose two optimization techniques that reduce the complexity of computing edge-to-edge transition probabilities to generate next random steps, and reduce the cost of communicating out-neighbors for the probability computation, respectively. Our experiments on real-world and synthetic graphs show that SOOP achieves orders of magnitude better performance than baseline precompute solutions, and it can efficiently computes SOW algorithms on billion-scale graphs.
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000712575700003
出版者SCIENCE PRESS
源URL[http://119.78.100.204/handle/2XEOYT63/16926]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Niu, Songjie
作者单位1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100190, Peoples R China
2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
3.Bytedance Technol, Beijing 100086, Peoples R China
推荐引用方式
GB/T 7714		 Niu, Songjie,Zhou, Dongyan. SOOP: Efficient Distributed Graph Computation Supporting Second-Order Random Walks[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2021,36(5):985-1001.
APA Niu, Songjie,&Zhou, Dongyan.(2021).SOOP: Efficient Distributed Graph Computation Supporting Second-Order Random Walks.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,36(5),985-1001.
MLA Niu, Songjie,et al."SOOP: Efficient Distributed Graph Computation Supporting Second-Order Random Walks".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 36.5(2021):985-1001.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。