Heterogeneous Graph Transformer

本文提出了异质图上transformer结构HGT，保留节点特征分布异质性，提出元关系，并使用基于元关系计算相似度替代点乘，模型中利用相对时间差对动态图进行建模并提出HGSampling方法以解决规模大的图结构，在多个节点分类与链接预测任务上相较其他HGNN取得SOTA效果。paper

ABSTRACT

近年来提出的GNN多应用于同质图，考虑节点和边都属于同一种类型，而我们提出Heterogeneous Graph Transformer (HGT)模型可以解决Web-scale的异质图，为了捕获其异质性，我们设计了节点类型与边类型依赖的参数已使用异质图注意力机制，使模型维护了不同类型节点和边的专用表示。为了应对动态异质图，我们提出了相对时间编码机制来捕捉任意时刻的动态结构依赖性。同时我们设计了异质图mini-batch采样算法HGSampling使模型更高效。多种下游任务表明我们模型超越多个SOTA GNN baseline。

1. Introduction

传统的异质图方法，如PathSim，metapath2vec等都需要通过预先定义meta-path元路径来建模异质结构，而近来也有将GNN应用到异质图中的工作，但他们也有以下问题：

• 大多数GNN也依赖于预先定于元路径，需要专家经验
• 通常这些GNN模型假设所有节点和边特征均属于同一个特征空间，或者为每一种类型设定non-sharing的投射矩阵，导致这些模型无法充分捕捉图上的异质性
• 通常忽略了异质图的动态性
• 没法应用于大规模的异质图中

比如OAG(Open Acadamic Graph)中每个节点和边有着不同的特征分布，比如文章有文本特征(Text Feature))而机构则其特征来自于附属该机构的学者，共同作者关系和引用关系显然不同。OAG明显是在不断演化，比如文章发表数目增长，会议关注点的变更(KDD在1990年与数据库更相关)，OAG的图结构中存在大量的节点数目与边的数目。

考虑到这些问题和挑战，我们提出了异质图神经网络，其实现了如下四个特点：

• 保留节点类型和边类型依赖(node-type dependent)的表示
• 捕捉网络动态性
• 避免预定义元路径
• 可扩展到大规模网络

为了解决图的异质性，我们提出了节点和边类型依赖的注意力机制，模型中所用的异质互注意力(mutual attention) 通过将边$e={s,t}$拆解为元关系三元组$<s节点类型，边类型，t节点类型>$，对这些元关系设置相应的权重矩阵来计算连边上的注意力值，这样每一个不同类型的节点和边都刻意保留其特有的特征空间。与此同时，对于类型不同的节点仍可以在不影响其特征分布的前提下进行传递信息。HGT也可以通过message passing的机制来叠加多层来获得高阶邻居的信息，从某种程度上也是定义了soft meta-path，无需通过预定义元路径，而是利用所提出的注意力机制自动学到隐式元路径服务于下游任务。

同时为了建模图的动态性，我们提出相对时间编码(relative temporal encoding)策略，将不同时刻的所有边全都作为一个整体而不对其基于时间片切分，RTE能够建模任意长度时间下的结构依赖性，并作为到未曾出现的未来时刻。最终，RTE使HGT能自动学习到这种时间依赖于异质图的演变。

同时我们提出HGSampling采样策略以应对大规模的图数据，其核心思想通过采样异质子图使不同类型节点具有相同的比例，而目前的诸如GraphSage, FastGCN, LADIES都会导致一个采样出来的节点类型与边类型 highly imbalanced 的分布。并且HGSampling尽可能使子图紧密使信息得以保留，并可以应用于 arbitrary-size 的异质图。

我们在OAG数据上展现了模型的有效性，该数据集包含1.79亿个节点和20亿条边，并且涵盖了1900到2019年所有的数据（这个规模未曾在异质图使用），实验表明我们的模型比其他SOTA的GNN模型与异质图专用模型效果要好9-21%，并且实验表明该模型可以自动获取隐元路径在不同任务下的权重。

2. PRELIMINARIES

2.1 Heterogeneous Graph Mining

• Heterogeneous Graph：异质图可以定义为一个有向图$G=(\mathcal{V}, \mathcal{E}, \mathcal{A}, \mathcal{R})$，节点$v \in \mathcal{V}$与边$e \in \mathcal{E}$都有对应映射函数 $\tau(v) \colon V \rightarrow \mathcal{A}$与$\phi(e) \colon E \rightarrow \mathcal{R}$。异质图满足$|\tau(v)| + |\phi(e)| >2$。
• Meta Relation：对于任意一条边$e=(s,t)$，其元关系(meta relation)可以定义为$<\tau(s), \phi(e), \tau(t)>$，$\phi(e)^{-1}$则是inverse of $\phi(e)$. 为了更好的建模这种数据之间的异质性，在异质图中假设两个节点之间可以存在多种元关系。
• MetaPath：元路径$\Phi$ 可以理解为由元关系所组成的序列 $\mathcal{A}1 \stackrel{\mathcal{R}_1}{\rightarrow} \mathcal{A}_2 \stackrel{\mathcal{R}_2}{\rightarrow} \cdots \stackrel{\mathcal{R}_L}{\rightarrow} \mathcal{A}{L+1}$ (or $\Phi = \mathcal{A}1 \rightarrow \mathcal{A}_2 \rightarrow \cdots \rightarrow \mathcal{A}{L+1}$)
• Dynamic Heterogeneous Graph： 为了建模图的动态性，我们认为每一条边的时间是固定在，取决于其生成边的时刻，于是可以对每一条边$e=(s,t)$赋予一个时间戳$T$，表明$s$在$T$时刻与$t$相连，而对于节点来说，一个可以赋予多个时间戳，例如WWW@1994就是第一节WWW会议，其主要关注点在 Internet Protocol 和 Web Infrastructure, 而对于WWW@2020来说关注 social analysis, computing search, IR, privacy and society 等等

2.2 Graph Neural Network

2.3 Heterogeneous GNNs

• RGCN: 对每一个边类型设计一个独特的投射矩阵(linear projection weight)
  
• HetGNN: 利用多个RNN对不同类型的节点进行提取信息并融合 multi-model 的信息
  
• HAN: 利用多个attention对通过元路径获得的邻接矩阵进行分别聚合并融合
  

这些模型通常只用节点类型或边类型来设计权重矩阵，但对于出现频率很低的边，很难学习到准确的relation-specific的权重矩阵，所以本文的核心在于参数共享

每条边$e=(s,t)$都有与该边对应的元关系（meta-relation) $<\tau(s), \phi(e), \tau(t)>$，边与边之间存在一定联系，例如：对于“第一作者”与“第二作者”这两种边，其源(source)节点和目标(target)节点均分别为 Author 和 Paper。

3. HETEROGENEOUS GRAPH TRANSFORMER

该模型可以被拆分为四个模块，异质互注意力模块、异质消息传递模块、类型聚集模块、RTE模块

3.1 Heterogeneous Mutual Attention

先基于如下公式进行计算

对于传统图注意力机制GAT

其假设节点处于同一个特征分布，将忽略了异质性，本文我们通过基于元关系$<\tau(s), \phi(e), \tau(t)>$这个三元组，类似于Transformer的结构将目标节点$t$作为Query向量，源节点$s$作为Key向量，同时我们对每一个元关系都有专用的投射矩阵，目的是最大程度的建模分布的差异性

Transformer Attention

Heterogeneous Graph Transformer

传统的Transformer结构利用dot-product进行计算attention系数（Query Vector 和 Key Vector之间的相似度），而本文为了建模边的异质性，则使用edge-specific的矩阵来捕捉不同的语义关系。$\mu_{<\tau(s), \phi(e), \tau(t)>}$可以理解为对该meta-relation的一个权重（学习得到）

3.2 Heterogeneous Message Passing

和上一个模块类似，这里先对每个源节点特征进行投射相应特征空间，然后利用边的权重矩阵进行构建边的依赖性。其实本质思想就是，一个节点特征，首先先过一个节点类型对应的投射矩阵，然后再过相应的边类型对应的投射矩阵，来建立这种节点与边的异质性。

3.3 Target-Specific Aggregation

此时获得到的$\widetilde{H}^{(l)}[t]$是经过源节点类型和边类型矩阵线性组合后的结果

对聚合的信息进行转化成目标节点对应的特征分布，然后一个短路连接汇聚自身信息。

Summary：如果直接那meta-relation每个构造一个矩阵的话，那么参数不能得到共享，明显很多有meta-relation之间相关性都忽视了，而现在这样相同类型共享参数，只是改变了中间关系的投射矩阵，使很多关系数目很少也能得到相应的泛化

3.4 Relative Temporal Encoding

通常构建网络的dynamic性质一般进行时间片切割，对切割的时间片单独作为一个图，但是这样不同时间片上的结构依赖会丢失，并且$T_1$时间的节点表示可能依赖于$T_n$时间片上的边。所以更恰当的做法应当使用一个动态图将所有边进行保留，是不同时间片上的节点和边可以交互。

其中$\Delta T(t,s)=T(t)-T(s)$为相对时间差，$i$表示维度，为了使RTE模块的表示能和节点嵌入相加，使其和$d$(即节点表示维度)相同，每个维度都是不同频率的$sin/cos$构建的正弦曲线（类似于在这个函数上进行采点）

We chose the sinusoidal version because it may allow the model to extrapolate to sequence lengths longer than the ones encountered during training.

4. WEB-SCALE HGT TRAINING

4.1 HGSampling

核心思想就是对目标节点的邻居中每一种类型$\tau$维护一个bucket $B[\tau]$，每次基于各个bucket中的节点的重要性（相关度、采样的概率）进行采相同数目的节点，并且有以下优点：

• 使每种类型的节点和边数目相近
• 使采样获得的子图尽可能紧密（Dense)以减少信息损失，并且可以减少采样方差

4.2 Inductive Timestamp Assignment

引入一些先验信息，异质图中存在一些节点明显具有固定时间戳，如文章取决于发表日期，这类节点作为“事件”节点，也有类似会议节点时间戳应该基于与其相连的事件节点（采样）的时刻。所以对于这种类型节点，其初始时间戳为空，表明其可以与任意时间相连，这样在采样时就可以自适应的获取对应的时间戳。

5 EVALUATION

5.1 Web-Scale Datasets

主要体现数据量数据规模的大

The Field nodes in OAG are categorized into six levels from $L_0$ to $L_5$, which are organized with a hierachical tree.
Claming all these element are differentiated:

• author orders
• venue types
• self-loop
• relation type $\phi$ with an reverse relation type $\phi^{-1}$

5.2 Experimental Setup

任务:

• 三个节点分类任务，Paper-Field(L1)、Paper-Field(L2)、Paper-Venue。分别表示文章属于一级（二级）领域中哪一个、已经文章发表对应的会议。类似DBLP中判断文章的类型(data mining, machine learning, etc)
• 一个链接预测任务，Author Disambiguation，同名作者与其对应论文进行链接预测任务

数据划分

• 训练集 2015年之前
• 验证集 2015-2016年
• 预测集 2016-2019

验证指标

• Mean Reciprocal Rank(MRR)
• Normalized Discounted Cumulative Gain(NDCG)

初始化特征

• paper： 用XLNet预训练title的词向量
• author： 用发表过paper的平均表示
• field、venue、institude：用meta2vec进行预训练获得

对所有同质图的GNN首先将异质节点特征分别过一个线性层，使表示投射到同一个特征空间。

5.3 Experimental Results

从表格中可以看出，HGT模型的效果均好于其他模型，并且所使用的参数也更少，说明利用这个元关系有更好的泛化效果。从消融实验中可以看出对不同的元关系设置相对应的参数矩阵、以及RTE模块均有相应的提升

5.4 Visualize Meta Relation Attention