网络嵌入综述

其他
字数统计: 11.4k   |   阅读时长≈ 41 分钟

https://link.springer.com/article/10.1007/s00521-020-04908-5

Network representation learning: a systematic literature review

1.概述

1.1 背景

Data Representation：用一系列符号或者数字也就是特征向量来描述某个对象，它能反映所描述对象的特征、结构以及分布信息。一个好的数据表示通常能大大减小数据的体量，同时保持原始数据的基本特征以及对噪声的鲁棒性。表示学习近些年来在模式识别和机器学习领域是一个非常重要的研究热点，在很多顶级期刊会议，如TPAMI、TNNLS、TKDE、KDD、NIPS、ICML、AAAI、IJCAI以及ICLR等，都有很多相关文章。

表示学习可以直接从原始低维感知数据中学习到高维抽象特征，这更有利于后续的数据分析和处理。深度学习是表示学习的一种典型方法，它能自动提取适当的特征或者从数据中获取到对个级别的表示。深度学习技术已经成功应用在语音识别、信号处理、图像识别、对象识别等领域，尤其是在自然语言处理领域。

在表示学习的浪潮中，网络表示学习（又称网络嵌入）也在蓬勃发展。因为从网络数据中提取结构信息的传统方法通常取决于拓扑统计信息、聚合系数或者设计精良的人工特征，这带来了很多弊端。因此受成功应用在NLP领域的表示学习的启发，网络表示学习旨在从给定网络数据中学习到低维向量空间中的一些特征，但是编码了各种列结构和语义信息。获取到数据向量表示后，可以通过现成的机器学习方法直接解决网络挖掘问题。网络表示学习已经被证明可用于许多数据挖掘和机器学习任务，比如链路预测、节点分类、网络重构、推荐、可视化以及社区发现等等。下图展示了2010年~2020年网络表示相关论文数量：

下图展示了近10年来，网络表示学习领域不同子方向的论文数量：
## 1.2 图嵌入 VS 网络嵌入

1.3 分类框架

1.4 定义

1.4.1 网络中的数据

  1. 网络定义：G=(V,E)G=(V,E)，V表示顶点集合，E表示顶点间边的集合。

  2. **同构/异构网络：**给定G=(V,E)G=(V,E)，ϕ:V→A\phi:V\rightarrow A，Ψ:E→R\Psi:E\rightarrow R是顶点和边的映射函数，如果∣A∣>1|A|>1或者∣R∣>1|R|>1则网络为异构网络，否则为同构网络。

    https://www.jiqizhixin.com/graph/technologies/9f924061-6327-40af-a9a6-b5d923f6f1c2

    当代大多数信息网络分析都有一个基本假设：对象或链接的类型是独特的。也就是说，网络是同构的，包含相同类型的对象和链接。这些同构网络通常是通过简单地忽略物体和链接的异质性或仅考虑一种类型的对象之间的一种类型的关系。然而，大多数真实网络都包含多类型的交互关系，我们可以用不同类型的对象和链接将它们建模为异构信息网络（简称HIN或异构网络）。

    基于这个概念之上，异构信息网络的定义为：如果对象的类型| A |>1 或关系类型| R | > 1，信息网络被称为异构信息网络；否则，它是一个同质的信息网络。与广泛研究的同构网络相比，异构信息网络包含更丰富的结构和语义信息，为数据挖掘提供了大量的机会和挑战。

  3. **知识图谱：**一个知识图谱定义为有向图，图中节点表示实体，边表示subject-property-object三元组关系，表示为<h,r,t><h,r,t>。通常在一个知识图谱中，边和节点的类型有多种，因此知识图谱可以看做异构网络的一种。

  4. **静态/动态网络：**动态网络随着时间会不断变化，时刻t的网络表示为Gt={Vt,Et}G^t=\{V^t,E^t\}，其中VtV^t表示节点集合，EtE^t表示t时刻边的状态。本文中未作特殊说明，指的都是静态网络。

1.4.2 网络中的结构及其他信息

  1. **First-order proximity：**节点uu和vv之间边的权重wuvw_{uv}，表示两个节点间局部成对邻近度。如果两个节点之间没有变，那么一阶邻近度为0。
  2. **Second-order 和 High-order proximity：**假设su=(wu1,wu2,...,wu∣V∣)s_u=(w_{u1},w_{u2},...,w_{u|V|})表示节点uu和其他所有节点之间的一阶邻近度，那么uu和vv之间的二阶邻近度可以通过sus_u和svs_v之间的余弦距离计算得到。同理，两节点之间的X-order邻近度可以通过他们之间的 X-1 order邻近度的相似度计算得到。
  3. **Meta-path of the network：**给定异构信息网络G=(V,E)G=(V,E)，一条元路径ππ表示一个节点类型序列v1,v2,...,vnv_1,v_2,...,v_n和（或者）边类型e1,e2,...,en−1: π=v1→e1⋅⋅⋅vi→ei⋅⋅⋅→en−1vne_1,e_2,...,e_{n-1}:\ π=v_1 \stackrel{e_1} \rightarrow···v_i\stackrel{e_i}\rightarrow···\stackrel{e_{n-1}}\rightarrow v_n。

1.4.3 网络嵌入的问题定义

  • **问题1：（同构网络嵌入）**给定输入图G，同构网络嵌入旨在将节点或者子图或者整个网络映射到一个低维空间Rd(d≪∣V∣)R^d(d\ll|V|)。我们希望嵌入向量能够尽可能多的保留网络的各种特征。
  • **问题2：（异构网络嵌入）**给定网络G，异构网络嵌入旨在将不同类型的实体或者关系映射到一个低维空间Rd(d≪∣V∣)R^d(d\ll|V|)。我们希望嵌入向量能够尽可能丰富的保留G中的结构和语义信息。
  • **问题3：（动态网络嵌入）**给定一系列动态网络G1,G2,...,GT{G^1,G^2,...,G^T}，动态同构或异构网络嵌入希望学习到一个映射函数ft:vi→Rdf^t:v_i\rightarrow R^d。随着时间的推进，该目标函数保留了viv_i和vjv_j之间的结构和语义信息。

2. 同构网络嵌入

将原始网络数据喂给网络嵌入算法，得到低维向量后，利用现成的机器学习模型完成各类图分析任务。

2.1 节点嵌入

2.1.1 基于随机游走

一、方法

随机游走被广泛应用于网络数据分析中，来捕捉拓扑结构信息。随机游走会在图中选取某个节点然后沿着图中的边随机移动，形成一条移动路径。我们可以把得到的路径类比成NLP中的语料库中的句子，网络中的顶点当成文本语料库中的单词。然后利用NLP中的技术比如word2vec，我们可以将节点映射到低维向量空间中。学术界基于节点序列和文本序列之间的相似性提出了一些方法，比较具有代表性的有：

  1. DeepWalk

    受word2vec的启发而提出的一种方法。Deepwalk算法通过在图上随机游走生成节点序列，每一条游走路径相当于NLP语料库中的一个句子，而一个节点相当于一个一个单词。然后，在路径上应用skip-gram模型，在节点嵌入条件下，来最大化观测到节点邻居的概率。

  2. Node2vec

    但是DeepWalk有一些缺陷，首先就是研究人员发现不同的游走策略会产生不同的节点表示。Node2vec通过广度优先采样（BFS）和深度优先采样（DFS）的有偏策略改进了DeepWalk方法。通过调整搜索偏置参数，模型可以获得良好的节点特征向量。

  3. DDRW

    DeepWalk的第二个问题就是对于某些特定的节点分类任务，模型无法得到具有判别力的特征表示。DDRW旨在学习一个潜在表示空间，可以很好地捕捉到网络的拓扑结构，同时在网络分类任务中具有很好地判别力。该模型通过对分类目标和隐藏空间中的嵌入实体目标进行联合优化，扩展了DeepWalk。

  4. TriDNR

    DeepWalk的第三个问题就是没有对节点标签信息进行建模。TriDNR模型从三方面学习网络表示：节点结构，节点内容和节点标签。

  5. Struct2vec

    DeepWalk还有一个问题：在结构等价的任务中表现比较差。Struct2vec使用层次结构在不同尺度下测量相似性来估计结构相似性，并构造了一个多层图，通过非对称随机游走对节点的结构相似性进行编码并生成结构上下文。然后，应用skip-gram模型来学习节点的潜在表示，最大化节点上下文在序列中的可能性。

二、讨论

虽然基于随机游走的方法取得了不错的效果，但是其随机性带来的弊端是不能忽略的。

2.1.2 基于优化的方法

一、方法

基于优化的方法旨在设计一个合适的目标函数来对图的结构和语义信息进行建模，然后通过各种优化方法来最大化或最小化目标函数得到节点的向量表示。比如LINE使用负采样+ASGD，APP使用负采样+SGD。

  1. Line

    Line模型设计了一阶邻近度和二阶邻近度两个损失函数。作者建议优化联合概率分布和经验概率分布的KL散度。为了得到顶点的嵌入，提出了一种边采样策略来最小化一阶或者二阶邻近度。

  2. APP

    APP模型同时捕捉节点对之间的非对称邻近和高阶相似度。为了保留非对称邻近，顶点v需要同时担任两个角色：source role和target role，分别用sv→\mathop{s_v}\limits^{\rightarrow}和tv→\mathop{t_v}\limits^{\rightarrow}表示。全局目标函数被设计成sus_u和tvt_v的内积，表示节点对(u,v)(u,v)之间的相似度。

二、讨论

Line模型复杂度和边的数量线性相关，可以轻松应用到大型网络中去。而且，这类模型的性能主要依赖于目标函数的建模能力。因此如果能设计出更准确的目标函数，基于优化的模型性能会得到进一步的提高。

2.1.3 基于矩阵分解

一、方法

网络或者图通常可以表示成矩阵形式，比如邻接矩阵或者拉普拉斯矩阵。因此，很容易想到用矩阵分解的方法来获取节点嵌入。矩阵分解，比如奇异值分解（SVD），特征值分解，是数学里一种重要方法，已经成功应用在很多领域。

基于矩阵分解的模型主要有：GraRep，HOPE和M-NMF。GraRep通过分解全局结构信息矩阵来获取节点嵌入，它整合了各种k-step关系信息。HOPE使用SVD分解高阶邻近度矩阵来获取高阶邻近嵌入。M-NMF提出了一种模块化的非负矩阵分解模型，同时保留了一阶微观结构，二阶邻近度以及宏观的团体结构的特征。

需要注意的时，现实世界的网络除了结构外还包含了其他丰富的信息。因此，为了对这些辅助信息建模，TADW将顶点的文本特征引入到矩阵分解框架中。MMDW基于矩阵分解，在一个统一的学习框架中，将标签信息整合到了顶点表示中。

二、讨论

GraRep方法仅仅通过SVD进行线性降维，导致更多地非线性信息的损失。因为矩阵分解十分灵活，TADW、MMDW和M-NMF很容易进行扩展，整合其他信息。HOPE也可以通过设计新的高阶邻近度矩阵进行扩展。

2.1.4 基于深度学习方法

近年来，深度学习技术在许多领域都展现了强大的数据建模能力，网络数据也不例外。自编码器、各种卷积神经网络、注意力机制、对抗学习等都被应用到网络数据中。

2.1.4.1 基于自编码器的方法

这种类型方法主要分为两类：基于传统自编码器和基于图自编码器。前者的典型算法有SDNE和DNGR ，后者的典型算法有GAE和ARGA。

  1. SDNE

    SDNE提出了一种改进的卷积自编码器模型，同时优化一阶和二阶邻近度来获取网络的局部和全局结构特征。一阶邻近度利用拉普拉斯矩阵保留下来，二阶邻近度通过深度自编码器保留下来。最后，将深度自编码器的中间层作为最终的节点表示。

  2. DNGR

    DNGR通过positive pointwise mutual information(PPMI)矩阵来获取图的结构信息，学习堆叠式的降噪自编码器来获取节点嵌入。需要注意的时，DNGR是task-agnostic的，无法保证对于某个特定任务有好的表现。

  3. DNNNC

    DNNNC是对DNGR的一个拓展，是一种有效的classification-oriented的节点嵌入方法，可以提高节点分类的表现。

  4. GAE

    GAE可以看做基于图自编码器的pioneering work。该模型设计了一个卷积神经网络作为编码器，一个简单的内积解码器，用于图结构数据上的无监督学习。但是这种模型有三个弊端：

    • 模型无法得到稳定的图表示——ARGA模型，提出了对抗训练模式来对GAE的隐藏编码进行正则化。
    • 不是为了某个特定的图分析任务而设计的——DAEGC提出clustering-oriented节点嵌入模型，通过联合优化来同时获取图嵌入和图聚类结果。
    • 解码器太简单，丢失了太多的结构信息——TGA模型提出了一种triad解码器，通过对三元闭包属性（现实世界网络的基础）进行建模。

2.1.4.2 基于GCN的方法

Semi-supervised classification withgraph convolutional network这篇文章提出的GCN模型可以看做是最具代表性的工作，它采用了CNN在图结构数据上的一种有效的变体。主要的卷积架构是通过谱图卷积的一个局部一阶近似。研究者发现这个模型也有一些代表性的弊端：

  • GCN无法对网络的全局信息进行建模——DGCN模型采用双重图卷积网络，基于邻接矩阵的卷积ConvA和基于PPMI的卷积ConvP。这样模型能同时保留局部和全局信息。
  • 节点数量很大时，GCN占用的内存和计算资源很大——LGCL通过可学习的卷积层和一种有效的子图训练策略，提出了一种适用于大规模网络的可学习GCN。
  • GCN太浅了，无法捕捉更多信息——HesGCN提出了一种更有效的卷积规则，对一阶谱图Hessian卷积（Hessian矩阵和谱图卷积的结合）进行优化。

2.1.4.3 基于图注意力的方法

2018年，Velickovic在Graph attention network一文中提出了GATs模型，用于节点分类的一种基于注意力的架构。它的主要思想是按照自注意力策略，通过节点的邻居，计算每个节点的隐藏表示。

2.1.4.4 基于GAN的方法

这一类方法中比较有代表性的有：ANE、GraphGAN和ProGAN。

  1. ANE

    ANE主要包含两部分：一个是结构保留组件，另一个是对抗学习组件。具体来说，用DeepWalk来保留结构信息，对抗学习组件包含一个生成器和一个判别器。

  2. GraphGAN

    GraphGAN是另一个比较创新的基于GAN的图表示学习框架。给定一个顶点，生成模型旨在拟合它和其他所有顶点之间的连接分布，并且生成fake样本来迷惑判别器。

  3. ProGAN

    ProGAN提出在不同节点之间生成邻近度，这有助于发现复杂的潜在的邻近性，有利于网络嵌入。

2.1.5 其他

GraphWave和上面所有方法不同，它基于以该节点为中心的频谱图小波扩散，为每一个节点学习一个不同维度的结构嵌入。该方法使得通过谱图小波来学习节点的结构嵌入成为可能，关键是将小波系数看做概率分布，通过经验特征函数对分布进行描述。

2.1.6 总结

对于基于自编码器和GAN的模型，它们都是无监督模型。学习到的表示可以完成节点聚类、链路预测等任务。值得注意的是，由于网络数据的特殊性，在网络数据中应用自编码器，其学习能力是有限的。因此，设计一个面向图的自编码器是一个非常紧急的研究问题。虽然上面提到了一些这方面的工作，但是还有很大的发展空间。因为大多数自编码器及其变体都是使用KL散度来计算两个分布之间的相似度，这不是一个真实的度量。因此，最近提出的Wasserstein autoencoders为下一代图自编码器提供了一个研究方向。

基于GAN的模型也有一些弊端，比如稳定性差，这可能是GAN本身的特性导致的。将GAN应用在图数据上仍然有很大发展空间。

对于基于GCN和GAN的模型，它们主要应用于半监督节点分类任务。对于GCN，其时间复杂度和图的边数量线性相关，GAT的时间复杂度和GCN相当。因此，这两类方法都能使用与大规模网络。

2.2 子图嵌入

子图嵌入即将部分节点和边构成的集合映射成一个低维向量。比较有代表性的方法是Subgraph2vec，它在一个连续向量空间中对语义子结构依赖进行编码。首先，它利用WL重新标记策略提取给定图中每个节点周围的根子图，然后通过radial skip-gram模型学习它的嵌入。

2.3 整图嵌入

整图嵌入就是将整个图映射成一个向量，下面主要介绍目前效果最好的基于Graph kernel和基于深度学习的两类方法。

2.3.1 基于Graph kernel的方法

这一类方法中比较典型的有两种：graph kernel和deep graph kernel（DGK）。Graph kernel定义了两个子图之间距离的度量函数。DGK提出利用子结构之间独立的信息来学习它们的潜在表示。DGK是这一类方法中表现最好的方法之一，已经被证明了优于其他三种比较流行的图核方法Graphlet kernel、Weisfeiler-Lehman kernel和shortest-path graph kernel。

这一类方法的主要缺点是需要精心提取的特征。另外，这些模型的相似度是直接基于全局图结构计算到的，并且计算图之间的距离代价很大。预测规则也难以解释，因为图特征很多且都是隐藏的。而且它们不能捕捉一些重要的子结构，这对图分类很重要。

2.3.2 基于深度学习的方法

2.3.2.1 基于CNN

这一类方法主要有两种：基于传统CNN和基于普卷积。

  1. 基于传统CNN

    • PSCN

      具有代表性的模型是PSCN，它可以看做是第一个用CNN来进行任意图分类的工作。该模型设计了一种通用的方法，可以通过对基于图像的卷积网络进行模拟，从图上提取局部连接区域，然后在输入的局部连接区域上进行卷积操作。PSCN的最终架构包含节点序列选择、邻居图构造、图正则化和卷积模块四部分。

    • NgramCNN

      但是PSCN模型存在一些缺点：（1）邻居的选择；（2）丢失了复杂的子图特征；（3）特别的打标签方法。最近提出的NgramCNN模型解决了上述问题。它包含三个核心组件：（1）n-gram正则化，对邻接矩阵中的节点进行排序，输出n-gram正则化的邻接矩阵；（2）一个特别的卷积层，称为diagonal卷积，它可以提取通用的子图模式；（3）一个堆叠的卷积结构，由若干卷积层和一个池化层构成。

    • DGCNN

      PSCN还有一个问题就是数据预处理复杂度高，为了解决这个问题，研究人员提出了DGCNN——一个纯神经网络架构，实现了端到端的图分类。

  2. 基于谱卷积

    Spectral networks and locally connected networks on graphs这篇文章最先提出谱图CNN模型，然后 Convolutional neural networks on graphs with fast localized spectral filtering这篇文章对其进行了拓展。 但是这两个模型复杂度较高，无法应用到大规模网络中。为了解决这个问题，将GCN和其他有效的机制相结合很有吸引力。比如最近将differentiable pooling和self-attention pooling引入到GCN中来从节点嵌入中获取图嵌入，在图分类任务中取得了很好地表现。

2.3.2.2 基于注意力

基于注意力的方法中具有代表性的一个模型是GAM——一个原生的RNN模型，它关注图中比较小但是信息量丰富的部分，避免了图中其余部分的噪声。注意力机制主要用来指导模型向信息更丰富的部分移动。

2.3.2.3 总结

许多图分类算法都是基于传统CNN模型的，比如NgramCNN和DGCNN，它们的本质还是通过传统的CNN来指导特征处理和转换。尽管这些模型取得了不错的效果，但是它们捕捉复杂结构的能力天生不足。为了更好地辨别网络中的复杂结构，最近提出的模型CapSGNN，利用CapsNet在图像处理领域的强大能力来进行图分类，取得了不错的效果。因此，如何从复杂结构空间学习到最具有判别力的信息是解决图分类问题的关键。

2.4 动态同构网络嵌入

现有的大部分网络嵌入工作都是针对静态网络的，忽略了网络的动态性。因此，正对动态网络的网络嵌入是一个开放性问题，它也逐渐得到了相关研究人员的关注。考虑网络在时间上的动态性，设计一个有效的动态网络嵌入算法是十分重要的。比较有代表性的工作有：DHPE、DynamicTriad和动态GCN，前两个不是基于深度学习的方法。

  1. DHPE

    DHPE提出了一种动态网络嵌入方法，首次采用GSVD来保留高阶邻近度。然后研究人员提出了一种广义本征摄动方法来逐步更新GSVD的结果。这样，我们就将动态问题转换成了特征值更新问题。

  2. DynamicTriad

    DynamicTriad通过对三元闭包过程进行建模来设计动态网络嵌入算法，它可以让我们的模型捕捉到网络的动态性

  3. Dynamic GCN

    Dynamic GCN结合了长短期记忆网络和GCN来图结构之间的学习长短期依赖。改模型的效果已经被证明了其在基于顶点和基于图的半监督分类任务中的优越性。

总之，如何对网络动态特征和节点嵌入更新进行建模是解决动态网络嵌入问题的关键。随着深度学习的发展，基于神经网络的动态网络嵌入方法取得了很大的进展。

3. 异构网络嵌入

和同构网络相似，现实世界中广泛存在着大量异构网络，知识图谱就是一种典型的异构网络。以在线社交网络为例，它可能包含不同类型的跨模态节点（比如用户、图片、文本、视频等）和复杂的关系。因此，和同构网络嵌入相比，由于异构网络的异质性和高复杂性，异构网络嵌入是一个更具挑战性的问题。异构社交网络表示学习的架构如下图所示：

异构网络嵌入可以将网络中的不同的异构对象映射到统一的潜在空间，这样来自不同空间的对象就可以直接进行比较。下面主要从KG和HIIN两个方面介绍异构网络嵌入。

3.1 知识图谱嵌入

3.1.1 常用方法及数据集

代表性方法：

常用数据集：
### 3.1.2 基于Translation

基于translation的模型的核心是translation距离。早期，研究人员使用经验距离模型，比如SE。但是这种模型丢失了太多的信息，导致模型效果较差。后来，人们大多采用本文下面介绍的translation模型。

**一、方法**

  1. TransE

    TransE是第一个基于translation的模型，也是最具代表性的translational距离模型。它将实体和关系在同一个空间中表示成向量。TransE受skip-gram模型启发，认为词嵌入之间的不同点代表着它们的关系。对于一个三元组<h,r,t><h,r,t>，TransE将从实体h到实体t的转换看成它们之间的关系r。因此，(h+r)(h+r)会和(t)(t)很接近，最终的得分函数定义为：fr(h,t)=∣∣h+r−t∣∣22f_r(h,t)=||h+r-t||^2_2。需要注意的时TransE只适用于1-to-1的关系。

  2. TransH

    TransH是为了解决1-to-N、N-to-1以及N−to−NN-to-N问题的。TransH提出一种模型叫“translation on a hyperplane”。在不同关系的超平面上，一个实体会有不同的表示。TransH通过一个正则向量wrw_r将实体嵌入hh和tt投影到一个具体关系的超平面上，h′=h−wrThwrh'=h-w_r^Thw_r，t′=t−wrTtwrt'=t-w_r^Ttw_r。最终的目标函数定义为：fr(h,t)=∣∣(h−wrThwr)+r−(t−wrTtwr)∣∣22f_r(h,t)=||(h-w_r^Thw_r)+r-(t-w_r^Ttw_r)||_2^2。

  3. TransR

    TransE和TransH都是假设实体和关系在同一个向量空间，但是关系和实体都是不同类型的对象，它们不应该在同一个向量空间。TransR模型就是基于这一思想被提出的。TransR将TransE和TransH中的单个向量空间拓展到了多个向量空间。具体地，对于每一个关系rr，通过映射矩阵MrM_r将实体映射到关系向量空间，h′=Mrhh'=M_rh，t′=Mrtt'=M_rt。得分函数定义为：fr(h,t)=∣∣Mrh+r−Mrt∣∣22f_r(h,t)=||M_rh+r-M_rt||_2^2。

  4. TransD

    TransR也有一些缺点：（1）对于关系r，所有的实体都共享同一个映射矩阵MrM_r。但事实上，该关系链接的实体的类型和属性都不尽相同。（2）投影操作是实体和关系之间交互的过程，仅仅通过关系来确定关系映射矩阵是不合理的。（3）矩阵和向量的乘法操作计算开销大，当关系数量很多时，TransE和TransH的参数量巨大。

    因此，为了提升TransR，一个更好的模型TransD被提出来了。对于每个实体和关系都定义了两个向量，一个表示实体或者关系的含义，另一个表示如何将实体投影到关系向量空间，用于构造投影矩阵。这样，每个emtity-relation对都有一个自己独特的映射矩阵。最终的得分函数定义为：fr(h,t)=∣∣Mrhh+r−Mrtt∣∣22f_r(h,t)=||M_{rh}h+r-M_{rt}t||_2^2。

  5. TranSparse

    尽管上面的模型效果已经很好了，但是知识图谱中的实体和关系是异构、不均衡的，因此还存在很多挑战。为了解决异构和不均衡的问题，研究人员提出了TransSparse模型。M(θ)M(\theta)表示矩阵MM的sparse degree为θ\theta。TranSparse得分函数定义为：fr(h,t)=∣∣Mrh(θrh)h+r−Mrt(θrt)t∣∣l1/22f_r(h,t)=||M_r^h(\theta_r^h)h+r-M_r^t(\theta_r^t)t||_{l1/2}^2。

  6. TransA

    为了解决优化函数对某些特定图的局限性，TransA更具知识图谱的结构，自适应性地找到了最优的损失函数，因此不需要事先封闭候选集。它不仅使得基于Translation的嵌入在实践中更容易处理，还提高了模型的表现。它的得分函数定义为：fr(h,t)=∣∣h+r−t∣∣f_r(h,t)=||h+r-t||。

  7. MTransE

    考虑到大多数知识图谱嵌入方法都是用于单语言知识图谱，相关研究人员提出了一种用于多语言知识图谱嵌入模型MTransE。通过在单独的嵌入空间中对每种语言的实体和关系进行编码，MTransE为每个嵌入向量提供了其在其他空间中跨语言版本对应的转换，同时保留了单语言嵌入的功能。其得分函数定义和TransA模型相同。

  8. TorusE

    最近，研究人员注意到TransE的正则问题。TorusE采用和TransE相同的原理，但是希望通过改变嵌入空间来解决正则化问题。首先考虑嵌入空间的要求。然后引入一个lie group作为候选空间。最后改模型无需进行任何正则化即可得到实体和关系的嵌入。它的得分函数定义为：min(x,y)∈([h]+[r])×[t]\mathop{min}\limits_{(x,y)\in([h]+[r])\times[t]}。

二、讨论

上面的大多数方法都是基于TransE的，直觉上，通过对最近算法进行改进可以进一步提高模型性能。

3.1.3 基于语义匹配

一、方法

  1. RESCAL

    用一个向量捕捉每个实体的潜在语义，用一个n-by-n的矩阵表示每个关系。它最终的得分函数定义为：fr(h,t)=hTMrtf_r(h,t)=h^TM_rt。

  2. NTN

    NTN基于RESCAL进行拓展，提出了一个标准线性神经网络和双线性张量结构。

  3. DistMult

    DistMult通过将表示关系的矩阵严格限制为对角矩阵，简化了RESCAL。但是存在一个问题：(h,r,t)(h,r,t)和(t,r,h)(t,r,h)的得分相同。

  4. ComplEx

    ComplEx为了解决DistMult的问题，使用复数代替原来的实数，在计算双线性映射前先求尾实体的共轭，从而扩展了双线性映射。

  5. HOLE

    HOLE提供了一种全息嵌入方法，通过结合RESCAL中使用的张量积的表达能力和TransE的简单性，学习整个知识图谱的向量空间表示。

  6. Analogy

    Analogy拓展了RESCAL模型来对类比属性进行建模，这对知识库的不全十分有用。例如，如果系统A类似于系统B，则可以通过镜像A中的对象来推断B中未观察到的三元组。它采用和RESCAL相同的得分函数，并添加了对矩阵MrM_r的约束。

二、讨论

双线性模型比基于Translation的模型具有更多地冗余，因此很容易过拟合。

3.1.4 基于信息混合

一、方法

  1. DKRL

    为了吸收更多地信息来提高模型表现，DKRL提出了基于描述的实体表示。它通过CBOW或者CNN，从实体描述中构建实体的表示。

  2. TKRL

    层次实体类型中也蕴含大量对知识图谱有用的信息，TKRL是第一个借助层次结构，显示的将类型信息编码为多种表示形式的方法。

二、讨论

如已在DKRL和TKRL中反映的那样，多种信息（如文本信息和类型信息）被视为嵌入三元组的结构化信息的补充，对于知识图谱的表示学习意义重大。也就是，包含更多信息的模型将更接近实际问题，可以极大的推动相关实际应用的发展。

3.1.5 基于GNN和GCN

图神经网络包括GCN和GAT已经证明了对图数据的强大建模能力，知识图谱也是其应用场景之一。

一、方法

  1. R-GCNs

    R-GCNs将GCN拓展应用到了知识图谱中，模型对每个实体的邻居进行卷积操作，并赋予它们一个权重。

  2. 基于GAT

    Nathani等人在“ (2019) Learningattention-based embeddings for relation prediction in knowledgegraphs ”一文中提出了一种基于图注意力的特征嵌入方法，给定一个实体，可以在其多条邻居中同时捕捉实体和关系特征。

  3. ConvE

    除了GNN外，研究人员也尝试着用多层CNN网络来学习深度特征表示，典型的工作就是ConvE。改模型在embedding上使用2D卷积，并且使用多个非线性特征层来对知识图谱进行建模。

二、讨论

近些年来随着深度学习的发展，尤其是GNN和CNN，讲这些先进方法应用到知识图谱领域逐渐变得流行起来。

3.1.6 其他

除了上述方法，ManifoldE将基于manifold的原理M(h,r,t)=Dr2M(h,r,t)=D_r^2应用到一个三元组<h,t,t><h,t,t>上。在给定头实体和关系的时候，将尾实体置于高维流形中。直觉上，改模型的得分函数应该是三元组和流行之间的距离：fr(h,t)=∣∣∣∣h+r−t∣∣22−Dr2∣∣2f_r(h,t)=\big|\big|||h+r-t||_2^2-D_r^2\big|\big|^2，其中DrD_r是关系rr的流形参数。

3.2 异构信息网络嵌入

3.2.1 基于优化

一、方法

这里比较有代表性的方法有：LSHM、PTE和Hebe。

  1. LSHM

    LSHM是一个潜在空间异构模型，是这类方法的初始工作之一。改模型假设网络中相连的两个检点倾向于共享一些相似的表示，尽管它们的类型可能不同。通过结合分类和回归损失来学习节点的潜在表示。不同类型节点的标签通过它们的表示计算得到。

  2. PTE

    PTE同时利用有标签和无标签数据来学习异构文本网络中的文本嵌入。首先将标签信息和不同几倍的单词贡献信息表示成大规模异构文本网络。然后，异构文本网络可以有三个双向网络组成：单词-单词，单词-文档以及单词-标签网络。为了学习到异构文本网络的嵌入，一个直觉上的方法就是通过最小化三个网络中的节点对之间的条件概率来同时嵌入这三个双向网络。

  3. Hebe

    Hebe捕捉了整个异构信息网络中的多个交互。形成了一致且语义完整的单元的一组对象称之为超边，并将其视为一个事件。因此，这种方法保留了更多地网络中的语义信息。研究人员基于超边提出了两种模型：HEBE-PO和HEBE-PE。前者对同一超边中参与对象自身之间的邻近度进行建模，后者对超边与参与对象之间的邻近度进行建模。

二、讨论

上述模型对异构网络的建模能力有限，导致丢失了很多信息，比如节点类型信息。由于异构网络的复杂性，设计更准确的目标函数是实现这类方法的关键。

3.2.2 基于深度学习

和同构网络嵌入相似，深度学习模型也可以用于异构网络表示学习中，可以捕捉异构网络组件间的复交互。这些方法大体上可以分为两类：基于传统神经网络和基于CNN。

3.2.2.1 基于传统神经网络

传统的神经网络包括CNN、自编码器等等，在图像处理、cv以及其他很多领域取得了很好地效果。但是，考虑到异构网络中通常包含多种类型的信息和复杂的结构，让传统神经网络在这种类型数据上表现良好很具有挑战性。HNE和DHNE是两种比较具有代表性的方法。

  1. HNE

    HNE通过深度架构共同建模异构网络中的内容和拓扑结构。改模型将特征学习过程分解成多个非线性层构成的深度结构，包括图像-图像，图像-文本以及文本-文本三个模块。HNE利用CNN网络学习图像特征，用全连接层提取具有判别李的文本表示。最后，它将异构网络中的不同对象转换成统一的向量表示。

  2. DHNE

    尽管HNE已经取得了很好地效果，但是它忽略了异构网络中普遍存在不可分解的超边的问题。因此DHNE提出通过深度模型将对含有超边的hypernetwork进行嵌入。DHNE从理论上证明了现有方法中常用的嵌入空间中的任何线性相似度量都无法维持超网络中不可分解性。DHNE通过设计一个带有自编码器的新的深层模型来实现非线性元组的相似性函数，同时在形成的嵌入空间中保留局部和全局的邻近度。

3.2.2.2 基于GNN

受GNN在同构网络中成功应用的影响，GNN逐渐也被用于异构网络，具有代表性的方法有HetGNN和HAN。

  1. HetGNN

    HetGNN有效地同时考虑了网络的结构信息和节点内容信息。首先，改模型通过RWR为每个节点采样固定大小的邻居，并基于节点类型对它们进行分组。然后，改模型设计了一个包含两个模块的神经网络架构来聚合采样到的邻居节点的信息。最后，改模型利用一个graph context loss和mini-batch梯度下降来端到端的训练模型。

  2. HAN

    HetGNN没有考虑到异构网络中的重要信息，因此HAN基于层级注意力提出了一种异构图神经网络，包含节点级和语义级注意力。具体来说，节点级注意力旨在了解节点和其基于元路径的邻居之间的重要性，而语义级的注意力则用来学习不同原路径的重要性。

3.2.2.3 讨论

和同构网络相比，异构网络中基于深度学习的算法比较少，因为在异构网络中学习网络表示更具有挑战性。除了深度学习外，broad learning已经被引入到网络嵌入中来了，基于broad learning来做网络嵌入具有很大潜力。

3.2.3 基于元路径

一、方法

该类型具有代表性的算法主要有：Metapath2vec、metapath2vec和HIN2Vec两种。

  1. Metapath2vec和metapath2vec++

    前者同时保留了异构图中的结构和语义之间的关联性。该模型设计了一个基于元路径的随机游走，用于为各种类型的节点生成具有网络语义的异构领域，构建了执行节点嵌入的异构skip-gram模型。后者探索了将元路径应用于异构网络中的表示学习。

  2. HIN2Vec

    和Metapath2vec不同，HIN2Vec还学习元路径的表示。具体来说，改模型首先采用随机游走和负采样来准备训练数据。然后，训练一个逻辑二元分类器来预测两个输入节点是否有某种特定关系，来有效学习节点向量和元路径向量。

二、讨论

虽然基于元路径的方法取得了不错的效果，但是仅仅通过元路径来获取异构网络中的信息是不够的。因此，设计一个更好的语义信息采样策略可以显著提高异构网络嵌入算法的性能。最近提出的MetaGraph2vec和HERec对这个方向进行了一些探索并成功应用于节点分类和推荐任务中。

3.2.4 其他

  1. ASPEM

    ASPEM分别单独封装了每个角度的信息，而不是在一个语义空间中保留网络信息。模型提出了角度选择方法，证明了可以使用网络统计信息从任何异构信息网络中选择一组具有代表新的角度，而无需额外的监督。为了给某个角度设计算法，作者拓展了skip-gram模型。因此对于节点u的嵌入，最终是通过涉及到u的所有角度学习到的向量联合得到的。

  2. Tree2Vector

    树形数据可以看作成一个特殊的异构网络。例如一个表示作者的树状数据可以由作者信息节点、写的书节点以及书的评论节点构成。在这种情况下，研究人员设计了有效的方法将树状结构的数据转换成向量表示。Tree2Vector是一个具有代表性的工作，它主要通过使用无监督聚类技术通过节点分配过程以及局部敏感的重建方法对重建过程进行建模来实现的。但是，这是一个无监督模型，无法直接应用的监督学习中。因此为树状数据设计一个端到端的有监督学习模型是另一个值得探讨的问题。

4. 网络嵌入的应用

节点分类、节点聚类、链路预测、可视化、推荐、图分类、知识图谱中的应用以及其他一些场景(图像分类、强化学习、跨模态检索等等)

5. 总结及未来方向

虽然面向网络数据的表示学习已经取得了很大的进展，但是在未来工作中任然面临着巨大的挑战。下面主要从两个理论和应用两个方面来介绍未来可能的研究方向。

5.1 算法和理论

  1. 当前几乎所有网络嵌入算法都嘉定网络数据被嵌入到欧几里得空间中，在非欧空间中设计网络嵌入算法仍然是一个充满挑战和希望的研究方向。
  2. 现实中的大部分网络无疑都是动态、异构的，设计一个有效的动态、异构网络嵌入算法将是下一个研究话题。
  3. 现有的基于深度学习的算法仍存在一些问题：比如大数据集上的不稳定性、复杂的训练、鲁棒性较差等等，因此这些方法仍有巨大发展空间。
  4. 如何直接测量数据表示的质量是长期存在于表示学习领域的一个问题。提出或者设计用于表示学习的新评估或度量方法是一个紧迫的问题。另外，当前图嵌入算法缺乏解释性，从直觉上看，模型的解释性和数据表示的度量方法可能会相互促进者发展。
  5. 当前深度学习无法完成因果推理任务，设计有效的图神经网络以支持组合泛化和关系推理是一个非常有希望的方向。

5.2 应用

考虑到网络数据的普遍性，许多跨学科问题都可以抽象成图挖掘和分析问题。尽管已经有了一些成功的应用，例如蛋白质网络、脑网络、分子网络、药物发现等等，但是网络嵌入算法仍具有广阔的应用前景。

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2021-2022 Yin Peng
  • 引擎: Hexo   |  主题:修改自 Ayer
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信