0
近年来，图神经网络掀起了将深度学习方法应用于图数据分析的浪潮。不过其作为一门古老的认识世界的方法论，人们对于图表征技术的研究从很早以前就开始了。
虽然现在深度神经网络在物体识别、图像分类和自然语言处理领域都取得了巨大的成功。然而，「设计出最优的神经网络，学习并输出任意的图」仍然是一个热门的研究课题。
本文是一篇出自伦敦大学学院的图表征学习综述，详细介绍了图核、卷积、图神经网络、图嵌入、概率模型共五类图表征学习方法的起源与发展，并对图数据表征学习方法的最新进展和未来发展方向进行总结和讨论。
将数据构造为图的形式可以帮助我们以一种系统化的方式研究如何发掘复杂的关系和模式。例如，互联网图展示出了给定网页间高频链接的复杂结构；在自然语言处理领域中，人们有时以树的形式表征文本，理解单词之间的联系，从而推断出句子的意义。
然而，机器学习领域的研究主要关注于向量形式的表征，而真实世界中的数据并不能很轻易地被表征为向量。现实世界场景下复杂图结构的例子包括：生物学网络、计算机网络、传感器网络、社交网络、论文引用网络、电力网络和交通网络。通过使用基于图的表征，我们可以捕获结构化数据的顺序、拓扑、集合和其它关系特性。
神经网络是通用的函数近似器。近年来的研究进展表明，深度学习模型已经在语音识别、目标识别与探测、自然语言处理等诸多领域中取得了巨大的成功。此外，在大型数据集、先进的计算处理能力，以及机器学习方法领域繁荣的新兴研究等因素的作用极大地促进了深度学习研究。
需要指出的是，对于机器学习来说，神经网络方法和非神经网络方法的主要区别在于学习数据的表征。在机器学习术语中，我们会使用「特征」一词，而在表征学习术语中，我们关心的是学习数据的最优表征，它有助于下游的机器学习任务。
学习「图表征」背后的思想是：学习一类映射，这类映射将顶点、子图或整体的图嵌入到低维向量空间中的点上。然后，我们优化这些映射，使他们反映嵌入空间的几何结构，学习到的嵌入可以被用作机器学习任务的向量化输入。
需要注意的是，本文讨论的是一些流行的使用基于图表征的数据域，包括生物学数据、化学数据、网页数据、文本数据、关系数据、社交媒体数据等。
2.1 相关概念
在这里，我们介绍图理论术语，为接下来涉及图数据的讨论提供相关背景。图是一个有序对
(V,E)。顶点集合 V 满足 n ≡ |V|，它代表图的阶。在相应的边集 E(G) 中，e_ij 代表顶点 i 和 j 之间的边。 我们使用符号 V(G) 和 E(G) 图 G 的点集和边集。
图的类型：本文考虑的主要是简单图。「简单图」的顶点之间仅仅通过一条边相连。本文还将讨论「无向图、有向图、带权图」：在「无向图」中，每条边被表征为一个无需对{v,w}；在「有向图」中，边则被表征为有序对；在「带权图」中，权值函数 w:f→R 为每条边赋予权值。
如果所有顶点对之间都存在路径，那么该图是「连通图」。如果图中的所有顶点有相同的度，那么我们有一个「正则图」。如果每对顶点之间都存在一条边，则该图为「完全图」。
度、游走、环、路径、距离、高度、深度：
顶点 u 的「度」被表示为 deg(u)，它代表与 u 相连的边数。
「游走」是一个由邻接顶点及其相应的边交替组成的序列，游走的长度由包含的边数确定。我们有时将长度为 k 的游走中的顶点表示为序列 v_0,v_1,...,v_k。
如果 v_0 = v_k（即起点与终点相同），则该游走是一个「环」。
「路径」表示每个顶点至多出现一次的游走。
两个顶点时间的「距离」记作「dist(u,v)」，它被定义为两点之间最短路径的长度。
顶点的「高度」代表节点与各个叶子节点之间自顶向下的路径中最长的一条路径上的边数。
顶点的「深度」是从该节点到树的根节点的路径上的边数。
子图：若 G_1 是图 G 的子图，则它的点集和边集都是 G 的点集和边集的子集。 「团」图的一个完全子图。「环」也是一种连通的子图，其中每个顶点都恰好有两个邻点，不包含环的图被称为「森林」。一个连通的森林被称为「树」。「子森林」是一个无环子图，「子树」是一个连通的子森林。对于给定的顶点 v，它的邻居节点的集合被表示为 N_v。
图同构：令 G = (V, E) 和 G′ = (V′, E′) 为两个图。若存在一个双射函数 f : V → V′，使得对于任意的 u, v ∈ V，我们有 G 中的 f(u) 和 f(v) 是邻接的当且仅当 u 和 v 在 G′ 中邻接，则 G 和 G′ 同构。
解决图同构问题与机器学习紧密相关，它为发掘数据点之间的相似度提供了一种方法。然而，图同构是一个颇具挑战的问题，目前还没有多项式时间内的算法能够求解图同构问题。
求解图匹配问题的早期算法提出使用「图编辑距离」以及「拓扑描述子」。使用图编辑距离涉及到对将图 G1 转化为 G2 的关键操作进行计数，从而提供分配成本的灵活性。然而，这种方法存在需为不同的操作以及子图同构的中间步骤选取最优的代价函数的问题。使用将每个图映射到一个特征向量上的拓扑描述子也存在在变换步骤中损失拓扑信息的问题。一种实际可行的替代方法是使用由可以在多项式时间内计算出来的图形成的子结构，这通常被称为「结构袋」（bag-of-structures）方法。
2.2 图的矩阵表征
2.2.1 矩阵的类型
我们需要使用矩阵形式的输入表征来生成特征。这些矩阵包括：邻接矩阵，度矩阵以及拉普拉斯矩阵。邻接矩阵 A 将图的整个拓扑结构通过以下方式封装在 n*n 形式的矩阵中。
度矩阵 D_ii 是一个对角矩阵，其中 d_i 为顶点 i 的度。
对于一个无权图来说，归一化后的拉普拉斯矩阵 L 形如：
归一化后的拉普拉斯矩阵 L 的谱分解定义如下：L 是一个对称的半正定矩阵，可以写作 L = ΦΛΦ^T，其中对角矩阵 λ = diag(λ_1, λ_2, λ_3,...,λ_|V|)，其元素为排序后的 L 的特征值；而 Φ = (φ_1, φ_2,...,φ_|V|) 是由排序有的列特征向量组成的矩阵。图的「谱」研究的是邻接矩阵的特征值。
2.2.2 矩阵之间的关系
邻接矩阵的归一化形式为
。图的拉普拉斯矩阵也可以使用度矩阵和邻接矩阵，通过公式 L=D-A 计算出来。归一化之后的拉普拉斯矩阵可以被写作
，进一步得到
。
图数据的常见用例包括：图比较、图分类、图聚类、链接预测、图压缩、图可视化。
图比较：图比较任务旨在通过映射 s : G × G → ℜ 确定两图之间的相似度。传统的图比较算法分为基于集合的、基于子图的和基于核的算法。
图分类：图分类问题可以被分为两类：一种是顶点分类问题，另一类是对于整个图的分类问题。在整个图的分类问题中，给定一个由图组成的数据集 D，其中每个图 G_i 可以被表征为 G_i = (V_i, E_i)，图分类的目标是学习模型 f : D → Y，并将图分类为一类或多类。通常，每个图都有一个相应的类别标签 Y = {1 . . . y}。
链接预测：以往，我们并不知道缺乏哪些链接或未来会形成哪些链接。从宏观上说，链接预测任务旨在预测网络结构如何随着现有的成员形成新的链接、断开连接而演化。例如，在「蛋白质-蛋白质」交互网络中，链接预测可以确定蛋白质之间新的交互。给定一个网络的图 G = (V, E)，链接预测任务可以定义如下：假设 U 是一个一般性的集合，它包含 |V|(|V|-1)/2 个可能的链接，其中 |V| 表示集合中元素的个数。因此，链接预测任务的目的是在集合 U-E 中寻找链接。数据集被随机划分为两个部分：E^T（训练集）和 E^P（测试集）。「网络增长预测」问题被认为是链接预测问题的延伸。在社交网络分析领域，链接预测被用于预测用户形成新的朋友关系的偏好，该过程导致了用户社交网络的增长。
图聚类：在图聚类问题中，边的结构起到了很重要的作用。图的顶点会被分组到不同的聚类簇中，分组的原则为：在形成的簇内部有许多边，而簇之间的边相对就少一些。主要有两类图聚类方法：图内聚类和图间聚类方法。顾名思义，图内聚类方法将一个图内部的顶点划分到不同的簇中，而图间聚类方法则将一系列图划分到不同的聚类中。在生物学领域，图聚类技术被应用在基因调控网络、代谢网络、神经网络和血液网络中。在社交网络中，聚类算法被用于社区发现任务。
其它用例：诸如网页或社交网络图等典型的大规模图包含超过十亿条边并且会迅速增长。从可计算性的角度来说，从大型图中学习知识是一项非常巨大的挑战。最近，图压缩和图可视化为解决这一问题提供了动力。图的压缩表征会对其拓扑结构进行编码。构建良好的图表征是一种节省存储空间的方法，人们研究出了多种压缩方案提供各种各样的图表征。图可视化显式地向我们展示了顶点、社区或子图之间的联系。图的可视化图形可以展示出一些有趣的特性，使阅读者可以从另一个角度研究网络。然而，定制化、布局，以及生成动态变化的可视化结果等问题仍然有待进一步探索。
核方法是一类被广泛使用的算法，它可以被应用于任意的数据结构。在一些表征学习方法中，核方法也被用作构建模块。核函数是两个向量在特征空间中的内积，它将学习算法与实例独立开来。这意味着学习算法仅仅依赖于实例之间的核值，而无需显式的使用原始的数据表证。
令 X 为一个非空集合，k : X × X → R，其中 × 代表集合乘积（笛卡尔积）。如果 k(x, y) = k(y, x) ，则核 k 是对称的；若 x_1,...,x_n∈X（n ≥ 1），且由 k_ij = k(x_i, x_j) 定义的矩阵 k 是正定的，则 k 是正定的，那么有：
核函数可以记作：
其中 φ(x) 为特征向量。
4.1 图的核方法
学习结构化数据的字典是一种兴起于上世纪 90 年代的方法。在「结构袋」（Bag-of-Structures
）方法中，每个数据点都被表征为一个给定图的子结构时衍生出的向量。使用结构袋方法，每类核的特征表征都是固定的，每个维度对应于一类子结构。这种方法会导致产生核空间有非常高的维度。令 G 为一个由图组成的非空集合，则 k : G × G → R 被成为一个图核，在这里 < φ(G), φ(G′) > 分别都是图的特征向量。
现有的图核方法是 R-卷积核的实例。R-卷积框架是对两个结构化对象进行分解后，构建在图对上的。论文「Convolution kernels on discrete structures」提出了将一个对象分解为原子化的子结构的思路。每种新分解出的关系 R 都会产生一种新的图核。
目前，有两类基本的图核学习方法：学习定义在图上的核，以及学习定义在图之间的核。Kondor 和 Lafferty 提出了学习图上的核（单个图上的顶点之间形成的图）的想法。Gartner 提出了学习图之间核的想法。在本文中，我们主要回顾三类使用了结构袋方法的核：游走和路径上的核、子树上的核，以及子图上的核。
4.1.1定义在游走和路径上的核
随机游走核由 Gartner 提出，其基础是对基于由数据集 D 中的图之间的节点序列形成的游走的子结构进行计数。为了找到两图之间的公共游走，这里使用了一种由图 G_1 和 G_2 中标注相同的顶点和边构成的积图。其中，(p1,p2) 为随机游走的起始概率，(q1, q2) 为停止概率。A_1, A_2 为 G_1 和 G_2 的邻接矩阵。在直积图 G 上的长度为 l 的公共游走可计算如下，其中 ⊗为克罗内克积。
两图之间的随机游走核可以被形式化定义如下：
其中，λ 为应用于长程游走的折算因子，它对所有长度不同的公共游走进行加权求和。随机游走核可以被定义为一种更简洁的形式：
最短路径核是通过计算数据集 D 中所有长度为 n 的最短路径 p 的对计算出来的。给定图 G 和 G' 的最短路径 p 和 p′， 最短路径核是在边上合理地选择核，通过对 p 和 p′ 中的边 E_p 和 E_p′ 组成的对进行加权求和得到的。
环模式核是通过对在 D 中出现的每个图中出现的公共环进行计数得出的，其定义如下：
其中 φ(G) 为图的特征向量。
4.1.2 定义在子树上的核
由 Ramon 和 Gartner 提出的子树核，是通过寻找数据集 D 中的每个图中的公共子树并对其进行比较而计算出来的。根据定义，图 G 的子树是由 G 中具有底层的树结构的不通顶点组成的连通子集。寻找数据集 D 中的图之间公共的树状邻居结构相当于对相同的高度为 h 的子树对进行计数。这样做的好处是，我们得到了将图的拓扑封装起来的图结构的丰富表征。图上的子树核是定义在顶点上的子树核的加和：
Weisfelier-Lehman 核（WL）是一种快速计算的子树核。该核使用 WL 同构性检验，它由以下步骤迭代式地组成：（1）确定多重集标签（2）标签压缩（3）重新更新多重集标签。在这里，h 为深度，l 为重新更新标注的函数，WL 定义如下：
4.1.3 定义在子图上的核
子图核的计算思路是：相似的图往往具有相似的子图，这些子图可以被用于图比较。连通的尺寸为 k 的非同构子图被称为图元核（graphlet）G_k = {g_1, g_2, g_3,...,g_(n_k)}，其中 n_k 是规模为 k 的图元核的个数。令 φ(G_f) 为长度为 n_k 的归一化向量，它的第 i 个元素是 G 中图元核 g_i 出现的频率，s_j 表示 G 中出现子图 g_k 的次数。
图元核核使用所有可能的 k 阶连通子图的计数向量的点积来计算两图之间的相似图。
4.1.4 使用结构袋方法存在的挑战
对角优势：结构袋方法递归地将结构化目标分解为子结构，但是这也带来了各种各样的挑战。例如，其中一个挑战就是「对角优势」问题，此时核矩阵接近于单位矩阵。当不同的子结构被视为不同的特征时这一问题就会发生，而且随着子结构数量的增加，特征的集合也会变大。因此，给定的两个图包含相似子结构的概率会减小。所以，某张图与其自身的相似度比它与训练集中其它图的相似度要高得多。
子结构稀疏&子结构依赖：子结构稀疏问题指的是，图与图之间只存在很少的共同子结构。子结构以来指的是，由于一个子图可以在另一个子图中找到，或者可以通过修改其他子图的顶点和边来得到，所以子图不是独立的。因此，通过这些子图表征的特征自然而然地趋向于相似。最后，大多数图核将各个子结构视为独立的特征，这不仅会增大数据集，还回导致特征趋同。因此，因此，经常出现的子结构，和那些经常包含较低阶子结构的子结构，往往对于出现指数贡献更大。
五、学习图表征
下面将介绍五类图表征方法：核方法、卷及方法、图神经网络方法、图嵌入方法，以及概率方法。「图表征」指的是通过神经网络计算方法学习到特征，每种学习到的表征都分别对图的拓扑信息进行编码。
5.1 核方法
近期的研究进展突出了神经网络和核方法之间的关系。例如，Cho 和 Saul 构建了模仿神经网络的核方法，而 Marial 等人说明了卷积神经网络和核之间的关系。这里的核方法的特点是，引入神经学习技术将核方法用于图数据。
深度图核（Deep graph kernels）：是将图核与深度学习技术相结合的重要方法之一。他们试图解决获取子结构之间有意义的语义的问题。结构袋方法存在子结构依赖、子结构稀疏和对角优势的问题。作者通过引入维度为 |S| × |S| 的半正定的编码矩阵 M 对子结构之间的关系进行编码来缓解这些问题，其中 |S| 为从训练数据中提取出的子结构字典的尺寸。这项工作是通过设计 M 来实现的，它考虑到了子结构空间的相似度。
计算 M 的方式为：首先计算子结构之间关系的「编辑距离」，接着使用概率化的自然语言模型学习子结构的潜在表征。核的定义如下：
核神经网络：在「Deriving Neural Architectures from Sequence and Graph Kernels」论文中，作者使用核定义了结构化的数据（例如序列和图）从而得到神经化的操作。他们设计了一种使用核内积的新型架构，将它嵌入到了一个循环神经网络中。该例阐释了如何将图核嵌入到神经模块中。给定考虑了特征向量 f_x 的随机游走核，可以通过以下方式将核与神经计算联系起来：
其中，⊙ 是元素点积，N(v)代表图中围绕顶点 v 的邻居，W 是权值矩，c_j[t] 和 h[t] 是激活前后的状态。
5.2 卷积方法
CNN 架构可以从具有底层的时空网格结构的数据中提取表征，使它们适用于图像、视频以及语音数据。CNN 被设计用来通过提取出输入数据的局部不变性质在信号域上提取局部特征。
图卷积：由于底层不规则的空间几何信息（这种数据被称为非欧数据），许多数据在它们底层的图上都具有不规则的结构。通常，在时序和图像数据中我们找到的是点阵类型的底层结构，而在诸如文本数据、传感器数据、网格数据、社交网络数据以及基因数据等数据中，我们找到的却往往是不规则的底层结构。为了给图数据设计卷积网络，我们需要使用一种相似的在不规则的图数据域上有效的卷积运算符。
下面，我们介绍用来形式化定义图卷积操作的相关概念。当我们考虑无向图时，「图信号」是一种函数映射 x : V → ℜ，它定义在图的节点上，通过向量 x ∈ ℜ^N 来表征，其中向量 x 的第 n 个元素表示集合 V 中第 n 个顶点处的信号值。我们可以认为数据与图的顶点绑定在一起，例如一个顶点可能代表「基因-基因」交互网络中的单个基因。
对于一个 函数 f、频率 w 来说，典型的傅里叶为 f 和特征函数 exp(2πiwt) 的内积。
函数 f : V → R 的图傅里叶变换是 f 在图拉普拉斯算子的特征函数上的扩展。对于半正定拉普拉斯矩阵 L ，其特征向量的标准正交集合为
，非负特征值为
，特征值分解可以写作
，其中
，U 为傅里叶基。傅里叶变换将时域信号转化为频域信号。而空域信号 x 的图傅里叶变换为
，由于 U 为正交基，则我们有
。卷积是通过一个积分定义的，它表示了给定一个函数 g 在另一个函数 f 上平移做内积时重叠的量。 
图上的卷积操作定义如下，其中 ⊙ 为元素内积
在 CNN 中常常被用于图像数据的离散卷积是定义在规则的 2D、3D 网格数据上的，因此不适用于图数据域。对于图这样的不规则网格来说，我们需要定义局部的卷积核「谱域图卷积」。谱域图卷积利用了一个事实：卷积是傅里叶域上的乘法。对于信号 x 和滤波器 g_θ 来说，谱域卷积可以写作：
其中 ，
，θ ∈R 是傅里叶系数向量。
5.2.1 空域和谱域方法
对于图数据来说，有两种主要的基于卷积的方法：空域方法和谱域方法。
空域方法的特点在于，在 CNN 中使用由图数据环境下某个顶点的邻居形成的局部感受野。我们将感受野构建为对于一种直接的图中距离的度量，给定一个顶点作为卷积核的中心，我们观察在一定跳数范围内的顶点。谱域方法的特点在于，使用基于图拉普拉斯分解的距离度量。
这两种方法都需要仔细考虑，创建谱域卷积依赖于图结构。对于空域卷积来说，需要为图数据创建具有平移不变性的卷积，还要为特定的问题解决确定顶点排序和邻居节点顺序的问题。CNN 的另一个缺点是，卷积操作只适用于假设图域固定的顶点特征，但在许多情况下，图可能是有噪声的，一些图是事先计算好的，这并不一定反映成员之间的真实关系。
5.2.2 空域方法
空域卷积：PATCHY-SAN（PS）中就用到了空域卷积方法。在这里，它被用来以一种有监督的方式使用 CNN 学习图的表征，从而以一种与经典的 CNN 在图像上的工作模式相类似的方式创建感受野。对于给定的图 G，在一个区间的顶点序列选择过程中，会指定一个顶点序列；而在邻居聚合步骤中，会确定一些邻居节点，从而创建感受野。因此，一个节点的感受野就是一个邻居感受野。在创建了邻居感受野后，需要实现一个归一化的步骤，它本质上是对顶点进行排序，从而在向量空间中为得到用于学习图表征的图特征创建了一个向量。
扩散卷积神经网络（Diffusion-convolutional neural networks）是另一种空域方法，它使用随机游走选择空域中相近的顶点，通过将第 i 个参数 w_i 与转移矩阵 P_i 的第 i 次幂相关联来构建卷积。
广义卷积：论文「A generalization of convolutional neural networks to graphstructured data」对 CNN 进行了推广，使模型能够在尺寸不同的图上生成卷积。该方法使用了一种空域方法选择排序前 k 的邻居，它是以一种图上的基于随机游走的转移矩阵为基础的。他们用 P 导出了 Q^k_ij，它计算出了在 k 步中从给定的顶点 x_i 到 x_j 的平均访问次数。图中顶点 x_i 处的卷积被表征为张量积 (M, N, d) → (M, N, p, d) 的形式，这个四维张量包含通过 Q^k 选择出的每种特征排在前 p 的邻居、M 个观测数据、N 中特征，节点深度为 d。
模体 CNN：模体（Motif ）是一种小型的子图模式，它表示了节点之间特定的连接模式。论文「Motif-based convolutional neural network on graphs」提出了一种基于模体的 CNN，他们定义了一些模体，从而创建了一个围绕目标顶点的感受野。定义了顶点 v_i 处的模体卷积单元后，所有在局部通过这种模体相连的顶点的特征都会根据其各自的语义角色被加权。模体 CNN 使用了一种注意力机制来整合从各种模体中提取到的特征，从而进行半监督学习。
5.2.3 谱域方法
「Spectral networks and locally connected networks on graphs」这项工作中提出了谱域网络，并介绍了一种构建连通的局部邻居图的技术。使用谱域网络旨在通过图傅里叶变换对卷积网络进行推广。在构建谱域卷积的过程中，图拉普拉斯矩阵的谱被用于推广卷积操作。每一种构建的谱域卷积都在 MINST 数据集的各种变体上进行了测试。
在论文「Deep convolutional networks on graph-structured data」中，作者使用谱域图卷积核构建了上述工作。他们训练了一种图卷积层，它在给定一个傅里叶矩阵 U、插值核 K、权值 w 的情况下，执行前向和反向传播。在前向和反向传播过程中，任务相当于在图上学习谱域卷积核。在第一种变体中，他们从下采样的 MNIST 数据中提取坐标，通过拉普拉斯谱构建卷积。在第二种变体中，MNIST 数据被投影到 3D 球面上。
广义图 CNN ：论文「Convolutional neural networks on graphs with fast localized spectral filtering」提出了一种彻底使用谱理论公式将 CNN 推广到图数据上的方法。在特征提取阶段，作者进行了图信号滤波和图粗化处理。在图滤波阶段，根据谱公式，在半径为 k 的球内严格定义局部滤波器。在图粗化阶段，他们使用了一种快速的图聚类软件 Graclus。他们为一个给定的无向图计算了归一化割和比例关联，而无需任何的特征向量计算。当池化压缩输出时，需要定义有意义的图邻居。为了最好地实现这一目标，作者设计了一种二叉树来组织顶点，该策略类似于构建一个一维信号。
图卷积网络：论文「Semi-supervised classification with graph convolutional networks」提出了一种用于半监督节点分类的图卷积网络（GCN）。他们使用了一个神经网络模型 f(X, A) 对图结构进行编码，该模型使用了一种层与层之间的传播规则，其中特征 X 是通过在邻接矩阵 A 上使用流行的 WL 算法得到的。在这种情况下，考虑谱域卷积
其中，x 是每个顶点的信号，计算该信号的计算开销是相当大的（尤其是在大型图中）。g_θ 可以通过切比雪夫多项式近似得到：
论文「Modeling relational data with graph convolutional networks」提出了一种关系图卷积网络（R-GCN），它是对 GCN 的扩展，可以用于链接预测、预测事实、实体分类。该模型是由编码器和解码器组成，编码器是一个生成实体的潜在表征的 R-GCN，解码器是一个张量分解模型。
识别和注意力机制（GAT）：在论文「Beyond Grids: Learning Graph Representations for Visual Recognition」中，二维特征图被转化为了图结构，其中节点代表图块区域而边则获取到这些区域之间的关系。通过使用图投影、图卷积以及图重投影等步骤，完成了图结构的上下文建模和识别。图注意力网络（Graph attention networks）使用基于注意力的架构进行图结构数据的节点分类。在计算了每条边重要性时，它只处理了每个关联顶点的特征。之后，该模型被用于归纳学习，它可以被泛化到未曾见过的图上。
5.3 图神经网络
我们将基于图的神经网络（GNN）定义为一种连接遵循 G(V,E) 结构的框架。
图神经网络（GNN）：这最早提出由图结构驱动的神经网络架构的方法之一。给定其邻居所包含的信息，每个顶点附有一个状态向量 x_v，其中每个顶点包含顶点层次上的标签信息 l_v。
GNN 中两个主要的步骤是：（1）一个参数化的转移方程 x_v = f_w(l_v, l_N(v))，它表明顶点 v、标签 l_v、邻居节点N(v)之间的依赖关系传递了学习到的顶点表征。（2）局部的输出函数 O_v = g_w(x_v, l_v) 将顶点表征映射到各个图的标签上。编码网络是通过将每个顶点的状态存储下来并且在激活时更新状态构建的。GNN 通过一种递归的方式学习，它使用一种循环关系获取每个顶点 v 在欧氏空间中的嵌入 x_v。该模型是端到端可微的，它通过最小化二次代价函数学习参数 w。
图门控序列神经网络和门控图变换网络：图门控序列神经网络（GGSNN）是一种 GNN 的变体，可以得到非序列输出。该模型的一个典型的示例是：输出逻辑公式。通过使用门控循环单元（GRU），GGSNN 展开了一个固定数目步骤的递归式。基于时间的反向传播算法（BPTT）被用来基于梯度。传播模型与 GNN 思路相当，每个顶点的表征都是遵循一种递归关系更新的。输出模型是针对每个顶点定义的可谓函数，它映射到一个输出上。
论文「Learning graphical state transitions」提出使用门控图变换神经网络（GGTNN），从而解决推理问题。这篇论文融合了诸如节点添加、节点状态更新、信息传播、信息聚合等大量的图变换操作，从而解决自动问答和图重构任务。Battagalia等人对图神经网络架构进行了丰富的研究，讨论了各种设计特性，包括消息传递神经网络、非本地神经网络以及各种图神经网络变体。
5.4 图嵌入方法
将图嵌入到一个低维空间中涉及到一系列技术，这些技术将输入图变换到其分别的向量表征中，并通过一个应设函数将它映射到空间中的一点。
各种各样的图嵌入技术已经被用于可视化、社区发现、无线设备定位、电网路由等任务中。图嵌入技术重点关注保持邻近性，从而使相同邻域中的顶点在欧氏空间中邻近。在过去，图嵌入方法已经被成功地用于获取底层图数据表征。
在 ISOMAP 中，他们使用了一个邻域球面将图数据转化到一个图中，使用迪杰斯特拉算法计算顶点之间的测地距离。另一种方法是多维标度法(MDS)，当它被应用于测地线距离矩阵时，得到的结果是一个重构流形，它通常被用于定位复杂数据集中格式良好的流形。局部线性嵌入，被认为是 PCA的一种变体，它使用了最近邻方法减少了数据的维度。
论文「Representation learning on graphs: Methods and applications」则介绍了将自编码器应用于生成图表征的方法。我们有一对编码器解码器框架得到一对嵌入 (z_i, z_j)，这样一来我们在重构框架上使用了如下所示的损失函数 L：
大致的想法是，编码器 ENC 将顶点映射到向量嵌入上，而解码器 DEC 接受一组嵌入，并根据这些嵌入解码出用户指定的图统计信息。大多数作者采用的一般工作流程设置是找到在图上定义的相似度函数，然后是学习嵌入的成对编码器-解码器，L 是决定性能的损失函数。
将自然语言技术用于学习图的节点和边的表征是早期图表征学习研究领域的主要范式。研究人员凭直觉提出了一个大胆的假设，对单词编码到一个 N 维空间中向量中（其中每个维度代表一些语义）的方法进行修改，以类似的方式学习图表征，使每个向量编码图的拓扑信息。
此外，图嵌入方法在基于游走的方法、基于子图的嵌入方法、多模态数据图的嵌入、归纳框架等方面取得的最新的进展包括：深度游走（DeepWalk）、Node2Vec、Grarep 、subgraph2vec、Visual Genome 等。
5.5 概率方法
学习图数据表征的概率方法包括各种各样的神经生成式模型、基于梯度的最优化方法以及神经推理技术。潜变量建模涉及到对一个潜变量 z 和一个观测到的变量 x 之间的关系通过一个相关的参数 θ 建模。
在这里 p_θ(x, z) 是联合分布，p(z) 是先验分布， p_θ(x|z) 是似然函数。在贝叶斯模型中进行推理是通过对后验概率 p(z|x) 进行调整实现的。在许多情况下，由于复杂的概率密度函数，计算后验概率并不容易，因此需要近似推断工具。变分方法包含一系列通过一个简单的密度函数对复杂的密度函数做近似的方法，这种简单的密度函数由一个新的近似后验分布 q_θ(z|x) 表征。变分自编码器是一类新的变分方法，它利用了神经网络的计算范式，使用反向传播技术构建了一类新的神经生成式模型。这种生成的动作发生在将数据从潜在空间映射到观察空间的过程中，这个映射是使用神经网络完成的。
图 1：编码器-解码器潜变量模型的示意图
变分图自编码器（Variational Graph Auto-Encoders）是一种学习图表征的变分自编码器方法。它将 GCN 作为了一个编码器，并使用了内积操作作为解码器。模型推断如下所示：
X 是使用 WL 算法得到的节点特征矩阵，A是邻接矩阵，则我们有：
在这里，µ 和 σ 是通过 GCN(X,A) 赋值的参数。生成模型形如：
其中，σ(·) 为 logistic 函数。该过程通过优化下面的变分下界来学习：
此外，概率方法在分子数据表征、特征空间设计、图生成等领域均有一系列进展（详情请参阅原文）。
在图表征学习领域中，一些新兴的研究重点关注的是先验分布中编码图数据、学习带权图的表征、学习时序图的表征、学习时序模体的表征、解决非欧图域的特定挑战、解决使用有向图的挑战。与此同时，在开发新的概率方法来学习图数据的表征方面，也还有进一步的发展空间。
本文对核方法、卷积方法、图神经网络方法、图嵌入方法和概率方法等五种主要方法进行了鉴别、分组、调研和讨论。虽然表征学习解决了自动地利用图像、声音和文本数据的信息，但并没有一个通用的好方法来处理图数据。从业人员可以将这篇综述作为获取关于最新进展的知识的路线图，也可以作为指导进一步实验的工具。 雷锋网 雷锋网 雷锋网
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
