0%

GCN的通俗理解,无复杂公式

近期在鼓捣图神经网络,发现直接读state-of-art的论文基本读不懂,于是先决定搞懂图神经网络的最基本概念,即工作原理、处理数据流程等。因网上的众多文章(包括原论文)都有复杂的数学公式,我不是否认数学公式不好,而是胡乱的堆公式对讲明白原理没有丝毫帮助。于是决定做一篇GCN的简单阐述,意在用最简单的语言,表达最清晰的思路。

定义

图的表示为$G=(V,E)$,将图的节点表示和邻接矩阵作为网络的输入:

  • 对于每一个节点$i$的特征描述$x_i$,组成一个$N\times D$的矩阵$X$,$N$是节点的数量,$D$是特征的维度;
  • 图的邻接矩阵为$A$;
  • 网络的输出是$Z$,维度是$N\times F$,$F$是输出维度的特征。

每一层神经网络可以定义为非线性函数:

\begin{equation}
H^{l+1}=f(H^l, A)
\end{equation}

其中,$H^0=X,H^l=Z$,$l$是网络的层数,$f$是选择的网络模型,就这样一层一层的输出。

简单实例

首先定义逐层之间的传播规则:

\begin{equation}f(H^l,A)=\sigma (AH^lW^l)\end{equation}

其中,$W^l$是第$l$层的网络权重,$\sigma$是非线性的激活函数,这是最简单的定义。对这个最简单的定义添加两个限制:

  • $A\times H^l$意味着对于图中的每一个节点,将它所有的邻居节点的全部特征向量求和,但没有考虑自己(除非有链接到自己的环),所以要对矩阵$A$增加单位矩阵$I$,这样矩阵的每一个节点就具有链接到自己的回路;
  • 考虑到邻接矩阵$A$的同时,也要考虑到节点的度,度越大,表明该节点和其他节点的关系越大,如果直接提取度数很大节点和周围节点的联系,即将邻居节点的全部特征向量求和,势必会导致数据分布的不均衡。此时标准化的方式为:要取该节点的周围节点特征值的平均值。通俗点说,就是一个节点和四个节点挨着,那么对这四个节点,取每个节点特征值的$1/4$在求和就行了。而实现这种方式只需要一个矩阵变换:方式为$D^{-1}A$/其中,$D$是对角矩阵,矩阵元素是节点的度。论文中使用了对称标准化$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$的方式,这不再严格等于相邻节点的平均。
  • (只是这么一种处理方式,不必太在意),还是要在意一下,我之前认为傅立叶变换等数学推导可以忽略,结果发现这是傅立叶变换和逆变换的两个过程,如果想要看懂这个过程,可以参考:李宏毅机器学习课程 GNN 的第二章节的课程。

此时,传播规则为:

\begin{equation}f(H^l,A)=\sigma (\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^lW^l)\end{equation}

其中,$\hat{A}=A+I$,$\hat{D}$是$\hat{A}$的节点度的矩阵。

模型操作

如果你看到这里还不是很懂,那我很建议去看它的代码,一目了然。值得注意的是,模型产生了这些节点的嵌入,它们非常类似于图的社区结构。

半监督学习

只对有标签的数据训练,没有标签的数据在损失函数中不考虑。

代码

恕我直言,上古时期的tensorflow代码没有看懂,keras的代码还能看懂,但没有调通,看源代码的众多issue就知道了。

  1. 第一步加载数据,X, A, y = load_data(dataset=DATASET),其中X是特征矩阵,即节点的向量表示,A是临界矩阵,y是标签;
  2. 然后得到训练数据graph,由XA_(处理后的矩阵,包括增加单位矩阵和对称标准化)组成;
  3. 之后数据经过doupout,传入GraphConvolution层;

GraphConvolution 解析

重要的一点是,图卷积网络和卷积核无关。而是直接矩阵相乘,在得到节点的嵌入表示后,再去划分就很容易了。可以参看原文的代码(我删除了一部分无关紧要的代码):

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
class GraphConvolution(Layer):
"""Basic graph convolution layer as in https://arxiv.org/abs/1609.02907"""

def compute_output_shape(self, input_shapes):
features_shape = input_shapes[0]
output_shape = (features_shape[0], self.units)
return output_shape # (batch_size, output_dim)

def build(self, input_shapes):
features_shape = input_shapes[0]
assert len(features_shape) == 2
input_dim = features_shape[1]

self.kernel = self.add_weight(shape=(input_dim * self.support,
self.units),
initializer=self.kernel_initializer,
name='kernel',
regularizer=self.kernel_regularizer,
constraint=self.kernel_constraint)

self.bias = self.add_weight(shape=(self.units,),
initializer=self.bias_initializer,
name='bias',
regularizer=self.bias_regularizer,
constraint=self.bias_constraint)

self.built = True

def call(self, inputs, mask=None):
features = inputs[0]
basis = inputs[1:]

supports = list()
for i in range(self.support):
supports.append(K.dot(basis[i], features))
supports = K.concatenate(supports, axis=1)
output = K.dot(supports, self.kernel)

output += self.bias
return self.activation(output)

如上,我么很容易看出 GCN 的工作就是矩阵相乘,将输出的维度不断的压缩,得到节点的嵌入表示。也许你会很疑惑?众多科普文章中的拉普拉斯算子什么的呢?关于这一点,原作者也做出了解释:

spectral graph convolution(我不知道该怎么翻译了):定义为信号与图的傅立叶空间中的滤波器相乘。说人话的意思是:矩阵$X$要和矩阵$U$相乘,矩阵$U$是图灵拉普拉斯矩阵$L$的特征向量矩阵,$L$的计算方式是:$L=I-\hat{A}$,但是具有高昂的计算代价。

结语

也许你会疑问,图网络是用来干什么的?正如作者所说,GCN仅仅是一个开始。据我个人的粗俗分析,可以用来:

  1. 借助GCN学习得到的节点表示,来进行大规模图划分;
  2. 如果GCN的标签是自己本身,那是不是可以用类似 autoencoder 的形式来进行链接预测?
  3. 能否学习节点之间的隐藏联系,推断序列数据的结构?
  4. 能否与周围环境交互,对已有的模型进行调整,主动构建关系、对象等?

当然,距离实现以上这些还有很长的路要走。

参考

站在巨人的肩膀上,我们能更好的前行:

  1. 参考论文: https://arxiv.org/pdf/1609.02907.pdf
  2. 参考博客(原文讲的很好): http://tkipf.github.io/graph-convolutional-networks/
  3. 数据集(cora): http://www.cs.umd.edu/~sen/lbc-proj/LBC.html
  4. 代码参考(tensorflow): https://github.com/tkipf/gcn
  5. 代码参考(keras): https://github.com/tkipf/keras-gcn
感谢上学期间打赏我的朋友们。赛博乞讨:我,秦始皇,打钱。

欢迎订阅我的文章