《Deep Learning on Graphs: A Survey》学习笔记【简略】

《Deep Learning on Graphs: A Survey》

《Deep Learning on Graphs: A Survey》

Zhang Z, Cui P, Zhu W. Deep learning on graphs: A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2020.

18年的一篇GNN综述,读完之后,感觉GCN那一部分对我帮助还不小,帮我理清了脉络,也可能是因为之前把《Graph Representation Learning》这本书看完了,所以阅读过程还比较顺利。后面的VGAE和图强化学习看的就比较粗,以后要是用到了再去看吧。

希望这篇笔记能够对后面的开题报告以及研究有所帮助吧。时间关系,只写一些对我近期可能有帮助的内容,毕竟本科毕设也不期望能搞出什么大事情,所以比较简略。


Abstract

图数据无处不在,但是由于图数据自身结构的特殊性,对图数据应用深度学习方法有很多挑战。这篇综述主要是回顾各种图的深度学习模型,并将模型分为3类:

  1. 半监督方法:GNN、GCN
  2. 无监督方法:GAE
  3. 最新进展:Graph RNN、Graph RL

最后还会说一下模型的应用和未来发展方向。

1 INTRODUCTION

前面扯了一堆深度学习方法怎么怎么好、图数据又多么重要,其实就是想表达:我们非常需要使用DL方法研究图数据,但是有很多挑战和问题亟待解决,不然也不会有这篇文章了。几个挑战:

  1. 不规则域: 图数据没有像图片那样规则的网格结构,重新定义卷积、池化?
  2. 不同的任务和结构
  3. 可扩展性和并行性: 是否能扩展到大型图上面?时间复杂度是否可行?
  4. 交叉学科
在这里插入图片描述

之前也提到了,本文将模型分为3类。办监督的方法使用节点属性(特征)和标签来进行端到端训练;无监督方法使用GAE来进行表示学习;最新进展使用了其他独特的方法。


在这里插入图片描述

Related works.
主要说了一下图的DL方法和网络嵌入(Network embedding)的联系和区别。它们俩有交集:使用DL方法去做图的嵌入表示学习。但网络嵌入也可以不使用DL方法,图的DL方法也不只着眼于网络嵌入这个任务。

2 NOTATIONS AND PRELIMINARIES

符号表,2333,基本上看过一遍《Graph Representation Learning》都会对它们相当熟悉,即使换了一个“马甲”。


在这里插入图片描述

需要解决的任务主要分为2个领域:(其实我觉得应该分为3类。。)

  1. 节点级(node-level)任务:节点分类、 链接预测等。
  2. 图级(graph-level)任务:图分类、图生成等。

\color{#FF3030}{\boldsymbol{以下才是正文}}😂

3 GRAPH NEURAL NETWORKS (GNNS)

本文把在卷积操作出现之前的方法单独视为GNN(半监督),但其实很多地方把所有使用DL方法学习图数据的模型,统称为GNN,还挺容易混淆的。
GNN和下一节的GCN十分相似,都使用了在邻居之间交换信息(MPNN)这一框架,不同之处在于早期GNN的每一层都不相同,而GCN的每一层都是相同的。
感觉对我没什么帮助,也不是重点,直接跳过一些细节。

4 GRAPH CONVOLUTIONAL NETWORKS (GCNS)

这一部分是我本次关注的重点!

还是老问题,很多地方把 「Kipf and Welling」 文章中的模型定义为GCN,而在本文中将使用了卷积操作的模型统称为GCN。

在这里插入图片描述

4.1 Convolution Operations

4.1.1 Spectral Methods

提到频域方法,第一反应应该想到这些名词:「拉普拉斯矩阵、图卷积、图傅里叶变换、滤波器」等等。学过通信DSP的相关知识可能会好一些,因为就是类比的信号处理,可惜cs专业并没有学过,现在一看到信号的傅里叶变换等概念就发蒙,只能先跳过去。
主要讲一下我自己对于图中的信号u^l\in R^N(signal)和节点隐藏表示h^l\in R^{f^l}(hidden representation)的一些理解吧。
H^l= \begin{bmatrix} &\cdots&h^l&\cdots\\ \vdots&&&\\ u^l&&&\\ \vdots&&&\\ \end{bmatrix},\in R^{N\times f^l}
从公式中可一直观的看到它们和隐藏层矩阵之间的关系。图中的信号可以看成是列,隐藏表示可以看作是行。一开始定义的各种变换和操作都是针对图信号的,经过后面的发展,逐渐演变成了适用于NN的隐藏表示的形式。
总之,通过图卷积操作(不熟悉的话看一下《GRL_Book》恶补一下),我们可以定义图信号的滤波操作,这也是后续各种空域(spatial)方法的基础。
u'=\left(Q \Theta(\Lambda) Q^T\right)u
在文章中\Theta统一代表可学习的参数。
频域方法虽然产生了聚合邻域这一想法,但是有2个主要缺陷:

  1. L矩阵分解的时间复杂度至少O(N^2),无法扩展大大型图上。
  2. 滤波器依赖于Q,参数无法在多个图中共享。

4.1.2 Efficiency Aspect

以下介绍的方法都是空域(spatial)方法。


一个比较经典的模型是ChebNet。后面需要重点阅读。

Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering[J]. arXiv preprint arXiv:1606.09375, 2016.

它的主要思想是多项式滤波器+切比雪夫展开:
\Theta(\Lambda)=\sum_{k=0}^{K-1}\theta_k \mathcal T_{k}(\tilde \Lambda)\\ u'=\sum_{k=0}^{K-1}\theta_k\mathcal T_{k}(\tilde L)u=\sum_{k=0}^{K-1}\theta_k \overline u_k
最后简化到了这个程度,并且\overline u_k还可以通过递推式子得到。时间复杂度降到了O(KM),并且每次滤波(卷积)相当于聚合了每个节点的K跳邻居信息。


最经典的空域卷积模型莫过于Kipf and Welling文章中提到的GCN模型了。后面需要重点阅读。

Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

它简化了滤波器,每次卷积只聚合一阶(直接)邻居信息(相当于K=1),并且使用了对称标准化+自循环更新。写成矩阵的形式,就开始有了NN的味道了。
H^{l+1}=\rho\left((\tilde D^{-\frac12}\tilde A\tilde D^{-\frac12})H^l\Theta^l \right)
之前在笔记中多次提到过GCN,在这里就不多说了。


4.1.3 Multiple Graphs Aspect

如果需要训练多个不同大小的图,并且想在训练的时候让不同的图参数共享,可以使用这一部分介绍的模型。
然而,我看了一下那几个引文网络数据集,发现图的数量都是1,那么就没有这部分什么事了,就不写笔记了。

4.1.4 Frameworks


主要介绍了主流的消息传递框架MPNN,和《GRL_Book》中提到的差不多,有时间需要看一下。

Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry[J]. arXiv preprint arXiv:1704.01212, 2017.

大体上比较熟了,懒得再写一遍了。文章提到了添加一个和所有节点全连接的"master" node,来加速长距离的消息传递,这一点之前没有注意到。


接下来,是经常被用来进行实验的GraphSAGE模型,里面的消息传递操作也相当经典。后面需要重点阅读。

Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[C]//Advances in neural information processing systems. 2017: 1024-1034.

基本就是根据MPNN框架照猫画虎,消息传递操作如下:
m_i^{l+1}=Aggregate^l\left(\{h_j^l,\forall j\in N(i)\}\right)\\[2ex] h_i^{l+1}=\rho \left(\Theta^l[h_i^l\oplus m_i^{l+1}]\right)
更新函数没什么新东西,顶多是拼接操作新奇一点(可能借鉴了跳跃连接?);给出了3个聚合函数:

  1. 逐元素平均
  2. LSTM:这个需要给节点排序,不知道如何保证排列不变性的?
  3. max池化

后面也有介绍GN这样更通用(更吓人)的一般性框架,暂且搁置吧。
最常见的选择是改进版本的GCN卷积层+MPNN框架。

4.2 Readout Operations

这部分说白了就是池化操作,在GNN中美其名曰readout。它将所有节点的嵌入表示进行池化得到整张图的嵌入表示,然后再拿着这个图级表示,去做一些诸如图分类这样的任务。

Order invariance
顺序不变性,或者说排列不变性,这是一个老生常谈的问题了。通俗来说就是,同一张图的各种矩阵,不论它们最初的节点排列顺序是怎样的,最终学习出来的图级表示必须是相同的。这部分和图同构测试也有一些关系。

4.2.1 Statistics

满足排列不变性+能聚合所有节点嵌入表示最简单的方法是直接sum,max或average。也就是说,通过对最后一层得到的节点嵌入表示进行上述简单的操作,就可以得到图级表示。但由于它过于简单粗暴,就导致损失了很多结构信息。
当然,还有一些带参数的方法,但也都是大同小异,表达能力有限。

4.2.2 Hierarchical clustering

另一种方法是层次聚类,它一般和之前的卷积层一起进行端到端的训练。


比较早的池化模型是DiffPool。后面需要重点看一下。

Ying Z, You J, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[C]//Advances in neural information processing systems. 2018: 4800-4810.

它的主要思想是,学习簇分配矩阵S,然后通过S去得到一个坍缩后的图(新的A和X),重复这个过程直至收敛。每次进行坍缩,图的簇数都会减少。
关于这个模型,之前的笔记说的也比较清楚了,不再详细展开。


4.2.3 Others

其他方法,比如说增加一个代表整张图的特殊节点等。
一般来说,前两种方法出现的比较多。

4.3 Improvements and Discussions

一些改进策略(大方向),对于某些模型的改进可能会有一些帮助。

4.3.1 Attention Mechanism

不同重要程度的邻居需要区别对待,聚合的时候来一个加权操作,这就是注意力机制。


在实践中,将所有邻居同等对待或人为去指定哪个节点更重要,往往不太行。注意力机制是一个比较好的改进思路。
最早的图注意力模型是GAT。后面需要重点看一下。

Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.

它主要的各种变体都是如何去计算注意力权重\alpha_{ij}。此外,它还提出了多头注意力机制。这个模型,之前的笔记也写过,不再进行展开。


4.3.2 Residual and Jumping Connections

一方面是受到了ResNet的启发,一方面是模型存在过平滑的问题,冗余连接/跳跃连接开始被应用于GNN的模型中。
在GCN模型中,Kipf and Welling也引入了冗余连接,以保留上一层的结果。这样做可以缓解过平滑问题,增加模型的深度。
H^{l+1}=\rho\left((\tilde D^{-\frac12}\tilde A\tilde D^{-\frac12})H^l\Theta^l \right)+H^l


CLN模型看起来更聪明一点,类似于一种加权求和,权重是可学习的参数。

Pham T, Tran T, Phung D, et al. Column networks for collective classification[J]. arXiv preprint arXiv:1609.04508, 2016.

h_i^{l+1}=\alpha_i^l \odot \tilde h_i^{l+1}+(1-\alpha_i^l)\odot h_i^l


JK-Nets把最后一层和之前的所有层都进行一个连接,得到最终的嵌入表示。

Xu K, Li C, Tian Y, et al. Representation learning on graphs with jumping knowledge networks[J]. arXiv preprint arXiv:1806.03536, 2018.


实验表明,添加跳跃连接是改进模型表达能力的一个很好的方法。

4.3.3 Edge Features

这些策略一般用在多关系图中,暂时还用不到,溜了。

4.3.4 Accelerating by Sampling

在大规模图上,效率问题一直是瓶颈,特别是在模型很复杂的时候。在一个十几亿级别的图上,如果你还企图搞个O(N^2)的操作,那真是太naive了。基本上,还是需要通过牺牲一些信息进行采样,来达到效率和表达能力之间的权衡。
在《GRL_Book》的第8章中提到过,其实真实图中的节点度是服从幂律分布的。也就是说,总会有极个别度数超级高的节点,它们邻居节点数量的增长速度十分吓人。
GraphSAGE采样固定数量的邻居节点,PinSage使用随机游走方法采样邻居节点。


另一种不同的策略是FastGCN模型。

Chen J, Ma T, Xiao C. Fastgcn: fast learning with graph convolutional networks via importance sampling[J]. arXiv preprint arXiv:1801.10247, 2018.

它从积分变换的角度来看问题,听起来就很高端:将节点解释为符合i.i.d.的样本,图卷积操作看作是积分变换。有时间再去看一下paper,根本不知道它在说什么。


4.3.5 Inductive Setting

我觉得解释为归纳学习好理解一点。归纳学习的典型特点:训练时使用带标签的V_{train},测试时使用训练时不可见的V_{ind}
GraphSAGE、GAT、FastGCN等模型都属于归纳GCN模型,它们训练的也都是有特征的图。

4.3.6 Random Weights

通过设置随机权重,未经训练的GCN模型也可以提取到有意义的节点特征?

5 GRAPH AUTOENCODERS (GAES)

AE属于无监督学习的范畴,在图中一般称为GAE。这些模型的架构都离不开编解码器模型,《GRL_Book》对这个框架中介绍的相当详细了。


在这里插入图片描述

5.1 Autoencoders

这一部分有一些学习节点嵌入表示的模型还是很有参考价值的,因此,直接列举几个姑且、可能对我毕设有帮助的几个模型。


结构化的深层嵌入网络SDNE模型。

Wang D, Cui P, Zhu W. Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 1225-1234.


编码器使用了GCN的GC-MC模型。

Berg R, Kipf T N, Welling M. Graph convolutional matrix completion[J]. arXiv preprint arXiv:1706.02263, 2017.

5.2 Variational Autoencoders


之前看了好几次VGAE模型都没有看懂,现在发现遇到的次数多了,好像也慢慢有点感觉了?!

Kipf T N, Welling M. Variational graph auto-encoders[J]. arXiv preprint arXiv:1611.07308, 2016.

那几个后验分布还是让我有点晕头转向,之前的笔记也有写过这个。
它的encoder使用了2个独立的GNN,分别去计算嵌入表示H的均值和方差,以便使用高斯(正态)分布进行H的采样。decoder说是要算后验概率P(A|H),其实在VGAE中也就是使用了简单的内积解码器。最后就是那个带有KL散度的特别恶心的loss。


其他模型都是对VGAE做出的改进,直接忽略了,还是要慢慢来。

5.3 Improvements and Discussions

对GAE的一些改进措施。

5.3.1 Adversarial Training

使用生成对抗网络GAN(就是淦),进行对抗训练。把encoder看作是generator,然后使用discriminator区分到底是假的还是真的。这种极大极小联合优化感觉还蛮困难的,之前也有看到很过模型的名字后面都会加一个GAN。

5.3.2 Inductive Learning and GCN encoder

encoder使用GCN可以继承GCN归纳学习的良好性质。很多模型都会将GAE和GCN结合使用,效果更好。

5.3.3 Similarity Measure

如何选择相似性度量,目前还没有清晰的判断依据。

6 RECENT ADVANCEMENT

最新进展。。。聚焦于图生成领域,目前和我没什么太大关系。


在这里插入图片描述

6.1 Graph Recurrent Neural Network

Graph RNN将RNN的知识用到了图的层面。

6.2 Graph Reinforcement Learning

Graph RL主要用到了强化学习的一些知识。

7 CONCLUSION AND DISCUSSION

总结并没有什么东西。主要介绍了一下应用和未来方向。

  1. 如何处理不同类型的图。同构、异构图,有符号图,超图等等。
  2. 如何处随时间变化的动态图。
  3. 在其他学科领域的可解释性。
  4. 如何有效地组合各种模型架构。
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,723评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,003评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,512评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,825评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,874评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,841评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,812评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,582评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,033评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,309评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,450评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,158评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,789评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,409评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,609评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,440评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,357评论 2 352

推荐阅读更多精彩内容