1.3 Scalable GNN

1.3.1 問(wèn)題背景

一方面，GCN在設(shè)計(jì)之初其卷積操作是在全圖上進(jìn)行的，在每一層對(duì)于所有結(jié)點(diǎn)聚合1階鄰居并融入自身表征，這樣第K層的輸出表征就包含了K階鄰居的信息。另一方面，圖數(shù)據(jù)不同于其他數(shù)據(jù)集，結(jié)點(diǎn)之間存在邊這種關(guān)聯(lián)，無(wú)法直接通過(guò)隨機(jī)采樣進(jìn)行Mini-Batch訓(xùn)練。因此GNN的許多模型無(wú)法直接擴(kuò)展到大圖上，然而真實(shí)業(yè)務(wù)場(chǎng)景中的圖數(shù)據(jù)往往都是億級(jí)別的。該章節(jié)介紹一些大圖上訓(xùn)練GNN的方法，主要分為基于采樣的方法和基于預(yù)處理的方法。

1.3.2 基于采樣的方法

基于采樣的方法可以分為三小類，Node-Wise Sampling，Layer-Wise Sampling和Subgraph-Wise Sampling。其中Node-Wise Sampling是一種比較通用有效的方法，在GNN4Rec方向中應(yīng)用得最多；Layer-Wise Sampling其實(shí)就是一種弱化地Node-Wise Sampling，效果不咋地意義不大；Subgraph-Wise Sampling比較受限于場(chǎng)景，這一點(diǎn)在后面總結(jié)GNN4Rec工作時(shí)會(huì)提到。

Node-Wise Sampling[5]：由GraphSage首次提出，首先隨機(jī)采樣一個(gè)batch的root結(jié)點(diǎn)，接著從root結(jié)點(diǎn)出發(fā)迭代地采樣1-K階鄰居，在訓(xùn)練時(shí)則迭代地聚合K-1階鄰居，最終得到每個(gè)root結(jié)點(diǎn)融合了K-Hop鄰居信息的表征。這種方法主要存在以下幾個(gè)缺點(diǎn)：

隨著層數(shù)增加，采樣到的鄰居數(shù)量指數(shù)增長(zhǎng)

結(jié)點(diǎn)的利用率低（許多結(jié)點(diǎn)的表征存在大量重復(fù)計(jì)算）

沒(méi)有考慮采樣造成的偏差和方差

Node-Wise Sampling

Layer-Wise Sampling[21]：由FastGCN首次提出，對(duì)于每一層都采樣固定數(shù)量的結(jié)點(diǎn)，最終采樣的結(jié)點(diǎn)數(shù)量與層數(shù)成線性關(guān)系；同時(shí)分析了采樣帶來(lái)的偏差與方差（做了大量簡(jiǎn)化），確保采樣方法盡可能無(wú)偏有效。但是，該方法采樣到的結(jié)點(diǎn)連接非常稀疏，不利于進(jìn)行有效地消息傳遞，實(shí)際上實(shí)驗(yàn)效果也確實(shí)比較差。

Layer-Wise Sampling

Subgraph-Wise Sampling[22]：由ClusterGNN首次提出，首先用圖劃分算法（Metis等）將原圖劃分為一些子圖，這些子圖具有“高內(nèi)聚，低耦合”的特點(diǎn)，接著在每個(gè)Batch隨機(jī)采樣一個(gè)子圖（或多個(gè)子圖合并為更大的子圖從而降低方差），在該子圖上訓(xùn)練完全的GCN。GraphSAINT進(jìn)一步考慮了子圖采樣的偏差，通過(guò)兩個(gè)正則化系數(shù)來(lái)修正子圖采樣給“鄰居聚合”與“損失函數(shù)”帶來(lái)的偏差，不過(guò)從之前個(gè)人復(fù)現(xiàn)的情況來(lái)看[23]，GraphSAINT的實(shí)驗(yàn)結(jié)果主要是靠論文中沒(méi)有提到的代碼中的一系列Trick。

Subgraph-Wise Sampling

1.3.3 基于預(yù)處理的方法

基于預(yù)處理的方法是針對(duì)一類特定的GNN模型設(shè)計(jì)的，不具有通用性，這類模型將消息傳遞與特征變換解耦，對(duì)于消息傳遞部分可以預(yù)計(jì)算（例如SGC，PPNP，SIGN[24]），最后退化為數(shù)據(jù)預(yù)處理+MLP（也可以是其他模型），而MLP部分是可以直接隨機(jī)采樣做Mini-Batch訓(xùn)練的。特別地，對(duì)于PPNP，迭代計(jì)算的方式復(fù)雜度還是挺高的，因此可以進(jìn)一步使用傳統(tǒng)的Push算法[25]或蒙特卡羅算法[26]近似計(jì)算。

Push算法

1.4 Heterogeneous GNN

1.4.1 問(wèn)題背景

現(xiàn)實(shí)場(chǎng)景中大多是異構(gòu)圖，結(jié)點(diǎn)類型和邊類型是多樣的，例如，在電商場(chǎng)景，結(jié)點(diǎn)可以是Query，Item，Shop，User等，邊類型可以是點(diǎn)擊，收藏，成交等，GCN，GAT等模型無(wú)法建模這樣的異構(gòu)性：一方面，不同類型的結(jié)點(diǎn)的Embedding維度就沒(méi)法對(duì)齊；另一方面，不同類型的結(jié)點(diǎn)的Embedding位于不同的語(yǔ)義空間。這限制了模型做特征融合和Attention計(jì)算。以下會(huì)介紹幾個(gè)比較典型的異構(gòu)GNN模型，它們都是通過(guò)Node or Edge Type-Specific Transformation來(lái)建模結(jié)點(diǎn)或邊的異構(gòu)性。不過(guò)KDD 2021[27]一篇工作通過(guò)實(shí)驗(yàn)比較發(fā)現(xiàn)，對(duì)異構(gòu)性的建模帶來(lái)的提升十分有限，該方向的工作大多存在不公平比較的問(wèn)題，實(shí)際上只使用簡(jiǎn)單的GCN或GAT就能取得非常好的效果，吊打一堆所謂的SOTA Heterogeneous GNN。最近也有在做異構(gòu)圖建模的工作，業(yè)務(wù)場(chǎng)景是手淘的下拉推薦（搜索場(chǎng)景），從離線的實(shí)驗(yàn)結(jié)果來(lái)看，當(dāng)結(jié)點(diǎn)的特征比較復(fù)雜且數(shù)據(jù)的規(guī)模比較龐大時(shí)，對(duì)異構(gòu)性的建模效果還是比較明顯的。

1.4.2 代表工作

RGCN[14]：RGCN可能是最早考慮異構(gòu)性的GNN模型了，通過(guò)Edge-Type-Specific Transformation建模邊的異構(gòu)性。

RGCN

HAN[15]：通過(guò)Node-Type-Specific Transformation建模結(jié)點(diǎn)的異構(gòu)性，在計(jì)算Attention時(shí)不僅考慮了某Meta-Path下鄰居的重要性，還考慮了不同Meta-Path之間的重要性。不過(guò)HAN比較依賴Meta-Path的人工選擇。

HAN

KGAT[28]：通過(guò)Edge-Type-Specific Transformation + Ralation Embedding（類似于TransR）建模結(jié)點(diǎn)和邊的異構(gòu)性。

KGAT

HGT[29]：在Attention計(jì)算和Message Passing階段都考慮到了對(duì)異構(gòu)性的建模，分別使用Node-Type-Specific Transformation和Edge-Type-Specific Transformation建模結(jié)點(diǎn)和邊的異構(gòu)性（不過(guò)這參數(shù)量相當(dāng)大呀）。

HGT

1.5 圖神經(jīng)網(wǎng)絡(luò)的優(yōu)勢(shì)

在應(yīng)用某項(xiàng)技術(shù)解決業(yè)務(wù)場(chǎng)景中的某個(gè)問(wèn)題時(shí)，我們需要充分了解這項(xiàng)技術(shù)的特點(diǎn)和優(yōu)勢(shì)，以下從五個(gè)方面談?wù)剛€(gè)人對(duì)GNN優(yōu)點(diǎn)的理解。

GNN VS MLP/CNN/RNN：圖數(shù)據(jù)中結(jié)點(diǎn)鄰居具有兩個(gè)特點(diǎn)，一是數(shù)量不定，二是順序不定，因此MLP/CNN/RNN無(wú)法直接處理這樣的非歐式數(shù)據(jù)而只能用GNN建模。實(shí)際上，我們可以將GNN看做一種更加泛化的模型，例如，RNN相當(dāng)于線性圖上的GNN，而Transformer相當(dāng)于完全圖上的GNN。

GNN VS Graph Embedding：在GNN火起來(lái)之前已經(jīng)涌現(xiàn)出很多Graph Embedding方法，并被廣泛應(yīng)用在搜推的向量召回階段，這類方法受Word2vec[30]啟發(fā)設(shè)計(jì)，從最初的的Item2Vec[31]的Item Sequence+Skip-Gram，到DeepWalk[32]的Random Walk+Skip-Gram；到Node2Vec[33]基于平衡同質(zhì)性和結(jié)構(gòu)性的考慮改進(jìn)Random Walk部分；到MetaPath2Vec[34]基于對(duì)圖的異構(gòu)性的考慮改進(jìn)Random Walk部分；到EGES[35]引入屬性數(shù)據(jù)緩解行為數(shù)據(jù)的稀疏性，可以發(fā)現(xiàn)這類方法都遵循著Skip-Gram的范式。GNN相比這些方法的優(yōu)點(diǎn)主要體現(xiàn)在四處：

GNN可以結(jié)合目標(biāo)任務(wù)端到端地訓(xùn)練，而Graph Embedding更像是預(yù)訓(xùn)練的方式，其學(xué)習(xí)到的Embedding不一定與我們的目標(biāo)任務(wù)相關(guān)，特別是在樣本規(guī)模龐大的業(yè)務(wù)場(chǎng)景，端到端訓(xùn)練得到的Embedding比預(yù)訓(xùn)練得到的Embedding更有效。

GNN的層級(jí)網(wǎng)絡(luò)結(jié)構(gòu)方便與其他深度學(xué)習(xí)技術(shù)結(jié)合（縫合怪水論文最愛(ài)），例如GCN+Attention=GAT。

GNN可以適用Inductive的任務(wù)，即當(dāng)圖的結(jié)構(gòu)發(fā)生變化后，例如加入了一些新的結(jié)點(diǎn)，Graph Embedding方法就需要重新訓(xùn)練模型，而GNN可以使用類似GraphSage Node-Wise Sampling的方式，使用已經(jīng)訓(xùn)練好的模型直接對(duì)新的結(jié)點(diǎn)進(jìn)行推斷。

GNN可以使用更加豐富的特征，Graph Embedding方法本質(zhì)上使用的是ID特征，GNN在消息傳遞的過(guò)程中可以使用多種特征。

GNN VS Feature Concat & Collaborative Filtering & Proximity Loss：GNN相比后三種方法的優(yōu)點(diǎn)可以統(tǒng)一歸納為：通過(guò)堆疊多層顯示地學(xué)習(xí)高階的關(guān)聯(lián)信息。Feature Concat表示將特征拼接到一起然后通過(guò)特征交叉（例如FM，NFM等）可以學(xué)習(xí)到一階的屬性關(guān)聯(lián)信息（區(qū)別于交叉特征的階數(shù)），例如，user a買過(guò)item b，item b和item c都具有屬性attribute a，那么user a也有可能購(gòu)買item b，但是Feature Concat不保證能學(xué)到高階的屬性關(guān)聯(lián)信息；Collaborative Filtering可以通過(guò)用戶歷史行為學(xué)習(xí)到一階的行為關(guān)聯(lián)信息，例如，user a和user b都購(gòu)買過(guò)item a， user b又購(gòu)買過(guò)item b，那么user a也有可能購(gòu)買item b；Proximity Loss表示在損失函數(shù)中加入正則項(xiàng)使得相鄰的結(jié)點(diǎn)更相似，但是一方面它是一種隱式的方式，另一方面想確保學(xué)習(xí)到高階的相似關(guān)系，就需要加入更復(fù)雜的2,3，...，K階正則項(xiàng)，實(shí)際上這也是GCN提出時(shí)的出發(fā)點(diǎn)之一。

KGAT論文中的例子