Graph Matching Networks for Learning the Similarity of Graph Structured Objects

所需积分/C币:42 2019-05-07 21:11:00 1.15MB PDF
89
收藏 收藏
举报

近日,DeepMind 和谷歌联合进行了一项研究,该研究提出了一种执行相似性学习的新型强大模型——图匹配网络(GMN),性能优于 GNN 和 GCN 模型。该论文已被 ICML 2019 接收。 DeepMind 和谷歌的这项新研究聚焦检索和匹配图结构对象这一极具挑战性的问题,做出了两个重要贡献。 首先,研究者展示了如何训练图神经网络(GNN),使之生成可在向量空间中执行高效相似性推理的图嵌入。其次,研究者提出了新型图匹配网络模型(GMN),该模型以一对图作为输入,通过基于跨图注意力的新型匹配机制进行联合推理,从而计算它们之间的相似性分数。 研究者证明 GMN 模型在不同领域中的有效性,包括极具挑战性的基于控制流图的函数相似性搜索问题,这个问题在检索软件系统的漏洞中起着非常重要的作用。实验分析表明 GMN 模型不止能在相似性学习的环境下利用结构,还能超越针对这些问题手动精心设计的特定领域基线系统。研究主题:图相似性学习问题 图是编码关系结构的自然表征,常常出现在多个领域中。根据图结构数据定义的计算可以用在各种领域中,从计算生物学和化学的分子分析到自然语言理解中知识图或图结构解析的分析都可以。 近几年来,图神经网络(Graph Neural Network,GNN)已经成为可以有效学习结构数据表征、解决各种基于图的监督预测问题的模型了。这样的模型在迭代聚合局部结构信息的传播过程中设计并计算图节点表征,从而对图元素的排列(permutation)具有不变性。然后直接将这些节点表征用于节点分类,或者将它们合并到用于图分类的图向量中。而 GNN 在监督分类或回归以外的问题的相关研究相对较少。 DeepMind 的这篇论文研究的是图结构对象的相似性学习问题,这个问题在现实生活中有很多重要的应用,尤其是在图数据库中基于相似性的搜索。还有一个应用是涉及计算机安全的二元函数相似性搜索,给定的二元函数可能包含有已知漏洞的代码,我们要检查这个二元函数中是否有和已知易受攻击的函数相似的控制流图(control-flow-graph)。这有助于识别闭源软件中易受攻击的静态连结函式库,这是一个很常见的问题 (CVE, 2010; 2018),现在还没有很好的解决方法。图 1 展示了一个例子,在这个例子中用汇编语言注释的控制流图来表示二元函数。这种相似性学习问题极具挑战性,因为就算是图之间细微的差别也会造成语义上极大的不同,但结构不同的图语义上可能非常相似。因此,对这个问题而言,一个成功的模型应该(1)利用图结构;(2)能从图的结构和学习到的语义中推导出图的相似性。图 1:二元函数相似性学习问题。检查两个图是否相似需要推理图的结构和语义。左边两个控制流图对应使用不同编译器编译的相同函数(因此二者比较相似),但右侧图对应的是不同函数。 解决方案 为了解决图相似性学习问题,该论文研究了 GNN 在这种情况中的使用,探讨了如何用 GNN 将图嵌入到向量空间,并学习这种嵌入模型,从而使向量空间中相似的图靠近、不相似的图分开。这个模型的一个重要特性是它可以将每一个图独立地映射到一个嵌入向量,然后在向量空间中执行相似性计算。因此,可以预先计算并索引大型数据库中的图嵌入,这样就能用快速的最近邻搜索数据结构(如 k-d 树) 或局部敏感哈希算法 (Gionis et al., 1999) 执行高效的检索。 研究者进一步扩展 GNN,提出新型图匹配网络(Graph Matching Networks,GMN)来执行相似性学习。GMN 没有单独计算每个图的图表征,它通过跨图注意力机制计算相似性分数,来关联图之间的节点并识别差异。该模型依赖成对图计算图表征,因此它比嵌入模型更强大,并在准确率和计算之间做出了很好的权衡。 研究者在三个任务上评估了 GMN 和基线模型:仅捕获结构相似性的合成图编辑距离学习任务(synthetic graph edit-distance learning tas),以及两个现实世界任务——二元函数相似性搜索和网格检索,这两项任务都需要推理结构相似性和语义相似性。在所有任务中,GMN 都比基线和结构不可知(structure agnostic)模型的性能更好。在更详细的模型简化测试中,研究者发现 GMN 始终优于图嵌入模型和 Siamese 网络。 该研究的贡献如下: 展示了如何用 GNN 产生用于相似性学习的图嵌入; 提出了新型图匹配网络(GMN),该网络基于跨图注意力匹配来计算相似性; 实验证明,该研究提出的图相似性学习模型 GMN 在多个应用中都有良好的表现,比结构不可知模型和现有的手动建立的基线模型都要好。 深度图相似性学习 给定两个图 G1 = (V1, E1) 和 G2 = (V2, E2),我们需要一个可以计算

...展开详情
试读 18P Graph Matching Networks for Learning the Similarity of Graph Structured Objects
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享宗师

关注 私信
上传资源赚钱or赚积分
最新推荐
Graph Matching Networks for Learning the Similarity of Graph Structured Objects 42积分/C币 立即下载
1/18
Graph Matching Networks for Learning the Similarity of Graph Structured Objects第1页
Graph Matching Networks for Learning the Similarity of Graph Structured Objects第2页
Graph Matching Networks for Learning the Similarity of Graph Structured Objects第3页
Graph Matching Networks for Learning the Similarity of Graph Structured Objects第4页

试读结束, 可继续读2页

42积分/C币 立即下载 >