本文仅作学术分享,如有侵权,请联系后台删文处理
-
本文的提纲与叙述要点主要参考了2篇图神经网络的Survey,分别是来自IEEE Fellow的A Comprehensive Survey on Graph Neural Networks[1] 以及来自清华大学朱文武老师组的Deep Learning on Graphs: A Survey[7], 在这里向两篇Survey的作者表示敬意。
-
同时,本文关于部分图卷积神经网络的理解很多都是受到知乎问题[8]高赞答案的启发,非常感谢他们的无私分享!
-
最后,本文还引用了一些来自互联网的生动形象的图片,在这里也向这些图片的作者表示感谢。本文中未注明出处的图片均为笔者制作,如需转载或引用请联系本人。
-
图神经网络的概念最早在2005年提出。2009年Franco博士在其论文 [2]中定义了图神经网络的理论基础,笔者呆会要讲的第一种图神经网络也是基于这篇论文。
-
最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间(比如像图像 Image)或者是序列(比如像文本 Text),许多常见场景也都可以转换成图(Graph),然后就能使用图神经网络技术来建模。
-
2009年后图神经网络也陆续有一些相关研究,但没有太大波澜。直到2013年,在图信号处理(Graph Signal Processing)的基础上,Bruna(这位是LeCun的学生)在文献 [3]中首次提出图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络。
-
其后至今,学界提出了很多基于空域的图卷积方式,也有不少学者试图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少,只受到部分学者的青睐。
-
值得一提的是,图神经网络与图表示学习(Represent Learning for Graph)的发展历程也惊人地相似。2014年,在word2vec [4]的启发下,Perozzi等人提出了DeepWalk [5],开启了深度学习时代图表示学习的大门。更有趣的是,就在几乎一样的时间,Bordes等人提出了大名鼎鼎的TransE [6],为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。
状态更新与输出
不动点理论
模型学习
-
调用 若干次,比如 次,直到 收敛。
-
此时每个结点的隐藏状态接近不动点的解。
-
对于有监督信号的结点,将其隐藏状态通过 得到输出,进而算出模型的损失。
根据上面的过程,在反向传播时,我们可以直接求出 和 对最终的隐藏状态 的梯度。然而,因为模型递归调用了 若干次,为计算 和 对最初的隐藏状态 的梯度,我们需要同样递归式/迭代式地计算 次梯度。最终得到的梯度即为 和 对 的梯度,然后该梯度用于更新模型的参数。这个算法就是 Almeida-Pineda 算法[9]。之所以要求 为压缩映射,也是因为只有 为压缩映射时,AP 才能得到一个收敛的梯度。
-
GNN的基础理论是不动点理论,这就意味着GNN沿时间展开的长度是动态的,是根据收敛条件确定的,而RNN沿时间展开的长度就等于序列本身的长度。
-
GNN每次时间步的输入都是所有结点 的特征,而RNN每次时间步的输入是该时刻对应的输入。同时,时间步之间的信息流也不相同,前者由边决定,后者则由序列的读入顺序决定。
-
GNN采用 AP 算法反向传播优化,而RNN使用BPTT(Back Propogation Through Time)优化。前者对收敛性有要求,而后者对收敛性是没有要求的。
-
GNN循环调用 的目标是得到每个结点稳定的隐藏状态,所以只有在隐藏状态收敛后才能输出;而RNN的每个时间步上都可以输出,比如语言模型。
GNN的局限
-
GNN只将边作为一种传播手段,但并未区分不同边的功能。虽然我们可以在特征构造阶段()为不同类型的边赋予不同的特征,但相比于其他输入,边对结点隐藏状态的影响实在有限。并且GNN没有为边设置独立的可学习参数,也就意味着无法通过模型学习到边的某些特性。
-
如果把GNN应用在图表示的场景中,使用不动点理论并不合适。这主要是因为基于不动点的收敛会导致结点之间的隐藏状态间存在较多信息共享,从而导致结点的状态太过光滑(Over Smooth),并且属于结点自身的特征信息匮乏(Less Informative)。
状态更新
-
用结点特征初始化各个结点的(部分)隐藏状态。
-
对整张图,按照上述状态更新公式固定迭代若干步。
-
对部分有监督信号的结点求得模型损失,利用BPTT算法反向传播求得和GRU参数的梯度。
实例1:到达判断
实例2:语义解析
-
首先,通过表格建立对应的Graph。再利用GGNN的方法计算每个Header的隐藏状态。
-
然后,在Seq2seq模型的编码阶段(Encoding),用每个输入的自然语言单词的词向量对表格所有Header的隐藏状态算一个Attention,利用Attention作为权重得到了每个自然语言单词的图感知的表示。
-
在解码阶段(Decoding),如果输出的是表格中的Header/Table这类词,就用输出的向量与表格所有Header/Table的隐藏状态算一个分数,这个分数由提供的。实际上是一个全连接层,它的输出实际上是SQL单词与表格中各个Header/Table的联系程度。为了让SQL的每个输出都与历史的信息一致,每次输出时都用之前输出的Header/Table对候选集中的Header/Table打分,这样就利用到了多表的信息。
-
循环神经网络的好处在于能够处理任意长的序列,但它的计算必须是串行计算若干个时间步,时间开销不可忽略。所以,上面两种基于循环的图神经网络在更新隐藏状态时不太高效。如果借鉴深度学习中堆叠多层的成功经验,我们有足够的理由相信,多层图神经网络能达到同样的效果。
-
基于循环的图神经网络每次迭代时都共享同样的参数,而多层神经网络每一层的参数不同,可以看成是一个层次化特征抽取(Hierarchical Feature Extraction)的方法。
参考文献
<section style="white-space: normal;line-height: 1.75em;text-align: center;"><strong style="color: rgb(0, 0, 0);font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;letter-spacing: 0.544px;widows: 1;background-color: rgb(255, 255, 255);max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong>完<strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong></span></strong></span></strong></section><pre><pre style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;white-space: normal;font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;widows: 1;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section><section style="margin-bottom: 15px;padding-right: 0em;padding-left: 0em;max-width: 100%;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 25.5938px;letter-spacing: 3px;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;font-size: 16px;font-family: 微软雅黑;caret-color: red;box-sizing: border-box !important;overflow-wrap: break-word !important;">为您推荐</span></strong></span></section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;">图灵奖得主Yann LeCun《深度学习》春季课程</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;">你一定从未看过如此通俗易懂的YOLO系列解读 (下)</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;">22课时、19大主题,CS 231n进阶版课程视频上线<br /></section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;">数据分析入门常用的23个牛逼Pandas代码</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="color: rgb(87, 107, 149);font-size: 14px;">如何在科研论文中画出漂亮的插图?</span><br /></section></section></section></section></section></section></section></section></section>
本篇文章来源于: 深度学习这件小事
本文为原创文章,版权归知行编程网所有,欢迎分享本文,转载请保留出处!
内容反馈