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

1.3 Scalable GNN

1.3.1 問(wèn)題背景

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

1.3.2 基于采樣的方法

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

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

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

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

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

Node-Wise Sampling

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

Layer-Wise Sampling

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

Subgraph-Wise Sampling

1.3.3 基于預處理的方法

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

Push算法

1.4 Heterogeneous GNN

1.4.1 問(wèn)題背景

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

1.4.2 代表工作

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

RGCN

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

HAN

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

KGAT

HGT[29]：在A(yíng)ttention計算和Message Passing階段都考慮到了對異構性的建模，分別使用Node-Type-Specific Transformation和Edge-Type-Specific Transformation建模結點(diǎn)和邊的異構性（不過(guò)這參數量相當大呀）。

HGT

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

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

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

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

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

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

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

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

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

KGAT論文中的例子