论文阅读笔记：Graph Matching Networks for Learning the Similarity of Graph Structured Objects

论文做的是用于图匹配的神经网络研究，作者做出了两点贡献:

1. 证明GNN可以经过训练，产生嵌入graph-leve的向量可以用于相似性计算。
2. 作者提出了一种新的基于注意力的跨图匹配机制GMN(cross-graph attention-based matching mechanism)，来计算出一对图之间的相似度评分。（核心创新点）

论文证明了该模型在不同领域的有效性，包括具有挑战性的基于控制流图(control-flow-graph)的函数相似性搜索问题、软件系统漏洞检测。实验分析表明，图匹配模型不仅能够在上下文相似性学习的背景下挖掘结构信息，并且性能优于hand-engineered的baseline。

主要内容

提出两种图的相似性计算方法：一个是基于GNN传统的图嵌入(Graph Embedding Models)方法，另一个是GMN(Graph Matching Networks)。

1.Graph Embedding Models

主要思路是用传统GNN把全图表征成一个向量，然后利用图的向量来计算图与图之间的相似性。模型由：编码层、传播层、聚合层构成。

编码层： 通过多层感知器将节点和边的特征进行编码

传播层： 在迭代过程中传播节点之间的特征信息

聚合层： 从所有节点中聚合特征，嵌入到一个新的向量空间来表征全图

2.Graph Matching Networks（GMN）

提出了一种新的基于注意力的跨图匹配机制，可以看到GMN方法在节点特征传播过程中就已经用到了两图之间的交叉信息，这样有助于找到图对之间顶点的关系，并且能够在从局部到整体都能进行图对之间的相似度信息的传播。相比图嵌入模型，GMN的信息流动更加高效，更加有利于图相似度特征信息的提取。

GMN也是分三个部分：编码层、传播层、聚合层。其中编码层和图嵌入模型的编码层一样:

GMN的传播层就是增加了注意力机制后的传播层， f m a t c h f_{match} fmatch​做的就是跨图信息的计算，attention公式如下：

聚合层：

损失函数：

损失函数有二元组和三元组(都被设置在[0,1]范围内)，二元组构建了相同和不同的图对，相同图对的label=1，不同的label=-1，三元组的存了3个graph，在loss设计上将模型引导为拉近G1,G2的距离，拉远G1G3之间的距离。 在作者的实验中，使用二元组或三元组的精度都差不多。

用汉明距离作为距离度量，目标最小化positive pairs，最大化negative pairs.

实验

作者在两个任务上将提出的GMNs与其他方法对比，均证明了GMNs的性能。

任务一：图编辑距离学习

通过程序自动生成图，并生成出正负样本。生成1000组验证集，评价指标有AUC和三元组的acc

任务二：基于控制流图的二元函数相似搜索
作者采用不同的编译器GCC和clang以及不同的编译器优化级别，对目前流行的开源视频处理软件ffmpeg生成的数据进行训练和评价，得到7940个函数，每个函数有8个CFG。训练模型在CFG上学习相似性度量，使得同一功能的CFG具有较高的相似性，否则相似性较低。经过训练后，这种相似性度量可以用于二进制库的搜索，并且在编译器类型和优化级别上保持不变。性能如下图：