TKDE'21 | 异质图神经网络如何自动发现元路径?

2021 年 10 月 18 日 图与推荐

论文地址：https://ieeexplore.ieee.org/document/9508875

代码地址：https://github.com/kepsail/ie-HGCN

1. 引言

目前面向异质图的图卷积神经网络普遍存在两个重要的不足：（1）大部分已有工作依赖用户人工输入一系列任务相关的元路径（Meta-path），这对于没有专业知识的用户来说是困难的。换句话说，已有方法无法有效地、灵活地从所有可能的元路径中自动挖掘出针对某个任务的最优元路径，这阻碍了模型的有效性和可解释性；（2）大部分已有方法在执行图卷积之前都需要执行额外的、耗时的预处理操作，这显著增加了模型的时间复杂度，限制了模型的伸缩性。为了解决上述两个问题，该论文提出了高效且可解释的异质图卷积神经网络ie-HGCN，其包含了投影，对象级聚合，类型级聚合三个关键步骤。该模型可以端到端地自动评估所有可能的元路径的重要性，在粗粒度和细粒度两个层面上发现对于当前任务最优的元路径。而且，提出的两层聚合架构也可以避免额外的预处理操作，从而降低了模型的时间复杂度。论文从理论上证明了ie-HGCN自动发现元路径的能力，分析了其与谱图卷积的联系，分析了其近似线性的时间复杂度。在四个真实网络数据集上的实验结果显示，ie-HGCN不仅能够取得优越的性能，而且可以有效地发现元路径。

2. 方法

下图通过在DBLP上的一个模型实例展示了方法的基本流程。如左侧子图（a）所示，模型一共包含5层。在每一层，针对某个对象类型，都将其异质邻居的特征聚合过来（实线），同时也将其自身的上一层的特征聚合过来（虚线）。右侧子图（b）展示了针对P（Paper）类型对象的计算过程：（1）自身/邻居的特征投影；（2）利用归一化邻接矩阵聚合；（3）利用注意力聚合。

图1 模型整体架构图。

投影

考虑到在异质图里，不同类型的对象的特征通常有着不同的分布，因此在每一层，通过相关的投影矩阵把邻居特征映射到一个共同的语义空间中。同时，也将上一层输出的目标对象的自身特征也投影到这个空间：

对象级聚合

对于每种类型的邻居，通过相应的行归一化的邻接矩阵将其投影后的特征聚合起来。这里，自身的投影特征不需要执行对象级聚合。至此，形成若干个临时的特征，即：目标对象自身的投影特征，以及聚合的各种类型的邻居的投影特征。每种特征都从不同的方面反映了目标对象的特性。

类型级聚合

利用注意力机制将这些临时的特征聚合起来，从而全面地刻画目标对象的特性。首先，通过不同的参数将目标对象的自身投影特征映射为注意力的查询值和键值，也通过不同的参数将邻居的聚合特征映射为相应的键值：

然后，通过一个小型的非线性神经网络将查询与键值映射为注意力系数：

通过softmax函数将注意力系数归一化：

利用归一化的注意力系数，将若干个临时特征聚合起来，形成目标对象本层输出的新的特征：

3. 理论分析

论文从理论上证明、分析了该模型具有以下三个良好的性质：

在粗粒度和细粒度两个层面上，可以自动发现针对当前任务最优的原路径。
模型实际上是在谱域执行异质谱图卷积。
具有近似线性的时间复杂度。

4. 实验

论文在4个公开的真实数据集上与若干个先进的基线方法进行了实验比较。结果显示该模型能够取得优越的性能以及效率。最重要的是，模型可以有效地自动发现最有用的元路径，从而促进了模型的可解释性。我们考虑在DBLP数据集上对作者（A）类型的对象进行分类任务。下图展示了模型发现的针对此任务最有用的若干元路径。上方的子图（a）展示了每一层中，每个目标对象类型与邻居类型（包括自身）之间的归一化注意力系数。下方的子图（b）展示了最有用的几条元路径的重要性得分及其计算过程。其中，第二列中的符号“—”代表了自连接（如图1中的虚线所示），这表明了有些路径是可以“坍缩”的。如此，经过合并一系列等价的路径，我们可以得到任意长度的元路径（第一列）的重要性得分。

很明显，我们可以看到，元路径CPA的得分最高，而该路径的语义是：作者（A）将其论文（P）发表到了会议（C）。令人鼓舞的是，这与数据集的真实情况高度吻合。实际上，这个数据集中，作者（A）类型对象的真实类别标签（ground-truth label）就是根据作者的论文（P）所发表的会议（C）来被标记的。其他几个得分高的元路径也可以得到合理的解释。元路径CPTPA表明除了作者自己所发表论文的会议以外，另外一些会议也很重要，这些会议里的论文和作者的论文有很多共同的关键词（T）。元路径CPAPA表明作者的共同合作者所发表论文的会议也很重要。元路径CPCPA也比较有意思，因为一篇论文通常只会被发表到一个会议，从而左侧的子路径CPC等价于子路径C，进而CPCPA也可以被解释为CPA。