2W字長文 | 漫談工業界圖神經網絡推薦系統（2）

1.3 Scalable GNN

1.3.1 問題背景

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

1.3.2 基于采樣的方法

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

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

隨著層數增加，采樣到的鄰居數量指數增長

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

沒有考慮采樣造成的偏差和方差

Node-Wise Sampling

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

Layer-Wise Sampling

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

Subgraph-Wise Sampling

1.3.3 基于預處理的方法

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

Push算法

1.4 Heterogeneous GNN

1.4.1 問題背景

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

1.4.2 代表工作

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

RGCN

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

HAN

KGAT[28]：通過Edge-Type-Specific Transformation + Ralation Embedding（類似于TransR）建模結點和邊的異構性。

KGAT

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

HGT

1.5 圖神經網絡的優勢

在應用某項技術解決業務場景中的某個問題時，我們需要充分了解這項技術的特點和優勢，以下從五個方面談談個人對GNN優點的理解。

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

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

GNN可以結合目標任務端到端地訓練，而Graph Embedding更像是預訓練的方式，其學習到的Embedding不一定與我們的目標任務相關，特別是在樣本規模龐大的業務場景，端到端訓練得到的Embedding比預訓練得到的Embedding更有效。

GNN的層級網絡結構方便與其他深度學習技術結合（縫合怪水論文最愛），例如GCN+Attention=GAT。

GNN可以適用Inductive的任務，即當圖的結構發生變化后，例如加入了一些新的結點，Graph Embedding方法就需要重新訓練模型，而GNN可以使用類似GraphSage Node-Wise Sampling的方式，使用已經訓練好的模型直接對新的結點進行推斷。

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

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

KGAT論文中的例子