赞
踩
论文:Graph U-Nets
作者:Hongyang Gao , Shuiwang Ji
美国德克萨斯A&M大学计算机科学与工程系
来源:ICML 2019
论文链接:
Arxiv: https://arxiv.org/pdf/1905.05178.pdf
github链接:https://github.com/HongyangGao/gunet
此文研究了图数据的表示学习问题。在计算机视觉领域,像素级预测任务近年来取得了很大的进展。像U-Net这样的编码器-解码器架构是实现这些任务的最先进的方法,并且已经成功地应用于许多像素级的预测任务,但类似的方法在图数据上还很缺乏。因此,文中提出了一个作用在图上的U-Net网络Graph U-Nets,包括graph pooling(gPool)和graph unpooling(gUnpool)层,综合gPool和gUnpool设计Encoder和Decoder。graph U-Nets可以编码高维特征,然后解码生成网络embedding。
参考:GCN - Semi-Supervised Classification with Graph Convolutional Networks 用图卷积进行半监督节点分类 ICLR 2017
在深度学习的世界中流程着这么一句话分类网络首选ResNet,检测网络选YOLO,分割网络就选U-Net。文中使用CV领域的U-Net网络结构应用到Graph上。下面来看看U-Net网络结构(论文原文在这里U-Net: Convolutional Networks for Biomedical
Image Segmentation):
从图中我们可以看出U-Net主要分为两部分左侧的encode(编码)以及右侧的decode(解码)。在左侧编码部分主要是通过降采样操作获取图片的特征信息,然后再将这一部分的信息与右侧的部分进行整合,最终输出图片的语义信息。
其实现代码在这里。
假设 u ⃗ \vec{u} u 在 v ⃗ \vec{v} v 上的投影向量是 u ⃗ ′ \vec{u}' u ′,且向量 u ⃗ \vec{u} u 和 v ⃗ \vec{v} v 的夹角为 θ \theta θ。一个向量有两个属性,大小和方向,我们先确定 u ⃗ ′ \vec{u}' u ′的大小(即长度,或者模),从 u ⃗ \vec{u} u 的末端做 v ⃗ \vec{v} v 的垂线,那么 d d d就是 u ⃗ ′ \vec{u}' u ′的长度。而 u ⃗ ′ \vec{u}' u ′和 v ⃗ \vec{v} v 的方向是相同的, v ⃗ \vec{v} v 的方向 v ⃗ / ∣ v ⃗ ∣ \vec{v}/|\vec{v}| v /∣v ∣也就是 u ⃗ ′ \vec{u}' u ′的方向,所以
u ⃗ ′ = d v ⃗ ∣ v ⃗ ∣ d = ∣ u ⃗ ∣ cos θ \vec{u}^{\prime}=d \frac{\vec{v}}{|\vec{v}|} \\ d=|\vec{u}| \cos \theta \\ u ′=d∣v ∣v d=∣u ∣cosθ
由于 v ⃗ ⋅ u ⃗ = ∥ v ⃗ ∥ ∥ u ⃗ ∥ cos θ \vec{v} \cdot \vec{u}=\|\vec{v}\|\|\vec{u}\| \cos \theta v ⋅u =∥v ∥∥u ∥cosθ,所以有两个向量的余弦值 cos θ \cos \theta cosθ:
similarity
(
u
⃗
,
v
⃗
)
=
cos
θ
=
u
⃗
⋅
v
⃗
∣
u
⃗
∥
v
⃗
∣
\text{similarity}(\vec{u},\vec{v})=\cos \theta=\frac{\vec{u} \cdot \vec{v}}{|\vec{u} \| \vec{v}|} \\
similarity(u
,v
)=cosθ=∣u
∥v
∣u
⋅v
因此最终
u
⃗
\vec{u}
u
在
v
⃗
\vec{v}
v
上的投影向量是
u
⃗
′
\vec{u}'
u
′为:
u
⃗
′
=
u
⃗
⋅
v
⃗
∣
v
⃗
∣
2
v
⃗
\vec{u}^{\prime}=\frac{\vec{u} \cdot \vec{v}}{|\vec{v}|^{2}} \vec{v}
u
′=∣v
∣2u
⋅v
v
这个向量的长度d(也叫做标量投影)是
∣
u
⃗
′
∣
=
∣
u
⃗
∣
cos
θ
=
∣
u
⃗
∣
u
⃗
⋅
v
⃗
∣
u
⃗
∣
∣
v
⃗
∣
=
u
⃗
⋅
v
⃗
∣
v
⃗
∣
\left|\vec{u}^{\prime}\right|=|\vec{u}| \cos \theta=|\vec{u}| \frac{\vec{u} \cdot \vec{v}}{|\vec{u}||\vec{v}|}=\frac{\vec{u} \cdot \vec{v}}{|\vec{v}|}
∣u
′∣=∣u
∣cosθ=∣u
∣∣u
∣∣v
∣u
⋅v
=∣v
∣u
⋅v
注意:
常用向量的余弦值
cos
θ
\cos \theta
cosθ来衡量两个向量的相似度。例如,计算两个句子向量
句子A:(1,1,2,1,1,1,0,0,0)
和句子B:(1,1,1,0,1,1,1,1,1)的向量余弦值来确定两个句子的相似度。
计算过程如下:
cos
(
θ
)
=
1
×
1
+
1
×
1
+
2
×
1
+
1
×
0
+
1
×
1
+
1
×
1
+
0
×
1
+
0
×
1
+
0
×
1
1
2
+
1
2
+
2
2
+
1
2
+
1
2
+
1
2
+
0
2
+
0
2
+
0
2
×
1
2
+
1
2
+
1
2
+
0
2
+
1
2
+
1
2
+
1
2
+
1
2
+
1
2
=
6
7
×
8
=
0.81
cos(θ)=1×1+1×1+2×1+1×0+1×1+1×1+0×1+0×1+0×1√12+12+22+12+12+12+02+02+02×√12+12+12+02+12+12+12+12+12=6√7×√8=0.81
因为$ cos(0°)=1$,当计算结果中夹角的余弦值为0.81非常接近于1,说明两个向量的夹角很小,所以,上面的句子A和句子B是基本相似的。
Graph U-Nets使用了类似CNN里的k-max pooling的池化机制,很好理解,k-max pooling其实就是在池化时选中最大的k个节点,例如,k=2时,选择前2大的:
为了解决这些挑战,文中提出了新的graph pooling(gPool)和graph unpooling(gUnpool)层:
(1)Kipf的GCN
X ℓ + 1 = σ ( D ^ − 1 2 A ^ D ^ − 1 2 X ℓ W ℓ ) (1) \tag{1} X_{\ell+1}=\sigma\left(\hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} X_{\ell} W_{\ell}\right) Xℓ+1=σ(D^−21A^D^−21XℓWℓ)(1)
参考:GCN - Semi-Supervised Classification with Graph Convolutional Networks 用图卷积进行半监督节点分类 ICLR 2017
(2)GraphSAGE
采样固定数量的相邻节点,以保持计算内存占用的一致性。
参考:GraphSAGE:Inductive Representation Learning on Large Graphs 论文详解 NIPS 2017
(3)GAT
利用注意力机制使相邻节点的权值不同。
参考:GAT - Graph Attention Network 图注意力网络 ICLR 2018
(4)RGCN
使用关系图卷积网络进行链接预测和实体分类任务。
参考:RGCN - Modeling Relational Data with Graph Convolutional Networks 使用图卷积网络对关系数据进行建模 ESWC 2018
CNN中的卷积在图分类上的一些工作:
下面介绍graph pooling(gPool)层和graph unpooling(gUnpool)层。基于这两个新层,提出了进行节点分类任务的graph U-Nets。
符号定义:
池化层在CNNs中对网格状数据起着重要的作用,可以减小feature map的大小,扩大感受域,从而产生更好的性能,泛化能力也增强。
但是,不能将这些池化操作直接应用到图数据上,特别是因为图中节点之间没有局部性信息。因此,分割操作不适用于图。全局池化操作将所有节点映射为一个节点,限制了网络的灵活性。k-max池化操作输出可能来自图中不同节点的k个最大单元,导致所选节点的连接性不一致。
文中使用图池化层(gPool)来对图数据进行向下采样(即池化),自适应地选择节点的一个子集来形成一个新的但是更小的图。为此,使用了一个可训练的投影向量 p \mathbf{p} p,将节点 i i i的特征向量 x i \mathbf{x}_i xi投影到1个的标量,然后执行k-max池化来选择节点。
具体地,给定一个具有特征向量 x i x_i xi的节点 i i i, x i x_i xi在 p \mathbf{p} p上的标量投影为:
y i = x i p / ∥ p ∥ y_{i}=\mathbf{x}_{\mathbf{i}} \mathbf{p} /\|\mathbf{p}\| yi=xip/∥p∥
为了在采样节点的过程中尽可能多地保留原始图中的信息,选择在 p \mathbf{p} p上投影的标量最大的k个节点来形成一个新的图。有点类似PCA,PCA按照特征值大小进行维度筛选。
图池化传播规则为:
y
=
X
ℓ
p
ℓ
/
∥
p
ℓ
∥
i
d
x
=
rank
(
y
,
k
)
y
~
=
sigmoid
(
y
(
i
d
x
)
)
X
~
ℓ
=
X
ℓ
(
i
d
x
,
:
)
A
ℓ
+
1
=
A
ℓ
(
i
d
x
,
i
d
x
)
X
ℓ
+
1
=
X
~
ℓ
⊙
(
y
~
1
C
T
)
(2)
\tag{2} y=Xℓpℓ/‖pℓ‖idx=rank(y,k)˜y=sigmoid(y(idx))˜Xℓ=Xℓ(idx,:)Aℓ+1=Aℓ(idx,idx)Xℓ+1=˜Xℓ⊙(˜y1TC)
结合公式和下图,gPool过程如下:
(1)输入:节点的特征矩阵
X
ℓ
∈
R
N
×
C
X^{\ell} \in \mathbb{R}^{N \times C}
Xℓ∈RN×C和邻接矩阵
A
ℓ
∈
R
N
×
N
A^{\ell} \in \mathbb{R}^{N \times N}
Aℓ∈RN×N。
(2)投影:
y
=
X
ℓ
p
ℓ
/
∥
p
ℓ
∥
\mathbf{y} =X^{\ell} \mathbf{p}^{\ell} /\left\|\mathbf{p}^{\ell}\right\|
y=Xℓpℓ/∥∥pℓ∥∥。通过矩阵乘法和
sigmoid
(
⋅
)
\text{sigmoid}(\cdot)
sigmoid(⋅),得到了
y
\mathbf{y}
y,
y
=
[
y
1
,
y
2
,
⋯
,
y
N
]
T
\mathbf{y}=\left[y_{1}, y_{2}, \cdots, y_{N}\right]^{T}
y=[y1,y2,⋯,yN]T,使用
y
i
y_i
yi来度量节点
i
i
i在投影向量
p
ℓ
\mathbf{p}^{\ell}
pℓ上的投影值。与网格数据中的池化操作相比,gPool池化层在投影向量
p
\mathbf{p}
p中使用了额外的训练参数。
y
~
∈
R
k
\tilde{\mathbf{y}} \in \mathbb{R}^{k}
y~∈Rk,
y
~
=
sigmoid
(
y
(
i
d
x
)
)
\tilde{\mathbf{y}} =\operatorname{sigmoid}(\mathbf{y}(\mathrm{idx}))
y~=sigmoid(y(idx))如下图所示,表示将选出TopK后的节点的投影向量进行一个非线性变换(不太理解为何此处要使用sigmoid)。
(3)选择Top K的节点:假设选择的
k
k
k个索引为
i
1
,
i
2
,
⋯
,
i
k
i_{1}, i_{2}, \cdots, i_{k}
i1,i2,⋯,ik,其中
i
m
<
i
m
i_{m} < i_{m}
im<im且
1
≤
m
<
n
≤
k
1 \leq m<n \leq k
1≤m<n≤k。
rank
(
y
,
k
)
\operatorname{rank}(\mathbf{y}, k)
rank(y,k)表示节点的排序操作,返回
y
\mathbf{y}
y中值最大的
k
k
k个节点的索引。
(4)Gate操作:
X
ℓ
+
1
=
X
~
ℓ
⊙
(
y
~
1
C
T
)
X^{\ell+1} =\tilde{X}^{\ell} \odot\left(\tilde{\mathbf{y}} \mathbf{1}_{C}^{T}\right)
Xℓ+1=X~ℓ⊙(y~1CT)。计算选择出来的TopK的节点的投影值
y
\mathbf{y}
y和这些节点的特征矩阵
X
~
\tilde{X}
X~的element-wise积(即Hardmard积),得到新图的节点的特征矩阵
X
ℓ
+
1
X^{\ell+1}
Xℓ+1。gate操作使得投影向量
p
\mathbf{p}
p可以通过反向传播进行训练。在没有gate操作的情况下,投影向量
p
\mathbf{p}
p会产生离散的输出,这使得它无法通过反向传播进行训练。
1
C
∈
R
C
\mathbf{1}_{C} \in \mathbb{R}^{C}
1C∈RC是一个所有元素都是1,大小为
C
C
C的向量(
C
C
C是输入的特征矩阵的宽度),
y
~
1
C
T
\tilde{\mathbf{y}} \mathbf{1}_{C}^{T}
y~1CT其实就是表示转换成由
y
~
\tilde{\mathbf{y}}
y~中的元素构成的向量。
(5)输出:新图的邻接矩阵
A
ℓ
+
1
∈
R
k
×
k
A^{\ell+1} \in \mathbb{R}^{k \times k}
Aℓ+1∈Rk×k和特征矩阵
X
~
ℓ
+
1
∈
R
k
×
C
\tilde{X}^{\ell+1} \in \mathbb{R}^{k \times C}
X~ℓ+1∈Rk×C,经过一个gPool层后,图中的节点数量从
N
N
N变到了
k
k
k。
下图展示了一个4节点,节点特征维度为5的池化示意图:
上采样操作对于U-Net这样的编码器-解码器网络非常重要。网络的编码器通常采用池化操作来减小feature map的大小。而在解码器中,需要对feature map进行上采样以恢复其原始分辨率。对于像图像这样的网格数据,有几种上采样操作,如deconvolution层( Image-to-image translation with conditional adversarial networks,2015 CVPR;Stacked what-where auto-encoders 2015)和unpooling层(Fully convolutional networks for semantic segmentation,2015 CVPR)。但是,目前在图数据上还没有这种操作。
为了在图数据上使用上采样操作,文中提出了graph unpooling(gUnpool)层,它执行gPool层的相反操作,将图恢复到原始结构。为此,需要在gPool层存储所选的节点的位置,然后在gUnpool层根据这些信息恢复原始的图结构。gUnpool和gPool存在对应关系,ggUnpool必须利用由gPool操作提供的信息,即gPool层中进行TopK的选择时用到的idx信息,这也是为什么此网络为U-Net架构的原因吧!
graph unpooling层的逐层传播规则为:
X ℓ + 1 = distribute ( 0 N × C , X ℓ , idx ) (3) \tag{3} X^{\ell+1}=\text { distribute }\left(0_{N \times C}, X^{\ell}, \text { idx } \right) Xℓ+1= distribute (0N×C,Xℓ, idx )(3)
U-Net这样的编码器网络在像素级预测任务上有很好的性能,因为它们可以在保持局部空间信息的同时对高层特征进行编码和解码。文中在gPool和gUnpool层的基础上提出了用于节点分类任务的。
在graph U-Nets 架构中,首先应用一个图的embedding层将节点转换成低维表示,因为一些数据集的原始输入,如Cora通常有非常高维的特征向量。在图embedding层之后,通过堆叠几个编码器模块和解码器模块。
在gPool层中,对一些重要节点进行采样,以形成一个新的用于高级特征编码的图。由于在删除gPool中的节点删除了相关的边,因此图中的节点可能会变得相互隔离,这可能会影响后续层中的信息传播。当使用GCN层用于聚合来自邻居节点的信息的时,信息可能存在丢失。因此,需要增加池化了的图中节点之间的连接性。
为了解决上述问题,使用第 k k k个图的幂 G k \mathbb{G}^{k} Gk来增加图的连通性。该操作在距离最多 k k k跳的节点之间建立链接(Subsampling for graph power spectrum estimation, 2016)。文中使用 k = 2 k = 2 k=2,因为在每个gPool层之前有一个GCN层来聚合一阶邻居节点的信息。将公式(2)中的第5个公式 A ℓ + 1 = A ℓ ( i d x , i d x ) A^{\ell+1} =A^{\ell}(\mathrm{idx}, \mathrm{idx}) Aℓ+1=Aℓ(idx,idx)替换为:
A 2 = A ℓ A ℓ , A ℓ + 1 = A 2 ( idx , idx ) (4) \tag{4} A^{2}=A^{\ell} A^{\ell}, \quad A^{\ell+1}=A^{2}(\text { idx } , \text { idx } ) A2=AℓAℓ,Aℓ+1=A2( idx , idx )(4)
接下来,就可以对连通性较好的增广图进行图采样。
在公式(1)中,使用的是添加了自循环的“renormalization”邻接矩阵
A
^
=
A
+
I
\hat{A}=A+I
A^=A+I
X
ℓ
+
1
=
σ
(
D
^
−
1
2
A
^
D
^
−
1
2
X
ℓ
W
ℓ
)
(1)
\tag{1} X_{\ell+1}=\sigma\left(\hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} X_{\ell} W_{\ell}\right)
Xℓ+1=σ(D^−21A^D^−21XℓWℓ)(1)
考虑到节点自身的特征向量应该有更高的权重,因此将邻接矩阵改为
A
^
=
A
+
2
I
\hat{A}=A+2I
A^=A+2I。
需要实验证明的内容
任务
transductive learning的节点分类任务的数据集
inductive learning的图分类任务的数据集
transductive learning的节点分类任务
inductive learning的图分类任务
transductive learning的节点分类任务性能研究
inductive learning的图分类任务性能研究
在下面的实验中,使用图连通性增强的gPool层,并且使用的是2次图幂。从gPool层删除了图连接增强,同时保持其他设置不变,以保证比较的公平性。
结果表明,缺乏图连通性增强会导致三个数据集的性能一致性地下降。说明使用图的二次幂增强图的连通性有助于采样的图中节点间的信息传递。
在g-U-Nets中,编码器和解码器部分的块数是一个重要的超参数,因此通过实验研究了网络深度与节点分类精度之间的关系。
从结果可以看出,网络越深,性能越高,直到深度达到4。过拟合问题常发生在较深的网络中,当深度超过此值时,会抑制网络性能。在图像分割中,通常使用深度为3或4的U-Net模型,这与实验中的选择是一致的。表明了即使在非常浅的网络中,gPool和gUnpool层在接受野扩大和高级特征编码方面的能力。
结果表明,U-Net模型中的gPool层只增加了0.12%的额外参数,但性能可以提高2.3%。因此,额外参数的增加是微不足道的,不会增加过拟合的风险。
有错误的地方还望不吝指出,欢迎进群交流GNNs(入群备注信息!!!,格式:姓名(或网名) -(学校或其他机构信息)- 研究方向)。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。