从图嵌入到图分类——图网络入门综述

即时新闻 2020-05-22193未知admin

  作者在伦敦Connected Data上的之后,与很多拥有图数据,想要开始机器学习但不知道怎样开始的研究团队进行了交流。在这篇文章里,作者以通俗易懂的方式展示了他们在图上进行机器学习的方法技巧,并提供了相关的资料。

  注:作者 David Mack 是 Octavian.ai 的创始人。Octavian.ai 是一家开源,致力于机器问答系统和图上深度学习。这是他们的开源项目列表:

  一、 什么是图数据?通过与这些希望获得机器学习领域协助的团队交流我们得知,图数据真是无处不在 —— 从疾病诊断,遗传学研究还有健康管理,到银行和工程,图都是一种解决困难问题的强有力的模式。

  简单来说,一张图就是节点(比如人)和他们之间关系(比如 Fati 是 Jacob 的朋友)的。这些节点通常具有自己的属性(比如 Fati 23岁)。

  图1 数据库中以图形式的储存数据。如图所示,这个例子在数据库里通常是这样存储的。一个最主流的图数据库是Neo4j,用他们自己的话说“ 这是一个处于世界领先地位的图数据库,因为它具有本地的图存储和图处理能力。

  如图所示,这个例子在数据库里通常是这样存储的。一个最出名的图数据库是Neo4j,用他们自己的话说“ 这是一个处于世界领先地位的图数据库,因为它具有本地的图存储和图处理能力。

  你可以在 Neo4j 数据库中使用 Cypher 查询数据,这是一种类似于SQL的图查询语言。在之前的演示示例中,我们可以这样获取一个 Fati 朋友的列表:

  MATCH (n1)-[:IS_FRIEND_OF]-(n2)RETURN n2.name图是描述数据的一种极具灵活性的强大方式。传统的关系型数据库很难用固定模式存储不同实体之间的联系,然而这些联系是现实世界中普遍且至关重要的一部分。在图数据库中,这些联系常易于存储和查询的。此外,通常很多事物之间的联系(例如家庭之间的关系)构成问题的关键,使用图数据库使得问题变得很简单。

  备注:关系(relationship)和边(edge)在这篇文章里是可以相互替换的。Neo4j 语境下使用前者,图论语境下用后者。

  二、 为什么要在图数据上使用机器学习?(Graph ML)首先,为什么使用机器学习? 关于这个问题,Benedict Evans 写了一篇很好的文章 “Ways to think about chine Learning” ,覆盖了企业思考和开始机器学习的方式。

  这里总结来自 Ben 对于图机器学习(Graph ML) 两种有用的观点:

  真实世界的数据是充满干扰且多层次的。比如像”描述图中的人物“此类任务对于人类来说很简单,但是很难抽象为离散的算法。

  这在图上也是成立的——得益于式的关系结构,它们与图像或向量有非常大的不同。我们可以在 Graph ML 上建立适用于通用模式的方法。

  ML 可以以人类无法企及的规模来转换信息。另一方面,对于计算机来说,它们可以准确执行我们的指令(虽然偶尔也会出现错误)。这意味着它们可以完全地运行指令,并且没有任何额外操作。需要它们运行多久,它们就会持续多久。因此,计算机可以处理非常大规模的数据(换类需要很多时间或注意力)。这让新的应用成为可能,例如从数十亿的web数据里找出欺诈的特征。

  三、 什么是 Graph ML?这可以简单地定义为 ”在图数据上应用机器学习(applying chine learning to graph data)“。我们特地这样通俗地解释,是因为在这篇文章里,我们将聚焦于神经网络和深度学习本身,即便如此,我也会尽可能地包含补充的链接。

  我不想去写传统的图,包括一些广为人知的算法,如 PageRank,Clique Indentification, Shortest Path 等。这些强大且能够作为第一选择的算法已经在公开的资料中有了大量的参考。

  使用 Graph ML 会遇到什么样的挑战?然而在这个令人激动又充满希望的领域里,Graph ML 还是一项非常年轻的技术。

  主流机器学习的讨论更多的是在可应用性(例如使用ResNet进行迁移学习来分类图像,或者在文本中使用BERT预测),还有对者的易用性上(例如 TensorFlow, PyTorch, FastAI)。这并不是简单而通用的技术,即便如此也没有任何流行的ML库支持图数据。

  同样的,像 Neo4j 这样的图数据库自己也没有支持在数据上运行ML的方法。(尽管 Neo4j 已经在尝试使它成为可能)

  在深度学习库中不支持图的其中一个原因是图具有过于灵活的的数据结构(例如任何节点与节点有任意多的连接)并不契合主流深度学习库和 GPU 架构中使用的固定大小图和固定尺寸张量。

  更简单来说,用矩阵来描述并操作一个稀疏图常困难的。不是不可能,但比使用向量,文本还有图像要难得多。

  尽管如此,Graph ML 的趋势依然无法。我个人预测,这将成为我们在很多产业中数据的一个主流的基本方式。

  再提及一点,就像任何机器学习技术,大多数 Graph ML 都需要大量的训练数据。

  Graph ML系统在实际运行中是怎样的?虽然这个问题的答案会随着任务和数据集的变化而变化,但它有助于概括出你,这个敏锐的冒险家,将会遇到的问题。

  绝大多数时候,这系统需要你自己来写代码完成 —— 因为高级的 Graph ML 工具还不存在。你可能会想要用 Python, 还有机器学习库 像TensorFlow 或者 PyTorch 来实现。根据你的数据规模,你可以在单机上实现训练模型,也可以使用分布式系统。(有趣的是,很多图训练过程可以很好地在分布式系统上工作)。

  你很可能需要先从存储在 CSV 文件和在 Neo4j 这样的数据库,或者格式的图数据库中提取你的数据。

  然后你需要把数据提供给机器学习库。在我当前的工作中(涉及到百万的小图(all graphs)),我把每一张图都预先编译成了 TFRecord,特征向量存储了节点,联系,还有相邻矩阵信息。所有节点的属性与文本被标记成了一个字典的格式。

  这只在小图上起作用,如果图很大,你需要用某种方案把图分为较小的训练样本(你可以分批训练,或者按照 节点-边-节点 三个一组的形式训练)。

  :一些情况下数据在导入机器学习库之前进行表格化(tabularize )。Node2Vec 就是一个很好的例子,它的每一个节点都被随机游走(Random Walk)转换成向量,然后这些向量再以列表的形式传入机器学习模型。

  一旦在数据传入之后,真正的模型和训练工作就开始了。这是一个复杂的变化过程。

  最终,模型会被用在某些地方。一些情况下,一个模型计算完成后的新节点/边/图信息会存储在外部数据库里。

  另外一部分的模型会被部署在线上的产品中。在这种情形下,从图数据建立的模型系统需要更好的性能(可以是从图数据库中导入数据),然后这个预测模型最终会被用户或下一代系统所利用(例如 Alexa 和用户的问答系统)。

  四、 让我们在图上开始机器学习吧!让我们先看一下一些可以用来在图上执行机器学习的吧。

  我将在这里大概列举一系列方法,指出它们其中的一些缺点和优点,然后给出完整的链接。因为篇幅这里省略了一些细节。尽管这是一个年轻的领域,研究人员还是想出了一系列令人眼花缭乱丰富的方法处理Graph ML。即便我想在本文中详尽介绍,遗憾的是也没有办法完全列出主要的部分。

  你想要执行什么类型的任务?对于 Graph ML有各种各样的开始和执行过程的方式。因此,通过考虑你的任务目的来缩小开始的范围和方式是很有帮助的。

  如同任何机器学习系样,缩小和明确你要实现的目标,将对你的试验成功和试验过程有极大的帮助。通过提出一个最小的、明确的目标,你的模型和需要数据集就会减小到易于处理的程度。

  最后一点,图数据库是特别有吸引力的,它鼓励我们朝着宏伟的“万能”目标前进:因为图数据库几乎可以代表任何东西,所以这对试图建立通用的智能的工作者很有力的。:)

  我们将要阐述的任务类型:预测两个节点之间的关系是否存在预测和分类节点,边,还有整张图

  本文旨在作为你自己研究的初级参考。与任何数据科学一样,使用方法也需要适应你个人所处的。由于许多Graph ML尚处于早期研究阶段,因此你应该在找到一个有效的方法之前尝试多种方法。

  基本过程在开始构建一个 Graph ML 系统(可能需要对基础设施进行大量投资)之前,重要的是要考虑简单的方法是否已经足够达成目,这能为你节约下很多不必要的工作。这里有一些简化问题的方法:

  你可以把你的数据列表化(tabularize)么(你能看到节点列表么?你可以在 节点-边-节点 的三元组模式下工作么?)然后在此之上应用传统的机器学习过程(例如线性回归,前馈网络)?你能把数据集过滤成更小的部分么?(例如移除现有的节点)你可以把这个图聚类成子图,并把它们合成一个表么?你是否可以使用传统机器学习扩展的的图度量指标(如 PageRank)?(例如对计算节点的属性应用线性回归来对节点进行分类)在下面可以适用的部分中,我会回顾其中的一些方法。

  通用 Graph ML 方法一些 Graph ML 的方法通用性强。我已经在这里包含了它们全部的介绍。在下面的章节中,我将参考此部分并着重解释一些应用在特定任务的过程。再一次重申,我们不可能在一篇文章中涉及所有Graph MLD的内容,我们能做的较好的就是给你,以便你继续深入。

  你可以跳过这个章节,并在开始解决你感兴趣的任务的时候回头再看。节点层

  五、 节点嵌入 Node embeddings节点嵌入是 graph ML 早期的一种方式,它的流行是因为简单,稳定,且易于计算。

  简单来说,节点嵌入就是轮流计算图中的每一个节点的向量。向量可以计算出有用的属性,例如任意两个节点嵌入的内积可以表示它们是否来自于同一个社群。

  权衡之下必然会放弃一些信息。一个固定长度的向量很少能代表一个节点周围的所有图结构。它可以包含也可以不包含节点和关系属性。

  然而,只有少量具有创新性的节点层可以被 Graph ML 过程复用。在这样的设置下,节点层成为一种节点属性,并被用作技术的催化剂,即使它并没有像生成层一样嵌入到图结构中。

  一次随机游走从图中的一个节点开始,随机地选择一个边,并穿过它。然后重复这一过程,直到提供径足够地长。

  随机游走的聪明之处在于它将一个度的不规则事物(图)为一个简单的矩阵(每个径由节点组成的固定长度的径列表)。

  在足够大的规模下,从理论上可以从随机游走中重建出基本的图结构。随机游走发挥了机器学习的巨大优势:从大量数据中学习。

  有很多方法可以利用随机游走来计算节点嵌入。下面我将重点介绍一些主要的方法。

  将这些随机游走为计算嵌入的方法有一种智能的优化方式。首先为每个节点分配一个随机层,(例如长度为N的高斯向量)。然后对于每对源相邻节点,我们希望通过调整这些层来较大化它们的点积。同时最后,我们最小化随机节点对的点积。这样做的效果是我们学习了一组嵌入,这些嵌入倾向于在相同的遍历过程中高点积的节点。例如在相同的 社群/结构中。

  图4 由node2vec生成的LesMisérables可视化外观网络,其标签颜色表示了同质性(顶部)和结构等价性(底部)。

  你要知道关于node2vec 的最后一点是,它是由参数决定随机游走的形式的。通过 ”In-out“ 超参数,你可以优先考虑遍历是否集中在小的局部区域(例如这些节点是否在同一个小边中?)或者这些游走是否在图中广范(例如这些节点是否处于类型的结构中?)。

  node2vec 扩展node2vec 的优势在于它的简单,但这也是它较大的弱点。标准算法并不包含节点属性或边属性以及需要的信息。

  但是,扩展 node2vec 使它包含更多的信息非常简单,只需更改损失函数,比如:尝试不同的学习函数替代两个节点层之间的点积不仅使用节点层,也需要包含它们的属性

  使用随机游走的协同过滤(Collaborative filtering)一个使用随机游走来解决协同过滤的简单例子是输入用户对产品的评论,预测用户会喜欢哪些产品。这大体上遵循了与 node2vec 相同的方案,尽管已经进一步简化。你可以在本文中找到完整的实现和解释。

  六、 图卷积网络图网络是 Graph ML 的一个丰富而重要的领域,其基本前提是在图结构中嵌入神经网络:

  通常,这涉及存储每个节点的状态,并使用邻接矩阵将这些状态到节点的近邻节点。

  在的文章中,图网络被认为是用于在节点,边和整个图上状态和聚合状态的函数。这样,来自于许多不同理论的架构都是可比较的。下面是从函数中提取的步骤:

  七、 对图网络的扩展在我们的MacGraph研究项目中,我们一直在尝试对图网络进行一些扩展。虽然我们仍在改进这些方法,但它们已经展现出很大的希望,值得研究。

  我们正在尝试学习不同的推理算法,从图中提取和转换数据。为此,我们在上述网络中添加了一系列组件,使其类似于基于图的图灵机器:

  每个节点上的 GRU 单元使得每个节点在多次迭代中更好地保持状态。节点从基于注意力机制的全局控制单元读写数据。一个控制单元(本质上是一个 LSTM 单元),它把当前任务作为输入,并向网络的其余部分输出一系列控制,指导它们的下一步行动——这是基于Macnet体系结构。节点和边列表从注意力导向的控制单元读取。供上述组件读写的工作状态存储器。

  八、 链接预测预测两个节点之间是否存在关系这是一项通常且非常简单的任务,基本表示为:

  例如知识图补全(例如,如果米开朗基罗是托斯卡纳出生的画家,他是意大利人吗?),预测蛋白质相互作用。这两种方法都可以用来预测新的未知事物(例如哪些药物可能有效?)以及改进现有不完善的数据(例如,此任务属于哪个项目?).

  关于许多方法的更多信息,可以在前面的“通用 Graph ML 方法”一节中找到。

  嵌入层通常是这样生成的:图中邻近的节点具有相似的嵌入的张量。然后就能比较距离(例如点积或欧几里得距离)来预测存在连接的可能性。有些方法,比如 node2vec,实际上是直接训练嵌入层的存/无(presence/absence)链接样本。

  图网络可用于生成链接预测的嵌入节点。在这种情况下,需要将链接预测能力纳入到网络的损失函数中。

  具有图特征的深度学习这意味着对图数据进行序列化,然后在其上运行传统的前馈网络。

  例如,每个节点可以由其属性表示(形成张量)。每个训练示例都有两个节点和关系类型作为特征,存在的边则作为标签。记住要平衡已标注的类数量。

  当许多图结构反映在属性中时(例如,街道图和每个节点都有其 GPS ),这种简单的方法可以很好地工作。

  斯坦福大学的这种有趣的方法基本上将图形记忆成张量和矩阵。“我们的模型优于以前的模型,可以对 WordNet 和Freebase 中未公开的关系进行分类,准确率分别为86.2%和90.0%。

  强化学习强化学习也可用于链接预测。在这种方法中,网络学习从图中提取一系列事实,并结合这些事实生成链接预测。这种方法的一个例子是“Multi-hop knowledge graph reasoning with reward shaping”,在这种推理中,网络学习遍历图并使用该信息生成链接预测。

  九、 节点,边和整个图的评分和分类另一个常见的任务是尝试对图的一部分进行分类或评分。例如,试图找出与某个基因相关的蛋白质。或者尝试根据他们的交友小组把学生到他们的学校。分类意味着输出潜在标签之间的概率分布,评分意味着输出一个可用于与标签进行比较的权重。两者在概念上相似,分类涉及更度。

  通常的任务是定义以下函数之一,其中 Output 是一组可能的类别分布或一组可能的输出分数:

  对图执行一些计算,也许是将其节点和边的多个元素组合成存储在节点、边 和/或 整个图中的状态中。提取、聚合并将状态转换为所需的输出。

  步骤1可以使用许多不同的方法来执行,我将在下面列出。步骤2通常使用前馈神经网络(FFN)来执行。提取和聚合可以使用手工建立的函数(例如,读取特定节点、将特定边求和)或学习的函数(例如,注意力机制提取、聚合卷积)。

  这两个步骤的选择都是数据科学和实验的问题,还没有出现任何明确的“一刀切”的解决方案。

  关于其中许多方法的更多信息,可以在前面的“通用 Graph ML 方法”一节中找到。

  当使用嵌入时,通常这些检测的节点通过一个小的 FFN 网络来得到期望的输出。根据用例的不同,节点的属性也可以包含在FFN的输入中。

  如果节点嵌入是使用随机游走创建的(例如,使用node2vec),则它们将包含可能与正在执行的分类或评分相关的原始结构信息(例如,节点所在的边或其所属的上一层结构)(例如,聚类处于不同图的子边)。

  图网络图网络是一种将神经网络嵌入到图中的通用方法。图网络可以计算节点、边和图的状态(根据应用的场景可以省略其中的一些状态)。然后可以转换这些状态以产生最终输出。例如,图状态可以通过一个 FFN 来创建一个完整的图分类。

  注意力序列一个有趣的方法是在论文“使用结构化注意力进行图分类”中得来的。在这项工作中,我们使用注意力从图中反复读取节点.

  网络的中心是一个 LSTM 单元,它控制从哪个节点读取数据,将注意力读取到的数据合并到其内部的状态,然后输出对图分类的预测。

  这类似于“用于机器推理的综合注意力网络”中的方法(尽管不在图数据上),其中一个中心 RNN 单元引导注意力读取和读取数据的合成。*论文链接

  基于分块或节点属性的传统深度学习将问题简化为一个对照数据集,可以找到许多更好的研究方法(例如前馈和卷积神经网络)。

  一种方法是将每个节点及其属性视为一个训练样本。这可能涉及手工创建你认为将有助于 分类/评分 的附加属性。

  创建图的另一种方法是提取固定大小的分块。在这个模型中,一个节点、它的边以及它的近邻节点被提取到一个固定大小的表中。固定大小意味着边和节点有较大数量的存储,如果表中存在多出边和节点,则必须随机抽样。此外,如果节点和边少于固定表可以存储的数量,则需要用指定的空值填充。最后,必须选择如何选择分块-一个简单的模型是从每个节点或边提取一个分块。

  节点属性在搜索引擎上的技术最后,也有一些非机器学习方法值得思考。如果在某种链接、内容或文本的基础上对节点进行评分,可能会对搜索引擎/文档检索效果提升有效。

  这是一个非常成熟的计算机科学领域。更多提示,请查阅的信息检索文章。

  附录在本文中,我引用了很多资源,为了方便起见,都在此列出。此外,我还添加了前面未列出的有趣项目。

原文标题:从图嵌入到图分类——图网络入门综述 网址:http://www.bestpluginsforwp.com/jishixinwen/2020/0522/45541.html

Copyright © 2002-2020 无边无际新闻网 www.bestpluginsforwp.com 版权所有  

联系QQ:1352848661