概要

Transfomer
- 计算复杂度高
- 无法利用复杂的图结构
GNN
- 固定的结构，WL限制
- 弱的表达能力

针对GNN方面，在传统的MP模型中，下面左右两种图结构无法得到区分

模型

数据预处理

注意力采样机制

作用：扩充了感知范围，使得采样不再局限于邻居

S = X X^{T}

式(1)为自注意力表达式，左端 $S_{i j}$ 可表示 $v_{i}, v_{j}$ 两点见原始语义相似度。此时缺乏图结构信息的，进行如下更改

S = S + α \hat{A} S, \hat{A} = A + I

式(2)相当于对中心点 $v_{i}$ ，对他的邻居与其他各点的相似性进行了吸收。基于 $S$ 可设计采样函数

S e m (v_{i}) = {v_{j} | v_{j} \in V, S (i j) \in t o p - k (S (i :))}

TIP

复杂度显然是 $O (n^{2})$ 的，但由于整个训练过程只处理一次，可以视为数据预处理过，不算入模型复杂度。

位置编码

图结构是不存在天然的节点序列的，为此本文考虑位置编码与以下三个方面有关

最短hop-path
degree
PageRank embedding

TIP

在这里是有疑问的，很多节点的特征例如介数中心性都能够作为学习位置编码的输入信息，Rethinking Graph Transformers with Spectral Attention一文或许给出的位置编码学习方式更可信

S P E (v_{i}) = M L P (p (i, j)) D E (v_{i}) = M L P (d e g_{i}) P R E (v_{i}) = M L P (P_{r} (v_{i}))

对于中心点 $v_{i}$ 和 $v_{j} \in S m p (v_{i})$

h_{i} = C O M B (A G G (x_{i}, S P E (v_{i}, v_{i}), D E (v_{i}), P R E (v_{i}))) h_{j} = C O M B (A G G (x_{j}, S P E (v_{i}, v_{j}), D E (v_{j}), P R E (v_{j})))

TIP

复杂度与最短路算法复杂度有关，在堆数据结构下可进一步优化。

模型架构

Transormer Layer

首先是Transformer层，旨在扩充GNN感知范围使其能够聚合多hop以外的相关节点的信息。
但直接将其应用到整个图上会

无视连通性在整个图上传递信息
计算复杂度本文做了如下改进，以 $v_{i}$ 为中心点为例

I n p u t : H \in R^{N \times d_{i n}} q = h_{i} W_{q} k = H_{i}^{S m p} W_{k} v = H_{i}^{S m p} W_{v} a_{t} = \frac{q K^{T}}{\sqrt{d_{o u t}}} h_{i} = s o f t m a x (a_{t}) v

TIP

矩阵运算下具有复杂度 $K \times d_{o u t} \times N$ ，总体上 $O (k N)$ 。

上式中 $q$ 为 $1 \times d_{o u t}$ ， $k, v$ 为 $k \times d_{o u t}$ ，其中 $k$ 为采样个数，上式可扩展为多头。

GNN

作用：捕捉邻居信息，更好的利用图结构。

h_{M} (v_{i}) = M e s s a g e (h_{k}, \forall v_{k} \in N (v_{i})) h_{i} = C o m b i n e (h_{i}, h_{M} (v_{i}))

TIP

计算复杂度仍然为 $O (k N)$ ，同时既然上文S相似度已被计算出，为何MP过程不利用？

Samples Update Sub-Module

作用：在Trans 和 GNN layers后， S应该得到更新。但重新计算所需要的时间成本昂贵。
本文提出了两种解决方案

Random Walk based Update

设计转移概率

P_{i \to j} = {\begin{cases} \frac{h_{i} h_{j}^{T}}{\sum_{l \in N (v_{i})} h_{i} h_{l}^{T}} i f v_{j} \in N (v_{i}) \\ 0 e l s e \end{cases}

通过控制随机Walk的长度 $L$ 限制复杂度

Message Passing based Update

A t t n_{M} s g (v_{i}) = \cup S m p (v_{j}), \forall v_{j} \in N (v_{i})

对中心点 $v_{i}$ 的所有邻居的采样进行聚合。

理论

TransGNN 至少与 GNN 持平通过控制 $Q, K$ ，可以使得 $H_{o u t} = \frac{1}{\sqrt{d_{o u t}}} H (W_{v} + I) H = σ (A H_{o u t} W) = σ (A \frac{1}{\sqrt{d_{o u t}}} H (W_{v} + I) W) l e t W_{v} = d i a g (\sqrt{d_{o u t} - 1}) H = σ (A H W)$
TransGNN 比 1-WL 更有表现力若感知视野为1,下图中左右图无法区分，至少TransGNN中利用最短路信息不同，故而是可分辨的

概要 ​

模型 ​

数据预处理 ​

注意力采样机制 ​

位置编码 ​

模型架构 ​

Transormer Layer ​

GNN ​

Samples Update Sub-Module ​

Random Walk based Update ​

Message Passing based Update ​

理论 ​

概要

模型