Graph Matching Networks for Learning the Similarity of Graph Structured Objects

摘要

图嵌入及有效的相似推理

• GNN已经成为定义在结构化数据上的各种有监督预测问题的有效模型，我们演示了如何训练图神经网络（GNN），使其能够在向量空间中生成图的嵌入，从而实现有效的相似推理

新的图匹配网络模型

• 以一对图为输入，通过一种新的基于cross-graph attention的匹配机制，通过对图进行联合推理，计算出它们之间的相似度

实验证明

• 基于控制流图的功能相似性搜索的挑战性问题

introduction

图神经网络介绍

解决相似性问题

• 用于解决二进制函数的漏洞检查
• 二进制函数的流程图对比

提出GNN

• 将图嵌入到向量空间

  • 学习嵌入模型

    • 相似的图在向量空间中更接近

  • 每个图独立地映射到一个嵌入向量，然后所有的相似度计算都在向量空间中进行

  • 所以

    • 图在大型数据库中的嵌入可以被预先计算和索引，这使得我们能够使用快速近邻搜索进行高效检索

GNN的扩展

• 图匹配网络（GMNs）

  • 用于相似性学习
  • 通过cross-graph attention机制计算相似度得分，以便跨图关联节点并识别差异
  • 通过使图的表示计算更加依赖于“成对的图”，该匹配模型比嵌入模型更加强大，提供了一个很好的精度计算权衡。

实验证明

• 捕获结构相似性的合成图edit-distance学习任务
• 对结构相似性和语义相似性进行推理的现实任务

related work

GNN和图表示学习

图相似度和图Kernels

• Graph kernels

  • 用于衡量图的相似性，但是需要设计比较好的kernels

距离度量学习

• 关于度量学习的早期工作大多假设数据已经存在于向量空间中，并且只有线性度量矩阵才能正确地测量该空间中的距离，以便将相似的示例分组在一起，而将不同的示例相距很远

Siamese网络

• 子主题 1

graph hashes

• 人为设计的hash函数；擅长精确匹配，但是不擅长估计相似性

Methods

graph embedding model

• 独立embeddings

  • encoder

    • 将点和边，map到隐含空间

      • 使用MLP

  • GNN

    • 通过整个图，流动信息
    • 计算node representation：编码局部邻接矩阵信息等
    • 点可以整合所有信息

  • 得到graph representations

    • hG
    • 更进一步的MLPG( MLP())

• 计算距离，distance

  • 欧式距离或者汉明距离

graph matching networks (GMNs)

• 主要思路

  • 计算相似性分数，为a pair of graphs jointly on the pair
  • 计算每个图的representation （jonitly on the pair)

• message passing步骤与embedding model不同

  • 不仅从graph内获取信息，还从图间获取信息（出现other graph的all node）

• 计算图内的信息，类似embedding model

• 计算一个图中的each node和另一个图的所有节点的attend

  • 计算图间的attention

• 计算图间的信息

  • 结合注意力权重的所有node representation的和，然后取不同

• 算法实现

  • a few similar function
  • cross-graph attention
  • Graph matching layer and graph matching networks

Training

• labeled data examples
• training on pairs
• training on triplets

Dataset

Task

• The graph edit distance task

参考链接

Graph Matching Networks for Learning the Similarity of Graph Structured Objects
https://arxiv.org/abs/1904.12787