本篇中我们只讨论聚合流程,不考虑GraphSAGE的小批量训练等内容。
我们先来看一下GraphSAGE的聚合流程伪代码,之后会给出两个具体的计算例子进行说明:
11行中,
N
(
k
)
(
u
)
N^{(k)}(u)
N(k)(u)表示节点u的邻居节点采样函数(指的是从其邻居节点中选取一批节点),Agg()指的是邻居节点的聚合算子,有平均(加和)聚合算子,也有最大(平均)池化聚合算子。我们接下来会以平均聚合算子和平均池化聚合算子为例进行说明。
12行中,
[
h
u
(
k
−
1
)
∣
∣
h
N
(
u
)
k
]
[h_u^{(k-1)}||h_{N(u)}^k]
[hu(k−1)∣∣hN(u)k]表示两个向量缀连起来(即[h1[1], h1[2], …, h1[n], h2[1], h2[2], …, h2[m]]),对这个缀连起来的向量乘一个
W
k
W^k
Wk进行线性变换(往往在这一步将向量的维数转换成想要嵌入表示输出的
d
o
u
t
d_{out}
dout维),再加个激活函数进行非线性变换。
最后对得到的向量进行归一化,就对节点
u
u
u完成了一次聚合过程。
数据准备
对于下面这样一个图:
假如我们想要节点的嵌入输出的outputdim为2维的,输入的图对应初始特征数据如下:
i
d
,
x
0
,
x
1
,
x
2
,
x
3
1
,
0.5
,
0.6
,
0.7
,
0.8
2
,
0.3
,
0.8
,
0.3
,
0.4
3
,
0.7
,
0.9
,
0.6
,
0.9
4
,
0.2
,
0.1
,
0.2
,
0.3
5
,
0.8
,
0.4
,
0.3
,
0.2
id,x_0,x_1,x_2,x_3\\ 1,0.5,0.6,0.7,0.8\\ 2,0.3,0.8,0.3,0.4\\ 3,0.7,0.9,0.6,0.9\\ 4,0.2,0.1,0.2,0.3\\ 5,0.8,0.4,0.3,0.2\\
id,x0,x1,x2,x31,0.5,0.6,0.7,0.82,0.3,0.8,0.3,0.43,0.7,0.9,0.6,0.94,0.2,0.1,0.2,0.35,0.8,0.4,0.3,0.2
我们先完成第一步,邻居节点聚合。
这一步可以采用多种聚合算子,我们在此以平均聚合算子与平均池化聚合算子为例。
平均聚合算子
这里的Agg()是指取平均: A V E R A G E ( h j ) AVERAGE(h_j) AVERAGE(hj)
h
4
(
0
)
=
[
0.2
,
0.1
,
0.2
,
0.3
]
T
h_4 ^{(0)} =[0.2,0.1,0.2,0.3]^T
h4(0)=[0.2,0.1,0.2,0.3]T
节点4的邻接节点为2,3,5
我们用平均聚合算子AVERAGE(h)对2,3,5这三个节点的信息进行聚合:
A
g
g
(
1
)
(
h
2
(
0
)
,
h
3
(
0
)
,
h
5
(
0
)
)
Agg^{(1)}(h_2(0),h_3(0),h_5(0))
Agg(1)(h2(0),h3(0),h5(0))
就是对这三个向量对应值相加取均值,得到:
h
N
(
4
)
(
1
)
=
[
0.6
,
0.7
,
0.4
,
0.5
]
h_{N(4)}^{(1)}=[0.6,0.7,0.4,0.5]
hN(4)(1)=[0.6,0.7,0.4,0.5]
由上面我们得到
h
4
(
1
)
h_4^{(1)}
h4(1)为:
σ
(
W
(
1
)
[
h
u
(
0
)
,
h
N
(
u
)
(
1
)
]
)
=
σ
(
W
(
1
)
[
0.2
,
0.1
,
0.2
,
0.3
,
0.6
,
0.7
,
0.4
,
0.5
]
T
)
\sigma(W^{(1)}[h_u^{(0)},h_{N(u)}^{(1)}]) =\sigma(W^{(1)}[0.2,0.1,0.2,0.3,0.6,0.7,0.4,0.5]^T)
σ(W(1)[hu(0),hN(u)(1)])=σ(W(1)[0.2,0.1,0.2,0.3,0.6,0.7,0.4,0.5]T)
为了使得输出是一个
2
×
1
2×1
2×1的向量,我们设置
W
(
1
)
W^{(1)}
W(1)为一个
2
×
8
2×8
2×8 的矩阵,比如我们初始化为:
1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 1,0,0,0,1,0,1,0\\0,1,0,1,0,0,1,0 1,0,0,0,1,0,1,00,1,0,1,0,0,1,0
与上面的向量相乘,得到 [ 1.2 , 0.8 ] T [1.2,0.8]^T [1.2,0.8]T
将其代入激活函数(ReLU)后进行归一化,就正式得到
h
4
(
1
)
=
[
0.83205029
,
0.5547002
]
T
h_4^{(1)} = [0.83205029,0.5547002 ]^T
h4(1)=[0.83205029,0.5547002]T
这样就正式完成了对节点4的一次聚合操作。
对第一层的其他节点的操作也是类似的。
平均池化聚合算子
平均池化聚合算子,就是指
A
V
E
R
A
G
E
[
σ
(
W
h
+
b
)
]
AVERAGE[\sigma(Wh+b)]
AVERAGE[σ(Wh+b)],
σ
\sigma
σ是激活函数(ReLU)
具体怎么做的呢?
我们待处理的邻接节点:
h
2
(
0
)
=
[
0.3
,
0.8
,
0.3
,
0.4
]
,
h
3
(
0
)
=
[
0.7
,
0.9
,
0.6
,
0.9
]
,
h
5
(
0
)
=
[
0.8
,
0.4
,
0.2
,
0.3
]
h_2^{(0)} = [0.3,0.8,0.3,0.4],\\ h_3^{(0)} = [0.7,0.9,0.6,0.9],\\ h_5^{(0)} = [0.8,0.4,0.2,0.3]
h2(0)=[0.3,0.8,0.3,0.4],h3(0)=[0.7,0.9,0.6,0.9],h5(0)=[0.8,0.4,0.2,0.3]
此刻我们在此添加一个dense层(全连接层)。这里全连接层是指:对这每个节点,其向量的每个分量经过了一个全连接层。
对于 h j h_j hj,输出是: R e L U ( W h j + b ) ReLU(Wh_j+b) ReLU(Whj+b)
我们引入一个权重矩阵
W
W
W,它是hidden dim×input dim维度的,在这里input dim是4维,我们设定这个隐藏层的输出维度为3,那么W就是一个3×4的矩阵;对于同一层中的每个邻居节点,W是固定的。
b就是一个hidden_dim(3)维的向量。
所以说线性变换的输出就是
这样的话:
对于节点2,我们的输入
h
2
(
0
)
=
[
0.3
,
0.8
,
0.3
,
0.4
]
h_2{(0)} = [0.3,0.8,0.3,0.4]
h2(0)=[0.3,0.8,0.3,0.4]是4维的。
所以
o
1
=
w
11
x
1
+
w
12
x
2
+
w
13
x
3
+
w
14
x
4
+
b
1
o
2
=
w
21
x
1
+
w
22
x
2
+
w
23
x
3
+
w
24
x
4
+
b
2
o
3
=
w
31
x
1
+
w
32
x
2
+
w
33
x
3
+
w
34
x
4
+
b
3
o1 = w11x1+w12x2+w13x3+w14x4+b1\\ o2 = w21x1+w22x2+w23x3+w24x4+b2\\ o3 = w31x1+w32x2+w33x3+w34x4+b3
o1=w11x1+w12x2+w13x3+w14x4+b1o2=w21x1+w22x2+w23x3+w24x4+b2o3=w31x1+w32x2+w33x3+w34x4+b3
所以实际上
o
=
W
h
2
(
0
)
o = Wh_2{(0)}
o=Wh2(0)
W W W 权重的初始化有多种方式,我们在此用随机数初始化
col0 | col1 | col2 | col3 |
---|---|---|---|
0.17 | 0.4 | -0.14 | 0.51 |
0.75 | -0.04 | 0.67 | -0.18 |
0.53 | -0.04 | 0.4 | 0.77 |
b = [ 0.66 , − 0.58 , − 0.64 ] b = [0.66,-0.58,-0.64] b=[0.66,−0.58,−0.64]
对于节点2,3,5,得到的
W
h
j
+
b
Wh_j+b
Whj+b分别为
[
1.19
,
−
0.26
,
−
0.08
]
[
1.51
,
0.15
,
0.63
]
[
1.08
,
0.08
,
0.08
]
[1.19,-0.26,-0.08]\\ [1.51,0.15,0.63] \\ [1.08,0.08,0.08]
[1.19,−0.26,−0.08][1.51,0.15,0.63][1.08,0.08,0.08]
将上述三个向量经过激活函数ReLU:
就得到(对每个分量分别取ReLU)
[
1.19
,
0
,
0
]
[
1.51
,
0.15
,
0.63
]
[
1.08
,
0.08
,
0.08
]
[1.19, 0, 0]\\ [1.51,0.15,0.63] \\ [1.08,0.08,0.08]
[1.19,0,0][1.51,0.15,0.63][1.08,0.08,0.08]
对上面三个向量取均值
h
N
(
4
)
(
0
)
=
A
V
E
R
A
G
E
(
R
e
L
U
(
W
h
j
+
b
)
)
=
[
1.26
,
0.08
,
0.24
]
h_{N(4)}^{(0)} = AVERAGE(ReLU(Wh_j+b)) = [1.26,0.08,0.24]
hN(4)(0)=AVERAGE(ReLU(Whj+b))=[1.26,0.08,0.24]
这样我们就完成了第一步;
刚刚我们得到了 h N ( 4 ) ( 1 ) h_{N(4)}^{(1)} hN(4)(1),而 h 4 ( 0 ) = [ 0.2 , 0.1 , 0.2 , 0.3 ] h_4^{(0)} = [0.2,0.1,0.2,0.3] h4(0)=[0.2,0.1,0.2,0.3]
因为经过了一个平均池化聚合,邻居节点的输出变成了3维的,所以GraphSAGE对当前节点与邻居节点分别引入了一个权重矩阵,于是伪代码第12行的操作在这里为:
R e L U ( W ( 1 ) [ h u ( 0 ) , h N ( u ) ( 1 ) ] ) = R e L U ( W s e l f ( 1 ) h 4 ( 0 ) + W n e i g h ( 1 ) h N ( 4 ) ( 1 ) ) ReLU(W^{(1)}[h_u^{(0)},h_{N(u)}^{(1)}]) = ReLU(W_{self}^{(1)}h_4^{(0)}+W_{neigh}^{(1)}h_{N(4)}^{(1)}) ReLU(W(1)[hu(0),hN(u)(1)])=ReLU(Wself(1)h4(0)+Wneigh(1)hN(4)(1))
因为我们想要输出是2维的,那么
W
s
e
l
f
(
1
)
W_{self}^{(1)}
Wself(1)和
W
n
e
i
g
h
(
1
)
W_{neigh}^{(1)}
Wneigh(1)就分别是4×2维的和3×2维的;
当然,我们也可以在括号里加一个二维的bias向量作偏置。
将计算得到的结果向量经过一个ReLU函数(依然是对各分量分别取ReLU),再除以它的模进行归一化后输出,就完成了聚合操作。文章来源:https://www.toymoban.com/news/detail-429588.html
(关于具体计算过程,有参考GraphSAGE的官方代码,如有疏漏之处敬请指正)文章来源地址https://www.toymoban.com/news/detail-429588.html
到了这里,关于GraphSAGE聚合流程计算实例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!