图自然存在于现实世界的各种场景中,例如社交媒体网络中的社交图/扩散图、研究领域的引文图、电商领域的用户兴趣图、知识图等。有效的图分析可以使很多应用受益,如节点分类、节点聚类、节点检索/推荐、链接预测等。尽管图分析graph analytics
是实用的和必要的,但大多数现有的图分析方法都存在昂贵的计算成本和空间成本的问题。然而,图嵌入graph embedding
提供了一种有效而高效的方法来解决图分析问题。具体来说,graph embedding
将图转换为一个低维空间,其中的图信息被保留下来。通过将图表示为一个(或一组)低维向量,然后可以有效地计算图算法。
graph embedding
的问题与两个传统的研究问题有关,即图分析和 representation learning
:
representation learning
的目的是获得更好的data representation
从而用于构建分类器或其他预测器。graph embedding
位于这两个问题的重叠部分,侧重于学习低维representation
。这里区分了graph rerpesentation learning
和 graph embedding
。注意,graph rerpesentation learning
并不要求学到的 representation
是低维的。
将图嵌入到低维空间并不是一件简单的事情。graph embedding
的挑战取决于问题的设置,它由嵌embedding input
和embedding output
组成。论文 《A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications》
将 input graph
分为四类,包括同质图 homogeneous graph
、异质图 heterogeneous graph
、带有辅助信息的图、和由非关系型数据non-relational data
构建的图。
不同类型的embedding input
带有不同的信息要在emebdding
空间中保留,因此对图的嵌入问题提出了不同的挑战。例如,当嵌入一个只有结构信息的图时,节点之间的连接是需要保留的目标。然而,对于带有节点标签或属性信息的图来说,辅助信息(即节点标签、属性信息)从其他角度提供了图的属性,因此在嵌入过程中也需要被考虑。
与embedding input
是给定的、固定的不同,embedding output
是任务驱动的。例如,最常见的 embedding output
类型是 node embedding
,它将临近的节点表示为相似的向量。 node embedding
可以有利于节点相关的任务,如节点分类、节点聚类等。
然而,在某些情况下,目标任务可能与图的更高粒度有关,例如,node pair
、子图、整个图。因此,在 embedding output
方面的第一个挑战是为目标任务找到一个合适的 embedding output
类型。论文 《A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications》
将 graph embedding output
分为四种类型,包括 node embedding
、edge embedding
、hybrid embedding
和 whole-graph embedding
。
不同的输出粒度对 good embedding
有不同的标准,并面临不同的挑战。例如,一个好的 node embedding
保留了与嵌入空间中的邻近节点的相似性。相比之下,一个好的 whole-graph embedding
将整个图表示为一个矢量,这样就可以保留graph-level
的相似性。
根据对不同问题设置中所面临的挑战的观察,作者提出了两个 graph embedding
工作的分类法,即根据问题设置和嵌入技术对 graph embedding
文献进行分类。具体而言:
graph embedding
问题的不同设置,以及在每个设置中面临的挑战。需要注意的是,尽管已经有一些尝试来综述 graph embedding
,但它们有以下两个局限性:
graph embedding
技术来进行分类。他们都没有从问题设置的角度分析 graph embedding
工作,也没有总结每个问题设置中的挑战。graph embedding
综述中,仅涉及了有限的相关工作。例如,《Graph embedding techniques, applications, and performance: A survey》
主要介绍了12
种有代表性的 graph embedding
算法,《Knowledge graph embedding: A survey of approaches and applications》
只关注知识图的嵌入。此外,没有对每种 graph embedding
技术背后的洞察力进行分析。论文贡献:
graph embedding
分类法,并总结了每个设置中面临的挑战。作者是第一个根据问题设置对 graph embedding
工作进行分类的人,这为理解现有工作带来了新的视角。graph embedding
技术进行了详细的分析。与现有的 graph embedding
综述相比,论文不仅综述了一套更全面的 graph embedding
工作,而且还提出了每个技术背后的见解总结。与简单地罗列过去如何解决 graph embedding
的问题相比,总结的见解回答了问题:为什么能(以某种方式)解决 graph embedding
问题。graph embedding
的应用进行了系统的分类,并将这些应用划分为节点相关、边相关、图相关。对于每个类别,论文提出了详细的应用场景作为参考。graph embedding
领域提出了四个有希望的未来研究方向。对于每个方向,论文对其在当前工作中的缺点(不足)进行了全面分析,并提出了未来的研究方向。给定图
定义:
knowledge graph
entity
,边为subject-property-object
三元组。每条边由 (head entity, relation, tail entity)
的形式组成,记作 定义节点 first-order proximity
为节点
定义
定义节点 second-order proximity
为节点
如果我们用 cos
函数作为邻域相似性的度量,则二阶邻近性为:
节点 higher-order proximity
也可以类似地定义。例如,节点
可以采用递归定义:
注意:也可以使用其它的一些指标来定义高阶邻近度,如 Katz Index, Rooted PageRank, Adamic Adar
等等。
定义 grap embedding
为:给定一个图 embedding
维度 graph embedding
需要将图
embedding
(如节点、边、子结构)。如下图所示,单张图以不同粒度嵌入到一个二维空间,其中
graph embedding
的输入是图,这里我们将输入图划分为四类:同质图homogeneous graph
、异质图 heterogeneous graph
、带辅助信息的图、从非关系数据人工构造的图。每种类型的图都会给graph emebdding
带来不同的挑战。
同质图:图的节点和边分别只有一种类型。同质图可以进一步划分为加权图、无权图,以及有向图,无向图。
挑战:如何捕获图中观察到的各种各样的连接模式?由于同质图中仅有结构信息可用,因此同质图 graph embedding
的挑战在于如何在 embedding
中保持输入图中观察到的这些连接模式。
异质图:异质图包含三种场景:
Community-based Question Answering:cQA
:cQA
是基于互联网的众包服务,用户可以在网站上发布问题,然后由其它用户回答。直观来看,cQA
图中有不同类型的节点,如问题 question
、答案 answer
、用户 user
。除了以上三种类型的异质图之外,还有其它类型的异质图。
挑战:
embedding
中,不同类型的节点(或者不同类型的边)被嵌入到同一个公共空间中。如何确保 embedding
的全局一致性是一个问题。带辅助信息的图:除了包含节点结构之外,带辅助信息的图还包含节点/边/全图的辅助信息。有五种类型的辅助信息:
label
:节点带标签信息(离散值)。带相同标签的节点的 embedding
应该彼此靠近、不同标签的节点的 embedding
应该彼此远离。attribute
:节点带属性信息。和标签不同,属性值可以是连续的也可以是离散的。属性值差异较小的节点的 embedding
应该彼此靠近、属性值差异较大的节点的 embedding
应该彼此远离。node feature
:节点带特征信息。和属性值不同,特征可能包含文本、向量、图像等多种类型的内容。节点特征通过提供丰富的结构化信息来提升 graph emebdding
性能。另外,这也使得 inductive graph embedding
成为可能。information progapation
:消息传播。一个典型例子是 Twitter
中的转发。knowledge base
:知识库。流行的知识库包括 Wikipedia, Freebase, YAGO, DBPedia
等。以 Wikipedia
为例,concept
是用户提出的实体 entity
,文本是该实体相关的文章。其它类型的辅助信息包括用户 check-in
数据(用户位置信息)、用户 item
偏好排名信息等等。注意,辅助信息不仅局限于一种类型,也可以考虑多种类型如 label & node feature
。
挑战:如何融合丰富的非结构化信息,使得学到的 embedding
同时编码了图的拓扑结构和辅助信息?除了图结构信息之外,辅助信息还有助于定义节点相似性。因此如何融合图拓扑结构和辅助信息这两个信息源,这是一个问题。
人工构造图:此时没有图数据,需要通过不同的方法从非关系数据中人工构建图。大多数情况下,输入为特征矩阵
通常使用样本
一种直接的计算方法是将
为解决该问题,一个方法是从 kNN graph
,并基于 kNN
图估计一个邻接矩阵 Isomap
将测地线距离融合到 kNN
图,然后找到两个节点之间的最短距离作为它们的测地线距离。
另一种构造图的方法是基于节点的共现,从而在节点之间建立边。如在图像领域,研究人员将像素视为节点,像素之间的空间关系视为边。
除了上述基于成对节点相似性以及节点共现的方法之外,还针对不同目的设计了其它的图构造方法。
挑战:
embedding
空间中?即如何在 embedding
空间中保留构造图的节点邻近性。graph emebdding
的输出是图(或者图的一部分)的一个(或者一组)低维向量。根据输出粒度,可以将 graph embedding
输出分为 node embedding
、edge embedding
、hybrid embedding
、whole-graph embedding
。
与固定的且给定的输入不同,graph embedding
的输出是任务驱动的。例如, node embedding
可用于各种与节点相关的图分析任务,而某些任务可能需要全图 whole-graph embedding
。因此,embedding
输出的第一个挑战是如何找到满足特定任务需求的、合适的 graph embedding
。
node embedding
:将每个节点表示为低维空间中的向量,图中临近的节点在 embedding
空间中有相似的向量表示。
各种 graph embedding
方法之间的差异在于如何定义两个节点之间的相近程度 closeness
,其中一阶邻近度和二阶邻近度是计算两个节点相近程度的常用度量,某些工作中也使用高阶邻近度。
挑战:如何在各种类型的输入图中定义成对节点的邻近性,以及如何在 embedding
中对这种相近程度进行编码?
edge embedding
:将每条边表示为低维空间中的向量。 edge embedding
在以下两种情况下很有用:
embedding
需要学习 node embedding
和 edge embedding
。每条边都是三元组 edge embedding
需要在embedding
空间中保留 pair
对嵌入为一个向量,从而预测这对节点之间是否存在链接。总之, edge embedding
有利于与边相关的图分析,如链接预测、知识图谱的实体/关系预测。
挑战:
edge-level
相似度?边的相似度不同于节点相似度,因为边通常包含一对节点。edge embedding
需要编码这种不对称属性。hybrid embedding
:嵌入图的不同类型的组件,如 node + edge
(子结构 substructure
)、node + community
。
已有大量工作研究了子结构嵌入substructure embedding
,而社区嵌入 community embedding
目前关注较少。
substructure embedding
或者community embedding
也可以通过聚合结构中的node embedding
和 edge embedding
来得到,但是这种间接的方式并未针对结构的表示进行优化。而且, node embedding
和 edge embedding
可以彼此强化:通过融合社区感知 community-aware
的高阶邻近度,可以学到更好的 node embedding
;而当学到更好的 node embedding
时,就可以检测到更好的社区。
挑战:
embedding
输出相反, hybrid embedding
并未提供需要嵌入的目标(如子图,社区)。因此第一个挑战是如何生成这种目标结构。embedding
目标类型的异质性是一个问题。whole-graph embedding
:将整个图输出为一个 embedding
向量,这通常用于蛋白质、分子等较小的图。这种情况下,一个图表示为一个向量,相似的图被嵌入到相近的 embedding
空间。
whole-graph embedding
提供了图相似度计算的一种简单有效解决方案,使得图分类任务受益。
挑战:
whole-graph embedding
需要捕获整个图的属性,而不是单个节点或者边的属性。expressiveness
和效率 efficiency
之间平衡? 由于需要捕获全图属性,因此和其它类型的 embedding
相比, whole-graph embedding
耗时更多。 whole-graph embedding
的关键挑战是如何在学到的 embedding
的表达能力和 embedding
算法的效率之间平衡。graph embedding
目标是在低维 embedding
空间中表达一个图,其中该 embedding
空间保留尽可能多的图属性信息。不同 graph embedding
算法之间的差异主要在于如何定义需要保留的图属性。不同的算法对于节点相似性、边相似性、子结构相似性、全图相似性有不同的定义,以及对于如何将这种相似性保留在 embedding
空间有各自不同的见解 insight
。基于矩阵分解 Matrix Factorization
的graph emebdding
方法以矩阵形式表示图属性,如节点成对相似性 node pairwise similarity
,然后分解该矩阵从而得到 node embedding
。
基于矩阵分解的 graph embedding
方法也是 graph embedding
的早期研究方式。大多数情况下,输入是非关系型的 non-relational
、高维的数据通过人工构造而来的图,输出是一组 node embedding
。因此可以将 graph embedding
视为保留结构信息的降维问题,该问题假设输入数据位于低维流形中。
有两种类型的基于矩阵分解的 graph embedding
方法:分解图拉普拉斯特征图 Laplacian Eigenmaps
、分解节点邻近度矩阵proximity matrix
。
总结:矩阵分解主要用于两种场景:嵌入由非关系数据构成的图的node embedding
(这是拉普拉斯特征图的典型应用场景)、嵌入同质图。
图拉普拉斯特征图分解的思想是:保留的图属性为成对节点相似性,因此如果两个相距较远的节点(通过 embedding
距离衡量)的相似度较大,则给予较大的惩罚。
为方便讨论,假设 embedding
的维度为一维,即将每个节点 insight
,则最优化 embedding
为:
假设
embedding
维度为维,则可以分别针对每一维来计算最优的 embedding
。
其中:
embedding
,embedding
组成的 embedding
向量。但是,上述最优化方程没有唯一解。假设
则最优解 eigenproblem
eigenvalue
对应的特征向量 eigenvector
。
上述 graph embedding
的问题是该方法是 transductive
的,它仅能嵌入已有的节点。实际应用中还需要嵌入未见过的、新的节点。
一种解决方案是设计线性函数 feature vector
。这样只要提供节点的特征向量,我们就可以求得其 embedding
。因此 inductive graph embedding
问题的核心在于求解合适的
同样地我们认为如果相距较远的两个节点(通过 embedding
距离衡量)的相似度较大,则给与较大的惩罚。则最优化 embedding
为:
其中
类似地,为了移除缩放因子的效果,我们通常增加约束条件
则最优解 eigenproblem
eigenvalue
对应的特征向量 eigenvector
。
上述讨论都是假设
embedding
为一维的。事实上如果希望embedding
是多维的,如维,则选择的不是最大特征值对应的特征向量,而是 top d
特征值对应的特征向量。
现有方法的差异主要在于如何计算节点 eigenmaps-based graph embedding
方法,并给出了它们如何计算节点相似度矩阵
其中:Eq.2
表示目标函数 Eq.4
表示目标函数 SVM
分类器的目标函数。
最初的研究 MDS
直接采用两个特征向量 MDS
不考虑节点的相邻关系,也就是说,任何一对训练样本都被认为是相连的。
后续研究(如Isomap
、LE
、LPP
、LLE
)通过首先从数据特征中构建一个 k nearest neighbour graph
来克服这个问题。每个节点只与它的 top-k
相似邻居相连。之后,利用不同的方法来计算相似性度矩阵
最近设计了一些更先进的模型。例如:
AgLPP
入了一个 anchor graph
,以显著提高 LPP
的效率。LGRM
学习了一个 local regression model
来掌握图的结构,以及一个全局回归global regression
项来进行 out-of-sample
的数据推断。local geometry
的工作不同,LSE
使用 local spline regression
来保留 global geometry
。当辅助信息(如label
、属性)可用时,目标函数被调整以保留更丰富的信息:
SR
构建了一个邻接图adjacent graph
labelled graph
LPP
数据集的局部几何结构 local geometric structure
,另一部分试图在标记的训练数据上获得最佳类别可分的embedding
。ARE
也构建了两个图:一个是编码局部几何结构的邻接图 pairwise relation
的 feedback relational graph
RF-Semi-NMF-PCA
的目标函数由三个部分组成,从而同时考虑聚类、降维和 graph embedding
:PCA
、k-means
和 graph Laplacian regularization
。其他一些工作认为,不能通过简单地枚举成对的节点关系来构建 semidefinite programming: SDP
来学习
SDP
旨在找到一个内积矩阵,使图中不相连的任何两个输入之间的成对距离最大化,同时保留最近的邻居距离。MVU
构建了这样的矩阵,然后将MDS
应用于学到的内积矩阵。《Unsupervised large graph embedding》
证明:如果 PSD
的、以及秩为 LPP
等价于正则化的 SR
。除了上述求解广义特征值方法之外,另一个方向是试图直接分解节点邻近度矩阵。可以基于矩阵分解技术在低维空间中近似节点邻近度,使得节点邻近度的近似损失最小化。
给定节点邻近度矩阵
其中:
embedding
矩阵。content embedding
矩阵。该目标函数是寻找邻近度矩阵 SVD
分解:
其中:
则我们得到最优 embedding
为:
根据是否保留不对称性,节点 embedding
可以为
我们在下表中总结了更多的矩阵分解方案,例如正则化的高斯矩阵分解、正则化的低秩矩阵分解、带更多正则化约束的矩阵分解等。
其中:Eq.5
表示目标函数
graph embedding
在图上应用深度学习模型,这些模型的输入可以是从图采样得到的路径,也可以是整个图本身。因此基于是否采用随机游走从图中采样路径,我们将基于深度学习的 graph embedding
分为两类:带随机游走的 deep learning
、不带随机游走的 deep learning
。graph emebdding
中。除了人工构造的图之外,所有类型的图输入以及所有类型的 embedding
输出都可以应用基于深度学习的 graph embedding
方法。基于带随机游走的 deep learning
的 graph embedding
的思想是:对于给定的节点,通过给定该节点的embedding
的条件下最大化该节点邻域的条件概率,则可以在 embedding
空间中保留图的二阶邻近度。
在基于带随机游走的deep learning
的 grap emebdding
中,图表示为从图中采样的一组随机游走序列。然后深度学习模型被应用于这些随机游走序列从而执行 grap embedding
。在嵌入过程中,embedding
保留了这些随机游走序列携带的图属性。
基于以上的洞察,DeepWalk
采用神经语言模型(SkipGram
) 执行 grap embedding
,其中 SkipGram
旨在最大化窗口内单词之间的共现概率。DeepWalk
首先应用截断的随机游走从输入图采样一组随机序列,然后将 SkipGram
应用于采样到的随机序列,从而最大化给定节点条件下节点邻域出现的概率。通过这种方式,相似邻域(具有较大的二阶邻近度)的节点共享相似的 embedding
。
DeepWalk
的目标函数为:
其中: embedding
;
SkipGram
不考虑窗口内节点的属性,因此有:
这里假设给定节点
的条件下,上下文窗口内的各节点之间相互独立。
其中 embedding
时,节点 softmax
函数:
上述概率难以计算,因为分母需要计算 embedding
的内积,算法复杂度为
Hierarchical Softmax
:我们构造二叉树来高效计算
假设根节点到叶节点
sigmoid
函数; embedding
。
现在 Hierarchical Softmax
函数将 SkipGram
的时间复杂度从
负采样:负采样的核心思想是将目标节点和噪声区分开来。即对于节点
其中:
通常
最终负采样将 SkipGram
的时间复杂度从
DeepWalk
的成功引起了很多后续的研究,这些研究在graph embedding
的采样路径上应用了各种深度学习模型(如 SkipGram
或 LSTM
),我们在下表中总结了这些方法。其中:
Eq.11
表示 Eq.12
表示 如下表所示,大多数研究都遵循了 DeepWalk
思想,但是改变了随机游走采样方法或者要保留的邻近度。注意:SkipGram
仅能嵌入单个节点,如果需要嵌入一个节点序列到固定维度的向量(如将一个句子嵌入为一个向量),则需要使用 LSTM
。
不基于带随机游走的 deep learning
的 graph embedding
的思想是:深度神经网络体系结构是将图编码到低维空间的强大、有效的解决方案。
这一类deep learning
方法直接将深度神经网络应用于整个图(或者图的邻接矩阵)。以下是一些用于 graph embedding
的流行深度学习模型:
自编码器 autoencoder
:自编码器旨在通过其编码器encoder
和解码器 decoder
,使得自编码器的输出和输入的重构误差最小。编码器和解码器都包含多个非线性函数,其中编码器将输入数据映射到representation space
、解码器将 representation space
映射到重构空间。
就邻域保持而言,采用自编码器的 grap embedding
思想类似于节点邻近度矩阵分解。具体而言,由于邻接矩阵包含了节点的邻域信息,因此如果将邻接矩阵作为自编码器的输入,则重构过程将使得具有相似邻域的节点具有相似的 embedding
。
Deep Neural Network
:卷积神经网络及其变种已被广泛用于graph embedding
。
CNN
模型,并对 input graph
进行重构从而适应 CNN
。还有一些其他类型的基于深度学习的 graph embedding
方法,如:
DUIF
使用 hierarchical softmax
作为前向传播来最大化modularity
。HNE
利用深度学习技术来捕捉异质组件之间的交互,如 CNN
组件用于图片、FC
层用于文本。 我们在下表中总结了所有不带随机游走的基于深度学习的 graph embedding
方法,并比较了它们使用的模型以及每个模型的输入。
基于边重建edge reconstruction
的 node embedding
基本思想是:通过 node embedding
重建的边应该和输入图中的边尽可能一致。
因此,基于边重建的node embedding
方法通过最大化边的重建概率edge reconstruction probability
或最小化边的重建损失edge reconstruction loss
,从而优化边重建的目标函数。其中重建损失又分为 distance-based
损失和 margin-based ranking
损失。
总结:基于边重构的方法适用于大多数 grap embedding
场景。根据我们的观察发现,只有非关系数据中构建的人工图embedding
、 whole-graph embedding
还未应用这种方式。原因是:
whole-graph embedding
。最大化边的重建概率的基本思想是:好的node embedding
应该能够最大程度地重建图中的边。
因此,该方法最大化所有观察到的边的生成概率。给定节点 embedding
它表示节点
为学习node embedding
,我们最大化图中所有边的生成概率,因此目标函数为:
类似地,节点
则最大化二阶邻近性的目标函数为:
其中 {start_node, end_node}
组成的集合,即从每条随机游走序列上随机截取的两个点。这使得节点之间的二阶邻近度转换为从起点到终点的随机游走概率。
最小化边的重建distance-based
损失的基本思想:通过 node embedding
计算的节点邻近度,应该尽可能和图中通过边计算的节点邻近度一致,从而最小化邻近度之间的差异,最终保留图的邻近度属性。
通过 node embedding
计算的一阶邻近度为:
而通过图中边计算的经验一阶邻近度为:
其中
KL
散度为距离函数来计算
类似地,通过 node embedding
计算的二阶邻近度为:
而通过图中边计算的经验二阶邻近度为:
其中 out-degree
(或者在无向图中就是节点的 degree
)。同样地,由于计算
KL
散度为距离函数来计算
最小化边的重建margin-based
排序损失的基本思想:边暗示了一对节点之间的相关性relevance
。因此,对于一个节点 A
,假设它和节点 B
存在边、和节点 C
不存在边,则在节点 B
和 C
之间,节点 A
的 embedding
和节点 B
的embedding
更相似。
定义 margin-based ranking loss
为:
其中 margin
超参数。
最小化该损失函数鼓励 margin
,因此鼓励
下表中我们总结了现有的利用 graph embedding
的边重建技术,给出了它们的目标函数和保留的节点邻近度。通常大多数方法使用上述目标函数之一。注意:当在 graph embedding
期间同时优化另一个任务时,该 task-specific
目标函数将融合到总的目标函数中。
大多数现有的知识图谱embedding
方法都选择优化margin-based ranking
损失函数。知识图谱 head entity
tail entity
embedding
可以解释为保留图的排名ranking
属性,使得真实的三元组
具体而言,在知识图谱 embedding
中,我们设计了能量函数
embedding
之间的相似性得分。embedding
的距离得分。embedding
空间的转换。可选的
最终,知识图谱的 graph embedding
目标函数为:
其中
现有知识图谱 embedding
方法主要优化上述
Graph Kernel
的原理是:整个图结构可以表示为一个向量,其中向量每个分量表示被分解的基本子结构的计数。
Graph Kernel
是 R
卷积的一个实例,它是一种在离散的复合对象 discrete compound object
上定义 kernel
的一种通用方法。这种方法通过将结构化对象递归地分解为 “原子” 的子结构,并两两进行比较。Graph Kernel
将每个图表示为一个向量,并使用两个向量的内积来比较两个图的相似性。在Graph Kernel
中通常定义三种类型的 “原子” 子结构:Graphlet
、Subtree Pattern
、Random Walk
。
Graphlet
:一个 Graphlet
是一个 size-k
的、诱导的 induced
、非同构的 non-isomorphic
子图。
假设将图 graphlet
graphlet
Subtree Pattern
:在这种 kernel
中,图被分解为 subtree pattern
。
一个例子是 Weisfeiler-Lehman
子树。对于带标记的图(即具有离散型的节点标签)执行 relabeling
迭代过程。每次迭代过程中如下图所示:
multiset label
,multiset label
中对邻居标签进行升序排列。multiset label
映射称为新的label
。这里使用字符串到 ID
的映射,也可以采用其它映射函数如哈希函数。label
执行 relabel
过程。假设在图 relabelling
过程,则 embedding
block
,第 block
的第
Random Walk
:在这种 kernel
中,图被分解为随机游走序列或路径(注意,这里的路径是固定的不是随机的),而 kernel
表示随机游走序列或路径出现的频次。
以路径为例,假设图
总结:Graph Kernel
用于捕获整个图的全局属性,因此仅用于 whole-graph emebdding
。输入图的类型通常是同质图,或者带有辅助信息的图。
可以指定输入特征和类别标签的联合分布来定义生成式模型 generative model
。一个典型的例子是潜在迪利克雷分配 Latent Dirichlet Allocation: LDA
,其中文档被解释为主题的分布,主题是单词的分布。
有两种生成式模型用于 graph embedding
:
Embed Graph Into The Latent Semantic Space
:原理是节点被嵌入到潜在语义空间中,其中节点之间的距离解释了观察到的图结构。
该方法直接将图嵌入到潜在空间,每个节点都表示为潜在空间中的一个向量。换句话讲,它将观察到的图视为从生成模型生成而来。例如在 LDA
中,文档被嵌入到 topic
空间中,单词相似的文档具有相似的 topic
向量。
Incorporate Latent Semantics for Graph Embedding
:原理是图中距离较近、且具有相似语义的节点应该紧密嵌在一起。其中节点语义可以通过生成式模型从节点描述信息中获取。
该方法使用潜在语义作为节点辅助信息从而进行 graph embedding
。最终 embedding
不仅取决于图结构信息,还取决于节点的潜在语义信息。
这两种方法的不同之处在于:第一种方法中 emebdding
空间就是潜在空间 latent space
;第二种方法中,潜在空间用于融合节点的不同来源的信息,并帮助将一个图嵌入到另一个空间。
总结:生成式模型可以用于node embedding
、 edge embedding
。由于该方法考虑了节点语义,因此输入图通常是异质图,或者带有辅助信息的图。
有时在一项工作中结合了多种技术:
《Cross view link predictionby learning noise-resilient representation consensus》
通过最小化 margin-based ranking loss
学习 edge-based embedding
,并通过矩阵分解学习 attribute-based embedding
。《Semantically smooth knowledge graph embedding》
优化了 margin-based ranking loss
,并将基于矩阵分解的损失作为正则化项。《Community-based question answering via asymmetric multifaceted ranking network learning》
使用 LSTM
来学习嵌入 cQA
中的句子,并使用 margin-based ranking loss
来融合好友关系。《Context-dependent knowledge graph embedding 》
采用 CBOW/SkipGram
进行知识图谱实体嵌入,然后通过最小化 margin-based ranking loss
对 embedding
进行微调。《Text-enhanced representation learning for knowledge graph》
使用 word2vec
来嵌入文本上下文,使用 TransH
来嵌入实体/关系,从而在知识图谱嵌入中利用了丰富的上下文信息。《Collaborative knowledge base embedding for recommender systems》
利用知识库中的异质性信息来提高推荐性能。它使用 TransR
进行 network embedding
,并使用自编码器进行 textual embedding
和 visual embedding
。items semantic representation
相结合。除了所介绍的五类技术外,还有其他方法:
《Hierarchical graph embedding in vector space by graph pyramid》
提出了通过图与prototype graph
的距离来嵌入图的方法。《On the embeddability of random walk distances 》
首先使用 pairwise
最短路径距离来嵌入一些 landmark
节点。然后嵌入其他节点,使其与 landmark
节点的距离尽可能地接近真实的最短路径。《Cross view link predictionby learning noise-resilient representation consensus》
联合优化了基于边的损失(最大化观察一个节点的邻居的可能性)和基于属性的损失(学习 link-based representation
的线性投影)。KR-EAR
(《Knowledge representation learning with entities, attributes and relations》
) 将知识图谱中的关系区分为 attribute-based
和 relation-based
。它构建了一个 relational triple encoder
(TransE
、TransR
)来嵌入实体和关系之间的关联,以及一个 attributional triple encoder
来嵌入实体和属性之间的关联。Struct2vec
通过 hierarchical metric
考虑了节点的结构身份 structral identify
,从而用于node embedding
。《Fast network embedding enhancement via high order proximity approximation》
通过近似高阶邻近性矩阵提供了一种快速嵌入方法。我们在下表给出所有五种 graph embedding
的优缺点。
基于矩阵分解的 graph embedding
使用 global pairwise
相似度的统计信息来学习 embedding
。
由于某些任务依赖于独立的局部上下文窗口,因此它可以超越基于深度学习的 graph embedding
方法。但是,无论是邻接矩阵的构造还是矩阵的特征值分解,其时间代价、空间代价都很高。这使得矩阵分解的效率较低,并且无法扩展到大规模的图。
基于深度学习的 grap emebdding
效果突出。我们认为深度学习适用于 graph embedding
,因为它具有从复杂图结构中自动识别出有用representation
的能力。例如:
另一方面,基于深度学习的方法也有局限性:
对于带随机游走的深度学习方法,它仅考虑路径内的局部邻域,因此忽略了全局结构信息。
另外,由于无法在统一的框架中同时优化embedding
和路径采样,因此很难找到最佳的采样策略。
对于不带随机游走的深度学习方法,计算代价通常很高。
最后,传统的深度学习架构假设输入数据是 grid
结构从而充分利用 GPU
,但是图数据不具备 grid
结构,因此需要不同的解决方案来提高计算效率。
基于边重建的graph embedding
方法可以基于观察到的边或者有序三元组从而优化目标函数。和前两类 graph embedding
相比,它的训练效率更高。
但是这一系列方法是使用直接观测到的局部信息进行训练的,因此获得的 embedding
缺乏对全局图结构的了解。
基于 graph kernel
的 graph embedding
将整个图转换为一个向量,从而促进 graph-level
的图分析任务,例如图分类。它比其它类型的技术更加高效,因此它只需要枚举图中出现的“原子”的子结构。
但是,这种类似于 bag-of-word
的方法有两个局限:
size
为 k+1
的 graphlet
可以通过size
为 k
的 graphlet
通过添加一些新的节点和一些新的边得到。这意味着通过 graphlet
的 graph representation
存在冗余信息。size
的增加,graph embedding
维度通常呈指数型增长,从而导致 embedding
的稀疏性问题。基于生成式模型的 graph embedding
可以自然地利用统一模型中不同来源的信息(如,图结构、节点属性)。直接将图嵌入到潜在的语义空间中,得到的 emebdding
可以用语义来解释。
但是,假设观测数据满足某种分布通常很难证明。并且生成式方法需要大量的训练数据来估计模型。因此对于较小的图或者少量的图,它无法很好地工作。
节点相关应用:
节点分类:通常先将每个节点嵌入为一个低维向量,然后通过在标记节点的 embedding
向量上应用分类器进行训练。
另外,和上面的两阶段节点分类相比,一些工作设计了一个统一的框架来共同优化node embedding
和节点分类,从而学到每个节点的 classification-specific representation
。
节点聚类:通常先将每个节点嵌入为一个低维向量,然后将传统的聚类算法应用于node embedding
。作为无监督算法,当节点标签不可用时可以使用聚类算法。
现有大多数方法都使用 k-means
作为聚类算法。也有一些方法在一个目标中共同优化了聚类和node embedding
,从而学到每个节点的 clustering-specific representation
。
节点推荐/检索/排序:节点推荐任务是基于某些标准(如相似性),将 top-K
相似节点推荐给目标节点。
在 knowledge graph embedding
中被广泛讨论的一个具体应用是entity ranking
:在三元组
边相关的应用:
链接预测:graph embedding
旨在用低维的向量来表示图,但有趣的是,得到的 embedding
向量也可以反过来帮助推断图结构。
实际上输入的图通常是残缺的。例如,在社交网络中实际上彼此认识的两个用户可能因为种种原因并没有添加为好友。在graph embedding
中,低维 embedding
向量预期会保留不同阶次、不同尺度的邻近度,因此这些embedding
向量编码了有关网络结构的丰富信息,并可以用于预测图中的缺失链接。
基于 graph embedding
的链接预测大多数应用于同质图,也有少量工作涉及异质图的链接预测。
三元组分类 Triple Classification
:三元组分类是知识图谱的特定应用,其目标是对未见过的三元组
图相关应用:
embedding
,然后在二维空间中使用不同的颜色绘制从而表示节点类别。图可视化生动地展示了属于同一个类别节点的 embedding
是否彼此靠近。其它应用:上面讨论的是一些通用的应用,这里是一些具体的应用:
relational fact
、从文本中提取医学实体、将自然语言文本与知识图谱中的实体联系起来,等等。geo-tagged
的社交媒体的记录 <time, location, message>
从而在给定其中两个元素的情况下恢复缺失的第三个元素;使用 graph embedding
来数据维度从而用于人脸识别;将图像映射到一个语义流形中从而促进 content-based
的图像检索。social interaction graph
来预测 propagation user
并识别领域专家。graph
,然后将 emebdding
用于图像分类、图像聚类、图像分割、模式识别,等等。这里我们总结了graph embedding
四个未来方向,包括计算效率、问题设置、技术、应用场景。
计算效率computation efficiency
:传统的深度学习模型(专为欧式结构的数据来设计)利用现代 GPU
来优化计算效率,通常假设输入数据为一维或二维网格形状。但是图不具备这种网格结构,因此需要针对 graph embedding
设计深度架构来提高模型效率。
问题设置 problem setting
:动态图是 graph embedding
的一种有前景的方向。图并不总是静态的,可以是动态演进的。一方面,图的结构可能随时间发生变化,如出现一些新节点、新的边,而有一些旧节点、旧的边消失;另一方面,图中节点的属性可能随时间发生变化。
与静态图的嵌入不同,动态图的技术需要可扩展的(最好是增量的),以便有效地处理动态变化。这使得大多数现有的 graph embedding
方法都存在效率低的问题,不再适用。如何针对动态图设计有效的 graph embedding
方法,仍然是悬而未决的问题。
技术 techniques
:结构感知 structure-aware
对基于边重建的 graph embedding
非常重要。目前基于边重建的 graph embedding
方法仅依赖于一阶邻域,图的全局结构(如路径、树、子图模式)被忽略。
从直觉上讲,一个子结构包含的信息要比单条边更丰富。因此,需要有一种有效的结构感知 graph embedding
优化框架以及子结构采样策略。
应用:graph embedding
已应用于许多不同的应用中。它可以将不同数据源、不同平台、不同视角的数据映射到公共的空间,从而便于直接比较。如 content-based
图像检索、keyword-based
图像/视频检索等。
使用 graph embedding
进行表示学习的优势在于:训练数据的graph
的流形被保留在 embedding
中,并可以进一步使得后续的应用受益。因此, graph embedding
可以使那些假定输入数据实例与某些关系(即通过某些link
来连接)相关的任务受益。探索从 graph embedding
中受益的应用场景是非常重要的,因为它从不同的角度为传统问题提供了有效的解决方案。
近年来,由于网络在现实世界中无处不在,图分析 graph analysis
已经引起了越来越多的关注。图分析任务可以大致抽象为以下四类:节点分类、链接预测、节点聚类、以及可视化:
在过去的几十年里,人们为上述任务提出了许多方法:
论文 《Graph Embedding Techniques, Applications, and Performance: A Survey》
提供了一种分类方法,来分析现有的方法以及应用领域。
通常图任务的模型要么在原始图的邻接矩阵上执行,要么在一个派生的向量空间上执行。近年来,基于向量空间的 graph representation
方法能够保持图的属性,因此被广泛应用。获得这样的 embedding
对于图分析任务非常有用。可以将node embedding
作为模型的特征输入,这可以避免使用一个非常复杂的模型直接应用到图数据上。
获得每个节点的 embedding
向量非常困难,并存在一些挑战:
属性选择:节点的良好的 embedding
向量应该保持图结构信息。第一个挑战是:embedding
应该保留图的哪个属性?
由于在图上存在多种距离度量和属性(如一阶邻近度、二阶邻近度),因此这种选择可能很困难,并且依赖于具体的任务。
可扩展性:大多数真实网络都很大,并且包含数百万节点和边。embedding
算法应该是可扩展的,并能够处理大图。
embedding
维度:选择最佳的 embedding
维度可能很困难。例如,更高的维度可以提高边重建的准确性,但是具有更高的时间复杂度和空间复杂度。根据方法的不同,具体的最佳 embedding
维度也是 task-specific
的。如,在链接预测任务中,如果使用的模型仅捕获节点之间的局部连接,则较小的 embedding
维度可能导致更好的链接预测准确性。
论文贡献:
graph embedding
方法的分类法,并解释了它们的差异。作者定义了四个不同的任务,也就是 graph embedding
技术的应用领域。作者说明了 graph embedding
的演变、所面临的挑战、以及未来可能的研究方向。graph embedding
模型进行了详细而系统的分析,并讨论了它们在各种任务上的表现。对于每一种方法,作者通过对一些常见的数据集和应用场景的综合比较评估,分析其保留的属性及其准确性。此外,作者对所评估的方法进行了超参数敏感性分析以测试它们的鲁棒性,并提供对最佳超参数的理解。graph embedding
的进一步研究,论文最后介绍了GEM
,这是作者开发的开源 Python
库,在一个统一的接口下提供了本综述中讨论的所有 graph embedding
方法的实现。就作者所知,这是第一篇综述 graph embedding
技术及其应用的论文。给定图
邻接矩阵
定义节点 first-order proximity
为节点
我们认为:如果两个节点之间具有较大权重的连接,则它们更为相似。由于边
定义
定义节点 second-order proximity
为节点 cos
函数作为邻域相似性的度量,则二阶邻近性为:
节点 higher-order proximity
也可以类似地定义。例如,节点
和
《A Comprehensive Survey of Graph Embedding[2017]》
类似,也可以采用递归定义:
也可以使用其它的一些指标来定义高阶邻近度,如 Katz Index, Rooted PageRank, Common Neighbors, Adamic Adar
等等。
给定一个图 graph embedding
是一个映射
因此,embedding
将每个节点映射到低维特征向量,并尝试保留节点之间的连接信息。
graph embedding
技术的历史演进:
在21
世纪初,研究人员开发了 graph embedding
算法,作为降维技术的一部分。他们会根据邻居关系为 similarity graph
,然后将图的节点嵌入到一个 embedding
的思想是:让相连的节点在向量空间中相互靠近。Laplacian Eigenmaps
和 Locally Linear Embedding: LLE
是基于这个原理的算法的例子。然而,可扩展性是这种方法的一个主要问题,其时间复杂度为
自 2010
年以来,关于 graph embedding
的研究已经转向获得可扩展的 graph embedding
技术,这些技术利用了现实世界网络的稀疏性。例如:
Graph Factorization
使用邻接矩阵的近似分解化作为 embedding
。LINE
扩展了这种方法,并试图保留一阶邻近性和二阶邻近性。HOPE
扩展了 LINE
,试图通过使用广义的奇异值分解Singular Value Decomposition: SVD
来分解相似性矩阵而不是邻接矩阵,从而保留高阶接近性。SDNE
使用自编码器来嵌入图的节点并捕获高度非线性的依赖关系。新的可扩展方法的时间复杂度为
我们将近年来提出的 graph embedding
技术分为三类:
factorization-based
。random walk-based
。deep learning-based
。这些类别代表性的方法以及简要介绍如下表所示。
基于分解的方法以矩阵形式表示节点之间的连接,然后将该矩阵分解从而获得node embedding
。用于表示连接的矩阵可以为节点邻接矩阵、图拉普拉斯矩阵、节点转移概率矩阵、Katz
相似度矩阵。
Katz Index:KI
用于区分不同邻居节点的不同影响力,它给邻居节点赋予不同的权重:对于短路径赋予较大权重、对于长路径赋予较小的权重。给定节点
以及邻接矩阵 ,则节点 之间长度为 的路径权重为 。则有: 其中
为权重衰减因子。为保证数列的收敛性, 必须小于邻接矩阵 最大特征值的倒数。 令
KI
矩阵为,则有: 由于存在矩阵求逆运算,因此总的算法复杂度为
。
矩阵分解的方法因矩阵属性而异。如果获得的矩阵是半正定的(例如,图拉普拉斯矩阵),则可以使用特征值分解 eigenvalue decomposition
。对于非结构化矩阵 unstructured matrices
,可以使用梯度下降法在线性时间内获得 embedding
。
LLE
:局部线性嵌入 Locally Linear Embedding:LLE
假设每个节点的 embedding
都是其邻居节点的 embedding
的线性组合。
假设图 embedding
node embedding
的线性组合近似为:
我们通过最小化近似误差来得到目标函数:
其中 embedding
矩阵。
可以看到当
进一步地,为消除平移不变性,因为如果 embedding
以零点为中心:
因此得到最优化方程:
可以将上述最优化问题简化为一个特征值问题 eigenvalue problem
,最终的解为稀疏矩阵 eigenvalue
对应的特征向量eigenvector
,并剔除最小特征值对应的特征向量。
Laplacian Eigenmaps
:拉普拉斯特征图Laplacian Eigenmaps
旨在当 embedding
距离较近。具体而言,其目标函数为:
其中 tr(.)
为矩阵的迹trace
,
可以看到当
上述最优化问题的解为归一化的图拉普拉斯矩阵 eigenvalue
对应的特征向量 eigenvector
。
Cauchy Graph Embedding
:对于任意节点
则我们称该 embedding
保留了局部拓扑结构local topology
。即:对于任意一对节点
在拉普拉斯特征图中,由于embedding
距离使用二次函数,因此:对于embedding
距离较大的不相似的节点,其距离的平方较大;对于 embedding
距离较小的相似节点,其距离平方较小。因此该目标函数更侧重于找到 ”不相似性性“,而不是”相似性“ 。即:
embedding
,则惩罚较小。embedding
,则惩罚较大。因此拉普拉斯特征图倾向于将节点都映射到相似的 embedding
,这使得emebdding
无法保留图的局部拓扑结构。
Cauchy Graph Embedding
通过将
注意这里为 max
而不是 min
。
这一变化得核心在于:对于较大的
但是对于较小的
,模型也鼓励较小的距离 。所以无论如何,模型都鼓励 。
SPE
:结构保持嵌入 Structure Preserving Embedding:SPE
是扩展拉普拉斯特征图的另一种方式。SPE
目标是准确地重建输入图。embedding
存储为一个半正定的核矩阵 connectivity algorithm
我们求解最优化方程:
从而试图重建 rank-1
的谱嵌入 spectral embedding
。
连通算法
此时求解的kernel
为了处理图中的噪音,可以添加一个松弛变量
其中 slackness
。
Graph Factorization
:图分解Graph Factorization:GF
算法是第一个可以在 graph embedding
的算法。为了获得 embedding
,GF
通过最小化以下目标函数来分解邻接矩阵:
其中
注意:求和是在所有观测到的边上,而不是所有的节点
pair
对上。
GF
是一种可扩展的、近似的求解方案。由于邻接矩阵通常不是半正定的,因此即使 embedding
的维度选择为
GraRep
:GrapRep
定义节点的转移概率矩阵为
其中
最终执行矩阵分解:
其中 embedding
, embedding
。
最终拼接节点所有阶的 embedding
得到node embedding
。
GrapRep
的缺陷在于其可扩展性,因为
HOPE
:HOPE
通过最小化 node embedding
矩阵,coordinate
矩阵,
如果将
视为 embedding
空间中的一组基向量,则为 embedding
空间的坐标,来近似高阶邻近度。
作者尝试了不同的相似性度量,包括 Katz Index, Rooted Page Rank, Common Neighbors, Adamic-Adar
。例如当选择 Katz Index
时,高阶邻近度矩阵为:
其中 HOPE
可以使用广义奇异值分解可以有效获得node embedding
。
其它方法:为了对高维数据降维,这里其它一些方法能够执行 graph embedding
,包括:主成分分析Principal Component Analysis:PCA
、线性判别分析 Linear Discrimant Analysis:LDA
、IsoMap
、多尺度缩放Multidimesional Scaling:MDS
、局部特性保持Locality Preserving Properties:LPP
、核特征图Kernel Eigenmaps
。《Non-negative graph embedding》
提出了一个通用框架用于为这些算法产生非负的 graph embedding
。
最近的一些技术聚焦在联合学习网络结构和节点属性信息上:
Augmented Relation Embedding: ARE
用基于内容的图像特征来增强网络,并修改graph-Laplacian
矩阵来捕获这些信息。Text-associated DeepWalk: TADW
对节点的相似度矩阵执行分解,同时用到了文本特征矩阵。Heterogeneous Network Embedding: HNE
学习网络每个模态的表示,然后使用线性变换将它们映射到同一个公共空间中。随机游走已被用于近似求解图中的很多属性,包括节点中心性 centrality
、节点相似性 similarity
。
当只能观察到图的一部分,或者图太大而无法整体计算时,随机游走的方法特别有用。人们已经提出一些使用随机游走的方法来获得 node representation
。
DeepWalk
:DeepWalk
通过最大化随机游走过程中节点
此外,可以通过基于内积的解码器来从 node embedding
中重建边。
node2vec
:类似于 Deepwalk
,node2vec
通过最大化给定节点在随机游走序列中后续节点出现的概率,从而保留节点之间的高阶邻近度。
和 Deepwalk
区别在于:node2vec
采用了有偏的随机游走,可以在广度优先搜索BFS
和深度优先搜索 DFS
之间平衡。因此, node2vec
可以产生比 DeepWalk
更高质量的 embedding
。选择正确的 balance
能够保留社区结构community structure
、或者保留节点的结构等价性 structural equivalence
。
Hierarchical Representation Learning for Network: HARP
:Deepwalk
和 node2vec
随机初始化node embedding
来训练模型,由于它们的目标函数是非凸的,因此这种随机初始化可能卡在局部最优点。Hierarchical Representation Learning for Networks:HARP
引入了一种策略,可以通过更好的权重初始化策略来改进方法并避免局部最优。
为此,HARP
构建了一种层次结构 hierarchy
,每一层都是通过将前一层的节点聚合从而对图进行粗化 coarsening
。然后,HARP
生成最粗粒度的图的 embedding
,并将该 embedding
初始化更细粒度的图的 embedding
。
就这样一层一层地训练和初始化来传播这些不同层的 embedding
,直到获得初始图的 embedding
。因此,HARP
可以和基于随机游走的方法结合使用,从而获得更好的 embedding
。
Walklets
:DeepWalk
和 node2vec
通过随机游走来隐式地保留节点之间的高阶邻近度。由于随机性,节点之间的距离在不同随机游走序列中可能不同。而基于分解的方法通过目标函数从而显式保留节点之间的距离。
Walklets
将显式建模的思想和随机游走思想相结合,该模型通过跳过随机游走序列的 DeepWalk
中的随机游走策略。
其它方法:也有上述方法的几种变体。GenVector, Discriminative Deep Random Walk:DDRW, Tri-party Deep Network Representation:TriDNR
通过联合学习网络结构和节点属性来扩展了随机游走方法。
越来越多的深度学习方法应用于图分析。由于深度自编码器能够对数据中的非线性结构进行建模,因此被广泛应用于降维。最近 SDNE, DNGR
利用深度自编码器这种能力来生成 embedding
从而捕获图的非线性。
Structural Deep Network Embedding: SDNE
:SDNE
提出使用深度自编码器来保留网络的一阶邻近度和二阶邻近度,它通过共同优化两个邻近度来实现这一目标。
SDNE
使用高度非线性的函数来获取 embedding
,模型分为两个部分:
embedding
。embedding
,使得相似的节点在 embedding
空间中更紧密。Deep Neural Networks for Learning Graph Representations:DNGR
:DNGR
结合了随机游走和深度自编码器。该模型由三部分组成:随机游走、positive pointwise mutual information :PPMI
矩阵、堆叠式的降噪自编码器。
HOPE
中的相似矩阵。PPMI
矩阵。PPMI
矩阵输入到堆叠的降噪自编码器中获得 embedding
。输入的 PPMI
矩阵可以确保自编码器模型可以捕获更高阶的邻近度。此外,使用堆叠式的降噪自编码器有助于在图中存在噪声的情况下增强模型的鲁棒性,并有助于捕获具体任务所需的底层结构,这些任务包括链接预测、节点分类等。
Graph Convolutional Networks:GCN
:上述讨论的基于深度神经网络的方法(SDNE,DNGR
等)将每个节点的全局邻域(DNGR
中 PPMI
的一行、SDNE
中邻接矩阵的一行)作为输入。对于大型稀疏图,这可能计算代价太大。图卷积神经网络GCN
通过在图上定义卷积算子来解决该问题。
GCN
迭代式地聚合节点邻域 embedding
,并使用邻域聚合后的 emebdding
和节点前一轮 embedding
来更新节点这一轮的 embedding
。由于 GCN
仅聚合节点的局部邻域,因此可扩展性更强。经过多次迭代之后,节点学到的 embedding
能够刻画全局邻域。
可以将卷积滤波器大致分为空间滤波器 spatial filter
、谱域滤波器 spectral filter
。空间滤波器直接作用于原始图和邻接矩阵,谱域滤波器作用于图的拉普拉斯矩阵的谱域。
Variational Graph Auto-Encoders:VGAE
:图的变分自编码器使用 GCN
作为编码器、使用向量内积作为解码器。输入为图的邻接矩阵,并依赖 GCN
来学习节点之间的高阶邻近度。实验表明,和非概率non-probabilistic
的自编码器相比,使用变分自编码器可以提升性能。
LINE
:LINE
显式地定义了两个目标函数,分别用于保持一阶邻近度和二阶邻近度。
一阶邻近度目标函数类似于因子分解 Graph Factorization:GF
,因为它们都旨在保持邻接矩阵和成对embedding
内积产生的矩阵的之间差异足够小。区别在于 GF
通过直接最小化二者之间的差异来实现,而 LINE
通过最小化理论联合概率分布和经验联合概率分布的KL
距离来实现。
LINE
为每对节点定义了两个联合概率分布,其中理论联合概率分布采用 embedding
定义为:
经验联合概率分布使用邻接矩阵定义为:
因此一阶邻近度目标函数为:
类似地,LINE
定义了二阶邻近度目标函数:
.
我们可以将 embeddign
解释为描述图数据的 representation
,因此它可以深入了解图的属性。
我们以下图为例,考虑一个全连接的二部图
embedding
距离紧凑的 embedding
算法( Community Preserving Embedding:CPE
)无法捕获图结构,如下图 (b)
所示。structurally-equivalent
节点的 embedding
距离紧凑的 embedding
算法(Structural-equivalence Preserving Embedding:SPE
)效果很好,如下图 (c)
所示。类似地,考虑将两个星形结构通过一个 hub
节点相连的图 1,3
是结构等价的,因此在下图 (f)
中它们的 embedding
相距很近、在下图 (e)
中它们相距很远。
因此,可以根据 embedding
算法解释图属性的能力将这些算法分类:
connectivity
。另外,除非显式地在目标函数中包含结构对等性structural equivalence
,否则基于因子分解的方法也无法学习结构对等性。embedding
方法学到的连接性和结构性的 mixture
。mixture
。例如,下图 (c)
中给出了 SDNE
学到的针对完全二部图 complete bipartite graph
的 node embedding
。作为图的 representation
,embedding
可以应用于各种下游任务,包括:网络压缩 network compression
、可视化 visualization
、聚类 clustering
、链接预测 link prediction
、节点分类 node classification
。
网络压缩:给定图 aggregation based
的方法来压缩图。这方面工作的主要思路是利用图的链接结构link structure
来分组节点和边。《Graph summarization with bounded error》
利用信息论中的 Minimum Description Length: MDL
将图 summarize
为一个 graph summary
和 edge correction
。
类似于这些 representation
,graph embedding
也可以解释为图的 summarization
。《Structural deep network embedding》
和 《Asymmetric transitivity preserving graph embedding》
通过从 embedding
中重建原始图并评估重建误差来明确地测试这一假设。他们表明,每个节点的低维 representation
(在100
的数量级)有助于图的重建。
可视化:由于 embedding
是图在向量空间的表示,因此可以使用降维技术,如主成分分析 PCA
、t-SNE
等技术来对图进行可视化。如 DeepWalk, LINE, SDNE
的原始论文中都展示了 node embedding
的可视化。
聚类:聚类分为两类,即基于结构的聚类、基于属性的聚类。
基于结构的聚类:它又分为两类,即基于社区community-based
的聚类、基于结构等效structurally equivalent based
的聚类。
intra-cluster edge
、子图之间具有少量的簇间边 inter-cluster edge
。hub
节点、异常点)。基于属性的聚类:基于属性的聚类除了观测到的链接之外,还利用节点属性来聚类。
《A spectral clustering approach to finding communities in graphs》
在 embedding
上使用 k-means
对节点进行聚类,并将在 Wordnet
和 NCAA
数据集上获得的聚类可视化,验证了所获得的聚类有直观的解释。
链接预测:网络是根据观测到的实体之间的交互而构建的,这些交互可能是不完整 incomplete
的或者不准确 inaccurate
的。链接预测的目标是识别虚假的交互并预测缺失的交互。人们综述了链接预测领域的最新进展,并将算法分为:基于相似性(局部相似性和全局相似性)的方法、基于最大似然的方法、概率性的方法。
embedding
可以显式或隐式地捕获网络的固有动态 inherent dynamics
,从而可以执行链接预测。实验表明:通过使用 embedding
执行链接预测要比基于传统相似度的链接预测方法更准确。
节点分类:通常由于各种原因,在网络中只有部分节点被标记,大部分节点的标记都是未知的。节点分类任务是通过网络结构和已标记节点来预测这些缺失的标记。
节点分类方法大概分为两类,即基于特征提取的方法和基于随机游走的方法:
embedding
可以解释为基于网络结构自动抽取的特征,因此属于第一类。实验表明:通过使用 embedding
的节点分类可以更准确地预测缺失的标签。
实验配置:32 core 2.6 GHz
的 CPU
、128 GB RAM
、Nvidia Tesla K40C
的单机,Ubuntu 14.04.4 LTS
操作系统。
数据集:我们使用一个人工合成的数据集SYN-SBM
以及 6
个真实数据集,这些数据集的统计信息见下表(No. of labels
表示标签类别数) 。
SYB-SNM
:使用 Stochastic Block Model
方法人工创建的图,其中包括 1024
个节点、3
个社区。我们设置 in-block
概率为 0.1
以及 cross-block
概率为 0.01
。由于我们知道这个图中的社区结构 community structure
,我们用它来可视化通过各种方法学到的 emebdding
。KARATE
:Zachary
的 karate network
是一个著名的大学空手道俱乐部的社交网络。它在社交网络分析中被广泛研究。BLOGCATALOG
:这是一个由BlogCatalog
网站上博主的社交关系组成的网络。标签代表了博主的兴趣,这是通过博主提供的 meta data
推断出的。YOUTUBE
:这是一个 Youtube
用户的社交网络。标签代表了喜欢的视频类型。HEP-TH
:原始数据集包含 1993
年1
月至2003
年4
月期间的High Energy Physics Theory
的论文摘要。我们为这一时期发表的论文建立了一个合作网络 collaboration network
。ASTRO-PH
:这是一个由 1993
年1
月至2003
年4
月期间提交到arXiv
的论文的作者组成的合作网络。PPI
:这是一个人类蛋白质之间的生物交互网络 biological interaction network
。评估指标:
对于图重构和链接预测任务,我们使用 Precision at K:Pr@K
、Mean Average Precision:MAP
为评估指标。
Pr@K
表示对于节点 top K
节点中和节点AP@K
给出节点 Pr@k
均值,即:MAP@K
进一步评估了所有节点的 Pr@k
值。 对于节点分类任务,我们使用 micro-F1
和 macro-F1
指标。
我们使用 graph embedding
重建节点的邻近度,然后根据节点邻近度对节点进行排序,并计算 top K
个预测中实际链接的占比作为重构精度 reconstruction precision
。由于对所有节点 pair
对计算的代价很大 (复杂度为 1024
个节点进行评估。为缓解采样随机性对评估结果的影响,我们随机采样并评估五次,并上报评估结果的均值和方差。
为获得每种 embedding
方法的最佳超参数,我们进行超参数搜索并评估每种超参数的平均 MAP
(评估时采样五次)。最后我们使用最佳超参数来重新训练模型并报告5
次采样的平均结果。
下图给出了不同方法 128
维 embedding
获得的重构精度。结论:
虽然embedding
性能与数据集有关,但是总体而言保留高阶邻近度的 embedding
方法要更好。
拉普拉斯特征图LE
在 SBM
上的出色表现归因于数据集中缺乏高阶结构。
SDNE
在所有数据集上均表现良好,这归因于它从网络中学习复杂结构的能力。
虽然
SDNE
效果好,但是其计算复杂度为,这对于大型图是不现实的。
node2vec
学到的 embedding
具有较低的重构精度,这可能是由于高度非线性的降维导致了非线性的流形。
理论上
node2vec
的高度非线性会导致更好的表达能力,这里node2vec
结果交叉表明出现了严重的过拟合。
HOPE
学习线性的 embedding
但是保留了高阶邻近度,它可以很好地重建图,无需任何额外参数。
进一步地,我们考察 embedding
维度对于重建误差的影响。结论:
embedding
维度的增加,MAP
值也增加。这是很直观地,因为更高的 embedding
维度能存储更多信息。SDNE
可以将图以很高的精度嵌入到 16
维向量空间中,尽管需要解码器及其参数来获得这种精度。由于 embedding
是图中节点的低维向量表示,因此我们可以利用 embedding
来可视化节点从而了解网络拓扑结构。由于不同 embedding
方法保留了网络中的不同结构,因此它们的能力以及对节点可视化的解释也有所不同。
例如,设置广度优先BFS
超参数的 node2vec
学到的 embedding
倾向于将结构等效的节点聚集在一起;直接保留节点之间 k-hop
距离的方法(GF,LE,LLE
的 HOPE,SDNE
的
我们对 SBM, Karate
数据集使用不同方法生成 128
维的节点embedding
,并通过t-SNE
将这些 embedding
可视化到 2D
空间。
SBM
数据集的可视化结果如下图所示。由于我们已知底层社区结构,因此我们使用社区标签为节点着色,不同颜色代表不同社区。
结论:尽管数据集结构良好,所有 embedding
都一定程度上捕获了社区结构,但是由于 HOPE,SDNE
保留了高阶邻近性,因此相比于 LE,GF,LLE
,HOPE,SDNE
可视化的不同社区的间隔更清晰。
Karate
可视化结果如下图所示。结论:
LLE,LE
试图保留图的社区结构,并将较高 intra-cluster
边的节点聚类在一起。
GF
将社区结构紧密地嵌在一起,并使社区内节点远离其它节点。
在 HOPE
中,我们观察到编号为 16,21
的节点,它们在原始图的 Katz
相似度非常低(0.0006
),并在 embedding
空间中相距最远。
node2vec,SDNE
同时保留了节点社区结构和节点结构角色。
32,33
是 degree
很高的 hub
节点,并且是它们各自社区的中心节点。它们被嵌入在一起,并远离其它低 degree
的节点,并且更靠近各自社区的节点。0
充当社区之间的 bridge
,因此SDNE
将节点 0
嵌入到远离其它节点。注意,与其它方法不同,这并不意味着节点 0
和其它节点断开连接,而是 SDNE
将节点 0
标识为独有的节点类型。虽然尚未研究过深度自编码器识别网络中重要节点的能力,但是鉴于这一发现我们认为这一方向是有希望的。
graph embedding
另一个重要应用是预测图中未观测的连接。一个好的 network representation
应该能够很好地捕获图的固有结构,从而预测可能的、但是未观测的链接。
为测试链接预测任务中不同 embedding
方法的性能,对于每个数据集我们随机隐藏 20%
的边,并利用剩余 80%
边来学习 embedding
。然后根据学到的 embedding
来预测训练数据中未观测到的、最有可能的边。
和图重构任务一样,我们随机采样 1024
个节点的随机子图,并针对子图中的隐藏边来预测边是否存在。为缓解采样随机性对评估结果的影响,我们随机采样并评估五次,并上报评估结果的均值和方差。
直接在原始的图上进行评估需要评估
的 node pair
,这对于大一点的图而言计算量太大。
我们对每个emebdding
方法执行超参数搜索,并使用最佳超参数重新在 80%:20%
拆分得到的训练集上重新训练模型。
下图给出了不同方法的 128
维embedding
的效果。结论:
node2vec
在 BlogCatalog
数据集上表现良好,但是在其它数据集上表现不佳(垫底)。HOPE
在所有数据集上均表现良好,这意味着保留高阶邻近性有利于预测未观测到的链接。SDNE
优于所有其它方法,但是在 PPI
数据集上除外。在 PPI
数据集上,随着 embedding
尺寸增加到 8
以上,SDNE
性能急剧下降。进一步地,我们考察 embedding
维度对于链接预测性能的影响。结论:
在 PPI
数据集上,随着 embedding
尺寸增加到 8
以上,SDNE
性能急剧下降。
在 PPI, BlogCatalog
数据集中,与图重构任务不同,随着 embedding
维度的增加链接预测性能不会得到改善。这可能是因为具有更多参数的模型在观测到的链接上过拟合,并且无法预测到未观测的链接。
即使在相同数据集上,方法性能也取决于 embedding
维度。例如:
PPI
数据集上,HOPE
在高维度 embedding
上的效果超越了其它方法。SNDE
在低维度 embedding
上的效果超越了其它方法。我们最终要评估的是在各模型的最佳
embedding
上,每个模型的效果。
良好的 graph embedding
可以捕获网络结构,这对于节点分类很有用。通过使用生成的 embedding
作为特征对节点进行分类,我们比较了不同 embedding
方法的有效性。其中分类算法为 LIBLINEAR
库提供的 one-vs-one
逻辑回归模型。
对于每个数据集,在分类期间我们随机抽取 10% ~ 90%
的标记节点作为训练集,剩余标记节点作为测试集。我们随机执行5
次拆分并报告测试集上评估结果的均值。
下图给出了节点分类实验的结果。结论:
node2vec
在大多数节点分类任务上超越了其它方法。如前所述,node2vec
保留了节点之间的同质性 homophily
,以及结构对等性structural equivalence
。这表明这在节点分类中可能很有用。
例如在 BlogCatalog
中,用户之间可能具有相似的兴趣,但是网络是通过社交关系而不是兴趣关系而建立的。
在 SBM
数据集中,其它方法性能超越了 node2vec
。这是因为SBM
数据集的标签反映了社区,而节点之间没有结构上的对等性。
进一步地,我们考察 embedding
维度对于节点分类性能的影响。其中训练集、测试集拆分比例为 50%:50%
。结论:
SBM
是非常结构化的社区,因此即使是 8
维的 embedding
也可以达到很好的效果。PPI,BlogCatalog
数据集,node2vec
需要 128
维的 embedding
才能达到最佳性能。 这里我们要解决三个问题:
embedding
方法对于超参数鲁棒性如何?embedding
被使用的下游任务?我们通过分析每个 embedding
方法上不同超参数的性能来回答这些问题。我们评估了 SBM, PPI, Hep-th
数据集。由于图拉普拉斯没有超参数,因此不在我们分析范围之内。
Graph Factorization:GF
:GF
模型的目标函数包含了权重正则化项,该项带有一个超参数:正则化系数。正则化系数可以控制 embedding
的泛化能力:
我们在下图的实验结果中观察到这种效果。可以看到:
HOPE
: HOPE
将节点相似度矩阵分解从而得到node embedding
,因此超参数取决于获得相似度矩阵的方法。由于我们在实验中使用 Katz
指数来计算相似度,因此我们评估了衰减因子
embedding
空间中相近的位置。weak community
的图,重要的是捕获高阶距离,因此较高的 embedding
。下图的实验结果验证了我们的假设。结论:
SBM
由紧密的社区组成,因此增加 PPI, HEP-th
数据集中,随着 PPI, Hep-th
数据集包含高阶的链接。SDNE
:SDNE
使用耦合的深度自编码器来嵌入图,它利用超参数
下图给出了不同参数值的实验结果。结论:
Hep-th
数据集,最佳 MAP
提升超过 3
倍;对于 PPI
数据集,最佳 MAP
提升大约 2
倍。node2vec
在图上执行有偏得随机游走,并将共现的节点嵌入到 embedding
空间中靠近得位置。在该方法得各个超参数中,我们分析超参数 10
,随机游走序列长度为 80
)。
超参数 BFS
和 DFS
之间插值,从而反应结点的不同类型的相似性。
返回参数 Return Parameter
一个较大的值
这种策略鼓励适当的进行探索新结点,并避免采样过程中的冗余2-hop
(即:经过两步转移又回到了结点本身)。
一个较小的值
这种策略使得随机游走序列尽可能地留在源点
内外参数 In-out parameter
BFS
的行为。DFS
的行为。但是这种策略和BFS、DFS
本质上是不同的:我们的策略采样的结点与源点的距离并不是严格相等的(BFS
)、也不是严格递增的 (DFS
)。另外我们的策略易于预处理,且采样效率很高。
我们实验不同 PPI, Hep-th
数据集得效果如下图所示。结论:
我们实验不同 SBM
的效果。结论:
MAP
性能得到提升,直到最佳性能。SBM
具有紧密联系的、结构良好的社区,因此最优
我们发布了一个开源的 Python
库:Graph Embedding Methods: GEM
(https://github.com/palash1992/GEM
),它为这里介绍的所有方法的实现及其评估指标提供了一个统一的接口。该库同时支持加权图和无权图。GEM
的 hierarchical design
和模块化实现有助于用户在新的数据集上测试所实现的方法,并作为一个 platform
来轻松开发新的方法。
GEM
提供了 Locally Linear Embedding
、Laplacian Eigenmaps
、Graph Factorization
、HOPE
、SDNE
、以及 node2vec
的实现。对于node2vec
,我们使用作者提供的C++
实现并提供一个 Python
接口。
此外,GEM
提供了一个接口来在上述四个任务上评估学到的 embedding
。该接口很灵活,支持多种边重建指标,包括余弦相似度、欧氏距离、以及 decoder based
指标。对于多标签的节点分类,该库使用 one-vs-rest
逻辑回归分类器,并支持使用其他临时 ad hoc
的分类器。
我们认为在图嵌入领域有三个有前途的研究方向:
探索非线性模型:如综述所示,通用的非线性模型(如,基于深度学习的模型)在捕获图的固有动态inherent dynamics
方面显示出巨大的前景。这些非线性模型有能力近似任意函数,但是缺点是可解释性有限。
进一步研究这些模型所学到的 embedding
的可解释性,可能是非常有用的。
研究网络的演变 evolution
:利用 embedding
来研究图的演变是一个新的研究领域,需要进一步探索。
生成具有真实世界特征的人工合成网络:生成人工合成网络一直是一个流行的研究领域,主要是为了便于模拟。真实graph
的低维向量 representation
可以帮助理解图结构,因此对生成具有真实世界特征的人工合成图很有帮助。
图机器学习的核心问题是:找到一种将图结构信息结合到机器学习模型中的方法。例如:
relationship strength
或者共同好友数量。从机器学习角度来看,面临的挑战是:没有直接的方法可以将有关图结构的高维非欧信息编码为特征向量。为了从图上提取图结构信息,传统的机器学习方法通常依赖于图的统计信息(如 degree
等)、核函数、或者精心设计的用于衡量图局部邻域结构的特征。但是,这些方法都有局限性:
最近涌现出很多方法来寻求学习图的有效representation
从而能够编码有关图结构信息,这些方法背后的思想是:学习一个映射,该映射将节点或者子图或者整个图映射到低维向量空间 emebdding
空间中的几何关系能够反映原始图结构。一旦得到这样的映射,就可以将学到的 embedding
用作下游机器学习任务的特征输入。
表示学习representation learning
方法和之前工作的主要区别在于如何处理图结构表示的问题。
representation learning
将该问题视为机器学习任务本身,使用数据驱动的方法来学习对图结构进行编码的 emebdding
。假设representation learning
的输入为无向图
representation learning
的目标是利用
大多数方法仅使用
论文 《Representation Learning on Graphs: Methods and Applications》
以综述的形式总结了这些 representation learning
方法。
我们首先讨论节点 embedding
,其目的是将节点编码为低维向量,从而包含节点在图中的位置信息以及节点的局部邻域结构。这些低维 embedding
可以看作是将节点投影到低维潜在空间中,其中潜在空间中节点之间的几何关系对应于原始空间中节点之间的交互(如是否存在边)。
下图给出了著名的 Zachary Karate Club
社交网络的节点 embedding
,这些二维的节点 embedding
捕获了社交网络中隐式的社区结构 community structure
。下图中,如果两个用户是好友关系,则他们之间存在边。节点根据不同社区community
进行着色。
在讨论各种节点 embedding
技术之前,我们首先提出一个统一的 encoder-decoder
框架,在该框架中统一了各种各样的节点 embedding
方法。
在encoder-decoder
框架中,我们围绕两个关键的映射函数来组织各种方法:
encoder
:它将每个节点映射到一个低维向量。decoder
:它从学到的 embedding
中解码有关图结构的信息。encoder-decoder
思想背后的直觉如下:如果我们可以从encoder
的低维的 embedding
中解码高维的图信息(如,节点在图中的全局位置或节点的局部邻域结构),则原则上这些 embedding
包含了下游机器学习任务所需的所有信息。
encoder
是一个函数: embedding
向量 embedding
向量维度。
decoder
也是一个函数,它接收一组节点 embedding
,并从这些 embedding
中解码人工指定的图统计信息。如,decoder
可能会根据给定节点的 embedding
预测节点之间的边,或者预测节点所属的社区。
原则上 decoder
可以有很多选择,但是绝大多数方法都是采用基础的 pairwise decoder
:
它将一对节点的 embedding
映射到一个实数值的节点相似度,从而刻画原始图中两个节点的相似性。
encoder-decoder
框架整体架构如下图所示。
encoder
根据节点在图中的位置、节点局部邻域结构信息、节点属性信息,从而将节点 decoder
从低维向量 通过联合优化 encoder
和 decoder
,系统学会了将图结构有关的信息压缩到低维 embedding
空间中。
我们将 pairwide decodr
应用到一对 embedding
encoder, decoder
,从而最大程度地减少重构误差,使得:
即,我们要优化 encoder-decoder
模型,以便可以从节点的低维 embedding
其中
在实践中,大多数方法通过最小化经验损失
其中:
pair
对组成。一旦我们优化了 encoder-decoder
,就可以使用训练好的 encdoer
为节点生成 embedding
,然后将其作为下游机器学习任务的特征输入。例如,可以将学到的 embedding
作为逻辑回归分类器的输入,从而预测节点所属的社区。
通过这种 encoder-decoder
视角,我们沿着以下四个部分对各种节点 embedding
方法进行讨论:
pairwise similarity function
encoder
函数 ENC
:用于生成节点 embedding
。该函数包含大量可训练的参数,这些参数在训练期间进行优化。decoder
函数 DEC
:用于从生成的节点 embedding
中重建 pairwise
节点相似性。该函数通常不包含可训练的参数。正如我们即将讨论的,各种节点 embedding
方法之间的主要区别在于如何定义这四个部分。
我们讨论的所有方法都涉及通过最小化损失函数来优化 encoder
的参数。大多数情况下我们使用随机梯度下降算法来优化,尽管某些算法确实允许通过矩阵分解来获得闭式解。
注意,这里我们关注的重点并不是优化算法,而是不同 embedding
方法之间的更高层次的差异,而与底层优化方法的细节无关。
大多数节点 embedding
方法都依赖于我们所说的浅层嵌入 shallow embedding
。对于这些浅层 embedding
方法,将节点映射到 embedding
向量的 encoder
函数仅仅是一个 embedding lookup
:
其中:
embedding
向量的 embedding
矩阵,第 embedding
向量。one-hot
向量。浅层 embedding
方法的可训练参数仅仅是 embedding
矩阵
浅层 embedding
方法在很大程度上受到降维dimensionality reduction
和多维缩放multi-dimensional scaling
中的经典矩阵分解技术的启发。但是,我们在 encoder-decoder
框架中重新解释了它们。
下表总结了 encoder-decoder
框架中的一些著名的浅层 embedding
方法,我们根据几个方面来区分它们:decoder
函数、图相似性度量、损失函数。
总体而言它们分为基于矩阵分解的方法Matrix Factorization
、基于随机游走的方法Random Walk
。注意,在基于随机游走的方法中,decoder
和 similarity
函数都是非对称的,其中相似度函数
注意,相似度函数
就是 。在不同的模型中, 有不同的表现形式。而在基于随机游走的方法中,其表现形式就是 。
早期的节点 embedding
方法主要集中于矩阵分解上,这直接受到经典的降维技术的启发。
拉普拉斯特征图Laplacian Eigenmaps
:最早的、最著名的基于矩阵分解的方法是拉普拉斯特征图Laplacian Eigenmaps:LE
方法。我们可以将拉普拉斯特征图视为一种 encoder-decoder
框架内的浅层 embedding
方法,其中 decoder
定义为:
损失函数根据节点pair
对的相似性进行加权:
内积方法Inner-product method
:在拉普拉斯特征图之后,有大量基于 pairwise
的、内积式 decoder
的 embedding
方法,其中 decoder
定义为:
即两个节点之间关系的强度strength
和它们 embedding
的内积成正比。
图因子分解 Graph Factorization:GF
、GraRep
、HOPE
都完全属于此类。这三种方法都使用内积式 decoder
,都采用均方误差 mean squared error:MSE
损失函数:
它们之间的主要区别在于采用的节点相似性函数不同,即如何定义
GF
算法直接基于邻接矩阵来定义节点相似度,即 GraRep
算法考虑邻接矩阵的各种幂次从而捕获高阶节点相似性,如 HOPE
算法支持通用的相似性度量,如基于 Jaccard
指标的邻域交集。这些不同的相似性函数在建模一阶邻近性(如
本节中我们将这些方法统称为基于矩阵分解的方法,因为大致上它们优化了以下形式的损失函数:
其中:
embedding
矩阵。直观上讲,这些方法的目标是为每个节点学习 embedding
,使得学到的 embedding
向量之间的内积近似于某个给定的节点相似性度量。
最近一些比较成功的浅层 embedding
方法都是基于随机游走统计信息来学习节点 embedding
。它们的关键创新在于:优化节点 embedding
,使得随机游走序列上共现的节点具有相似的 embedding
,如下图所示。
因此,这些随机游走方法并没有像基于矩阵分解方法那样使用确定性的节点相似性度量,而是采用一种灵活的、随机的节点相似性度量,从而在很多场景下都具有出色的性能。
基于随机游走的方法从每个节点 embedding
向量,使得两个 embedding
向量
DeepWalk & node2vec
:与上述矩阵分解方法一样,DeepWalk
和 node2vec
依赖浅层 embedding
并使用内积式 decoder
。但是,这些方法不是对确定性的节点相似性度量进行解码,而是优化 embedding
从而对随机游走的统计信息进行编码。
这些方法背后的基本思想是学习 embedding
,使得:
其中:
注意:不像基于矩阵分解方法那样使用确定性的、对称的节点相似性度量(如边的强度
进一步地,DeepWalk
和 node2vec
最小化以下交叉熵损失函数:
其中训练集
由于计算 DeepWalk
和 node2vec
使用不同的优化和近似来计算 Softmax
和负采样技术。
node2vec
和 DeepWalk
之间的关键区别在于:node2vec
允许定义灵活的随机游走策略,而 DeepWalk
只能使用简单的无偏随机游走。具体而言, node2vec
引入两个随机游走超参数 bias
。假设随机游走当前节点为
返回参数 Return Parameter
一个较大的值
这种策略鼓励适当的进行探索新结点,并避免采样过程中的冗余2-hop
(即:经过两步转移又回到了结点本身)。
一个较小的值
这种策略使得随机游走序列尽可能地留在源点
内外参数 In-out parameter
BFS
的行为。DFS
的行为。通过引入这些超参数,node2vec
可以在广度优先搜索和深度优先搜索之间折衷。实验发现:调整这些超参数可以使得模型在学习社区结构 community structure
和局部结构角色 local structrual role
之间折衷,如下图所示。下图表示从《悲惨世界》小说中得到的人物与人物互动图的两个不同的视角,如果相应的人物有互动则两个节点就会连接起来。
structural equivalence
,或者说两个节点在其局部邻域中扮演类似的角色(例如,bridging node
为蓝色)。下图说明了 node2vec
如何通过
图 A
:假设随机游走刚从节点
图 B
:广度优先搜索 BFS
和深度优先搜索 DFS
的随机游走之间的差异。
BFS
的随机游走主要探索节点的 1-hop
邻域,因此在捕获局部结构角色方面更为有效。DFS
的随机游走主要探索得更远,对于捕获社区结构方面更为有效。LINE
:LINE
是另一种非常成功的浅层 embedding
方法,它不是基于随机游走,而基于共现。
LINE
经常与 DeepWalk
和 node2vec
进行比较,它结合了两个 encoder-decoder
目标,分别优化了一阶节点相似性和二阶节点相似性。
一阶节点相似性为 decoder
为:
二阶节点相似性为 decoder
为:
一阶目标和二阶目标都是基于 KL
距离的损失函数。因此, LINE
在概念上和 node2vec, DeepWalk
有关,因为LINE
使用了概率性的 decoder
和损失函数。但是,LINE
明确地分解了一阶相似度和二阶相似度,而不是采用固定长度的随机游走序列。
HARP
:HARP
(《Harp: Hierarchical representation learning for networks》
)是一种元数据策略,通过图预处理步骤来改善各种随机游走方法。
HARP
使用图粗化 coarsening
过程将 DeepWalk, node2vec, LINE
等。在得到 embedding
之后,每个超级节点学到的 emebdding
将作为超级节点中每个组成节点的初始 embedding
,然后执行更细粒度的 embedding
学习。
这种方式在不同粒度上以层次方式反复执行,每次都能得到更细粒度的 emebdding
。实践表明HARP
可以持续改善 DeepWalk, node2vec, LINE
等方法的性能。
目前为止我们研究过的所有节点 embedding
方法都是浅层 embedding
方法,其中 encoder
只是一个简单的 embedding lookup
。这种方式有很多缺点:
浅层embedding
的encoder
中节点之间没有共享任何参数,即 encoder
只是基于节点 ID
的 embedding lookup
。
embedding
方法的泛化能力较差。embedding
方法中参数数量为 浅层 embedding
的 encoder
无法利用节点属性。在很多大型图中,节点有丰富的属性信息(如社交网络的用户画像),这些属性信息对于节点在图中的位置和角色具有很高的信息价值。
浅层 embedding
方法本质是 transductive
的,它们只能为训练阶段存在的节点生成 embeddign
,无法为从未见过的节点生成 embedding
。因此无法应用到不断演变的图、需要泛化到新的图等场景。
最近已经提出很多方法来解决这些问题。这些方法仍然使用 encoder-decoder
框架,但是和浅层 embedding
不同之处在于:它们使用更复杂的 encoder
(通常基于深度神经网络),并且更依赖于图的结构和节点属性。
Deep Neural Graph Representations: DNGR
和 Structural Deep Network Embeddings: SDNE
解决了上面的第一个问题。和浅层 embedding
方法不同,它们使用深度神经网络将图结构直接融合到 encoder
算法中。
它们背后的基本思想是:使用自编码器来压缩有关邻域的信息(如下图所示)。另外,不同于之前的方法,DNGR, SDNE
的 decoder
只有一个节点而不是一对节点。
在这两个方法中,令 DNGR
和 SDNE
自编码器的目标是基于邻域向量 embedding
向量中重建
因此这些方法的损失函数为:
和 pairwise decoder
一样,我们选择 embedding
DNGR,SDNE
将节点的邻域信息压缩为低维向量。
对于 SDNE,DNGR
, encoder
和 decoder
函数均由多个堆叠的神经网络层组成,encoder
的每一层都降低了其输入的维度,decoder
的每一层都增加了其输入的维度。
SDNE
和 DNGR
在相似度函数(用于构造邻域向量
DNGR
根据随机游走序列中两个节点共现的 pointwise mutual information:PMI
来定义 DeepWalk
和 node2vec
。
SDNE
简单地定义
SDNE
还结合了自编码器的损失函数和拉普拉斯特征图的损失函数:
注意:公式 SDNE, DNGR
可以将有关节点全局邻域的结构信息以正则化的形式直接合并到 encoder
中。
这对于浅层 embedding
方法是不可能的,因为浅层 embedding
方法的 encoder
取决于节点 ID
,而不是节点全局邻域结构。
尽管SDNE, DNGR
在 encoder
中编码了有关节点全局邻域的结构信息,但是它们仍然存在一些严重的局限性。
SDNE,DNGR
也是 transductive
的,无法处理不断演变的图,也无法跨图进行泛化。最近许多节点 embedding
方法旨在通过设计依赖于局部邻域(而不是全局邻域)的 encoder
来解决浅层 embedding
方法和自编码器方法的缺陷。这些方法背后的直觉是:通过聚合来自局部邻域的信息来为节点生成 embedding
,如下图所示。
为了生成节点 A
的 embedding
,模型聚合了来自 A
的局部邻域(节点 B,C,D
)的消息。然后,这些邻域节点又基于它们各自邻域来聚合消息,依次类推。下图给出了一个迭代深度为 2
的版本,它聚合了节点 A
的 2-hop
邻域消息,原则上可以为任意深度。
和之前讨论的方法不同,这些邻域聚合算法依赖于节点属性 embedding
。在没有属性信息的情况下,也可以使用简单的图统计信息(如节点 degree
)作为节点属性;或者也可以为每个节点分配一个 one-hot indicator
作为属性。
这些邻域聚合方法通常称作卷积,因为它们将节点embedding
表示为周围邻域的函数,这和计算机视觉中的卷积算子很类似。
在编码阶段,邻域聚合方法以迭代或递归的方式构建节点的 embedding
。
embedding
初始化为节点属性向量。encoder
算法的每次迭代过程中,节点使用一种聚合算法来聚合邻域的 embedding
。embedding
,它结合了邻域聚合 embedding
以及该节点上一轮迭代的 embedding
。embedding
被馈入一个 dense
层从而得到本轮迭代的 embedding
。以上过程不断重复进行,使得节点 embedding
聚合了图中距离该节点越来越远的信息。但是 embedding
维度仍然保持不变并限制在低维,迫使 encoder
不断将越来越大范围的邻域的信息压缩到低维向量。
经过 emebdding
向量作为节点的输出 representation
。
整体算法如下所示:
邻域聚合 encoder
算法:
输入:
输出:节点的 representation
算法步骤:
初始化:
迭代,
对于每个节点
执行归一化:
返回
有很多遵循上述算法的最新方法,包括 GCN
、Column Network
、GraphSAGE
等。这些算法中的可训练参数包括一组权重矩阵 embedding
方法不同,这些参数在所有节点之间共享。
对每个节点都相同的聚合函数和权重矩阵为所有节点生成 embedding
,在这个过程中仅输入节点属性和邻域结构在不同节点之间发生变化。这种参数共享提高了效率(即参数规模和图的大小无关),也提供了正则化,还允许为训练期间从未见过的节点生成 embedding
(即 inductive learning
)。
GraphSAGE, Column Network
以及各种 GCN
方法都遵循以上算法,但是区别在于执行聚合(Agg
函数)、向量组合(COMBINE
函数)的方式不同。
GraphSAGE
使用向量拼接作为 COMBINE
函数,并允许使用通用聚合函数作为 Agg
函数,如均值池化、最大池化、LSTM
。他们发现更复杂的聚合器,尤其是最大池化,获得了明显的收益。
GCN
和 Column Network
使用加权和的方式作为 COMBINE
函数,并使用均值聚合(加权或者不加权)作为 Agg
函数。
Column Network
使用一个额外的插值项,即在 Normalize
之前:
其中
这个插值项允许模型在迭代过程中保留局部信息。由于随着
原则上可以将 GraphSAGE, Column Network, GCN
的 encoder
和前面讨论的任何一种 decoder
以及损失函数一起使用,并使用 SGD
来优化。
在节点分类、链接预测的 benchmark
上,实验发现这些方法相对浅层 embedding
的 encoder
提供了一致的增益。
从 high level
上讲,这些方法解决了浅层 embedding
的四个主要限制:
encoder
中。sub-linear
,即低于 embedding
,即 inductive learning
。目前为止 encoder-decoder
架构默认都是无监督的。即,模型在一组节点上进行优化,优化目标是重构依赖于图
但是,很多 embedding
算法(尤其是邻域聚合方法)也可以包含 task-specific
监督信息,尤其是通常会结合节点分类任务中的监督信息来学习节点 embedding
。
为简单起见,我们讨论节点具有二元类别标签的情形,但是我们的讨论很容易扩展到更复杂的多类分类问题。
假设每个节点 sigmoid
函数,函数的输入为节点 embedding
:
其中
然后我们计算预测标签和真实标签之间的交叉熵作为损失函数:
最后我们通过 SGD
来优化模型的参数。
这种 task-specific
监督信息可以完全替代掉 decoder
中的重建损失,也可以和 decoder
重建损失一起使用(即同时包含监督损失和无监督损失)。
前面讨论的都是简单的无向图,而现实世界中很多图具有复杂的多模态 multi-modal
、多层级(如异质节点、异质边) 的结构。已有很多工作引入了不同的方法来处理这种异质性。
很多图包含不同类型的节点和边。如,推荐系统中包含两种类型的节点:用户节点、item
节点。解决该问题的通用策略是:
对不同类型的节点使用不同的 encoder
。
使用 type-specific
参数扩展 pairwise decoder
。例如,在具有不同类型边的图中,可以将标准的内积式 edge decoder
(即 bilinear
形式:
其中
最近人们提出了一种从异质图中采样随机游走序列的策略,其中随机游走仅限于特定类型节点之间。这种方法允许我们将基于随机游走的浅层 embedding
方法应用于异质图。
某些场景下图有很多层,其中不同层包含相同的节点,即多层图 multi-layer graph
。注意,这里不是神经网络的层数,而是图数据的层数。此时跨层的信息共享是有益的,因为节点在其中一层的 embedding
可以接收节点在其他层的 embedding
信息。
OhmNet
结合了带正则化项的 node2vec
从而跨层绑定 embedding
。具体而言,假设节点
其中:
embedding
。OhmNt
通过使用 hierarchy
来扩展这个思想,从而可以学习不同graph layer
上的 embedding
,而正则化项可以在 graph layer
的 parent-child
关系之间依次使用。
如下图所示:
A
:一个包含四层的图,其中相同节点出现在不同的层。这种多层结构可以通过正则化来学习,使得相同节点在不同层之间的 emebdding
彼此相似。
B
:通过层次结构来展示多层图,其中 non-root
层包含所有子层的所有节点和所有边。
这种结构可以学习不同层级结构的 embedding
,并在 parent-child
层级关系之间应用正则化,使得相同节点在 parent
和 child
层级之间的 embedding
相似。
C-E
:大脑组织中不同的 “蛋白质-蛋白质”作用图protein-protein interaction graph
对应的multi-layer graph embedding
。embedding
是通过 OhmNet
方法得到并通过 t-SNE
可视化。
C
:不同组织区域中的层级结构。D
:脑干brainstem
层得到的蛋白质 embedding
的可视化。E
:全脑whole-brain
层得到的蛋白质 embedding
的可视化。目前为止我们研究的所有方法都优化节点 embedding
,使得图中距离相近的节点具有相似的 embedding
。但是在很多任务中,更重要的是学习和节点结构角色structural roles
相对应的表示形式,而与它们在图中的全局位置无关。
node2vec
为这个问题提供了一种解决方案,它采用有偏的随机游走从而更好地捕获结构角色。struc2vec
和 graphwave
提出了专门用于捕获结构角色的节点 embedding
方法。struc2vec
涉及一系列从原始图 k-hop
邻居之间的结构相似性。
具体而言,令 k-hop
的节点集合, degree
的有序序列。在辅助图
其中:
degree
序列 dynamic time wariping:DTW
来计算这两个序列之间的距离。
通过
来刻画节点 的 阶邻域,通过 来计算节点 和节点 之间 阶邻域的差异。 越小则说明节点 和 之间越相似。
在计算得到这些加权辅助图之后,struc2vec
对它们执行有偏的随机游走,并将这些随机游走作为 node2vec
优化算法的输入。
graphwave
采用另一种非常不同的方法来捕获结构角色,它依赖于谱图小波 spectral graph wavelet
以及 heat kernel
技术。
简而言之,令 degree
矩阵, eigenvector
组成的矩阵 eigenvector matrix
,对应的特征值eigenvalues
为
定义 heat kernel
为 scale
超参数。
对于每个节点 graphwave
使用
其中:
one-hot indicator
向量,表示 graphwave
表明这些 degree
。选择一个合适的 scale
graphwave
能够有效地捕获有关图中节点角色的结构信息。
graphwave
的一个典型示例如下图所示:
A
:一个人工合成的杠铃图,其中节点根据其结构角色着色。
B-D
:杠铃图上不同结构角色检测算法输出的节点emedding
,通过 PCA
降维来可视化。
B
:RoIX
算法,它采用人工设计的特征,是 baseline
方法。C
:struc2vec
算法。D
:graphwave
算法。所有方法都可以正确区分杠铃末端和杠铃其它部分,只有 graphwave
方法能够正确区分所有结构角色。
另外,D
的节点看起来比 A
中原始图节点少得多,因为 graphwave
将颜色相同(即结构角色相同)的节点映射到 embedding
空间中几乎相同的位置。
节点 embedding
最常见的应用是可视化 visualization
、聚类 clustering
、节点分类 node classification
、链接预测 link prediction
。
可视化和模式挖掘:节点 embedding
为可视化提供了强大的新的范式paradigm
。因为节点被映射到实值向量,因此研究人员可以轻松地利用现有的通用技术对高维数据集进行可视化。
例如,可以将节点 embedding
和 t-SNE, PCA
之类的通用技术结合,从而得到图的二维可视化。这对于发现社区以及其它隐藏结构非常有用。
聚类和社区检测:和可视化类似,节点 embedding
也是对相关节点进行聚类的强大工具。同样地,由于每个节点都和实值向量相关联,因此可以将通用聚类算法应用到节点embedding
上,如k-means, DB-scan
等。
这为传统的社区检测技术提供了开放的、更强大的替代方案,并且还开辟了新的天地,因为节点 embedding
不仅可以捕获社区结构,还可以捕获不同节点扮演的结构角色。
节点分类和半监督学习:节点分类可能是评估节点 embedding
的最常见 baseline
任务。大多数情况下,节点分类任务是半监督学习的一种形式,其中仅一小部分节点的标签可用,目标是仅基于这一小部分标记节点来标记整个图。
链接预测:节点 embedding
作为链接预测的特征也非常有用,其目标是预测缺失的边或将来可能形成的边。
链接预测是推荐系统的核心,其中节点 embedding
反映了节点之间的深度交互。典型的场景包括预测社交网络中缺失的好友链接,电影推荐中预测用户和电影之间的亲和力 affinity
。
现在我们考虑子图或者全图的 embedding
,其目标是将子图或者整个图编码为低维 embedding
。
正式地讲,我们需要学习一个诱导子图induced subgraph
embedding
。然后
子图的 representation learning
和graph kernel
密切相关。graph kernel
定义了子图之间的距离度量,但是这里我们不会对 graph kernel
进行仔细讨论,因为这是一个庞大、丰富的研究领域。我们讨论的方法和传统的 graph kernel
不同,我们寻求从数据中学习有用的 representation
,而不是通过 graph kernel
函数得到预先指定的feature representation
。
有很多方法都是基于前面介绍的单个节点 embedding
的技术。但是,和节点 embedding
不同,大多数子图 emebdding
方法都是基于完全监督的 fully-supervised
。因此,这里我们假设子图 embedding
都是采用交叉熵损失函数。
有几种子图 emebdding
技术可以看作是基于卷积的节点 embedding
算法的直接扩展。这些方法背后的基本直觉是:它们将子图等价于节点 embedding
的集合。它们使用卷积的邻域聚合思想为节点生成 embedding
,然后使用额外的模块来聚合子图对应的节点 embedding
集合。
这里不同方法之间的主要区别在于:如何聚合子图对应的节点 embedding
集合。
sum-based
方法:
《convolutional molecular fingerprints》
通过对子图中所有节点 embedding
进行求和,从而得到子图的 embedding
:
其中 encoder
算法的变体来生成的。
《Discriminative embeddings of latent variable models for structured data》
采用类似于 sum-based
方法,但是概念上它和 mean-field inference
相关:如果图中的节点视为潜在变量,则邻域聚合卷积 encoder
算法可以视为一种 mean-field inference
的形式,其中消息传递操作被可微的神经网络替代。因此,该论文提出了基于 Loopy Belief Propagation
的 encoder
,基本思想是为每条边 embedding
然后根据这些临时 embedding
聚合得到节点 embedding
:
一旦得到节点 embedding
,论文使用子图中所有节点 embedding
的简单求和从而得到子图的 embedding
。
graph-coarsening
方法: 《Spectral networks and locally connected networks on graphs》
也采用了卷积方法,但是它并未对子图的节点 embedding
求和,而是堆叠了卷积层以及图粗化 graph coarsening
层(类似于 HARP
方法)。
在图粗化层中,节点被聚类在一起(可以使用任何图聚类算法),并且聚类之后使用一个簇节点来代表簇内所有节点。这个簇节点的 embedding
为簇内所有节点 embedding
的最大池化。然后,新的、更粗粒度的图再次通过卷积 encoder
,并不断重复该过程。
从概念上讲,GNN
和邻域聚合卷积 encoder
算法密切相关。但是GNN
的直觉是:将图视为节点之间消息传递的框架,而不是从邻域那里收集信息。
在原始 GNN
框架中,每个节点以一个随机的 embedding
GNN
算法每轮迭代过程中,节点根据其邻域消息更新 embedding
为:
其中:embedding
向量维度。
上述公式以递归的方式重复迭代直到 embedding
收敛为止,其中必须确保
一旦经过 embedding
为
《Gated Graph Sequence Neural Networks》
使用 GRU
扩展和修改了 GNN
框架,它使用节点属性来初始化
其中
《Neural Message Passing for Quantum Chemistry》
考虑 GNN
的另一种迭代方式:
其中:
这个称为消息传递神经网络 Message Passing Neural Networks:MPNNs
,它可以概括很多图神经网络方法。
所有这些图神经网络方法原则上可以用于 node-level
的 embedding
,尽管它们更经常用于 subgraph-level
的 embedding
。
为了计算子图embedding
,可以采用任何聚合过程。也可以引入一个“虚拟”的超级节点来完成聚合,该超级节点连接到目标子图中的所有节点。
embedding
主要用于子图分类。例如对不同分子对应的图的属性进行分类,包括分子药物的治疗效果、分子材料的功能等。也可以将子图 embedding
用于图像分类(将图像转换为 graph
之后)、预测计算机程序是否满足某种形式的属性、以及执行逻辑推理任务。目前graph representation
领域还有很多悬而未决的问题:
可扩展性scalability
:尽管大多数方法理论上都有很高的可扩展性(时间复杂度 embedding
,并且假设用于训练和测试的所有节点的属性、embedding
、以及 edge list
都可以放在内存中,这在现实中与实际情况不符。
解码高阶主题 motifs
:近年来很多工作都致力于改善生成节点 embedding
的 encoder
,但是 decoder
还是最基础的 pairwise decoder
。这种 decoder
可以预测节点之间的成对关系,并忽略涉及两个以上节点的高阶图结构。
众所周知,高阶结构主题对于复杂网络的结构和功能是必不可少的,设计能够解码复杂主题的 decoder
算法是未来工作的重要方向。
动态图:很多领域都涉及高度动态的图,但是目前我们缺乏建模动态图 embedding
的方法。
大量候选子图的 inference
:当前子图 embedding
方法的主要技术限制在于它们要求在学习过程之前预先指定目标子图。我们需要改善子图 embedding
方法,使得该方法能够有效地自动推断大量的候选子图,无需人工指定。
可解释性:representation learning
缓解了人工设计特征的负担,但是代价是可解释性较差。除了可视化和 benchmark
评估之外,还必须开发新技术以提高学到的 embedding
的可解释性。我们需要确保这些 embedding
方法真正学到图相关的信息,而不仅仅是利用 benchmark
的一些统计趋势。