來源：PaperWeekly

1、論文介紹

子圖 GNN 能夠將圖建模成為子圖的集合。時至今日，對于子圖 GNN 結構的設計和其性質的理論分析方向仍有待探索。本文研究了子圖方法中最重要的部分——基于結點的子圖選擇策略，如 ego-network/node marketing/node deletion。本文將子圖表達能力的上界界定為 3-WL，并設計了新的子圖 GNN 模型，稱之為 SUN，在理論上統(tǒng)一了之前的子圖模型，并在多個數(shù)據(jù)集上取得了更優(yōu)越的表現(xiàn)。

2、動機

目前已有許多工作，旨在提升 GNN 的表達性。其中另辟蹊徑在子圖領域進行的研究也不在少數(shù)。這些方法通常是從原始輸入圖中提取出子圖集 (bags)，并在子圖集上進行聚合等一系列操作，目的是對原圖進行有效的表示。 

從原圖中挑選并提取子圖有許多策略，選擇不同的策略對模型的時間開銷和性能表現(xiàn)存在影響。

盡管子圖 GNN 擁有廣闊的發(fā)展前景，我們仍缺少對其系統(tǒng)理解與理論分析。首先，理論上子圖方法能夠嚴格超越 WL test，但其 expressive power 的上界仍未可知。其次，在實踐上，各種模型之間采取的信息傳遞和聚合策略是有差別的，是否存在對于信息傳遞規(guī)則的一個通用理解？在這兩方面之上，我們既需要對于各種模型表達能力上界進行合理的標定，又希望能夠在之后設計出更強大的子圖 GNN。 

基于以上，本文提出并解決了兩個問題：1）這些子圖 GNN 方法的表達能力上界在哪里；2）在子圖集上進行的等變信息傳遞層之間的內在聯(lián)系是什么。 

本文的貢獻主要有以下兩點：

1. 對在子圖集上進行操作的對稱性集合提出了新的分析；

2. 提出了 SUN，對之前基于結點的子圖 GNN 進行了合理的泛化。

3、方法

3.1 Subgraph GNNs

子圖 GNN 按如下公式計算圖 G 的表示：

其中，

 是從圖 G 生成子圖集的子圖選擇策略。 是對結點和子圖進行排列組合的 T 個等變層； 是具有不變性的池化函數(shù)。 是 MLP；不同的子圖 GNN 區(qū)別在于采取不同的  和 。

一個基于結點的子圖選擇策略表示為 ，輸入是一張圖 G 和一個結點 v。

3.2 基于結點的子圖選擇策略的symmetries

以往的工作對子圖集采取兩套排列組合方式：在結點上進行的  和在子圖集上進行的 。

本文觀察到，當采用基于結點的選擇策略時，子圖和結點之間存在一種對應關系，因此本文僅僅采用單個排列組合  同時應用于結點和子圖上：

3.3 SubGNNs的上界

在本節(jié)中，本文證明了子圖 GNN 的上界是 3-WL，原因是能被 3-IGN “inplement”：

3.4 A design space for subGNNs

3.5 SUN

4、實驗

人工數(shù)據(jù)集上的任務是對圖中子結構進行計數(shù)，SUN 在 4 個任務中的 3 個上表現(xiàn)都最好；真實數(shù)據(jù)集采用 ZINC-12k，用 MAE 進行衡量，SUN 取得了 SOTA 的結果。

本文測試了當采取訓練數(shù)據(jù)的一小部分時，模型能否仍有效，即模型的泛化能力如何。

5、總結

本文的工作對現(xiàn)有子圖 GNN 的工作進行了統(tǒng)一和拓展，并界定了這些方法的 expressive power 上界是 3-WL。通過對 expressive power 在 1 & 3-WL 之間的模型進行系統(tǒng)研究，提出了子圖 GNN 這一類模型的通用理論。在實驗部分，本文額外研究了這些模型的泛化能力，其中 SUN 表現(xiàn)最好。

論文標題：

Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries

論文鏈接：

http://arxiv.org/abs/2206.11140

代碼鏈接：

https://github.com/beabevi/SUN