《第7章-GNN的变体和框架》学习笔记
第7章-GNN的变体和框架
7.1 GraphSAGE
GraphSAGE是对初始GCN模型的改进版本。
最最主要的贡献是采用了小批量训练方式(mini-batch)。为了适应小批量的方式,模型对聚合操作也进行了改进和拓展。
7.1.1 采样邻居
全图的训练方式(full-batch)对大规模的图数据来说并不适用,会使得训练代价很高。
GraphSAGE对邻居进行随机采样来控制运算时节点
k
k
k阶子图的数据规模,在此基础上对子图进行随机组合来完成小批量训练。
7.1.2 聚合邻居
GraphSAGE提出了几种新的聚合操作(aggregator):
(1)mean/sum aggregator
A
g
g
s
u
m
=
σ
(
S
U
M
{
W
h
j
+
b
,
∀
v
j
∈
N
(
v
i
)
}
)
Agg^{sum}=\sigma(SUM\{Wh_j+b,\forall v_j\in N(v_i)\})
Aggsum=σ(SUM{Whj+b,∀vj∈N(vi)})
(2)max aggregator
A
g
g
m
a
x
=
M
A
X
{
σ
(
W
h
j
+
b
)
,
∀
v
j
∈
N
(
v
i
)
}
Agg^{max}=MAX\{\sigma(Wh_j+b),\forall v_j\in N(v_i)\}
Aggmax=MAX{σ(Whj+b),∀vj∈N(vi)}
7.1.3 GraphSAGE算法过程
实际实现的时候应该分为2步走。
(1)首先将小批量集合
β
\beta
β内中心节点的
k
k
k阶子图一次性都遍历出来。
(2)聚合邻居节点,然后与上一层的特征进行拼接,最后再进行归一化处理。
GraphSAGE完全没有用到 L L L或 L ~ s y m \tilde L_{sym} L~sym,节点的特征学习仅与其 k k k阶邻居有关,可以进行归纳学习(Inductive Learning)。这样,对于新节点的加入来说十分方便,这也是随机游走等方法不具备的优势。
7.2 GAT
图注意力网络(GAT)通过注意力机制(Attention Mechanism)对邻居节点进行聚合操作,实现了对不同邻居权重的自适应分配。
7.2.1 注意力机制
注意力机制的核心在于对给定信息进行权重分配。注意力机制的定义,
A
t
t
e
n
t
i
o
n
(
Q
u
e
r
y
,
S
o
u
r
c
e
)
=
∑
s
i
m
i
l
a
r
i
t
y
(
Q
u
e
r
y
,
K
e
y
i
)
⋅
V
a
l
u
e
i
Attention(Query,Source)=\sum similarity(Query,Key_i)\cdot Value_i
Attention(Query,Source)=∑similarity(Query,Keyi)⋅Valuei
其中
S
o
u
r
c
e
Source
Source为信息源,
Q
u
e
r
y
Query
Query为先验信息,信息一般通过
(
K
e
y
−
V
a
l
u
e
)
(Key-Value)
(Key−Value)的形式表示出来,
s
i
m
i
l
a
r
i
t
y
(
Q
u
e
r
y
,
K
e
y
i
)
similarity(Query,Key_i)
similarity(Query,Keyi)为相关度函数,注意力机制就是对所有的
V
a
l
u
e
Value
Value加权求和。
7.2.2 图注意力层
类比之前的注意力机制,节点
v
i
v_i
vi在第
l
l
l层的特征向量为
h
i
∈
R
d
(
l
)
h_i\in R^{d^{(l)}}
hi∈Rd(l),经过图注意力层(GAL)进行聚合操作之后,输出新的特征向量
h
i
′
∈
R
d
(
l
+
1
)
h'_i\in R^{d^{(l+1)}}
hi′∈Rd(l+1)。
定义为,
e
i
j
=
L
e
a
k
y
R
e
L
U
(
a
T
[
W
h
i
∣
∣
W
h
j
]
)
e_{ij}=LeakyReLU(a^T[Wh_i||Wh_j])
eij=LeakyReLU(aT[Whi∣∣Whj])
其中
e
i
j
e_{ij}
eij为权重系数,选择单层全连接层作为相似度函数。
α
i
j
=
s
o
f
t
m
a
x
j
(
e
i
j
)
=
e
x
p
(
e
i
j
)
∑
v
k
∈
N
(
v
i
)
e
x
p
(
e
i
k
)
\alpha_{ij}=softmax_j(e_{ij})=\frac{exp(e_{ij})}{\sum_{v_k\in N(v_i)}exp(e_{ik})}
αij=softmaxj(eij)=∑vk∈N(vi)exp(eik)exp(eij)
其中
α
i
j
\alpha_{ij}
αij为权重系数,进行归一化处理。
h
i
′
=
σ
(
∑
v
j
∈
N
(
v
i
)
α
i
j
W
h
j
)
h'_{i}=\sigma(\sum_{v_j\in N(v_i)}\alpha_{ij}Wh_{j})
hi′=σ(vj∈N(vi)∑αijWhj)
进行加权平均后,
h
i
′
h'_{i}
hi′为节点新的特征向量。
7.2.3 多头图注意力层
多头注意力机制(multi-head attention)就是调用 K K K组相互独立的注意力机制,然后将结果进行拼接或者平均操作。
h
i
′
=
∣
∣
k
=
1
K
σ
(
∑
v
j
∈
N
(
v
i
)
α
i
j
(
k
)
W
(
k
)
h
j
)
h'_{i}=||_{k=1}^K \sigma(\sum_{v_j\in N(v_i)}\alpha_{ij}^{(k)}W^{(k)}h_{j})
hi′=∣∣k=1Kσ(vj∈N(vi)∑αij(k)W(k)hj)
其中
∣
∣
||
∣∣为拼接操作。
增加多组相互独立的注意力机制,可以注意到节点之间的多处相关特征,使得系统的学习能力更加强大。
图的注意力机制模型比GCN多了一个新的可学习维度——边上的权重系数。
X
′
=
(
A
~
⨀
M
)
X
W
X'=(\tilde A\bigodot M)XW
X′=(A~⨀M)XW
其中权重矩阵
M
∈
R
N
×
N
M\in R^{N\times N}
M∈RN×N,就是将GCN中的
L
~
s
y
m
\tilde L_{sym}
L~sym换成了
(
A
~
⨀
M
)
(\tilde A\bigodot M)
(A~⨀M),使得图注意力模型有着很高的表达能力。
7.3 R-GCN
之前的模型没有考虑节点之间不止一种关系的异构图,解决方法就是使用R-GCN。
相比于GCN的聚合操作,R-GCN又增加了一个聚合关系的维度,
h
i
(
l
+
1
)
=
σ
(
∑
r
∈
R
∑
v
j
∈
N
v
i
(
r
)
1
c
i
,
r
W
(
l
)
h
j
(
l
)
+
W
o
(
l
)
h
i
(
l
)
)
h_{i}^{(l+1)}=\sigma(\sum_{r\in R}\sum_{v_j\in N_{v_i}^{(r)}}\frac {1}{c_{i,r}}W^{(l)}h_{j}^{(l)}+W_o^{(l)}h_i^{(l)})
hi(l+1)=σ(r∈R∑vj∈Nvi(r)∑ci,r1W(l)hj(l)+Wo(l)hi(l))
其中
W
r
W_r
Wr是具有
r
r
r关系的邻居所对应的权重矩阵,
W
o
(
l
)
h
i
(
l
)
W_o^{(l)}h_i^{(l)}
Wo(l)hi(l)对应着节点的自连接,
1
c
i
,
r
\frac {1}{c_{i,r}}
ci,r1用于归一化。
R-GCN共有2层聚合操作:
(1)第1层先对同种关系进行单独聚合
(2)第2层进行总聚合,还考虑了自连接的关系
为了避免过拟合,R-GCN提出了对
W
r
W_r
Wr进行基分解的方法,
W
r
=
∑
b
=
1
B
a
r
b
V
b
W_r=\sum_{b=1}^B a_{rb}V_b
Wr=b=1∑BarbVb
其中
V
b
V_b
Vb是基,它的优化是所有关系都共享的,可有效防止过拟合。
a
r
b
a_{rb}
arb是分解系数,以上两个是取代
W
r
W_r
Wr学习的参数。
7.4 GNN的通用框架
GNN的通用框架主要分为3类:
(1)消息传播神经网络(MPNN)
(2)非局部神经网络(NLNN)
(3)图网络(GN)
7.4.1 MPNN
MPNN的基本思路是通过消息函数和更新函数进行消息传播,对于节点
v
i
v_i
vi特征向量的更新可以表示为,
m
i
(
k
+
1
)
=
∑
v
j
∈
N
(
v
i
)
M
(
k
)
(
h
i
(
k
)
,
h
j
(
k
)
,
e
i
j
)
h
i
(
k
+
1
)
=
U
(
k
)
(
h
i
(
k
)
,
m
i
(
k
+
1
)
)
m_i^{(k+1)}=\sum_{v_j\in N(v_i)}M^{(k)}(h_i^{(k)},h_j^{(k)},e_{ij}) \\[2ex] h_i^{(k+1)}=U^{(k)}(h_i^{(k)},m_i^{(k+1)})
mi(k+1)=vj∈N(vi)∑M(k)(hi(k),hj(k),eij)hi(k+1)=U(k)(hi(k),mi(k+1))
消息传播一般对应于模型中的层。MPNN的核心是消息函数
M
M
M和更新函数
U
U
U,之前的GCN、R-GCN和GraphSAGE都可以看作是MPNN的特例。
7.4.2 NLNN
NLNN是注意力机制的一般化总结,使用non-local操作对邻居节点进行加权求和,
h
i
′
=
1
c
(
h
)
∑
∀
j
f
(
h
i
,
h
j
)
⋅
g
(
h
j
)
h'_i=\frac{1}{c(h)}\sum_{\forall j}f(h_i,h_j)\cdot g(h_j)
hi′=c(h)1∀j∑f(hi,hj)⋅g(hj)
一般另,
g
(
h
j
)
=
W
g
h
j
g(h_j)=W_gh_j
g(hj)=Wghj
相似度函数
f
f
f则有以下函数可供选择。
(1)内积
f
(
h
i
,
h
j
)
=
θ
T
(
h
i
)
ϕ
(
h
j
)
f(h_i,h_j)=\theta^T(h_i)\phi(h_j)
f(hi,hj)=θT(hi)ϕ(hj)
其中
θ
(
h
i
)
\theta(h_i)
θ(hi)和
ϕ
(
h
j
)
\phi(h_j)
ϕ(hj)都代表某种线性变换。
(2)全连接层
f
(
h
i
,
h
j
)
=
σ
(
a
T
[
θ
(
h
i
)
∣
∣
ϕ
(
h
j
)
]
)
f(h_i,h_j)=\sigma(a^T[\theta(h_i)||\phi(h_j)])
f(hi,hj)=σ(aT[θ(hi)∣∣ϕ(hj)])
(3)高斯函数
f
(
h
i
,
h
j
)
=
e
θ
T
(
h
i
)
ϕ
(
h
j
)
f(h_i,h_j)=e^{\theta^T(h_i)\phi(h_j)}
f(hi,hj)=eθT(hi)ϕ(hj)
类似于GAT中的做法。
7.4.3 GN
GN是比MPNN和NLNN更加一般的总结。
比较复杂,就不过多展开了。
总结
加油!