- 1基于STM32的智能换气除湿杀菌鞋柜_基于stm32的智能鞋柜
- 2微信小程序之音乐播放器_微信小程序音乐播放器
- 3Kafka 保证消息的不丢失_怎么样确保kafka消息不丢失
- 4Mysql事务隔离MVCC机制_mvcc机制是如何保证事务的隔离性的?
- 5人脸识别方法的研究_gabor特征人脸识别国外研究现状
- 6修改hosts文件，提高访问github的速度（github外网的登录问题）_github hosts
- 7usage of algorithm
- 8stm32开发三、单片机关键字extern
- 9读入一个小于10 的整数n，输出它的阶乘n!_2.输入一个小于10的正整数n,输出n的阶乘。
- 10[网络安全自学篇] 十.论文之基于机器学习算法的主机恶意代码_恶意代码 顶级论文
Graph上的Transformer：Graphormer_graph transformer
赞
踩
这个工作来自：Do transformers really perform badly for graph representation，Nips2021，名为Graphormer。Graphormer包含3个主要embedding：centrality encoding， spatial encoding，edge encoding。
centrality encoding
Graphormer认为节点的向心性（centrality）是图学习的重要信号，因此需要设计一个方法表示向心性并结合到Transformer中。使用图的出度和入度表示节点的向心性：
h
i
(
0
)
=
x
i
+
z
d
e
g
−
(
v
i
)
−
+
z
d
e
g
+
(
v
i
)
+
h_{i}^{(0)}=x_{i}+z^{-}_{deg^{-}(v_{i})}+z^{+}_{deg^{+}(v_{i})}
hi(0)=xi+zdeg−(vi)−+zdeg+(vi)+其中，
z
−
,
z
+
∈
R
d
z^{-},z^{+}\in\mathbb{R}^{d}
z−,z+∈Rd为入度
d
e
g
−
(
v
i
)
deg^{-}(v_{i})
deg−(vi)和出度
d
e
g
+
(
v
i
)
deg^{+}(v_{i})
deg+(vi)的可学习embedding。对于无向图，
d
e
g
−
(
v
i
)
deg^{-}(v_{i})
deg−(vi)和
d
e
g
+
(
v
i
)
deg^{+}(v_{i})
deg+(vi)可以统一为
d
e
g
(
v
i
)
deg(v_{i})
deg(vi)。
spatial encoding
Transformer的一大优势就是具有全局感受野。对于序列信息来说，为了获得序列中的空间信息，通常Transformer会引入Position embedding来编码序列中的空间信息。然而对于图结构来说，节点并没有组织成序列。为了在模型中编码图的空间信息，Graphormer提出了Spatial Encoding。
对于图 G G G，考虑函数 ϕ ( v i , v j ) \phi(v_{i},v_{j}) ϕ(vi,vj)衡量了图 G G G中节点 v i v_{i} vi与 v j v_{j} vj的空间关系。Graphormer使用shortest path distance (SPD) 来衡量两个相连节点之间的距离 ϕ ( v i , v j ) \phi(v_{i},v_{j}) ϕ(vi,vj)。如果两个节点不相连，则 ϕ = − 1 \phi=-1 ϕ=−1。引入spatial encoding后的Query-Key相似矩阵元素 A i j A_{ij} Aij为： A i j = ( h i W Q ) ( h j W K ) d + b ϕ ( v i , v j ) A_{ij}=\frac{(h_{i}W_{Q})(h_{j}W_{K})}{\sqrt{d}}+b_{\phi(v_{i},v_{j})} Aij=d (hiWQ)(hjWK)+bϕ(vi,vj)其中， b ϕ ( v i , v j ) b_{\phi(v_{i},v_{j})} bϕ(vi,vj)为 ϕ ( v i , v j ) \phi(v_{i},v_{j}) ϕ(vi,vj)索引的可学习的标量，在所有Layer上共享。
edge encoding
对于每个节点对
(
v
i
,
v
j
)
(v_{i},v_{j})
(vi,vj)，我们找到
(
v
i
,
v
j
)
(v_{i},v_{j})
(vi,vj)的最短路径：
S
P
i
j
=
(
e
1
,
e
2
,
.
.
.
,
e
N
)
SP_{ij}=(e_{1},e_{2},...,e_{N})
SPij=(e1,e2,...,eN)，然后计算沿路径的edge feature与可学习的embedding的点积的平均值：
A
i
j
=
(
h
i
W
Q
)
(
h
j
W
K
)
d
+
b
ϕ
(
v
i
,
v
j
)
+
c
i
j
A_{ij}=\frac{(h_{i}W_{Q})(h_{j}W_{K})}{\sqrt{d}}+b_{\phi(v_{i},v_{j})}+c_{ij}
Aij=d
(hiWQ)(hjWK)+bϕ(vi,vj)+cij其中：
c
i
j
=
1
N
∑
n
=
1
N
x
e
n
(
w
n
E
)
⊤
c_{ij}=\frac{1}{N}\sum_{n=1}^{N}x_{e_{n}}(w_{n}^{E})^{\top}
cij=N1n=1∑Nxen(wnE)⊤其中，
x
e
n
x_{e_{n}}
xen是在路径
S
P
i
j
SP_{ij}
SPij中的第
n
n
n个edge feature，
w
n
E
∈
R
d
E
w_{n}^{E}\in\mathbb{R}^{d_{E}}
wnE∈RdE为第
n
n
n个可学习的embedding。
额外的：Special Node
Graphormer基于Transformer实现，为了更好地表示图的整体信息，还添加了一个节点，名为
[
V
N
o
d
e
]
[VNode]
[VNode]，并将
[
V
N
o
d
e
]
[VNode]
[VNode]与其他节点独立连接，这类似于BERT中的
[
C
L
S
]
[CLS]
[CLS]。
总结
Graphormer利用Transformer带有全局感受野的自注意力结构，并引入三种空间编码方式来弥补Transformer感知图结构能力的不足。
