论文笔记-HGT Heterogeneous graph transformer

核心思想:利用异构图的元关系来参数化异构相互注意力、消息传递和传播步骤的权重矩阵,从而获取不同类型节点的表示。

Hu Z, Dong Y, Wang K, et al. Heterogeneous graph transformer[C]//Proceedings of The Web Conference 2020. 2020: 2704-2710.

方法介绍

网络聚合算子

总体结构

输入一个异构网络,HGT利用所有节点对,(源节点 s,关系类型 e,目标节点 t ),其目标是汇聚目标节点t的各个源节点s的上下文表示信息,计算出t的表示。分为3个部分:Heterogeneous Mutual Attention,Heterogeneous Message Passing , Target-Specific Aggregation

  • Attention: 计算每一个源节点s相对于目标节点t的重要性
  • Message:抽取源节点s的信息
  • Aggregate:聚合目标节点每一个源节点的信息

步骤一:Heterogeneous Mutual Attention

  • 首先,计算目标节点t 和 源节点s 的 mutual attention。

  • 与 Transformer 核心区别是,Transformer对所有的word都用了同一个 projections ,而HGT对每一种边类型(meta relation)都使用了不同的 projection weights.

步骤二:Heterogeneous Message Passing

  • 将信息从源节点传递到目标节点,同时在消息传递过程中加入边的元关系,以处理不同类型的节点和边的分布差异。

步骤三:Target-Specific Aggregation

  • 这一过程将以上的异构相互注意力Attention和异构信息Message进行Product再Add,从本质来看,这个操作的目的是将异构注意力和消息从源节点聚合到目标节点。

  • 然后上面得到的结果经过一个激活层,再做线性变换并做一个残差连接:

mini-bach子图采样 HGSampling

为了适应大规模网络,必须要对网络进行采样。如果不采样的话,就需要把整个图塞到GPU里面去计算,因此大规模网络是不适用的。本人尝试使用了DGL框架的HGT方法,在1080Ti的GPU上,不使用图采样,仅能够支持万级别的节点和几十万条边的网络规模,再往大,显存就不够用了。

此论文提出一种适用于异构图的子图采样方法HGSampling,该方法,1、保证每一种类型的节点和边都有相似的数量,2、保证采样后的子图是稠密的,从而达到最小化的信息损失和减少采样带来的偏差。

算法1展示了采样的主过程,其主要思想是每个节点类型τ保留一个单独的节点Budget B[τ],使用重要性采样策略对每种类型采样相同数量的节点。当某一节点t已经被采样,我们将它的所有邻居加入预备采样集合中(算法2),使用归一化的度数去计算采样概率,类似于随机游走。