NeurIPS 2022 | 利用子圖和結(jié)點(diǎn)的對(duì)稱性提升子圖GNN

來(lái)源：PaperWeekly

1、論文介紹

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

2、動(dòng)機(jī)

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

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

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

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

本文的貢獻(xiàn)主要有以下兩點(diǎn)：

1. 對(duì)在子圖集上進(jìn)行操作的對(duì)稱性集合提出了新的分析；

2. 提出了 SUN，對(duì)之前基于結(jié)點(diǎn)的子圖 GNN 進(jìn)行了合理的泛化。

3、方法

3.1 Subgraph GNNs

子圖 GNN 按如下公式計(jì)算圖 G 的表示：

其中，

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

一個(gè)基于結(jié)點(diǎn)的子圖選擇策略表示為 ，輸入是一張圖 G 和一個(gè)結(jié)點(diǎn) v。

3.2 基于結(jié)點(diǎn)的子圖選擇策略的symmetries

以往的工作對(duì)子圖集采取兩套排列組合方式：在結(jié)點(diǎn)上進(jìn)行的  和在子圖集上進(jìn)行的 。

本文觀察到，當(dāng)采用基于結(jié)點(diǎn)的選擇策略時(shí)，子圖和結(jié)點(diǎn)之間存在一種對(duì)應(yīng)關(guān)系，因此本文僅僅采用單個(gè)排列組合  同時(shí)應(yīng)用于結(jié)點(diǎn)和子圖上：

3.3 SubGNNs的上界

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

3.4 A design space for subGNNs

3.5 SUN

4、實(shí)驗(yàn)

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

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

5、總結(jié)

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

論文標(biāo)題：

Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries

論文鏈接：

http://arxiv.org/abs/2206.11140

代碼鏈接：

https://github.com/beabevi/SUN