近期在鼓捣图神经网络,发现直接读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
就知道了。
- 第一步加载数据,
X, A, y = load_data(dataset=DATASET)
,其中X是特征矩阵,即节点的向量表示,A是临界矩阵,y是标签; - 然后得到训练数据
graph
,由X
和A_
(处理后的矩阵,包括增加单位矩阵和对称标准化)组成; - 之后数据经过
doupout
,传入GraphConvolution
层;
GraphConvolution
解析
重要的一点是,图卷积网络和卷积核无关。而是直接矩阵相乘,在得到节点的嵌入表示后,再去划分就很容易了。可以参看原文的代码(我删除了一部分无关紧要的代码):
1 | class GraphConvolution(Layer): |
如上,我么很容易看出 GCN
的工作就是矩阵相乘,将输出的维度不断的压缩,得到节点的嵌入表示。也许你会很疑惑?众多科普文章中的拉普拉斯算子什么的呢?关于这一点,原作者也做出了解释:
spectral graph convolution
(我不知道该怎么翻译了):定义为信号与图的傅立叶空间中的滤波器相乘。说人话的意思是:矩阵$X$要和矩阵$U$相乘,矩阵$U$是图灵拉普拉斯矩阵$L$的特征向量矩阵,$L$的计算方式是:$L=I-\hat{A}$,但是具有高昂的计算代价。
结语
也许你会疑问,图网络是用来干什么的?正如作者所说,GCN仅仅是一个开始。据我个人的粗俗分析,可以用来:
- 借助GCN学习得到的节点表示,来进行大规模图划分;
- 如果GCN的标签是自己本身,那是不是可以用类似 autoencoder 的形式来进行链接预测?
- 能否学习节点之间的隐藏联系,推断序列数据的结构?
- 能否与周围环境交互,对已有的模型进行调整,主动构建关系、对象等?
当然,距离实现以上这些还有很长的路要走。
参考
站在巨人的肩膀上,我们能更好的前行:
- 参考论文: https://arxiv.org/pdf/1609.02907.pdf
- 参考博客(原文讲的很好): http://tkipf.github.io/graph-convolutional-networks/
- 数据集(cora): http://www.cs.umd.edu/~sen/lbc-proj/LBC.html
- 代码参考(tensorflow): https://github.com/tkipf/gcn
- 代码参考(keras): https://github.com/tkipf/keras-gcn