TOIS'21 | 第一个基于多关系图的任务驱动GNN框架

北京航空航天大学、美国伊利诺伊大学芝加哥分校和英国利兹大学联合提出了一个全新的强化、递归且可扩展的由邻域选择引导的多关系图神经网络架构 RioGNN。与最先进的 GNN 以及专用异构模型相比，RioGNN 的各种下游任务显着提高了 0.70%–32.78%。

文章标题：Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks

文章链接：

https://www.zhuanzhi.ai/paper/8a690d4387829e68fef166ea325e3db2

代码链接：https://github.com/safe-graph/RioGNN

一、引言与贡献

异构图中具有丰富多样的节点和连边信息，传统的同构化异构图的方法将带来异构性损失。基于手工元路径或元图等的关系型图神经网络依赖固有实体关系，在细粒度任务中存在挑战。为此，该文提出了一个全新的强化、递归且可扩展的由邻域选择引导的多关系图神经网络架构 RioGNN。

本文由北京航空航天大学、美国伊利诺伊大学芝加哥分校和英国利兹大学联合完成。相关成果已被中国计算机学会推荐A类国际期刊ACM TOIS录用。

图神经网络（GNNs）已被广泛用于各种结构化图数据的表示学习，通常是通过不同操作聚合节点的邻域信息，在节点之间传递消息。尽管前景看好，但大多数现有 GNN 过分简化了图中边的复杂性和多样性，因此无法处理普遍存在的异构图（通常以多关系图表示形式）。基于手工元路径或元图等的关系型图神经网络依赖固有实体关系，在细粒度任务中存在挑战。为此，该文提出了一个全新的强化、递归且可扩展的由邻域选择引导的多关系图神经网络架构 RioGNN。

本文主要针对具有节点级嵌入的任务，以半监督方式学习多关系节点表示。我们使用 Yelp、Amazon 和 Mick-III 数据集，将 RioGNN 应用于欺诈检测和糖尿病检测两项任务，评估其有效性、效率和可解释性。实验评估了如何定义下游任务，包括转换节点分类、归纳节点分类和节点聚类。结果表明，与最先进的 GNN 以及专用异构模型相比，RioGNN 的各种下游任务显着提高了 0.70%–32.78%。我们表明，我们的 RSRL 框架不仅将学习时间提高了 4.52 倍，而且在节点分类方面也实现了 4.90% 的改进。我们还在上述任务中评估了 RioGNN 对超参数的敏感性。最后，我们进行了一系列案例研究，以展示 RSRL 如何自动学习不同任务中隐式关系的重要性和参与度。

在实际应用中，我们对多关系图进行建模，以半监督学习的方式将实际问题作为节点分类任务。根据领域知识构建多关系图后，例如垃圾评论检测、疾病诊断等，可以训练多关系 GNN。然而，当我们训练更具辨别力、有效和可解释的节点嵌入时，多关系 GNN 面临三个主要挑战：

如何在 GNN 中的邻居聚合期间处理行为不当的节点（挑战 1）。

输入节点的特征 X 通常基于启发式方法（例如 TF-IDF、Bag-of-Words、Doc2Vec 等）提取，容易受到以下不当行为的影响：对抗性攻击、伪装或简单的不精确特征选择。因此，中心节点的数值嵌入往往会被行为不当的相邻节点同化。例如，在垃圾邮件评论检测任务中，对抗性或伪装行为是不可忽略的噪声，会大大降低 GNN 学习特征表示的准确性。特征或关系伪装可以使行为不当和良性实体的特征相似，并进一步误导 GNN 生成无信息的节点嵌入。在医学疾病诊断任务中，基于文本属性的特征选择可能无法提取高级或细粒度的语义，从而容易导致节点特征不精确。因此，在应用于任何 GNN 之前，这些问题需要有效的相似性度量来过滤邻居。

如何基于相似性度量自适应地选择最合适的邻居节点（挑战2）。

对于大多数实际问题，数据标注是昂贵的，我们无法通过数据标注来选择每个关系下的所有相似邻居。直接将过滤阈值视为超参数的方法不再适用于具有大量噪声或行为不当节点的多个关系图。首先，不同的关系具有不同的特征相似度和标签相似度。其次，不同的关系对过滤阈值有不同的精度要求。因此，必须设计自适应采样机制，以便可以针对动态环境中的特定关系要求选择最佳数量的相似邻居。

如何以连续的方式高效地学习和优化过滤阈值（挑战 3）。

我们的初步工作采用了具有固定策略的伯努利多臂老虎机框架来加强过滤阈值的学习。然而，它实质上受到状态的观察范围和手动指定策略的限制，因此过滤阈值的最终收敛结果往往是局部最优的。此外，为了保持预测精度，面对大规模数据集，必须减小过滤阈值的调整步长或使用连续动作空间。这个过程无疑会扩大动作空间，导致收敛周期的增加和计算量的巨大增长，可能会损失准确性。因此，这个问题需要一个自动且高效的强化学习框架，能够快速获得充足且高质量的解决方案。

相应的，我们的工作贡献总结如下：

• 第一个基于多关系图的任务驱动GNN框架，充分利用关系采样、消息传递、度量学习和强化学习来指导不同关系内部和之间的邻居选择。

• 一种灵活的邻域选择框架，该框架采用增强的关系感知邻域选择器和标签感知神经相似性邻域度量。

• 一种递归的、可扩展的强化学习框架，通过对不同规模的图形或任务的可估计深度和宽度来学习优化的过滤阈值。

• 第一次从不同关系的重要性角度研究多关系GNN的可解释性。

我们在前期工作的基础上进行了扩展，将专门针对伪装欺诈者的欺诈检测器的防伪装 GNN（CARE-GNN）模型扩展到支持广泛实际任务的更通用体系结构。具体来说，改进包括：

1. 给出了不同实际任务下多关系图神经网络的定义、动机和目标的完整版本；将标签感知的相似性邻居度量从一层扩展到多层以选择相似的邻居；

2. 提出了一种新颖的递归和可扩展的强化学习框架，以通用且高效的方式优化每个关系的过滤阈值以及 GNN 训练过程，而不是之前的伯努利多臂老虎机方法；

3. 在强化学习框架下，同时利用离散和连续策略寻找不同关系的最优邻居；

4. 对三个有代表性的通用数据集进行广泛的实验，不局限于欺诈检测场景。

此外，还讨论了更深入的实验结果，以证明所提出架构的有效性和效率。我们提供多关系图表示学习结果的方差。我们还基于提议的 RSRL 框架的过滤阈值，从一个新的角度展示了对不同关系重要性的解释。

二、背景与概述

图神经网络（GNNs）通过聚合邻居信息进行表示，在生物信息学、社会网络、自然语言处理、推荐系统、计算机视觉等多个领域都具有不错的应用效果。其中，由于现实世界信息普遍存在的异构性，能够整合多种类型的节点和边的异构图神经网络的构建受到了广泛关注。

多关系图直接将要分类的元素作为节点，将不同标签元素的关键关系作为多重连接，可以广泛应用于具有挑战性的分类任务。 值得注意的是，从 HIN 出发， 多关系图能够灵活地表征和明确区分边类型，而无需严格遵循实体关联的元结构指定任意两个节点之间的语义连接。我们通过两个实际应用来举例说明其适用性，并比较基于 MR-Graph 的建模和基于 HIN 的方法之间的差异：

垃圾邮件检测

垃圾评论是指那些虚假的评论发布到产品或商家，目的是推广他们的目标。欺诈检测必须从自然的邮件中识别出垃圾邮件评论。由于垃圾评论添加了一些特殊字符或模拟良性的电子邮件行为(如一个用户发布垃圾邮件，同时保持一定频率的自然的评论)，以避免被发现，这给区分垃圾评论带来了挑战。我们将具有不同标签的注释视为节点，将不同的代表性 交互视为不同类型的连接，从而构建多关系图，从而将此问题转化为双分类问题。

如图1(a)所示，MR-Graph 示例描述了从电子商务评论数据中提取的有机自然的评论、垃圾评论及其交互。我们提取了两个与欺诈行为密切相关的评论之间的代表性互动，并将它们表示为不同类型的边缘——属于同一用户，具有相同的星级，针对同一月发布的同一产品，属于相同的字数水平，包含特殊字符，针对位于同一城市的产品。作为一种替代方法，传统的基于HIN的建模(图1(b))更加关注结构化连接所概述的关系。

fig01.png

疾病诊断

在疾病诊断任务中，糖尿病、脑卒中、青光眼是中老年人常见病，早期症状识别非常重要。 但由于这三种疾病的症状相似，临床上很难区分患者。例如，中风的症状包括视力丧失、突然虚弱和刺痛感，这与 II 型糖尿病患者的症状相似。此外，糖尿病的早期症状之一是由液体水平变化引起的视力模糊。因此，眼睛可能会改变形状，干扰眼睛的聚焦能力。虽然这种视力障碍可能表明患有糖尿病，但在青光眼患者中也是如此。在这里，将患者作为多关系图的节点，将具有不同相似症状的患者连接成不同类型的边，可以将任务转化为多分类任务。

图 2(a) 说明了用于疾病诊断的患者 MR 图。我们相信可以模拟和代表以下类型患者之间的关系：“头痛”症状，“视力模糊”症状，“高血糖”测试结果，“高血压”测试结果，“甲唑胺”病史，等更有助于糖尿病患者及其疑似疾病的诊断。甚至，两个患者之间可能存在多种关系。例如，患者5和患者8具有“视力模糊”症状和“高血压”测试结果两种共同关系。同时，以往基于 HIN 的电子健康记录 (EHR) 建模 侧重于不同属性或类型数据的关联和融合，相应的方法适用于各种疾病的诊断。此外，缺乏对某些确定疾病的细粒度分析。我们还给出了图 2(b) 中异构电子健康记录图的说明。

fig02.png

三、方法

基于以上背景，RioGNN 被提出作为一种新型的强化、递归和可扩展的邻接选择引导的多关系图神经网络，以驾驭定制神经网络结构的复杂性，同时保持关系依赖的表示。

图 3 描绘了 RioGNN 的整体架构，由三个关键模块组成——标签感知相似性测量、相似性感知邻居选择器和关系感知邻居聚合器。此外，我们还描述了整体算法和优化。

fig03.png

首先 RioGNN 根据实际任务构建一个多关系图，以反映节点、边、属性和标签的异质性。比如，同样的疾病检测任务，多关系图把病人作为多关系图的节点，把具有不同类似症状的病人连接成不同类型的边，从而将任务转换成多分类任务。

多关系图（MR-Graph）与多关系GNN定义

MG-Graph定义为：  ，其中   是节点集合   ，每一个节点   都有d维特征向量   ，并且   表示所有节点特征的集合。   是关系   下节点   和   之间的一条边，其中   是边的数量。请注意，一条边可以与多个关系相关联，存在   种类型的边。   是   中每个节点的标签集。

图神经网络 (GNN) 是一种深度学习框架，通过聚合来自其相邻节点的信息来嵌入图结构数据。基于 MG-Graph，我们可以从多层邻居聚合的角度根据不同的关系勾勒出 Multi-Relational GNN 的统一表述。 对于中心节点   ，节点   在第   层的隐藏或聚合嵌入称为   ：

其中   表示关系   下第l层的边，   指示关系   下邻居节点   的聚合嵌入。   表示聚合函数，它将来自不同关系的邻域信息映射到一个向量中，例如平均聚合和注意力聚合。   是通过串联或求和将节点   的信息及其相邻信息组合起来的算子。我们用输入的   维特征向量   初始化节点嵌入   。GNN 使用带有二元分类损失函数的部分标记节点进行训练。 我们不是直接聚合所有关系的邻居，而是将聚合部分分离为关系内聚合和关系间聚合过程。 在关系内聚合过程中，每个关系下邻居的嵌入同时聚合。 然后，在相互关系聚合过程中组合每个关系的嵌入。 最后，最后一层的节点嵌入用于预测。

标签感知的神经相似性度量

为了避免不同类型的节点之间的嵌入过度同化，RioGNN 采用了一个标签感知的神经相似性度量，以确定基于节点属性的最相似的邻居。我们的方法的时间复杂度可以从   到   一般来说，计算成本较低，因为对于节点集   中的每个节点，我们没有像 LAGCN 那样使用其  个邻居与   维特征的组合嵌入来衡量相似性，而仅考虑 FCN 基于其自身特征预测的标签。

相似性感知自适应邻居选择器

Top-p采样： 在聚合来自中心节点   及其邻域的信息之前，我们执行 Top-p 采样以根据不同的关系过滤不同的邻域。关系   在第   层的滤波阈值   表示对所有邻居的选择比例。例如，当   时，所有邻居节点都得以保留。具体来说，在训练阶段，对于关系   下的一批节点中的一个节点  ，我们首先在第   层中对于边   首先计算一组相似性分数   。然后我们对于每个中心节点v的邻居按照   降序排序，并在第   层将最顶部的   邻居作为所选邻居，即   。剩余节点将在当前批次被丢弃，并且不参与层内的后续聚合过程。

RSRL框架： 以前的工作将过滤阈值视为一个超参数，这对于具有大量噪声或行为不当的节点的多关系图不再有效。 为了解决这个问题，我们的前期工作采用了具有固定学习策略的伯努利多臂老虎机框架，并动态更新了过滤阈值。然而，这种方法的有效性在很大程度上受到状态观察范围和手动指定策略的限制。 因此，过滤阈值的最终收敛结果往往是局部最优的。 面对更大规模的数据集，保持预测精度还需要减小过滤阈值的调整步长。 这个过程会增加收敛epoch的数量，带来计算量的增加和精度的损失。

fig04.png

为了解决这些问题，我们在传统的基于强化学习的方法的基础上，提出了一种新颖的递归和可扩展强化学习框架 RSRL，不仅可以通过学习环境更新策略，而且可以使用递归结构快速、准确满足不同关系的精度要求。图 4描绘了基于森林的学习架构。 一棵树在每个epoch中的具体过程如右图所示，其中   和   分别代表上一个epoch之后的状态和奖励， （图中例子为0.5）代表当前epoch中预测的动作。 我们将 RSRL 制定为 L 层强化学习 (RL) 森林，并将第   层森林定义为：

   实际上是指在第   层获得最佳关系滤波阈值组合的过程。每个关系独立地以自适应的深度   和宽度   构造RL树   。   是深度优先和宽度优先的权重参数，   是关系   中包含在节点中的最大邻居数。   执行强化学习  在每个深度以精度   过滤阈值。在第   层，   通过多次 RL 递归获取精度高于前一关系深度   的邻居节点的最佳过滤阈值   ，直到在深度   处找到最大精度要求的阈值。   递归过程表示为：

其中   表示当 RL 树在第   层的深度为   时，关系   中要丢弃的邻居节点的最佳比例。每个深度的 RL 模块的学习范围是前一个深度选择的滤波器阈值   的   以内的值。当递归过程达到最大深度   时，我们得到第   层关系   的最终过滤阈值   。考虑到复杂度与动作空间的大小呈线性关系，该过程对 RL 动作进行了精确递归，可以将时间从   减少到   ，其中   并且   为关系   下的最大节点度。

关系感知加权邻居聚合器

最后，RioGNN 开发了一个强化的关系感知邻居选择机制，在汇总不同关系的所有邻居信息之前，选择一个关系中目标节点的最相似邻居，以获得最终的节点嵌入。对于中心节点  ，在第  层的关系   下，关系内邻居聚合可以定义如下：

其中   表示均值聚合器   的嵌入按位求和操作，  是指在第   层在关系   下通过计算获得的顶部   节点的集合。中心节点v的关系内邻域聚合的目的是将上一层关系   下的所有邻域信息聚合到嵌入向量   中。

进一步地，我们将关系间聚合定义如下：

其中   表示第   层的关系内邻居嵌入，   可以是任何类型的聚合器。这里我们直接使用RSRL框架优化的   作为聚合权重。

四、实验

在不同的场景中构建多关系图

我们为两个任务场景和三个数据集的实验构建了不同的多关系图。表2列出了不同数据集节点和关系的各种统计信息。除了不同场景下的节点数和噪声节点的比例（Fraud%，Diabetes%），我们还给出了不同关系的边数。对于每个数据集中的每个关系，我们根据相邻节点的特征向量的欧氏距离（范围为0到1）计算相邻节点的特征相似度，并对平均特征相似度进行归一化。表2的最后一列显示了每个关系的平均标签相似度，它是根据两个连接的节点是否具有相同的标签来计算的。

table02.png

RioGNN在欺诈检测任务中的有效性、效率和可解释性

我们进行实验以评估 Yelp 和 Amazon 数据集上欺诈检测任务的准确性。 我们报告了 RioGNN、基线和变体在 500 个 epoch 中的最佳测试结果。 从结果可以看出，在大多数训练比率或指标下，RioGNN 的表现优于其他基线和变体。 这表明 RioGNN 在欺诈检测场景中的可行性。

table04.png

RioGNN在疾病检测任务中的有效性、效率和可解释性

我们进行实验以评估 MIMIC-III 数据集上糖尿病诊断的准确性。 如表 7 所示，我们报告了 RioGNN 和各种基线和变体在 700 个 epoch 中的最佳测试结果。 从结果可以看出，在大多数训练比率和指标下，RioGNN 的表现优于其他基线和变体。

table07.png

五、总结

该文研究了RioGNN，一个强化的、递归的和可扩展的邻域选择引导的多关系图神经网络架构。它是第一个基于多关系图的任务驱动型 GNN 框架，充分利用关系采样、消息传递、度量学习和强化学习来指导不同关系内部和之间的邻居选择。提出了一个灵活的邻域选择框架，采用了强化的关系感知邻域选择器与标签感知的神经相似性邻域测量。提出了一个递归和可扩展的强化学习框架，通过可估计的深度和宽度来学习不同规模的图或任务的优化过滤阈值。首次从不同关系的重要性角度研究了多关系 GNN 的可解释性。

在三个真实世界基准数据集上进行的实验表明，RioGNN 在所有数据集上显着、一致且稳定地优于最先进的替代方案。 我们的工作显示了学习 GNN 的增强邻域聚合的前景，可能为未来的研究开辟新的途径，通过自适应邻域选择来提高 GNN 的性能，并分析不同关系在消息传递中的重要性。