来源：NeurIPS 2019
论文链接
代码链接

摘要

图神经网络（GNNs）在图表示学习中得到了广泛的应用，实现了节点分类和连接预测等任务的最佳性能。然而，大多数现有的GNNs都被设计为在固定（fix）和同质（homogeneous）的图上学习节点表示。当在不确定的图或由各种类型的节点和边组成的异构（heterogeneous）图上学习表示时，这些限制尤其成问题。本文提出了能够生成新的图结构的图变换网络(Graph Transformer Networks, GTNs)，它涉及在原始图上识别未连接节点之间的有用连接，同时以端到端方式学习新图上的有效节点表示。图变换层是GTNs的核心层，学习边类型和复合关系的软选择，以产生有用的多跳连接，即所谓的元路径。我们的实验表明，GTNs基于数据和任务，在没有领域知识（domain knowledge）的情况下学习新的图结构，并通过在新图上的卷积产生强大的节点表示。在没有域特定的图预处理的情况下，GTNs在所有三个benchmark节点分类任务中实现了对比需要领域知识的预定义的元路径的现有技术方法的最佳性能。

背景

近年来，图神经网络被广泛应用于图的分类，连接预测和节点分类中。GNNs学到的表示法已被证明在各种图数据集中取得了最先进的表现，例如社交网络，引文网络，大脑的功能结构，推荐系统。GNNs利用底层图结构直接对图进行卷积，将节点特征传递给邻域，或使用给定图的傅里叶基（即Laplacian算子的特征函数）在谱域中进行卷积。

然而，大多数GNN的一个限制是它们假设在固定和同质图的情况下进行GNNs操作。由于上面讨论的图卷积是由固定的图结构来确定的，所以存在丢失/谬误连接的噪声图导致与图上的错误邻居的无效卷积。此外，在一些应用中，构造用于操作GNN的图不是微不足道的。例如，引用网络具有多种类型的节点(例作者、论文、会议)和由它们之间的关系(如作者-论文、论文-会议)定义的边，它被称为异构图。普通的方法是忽略节点/边类型，并将其视为同质图（具有一种类型的节点和边的标准图）。显然，这不是最佳的方案，因为模型不能利用类型信息。最近的方法采用的补救措施是手动设计与异质边缘连接的路径，并将异构图转化为由meta-path定义的同构图。然后，传统的GNN可以对变换的同构图进行运算。这是一种两阶段的方法，每个问题都需要手工构建元路径。这些元路径的选择对下游分析的准确性有很大的影响。

在此，我们开发了图变换网络（GTN），该网络学习将异构输入图转换为每个任务有用的元路径图，并以端到端方式学习图上的节点表示。GTNs可以被看作是空间变换网络的图模拟，它明确地学习输入图像或特征的空间变换。将异构图转换为元路径定义的新图结构的主要挑战是元路径可能具有任意长度和边类型。例如，引用网络中的作者分类可能受益于元路径，即作者-论文-作者(APA)或作者-论文-会议-作者(APCPA)。此外，引用网络是有向图，相对来说只有较少的图神经网络可以操作。为了应对这些挑战，我们需要一个模型，该模型基于与异构图中软选择的边类型相连接的复合关系生成新的图结构，并通过关于给定问题的学习图形结构上的卷积来学习节点表示。

我们的贡献如下：(1)提出了一种新的图变换网络，以学习一种新的图结构，该结构包括识别有用的元路径和多跳连接来学习图上的有效节点表示。(2)图的生成是可解释的，模型能够为预测提供有效元路径的洞察力。(3)我们证明了图变换网络学习的节点表示的有效性，从而获得了最佳的性能，而现有的方法在异构图的所有三种基准节点分类中都使用了领域知识。

模型

我们的图变换网络的目标是生成新的图结构，同时在学习到的图上学习节点表示。与大多数假设图是给定的CNNs不同的是，GTNS使用多个候选邻接矩阵寻找新的图结构，以执行更有效的图卷积，并学习更强大的节点表示。学习新的图结构涉及识别有用的元路径，它们是与异质边和多跳连接的路径。

图表示为 $G = (V, E)$ ， $V$ 是节点的集合， $E$ 是边的集合。
$Tv\mathcal{T}^v$ 和 $Te\mathcal{T}^e$ 分别表示节点的种类集合和边的种类集合。
异质图表示为邻接矩阵的集合 $A_k)_{k=1}^K$ ，其中 $K=∣Te∣K=|\mathcal{T}^e|$ ，它也可以写成张量 $A∈RN×N×K\mathbb{A}\in R^{N\times N\times K}$ 。

元路径的生成

以前的工作需要手动定义元路径，并在元路径图上执行图神经网络。相反，我们的图转换网络(GTNs)学习给定数据和任务的元路径，并在所学习的元路径图上操作图卷积。这使我们有机会找到更有用的元路径，并使用多个元路径图生成几乎不同的图卷积。图1中图转换(GT)层中的新的元路径图生成有两个部分。首先，GT层从候选邻接矩阵A中柔和地选择两个图结构Q1和Q2。第二，它通过两个关系的组成来学习新的图结构(即两个邻接矩阵的矩阵乘法，Q1Q2)。
具体来说，

图1即表示GT(Graph Transformer) Layer，它先从tensor $A\mathbb{A}$ (每一片就是一种edge type)中用权重选择adjacency matrices(即edge type)。权重选择的方式也可以理解成卷积，卷积后的两个matrices分别是两个图结构，表示为 $Q_1$ 和 $Q_2$ 。
选择matrices的两个卷积核是用softmax计算得出的(比如图中例子，一个卷积核说取最前面的matrices，一个卷积核说取最后面那个matrices)，但实际上是带有权重分配的。
然后再将两个matrices组成新的图结构(即两个邻接矩阵的矩阵乘法， $Q_1Q_2$ )。

用数学形式可以表示为：

选择的 $Q$ 可以表示为： $Q=F(A;Wϕ)=ϕ(A;softmax(Wϕ))Q=F(\mathbb{A};W_{\phi})=\phi(\mathbb{A};softmax(W_{\phi}))$ 即得出的 $Q$ 是将 $A\mathbb{A}$ 和权重参数 $WϕW_{\phi}$ 送去卷积层卷积得到的。
每一个 $Q_i$ 可以表示成： $∑tl∈Teαtl(l)Atl\sum_{t_l\in\mathcal{T}^e}\alpha_{t_l}^{(l)}A_{t_l}$ 其中 $Te\mathcal{T}^e$ 是边的类型集合， $αtl(l)\alpha_{t_l}^{(l)}$ 是边的第 $l$ 种类型 $t_l$ 在第 $l$ 层的权重。
以图中为例： $Te\mathcal{T}^e$ 有4个 ${t_1,t_2,t_3,t_4\}$ ，即对应4层matrices： ${A_1,A_2,A_3,A_4\}$ ， $Wϕ={α1,α2,α3,α4}W_{\phi}=\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\}$
如果不是分两个 $Q$ ，而是多个，则最后得到的结果新A可表示为： $AP=(∑t1∈Teαt1(1)At1)(∑t2∈Teαt2(2)At2)⋯(∑tl∈Teαtl(l)Atl)A_P=(\sum_{t_1\in\mathcal{T}^e}\alpha_{t_1}^{(1)}A_{t_1})(\sum_{t_2\in\mathcal{T}^e}\alpha_{t_2}^{(2)}A_{t_2})\cdots(\sum_{t_l\in\mathcal{T}^e}\alpha_{t_l}^{(l)}A_{t_l})$

多通道

为了同时考虑多种类型的元路径，图1中1×1卷积的输出通道设置为 $C$ 。然后，GT层产生一组元路径，中间邻接矩阵Q1和Q2成为邻接张量 $Q1\mathbb{Q}_1$ 和 $Q2∈RN×N×C\mathbb{Q}_2\in R^{N\times N\times C}$ ，如图2所示。通过多个不同的图结构学习不同的节点表示是有益的。在 $l$ 个GT层堆栈之后，将GCN应用于元路径张量 $Al∈RN×N×C\mathbb{A}^l\in R^{N\times N\times C}$ 的每个通道，并将多个节点表示连接起来。

其中 $∣ ∣$ 是拼接操作。 $C$ 表示通道数量。 $A~il=Ail+I\tilde{A}_i^l=A_i^l+I$ 表示张量 $A(l)\mathbb{A}^{(l)}$ 的第 $l$ 个通道。 $D~i\tilde{D}_i$ 是 $A~i\tilde\mathbb{A}_i$ 的度矩阵， $W∈Rd×dW\in R^{d\times d}$ 是训练权重矩阵， $X∈RN×dX\in R^{N\times d}$ 表示特征矩阵。

实验

在这一节中，我们评估了我们的方法相对于各种最新的节点分类模型的优势。我们进行实验和分析，回答以下研究问题：Q1：GTN生成的新图结构对学习节点表示是否有效？Q2：GTN能否根据数据集自适应地产生可变长度的元路径？Q3：如何从GTNs生成的邻接矩阵来解释每个元路径的重要性？

从新的图结构中学习的表示的有效性。表2显示了GTN和其他节点分类基线的性能。通过对实验结果的分析，我们将回答问题Q1和Q2。我们注意到，我们的GTN针对所有网络嵌入方法和图神经网络方法，实现了所有数据集的最高性能。

通过GTNs与预定义的元路径和top-ranked元路径进行比较。我们的模型找到了重要的元路径，这些元路径与目标节点之间的预定义的元路径一致（一种具有节点分类标签的节点的类型）。此外，GTNs还发现了所有类型的节点之间的新的相关元路径。

如表3所示，在有类标签可预测的目标节点之间，按域知识预定义的元路径也始终在GTNs中排在首位。这表明GTN能够学习元路径对于任务的重要性。更有趣的是，GTNs发现了重要的元路径，它们不在预定义的元路径集中。例如，在DBLP数据集中，GTN将APC列为最重要的元路径，它不包括在预定义的元路径集中。作者的研究领域(标记为预测)与作者发表文章的地点有关，这是有意义的。我们认为GTNs的可解释性通过元路径上的注意分数为节点分类提供了有用的洞察力。

图3显示了每个图转换层的邻接矩阵(边类型)的注意分数。与DBLP结果相比，恒等矩阵在IMDB中具有更高的注意力得分。正如在上文中所讨论的，GTN能够学习比GT层数更短的元路径，它们与IMDB一样更有效。通过将较高的注意力分数分配给恒等矩阵，GTN试图坚持较短的元路径，即使是在较深的层。这个结果表明GTN能够根据数据集自适应地学习最有效的元路径长度。

结论

我们提出了一种在异构图上学习节点表示的图变换网络。该方法将异构图转化为由任意边类型和任意长度的元路径定义的多个新图，同时通过对学习到的元路径图进行卷积学习节点表示。所学习的图结构使节点表示更加有效，使得在异构图的所有三种基准节点分类任务上，在没有任何预定义的领域知识元路径的情况下，获得了最先进的性能。由于我们的图转换层可以与现有的GNN相结合，我们认为我们的框架为GNN提供了一种新的方法，使其能够自行优化图结构，根据数据和任务操作卷积，而无需任何人工操作。有趣的未来方向包括研究GT层与不同种类的GNNs而非GCNs组合的功效。此外，由于最近出现了一些研究诸如连接预测和图分类的其它网络分析任务研的几个异构图数据集，所以将GTNs应用于其它任务也是令人感兴趣的未来方向。

新人创作打卡挑战赛发博客就能抽奖！定制产品红包拿不停！