计算机科学与探索, 2022, 16(1): 59-87 DOI: 10.3778/j.issn.1673-9418.2104020

综述·探索

图嵌入模型综述

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

1.中国人民公安大学 信息网络安全学院,北京 100038

2.天津市公安局河西分局 科技信息化支队,天津 300202

3.天津市公安局河东分局 科技信息化支队,天津 300171

4.中国人民公安大学 新型犯罪研究中心,北京 100038

Graph Embedding Models: A Survey

YUAN Lining1, LI Xin2, WANG Xiaodong3, LIU Zhao,4,+

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

通讯作者: + E-mail:liuzhao@ppsuc.edu.cn

收稿日期: 2021-04-8   修回日期: 2021-09-7  

基金资助: 中央高校基本科研业务费专项资金(2019JKF425)
国家重点研发计划(2018YFC0809800)

Received: 2021-04-8   Revised: 2021-09-7  

Fund supported: Fundamental Research Funds for the Central Universities of China(2019JKF425)
National Key Research and Development Program of China(2018YFC0809800)

作者简介 About authors

袁立宁(1995—),男,硕士研究生,CCF学生会员,主要研究方向为机器学习、图神经网络等。

YUAN Lining, born in 1995, M.S. candidate, student member of CCF. His research interests include machine learning, graph neural network, etc.

李欣(1987—),男,硕士,主要研究方向为机器学习、公安信息化等。

LI Xin, born in 1987, M.S. His research interests include machine learning, policing information system, etc.

王晓冬(1980—),男,中级工程师,主要研究方向为警务大数据、技术侦查等。

WANG Xiaodong, born in 1980, intermediate engineer. His research interests include police big data, technical investigation, etc.

刘钊(1981—),男,博士,讲师, 主要研究方向为机器学习、计算机视觉。

xml:lang="en"LIU Zhao, born in 1981, Ph.D., lecturer. His research interests include machine learning and computer vision.

摘要

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

关键词： 图嵌入; 静态图嵌入; 动态图嵌入; 随机游走; 图神经网络（GNN）

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.

Keywords： graph embedding; static graph embedding; dynamic graph embedding; random walk; graph neural networks (GNN)

PDF (28772KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

袁立宁, 李欣, 王晓冬, 刘钊. 图嵌入模型综述[J]. 计算机科学与探索, 2022, 16(1): 59-87 DOI:10.3778/j.issn.1673-9418.2104020

YUAN Lining, LI Xin, WANG Xiaodong, LIU Zhao. Graph Embedding Models: A Survey[J]. Journal of Frontiers of Computer Science & Technology, 2022, 16(1): 59-87 DOI:10.3778/j.issn.1673-9418.2104020

图是复杂系统中常用的信息载体,可以表示现实中许多复杂关系,如社交网络[1]、犯罪网络[2]、交通网络[3]等。图结构作为一种非欧几里德数据,很难直接应用卷积神经网络（convolutional neural network,CNN）[4]和循环神经网络（recurrent neural network,RNN）[5]等深度学习方法[6]。为了构造用于图数据挖掘的特征表示,图嵌入将节点映射到低维空间,生成保留原始图中某些重要信息的低维向量。目前,图嵌入不仅在节点分类[7]、链接预测[8]、节点聚类[9]、可视化[10]等复杂网络上的机器学习任务中获得成功,还广泛用于社交影响力建模[11]、内容推荐[12]等现实任务。

早期的图嵌入算法主要用于数据降维,通过邻域关系构建相似度图,将节点嵌入低维向量空间,并保持相连节点向量的相似性。这类方法通常时间复杂度高,很难扩展到大型图上。近年来,图嵌入算法转向扩展性强的方法。例如,矩阵分解方法[13]使用邻接矩阵的近似分解作为嵌入;随机游走法[14]将游走序列输入到Skip-Gram[15]生成嵌入。这些方法利用图的稀疏性降低了时间复杂度。当前,很多综述[16,17,18,19,20,21]对图嵌入方法进行了归纳与总结,但存在两大局限：一是部分综述仅涉及传统方法介绍,许多新模型没有纳入研究;二是这些综述只关注静态图嵌入或动态图嵌入,忽略了二者之间的关联性。

本文对图嵌入方法进行全面系统性综述,有以下三方面的贡献：（1）提出一种新的图嵌入分类法,同时对静态图和动态图方法进行分类;（2）对现有模型进行系统性分析,为理解现有方法提供新视角;（3）提出了四个图嵌入的潜在研究方向。

1 图嵌入相关定义及符号表示

1.1 问题定义

定义1（图） 图通常表示为 G=(V,E),其中 V表示节点集, E表示边集。

定义2（静态图） 给定图 G=(V,E),如果节点和边的状态不随时间变化,图 G为静态图。

定义3（动态图） 动态图可以按时间分成一系列演化图 G=(G1,G2,⋯,GT),T表示演化图的数量。每个演化图 Gt=(Vt,Et)表示节点和边在 t时刻的状态。动态图包含快照型和连续时间型（见图1）。快照型动态图按时间序列将动态图分解为等间隔的静态图;连续时间型用多个时间戳标记每条边来保留节点间的连接变化。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1   快照型和连续时间型动态图

Fig.1   Snapshot and continuous-time dynamic graphs


定义4（一阶相似度） 一阶相似度描述节点之间的成对邻近度。如果节点 vi和 vj之间存在一条边, vi和 vj的一阶相似度为边权重 wij;如果在 vi和 vj之间没有边,一阶相似度为0。

定义5（二阶相似度） 二阶相似度描述节点邻域结构的相似度。假设 wi=[wi1,wi2,⋯,win]表示节点 vi与其他节点的一阶相似度,那么 vi和 vj的二阶相似度由 wi和 wj的相似程度决定。

定义6（图嵌入） 图嵌入将每个节点映射成低维向量表示（见图2）,同时保留了原始图中某些关键信息。映射函数通常定义为 f:vi→Yi∈Rd,其中 d为嵌入向量的维度。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2   图嵌入的一般过程

Fig.2   General framework for graph embedding


1.2 符号表示

本文常用符号及其定义见表1。

表1   符号及定义

Table 1  Symbols and definitions

符号说明
A邻接矩阵
D顶点度矩阵
L拉普拉斯矩阵
X特征矩阵
S相似度矩阵
W系数矩阵
G静态图
$\mathcal{G}$动态图
V节点集
E边集
d嵌入维度
Y嵌入表示

新窗口打开| 下载CSV


2 图嵌入分类

本章提出一种新的分类方法,用于现有图嵌入模型的分类。按照模型所使用的算法原理将静态图和动态图模型同时分为五大类：基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器[22]的图嵌入、基于图神经网络（graph neural networks,GNN）[23]的图嵌入和基于其他方法的图嵌入。图3为分类思路及内容体系构建,图4为图嵌入模型的分类汇总。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3   图嵌入内容体系

Fig.3   Content system of graph embedding


图4

新窗口打开| 下载原图ZIP| 生成PPT

图4   图嵌入模型分类汇总

Fig.4   Categorization and summary of graph embedding models


2.1 基于矩阵分解的图嵌入

基于矩阵分解的图嵌入通过分解节点关系矩阵获得低维嵌入。不同的关系矩阵采用的分解方法不同,例如邻接矩阵通常使用奇异值分解（singular value decomposition,SVD）的方法生成节点嵌入,而属性矩阵通常使用特征值分解的方法。

2.1.1 基于矩阵分解的静态图嵌入

基于矩阵分解的静态图嵌入模型对节点关联信息矩阵和属性信息矩阵进行特征分解,然后将分解得到的属性嵌入和结构嵌入进行融合,生成节点的低维嵌入表示。图5说明了矩阵分解和静态图嵌入生成的一般过程。

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5   基于矩阵分解的静态图嵌入模型框架

Fig.5   Framework of eigenvalue factorization in static graph embedding


局部线性映射（locally linear embedding,LLE）[24]将每个节点表示为相邻节点的线性组合,构造邻域保持映射（见图6）。具体实现分为三步：（1）以某种度量方式（如欧氏距离）选择k个邻近节点;（2）由k个近邻线性加权重构节点,并最小化节点重建误差获得最优权重;（3）最小化最优权重构建的目标函数生成 Y。目标函数的表达式为：

L=∑|Yi-∑WijYj|2

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6   LLE步骤

Fig.6   Steps of LLE


式中, Wij为节点 i与节点 j的权重系数。作为一种重要的降维算法,LLE在降维时能够保持样本的局部特征,并通过稀疏矩阵特征分解的方式适当降低了计算复杂度。但是,该模型对k值的选择十分敏感,对最终的降维结果有极大影响。

许多图分解和重构的目标函数都使用节点向量来确定边的建立。GF（graph factorization）[13]假设边的存在信息可以由节点向量内积 Yi,Yj有效地捕捉。为了获得嵌入,GF对邻接矩阵进行分解,并利用均值方差和L2正则项构建目标函数：

L=12∑(Aij-Yi,Yj)2+λ2∑Yi2

由上式特性可知,在节点数量较多、嵌入维度较大时,模型计算会产生极大的内存占用。为此,GF设计了一种最小化簇外一阶邻居数量的图分割算法,保证图结构信息无损,提升模型计算效率。

GraRep[25]分别构建1到k步的对数转移概率矩阵 {T1,T2,⋯,Tk},将 Tk中所有负值元素替换为0,使 Tk为正k步对数转移概率矩阵,以减少噪声[26]。最后,使用SVD分解 Tk得到节点表示 Yk,并将 {Y1,Y2,⋯,Yk}进行合并,得到最终嵌入 Y。GraRep能够在嵌入中整合全局结构信息,但训练过程中涉及矩阵运算和SVD,计算复杂度极高,难以扩展到大规模图数据。

非对称传递性可以刻画有向边之间的关联,有助于捕捉图的结构。为了保留有向图中的非对称传递性,HOPE[27]采用了一种保持高阶相似度的嵌入方法,在保留非对称传递性的向量空间中生成图嵌入（见图7）,训练中使用L2范数进行优化：

L=S-YsYtTF2

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7   HOPE模型框架

Fig.7   Framework of HOPE


式中, Ys为源嵌入, Yt为目标嵌入。许多相似性度量可以反映非对称传递性,如Katz指标[28]、Adamic-Adar分数等,用于构建相似度矩阵 S。此外,HOPE使用广义SVD（generalized singular value decomposition,GSVD）[29]分解 S,适当降低了计算复杂度,但是低阶GSVD逼近能力有限,限制了模型表达能力。

在原始图上,本征图用于保留节点间有利关联,惩罚图用于保留节点间的不利关联。为了综合本征图和惩罚图的特点,NGE（non-negative graph embedding）[30]引入非负矩阵分解（non-negative matrix factorization,NMF）[31]生成嵌入表示。NMF将数据矩阵分解成低阶非负基矩阵 W和非负系数矩阵 Y,并使用L1损失作为目标函数。在此基础上,NGE将 Y和 W分成两部分： Y=[Y1,Y2];W=[W1,W2]。由于 (W1,Y1)和 (W2,Y2)是互补空间,可以通过叠加的方式重构原始数据, Y2的目标函数可以由惩罚图目标函数进行转换。将NMF的L1损失和 Y1和 Y2目标函数相结合,可得NGE的目标函数为：

$L={{\sum\limits_{i\ne j}{\left\| y_{i}^{1}-y_{j}^{1} \right\|}}^{2}}{{A}_{ij}}+{{\sum\limits_{i\ne j}{\left\| y_{i}^{2}-y_{j}^{2} \right\|}}^{2}}A_{ij}^{p}+\lambda \left\| V-WY \right\|$

式中, Y1=[y11,y21,⋯,yN1]表示生成的低维嵌入, Y2=[y12,y22,⋯,yN2], λ表示平衡图嵌入和数据重构的正值参数。NGE提出了非负图嵌入的通用公式,并且同时使用本征图和惩罚图能够有效重构原始数据,但是该模型的计算成本相对较高,不能在保持非负性更新规则的同时显式控制基矩阵的稀疏性。

拉普拉斯特征映射（Laplacian eigenmaps,LE）[32]与LLE相似,也是从局部近似的角度构建数据之间的关系。具体而言,LE使用邻接矩阵建立包含局部结构信息的嵌入表示,并要求相连节点在嵌入空间中尽可能地靠近。因此,LE的目标函数为：

L=∑Aij|yi-yj|2

由上式可知,LE的目标函数强调权值大的节点对,弱化权值小的节点对,导致原始图中的局部拓扑结构被破坏。为了增强图嵌入的局部拓扑保持性,柯西图嵌入（Cauchy graph embedding,CGE）[33]引入距离的反函数来保持节点在嵌入空间中的相似关系。因此,CGE将LE的目标函数改写为：

L=∑Aij|yi-yj|2+σ2

相比LE,CGE的目标函数更加强调短距离,即确保局部越邻近的节点在嵌入空间的距离越接近。

为了保持图的全局拓扑结构,SPE（structure preserving embedding）[34]通过一组线性不等式学习包含节点连接关系的低阶核矩阵获得嵌入表示。SPE以核矩阵 K为输入,使用连接算法f输出关系矩阵 A˜=f(K)。通过比较邻接矩阵 A与关系矩阵 A˜的差值可以评估 K产生的嵌入对图结构信息的保留程度。与LE相比,SPE在图的可视化以及无损压缩方面有显著提升,证明了在降维算法中引入结构保持约束可以更加准确地表示高维数据。

2.1.2 基于矩阵分解的动态图嵌入

从矩阵分解的角度看,图的动态演化实质上是原始矩阵的不断变化。基于矩阵分解的动态图方法利用特征分解构造图的高阶相似度矩阵,然后利用矩阵摄动理论[35]更新图的动态信息。矩阵摄动理论可以高效更新图的高级特征对,同时避免了每个时刻的重新计算嵌入矩阵。图8是基于矩阵分解的动态图嵌入的一般过程。

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8   基于矩阵分解的动态图嵌入模型框架

Fig.8   Framework of matrix factorization in dynamic graph embedding


DANE[36]采用分布式框架（见图9）：离线部分,采用最大化相关性[37]的方法,引入 pAt和 pXt使拓扑嵌入 YAt和特征嵌入 YXt投影后的相关性最大化,捕捉图结构和节点属性的依赖关系,然后将前 d个特征向量进行拼接,保持 YAt和 YXt在表示上一致;在线部分,使用矩阵摄动理论更新嵌入的特征值和特征向量。在 t时刻,DANE对拓扑结构和节点属性进行谱图嵌入;在 t+1时刻,DANE使用矩阵摄动理论更新 YA和 YX生成新的嵌入。DANE有效捕捉了拓扑结构和节点属性的相关性,保留了图的动态信息,但模型的在线部分仅使用一阶矩阵摄动理论更新嵌入表示,并未考虑图的高阶相似性。

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9   DANE模型结构

Fig.9   Framework of DANE


DHPE[38]同样采用分布式框架：静态部分,DHPE与HOPE相似,将GSVD分解Katz相似度矩阵转换为广义特征值问题[39],使每个时刻生成的低维嵌入保留节点的高阶相似度;动态部分,DHPE使用矩阵摄动理论更新GSVD的结果。此外,模型假设图中节点数恒定（添加或删除的节点为孤立节点）,使每个时刻图的变化转化为边的变化。DHPE能够在保持高阶相似性的同时更新节点嵌入,其增量计算方案有效提升了动态模型的计算效率。

Chen等人[40]提出了TRIP和TRIP-BASIC两种在线算法跟踪动态图的特征对,其核心思路是利用矩阵摄动理论对图的特征对进行更新。TRIP和TRIP-BASIC引入图中三角形个数[41,42]作为属性信息构建特征函数,然后将特征对映射成属性向量。上述模型能够有效追踪特征对、三角形个数和鲁棒性分数随时间的动态变化,但是模型的误差会随着时间推移不断积累。

由于增量矩阵的更新采用近似值的方式,导致生成嵌入的过程中误差不断积累。为解决上述问题,TIMERS[43]采用SVD最大误差界重启算法,设置SVD重新启动时间,减少时间上的误差积累。该模型的核心包含两部分：（1）增量更新,通过函数f近似地更新前一时刻的结果;（2）SVD重启,通过设置误差阈值,确定执行SVD重启时刻,重新计算最优SVD结果,并最小化重启次数。

MF[44]通过构造携带重要特征的矩阵因子,使潜在的NMF特征有效地表达动态信息。为了充分利用不同时刻的拓扑信息,MF对嵌入空间的邻接关系矩阵进行整合,找到在各个时刻一致的嵌入矩阵 Y*和系数矩阵 W*,并通过最小化Frobenius范数使各时刻 Yt和 Y*、 Wt和 W*差异最小。基于NMF加权表示相似性指数的MF比基于静态表示相似性指数的方法具有更好的性能。

DWSF[45]采用使用Semi-NMF[46]和弱监督分解（weakly supervised factorization,WSF）[47],将数据矩阵 X分解为标签矩阵 M和嵌入矩阵 Y(X=MY,其中 M是非负的, X和 Y没有约束）,然后使用标签传播（label propagation）算法[48]初始化标签矩阵因子,将类标签从有标签的数据实例传播到无标签的数据实例,最后将控制信息量的平滑度项与Semi-NMF相结合,优化模型参数生成嵌入。DWSF将有限的监督信息合并为类别标签,在每次迭代中动态更新,大幅提升了模型在分类任务上的表现。

2.2 基于随机游走的图嵌入

受word2vec[15]的启发,基于随机游走的图嵌入方法将节点转化为词,将随机游走序列作为句子,利用Skip-Gram生成节点的嵌入向量。随机游走法可以保留图的结构特性,并且在无法完整观察的大型图上仍有不错的表现。

2.2.1 基于随机游走的静态图嵌入

基于随机游走的静态图嵌入模型通过随机游走获得训练语料库,然后将语料库集成到Skip-Gram获得节点的低维嵌入表示。

Deepwalk[49]使用随机游走对节点进行采样,生成节点序列,再通过Skip-Gram最大化节点序列中窗口 w范围内节点之间的共现概率,将节点 vj映射为嵌入向量 Yj（见图10）：

图10

新窗口打开| 下载原图ZIP| 生成PPT

图10   Deepwalk模型结构

Fig.10   Framework of Deepwalk


maxlnPrvj-w,⋯,vj-1,vj+1,⋯,vj+wYj

生成的嵌入 Y将节点之间的关系编码在低维向量空间,用于捕捉邻域相似性和社区结构,学习节点的潜在特征。Deepwalk不仅在数据量较少时有较好的表现,还可以扩展到大型图的表示学习。由于优化过程中未使用明确的目标函数,使得模型保持网络结构的能力受到限制。

node2vec[50]在Deepwalk的基础上,引入有偏的随机游走（见图11）,增加邻域搜索的灵活性,生成质量更高、信息更多的嵌入表示。通过设置 p和 q两个参数,平衡广度优先搜索（breadth-first sampling,BFS）和深度优先搜索（depth-first sampling,DFS）策略,使生成的嵌入能够保持社区结构等价性或邻域结构等价性。虽然node2vec能够保持更多的一阶相似度和二阶相似度信息,但仍然缺少明确的目标函数来保持全局网络结构。

图11

新窗口打开| 下载原图ZIP| 生成PPT

图11   node2vec中的随机游走过程

Fig.11   Random walk procedure in node2vec


Deepwalk和node2vec采用随机游走探索节点局部邻域,使得学习到的低维表示无法保留图的全局结构,同时使用随机梯度下降求解非凸的目标函数,使生成的嵌入可能陷入局部最优解。为了解决上述问题,HARP[51]将原始图中的节点和边递归地合并在一起,得到一系列结构相似的压缩图。这些压缩图有不同的粒度,提供了原始图全局结构的视图。从最粗略的形式开始,每个压缩图学习一组嵌入表示,并用于初始化下一个更细化的压缩图的嵌入。HARP能够与Deepwalk和node2vec结合使用,提升原始模型性能,生成信息更丰富的嵌入表示。

利用分层Softmax,Deepwalk目标函数可以改写为矩阵分解的形式[52]：

Mij=ln[ei(A+A2+⋯+Ak)]jk

式中, Mij是以节点 i为起点 j为终点的长度为 k的路径期望值; ei是one-hot向量,其第 i个元素为1其余元素为0, Ak的不同幂次代表了不同的尺度。可见Deepwalk已经隐式地建模了从1到 k阶的多尺度依赖关系,但无法单独访问不同尺度。为了显式地构建k阶关系,Walklets[53]修改了Deepwalk的采样过程,在随机游走序列上跳过 k-1个顶点。除此之外,模型的优化和嵌入生成方式均与Deepwalk相同。相较于Deepwalk,Walklets能够捕获节点与社区之间不同尺度的层次结构,进而显式建模多尺度关系,保留更丰富的节点从属关系信息。

TriDNR[54]是首个利用标签信息进行表示学习的深层神经网络模型,能够同时利用网络结构、节点特征和节点标签学习节点嵌入表示（见图12）。具体而言,TriDNR使用两个神经网络来捕获节点-节点、节点-单词、标签-单词之间的关系。对于网络结构,通过随机游走序列最大化共现概率来保持图中节点间的邻近关系;对于节点特征,通过最大化给定节点的单词序列的共现概率捕获节点与单词的相关性;对于节点标签,通过最大化给定类别标签的单词序列的概率建模标签与单词的对应关系。最后,使用耦合神经网络的算法将三部分信息合并为节点嵌入。

图12

新窗口打开| 下载原图ZIP| 生成PPT

图12   TriDNR模型结构

Fig.12   Architecture of TriDNR model


2.2.2 基于随机游走的动态图嵌入

基于随机游走的动态图嵌入模型将每条边与对应时刻相关联,使随机游走序列由一系列包含递增时刻的边所连接的节点构成,最后利用Skip-Gram模型将每个节点映射成 d维向量。

Sajjad等人[55]将图嵌入的生成过程分为两步：首先,更新动态图上的随机游走序列。与直接在静态快照上从头开始随机游走相比,更新算法保持了随机游走的统计特性。然后,在给定前一时刻的嵌入表示以及更新后的随机游走序列的条件下,利用Skip-Gram模型对嵌入表示进行更新。CTDNE[56]则利用时间随机游走从连续型动态图中学习包含时间信息的嵌入表示。实际上,CTDNE采用的时间随机游走与静态图方法相似,但约束每个随机游走符合边出现的时间顺序,即边的遍历必须按照时间递增的顺序,由于每条边包含多个时间戳,使得同一节点可能在游走中出现多次。时间信息的引入减少了嵌入的不确定性,使CTDNE在众多任务上的表现优于Deepwalk和node2vec等静态模型。

在动态图中应用静态方法存在两大问题：（1）对每个快照都进行随机游走非常耗时;（2）不同快照的嵌入空间并不一致。为解决上述问题,Mahdavi等人在node2vec的基础上,提出了动态图嵌入模型dynnode2vec[57]。该模型在快照G1上运行node2vec获得嵌入向量以及训练后的Skip-Gram模型。对于后续快照,在两个连续快照之间执行以下步骤：（1）为演化节点生成随机游走序列;（2）使用动态Skip-Gram[58]将前一时刻学习到的嵌入作为初始权值,结合演化节点的随机游走生成当前时刻嵌入。由于动态图是逐渐演化的,即大多数节点的邻域保持不变,dynnode2vec仅对演化节点进行随机游走大幅提升了模型效率。

STWalk[59]是一种无监督节点轨迹学习算法,通过捕捉给定时间窗口内节点变化生成嵌入表示。该模型将当前时刻快照上的随机游走定义为空间游走,过去时刻快照上的随机游走定义为时间游走,从而捕捉节点的时空行为,然后利用Skip-Gram生成节点轨迹的嵌入表示。STWalk有两种不同的变体：STWalk1同时考虑空间游走和时间游走来学习嵌入表示;STWalk2将空间游走和时间游走建模为两个子问题并分别求解,然后组合两个结果获得最终的嵌入表示。上述模型仅使用图的结构信息学习捕获节点轨迹时空特性的低维嵌入,未考虑节点特征和标签信息。

Deepwalk和node2vec模仿单词嵌入作为节点嵌入表示,而tNodeEmbed[60]模仿句子嵌入[61]作为节点嵌入表示。句子中每个单词不仅代表节点随时间变化的向量,还捕捉了节点角色和连接关系的动态变化。为此,tNodeEmbed使用联合损失函数优化两个目标：（1）三维特征空间中节点的静态邻域;（2）图的动态特性。tNodeEmbed使用node2vec对节点嵌入进行初始化,将不同时刻的节点表示进行对齐,然后根据给定的图分析任务和过去时刻的节点嵌入联合学习,使生成的嵌入既保留图的结构和动态信息,又适用于特定任务。

2.3 基于自编码器的图嵌入

自编码器（autoencoder,AE）[62]是一种人工神经网络,包含编码器和解码器两部分,用于无监督地构造输入数据的向量表示。通过对数据中的非线性结构进行建模,自编码器使隐藏层学习到的表示维度小于输入数据,即对原始数据进行降维。基于自编码器的图嵌入方法使用自编码器对图的非线性结构建模,生成图的低维嵌入表示。

2.3.1 基于自编码器的静态图嵌入

基于自编码器的图嵌入方法起源于使用稀疏自编码器的GraphEncoder[63]。其基本思想是将归一化的图相似度矩阵作为节点原始特征输入到稀疏自编码器中进行分层预训练,使生成的低维非线性嵌入可以近似地重建输入矩阵并保留稀疏特性：

Encoder:Y=f(X)Decoder:Xˆ=g(Y)

式中, X={xi}i=1N表示输入矩阵, Xˆ={xˆi}i=1N表示重构的输出矩阵, f(·)是编码器, g(·)是解码器。简言之,GraphEncoder将输入矩阵 X的信息压缩到低维嵌入 Y中,并利用L2重建损失对 Y进行优化。稀疏自编码器降低了计算复杂度,相较之前常用的谱聚类方法,具有灵活高效的特性。

SDNE[64]利用深度自编码器以及图的一阶、二阶相似度,捕获高度非线性的网络结构。SDNE包含有监督组件和无监督组件（见图13）,用于保持节点的一阶和二阶相似度。有监督组件引入拉普拉斯特征映射作为一阶相似度的目标函数,使生成的嵌入捕获局部结构信息。无监督组件修改L2重建损失函数作为二阶相似度的目标函数,使生成的嵌入捕获全局结构信息。对一阶和二阶相似度联合优化,增强了模型在稀疏图上的鲁棒性,使生成的嵌入同时保留全局和局部结构信息。

图13

新窗口打开| 下载原图ZIP| 生成PPT

图13   SDNE模型结构

Fig.13   Framework of SDNE


DNGR[65]生成低维嵌入的过程主要分为三步：（1）利用随机冲浪模型捕捉图的结构信息,并生成共现概率矩阵;（2）利用共现概率矩阵计算正逐点互信息（positive pointwise mutual information,PPMI）矩阵[66];（3）将PPMI矩阵输入堆叠去噪自编码器（stacked denoising autoencoder,SDAE）生成低维嵌入表示。相较于随机游走,随机冲浪直接获取图的结构信息,克服了原有采样过程的限制;PPMI矩阵能够保留图的高阶相似度信息;堆叠结构使隐层维度平滑递减,提升深层架构学习复杂特征的能力,同时去噪策略增强了模型的鲁棒性。

DNE-APP[67]利用半监督堆叠式自编码器（stacked autoencoder,SAE）生成保留k阶信息的低维嵌入主要分为两步：（1）使用PPMI度量和k步转移概率矩阵,生成包含k阶信息的相似度聚合矩阵。（2）使用SAE重构相似度聚合矩阵,学习低维非线性嵌入表示。与仅保持一阶和二阶相似度的SDNE相比,DNE-APP模型可以保持不同的k阶相似度;与仅重建高阶相似度的DNGR相比,DNE-APP在重建过程中引入了成对约束,使相似节点在嵌入空间更加接近。

变分自编码器（variational autoencoder,VAE）[68]是用于降维的生成式模型,其优势为容忍噪声和学习平滑的表示。VGAE[69]首先引入VAE学习可解释的无向图嵌入表示。模型的编码器部分使用图卷积网络（graph convolutional network,GCN）[70]：

$\begin{align} & q(Y|X,A)=\overset{N}{\mathop{\underset{i=1}{\mathop{\prod }}\,}}\,q({{y}_{i}}|X,A), \\ & \text{with}q({{y}_{i}}|X,A)=N({{y}_{i}}|{{\mu }_{i}},\text{diag}\left( \delta _{i}^{2} \right)) \\ \end{align}$

式中, μ=GCNμ(X,A)是均值向量 μi的矩阵,同样 lnδ=GCNμ(X,A)为方差向量。模型的解码器部分使用嵌入的内积：

$\begin{align} & p(A|Y)=\overset{N}{\mathop{\underset{i=1}{\mathop{\prod }}\,}}\,\overset{N}{\mathop{\underset{j=1}{\mathop{\prod }}\,}}\,p({{A}_{ij}}|{{y}_{i}},{{y}_{j}}), \\ & \text{with}p({{A}_{ij}}=1|{{y}_{i}},{{y}_{j}})=\sigma \left( y_{i}^{\text{T}}{{y}_{j}} \right) \\ \end{align}$

式中, σ(·)是sigmoid函数。最后,VGAE通过最小化重构损失和变分下界对模型进行优化：

L=Eq(Y|X,A)[lnp(A|Y)]-KL[q(Y|X,A)|pY

式中, KL[q(·)||p(·)]为 q(·)和 p(·)的 KL散度[71], p(Y)为高斯先验。

Salha等人提出的Linear-VGAE模型[72]使用基于归一化邻接矩阵的简单线性模型替换VGAE中的GCN编码器：

μ=A˜XWμandlnσ=A˜XWσ

式中, A˜为归一化的邻接矩阵, Wμ和 Wσ为权重矩阵。Linear-VGAE仅使用归一化邻接矩阵和两个权重矩阵生成嵌入表示,未使用激活函数,降低了编码器复杂度。通过对比VGAE模型性能,证明简单的线性节点编码方案同样有效。

与一般的非对称模型不同,GALA[73]采用完全对称的图卷积自编码器模型生成图的低维嵌入表示。在对输入矩阵重构的过程中,编码器执行的拉普拉斯平滑[74]与解码器的拉普拉斯锐化[75]相对称。与现有的VGAE方法不同,为了使解码器可以直接重构节点的特征矩阵,GALA使用谱半径为1的拉普拉斯锐化表示。相较于仅使用GCN编码器的模型,GALA的对称结构,能够在编码和解码过程中同时使用结构信息和节点特征。

ANE[76]使用对抗性自编码器[77]生成捕获高度非线性结构信息的低维嵌入。具体而言,ANE利用一阶和二阶相似度捕捉图的局部和全局结构,使生成的嵌入可以保持高度的非线性,同时训练过程对抗性自编码器的两个准则：一是基于重建误差的自编码器训练准则;二是将嵌入表示的聚合后验分布与任意先验分布匹配的对抗性训练准则。通过施加对抗性正则化,ANE改善了嵌入生成过程中的流形断裂问题,提升了低维嵌入的表示能力。

2.3.2 基于自编码器的动态图嵌入

基于自编码器的动态图方法将每个时刻训练的参数作为下一时刻自编码器的初始值,从而在一定程度上保持生成嵌入的稳定性,节省模型的训练时间,提高模型的计算效率。

受SDNE的启发,Goyal等人提出了快照型动态图嵌入模型DynGEM[78]（见图14）。该模型使用深度自编码器将输入数据映射到高度非线性的低维嵌入空间,以捕捉任一时刻快照中节点的连接趋势,同时下一个时刻的嵌入模型直接继承前一个时刻的训练参数,使t时刻的快照嵌入可以利用 t-1时刻快照嵌入进行增量的学习。由于动态图中节点的数量不断变化,DynGEM设计了一种可动态调节神经网络中神经元个数、隐层层数的方法PropSize。在训练过程中,DynGEM结合一阶相似度和二阶相似度保留局部结构信息和全局结构信息,同时引入L1和L2正则化进一步提升模型性能。需要注意的是DynGEM不强加保持相邻时刻嵌入接近的显式正则化,即相邻时刻的快照如果明显不同,则相应的编码函数 ft-1和 ft也有所不同。

图14

新窗口打开| 下载原图ZIP| 生成PPT

图14   DynGEM模型结构

Fig.14   Framework of DynGEM


DynGEM生成当前时刻嵌入时只捕获了前一时刻的信息,致使大量历史信息被忽略,为此Goyal等人提出了另一个基于自编码器的动态图嵌入模型dyngraph2vec[79]。该模型将之前l个时刻的图结构信息作为输入,将当前时刻生成图嵌入作为输出,从而捕获当前时刻与之前多个时刻节点之间的非线性交互信息。该模型有三种变体（见图15）：dyngraph-2vecAE以一种简单的方式对自编码器进行扩展;dyngraph2vecRNN和dyngraph2vecAERNN使用长短期记忆网络（long short-term memory,LSTM）[80]对历史信息编码。在动态图的演化过程中,dyngraph2vec仅使用相邻节点,未考虑图的高阶相似度信息。

图15

新窗口打开| 下载原图ZIP| 生成PPT

图15   dyngraph2vec变体结构

Fig.15   Variations of dyngraph2vec


随着动态图的演化,NetWalk[81]可以增量地学习网络表示（见图16）。具体而言,NetWalk利用初始的动态图上提取的多个游走序列以及深度自编码器的隐藏层生成节点嵌入表示。在训练过程中,NetWalk联合最小化游走序列中成对节点的表示距离和自编码器的重构误差,使学习到的嵌入表示既可以实现局部拟合,又可以实现全局正则化。NetWalk对生成到的嵌入表示使用动态聚类模型,能够标记图中异常[82,83]的节点或边。

图16

新窗口打开| 下载原图ZIP| 生成PPT

图16   NetWalk异常检测的流程

Fig.16   Workflow of NetWalk for anomaly detection


BurstGraph[84]将动态图的演化分为一般演化和突发演化,并使用两个基于RNN的VAE分别对每个时刻的演化信息进行建模。在编码器部分,两个自编码器共同使用GraphSAGE[85]学习到的节点特征和拓扑结构信息。对于突发演化,BurstGraph在VAE中引入了spike & slab分布[86]作为近似后验分布;对于一般演化,BurstGraph使用原始的VAE模型。为了充分利用图的动态信息,BurstGraph使用RNN捕捉每个时刻的图结构,将一般演化和突发演化信息保留在RNN状态单元中,并随时间的推移不断更新状态单元。由于生成的嵌入中保留了突发信息,BurstGraph常用于关于图的异常检测中的突发检测[87,88]任务。

动态图嵌入通常存在三方面的局限性：（1）嵌入表示空间[89,90],欧式空间表示可能导致图的潜在层次结构失真;（2）动态信息,忽视图的动态演化通常会导致模型错误地利用未来信息来预测过去的交互;（3）不确定性[91],图的固有特性,生成的确定性表示不能对不确定性建模。为了解决上述问题,HVGNN[92]采用双曲变分GNN对双曲空间中的动态图进行建模,使生成的嵌入同时包含图的动态信息和不确定性。具体而言,HVGNN使用双曲空间代替欧式空间,同时引入新的时间GNN（temporal GNN,TGNN）来建模动态特性。为了建模图的不确定性,HVGNN设计了一个基于TGNN的双曲VGAE,使模型可以对不确定性和动态进行联合建模。最后,引入的重参数化采样算法,实现模型的梯度学习。相较于欧式空间计算量的指数增长,双曲空间降低了模型的计算复杂度;对于不确定性的建模,增强了传递较少信息且具有较多动态特性节点的表示性能。

2.4 基于图神经网络的图嵌入

图神经网络（GNN）是专门处理图数据的深度模型,其利用节点间的消息传递来捕捉某种依赖关系,使生成的嵌入可以保留任意深度的邻域信息。由于GNN模型强大的表示能力,嵌入模型的性能得到了显著提升。

2.4.1 基于图神经网络的静态图嵌入

基于GNN的静态图模型聚合节点邻域的嵌入并不断迭代更新,利用当前的嵌入及上一次迭代的嵌入生成新的嵌入表示。通过多次迭代,GNN模型学习到的嵌入可用于表征全局结构。

GCN使用节点特征矩阵 X与邻接矩阵 A生成包含节点的特征信息的嵌入表示（见图17）。对于多层GCN,层间传播公式为：

H(l+1)=σD˜-12A˜D˜-12HlWl

图17

新窗口打开| 下载原图ZIP| 生成PPT

图17   多层GCN结构

Fig.17   Framework of multi-layer GCN


其中, A˜=A+I, D˜为 A˜的度矩阵, σ(·)为激活函数, H(·)为各层激活矩阵,且 H(0)为 X。为了提高层间传播效率,GCN使用图上谱卷积一阶近似[93,94]。对于双层GCN模型,其前向传播公式为：

Y=f(X,A)=σ1Aˆσ0AˆXW0W1

其中, Aˆ=D˜-12A˜D˜-12。最终,GCN使用神经网络模型 f(X,A)对图结构进行编码,生成高质量的嵌入表示。GCN的优点在于结构信息能够在各层之间共享,缺点在于扩展性相对较差,因为训练过程执行全批次梯度下降收敛较慢,导致模型难以扩展到大规模 网络。

GCN通常应用于固定图的直推式表示学习,GraphSAGE将其扩展到归纳式无监督学习的任务中,利用节点特征（例如文本属性、节点度）学习不可见节点的嵌入表示。GraphSAGE不是为每个节点训练单独的嵌入,而是通过采样和聚合节点的局部邻域特征训练聚合器函数,同时学习每个节点邻域的拓扑结构及特征分布,生成嵌入表示（见图18）。相比GCN,GraphSAGE使用无监督损失函数强制邻近节点具有相似表示,远距离节点具有不同的表示。在给定下游任务的情况下,GraphSAGE能够替换或增加相应的目标函数,进行有监督或半监督学习,提升模型的灵活性;训练过程执行分批次训练,提升模型的收敛速度。

图18

新窗口打开| 下载原图ZIP| 生成PPT

图18   图解GraphSAGE采样和聚合方式

Fig.18   Visual illustration of GraphSAGE sampling and aggregation approach


图注意力网络（graph attention network,GAT）[95]在GCN的基础上引入注意力机制[96],对邻近节点特征加权求和,分配不同的权值。针对单个节点,GAT使用self-attention[97]获得注意力系数：

eij=aWhi,Whj

式中, eij表示的是节点 j对节点 i的重要性。GAT使用masked-attention[97]将注意力分配到节点i的邻域：

αij=exp(LeakyReLU(aT[Whi||Whj]))∑exp(LeakyReLU(aT[Whi||Whk]))

式中, a是层间的权重矩阵,||表示拼接运算。最后,使用multi-head attention[97]生成节点嵌入：

yi=σ1K∑k=1K∑αijkWkhj

式中, σ表示激活函数, K表示multi-head attention的头数, αk为第 k个self-attention。注意力参数全图共享,大幅减少了参数占用的存储空间,同时GAT对所有邻居节点进行采样,较GraphSAGE得到的嵌入更具表征性。GAT的缺点在于使用二阶以上邻居时,容易导致过度平滑。

用于图嵌入的GNN模型大多遵循邻域聚合架构,通过递归地聚合和变换邻域节点的特征向量生成节点嵌入,因此不能有效区分某些简单的图结构。为了提高GNN模型对图结构的辨识能力,图同构网络（graph isomorphism network,GIN）[98]利用GNN和WL（Weisfeiler-Lehman）图同构测试[99]之间的密切联系,使生成的嵌入保留图结构辨识信息。WL测试通过聚合给定节点邻居的特征向量对该节点进行迭代更新,同时使用内射聚合更新将不同的节点邻域映射为不同的特征向量。GIN采用与WL内射聚合相似的方式进行建模：首先,将节点邻居的特征向量抽象为一个多集;然后,将邻居聚合运算抽象为多集上的函数（多集函数的区分性越强,底层的表征能力就越强）;最后,将生成的嵌入用于图分类任务,其性能可以匹配WL测试的结果。

MF-GCN[100]是一种多滤波GCN模型（见图19）,在每个传播层使用多个局部GCN滤波器进行特征提取,使模型捕捉到节点特征的不同方面。对于第一层,MF-GCN对节点属性进行如下操作：

图19

新窗口打开| 下载原图ZIP| 生成PPT

图19   MF-GCN模型结构

Fig.19   Framework of MF-GCN


xN(i)l=α∑1D(i,i)D(j,j)xjWl

式中, xj是节点 j的特征向量, xN(i)l表示第 l个局部GCN生成的节点 i邻域低维嵌入, α为激活函数。将多个局部GCN生成的表示进行拼接生成节点邻域嵌入表示 yN(u)k,再与 k-1层的嵌入 yuk-1拼接即为第k层嵌入 yuk。MF-GCN使用的局部GCN和优化策略与GraphSAGE相似,关键的不同在于MF-GCN使用多个局部GCN获取节点特征不同方面的信息,使生成的嵌入保留更丰富的属性信息。

多数GCN模型中邻域相互作用项的系数相对较小,导致性能与采用线性策略的简化图卷积网络（simplified graph convolutional networks,SGC）[101]相当。为了有效捕捉图的复杂非线性,GraphAIR[102]同时对邻域聚合和邻域交互进行建模。GraphAIR由两部分组成：邻域聚合模块通过组合邻域特征来构建节点表示;邻域交互模块通过乘法运算显式建模邻域交互。现有的大多数GCN模型与GraphAIR兼容,可以提供即插即用的邻域聚合模块和邻域交互模块。此外,GraphAIR利用残差学习策略,将邻域交互与邻域聚合分离,使模型更容易优化。

SDGNN[103]是用于处理符号有向图的嵌入模型,其在传统GNN的基础上考虑了平衡理论[104]和地位理论[105],重新设计聚合器和损失函数。SDGNN聚合来自不同邻域的信息,并使用MLP（multilayer perceptron）将这些消息编码为节点嵌入。SDGNN的聚合器可分为两类：一是平均聚合器,二是注意力聚合器。为了优化生成的嵌入,SDGNN使用组合损失函数来重构网络中的符号、方向和三角形三个关键特征。平衡理论和地位理论的引入,使SDGNN在考虑边缘符号的同时兼顾方向信息,提升了模型在符号图分析任务中的表现。

2.4.2 基于图神经网络的动态图嵌入

基于GNN的动态图模型通常在静态图模型的基础上,引入一种循环机制更新网络参数,实现动态过程的建模,使生成低维嵌入可以有效保留图的动态演化信息。

DyRep[106]将动态图嵌入假设为图的动态（拓扑演化）和图上的动态交织演化（节点间的活动）的中介过程。DyRep采用关联和通信事件的形式接收动态信息,并基于以下原则捕获观察到的事件的影响,更新有关节点的表示：（1）自我传播。自我传播是支配单个节点演化的动力中最小的组成部分。节点相对于其先前位置在嵌入空间中演化,而不是以随机方式进化。（2）外源驱动。一些外力可以在某时间间隔平滑地更新该节点的当前特征。（3）局部嵌入传播。事件中涉及的两个节点形成临时（通信）或永久（关联）路径,用于信息从一个节点的邻域传播到另一个节点。DyRep采用双时间尺度来捕捉图级和节点级的动态过程,计算节点表示并参数化。最后,使用时间注意机制[95,107]耦合模型的结构和时间信息,使生成的节点嵌入可以捕获非线性的动态信息。DyRep作为一种归纳式学习模型,强调学习节点的表示方法而不是节点的固定表示,因此更利于新的节点表示的生成。

DySAT[108]通过邻域结构和时间两个维度的联合自注意力来计算节点嵌入,主体为三个模块（见图20）：（1）结构注意力块通过自注意聚集和堆叠从每个节点局部邻域中提取特征,以计算每个快照的中间表示并输入到时间模块;（2）时间自注意力块通过嵌入每个快照的绝对时间位置[109]来捕获排序信息,并将位置嵌入与结构注意力块的输出组合,输入到前馈层;（3）图上下文预测模块通过跨多个时间步长的目标函数保留节点的邻域信息,使生成的嵌入能够捕捉结构演化。DySAT的优点在于使用多头注意力 能够捕获动态性的多个方面,缺点在于该模型 仅适用于节点数恒定的动态图,并且节点共现率作为损失函数导致模型捕捉节点的动态变化的能力 有限。

图20

新窗口打开| 下载原图ZIP| 生成PPT

图20   DySAT模型结构

Fig.20   Framework of DySAT


动态图中节点可能频繁出现和消失,使得RNN在学习这种不规则的行为时非常具有挑战性。为了解决这个问题,EvolveGCN[110]在每个时间步使用RNN来调整GCN（即网络参数）,即关注GCN参数在每个时刻的演化而不关注该时刻的节点表示,这不仅提高了模型的自适应性和灵活性,还可以保持图的动态信息。此外,EvolveGCN只对RNN参数进行训练,不再训练GCN参数,这种方式使得参数的数量不会随着时刻的增加而增长,使该模型像常用的RNN一样易于管理。

在新的边出现时,DGNN[111]不仅更新节点表示,同时将交互信息传播到其他受影响的节点,使嵌入信息在更新和传播过程中可以合并交互之间的时间间隔。当新的边出现时,两端节点及其一阶邻域都有明显的概率变化。此外,邻域受到的影响与时刻有关,最近时刻与端点交互的邻居节点对出现的新变化很敏感,而较远的过去时刻的邻居受影响较小。端点和一阶邻域均使用时态信息增强LSTM作为更新模块的基本框架,使模型能够处理不同时间间隔的信息。

TemporalGAT[112]通过集成GAT和时间卷积网络（temporal convolutional network,TCN）[113,114]来学习动态图上的嵌入表示（见图21）。该模型将self-attention应用于节点邻域,并通过TCN保留图的动态信息。最后,采用二元交叉熵损失函数[115]学习节点表示,并预测节点之间是否存在边。TemporalGAT不仅能够建模节点数目不固定的动态图,还能同时捕获动态图的结构信息与时间信息。

图21

新窗口打开| 下载原图ZIP| 生成PPT

图21   TemporalGAT模型结构

Fig.21   Framework of TemporalGAT


2.5 基于其他方法的图嵌入

2.5.1 基于其他方法的静态图嵌入

LINE[116]同样定义了一阶相似度和二阶相似度函数,并对其进行优化。一阶相似度用于保持邻接矩阵和嵌入表示的点积接近,二阶相似度用于保持上下文节点的相似性。为了结合一阶和二阶相似度,LINE分别优化一阶和二阶相似度的目标函数,然后将生成的嵌入向量进行拼接。LINE的边采样策略克服了随机梯度下降的局限性,使其能够应用到大规模图嵌入中;但是一阶和二阶表示单独优化以及简单的拼接操作,限制了模型表示能力。

DRNE[117]没有重建邻接矩阵,而是直接使用LSTM聚合邻域信息重建节点嵌入（见图22）。DRNE的目标函数如下：由于LSTM要求其输入是一个序列,DRNE根据节点的度数进行排序,同时对度数较大的节点采用邻域抽样技术,以防止过长的记忆。这种方法可以保持节点的正则等价性和多种中心性度量（如PageRank[118]）。

图22

新窗口打开| 下载原图ZIP| 生成PPT

图22   DRNE模型结构

Fig.22   Framework of DRNE


Transformer[97]架构已经成为许多领域的主流选择,但在图级预测任务中,通常表现不佳。为此,Ying等人在标准Transformer的基础上利用图的结构信息构建Graphormer[119]（见图23）。对于结构信息的编码主要分为三部分：（1）中心性编码（centrality encoding）用于捕捉图中节点的重要性,根据每个节点的度为每个节点分配一个可学习向量,并将其添加到输入层的节点特征中。（2）空间编码（spatial encoding）用于捕捉节点之间的结构关系,根据每个节点对的空间关系为其分配了一个可学习的嵌入。（3）边编码（edge encoding）用于捕捉边缘特征中额外的空间信息,然后将其输入到Transformer层。Graphormer同时使用上述结构信息编码,提升模型性能,进而生成更优的嵌入表示。

图23

新窗口打开| 下载原图ZIP| 生成PPT

图23   Graphormer模型结构

Fig.23   Framework of Graphormer


2.5.2 基于其他方法的动态图嵌入

HTNE[120]使用Hawkes过程[121]捕捉历史邻域对当前邻域的影响,建模动态图中节点的邻域序列。然后,将节点分别映射为基向量和历史向量,并输入到Hawkes过程以生成嵌入表示。由于历史邻域对当前邻域形成的影响因节点而不同,引入注意力机制调节影响的大小。HTNE的核心在于使用邻域的形成过程描述节点的动态演化,Hawkes过程及注意力的引入使生成的嵌入有效集成到上述信息。

DynamicTriad[122]通过施加三元组（一组三个顶点的集合）模拟图的动态变化。一般来说,三元组分为两种类型：闭合三元组和开放三元组。由开放三元组演化为封闭三元组的三元组闭合过程是动态图形成和演化的基本机制[123,124]。DynamicTriad采用统一的框架来量化上述闭合过程,使模型能够有效捕捉图的动态信息。

动态图通常是在微观和宏观两方面随时间演化,微观动态可以描述拓扑结构的形成过程,宏观动态描述了图规模的演化模式。M2DNE[125]是首个将微观动态和宏观动态同时融入到动态图嵌入过程的模型。对于微观动态,M2DNE把边的建立当作时间事件,并提出时间注意点流程来捕获用于嵌入生成的时间属性。对于宏观动态,M2DNE通过定义使用嵌入参数化的动态方程来捕获内在演化模式,再利用内在演化模式在更高层次上约束图的拓扑结构。最后,M2DNE利用微观动态和宏观动态的演化和交互,生成节点嵌入。微观动态描述的是网络结构的形成过程,宏观动态描述的是网络规模的演化模式。大多数动态图方法只考虑了微观动态,忽略了宏观动态在保持网络结构和演化模式方面的重要价值,M2DNE同时使用宏观动态和微观动态,进而增强了模型的泛化能力。

因果匿名游走（causal anonymous walks,CAW）[126]与匿名游走（anonymous walks,AW）[127]相比有两个不同性质：（1）因果关系提取。CAW从感兴趣的链接开始,随着时间的推移回溯多个相邻链接,以编码动态图的基本因果关系。（2）基于集合的匿名化。CAW删除遍历集合中的节点标识以保证归纳学习,同时根据特定位置出现的计数对相应节点标识进行编码。CAW-N是专门用于链接预测的变体,该模型对两个感兴趣的节点进行CAW采样,然后通过RNN和集合池化对采样结果进行编码和聚合,生成最终嵌入。CAW-N不仅保留了游走过程中所有细粒度的时间信息,还可以通过motif [128,129]计数将其移除。

2.6 图嵌入模型关系分析

图嵌入可以解释为生成图数据的向量表示,用于洞察图的某种特性。表2和表3归纳了主要静态图嵌入和动态图嵌入的模型策略。基于矩阵分解的方法只有包含特定的目标函数,才能学习相应的图结构和信息。基于随机游走的方法可以通过改变参数来控制游走方式,还可以与其他模型叠加提升性能。基于AE和GNN的方法利用近似定理[130]广泛建模,使模型能够同时学习节点属性、拓扑结构和节点标签等信息。

表2   静态图嵌入模型策略归纳

Table 2  Strategies of static graph embedding

模型分类模型时间模型策略
矩阵分解LLE[24]2000构造邻域保持映射,最小化重建损失函数
GF[13]2013分解邻接矩阵,利用向量内积捕捉边的存在
GraRep[25]2015使用SVD分解k步对数转移概率矩阵
HOPE[27]2016GSVD分解相似度矩阵,L2范数保持高阶相似度
NGE[30]2013使用NMF将输入分解为系数矩阵和嵌入矩阵
LE[32]2001保持相连节点在嵌入空间尽可能靠近
CGE[33]2011修改LE损失函数,保持低权值节点对相似性
SPE[34]2009利用核矩阵生成关系矩阵 A˜,最小化 A和 A˜的差异
随机游走Deepwalk[49]2014使用随机游走采样节点,Skip-Gram最大化节点共现概率
node2vec[50]2016在Deepwalk的基础上引入有偏的随机游走
HARP[51]2017利用原始图生成保留全局结构的压缩图
Walklets[52]2016改进Deepwalk,捕获节点与社区的从属关系并建模
TriDNR[54]2016最大化节点标签、节点邻域、节点内容的共现概率
自编码器GraphEncoder[63]2014利用L2损失函数重构图相似度矩阵
SDNE[64]2016使用有监督和无监督组件分别保持一阶和二阶相似度
DNGR[65]2016随机冲浪捕获图结构,生成PPMI矩阵输入SDAE
DNE-APP[67]2017使用PPMI度量和k步转移矩阵构建相似度聚合矩阵
VGAE[69]2016引入VAE,使用GCN编码器,使用内积解码器
GALA[73]2020编码器执行拉普拉斯平滑,解码器执行拉普拉斯锐化
ANE[76]2018施加对抗性正则化避免流形断裂
图神经网络GCN[70]2016利用谱卷积一阶近似提高层间传播效率
GraphSAGE[85]2017采样和聚合节点的局部邻域特征训练聚合器函数
GAT[95]2017在GCN的基础上引入self-attention和multi-head attention
GIN[98]2018利用GNN和WL图同构测试保留图结构信息
MF-GCN[100]2020使用多个局部GCN滤波器提取节点特征
GraphAIR[102]2020邻域聚合模块融合节点特征表示,邻域交互模块通过乘法运算显示建模
SDGNN[103]2021在GNN的基础引入地位理论和平衡理论
其他LINE[116]2015分别优化一阶和二阶相似度,将嵌入向量进行拼接
DNRE[117]2018直接使用LSTM聚合邻域信息重建节点嵌入
Graphormer[119]2021在标准Transformer基础上,引入有中心性编码、空间编码和边编码

新窗口打开| 下载CSV


表3   动态图嵌入模型策略归纳

Table 3  Strategies of dynamic graph embedding

模型分类模型时间模型策略
矩阵分解DANE[36]2017拉普拉斯特征映射捕获t时刻的结构和属性信息,矩阵摄动理论更新动态信息
DHPE[38]2018GSVD分解各时刻Katz矩阵,矩阵摄动理论更新动态信息
TRIP[40]2015利用图中三角形个数构建特征函数,将特征对矩阵映射成嵌入向量
TIMERS[41]2017SVD最大误差界重启,消除增量更新积累的误差
DWSF[45]2017将图中有限监督信息合并为标签,并在每次迭代中更新
随机游走CTDNE[56]2018按照时间顺序对边进行遍历
dynnode2vec[57]2018node2vec初始化快照,对变化点执行随机游走,利用Skip-Gram更新动态信息
STWalk[59]2017捕捉规定时间窗内节点的变化
tNodeEmbed[60]2019模仿句子嵌入作为节点嵌入,捕捉节点角色和边的动态变化
自编码器DynGEM[78]2018提出PropSize动态调节神经元个数,同时引入L1和L2正则化
dyngraph2vec[79]2019组合AE和LSTM,构建不同的编码器和解码器组合
NetWalk[81]2018同时最小化节点距离和自编码器重构误差
BurstGraph[84]2019将动态演化分为一般演化和突发演化,RNN捕捉各时刻的图结构
HVGNN[92]2021采用基于TGNN的双曲VGAE
图神经网络DyRep[106]2018基于自我传播、外源驱动、局部嵌入传播更新节点表示
DySAT[108]2020结构注意力提取邻域特征,时间注意力捕捉多个时刻的表示
EvolveGCN[110]2019在每个时刻使用RNN调整GCN参数
DGNN[111]2020使用时态信息增强LSTM作为更新框架
TemporalGAT[112]2020集成GAT和TCN,self-attention应用于邻域,TCN用于动态信息更新
其他HTNE[120]2018Hawkes捕捉过去时刻对当前时刻邻域的影响,Skip-Gram更新动态信息
DynamicTriad[122]2018通过闭合三元组和开放三元组模拟图的动态演化
M2DNE[125]2019微观动态描述结构的形成,宏观动态描述规模的演化,利用二者交互生成嵌入
CAW[126]2021回溯多个时刻的相邻链接编码因果关系,根据特征位置计数编码相应节点标识

新窗口打开| 下载CSV


图嵌入模型之间不是相互割裂的,而是存在理论依托关系：CGE修改LE的目标函数,进一步增强邻近节点相似性;DANE离线模型采用类似LE的方式保持各时刻快照的一阶相似度;DHPE以HOPE为基础,引入矩阵摄动理论更新动态信息;NGE、MF和DWSF以NMF为基础;node2vec在Deepwalk的基础上引入有偏的随机游走;HARP通常与Deepwalk或node2vec结合使用;dynnode2vec在node2vec的基础上,使用Skip-Gram更新动态信息;DNE-APP在DNGR基础上引入成对约束;VGAE使用GCN作为编码器;BurstGraph使用GraphSAGE进行采样;GAT在GCN的基础上引入注意力机制;MF-GCN以GraphSAGE为基础构建;GraphAIR将GCN和GAT作为组件;EvolveGCN使用RNN调整GCN参数;TemporalGAT对GAT和TCN进行集成。

3 数据集与应用

本章将详细介绍常见图嵌入数据集和机器学习任务。表4和表5分别为常用静态图和动态图嵌入数据集的统计信息。

表4   静态图数据集统计信息

Table 4  Statistics of static graph datasets

统计项20-NewsGroupFlickrDBLPYouTubeWikipediaCoraCiteSeerPubmedYelp
#Nodes1 720,3 224,5 14180 51329 1991 138 4992 4052 7083 32719 7176 569
#EdgesFully connected5 899 882133 6642 990 44317 9815 4294 73244 33895 361
#Features————4 9731 4333 703500—
#Labels3,6,919544717763—

新窗口打开| 下载CSV


表5   动态图数据集统计信息

Table 5  Statistics of dynamic graph datasets

统计项EpinionsHep-thASEnronUCI
#Nodes14 1801 424~7 9807 7161841 809
#Edges227 6422 556~21 03610 695~26 46763~59116 822
#Features9 936————
#Labels20————
#Time Steps166010012813

新窗口打开| 下载CSV


3.1 数据集

3.1.1 静态图嵌入数据集

20-Newsgroup[63]：由大约20 000个新闻组文档构成的数据集。这些文档根据主题划分成20个组,每个文档表示为每个词的TF-IDF分数向量,构建余弦相似图。为了证明聚类算法的稳健性,分别从3、6和9个不同的新闻组构建了3个图,使用的缩写NG是Newsgroup的缩写。

Flickr[131]：由照片分享网站Flickr上的用户组成的网络。网络中的边指示用户之间的联系关系。标签指示用户的兴趣组（例如黑白色摄影）。

DBLP[53]：引文网络数据集,每个顶点表示一个作者,从一个作者到另一个作者的参考文献数量由这两个作者之间的边权重来记录。标签上标明了研究人员发表研究成果的4个领域。

YouTube[132]：YouTube视频分享网站用户之间的社交网络。标签代表了喜欢视频类型（例如动漫视频）的观众群体。

Wikipedia[133]：网页共现网络,节点表示网页,边表示网页之间的超链接。Wikipedia数据集的TF-IDF矩阵是描述节点特征的文本信息,节点标签是网页的类别。

Cora、CiteSeer、Pubmed[134]：标准的引文网络基准数据集,节点表示论文,边表示一篇论文对另一篇论文的引用。节点特征是论文的词袋表示,节点标签是论文的学术主题。

Yelp[135]：本地商业评论和社交网站,用户可以提交对商家的评论,并与其他人交流。由于缺乏标签信息,该数据集常用于链接预测。

3.1.2 动态图嵌入数据集

Epinions[136]：产品评论网站数据集,基于评论的词袋模型生成节点属性,以用户评论的主要类别作为类别标签。该数据集有16个时间戳。

Hep-th[137]：高能物理理论会议研究人员的合作网络,原始数据集包含1993年1月至2003年4月期间高能物理理论会议的论文摘要。

AS(autonomous systems)[138]：由边界网关协议日志构建的用户通信网络。该数据集包含从1997年11月8日到2000年1月2日的733条通信记录,通常按照年份将这些记录划分为不同快照。

Enron[139]：Enron公司员工之间的电子邮件通信网络。该数据集包含1999年1月至2002年7月期间公司员工之间的电子邮件。

UCI[140]：加州大学在线学生社区用户之间的通信网络。节点表示用户,用户之间的消息通信表示边缘。每条边携带的时间指示用户何时通信。

3.2 网络重构

网络重构任务是利用学习到节点低维向量表示重新构建原始图的拓扑结构,评估生成的嵌入保持图结构信息的能力。通过计算基于节点嵌入的内积或者相似性来预测节点间是否存在链接,使用前k对顶点真实链接所占原始图中链接的比例来评估模型的重构表现。

网络重构任务通常分为3个步骤：（1）使用图嵌入模型生成嵌入表示。（2）计算节点对应的重构邻近度并进行排序。（3）计算前k对节点的真实链接的比例。

网络重构任务通常采用MAP（mean average pre-cision）[141]作为评价指标：

AP(i)=∑jPr@j(i)∙Δi(j)|{Δi(j)=1}|MAP=∑i=1nAP(i)|V|

式中 ,Pr@j(i)是节点 vi的精度, Δi(j)=1表示节点 i和 j之间存在连接。

好的网络嵌入方法能够捕捉到具有网络结构信息的嵌入表示,从而能够很好地重构网络。在Yelp数据集上,ANE和LINE的结果要好于仅利用一阶相似度的LE和使用随机游走的Deepwalk。可见,表示局部结构的一阶相似性和表示全局结构的二阶相似性在保持网络结构方面都起着重要的作用。由于ANE采用了对抗性训练,其表现略优于LINE。各模型网络重构性能见图24。

图24

新窗口打开| 下载原图ZIP| 生成PPT

图24   网络重构性能对比

Fig.24   Performance comparison of graph reconstruction


3.3 节点分类

节点分类任务是利用图的拓扑结构和节点特征确定每个节点所属类别。现实世界的图数据,可能不是完全标签化的,由于各种因素大部分节点的标签可能是未知的,节点分类任务可以利用已有标签节点和连接关系来推断丢失的标签。此外,节点分类任务可分为两类：多标签分类和多类分类。前者使用的数据集中每个节点仅由一个类别标签标记,后者则由多个类别标签标记。

节点分类任务通常分为3个步骤：（1）使用图嵌入模型生成嵌入表示。（2）将包含标签信息的数据集划分为训练集和测试集。（3）在训练集上训练分类器,在测试集验证模型性能。常用的分类器包括逻辑回归分类器[142]、最近邻分类器[143]、支持向量机[144]和朴素贝叶斯分类器[145]等。

节点分类任务通常采用 micro-F1和 macro-F1作为评价指标：

$\left\{\begin{array}{l}\text { macro }-F 1=\frac{\sum_{l \in L} F 1(l)}{|L|} \\ \text { micro }-F 1=\frac{2 \times P \times R}{P+R}\end{array}\right.$

式中, F1(l)是标签 l的 F1分数, P表示准确率, R表示召回率。对于多分类任务准确度（Accuracy）与 micro-F1的值相同。

利用网络结构和节点特征预测节点标签在网络分析中有着广泛的应用。通过将生成的嵌入作为节点特征对节点进行分类,可以比较各种嵌入方法在该任务中的有效性。

在CiteSeer数据集上的静态图节点分类实验中,同时使用节点特征和网络拓扑结构的GNN模型均取得了较好的结果,仅使用网络结构进行无监督学习的Deepwalk、node2vec和LINE模型性能较差。相较原始的GraphSAGE模型,MF-GCN使用多个局部GCN滤波器进行特征提取,使模型捕捉到节点特征的不同方面,从而进一步提升了模型性能。同样突出的GraphAIR模型分别对邻域聚合和邻域交互进行建模,与原始的GCN和GAT模型结合使用,提升基础模型的性能。各模型静态图节点分类性能见图25。

图25

新窗口打开| 下载原图ZIP| 生成PPT

图25   静态图节点分类性能对比

Fig.25   Performance comparison of static graph node classification


在引入时间信息的DBLP数据集上的动态图节点分类实验中,与静态图嵌入模型（DeepWalk、node2vec、LINE和SDNE）相比,DANE保留的动态信息使生成的嵌入具有更强的表示能力;与动态图嵌入模型（tNodeEmbed、CTDNE、HTNE、DynamicTriad和M2DNE）相比,DANE捕捉了拓扑结构和节点属性特征的相关性,并保留图的动态信息,生成抗噪声的嵌入,从而提高结构嵌入的准确性。此外,由于DANE抗噪声的特性,使其有较好的鲁棒性。各模型动态图节点分类性能见表6。

表6   动态图节点分类性能对比

Table 6  Performance comparison of dynamic graph node classification %

IndexDeepwalknode2vecLINEDANEtNodeEmbedCTDNEHTNEDynamicTriadM2DNE
micro-F169.6575.2067.5674.5382.2071.7071.4071.1069.75
macro-F172.3723.5070.9775.6950.408.306.905.5069.71

新窗口打开| 下载CSV


3.4 链接预测

链接预测任务用于预测两个节点之间是否存在边或者预测图中未观察到的链接,评估生成嵌入在保持拓扑结构方面的性能。

链接预测任务通常分为3个步骤：（1）使用图嵌入模型生成嵌入表示。（2）对数据集中任意两个节点间的边信息进行标记,然后将数据集分为训练集和测试集。（3）在训练集上训练分类器,在测试集上进行链接预测实验。

链接预测任务通常采用AUC（area under the curve）和AP（average precision）作为评价指标：

AUC：把阈值设置在紧靠每个正例之下,计算负类的查全率,再取平均值。

AP：把阈值设置在紧靠每个正例之下,计算正类的查准率,再取平均值。

图嵌入可以显式或隐式地捕获网络的固有结构,以预测可能存在但未被观察到的连接关系。在CiteSeer数据集上,GraphAIR（AIR-GAE）的性能优于其他基于GNN和AE的方法,Deepwalk的表现最差。主要原因可能是链路预测任务通常使用成对解码器来计算两个节点之间链路的概率。例如,GAE和VGAE假设两个节点之间存在边的概率与这两个节点的嵌入的点积成正比。AIR-GAE通过两个节点嵌入相乘来显式地对邻域交互进行建模,这与链接预测任务有着内在的联系,进而提升了模型性能。各模型链接预测性能见表7。

表7   链接预测性能对比

Table 7  Performance comparison of link prediction %

IndexDeepwalkGAEVGAELinear-GAELinear-VGAEGALAGraphSAGEMF-GCNGraphAIR
AUC80.589.590.891.591.694.493.792.495.0
AP83.689.992.092.993.194.8———

新窗口打开| 下载CSV


3.5 聚类

聚类任务采用无监督的方式将图划分为若干个社区,使属于同一社区的节点具有更多相似特性。在利用模型生成嵌入后,一般采用频谱聚类（非归一化谱聚类[146]和归一化谱聚类[147]）和k-means[148]等经典方法将节点嵌入聚类。

聚类任务通常采用归一化互信息（normalized mutual information,NMI）[149]评估聚类性能：

NMI=1-H(M1|M2)norm+H(M2|M1)norm2

式中, NMI用于度量 M1和 M2聚类结果之间的相似性, H(·)表示信息熵。

将生成的嵌入表示进行聚类,使具有相似特性的节点尽可能在同一社区。在20-NewsGroup数据集上,GraRep、LINE和DNGR模型在3NG、6NG和9NG实验中性能明显优于其他基线算法。对于GraRep和LINE,两种方法可以有效捕捉丰富的局部关系信息,从而提高了聚类结果。对于DNGR,使用的深度神经网络能够有效捕捉图的非线性,同时使用随机冲浪代替广泛使用的抽样方法加强了原始图中信息的提取。各模型聚类性能见图26。

图26

新窗口打开| 下载原图ZIP| 生成PPT

图26   节点聚类性能对比

Fig.26   Performance comparison of node clustering


3.6 异常检测

异常检测任务用于识别图中的“非正常”结构,通常包括异常节点检测、异常边缘检测和异常变化检测。常见的异常检测方法有两种：一是将原始图进行压缩,通过聚类和离群点检测识别压缩图中的异常[150,151];二是利用模型生成节点嵌入并分组为k个社群,检测不属于已有社群的新节点或边。

异常检测任务通常采用AUC作为评价指标。

图数据的异常检测主要是找出与正常数据集差异较大的离群点（异常点）。好的嵌入表示能够利用决策边界,有效界定正常点与异常点。在DBLP和Hep-th数据集上,Deepwalk、node2vec和SDNE的实验结果相近,而NetWalk明显优于上述方法。NetWalk模型的高性能得益于以下优点：（1）网络嵌入可以动态更新;（2）流式节点和边可以在存储空间恒定的情况下进行高效编码;（3）可以灵活地扩展到不同类型的网络;（4）可实时检测网络异常。各模型异常检测性能见图27。

图27

新窗口打开| 下载原图ZIP| 生成PPT

图27   异常检测性能对比

Fig.27   Performance comparison of anomaly detection


3.7 可视化

可视化任务是对嵌入进行降维和可视化,从而直观地观察原始图中某些特征。可视化任务通常是在有标签数据集上进行的,不同标签的节点在二维空间中使用不同的颜色进行标记。由于嵌入中保留了原始图的某种信息,可视化结果直接反映了二维空间中同一社群节点具有更加相似的特征。

对于可视化任务,好的嵌入表示在二维图像中相同或相近的节点彼此接近,不同的节点彼此分离。在Cora数据集上,将模型生成的低维嵌入输入到t-SNE[10,152],使嵌入维数降至2,同一类别的节点使用相同的颜色表示。Yuan等人[153]比较了不同模型的可视化性能,部分可视化结果见图28。GCN和GAT学习的节点向量能够有效捕捉到社区的结构,使同类型节点更为接近。Deepwalk和SDNE只使用邻接矩阵作为输入,没有充分利用节点特征和标签信息,导致模型性能较差,尤其是SDNE模型,不同类型的点在二维空间中几乎是无序的。

图28

新窗口打开| 下载原图ZIP| 生成PPT

图28   不同模型的可视化结果

Fig.28   Visualization of different models


4 未来研究方向

通过对传统和新型图嵌入方法的研究和分析,现阶段的主要任务依然是提升模型对大规模和复杂图数据的扩展性、创新模型方法和提高下游任务性能。据此,本章提出了未来工作的四个研究方向。

（1）面向大规模图数据的嵌入模型

对于大规模静态图嵌入,通常采用分布式计算或无监督学习的方式提高计算效率。开放图基准（open graph benchmark,OGB）[154]是新兴图学习领域可扩展、可重复的基准,通过验证node2vec、LINE和GraphSAGE等实验表现,证明了模型的有效性。对于大规模动态图嵌入,现有模型无法采用类似静态图的方式实现图表示学习任务,因为动态图的规模不仅涉及图的大小,还涉及快照或时间戳的数量。因此,降低网络演化复杂度和提升模型性能是解决大规模动态图嵌入问题的两个重要方面。

（2）面向复杂图数据的嵌入模型

现阶段,大部分研究仍集中在简单的同质图上,如经典的GCN模型只需邻接矩阵、节点特征矩阵和系数矩阵即可实现。然而,现实世界的网络往往更加复杂,如异质图、有向图和超图等。现有模型中,HGSL[155]实现了异质图表示学习,SDGNN实现了符号有向图表示学习,DANE实现了属性图的表示学习。随着图表示学习研究的深入,探索更为复杂图数据的表示将仍旧是有前景的研究方向。

（3）改进模型训练策略

复杂的模型可以提升效果,但往往超参数较多且难以训练。相较于设计新的模型架构,一些研究者开始探索如何利用训练策略（如数据扩增[156]）来提升现有模型的性能。GraphMix[157]利用数据扩增技术,将简单的GCN架构提升到先进基线模型的水平,并且无需额外的内存和计算消耗。现阶段,除了开发新的图嵌入模型外,充分挖掘已有模型潜力仍然是一项充满挑战的工作。

（4）面向特定任务的嵌入模型

大部分图嵌入模型生成的结果将用于节点分类、链接预测、可视化等多个任务。与上述建模思路不同,面向任务的嵌入模型只关注一个任务,并充分利用与该任务相关信息来训练模型。多数情况下,面向任务的嵌入模型在目标任务上比通用嵌入模型更有效,如Semi-AttentionAE[153]采用集成学习的方法,联合训练GAT与LE,提升节点分类任务性能。针对特定任务设计高性能模型同样是今后研究的热点方向。

5 结束语

本文对图嵌入文献进行了全面回顾,给出了图嵌入有关定义,提出了静态图和动态图模型通用的分类方法,对现有模型的核心策略以及静态图和动态图模型理论相关性进行了系统性分析。在应用部分,介绍了图嵌入常用数据集以及节点分类、链接预测等常见的机器学习任务,比较了不同模型的表现。最后,从图数据、模型策略和应用场景三方面提出了图嵌入领域四个未来有希望的研究方向。

参考文献

宋雨萌, 谷峪, 李芳芳, 等.

人工智能赋能的查询处理与优化新技术研究综述

[J]. 计算机科学与探索, 2020, 14(7):1081-1103.

[本文引用: 1]

SONG Y M, GU Y, LI F F, et al.

Survey on AI powered new techniques for query processing and optimization

[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(7):1081-1103.

[本文引用: 1]

TRONCOSO F, WEBER R.

A novel approach to detect associations in criminal networks

[J]. Decision Support Systems, 2020, 128:113159.

DOI      URL     [本文引用: 1]

GUO S N, LIN Y F, FENG N, et al.

Attention based spatial-temporal graph convolutional networks for traffic flow forecasting

[C]// Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, Honolulu, Jan 27-Feb 1, 2019. Menlo Park: AAAI, 2019: 922-929.

[本文引用: 1]

GU J X, WANG Z H, KUEN J, et al.

Recent advances in convolutional neural networks

[J]. Pattern Recognition, 2018, 77:354-377.

DOI      URL     [本文引用: 1]

SALEHINEJAD H, SANKAR S, BARFETT J, et al.

Recent advances in recurrent neural networks

[J]. arXiv:1801.01078, 2017.

[本文引用: 1]

LECUN Y, BENGIO Y, HINTON G.

Deep learning

[J]. Nature, 2015, 521(7553):436-444.

DOI      URL     [本文引用: 1]

BHAGAT S, CORMODE G, MUTHUKRISHNAN S.

Node classification in social networks

[M]//AGGARWALC C.Social Network Data Analytics. Berlin, Heidelberg: Springer, 2011: 115-148.

[本文引用: 1]

LIBEN-NOWELL D, KLEINBERG J.

The link-prediction problem for social networks

[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7):1019-1031.

DOI      URL     [本文引用: 1]

DING C H Q, HE X F, ZHA H Y, et al.

A min-max cut algorithm for graph partitioning and data clustering

[C]// Proceedings of the 2001 IEEE International Conference on Data Mining, San Jose, Nov 29-Dec 2, 2001. Washington:IEEE Computer Society, 2001: 107-114.

[本文引用: 1]

VAN DER MAATEN L, HINTON G.

Visualizing data using t-SNE

[J]. Journal of Machine Learning Research, 2008, 9(11):2579-2605.

[本文引用: 2]

QIU J Z, TANG J, MA H, et al.

DeepInf: social influence prediction with deep learning

[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2110-2119.

[本文引用: 1]

SILVEIRA T, ZHANG M, LIN X, et al.

How good your recommender system is? A survey on evaluations in recom-mendation

[J]. International Journal of Machine Learning and Cybernetics, 2019, 10(5):813-831.

DOI      URL     [本文引用: 1]

AHMED A, SHERVASHIDZE N, NARAYANAMURTHY S M, et al.

Distributed large-scale natural graph factorization

[C]// Proceedings of the 22nd International World Wide Web Conference, Rio de Janeiro, May 13-17, 2013. New York: ACM, 2013: 37-48.

[本文引用: 3]

LOVÁSZ L.

Random walks on graphs: a survey

[J]. Com-binatorics, Paul Erdös is Eighty, 1993, 2(1):1-46.

[本文引用: 1]

GOLDBERG Y, LEVY O.

word2vec explained: deriving Mikolov et al.’s negative-sampling word-embedding method

[J]. arXiv:1402.3722, 2014.

[本文引用: 2]

CAI H, ZHENG V W, CHANG K C.

A comprehensive survey of graph embedding: problems, techniques, and applications

[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(9):1616-1637.

DOI      URL     [本文引用: 1]

GOYAL P, FERRARA E.

Graph embedding techniques, applications, and performance: a survey

[J]. Knowledge-Based Systems, 2018, 151:78-94.

DOI      URL     [本文引用: 1]

CHEN F X, WANG Y C, WANG B, et al.

Graph repres-entation learning: a survey

[J]. APSIPA Transactions on Signal and Information Processing, 2020, 9:e15.

DOI      URL     [本文引用: 1]

CUI P, WANG X, PEI J, et al.

A survey on network embedding

[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(5):833-852.

DOI      URL     [本文引用: 1]

XIE Y, LI C, YU B, et al.

A survey on dynamic network embedding

[J]. arXiv:2006.08093, 2020.

[本文引用: 1]

SKARDINGA J, GABRYS B, MUSIAL K.

Foundations and modelling of dynamic networks using dynamic graph neural networks: a survey

[J]. IEEE Access, 2021, 9:79143-79168.

DOI      URL     [本文引用: 1]

NG A.

Sparse autoencoder

[J]. CS294A Lecture Notes, 2011, 72:1-19.

[本文引用: 1]

SCARSELLI F, GORI M, TSOI A C, et al.

The graph neural network model

[J]. IEEE Transactions on Neural Networks, 2008, 20(1):61-80.

DOI      URL     [本文引用: 1]

ROWEIS S T, SAUL L K.

Nonlinear dimensionality red-uction by locally linear embedding

[J]. Science, 2000, 290(5500):2323-2326.

DOI      URL     [本文引用: 2]

CAO S S, LU W, XU Q K.

GraRep: learning graph repres-entations with global structural information

[C]// Proceedings of the 24th ACM International Conference on Information and Knowledge Management, Melbourne, Oct 19-23, 2015. New York: ACM, 2015: 891-900.

[本文引用: 2]

LEVY O, GOLDBERG Y.

Neural word embedding as implicit matrix factorization

[C]// Proceedings of the Annual Conference on Neural Information Processing Systems 2014, Montreal, Dec 8-13, 2014. Red Hook: Curran Associates, 2014: 2177-2185.

[本文引用: 1]

OU M D, CUI P, PEI J, et al.

Asymmetric transitivity preserving graph embedding

[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 1105-1114.

[本文引用: 2]

KATZ L.

A new status index derived from sociometric analysis

[J]. Psychometrika, 1953, 18(1):39-43.

DOI      URL     [本文引用: 1]

PAIGE C C, SAUNDERS M A.

Towards a generalized singular value decomposition

[J]. SIAM Journal on Numerical Analysis, 1981, 18(3):398-405.

DOI      URL     [本文引用: 1]

YANG J C, YANG S C, FU Y, et al.

Non-negative graph embedding

[C]// Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, Jun 24-26, 2008. Washington: IEEE Computer Society, 2008: 1-8.

[本文引用: 2]

LEE D D, SEUNG H S.

Learning the parts of objects by non-negative matrix factorization

[J]. Nature, 1999, 401(6755):788-791.

DOI      URL     [本文引用: 1]

BELKIN M, NIYOGI P.

Laplacian Eigenmaps and spectral techniques for embedding and clustering

[C]// Proceedings of the Neural Information Processing Systems: Natural and Synthetic, Vancouver, Dec 3-8, 2001. Cambridge: MIT Press, 2001: 585-591.

[本文引用: 2]

LUO D J, DING C H Q, NIE F P, et al.

Cauchy graph embe-dding

[C]// Proceedings of the 28th International Conference on Machine Learning, Bellevue, Jun 28-Jul 2, 2011. Madison: Omnipress, 2011: 553-560.

[本文引用: 2]

SHAW B, JEBARA T.

Structure preserving embedding

[C]// Proceedings of the 26th Annual International Conference on Machine Learning, Montreal, Jun 14-18, 2009. New York: ACM, 2009: 937-944.

[本文引用: 2]

LI R C. Matrix perturbation theory[M]//HOGBEN L. 2nd ed. Handbook of Linear Algebra. Boca Raton: CRC Press, 2013.

[本文引用: 1]

LI J D, DANI H, HU X, et al.

Attributed network embe-dding for learning in a dynamic environment

[C]// Proceedings of the 2017 ACM on Conference on Information and Know-ledge Management, Singapore, Nov 6-10, 2017. New York: ACM, 2017: 387-396.

[本文引用: 2]

HARDOON D R, SZEDMAK S, SHAWE-TAYLOR J.

Canonical correlation analysis: an overview with application to learning methods

[J]. Neural Computation, 2004, 16(12):2639-2664.

DOI      URL     [本文引用: 1]

ZHU D Y, CUI P, ZHANG Z W, et al.

High-order proximity preserved embedding for dynamic networks

[J]. IEEE Tran-sactions on Knowledge and Data Engineering, 2018, 30(11):2134-2144.

[本文引用: 2]

STRANG G, STRANG G, STRANG G, et al. Introduction to linear algebra[M]. Wellesley: Wellesley-Cambridge Press, 1993.

[本文引用: 1]

CHEN C, TONG H H.

Fast Eigen-functions tracking on dynamic graphs

[C]// Proceedings of the 2015 SIAM Inter-national Conference on Data Mining, Vancouver, Apr 30 - May 2, 2015. Philadelphia: SIAM, 2015: 559-567.

[本文引用: 2]

TSOURAKAKIS C E.

Fast counting of triangles in large real networks without counting: algorithms and laws

[C]// Proceedings of the 8th IEEE International Conference on Data Mining, Pisa, Dec 15-19, 2008. Washington: IEEE Com-puter Society, 2008: 608-617.

[本文引用: 2]

TSOURAKAKIS C E.

Counting triangles in real-world networks using projections

[J]. Knowledge and Information Systems, 2011, 26(3):501-520.

DOI      URL     [本文引用: 1]

ZHANG Z W, CUI P, PEI J, et al.

Timers: error-bounded SVD restart on dynamic networks

[C]// Proceedings of the 32nd AAAI Conference on Artificial Intelligence, the 30th Innovative Applications of Artificial Intelligence, and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 224-231.

[本文引用: 1]

AHMED N M, CHEN L, WANG Y L, et al.

DeepEye: link prediction in dynamic networks based on non-negative matrix factorization

[J]. Big Data Mining and Analytics, 2018, 1(1):19-33.

DOI      URL     [本文引用: 1]

SEYEDI S A, MORADI P, TAB F A.

A weakly-supervised factorization method with dynamic graph embedding

[C]// Proceedings of the 2017 Artificial Intelligence and Signal Processing Conference, Shiraz, Oct 25-27, 2017. Piscataway: IEEE, 2017: 213-218.

[本文引用: 2]

WANG Y X, ZHANG Y J.

Nonnegative matrix factorization: a comprehensive review

[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 25(6):1336-1353.

DOI      URL     [本文引用: 1]

TRIGEORGIS G, BOUSMALIS K, ZAFEIRIOU S, et al.

A deep matrix factorization method for learning attribute representations

[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 39(3):417-429.

DOI      URL     [本文引用: 1]

LIU Y, LEE J, PARK M, et al.

Learning to propagate labels: transductive propagation network for few-shot learning

[J]. arXiv:1805.10002, 2018.

[本文引用: 1]

PEROZZI B, AL-RFOU R, SKIENA S.

DeepWalk: online learning of social representations

[C]// Proceedings of the 20th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining, New York, Aug 24-27, 2014. New York: ACM, 2014: 701-710.

[本文引用: 2]

GROVER A, LESKOVEC J.

node2vec: scalable feature learning for networks

[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 855-864.

[本文引用: 2]

CHEN H C, PEROZZI B, HU Y F, et al.

Harp: hierarchical representation learning for networks

[C]// Proceedings of the 32nd AAAI Conference on Artificial Intelligence, the 30th Innovative Applications of Artificial Intelligence, and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 2127-2134.

[本文引用: 2]

YANG C, LIU Z Y.

Comprehend deepwalk as matrix factor-ization

[J]. arXiv:1501.00358, 2015.

[本文引用: 2]

PEROZZI B, KULKARNI V, SKIENA S.

Walklets: multiscale graph embeddings for interpretable network classification

[J]. arXiv:1605.02115, 2016.

[本文引用: 2]

PAN S R, WU J, ZHU X Q, et al.

Tri-party deep network representation

[C]// Proceedings of the 25th International Joint Conference on Artificial Intelligence, New York, Jul 9-15, 2016. Menlo Park: AAAI, 2016: 1895-1901.

[本文引用: 2]

SAJJAD H P, DOCHERTY A, TYSHETSKIY Y.

Efficient representation learning using random walks for dynamic graphs

[J]. arXiv:1901.01346, 2019.

[本文引用: 1]

NGUYEN G H, LEE J B, ROSSI R A, et al.

Continuous-time dynamic network embeddings

[C]// Companion Procee-dings of the Web Conference, Lyon, Apr 23-27, 2018. New York: ACM, 2018: 969-976.

[本文引用: 2]

MAHDAVI S, KHOSHRAFTAR S, AN A J.

Dynnode2vec: scalable dynamic network embedding

[C]// Proceedings of the 2018 IEEE International Conference on Big Data, Seattle, Dec 10-13, 2018. Piscataway: IEEE, 2018: 3762-3765.

[本文引用: 2]

KIM Y, CHIU Y I, HANAKI K, et al.

Temporal analysis of language through neural language models

[J]. arXiv:1405.3515, 2014.

[本文引用: 1]

PANDHRE S, MITTAL H, GUPTA M, et al.

STWalk: learning trajectory representations in temporal graphs

[C]// Proceedings of the ACM India Joint International Conference on Data Science and Management of Data, Goa, Jan 11-13, 2018. New York: ACM, 2018: 210-219.

[本文引用: 2]

SINGER U, GUY I, RADINSKY K.

Node embedding over temporal graphs

[J]. arXiv:1903.08889, 2019.

[本文引用: 2]

PALANGI H, DENG L, SHEN Y L, et al.

Deep sentence embedding using the long short term memory network: analysis and application to information retrieval

[J]. arXiv:1502.06922, 2015.

[本文引用: 1]

BOURLARD H, KAMP Y.

Auto-association by multilayer perceptrons and singular value decomposition

[J]. Biological Cybernetics, 1988, 59(4):291-294.

DOI      URL     [本文引用: 1]

TIAN F, GAO B, CUI Q, et al.

Learning deep representations for graph clustering

[C]// Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, Jul 27 -31, 2014. Menlo Park: AAAI, 2014: 1293-1299.

[本文引用: 3]

WANG D X, CUI P, ZHU W W.

Structural deep network embedding

[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 1225-1234.

[本文引用: 2]

CAO S S, LU W, XU Q K.

Deep neural networks for learning graph representations

[C]// Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, Feb 12-17, 2016. Menlo Park: AAAI, 2016: 1145-1152.

[本文引用: 2]

BULLINARIA J A, LEVY J P.

Extracting semantic repres-entations from word co-occurrence statistics: a computational study

[J]. Behavior Research Methods, 2007, 39(3):510-526.

DOI      URL     [本文引用: 1]

SHEN X, CHUNG F L.

Deep network embedding with aggregated proximity preserving

[C]// Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Sydney, Jul 31-Aug 3, 2017. New York: ACM, 2017: 40-43.

[本文引用: 2]

KINGMA D P, WELLING M.

Auto-encoding variational Bayes

[J]. arXiv:1312.6114, 2013.

[本文引用: 1]

KIPF T N, WELLING M.

Variational graph auto-encoders

[J]. arXiv:1611.07308, 2016.

[本文引用: 2]

KIPF T N, WELLING M.

Semi-supervised classification with graph convolutional networks

[J]. arXiv1609.02907, 2016.

[本文引用: 2]

KULLBACK S, LEIBLER R A.

On information and suffi-ciency

[J]. The Annals of Mathematical Statistics, 1951, 22(1):79-86.

DOI      URL     [本文引用: 1]

SALHA G, HENNEQUIN R, VAZIRGIANNIS M.

Keep it simple: graph autoencoders without graph convolutional networks

[J]. arXiv:1910.00942, 2019.

[本文引用: 1]

PARK J, LEE M, CHANG H J, et al.

Symmetric graph convolutional autoencoder for unsupervised graph represen-tation learning

[C]// Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision, Seoul, Oct 27-Nov 2, 2019. Piscataway: IEEE, 2019: 6518-6527.

[本文引用: 2]

CAI D, HE X F, HU Y X, et al.

Learning a spatially smooth subspace for face recognition

[C]// Proceedings of the 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Minneapolis, Jun 18-23, 2007.Washington: IEEE Computer Society, 2007: 1-7.

[本文引用: 1]

TAUBIN G.

A signal processing approach to fair surface design

[C]// Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, Aug 6-11, 1995. New York: ACM, 1995: 351-358.

[本文引用: 1]

XIAO Y, XIAO D, HU B B, et al.

ANE: network embe-dding via adversarial autoencoders

[C]// Proceedings of the 2018 IEEE International Conference on Big Data and Smart Computing, Shanghai, Jan 15-17, 2018. Washington:IEEE Computer Society, 2018: 66-73.

[本文引用: 2]

MAKHZANI A, SHLENS J, JAITLY N, et al.

Adversarial autoencoders

[J]. arXiv:1511.05644, 2015.

[本文引用: 1]

GOYAL P, KAMRA N, HE X, et al.

DynGEM: deep embedding method for dynamic graphs

[J]. arXiv:1805.11273, 2018.

[本文引用: 2]

GOYAL P, CHHETRI S R, CANEDO A.

Dyngraph2vec: capturing network dynamics using dynamic graph repres-entation learning

[J]. Knowledge-Based Systems, 2020, 187:104816.

DOI      URL     [本文引用: 2]

HOCHREITER S, SCHMIDHUBER J.

Long short-term memory

[J]. Neural Computation, 1997, 9(8):1735-1780.

DOI      URL     [本文引用: 1]

YU W C, CHENG W, AGGARWAL C C, et al.

NetWalk: a flexible deep embedding approach for anomaly detection in dynamic networks

[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2672-2681.

[本文引用: 2]

AKOGLU L, FALOUTSOS C.

Anomaly, event, and fraud detection in large network datasets

[C]// Proceedings of the 6th ACM International Conference on Web Search and Data Mining, Rome, Feb 4-8, 2013. New York: ACM, 2013: 773-774.

[本文引用: 1]

AKOGLU L, TONG H H, KOUTRA D.

Graph based anomaly detection and description: a survey

[J]. Data Mining and Knowledge Discovery, 2015, 29(3):626-688.

DOI      URL     [本文引用: 1]

ZHAO Y F, WANG X W, YANG H X, et al.

Large scale evolving graphs with burst detection

[C]// Proceedings of the 28th International Joint Conference on Artificial Intelligence, Macao, China, Aug 10-16, 2019: 4412-4418.

[本文引用: 2]

HAMILTON W L, YING R, LESKOVEC J.

Inductive representation learning on large graphs

[J]. arXiv:1706.02216, 2017.

[本文引用: 2]

MITCHELL T J, BEAUCHAMP J J.

Bayesian variable selection in linear regression

[J]. Journal of the American Statistical Association, 1988, 83(404):1023-1032.

DOI      URL     [本文引用: 1]

HEARD N A, WESTON D J, PLATANIOTI K, et al.

Bayesian anomaly detection methods for social networks

[J]. The Annals of Applied Statistics, 2010: 645-662.

[本文引用: 1]

KLEINBERG J.

Bursty and hierarchical structure in streams

[J]. Data Mining and Knowledge Discovery, 2003, 7(4):373-397.

DOI      URL     [本文引用: 1]

CHEN W, FANG W, HU G, et al.

On the hyperbolicity of small-world and treelike random graphs

[J]. Internet Math-ematics, 2013, 9(4):434-491.

[本文引用: 1]

GANEA O E, BÉCIGNEUL G, HOFMANN T.

Hyperbolic neural networks

[J]. arXiv:1805.09112, 2018.

[本文引用: 1]

ZHU D Y, CUI P, WANG D X, et al.

Deep variational network embedding in Wasserstein space

[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2827-2836.

[本文引用: 1]

SUN L, ZHANG Z B, ZHANG J W, et al.

Hyperbolic variational graph neural network for modeling dynamic graphs

[C]// Proceedings of the 35th AAAI Conference on Artificial Intelligence, the 33rd Conference on Innovative Applications of Artificial Intelligence, the 11th Symposium on Educational Advances in Artificial Intelligence, Virtual Event, Feb 2-9, 2021. Menlo Park: AAAI, 2021: 4375-4383.

[本文引用: 2]

HAMMOND D K, VANDERGHEYNST P, GRIBONVAL R.

Wavelets on graphs via spectral graph theory

[J]. Applied and Computational Harmonic Analysis, 2011, 30(2):129-150.

DOI      URL     [本文引用: 1]

DEFFERRARD M, BRESSON X, VANDERGHEYNST P.

Convolutional neural networks on graphs with fast localized spectral filtering

[J]. arXiv:1606.09375, 2016.

[本文引用: 1]

VELIČKOVIĆ P, CUCURULL G, CASANOVA A, et al.

Graph attention networks

[J]. arXiv:1710.10903, 2017.

[本文引用: 3]

CHAUDHARI S, MITHAL V, POLATKAN G, et al.

An attentive survey of attention models

[J]. arXiv:1904.02874, 2019.

[本文引用: 1]

VASWANI A, SHAZEER N, PARMAR N, et al.

Attention is all you need

[J]. arXiv:1706.03762, 2017.

[本文引用: 4]

XU K, HU W, LESKOVEC J, et al.

How powerful are graph neural networks?

[J]. arXiv:1810.00826, 2018.

[本文引用: 2]

LEMAN A A, WEISFEILER B.

A reduction of a graph to a canonical form and an algebra arising during this reduction

[J]. Nauchno-Technicheskaya Informatsiya, 1968, 2(9):12-16.

[本文引用: 1]

WANYAN T, ZHANG C, AZAD A, et al.

Attribute2vec: deep network embedding through multi-filtering GCN

[J]. arXiv:2004.01375, 2020.

[本文引用: 2]

WU F, SOUZA A H, ZHANG T Y, et al.

Simplifying graph convolutional networks

[C]// Proceedings of the 36th International Conference on Machine Learning, Long Beach, Jun 9-15, 2019: 6861-6871.

[本文引用: 1]

HU F Y, ZHU Y Q, WU S, et al.

Graphair: graph rep-resentation learning with neighborhood aggregation and interaction

[J]. Pattern Recognition, 2021, 112:107745.

DOI      URL     [本文引用: 2]

HUANG J, SHEN H, HOU L, et al.

SDGNN: learning node representation for signed directed networks

[J]. arXiv:2101.02390, 2021.

[本文引用: 2]

LESKOVEC J, HUTTENLOCHER D, KLEINBERG J M.

Predicting positive and negative links in online social networks

[C]// Proceedings of the 19th International Con-ference on World Wide Web, Raleigh, Apr 26-30, 2010. New York: ACM, 2010: 641-650.

[本文引用: 1]

LESKOVEC J, HUTTENLOCHER D P, KLEINBERG J M.

Signed networks in social media

[C]// Proceedings of the 28th International Conference on Human Factors in Computing Systems, Atlanta, Apr 10-15, 2010. New York:ACM, 2010: 1361-1370.

[本文引用: 1]

TRIVEDI R, FARAJTABAR M, BISWAL P, et al.

Dyrep: learning representations over dynamic graphs

[C]// Proceedings of the 2019 International Conference on Learning Repres-entations, 2019.

[本文引用: 2]

ZHANG J, SHI X, XIE J, et al.

GaAN: gated attention networks for learning on large and spatiotemporal graphs

[J]. arXiv:1803.07294, 2018.

[本文引用: 1]

SANKAR A, WU Y H, GOU L, et al.

DySAT: deep neural representation learning on dynamic graphs via self-attention networks

[C]// Proceedings of the 13th ACM International Conference on Web Search and Data Mining, Houston, Feb 3-7, 2020. New York: ACM, 2020: 519-527.

[本文引用: 2]

GEHRING J, AULI M, GRANGIER D, et al.

Convol-utional sequence to sequence learning

[C]// Proceedings of the 34th International Conference on Machine Learning, Sydney, Aug 6-11, 2017. New York: ACM, 2017: 1243-1252.

[本文引用: 1]

PAREJA A, DOMENICONI G, CHEN J, et al.

EvolveGCN: evolving graph convolutional networks for dynamic graphs

[C]// Proceedings of the 34th AAAI Conference on Artificial Intelligence, the 32nd Innovative Applications of Artificial Intelligence Conference, the 10th AAAI Symposium on Educational Advances in Artificial Intelligence, New York, Feb 7-12, 2020. Menlo Park: AAAI, 2020: 5363-5370.

[本文引用: 2]

MA Y, GUO Z Y, REN Z C, et al.

Streaming graph neural networks

[C]// Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2020: 719-728.

[本文引用: 2]

FATHY A, LI K.

TemporalGAT: attention-based dynamic graph representation learning

[C]// LNCS 12084: Proceedings of the 24th Pacific-Asia Conference on Knowledge Dis-covery and Data Mining, Singapore, May 11-14, 2020. Cham: Springer, 2020: 413-423.

[本文引用: 2]

BAI S J, KOLTER J Z, KOLTUN V.

An empirical evalu-ation of generic convolutional and recurrent networks for sequence modeling

[J]. arXiv:1803.01271, 2018.

[本文引用: 1]

VAN DEN OORD A, DIELEMAN S, ZEN H, et al.

Wavenet: a generative model for raw audio

[J]. arXiv:1609.03499, 2016.

[本文引用: 1]

SANKAR A, WU Y, GOU L, et al.

Dynamic graph repre-sentation learning via self-attention networks

[J]. arXiv:1812.09430, 2018.

[本文引用: 1]

TANG J, QU M, WANG M Z, et al.

LINE: large-scale information network embedding

[C]// Proceedings of the 24th International Conference on World Wide Web, Florence, May 18-22, 2015. New York: ACM, 2015: 1067-1077.

[本文引用: 2]

TU K, CUI P, WANG X, et al.

Deep recursive network embedding with regular equivalence

[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2357-2366.

[本文引用: 2]

PAGE L, BRIN S, MOTWANI R, et al.

The PageRank citation ranking: bringing order to the Web[R]

Stanford InfoLab, 1999.

[本文引用: 1]

YING C, CAI T, LUO S, et al.

Do transformers really perform bad for graph representation?

[J]. arXiv:2106.05234, 2021.

[本文引用: 2]

ZUO Y, LIU G N, LIN H, et al.

Embedding temporal network via neighborhood formation

[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2857-2866.

[本文引用: 2]

HAWKES A G.

Spectral of some self-exciting and mutually exciting point processes

[J]. Biometrika, 1971, 58(1):83-90.

DOI      URL     [本文引用: 1]

ZHOU L K, YANG Y, REN X, et al.

Dynamic network embedding by modeling triadic closure process

[C]// Pro-ceedings of the 32nd AAAI Conference on Artificial Inte-lligence, the 30th Innovative Applications of Artificial Intelligence, and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 571-578.

[本文引用: 2]

COLEMAN J S. Foundations of social theory[M]. Cam-bridge: Harvard University Press, 1994.

[本文引用: 1]

HUANG H, TANG J, LIU L, et al.

Triadic closure pattern analysis and prediction in social networks

[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(12):3374-3389.

DOI      URL     [本文引用: 1]

LU Y F, WANG X, SHI C, et al.

Temporal network embe-dding with micro-and macro-dynamics

[C]// Proceedings of the 28th ACM International Conference on Information and Knowledge Management, Beijing, Nov 3-7, 2019. New York: ACM, 2019: 469-478.

[本文引用: 2]

WANG Y, CHANG Y Y, LIU Y, et al.

Inductive repres-entation learning in temporal networks via causal anon-ymous walks

[J]. arXiv:2101.05974, 2021.

[本文引用: 2]

MICALI S, ZHU Z A.

Reconstructing Markov processes from independent and anonymous experiments

[J]. Discrete Applied Mathematics, 2016, 200:108-122.

DOI      URL     [本文引用: 1]

AHMED N K, NEVILLE J, ROSSI R A, et al.

Efficient graphlet counting for large networks

[C]// Proceedings of the 2015 IEEE International Conference on Data Mining, Atlantic City, Nov 14-17, 2015. Washington: IEEE Computer Society, 2015: 1-10.

[本文引用: 1]

PARANJAPE A, BENSON A R, LESKOVEC J.

Motifs in temporal networks

[C]// Proceedings of the 10th ACM International Conference on Web Search and Data Mining, Cambridge, Feb 6-10, 2017. New York: ACM, 2017: 601-610.

[本文引用: 1]

HORNIK K, STINCHCOMBE M B, WHITE H.

Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks

[J]. Neural Networks, 1990, 3(5):551-560.

DOI      URL     [本文引用: 1]

ZAFARANI R, LIU H.

Social computing data repository

[M]. Tempe: Arizona State University, 2009.

[本文引用: 1]

TANG L, LIU H.

Scalable learning of collective behavior based on sparse social dimensions

[C]// Proceedings of the 18th ACM Conference on Information and Knowledge Management, Hong Kong, China, Nov 2-6, 2009. New York: ACM, 2009: 1107-1116.

[本文引用: 1]

YANG C, LIU Z Y, ZHAO D L, et al.

Network repres-entation learning with rich text information

[C]// Procee-dings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Jul 25-31, 2015. Menlo Park:AAAI, 2015: 2111-2117.

[本文引用: 1]

SEN P, NAMATA G, BILGIC M, et al.

Collective classi-fication in network data

[J]. AI Magazine, 2008, 29(3):93.

[本文引用: 1]

ZENG H Q, ZHOU H K, SRIVASTAVA A, et al.

Graphsaint: graph sampling based inductive learning method

[J]. arXiv:1907.04931, 2019.

[本文引用: 1]

TANG J L, GAO H J, LIU H.

mTrust: discerning multi-faceted trust in a connected world

[C]// Proceedings of the 5th International Conference on Web Search and Data Mining, Seattle, Feb 8-12, 2012. New York: ACM, 2012: 93-102.

[本文引用: 1]

GEHRKE J, GINSPARG P, KLEINBERG J M.

Overview of the 2003 KDD Cup

[J]. SIGKDD Explorations, 2003, 5(2):149-151.

DOI      URL     [本文引用: 1]

LESKOVEC J, KREVL A. SNAP datasets: Stanford large network dataset collection[EB/OL]. [2021-02-10]. http://snap.stanford.edu/data/.

URL     [本文引用: 1]

KLIMT B, YANG Y M.

The enron corpus: a new dataset for email classification research

[C]// LNCS 3201: Proceedings of the 15th European Conference on Machine Learning, Pisa, Sep 20-24, 2004. Berlin, Heidelberg: Springer, 2004: 217-226.

[本文引用: 1]

PANZARASA P, OPSAHL T, CARLEY K M.

Patterns and dynamics of users’ behavior and interaction: network analysis of an online community

[J]. Journal of the American Society for Information Science and Technology, 2009, 60(5):911-932.

DOI      URL     [本文引用: 1]

KUMARAN G, ALLAN J.

Adapting information retri-eval systems to user queries

[J]. Information Processing & Management, 2008, 44(6):1838-1862.

DOI      URL     [本文引用: 1]

HOSMER D W, LEMESHOW S, STURDIVANT R X.

Applied logistic regression

[M]. New York: John Wiley & Sons, Inc., 2000.

[本文引用: 1]

PEDREGOSA F, VAROQUAUX G, GRAMFORT A, et al.

Scikit-learn: machine learning in Python

[J]. Journal of Machine Learning Research, 2011, 12:2825-2830.

[本文引用: 1]

SUYKENS J A K, VANDEWALLE J.

Least squares support vector machine classifiers

[J]. Neural Processing Letters, 1999, 9(3):293-300.

DOI      URL     [本文引用: 1]

MCCALLUM A, NIGAM K.

A comparison of event models for Naive Bayes text classification

[C]// Procee-dings of the AAAI-98 Workshop on Learning for Text Categorization, Madison, Jul 26-27, 1998. Menlo Park: AAAI, 1998: 41-48.

[本文引用: 1]

VON LUXBURG U.

A tutorial on spectral clustering

[J]. Statistics and Computing, 2007, 17(4):395-416.

DOI      URL     [本文引用: 1]

SHI J B, MALIK J.

Normalized cuts and image seg-mentation

[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.

DOI      URL     [本文引用: 1]

MACQUEEN J.

Some methods for classification and analysis of multivariate observations

[C]// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, Dec 27, 1965-Jan 7, 1966. Berkeley: University of California Press, 1966: 281-297.

[本文引用: 1]

CAI D, HE X F, HAN J W, et al.

Graph regularized nonnegative matrix factorization for data representation

[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8):1548-1560.

DOI      URL     [本文引用: 1]

MANZOOR E A, MILAJERDI S, AKOGLU L.

Fast memory-efficient anomaly detection in streaming heterogeneous graphs

[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 1035-1044.

[本文引用: 1]

RANSHOUS S, HARENBERG S, SHARMA K, et al.

A scalable approach for outlier detection in edge streams using sketch-based approximations

[C]// Proceedings of the 2016 SIAM International Conference on Data Mining, Miami, May 5-7, 2016. Philadelphia: SIAM, 2016: 189-197.

[本文引用: 1]

TANG J, LIU J Z, ZHANG M, et al.

Visualizing large-scale and high-dimensional data

[C]// Proceedings of the 25th International Conference on World Wide Web, Mon-treal, Apr 11-15, 2016. New York: ACM, 2016: 287-297.

[本文引用: 1]

YUAN L N, WANG Y, CHENG X G, et al.

Semi- AttentionAE: an integrated model for graph representation learning

[J]. IEEE Access, 2021, 9:80787-80796.

DOI      URL     [本文引用: 2]

HU W, FEY M, ZITNIK M, et al.

Open graph benchmark: datasets for machine learning on graphs

[J]. arXiv:2005.00687, 2020

[本文引用: 1]

ZHAO J N, WANG X, SHI C, et al.

Heterogeneous graph structure learning for graph neural networks

[C]// Proceedings of the 35th AAAI Conference on Artificial Intelligence, 33rd Conference on Innovative Applications of Artificial Intelligence, the 11th Symposium on Educational Adv-ances in Artificial Intelligence, Virtual Event, Feb 2-9, 2021. Menlo Park: AAAI, 2021: 4697-4705.

[本文引用: 1]

VAN DYK D A, MENG X L.

The art of data augmentation

[J]. Journal of Computational and Graphical Statistics, 2001, 10(1):1-50.

DOI      URL     [本文引用: 1]

VERMA V, QU M, KAWAGUCHI K, et al.

GraphMix: improved training of GNNs for semi-supervised learning

[J]. arXiv:1909.11715, 2019.

[本文引用: 1]

/

〈 〉

京ICP备13024263号-1
Copyright © 《计算机科学与探索》编辑部
技术支持：北京玛格泰克科技发展有限公司
总访问量
今日访问
在线人数