https://qiniu.pattern.swarma.org/pdf/arxiv/2002.01680.pdf

https://github.com/cynricfu/MAGNN

MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding ，KDD，2020

总结：现有的利用元路径做异构网络嵌入的方法存在一些限制：“要么忽略了节点的内容特征，要么丢弃了元路径上的中间节点，要么仅仅考虑一条元路径”。为了解决这些问题，作者提出了MAGNN模型，包含三个组件：（1）node content转换器，用一个简单的线性映射把异构特征信息（比如图像和文本）映射到同一个特征空间；（2）intra-metapaht聚合器，将同一个类型元路径的多条实例合并成单个向量，表示该类型元路径的语义信息（这块参考RotatE，用一个Relational rotation encoder进行整合）；（3）inter-metapath聚合器，将不同类型元路径的语义信息整合到一起（用一个注意力机制）。

1. 简介

1.1 摘要

A large number of real-world graphs or networks are inherently het-erogeneous, involving a diversity of node types and relation types.Heterogeneous graph embedding is to embed rich structural and se-mantic information of a heterogeneous graph into low-dimensionalnode representations. Existing models usually define multiple meta-paths in a heterogeneous graph to capture the composite relationsand guide neighbor selection. However, these models either omitnode content features, discard intermediate nodes along the meta-path, or only consider one metapath. To address these three lim-itations, we propose a new model namedMetapath AggregatedGraph Neural Network(MAGNN) to boost the final performance.Specifically, MAGNN employs three major components, i.e., thenode content transformation to encapsulate input node attributes,the intra-metapath aggregation to incorporate intermediate seman-tic nodes, and the inter-metapath aggregation to combine mes-sages from multiple metapaths. Extensive experiments on threereal-world heterogeneous graph datasets for node classification,node clustering, and link prediction show that MAGNN achievesmore accurate prediction results than state-of-the-art baselines.

现实世界中的很多网络都是异构的，涉及到多种类型的节点和边。异构网络嵌入旨在将网络中丰富的结构和语义信息嵌入到一个低维节点表示中。现有的模型通常在异构网络中定义多个元路径来捕捉复杂的关系并指导领域的原则。但是这些方法要么忽略了节点的内容特征，要么丢弃了元路径上的中间节点，要么仅仅考虑一条元路径。为了解决这三个限制，本文作者提出了一个MAGNN的新模型。具体来说，MAGNN包含三个组件：（1）node content转换器，捕捉节点属性信息（2）intra-metapath聚合器，合并元路径中间语义节点信息（3）inter-metapath聚合器，组合多个元路径中的信息。三个异构网络上的大量实验表明，在节点分类、链路预测和节点聚类三个任务上，MAGNN和当前最优方法相比都取得了更好结果。

1.2 本文工作

现有的基于元路径的嵌入方法比如ESim，metapath2vec，HIN2vec、HERec等虽然传统方法性能好，但是也存在一些limitations：

1. 没有利用node content信息，在具有丰富节点内容特征的异构网络上表现不好
2. 丢弃了元路径上中间节点，只考虑了路径两端的节点
3. 模型只依赖于一条元路径，需要手动选取一条元路径，丢失了其他元路径信息，达不到最优效果

为了解决这些问题，作者提出了MAGNN模型。

1.3 问题定义

异构网络：$\mathcal{G=(V,E)}$，节点类型映射$\mathcal{\phi:V\rightarrow E}$，边类型映射$\psi: \mathcal{E} \rightarrow \mathcal{R}$，$\mathcal A$和$\mathcal R$分别表示节点类型和边类型集合且$|\mathcal A|+|\mathcal R|>2$

元路径：$A_{1} \stackrel{R_{1}}{\longrightarrow} A_{2} \stackrel{R_{2}}{\longrightarrow} \cdots \stackrel{R_{l}}{\longrightarrow} A_{l+1}$，$A_1\sim A_l$为节点类型，$R_1\sim R_l$为边类型

**基于元路径的neighbor：**给定元路径P，通过元路径实例连接到节点v的路径上节点定义为$N_v^P$（注：如果一个neighbor通过两个不同的元路径实例连接到v，那么这个neighbor看做$N_v^P$中两个不同的节点；如果P是对称的，那么$N_v^P$包含节点v本身）

**基于元路径的graph：**给定元路径P，$\mathcal G$中所有metapath-P-based neighbor pairs构成的图称之为metapath-based Graph，表示为$\mathcal G^P$（注：如果P是对称的，那么$\mathcal G^P$是同构的）

**异构网络嵌入：**给定异构网络$\mathcal {G=(V,E)}$，节点属性$X_{A_i}\in\R^{|\mathcal V_{A_i}|\times d_{A_i}}$，学习d维节点表示$h_v\in\R ^d$，$d\ll|\mathcal V|$，能够同时捕捉丰富的结构和语义信息

2. MAGNN

2.1 Node Content Transformation

带有节点属性的异构网络中，不同类型节点的特征向量的维度不同，即使相同也可能处于不同的特征空间（比如图像特征和文本特征）。因此，在将节点特征喂给MAGNN之前，需要将节点的特征向量映射到同一个潜在空间。

对于$v\in\mathcal V_A$，$A\in\mathcal A$，有：

$h_v'=W_A·x_v^A$

其中$x_v\in\R^{d_A}$表示原始特征向量，$h_v'$表示映射后的特征向量，$W_A$表示类型A矩阵特征映射的参数。

2.2 Intra-metapath Aggregation

• $P(v,u)$表示一条连接目标节点v和邻域节点u的元路径实例，其中$u\in\mathcal N_v^P$
• 定义元路径实例内部节点为$\left\{m^{P(v, u)}\right\}=P(v, u) \backslash\{u, v\}$。

Intra-metapath aggregation利用一个encoder，将元路径实例中涉及到的所有内部节点特征整合成一个向量：

$\mathbf{h}_{P(v, u)}=f_{\theta}(P(v, u))=f_{\theta}\left(\mathbf{h}_{v}^{\prime}, \mathbf{h}_{u}^{\prime},\left\{\mathbf{h}_{t}^{\prime}, \forall t \in\left\{m^{P(v, u)}\right\}\right\}\right)\tag 2$

$h_{P(v,u)}\in\R^{d'}$表示该条元路径实例的特征。对于encoder $f_\theta(·)$作者提供了三种方案：

1. Mean encoder

   $\mathbf{h}_{P(v, u)}=\operatorname{MEAN}\left(\left\{\mathbf{h}_{t}^{\prime}, \forall t \in P(v, u)\right\}\right)\tag 8$

2. Linear encoder

   $\mathrm{h}_{P(v, u)}=\mathrm{W}_{P} \cdot \operatorname{MEAN}\left(\left\{\mathbf{h}_{t}^{\prime}, \forall t \in P(v, u)\right\}\right)\tag 9$

3. Relational rotation encoder

   基于知识图谱方法RotatE提出来的，mean和linear方法都只是将元路径实例看做一个集合，忽略了元路径的序列结构。给定$P(v,u)=(t_0,t_1,...,t_n)$，$t_0=u$，$t_n=v$，$R_i$表示$t_{i-1}$和$t_i$之间的关系，$r_i$为$R_i$的关系向量。relational rotation encoder定义如下：

   $\begin{array}{l}\mathbf{o}_{0}=\mathbf{h}_{t_{0}}^{\prime}=\mathbf{h}_{u}^{\prime} \\\mathbf{o}_{i}=\mathbf{h}_{t_{i}}^{\prime}+\mathbf{o}_{i-1} \odot \mathbf{r}_{i} \\\mathbf{h}_{P(v, u)}=\frac{\mathbf{o}_{n}}{n+1}\end{array}\tag {10}$

   其中$h_{t_i}'$和$r_i$都是复向量（前半部分看做实部，后半部分看做虚部），$\odot$表示element-wise乘。

   注：为什么是复向量？$r_i$怎么来的？

得到$h_{P(v,u)}$后，利用一个graph attention layer整合P类型元路径下的所有实例对节点v的影响（每条路径实例对v的影响程度不同，所以采用注意力机制）：

$\begin{array}{l} e_{v u}^{P}=\text { LeakyReLU }\left(\mathrm{a}_{P}^{\top} \cdot\left[\mathbf{h}_{v}^{\prime} \| \mathbf{h}_{P(v, u)}\right]\right) \\ \alpha_{v u}^{P}=\frac{\exp \left(e_{v u}^{P}\right)}{\sum_{s \in \mathcal{N}_{v}^{P}} \exp \left(e_{v s}^{P}\right)}, \\ \mathbf{h}_{v}^{P}=\sigma\left(\sum_{u \in \mathcal{N}_{v}^{P}} \alpha_{v u}^{P} \cdot \mathbf{h}_{P(v, u)}\right) \end{array}\tag 3$

$a_P$为注意力参数，$||$表示拼接操作，$e_{vu}^P$表示该实例的重要程度，$\alpha_{vu}^P$表示正则化后的重要程度，最后所有路径实例的影响加权求和作为最终输出。此处注意力机制也可以拓展成多头的，提高模型稳定性：

$\mathbf{h}_{v}^{P}=\|_{k=1}^{K} \sigma\left(\sum_{u \in \mathcal{N}_{v}^{P}}\left[\alpha_{v u}^{P}\right]_{k} \cdot \mathbf{h}_{P(v, u)}\right)\tag 4$

**总结：**给定经2.1转换后的节点特征和所有以节点类型为$A\in\mathcal A$开始或结尾的元路径集合$\mathcal P_A=\{P_1,P_2,...,P_M\}$，经过intra-metapath aggregation后可以得到M个metapath-specific向量表示：$\{h_v^{P_1},h_v^{P_2},...,h_v^{P_M}\}$。

2.3 Inter-metapath Aggregation

首先对每个类型元路径$P_i\in\mathcal P_A$，计算该类型路径在所有节点$v\in\mathcal V_A$下线性转换后的平均值：

$\mathrm{s}_{P_{i}}=\frac{1}{\left|\mathcal{V}_{A}\right|} \sum_{v \in \mathcal{V}_{A}} \tanh \left(\mathbf{M}_{A} \cdot \mathbf{h}_{v}^{P_{i}}+\mathbf{b}_{A}\right)\tag 5$

其中$M_A$和$b_A$为线性转换层的参数。然后按照下面的方式对$\{h_v^{P_1},h_v^{P_2},...,h_v^{P_M}\}$进行注意力整合：

$\begin{array}{l} e_{P_{i}}=\mathrm{q}_{A}^{\top} \cdot \mathrm{s}_{P_{i}} \\ \beta_{P_{i}}=\frac{\exp \left(e_{P_{i}}\right)}{\sum_{P \in \mathcal{P}_{A}} \exp \left(e_{P}\right)} \\ \mathbf{h}_{v}^{\mathcal{P}_{A}}=\sum_{P \in \mathcal{P}_{A}} \beta_{P} \cdot \mathbf{h}_{v}^{P} \end{array}\tag 6$

其中$q_A$为注意力参数，$e_{P_i}$为$h_v^{P_i}$的重要程度，$\beta_{P_i}$为$h_v^{P_1}$的正则化后的重要程度，$h_v^{\mathcal P_A}$为最终输出。

最后MAGNN再利用一个额外的线性转换成计算最终节点嵌入：

$\mathbf{h}_{v}=\sigma\left(\mathbf{W}_{o} \cdot \mathbf{h}_{v}^{\mathcal{P}_{A}}\right)\tag 7$

2.4 Training

两种方式：半监督学习和无监督学习

1. 半监督

   利用一小部分有标签节点进行训练，交叉熵损失定义如下：

   $\mathcal{L}=-\sum_{v \in \mathcal{V}_{L}} \sum_{c=1}^{C} \mathrm{y}_{v}[c] \cdot \log \mathrm{h}_{v}[c]\tag {11}$

   其中$\mathcal V_L$为有标签节点，$C$表示类别数量，$y_v$是节点one-hot向量，$h_v$为预测的节点类型概率向量。

2. 无监督学习

   通过负采样，最小化下列损失函数：

   $\mathcal{L}=-\sum_{(u, v) \in \Omega} \log \sigma\left(\mathbf{h}_{u}^{\top} \cdot \mathbf{h}_{v}\right)-\sum_{\left(u^{\prime}, v^{\prime}\right) \in \Omega^{-}} \log \sigma\left(-\mathbf{h}_{u^{\prime}}^{\top} \cdot \mathbf{h}_{v^{\prime}}\right)\tag {12}$

   其中$\sigma(·)$是sigmoid函数，$\Omega$表示observed（positive）节点对，$\Omega^-$为unobserved节点对（$\Omega$的补集）。

模型伪代码如下图所示：

3. 实验

解决5个问题：

1. 节点分类任务中MAGNN如何？
2. 节点聚类任务中MAGNN如何？
3. 链路预测任务中MAGNN如何？
4. 三个components中，哪个最有用？
5. 不同的图嵌入方法表征能力为何不同？

3.1 数据集

数据集：IMDb（节点分类），DBLP（节点聚类），Last.fm（链路预测）

3.2 Baselines

• traditional homogeneous models：LINE，node2vec
• traditional heterogeneous models ：ESim，metapath2vec，HERec
• homogeneous GNNs：GCN，GAT
• heterogeneous GNNs ：GATNE，HAN

3.3 基础实验

一、 节点分类

将各个模型生成的node embedding喂给一个SVM分类器，以此比较个模型性能。下表Training表示SVM中用多少数据用于训练。

二、节点聚类

学到的embedding放到K-Means中，重复10次试验取平均值，结果如下表：

三、链路预测

3.4 消融实验

$MAGNN_{rot}$表示2.2节的encoder使用rotation encoder，$MAGNN_{sm}$表示只考虑单个最好的元路径，$MAGNN_{avg}$表示2.2节的encoder使用mean encoder，$MAGNN_{linear}$表示用linear encoder，$MAGNN_{feat}$表示不适用content feature。

3.5 可视化

Last.fm数据集中随机选取30个user-artist对，然后将它们的embedding投影到二维空间中。