GCN-图卷积模型理解

GCN

GCN简介

GCN-Graph Convolutional Networks，即图卷积神经网络。论文提出了一种可以在图结构中进行有效特征抽取的架构，这是和我们认为的卷积神经网络所处理的图片问题不同，图往往是非结构数据，呈散发或者聚合的样子，因此，很难通过普通的卷积网络来进行特征抽取。

原理

论文作者有丰富的数学经验和非常严谨的推导能力，小编的能力还不足以进行详细解释，只能通过论文中的主要公式并结合前人的资料，来做一个总结。

论文中的主要公式如下：
$H^{(l+1)}=\sigma ({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)})$
其中
$\tilde{A}=A+I_N$，A是图邻接矩阵，I是单位矩阵；
$\tilde{D}$是邻接矩阵转换而来的度矩阵；
$H$是节点的特征矩阵；
$W$是随机权重矩阵。
我们假设如下设计：

A = np.matrix([[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]])
1
2
3
4
5
6

矩阵A是特征矩阵，为6*6

H = np.matrix([[6, 8, 9, 8, 4, 3, 1, 3, 2, 4, 0, 2],
               [6, 0, 0, 2, 1, 1, 1, 3, 7, 1, 0, 7],
               [6, 5, 8, 0, 6, 5, 9, 4, 1, 8, 2, 1],
               [8, 4, 5, 3, 0, 4, 4, 6, 5, 8, 4, 6],
               [3, 8, 1, 4, 6, 5, 2, 5, 1, 6, 0, 7],
               [0, 9, 9, 5, 7, 1, 8, 2, 2, 3, 8, 5]])
1
2
3
4
5
6

矩阵H为特征矩阵，为6*12，即表示每个节点有12维特征
为什么要用邻接矩阵+单位矩阵？
如果不加单位矩阵，在和特征矩阵相乘时，就无法融合自身特征。

$\tilde{A}H$的意义何在？
$\tilde{A}H$意义在于，采用关系矩阵和对应的特征矩阵相乘，来融合不同节点之间的特征，进而对表示当前节点。

$\tilde{A}H$如下表示：

[[ 9  8  1  6  7  6  3  8  8  7  0 14]
 [15 21 18 12 16 13 12 12  4 18  2 10]
 [14  4  5  5  1  5  5  9 12  9  4 13]
 [ 9 22 18  9 19 11 19 11  4 17 10 13]
 [20 12 14 13  5  8  6 12 14 13  4 15]
 [ 8  4  5  3  0  4  4  6  5  8  4  6]]
1
2
3
4
5
6

我们可以看到，$\tilde{A}H$变成一个6*12维的矩阵，每个节点聚合了自身相连节点的特征。

$\tilde{D}$矩阵表示如下：

[[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]]
1
2
3
4
5
6

为什么要引入$\tilde{D}$
如果不引入度矩阵，在邻接矩阵和特征矩阵直接相乘之后，就无法区分不同节点的重要性。如果一个节点的邻居节点非常多(度非常大)，那么这些邻居所传递的特征应该减弱一些。

为什么使用${\tilde{D}}^{-\frac{1}{2}}$
进行${\tilde{D}}^{-1}$就类似于进行归一化操作；而对每个元素进行开根号操作，是为了避免度过大，导致最终的特征不明显。加入a节点的度为100，那么两个$\frac{1}{100}$相乘就是$\frac{1}{10000}$，这就会导致数值过小，开根号之后，就是两个$\frac{1}{10}$进行相乘，也不过是$\frac{1}{100}$。

${\tilde{D}}^{-\frac{1}{2}}$表示如下：

[[0.70710678 0.         0.         0.         0.         0.        ]
 [0.         0.57735027 0.         0.         0.         0.        ]
 [0.         0.         0.70710678 0.         0.         0.        ]
 [0.         0.         0.         0.57735027 0.         0.        ]
 [0.         0.         0.         0.         0.57735027 0.        ]
 [0.         0.         0.         0.         0.         1.        ]]
1
2
3
4
5
6

${\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)}$得出来的特征矩阵表示为：

tensor([[ 7.6337, 14.1229,  0.2555,  5.3214,  6.5139, 17.6447],
        [10.7289, 14.3577,  0.1687,  7.9047,  4.6455, 23.8508],
        [ 9.2757,  9.2063,  1.3585,  4.2395, -3.5072, 20.5705],
        [14.5890, 14.3509,  4.3755, 15.4938,  1.9428, 31.4894],
        [ 9.4929, 14.2528,  0.9730,  4.5586,  3.6944, 19.6349],
        [15.8333, 10.7235,  3.8635, 14.9488, -1.9711, 28.8009]],
       dtype=torch.float64)
1
2
3
4
5
6
7

$softmax(\tilde{A}ReLU(\tilde{A}X{W}^0)W^1)$结果如下：

tensor([[  8.2074,  -0.6540,   4.8701,   9.9986,  12.5447,  -9.0682],
        [ 12.3482,  -2.2859,   4.8332,   7.5971,  10.3582,  -8.7932],
        [  9.1299,   0.8241,   7.4153,   5.8852,   4.9821,  -8.1917],
        [ 14.8664,  -0.7018,   3.5808,  11.7506,   9.4826, -13.7287],
        [  9.0130,   0.4613,   6.3380,  10.1234,  12.0750, -10.6103],
        [ 13.8291,   0.3827,   3.6747,  16.6514,   9.5593, -17.6799]],
       dtype=torch.float64)
1
2
3
4
5
6
7

最终分类结果如下：

2
2
0
0
0
0
1
2
3
4
5
6

以上就只拉普拉斯在GCN中所起到的作用了，用python简单实现，代码如下：

# -*- coding: utf-8 -*-
# !/usr/bin/env python
import torch
import torch.nn as nn
import numpy as np
import torch.nn.functional as F
import scipy.sparse as sp
import math
#定义邻接矩阵
A = np.matrix([[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]])
#定义特征矩阵
H = np.matrix([[6, 8, 9, 8, 4, 3, 1, 3, 2, 4, 0, 2],
               [6, 0, 0, 2, 1, 1, 1, 3, 7, 1, 0, 7],
               [6, 5, 8, 0, 6, 5, 9, 4, 1, 8, 2, 1],
               [8, 4, 5, 3, 0, 4, 4, 6, 5, 8, 4, 6],
               [3, 8, 1, 4, 6, 5, 2, 5, 1, 6, 0, 7],
               [0, 9, 9, 5, 7, 1, 8, 2, 2, 3, 8, 5]])
#定义权重矩阵W1
W1 = torch.empty(size=(12,6), dtype=float)
nn.init.xavier_uniform_(W1.data,gain=1.414)
#定义权重矩阵W2
W2 = torch.empty(size=(6,6), dtype=float)
nn.init.xavier_uniform_(W2.data,gain=1.414)
#获取度矩阵
D = np.array(np.sum(A, axis=0))[0]
D = np.matrix(np.diag(D))
#获取度矩阵开-1/2次方
invD = np.sqrt(D) ** -1
#获取单位矩阵+邻接矩阵
invA = A + np.eye(len(A))
#拉普拉斯矩阵计算
X = torch.tensor(invD * invA * invD * H, dtype=float)
X = torch.matmul(X,W1)
#过一次激活函数
Relu = torch.nn.ReLU()
L = torch.matmul(torch.tensor(invA),Relu(X))
L = torch.matmul(L,W2)
#softmax求概率
soft = torch.nn.functional.softmax(L)
#获取每个node标签
for each in list(soft.data.numpy()):
    print(list(each).index(max(each)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

结语

关于GCN的讲解大概就是这样了，如果大家有什么问题或者需要补充的，请留言或者加QQ：1143948594，随时联系！！！
附：
论文链接:https://arxiv.org/pdf/1609.02907.pdf
tf版代码:https://github.com/tkipf/gcn