Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (1): 59-87.DOI: 10.3778/j.issn.1673-9418.2104020

• Surveys and Frontiers • Previous Articles     Next Articles

Graph Embedding Models: A Survey

YUAN Lining1, LI Xin2, WANG Xiaodong3, LIU Zhao4,+()   

  1. 1. School of Information Network Security, People's Public Security University of China, Beijing 100038, China
    2. Science and Informatization Division, Hexi Branch of Tianjin Public Security Bureau, Tianjin 300202, China
    3. Science and Informatization Division, Hedong Branch of Tianjin Public Security Bureau, Tianjin 300171, China
    4. Research Center for New Crimes, People's Public Security University of China, Beijing 100038, China
  • Received:2021-04-08 Revised:2021-09-07 Online:2022-01-01 Published:2021-09-13
  • About author:YUAN Lining, born in 1995, M.S. candidate, student member of CCF. His research interests include machine learning, graph neural network, etc.
    LI Xin, born in 1987, M.S. His research interests include machine learning, policing information system, etc.
    WANG Xiaodong, born in 1980, intermediate engineer. His research interests include police big data, technical investigation, etc.
    xml:lang="en"LIU Zhao, born in 1981, Ph.D., lecturer. His research interests include machine learning and computer vision.
  • Supported by:
    Fundamental Research Funds for the Central Universities of China(2019JKF425);National Key Research and Development Program of China(2018YFC0809800)

图嵌入模型综述

袁立宁1, 李欣2, 王晓冬3, 刘钊4,+()   

  1. 1.中国人民公安大学 信息网络安全学院,北京 100038
    2.天津市公安局河西分局 科技信息化支队,天津 300202
    3.天津市公安局河东分局 科技信息化支队,天津 300171
    4.中国人民公安大学 新型犯罪研究中心,北京 100038
  • 通讯作者: + E-mail: liuzhao@ppsuc.edu.cn
  • 作者简介:袁立宁(1995—),男,硕士研究生,CCF学生会员,主要研究方向为机器学习、图神经网络等。
    李欣(1987—),男,硕士,主要研究方向为机器学习、公安信息化等。
    王晓冬(1980—),男,中级工程师,主要研究方向为警务大数据、技术侦查等。
    刘钊(1981—),男,博士,讲师, 主要研究方向为机器学习、计算机视觉。
  • 基金资助:
    中央高校基本科研业务费专项资金(2019JKF425);国家重点研发计划(2018YFC0809800)

Abstract:

Effective graph analysis methods can reveal the intrinsic characteristics of graph data. However, graph is non-Euclidean data, which leads to high computation and space cost while applying traditional methods. Graph embedding is an efficient method for graph analysis. It converts original graph data into a low-dimensional space and retains key information to improve the performance of downstream tasks such as node classification, link prediction, and node clustering. Different from previous studies, this paper focuses on both static and dynamic graph embedding. Firstly, this paper proposes a universal taxonomy of static and dynamic methods, including matrix factorization based methods, random walk based methods, autoencoder based methods, graph neural networks (GNN) based methods and other embedding methods. Secondly, this paper analyzes the theoretical relevance of static and dynamic methods, and comprehensively summarizes the core strategy, downstream tasks and datasets. Finally, this paper proposes four potential research directions of graph embedding.

Key words: graph embedding, static graph embedding, dynamic graph embedding, random walk, graph neural networks (GNN)

摘要:

图分析用于深入挖掘图数据的内在特征,然而图作为非欧几里德数据,传统的数据分析方法普遍存在较高的计算量和空间开销。图嵌入是一种解决图分析问题的有效方法,其将原始图数据转换到低维空间并保留关键信息,从而提升节点分类、链接预测、节点聚类等下游任务的性能。与以往的研究不同,同时对静态图和动态图嵌入文献进行全面回顾,提出一种静态图嵌入和动态图嵌入通用分类方法,即基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器的图嵌入、基于图神经网络(GNN)的图嵌入和基于其他方法的图嵌入。其次,对静态图和动态图方法的理论相关性进行分析,对模型核心策略、下游任务和数据集进行全面总结。最后,提出了四个图嵌入的潜在研究方向。

关键词: 图嵌入, 静态图嵌入, 动态图嵌入, 随机游走, 图神经网络(GNN)

CLC Number: