一、HGT [2020]

《Heterogeneous Graph Transformer》

1. 异质图通常用于对复杂系统进行抽象和建模，图中包含不同类型的对象、不同类型的链接。如，Open Academic Graph:OAG 数据中包含五种类型的节点：论文（Paper）、作者（Author）、机构（Institution）、会议（Venue）、领域（Field），以及它们之间各种不同类型的关系，如下图所示。

   

   关于异质图挖掘已有大量的研究。一种经典的范式（paradigm）是定义和使用元路径（metapath ）来建模异质图，例如 PathSim 和 metapath2vec。最近，鉴于图神经网络（ GNN）的成功，有几种方法尝试采用 GNN 来学习异质图。然而，这类工作面临以下几个问题：

   • 首先，大多数针对异质图的metapath设计需要特定的领域知识。

   • 其次，它们要么简单地假设不同类型的节点/边共享相同的特征和representation space，要么假设不同类型的节点/边都有各自的特征和representation space。这两种极端使得它们都不足以捕获异质图的属性。

   • 再次，大多数现有方法忽略了异质图的动态特性。

   • 最后，它们固有的设计和实现使其无法建模 web-scale 异质图。

   以 OAG 为例：

   • 首先，OAG 中的节点和边可能有不同的特征分布，例如 paper 节点有文本特征，而 institution 节点可能有附属学者的特征，作者之间的co-authorship 关系明显不同于论文之间的 citation 关系。

   • 其次，OAG 一直在不断演变，例如，出版物的数量每隔 12 年翻一番，KDD 会议在 1990 年更多地与数据库相关而近年来更多地与机器学习相关。

   • 最后，OAG 包含数亿个节点和数十亿个关系，这使得现有的异质 GNN 无法扩展以处理它。

   为了解决上述问题，论文 《Heterogeneous Graph Transformer》 提出了建模 web-scale 异质图的 Heterogeneous Graph Transformer:HGT 架构，目标是：维护 node-type dependent representation 和 edge-type dependent representation 、捕获网络动态、避免自定义metapath、以及能够扩展到 web-scale 的图。

   • 为了处理图的异质性，HGT 引入了节点类型依赖的 attention 机制 node-type dependent attention、边类型依赖的 attention 机制（edge-type dependent attention）。HGT 并未参数化每种类型的边，而是通过每条边 $e=(s,t)$$e=(s,t)$ 的关系三元组来分解边 $e$$e$ ，从而定义 HGT 的异质互注意力（heterogeneous mutual attention）。这个关系三元组为<node type of s, edge type of e between s&t , node type of t >。

     HGT 使用这些元关系来对权重矩阵进行参数化，从而计算每条边上的注意力。这样允许不同类型的节点、边保持其特有的representation space，同时不同类型的、相连的节点仍然可以交互、传递、聚合消息，不受它们类型不同的影响。

     由于 HGT 架构的性质，HGT 可以通过跨层信息传递来聚合来自不同类型高阶邻居的信息，这些信息可以被视为 soft metapath 。换句话讲，HGT 仅使用其 one-hop 边作为输入，无需手动设计 metapath，最终提出的注意力机制也可以自动隐式地学习和提取针对不同下游任务很重要的 metapath 。

   • 为解决动态图的问题，HGT 提出了相对时间编码（ relative temporal encoding:RTE）策略来增强 HGT。

     HGT 建议不要把输入图划分为不同的时间戳，而是建议将在不同时间发生的所有边作为一个整体来维护，并设计 RTE 策略来建模任意时间区间（甚至是未知的和未来的）的时间依赖性（temporal dependency）。通过端到端的训练，RTE 使 HGT 能够自动学习异质图的时间依赖和演变。

   • 为处理 web-scale 规模的图数据，HGT设计了用于 mini-batch 图训练的首个异质子图采样算法（HGSampling）。其主要思想是对异质子图进行采样，在采样到的子图中不同类型的节点具有相似的比例。因为如果直接使用现有的同质图采样算法，如 GraphSage/FastGCN/LADIES，会导致采样子图的节点类型、边类型高度不平衡。此外，HGSampling 还被设计为使得采样子图保持稠密，从而最大程度地减少信息丢失。

     通过 HGSampling，所有的 GNN 模型包括论文提出的 HGT，都可以在任意大小的异质图上进行训练和推断。

   论文在 web-scale 的 OAG 数据集上实验了 HGT 的有效性和效率，该数据集由 1.79 亿个节点、20 亿条边组成，时间跨度 1900 ~ 2019 年，是迄今为止规模最大、时间跨度最长的异质图数据集。

   实验结果表明：和SOTA 的 GNN 以及异质图模型相比，HGT 可以显著改善各种下游任务，效果提高 9% ~ 21% 。进一步研究表明，HGT 确实能够自动捕获隐式 metapath 针对不同任务的重要性。

1.1 基础知识和相关工作

1.1.1 异质图挖掘

1. 异质图定义：定义异质图 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R})$$\mathcal G = (\mathcal V, \mathcal E, \mathcal A, \mathcal R)$ ，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V =\{v_1,\cdots,v_n\}$ 为节点集合， $\mathcal{E}$$\mathcal E$ 为边集合，$\mathcal{A}$$\mathcal A$ 为节点类型集合，$\mathcal{R}$$\mathcal R$ 为边类型集合。每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 关联一个节点类型 $\tau (v)\in \mathcal{A}$$\tau(v)\in \mathcal A$ ，每条边 $e\in \mathcal{E}$$e\in \mathcal E$ 关联一个边类型 $\varphi (e)\in \mathcal{R}$$\phi(e)\in \mathcal R$ 。

2. 元关系（meta relation）定义：对于每条边 $e=(s,t)$$e=(s,t)$ ，定义它的元关系（meta relation）为三元组 $<\tau (s),\varphi (e),\tau (t)>$$<\tau(s), \phi(e), \tau(t)>$ 。 定义 $\varphi (e{)}^{-1}$$\phi(e)^{-1}$ 为关系 $\varphi (e)$$\phi(e)$ 的逆关系（inverse relation）。经典的metapath 范式被定义为这种元关系的序列。

   注意：为更好地建模真实世界的异质网络，我们假设不同类型的节点之间可能存在多种类型的关系。如 OAG 中，通过考虑作者顺序（如“第一作者”、“第二作者”等），作者类型节点和论文类型节点之间存在不同类型的关系。

3. 动态异质图：为建模真实世界异质图的动态特性，我们为每条边 $e(s,t)$$e(s,t)$ 分配一个时间戳 $T$$T$ ，它表示在时刻 $T$$T$ 节点 $s$$s$ 和节点 $t$$t$ 产生链接。对于节点 $s$$s$ 的首次出现，我们也会给节点 $s$$s$ 分配一个时间戳 $T$$T$ 。

   • 我们假设边的时间戳是不变的，表示边的创建时间。例如当一篇论文在时刻 $T$$T$ 发表在会议上时，$T$$T$ 被分配给论文节点和会议节点之间的边。

   • 我们假设节点可以有多个时间戳。例如，会议节点 WWW 可以分配任何时间戳。WWW@1994 意味着我们正在考虑第一版 WWW，它更多地关注互联网协议和 web 基础设施；而 WWW@2020 意味着即将到来的 WWW，其研究主题将扩展到社交分析、普适计算（ubiquitous computing）、搜索和信息检索、隐私等等。

   在挖掘异质图方面已经有了重要的研究方向，例如节点分类、节点聚类、节点排序、以及 node representation learning ，然而异质图的动态视角尚未得到广泛的探索和研究。

1.1.2 GNN

1. GNN 可以视为基于输入图结构的消息传递，它通过聚合局部邻域信息来获得节点的 representation。

   假设节点 $v$$v$ 在 GNN 第 $l$$l$ 层的 representation 为 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ ，则 GNN 的 node representation 更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}\leftarrow {\text{Agg}}_{\mathrm{\forall }u\in {\mathcal{N}}_v}\left(\left\{\text{Extract}({\overrightarrow{\mathbf{h}}}_u^{(l-1)};{\overrightarrow{\mathbf{h}}}_v^{(l-1)},e(u,v))\right\}\right)$$

   其中：${\mathcal{N}}_v$$\mathcal N_v$ 为节点 $v$$v$ 的邻域， $e(u,v)$$e(u,v)$ 为节点 $u$$u$ 到节点 $v$$v$ 的边。

   GNN 有两个基本的算子：

   • Extract(.) 算子：邻域信息抽取器（extractor）。它使用 target 节点 $v$$v$ 的 representation ${\overrightarrow{\mathbf{h}}}_v^{(l-1)}$$\mathbf{\vec h}_v^{(l-1)}$ 以及两个节点之间的边 $e(u,v)$$e(u,v)$ 作为query，并从 source 节点 $u$$u$ 的 representation ${\overrightarrow{\mathbf{h}}}_u^{(l-1)}$$\mathbf{\vec h}_u^{(l-1)}$ 中抽取有用的信息。

   • Agg(.) 算子：邻域信息聚合器（aggregator）。它用于聚合target 节点 $v$$v$ 的邻域信息。通常采用 mean, sum, max 等函数作为聚合函数，也可以设计更复杂的聚合函数。

   此外，还有很多将注意力机制集成到 GNN 的方法。通常，基于注意力的模型通过估计每个 source 节点的重要性来实现 Extract(.) 算子，并在此基础上应用加权聚合。

2. 在上述 GNN 通用框架之后，人们已经提出了各种GNN 架构（同质的）：

   • 《Semi-Supervised Classification with Graph Convolutional Networks》 提出了图卷积网络（graph convolutional network: GCN），它对图中每个节点的一阶邻域进行均值池化，然后进行线性投影和非线性激活操作。

   • 《Inductive Representation Learning on Large Graphs》 提出了 GraphSAGE，将 GCN 的聚合操作从均值池化推广到 sum 池化、最大池化、以及 RNN 。

   • 《Graph Attention Networks》 通过将注意力机制引入 GNN 从而提出了 graph attention network: GAT。这种注意力机制允许 GAT 为同一个邻域内的不同节点分配不同的重要性。

1.1.3 异质 GNN

1. 最近，一些工作试图扩展 GNN 从而建模异质图。

   • 《Modeling Relational Data with Graph Convolutional Networks》 提出了relational graph convolutional network: RGCN 来建模知识图谱。RGCN 为每种类型的边保留不同的线性投影权重。

   • 《Heterogeneous Graph Neural Network》 提出了 heterogeneous graph neural network: HetGNN ，它针对不同的节点类型采用不同的 RNN 来融合多模态特征。

   • 《Heterogeneous Graph Attention Network》 基于注意力机制为不同的 metapath-based 边保留不同的权重，同时对不同的 metapath 也保留不同的权重。

   尽管实验上看这些方法都比普通的 GCN 或 GAT 要好，但是它们对不同类型的节点或不同类型的边采用不同的权重矩阵，从而没有充分利用异质图的特性。因为不同类型的节点/边的数量可能差异很大，对于出现次数不多的边，很难准确地学到合适的 relation-specific 权重。

   为解决这个问题，我们提出了参数共享从而实现更好的泛化，这类似于推荐系统中的 FM 思想。具体而言，给定一条边 $e=(s,t)$$e=(s,t)$ ，其元关系 （meta relation）为 $<\tau (s),\varphi (e),\tau (t)>$$<\tau(s),\phi(e),\tau(t)>$ 。如果我们使用三个矩阵来建模对应的三个元素 $\tau (s),\varphi (e),\tau (t)$$\tau(s),\phi(e),\tau(t)$ ，则大多数边的权重可以共享。

   例如，在 “第一作者”关系 和 “第二作者”关系中，它们的源节点类型都是作者、目标节点类型都是论文。换句话讲，从一种关系中学到的有关作者和论文的知识可以迅速地迁移并适应于另一种关系。因此，我们将该思想和功能强大的、类似于 Transformer 注意力体系结构相结合，这就是 Heterogeneous Graph Transformer: HGT 。

2. 综上所述，HGT 和现有异质图建模方法的主要区别在于：

   • 我们并没有试图对单独的节点类型或单独的边类型建模，而是使用元关系 $<\tau (s),\varphi (e),\tau (t)>$$<\tau(s),\phi(e),\tau(t)>$ 来分解 边 $e$$e$ ，使得 HGT 使用相同的甚至更少的参数来同时捕获不同模型之间的通用模式（common pattern）以及特定模式（specific pattern）。

   • 与大多数现有的metapath-based 方法不同，我们依赖于神经网络体系结构本身来融合高阶异质邻域信息，从而自动学习隐式的metapath的重要性。

   • 以前的大多数工作都未考虑图（异质的）的动态特性，而我们提出了相对时间编码 RTE 技术，从而在有限的计算资源内融合了时间信息。

   • 现有的异质 GNN 都不是为了 web-scale 图数据而设计的，也没有在 web-scale 图上进行实验。我们提出了为 web-scale 的图训练设计的 mini-batch 异质子图采样算法，可以在十亿规模的 Open Academic Graph 上进行实验。

1.2 模型

1. HGT 的核心思想是：使用元关系来参数化权重矩阵，从而实现异质互注意力 （heterogeneous mutual attention）、消息传递（ message passing）、传播（propagation）。另外，为进一步融合网络的动态性，我们在模型中引入相对时间编码机制。

   下图给出了 HGT 的总体架构。给定一个采样的异质子图（sampled heterogeneous sub-graph），HGT 提取所有相连的节点 pair 对，其中目标节点 $t$$t$ 是由源节点 $s$$s$ 通过边 $e$$e$ 进行连接。HGT 的目标是聚合来自于源节点的信息，从而获得目标节点 $t$$t$ 的上下文表示 （contextualized representation）。这样的过程可以分解为三个部分：元关系感知的异质互注意力（meta relation-aware heterogeneous mutual attention）、从源节点发出的异质消息传递（heterogeneous message passing from source nodes）、特定于目标的异质消息聚合（target-specific heterogeneous message aggregation）。

   我们将第 $l$$l$ 层 HGT 层的输出记作 ${\mathbf{H}}^{(l)}$$\mathbf H^{(l)}$ ，它也是第 $l+1$$l+1$ 层 HGT 层的输入。通过堆叠 $L$$L$ 个这样的层，我们可以获得整个图的representation 为 ${\mathbf{H}}^{(L)}$$\mathbf H^{(L)}$ ，然后将其用于端到端训练或者下游任务。

   下图中， $t$$t$ 为目标节点， $s_1,s_2$$s_1,s_2$ 为源节点，不同颜色表示不同的节点类型。 HGT 使用边 $e_1=(s_1,t),e_2=(s_2,t)$$e_1=(s_1,t), e_2=(s_2,t)$ 以及它们的元关系 $<\tau (s_1),\varphi (e_1),\tau (t)>,<\tau (s_2),\varphi (e_2),\tau (t)>$$<\tau(s_1), \phi(e_1),\tau(t)>, <\tau(s_2), \phi(e_2),\tau(t)>$ 作为输入，从而学习每个节点的上下文表示 ${\mathbf{H}}^{(L)}$$\mathbf H^{(L)}$ 。

   HGT 遵循 GAT 的 attention 机制，但是 HGT 在计算 query, key, value 时考虑了节点和边的异质性。此外，在计算节点的 representation 时考虑了相对时间编码（类似于相对位置编码）。

   

1.2.1 Heterogeneous Mutual Attention

1. HGT 的第一步是计算源节点 $s$$s$ 和目标节点 $t$$t$ 之间的互注意力。基于注意力机制的常规 GNN 为：

   $${\overrightarrow{\mathbf{h}}}_t^{(l)}\leftarrow {\text{Agg}}_{s\in {\mathcal{N}}_t,(s,t)\in \mathcal{E}}(\text{Attention(s,t)}\times \text{Message}(s))$$

   其中有三个基础算子：

   • Attention 算子：评估每个源节点 $s$$s$ 对于目标节点 $t$$t$ 的重要性。

   • Message 算子：抽取源节点 $s$$s$ 的消息。

   • Agg 算子：利用注意力权重来聚合邻域的消息。

   例如，GAT 采用一种加性机制（additive mechanism）来作为Attention 算子，采用共享的权重矩阵来计算每个节点的消息，采用简单的均值然后接一个非线性激活函数来作为 Agg 算子。即：

   $$\begin{array}{c}\text{Attention}(s,t)={\text{Softmax}}_{s\in {\mathcal{N}}_t}(\overrightarrow{\mathbf{a}}\cdot (\mathbf{W}{\overrightarrow{\mathbf{h}}}_t^{(l-1)}||\mathbf{W}{\overrightarrow{\mathbf{h}}}_s^{(l-1)}))\\ \text{Message}(s)=\mathbf{W}{\overrightarrow{\mathbf{h}}}_s^{(l-1)}\\ \text{Agg}(\cdot )=\sigma (\text{Mean}(\cdot ))\end{array}$$

   其中：

   • $\overrightarrow{\mathbf{a}}$$\mathbf{\vec a}$ 为待学习的注意力向量（attention vector）。

   • $\mathbf{W}$$\mathbf W$ 为待学习的权重矩阵，它是全局共享。

   • $||$$||$ 为向量的拼接；$\sigma (\cdot )$$\sigma(\cdot)$ 为非线性函数； $\text{Mean}(\cdot )$$\text{Mean}(\cdot)$ 为多个向量取均值操作。

2. 尽管 GAT 可以有效地给更重要的节点以更高的注意力，但是它假设节点 $s$$s$ 和 $t$$t$ 具有相同的特征分布，并使用同一个权重矩阵 $\mathbf{W}$$\mathbf W$ 。所谓相同的特征分布指的是：节点具有相同的特征类型，并且特征各维度的取值概率分布是相同的。但是，这种假设对于异质图是不正确的，因为异质图中每种类型的节点都有自己的特征分布。

   有鉴于此，我们设计了异质互注意力机制。给定一个目标节点 $t$$t$ 及其所有邻居 $t\in {\mathcal{N}}_t$$t\in \mathcal N_t$ ，这些邻居可能属于不同的类型，我们基于它们之间的元关系来计算它们的互注意力。

3. 受到 Transformer 体系结构设计的启发，我们将目标节点 $t$$t$ 映射为一个 Query 向量，将源节点 $s$$s$ 映射为 Key 向量，然后计算它们内积作为 attention。但是和 Transformer 的区别在于：常规的 Transformer对所有单词都使用同一组映射矩阵，但是在HGT 中每种元关系都有它们自己的一组映射矩阵。

   为最大程度地共享参数，同时保持不同关系的各自特性，我们将元关系的权重矩阵参数化为源节点投影矩阵、边投影矩阵、目标节点投影矩阵。具体而言，对于 $h$$h$ 个头，边 $e=(s,t)$$e=(s,t)$ 的 attention 为：

   $$\begin{array}{c}\text{Attention}(s,e,t)={\text{Softmax}}_{s\in {\mathcal{N}}_t}(|{|}_{i\in [1,2,\cdots ,h]}{\text{ATT-head}}^i(s,e,t))\\ {\text{ATT-head}}^i(s,e,t)=\left({\left({\overrightarrow{\mathbf{k}}}_s^i\right)}^{\mathrm{\top }}{\mathbf{W}}_{\varphi (e)}^{\text{ATT}}{\overrightarrow{\mathbf{q}}}_t^i\right)\times \frac{{\mu }_{<\tau (s),\varphi (e),\tau (t)>}}{\sqrt{q}}\\ {\overrightarrow{\mathbf{k}}}_s^i={\text{K-Linear}}_{\tau (s)}^i\left({\overrightarrow{\mathbf{h}}}_s^{(l-1)}\right)\\ {\overrightarrow{\mathbf{q}}}_t^i={\text{Q-Linear}}_{\tau (t)}^i\left({\overrightarrow{\mathbf{h}}}_t^{(l-1)}\right)\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{q}}}_t^i$$\mathbf{\vec q}_t^i$ 为第 $i$$i$ 个 attention head 中的 query 向量，它是类型为 $\tau (t)$$\tau(t)$ 的目标节点通过一个线性映射 ${\text{Q-Linear}}_{\tau (t)}^i:{\mathbb{R}}^d\to {\mathbb{R}}^{d/h}$$\text{Q-Linear}_{\tau(t)}^i:\mathbb R^d\rightarrow \mathbb R^{d/h}$ 得到。每种不同类型的目标节点都有各自独立的线性投影函数，从而可以最大程度地建模不同节点类型的差异。

   • ${\overrightarrow{\mathbf{k}}}_s^i$$\mathbf{\vec k}_s^i$ 为第 $i$$i$ 个 attention head 中的 key 向量，它是类型为 $\tau (s)$$\tau(s)$ 的源节点通过一个线性映射 ${\text{Q-Linear}}_{K\tau (s)}^i:{\mathbb{R}}^d\to {\mathbb{R}}^{d/h}$$\text{Q-Linear}_{K\tau(s)}^i :\mathbb R^d\rightarrow \mathbb R^{d/h}$ 得到。每种不同类型的源节点都有各自独立的线性投影函数。

   • ${\text{ATT-head}}^i(s,e,t)$$\text{ATT-head}^i(s,e,t)$ 表示第 $i$$i$ 个 attention head 中，query 向量 ${\overrightarrow{\mathbf{q}}}_t^i$$\mathbf{\vec q}_t^i$ 和 key 向量 ${\overrightarrow{\mathbf{k}}}_s^i$$\mathbf{\vec k}^i_s$ 之间的相似性。

     异质图的一个特点是：在一对节点之间可能存在多种不同类型的边。因此，和常规的 Transformer 将 query 向量和 key 向量直接内积不同，HGT 考虑对每种边类型 $\varphi (e)$$\phi(e)$ 采用各自不同的 edge-based 矩阵 ${\mathbf{W}}_{\varphi (e)}^{\text{ATT}}\in {\mathbb{R}}^{d/h\times d/h}$$\mathbf W_{\phi(e)}^{\text{ATT}}\in \mathbb R^{d/h\times d/h}$ 。通过这种方式，模型甚至可以捕获同一对节点之间的不同语义关系。

     此外，由于并非所有关系均对目标节点做出相同的共享，因此我们采用了一个先验张量（prior tensor） $\mu \in {\mathbb{R}}^{|\mathcal{A}|\times |\mathcal{R}|\times |\mathcal{A}|}$$\mu\in \mathbb R^{|\mathcal A|\times |\mathcal R|\times |\mathcal A|}$ 用于表示每个元关系三元组的重要性，从而对 ${\text{ATT-head}}^i(s,e,t)$$\text{ATT-head}^i(s,e,t)$ 的自适应缩放。

   • 最后，我们将 $h$$h$ 个 attention head 拼接起来，从而获得每对节点 pair 对的 attention 向量。然后对于每个目标节点 $t$$t$ ，我们从其邻域 ${\mathcal{N}}_t$$\mathcal N_t$ 聚合所有的注意力进行 softmax，使其满足：

     $$\sum _{s\in {\mathcal{N}}_t}\text{Attention}(s,e,t)=\overrightarrow{\mathbf{1}}\in {\mathbb{R}}^h$$

     即：对于目标节点 $t$$t$ ，每个 head 邻域内的注意力之后为 1：$\sum _{s\in {\mathcal{N}}_t}\alpha (s,t{)}^i=1.0$$\sum_{s\in \mathcal N_t} \alpha(s,t)^i = 1.0$ 。

1.2.2 Heterogeneous Message Passing

1. 和注意力计算过程类似，我们希望将边的元关系融合到消息传递过程中，从而缓解不同类型节点和不同类型边的分布差异。

   对于边 $e=(s,t)$$e=(s,t)$，我们计算其 multi-head 消息为：

   $$\begin{array}{c}\text{Message}(s,e,t)=|{|}_{i=1,2,\cdots ,h}{\text{MSG-head}}^i(s,e,t)\\ {\text{MSG-head}}^i(s,e,t)={\text{M-Linear}}_{\tau (s)}^i\left({\overrightarrow{\mathbf{h}}}_s^{(l-1)}\right){\mathbf{W}}_{\varphi (e)}^{\text{MSG}}\end{array}$$

   其中：

   • ${\text{MSG-head}}^i(s,e,t)$$\text{MSG-head}^i(s,e,t)$ 为第 $i$$i$ 个 message head，它先将类型为 $\tau (s)$$\tau(s)$ 的源节点 $s$$s$ 经过一个线性投影 ${\text{M-Linear}}_{\tau (s)}^i:{\mathbb{R}}^d\to {\mathbb{R}}^{d/h}$$\text{M-Linear}_{\tau(s)}^i:\mathbb R^d \rightarrow \mathbb R^{d/h}$ ，然后再通过一个矩阵 ${\mathbf{W}}_{\varphi (e)}^{\text{MSG}}\in {\mathbb{R}}^{d/h\times d/h}$$\mathbf W_{\phi(e)}^{\text{MSG}}\in \mathbb R^{d/h\times d/h}$ 来融合边类型的依赖性。

     这里的 ${\mathbf{W}}_{\varphi (e)}^{\text{ATT}}$$\mathbf W_{\phi(e)}^{\text{ATT}}$ 和 ${\mathbf{W}}_{\varphi (e)}^{\text{MSG}}$$\mathbf W_{\phi(e)}^{\text{MSG}}$ 用于区分不同的边类型，并且可以支持多重边。

   • 然后，我们拼接所有的 $h$$h$ 个 message head 从而为每条边得到 $\text{Message}(s,e,t)$$\text{Message}(s,e,t)$ 。

2. 计算 multi-head 注意力过程和计算 multi-head 消息过程，二者之间可以并行进行。

1.2.3 Target-Specific Aggregation

1. 在计算出异质 multi-head 注意力、异质 multi-head 消息之后，我们需要将它们从源节点聚合到目标节点。

   我们可以简单地使用每个 head 的注意力向量作为权重，从而加权平均对应 head 每个源节点的消息。因此聚合过程为：

   $${\widetilde{\overrightarrow{\mathbf{h}}}}_t^{(l)}=\underset{s\in {\mathcal{N}}_t}{⨁}(\text{Attention}(s,e,t)\times \text{Message}(s,e,t))$$

   这将信息从不同类型的所有邻居（源节点）的信息聚合到目标节点 $t$$t$ 。

2. 最后一步是将目标节点 $t$$t$ 的representation 向量映射回其特定类型。为此，我们采用一个线性投影 ${\text{A-Linear}}_{\tau (t)}$$\text{A-Linear}_{\tau(t)}$ 来作用到 ${\widetilde{\overrightarrow{\mathbf{h}}}}_t^{(l)}$$\tilde{\mathbf{\vec h}}_t^{(l)}$ ，然后跟一个残差连接：

   $${\overrightarrow{\mathbf{h}}}_t^{(l)}={\text{A-Linear}}_{\tau (t)}\left(\sigma \left({\widetilde{\overrightarrow{\mathbf{h}}}}_t^{(l)}\right)\right)+{\overrightarrow{\mathbf{h}}}_t^{(l-1)}$$

   这样我们就获得了目标节点 $t$$t$ 的第 $l$$l$ 层输出 ${\overrightarrow{\mathbf{h}}}_t^{(l)}$$\mathbf{\vec h}_t^{(l)}$ 。

   因为前面将邻域节点信息 映射到公共空间，那么现在需要将公共空间映射回目标节点的特定类型空间。

3. 由于真实世界的图具有 small-world 属性，因此堆叠 $L$$L$ 层 HGT 层（$L$$L$ 是一个较小的数）就可以使得每个节点在整个图中触达大多数节点，这些节点具有不同类型和不同关系。即 HGT 为每个节点生成高度上下文相关的表示 ${\mathbf{H}}^{(L)}$$\mathbf H^{(L)}$ ，它可以用于任何异质网络下游任务，如节点分类和链接预测。

4. 在 HGT 的整个体系结构中，我们高度依赖使用元关系 $<\tau (s),\varphi (e),\tau (t)>$$<\tau(s), \phi(e), \tau(t)>$ 来分别参数化权重矩阵，这可以理解为模型容量和效率之间的折衷。

   • 和常规的 Transformer 相比，我们的模型区分了不同的节点类型和不同的关系类型，因此能够处理异质图中的分布差异。

   • 和为每种元关系保留独立的权重矩阵的现有方法相比，HGT 的三元组参数化可以更好地利用异质图的 schema 来实现参数共享。

     • 一方面，几乎从未出现过的关系仍然可以从这种参数共享中受益，从而可以实现快速适应和泛化。

     • 另一方面，不同类型的节点和关系仍然可以使用更少的参数集合来维持其独有的特点。

1.2.4 Relative Temporal Encoding

1. 这里我们介绍用于 HGT 的相对时间编码 RTE 技术来处理动态图。

   传统的融合时间信息的方法是为每个时间片（time slot）构建一个独立的图，但是这种方式可能丢失跨不同时间片的结构相关性。同时，节点在时刻 $t$$t$ 的representation 可能依赖于其它时刻发生的连接。因此，对动态图进行建模的一种正确方式是：维持在不同时刻发生的所有边，并允许具有不同时间戳的节点和边彼此交互。

   有鉴于此，HGT 提出了相对时间编码 RTE 机制来建模异质图中的动态依赖性（dynamic dependency）。RTE 的灵感来自于 Tansformer 中的位置编码方法，该方法已成功地捕获了长文本中单词的顺序依赖性 （sequential dependency）。

   具体而言，给定源节点 $s$$s$ 和目标节点 $t$$t$ ，以及它们的时间戳 $T(s),T(t)$$T(s), T(t)$ ，我们定义相对时间间隔 $\mathrm{\Delta }T(t,s)=T(t)-T(s)$$\Delta T(t,s) = T(t) - T(s)$ 作为索引来获得相对时间编码 $\text{RTE}(\mathrm{\Delta }T(t,s))$$\text{RTE}(\Delta T(t,s))$ 。

   注意：训练数据集可能没有覆盖所有可能的时间间隔，因此 RTE 应该能够泛化到未看到的时间和时间间隔。因此我们使用一组固定的正弦函数作为 basis，并使用一个可训练的线性映射 $\text{T-Linear}:{\mathbb{R}}^d\to {\mathbb{R}}^d$$\text{T-Linear}:\mathbb R^d\rightarrow \mathbb R^d$ 作为 RTE：

   $$\begin{array}{c}\text{Base}(\mathrm{\Delta }T(t,s),2i)=\sin \left(\frac{\mathrm{\Delta }{T}_{t,s}}{{10000}^{2i/d}}\right)\\ \text{Base}(\mathrm{\Delta }T(t,s),2i+1)=\cos \left(\frac{\mathrm{\Delta }{T}_{t,s}}{{10000}^{(2i+1)/d}}\right)\\ \text{RTE}(\mathrm{\Delta }T(t,s))=\text{T-Linear}(\text{Base}(\mathrm{\Delta }{T}_{t,s}))\end{array}$$

   最终，针对目标节点 $t$$t$ 的相对时间编码将添加到源节点 $s$$s$ 的 representation 中：

   $${\widehat{\overrightarrow{\mathbf{h}}}}_s^{(l-1)}={\overrightarrow{\mathbf{h}}}_s^{(l-1)}+\text{RTE}(\mathrm{\Delta }T(t,s))$$

   该过程发生在每个 step 的信息聚合之前。

   通过这种方式，融合时间的representation ${\widehat{\overrightarrow{\mathbf{h}}}}_s^{(l-1)}$$\hat{\mathbf{\vec h}}_s^{(l-1)}$ 将捕获源节点 $s$$s$ 和目标节点 $t$$t$ 的相对时间信息。

   RTE 的详细过程如下图所示：

   

2. 目前为止我们为每个节点 $t$$t$ 分配了一个时间戳 $T(t)$$T(t)$ ，但是现实世界中很多节点都具有多个时间戳，我们将这些节点称作 plain 节点。如：论文数据集中，WWW 会议在 1974 年和 2019 年都举行，但是这两年的研究主题截然不同。因此我们需要决定将哪个时间戳添加到 WWW 节点。

   与 plain 节点相反，异质图中存在一些 event节点，它存在唯一的、固定的时间戳。如：论文数据集中，论文节点和该论文发表时间明确相关。

   为此，我们提出了一种 inductive 时间戳分配算法，它对 plain 节点基于该plain 节点相连的 event 节点来分配时间戳。基本思想是：plain 节点从 event 节点中继承时间戳。我们检查节点是否为 event 节点：

   • 如果节点是 event 节点，如特定年份发表的论文节点，则我们保留该 event 节点的时间戳从而捕获时间依赖性temporal dependency。

   • 如果节点不是 event 节点，则可以像作者节点一样关联多个时间戳，我们将相连节点的时间戳分配给这个 plain 节点。

     如果有多个时间戳，那么怎么计算 $\mathrm{\Delta }T(t,s)$$\Delta T(t,s)$ ？根据下面提到的算法过程，是通过子图采样算法来自动分配的，这个时间戳的分配具有一定的随机性。

   这样我们可以在子图采样过程中自适应地分配时间戳。

1.2.5 HGSampling

1. full-batch 的 GNN 训练要求计算每层所有节点的 representation，这使得它无法扩展到 web-scale 图。为解决这些问题，已有各种基于采样的方法在一个节点子集上训练 GNN。但是这些方法无法直接应用到异质图，因为在异质图中每种类型节点的 degree 分布和节点总数可能差异非常大，所以这些采样方法直接应用到异质图中可能得到节点类型极为不平衡的子图。

   为解决该问题，我们提出了一种有效的异质图 mini-batch 采样算法 HGSampling，使得 HGT 和传统 GNN 都能够处理 web-scale 异质图。其核心是为每种节点类型 $\tau$$\tau$ 保留单独的节点预算 $\mathcal{B}[\tau ]$$\mathcal B[\tau]$ ，它是一个列表，存储该类型所有节点的采样重要性。然后在利用重要性采样策略（importance sampling strategy）来降低方差。

   HGSampling 优势：

   • 为每种类型保留相似数量的节点和边。

   • 采样到的子图保持稠密，从而最大程度地减少信息损失并降低采样方差。

2. HGSampling 算法：

   • 输入：

     • 包含所有元关系的邻接矩阵 $\mathbf{A}$$\mathbf A$

     • 每种类型的节点的采样数量 $n$$n$

     • 采样深度 $L$$L$

     • mini-batch 节点集合 $\mathcal{O}$$\mathcal O$ （即第 $L$$L$ 层的节点集合）

   • 输出：最终输出节点集合 $\mathcal{O}$$\mathcal O$ 及其邻接矩阵 $\hat{\mathbf{A}}$$\hat{\mathbf A}$

   • 算法步骤：

     • 初始化采样节点集合 $\mathcal{S}\leftarrow \mathcal{O}$$\mathcal S\leftarrow \mathcal O$ 。

     • 初始化一个空的预算 $\mathcal{B}=\{\}$$\mathcal B = \{\}$ ，它存储每种节点类型的节点及节点归一化的 degree 。

     • 对 $\mathcal{S}$$\mathcal S$ 中每个节点 $t$$t$ ，将邻居节点添加到 $\mathcal{B}$$\mathcal B$ 中：$\text{Add-in-Budget}(\mathcal{B},t,\mathbf{A},\mathcal{S})$$\text{Add-in-Budget}(\mathcal B, t, \mathbf A, \mathcal S)$ 。

       $\mathcal{B}$$\mathcal B$ 中存放候选的邻域集合以及对应的每个节点的归一化 degree 。

     • 迭代 $l=1,2,\cdots ,L$$l=1,2,\cdots,L$ ，迭代步骤为：

       • 对 $\mathcal{B}$$\mathcal B$ 中的每个节点类型 $\tau \in \mathcal{B}$$\tau\in \mathcal B$ 进行迭代，迭代步骤为：

         • 对 $\mathcal{B}[\tau ]$$\mathcal B[\tau]$ 的每个节点 $s$$s$ ，计算采样概率为：

           $$p^{(l-1)}[\tau ][s]\leftarrow \frac{{(\mathcal{B}[\tau ][s])}^2}{||\mathcal{B}[\tau ]|{|}_2^2}$$

           其中分子为节点 $s$$s$ 的归一化 degree 的平方，分母为 $\mathcal{B}$$\mathcal B$ 中类型为 $\tau$$\tau$ 的所有节点的归一化 degree 的平方和。

         • 从 $\mathcal{B}[\tau ]$$\mathcal B[\tau]$ 中使用概率 $p^{(l-1)}[\tau ]$$p^{(l-1)}[\tau]$ 采样 $n$$n$ 个节点 $\{t_i{\}}_{i=1}^n$$\{t_i\}_{i=1}^n$ 。

         • 对于每个采样到的节点 $t\in \{t_i{\}}_{i=1}^n$$t\in \{t_i\}_{i=1}^n$ ，执行：

           • 添加节点 $t$$t$ 到输出节点集合 $\mathcal{O}[\tau ].\text{add}(t)$$\mathcal O[\tau].\text{add}(t)$。

           • 添加节点 $t$$t$ 的邻居到 $\mathcal{B}$$\mathcal B$ ：$\text{Add-in-Budget}(\mathcal{B},t,\mathbf{A},\mathcal{S})$$\text{Add-in-Budget}(\mathcal B, t, \mathbf A, \mathcal S)$ 。

           • 从 $\mathcal{B}$$\mathcal B$ 中移除节点 $t$$t$ ：$\mathcal{B}[\tau ].\text{pop}(t)$$\mathcal B[\tau].\text{pop}(t)$ 。

     • 基于输出节点集合 $\mathcal{O}$$\mathcal O$ 和邻接矩阵 $\mathbf{A}$$\mathbf A$ 来重构采样的邻接矩阵 $\hat{\mathbf{A}}$$\hat{\mathbf A}$ 。

     • 返回 $\mathcal{O}$$\mathcal O$ 和 $\hat{\mathbf{A}}$$\hat{\mathbf A}$ 。

3. Add-In-Budget 算法：

   • 输入：

     • 集合 $\mathcal{B}$$\mathcal B$ ，它用于存储每种类型的节点及其归一化的 degree

     • 被添加的节点 $t$$t$

     • 包含所有元关系的邻接矩阵 $\mathbf{A}$$\mathbf A$

     • 采样节点集合 $\mathcal{S}$$\mathcal S$

   • 输出：更新后的集合 $\mathcal{B}$$\mathcal B$

   • 算法步骤：

     • 对于每种可能的源节点类型 $\tau$$\tau$ 和边类型 $\varphi$$\phi$ 迭代，迭代步骤为：

       • 根据 $<\tau ,\varphi ,\tau (t)>$$<\tau,\phi,\tau(t)>$ 计算节点 $t$$t$ 的归一化 degree：

         $${\hat{D}}_t\leftarrow \frac{1}{\text{len}(A_{<\tau ,\varphi ,\tau (t)>}[t])}$$

         其中 $A_{<\tau ,\varphi ,\tau (t)>}$$A_{<\tau,\phi,\tau(t)>}$ 表示目标节点为 $t$$t$、源节点类型为 $\tau$$\tau$、链接类型为 $\varphi$$\phi$ 的一阶邻居源节点集合。

         这里计算的是目标节点 $t$$t$ 关于源节点类型 $\tau$$\tau$ 的 degree，而不是 $t$$t$ 的总 degree 。

       • 对于每个源节点 $s\in A_{<\tau ,\varphi ,\tau (t)>}[t]$$s\in A_{<\tau,\phi,\tau(t)>}[t]$ 且未被采样到（ $s\notin \mathcal{S}$$s\notin \mathcal S$）进行迭代，迭代步骤为：

         • 如果 $s$$s$ 没有时间戳，则： s.time = t.time 。

         • 将节点 $s$$s$ 添加到 $\mathcal{B}$$\mathcal B$ 中，并带上目标节点 $t$$t$ 的归一化 degree : $\mathcal{B}[\tau ][s]\leftarrow \mathcal{B}[\tau ][s]+{\hat{D}}_t$$\mathcal B[\tau][s] \leftarrow \mathcal B[\tau][s] + \hat D_t$ 。

     • 返回更新后的 $\mathcal{B}$$\mathcal B$ 。

4. 算法解释：假设节点 $t$$t$ 已经被采样到，我们使用 Add-In-Budget 算法将其所有一阶邻居添加到对应的 $\mathcal{B}$$\mathcal B$ 中，并将节点 $t$$t$ 的归一化 degree 添加到这些邻居上，然后将其应用于计算采样概率。这样的归一化等效于累积每个采样节点到其邻域的随机游走概率，从而避免采样被高阶节点统治。直观地看，该值越高，则候选节点和当前节点之间的相关性越大，因此应该赋予其更高的采样概率。

   $\mathcal{B}$$\mathcal B$ 更新之后，我们在 HGSampling 算法的前几行计算采样概率，通过计算 $\mathcal{B}$$\mathcal B$ 中每个节点 $s$$s$ 的 累积归一化 degree 的平方来计算重要性采样的概率。通过这种采样概率，我们可以降低采样方差。

   然后，我们使用计算到的概率对类型为 $\tau$$\tau$ 采样 $n$$n$ 个节点，并将其添加到输出节点集合中。然后，我们将它们的邻居添加到 $\mathcal{B}$$\mathcal B$ 中，并将它们自己从 $\mathcal{B}$$\mathcal B$ 中移除。

   重复这样的过程 $L$$L$ 次，我们从初始节点获得深度为 $L$$L$ 的采样子图。最后，我们在采样节点之间重建邻接矩阵。

   通过使用上述算法，被采样的子图对每个类型包含相似的节点数量，并且足够稠密，且通过归一化的 degree 和重要性采样来降低方差。因此这种方式适用于 web-scale 图上训练 GNN 。

   整个采样过程如下图所示：不同颜色表示不同的节点类型。

   • (0) ：选择初始节点 $P_1$$P_1$ （黑色圆圈圈住的节点）。此时 $\mathcal{B}$$\mathcal B$ 全空。

   • (1)：选择 $P_1$$P_1$ 的邻居节点集合（边进行了加粗），并将邻居节点加入 $\mathcal{B}$$\mathcal B$ 中。不同类型的邻居节点加入到不同类型的队列中，并带上 $P_1$$P_1$ 的归一化 degree 和时间戳（根据 inductive 时间戳分配）。

   • (2)：对每种类型采样 $n$$n$ 个节点，这里 $n=3$$n=3$ 并采样到节点 $P_3,A_1,V_1$$P_3, A_1,V_1$ （黑色圆圈圈住），并将它们从 $\mathcal{B}$$\mathcal B$ 中弹出。于是$\mathcal{B}$$\mathcal B$ 中就剩下节点 $P_2$$P_2$ 。

   • (3)：对于新采样的节点 $P_3,A_1,V_1$$P_3, A_1,V_1$ ，将它们的邻居节点加入到 $\mathcal{B}$$\mathcal B$ 中。例如，对于节点 $A_1$$A_1$ ，其邻居节点为 $P_2,V_1,A_2,P_1$$P_2, V_1,A_2, P_1$ ，其中 $P_1,V_1$$P_1,V_1$ 为已采样到的节点不予考虑， $P_2$$P_2$ 已经在队列中则对其 degree 值进行累加。

   • (4)：对每种类型采样 $n$$n$ 个节点，这里 $n=3$$n=3$ 并采样到节点 $P_2,A_2,V_2$$P_2, A_2,V_2$ （黑色圆圈圈住），并将它们从 $\mathcal{B}$$\mathcal B$ 中弹出。

   • (5)：采样结束。

   

1.3 实验

1. 我们在三个异质学术图数据集上评估 HGT，并分别执行 Paper-Field 预测、Paper-Venue 预测、Author Disambiguation 任务。

2. 数据集：我们使用 Open Academic Graph:OAG 数据集，它包含超过 1.78 亿节点和 22.36 亿条边，这是最大的公开可用的异质学术数据集。此外，OAG 中所有论文关联一个发表日期，该日期从 1900 到 2019 年。

   数据集包含五种类型的节点 Paper、Author、Field、Venue、Institute，其中 OAG 的领域Field 字段一共包含 L0 到 L5 共六个层级，这些层级通过层级树（hierarchical tree）来组织。因此，我们根据领域层级来区分 Paper-Field 边。此外，我们还区分了不同的作者顺序（第一作者、最末作者、其它作者）和会议类型（期刊jornal、会议 conference、预印本 preprint）。最后，self 类型对应于自环连接，这是 GNN 架构中广泛添加的。除了 self 关系是对称的之外，其余所有关系都是不对称的，每种关系 $\varphi$$\phi$ 都具有对应的反关系（reverse relation） ${\varphi }^{-1}$$\phi^{-1}$ 。

   为测试 HGT 的泛化能力，我们还从 OAG 构造了两个特定领域的子图：计算机科学 CS 学术图、医学 Med 学术图。CS和 Med 图都包含数千万个节点和数亿条边。

   所使用的三个数据集比以前 GNN 研究中广泛使用的小型引文网络（Cora,Citeseer,Pubmed）大得多，后者仅包含数千个节点。

   下表给出了数据集的统计信息，其中 P-A 表示“论文 -- 作者”、 P-F 表示 “论文 -- 研究领域”、P-V 表示 “论文 -- 会议”、 A-I 表示 “作者 -- 研究机构”、P-P 表示论文引用。

   

3. 我们通过四个不同的下游任务来评估 HGT：Paper -- Field(L1) 预测、Paper -- Field(L2) 预测、Paper -- Venue 预测、Author Disambiguation 。

   • 前三个任务是节点分类任务，目标是分别预测每篇论文的一级领域、二级领域、发表会议。

     我们使用不同的 GNN 获取论文的上下文节点 representation，并使用 softmax 输出层来获取其分类标签。

   • 对于Author Disambiguation 任务，我们选择所有同名的作者及其相关的论文，任务目标是在这些论文和候选作者之间进行链接预测。

     从 GNN 获得论文节点和作者节点的 representation 之后，我们使用 Neural Tensor Network 来获得每个 author -- paper 节点对之间存在链接的概率。

   对于所有任务，我们使用 2015 年之前发布的论文作为训练集，使用 2015 ~ 2016 年之间的论文作为验证集，使用 2016 ~ 2019 年之间的论文作为测试集。

   我们使用 NDCG 和 MRR 这两个广泛应用的 ranking 指标作为评估指标。我们对所有模型进行 5 次训练，并报告测试集性能的均值和标准差。

4. baseline 方法：我们比较了两类 SOTA 图神经网络，所有baseline 以及我们的 HGT 都通过 PyTorch Geometric(PyG) package 来实现。

   • 同质图 GNN baseline：

     • GCN：简单地对邻域 embedding 取平均，然后跟一个线性映射。我们使用 PyG 提供的实现。

     • GAT：对邻域节点采用 multi-head additive attention。我们使用 PyG 提供的实现。

   • 异质图 GNN baseline：

     • RGCN：对每种元关系（三元组）保持不同的权重。我们使用 PyG 提供的实现。

     • HetGNN：对不同的节点类型采用不同的 Bi-LSTM 来聚合邻域信息。我们根据作者提供的官方代码使用 PyG 重新实现。

     • HAN：通过不同的 metapath 使用分层注意力来聚合邻域信息。我们根据作者提供的官方代码使用 PyG 重新实现。

   此外，为了系统地分析 HGT 的两个主要部分的有效性，即异质权重参数化（ Heterogeneous Weight Parameterization: Heter）、相对时间编码（Relative Temporal Encoding: RTE），我们进行了消融研究。我们比较了移除这些部分的 HGT 模型性能。具体而言，我们用 -Heter 表示对所有元关系使用相同的权重集合，使用 -RTE 表示没有相对时间编码。考虑所有的排列，我们得到以下模型：

   $${\text{HGT}}_{\text{-Heter}}^{-\text{RTE}},{\text{HGT}}_{\text{-Heter}}^{+\text{RTE}},{\text{HGT}}_{\text{+Heter}}^{-\text{RTE}},{\text{HGT}}_{\text{+Heter}}^{+\text{RTE}}$$

   我们使用HGSampling 采样算法应用到所有 baseline GNN ，从而处理大规模的 OAG 数据集。为了避免数据泄露，我们从子图中删除我们目标预测的链接。

5. 输入特征：我们对不同的节点类型采用不同的特征：

   • 论文节点：使用预训练的 XLNet 来获取标题中每个单词的 representation。然后，我们根据每个单词的注意力对它们进行加权平均，从而得到每篇论文的标题 representation。

   • 作者节点：使用该作者发表的所有论文的标题的 representation 取平均。

   • 领域节点、会议节点、机构节点：使用 metapath2vec 来训练其node embedding，从而反映异质网络结构。

   另外，同质 GNN 假设所有节点都是相同类型的特征。因此，为了进行公平的比较，我们在输入特征和同质GNN 之间添加一个适配层，该层用于对不同类型的节点进行不同的线性映射。可以认为该过程能够将异质特征映射到相同的特征空间。

6. 实现方式：

   • 对于所有的 baseline，我们在整个神经网络网络中使用隐层维度为 256。

   • 对于所有基于 multi-head attention 方法，我们将 head 数量设为 8 。

   • 所有 GNN 均为三层（不包括适配层），使得每个网络的感受野完全相同。

   • 所有 baseline 方法均通过 Cosine Annealing Learning Rate Scheduler 的 AdamW 优化器优化。

   • 每个模型我们训练 200 个 epoch，然后选择验证损失最小的那个作为评估模型。

   • 我们选择使用 GNN 文献中默认使用的超参数，并未进行超参数调优。

7. 所有模型在所有数据集上的表现如下表所示，其中评估指标为 NGCD, MRR 。结论：

   • HGT 在所有数据集的所有任务上均显著优于所有 baseline。总体而言，在所有三个大规模数据集上的四个任务中，HGT 平均优于 GCN, GAT, RGCN, HetGNN, HAN 大约 20% 。

     此外， HGT 具有更少的参数、差不多的 batch 时间。这表明 HGT 根据元关系 schema 建模异质边，从而以更少的资源实现更好的泛化

   • 和完整模型 ${\text{HGT}}_{\text{+Heter}}^{+\text{RTE}}$$\text{HGT}_{\text{+Heter}}^{+\text{RTE}}$ 相比：

     • 删除异质权重参数化的模型，即 ${\text{HGT}}_{\text{-Heter}}^{+\text{RTE}}$$\text{HGT}_{\text{-Heter}}^{+\text{RTE}}$ 降低了 4% 的性能。

     • 删除相对时间编码的模型，即 ${\text{HGT}}_{\text{+Heter}}^{-\text{RTE}}$$\text{HGT}_{\text{+Heter}}^{-\text{RTE}}$ 降低了 2% 的性能。

     这表明了权重参数化、相对时间编码的重要性。

   • 最后我们还尝试了一个 baseline，它为每个关系类型保留不同的参数矩阵。但是，这样的 baseline 包含太多参数，因此我们的实验设置没有足够的 GPU 内层对其进行优化。

     这也表明：使用元关系对权重矩阵进行分解可以在较少的资源条件下获得有竞争力的优势。

   

8. 为进一步评估相对时间编码 RTE 如何帮助 HGT 捕获图的动态性，我们进行一个案例研究来展示会议主题的演变。我们选择被引用次数最多的 100 个计算机科学会议，为它们分配了三个不同的时间戳 2000、2010、2020 ，并构造了由它们初始化的子图。我们使用训练好的 HGT 来获取这些会议的 representation ，然后计算这些会议之间的欧式距离。

   我们以 WWW、KDD、NeuraIPS 为例，对于每个会议我们选择其 top 5 最相似的会议，从而显示会议主题随时间的变化。结果如下表所示。结论：

   • 2000 年的 WWW 和某些数据库会议(SIGMOD 和 VLDB) 以及一些网络会议（NSDI 和 GLOBECOM） 更相关。但是，除了 SIGMOD, GLOBECOM 之外， 2020 年的 WWW 和某些数据挖掘和信息检索会议（KDD, SIGIR, WSDM） 更相关。

   • 2000 年的 KDD 和传统的数据库和数据挖掘会议更相关，而 2020 年的 KDD 倾向于和多种主题相关，如机器学习（NeurIPS）、数据库 （SIGMOD）、Web(WWW)、AI（AAAI）、NLP (EMNLP )。

   • 除此之外，HGT 还能捕获新会议带来的差异。例如 2020 年的 NeurIPS 和 ICLR（这是一个新的深度学习会议） 相关。

   该案例研究表明：相对时间编码可以帮助捕获异质学术图的时间演变。

   

9. 为说明融合的元关系模型如何使得异质消息传递过程受益，我们选择在前两层 HGT 层中具有最高注意力的模式，并在图中绘制元关系注意力层次树。

   例如，为计算论文的 representation，最重要的三个元关系序列为：

   $$\begin{array}{c}<\text{Paper},\text{is-published-at},\text{Venue},{\text{is-published-at}}^{-1},\text{Paper}>\\ <\text{Paper},{\text{has-L}}_2\text{-field-of},\text{Field},{\text{has-L}}_5{\text{-field-of}}^{-1},\text{Paper}>\\ <\text{Institude},{\text{is-affiliated-with}}^{-1},\text{Author},\text{is-first-author-of},\text{Paper}>\end{array}$$

   这可以分别视为 metapath: PVP, PFP, IAP 。

   注意：无需手动设计既可以自动从数据中学到这些 metapath 及其重要性。

   右图给出了计算作者 representation 的另一个case。这些可视化结果表明，HGT 能够隐式地学到为特定下游任务构造的重要的 metapath，无需手动构建。