论文链接：https://arxiv.org/pdf/2002.01680.pdf

代码：https://github.com/cynricfu/MAGNN

摘要：大量现实世界的图或网络本质上是异构的，其中包含了多种类型的节点和连边关系。异构图嵌入是将异构图中丰富的结构和语义信息嵌入到网络节点的低维向量表示中。现有模型通常采用定义多个元路径的方式来捕捉其中的复合关系，并以此来指导邻居节点的选择。然而这些模型要么忽略了节点的内容特征（或属性特征），要么只考虑了元路径两端节点而舍弃了元路径内部节点信息，要么只依赖于单个元路径，从而导致其他元路径信息的丢失。为解决上述问题，我们提出了一个名为MAGNN的模型。该模型主要由三个组件组成：节点内容转换：封装输入节点的属性；元路径内部聚合：聚合元路径内部的语义节点特征；元路径间聚合：聚合多个元路径信息。针对节点分类、节点聚类和链路预测任务，在三个真实数据集上进行了仿真实验，实验结果表明，MAGNN优于最先进的基线方法。

1、Introduction

许多现实世界中的数据集可以自然而然的通过图形结构来进行刻画，其中数据对象及其之间的关联关系可以分别由节点和连边表示。如社交网络、物理系统、交通网络、引文网络、推荐系统、知识图谱等。图因其独特的非欧几里得性质使得其难以被传统机器学习模型建模。对于图中每个节点的邻域节点集合，它们之间没有顺序或大小限制。而大多数统计模型都会假设输入数据位于欧几里得空间，有序且大小固定。因此节点若能通过欧几里得空间中有意义的低维向量进行表示，然后作为其他机器学习模型的输入，这将是意义非凡的。

对于图结构特征，已提出了许多不同的图嵌入技术。LINE利用节点间的一阶和二阶相似度来生成节点嵌入。基于随机游走的方法，如DeepWalk、node2vec、TADW等将随机游走生成的节点序列馈送到skip-gram模型中来学习节点嵌入。随着深度学习等技术的快速发展，人们提出了图神经网络（GNN），它使用专门设计的神经网络层来学习图嵌入。基于频谱的GNN，包括ChebNet和GCN，在整个图的傅里叶域中执行图卷积运算。最近基于空间的GNN，如GraphSAGE、GAT及许多其他变体通过直接在图域中执行图卷积操作来解决模型的可扩展性和泛化能力等问题。越来越多的研究人员开始关注于这一前景广阔的领域。

尽管 GNN 在许多任务上都取得了优异的表现，但大多数基于 GNN 的模型都假设输入的是同构图，即其中只包含一种节点类型和一种边类型。而现实世界中大多数的图是由位于不同特征空间中带有属性的多种类型的节点及连边关系构成。如科研合作网络中，至少包含两种类型的节点：作者和论文。作者属性可能包括从属机构、引文和研究领域。论文属性可能包括关键字、位置、年份等。我们将此类图成为异构信息网络（HIN）或异构图。图结构和节点内容的异质性使得GNN难以将其丰富多样的信息编码到低维向量空间中。

大多数现有异质网络嵌入方法基于元路径思想。元路径是在网络模式上定义的节点类型和边类型的有序序列，它描述了所涉及的节点类型之间的复合关系。如在包含作者、论文和地点的学者网络中，作者-论文-作者 (APA) 和作者-论文-地点-论文-作者 (APVPA) 是描述作者之间两种不同关系的元路径。APA 元路径关联两位共同作者，而 APVPA 元路径关联两位在同一地点发表论文的作者。因此我们可以将元路径视为两个节点之间的高阶邻近度。由于传统的 GNN 对所有节点一视同仁，因此无法对异构图中复杂的结构和语义信息进行建模。

尽管这些基于元路径的嵌入方法在节点分类和链接预测等各种任务上优于传统的网络嵌入方法，但它们仍然至少存在以下不足之一。(1) 该模型没有利用节点内容特征，因此它很少在具有丰富节点内容特征的异构图上表现良好（例如，metapath2vec、ESim、HIN2vec 和 HERec ）。(2) 模型只考虑两个端节点，丢弃了元路径上的所有中间节点，导致信息丢失（例如，HERec 和 HAN）。 (3) 模型在图嵌入中依赖单一元路径。因此该模型需要手动定义元路径，且会丢失来自其他元路径的信息，从而导致性能欠佳（例如，metapath2vec）。

为了解决这些问题，我们提出了一种用于异构图嵌入的新型元路径聚合图神经网络 (MAGNN)。 MAGNN 通过应用节点内容转换、元路径内聚合和元路径间聚合来生成节点嵌入，从而解决了上述所有问题。具体来说，不同类型的节点可能其维度不等，MAGNN首先应用特定于类型的线性变换将异构节点的属性特征投影到同一个潜在的向量空间中。然后使用注意力机制对每个元路径应用元路径内部聚合。在该过程中，每个目标节点从元路径实例所连接的基于元路径邻居节点中提取并组合信息。通过这种方式，MAGNN 从两个相邻节点和它们之间的元路径上下文中捕获异构图的结构和语义信息。在元路径内聚合之后，MAGNN 使用注意力机制进一步进行元路径间聚合，将多个元路径中获得的潜在向量融合到最终节点嵌入中。通过集成多个元路径，我们的模型可以学习异构图中根深蒂固的综合语义。

总而言之，本文的主要贡献如下：

（1）我们提出了一个新的异质图嵌入模型MAGNN；

（2）我们设计了几个候选编码器函数，用于从元路径实例中提取信息，其中包括一个基于复杂空间中的关系旋转思想的编码器函数。

（3）我们在 IMDb 和 DBLP 数据集上进行了节点分类和节点聚类任务，在Last.fm 数据集上进行了链路预测任务。实验结果表明MAGNN模型的表现超越了state-of-the-art baselines。

2、Preliminary

在本小节中，我们给出了与异构图相关的一些重要术语的形式化定义。图 1 提供了图解说明。此外，表 1 总结了本文中常用的符号，以供快速参考。

定义2.1 异构图。异构图被定义为 $G=(V,E)$ ，节点类型映射函数： $\phi ：V\rightarrow \hat{A}$ ，边类型映射函数： $\psi =E\rightarrow \hat {R}$ 。 $\hat{A} 和\hat {R}$ 分别表示预定义的节点类型集合和连边类型集合，并且 $|\hat{A} |+|\hat R|>2$ 。

定义2.2 元路径。元路径P被定义为一个如下形式的路径，可缩写为（ $A_{1} A_{2}…A_{l+1}$ ），

元路径表示形式

它描述了从节点类型 $A_{1}到A_{l+1}$ 的复合关系 $R=R_{1}\circ R_{2}\circ …\circ R_{l}$ 。其中 $\circ$ 表示关联关系的复合操作。

定义2.3 元路径实例。给定异构图中的一个元路径P，元路径实例 $p\in P$ 被定义为图中遵循P的定义模式的节点序列。

定义2.4 基于元路径的邻域。给定异构图中的一个元路径P，节点 $\upsilon$ 的基于元路径的邻域 $N_{\upsilon }^P$ 被定义为通过元路径P的元路径实例与节点 $\upsilon$ 所连接的节点集合。由两个不同的元路径实例连接的邻居被视为 $N_{\upsilon }^P$ 中的两个不同节点。注意若元路径P对称，则 $N_{\upsilon }^P$ 中也包含节点 $\upsilon$ 本身。

图示说明

例如考虑图1中的元路径UATA，艺术家 Queen 是用户 Bob 的基于元路径的邻居。这两个节点通过元路径实例 Bob-Beatles-Rock-Queen 连接。此外，我们可以将 Beatles 和 Rock 称为此元路径实例的中间节点。

定义2.5 基于元路径的图。给定异构图G中的元路径P，基于元路径的图 $G^P$ 由原始图G中所有的基于元路径P的邻居节点对组成。若P对称，则 $G^P$ 为同构图。如图1(d)所示。(去掉了元路径实例的中间节点，只保留了元路径实例两端的节点，并在两节点间建立连边)

定义2.6 异构图嵌入。给定异构图 $G=(V,E)$ , $X_{A_{i}} \in R^{|V_{A_i}|\times d_{A_i}}$ 为类型为 $A_{i}\in \hat{A}$ 的节点的属性矩阵，异构图嵌入的主要任务是为任意节点 $\upsilon \in V$ 学习一个 $d$ 维节点表示 $h_{\upsilon }\in R^{d}$ ，其中 $d\ll |V|$ ，该表示能够捕捉异构图G中涉及的丰富的结构和语义信息。

3、Related Work

3.1 Graph Neural Networks

GNN的目标是为每一个节点 $\upsilon$ 学习一个可用于如节点分类、节点聚类、链路预测等下游任务的低维向量表示 $h_{\upsilon }$ 。这背后的基本原理是每个节点都能通过其自身特征和其邻域来定义。遵循这一想法，并基于图信号处理，基于频谱的GNN首先被提出，以在图的傅里叶域中执行图卷积运算。ChebNet利用Chebyshev 多项式在图傅里叶域中过滤图信号（节点特征）。另一个具有影响力的模型是 GCN，它通过约束和简化 ChebNet 的参数来缓解过拟合问题并提高性能。然而，基于频谱的 GNN 的可扩展性和泛化能力较差，因为它们需要整个图作为每一层的输入，并且它们所学习的滤波器依赖于图拉普拉斯算子的特征基，这与特定的图结构密切相关。

基于空间的 GNN 被提出以解决上述两个限制。这种 GNN 通过聚合来自每个节点的邻居特征信息直接在图域中定义卷积，从而模仿卷积神经网络对图像数据的卷积操作。GraphSAGE是开创性的基于空间的 GNN 框架，它建立在聚合函数的一般概念之上，用于有效生成节点嵌入。聚合器函数对目标节点的局部邻域进行采样、提取和转换，从而提升在看不到的节点或图上的并行训练及泛化能力。基于这个想法，已经提出了许多其他基于空间的 GNN 变体。受 Transformer 的启发，GAT将注意力机制整合到聚合器函数中，以从目标节点的角度考虑每个邻居信息的相对重要性。GGNN通过将聚合的邻域信息作为当前时间步的 GRU 的输入，将门控循环单元 (GRU) 添加到聚合函数。GaAN将 GRU 与门控多头注意力机制相结合，用于处理时空图。STAR-GCN堆叠多个 GCN 编码器-解码器以提高预测评估性能。

3.2 Heterogeneous Graph Embedding

异构图嵌入的目标在于将异构图中的节点映射到一个低维向量空间。许多研究成果已经解决了这个具有挑战性的主题。例如metapath2vec通过单个元路径引导的随机游走生成节点序列，然后送入到skip-gram模型来生成节点嵌入。给定用户定义好的元路径，ESim通过从采样的正负元路径实例中来学习节点的嵌入。HIN2vec执行多个预测训练任务来学习异构图的节点和元路径的表示。给定元路径，HERec将异构图转换为基于元路径的邻居的同构图，并应用DeepWalk模型来学习目标类型的节点嵌入。与HERec类似，HAN以类似方式将异构图转换为多个基于元路径的同构图，但使用图注意力网络架构图来聚合来自邻居节点的信息，并利用注意力机制来组合各种元路径。另一个模型PME通过将节点嵌入投影到相应的关系空间并优化投影节点之间的邻近度来学习节点嵌入。

然而所有上述介绍的异构图嵌入方法都有一定的局限性：它们要么忽视了节点的内容特征，要么只考虑了元路径两端节点而舍弃了元路径内部节点信息，要么只依赖于单个元路径，从而导致其他元路径信息的丢失。尽管它们可能改进了一些异构图数据集的同构图嵌入方法的性能，但通过更全面地利用异构图中嵌入的信息，仍有改进的空间。

4、Methodology

本小节中，我们介绍了新的异构图嵌入模型MAGNN。该模型由三个部分组成：节点内容转换；元路径内部聚合；元路径间聚合。图2说明了单个节点的嵌入过程，整个前向传播算法如算法1所示。

4.1 Node Content Transformation

对于与节点属性相关的异构图，不同的节点类型可能具有不相等的特征向量维度。即使它们恰好是相同的维度，它们也可能位于不同的特征空间中。例如，即使 $n_{1}=n_{2}$ ，文本的 $n_{1}$ 维词袋向量和图像的 $n_{2}$ 维强度直方图向量也不能直接一起操作。当我们在一个统一的框架中处理不同维度的特征向量时，它们是很麻烦的。因此我们首先需要将不同类型的节点特征投影到同一个潜在向量空间中。

因此在将节点向量馈入MAGNN模型之前，我们使用一个基于特定类型的线性转换将每个类型的节点特征向量投影到一个相同的潜在特征空间。对于一个类型为 $A\in \hat{A}$ 的节点 $\upsilon \in V_{A}$ ，则有：

其中 $x_{\upsilon }\in R^{d_{A}}$ 为初始特征向量， $h_{\upsilon }^{/}\in R^{d^/}$ 为节点 $\upsilon$ 映射后的隐层向量。 $W_{A} \in R^{d^/\times d_{A}}$ 为类型为A的节点的参数化权重矩阵。

节点内容转换解决了源自节点内容特征的图的异质性。应用此操作后，所有节点的投影特征共享相同的维度，这有助于下一个模型组件的聚合过程。

4.2 Intra-metapath Aggregation

给定元路径P，元路径内聚合层通过对 P 的元路径实例进行编码来学习嵌入在目标节点、基于元路径的邻居节点以及它们之间的上下文中的结构和语义信息。令 $P(v,u)$ 为连接目标节点 $v$ 及其基于元路径邻居节点 $u \in N_{v}^P$ 的元路径实例，我们进一步定义 $P(v,u)$ 的中间节点为:

元路径内聚合采用特殊的元路径实例编码器将沿元路径实例的所有节点特征转换为单个向量：

其中 $h_{P(v,u)}\in R^{d^/}$ 的维度为 $d^{/}$ 。为简单起见，这里尽管可能有多个实例连接两个节点，但我们仍使用 $P(v,u)$ 表示单个实例。第 4.4 节介绍了合格元路径实例编码器的几种选择。

将元路径实例编码到向量表示中之后，我们采用一个图注意力层对与目标节点 $v$ 相关的 $P$ 的元路径实例进行加权求和。其关键思想是不同的元路径实例对目标节点的表示具有不同的影响力。我们可以对每个元路径实例学习一个归一化的重要性权重 $\alpha _{vu}^P$ ，再将所有实例进行加权求和来对此进行建模：

此处 $a_P \in R^{2d^{/}}$ 为元路径P的参数化注意力向量，||表示向量拼接操作。 $e_{vu}^P$ 表示到节点 $v$ 的元路径实例 $P(v,u)$ 的重要性，之后使用softmax函数对所有 $u \in N_{v}^{P}$ 进行归一化操作。当所有 $u \in N_{v}^{P}$ 获得归一化后的重要性权重系数（或注意力系数） $\alpha _{vu}^P$ ，它们被用于计算关于节点 $v$ 的元路径实例的表示的加权组合。最后经过一个激活函数 $\sigma (\cdot )$ 输出。

这种注意力机制也可以扩展到多头，这有助于稳定学习过程并减少图的异质性引入的高方差。也就是说，我们执行 K 个独立的注意力机制，然后将它们的输出拼接起来，得到以下公式：

其中 $[\alpha _{vu}^P]_k$ 为节点 $v$ 在第 $k$ 个注意力头上的元路径实例 $P(v,u)$ 的归一化后的重要性。

综上所述，给定投影特征向量 $h_{u}^{/}\in R^{d^{/}}， \forall u\in V$ 和起始节点类型为 $A\in \hat{A}$ 的元路径集合 $\hat P_{A}=\left\{ P_1,P_2,…,P_M \right\}$ ，MAGNN模型的元路径内部聚合即为目标节点 $v\in V_{A}$ 生成 $M$ 个针对特定元路径的向量表示，记为 $\left\{ h_{v}^{P_1},h_{v}^{P_2},…,h_{v}^{P_M} \right\}$ 。每个 $h_{v}^{P_i}\in R^{d^{/}}$ (假设 $K=1$ )都可以被解释为一个关于节点 $v$ 的元路径 $P_{i}$ 的元路径实例的概要，展示了节点 $v$ 中隐含的一种语义信息。

4.3 Inter-metapath Aggregation

聚合了每个元路径中的节点及连边数据之后，我们需要使用元路径间聚合层来组合所有元路径揭示的语义信息。对于一个类型为A的节点 $v\in V_{A}$ ，生成了 $|V_A|$ 组隐层向量： $\left\{ h_{v}^{P_1},h_{v}^{P_2},…,h_{v}^{P_M} \right\}$ ，其中M为A类型节点的元路径数量。一种直接的元路径间聚合方法是采用这些节点向量的元素平均值。我们通过利用注意力机制为不同的元路径分配不同的权重来扩展这种方法。此操作是合理的，因为元路径在异构图中并不同等重要。

首先，针对各元路径 $P_i\in \hat P_A$ ，对所有类型为A的节点在特定元路径下的节点向量进行转换，然后取其均值：

其中 $M_A \in R^{d_m\times d^{/}}$ 和 $b_A \in R^{d_m}$ 为可学习的参数。

然后我们使用注意力机制融合特定元路径下的节点 $v$ 的特征向量：

其中 $q_A \in R^{d_m}$ 为针对A类型节点的参数化注意力向量。 $\beta _{P_i}$ 可以被解释为元路径 $P_i$ 对A类型节点的相对重要性。当计算出每个元路径 $P_i\in \hat P_A$ 的 $\beta _{P_i}$ ，我们就可以使用这个注意力系数对节点 $v$ 的所有针对特定元路径的向量进行加权求和。

最后，MAGNN 使用带有非线性函数的附加线性变换将节点嵌入投影到具有所需输出维度的向量空间：

其中 $\sigma (\cdot )$ 为激活函数， $W_o \in R^{d_o\times d^{/}}$ 为权重矩阵。该映射针对具体任务有所不同，可以看成是用于节点分类的线性分类器，也可以视为带有节点间相似性度量的空间投影，以便用于链路预测任务。

4.4 Metapath Instance Encoder

为了编码4.2节中的每个元路径实例，我们检验了三个备选编码函数：

（1）Mean encoder：该函数采用元路径实例 $P(v,u)$ 的节点向量的元素均值：

（2）Linear encoder：该函数是对均值编码器的扩展，它附加了一个线性变换：

（3）Relational rotation encoder：我们还研究了基于复杂空间中关系旋转的元路径实例编码器，这一操作是 RotatE提出用于知识图嵌入的方法。上面介绍的Mean encoder和Linear encoder将元路径实例本质上视为一个集合，因此忽略了嵌入在元路径的顺序结构中的信息。关系旋转提供了一种对此类知识进行建模的方法。给定 $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$ 的关系向量，关系旋转编码器公式为：