计算机工程与应用 ›› 2022, Vol. 58 ›› Issue (13): 1-13.DOI: 10.3778/j.issn.1002-8331.2201-0206

• 热点与综述 • 上一篇    下一篇

基于随机游走的图嵌入研究综述

腊志垚,钱育蓉,冷洪勇,顾天宇,张继元,李自臣   

  1. 1.新疆大学 软件学院,乌鲁木齐 830046
    2.新疆大学 新疆维吾尔自治区信号检测与处理重点实验室,乌鲁木齐 830046
    3.北京理工大学 计算机学院,北京 100081
    4.广东水利电力职业技术学院 大数据与人工智能学院,广州 510635
  • 出版日期:2022-07-01 发布日期:2022-07-01

Overview of Research on Graph Embedding Based on Random Walk

LA Zhiyao, QIAN Yurong, LENG Hongyong, GU Tianyu, ZHANG Jiyuan, LI Zichen   

  1. 1.Software College, Xinjiang University, Urumqi 830046, China
    2.Key Laboratory of Signal Detection and Processing in Xinjiang Uygur Autonomous Region, Xinjiang University, Urumqi 830046, China
    3.School of Computer Science, Beijing Institute of Technology, Beijing 100081, China 
    4.College of Big Data and Artificial Intelligence, Guangdong Polytechnic of Water Resources and Electric Engineering,Guangzhou 510635, China
  • Online:2022-07-01 Published:2022-07-01

摘要: 近年来,图嵌入已经成为图神经网络领域研究的热点。图嵌入作为图任务分析的一种重要手段,将图的高维非欧信息编码到低维向量空间中,从而提升下游任务的性能和效率。为了及时掌握当前基于随机游走的图嵌入方法的研究现状,通过归纳与整理,对现有的经典模型进行介绍与分类,主要分为基于经典随机游走的模型和基于属性游走的模型;然后对每一种模型解决的问题、算法思想、模型策略、优缺点和应用场景进行了详细的归纳与分析,并在几种常见的数据集上评估了部分模型的性能。通过研究发现,当前的基于随机游走的图嵌入亟待解决四个方面的问题:属性选择、可扩展性、嵌入维度选择和可解释性,针对这些问题,图嵌入需要建立一致的理论框架,为后面的研究提供可参考的标准。

关键词: 图嵌入, 图神经网络, 图任务分析, 随机游走, 属性游走

Abstract: In recent years, graph embedding has become a research hotspot in the field of graph neural networks. As an important means of graph task analysis, graph embedding encodes the high-dimensional non-Euclidean information of graph into low-dimensional vector space, so as to improve the performance and efficiency of downstream tasks. In order to keep abreast of the current research status of graph embedding methods based on random walks, the existing classical models are introduced and classified through induction and sorting, which are mainly divided into models based on classical random walks and models based on attribute walks. Then, the problems, algorithm ideas, model strategies, advantages and disadvantages and application scenarios solved by each model are summarized and analyzed in detail, and the performance of some models is evaluated on several common data sets. Through the research, it is found that the current graph embedding based on random walk needs to solve four problems:attribute selection, scalability, embedding dimension selection and interpretability. To solve these problems, graph embedding needs to establish a consistent theoretical framework to provide a reference standard for later research.

Key words: graph embedding, graph neural network, graph task analysis, random walk, attribute walk