一文读懂图卷积神经网络（GCN）

本文围绕经典论文介绍GCN，解释其定义，即处理图结构数据的网络，输入为带特征的图，输出为节点特征。解析核心公式，通过添加自环、对称归一化邻接矩阵解决信息丢失和尺度问题，还提及在Cora数据集上的应用及数学证明参考。

GCN 学习

本文讲的GCN理论知识来源于论文：

免费影视、动漫、音乐、游戏、小说资源长期稳定更新！ 👉 点此立即查看 👈

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

这是在GCN领域最经典的论文之一

1. 什么是GCN

GCN结构图
       

我们可以根据这个GCN的图看到，一个拥有 $C$C 个input channel的graph作为输入，经过中间的hidden layers，得到 $F$F 个 output channel的输出。

图卷积网络主要可以由两个级别的作用变换组成：

注意本文讲的图都特指无向无权重的图。

例如说通过引入一些形式的pooling 操作. 然后改变图的结构。但是本次讲过GCN并没有进行这个级别的操作。所以看到上图我们的网络结构的输出和输出的graph的结构是一样的。

通常说node level的作用是不改变graph的结构的，仅通过对graph的特征/信号（特征信号 $X$X 作为输入：一个 $N\ast D$N∗D 矩阵( $N$N: 输入图的nodes的个数， $D$D 输入的特征维度) ，得到输出 $Z$Z：一个 $N\ast F$N∗F 的矩阵( $F$F 输出的特征维度)。

a) 一个特征描述（feature description） $x_i$xi : 指的是每个节点 $i$i 的特征表示

b) 每一个graph 的结构都可以通过邻接矩阵 $A$A 表示（或者其他根据它推导的矩阵）

举例：

我们可以很容易的根据一个邻接矩阵重构出一个graph。 例如下图： $G=(V,E)$G=(V,E) 其中 $V$V 代表节点， $E$E 代表边

根据图，我们就可以得出下面的维度图和邻接矩阵

论文公式提出

因为 $A$A 可以确定唯一的一张图，这么重要的一个属性我们肯定是要把他放到神经网络传递函数里面去的，所以网络中间的每一个隐藏层可以写成以下的非线性函数：

其中输入层 $H(0)=X$H(0)=X , 输出层 $H(L)=Z$H(L)=Z , $L$L 是层数。 不同的GCN模型，采用不同 $f(\cdot ,\cdot )$f(⋅,⋅)函数。

上面是我们理想中的函数的形式，论文中最终推导出来的函数是这样的：

论文公式逐步解析

每一个节点下一层的信息是由前一层本身的信息以及相邻的节点的信息加权加和得到，然后再经过线性变换 $W$W 以及非线性变换 $\sigma ()$σ() 。

我们一步一步分解，我们要定义一个简单的$f(H^{(l)},A)$f(H(l),A) 函数，作为基础的网络层。

可以很容易的采用最简单的层级传导（layer-wise propagation）规则:

$f(H^{(l)},A)=\sigma (A{H}^{(l)}{W}^{(l)})$f(H(l),A)=σ(AH(l)W(l))

我们直接将 $AH$AH 做矩阵相乘，然后再通过一个权重矩阵 $W^{(l)}$W(l)做线性变换，之后再经过非线性激活函数 $\sigma (\cdot )$σ(⋅) , 比如说 $ReLU$ReLU，最后得到下一层的输入 $H^{l+1}$Hl+1 。

import paddleA = paddle.to_tensor([    [0,1,0,0,1,0],    [1,0,1,0,1,0],    [0,1,0,1,0,0],    [0,0,1,0,1,1],    [1,1,0,1,0,0],    [0,0,0,1,0,0]],dtype='float32')print(A)H_0 = paddle.to_tensor([[1],[2],[3],[4],[5],[6]],dtype='float32')print(H_0)x = paddle.matmul(A,H_0)print(x)

Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0., 1., 0., 0., 1., 0.],        [1., 0., 1., 0., 1., 0.],        [0., 1., 0., 1., 0., 0.],        [0., 0., 1., 0., 1., 1.],        [1., 1., 0., 1., 0., 0.],        [0., 0., 0., 1., 0., 0.]])Tensor(shape=[6, 1], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[1.],        [2.],        [3.],        [4.],        [5.],        [6.]])Tensor(shape=[6, 1], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[7. ],        [9. ],        [6. ],        [14.],        [7. ],        [4. ]])

从上面输出可以看的出来：每个值保留了相邻节点的值

输入层的 $x_1=[1]$x1=[1] , 根据矩阵的运算公式我们可以很容易地得到下一层的该节点的表示 $X_1^{\mathrm{\prime }}=[7]$X1′=[7], 也很容易发现 $X_1^{\mathrm{\prime }}(1)=x_2+x_5$X1′(1)=x2+x5，而 $x2,x5$x2,x5就是节点1的相邻节点。

就是可以看图：

[1] = 2 + 5
[2] = 1+ 3 + 5
······
[6] = 4

所以我们 $AH$AH 就是快速将相邻的节点的信息相加得到自己下一层的输入。

但是这样就出现了新的问题：

问题一
我们虽然获得了周围节点的信息了，但是自己本身的信息却没了

解决方案：
对每个节点手动增加一条self-loop 到每一个节点，即 $\widehat{A}=A+I$A=A+I
其中 $I$I是单位矩阵identity matrix。

问题二
从上面的结果也可以看出，在经过一次的$AH$AH 矩阵变换后，得到的输出会变大，即特征向量 $X$X 的scale会改变，在经过多层的变化之后，将和输入的scale差距越来越大。

解决方案：
可以将邻接矩阵 $A$A 做归一化使得最后的每一行的加和为1，使得 $AH$AH 获得的是weighted sum。

我们可以将 $A$A 的每一行除以行的和，这就可以得到normalized的 $A$A 。而其中每一行的和，就是每个节点的度degree。

用矩阵表示则为： $A=D^{-1}A$A=D−1A ，对于$A_{ij}=\frac{A_{ij}}{d_i}$Aij=diAij

代码展示：

import paddleimport numpy as npA = paddle.to_tensor([    [0,1,0,0,1,0],    [1,0,1,0,1,0],    [0,1,0,1,0,0],    [0,0,1,0,1,1],    [1,1,0,1,0,0],    [0,0,0,1,0,0]],dtype='float32')print(A)D = paddle.to_tensor([    [2,0,0,0,0,0],    [0,3,0,0,0,0],    [0,0,2,0,0,0],    [0,0,0,3,0,0],    [0,0,0,0,3,0],    [0,0,0,0,0,1]], dtype='float32')print(D)# 防止为0时取倒数变成无穷大D[D==0] = D.max() + 1e100DD = paddle.reciprocal(D)print(DD)hat_A = paddle.matmul(DD,A)print(hat_A)

Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0., 1., 0., 0., 1., 0.],        [1., 0., 1., 0., 1., 0.],        [0., 1., 0., 1., 0., 0.],        [0., 0., 1., 0., 1., 1.],        [1., 1., 0., 1., 0., 0.],        [0., 0., 0., 1., 0., 0.]])Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[2., 0., 0., 0., 0., 0.],        [0., 3., 0., 0., 0., 0.],        [0., 0., 2., 0., 0., 0.],        [0., 0., 0., 3., 0., 0.],        [0., 0., 0., 0., 3., 0.],        [0., 0., 0., 0., 0., 1.]])Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0.50000000, 0.        , 0.        , 0.        , 0.        , 0.        ],        [0.        , 0.33333334, 0.        , 0.        , 0.        , 0.        ],        [0.        , 0.        , 0.50000000, 0.        , 0.        , 0.        ],        [0.        , 0.        , 0.        , 0.33333334, 0.        , 0.        ],        [0.        , 0.        , 0.        , 0.        , 0.33333334, 0.        ],        [0.        , 0.        , 0.        , 0.        , 0.        , 1.        ]])Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0.        , 0.50000000, 0.        , 0.        , 0.50000000, 0.        ],        [0.33333334, 0.        , 0.33333334, 0.        , 0.33333334, 0.        ],        [0.        , 0.50000000, 0.        , 0.50000000, 0.        , 0.        ],        [0.        , 0.        , 0.33333334, 0.        , 0.33333334, 0.33333334],        [0.33333334, 0.33333334, 0.        , 0.33333334, 0.        , 0.        ],        [0.        , 0.        , 0.        , 1.        , 0.        , 0.        ]])

但是在实际运用中采用的是对称的normalization：

用矩阵表示则为：

$$A=D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$$A=D−21AD−21

对于$A_{ij}=\frac{A_{ij}}{\sqrt{d_i}\sqrt{d_j}}$Aij=didjAij

这其实是跟Laplacian Matrix 有关，拉普拉斯算子是这样的：

$$L=I_N-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$$L=IN−D−21AD−21

import paddleimport numpy as npA = paddle.to_tensor([    [0,1,0,0,1,0],    [1,0,1,0,1,0],    [0,1,0,1,0,0],    [0,0,1,0,1,1],    [1,1,0,1,0,0],    [0,0,0,1,0,0]],dtype='float32')print(A)D = paddle.to_tensor([    [2,0,0,0,0,0],    [0,3,0,0,0,0],    [0,0,2,0,0,0],    [0,0,0,3,0,0],    [0,0,0,0,3,0],    [0,0,0,0,0,1]], dtype='float32')print(D)# 取逆D[D==0] = D.max() + 1e100DD = paddle.reciprocal(D)print(DD)# 开方_DD = paddle.sqrt(DD)# 求积hat_A = paddle.matmul(paddle.matmul(_DD,A),_DD)print(hat_A)

Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0., 1., 0., 0., 1., 0.],        [1., 0., 1., 0., 1., 0.],        [0., 1., 0., 1., 0., 0.],        [0., 0., 1., 0., 1., 1.],        [1., 1., 0., 1., 0., 0.],        [0., 0., 0., 1., 0., 0.]])Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[2., 0., 0., 0., 0., 0.],        [0., 3., 0., 0., 0., 0.],        [0., 0., 2., 0., 0., 0.],        [0., 0., 0., 3., 0., 0.],        [0., 0., 0., 0., 3., 0.],        [0., 0., 0., 0., 0., 1.]])Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0.50000000, 0.        , 0.        , 0.        , 0.        , 0.        ],        [0.        , 0.33333334, 0.        , 0.        , 0.        , 0.        ],        [0.        , 0.        , 0.50000000, 0.        , 0.        , 0.        ],        [0.        , 0.        , 0.        , 0.33333334, 0.        , 0.        ],        [0.        , 0.        , 0.        , 0.        , 0.33333334, 0.        ],        [0.        , 0.        , 0.        , 0.        , 0.        , 1.        ]])Tensor(shape=[6, 6], dtype=float32, place=CUDAPlace(0), stop_gradient=True,       [[0.        , 0.40824828, 0.        , 0.        , 0.40824828, 0.        ],        [0.40824828, 0.        , 0.40824828, 0.        , 0.33333331, 0.        ],        [0.        , 0.40824828, 0.        , 0.40824828, 0.        , 0.        ],        [0.        , 0.        , 0.40824828, 0.        , 0.33333331, 0.57735026],        [0.40824828, 0.33333331, 0.        , 0.33333331, 0.        , 0.        ],        [0.        , 0.        , 0.        , 0.57735026, 0.        , 0.        ]])

$A_{0,1}=\frac{A_{0,1}}{\sqrt{d_0}\sqrt{d_1}}=\frac{1}{\sqrt{2}\sqrt{3}}=0.4082$A0,1=d0d1A0,1=231=0.4082

把这两个tricks结合起来，我们就可以原文的公式:

其中 $\widehat{A}=A+I$A=A+I , $\widehat{D}$D 是 $\widehat{A}$A 的degree matrix。 而 ${\widehat{D}}^{-\frac{1}{2}}\widehat{A}{\widehat{D}}^{-\frac{1}{2}}$D−21AD−21 是对 $A$A 做了一个对称的归一化。

在Cora数据集上训练的两层GCN的隐藏层激活的可视化效果如下：

2. 数学证明：

附上参考的视频：

https://www.bilibili.com/video/BV1Vw411R7Fj