Structure-Aware Transformer for Graph Representation Learning（ICML22）
摘要
Transformer 架构最近在图表示学习中受到越来越多的关注，因为它通过避免严格的结构归纳偏差而仅通过位置编码对图结构进行编码，自然地克服了图神经网络（GNN）的一些限制。 在这里，我们表明由 Transformer 使用位置编码生成的节点表示不一定捕获它们之间的结构相似性。 为了解决这个问题，我们提出了 Structure-Aware Transformer，这是一类基于新的自注意力机制的简单而灵活的图形 Transformer。 这种新的自注意力通过在计算注意力之前提取以每个节点为根的子图表示，将结构信息合并到原始自注意力中。 我们提出了几种自动生成子图表示的方法，并从理论上证明所得到的表示至少与子图表示一样具有表现力。
介绍
Transformers (Vaswani et al., 2017)，已被证明在自然语言理解 (Vaswani et al., 2017)、计算机视觉 (Dosovitskiy et al., 2020) 和生物序列建模 (Rives et al., 2020) 方面取得了成功。 2021），提供了解决这些问题的潜力。
Transformer 架构不仅仅在消息传递机制中聚合本地邻域信息，而是能够通过单个自注意力层捕获任何节点对之间的交互信息。 此外，与 GNN 相比，Transformer 避免在中间层引入任何结构归纳偏差，从而解决了 GNN 的表达能力限制。 相反，它将有关节点的结构或位置信息仅编码为输入节点特征，尽管限制了它可以从图结构中学习的信息量。 因此，将有关图结构的信息集成到 Transformer 架构中在图表示学习领域获得了越来越多的关注。 然而，大多数现有方法仅对节点之间的位置关系进行编码，而不是对结构关系进行显式编码。 因此，它们可能无法识别节点之间的结构相似性，并且可能无法对节点之间的结构交互进行建模。
上图中节点u，v的位置编码是相同的，因为这两个节点到相邻节点的最近距离都相同，可是他们的结构编码是不同的。
本文贡献
本文引入一种灵活的结构感知自注意力机制，该机制明确考虑图结构，从而捕获节点之间的结构交互。 由此产生的 Transformer 类，我们称之为结构感知 Transformer (SAT)，可以提供图的结构感知表示，这与大多数现有的用于图结构数据的位置感知 Transformer 不同。
- 重新表述了 Vaswani 等人的自注意力机制。 （2017）作为内核平滑器，并通过提取以每个节点为中心的子图表示，扩展节点特征上的原始指数内核以也考虑局部结构。
- 提出了几种自动生成子图表示的方法，使生成的内核更平滑，能够同时捕获节点之间的结构和属性相似性。 理论上保证得到的表示至少与子图表示一样具有表达能力。
背景
输入交互图和用户和物品的嵌入表示X。
基于transformer的图
再经过残差链接和前馈网络
绝对编码
绝对编码是指在主Transformer模型之前，将图形的位置或结构表示添加或连接到输入节点特征，例如拉普拉斯位置编码（Dwivedi & Bresson，2021）或RWPE（Dwivedi等人，2022年）的报告。这些编码方法的主要缺点是，它们通常不提供节点与其邻域之间的结构相似性的度量。
自注意作为核平滑
结构感知Transformer
1. 结构感知自注意力
采用上述的自注意作为核平滑，公式如下：
此处的注意力计算方式不再是单个节点的嵌入，而是这个节点构成的子图。
kgraph核函数是两个子图嵌入的点积，子图的抽取如下：
- k-subtree GNN extractor
简而言之：将用户物品嵌入通过k层GNN最终获取节点u的嵌入，即时u的k-subtree（子图）
- k-subgraph GNN extractor
简而言之：将节点u的所有邻居的k-subtree相加就是节点u的k-subgraph
结构感知Transformer
