神經子圖同構計數

摘要

????????本文研究了一個新的圖學習問題：學習計算子圖同構。與其他傳統的圖學習問題，如節點分類和鏈接預測不同，子圖同構計數是NP完全的，需要更多的全局推理來監督整個圖。為了使其可擴展為大規模的圖形和模式，我們提出了一個學習框架，增強不同的表示學習架構和迭代出席模式和目標數據圖，以記憶子圖同構搜索的中間狀態，用于全局計數。我們開發了小圖（每個圖中≤ 1，024個子圖同構）和大圖（每個圖中≤ 4，096個子圖同構）集，以評估不同的表示和交互模塊。誘變化合物數據集MUTAG也用于評估神經模型并證明遷移學習的成功。雖然基于學習的方法是不精確的，但與原始NP完全問題的指數時間相比，我們能夠在線性時間內概括計算大型模式和數據圖。實驗結果表明，基于學習的子圖同構計數可以在誤差可接受的情況下，將傳統算法VF 2的速度提高10- 1000倍。基于微調的域自適應也顯示了我們的方法在現實世界中的應用程序的有用性。

CCS概念

????????計算理論→模式匹配; 信息系統→信息集成。

關鍵詞

? ? ? ? 子圖同構，動態存儲，神經網絡

一、簡介

????????計算子圖同構的目的是確定給定圖的匹配的子圖的數量（即，同構于）感興趣的特定圖案圖。它是知識發現和數據挖掘應用中有用的圖相關任務之一，例如，在生物信息學中發現蛋白質相互作用[1，34]，在化學信息學中為新藥開發尋找活性化合物[24]，以及在在線社交網絡分析中挖掘社交結構[30]。此外，尋找子結構對于異構信息網絡（HIN）（如知識圖和推薦系統）是有用的[13，25，26，59]。HIN模式上的豐富類型提供了有意義的語義，因此計數本身對于各種類型的查詢都很有價值。例如，在知識圖譜中，我們可以回答諸如“非洲有多少種語言是居住在尼羅河沿岸的人說的？”在社交網絡上，類似于“朋友對的數量，其中一個喜歡漫畫，另一個喜歡其電影改編”的查詢可以幫助簡要介紹廣告定向。

????????然而，以前的研究類似的任務往往是在特定的約束條件下，和討論的一般模式上的大型異構圖是有限的。特別是，以前關于計數的研究減少到具有3-5個節點作為基元的小子圖（不考慮同構）[34]或小圖（限于誘導子圖）[38]。此外，盡管定制的模式挖掘算法或基于圖數據庫索引的方法可以解決子圖同構的一般問題[5，8，19，20，48]，但由于任務的NP完全性質，所有這些算法都難以擴展到更大的圖。為了在更一般和理論上基本的設置下擴展到更大的圖，需要替代的可擴展方法。具體來說，我們轉而通過機器學習來近似答案。圖學習最近引起了人們的廣泛關注，因為表示學習的神經方法已被證明對復雜數據結構有效[18，28，35，40，50，53]。不可否認，大多數現有的圖表示學習算法都集中在節點分類和鏈接預測等任務上[17]，這些任務來自局部結構的信息足以進行推理。這些任務與我們的任務不同，我們的任務是在整個圖上計數。然而，最近已經證明，涉及全局推理的更具挑戰性的推理問題，如匯總統計，關系argmax，動態規劃和NP-hard子集求和，可以通過使用適當設計的架構進行學習來優雅地解決[54]。結果是鼓舞人心和令人鼓舞的。然而，在利用機器學習計算子圖同構的目標面前仍然存在挑戰：

現有數據集的典型大小是有限的，遠遠不足以訓練圖神經網絡。同時，與其他圖學習問題（如最短路徑[15]或中心性[11]）相比，由于難以獲得地面真值，因此為這個問題生成足夠的訓練數據是不平凡的。
必須仔細選擇合適的歸納偏置，以完成這一具有挑戰性的任務[3]。因此，應該考慮以下考慮：首先，作為考慮異構節點類型和邊類型的一般情況，為了表示和區分具有鄰域結構的節點和邊，應該應用更強和更復雜的表示學習技術。其次，任務不是在單個圖上執行，而是涉及額外的模式。因此，在模型設計中必須考慮兩個圖之間的相互作用。第三，該模型將被訓練并應用于不僅具有大型圖形而且具有大量樣本的數據集，考慮到可能模式的多樣性。因此，還應考慮計算效率。

????????在本文中，為了解決上述挑戰，我們首先為我們的實驗開發了兩個大規模數據集，包括一個小圖（每個圖中的計數≤ 1，024）和一個大圖（每個圖中的計數≤ 4，096）。我們開發了一個框架來從我們的數據集中學習。為了在圖神經網絡中找到適當的歸納偏差，我們比較了提取節點和邊的表示的不同方法，包括CNN [27]，RNN如GRU [7]，注意力模型如Transformer-XL [9]，RGCN [40]，這是異構圖的圖卷積網絡的自然推廣，以及RGIN，RGCN與最近的圖同構網絡（GIN）的擴展[53]。此外，我們開發了一個動態的中間注意記憶網絡（DIAMNet），它迭代地參加查詢模式和目標數據圖掃描的數據圖與局部結構記憶的全局推理。然后，我們對我們的合成數據集進行系統評估，以證明我們引入的歸納偏差的有效性。此外，我們還進行了實驗，著名的基準數據集，MUTAG，顯示的權力和實用性，我們的方法為真實的應用程序。

????????我們的主要貢獻概括如下：

據我們所知，這是第一個將子圖同構計數問題建模為學習任務的工作，其中訓練和推理都具有線性時間復雜度，可根據模式/圖大小和數據示例的數量進行伸縮
我們在端到端學習框架下，利用不同深度神經網絡架構的表示能力。特別地，我們為序列模型和圖模型提供了通用的編碼方法，并在此基礎上引入了一個動態中間注意力記憶網絡來解決更全局的計數推理問題.
我們在兩個合成數據集和一個著名的真實的基準數據集上進行了拓展實驗，這表明我們的框架可以在相對較大的圖和模式上實現良好的結果。有關數據和代碼，請訪問https://github.com/HKUST-KnowComp/NeuralSubgraphCounting

二、前言

????????我們開始先介紹問題和我們的總體思路

2.1問題定義

????????傳統上，子圖同構問題定義在兩個簡單圖或兩個有向簡單圖之間，這是一個NP完全問題。我們將問題擴展到更一般的情況下，有向異構多重圖。圖或模式定義為 $G=\left (V,E,X,Y \right )$ ，其中 $V$ 是頂點的集合，每個頂點具有不同的頂點id。 $E \subseteq V \times V$ 是邊的集合， $X$ 是將頂點映射到頂點標簽的標簽函數， $Y$ 是將邊映射到邊標簽集合的標簽函數。在異構多重圖的背景下，每個多重邊可以用一個有序的源和目標對以及一組邊標簽沿著來表示。也就是說，每個邊可以用源、目標及其邊標簽唯一地標識。為了簡化陳述，我們假設 $Y((u,v)) = \phi$ 如果 $(u,v )\notin E$ 。在這里，我們專注于保持圖拓撲，頂點標簽和邊標簽，但不是頂點ID的同構映射。更精確地說，一個模式 $G_P=\left (V_P,E_P,X_P,Y_P \right )$ 同構于一個圖 $G_G=\left (V_G,E_G,X_G,Y_G \right )$ ，如果存在一個雙射 $f:V_G \rightarrow V_p$ 使得

$\bullet \forall v \in V_G,X_G(v)= X_p(f(v))\\ \bullet \forall v \in V_P,X_P(v)= X_G(f^{-1}(v))\\ \bullet \forall (u,v) \in E_G,Y_G((u,v))= Y_p((f(u),f(v)))\\ \bullet \forall (u,v) \in E_P,Y_P((u,v))= Y_G((f^{-1}(u),f^{-1}(v)))\\$

????????然后，將同構于圖 $G_G$ 的模式 $G_P$ 記為 $G_P \simeq G_G$ ，將函數 $f$ 記為同構。此外，模式 $G_P=\left (V_P,E_P,X_P,Y_P \right )$ 同構于圖 $G_G=\left (V_G,E_G,X_G,Y_G \right )$ 的子圖 $G_G^{'}=\left (V_G^{'},E_G^{'},X_G^{'},Y_G^{'} \right )$ , $V_G^{'} \subseteq V_G^{'} ,\:E_G^{'} \subseteq E_G \cap \left ( V_G^{'} \times V_G^{'} \right )$ 如果 $G_P \simeq G_G^{'}$ 。雙射函數 $f:V_G^{'} \rightarrow V_p$ 稱為子圖同構。

????????定義子圖同構計數問題為求模式圖 $G_P$ 與圖 $G_G$ 之間所有不同子圖同構的個數。示例如圖1所示。

圖一：不同設置中的子圖同構計數示例：同構圖、存在兩種類型的節點的異構頂點圖、以及存在兩種類型的節點和兩種類型的邊的異構頂點和異構邊圖。

2.2總體思路

????????因此，我們需要計算 $O\left ( Perm\left ( \left | V_G \right |, \left | V_P \right |\right ) \cdot d^{\left | V_p \right |}\right )$ 用蠻力法解決子圖同構計數問題，其中 $Perm(n,k) = \frac{n!}{(n-k)!}$ , $\left| V_G \right |$ |圖節點的數量 $\left| V_P \right |$ 是模式節點數， $d$ 是最大度。Ullmann的算法[48]，任務的標準精確方法，將搜索時間減少到 $O\left (\left | V_p \right | ^{\left | V_G \right |} \cdot \left | V_G \right | ^2\right )$ .

三、方法論

圖2：神經子圖同構計數模型的一般框架

????????學習計算子圖同構的一般框架如圖2所示。在我們的框架中，我們把圖 $G_G$ 看作包含信息的數據，把模式 $G_p$ 看作從圖中檢索信息的查詢。因此，計數問題可以自然地被公式化為在自然語言處理中很好地建立的問答問題（例如，[29]）。除了文本和圖形作為輸入的差異之外，主要問題是在QA模型中，答案通常是從提供的文本中提取的事實，而在計數問題中，答案是匹配的局部模式的匯總統計。為了使問題可學習，圖（或模式）應該表示為一系列邊，或一系列相鄰矩陣和頂點特征。圖3顯示了序列編碼和圖形編碼之間的區別。對于序列輸入，我們可以使用CNN [27]，RNN如LSTM [22]或Transformer-XL [9]來提取高級特征。如果輸入被建模為一系列相鄰矩陣和頂點特征，我們可以使用RGCN [40]或GIN [53]的擴展來學習頂點表示，并從鄰域傳遞消息。在獲得模式表示和圖形表示之后，我們將它們饋送到交互模塊中以從每一側提取相關特征。然后，我們將交互模塊的輸出上下文與大小信息饋送到完全連接的層中以進行預測。

圖3：不同編碼方法的兩個視圖。有三個頂點標簽（標記為橙子、藍色和黃色）和兩個邊標簽（標記為實線和虛線）。附加的數字顯示了頂點的一組可能的id。

3.1序列模型

3.1.1序列編碼

????????在序列模型中，圖（或模式）的最小元素是邊。根據定義，至少需要三個屬性來標識邊 $e$ ，它們是源頂點id $u$ 、目標頂點id $v$ 和它的邊標簽 $y \in Y(e)$ 。我們進一步添加頂點標簽的兩個屬性以形成一個5元組 $\left ( u,v,X(u),y,X(v) \right )$ 來表示邊的標簽，其中 $X(u)$ 是源頂點標簽， $X(v)$ 是目標頂點標簽。五元組的列表被稱為代碼。我們遵循gSpan [55]中定義的順序來按字典順序比較代碼對;附錄A中給出了詳細的定義。最小代碼是具有相同元素的最小詞典順序。最后，每個圖都可以用相應的最小代碼來表示，反之亦然。

????????假設一個圖被表示為一個最小碼，或者一個5元組的列表，下一個編碼步驟是將每個5元組轉換為一個向量。假設我們提前知道在一個數據集中 $|V|, |X|, |Y|$ 的最大值，我們可以預先將每個頂點id，頂點標簽和邊標簽編碼成 $\textup{B-aray}$ 數字，其中 $\textup{B}$ 是基數，每個數字 $d \in \left \{ 1,2,\cdots, B-1 \right \}$ 。我們可以將每個數字表示為一個one-hot vector，這樣每個id或label就可以被矢量化為一個multi-hot vector，它是這些one-hot vector的串聯。此外，5個多熱向量可以連接以表示5元組。5元組的多熱向量的長度為 $B \cdot \left ( 2 \cdot \left \lceil log_B\left ( Max\left ( \left | V \right | \right ) \right ) \right \rceil + 2 \cdot \left \lceil log_B\left ( Max\left ( \left | X \right | \right ) \right ) \right \rceil + \cdot \left \lceil log_B\left ( Max\left ( \left | Y\right | \right ) \right ) \right \rceil \right )$ 。最小值是在 $B = 2$ 時達到的。我們可以很容易地計算圖元組的維數 $d_g$ 和模式元組的維數 $d_p$ 。此外，最小碼可以被編碼成一個多熱矩陣， $\mathbf{G} \in \mathbb{R}^{\left | E_G \right | \times d_g}$ 對于圖 $G_G$ 或 $\mathbf{P} \in \mathbb{R}^{\left | E_P \right | \times d_p}$ 對于模式 $G_P$ 。

3.1.2序列神經網絡

????????給定3.1.1節中的編碼方法，我們可以簡單地將圖嵌入為多熱矩陣。然后，我們可以使用序列建模的一般策略來學習圖中邊之間的依賴關系。

卷積神經網絡（CNNs）

????????已被證明在序列建模中是有效的[27].在我們的實驗中，我們堆疊乘卷積層和最大池層，以獲得一系列高級特征。

長短時記憶體（LSTM）

????????[22]廣泛用于許多序列建模任務。它的存儲器單元被認為能夠學習長期依賴性。

Transformer-XL（TXL）

????????[9]是Transformer架構[49]的變體，能夠在不破壞時間一致性的情況下學習超過固定長度的長依賴關系。與原始的自回歸設置不同，我們使用Transformer-XL作為特征提取器，其中注意力機制在整個序列上具有完整的，未掩蔽的范圍。但其計算開銷與數據段長度和內存大小成二次方增長，因此需要在性能和效率之間進行權衡.

3.2圖模型

3.2.1圖形編碼

????????在圖模型中，每個頂點都有一個特征向量，每條邊用于將信息從源傳遞到目標。GNN不需要顯式的頂點ID和邊ID，因為鄰接信息包含在相鄰矩陣中。如第3.1.1節所述，我們可以將頂點標簽矢量化為多個熱點向量作為頂點特征。(有向或無向)簡單圖的鄰接信息可以存儲在稀疏矩陣中，以減少內存使用量，提高計算速度。對于異構圖，邊的行為應該依賴于邊的標簽。因此，應該應用特定于關系的轉換來混合邊標簽和拓撲信息，并將其傳遞給目標。

3.2.2圖神經網絡

????????我們設置編碼的頂點標簽作為頂點特征，并通過邊傳播混合消息。

關系圖卷積網絡（RGCN）

????????[40]專門用于處理現實知識庫中的多關系數據。每個關系對應于一個轉換矩陣，用于將特定于關系的信息從源轉換到目標。提出了兩種分解方法來解決參數數量隨著關系數量的快速增長的問題：基分解和塊對角分解。我們選擇塊對角分解，并遵循原始設置的均值聚合器。

圖同構網絡（GIN）

????????[53]可以在多層感知器（MLP）和總和聚合器的幫助下更好地捕獲同構圖結構。我們在每個關系圖卷積層之后添加MLP，并使用總和聚合器來聚合消息，我們將此變體命名為RGIN。

3.3動態中介注意記憶

表1：數據集統計。“#”表示數字，“A”表示平均值，“M” 表示最大值

????????在從序列模型或列向量為維的圖模型中獲得圖表示 $\widetilde{G}$ 和模式表示 $\widetilde{P}$ 后，我們將它們作為交互作用層的輸入，以提取模式和圖之間的相關上下文。一個天真的想法是使用注意機制[2]來建模這兩種表示之間的交互以及圖本身上的交互。然而，該方法由于進行序列建模其復雜度高達 $O\left (\left |E_P \right | \cdot \left |E_G \right | + \left |E_G \right |^{2} \right )$ ,對于圖形建模為 $O\left (\left |V_P \right | \cdot \left |V_G \right | + \left |V_G \right |^{2} \right )$ 。

圖4：動態中介注意記憶網絡（DIAMNet）。Φ1表示等式(1)和（2），Φ2表示等式（3）。(4)和（5），并且兩種類型的門是Eqs。(3)和（6）

????????外部存儲器 $M$ 分為 $M$ 塊 $\left \{ m_1,\cdots ,m_M \right \}$ ，其中 $m_j \in \mathbb{R}^d$ 。在每個時間步 $t$ ， $\left \{ m_j \right \}$ 通過多頭注意機制由模式和圖按順序更新[49]。具體地說，我們的DIAMNet的更新方程由下式給出：

$s_j^{(t)} = MultiHead\left ( \textbf{m}_j^{(t)},\widetilde{\boldsymbol{P}}, \widetilde{\boldsymbol{P}}\right ) \\z_j^{(t)} =\sigma\left (\textbf{U}_P \textbf{m}_j^{(t)}+\textbf{V}_P s_j^{(t)}\right ) \\\overline{s}_j^{(t)} =z_j^{(t)} \odot \textbf{m}_j^{(t)} +\left ( 1- z_j^{(t)} \right )\odot s_j^{(t)} \\\widetilde{s}_j^{(t)} = MultiHead\left ( \overline{s}_j^{(t)},\widetilde{\boldsymbol{G}}, \widetilde{\boldsymbol{G}}\right ) \\ \widetilde{z}_j^{(t)} =\sigma\left (\textbf{U}_G \overline{s}_j^{(t)}+\textbf{V}_G \widetilde{s}_j^{(t)}\right ) \\ \textbf{m}_j^{(t+1)} = \widetilde{z}_j^{(t)} \odot \overline{s}_j^{(t)} +\left ( 1- \widetilde{z}_j^{(t)} \right ) \odot \widetilde{s}_j^{(t)}$

????????這里 $MultiHead$ 是[49] 中描述的注意力方法， $\sigma$ 表示邏輯激活函數， $\overline{s}_j$ 是存儲器第 $j$ 塊的模式塊的中間狀態，它總結來自模式的信息， $\widetilde{s}$ 表示來自模式和圖的信息。 $z_j$ 和 $\widetilde{z}_j$ 是兩個門，用于控制第 $j$ 塊中狀態的更新。 $\boldsymbol{U}_P ,\boldsymbol{V}_P ,\boldsymbol{U}_G ,\boldsymbol{V}_G$ 是可訓練的參數。他們有很多可能的方法初始化 $\boldsymbol{M}^{(0)}$ ，我們在附錄D.3中討論內存初始化。

四、實驗

????????在本節中，我們報告我們的主要實驗結果。

4.1數據集

????????為了訓練和評估子圖同構計數問題的神經模型，我們需要生成足夠的graph-pattern數據。

合成數據

????????我們生成兩個合成數據集，一個是小型數據集(small)，一個是大型數據集(large)。由于對模式沒有特殊的約束，模式生成器可以生成任何沒有相同邊的連通多重圖，即，具有相同標簽的平行邊。相反，在給定一種模式的合成數據圖中子圖同構的基本真值數必須是易處理的。我們遵循TurboISO [19]中的鄰域等價類（NEC）的思想來控制圖生成過程中子圖同構的必要條件。詳細算法見附錄B。我們的圖形生成器首先生成多個不連通的組件，可能與一些子圖同構。然后，生成器將這些組件合并到一個更大的圖中，并確保在合并過程中不會創建更多的子圖同構。因此，子圖同構搜索可以在合并成一個大圖之前并行地在小組件上完成。使用上面的模式生成器和圖形生成器，我們可以為神經模型生成許多模式和圖形。我們對以下研究問題感興趣：序列模型和圖模型是否可以在有限的數據下表現良好，它們的運行時間是否可以接受，即使面對NP完全問題，內存是否可以幫助模型做出更好的預測，以及在合成數據上預訓練的模型是否可以轉移到現實數據。為了評估不同的神經架構和不同的預測網絡，我們生成了兩個不同圖形尺度的數據集，統計數據見表1。有187個獨特的模式，其中75個模式屬于小數據集，122個模式屬于大數據集。圖是基于這些模式隨機生成的。生成詳細信息見附錄C.1。

MUTAG

????????我們還在MUTAG數據集上生成了188個圖形的24個模式。我們使用相同的模式發生器生成24種不同的異質模式，其結構見附錄C.2。為了使數據集更具挑戰性，定型數據、開發數據和測試數據中的圖形是不相交的。

4.2實現細節

????????我們使用兩個線性層來分別將模式和圖形多熱點向量轉換為具有預定義隱藏大小的向量，而不是直接將多熱點編碼向量饋送到表示模塊。為了提高效率和性能，我們還增加了一個過濾網絡，過濾掉圖中與給定模式無關的邊或頂點，然后再表示模塊。該濾波器網絡的詳細信息見第D.1節。

4.2.1表示模型

????????在我們的實驗中，我們實現了五種不同的表示模型：（1）CNN是一個3層卷積層，后面是最大池化層。卷積核分別為2、3、4，步長為1。池化內核是2，3，4，步幅是1。(2)LSTM是一個簡單的3層LSTM模型。(3)TXL是一個6層Transformer編碼器，具有額外的內存。(4)RGCN是一個3層的RGCN，采用塊對角分解。我們遵循原始論文中的相同設置，在消息傳播部分使用均值池。(5)RGIN是GIN和RGCN的組合：在每個關系卷積層之后添加2層MLP，并使用總和聚合器。增加了殘差連接[21]以限制消失梯度問題。

4.2.2交互網絡

????????在從表示學習模塊獲得圖形表示 $\widehat{G}$ 和模式表示 $\widehat{P}$ 之后，我們將它們饋送到以下不同類型的交互層進行比較。

Pool：

????????一個簡單的池化操作直接應用于神經模型的輸出，用于分類或回歸。我們將sum pooling、mean-pooling和max pooling中的一種應用于 $\widehat{G}$ 和 $\widehat{P}$ ，以獲得 $\widehat{g}$ 和 $\widehat{p}$ ，然后將 $Concate(\widehat{g},\widehat{p},\widehat{g}-\widehat{p},\widehat{g} \odot \widehat{p})$ 和圖的大小和模式的大小發送到下一個全連接（FC）層。

MemAttn：

????????QA模型總是使用源注意力和自我注意力來尋找段落中的答案[23]。注意力的一個缺點是計算成本。我們考慮將內存用于鍵和值。雙門控多頭注意力應用于 $\widehat{G}$ 和 $\widehat{P}$ ，如附錄D.2所述。最后，我們得到模式和圖的均值池表示，并將池中的相同組合饋送到FC層。

DIAMNet：

????????我們將第3.3節中提出的DIAMNet的性能和效率與上述交互網絡進行了比較。類似地，我們在附錄D.3中有許多初始化策略，但我們發現均值池快速且性能良好。最后，我們將整個內存的大小信息饋送到下一個FC層。DIAMNet和MemAttn之間的主要區別在于，DIAMNet中的內存被視為查詢，初始化一次，更新 $t$ 次，而MemAttn將內存存儲 $2t$ 次，將內存作為鍵和值，并將圖形表示 $\widehat{G}$ 更新 $t$ 次。

4.3實驗設置

????????為了公平比較，我們將嵌入維度、所有表示模型的維度和過濾器的數量都設置為128。基于計算復雜度的考慮，TXL中的段大小和內存大小也是64。對于所有實驗，DIAMNet和MemAttn中的內存長度固定為4。在MemAttn和DIAMNet中，我們使用網格搜索來尋找最佳遞歸步驟，使用均方誤差（MSE）來訓練模型，并根據dev集的結果選擇最佳模型。優化器是AdamW [32]，對于合成數據，基本學習率為1 e-3，對于真實數據，基本學習率為1 e-4，權重衰減系數為1 e-6。為了避免梯度爆炸和過度擬合，我們添加了梯度裁剪和dropout，dropout率為0.2。我們在所有模塊中使用激活函數𝐿𝑒𝑎𝑘𝑦__𝑅𝑒𝐿𝑈。我們使用相同的表示模塊與共享的參數，以產生表示模式和圖形考慮到有限的模式數量。

????????對于small和large數據集，我們首先在小型數據集上訓練模型，然后在大型數據集上進一步使用課程學習[4]。對于MUTAG數據集，我們報告了最佳表示模型RGIN的結果，其中包含不同數量的訓練數據。還進行了從合成數據到MUTAG的遷移學習[36]。

????????????????在PyTorch和DGL框架下，在NVIDIA V100 GPU上完成了神經模型的訓練和評估。VF 2使用16核（32線程）Intel E5- 2620 v4 CPU并行完成。

4.4評估指標

????????當我們將這個子圖同構計數問題建模為學習問題時，我們使用在回歸任務中使用常用的度量，包括均方根誤差（RMSE）和平均絕對誤差（MAE）。在這個任務中，否定的預測是沒有意義的，因此這些預測被視為零。兩個平凡的基線，Zero總是預測0和Avg總是預測訓練數據的平均計數，也被用于比較

4.5合成數據的結果與分析

?????????表2：不同模型在small數據集上的結果,在整個測試集上評估時間

????????我們首先在表2中報告small數據集的結果，在表3中報告large數據集的結果。對于每個表示模塊，僅報告最佳池結果。除了瑣碎的全零和平均基線以及其他基于神經網絡學習的基線之外，我們還想知道我們的神經模型比傳統搜索算法快到什么程度。因此，我們還比較了運行時間（不包括I/O時間）。考慮到我們使用NEC來生成圖而不是隨機生成，為了公平我們與不涉及NEC或類似啟發式規則的VF 2算法[8]進行了比較（例如，VF3[5]中的規則）。從實驗中，我們可以得出以下觀察結果和結論。

表3：不同模型在large數據集上的結果，在整個測試集上評估時間。

不同表示架構的比較

????????如表2所示，一般來說，圖模型優于大多數序列模型。CNN是圖同構計數問題的最差模型。編碼順序沒有考慮相鄰頂點的連通性和相關的標簽信息。因此，卷積操作和池化操作不能提取有用的局部信息，但可能會引入一些噪聲。從large數據集的結果中，我們可以看到CNN也比其他人差。事實上，我們觀察到CNN總是預測大型圖為0。RNN和transformers廣泛用于序列任務，LSTM和TXL是具有內存的高級變體。我們注意到，具有不同交互網絡的LSTM模型始終優于TXL。雖然LSTM的內存比TXL小得多，但LSTM的內存可以以某種方式記住以前看到的所有信息，而TXL的內存只是前一段的表示。在我們的實驗中，段的大小是64，所以TX一次不能學習全局信息。局部結構信息也誤導了TXL，這與CNN一致。為TXL設置更長的段可能會帶來更好的結果，但它需要更多的GPU內存和更長的訓練時間。圖模型的性能總是優于序列模型。這并不奇怪，因為這些圖卷積操作是基于拓撲結構設計的。RGIN模型的性能明顯優于RGCN和其他序列模型，這表明MLP和求和聚合器在該任務中擅長頂點表示學習和結構建模。平均聚合器可以對鄰居的分布進行建模，但該分布可能會誤導模型[53]。

記憶的有效性

????????表2顯示了DIAMNet作為預測層的有效性。它優于其他池方法（SumPool，MeanPool，MaxPool）以及所有表示架構的注意力與內存機制（MemAttn）。這意味著我們可以使用少量額外的GPU內存和相應的計算成本來實現更好的結果。DIAMNet的內存和計算成本隨著輸入的大小線性增長。當模型應用于具有數千甚至數百萬個頂點和邊的實際數據時，其效率是不可忽視的。MemAttn也可以將二次計算成本降低到線性，但其性能不穩定。

????????當表示模塊是CNN或TXL時，基于池化的預測模塊通常更差。這一觀察表明，模式表示的上下文應該被計算在內，我們需要一種更好的方法來聚合上下文中的信息。DIAMNet可以幫助提取模式和圖形的上下文，即使表示層（如CNN）的性能不太好。最后，帶有DIAMNet的CNN是序列模型中最好的。在記憶的幫助下，局部信息可以進一步用于在全局水平上進行推斷。

在較大圖形上的性能

????????表3顯示了大比例圖的結果。我們可以發現大部分的結果與小數據集是一致的。RGIN仍然是我們的任務中最好的表示方法，動態記憶也很有效。在運行時間上，所有基于學習的模型都比傳統的子圖同構計數的VF2算法快得多。此外，神經網絡模型的運行時間僅線性增長，使得其能夠應用于大規模的實際數據。

圖5：在small數據集上，使用MaxPool的CNN和使用DIAMNet的CNN的模型行為。在這里， $O_V$ 表示x軸上的bin按模式/圖形頂點的大小排序， $O_E$ 按邊的大小排序， $O_X$ 按頂點標簽的大小排序， $O_Y$ 按邊標簽的大小排序。橙色表示真實計數，藍色表示預測。

模型行為

????????如圖5所示，使用CNN模型比較了MaxPool和DIAMNet的性能。我們發現，MaxPool總是能預測較小的子圖同構，而DIAMNet即使在圖變得很大很復雜的情況下也能預測較小的同構數，這是因為簡單的合并方法會丟失很多信息。相反，DIAMNet使用較小的存儲器來學習哪些信息應該被保留或丟棄。總體而言，我們的DIAMNet在大多數數據規模上都取得了較好的結果。當條柱按節點標注大小或邊標簽大小排序時，我們有相同的觀察，MaxPool在面對具有更多不同標簽的復雜模式時失敗，但DIAMNet幾乎可以處理所有復雜情況。

圖6：CNN與DIAMNet和RGIN與DIAMNet在large數據集上的模型行為。設置類似于圖5

????????我們還可以從圖6得出結論，不同的表示模塊的性能也不同。當圖尺寸較大（如圖6a和6b所示）并且模式變得復雜（如圖6c和6d所示）時，CNN的表現更差，這進一步表明CNN只提取局部信息，并且在較大的圖中受到全局信息的推斷。相反，帶有DIAMNet的RGIN不受邊大小的影響，因為它直接學習頂點表示而不是邊表示。此外，頂點標簽大小和邊標簽大小沒有明顯的不良影響在RGIN上，但CNN受到嚴重影響。因此，可以看出，具有很少拓撲信息的簡單卷積和池化操作不適合此任務。

4.6 在MUTAG上遷移學習

????????對于MUTAG數據，我們使用不同的交互網絡將不同數量的訓練對輸入到RGIN，并通過微調在小數據集上訓練的模型來嘗試遷移學習。結果如圖7中所示。當訓練數據不足時，從頭建立的模型與遷移學習模型的性能差距不容忽視。在遷移學習的幫助下，經過微調的RGIN模型在任意交互模塊的作用下均能將RMSE降低到1.588以下，而從頭得到的最佳模型的RMSE仍在1.884左右。當訓練數據有限時，除MemAttn-Transfer模型外，其他模型的性能均不理想.當提供30%-40%的訓練數據時，我們可以觀察到遷移學習的巨大改進。之后DIAMNet-Transfer的性能最好，最終達到了1.307的均方根誤差和0.440的平均誤差。值得注意的是，在MUTAG上的訓練數據中沒有出現測試圖，這表明我們的學習計數框架和算法有望在未來處理大規模真實的世界圖.

圖7：基于RGIN的模型在MUTAG數據集上的結果。虛線是從頭開始訓練的模型的結果，而實線是遷移學習的結果。當使用100%訓練數據時，Zero和Avg分別得到19.384和17.754 RMSE。

五、相關工作

子圖同構問題

????????給定一個模式圖和一個數據圖，子圖同構搜索的目標是利用雙射映射函數找到模式在數據圖中的所有出現。子圖同構是不同類型的圖匹配問題（單同構、同構和子圖同構）中的一個NP完全問題。大多數的子圖同構算法都是基于回溯的。該算法首先獲取一系列候選頂點并更新映射表，然后遞歸地調用自己的子圖搜索函數，每次只匹配一個頂點或一條邊。Ullmann算法[48]、VF2 [8]和GraphQL [20]都屬于這種類型的算法。然而，當模式或數據圖增長時，由于搜索空間也呈指數增長，因此仍然難以執行搜索。運用圖索引的思想設計了一些算法，如gIndex [56]，它可以用作過濾器來修剪掉許多不必要的圖。然而，基于圖索引的算法存在一個問題，即索引的時間和空間也隨著圖的增長而呈指數增長[43]。TurboISO [19]和VF 3 [5]添加了一些弱規則來找到候選子區域，然后在子區域上調用遞歸匹配過程。在大多數情況下，這些弱規則可以顯著減少搜索空間。此外，也有一些近似技術[10，47]用于三角形計數，但它們很難推廣到大型模式。隨機游走也被用來計算子圖同構[45，52]，但成本和錯誤仍然是問題。圖模擬[12，33]是另一種在三次時間上找到子圖同構的方法，但研究人員需要糾正拓撲捕獲失敗和錯誤或假匹配。

圖表示學習

????????圖（或網絡）表示學習可以直接學習每個圖節點的嵌入向量[16，37，44]。這種方法不容易推廣到看不見的節點。另一方面，圖神經網絡（GNNs）[3]提供了一種節點表示學習的解決方案，可以推廣到新的圖和看不見的節點。自2005年以來，許多圖神經網絡已經被提出[14，39]，但近年來發展迅速。他們中的大多數專注于將卷積神經網絡的思想推廣到一般的圖數據結構[18，28，35，50]或具有多種關系類型的關系圖結構[40]。最近，[53]提出了一個圖同構網絡（GIN），并展示了它的鑒別能力。其他人使用遞歸神經網絡（RNN）的想法，這些網絡最初被提出來處理序列數據來處理圖形數據[31，58]。有趣的是，有了外部存儲器，序列模型可以很好地處理復雜的任務，如語言建模[29，42]和圖上的最短路徑查找[15]。還有另一個研究分支稱為圖核[6，41，46，51，57]，它也將圖同構轉換為相似性學習問題。然而，他們通常工作在小圖，并沒有專注于子圖同構識別或計數問題。

六、結論

????????本文研究了具有挑戰性的子圖同構計數問題。在深度圖表示學習的幫助下，我們能夠將NP完全問題轉化為基于學習的問題。然后，我們可以使用學習的模型來預測多項式時間內的子圖同構計數。我們建立了兩個合成數據集來評估不同的表征學習模型和全局推理模型。結果表明，基于學習的方法是子圖同構檢測和計數的一個有前途的方向，而動態中間注意力記憶網絡確實有助于全局推理。鳴謝。本文得到了香港研究贈款理事會（RGC）的早期職業發展計劃（ECS，No.26206717）和研究影響基金（RIF，No.R6020 -19）以及華為諾亞方舟實驗室的捐贈基金的資助。

附錄

A 代碼的詞法順序

????????字典序是一個線性序，定義如下：

如果 $A = \left ( a_0,a_1,\cdots,a_m \right )$ 和 $B= \left ( b_0,b_1,\cdots,b_n \right )$ ，則 $A \leq B$ 當且僅當下列任一項為真：

??????? $\left ( 1 \right ) \exists t, 0\leq t\leq min\left ( m,n \right ) ,\forall k < t,a_k= b_k,a_t <_{e} b_t \\\left ( 2 \right ) \forall 0\leq k\leq m, a_k=b_k, \textup{and} n\geq m$

????????在我們的設置中 $a_i =\left ( u_{a_i} , v_{a_i},X( u_{a_i}), y_{a_i},X( v_{a_i})\right ) <_e$ ? $b_j=\left ( u_{b_j} , v_{b_j},X( u_{b_j}), y_{b_j},X( v_{b_j})\right )$ 當且僅當下列之一為真

$\left ( 1 \right ) u_{a_i} < u_{b_j} \\ \left ( 2 \right ) u_{a_i}=u_{b_j} ,v_{a_i} < v_{b_j}\\ \left ( 3 \right ) u_{a_i}=u_{b_j} ,v_{a_i} = v_{b_j}, y_{a_i} < y_{b_j}\\$

B 模式生成器和圖生成器

?算法1 模式生成器

????????如4.1節所述，需要兩個生成器來生成數據集。關于模式生成器的算法如算法1所示，該算法首先統一生成一棵有向樹。然后添加帶有隨機標簽的其余邊。頂點標簽和邊標簽也是統一生成的，但每個標簽都要求至少出現一次。算法2顯示了圖形生成的過程。兩個超參數控制子同構的密度：(1) $\alpha \in \left [ 0,1 \right ]$ 決定加入子同構的概率而不是隨機邊；(2) $\beta \in \mathbb{N}^+$ +是Dirichlet分布對組件樣本大小的參數。在生成多棵有向樹并滿足頂點數要求后，算法開始添加剩余的邊。它可以在一個組件中添加邊并嘗試添加子圖同構，也可以在兩個組件之間或一個組件中隨機添加邊。下面的合并子例程旨在將這些組件合并到一個大圖中。為了使數據集很難被黑客入侵，還需要進行洗牌。由于任意兩個分支之間的邊不滿足必要條件，在整個圖中搜索子同構等價于分別在分支中搜索。

?算法2 圖生成器

????????在算法1和算法2中，函數AddRandomEdges將所需的邊從一個組件添加到另一個組件，而不生成新的子圖同構。這兩個組件也可以是同一個，這意味著添加一個組件。NEC樹在TurboISO [19]中用于探索候選區域以進行進一步匹配。它需要 $O(\left | V_P \right |^2)$ 時間，但可以顯著減少數據圖中的搜索空間。它記錄了模式的等價類和必要條件。當在兩個組件之間添加隨機邊時，我們確保兩個組件之間的邊不滿足NEC樹中的必要條件。與隨機生成和傳統的子圖同構搜索相比，這種數據結構和這種思想有助于我們生成更多的數據和搜索子同構。

C 數據集細節

C.1合成數據集的詳細信息

表4：兩個數據集的參數和約束

????????我們可以使用兩個圖形生成器生成盡可能多的示例。然而，我們限制了訓練、開發和測試實例的數量，以確定基于學習的模型是否可以推廣到新的未見實例。生成了不同尺度的模式圖和數據圖。表4中列出了兩個生成器和約束的參數。添加了兩個約束以簡化此任務。平均度約束 $\left ( \frac{N_e}{N_v} \leq 4\right )$ 用于保持圖的不那么密集，而次同構計數約束 $\left ( \left \{ c \in \mathbb{N} | c\leq 1024 \right \} \textup{ for\: small} , \left \{ c \in \mathbb{N} | c\leq 4096 \right \} \textup{ for\: large} \right )$ {確保了兩個數據集的難度不同。

????????我們使用8核(16線程)Intel E5-2620v4 CPU并行生成數據。圖8顯示了兩個數據集的計數分布。從圖中我們可以看到，這兩個數據集都遵循長尾分布。

圖8：兩個數據集的子圖同構計數分布

C.2 MUTAG數據集詳情

????????MUTAG數據集包含188個致突變化合物圖。我們將188個圖分為62個訓練圖、63個驗證圖和63個測試圖，使用附錄B中的模式生成器生成24個不同的模式，最終構建了4,512個圖-模式對（1,488個訓練對，1,512個驗證對和1,512個測試對）。詳細的圖案結構如圖9所示。

圖9：MUTAG數據集中的24種不同模式

D 更多的實現細節

????????在本節中，我們提供了更多的實現細節，而不是表示架構和DIAMNet模塊。

D.1 Filter Network

????????直覺上，并非圖中的所有頂點和邊都可以匹配某些子同構，因此我們只需添加一個FilterNet來調整圖編碼，如下所示：

$\overline{p} = \textup{MaxPool}(p),\:\:\;\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:(7) \\ \widehat{G} =GW_G^T,\:\:\:\:\:\:\:\:\;\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:\;\;\:\:(8) \\f_i = \sigma(W_F\left ( \widehat{G}_{i:} \odot \overline{p} \right )),\;\;\:\:\;\;\:\;\;\:\:\;\;\:\:\:\:(9) \\G_{i:} = f_i \odot G_{i:}\;\;\:\:\;\;\:\;\;\:\:\;\;\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(10)$

????????其中 $\widehat{G}$ 是模式空間中的圖形表示， $\sigma$ 是sigmoid函數， $f_j$ 是決定 $j^{th}$ 頂點或 $j^{th}$ 邊過濾的門， $W_G \in \mathbb{R} ^{d_p \times d_g}$ 和 $W_F \in \mathbb{R} ^{1 \times d_p}$ 是可訓練的。多虧了多熱編碼，我們可以簡單地使用Eq（7以累積圖案的標簽信息。在這個過濾層之后，只有圖形的相關部分將被傳遞到下一個表示層。

D.2 MemAttn

????????為了解決二次成本問題，我們將內存用于鍵和值，并在查詢和內存之間進行點積。我們將 $\widehat{G}$ 初始化為 $\widehat{G}^{(0)}$ ，并更新 $t$ 次。細節如下所示：

$\boldsymbol{M}^{(t)} = \textit{MemInit} (\widehat{P}),\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(11) \\ s_j^{(t)}= \textit{MultiHead} \left ( \widehat{\boldsymbol{g}}_{j}^{(t)}, \boldsymbol{M}^{(t)},\boldsymbol{M}^{(t)}\right )\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(12) \\z_j^{(t)} = \sigma(\boldsymbol{U}_P \widehat{\boldsymbol{g}}_{j}^{(t)} +\boldsymbol{V}_Ps_j^{(t)}),\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(13) \\ \overline{s}_j^{(t)} = z_j^{(t)} \odot \widehat{\boldsymbol{g}}_{j}^{(t)} +\left ( 1- z_j^{(t)} \right ) \odot s_j^{(t)},\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(14) \\\boldsymbol{\overline{M}}^{(t)} = \textit{MemInit} (\overline{S}^{(t)}),\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(15) \\ \widetilde{s}_j^{(t)}= \textit{MultiHead} \left ( \overline{s}_{j}^{(t)}, \boldsymbol{\overline{M}}^{(t)},\boldsymbol{\overline{M}}^{(t)}\right )\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(16) \\\widetilde{z}_j^{(t)} = \sigma(\boldsymbol{U}_S \overline{\boldsymbol{s}}_{j}^{(t)} +\boldsymbol{V}_S \widetilde{s}_j^{(t)}),\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(17) \\ \widehat{g}_j^{(t+1)} = \widetilde{z}_j^{(t)} \odot \overline{s}_{j}^{(t)} +\left ( 1-\widetilde{z}_j^{(t)} \right ) \odot \widetilde{s}_j^{(t)},\:\:\:\:\:\:\:\:\:\:\:(18)$

????????初始化內存的方法有很多，我們在附錄D.3中簡要討論。在實驗中，我們簡單地選擇通過均值池進行初始化。

D.3存儲器初始化

????????有很多方法可以初始化給定輸入 $\boldsymbol{L} = \left \{ \boldsymbol{l}_1,\cdots,\boldsymbol{l}_L \right \}$ 的存儲器 $\boldsymbol{M} = \left \{ \boldsymbol{m}_1,\cdots,\boldsymbol{m}_M \right \}$ 在實驗中，我們簡單地通過以下方式初始化 $\boldsymbol{m}_i$ :

$s = \left \lfloor \frac{L}{M} \right \rfloor, \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(19) \\k = L-(M-1)\cdot s,\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:(20) \\ \boldsymbol{m}_i = \textup{MeanPool}\left ( \left \{ \textbf{l}_{i\cdot s} ,\cdots,\textbf{l}_{i\cdot s+k-1} \right \} \right )\:\:\:\:\:\:\:\:\:\:\:\:\:\:(21)$

????????其中， $s$ 是步幅， $k$ 是內核大小。簡單地將填充的輸入與長度 $M \cdot \left \lfloor \frac{L}{M} \right \rfloor$ 分開也應該工作得很好。可以很容易地用最大池化和總和池化來取代均值池化。有趣的是，我們也可以為 $\left \{ \textbf{l}_{i\cdot s} ,\cdots,\textbf{l}_{i\cdot s+k-1} \right \}$ 使用自我注意力來獲得更好的記憶塊 $\boldsymbol{m}_i$ 。然而，自注意使得初始化不快于 $O(L^{1.5})$ 。進一步的工作是設計散列和選擇，以幫助內存更好地記憶全局和局部結構信息的頂點，如節點具有相同的頂點標簽存儲在同一個內存塊。