Heterogeneous Graph Neural Network

2021-06-04

字数统计: 3.7k | 阅读时长≈ 16 分钟

https://dl.acm.org/doi/pdf/10.1145/3292500.3330961

https://github.com/chuxuzhang/KDD2019_HetGNN

Heterogeneous Graph Neural Network，KDD，2019

总结：解决异构网络嵌入中存在的三个挑战：（1）如何为每个节点采样高相关性的邻居？（2）如何设计一个node content编码器，解决不同节点携带的信息是异构这一问题？（3）如何考虑节点类型的影响，整合不同类型邻居节点的信息？针对这三个问题作者分别提出了解决方案：（1）采用RWR采样，按照出现频率选取前10各节点作为目标节点v的邻居，这样可以保证每个节点邻居数量相同，且高相关性邻居被采样到；（2）采用双向LSTM对节点内容信息进行编码，将文本、图像等多模态特征整合成一个特征向量；（3）将节点邻居按类型分类，计算每个类型邻居节点的信息，再通过注意力机制聚合所有类型邻居节点的信息。

1. 简介

1.1 摘要

Representation learning in heterogeneous graphs aims to pursue a meaningful vector representation for each node so as to facilitate downstream applications such as link prediction, personalized recommendation, node classification, etc. This task, however, is challenging not only because of the demand to incorporate heterogeneous structural (graph) information consisting of multiple types of nodes and edges, but also due to the need for considering heterogeneous attributes or contents (e.д., text or image) associated with each node. Despite a substantial amount of effort has been made to homogeneous (or heterogeneous) graph embedding, attributed graph embedding as well as graph neural networks, few of them can jointly consider heterogeneous structural (graph) information as well as heterogeneous contents information of each node effectively. In this paper, we propose HetGNN, a heterogeneous graph neural network model, to resolve this issue. Specifically, we first introduce a random walk with restart strategy to sample a fixed size of strongly correlated heterogeneous neighbors for each node and group them based upon node types. Next, we design a neural network architecture with two modules to aggregate feature information of those sampled neighboring nodes. The first module encodes “deep” feature interactions of heterogeneous contents and generates content embedding for each node. The second module aggregates content (attribute) embeddings of different neighboring groups (types) and further combines them by considering the impacts of different groups to obtain the ultimate node embedding. Finally, we leverage a graph context loss and a mini-batch gradient descent procedure to train the model in an end-to-end manner. Extensive experiments on several datasets demonstrate that HetGNN can outperform state-of-the-art baselines in various graph mining tasks, i.e., link prediction, recommendation, node classification & clustering and inductive node classification & clustering.

异构网络中的表示学习旨在为每个节点寻找一个有意义的表示向量，来解决链路预测、个性推荐、节点分类等下游任务。但是这个任务是十分具有挑战性的，一方面需要整合包含等多种类型节点和边组成的异构结构信息，另一方面还要考虑每个节点具有的异构属性或者内容。尽管对于异构网络嵌入、属性网络嵌入以及GNNs等问题已经有了大量研究，但是很少有研究能够有效地同时考虑异构结构信息和每个节点的异构内容信息。本文，作者提出了HetGNN模型，一种用来解决上述问题的异构图神经网络模型。具体来说，作者首先介绍了一个restart随机游走策略来为每个节点采样一个固定大小的、高相关的异构邻居，并对这些采样的邻居节点按照节点类型进行分类。然后设计一个包含两个模块的神经网络架构来整合这些采样到的邻居节点的信息。第一个模块对异构内容信息进行深度编码，为每个节点生成content embedding。第二个模块分别整合每个类别下所有邻居节点的content embedding（组内整合），然后按照每组节点的影响力，对conten embedding进行进一步整合（组间整合）得到最终的node embedding。·最后了利用一个graph context损失和mini-batch梯度下降来端到端的训练模型。几个数据集上的大量实验表明HetGNN模型比现有的最优模型在链路预测、推荐、节点分类、聚类等任务上性能更优。

1.2 本文工作

现有的图表示学习方法中，DeepWalk、metapath2vec、ASNE等方法都是直接学习节点潜在特征，不能很好地捕捉丰富的邻居信息。能力更强的GNNs比如GCN、GraphSAGE、GAT等可以学习到更好的节点embedding，但是大多数GNNs都是用于同构网络，将其应用于HetG中还存在如下挑战：

HetG中很多节点的邻居没有覆盖所有节点类型，并且不同节点的邻居数目各不相同。现有的大多数GNN都是直接聚合一阶邻居信息，这导致“hub”节点（度高的节点）embedding的生成会受到噪声节点的影响（邻居很多，里面会掺杂噪声邻居，削弱相关性强的邻居的影响力），而“cold-start”节点（度低的节点）embedding学习到的信息不够充分（因为邻居很少，聚合到的信息也很少）。因此，这产生了第一个Change：如何为每个节点采样高相关性的邻居？
HetG中的一个节点可能会携带非结构化信息，比如属性、文本、图像等，并且不同类型的节点可能会携带不同类型的信息。现有GNNs直接的concatenation操作或者线性转换无法对节点异构信息之间的深层次交互进行建模。另外，不同类型的节点不能共用一个特征转换函数，因为不同类型节点携带的信息是不同的（有的是文本，有的是图片）。因此，第二个挑战是：如何设计一个node content编码器，解决不同节点携带的信息是异构这一问题？
HetG中不同类型的邻居节点对node embedding的影响是不同的，例如在学术网络中，和venue节点相比，作者和论文节点对于作者节点嵌入的影响应该更大，而现有的GNNs大多用于同构网络，没有考虑节点类型的影响。因此，第三个挑战是：如何考虑节点类型的影响，整合不同类型邻居节点的信息？

为了解决上述3个问题，作者提出了HetGNN模型。

首先设计一个restart随机游走策略，为每个节点采样固定大小的高相关邻居节点，并将其按照节点类型分类。
然后设计一个包含两个模块的神经网络架构
- 第一个模块采用RNN对节点携带的异构信息进行编码，得到每个节点的content embedding
- 第二个模块利用另一个RNN按照节点类型整合每组邻居的content embedding（组内），再用一个注意力机制整合所有组的content embedding（组间）得到最终的节点嵌入。
最后，利用graph context损失和mini-batch梯度下降训练模型。

1.3 问题定义

本文的方法针对“Content-associated Heterogeneous Graph”，该类型图定义如下：C-HetG表示为 $G=(V,E,O_V,R_E)$ ，包含多种类型的节点和边， $O_V$ 和 $R_E$ 分别表示节点类型和边类型，另外每个节点还携带者和节点相关的异构信息比如属性、文本和图像。如下图所示：

异构网络表示学习定义为：给定一个C-HetG $G=(V,E,O_V,R_E)$ ，以及content信息 $C$ ，我们要训练一个模型 $\mathcal F_\Theta$ ，给每个节点学习一个d维嵌入 $\mathcal E\in\mathbb R^{|V|\times d}(d\ll|V|)$ ，这个embedding同时编码了异构结构信息和异构内容信息，用于各种图挖掘任务如链路预测、推荐、多标签分类等。

2. HetGNN

HetGNN包含四个部分：（1）异构邻居采样；（2）节点异构信息编码；（3）聚合异构邻居信息；（4）构造目标函数和模型训练过程。

2.1 异构邻居采样

采用RWR进行邻居节点采样，包含下面两步：

采样固定长度的RWR：从节点 $v\in V$ 开始随机游走，有一定概率p返回开始节点重新游走，直到采集到足够数量节点（游走过程中会添加约束确保每种类型节点都被采样到）。
按类型对采样到的节点进行分类，对于每个类型t，按照其在RWR(v)中的出现频率选取top k个节点，将它们视为节点v在t类型下最相关的邻居节点

这种采样方式可以有效解决上面提到的三个问题：

RWR采样的节点覆盖了所有节点类型
对邻居节点按类型分组，这样可以分组整合邻居节点的信息

2.2 编码异构内容信息

节点内容 $C_v$ 中第i项表示为 $x_i\in \mathbb R^{d_f\times 1}$ ， $x_i$ 是不同预训练好的模型计算出的content特征。现有的方法针对异构内容信息，大多采用concatenate操作或者线性转换，将异构信息特征转换成单个向量。本文作者设计了一个新的架构来编码异构内容信息，利用双向LSTM来捕捉深层次的特征交互，得到表达能力更强的content embedding。具体计算方式如下：

f_{1}(v)=\frac{\sum_{i \in C_{v}}\left[\overrightarrow{L S T M}\left\{\mathcal{F} C_{\theta_{x}}\left(\mathrm{x}_{i}\right)\right\} \oplus \overleftarrow{L S T M}\left\{\mathcal{F} C_{\theta_{x}}\left(\mathrm{x}_{i}\right)\right\}\right]}{\left|C_{v}\right|}\tag 1

其中 $f_1(v)\in R^{d\times 1}$ 表示最终的节点内容嵌入， $\mathcal{FC}_{\theta_x}$ 表示参数为 $\theta_x$ 的全连接层， $\oplus$ 表示拼接操作。LSTM的具体计算方式如下：

\begin{aligned} \mathrm{z}_{i} &=\sigma\left(\mathcal{U}_{z} \mathcal{F} C_{\theta_{x}}\left(\mathrm{x}_{i}\right)+\mathcal{W}_{z} \mathrm{~h}_{i-1}+\mathrm{b}_{z}\right) \\ \mathrm{f}_{i} &=\sigma\left(\mathcal{U}_{f} \mathcal{F} C_{\theta_{x}}\left(\mathrm{x}_{i}\right)+\mathcal{W}_{f} \mathrm{~h}_{i-1}+\mathrm{b}_{f}\right) \\ \mathrm{o}_{i} &=\sigma\left(\mathcal{U}_{o} \mathcal{F} C_{\theta_{x}}\left(\mathrm{x}_{i}\right)+W_{o} \mathrm{~h}_{i-1}+\mathrm{b}_{o}\right) \\ \hat{\mathrm{c}}_{i} &=\tanh \left(\mathcal{U}_{c} \mathcal{F} C_{\theta_{x}}\left(\mathrm{x}_{i}\right)+\mathcal{W}_{c} \mathrm{~h}_{i-1}+\mathrm{b}_{c}\right) \\ \mathrm{c}_{i} &=\mathrm{f}_{i} \circ \mathrm{c}_{i-1}+\mathrm{z}_{i} \circ \hat{\mathrm{c}}_{i} \\ \mathrm{~h}_{i} &=\tanh \left(\mathrm{c}_{i}\right) \circ \mathbf{o}_{i} \end{aligned}\tag 2

其中 $h_i$ 表示 $x_i$ 的hidden state， $\circ$ 表示哈达玛积， $\mathcal U_i\in\mathbb R^{(d/2)\times d_f}$ ， $\mathcal W_j\in\mathbb R^{(d/2)\times(d/2)}$ ， $\mathcal b_j\in\mathbb R^{(d/2)\times 2}$ 为可学习参数， $z_i$ ， $f_i$ ， $o_i$ 分别为forget、input和output三个门向量。

2.3 聚合异构邻居信息

包含两步：（1）same type neighbors aggregation；（2）types combination

对于节点v的t-type邻居，按照如下方式进行聚合：

f_{2}^{t}(v)=\mathcal{A} \mathcal{G}_{v^{\prime} \in N_{t}(v)}^{t}\left\{f_{1}\left(v^{\prime}\right)\right\}\tag 3

其中 $f_2^t(v)\in\mathbb R^{d\times 1}$ 表示t类型邻居聚合后的embedding， $\mathcal{AG}^t$ 表示t类型邻居节点聚合器，可以是全连接NN，也可以是GCN或者RNN。在本文中作者采用Bi-LSTM来分别聚合每个类型的邻居， $f_2^t(v)$ 计算方式如下：

f_{2}^{t}(v)=\frac{\sum_{v^{\prime} \in N_{t}(v)}\left[\overrightarrow{L S T M}\left\{f_{1}\left(v^{\prime}\right)\right\} \bigoplus \overleftarrow{L S T M}\left\{f_{1}\left(v^{\prime}\right)\right\}\right]}{\left|N_{t}(v)\right|}\tag 4

对于types combination，考虑到不同类型节点对embedding的影响力不同，节点v最终的embedding计算方式如下：

\mathcal{E}_{v}=\alpha^{v, v} f_{1}(v)+\sum_{t \in O_{V}} \alpha^{v, t} f_{2}^{t}(v)\tag 5

公式前半部分表示节点content嵌入，后半部分表示聚合邻居的embedding。 $\alpha^{v,*}$ 表示不同节点embedding的重要程度， $f_1(v)$ 表示节点的content embedding， $f_2^t(v)$ 表示t-type邻居节点的embedding。用 $\mathcal{F}(v)=\left\{f_{1}(v) \cup\left(f_{2}^{t}(v), t \in O_{V}\right)\right\}$ 表示所有的embedding集合，节点embedding的计算方式调整如下：