Structure-Aware Transformer for Graph Representation Learning

Structure-Aware Transformer for Graph Representation Learning

在图表示学习领域内

首先，在计算注意力之前，通过生成专属于每个节点的子图表示来捕捉其结构性特征，并将其与原始的自我注意力机制进行融合以构建一种增强型的关注力机制。这种设计旨在更好地捕捉复杂网络中的微粒化模式和宏观组织特征之间的关系。

优点：可以利用任何现有的GNN来提取子图表示。

GNN的主要不足表现为over-smoothing和over-squashing两种现象。
绝对编码主要通过向输入节点特征注入位置信息或结构信息。
相对编码则通过将图上节点间的相对位置关系融入注意力机制实现表征。
作者所提出的SAT方案巧妙地整合了消息传递模型与Transformer架构的优势。
其创新性地综合运用了绝对编码与创新性的相对编码方案。
这种编码体系巧妙地融合了图结构特征进而构建了一种既能关注局部又能兼顾全局信息处理能力的Transformer架构。
由自注意力机制模块与前馈神经网络构成。
其核心组件中的自注意力机制模块主要负责特征提取与关系建模。

通过自注意力机制建立后继联系，在其之后是一个由 skip-connection 和 feed-forward network 组成的模块。该模块共同构成了整个 Transformer 架构的基础组成部分。

Transformer始终会为所有属性相同的节点生成一致的表示向量，并不受其所在位置及周边结构的影响；因此，在实际应用中通常需要结合结构编码机制来整合这些信息到Transformer模型中。
在Transformer架构中自注意力机制（self-attention）能够被重新表述为一种内核平滑器（kernel smoother）。其中kernel是一种通过节点特征定义并经过训练优化得到的指数型内核：

k=\sum_{i=1}^n f(\mathbf{x}_i)

他主要关注于节点对间属性相似性的识别。在某些情况下（即当节点具有相同或相似的特征时），该kernel smoother无法筛选出与目标节点结构上存在差异的节点。

以上是背景信息，下面开始对提出作者的思想：SAT

为了消除上述现有算法的不足, 作者提出了基于结构感知注意力机制的新模型

其中：

这种新的注意力函数能够考虑子图之间的结构相似性。这种自我注意力不再等同与节点的任何排列，而只等同于特征和子图重合的节点。该方法假设没有边属性，但只要结构提取器能够容纳边属性，该方法就可以很容易地合并边属性。
在本文中，作者提出了两种结构提取器：
k-subtree GNN extractor:

k-subgraph GNN extractor:

在结构感知注意力机制中使用的子图表示被设计为量化评估节点之间结构相似性的情况；当这些节点具备相同的属性特征及其周边拓扑结构时，在该层机制下将能够生成对应的节点级特征表达。
SAT的主要缺陷在于其与Transformer共享同样的自我注意力计算复杂度问题；具体而言，在机制层面而言这会导致较高的时间复杂度。