异质图注意力网络（Heterogeneous Graph Attention Network,HAN）

0 摘要(Abstract)

GNN是一种基于深度学习的强大的图表示学习算法，它有着优越的性能。然而，GNN并没有对异质图（具有不同类型的节点和边）这一数据结构作充分的考虑。

异质图的丰富的语义信息给设计异质图神经网络带来了巨大的挑战。近期，深度学习上一个巨大的突破就是注意力机制的提出。注意力在许多领域中都表现出了巨大的潜力。在本文中，我们提出了一个新颖的异质图分级注意力网络——它包含节点级注意力和语义级注意力。具体来说，节点级注意力旨在学习某一个节点与其各个元路径下的各个邻居之间的注意力，语义级注意力旨在学习不同元路径的重要性。在学习了节点级和语义级注意力之后，节点和元路径的重要性就可以被充分考虑到了。

1 介绍(Introduction)

尽管注意力机制在深度学习上已经取得了成功，基于异质图这一数据结构的图网络还未被研究。然而，现实中有许多图具有多类型的节点和边，被称作异质图信息网络，简称为异质图。异质图具有复杂的信息和丰富的语义，因而被广泛应用于数据挖掘中。元路径是一种连接两个对象的复合关系，是一种用于捕捉语义的结构。

我们以电影数据(IMDB)为例，该图具有三种类型的节点：电影、演员和导演。两个电影之间的关系可以被解释为一个元路径电影-演员-电影(MAM)，它描述了由同一个演员出演的电影。此外，两个电影还有另一种关系，即电影-导演-电影(MDM)，它描述了由同一个导演编导的电影。可以看出，基于不同的元路径，节点之间的关系可以被解释为不同的语义。正是由于这种复杂性，传统的GNN不能够直接应用于异质图。

1.1 图的异质性(Heterogeneity of graph)

图的异质性是异质图的本质特征，不同类型的节点、边有不同的特点，它们的features可能会落入不同维度的特征空间。我们仍然以IMDB为例，演员的features可能包括sex，age，nationality，电影的features可能包括plot，actors。因此，如何处理基于这样复杂的结构的信息同时保留多元特征是一个亟待解决的问题。

1.2 语义级注意力(Semantic-level attention)

元路径反映了异质图复杂的语义信息，不同的元路径可以提炼出不同的语义信息。如何挑选出最有用的元路径是一个开放的问题。语义级注意力旨在学习每个元路径的重要性，并且为它们分配不同的注意力权重。我们仍然以IMDB为例，电影终结者可以与电影终结者2通过都是由演员施瓦辛格主演相连，或者通过都是在年份1984年上映相连。然而，当我们考虑电影终结者的这两种元路径的重要程度时，MAM(Movie-Actor-Movie)相比于MYM(Movie-Year-Movie)通常来说会更加重要。因此，将所有的元路径平等对待显然会造成语义信息的丢失。

1.3 节点级注意力(Node-level attention)

在异质图中，节点之间可以以多种类型的边相连接，每一个节点都有一些基于不同元路径的邻域节点集。如何区分邻域节点之间微妙的区别，并挑选出一些具有有效信息的邻域节点。对于每一个节点，节点级注意力旨在学习基于元路径的邻域节点集的重要性，并且为这些邻域节点们分配不同的注意力权重。我们仍然以IMDB为例，当我们选择元路径MDM(Movie-Director-Movie)时，电影终结者会同时与电影泰坦尼克号和电影终结者2通过共同的导演James Cameron相连。为了更好地确认电影终结者的类型为科幻片，我们的模型应该在电影终结者2上分配更多的注意力。因此，我们期望设计一种模型来挖掘不同邻域节点之间的微妙差别并学习注意力权重。

1.4 本文贡献(Contributions)

在文中，我们提出了一种全新的异质图注意力网络(Heterogeneous graph Attention Network,HAN)，它考虑了节点级注意力和语义级注意力。特别的，当我们给出节点的features作为模型输入时，我们可以使用特定类型的转换矩阵来将不同类型的节点的features投影到相同维度的向量空间中。接下来，节点级注意力将要学习节点与其基于不同元路径下的邻域节点集间的注意力值，然而语义级注意力将要学习不同元路径的注意力。在学习了这两种不同类型的注意力后，我们的模型可以学习到最佳的邻域节点和元路径的组合形式，使得节点嵌入能够更好地捕捉异质图复杂的结构信息和丰富的语义信息。在此之后，整体的模型可以通过端到端的反向传播算法进行优化。本篇论文主要有以下贡献：

首次提出基于异质图的注意力机制学习算法
提出异质图注意力网络(Heterogeneous graph Attention Network,HAN)，可以捕获语义信息，同时具有线性的复杂度，能够学习大规模异质图。
本算法经过大量实验表明相比于当前最先进的算法具有更优越的性能，同时，本算法还发掘出了异质图分析的巨大潜力。

2 相关工作(Related Work)

2.1 图神经网络(Graph Nerual Networks)

GNNs旨在将深度神经网络扩展到图这一数据结构中。近年来，出现了大量的关于扩展卷积操作到图上的尝试，它们大致分为两派：频域卷积和非频域卷积。前者考虑通过傅立叶变换在图的频域定义卷积操作，最后逆傅立叶变换回到空域；后者则直接在图的空域定义邻域，进而定义卷积操作。注意力机制最近饱受热议，它用于学习节点间的注意力权重，从而进行节点信息的更新。然而，上述方法都无法直接应用于异质图。

2.2 图嵌入(Network Embedding)

图嵌入，换言之，图表示学习(NRL)，是一种力图在保留原始图的结构和特性的前提下将图嵌入到一个低维空间，从而便于将图应用于下游任务中。例如，随机游走算法(random walk)，深度神经网络算法，矩阵分解算法，LINE算法等。然而，这些算法都是针对同质图的。

异质图嵌入最重要的是解决保留基于元路径的结构信息的问题。而已有的异质图嵌入算法都没有采用注意力机制。

3 预备(Preliminary)

异质图是一种特殊种类的数据结构，既包含了多种类型的节点，又包含了多种类型的边。

3.1 异质图(Heterogeneous Graph)

给定一个异质图(G=(V,E))，其中(V)为节点集，(E)为边集。此外，异质图还包括一个节点映射函数(phi:V o A) 和一个边映射函数(psi:E o R)。其中(A)和(R)分别代表着一些预先定义的节点类型和边类型，且(|A|+|R| > 2)。

3.2 基于元路径的邻域节点集(Meta-path based Neighbors)

给定一个节点i和一个元路径(Phi)，节点i基于元路径的邻域节点集表示为(N_i^Phi)，它表示着与i共处于元路径(N_i^Phi)的所有节点。注意，节点i本身也属于(N_i^Phi)。

4 模型提出(The Proposed Model)

在本章中，我们提出了一个全新的异质图半监督学习算法。我们的模型具有分级注意力结构：节点级注意力( o)语义级注意力。首先，我们对每一条元路径下的邻域节点集学习节点级注意力，然后聚合各个邻域节点集的节点级注意力得到语义级注意力，最后进行节点嵌入。（下表列出了与异质图相关的符号及含义，下图则表示出了HAN的整体框架）