【UCLA-微软-WWW2020】异构图Transformer，Heterogeneous Graph Transformer

摘要 近年来，使用结构化数据建模的图神经网络(GNNs)取得了巨大的成功。然而，大多数的GNN都是针对同构图设计的，在同构图中，所有的节点和边都属于同一种类型，使得它们无法表示异构结构。在这篇论文中，我们提出了一种异构图 Transformer(HGT)结构来对web级的异构图进行建模。为了对异构性进行建模，我们设计了节点类型和边类型的相关参数来描述每个边上的异构注意力程度，从而使HGT能够维护不同类型节点和边的特定表示。为了处理动态异构图，我们在HGT中引入了相对时间编码技术，该技术能够捕获具有任意持续时间的动态结构依赖关系。针对网络规模图数据的处理问题，设计了高效、可扩展的小批量图数据采样算法HGSampling。在拥有1.79亿个节点和20亿个边的开放学术图上进行的大量实验表明，所提出的HGT模型在各种下游任务上的性能始终比所有最先进的GNN基线高9-21%。

关键词：图神经网络；异构信息网络；表示学习；图嵌入；图注意力

介绍

异构图通常对复杂的系统进行抽象和建模，其中不同类型的对象以各种方式相互交互。此类系统的一些常见实例包括学术图、Facebook实体图、LinkedIn经济图，以及广泛的物联网网络。例如，图1中的开放学术图(OAG)[28]包含五种类型的节点:论文、作者、机构、场所(期刊、会议或预印本)和字段，以及它们之间不同类型的关系。

在过去的十年中，人们对异构图[17]的挖掘进行了大量的研究。其中一个经典的范例就是定义和使用元路径来对异类结构进行建模，例如PathSim[18]和变元ath2vec[3]。最近，鉴于图神经网络(GNNs)的成功[7,9,22]，[14,23,26,27]尝试采用GNNs来学习异构网络。然而，这些工作面临着几个问题:首先，它们大多涉及到为每种类型的异构图设计元路径，这需要特定的领域知识;其次，它们要么简单地假设不同类型的节点/边共享相同的特征和表示空间，要么为节点类型或单独的边类型保留不同的非共享权值，使它们不足以捕获异类图的属性;三是大多忽略了每一个(异构)图的动态性;最后，它们固有的设计和实现使得它们无法对web规模的异构图进行建模。

以OAG为例:首先，OAG中的节点和边可能具有不同的特征分布，如论文具有文本特征，而机构可能具有来自附属学者的特征，共同作者明显不同于引文链接;OAG一直在不断发展，例如:1)出版物的数量每12年翻一倍[4];2)KDD会议在1990年代更多地与数据库相关，而近年来更多地与机器学习相关;最后，OAG包含数亿个节点和数十亿个关系，使得现有的异构GNN无法扩展来处理它。

针对这些限制和挑战，我们建议研究异构图神经网络，其目标是维护节点和边类型依赖表示、捕获网络动态、避免自定义元路径和可扩展到web级图。在这项工作中，我们提出了异构图 Transformer(HGT)架构来处理所有这些问题。

为了处理图的异构性，我们引入了节点类型和边类型依赖注意力机制。HGT中的相互注意不是对每一个类型边参数化，而是根据其元关系三元组e=(s，t)，即 s为节点类型，s与t之间的e的边类型，t的节点类型。图1展示了异构学术图的元关系。具体来说，我们使用这些元关系来对权重矩阵参数化，以计算每条边上的注意力。因此，允许不同类型的节点和边维护其特定的表示空间。同时，不同类型的连接节点仍然可以交互、传递和聚合消息，而不受其分布差异的限制。由于其架构的性质，HGT可以通过跨层传递消息来整合来自不同类型的高阶邻居的信息，这可以看作是软元路径。也就是说，即使HGT只将其单跳边作为输入，而不需要手动设计元路径，所提出的注意力机制也可以自动、隐式地学习和提取对不同下游任务重要的元路径。

为了处理图数据的动态特性，我们提出了相对时间编码(RTE)策略来增强HGT。我们不打算将输入图分割成不同的时间戳，而是建议将发生在不同时间的所有边作为一个整体进行维护，并设计RTE策略来对任何持续时间长度的结构性时间依赖关系进行建模，甚至包括不可见的和未来的时间戳。通过端到端训练，RTE使HGT能够自动学习异构图的时间依赖性和演化。

为了处理网络规模的图形数据，我们设计了第一个用于小批量GNN训练的异构子图采样算法HGSampling。它的主要思想是样本异构子图中不同类型的节点与类似的比例,由于直接使用现有的(均匀)GNN抽样方法,如GraphSage [7], FastGCN[1],和LADIES[29],结果在高度不平衡的关于节点和边缘的类型。此外，它还被设计成保持采样子图的密度以最小化信息的丢失。通过HGSampling，所有的GNN模型，包括我们提出的HGT，都可以在任意大小的异构图上进行训练和推断。

我们证明了所提出的异构图Transformer在网络规模开放学术图上的有效性和效率，该开放学术图由1.79亿个节点和20亿个边组成，时间跨度从1900年到2019年，这是迄今为止在异构图上进行的规模最大、跨度最长的表示学习。此外，我们还检查领域特定的图表:计算机科学和医学学术图表。实验结果表明，与最先进的GNNs和专用的异构模型相比，在下游任务中HGT可以显著提高9-21%。我们进一步进行了案例研究，表明了所提出的方法确实能够自动捕获不同任务的隐式元路径的重要性。