DeepMind & Google最新論文提出圖匹配網絡，用于相似性學習問題，在幾大圖相關任務中性能超過了標準圖網絡GNN和其他模型。

一種新的圖匹配網絡，在幾個圖相關任務中均勝過精心設計的神經網絡模型和基于標準GNN的圖嵌入模型。

本文介紹來自DeepMind & Google的一篇ICML論文：《用于學習圖結構對象相似性的圖匹配網絡》。

地址：

https://arxiv.org/pdf/1904.12787.pdf

這篇論文針對圖結構對象的檢索與匹配這一具有挑戰性的問題，做了兩個關鍵的貢獻。

首先，作者演示了如何訓練圖神經網絡(GNN)在向量空間中生成圖嵌入，從而實現高效的相似性推理。

其次，作者提出了一種新的圖匹配網絡(Graph Matching Network)模型，給出一對圖形作為輸入，通過一種新的基于注意力的跨圖匹配機制(cross-graph attention-based matching mechanism)，對圖對進行聯合推理，計算出一對圖之間的相似度評分。

論文證明了該模型在不同領域的有效性，包括具有挑戰性的基于控制流圖(control-flow-graph)的函數相似性搜索問題，該問題在軟件系統漏洞檢測中具有重要作用。

實驗分析表明，圖匹配模型不僅能夠在相似性學習的背景下利用結構，而且還能夠勝過針對這些問題精心手工設計的領域特定的基線系統。

圖結構對象的相似性學習問題

圖是編碼關系結構的一種自然的表示，這種關系結構在許多領域都會遇到。通過圖結構數據定義的計算被廣泛應用于各領域，從用于計算生物學和化學的分子分析，到自然語言理解的知識圖或圖結構解析的分析。

近年來，圖神經網絡(GNNs)已成為一種有效的學習結構化數據表示和解決基于圖的各種監督預測問題的模型。通過迭代地聚合局部結構信息的傳播過程來設計和計算圖節點表示，這些模型對圖元素的排列是不變的。然后，這些節點表示被直接用于節點分類，或者合并到一個圖向量中用于圖分類。對于GNN，除了監督分類或回歸之外的問題的研究相對較少。

本文研究了圖結構對象的相似性學習問題(similarity learning)，該問題在現實世界中有許多重要的應用，尤其是在圖數據庫中基于相似性的檢索。

一個應用是二進制函數計算機安全問題的相似性搜索，給定一個可能包含或不包含具有已知漏洞代碼的二進制，我們要檢查該二進制中的任何控制流圖是否與數據庫中已知易受攻擊的函數非常相似。

這有助于在封閉源代碼軟件中識別易受攻擊的靜態鏈接庫，這是一個反復出現的問題，目前沒有好的解決方案。

圖1顯示了該應用的一個示例，其中二進制函數表示為帶有匯編指令注釋的控制流圖。

二進制函數相似性學習問題

這種相似性學習問題非常具有挑戰性，因為細微的差異就可以使兩個圖在語義上非常不同，而具有不同結構的圖仍然可以是相似的。

因此，一個成功的模型應該：

(1)利用圖的結構，

(2)能夠從圖的結構和所學習的語義推斷出圖的相似性。

為了解決圖的相似度學習問題，我們研究了GNN在這種情況下的使用，探討了如何將圖嵌入到向量空間中，并學習這種嵌入模型，使相似的圖在向量空間中更接近，而不同的圖在向量空間中距離更大。

該模型的一個重要特性是，它將每個圖獨立地映射到一個嵌入向量，然后所有的相似度計算都在向量空間中進行。因此，可以預先計算和索引大型數據庫中的圖嵌入，從而能夠使用快速的最近鄰搜索數據結構(如k-d trees)或局部敏感哈希算法(locality sensitive hashing)實現高效檢索。

我們進一步提出了一種對GNN的擴展，我們稱之為圖匹配網絡(Graph Matching Networks, GMNs)，用于相似性學習。

GMN不是單獨計算每個圖的表示，而是通過cross-graph的注意力機制來計算相似度評分，以便跨圖進行關聯節點和識別差異。通過使圖表示計算依賴于對(pair)，該匹配模型比嵌入模型更強大，提供了良好的精度-計算的權衡。

我們在三個任務上評估了所提出的模型和基線模型：一個是合成圖edit-distance學習任務，僅捕獲結構相似性；以及兩個現實世界任務——二進制函數相似性搜索和網格檢索，這兩個任務都需要對結構相似性和語義相似性進行推理。

在所有三個任務上，我們提出的方法都優于已有的基線模型和結構無關模型；在更詳細的消融研究中，我們發現圖匹配網絡始終優于圖嵌入模型和Siamese網絡。

總結而言，本文的貢獻在于：

(1)演示了如何使用GNN生成用于相似性學習的圖嵌入；

(2)提出了一種新的圖匹配網絡，通過基于cross-graph的注意力匹配來計算相似性；

(3)實證結果表明，本文所提出的圖相似性學習模型在多個應用中具有良好的性能，并且優于結構無關模型和已有的基線模型。

深度圖相似性學習

給定兩個圖G = (V?, E?)和G? = (V?, E?)，我們想要有一個模型來生成它們之間的相似度評分s(G?, G?)。每個圖表示為G = (V, E)，即節點V和邊E的集合，任意一個節點i∈V都可以與一個特征向量x_i相關聯，任意一條邊(i, j)∈E都可以與一個特征向量x_ij相關聯。這些特征可以表示諸如節點的類型、邊的方向等。如果一個節點或一條邊沒有任何相關的特征，我們就將相應的向量設置為常數向量1。

我們提出了兩種圖相似度學習模型：一種是基于標準GNN的學習圖嵌入模型，以及一種新的、更強大的GMN模型。

兩種模型如圖2所示。

圖嵌入模型(Graph Embedding Models)

圖嵌入模型是將每個圖嵌入到一個向量中，然后在該向量空間中使用相似性度量來度量圖之間的相似性。我們的GNN嵌入模型包括三個部分：(1)編碼器，(2)傳播層，(3)聚合器。

圖2：圖嵌入模型(左)和圖匹配模型(右)

圖匹配網絡

圖匹配網絡以一對圖作為輸入，并計算它們之間的相似度評分。與嵌入模型相比，匹配模型是在“對”的基礎上計算相似度的，而不是先將每個圖單獨映射到一個向量。因此，匹配模型可能比嵌入模型更強大，但代價是額外的計算效率。

我們提出如下的圖匹配網絡，改變了每個傳播層中的節點的更新模塊，不僅考慮每個圖邊緣的聚合信息，也考慮衡量一個節點在一個圖中匹配其他一個或多個節點的效果的cross-graph匹配向量：

實驗和結果

本節在三個任務上評估了圖相似性學習(GSL)框架和圖嵌入網絡(GNN)和圖匹配網絡(GMN)，并將這些模型與其他競爭方法進行了比較。

總體而言，實驗結果表明，GMN在圖相似度學習方面表現優異，始終優于其他方法。

Learning Graph Edit Distances

圖G?和圖G?之間的圖編輯距離(Graph edit distance)的定義是將G?轉換為G2所需的最小編輯操作數。通常，編輯操作包括添加/刪除/替換節點和邊緣。

圖的編輯距離自然是圖之間相似性的度量，在圖的相似性搜索中有許多應用。通過這個實驗，我們證明了GSL模型可以在極具挑戰性的問題上學習圖之間的結構相似性。

表1：圖嵌入(GNN)和圖匹配(GMN)模型與基線的比較

從表1可以看到，通過學習特定分布的圖，GSL模型能夠比一般基線做得更好，而GMN始終優于嵌入模型(GNN)。

圖3：圖匹配模型cross-graph attention的可視化

對于GMN，我們可以將cross-graph attention可視化，從而進一步了解它是如何工作的。圖3顯示了匹配模型的兩個例子，cross-graph注意力權重以綠色表示，權重的比例以綠色邊的透明度表示。我們可以看到，當兩個圖匹配時，注意力權重可以很好地對齊節點，當兩個圖不匹配時，注意力權重往往集中在度數較高的節點上。然而，這種模式并不像標準注意力模型那樣具有可解釋性。

基于控制流圖的二進制函數相似性搜索

二進制函數相似性搜索(Binary function similarity search)是計算機安全中的一個重要問題。當我們無法訪問源代碼時，例如在處理商業或嵌入式軟件或可疑的可執行程序時，就需要分析和搜索二進制文件。結合反匯編器和代碼分析器，我們可以提取一個控制流圖(CFG)，它以結構化格式包含二進制函數中的所有信息。

在CFG中，每個節點都是組裝指令的基本塊，節點之間的邊表示控制流，例如在分支、循環或函數調用中使用的跳轉或返回指令表示。

本節中，我們將針對漏洞搜索問題，其中使用已知存在一些漏洞的二進制代碼片段作為查詢，并通過一個庫搜索，找到可能具有相同漏洞的類似二進制代碼。

結果如圖4所示，評估了不同模型在不同傳播步數和不同數據設置下的性能。

圖4：不同模型在二進制函數相似性搜索任務中的性能

結果很顯然：

(1)隨著傳播步數增加，圖嵌入模型和匹配模型的性能都不斷增高；

(2)在傳播步數足夠的情況下，圖嵌入模型始終優于基線；

(3)圖匹配模型在所有設置和傳播步數的情況下都優于嵌入模型。

表2：函數相似性搜索任務的更多結果

表2總結了更多實驗，結果表明：

(1)GNN嵌入模型是有競爭力的模型(比GCN模型更強大)；

(2)利用Siamese網絡結構在圖表示的基礎上學習相似度優于使用預先指定的相似度度量；

(3)在計算過程的早期，GMN優于Siamese模型，說明了跨圖信息通信的重要性。