機器之心編輯部
圖神經網路 (GNN) 與動態規劃 (DP)之間的關係應該如何描述？DeepMind 的研究者推匯出了一個通用的積分變換圖，證明 GNN 和 DP 之間存在著錯綜複雜的聯繫，遠遠超出對個別演算法如 Bellman-Ford 的最初觀察。
近年來，基於圖神經網路 (GNN) 的神經演算法推理的進步得益於演算法式對齊（algorithmic alignment）概念的提出。從廣義上講，如果神經網路的各個元件與目標演算法很好地對齊，那麼神經網路將更好地學習執行推理任務（就樣本複雜度而言）。具體來說，GNN 被認為與動態規劃 (DP) 一致，而後者是一種表達多項式時間演算法的通用問題解決策略。然而，這種對齊方式是否真正得到了證明和理論上的量化？
來自 DeepMind 的研究者使用範疇論和抽象代數的方法表明，GNN 和 DP 之間存在著錯綜複雜的聯繫，遠遠超出了 Bellman-Ford 等單個演算法的最初觀察結果。得知這種聯繫後，很容易驗證文獻中一些之前的發現，DeepMind 希望它能成為構建更強大演算法式對齊 GNN 的基礎。
論文地址：https://arxiv.org/pdf/2203.15544.pdf
總結而言，該研究描述了使用範疇論和抽象代數來顯式地擴展 GNN-DP 連接，這在以前主要是在特定的例子上才能使用。該研究推匯出了一個通用的積分變換圖（基於標準的範疇概念，如拉回、推前和交換半群），並討論了為什麼它足夠通用，可以同時支持 GNN 和 DP 計算。有了這個圖，我們就可以立即將之前的大量工作統一起來，簡單地在積分變換中操作一個箭頭。
圖神經網路是動態規劃器
GNN 與 DP 連接的難點
在神經網路和 DP 之間建立嚴格的對應關係是比較困難的，因為它們的計算差異巨大。神經網路是基於實數線性代數構建而成，而 DP 通常是尋徑（path-finding）問題的一種泛化，它通常發生在 (N∪{∞}，min， +) 這樣的對象上，在數學中，這些對象通常被歸為歐幾里德空間的退化。GNN 與 DP 不能直接用簡單的方程式進行連接。
然而，如果我們定義一個任意的潛在空間 R 並做出儘可能少的假設，我們可以觀察到，對於 GNN 和 DP，我們關心的許多行為都是通過查看函數 S → R 產生的，其中 S 是一個有限集。在 GNN 下，R 可以看作是一組實值向量；在 DP 下，R 可以看作是熱帶數（tropical numbers）。所以 DeepMind 的主要研究對象是有限集類別以及 R 值的量化。這裡的類別是指對象集合（所有有限集）以及可組合箭頭（有限集之間的函數）的概念。
為了繪製 GNN-DP 連接，首先需要設計一個抽象對象，該對象可以捕獲 GNN 的訊息傳遞 / 聚合階段（等式 1）和 DP 的評分 / 重組階段（等式 2）。
DeepMind 將通過組合輸入特徵的變換來構建積分變換，這種方式將最小程度地依賴於 R 的特定選擇。在此過程中，DeepMind 構建了一個計算圖，該圖將適用於 GNN 和 DP(以及它們自己選擇的 R)，這種方式使得該研究將重點放在這些圖的元件儘可能對齊上。
積分變換、拉回和前推
積分變換的一般情況是稱為 span 的圖，如下所示：
這裡 V、E、W 是任意有限集，s、t 是任意函數。請注意，當 W = V 時，這正是 (V, E) 有向多重圖結構所需的資料，其中 s(e)解釋為邊的源，而 t(e)則是一條邊的目標。
這裡需要描述兩個操作，一個是沿著 s 的拉回（ pullback ） s^* 和一個沿著 t 的前推（pushforward） t_∗ 。對定義在 V 上的資料執行拉回的結果就是定義在 E 上的資料。然後前推應該獲取 E 上定義的資料並給出 W 上定義的資料，儘管我們會看到它實際上給出了一個需要聚合的資料包。方便的是，這個過程自然會與 GNN 的聚合步驟以及 DP 的重組步驟保持一致。
資料包含函數 f : V → R，這使得定義拉回變得簡單：s ^∗ f := f ◦ s （將邊對映到它的發送節點，然後在 f 中查找特徵 ）。
然而，前推是有問題的，因為 t 在使用函陣列合時面臨錯誤的方向。為了得到一個指向正確的箭頭，需要原像（ preimage ） t^-1 : W → P(E)，它取 E 的冪集的值。原像定義為 t^-1 (w) = {e | t(e) = w}。
完成轉換所缺少的只是一個聚合器，
。正如我們將在下一節中看到的，指定一個表現良好的聚合器與在 R 上施加一個可交換的么半群結構相同。
積分變換的四個箭頭
如前所述，有向圖 G = (V, E)等價於 span：其中 s 和 t 分別為每條邊的發送節點和接收節點。
從一些輸入特徵 f : V → R 開始，現在可以使用前面描述的所有對象來描述 f 的積分變換。最初，該研究關注重點是沿邊 e ∈ E 發送的訊息僅取決於發送者而不是接收者節點的情況。
該研究首先定義一個核變換 k：[E, R] → [E, R]，其在邊緣特徵上執行一些計算，例如在 Bellman-Ford 的情況下，將發送者距離 d_s(e)（之前通過 s^∗ 拉回邊緣）添加到邊緣權重 w_s(e)→t(e)。這裡 DeepMind 使用 [E, R] 作為函數集 E → R 的簡寫符號。使用核，我們可以完成下圖：
這四個箭頭構成了整體變換：從節點特徵開始，在邊緣上執行計算，最後在接收器中聚合邊緣訊息。在此過程中，DeepMind 更新了初始節點特徵（它們是 [V, R] 的元素）。
s^∗ 是先前定義的拉回箭頭，如前所述，DeepMind 使用源函數預先組合節點特徵。也就是說，(s^*f)(v) := f(s(v))。然後，將核應用於生成的邊緣特徵，將發送者的特徵與任何提供的邊緣特徵（例如邊緣權重）集成。
在應用核之後，將會得到邊緣訊息 m : E → R 作為結果。現在需要將這些訊息發送到接收節點，DeepMind 為此使用了前推。如前所述，他們定義
，並將其解釋為
中的形式和。 直觀地說，(t_∗m)(v) 是 v 處的傳入值包。
最後，DeepMind 對每個接收器逐點應用先前定義的聚合器
來計算每個節點的更新特徵。
上述設計的積分變換既能描述 GNN(公式 1)又能描述 DP(公式 2)，這使得 GNN 架構在演算法上與目標 DP 演算法對齊。也許最清楚的是最後一個箭頭，聚合器 (
)。如果我們讓 GNN 選擇的聚合函數與目標演算法使用的函數匹配，這應該會立即提高樣本複雜性和泛化能力。事實上，這與演算法推理中最早的研究路線之一非常吻合：將 GNN 與問題一致的聚合器部署。在組織現有研究和提出未來工作時，任何以這種方式分析 GNN 和 DP 的投入都可以提供豐厚的回報。
更多內容請參考論文原文。
