2W字長(cháng)文 | 漫談工業(yè)界圖神經(jīng)網(wǎng)絡(luò )推薦系統（1）

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

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

鏈接：

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

1. GNN介紹

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

非歐式數據

1.1 Common GNN

常用GNN模型及其貢獻

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

濾波器是全局的。

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

參數的量級是O(n)，與結點(diǎn)數量正相關(guān)，難以擴展到大圖。

特征分解的復雜度比較高。

Spectral CNN

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

濾波器是局部的，對應著(zhù)0-K階鄰居。

參數量的量級是O(K)。

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

ChebNet

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

GCN

SGC[4]：解耦了消息傳遞和特征變換， [公式] 部分可以預計算，簡(jiǎn)化后仍然可以在大多數數據集上取得和GCN相當的結果。

SGC

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

GAT

GraphSage[5]

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

GraphSage

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

Node-Wise Sampling

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

PPNP

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

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

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

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

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

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

HAN

1.2 Deeper GNN

1.2.1 問(wèn)題背景

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

GCN無(wú)法加深

1.2.2 理論分析

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

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

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

1.2.3 個(gè)人吐槽

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

1.2.4 加深意義

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

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

1.2.5 代表工作

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

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

JKNet

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

PPNP

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

GCNII

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

DAGNN