图机器学习(GML)&图神经网络(GNN)原理和代码完成前置学习系列二

 时间:2023-04-03 17:35:50      开云作者: 开云科技

  项目链接:欢迎fork欢迎三连!文章篇幅有限,部分程序出图纷歧一展现,概况进入项目链接即可

  图机器学习(GML)&图神经网络(GNN)原理和代码完成(PGL)[前置学习系列二]

  networkx :NetworkX 是一个 Python 包,用于创立、操作和研讨杂乱网络的结构、动力学和功用

  在链接猜测中,给定图G,咱们的方针是猜测新边。例如,当图未被彻底查询时,或许当新客户参加渠道(例如,新的LinkedIn用户)时,猜测未来联系或缺失边是很有用的。

  GNN链接猜测使命,即猜测图中两个节点之间的边是否存在。在Social Recommendation,Knowledge Graph Completion等运用中都需求进行链接猜测。模型完成上是将链接猜测使命当作一个二分类使命:

  例如:AUC值在一些场景下例如大规模引荐体系或信息检索,模型需求评价top-k猜测成果的精确性,因而关于链接猜测使命还需求一些其他的评价方针来衡量模型终究作用:

  MR, MRR, Hit@n方针意义:假定整个图谱n个实体,评价前先进行如下操作:

  (1)将一个正确的三元组(h,r,t)中的头实体h或许尾实体t,顺次替换成整个图谱中的其他一切实体,这样会发生n个三元组;

  (2)对(1)中发生的n个三元组别离核算其能量值,例如在TransE中核算h+r-t的值,这样n个三元组别离对应自己的能量值;

  (3)对上述n个三元组依照能量值进行升序排序,记载每个三元组排序后的序号;

  (4)对一切正确的三元组都进行上述三步操作MR方针:将整个图谱中每个正确三元组的能量值排序后的序号取均匀得到的值;

  MRR方针:将整个图谱每个正确三元组的能量排序后的序号倒数取均匀得到的值;

  Hit@n方针:整个图谱正确三元组的能量排序后序号小于n的三元组所占的份额。因而关于链接猜测使命来说,MR方针越小,模型作用越好;

  MRR和Hit@n方针越大,模型作用越好。接下来本文将在Cora引文数据集上,猜测两篇论文之间是否存在引证联系或被引证联系

  在链路猜测中,咱们仅仅测验在节点对之间树立相似性衡量,并链接最相似的节点。现在的问题是辨认和核算正确的相似性分数!

  设$N(i)$是节点$i$的一组街坊。在上图中,节点$i$和$j$的街坊能够标明为:

  公共街坊:$S(i,j) = \mid N(i) \cap N(j) \mid$,即公共街坊的数量。在此示例中,分数将为2,由于它们仅同享2个公共街坊。

  Adamic-Adar指数:$S(i,j) = \sum_ \frac {\log \mid N(k) \mid}$。 关于节点i和j的每个公共街坊(common neighbor),咱们将1除以该节点的街坊总数。这个概念是,当猜测两个节点之间的衔接时,与少数节点之间同享的元素比较,具有非常大的邻域的公共元素不太重要。

  咱们怎么进行链接猜测的评价?咱们有必要躲藏节点对的子集,并依据上面界说的规矩猜测它们的链接。这相当于监督学习中的train/test的区分。 然后,咱们评价密布图的正确猜测的份额,或许运用稀少图的规范曲线下的面积(AUC)。

  给定一个未符号某些节点的图,咱们期望对这些节点的标签进行猜测。这在某种意义上是一种半监督的学习问题。

  处理这些问题的一种常见办法是假定图上有必定的滑润度。滑润度假定指出经过数据上的高密度区域的途径衔接地址或许具有相似的标签。这是标签传达算法背面的首要假定。

  标签传达算法(Label Propagation Algorithm,LPA)是一种快速算法,仅运用网络结构作为辅导来发现图中的社区,而无需任何预界说的方针函数或关于社区的先验信息。

  单个标签在密布衔接的节点组中敏捷占有主导地位,可是在穿过稀少衔接区域时会遇到问题。

  该算法将生成猜测矩阵$F \in R^$,咱们将在下面胪陈。然后,咱们经过查找最或许的标签来猜测节点的标签:

  猜测矩阵是矩阵$F^{\star}$,其最小化滑润度和精确度。因而,咱们的成果在滑润性和精确性之间进行权衡。

  假如您想进一步了解这个主题,请重视图函数的滑润度和流形正则化的概念。斯坦福有一套很好的标签图能够下载:

  接下来咱们用python来完成节点标签的猜测。 为了给咱们运用到的标签添加更多的特征,咱们需求运用来自Facebook的实在数据。你能够再这儿下载,然后放到facebook途径下。

  Facebook 数据现已过将每个用户的 Facebook 内部 id 替换为新值来匿名化。此外,尽管现已供给了来自该数据集的特征向量,但对这些特征的解说却很含糊。例如,假如原始数据集或许包括特征“political=Democratic Party”,则新数据将仅包括“political=anonymized feature 1”。因而,运用匿名数据能够确认两个用户是否具有相同的政治派别,但不能确认他们各自的政治派别代表什么。

  嵌入的学习办法与 word2vec 的 skip-gram 嵌入的学习办法相同,运用的是 skip-gram 模型。问题是,咱们怎么为 Node2Vec 生成输入语料库?数据要杂乱得多,即(非)定向、(非)加权、(a)循环……

  在处理NLP或核算机视觉问题时,咱们习气在深度神经网络中对图画或文本进行嵌入(embedding)。到现在为止,咱们所看到的图的一个局限性是没有向量特征。可是,咱们能够学习图的嵌入!图有不同几个等级的嵌入:

  对图的组件进行嵌入(节点,边,特征…)(Node2Vec) node2vec是一个用于图标明学习的算法结构。给定任何图,它能够学习节点的接连特征标明,然后能够用于各种下流机器学习使命。

  最近关于图结构化数据的标明学习的作业首要会集在学习图子结构(例如节点和子图)的散布式标明。可是,许多图剖析使命(例如图分类和聚类)需求将整个图标明为固定长度的特征向量。尽管上述办法天然不具备学习这种标明的才能,但图内核依然是取得它们的最有用办法。可是,这些图内核运用手艺制造的特征(例如,最短途径、graphlet 等),因而遭到泛化性差等问题的阻止。为了处理这个约束,在这项作业中,咱们提出了一个名为 graph2vec 的神经嵌入结构来学习恣意巨细图的数据驱动的散布式标明。图2vec s 嵌入是以无监督的办法学习的,而且与使命无关。因而,它们能够用于任何下流使命,例如图分类、聚类乃至耕种监督标明学习办法。咱们在几个基准和大型实践国际数据集上的试验标明,graph2vec 在分类和聚类精度方面比子结构标明学习办法有明显进步,而且能够与最先进的图内核竞赛。

  咱们首要重视的是图组件的嵌入。有几种办法能够对节点或边进行嵌入。例如,DeepWalk【】 运用短随机游走来学习图中边的标明。咱们将评论Node2Vec,这篇论文由2016年斯坦福大学的Aditya Grover和Jure Leskovec宣布。

  作者说:“node2vec是一个用于图标明学习的算法结构。给定任何图,它能够学习节点的接连特征标明,然后能够用于各种下流机器学习使命。“

  近年来,深度学习彻底改变了许多机器学习使命,从图画分类和视频处理到语音辨认和天然语言了解。这些使命中的数据通常在欧几里得空间中标明。可是,越来越多的运用程序将数据从非欧几里德域生成并标明为具有杂乱联系和方针之间彼此依靠联系的图。图数据的杂乱性对现有的机器学习算法提出了严峻应战。最近,呈现了许多关于扩展图数据深度学习办法的研讨。在本次查询中,咱们全面概述了数据发掘和机器学习范畴中的图神经网络 (GNN)。咱们提出了一种新的分类法,将最先进的图神经网络分为四类,即循环图神经网络、卷积图神经网络、图主动编码器和时空图神经网络。咱们进一步评论了图神经网络在各个范畴的运用,并总结了图神经网络的开源代码、基准数据集和模型评价。最终,咱们在这个快速开展的范畴提出了潜在的研讨方向

  神经网络最近的成功推进了办法辨认和数据发掘的研讨。许多机器学习使命,如方针检测 [1]、[2]、机器翻译 [3]、[4] 和语音辨认 [5],从前严峻依靠手艺特征工程来提取信息特搜集,最近现已由各种端到端深度学习典范彻底改变,例如卷积神经网络 (CNN) [6]、递归神经网络 (RNN) [7] 和主动编码器 [8]。深度学习在许多范畴的成功部分归功于快速开展的核算资源(例如 GPU)、大练习数据的可用性以及深度学习从欧几里得数据(例如图画、文本、和视频)。以图画数据为例,咱们能够将图画标明为欧几里得空间中的规矩网格。卷积神经网络 (CNN) 能够运用图画数据的移位不变性、部分连通性和组合性 [9]。因而,CNN 能够提取与整个数据集同享的部分有意义的特征,用于各种图画剖析。

  尽管深度学习有用地捕获了欧几里得数据的躲藏办法,但越来越多的运用程序将数据以图形的办法标明。例如,在电子商务中,根据图的学习体系能够运用用户和产品之间的交互来做出高度精确的引荐。在化学中,分子被建模为图形,而且需求确认它们的生物活性以进行药物发现。在引文网络中,论文经过引文彼此链接,而且需求将它们分类到不同的组中。图数据的杂乱性对现有的机器学习算法提出了严峻应战。由于图或许是不规矩的,图或许具有可变巨细的无序节点,而且来自图中的节点或许具有不同数量的街坊,导致一些重要的操作(例如卷积)在图画域中很简略核算,可是难以运用于图域。此外,现有机器学习算法的一个中心假定是实例彼此独立。这个假定不再适用于图数据,由于每个实例(节点)经过各种类型的链接(例如引证、友谊和交互)与其他实例相关联。

  最近,人们对扩展图形数据的深度学习办法越来越感兴趣。受来自深度学习的 CNN、RNN 和主动编码器的推进,在曩昔几年中,重要操作的新泛化和界说敏捷开展,以处理图数据的杂乱性。例如,能够从 2D 卷积推行图卷积。如图 1 所示,能够将图画视为图形的特殊情况,其间像素由相邻像素衔接。与 2D 卷积相似,能够经过取节点邻域信息的加权均匀值来履行图卷积。

  二维卷积相似于图,图画中的每个像素都被视为一个节点,其间街坊由过滤器巨细确认。 2D 卷积取赤色节点及其街坊像素值的加权均匀值。 节点的街坊是有序的而且具有固定的巨细。

  图卷积。 为了得到赤色节点的躲藏标明,图卷积运算的一个简略处理方案是取赤色节点及其街坊节点特征的均匀值。 与图画数据不同,节点的街坊是无序且巨细可变的。

  图神经网络 (GNN) Sperduti 等人的简史。 (1997) [13] 初次将神经网络运用于有向无环图,这激发了对 GNN 的前期研讨。图神经网络的概念开端是在 Gori 等人中概述的。 (2005) [14] 并在 Scarselli 等人中进一步论述。 (2009) [15] 和 Gallicchio 等人。 (2010) [16]。这些前期研讨归于循环图神经网络(RecGNNs)的范畴。他们经过以迭代办法传达街坊信息来学习方针节点的标明,直到到达一个安稳的固定点。这个进程在核算上是贵重的,而且最近现已越来越多地尽力战胜这些应战[17],[18]。 受 CNN 在核算机视觉范畴的成功的鼓动,很多从头界说图数据卷积概念的办法被并行开发。这些办法归于卷积图神经网络 (ConvGNN) 的范畴。 ConvGNN 分为两个干流,根据光谱的办法和根据空间的办法。 Bruna 等人提出了榜首个关于根据光谱的 ConvGNN 的出色研讨。

  (2013)[19],它开发了一种根据谱图理论的图卷积。从那时起,根据谱的 ConvGNN [20]、[21]、[22]、[23] 的改善、扩展和近似值不断添加。根据空间的 ConvGNN 的研讨比根据光谱的 ConvGNN 早得多。 2009 年,Micheli 等人。 [24] 首要经过架构复合非递归层处理了图彼此依靠问题,一起承继了 RecGNN 的音讯传递思维。可是,这项作业的重要性被忽视了。直到最近,呈现了许多根据空间的 ConvGNN(例如,[25]、[26]、[27])。代表性 RecGNNs 和 ConvGNNs 的时刻线如表 II 的榜首列所示。除了 RecGNNs 和 ConvGNNs,在曩昔几年中还开发了许多代替 GNN,包括图主动编码器 (GAE) 和时空图神经网络 (STGNN)。这些学习结构能够树立在 RecGNN、ConvGNN 或其他用于图建模的神经架构上。

  新分类 咱们提出了一种新的图神经网络分类。图神经网络分为四组:循环图神经网络、卷积图神经网络、图主动编码器和时空图神经网络。

  归纳回忆 咱们供给了最全面的图数据现代深度学习技能概览。关于每种类型的图神经网络,咱们都供给了代表性模型的具体描绘,进行了必要的比较,并总结了相应的算法。

  丰厚的资源咱们收集了丰厚的图神经网络资源,包括最先进的模型、基准数据集、开源代码和实践运用。本查询可用作了解、运用和开发适用于各种实践生活运用的不同深度学习办法的实践攻略。

  未来方向 咱们评论了图神经网络的理论方面,剖析了现有办法的局限性,并在模型深度、可扩展性权衡、异质性和动态性方面提出了四个或许的未来研讨方向。

  在本节中,咱们介绍了图神经网络 (GNN) 的分类,如表 II 所示。 咱们将图神经网络 (GNN) 分为循环图神经网络 (RecGNN)、卷积图神经网络 (ConvGNN)、图主动编码器 (GAE) 和时空图神经网络 (STGNN)。 图 2 给出了各种模型架构的示例。 下面,咱们对每个类别进行扼要介绍。

  循环图神经网络(RecGNNs)大多是图神经网络的前驱著作。 RecGNN 旨在学习具有循环神经架构的节点标明。 他们假定图中的一个节点不断地与其街坊交流信息/音讯,直到到达安稳的平衡。 RecGNN 在概念上很重要,并启发了后来对卷积图神经网络的研讨。 特别是,根据空间的卷积图神经网络承继了音讯传递的思维。

  卷积图神经网络 (ConvGNNs) 将卷积操作从网格数据推行到图数据。 首要思维是经过聚合它自己的特征 xv 和街坊的特征 xu 来生成节点 v 的标明,其间 u ∈ N(v)。 与 RecGNN 不同,ConvGNN 堆叠多个图卷积层以提取高档节点标明。 ConvGNN 在构建许多其他杂乱的 GNN 模型中发挥着中心作用。 图 2a 显现了用于节点分类的 ConvGNN。 图 2b 展现了用于图分类的 ConvGNN。

  是无监督学习结构,它将节点/图编码到潜在向量空间并从编码信息中重建图数据。 GAE 用于学习网络嵌入和图形生成散布。 关于网络嵌入,GAE 经过重构图结构信息(例如图邻接矩阵)来学习潜在节点标明。 关于图的生成,一些办法逐渐生成图的节点和边,而另一些办法一次悉数输出图。 图 2c 展现了一个用于网络嵌入的 GAE。

  旨在从时空图中学习躲藏办法,这在各种运用中变得越来越重要,例如交通速度猜测 [72]、驾驶员机动预期 [73] 和人类动作辨认 [ 75]。 STGNN 的要害思维是一起考虑空间依靠和时刻依靠。 许多当时的办法集成了图卷积来捕获空间依靠性,并运用 RNN 或 CNN 对时刻依靠性进行建模。 图 2d 说明晰用于时空图猜测的 STGNN。

  GNN 在不同的使命和范畴中有许多运用。 尽管每个类别的 GNN 都能够直接处理一般使命,包括节点分类、图分类、网络嵌入、图生成和时空图猜测,但其他与图相关的一般使命,如节点聚类 [134]、链接猜测 [135 ],图切割[136]也能够经过GNN来处理。 咱们具体介绍了根据以下研讨范畴的一些运用。

  核算机视觉 GNN 在核算机视觉中的运用包括场景图生成、点云分类和动作辨认。辨认方针之间的语义联系有助于了解视觉场景背面的意义。 场景图生成模型旨在将图画解析为由方针及其语义联系组成的语义图 [137]、[138]、[139]。另一个运用程序经过在给定场景图的情况下生成传神的图画来回转该进程 [140]。由于天然语言能够被解析为每个单词代表一个方针的语义图,因而它是一种很有出路的处理方案,能够在给定文本描绘的情况下组成图画。 分类和切割点云使 LiDAR 设备能够“看到”周围环境。点云是由 LiDAR 扫描记载的一组 3D 点。 [141]、[142]、[143] 将点云转换为 k-最近邻图或超点图,并运用 ConvGNN 探究拓扑结构。 辨认视频中包括的人类行为有助于从机器方面更好地了解视频内容。一些处理方案检测视频剪辑中人体关节的方位。由骨骼衔接起来的人体关节天然构成了一个图形。给定人类关节方位的时刻序列,[73]、[75] 运用 STGNN 来学习人类动作办法。 此外,GNN 在核算机视觉中的适用方向数量仍在添加。它包括人-物交互[144]、小样本图画分类[145]、[146]、[147]、语义切割[148]、[149]、视觉推理[150]和问答[151]。

  天然语言处理 GNN 在天然语言处理中的一个常见运用是文本分类。 GNN 运用文档或单词的彼此联系来揣度文档标签 [22]、[42]、[43]。 尽管天然语言数据表现出次序,但它们也或许包括内部图结构,例如句法依靠树。句法依靠树界说了语句中单词之间的句法联系。 Marcheggiani 等人。 [152] 提出了在 CNN/RNN 语句编码器之上运转的句法 GCN。 Syntactic GCN 根据语句的句法依靠树聚合躲藏的单词标明。巴斯廷斯等人。 [153] 将句法 GCN 运用于神经机器翻译使命。 Marcheggiani 等人。[154] 进一步选用与 Bastings 等人相同的模型。 [153]处理语句的语义依靠图。 图到序列学习学习在给定笼统词的语义图(称为笼统意义标明)的情况下生成具有相同意义的语句。宋等人。 [155] 提出了一种图 LSTM 来编码图级语义信息。贝克等人。 [156] 将 GGNN [17] 运用于图到序列学习和神经机器翻译。逆向使命是序列到图的学习。给定语句生成语义或常识图在常识发现中非常有用

  精确猜测交通网络中的交通速度、交通量或路途密度关于智能交通体系至关重要。 [48]、[72]、[74] 运用 STGNN 处理交通猜测问题。 他们将交通网络视为一个时空图,其间节点是安装在路途上的传感器,边际由节点对之间的距离丈量,每个节点将窗口内的均匀交通速度作为动态输入特征。 另一个工业级运用是出租车需求猜测。 鉴于前史出租车需求、方位信息、气候数据和事情特征,Yao 等人。 [159] 结合 LSTM、CNN 和由 LINE [160] 练习的网络嵌入,构成每个方位的联合标明,以猜测时刻距离内某个方位所需的出租车数量。

  根据图的引荐体系将项目和用户作为节点。 经过运用项目与项目、用户与用户、用户与项目之间的联系以及内容信息,根据图的引荐体系能够发生高质量的引荐。 引荐体系的要害是对项目对用户的重要性进行评分。 成果,它能够被转换为链接猜测问题。 为了猜测用户和项目之间缺失的链接,Van 等人。 [161] 和英等人。 [162] 提出了一种运用 ConvGNN 作为编码器的 GAE。 蒙蒂等人。 [163] 将 RNN 与图卷积相结合,以学习生成已知评级的底层进程

  在化学范畴,研讨人员运用 GNN 来研讨分子/化合物的图形结构。 在分子/化合物图中,原子被视为节点,化学键被视为边际。 节点分类、图分类和图生成是针对分子/化合物图的三个首要使命,以学习分子指纹 [85]、[86]、猜测分子特性 [27]、揣度蛋白质界面 [164] 和 组成化合物

  GNN 的运用不只限于上述范畴和使命。 现已探究将 GNN 运用于各种问题,例如程序验证 [17]、程序推理 [166]、社会影响猜测 [167]、对抗性进犯防备 [168]、电子健康记载建模 [169]、[170] ]、大脑网络[171]、事情检测[172]和组合优化[173]。

  尽管 GNN 现已证明晰它们在学习图数据方面的才能,但由于图的杂乱性,应战依然存在。

  深度学习的成功在于深度神经架构 [174]。 可是,李等人。 标明跟着图卷积层数的添加,ConvGNN 的功能急剧下降 [53]。 跟着图卷积将相邻节点的标明推得更近,理论上,在无限数量的图卷积层中,一切节点的标明将收敛到一个点 [53]。 这就提出了一个问题,即深入研讨是否依然是学习图数据的好战略。

  GNN 的可扩展性是以损坏图完整性为价值的。 无论是运用采样仍是聚类,模型都会丢掉部分图信息。 经过采样,节点或许会错失其有影响力的街坊。 经过聚类,图或许被掠夺了共同的结构办法。 怎么权衡算法的可扩展性和图的完整性或许是未来的研讨方向。

  当时的大多数 GNN 都假定图是同质的。 现在的 GNN 很难直接运用于异构图,异构图或许包括不同类型的节点和边,或许不同办法的节点和边输入,例如图画和文本。 因而,应该开发新的办法来处理异构图。

  图本质上是动态的,节点或边或许呈现或消失,节点/边输入或许会随时刻改变。 需求新的图卷积来习惯图的动态性。 尽管图的动态功能够经过 STGNN 部分处理,但很少有人考虑在动态空间联系的情况下怎么履行图卷积。

  由于之前一直在研讨常识提取相关算法,后续为了构建小型范畴常识图谱,会用到常识交融、常识推理等技能,现在开端学习研讨图核算相关。

  现在现已覆盖了图的介绍,图的首要类型,不同的图算法,在Python中运用Networkx来完成它们,以及用于节点符号,链接猜测和图嵌入的图学习技能,最终讲了GNN运用。

  项目链接:欢迎fork欢迎三连!文章篇幅有限,部分程序出图纷歧一展现,概况进入项目链接即可