前言

题目： Heterogeneous Graph Attention Network
会议： WWW 2019
论文地址：Heterogeneous Graph Attention Network

前面的一篇文章里提到了图注意力网络GAT：ICLR 2018 | GAT：图注意力网络，GAT引入了Attention机制来给不同的邻居节点赋予不同的重要性，然后节点在聚合邻居节点特征的过程中会更多地提取重要邻居的特征，从而带来整体效果的提示。

GAT只考虑了同质图，也就是所有节点都同属于一类，即注意力机制在同类邻居节点中提取重要的部分。关于异质图的表示学习，前面的一篇文章里提到了metapath2vec：KDD 2017 | metapath2vec：异质图的可扩展表示学习，metapath2vec定义了meta-path scheme及其对应的随机游走策略，该策略能够捕获不同类型节点及关系的结构和语义相关性。

基于GAT和metapath2vec，本文提出了一种异质图注意力网络HAN(Heterogeneous Graph Attention Network)，HAN将GAT中提出的注意力机制从同质图扩展到了异质图。

1. 问题定义

1.1 节点/语义级注意力

元路径meta-path是连接两个对象的复合关系，是一种广泛用于捕获语义的结构。以图1(a)所示的电影数据IMDB为例：

上面的异质网络包含电影、演员和导演三种类型的节点。两部电影之间的关系可以通过元路径Movie-Actor-Movie(MAM)来揭示，而Movie-Director-Movie(MDM)则表示两部电影由同一位导演执导。可以看到，根据元路径的不同，异质图中节点之间的关系可以具有不同的语义。由于异质图的复杂性，传统的图神经网络不能直接应用于异质图。

基于以上分析，在设计异质图的注意机制图神经网络体系结构时，需要考虑以下新的要求:

1. 图的异质性：异质性是异质图的一个内在性质，即各种类型的节点和边。例如，不同类型的节点具有不同的特征，其特征可能落在不同的特征空间中。还是以IMDB为例，演员的特征可能涉及到性别、年龄和国籍。另一方面，电影的特征可能涉及到情节和演员。如何处理这些复杂的结构信息，同时保存多样的特征信息，是一个亟待解决的问题。
2. 语义级的注意力机制：异质图中涉及的语义信息不同且复杂，通常通过元路径meta-path来反映。异质图中不同的元路径可以提取不同的语义信息，如何为特定任务选择最有意义的元路径并融合语义信息是一个有趣的研究方向。语义级注意力的目的是了解每个元路径的重要性，并为它们分配适当的权重。还是以IMDB为例，《终结者》可以通过Movie-Actor-Movie连接到《终结者2》(均由施瓦辛格主演)，也可以通过Movie-Year-Movie连接到《鸟人》(均拍摄于1984年)。但是，在确定电影《终结者》的类型时，MAM通常比MYM发挥更重要的作用。因此，平等对待不同的元路径是不现实的，并且会削弱一些有用的元路径提供的语义信息。
3. 节点级的注意力机制：在异质图中，节点可以通过各种类型的关系来连接。给定一个元路径，每个节点有许多基于元路径的邻居，如何区分这些邻居的细微差别是必须的。对于每个节点，节点级注意力的目的是了解基于元路径的邻居的重要性，并为其分配不同的注意力值。还是以IMDB为例，在使用元路径Movie-Director-Moive(电影均为同一导演)时，《终结者》将通过詹姆斯·卡梅隆导演连接《泰坦尼克号》和《终结者2》。为了更好地识别《终结者》的类型是科幻电影，模型应该更多地关注《终结者2》，而不是《泰坦尼克号》。因此，应当设计一个模型，该模型能够发现邻居之间的细微差异，并正确地学习它们的权重。

基于上面提出的问题，本文提出了异质图注意力网络HAN，HAN同时考虑了节点级和语义级的注意力。

1.2 术语定义

异质图：

即图中节点类型数和边类型数之和大于2。

元路径：在异质图中，两个对象可以通过不同的语义路径连接起来，这种语义路径称为元路径。具体来讲，一个元路径$\Phi$被定义为：
$$V_1\stackrel{R_1}{\to }{V}_2\stackrel{R_2}{\to }...V_t\stackrel{R_t}{\to }{V}_{t+1}...\stackrel{R_{l-1}}{\to }{V}_l$$
需要注意的是，元路径中相邻节点的类型是不一样的，即$V_i$和$V_{i+1}$属于不同类型的节点，$R_i$表示两个节点间的关系。

如图1(a)所示：

两个电影可以通过多个元路径连接，如电影-演员-电影(Movie-Actor-Movie, MAM)和电影-导演-电影(Movie-Director-Movie, MDM)。不同的元路径总是揭示不同的语义。例如，MAM意味着合作演员关系，而电影-导演-电影(MDM)意味着它们由同一个导演执导。

基于元路径的邻居： 给定一个元路径$\Phi$，每个节点存在一组基于元路径的邻居，这些邻居可以揭示异质图中不同的结构信息和丰富的语义。给定一个异质图中的节点$i$和一个元路径$\Phi$，节点$i$基于元路径的邻居$N_i^{\Phi }$定义为通过元路径$\Phi$与节点$i$连接的节点集合。注意，节点的邻居包括它自己。例如对于上图中的节点$m_1$，给定元路径Movie-Actor-Movie, $m_1$的基于元路径的邻居节点包括$m_1$(本身)、$m_2$和$m_3$。同样，基于元路径Movie-Director-Movie的$m_1$的邻居节点包括$m_1$和$m_2$。

2. HAN

HAN的总体框架如下所示：

可以发现，本文提出的HAN分为三部分：节点级注意力+语义级注意力+预测。具体来讲，首先通过节点级注意力学习基于元路径的邻居对异质图中每个节点的重要性，然后聚合这些邻居节点的表示，最后通过语义级注意力将所有元路径的聚合结果加权得到节点的最终更新状态。

2.1 节点级注意力

在汇总每个节点的元路径邻居的信息之前，应该注意到每个节点基于元路径的邻居在特定任务的节点嵌入学习中扮演着不同的角色，表现出不同的重要性。HAN中引入了节点级注意力，可以学习基于元路径的邻居对异质图中每个节点的重要性，并聚合这些有意义的邻居的表示，以形成一个节点嵌入。

由于节点的异质性，不同类型的节点具有不同的特征空间。因此，对于每种类型的节点(例如类型${\varphi }_i$)，HAN设计了特定类型的转换矩阵$M_{{\varphi }_i}$，将不同类型节点的特征映射到同一特征空间中：
$$h_i^{{}^{\prime }}=M_{{\varphi }_i}\cdot h_i$$
其中$h_i^{{}^{\prime }}$和$h_i$表示映射前后节点$i$的特征。

所有节点的特征完成映射后，利用self-attention来学习每个邻居节点的权重。给定一个通过元路径$\Phi$连接的节点对$(i,j)$，节点级注意力$e_{ij}^{\Phi }$可以学习到节点$j$对节点$i$的重要性：
$$e_{ij}^{\Phi }=at{t}_{node}(h_i^{{}^{\prime }},h_j^{{}^{\prime }};\Phi )$$
这里的$at{t}_{node}$表示执行节点级注意力的深度神经网络。需要注意的是，$e_{ij}^{\Phi }$不是对称的，即节点$i$对节点$j$的重要性和节点$j$对节点$i$的重要性可以有很大的差异。研究表明，节点级注意力可以保持异质图的不对称性，而不对称性是异质图的一个关键特性。

与GAT一致，HAN在只关注节点的基于元路径的邻居节点，而不是所有节点，即$j\in N_i^{\Phi }$。在得到基于元路径的节点对之间的重要性后，通过softmax函数对其进行归一化，以得到每个基于元路径的邻居节点的权重系数${\alpha }_{ij}^{\Phi }$：
$${\alpha }_{ij}^{\Phi }=softmax(e_{ij}^{\Phi })=\frac{exp(\sigma (a_{\Phi }^T\cdot [h_i^{{}^{\prime }}||h_j^{{}^{\prime }}]))}{{\sum }_{k\in N_i^{\Phi }}exp(\sigma (a_{\Phi }^T\cdot [h_i^{{}^{\prime }}||h_k^{{}^{\prime }}]))}$$
这里和GAT操作类似，都是先将节点$i$的特征和其基于元路径的邻居节点$j$的特征进行一个concat操作，然后乘上一个权重系数$a_{\Phi }^T$，然后再经过一个激活函数以得到一个具体的表示节点$j$对节点$i$重要程度的数值，最后再利用softmax进行归一化以得到归一化的权重系数${\alpha }_{ij}^{\Phi }$。

得到每个基于元路径的节点的归一化权重系数后，再将它们的特征进行线性加权，即可得到节点基于某一元路径学习到的嵌入表示：
$$z_i^{\Phi }=\sigma (\sum _{j\in N_i^{\Phi }}{\alpha }_{ij}^{\Phi }\cdot h_j^{{}^{\prime }})$$
节点级聚合过程可以概括如下(a)：

由于异质图具有无标度的特性，因此图数据的方差很大。为了解决该问题，同GAT一致，HAN中也将节点级注意力扩展到了多头注意力，使训练过程更加稳定。具体来说就是重复$K$次节点级注意力，并将学习到的嵌入连接为特定语义的嵌入：

$$z_i^{\Phi }=|{|}_{k=1}^K\sigma (\sum _{j\in N_i^{\Phi }}{\alpha }_{ij}^{\Phi }\cdot h_j^{{}^{\prime }})$$

给定元路径集合 { Φ 0 , Φ 1 , . . . , Φ P } \left \{\Phi_0,\Phi_1,...,\Phi_P \right \} {Φ0​,Φ1​,...,ΦP​}，将节点特征输入到节点级注意力后，可以得到$P$组特定语义的节点嵌入，记作： { Z Φ 0 , Z Φ 1 , . . . , Z Φ P } \left \{Z_{\Phi_0},Z_{\Phi_1},...,Z_{\Phi_P} \right \} {ZΦ0​​,ZΦ1​​,...,ZΦP​​}。

2.2 语义级注意力

一般情况下，异质图中的每个节点都包含多种类型的语义信息，即每个节点都可以得到多个具有特定语义的节点嵌入，而基于语义的节点嵌入只能从一个方面反映节点的特性。为了学习更全面的节点嵌入，我们需要融合元路径所揭示的多种语义。为了解决异质图中元路径选择和语义融合的问题，HAN中提出了一种新的语义级注意力机制，用于自动学习不同元路径的重要性，并为特定任务融合它们。

将从节点级注意力中学习到的$P$组语义特定的节点嵌入作为输入，学习到的每个元路径的权重如下所示：
$$({\beta }_{{\Phi }_0},{\beta }_{{\Phi }_1},...,{\beta }_{{\Phi }_P})=at{t}_{sem}(Z_{{\Phi }_0},Z_{{\Phi }_1},...,Z_{{\Phi }_P})$$
这里的$at{t}_{sem}$表示执行语义级注意力的深度神经网络。

假设每个元路径的重要性记为$w_{{\Phi }_i}$，则有：
$$w_{{\Phi }_i}=\frac{1}{\mathcal{V}}\sum _{i\in \mathcal{V}}{q}^T\cdot tanh(W\cdot z_i^{\Phi }+b)$$
即对于每一个元路径${\Phi }_i$，其有着$|\mathcal{V}|$(节点个数)组节点嵌入表示。为了计算这条元路径的重要性，对于每一个节点，首先将其在该元路径下的嵌入表示经过一个非线性层，然后乘上一个语义级注意力向量$q$，最后再将所有节点的转换结果进行平均，以得到这条元路径的重要性。

需要注意的是，所有参数对于所有元路径和语义特定的嵌入都是共享的，即$W,b,q$对所有元路径来说是共享的。在得到所有元路径的重要性之后，利用softmax函数对其进行归一化，以得到每条元路径的归一化权重系数${\beta }_{{\Phi }_i}$：
$${\beta }_{{\Phi }_i}=\frac{exp(w_{{\Phi }_i})}{{\sum }_{i=1}^{P}exp(w_{{\Phi }_i})}$$
学习到每条元路径的重要性后，我们可以将所有基于元路径的节点嵌入表示进行加权：
$$Z=\sum _{i=1}^P{\beta }_{{\Phi }_i}\cdot Z_{{\Phi }_i}$$
语义级聚合过程可以概括如下(b)：

在得到所有节点的嵌入表示后，为了进行半监督节点分类，定义如下损失函数：
$$L=-\sum _{l\in y_L}{Y}^{l}ln(C\cdot Z^l)$$
其中$C$为分类器参数，$y_L$为有标签的节点的索引集合，$Y^l$和$Z^l$分别表示节点的标签和嵌入向量。

HAN的总体过程如下所示：

2.3 模型分析

HAN的分析如下：

• HAN能够处理异质图中各种类型的节点和关系，融合丰富的语义。信息可以通过不同的关系从一种节点传递到另一种节点。得益于这种异质的图注意力网络，不同类型的节点嵌入可以相互融合、相互促进、相互升级。
• HAN算法效率高，易于并行化。HAN整体复杂度与节点和基于元路径的节点对的数量成线性关系。由于节点级注意力和语义级注意力可以分别跨节点对和元路径进行并行化，因此该模型易于并行化。
• 分层注意力对整个异质图来讲是共享的，这意味着参数的数量不依赖于异质图的规模，可以用于归纳问题，即HAN可以为未知节点甚至未知图生成节点嵌入。
• HAN对学习到的节点嵌入具有良好的可解释性，为异质图分析提供了很大的优势。通过了解节点和元路径的重要性，HAN可以更关注特定任务的一些有意义的节点或元路径，并对异质图进行更全面的描述。基于注意力值，我们可以检查哪些节点或元路径对我们的任务做出了更高(或更低)的贡献，这有利于分析和解释我们的结果。

3. 实验

3.1 数据集

3.2 节点分类

实验结果如下所示：

由上表可知：

1. HAN的性能最好。
2. 对于传统的异质图嵌入方法来讲，ESim可以利用多个元路径，其性能优于metapath2vec。
3. 基于GNN的方法通常表现更好，如GCN和GAT。
4. 与简单的平均邻居相比，如GCN和HANnd，GAT和HAN可以适当地权衡信息，提高嵌入性能。
5. 与GAT相比，HAN由于成功地捕获了丰富的语义，显示出其优越性。
6. 此外，如果没有节点级注意力(HANnd)或语义级注意力(HANsem)，性能相比HAN会差一些，这说明了在节点和语义上对注意力机制进行建模的重要性。
7. 在ACM和IMDB中，HAN对分类结果的改善比DBLP更显著，这主要是因为APCPA比其他元路径重要得多。

3.3 聚类

在得到所有节点的嵌入表示后，使用K-Means来执行节点聚类，簇的数量K被设置为类的数量，并采用NMI和ARI方法对聚类结果进行质量评价，实验结果如下所示：

可以发现：

1. HAN始终表现最好。
2. 基于GNN的算法通常可以获得更好的性能。
3. 由于没有区分节点和元路径的重要性，metapath2vec和GCN效果一般。
4. HAN的性能明显优于GCN和GAT。
5. 在缺乏节点级注意力(HANnd)和语义级注意力(HANsem)的情况下，HAN表现出不同程度的退化。这说明通过对节点和元路径分配不同的重要性，HAN可以学习到更有意义的节点嵌入。

4. 总结

本文针对异质图分析中的几个基本问题，提出了一种完全基于注意力机制的半监督异质图神经网络HAN，HAN能够捕获异质图背后的复杂结构和丰富语义。

具体来讲，一个异质图中通常有多种元路径，每一种元路径下每个节点都有基于该元路径的邻居节点。HAN首先通过节点级注意力对基于元路径的邻居节点的重要性进行区分并加权处理，以得到某种元路径下节点的聚合特征；然后通过语义级注意力对所有元路径的重要性进行区分，最后将节点在所有元路径下的聚合特征进行加权处理，以得到该节点最终的更新表示。

通过与现有模型的比较，HAN表现出了较大的优越性。更重要的是，通过分析分层注意力机制，HAN对异质图分析具有良好的可解释性。