圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力對其性能和應(yīng)用范圍有著重要的影響，是GNN研究的核心問題和發(fā)展方向。增強(qiáng)表達(dá)能力是擴(kuò)展GNN應(yīng)用范圍、提高性能的關(guān)鍵所在。

目前GNN的表達(dá)能力受特征表示和拓?fù)浣Y(jié)構(gòu)這兩個(gè)因素的影響，其中GNN在學(xué)習(xí)和保持圖拓?fù)浞矫娴娜毕菔窍拗票磉_(dá)的主要因素。因此，現(xiàn)有的對GNN表達(dá)能力的研究主要都是從圖特征增強(qiáng)、圖拓?fù)湓鰪?qiáng)和GNN架構(gòu)增強(qiáng)這三個(gè)方面進(jìn)行探索。

為了幫助同學(xué)們設(shè)計(jì)更有效的GNN模型，快速找到自己的論文idea，學(xué)姐這次整理了這3大類（包括8個(gè)細(xì)分小類）GNN性能提升方法，每個(gè)方法涉及到的算法模型、論文原文以及代碼都放上了，需要的同學(xué)看這里↓

掃碼添加小享，回復(fù)“GNN優(yōu)化”

免費(fèi)獲取全部算法模型+論文+源碼

圖特征增強(qiáng)

提取特征之間的依賴關(guān)系

1.AM-GCN

論文：AM-GCN: Adaptive Multi-channel Graph Convolutional

自適應(yīng)多通道圖卷積網(wǎng)絡(luò)

模型簡介：論文提出自適應(yīng)多通道圖卷積網(wǎng)絡(luò)AM-GCN，通過注意力機(jī)制自適應(yīng)學(xué)習(xí)不同源信息的權(quán)重，大幅提升圖卷積網(wǎng)絡(luò)整合節(jié)點(diǎn)特征和拓?fù)浣Y(jié)構(gòu)的能力。

2.CL-GNN

論文：A Collective Learning Framework to Boost GNN Expressiveness

提升GNN表達(dá)能力的集體學(xué)習(xí)框架

模型簡介：本文提出了集體學(xué)習(xí)框架CL-GNN，通過Monte Carlo采樣增強(qiáng)了現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力，從而提高了節(jié)點(diǎn)分類的準(zhǔn)確率。

增強(qiáng)使用

1.ACR-GNN

論文：The Expressive Power of Graph Neural Networks as a Query Language

圖神經(jīng)網(wǎng)絡(luò)作為查詢語言的表達(dá)能力

模型簡介：論文發(fā)現(xiàn)基礎(chǔ)的AC-GNNs僅能表達(dá)FOC2的保護(hù)片段，而添加讀出層的ACR-GNNs則可以表達(dá)完整的FOC2。實(shí)驗(yàn)驗(yàn)證了理論發(fā)現(xiàn)，ACR-GNNs可以學(xué)習(xí)FOC2中的查詢，而AC-GNNs則難以擬合。

圖拓?fù)湓鰪?qiáng)

添加額外的拓?fù)湫畔?/h1>

1.Twin-GNN

論文：Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification

用于圖分類的高表達(dá)能力圖神經(jīng)網(wǎng)絡(luò)

模型簡介：論文提出Twin Weisfeiler-Lehman測試和基于其的Twin-GNN，通過同時(shí)傳遞節(jié)點(diǎn)標(biāo)簽和標(biāo)識提升了GNN的表達(dá)能力，在圖分類任務(wù)上優(yōu)于基于消息傳遞的GNN。

2.ID-GNN

論文：Identity-aware Graph Neural Networks

身份識別圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文提出身份識別圖神經(jīng)網(wǎng)絡(luò)ID-GNN，通過在消息傳遞中感知節(jié)點(diǎn)身份，提高了相對1-WL測試的表達(dá)能力，可以解決現(xiàn)有GNN的局限。

3.CLIP

論文：COLORING GRAPH NEURAL NETWORKS FOR NODE DISAMBIGUATION

著色圖神經(jīng)網(wǎng)絡(luò)用于節(jié)點(diǎn)消歧

模型簡介：通過為節(jié)點(diǎn)著色來消除屬性歧義，文中提出的著色圖神經(jīng)網(wǎng)絡(luò)CLIP在理論和實(shí)驗(yàn)上都展示了比傳統(tǒng)消息傳播圖神經(jīng)網(wǎng)絡(luò)更強(qiáng)的表達(dá)能力。

4.RP-GNN

論文：Relational Pooling for Graph Representations

關(guān)系池化用于圖表示

模型簡介：本文提出的關(guān)系池化為圖神經(jīng)網(wǎng)絡(luò)提供了超越流行方法的最大表達(dá)能力，使模型獲得比最初同構(gòu)測試更強(qiáng)的區(qū)分圖結(jié)構(gòu)的能力。

5.RNI-GNN

論文：The Surprising Power of Graph Neural Networks with Random Node Initialization

隨機(jī)節(jié)點(diǎn)初始化圖神經(jīng)網(wǎng)絡(luò)的驚人能力

模型簡介：本文研究了隨機(jī)節(jié)點(diǎn)初始化對提高圖神經(jīng)網(wǎng)絡(luò)表達(dá)能力的作用，理論上證明了即使部分隨機(jī)初始化，這種圖神經(jīng)網(wǎng)絡(luò)也是通用的，第一個(gè)不依賴計(jì)算密集高階屬性的通用圖神經(jīng)網(wǎng)絡(luò)結(jié)果。

編碼微拓?fù)?/h1>

1.DE-GNN

論文：Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

為圖表示學(xué)習(xí)設(shè)計(jì)證明更強(qiáng)大的神經(jīng)網(wǎng)絡(luò)

模型簡介：本文提出距離編碼機(jī)制，可以充分捕獲節(jié)點(diǎn)集與整圖節(jié)點(diǎn)之間的距離信息，理論上證明其表達(dá)能力優(yōu)于1-WL測試，為圖神經(jīng)網(wǎng)絡(luò)表示任意節(jié)點(diǎn)集提供了更強(qiáng)的區(qū)分能力。

2.PGNN

論文：Position-aware Graph Neural Networks

位置感知圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文提出位置感知圖神經(jīng)網(wǎng)絡(luò)，通過采樣節(jié)點(diǎn)作為錨點(diǎn)并聚合目標(biāo)節(jié)點(diǎn)與錨點(diǎn)集的距離表示，來學(xué)習(xí)反映節(jié)點(diǎn)在圖中的相對位置的嵌入，增強(qiáng)模型對圖結(jié)構(gòu)的建模能力，在鏈接預(yù)測等任務(wù)上優(yōu)于現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)。

3.PEG

論文：EQUIVARIANT AND STABLE POSITIONAL ENCODING FOR MORE POWERFUL GRAPH NEURAL NETWORKS

等變與穩(wěn)定的位置編碼，為更強(qiáng)大的圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文提出了一類稱為PEG的圖神經(jīng)網(wǎng)絡(luò)層，通過分離更新節(jié)點(diǎn)原始特征和基于拉普拉斯特征映射等方法獲得的節(jié)點(diǎn)位置特征，既保證了表示對圖同構(gòu)變換等變，又使模型對小擾動穩(wěn)定，增強(qiáng)了模型的泛化能力。

4.SMP

論文：Building powerful and equivariant graph neural networks with structural message-passing

利用結(jié)構(gòu)化消息傳遞構(gòu)建強(qiáng)大的且等變的圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文提出了一種基于結(jié)構(gòu)化消息傳遞的強(qiáng)大且等變的圖神經(jīng)網(wǎng)絡(luò)框架，該框架可以更準(zhǔn)確預(yù)測圖的拓?fù)鋵傩?，并在ZINC數(shù)據(jù)集上的分子圖回歸任務(wù)上取得最優(yōu)效果。

5.GD-WL

論文：RETHINKING THE EXPRESSIVE POWER OF GNNS VIA GRAPH BICONNECTIVITY

通過圖雙連通性重新思考圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力

模型簡介：本文從圖的雙連通性出發(fā)，提出了一類新的表達(dá)能力指標(biāo)，發(fā)現(xiàn)當(dāng)前圖神經(jīng)網(wǎng)絡(luò)大多無法區(qū)分雙連通性，僅ESAN框架例外。然后提出GD-WL方法，理論證明其可以區(qū)分所有雙連通指標(biāo)，并給出了Transformer實(shí)現(xiàn)。

編碼全局拓?fù)?/h1>

1.Eigen-GNN

論文：Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs

Eigen-GNN: 一種圖結(jié)構(gòu)保留的GNN插件

模型簡介：本文提出了Eigen-GNN，一種可插入現(xiàn)有GNN的模塊，通過利用圖的拉普拉斯特征值和特征向量來編碼結(jié)構(gòu)信息，增強(qiáng)GNN保留圖結(jié)構(gòu)的能力。

編碼局部拓?fù)?/h1>

1.GSN

論文：Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

通過子圖同構(gòu)計(jì)數(shù)提高圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力

模型簡介：本文提出了基于子圖同構(gòu)計(jì)數(shù)的圖神經(jīng)網(wǎng)絡(luò)表示方法GSN，增強(qiáng)了GNN對圖結(jié)構(gòu)的建模能力。GSN保留了GNN的局部性和線性復(fù)雜度，但可以區(qū)分困難的圖同構(gòu)實(shí)例。在多個(gè)實(shí)驗(yàn)中，GSN取得了優(yōu)于當(dāng)前SOTA的效果。

2.GraphSNN

論文：A NEW PERSPECTIVE ON "HOW GRAPH NEURAL NET-WORKS GO BEYOND WEISFEILER-LEHMAN?

從新視角看“圖神經(jīng)網(wǎng)絡(luò)如何突破Weisfeiler-Lehman限制”

模型簡介：本文提出了一種新視角來設(shè)計(jì)表達(dá)能力強(qiáng)的圖神經(jīng)網(wǎng)絡(luò)，通過開發(fā)基于局部同構(gòu)的層次結(jié)構(gòu)，理論上證明了基于消息傳遞的圖神經(jīng)網(wǎng)絡(luò)如何設(shè)計(jì)才能超過Weisfeiler Lehman測試，并根據(jù)這一理論提出了一個(gè)新的圖神經(jīng)網(wǎng)絡(luò)模型GraphSNN。

3.GNN-AK

論文：FROM STARS TO SUBGRAPHS: UPLIFTING ANY GNN WITH LOCAL STRUCTURE AWARENESS

通過局部結(jié)構(gòu)意識提升任意GNN

模型簡介：本文提出框架GNN-AK，將消息傳遞圖神經(jīng)網(wǎng)絡(luò)中的星形聚合擴(kuò)展為子圖編碼，使其考慮局部結(jié)構(gòu)信息，理論上證明提升了表達(dá)能力，實(shí)驗(yàn)大幅提高了性能，提供了在表達(dá)能力與可拓展性間權(quán)衡的通用升級方法。

4.NGNN

論文：Nested Graph Neural Networks

嵌套圖神經(jīng)網(wǎng)絡(luò)

模型簡介：嵌套圖神經(jīng)網(wǎng)絡(luò)通過學(xué)習(xí)節(jié)點(diǎn)局部子圖表示而非子樹表示，理論上證明了比1-WL測試更強(qiáng)的表達(dá)能力，僅增加常數(shù)復(fù)雜度開銷，實(shí)驗(yàn)表明可泛化提升各基礎(chǔ)圖神經(jīng)網(wǎng)絡(luò)的性能。

5.MPSN

論文：Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks

Weisfeiler-Lehman 方法引入拓?fù)浣Y(jié)構(gòu)

模型簡介：本文將拓?fù)浣Y(jié)構(gòu)與圖神經(jīng)網(wǎng)絡(luò)結(jié)合，在簡單復(fù)形上定義消息傳遞以捕獲全局結(jié)構(gòu)，理論上證明其表達(dá)能力強(qiáng)于標(biāo)準(zhǔn)圖神經(jīng)網(wǎng)絡(luò)，實(shí)驗(yàn)也表明其優(yōu)于當(dāng)前最先進(jìn)的模型。

掃碼添加小享，回復(fù)“GNN優(yōu)化”

免費(fèi)獲取全部算法模型+論文+源碼

6.ESAN

論文：EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS

等變子圖聚合網(wǎng)絡(luò)

模型簡介： 本文提出了一種新的圖神經(jīng)網(wǎng)絡(luò)框架ESAN，通過提取圖的可區(qū)分子圖集合并用等變網(wǎng)絡(luò)進(jìn)行編碼，來提升表現(xiàn)力。

7.LRP-GNN

論文：Can Graph Neural Networks Count Substructures?

圖神經(jīng)網(wǎng)絡(luò)能統(tǒng)計(jì)子結(jié)構(gòu)嗎?

模型簡介：本文通過子圖計(jì)數(shù)的視角深入研究圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力，對流行模型給出理論正面和負(fù)面結(jié)果，并提出了基于子結(jié)構(gòu)計(jì)數(shù)的新模型。

8.k-GNN

論文：Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

Weisfeiler-Leman 方法的神經(jīng)網(wǎng)絡(luò)延伸：高階圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文從理論角度研究圖神經(jīng)網(wǎng)絡(luò)，發(fā)現(xiàn)其表達(dá)能力等價(jià)于1-WL測試，因此存在相同的局限性。為此，提出了k-GNN模型，可以編碼多尺度的高階圖結(jié)構(gòu)信息。

9.K-hop GNN

論文：k-hop graph neural networks

多跳圖神經(jīng)網(wǎng)絡(luò)

模型簡介：標(biāo)準(zhǔn)GNN表達(dá)能力等價(jià)于WL測試，不能識別基本圖屬性如連通性和無三角形。本文提出的k-hop GNN通過聚合k跳范圍內(nèi)鄰居信息來更新節(jié)點(diǎn)表示，可以識別這些基本圖屬性。

10.KP-GNN

論文：How Powerful are K-hop Message Passing Graph Neural Networks

K跳消息傳遞圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力

模型簡介：本文首次理論分析了 K-hop 消息傳遞的表達(dá)能力，指出它優(yōu)于 1-WL 測試但仍有局限，并提出結(jié)合周邊子圖信息的 KP-GNN 框架來進(jìn)一步增強(qiáng)表達(dá)能力。

GNN架構(gòu)增強(qiáng)

提高聚集功能

1.GINN

論文：HOW POWERFUL ARE GRAPH NEURAL NETWORKS?

圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力有多強(qiáng)?

模型簡介：本文提供GNN表達(dá)能力分析的理論框架，指出流行GNN無法區(qū)分某些簡單圖，并提出一個(gè)與WL測試一樣強(qiáng)大且最具表達(dá)能力的GNN架構(gòu)，實(shí)證其SOTA的性能。

2.modular-GCN

論文：Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology

理解圖神經(jīng)網(wǎng)絡(luò)在學(xué)習(xí)圖拓?fù)浣Y(jié)構(gòu)中的表達(dá)能力

模型簡介：從圖矩的角度分析發(fā)現(xiàn)GCN學(xué)習(xí)圖拓?fù)涞哪芰τ邢?，理論分析后提出模塊化設(shè)計(jì)和殘差連接可以改進(jìn)GCN，使其可以區(qū)分小圖，深度比寬度更重要，組合不同傳播規(guī)則的模塊對提升表達(dá)能力關(guān)鍵。

3.diagonal-GNN

論文：Graph Neural Networks Are More Powerful Than we Think

圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力比我們想象的更強(qiáng)大

模型簡介：本文從線性代數(shù)的角度分析了GNN的表達(dá)能力，證明了GNN可以區(qū)分特征值不同的圖，設(shè)計(jì)了優(yōu)于WL測試的GNN架構(gòu)，實(shí)驗(yàn)驗(yàn)證了理論結(jié)論和架構(gòu)的有效性。

4.GNN-LF/HF

論文：Interpreting and Unifying Graph Neural Networks with An Optimization Framework

使用優(yōu)化框架解釋并統(tǒng)一圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文建立不同GNN傳播機(jī)制與統(tǒng)一優(yōu)化問題的聯(lián)系，在該框架下發(fā)現(xiàn)現(xiàn)有GNN使用樸素圖核，并提出考慮可調(diào)節(jié)圖核的目標(biāo)函數(shù)，證明提出模型收斂性及表達(dá)能力，實(shí)驗(yàn)表明還可以減輕過度平滑。

5.Geom-GCN

論文：GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS

幾何圖卷積網(wǎng)絡(luò)

模型簡介：本文從網(wǎng)絡(luò)幾何角度提出新的圖卷積網(wǎng)絡(luò)聚合方案，通過結(jié)構(gòu)化鄰域和雙級聚合克服了MPNN聚合器的兩個(gè)限制，在多個(gè)圖數(shù)據(jù)集上取得最先進(jìn)性能。

6.PG-GNN

論文：Going Deeper into Permutation-Sensitive Graph Neural Networks

深入研究排列敏感的圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文通過排列群提出排列敏感的圖神經(jīng)網(wǎng)絡(luò)聚合機(jī)制，證明嚴(yán)格優(yōu)于2-WL測試且不弱于3-WL測試，在多個(gè)數(shù)據(jù)集上驗(yàn)證了優(yōu)越性。

采用等變結(jié)構(gòu)

1.k-IGN

論文：INVARIANT AND EQUIVARIANT GRAPH NETWORKS

不變和笛卡爾圖網(wǎng)絡(luò)

模型簡介： 本文給出了(超)圖數(shù)據(jù)所有排列不變和笛卡爾線性層的特征化，展示了它們的維度分別是貝爾數(shù)，并證明了應(yīng)用于不同大小圖上的有效性。

2.PPGN

論文：Provably Powerful Graph Networks

可證明強(qiáng)大的圖網(wǎng)絡(luò)

模型簡介：本文證明了簡單交替使用多層感知機(jī)和矩陣乘法的圖網(wǎng)絡(luò)模型達(dá)到3-WL表達(dá)能力，在多個(gè)任務(wù)上驗(yàn)證了其最優(yōu)性。

3.k-FGNN

論文：The expressive power of kth-order invariant graph networks

k階不變圖網(wǎng)絡(luò)的表達(dá)能力

模型簡介：本文證明了k階不變圖網(wǎng)絡(luò)的表達(dá)能力被k維Weisfeiler-Leman圖同構(gòu)測試所限制，即兩者在區(qū)分圖上的能力相等。

4.Ring-GNN

論文：On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs

關(guān)于圖同構(gòu)測試和GNN函數(shù)逼近等價(jià)性的研究

模型簡介：本文證明了圖神經(jīng)網(wǎng)絡(luò)逼近排列不變函數(shù)和作為圖同構(gòu)測試的能力等價(jià)，并基于σ代數(shù)提出了統(tǒng)一框架來比較不同GNN的表達(dá)能力。

5.SUN

論文：Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries

通過重新思考對稱性來理解和擴(kuò)展子圖圖神經(jīng)網(wǎng)絡(luò)

模型簡介：本文通過重新思考子圖神經(jīng)網(wǎng)絡(luò)的對稱性來理解其表達(dá)能力上界并提出更一般的消息傳遞層，設(shè)計(jì)了一個(gè)新的子圖神經(jīng)網(wǎng)絡(luò)模型SUN來統(tǒng)一并改進(jìn)之前的結(jié)構(gòu)。

6.GNNML

論文：Breaking the Limits of Message Passing Graph Neural Networks

突破消息傳遞圖神經(jīng)網(wǎng)絡(luò)的限制

模型簡介：本文通過設(shè)計(jì)頻譜域?yàn)V波器和非局部更新，提出了一個(gè)復(fù)雜度線性但表達(dá)能力超過1-WL的消息傳遞圖神經(jīng)網(wǎng)絡(luò)框架。

7.k-MPNN

論文：EXPRESSIVENESS AND APPROXIMATION PROPERTIES OF GRAPH NEURAL NETWORKS

圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力和逼近性質(zhì)

模型簡介： 本文提出使用過程張量語言描述GNN計(jì)算，通過分析張量表達(dá)式中的索引和嵌套求和深度，可以自然地給出GNN表達(dá)能力關(guān)于WL測試的上下界。

掃碼添加小享，回復(fù)“GNN優(yōu)化”

免費(fèi)獲取全部算法模型+論文+源碼