【论文笔记】Heterogeneous Graph Attention Network

$题目：《Heterogeneous$题目：《Heterogeneous $Graph$Graph $Attention$Attention $Network》$Network》 ????
$作者：Xiao$作者：Xiao $Wang$Wang
$来源：WWW2019$来源：WWW2019
$源码：$源码：github addr
$笔记：Hu$笔记：Hu $Hengchang$Hengchang

原文摘自我自己的博客Link：http://holdenhu.site/2020/paper-noteheterogeneous-graph-attention-network/

Intro

---

本文提出的HAN(Heterogeneous Graph Attention Network)涉及到节点级别和语义级别。

• 节点级别的Attention主要学习节点及其临近节点间的权重。
• 语义级别的Attention是来学习基于不同meta-path的权重。

 

Related Work

---

Graph Neural Network
  ​GNN作为深度学习领域的扩展，用来处理无规则图结构数据。主要的信息传播使用卷积，即GCN，可以分为两类：

• 谱方法用于谱表示的图中，代表作Semi-supervised classification with graph convolutional networks
• 非谱域方法直接在图上进行卷积，对空间上的近邻进行操作。代表作大名鼎鼎的GraphSAGE。
   

Attention
注意力机制在深度学习中也有广泛的应用，self-attention、soft-attention等。也已经有很多基于图Attention的应用，但是都是同构图的数据。
但2019年随后的一篇Graph Transformer Networks也是在异构图上的工作,详见我的note。
 

Network Embedding
Network embedding和network representation learning都是在保留图的结构前提下，将网络转换到低位空间(比如推荐系统里常用的user embedding就是压缩到了一维特征值)。而以往的方法比如random walk、matrix factorization都是基于同构图。

 

Contribution

---

现实世界的交互数据往往种类繁多，构成的heterogeneous graph network (HIN)往往特别复杂，GNN不能直接应用。这也几乎是首次将attention机制用到处理meta-path和graph embedding里。

• HAN能解决异构图中多种Node、Relation，以及Semantic融合的问题；
• 该模型能够并行计算；
• 整个模型的Attention是共享的；
• 具有很好的可解释性；

 

Implemention

---

Preliminary

• Heterogeneous Graph
  图可以表示成：
  $\mathcal{G}=(\mathcal{V}, \mathcal{E})$G=(V,E)
  其中$\mathcal{V}$V表示节点集，$\mathcal{E}$E表示边的集合

• 两个映射函数把节点和边映射到他们的种类上去：
  $\phi: \mathcal{V} \rightarrow \mathscr{H}$ϕ:V→H
  $\psi: \mathcal{E} \rightarrow \mathcal{R}$ψ:E→R

• Meta-path的表示：
  $A_{1} \stackrel{R_{1}}{\longrightarrow} A_{2} \stackrel{R_{2}}{\longrightarrow} \cdots \stackrel{R_{l}}{\longrightarrow} A_{l+1}$A1​⟶R1​​A2​⟶R2​​⋯⟶Rl​​Al+1​
  简单来说即是从节点A到节点B所经过的一系列点的序列。

• Meta-path based Neighbors：基于一条meta-path的邻居节点。
  {{<note “// 默认一个节点的邻居节点包括其自身。”>}}

Structure Overview

• 先由Node-level Aggregating讲同一条元路径Φ上的节点根据不同的attention权重聚合起来(这里是简单的求和+**函数)。
  {{<note “// # 注意这里的，node 1、2、3、4都在一条meta path中。这里我觉得有点小小的绘图问题导致歧义。”>}}

• 再由Semantic-level Aggregating将不同元路径的输出通过另一个attention权重*聚合起来（这里聚合方式也是简单的求和）

Node Level Attention

1. Graph中有多种节点，可能对应的hidden feature的最佳表示形式不尽相同。所以先通过转换矩阵将所有节点转换到统一的特征空间。
   $\mathbf{h_i}^{\prime} = \mathbf{M}_{\phi_i} \cdot \mathbf{h}_i$hi​′=Mϕi​​⋅hi​

2. 给定一条元路径$Φ$Φ,以及头节点$i$i和尾节点$j$j，$att_node$attn​ode里包括训练权重计算$j$j对于$i$i的attention值（有方向）
   $e_{i j}^{\Phi}=a t t_{n o d e}\left(\mathbf{h}_{i}^{\prime}, \mathbf{h}_{j}^{\prime} ; \Phi\right)$eijΦ​=attnode​(hi′​,hj′​;Φ)

3. 通过softmax计算出节点$j$j的权重系数
   $\alpha_{i j}^{\Phi}=\operatorname{softmax}_{j}\left(e_{i j}^{\Phi}\right)=\frac{\exp \left(\sigma\left(\mathbf{a}_{\Phi}^{\mathrm{T}} \cdot\left[\mathbf{h}_{i}^{\prime} \| \mathbf{h}_{j}^{\prime}\right]\right)\right)}{\sum_{k \in \mathcal{N}_{i}^{\varphi}} \exp \left(\sigma\left(\mathbf{a}_{\Phi}^{\mathrm{T}} \cdot\left[\mathbf{h}_{i}^{\prime} \| \mathbf{h}_{k}^{\prime}\right]\right)\right)}$αijΦ​=softmaxj​(eijΦ​)=∑k∈Niφ​​exp(σ(aΦT​⋅[hi′​∥hk′​]))exp(σ(aΦT​⋅[hi′​∥hj′​]))​

4. 简单地将$Φ$Φ这条meta-path上邻接的节点的hidden feature根据不同的权重求和，再加上**函数，即得到节点i的更新结果$z_i^Φ$ziΦ​，即结点$i$i对于$Φ$Φ这条路径的embedding。
   $\mathbf{z_i}^{\Phi} = \sigma\left(\sum_{j \in \mathcal{N}_{i}^{\Phi}} \alpha_{i j}^{\Phi} \cdot \mathbf{h}_{j}^{\prime}\right)$zi​Φ=σ⎝⎛​j∈NiΦ​∑​αijΦ​⋅hj′​⎠⎞​

5. 实际考虑到方差大的问题，将Node-level Attention延伸到了Multihead Attention来解决这个问题。将不同head的结果concatenate到一起。
   $\mathbf{z_i}^{\Phi}=||_{k=1}^{K} \sigma\left(\sum_{j \in \mathcal{N}_{i}^{\Phi}} \alpha_{i j}^{\Phi} \cdot \mathbf{h}_{j}^{\prime}\right)$zi​Φ=∣∣k=1K​σ⎝⎛​j∈NiΦ​∑​αijΦ​⋅hj′​⎠⎞​

Semantic Level Attention

有了来自不同元路径的输出$z_i^Φ$ziΦ​, 为了学习到更综合的信息，我们需要根据meta-path将多种语义信息融合到一起。这里还是使用attention机制将来自元路径的信息有效聚合起来。
$\left(\beta_{\Phi_{0}}, \beta_{\Phi_{1}}, \ldots, \beta_{\Phi_{P}}\right)=\operatorname{att}_{\operatorname{sem}}\left(Z_{\Phi_{0}}, Z_{\Phi_{1}}, \ldots, Z_{\Phi_{P}}\right)$(βΦ0​​,βΦ1​​,…,βΦP​​)=attsem​(ZΦ0​​,ZΦ1​​,…,ZΦP​​)
{{<note “// 这里β是不同元路径对应的attention重要度参数。”>}}

• β的计算方法：

  1. 要学习每条语义的权重，论文首先使用一层的MLP将Semantic embedding进行非线性转换。通过Semantic-level Attention vector $q$q 来衡量多条Semantic embedding 间的相似性。
     $w_{\Phi_{i}}=\frac{1}{|\mathcal{V}|} \sum_{i \in \mathcal{V}} \mathbf{q}^{\mathrm{T}} \cdot \tanh \left(\mathbf{W} \cdot \mathbf{z}_{i}^{\Phi}+\mathbf{b}\right)$wΦi​​=∣V∣1​i∈V∑​qT⋅tanh(W⋅ziΦ​+b)
     {{<note “// 这里W是MLP的weight matrix，b是bias，q是attention vector。”>}}
  2. ​ 经过Softmax函数，得到语义权重。
     $\beta_{\Phi_{i}}=\frac{\exp \left(w_{\Phi_{i}}\right)}{\sum_{i=1}^{P} \exp \left(w_{\Phi_{i}}\right)}$βΦi​​=∑i=1P​exp(wΦi​​)exp(wΦi​​)​

• 最后的汇总得到的embedding也是通过简单的求和：
  $\mathrm{Z}=\sum_{i=1}^{P} \beta_{\Phi_{i}} \cdot \mathrm{Z}_{\Phi_{i}}$Z=i=1∑P​βΦi​​⋅ZΦi​​

Training

Loss function:

{{<note “//使用Cross-Entropy将-ln求和”>}}
$L=-\sum_{l \in \mathcal{Y}_{L}} \mathrm{Y}^{l} \ln \left(\mathrm{C} \cdot \mathrm{Z}^{l}\right)$L=−l∈YL​∑​Ylln(C⋅Zl)
这里$\mathcal{Y}_{L}$YL​表示有label的结点集；$\mathrm{Y}^{l}$Yl表示真实输出，即label；$\mathrm{Z}^{l}$Zl表示通过本论文方法得出的embedding值；$C$C表示分类器，来根据embedding值分类结点。

Evaluation

---

研究问题:

• Q1：GTN生成的新图结构对学习node representation是否有效？
• Q2：GTN能否根据数据集自适应地产生可变长度的元路径？
• Q3：如何从GTNs生成的邻接矩阵来解释每个元路径的重要性？

Dataset

​ 实验过程用到了DBLP、ACM、IMDB三个数据集。

Baselines

​Baseline包括：

• 传统算法：DeepWalk、Esim、metapath2vec
• GNN经典模型：GCN、GAT
• 本文模型：HAN of Node、HAN of Semantic、HAN
  
  从分类、聚类的实验结果来看，HAN(Attention of Node + Semantic)基本上都是最优的。

 

Process Pseudocode

---