https://arxiv.org/pdf/2003.01332

https://github.com/acbull/pyHGT

Heterogeneous Graph Transformer，WWW，2020

总结：未完待续

1. 简介

1.1摘要

Recent years have witnessed the emerging success of graph neu-ral networks (GNNs) for modeling structured data. However, mostGNNs are designed for homogeneous graphs, in which all nodesand edges belong to the same types, making them infeasible torepresent heterogeneous structures. In this paper, we present theHeterogeneous Graph Transformer (HGT) architecture for mod-eling Web-scale heterogeneous graphs. To model heterogeneity,we design node- and edge-type dependent parameters to charac-terize the heterogeneous attention over each edge, empoweringHGT to maintain dedicated representations for different types ofnodes and edges. To handle dynamic heterogeneous graphs, we in-troduce the relative temporal encoding technique into HGT, whichis able to capture the dynamic structural dependency with arbitrarydurations. To handle Web-scale graph data, we design the hetero-geneous mini-batch graph sampling algorithm—HGSampling—forefficient and scalable training. Extensive experiments on the OpenAcademic Graph of 179 million nodes and 2 billion edges showthat the proposed HGT model consistently outperforms all thestate-of-the-art GNN baselines by 9%–21%on various downstreamtasks. The dataset and source code of HGT are publicly available at https://github.com/acbull/pyHGT.

最近几年GNNs在结构化数据建模中取得了很大的成功，但是大多数GNNs模型都是用于同构网络（节点和边属于同一个类型），无法直接用于异构网络的表示学习。在本文中，作者介绍了Heterogeneous Graph Transformer（HGT）模型，用于web-scale异构网络的建模。为了对异构性进行建模，作者为node-type和edge-type分别使用独立的参数来characterize每一条边的heterogeneous attention，让HGT模型能够为每种类型的节点和边维护一个特定表示。为了处理动态异构图，作者引入了relative temporal编码技术。为了能够出来了web-scale图数据，作者设计了一种异构mini-batch图采样算法——HGSampling，采样子图进行有效地训练。在有179million节点和2billion边的Academic Graph数据集上的大量实验表明作者提出的HGT模型在各种下游任务上的表现优于state-of-art GNN 9%~21%。数据集和HGT源码发布在https://github.com/acbull/pyHGT。

1.2 本文工作

异构图挖掘主要有两种方式：（1）通过定义元路径来对异构结构进行建模，比如PathSim，Metapath2vec等等；（2）GNNS，比如R-CGNs，HetGNN和HAN。这些方法存在一些弊端：

1. 大多数方法都需要针对不同类型的图单独设计元路径，这就需要我们对图数据有一定了解。
2. 这些方法要么假设不同类型的节点和边具有具有相同的特征空间，要么只是针对不同类型节点或边使用不同的共享权重。这对于捕捉异构图的属性信息是不够的。
3. 大多数方法都忽略了图的动态特性。
4. 这些方法无法适用于大规模异构图的建模。

针对这些limitations，作者提出了HGT模型。（1）为了处理图的异构性，作者分别引入了node-type和edge-type独立的注意力机制；（2）如下图所示，HGT把one-hop edges作为输入，不需要手动设计元路径；

1.3 问题定义

1. 异构网络

   有向图$G=\mathcal{(V,E,A,R)}$，图中节点$v\in\mathcal V$，边$e\in\mathcal E$，以及类型映射$\tau(v):V\rightarrow\mathcal A$和$\phi(e):E\rightarrow\mathcal R$。

2. 元关系

   每一条边$e=(s,t)$连接source node s和target node t，元关系定义为$<\tau(s),\phi(e),\tau(t)>$，$\phi(e)^{-1}$表示$\phi(e)$的转置。

3. 动态异构图

   每一条边$e=(s,t)$都分配一个时间戳T，表示节点s和t在T时刻有一条边相连。如果s是第一次出现，那么T绑定为s出现的时间。如果一条边出现在多个时间点，允许一条边有多个时间戳T。

2. HGT

三个部分组成：Heterogeneous Mutual Attention，Heterogeneous Message Passing和Target-Specific Aggregation。

2.1 Heterogeneous Mutual Attention（聚合邻居信息）

计算目标节点t和其邻居节点s之间的相互注意力，计算方法如下：

$H^{l}[t] \leftarrow \underset{\forall s \in N(t), \forall e \in E(s, t)}{\text { Aggregate }}(\text { Attention }(s, t) \cdot \text { Message }(s))\tag 2$

包含三个部分：（1）Attention，评估每个source node的重要性；（2）Message，source node的信息（上一层的embedding）；（3）Aggregate，根据注意力权重聚合邻居节点信息。GAT模型聚合邻居信息的方式如下：

$\begin{aligned} \text { Attention }_{G A T}(s, t) &=\operatorname{Softmax}_{\forall s \in N(t)}\left(\vec{a}\left(W H^{l-1}[t] \| W H^{l-1}[s]\right)\right) \\ \quad \text { Message }_{G A T}(s) &=W H^{l-1}[s] \\ \text { Aggregate }_{G A T}(\cdot) &=\sigma(\operatorname{Mean}(\cdot)) \end{aligned}$

虽然GAT中的注意力机制能够有效的识别重要程度高的节点，但是它假设s节点和t节点的特征分布相同，使用了相同的权重参数W。这一假设在异构网络中是不成立的，因为不同类型的节点和边特征分布不同。鉴于这一限制，作者提出了异构相互注意力机制。给定目标节点t以及其所有邻居$s\in N(t)$，按照元关系$<\tau(s),\phi(e),\tau(t)>$分别计算每种类型元关系的相互注意力。

受Transformer的启发，作者将目标节点t看做Query向量，t的邻居节点看做Key向量，计算它们之间的点积作为attention。和Transformer的不同之处在于，普通的transformer只有一个用于所有单词的set of projections，而作者这里每种类型元关系都有自己的映射权重。

为了保证每种元关系都有自己的专属特征的同时，尽可能实现参数共享，降低模型复杂度， we propose to parameterize the weight matrices of the interac-tion operators into a source node projection, an edge projection,and a target node projection.

$\begin{aligned} \text { Attention }_{H G T}(s, e, t) &=\underset{\forall s \in N(t)}{\operatorname{Softmax}}\left(\|_{i \in[1, h]} \text { ATT-head }^{i}(s, e, t)\right) \\ \text { ATT-head }^{i}(s, e, t) &=\left(K^{i}(s) W_{\phi(e)}^{A T T} Q^{i}(t)^{T}\right) \cdot \frac{\mu_{\langle\tau(s), \phi(e), \tau(t)\rangle}}{\sqrt{d}} \\ K^{i}(s) &=\text { K-Linear }_{\tau(s)}^{i}\left(H^{(l-1)}[s]\right) \\ Q^{i}(t) &=Q \text { -Linear }_{\tau(t)}^{i}\left(H^{(l-1)}[t]\right) \end{aligned}\tag 3$

2.2 Target-Specific Aggregation

利用公式3，利用聚合多头注意力后得到的注意力向量作为权重，加权平均所有邻居节点的信息，来更新目标节点t的embedding：

$\widetilde{H}^{(l)}[t]=\bigoplus_{\forall s \in N(t)}\left(\text { Attention }_{H G T}(s, e, t) \cdot \text { Message }_{H G T}(s, e, t)\right)$

之后，再利用$A-Linear_{\tau(t)}$将t节点的嵌入映射回原有类型空间（作者这里还采用了残差连接，即将l-1层节点嵌入也作为输入）：

$H^{(l)}[t]=\text { A-Linear }_{\tau(t)}\left(\sigma\left(\widetilde{H}^{(l)}[t]\right)\right)+H^{(l-1)}[t]\tag 5$

2.3 Relative Temporal Encoding

传统的利用图动态信息的方式是在每个时间节点分别构建一个异构图，但是这种方式会丢失大量结构依赖性。另外，t时刻某个节点的表示可能依赖于其他时刻的边。因此对动态网络建模的一种合适方式是保留所有时刻的边和节点信息，将它们整合到一张图上，这样不同时刻的节点和边也能交互。

针对这个问题，受Transformer’s positional encoding方法的启发，作者提出RTE机制。具体来说，给定目标节点t和邻居节点s，以及它们对应的时间戳$T(s)$和$T(t)$，用$\Delta T(t,s)=T(t)-T(s)$作为index来获取一个relative temporal encoding $RTE(\Delta T(t,s))$。具体计算方式如下：

$\operatorname{Base}(\Delta T(t, s), 2 i) =\sin \left(\Delta T_{t, s} / 10000^{\frac{2 i}{d}}\right)\tag 6$

$\operatorname{Base}(\Delta T(t, s), 2 i+1) =\cos \left(\Delta T_{t, s} / 10000^{\frac{2 i+1}{d}}\right)\tag 7$

$\operatorname{RTE}(\Delta T(t, s)) =\text { T-Linear }\left(\operatorname{Base}\left(\Delta T_{t, s}\right)\right)\tag 8$

最后，再将$RTE(\Delta T(t,s))$添加到GNN的$H^{(l-1)}[s]$中：

$\widehat{H}^{(l-1)}[s]=H^{(l-1)}[s]+R T E(\Delta T(t, s))\tag 9$

2.4 训练

作者提出两个方法，将HGT用于带有动态信息的大规模异构网络：（1）异构mini-batch图采样算法——HGSampling；（2）inductive timestamp assignment method。

2.4.1 HGSampling

Full-Batch GNN训练时每一层都要计算所有节点的表示，无法用于大规模图数据。为了解决这个问题，研究人员提出了很多基于采样的方法来训练GNNs。但是，因为每种类型的节点度分布和节点总数差异很大，直接将这些方法用于异构网络进行子图采样是行不通的，这会导致子图在不同节点类型上极不平衡。

思想：为每种节点类型$\tau$维护一个独立的node budget $B[\tau]$，保证每种类型节点被采样到的数量尽可能一致。

采样步骤如下：

1. 给定初始点，并将初始点的邻居通过Add-In-Budget算法添加到budget中
2. budget中每种类型节点按照概率都pop n个节点，将这些节点添加到输出节点集合中
3. 新添加到输出节点集合的每一个节点，都执行Add-In-Budget操作
4. 重复2~3，知道Budget为空为止

算法伪代码如下：

下图展示了一个简单的子图采样过程：

2.4.2 Inductive Timestamp Assignment

上述算法可以正确执行的一个前提是：每个节点只有一个时间戳。但是在真实数据集中，这个前提条件可能不成立。比如学术网络中WWW会议在2019年、1974年都举办了，因此WWW节点会有两个时间戳（称之为plain节点）。还有一些节点的时间戳是和它邻居节点相关联的，比如论文节点的时间戳和它的发表时间相关联。因此，在子图采样过程中需要作一些特殊处理，确保每个节点有且只有一个准确的时间戳。作者采取的策略是：plani node继承event node的时间戳（算法2伪代码第6行）。检测节点是否是一个event节点，如果是（比如论文节点），则保持节点时间戳不变。如果不是（比如会议节点），则继承和该节点相关联的event节点的时间戳。

3. 实验

在大规模学术网络上：（1）Paper-Feild预测；（2）Paper-Venue预测；（3）Author消歧；（4）case study：HGT如何自动学习提取元路径的

3.1 实验设置

一、数据集

二、Baselines

1. 同构网络学习：GCN，GAT
2. 异构网络GNNs：RGCN，HetGNN，HAN
3. HGT变体：$HGT_{-Heter}^{-RTE}$，$HGT_{-Heter}^{+RTE}$，$HGT_{+Heter}^{-RTE}$，$HGT_{+Heter}^{+RTE}$。其中$-RTE$表示去除相对时间编码RTE部分，$-Heter$表示不同的元关系采用相同的权重参数（即不考虑网络异构性）。

3.2 实验结果

3.3 Case Study

为了进一步研究RTE是如何捕捉图的动态特征的，作者做了一个关于会议动态演化的实验。

3.4 可视化

这一部分主要解释HGT中使用的Meta Relation Attention可以自动学习到有效的元路径，无需人工手动定义。如下图所示，作者展示了HGT前两层权重值最大的schema：

如上图左半部分，如果要计算一篇论文的embedding， ⟨Paper,is_published_at, Venue,is_published_at−1, Paper⟩，⟨Paper,has_L2_field_o f, Field,has_L5_field_of−1, Paper⟩和⟨Institute,is_a f f iliated_with−1, Author,is_first_author_of，Paper⟩ 是三个注意力权重最大的元关系序列。这三个序列可以看做PVP，PFP和IAP三种类型元路径。这也就是说模型可以自动学出有用的元路径，无需人工手动定义。