集成多关系图神经网络

一、统一视角的 GNN

1、现有 GNN 传播范式

空域的 GNN 是如何传播的？如下图所示，以节点 A 为例:

首先其会将其邻居节点 N (A) 的信息聚合成一个 h_N(A)⁽¹⁾，再和 A 其上一层的表示  h_N(A)⁽¹⁾ 进行组合，然后经过一个 transformation 函数（即公式中的Trans(·)），就得到了 A 的下一层表示 h_N(A)⁽²⁾。这个就是一个最基本的 GCN 的传播范式。

另外，还有一种解耦的传播范式（decoupled propagation process）：

这两种方式有什么区别呢？解耦的传播范式中会先用一个特征提取器，也就是transformation 函数对初始的特征进行提取，然后将提取后的特征再放入聚合函数中进行聚合，可以看到这种方式将特征的提取与聚合分开了，即做到了解耦。这样做的好处在于：

• 可以自由的去设计前面的这个 transformation 函数，可以用任何的模型。
• 在聚合时可以增加很多层，来获得更远距离的连接信息，但是我们不会面临过度参数化的风险，因为聚合函数中没有需要优化的参数。

上面就是两种主要的范式，而节点的 embedding 输出可以使用网络的最后一层，也可以使用中间层的残差。

通过上面的回顾我们可以看到 GNN 中有两个基本的信息源：

• 网络的拓扑结构：一般可以捕捉图结构的同配信息属性。
• 节点的特征：一般都会包含节点的低频、高频信号。

2、一个统一的优化框架

基于 GNN 的传播机制，我们可以发现，现有的 GNN 有两个共同的目标：

• 从节点的特征中去编码有用的信息。
• 使用拓扑结构的平滑能力。

那么能否用数学语言去描述这两个目标呢？有人就提出了下面用公式表示的 GNN 优化统一框架：

优化目标中的第一项 ：

 是特征拟合项，它的目标是让学习到的节点表示 Z 尽可能与原始特征 H 接近，而 F₁, F₂ 是可以自由设计的图卷积核。当卷积核为单位矩阵 I 时，就相当于一个全通滤波器；当卷积核为 0 矩阵时就是低通滤波器，当卷积核为拉普拉斯矩阵 L 时就是高通滤波器。

优化目标的第二项形式上看是一个矩阵的迹，其作用是图上的正则项，迹与正则有什么关系呢？其实第二项展开后是下面这个形式：

其含义是捕获图上任意两个相邻节点之间特征的差异程度，代表了一个图的平滑程度。最小化这个目标就等价于让我和我的邻居更加相似。

3、用统一优化框架去理解现有 GNN

GNN 大都是在优化这一目标，我们可以分不同的情况做下讨论：

当参数 ：

 时优化目标就变成了：

求偏导就得到：

我们再把上面得到的结果做进一步的展开就能得到：

它的意义就表示第 K 层的所有节点表征等于第 K-1 层的节点表征在邻接矩阵上的传播过程，一直推导到最后就会发现就等于初始的特征 X 做完特征变换 W* 之后在邻接矩阵上传播 K 次。其实这就是去掉了非线性层的 GCN 或者 SGC 的模型。

当参数 F₁=F₂=I，ζ=1，ξ=1/α-1，α∈（0,q] ，且选择全通的滤波器时优化目标就变成了：

这时我们同样对 Z 求偏导，并令偏导等于 0 就可以得到优化目标的闭式解：

对结果稍作转换就可以得到下面的式子：

我们可以发现上面的式子就代表了节点特征在个性化 PageRank 上传播的过程，也就是 PPNP 模型。

同样是这样一个模型，如果用梯度下降的方式去求，并且设置步长为 b，迭代项是 k-1时刻目标函数对 Z 的偏导值。

当 

 时可以得到：

这就是 APPNP 模型。APPNP 模型的出现背景是 PPNP 模型中求矩阵的逆运算太过复杂，而 APPNP 使用迭代近似的手段去求解。也可以理解 APPNP 能收敛到 PPNP 是因为两者来源自同一个框架。

4、新的 GNN 框架

只要我们设计一个新的拟合项 O_fit，并设计一个对应的图正则项 O_reg，再加上一个新的求解过程就可以得到一个新的 GNN 模型。

① 例子1：从全通滤波到低通滤波

前面讲到过，全通滤波器下卷积核 F₁=F₂=I ，当卷积核为拉普拉斯矩阵 L 时就是高通滤波器。如果将这两种情况加权得到的 GNN 能 encode 低通的信息：

当 

 可以得到精确解：

同样，我们可以迭代求解：

5、Elastic GNN

前面的统一框架中提到的正则项相当于 L2 正则，相当于计算图上任意两个点之间的差异信息。有研究者觉得 L2 正则过于全局化，会导致整个图上的平滑程度趋于相同，这与实际并不完全一致。于是就提出加入 L1 正则项，L1 正则项会对图上变化比较大的地方惩罚比较小。

其中的 L1 正则项部分为：

总之，上面的这个统一框架告诉我们：

• 我们可以用一个更宏观的视角去理解 GNN
• 我们可以从这个统一框架出发去设计新的 GNN

但是，这个统一框架还只能适配于同质图结构，接下来我们看一下更加普遍的多关系图的结构。

二、关系GNN模型

1、RGCN

所谓的多关系图指的就是边的种类大于 1 的图，如下图所示。

这种多关系图在现实世界中非常广泛，比如化学分子中的多类型的分子键，又如社交关系图中人与人的不同关系。对于这样的图我们可以使用 Relational Graph Neural Networks 来建模。其主要思想是将具有 N 种关系的图单独聚合，从而得到 N 个聚合结果，再将 N 个结果聚合。

用公式表示就是：

可以看到聚合分两步进行，先从所有的关系 R 中选择一种关系 r，再找到包含这种关系的所有节点 N^r 进行聚合，其中 W^r 是用来加权各种关系的权重。因此可以看到随着图中关系数目的增加，权重矩阵 W^r 也会跟着增加，这样就会导致过度参数化的问题（Over-parameterization）。另外，将拓扑关系图根据关系拆分的做法也会导致过平滑（Over-smoothing）。

2、CompGCN

为了解决过度参数化的问题，CompGCN 用了一个向量化的关系编码器来代替 N 个关系矩阵 ：

 编码器包含正向、反向、自环三种方向的关系：

每一次迭代也都会对 relation 的 embedding 进行更新。

但这种启发式的设计，以及这样的参数化编码器同样也会造成过度的参数化。那么，基于上面的考虑就得到了我们工作的出发点：能否从优化目标的角度去设计一个更加可靠的 GNN，同时能够解决现有 GNN 存在的问题。

三、集成多关系图神经网络

我们的 EMR GNN 在今年发表，接下来主要从三个方面展开讨论我们如何设计一个适用于多关系图的 GCN：

• 如何设计一个合适的集成优化算法
• 消息的传递机制
• GNN 模型是怎么设计的

1、集成优化算法

这个优化算法需要满足两方面要求：

• 能够同时捕捉图上的多种关系
• 能够建模出图上不同关系的重要性

我们在多关系图上提出的集成的多关系图正则项如下：

这个正则项也是要去捕捉图信号的平滑能力，只不过这个邻接矩阵是在关系 r 下去捕获的，而受归一化约束的参数 μ_r 则是为了建模某种关系的重要程度。而第二项是系数向量的二范式正则，是为了让系数向量更加均匀。

而为了解决过平滑的问题我们又加了一个拟合项，来保证原始的特征信息不被丢失。拟合项与正则项加起来就是：

和上一章提到的统一框架相比，我们这里设计的目标函数包含节点矫正 Z 和关系矩阵参数 μ 两个变量。那么基于这样一个优化目标去推导得到一个消息传播机制也是一个挑战。

2、推导消息传递机制

在这里我们采用的是一个迭代优化的策略：

• 先固定节点表征 Z，再去优化参数 μ
• 根据上一步迭代的结果 μ 再去优化节点表征 Z

当固定节点表征 Z 时，整个优化目标就退化成只跟 μ 相关的一个目标函数，但是这是一个带约束的目标函数：

这其实是一个单纯形约束（constraint in a standard simplex）上的一个 μ 的convex函数，对于这类问题我们可以使用镜像熵梯度下降算法（Mirror Entropic Descent Algorithm）去解决。我们会先求出一个常量，然后对每一种关系下的权重系数进行更新，整个更新的过程类似于指数的梯度下降算法。

固定关系系数 μ 去更新 Z，这时的优化目标就退化成下面这种形式：

这样我们求目标函数对 Z 的偏导数，并令偏导数等于 0 就可以得到：

那么 Z 的闭式解就是：

同样我们可以用迭代的方式去得到近似解，这一过程可以表示如下：

从推导出的消息传递机制中我们可以证明该设计可以避免过度平滑，避免过度参数化，下面我们可以看下证明的过程。

原始的多关系 PageRank 矩阵是这样定义的：

个性化的多关系 PageRank 矩阵在此基础上加了一个返回自身节点的概率：

通过解上面的循环等式就可以得到多关系个性化 PageRank 矩阵：

我们让 :

 就可以得到：

这个也就是我们提出方案所得到的闭式解。也就是说我们的传播机制可以等价于特征 H 在节点的个性化 PageRank 矩阵上进行传播。因为这个传播机制中一个节点可以有一定的概率返回自身节点，也就是说在信息传递过程中不会丢失自身信息，从而防止过度平滑的问题。

另外，我们这个模型也缓解了过度参数化这一现象，因为从公式中可以看到，对于每一种关系我们的模型只有一个可学习的系数 μ_r ，相比于之前的 encoder，或者是权重矩阵 w_r 的参数量来比，我们这种参数量级几乎是可以忽略不计的。下图即为我们设计的模型架构：

其中 RCL 即为参数学习的步骤，而 Pro 步骤为特征传播的步骤。这两个步骤放在一起就构成了我们的消息传递层。那么怎样把我们的消息传递层整合到 DNN 中，且不引入额外的更多参数呢？我们也沿用了解耦的设计思路：先用一个 MLP 对输入特征进行提取，之后经过多层我们所设计的的消息传递层，叠加多层同样不会导致过平滑。最终的传递结果经过 MLP 完成节点分类即可做下游的任务。用公式将上述过程表示如下：

f(X;W) 就表示将输入特征经过 MLP 做特征提取，后面的 EnMP(K) 则表示将提取结果经过 K 层的的消息传递，g_θ 则表示经过一个分类的 MLP。

反向传播中我们只用更新两个 MLP 中的参数即可，而我们的 EnMP 中的参数是在前向传播过程中学习的，后向传播过程中不用更新 EnMP 任何的参数。

我们可以对比看下不同机制的参数量，可以看到我们的 EMR-GNN 的参数量主要来自于前后两个 MLP，以及 relation 的系数。当层数大于 3 时我们就可以知道 EMR-GNN 的参数量比 GCN 的参数量还要少，更是比其他异质图还要的少了。

在这么少的参数量下我们的 EMR-GNN 在如下不同的节点分类任务下还是可以达到最好的水平。

此外，我们还对比了不同的网络结构在层数增加后分类精度的变化，如下图所示，当当层数增加到 64 层后我们的模型依然能够保持较高的精度，而原始的 RGCN 当层数增加到 16 层以上时就会遇到内存不够的情况，想要迭加更多层更是不可能的，这就是由于其参数过多导致的。而 GAT 模型则由于过平滑而表现性能降低。

此外我们还发现，我们的 EMR-GNN 在较小的数据规模下即可达到全样本的分类精度，而RGCN 则下降很多。

我们还分析了 EMR-GNN 所学习到的关系系数μr是否真的有意义，那么什么算有意义呢？我们希望关系系数 μ_r 关系系数给重要的关系以更大的权重，给不重要的关系以更小的权重。我们分析的结果如下图所示：

其中绿色的柱状图表示在一种关系下分类时的效果，如果在某种关系下其分类精度更高，我们就可以认为该关系时重要的。而蓝色柱子则表示我们的 EMR-GNN 所学习到的关系系数。蓝绿对比可以看到我们的关系系数能够反映出关系的重要程度。

最后我们也做了一个可视化展示如下图所示：

可以看到 EMR-GNN 训练出来的节点 embedding 能够带有节点的结构化信息，它能够让同一类的节点更加内聚，不同类的尽可能分开，分割边界相对其他网络更清晰。

四、总结

1. 我们用统一的视角去理解 GNN

    ① 在这个视角下我们可以容易看出现有 GNN 有什么问题

    ②这个统一视角可以给我们一个重新设计 GNN 的基础

2. 我们从目标函数的角度尝试设计一个新的多关系的 GNN

    ① 我们首先设计了一个集成的优化框架

    ② 基于这样一个优化框架我们推导出来了一个消息传递机制

    ③ 这个带有少量参数的消息传递机制简单地与 MLP 结合即可得到 EMR-GNN

3. EMR-GNN 有什么好处？

    ① 它依靠一个可靠的优化目标，因此得到的结果可信，从数学上也可以解释其底层的原理

    ② 它可以解决现有的 Relation GNN 的过平滑问题

    ③ 解决过参数化问题

    ④ 容易训练、在更小的参数量下可得到较好的效果

五、Q&A环节

Q1：关系系数的学习与 attention 机制有什么区别吗？

A1：这里的关系系数学习是通过优化框架推导出来的更新过程，而 attention 是需要基于反向传播才能学习到的过程，所以说在优化上两者就有本质不同。

Q2：在大规模数据集上模型的适用性如何？

A2：我们在附录中分析了模型的复杂度，从复杂度上说我们和 RGCN 是一个量级的，但是参数量会比 RGCN 更少，因此我们的模型更是适用于大规模数据集。

Q3：这个框架能融入边的信息吗？

A3：可以在拟合项或者正则项中融入。

Q4：这些数学基础应该从哪里学？

A4：一部分是基于前人的工作，另外一部分优化相关的数学理论我们用的也是一些比较经典的优化方面论文。

Q5：关系图和异构图的区别在什么地方？

A5：关系图是一种异构图，只不过异构图我们都通常认为是哪些节点的类型或者边的类型大于 1 的。而关系图我们特别关注的是关系的类别大于 1，可以理解后者包括前者。

Q6：能否支持 mini-batch 的训练？

A6：支持。

Q7：未来 GNN 的研究方向是否更倾向于严格的、可解释的数学推导，而非启发式的设计。

A7：我们自己觉得严格的可解释的数学推导是一种可靠的设计方法。