圖神經(jīng)網(wǎng)絡(luò)是近年來(lái)很火的一個(gè)研究方向，在生物化學(xué)，推薦系統(tǒng)，自然語(yǔ)言處理等領(lǐng)域都得到了廣泛應(yīng)用。其中圖神經(jīng)網(wǎng)絡(luò)在推薦系統(tǒng)的應(yīng)用方面，已有幾篇綜述[1][2][3]做過(guò)詳細(xì)的歸納總結(jié)。但是讓人感到美中不足的是，綜述中總結(jié)的多是學(xué)術(shù)型工作，偏向于GNN模型上的微調(diào)，部分工作其實(shí)就是將上游的SGC[4]，GrapSage[5]，JKNet[6]等模型在幾個(gè)祖?zhèn)魍婢邤?shù)據(jù)集上刷一下結(jié)果講一個(gè)故事，很少關(guān)心模型的擴(kuò)展性，也很少關(guān)心圖的構(gòu)建，特征處理，線上打分等不可或缺的環(huán)節(jié)。

因此本文選取了一些近幾年阿里，騰訊，京東，華為等企業(yè)在KDD，SIGIR，CIKM等會(huì)議發(fā)表的文章，這些工作的實(shí)驗(yàn)至少是在真實(shí)業(yè)務(wù)場(chǎng)景的大規(guī)模數(shù)據(jù)集（千萬(wàn)級(jí)或億級(jí)）上進(jìn)行的，部分工作也成功在線上AB實(shí)驗(yàn)中取得了一些效果。全文分為三部分，第一部分簡(jiǎn)單介紹涉及較多的幾個(gè)GNN研究方向，包括Deeper GNN（GNN加深），Scalable GNN（大圖訓(xùn)練），Heterogeneous GNN（異構(gòu)GNN）；第二部分從幾個(gè)不同的角度總結(jié)選取的文章，包括應(yīng)用階段，圖的構(gòu)建，特征使用，采樣方法，模型結(jié)構(gòu)；第三部分會(huì)逐篇介紹這些工作的重點(diǎn)內(nèi)容。

鏈接：

https://zhuanlan.zhihu.com/p/423342532

1. GNN介紹

不同于傳統(tǒng)的MLP，CNN，RNN等模型，GNN可以建模鄰居順序與數(shù)量不定的非歐式數(shù)據(jù)，常被用來(lái)處理結(jié)點(diǎn)分類(lèi)，鏈接預(yù)測(cè)，圖分類(lèi)等任務(wù)。可以從兩個(gè)角度理解GNN，譜圖卷積與消息傳遞，今年我們?cè)贗CML的工作則是從迭代算法求解目標(biāo)函數(shù)的角度解釋GNN[7]，同時(shí)在該理論框架內(nèi)還能解釋并解決過(guò)平滑，邊的不確定性等問(wèn)題。針對(duì)不同類(lèi)型的任務(wù)，不同類(lèi)型的圖數(shù)據(jù)（異質(zhì)圖，動(dòng)態(tài)圖，異構(gòu)圖）等，存在許多特定的GNN模型，此外，還有圖的池化，圖預(yù)訓(xùn)練，圖自監(jiān)督等方向，相關(guān)的內(nèi)容可以參考綜述[8]。第一小節(jié)會(huì)簡(jiǎn)單介紹一些基礎(chǔ)通用且有代表性的GNN模型，后三小節(jié)分別介紹Deeper GNN，Scalable GNN和Heterogeneous GNN三個(gè)方向，這些都是在將圖神經(jīng)網(wǎng)絡(luò)應(yīng)用到推薦系統(tǒng)時(shí)經(jīng)常涉及的知識(shí)。最后一節(jié)談?wù)剛€(gè)人對(duì)圖神經(jīng)網(wǎng)絡(luò)的優(yōu)勢(shì)的理解。

非歐式數(shù)據(jù)

1.1 Common GNN

常用GNN模型及其貢獻(xiàn)

Spectral CNN[9]：利用拉普拉斯矩陣定義了圖上的卷積算子，其特點(diǎn)如下：

濾波器是全局的。

圖上的細(xì)微擾動(dòng)會(huì)導(dǎo)致特征基的變化。

參數(shù)的量級(jí)是O(n)，與結(jié)點(diǎn)數(shù)量正相關(guān)，難以擴(kuò)展到大圖。

特征分解的復(fù)雜度比較高。

Spectral CNN

ChebNet[10]：利用切比雪夫多項(xiàng)式近似，降低了計(jì)算量和參數(shù)量，其特點(diǎn)如下：

濾波器是局部的，對(duì)應(yīng)著0-K階鄰居。

參數(shù)量的量級(jí)是O(K)。

不需要進(jìn)行特征分解。

ChebNet

GCN[11]：進(jìn)一步簡(jiǎn)化了ChebNet，將譜圖卷積與消息傳遞聯(lián)系起來(lái)，其層級(jí)結(jié)構(gòu)便于和深度學(xué)習(xí)結(jié)合。

GCN

SGC[4]：解耦了消息傳遞和特征變換， [公式] 部分可以預(yù)計(jì)算，簡(jiǎn)化后仍然可以在大多數(shù)數(shù)據(jù)集上取得和GCN相當(dāng)?shù)慕Y(jié)果。

SGC

GAT[12]：將注意力機(jī)制引入GCN，建模了鄰居結(jié)點(diǎn)的重要性差異，增強(qiáng)了模型的表達(dá)能力。

GAT

GraphSage[5]

一方面，將消息傳遞框架范式化，分為Aggregate（聚合鄰居）和Concat（融合自身）兩個(gè)步驟。

GraphSage

另一方面，提出了一種簡(jiǎn)單有效的鄰居采樣方法，可以在大圖上進(jìn)行Mini-Batch訓(xùn)練，并且當(dāng)有新的結(jié)點(diǎn)加入時(shí)，不需要在全圖上聚合鄰居，也不需要重新訓(xùn)練模型，可以用訓(xùn)練好的模型直接推斷。

Node-Wise Sampling

PPNP[13]：同樣采用消息傳遞和特征變換分離的結(jié)構(gòu)，并基于個(gè)性化PageRank改進(jìn)消息傳遞，使模型可以平衡局部和全局信息。

PPNP

RGCN[14]：對(duì)于不同類(lèi)型的邊對(duì)應(yīng)的鄰居結(jié)點(diǎn)采用不同的參數(shù)矩陣從而建模邊的異構(gòu)性。當(dāng)邊的類(lèi)型很多時(shí)，參數(shù)也會(huì)變得很多，容易造成過(guò)擬合，并且不易訓(xùn)練，需要對(duì)參數(shù)進(jìn)行規(guī)約，使用了一下兩種方式：

Bias decomposition（定義一組基向量）不僅可以減少參數(shù)量，同時(shí)對(duì)于那些樣本較少的邊也能得到充分學(xué)習(xí)（參數(shù)共享）。

Block-diagnoal decomposition只能減少參數(shù)量，實(shí)驗(yàn)下來(lái)效果也不如Bias decomposition。

HAN[15]：將GAT擴(kuò)展到了異構(gòu)圖上，不僅考慮了不同鄰居結(jié)點(diǎn)的重要性差異，也考慮了不同語(yǔ)義的meta-path的重要性差異。

對(duì)于鄰居結(jié)點(diǎn)的重要性，例如，考慮meta-path：Paper-Author-Paper以及結(jié)點(diǎn)分類(lèi)任務(wù)，Paper A、C是數(shù)據(jù)庫(kù)算法論文，Paper B是圖神經(jīng)網(wǎng)絡(luò)論文，它們都是Author A的發(fā)表的文章，即PaperB、C都是Paper A的鄰居，但是在聚合時(shí)顯然Paper C與Paper A更相關(guān)，需要給與更大的權(quán)重。

對(duì)于meta-path的重要性，例如，考慮meta-path：Paper-Author-Paper以及Paper-Institution-Paper，通常同一個(gè)作者發(fā)表的文章，比同一個(gè)機(jī)構(gòu)產(chǎn)出的文章更相關(guān)。

HAN

1.2 Deeper GNN

1.2.1 問(wèn)題背景

在GCN的實(shí)驗(yàn)中發(fā)現(xiàn)[11]，一般2-3層的GCN可以取得最好的性能，繼續(xù)增加層數(shù)GCN的性能會(huì)開(kāi)始下降，達(dá)到8層以上會(huì)發(fā)生大幅度的下降。

GCN無(wú)法加深

1.2.2 理論分析

研究者證明了，隨著SGC（不考慮層間的非線性）層數(shù)的加深，所有結(jié)點(diǎn)會(huì)收斂到同一個(gè)表征（簡(jiǎn)單的線性代數(shù)知識(shí)可證）[16]。直觀上看，一個(gè)K層的SGC相當(dāng)于聚合了K-Hop的鄰居特征，當(dāng)K大于或等于圖的直徑時(shí)，每個(gè)結(jié)點(diǎn)都聚合了整張圖上所有結(jié)點(diǎn)的特征，從而每個(gè)結(jié)點(diǎn)都會(huì)收斂到同一個(gè)表征，結(jié)點(diǎn)之間自然會(huì)變得難以分辨。該現(xiàn)象被稱(chēng)為過(guò)平滑問(wèn)題。

也有人證明了，隨著GCN（考慮層間的非線性）層數(shù)的加深，所有結(jié)點(diǎn)的表征會(huì)收斂到同一個(gè)子空間[17]。

也有工作表示，消息傳遞和特征變換的耦合才是阻礙GCN加深的主要原因，不過(guò)并沒(méi)有從理論上證明只是通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證[18]。

1.2.3 個(gè)人吐槽

實(shí)際上不考慮層之間的非線性時(shí)，不斷加深SGC的層數(shù)甚至達(dá)到80層，只要給予模型更多的Epoch訓(xùn)練，整體上最終結(jié)果并不會(huì)有什么下降，這與很多論文里報(bào)告的SGC加深到10層以上效果驟降根本不符合。隨著層數(shù)的增加，所有結(jié)點(diǎn)確實(shí)會(huì)收斂到同一個(gè)表征，然而這需要非常深，只要計(jì)算機(jī)底層表示的精度能夠區(qū)分結(jié)點(diǎn)的差異，SGC的效果就不會(huì)有什么下降，無(wú)非是模型需要更多Epoch訓(xùn)練收斂。感興趣的同學(xué)可以實(shí)驗(yàn)驗(yàn)證一下。

1.2.4 加深意義

既然2-3層的效果最好，為什么還非要加深呢？這個(gè)問(wèn)題不少工作都不太關(guān)心，它們的實(shí)驗(yàn)結(jié)果也很一般，只是緩解了加深過(guò)程的下降，并沒(méi)有帶來(lái)什么額外的收益。一種說(shuō)法是，加深可以增強(qiáng)模型的表達(dá)能力（真是個(gè)萬(wàn)能理由），就像CNN那樣通過(guò)加深提升效果。比較靠譜的兩種說(shuō)法是，一是加深可以學(xué)習(xí)更高階的鄰居信息，這也是不少GNN4Rec工作提到的，高階信息蘊(yùn)含了多跳的關(guān)聯(lián)。JKNet中細(xì)致分析了中心結(jié)點(diǎn)和邊緣結(jié)點(diǎn)的情況，如下圖所示，邊緣結(jié)點(diǎn)的鄰居非常稀疏，需要加深獲取更大范圍的鄰居信息。二是對(duì)于半監(jiān)督結(jié)點(diǎn)分類(lèi)任務(wù)來(lái)說(shuō)，通過(guò)加深GCN建立長(zhǎng)距離的依賴(lài)，可以將帶標(biāo)簽結(jié)點(diǎn)的Label信息傳播給更多結(jié)點(diǎn)。

不同位置結(jié)點(diǎn)對(duì)鄰居范圍的要求

1.2.5 代表工作

Deeper GNN的許多工作，只是緩解了加深的性能下降，并沒(méi)有通過(guò)加深帶來(lái)正向收益。以下是幾個(gè)確實(shí)可以通過(guò)加深提升模型效果的工作。整體上看，比較有效的方法都是在以不同的方式組合不同范圍的鄰居信息，類(lèi)似于Inception組合不同的感受野。PPNP[13]相當(dāng)于引入了先驗(yàn)“近距離的鄰居更重要，并且鄰居的重要性隨距離指數(shù)衰減”，DAGNN[19]則是通過(guò)不同Hop的聚合結(jié)果去學(xué)習(xí)潛在的重要性分布。

JKNet[6]：GCN的第K層包含了K-Hop范圍的鄰居信息，只使用最后一層的輸出存在過(guò)平滑問(wèn)題，因此JKNet保留了每一層的輸出結(jié)果，最后綜合融合不同范圍的鄰居信息。

JKNet

PPNP[13]：采用消息傳遞和特征變換分離的結(jié)構(gòu)，并基于個(gè)性化PageRank改進(jìn)消息傳遞，使模型可以平衡局部和全局信息。

PPNP

GCNII[20]：除了使用個(gè)性化PageRank改進(jìn)消息傳遞，還引入了Residual Connections保持恒等映射的能力。

GCNII

DAGNN[19]：自適應(yīng)地學(xué)習(xí)不同范圍的鄰居信息的重要性。

DAGNN