论文题目：Heterogeneous Graph Neural Network

论文来源：KDD 2019

论文链接：https://arxiv.org/abs/1903.07293

代码链接：https://github.com/chuxuzhang/KDD2019_HetGNN

关键词：HIN, GNN, Graph Embedding

---

---

1 摘要

本文研究的是内容相关的异质图(content-associated HetG)的表示学习问题。

以往的工作大多没有同时考虑异质的结构信息以及每个节点的异质内容信息(节点的属性信息)。

本文提出了HetGNN解决上述问题。

首先，引入了带重启的随机游走机制(random walk with restart strategy)，为每个节点采样固定数量的强关联的异质邻居，并基于节点类型对它们分类。

接着，作者设计了由两个模块组成的神经网络框架来聚合被采样邻居节点的特征信息。

1. 第一个模块编码了节点异质内容信息(也就是属性信息)的深层次的交互特征，并为每个节点生成内容/属性嵌入(content embedding)；
2. 第二个模块聚合了不同类别的邻居节点的属性嵌入(按照邻居节点类型聚合)，同时使用了注意力机制，考虑不同类型的邻居的不同影响。

在多个数据集上进行了实验，并在多项图挖掘任务中超越了state-of-the-art。包括链接预测、推荐、节点分类和聚类以及归纳型(inductive)的节点分类和聚类任务。

2 引言

异质图(HetG)内含丰富的信息，包括不同类型的节点，节点间的连边，节点的无结构的属性信息。如图1(a)所示，不同类型的节点间有连边，节点也有不同的属性信息(author id, paper abstract, item picture等)。

2.1 已有的方法

（1）传统的方法

人为设计特征工程抽取出特征向量。

缺点：针对具体下游任务，应用受限，不能一般化推广到其他任务。

（2）表示学习方法

自动进行特征工程，可适用于多种下游任务。

1. 浅层模型：例如DeepWalk，将短的随机游走序列输入到SkipGram模型，估计节点在序列中的共现概率，以学习到节点嵌入。
2. 语义感知方法(semantic-aware aproaches)：例如metapath2vec，处理异质图中的异质节点和异质边。
3. 上下文感知方法(content-aware approaches)：例如ASNE，使用隐层的特征和属性信息以学习到节点嵌入。

（3）GNN方法

上述方法直接学习到了节点的隐层嵌入，但在受限于捕获丰富的邻居信息。GNN使用深层神经网络，强有力地聚合了邻居节点的特征信息。

而且，GNN天然可以进行归纳式学习(inductive learning)，可为训练过程中未出现过的节点生成嵌入表示。

例如GCN、GraphSAGE、GAT。

2.2 GNN在HetG上的挑战

现有的state-of-the-art的GNN不能很好地应对HetG中的挑战，但本文解决了这些问题。

（1）挑战一(C1)：如何为HetG中的节点采样到强相关的异质邻居？(如图1中的C1所示)

HetG中的许多节点不能和所有类型的节点都有连边。而且每个节点的邻居数目是不同的。例如**图1(a)**所示，author节点和venue节点没有直接的连边。**图1(b)**中节点$a$a有5个直接邻居，但是$c$c只有两个。

大多数GNN仅仅聚合一阶邻居的特征信息，会削弱距离远的邻居的影响。

（2）挑战二(C2)：如何为HetG中带有异质内容信息的不同节点设计节点内容信息的encoder？(如图1(b)中的C2所示)

HetG中的节点可能有无结构的异质内容信息，如属性、文本、图像等。

例如图1(b)中所示，第一种类型的节点b, c有属性信息和文本信息，第二种类型的节点f, g有属性信息和图像信息，第三种类型的节点d, e有文本信息和图像信息。

现有的GNN对节点的异质的内容信息，进行直接拼接处理或者是对其线性转换，但这不能建模深层次的交互信息。

每个节点的内容信息互不相同，对所有类型的节点使用相同的特征转换函数显然是不合适的。

（3）挑战三(C3)：如何在聚合异质邻居特征信息的过程中考虑不同节点类型的影响？(如图1(b)中的C3所示)

不同类型的邻居节点对目标节点的贡献度不同。

例如在图1(a)所示的学术网络中，类型为author和paper的邻居节点比起类型为venue的邻居节点对生成author节点的嵌入贡献度更大，因为venue节点含有更一般化的多样的主题信息。

大多数GNN主要是处理同质图，忽略了不同节点类型的影响。

2.3 作者提出

提出HetGNN解决上述挑战。

（1）首先设计了一个带重启的随机游走策略，为HetG中的每个节点采样固定数量的强关联的异质邻居。

（2）接着设计了两个模块组成的异质GNN，聚合采样邻居的特征信息。

第一个模块使用了RNN编码节点异质内容信息间深度的特征交互信息，得到每个节点的内容(content)嵌入。

第二个模块使用另一个RNN，聚合不同类别的邻居节点的嵌入，并且运用了注意力机制，为不同类型的异质邻居节点分配不同的注意力，得到最终的节点嵌入。

（3）最后使用基于图上下文的loss，运用mini-batch梯度下降法训练模型。

2.4 贡献

（1）定义了同时涉及图结构的异质性和节点内容异质性的异质图表示学习问题。

（2）提出HetGNN模型，用于HetG上的表示学习，实现了同时捕获异质的结构和节点内容，并且适用于直推式任务(transductive tasks)和归纳式任务(inductive tasks)。表1对比了HetGNN和其他模型。

（3）多个图数据挖掘任务实现state-of-the-art

3 问题定义

3.1 内容相关的HetG (Content-associated Heterogeneous Graphs)

C-HetG定义为 $G=(V,E,O_V,R_E)$G=(V,E,OV​,RE​)，$V$V是节点集，$E$E是边集，$O_V, R_E$OV​,RE​分别代表节点类型集合边类型集。每个节点都有异质的内容信息，比如属性、文本、图片。

3.2 异质图表示学习

给定C-HetG $G=(V,E,O_V,R_E)$G=(V,E,OV​,RE​)和节点内容集 $C$C，目标就是学习到参数为$\Theta$Θ的函数$F_{\Theta}$FΘ​，该函数可为每个节点学习到$d$d维的嵌入，以用于多种下游任务。并且该模型能够编码异质的图结构信息以及节点中异质的无结构的内容信息。

4 模型

模型由四部分组成：

• 采样异质的邻居节点
• 编码节点的异质的内容信息
• 聚合异质邻居节点的信息
• 定义目标函数并设计模型训练过程

图2展示了HetGNN模型的整体架构：

4.1 采样异质邻居节点(C1)

为了解决挑战一，作者提出了带有重启的随机游走策略(RWR)来采样异质的邻居节点，由以下两步组成：

（1）第一步：使用RWR采样固定长度的路径

从节点$v$v出发进行随机游走，以迭代的方式每一步走向当前节点的邻居节点，或者以$p$p的概率返回到起始节点，迭代直到采样到了固定数量的节点为止，生成的序列记为$RWR(v)$RWR(v)。同时保证$RWR(v)$RWR(v)中每种类型的节点都有，也就是采样到了所有类型的节点。

（2）第二步：将这些采样到的邻居节点按照类型进行分类

针对每种节点类型$t$t，根据其在$RWR(v)$RWR(v)中出现的频次，选取top $k_t$kt​个节点，将这些邻居节点就是和节点$v$v强相关的类型为$t$t的邻居节点。

---

这种策略的优势体现在：

• 为每个节点都采样到了所有类型的邻居节点；
• 每个节点采样到的邻居节点数是固定的，并且从中选择出了频次最高的邻居节点，也就是和该节点强相关的邻居节点。
• 与当前节点类型相同的邻居节点也会被采样到，这样就可以使用type-based aggregation。

4.2 编码异质的内容信息(C2)

设计模型从节点$v$v中抽取出异质的内容信息$C_v$Cv​，并使用神经网络$f_1$f1​得到它们的嵌入表示。

4.2.1 预训练分别得到不同属性的嵌入表示

定义集合 $C_v$Cv​ 中第 $i$i 个属性/内容 的特征表示为 $x_i\in R^{d_f\times 1}$xi​∈Rdf​×1。这个$x_i$xi​是可以通过预训练得到的，对于文本可以用Par2Vec预训练，对于图像可以用CNN。

4.2.2 使用Bi-LSTM聚合**不同属性的嵌入表示

以往的方法是将不同的属性特征直接拼接，或者将其线性转换到一个向量中。

本文是使用Bi-LSTM捕获深层次的特征交互信息，同时增强了模型的表达能力。节点$v$v的内容嵌入计算如下：

其中，内容嵌入向量$f_1(v)$f1​(v)是$d$d维的；$FC_{\theta_x}$FCθx​​是参数为$\theta_x$θx​的全连接神经网络，作为特征转换函数；操作符$\oplus$⊕表示拼接操作。

首先使用$FC$FC层转换不同的属性特征，然后将其输入Bi-LSTM进行深度编码，最后通过一个mean pooling层得到节点$v$v最终的内容嵌入。如图2(b)所示。

注意，不同属性的embedding输入Bi-LSTM是无序的，就像GraphSAGE一样随机给了一个输入顺序。并且，对不同类型的节点使用了不同的Bi-LSTM聚合它们的属性特征，因为不同类型节点的属性不同。

---

这种编码方式有以下3个优点：

• 结构简单参数少，模型实现和微调相对容易；
• 可融合异质的内容/属性信息，表达能力强；
• 模型易于扩展，可以额外添加属性特征。

4.3 聚合异质邻居的信息(C3)

为解决挑战三，设计了type-based神经网络。由两步组成：

（1）同一类型邻居的聚合：same type neighbors aggregation

（2）不同类型邻居的聚合：types combination

4.3.1 同一类型邻居的聚合

定义为节点$v\in V$v∈V采样到的$t$t类型的邻居节点为：$N_t(v)$Nt​(v)。使用神经网络 $f^t_2$f2t​ 聚合 $v^{'}\in N_t(v)$v′∈Nt​(v) 的内容嵌入，如下所示：

其中，$f^t_2$f2t​是同一类型邻居聚合后的$d$d维向量，$f_1(v^{'})$f1​(v′)是4.2.2中求得的$v^{'}$v′的内容嵌入。$AG^t$AGt是聚合$t$t类邻居的函数，可以是全连接的神经网络、CNN、RNN等。本文使用的是Bi-LSTM，因为它实验的效果更好。将上式重写如下：

和4.2.2一样，过一层mean pooling，如图2©所示。

注意，对于不同类型的节点，使用不同的Bi-LSTM，输入和前面一样也是无序的。

4.3.2 不同类型邻居的聚合

上一步是针对每种类型的节点进行了聚合，生成了$|O_V|$∣OV​∣个聚合向量，接下来要将它们再聚合起来。由于不同类型的邻居节点对学习到节点$v$v最终的表示贡献度不同，所以使用注意力机制，为不同类型分配不同的注意力。

输出的嵌入表示为：

其中，$\alpha^{v,*}$αv,∗表示不同嵌入的重要程度，$f_1(v)$f1​(v)是$v$v的内容嵌入，$f^t_2(v)$f2t​(v)是$v$v的type-based聚合得到的嵌入。

定义嵌入的集合为：$F(v)={\{f_1(v)\cup (f^t_2(v), t\in O_V)\}}$F(v)={f1​(v)∪(f2t​(v),t∈OV​)}，将$v$v的输出嵌入重新写成下面的形式，其中$u\in R^{2d\times 1}$u∈R2d×1是注意力机制的参数。这步如图2(d)所示。

为了让维度一致易于调参，节点自身的内容嵌入和聚合邻居后的内容嵌入维度均为$d$d。

4.4 目标函数

目标函数定义如下，参数为$\Theta$Θ，$CN^t_v$CNvt​是给定节点$v$v的$t$t类型的一阶/二阶邻居。也就是无监督学习，给定节点$v$v，最大化其邻居节点的概率(这里的邻居指的是一阶邻居和二阶邻居)。

$V_t$Vt​是图中类型为$t$t的节点集合，$E_v$Ev​是最终输出的节点嵌入表示。

还使用了负采样技术优化（7）式，因为（8）式的分母太难算了。注意负采样是按照节点类型区分的，即正样本和采样到的负样本是同一类型的节点。使用负采样，将（8）式近似为如下的形式：

其中$M$M是负采样的样本数，取值为1。

每次训练有当前样本$v$v，正样本$v_c$vc​，负样本$v_{c^{'}}$vc′​，所以最终的目标函数为：

训练过程在附录里有详细说明。

5 实验

实验目的：

回答4个问题：

1. HetGNN和state-of-the-art baseline相比，在链接预测、个性化推荐、节点分类和聚类任务上效果如何？
2. HetGNN和在inductive图挖掘任务上，例如inductive节点分类和聚类，和state-of-the-art baseline相比效果如何？
3. 节点的异质内容信息编码和异质邻居聚合是如何影响模型性能的？
4. 不同的超参数，如嵌入向量的维度、采样的邻居数目是如何影响模型性能的？

数据集：

使用了两种HetG，学术图和评论图。

对比方法：

metapath2vec(MP2V, 异质图), ASNE(属性图), SHNE(属性图), GraphSAGE(GSAGE), GAT

实验结果：

（1）链接预测实验结果

（2）推荐实验结果

（3）节点分类和聚类实验结果

（4）inductive的节点分类和聚类

（5）不同模块对模型效果的影响

（6）超参数的设置对模型效果的影响

6 总结

本文的特色在于对HIN中节点的内容信息，也就是节点的属性信息，进行了建模，以学习到更好的节点表示。

模型的整体思路很清晰，先编码节点多种多样的(异质)属性信息，将编码后得到的属性嵌入作为节点的表示；然后对于每个节点，根据邻居节点的类型，聚合同一类型的邻居节点的嵌入表示(也就是上一步编码后得到的属性嵌入)；最后将不同类型的邻居节点信息聚合起来。

作者提出了一些trick，比如带有重启的随机游走机制(RWR)，个人感觉带有重启的机制增加了随机游走中遍历到不同类型节点的可能性(也有人说是为了多次遍历到一阶邻居)。

作者还在随机游走中做了一些限制条件，目的是为每个节点采样到所有类型的邻居节点，个人认为这在一定程度上增强了距离远的节点的影响。同时选取了top k个和该节点强相关的邻居节点。

在聚合的过程中，像GraphSAGE一样，采用的均为Bi-LSTM。并且输入是无序的，随机给了个顺序输入，但效果很好。关于输入顺序方面是否可以进行更多的研究，这方面的可解释性太欠缺了。

进行了很多很多的实验，效果都很好，具体应用具体看待吧，感觉这个方法更适合用于节点属性信息丰富的HIN。

在文章结构方面，个人感觉作者做的非常好。哪个模块分哪几步，解释的很清楚流畅，有的小节最后还清楚地整理了优点体现在哪。在实验部分，一上来就写明了实验要解决的几个问题，并且在后面的描述中都有明显的呼应，清楚明了，值得学习。