文章名称

【KDD-2021】【Beijing University of Posts and Telecommunications/Singapore Management University】Pre-training on Large-Scale Heterogeneous Graph

核心要点

文章旨在解决现有图预训练任务只针对同构图的问题，提出了大规模异构图预训练框架PT-HGNN，利用节点级别和子图级别的预训练任务进行对比学习，并将学习到的语义知识和结构特性迁移到下游任务。为了适应大规模数据，作者还提出了基于异构图的Personal PageRank，来增加训练速度。

上节介绍了子图级别的预训练任务，本节继续介绍加速大规模图训练的方法。

研究背景

如前所述，在进行异构图学习是挑战包括，

• 如何在设计方法学习异构图中各类型节点的特征和语义差异，例如节点的出入度差异等。并利用对比是学习将这种特性encode到图节点的向量表示中。
• 如何设计方法快速的学习大规模图数据中的上述特性。

方法细节

方法架构

PT-HGNN的整体框架如下图所示，大致可以分为3个主要的阶段，采用2种预训练任务进行pre-train，

framework of PT-HGNN

针对大图数据的稀疏化

在图数据节点和边的数量比较庞大时。很难将全部数据都拿来进行训练。同时，也会造成更多的噪声和资源浪费。因此，很多方法考虑采用在线或离线的采样方式来缓解这一问题。在线方法一般难以满足（时间）性能需求，更多的方法采用离线采样的方式。Personal PageRank可以帮助寻找图中对目标节点影响比较重要的邻域[1]，然而，PPR只针对于同构图，作者将其扩展到Heterogeneous的场景。

PPR利用节点的出入度和邻接矩阵计算转移概率，以此反映该节点的重要程度。然而，在异构图中，由于类别不同，一些节点天然的具有较高的度，导致不能和其他不同类别的节点相比。如果所有节点放在一起计算转移矩阵，则会导致转移概率存在偏倚的情况。因此，作者利用如下图所示的方法，在固定的关系上计算转移概率矩阵。其中，是一个平滑矩阵（有点类似卷积），是对角阵，对角元素是所有类别是的元素的度。是关系下的邻接矩阵（注意，这个邻接矩阵中只有类型为的节点）。表示的逆关系（也就是说关系是有方向的，作者写了文章，和，文章是作者写的，互为逆关系）。

relational PPR S matrix

显然，上述矩阵乘法计算量非常大。因此作者采用random walk的方法来近似这个计算。具体做法参见代码实现部分。

得到状态转移矩阵，相当于得到了节点间的影响程度，通过从邻接矩阵中选取top-k的连边可以实现对大规模图数据的系数化。具体的公式如下图所示。 可以看到，筛选是利用做的，而筛选的目标是邻接矩阵中的元素（也就是边）

Edge Sparsification

最终，PT-HGNN采用如下图所的目标函数训练模型。

Total Loss

代码实现

基于random walk的PPR方法的伪代码如下图所示。其实，可以理解为通过迭代的方法，不断地减少转移概率的残差。

Relation-Based PPR with Random Walk

文章引用

[1] AleksandarBojchevski,JohannesKlicpera,BryanPerozzi,AmolKapoor,Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. 2020. Scaling graph neural networks with approximate pagerank. In KDD. 2464–2473.

[7] Yuan Fang, Wenqing Lin, Vincent Wenchen Zheng, Min Wu, Kevin Chen-Chuan Chang, and Xiaoli Li. 2016. Semantic proximity search on graphs with metagraph- based learning. In ICDE. 277–288.

[10] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. 2020. Mo- mentum contrast for unsupervised visual representation learning. In CVPR. 9729– 9738.

[27] Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. 2011. Path- Sim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. In VLDB. 992–1003.

[28] Aäron van den Oord, Yazhe Li, and Oriol Vinyals. 2018. Representation Learning with Contrastive Predictive Coding. arXiv preprint arXiv:1807.03748 (2018).

[*1] Pedersen, Lilian, Francisco Rodríguez and Fernando for Secretaria de Transporte Brunstein. “Manual de manejo ambiental y social.” (2007).