2019
摘要
通過新的基于交叉圖注意力的比對機制對輸入的一對圖進行聯合推理，計算它們之間的相似度得分
1.引言
現有的GNN通過疊代聚合局部結構資訊的傳播過程設計和計算圖節點表示，對圖元素的排列保持不變
（這句話文法分析看着好怪，詞性真的沒用錯嗎）
Scarselli et al., 2009;
Li et al., 2015;
Gilmer et al., 2017
然後将這些節點表示直接用于節點分類，或彙集到圖向量中進行圖分類。
GNN 對監督分類或回歸之外的問題的研究相對較少。
主要任務：
- 證明GNN可以為相似性學習提供嵌入
- 設計GMN計算圖間相似比對
2.相關
提出GNN與WL研究圖同構（相同）與本文要研究圖相似有差別
全圖同構或子圖同構(Berretti et al., 2001; Shasha et al., 2002; Yan et al., 2004; Srinivasa & Kumar, 2003)
——————
（這一段倒是總結了不少圖核的論文）
不過也提出圖核更重于設計，基于圖論，沒有基于學習，不端到端
(Yanardag & Vishwanathan, 2015)
引入了學習，但基本元素還是手工設計的
————————
Siamese網絡可通過網格化計算相似度
3.深層圖相似計算
采用标準GNN和本文的GMN
3.1 圖嵌入模型
這裡GNN包括三部分
- 編碼器
- 傳播層
- 聚合
編碼器
通過MLP構造節點和邊的嵌入向量h和e
傳播層
将節點嵌入映射到新的節點表示
其中fmessage 通常是對輸入拼接做MLP，而 fnode 可以是 MLP 或RNN系列
絕活這些資訊可以用簡單的求和，也可以用均值，最值，注意力等
通過多層傳播，每個節點的表示将在其局部鄰域中積累資訊。
聚合
輸入一系列節點表示計算出一個圖表示
通過上述帶有門控權重的聚合方法，可以濾波掉無關資訊，這比上面說的求和等方法強得多
有了兩個圖的表示就可以在歐式空間計算相似度了，比如歐氏距離，餘弦相似度，漢明相似度等
如果沒有傳播層就是
Deep Set (Zaheer et al., 2017) or PointNet (Qi et al., 2017)
計算獨立點的表示，再池化到整個圖上，但這樣就忽視了結構資訊，單純在處理一堆獨立資料
3.2 GMN
相比起GNN單獨對每個圖搞成嵌入，GMN是針對每對圖計算相似度
改變每個傳播層的節點更新子產品，不僅考慮之前每個圖邊上的聚合資訊，而且考慮圖間比對向量，用來衡量一個圖中的節點與另一個圖中的一個或多個節點的比對程度
這裡fmatch可以用注意力機制
相比起GNN，GMN在時間上開銷多了些
注意力子產品有兩個好處：
- 兩圖完美比對時，注意力權重達到峰值，μ的和為0，這樣兩圖在下一輪傳播中會計算相同的表示
- 圖間差異會記錄在μ的和中，通過傳播逐漸放大，可以讓比對模型對差異更加敏感
比對模型可以基于其他圖來改變目前圖的表示，也即調整圖的表示使得圖間差異愈發明顯便于比對
3.3 學習
可以選擇成對訓練，還是三元訓練
成對訓練需要标簽positive (相似) or negative (不相似)
而三元訓練隻需要相對相似，即 G1 更接近 G2 還是 G3
使用歐式相似度，基于邊緣的成對損失
其中t ∈ {−1, 1}作為這一對圖的标簽，γ > 0是邊緣參數，d是歐氏距離
當這一對相似（t=1）時，損失L收斂到0會讓d< 1−γ；當 t = −1 時，d> 1+γ。
給定 G1 和 G2 比 G1 和 G3 更接近的三元組，我們優化以下基于邊距的三元組損失：
損失收斂到0可以通過邊緣γ讓d(G1, G2)比d(G1, G3) 小
将圖表示成二進制-1或1，可以最小化相似對的漢明距離，最大化不相似對的距離
（擴大類間距，縮小類内距的方法嗎？）
這樣可以提高檢索效率
于是可以引入tanh變化優化損失函數
其中
是近似的平均漢明距離
（有點像多圖遞歸矩陣補全代碼裡的那個損失函數處理）
這樣會比基于邊緣的損失更穩定
4.實驗
4.1 GED
GED被定義為圖間最小距離，因為是NP難是以近似
（但是既然近似計算相似度的這些算法裡沒有用到GED或者其思想，那為啥還要說它呢，不就和它沒關系嗎？）
訓練過程：
随機構造一個n節點，邊機率p的圖G1，然後再随機替換kp條邊為新邊構造相似樣本G2，替換kn條邊構造不相似樣本G3，kp<kn
（原來如此，代碼裡構造資料集的過程類似于GED，這不是NP難嗎，怪不得運作不出來？）
模型需要預測相似對（G1，G2）的相似度高于不相似對（G1，G3）
對于 GMN，可以将圖間注意力可視化，以進一步了解它是如何工作的。
可以看到，當兩個圖比對時，注意力權重可以很好地對齊節點，而當它們不比對時，往往會關注度數較高的節點。 然而，該模式不像标準注意力模型那樣具有可解釋性。
5.總結
從相似性學習設定中學習的表示也可以輕松地泛化到訓練期間未見過的類的資料（零樣本泛化）。