【论文笔记】Graph Matching Networks for Learning the Similarity of Graph Structured Objects

中文标题：用于学习图结构化对象相似度的图匹配网络

发表会议：PRML 2019

文章链接：Graph Matching Networks for Learning the Similarity of Graph Structured Objects

源代码：无

1 Introduction

1.1问题陈述 ：

计算机安全问题中的二进制函数相似性搜索：给定一个二进制文件，该文件有可能包含具有已知漏洞的代码，用带有汇编指令注释的控制流图表示二进制函数，然后检查该二进制文件中的控制流图和数据库中的已知漏洞函数是否足够相似。这个相似性学习问题非常具有挑战性，因为细微的差异会使两个图在语义上非常不同，而具有不同结构的图仍然可以是相似的。

因此想要实现图相似度的比较：

1.利用图结构；

2.能够从图结构以及从所学的语义推断图的相似性。

1.2 解决办法：

本文提出了两种方法：

GNN：为了解决图的相似性学习问题，作者研究了GNNs在这种情况下的使用，探索它们如何被用来将图嵌入到向量空间中，并学习这种嵌入模型来使相似的图在向量空间中接近，而不相似的图远离。该模型的一个重要特性是，它将每个图独立地映射到一个嵌入向量，然后所有的相似度计算都在向量空间中进行。这种方法的好处是如果需要对数据库中大量的图进行比较的时候，只需要对数据库中图的这些embedding进行比较，可以利用已有的一些算法快速得到匹配，比如k-d trees、locality sensitive hashing。

GMN：提出了对GNN的扩展，我们将其称为图匹配网络（GMN）以进行相似性学习。GMN通过跨图关注机制来计算跨图的节点并识别差异，而不是为每个图独立地计算图表示。

1.3 贡献

1.证明了GNNs可以用来生成图嵌入，用于图相似度学习

2.提出了图匹配网络（Graph Matching Networks），可以通过交叉图注意力匹配来进行计算相似度。

3.实验表明相似度学习模型可以在一系列应用上实现好的性能。

2 Methodology

本文提出了Graph Embedding Model和Graph Matching Network。分别如下图左边和右边。

2.1 Graph Embedding Model

主要基于GNN来提取图上的信息，然后通过若干轮，在图上相邻节点之间交换信息，然后再把所有节点上的信息聚合产生关于这个图的整体embedding。分为三步Encoder、Propagation Layers和Aggregator。

2.1.1 Encoder

对图上每一个节点和每一条边的特征进行编码，如果节点或者边没有更多额外能利用的信息的话，它们的原始特征可以设置为常数1，即$x_{i}=1, x_{i j}=1$xi​=1,xij​=1。

$\begin{aligned} \mathbf{h}_{i}^{(0)}=& \operatorname{MLP}_{\text {node }}\left(\mathbf{x}_{i}\right), \quad \forall i \in V \\ \mathbf{e}_{i j}=& \operatorname{MLP}_{\text {edge }}\left(\mathbf{x}_{i j}\right), \quad \forall(i, j) \in E \end{aligned}$hi(0)​=eij​=​MLPnode ​(xi​),∀i∈VMLPedge ​(xij​),∀(i,j)∈E​
其中$x_i$xi​、$x_{ij}$xij​分别代表节点和边的特征，相应的MLP编码器就是简单的一个隐含层的神经网络。

2.1.2 Propagation Layers

第二步是在图上进行多轮的信息传播。每轮中，每条连边都通过一个神经网络生成一个message，每个节点都接受来自相邻节点的message并且形成新的节点表示。将相邻节点信息汇聚到中间节点可以使用均值、最大值和注意力等方法。
$\begin{array}{ll} \mathbf{m}_{j \rightarrow i}= & f_{\text {message }}\left(\mathbf{h}_{i}^{(t)}, \mathbf{h}_{j}^{(t)}, \mathbf{e}_{i j}\right) \\ \mathbf{h}_{i}^{(t+1)}= & f_{\text {node }}\left(\mathbf{h}_{i}^{(t)}, \sum_{j:(j, i) \in E} \mathbf{m}_{j \rightarrow i}\right) \end{array}$mj→i​=hi(t+1)​=​fmessage ​(hi(t)​,hj(t)​,eij​)fnode ​(hi(t)​,∑j:(j,i)∈E​mj→i​)​

2.1.3 Aggregator

第三步是把得到的节点表示都聚合起来，形成关于整个图的embedding。
$\mathbf{h}_{G}=\operatorname{MLP}_{G}\left(\sum_{i \in V} \sigma\left(\operatorname{MLP}_{\text {gate }}\left(\mathbf{h}_{i}^{(T)}\right)\right) \odot \operatorname{MLP}\left(\mathbf{h}_{i}^{(T)}\right)\right)$hG​=MLPG​(i∈V∑​σ(MLPgate ​(hi(T)​))⊙MLP(hi(T)​))
转换节点表示，然后使用带有门控向量的加权和在节点之间进行聚合。加权和可以帮助过滤掉不相关的信息，它比简单的和功能更强大，在经验上也有显著的提高。

2.2 Graph Matching Network

该模型在第一步和第三步都和前一种模型相同，最主要的区别是第二步在message passing的过程中会在两个图之间传递信息，每个节点都会去尽量匹配另一个图中的相似节点，并且产生图之间的信息传递。
$\begin{aligned} \mathbf{m}_{j \rightarrow i}= f_{\text {message }}\left(\mathbf{h}_{i}^{(t)}, \mathbf{h}_{j}^{(t)}, \mathbf{e}_{i j}\right), \forall(i, j) \in E_{1} \cup E_{2} \\ \boldsymbol{\mu}_{j \rightarrow i}= f_{\text {match }}\left(\mathbf{h}_{i}^{(t)}, \mathbf{h}_{j}^{(t)}\right), \forall i \in V_{1}, j \in V_{2}, \text { or } i \in V_{2}, j \in V_{1} \\ \mathbf{h}_{i}^{(t+1)}=f_{\text {node }}\left(\mathbf{h}_{i}^{(t)}, \sum_{j} \mathbf{m}_{j \rightarrow i}, \sum_{j^{\prime}} \boldsymbol{\mu}_{j^{\prime} \rightarrow i}\right) \\ \mathbf{h}_{G_{1}}=f_{G}\left(\left\{\mathbf{h}_{i}^{(T)}\right\}_{i \in V_{1}}\right) \\ \mathbf{h}_{G_{2}}=f_{G}\left(\left\{\mathbf{h}_{i}^{(T)}\right\}_{i \in V_{2}}\right) \\ s=f_{s}\left(\mathbf{h}_{G_{1}}, \mathbf{h}_{G_{2}}\right) \end{aligned}$mj→i​=fmessage ​(hi(t)​,hj(t)​,eij​),∀(i,j)∈E1​∪E2​μj→i​=fmatch ​(hi(t)​,hj(t)​),∀i∈V1​,j∈V2​, or i∈V2​,j∈V1​hi(t+1)​=fnode ​⎝⎛​hi(t)​,j∑​mj→i​,j′∑​μj′→i​⎠⎞​hG1​​=fG​({hi(T)​}i∈V1​​)hG2​​=fG​({hi(T)​}i∈V2​​)s=fs​(hG1​​,hG2​​)​

最关键的是$f_{\text {match}}$fmatch​，即如何产生两个图之间的匹配并且在图之间传递信息。这一步的具体产生形式如下:

$\begin{aligned} a_{j \rightarrow i} &=\frac{\exp \left(s_{h}\left(\mathbf{h}_{i}^{(t)}, \mathbf{h}_{j}^{(t)}\right)\right)}{\sum_{j^{\prime}} \exp \left(s_{h}\left(\mathbf{h}_{i}^{(t)}, \mathbf{h}_{j^{\prime}}^{(t)}\right)\right)} \\ \boldsymbol{\mu}_{j \rightarrow i} &=a_{j \rightarrow i}\left(\mathbf{h}_{i}^{(t)}-\mathbf{h}_{j}^{(t)}\right) \end{aligned}$aj→i​μj→i​​=∑j′​exp(sh​(hi(t)​,hj′(t)​))exp(sh​(hi(t)​,hj(t)​))​=aj→i​(hi(t)​−hj(t)​)​

2.3 模型训练

图相似度模型可以在一对图和一组三个图上训练。

2.3.1 margin-based pairwise loss

$L_{\text {pair }}=\mathbb{E}_{\left(G_{1}, G_{2}, t\right)}\left[\max \left\{0, \gamma-t\left(1-d\left(G_{1}, G_{2}\right)\right)\right\}\right]$Lpair ​=E(G1​,G2​,t)​[max{0,γ−t(1−d(G1​,G2​))}]

$t \in\{-1,1\}$t∈{−1,1}是一组标签，$\gamma>0$γ>0是超参数，$d\left(G_{1}, G_{2}\right)=\left\|\mathbf{h}_{G_{1}}-\mathbf{h}_{G_{2}}\right\|^{2}$d(G1​,G2​)=∥hG1​​−hG2​​∥2是欧氏距离，当$t=1$t=1时，损失函数希望$d\left(G_{1}, G_{2}\right)<1-\gamma$d(G1​,G2​)<1−γ，当$t=-1$t=−1时，希望$d\left(G_{1}, G_{2}\right)>1+\gamma$d(G1​,G2​)>1+γ。

2.3.1 margin-based triplet loss

$L_{\text {triplet }}=\mathbb{E}_{\left(G_{1}, G_{2}, G_{3}\right)}\left[\max \left\{0, d\left(G_{1}, G_{2}\right)-d\left(G_{1}, G_{3}\right)+\gamma\right\}\right]$Ltriplet ​=E(G1​,G2​,G3​)​[max{0,d(G1​,G2​)−d(G1​,G3​)+γ}]

它要求更为相似的对之间的距离至少比另一对之间的距离至少小$\gamma$γ。

3 Experiments

3.1 Learning Graph Edit Distances

第一个实验是人工生成的graph之间的比较，给定 $n$n 个节点和节点之间连边的概率 $p$p，随机生成一个图 $G_1$G1​，随机替换$k_p$kp​条边生成正样本 $G_2$G2​，随机替换 $k_n$kn​ 条边生成负样本 $G_3$G3​ ，其中 $k_p< k_n $。


当两个图相匹配时，注意力权值能够很好地对齐节点，而当两个图不匹配时，注意力权值则倾向于聚焦程度较高的节点。

3.2 Control Flow Graph based Binary Function Similarity Search

第二个实验是检查函数流程图之间的相似性，给定一系列函数（开源软件ffmpg中的各个函数）不同的编译器和编译指令编译出来会得到不同的汇编命令流程图，相同函数编译出来的不同流程图应该被看做是“类似”的，而不同函数编译出来的应该被看做是“不同”的。

ty Search

第二个实验是检查函数流程图之间的相似性，给定一系列函数（开源软件ffmpg中的各个函数）不同的编译器和编译指令编译出来会得到不同的汇编命令流程图，相同函数编译出来的不同流程图应该被看做是“类似”的，而不同函数编译出来的应该被看做是“不同”的。

参考：
https://zhuanlan.zhihu.com/p/65080269