admin管理员组文章数量:1565366
摘要:
深度学习兴起,数据一般用欧式空间表示,但出现的图数据-非欧氏空间。
本文工作:综述机器学习和数据挖掘中的GNN,①分为4类:循环图神经网络,卷积图神经网络,图自动编码器,时空图神经网络。②讨论:GNN在各个领域应用,③总结代码、数据集和模型评估
引言
神经网络成功原因:计算能力增强,大数据获取,神经网络可获取数据欧式空间中的潜在表示的强大能力
很多数据开始只能用图节点进行表示,GNN提出前原有算法存在问题:①图大小不确定,邻居数量不确定②原有算法假设数据之间是独立的
相关工作:首次提出图和流形的GCN-》卷积GNN-》解决图嵌入GNN-》GNN解决关系数据学习-》总结注意力机制在GNN上的应用
贡献:①提出对GNN的四种分类②提出对所有GNN分类的代表模型的综述③开源代码等数据丰富
④未来方向:分析现有模型的缺点以及模型深度等
内容:图基础知识-》分类-》模型综述-》应用-》挑战和总结
1. 背景和定义
GNN历史:
①递归RecRNN(根据节点邻居信息迭代学习节点表示,缺点:计算量大)
②卷积GNN(CNN在图上的应用)-ConvGNNs:
1)基于谱的方法:GCN
[1]M. Henaff, J. Bruna, and Y . LeCun, “Deep convolutional networks on
graph-structured data,”arXiv preprint arXiv:1506.05163, 2015.
[2=]M. Defferrard, X. Bresson, and P . V andergheynst, “Convolutional
neural networks on graphs with fast localized spectral filtering,” in
Proc. of NIPS, 2016, pp. 3844–3852.
[3]T. N. Kipf and M. Welling, “Semi-supervised classification with graph
convolutional networks,” inProc. of ICLR, 2017.
[4]R. Levie, F. Monti, X. Bresson, and M. M. Bronstein, “Cayleynets:
Graph convolutional neural networks with complex rational spectral
filters,”IEEE Transactions on Signal Processing, vol. 67, no. 1, pp.
97–109, 2017.
2)基于空域的方法(更早提出)
A. GNN和图嵌入
GNN可以用于进行图嵌入,挖掘节点高阶表示,保存节点结构信息和节点内容表示。GNN和图嵌入的区别:GNN是用于多重任务的神经网络,图嵌入是只针对相同任务的多种方法,不止深度学习方法。联系:GNN可以用图自编码器实现图嵌入。
GNN和图核方法
联系:都是进行图分类的重要方法
区别:图核函数用核函数计算图之间的相似性,(比如SVM)可用于图监督学习,也需要图表示,但是是确定的,不需要学习的,计算容易到瓶颈。GNN根据学习到的图表示,效率更高。
B.定义
字母定义、有向图
时空图:随着时间变化节点特征也在变化的属性图,
3. 分类和框架
① RecGNN:
在RNN框架中让节点不停和邻居交换信息最终得到稳定表示
② convGNN
和RecGNN不同,堆积多个ConvGNN获取高阶关系,也是根据节点邻居特征和节点自身特征获得节点特征。是其他复杂GNN的中心。
比如,多层ConvGNN节点分类,池化:将图转化成子图,readout:通过取子图的平均/和操作得到图表示
③图自编码器:无监督学习节点/图的向量表示,先编码表示,再用表示进行重构(结构信息,比如邻接矩阵)。编码器先使用图卷积得到节点表示,再用解码器计算向量之间的距离,得到邻接矩阵重构图,使得邻接矩阵和实际邻接矩阵差异最小,训练GAE
④时空图神经网络STGNN
学习时空图的隐藏模式,比如交通速度预测,集合图卷积和RNN、CNN分别挖掘空间依赖和时间依赖。举例:
用A和X计算的图卷积得到空间依赖性,沿着时间轴的1d-cnn捕捉时间依赖性。
B.框架
应用分类:
①节点级:节点回归或者节点分类,用RecGNN,ConvGNN等用信息传播获取节点高阶表示
②边级别:边分类或者链路预测,将从GNN中获得的两个节点的隐层状态作为输入,再用相似函数或者神经网络预测边的标签或者连接
③图级别:图分类问题
训练框架:
①节点级分类半监督学习:构建多层图卷积对部分未加标签的节点进行分类
②图级别分类的监督学习:构建多层图卷积、池化和readout层,对图进行分类,图卷积获取节点高阶表示美图池化层用于下采样,readout层将节点表示转化成图表示。
③图嵌入的无监督学习:两种方法:1)使用自编码器2)使用负采样方法,采样部分节点对作为负采样对,图中有链接的作为正采样样本。
对一些RecGNN和ConvGNN模型的总结,包括模型输入,时间复杂度(大多是O(m))
4. RecGNN
① GNN*:有向无环图-》无向图
交换邻居信息得到节点的状态,
其中,对参数方程f的要求是收缩映射,当f(·)为神经网络时,参数的雅可比矩阵必须加一个惩罚项(正则化项)。当满足收敛准则时,将最后一步节点隐藏状态转发到读出层。节点的状态传播(直到稳定)和计算参数梯度(一次梯度)是交替进行的。
② GraphESN
用回声状态网络扩展GNN*,GraphESN由编码器和输出层组成。编码器是随机初始化的,不需要训练。它实现了一个收缩状态转移函数,周期性地更新节点状态,直到全局图状态收敛。然后,以固定节点状态作为输入对输出层进行训练。
③GGNN
门控图神经网络(GGNN)[17]采用门控递归单元(GRU)[81]作为递归函数,将递归减少到固定的步数。其优点是,它不再需要约束参数来确保收敛。节点隐藏状态由其先前的隐藏状态和其相邻的隐藏状态(定义为)更新
使用BPTT更新参数,对于大图不合适,因为要把所有节点的中间状态都存储上。
④SSE
随机稳态嵌入(SSE)提出了一种可扩展到大图[18]的学习算法。SSE以随机和异步的方式循环更新节点隐藏状态。它可以选择采样一批节点用于状态更新,也可以采样一批节点用于梯度计算。为保持稳定性,将SSE的递归函数定义为历史状态和新状态的加权平均,其形式为
其中α为超参数,h(0)是随机初始化的。理论上并没有证明节点状态会逐渐收敛到不动点。
5 卷积图神经网络
1)和RecGNN区别:卷积层参数分别是不同和相同的
2)
①基于谱的(拉普拉斯特征值):无向图,引入图信号处理的过滤器,图卷积视为移除图信号的噪音
将节点特征通过谱卷积转换成新的特征:发展历程:谱GNN-》chebnet-》GCN
理解:
②基于空域的:和RecGNN思想相同:信息传播,发展迅速,聚合节点邻居表示和自身表示得到节点表示。
NN4G-》GCMM(概率模型)-》DCNN-》 PGC-DGCNN-》MPNN
1)NN4G:
转换成矩阵:
和GCN的区别:A是没有归一化的,容易出现隐层状态规模大小不同。
2)DCNN:假设图卷积是一个扩散过程,扩散图卷积:P为概率转移矩阵P=D^-1*A,f为激活函数
问题:离得越远的节点的信息越难使用上
3)PGC-DGCNN:用S(j)矩阵表示n路邻接矩阵,如果节点m到节点n的最短路径是j,则s(m,n)(j)=1
4)MPNN:消息传递框架,空间图卷积的一般框架,执行k步消息传递迭代(空间图卷积)
Uk,Mk是带有可学习参数函数
然后应用于下游任务:比如图级别的任务:用readout函数进行转换:不同的readout函数[22][85][86][87]
5)GIN(图同构网络):根据嵌入可以区分出不同的网络结构,给中心节点加了一个可学习的权重,
6)GraphSage:解决节点邻居数量不均衡(过少或者过多)的问题,采样邻居再聚合所有邻居和中心节点的表示
fk表示聚合函数,节点顺序对聚合函数不应该产生影响。SN(v)表示采样v的邻居(邻居权重是相同的)
7)GAT:邻居权重不同,需要学习
① GCN和GAT的区别:权重设置不同
GCN的节点对中心节点的权重是提前确定好的(AXW)-A是进行了标准化,即,但是GAT根据中心节点特征和邻居节点特征确定节点权重。
② GAT的定义:
权重定义:
可学习参数:a
③ GAT的进一步改进:GAAN[48](用自注意力机制对多头注意力进行加权,得到进一步的)-》
GeniePath[55]提出类似LSTM的门信息控制图卷积层信息流
PS: 多头注意力是求出多个节点的加权表示,将他们concat后再乘以W得到最终的节点表示
混合模型网络Mixture model network MoNet:采用另外一种方法计算节点邻居的权重
PATCHY -SAN:通过某些标准对节点邻居进行排序,得到权值共享以及节点的重要性排序
LGCN:基于节点特征信息对节点邻居进行排序
空间模型提升效率的方法:
①对于大图:graphsage-Kpop采样,对每个节点进行层级采样
②fastGCN [49]:每个卷积层独立随机选取固定的节点,缺点:因为是随机选取,所以层和层之间的关系是稀疏的
③自适应分层抽样方法:下层节点采样基于上层节点采样,和fastgcn相比提高了模型的准确率,但采样成本更高
④StoGCN:随机训练GCN,降低了接受域
⑤cluster-GCN:图聚类算法采样子图,对子图中的节点进行卷积
卷积GNN的时间空间复杂度:
m是边的个数,k是层数,s是batchsize,r是对每个节点进行采样的个数,每层隐层特征保持不变为d
从图中可以看出:graphsage用时间换取空间复杂度,stogcn时间复杂度最高,但是在采样个数很小的时候能实现最优效率,cluster-gcn时间复杂度不变,但有最低的空间复杂度
谱方法和空间模型方法对比:
谱方法基于图信号理论基础,空间方法由于灵活性等效率更高更好应用
①空间方法效率更高,谱方法因为要进行整张图的特征计算效率更低,而且空间方法只需要进行消息传播和节点采样,更容易应用在大规模图上
②谱方法中的图拉普拉斯泛化能力不强,不能应用在不同的图上,假设图的结构是固定的(因为只要图结构改变,特征就会改变)。空间模型应用在局部节点上,所以可移植性比较强,可以应用在不同的结构中。
③谱方法应用在无向图中,但空间方法应用广泛,比如有向图,边输入,以及异质图,信号图等等,因为这些图输入可以较容易的合成到聚合函数中。
③ 图池化模块
根据池化目标和角色,图池化分为:
1)下采样节点,减少模型参数,避免过拟合,和计算复杂性
2)readout操作基于节点表示得到图级别的表示
池化方法:
1)特征分解对图聚类进行划分 [100]
2)mean/max/sum池化最常用,或者使用attention改进这些池化[17], [27], [46] ,缺点:嵌入有效性不高,没有考虑到图大小,永远只生成固定大小的输出。-》[101]提出set2set方法可以生成输入大小变化的内存大小。然后用LSTM提取顺序信息。;[100]提出按照某种顺序重排节点顺序;DGCNN[52]根据图结构信息对图节点特征进行排序,提出sortpooling,并固定图的大小,少去多补0。;diffpool;SAGPool(既考虑节点特征,又考虑拓扑结构;注意力机制)
④理论层面的讨论
接受域形状:节点的接受域-对节点最终特征产生影响的节点集合
VC维:衡量模型复杂度,即能打散的最多节点个数
图同构:GNN如GCN、graphsage都无法区分同构图,但如果聚合函数或者readout函数是单射的(一对一),则可以区分
6 图自编码器
7 时空图神经网络
假设连接节点之间都有相互依赖关系,对动态节点进行建模。一般方案:将图卷积过滤隐层和输入特征,并将其加入到RNN中。表示:
历史案例:
① RNN+图卷积:
1)只使用节点或者边级别的RNN:
GCRN[71] 将LSTM+chebnet DCRNN[18]:扩散图卷积层+GRU,预测未来K布节点值
2)既使用节点也使用边级别的RNN:
structure RNN
②因为基于RNN的方法迭代传播太耗时,可能出现梯度爆炸和梯度消失的问题
-》CNN的方法
1D-CNN学习时间依赖,图卷积学习结构依赖
CGCN[74],ST-GCN【75】
③学习节点潜在空间依赖:
学习自适应节点结构关系Graph WaveNet:
8 应用
①基准图数据集
②评估指标和开源实现:
最常见应用:节点分类和图分类
节点分类:
使用测试集上的平均准确率和F1分数评估,存在问题:实验过程中使用相同的训练评估测试数据集会低估泛化误差,且不同模型使用的训练方式不同,如超参调整以及参数初始化等
图分类:
十折交叉验证
开源实现:几何学习库:pytorch geometric,开源库:DGL
③实际应用
节点分类、网络嵌入、图生成、时空图预测、节点聚类、连接预测、图划分
不同领域:
①cv:
场景图生成(生成一种语义化的图结构,节点对应图中的物体,关系代表节点之间的属性关系等):给出真实图<->场景图结构
点云分割分类;识别视频中人体动作[73][75]
②nlp:
使用最多:根据文本之间的关系进行文本标签分类、
根据依存句法树(句子中单词之间的句法关系)聚合单词表示,实现机器翻译(比如:syntaic GCN)
graph-to-sequence
sequence-to-graph【17】
③交通:
交通速度、交通流量预测、交通道路密度预测
出租车需求预测
④推荐系统:以项目和用户为节点
通过项目和项目、用户和用户、用户和节点之间的关系、内容信息,可以获取高质量推荐。
推荐系统关键:获取节点对用户的重要性得分。可以看做为链接预测
已有工作:【16】】【162】提出GAE,使用convGNN作为编码器,【163】将RNN和图卷积结合在一起学习已有排序
⑤化学
分子化合物,原子为节点,化学键为边
节点分类、图分类、图生成。目的是学习分子指纹[85]、[86]、预测分子性质[27]、推断蛋白质界面[164]、合成化合物[65]、[69]、[165]。
⑥其他
程序验证[17]、程序推理[166]、社会影响预测[167]、对抗攻击预防[168]、电子健康记录建模[169]、[170]、脑网络[171]、事件检测[172]和组合优化[173]
9 未来方向
①模型深度:随着模型深度增加,所有节点收敛到同一节点。
②可扩展性权衡:无论是采样还是聚类,模型都会丢失部分信息,比如采样可能使节点错过对其有影响的节点邻居,通过聚类可能使得图缺失一种独特结构模式。权衡算法的可扩展性和图的完整性
是未来的一个研究方向
③异构性:当前GNN基本都是针对同一种节点和边的同质图进行构建,对于异构图即不同节点类型形式的输入如文本和图片研究较少
④动态性
随着时间变化,图的节点和边会不消失和出现,虽然时空GNN可以解决图的部分动态性,但是并没有解决动态空间关系下图卷积的实现。
本文标签: SurveyComprehensiveGraphGNNNeuralNetworks
版权声明:本文标题:A Comprehensive Survey on Graph NeuralNetworks(GNN综述) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1725896873a1047748.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论