Do Transformers Really Perform Bad for Graph Representation

Motivation

• 原有将 transformer 应用于图的效果并不好

• 节点重要性，图结构性信息往往在目前的工作中被忽略

Thinking

• 为什么 GNN 效果不好

  • GNN 网络不能做的到很深，GNN 的一层本质上是在根据邻居节点的信息融合，层数过大会导致特征的趋同，反而丢失特征信息 oversmoothing，因此导致了感受野和趋同化的冲突

  • 有相关文章证明图网络无法处理部分同构图，也进而证明 GNN 的表征能力并不高

• 自然语言/图片是一种结构简单的图结构

  • 自然语言可作为句中节点都是一进一出的有向图

  #自然语言在 Transformer 中加入了 1D 的 position embedding

  • 图片可以是一个只有四个方向连接的图

  #图片（VIT）加入了 2D 的 position embedding

  • 同时有许多工作证明位置信息对 Transformer 的性能起很大作用

    #因此需要加入有关图结构信息的 embedding 作为辅助信息，本文加入了 Spatial，edge 和 centrality 三种结构性信息

Method

• Structural Encoding

  • Centrality Encoding

    关注节点重要性信息对图予以理解的影响

    • 利用度的大小作为节点重要性的度量

    h_i^{(0)}=x_i+z_{\deg^{-}(v_i)}^-+z_{\deg^{+}(v_i)}^+

    二者分别是可学习的由入度和出度决定的嵌入，在无向图中二者合并为一个向量并由度的大小决定

  • Spatial Encoding

    关注节点之间的空间位置关系

    • 利用最短路径的大小作为两个节点的空间位置关系度量，如果不相连则将该值设为-1，并未每个距离设置一个可学习的标量

    A_{ij}=\frac{(h_iW_Q)(h_jW_K)^T}{\sqrt{d}}+b_{\phi(v_i,v_j)}

  • Edge Encoding

    关注边特征的重要性

    • 注意力机制管制节点对之间的相关性，连边的特征和这种相关性有一定的表征关系

    • 对一个节点对找到一个最短传播路径，计算路径上所有边特征与一个可学习 embedding 点积的均值作为另一个偏置项

    \begin{aligned}A_{ij}=\frac{(h_iW_Q)(h_jW_K)^T}{\sqrt{d}}+b_{\phi(v_i,v_j)}+c_{ij},\text{ where }c_{ij}=\frac{1}{N}\sum_{n=1}^Nx_{e_n}(w_n^E)^T\end{aligned}

Details

• Graphformer Layer

  将归一化利用于多自注意力之前，FFN 层隐层神经元数量设置为等同于输入输出层的数量即嵌入维度大小 D

  \begin{aligned}h^{'(l)}&=\text{MHA}(\text{LN}(h^{(l-1)}))+h^{(l-1)}\\h^{(l)}&=\text{FFN}(\text{LN}(h^{'(l)}))+h^{'(l)}\end{aligned}

• Special Node

  • 加入了一个与所有节点相连的初始化节点 ，类似[CLS]

  • 最终这个节点的特征视为全图的特征向量表征

  • 同时，将这个节点与其他节点的空间编码 b_{\phi(v_i,v_j)} 重置为一个不同的可学习参数

‍