Hierarchical Transformer for Scalable Graph Learning

Hierarchical Transformer for Scalable Graph Learning(HSGT) [IJCAI 2023]

1.在什么场景下研究的什么问题(研究背景、目前存在的问题) 2.为什么要研究这个问题(研究的意义、目的) 3.怎么研究的，为什么(研究动机) 4.模型解决了什么问题，又带来了什么问题？

• 研究背景

  尽管目前Graph Transformer取得了不小的进展，但是几乎都是关注小规模的图，global self-attention机制的平方复杂度导致在处理大规模图时采用full batch training是困难的。除此以外，传统的sampling-based方法无法捕获high-level的上下文信息导致了部分性能的损失。

  因此作者由此出发，提出了层级可扩展的Graph Transformer(Hierarchical Scalable GT)。HSGT的成功将Transformer架构完全扩展到大规模图上的节点表示学习任务，同时保持高性能。通过利用coarsening technique构建的图层次结构(上图最左图)，HSGT在不同级别上有效地更新和存储节点嵌入中的多尺度信息。与基于采样的训练方法一起，HSGT仅使用Transformer块就可以有效地捕获和隔离层次图上的多级信息。经验评估表明，HSGT在大规模基准测试上实现了最先进的性能，图中包含数百万个节点，效率很高.

• HSGT – Step 1

  

  ① 如上图所示，首先输入一个large-scale的图，通过coarsening technique构建Graph Hierarchies。Graph coarsening可以看做用一个满射函数，将$G^0 = (V^0, E^0)$映射成$G^1 = (V^1, E^1)$ ，以此类推。$G^1$要能够捕获$G^0$必要的子结构(substructure)，且$

  V^1

  \ll

  V^0

  ,

  E^1

  \ll

  E^0

  $。

• HSGT – Step 2

  

  在每一个Horizontal Block里，对节点表征进行聚合和变换，这样就能得到在每个节点在该层的表征。Horizontal Block的聚合和变换如下式子所示：

  

  

  其中B是基于shortest path distance的bias 矩阵(From Graphormer)。

  在每一个Vertical Block里，第L+1层的节点v，由L层映射成节点v的那些节点的表征经过Transformer得到，表示如下：

  

  Vertical Block这种聚合模式允许每个融合表示 hv 在其相应的low-level子结构上包含有意义的信息，帮助下一个Horizontal Block实现更好的high-level 知识交换。 总的来说horizontal & vertical的协同作用可以概括为：在每个层次结构(Hierarchical layer)中，一个水平块首先在每个节点的局部上下文中交换和转换信息，然后如果存在更高的层，则执行一个垂直块来自适应地合并每个子结构。

• HSGT – Step 3

  

  在horizontal和vertical block交互完以后，通过一个Readout Block对每一层的节点表征执行Transformer，最后得到每一个节点最终的表征，数学符号表示如下：

  

• 实验部分

  本文实验部分主要是针对节点分类任务，在各个不同scale的图上进行了实验。

• 总结：本文通过构建Graph Hierarchies，使得HSGT在大规模图上也能很好的捕获到high-level的上下文信息（但是HSGT应该还是平方复杂度）。在HSGT中，Horizontal&Vertical这种信息交互方式是新颖的，且在最后的Readout Block中，Layer是固定的，不会导致输入Transformer的序列过长。(这种架构理论上来说是合理的，作者只在节点分类上做应该也是考虑到复杂度的问题吧，不然应该可以推广到edge-level和graph-level的任务)