本文約20000字 15分鐘
本文介紹了一些企業(yè)關于業(yè)務場景的大規(guī)模數據集的文章。 圖神經網絡是近年來很火的一個研究方向，在生物化學，推薦系統，自然語言處理等領域都得到了廣泛應用。其中圖神經網絡在推薦系統的應用方面，已有幾篇綜述[1][2][3]做過詳細的歸納總結。但是讓人感到美中不足的是，綜述中總結的多是學術型工作，偏向于GNN模型上的微調，部分工作其實就是將上游的SGC[4]，GrapSage[5]，JKNet[6]等模型在幾個祖?zhèn)魍婢邤祿纤⒁幌陆Y果講一個故事，很少關心模型的擴展性，也很少關心圖的構建，特征處理，線上打分等不可或缺的環(huán)節(jié)。 因此本文選取了一些近幾年阿里，騰訊，京東，華為等企業(yè)在KDD，SIGIR，CIKM等會議發(fā)表的文章，這些工作的實驗至少是在真實業(yè)務場景的大規(guī)模數據集（千萬級或億級）上進行的，部分工作也成功在線上AB實驗中取得了一些效果。全文分為三部分，第一部分簡單介紹涉及較多的幾個GNN研究方向，包括Deeper GNN（GNN加深），Scalable GNN（大圖訓練），Heterogeneous GNN（異構GNN）；第二部分從幾個不同的角度總結選取的文章，包括應用階段，圖的構建，特征使用，采樣方法，模型結構；第三部分會逐篇介紹這些工作的重點內容。 鏈接：
https://zhuanlan.zhihu.com/p/423342532 1. GNN介紹
不同于傳統的MLP，CNN，RNN等模型，GNN可以建模鄰居順序與數量不定的非歐式數據，常被用來處理結點分類，鏈接預測，圖分類等任務。可以從兩個角度理解GNN，譜圖卷積與消息傳遞，今年我們在ICML的工作則是從迭代算法求解目標函數的角度解釋GNN[7]，同時在該理論框架內還能解釋并解決過平滑，邊的不確定性等問題。針對不同類型的任務，不同類型的圖數據（異質圖，動態(tài)圖，異構圖）等，存在許多特定的GNN模型，此外，還有圖的池化，圖預訓練，圖自監(jiān)督等方向，相關的內容可以參考綜述[8]。第一小節(jié)會簡單介紹一些基礎通用且有代表性的GNN模型，后三小節(jié)分別介紹Deeper GNN，Scalable GNN和Heterogeneous GNN三個方向，這些都是在將圖神經網絡應用到推薦系統時經常涉及的知識。最后一節(jié)談談個人對圖神經網絡的優(yōu)勢的理解。 1.1 Common GNN
Spectral CNN[9]：利用拉普拉斯矩陣定義了圖上的卷積算子，其特點如下： 參數的量級是O(n)，與結點數量正相關，難以擴展到大圖。
Spectral CNN ChebNet[10]：利用切比雪夫多項式近似，降低了計算量和參數量，其特點如下：
GCN[11]：進一步簡化了ChebNet，將譜圖卷積與消息傳遞聯系起來，其層級結構便于和深度學習結合。 SGC[4]：解耦了消息傳遞和特征變換， [公式] 部分可以預計算，簡化后仍然可以在大多數數據集上取得和GCN相當的結果。 GAT[12]：將注意力機制引入GCN，建模了鄰居結點的重要性差異，增強了模型的表達能力。 一方面，將消息傳遞框架范式化，分為Aggregate（聚合鄰居）和Concat（融合自身）兩個步驟。
另一方面，提出了一種簡單有效的鄰居采樣方法，可以在大圖上進行Mini-Batch訓練，并且當有新的結點加入時，不需要在全圖上聚合鄰居，也不需要重新訓練模型，可以用訓練好的模型直接推斷。
PPNP[13]：同樣采用消息傳遞和特征變換分離的結構，并基于個性化PageRank改進消息傳遞，使模型可以平衡局部和全局信息。 RGCN[14]：對于不同類型的邊對應的鄰居結點采用不同的參數矩陣從而建模邊的異構性。當邊的類型很多時，參數也會變得很多，容易造成過擬合，并且不易訓練，需要對參數進行規(guī)約，使用了一下兩種方式： Bias decomposition（定義一組基向量）不僅可以減少參數量，同時對于那些樣本較少的邊也能得到充分學習（參數共享）。 Block-diagnoal decomposition只能減少參數量，實驗下來效果也不如Bias decomposition。
HAN[15]：將GAT擴展到了異構圖上，不僅考慮了不同鄰居結點的重要性差異，也考慮了不同語義的meta-path的重要性差異。 對于鄰居結點的重要性，例如，考慮meta-path：Paper-Author-Paper以及結點分類任務，Paper A、C是數據庫算法論文，Paper B是圖神經網絡論文，它們都是Author A的發(fā)表的文章，即PaperB、C都是Paper A的鄰居，但是在聚合時顯然Paper C與Paper A更相關，需要給與更大的權重。 對于meta-path的重要性，例如，考慮meta-path：Paper-Author-Paper以及Paper-Institution-Paper，通常同一個作者發(fā)表的文章，比同一個機構產出的文章更相關。
1.2 Deeper GNN
1.2.1 問題背景
在GCN的實驗中發(fā)現[11]，一般2-3層的GCN可以取得最好的性能，繼續(xù)增加層數GCN的性能會開始下降，達到8層以上會發(fā)生大幅度的下降。 1.2.2 理論分析
研究者證明了，隨著SGC（不考慮層間的非線性）層數的加深，所有結點會收斂到同一個表征（簡單的線性代數知識可證）[16]。直觀上看，一個K層的SGC相當于聚合了K-Hop的鄰居特征，當K大于或等于圖的直徑時，每個結點都聚合了整張圖上所有結點的特征，從而每個結點都會收斂到同一個表征，結點之間自然會變得難以分辨。該現象被稱為過平滑問題。 也有人證明了，隨著GCN（考慮層間的非線性）層數的加深，所有結點的表征會收斂到同一個子空間[17]。 也有工作表示，消息傳遞和特征變換的耦合才是阻礙GCN加深的主要原因，不過并沒有從理論上證明只是通過實驗進行了驗證[18]。 1.2.3 個人吐槽
實際上不考慮層之間的非線性時，不斷加深SGC的層數甚至達到80層，只要給予模型更多的Epoch訓練，整體上最終結果并不會有什么下降，這與很多論文里報告的SGC加深到10層以上效果驟降根本不符合。隨著層數的增加，所有結點確實會收斂到同一個表征，然而這需要非常深，只要計算機底層表示的精度能夠區(qū)分結點的差異，SGC的效果就不會有什么下降，無非是模型需要更多Epoch訓練收斂。感興趣的同學可以實驗驗證一下。 1.2.4 加深意義
既然2-3層的效果最好，為什么還非要加深呢？這個問題不少工作都不太關心，它們的實驗結果也很一般，只是緩解了加深過程的下降，并沒有帶來什么額外的收益。一種說法是，加深可以增強模型的表達能力（真是個萬能理由），就像CNN那樣通過加深提升效果。比較靠譜的兩種說法是，一是加深可以學習更高階的鄰居信息，這也是不少GNN4Rec工作提到的，高階信息蘊含了多跳的關聯。JKNet中細致分析了中心結點和邊緣結點的情況，如下圖所示，邊緣結點的鄰居非常稀疏，需要加深獲取更大范圍的鄰居信息。二是對于半監(jiān)督結點分類任務來說，通過加深GCN建立長距離的依賴，可以將帶標簽結點的Label信息傳播給更多結點。 1.2.5 代表工作
Deeper GNN的許多工作，只是緩解了加深的性能下降，并沒有通過加深帶來正向收益。以下是幾個確實可以通過加深提升模型效果的工作。整體上看，比較有效的方法都是在以不同的方式組合不同范圍的鄰居信息，類似于Inception組合不同的感受野。PPNP[13]相當于引入了先驗“近距離的鄰居更重要，并且鄰居的重要性隨距離指數衰減”，DAGNN[19]則是通過不同Hop的聚合結果去學習潛在的重要性分布。 JKNet[6]：GCN的第K層包含了K-Hop范圍的鄰居信息，只使用最后一層的輸出存在過平滑問題，因此JKNet保留了每一層的輸出結果，最后綜合融合不同范圍的鄰居信息。 PPNP[13]：采用消息傳遞和特征變換分離的結構，并基于個性化PageRank改進消息傳遞，使模型可以平衡局部和全局信息。 GCNII[20]：除了使用個性化PageRank改進消息傳遞，還引入了Residual Connections保持恒等映射的能力。 DAGNN[19]：自適應地學習不同范圍的鄰居信息的重要性。 1.3 Scalable GNN
1.3.1 問題背景
一方面，GCN在設計之初其卷積操作是在全圖上進行的，在每一層對于所有結點聚合1階鄰居并融入自身表征，這樣第K層的輸出表征就包含了K階鄰居的信息。另一方面，圖數據不同于其他數據集，結點之間存在邊這種關聯，無法直接通過隨機采樣進行Mini-Batch訓練。因此GNN的許多模型無法直接擴展到大圖上，然而真實業(yè)務場景中的圖數據往往都是億級別的。該章節(jié)介紹一些大圖上訓練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結點出發(fā)迭代地采樣1-K階鄰居，在訓練時則迭代地聚合K-1階鄰居，最終得到每個root結點融合了K-Hop鄰居信息的表征。這種方法主要存在以下幾個缺點：
Layer-Wise Sampling[21]：由FastGCN首次提出，對于每一層都采樣固定數量的結點，最終采樣的結點數量與層數成線性關系；同時分析了采樣帶來的偏差與方差（做了大量簡化），確保采樣方法盡可能無偏有效。但是，該方法采樣到的結點連接非常稀疏，不利于進行有效地消息傳遞，實際上實驗效果也確實比較差。 Subgraph-Wise Sampling[22]：由ClusterGNN首次提出，首先用圖劃分算法（Metis等）將原圖劃分為一些子圖，這些子圖具有“高內聚，低耦合”的特點，接著在每個Batch隨機采樣一個子圖（或多個子圖合并為更大的子圖從而降低方差），在該子圖上訓練完全的GCN。GraphSAINT進一步考慮了子圖采樣的偏差，通過兩個正則化系數來修正子圖采樣給“鄰居聚合”與“損失函數”帶來的偏差，不過從之前個人復現的情況來看[23]，GraphSAINT的實驗結果主要是靠論文中沒有提到的代碼中的一系列Trick。 1.3.3 基于預處理的方法
基于預處理的方法是針對一類特定的GNN模型設計的，不具有通用性，這類模型將消息傳遞與特征變換解耦，對于消息傳遞部分可以預計算（例如SGC，PPNP，SIGN[24]），最后退化為數據預處理+MLP（也可以是其他模型），而MLP部分是可以直接隨機采樣做Mini-Batch訓練的。特別地，對于PPNP，迭代計算的方式復雜度還是挺高的，因此可以進一步使用傳統的Push算法[25]或蒙特卡羅算法[26]近似計算。 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]一篇工作通過實驗比較發(fā)現，對異構性的建模帶來的提升十分有限，該方向的工作大多存在不公平比較的問題，實際上只使用簡單的GCN或GAT就能取得非常好的效果，吊打一堆所謂的SOTA Heterogeneous GNN。最近也有在做異構圖建模的工作，業(yè)務場景是手淘的下拉推薦（搜索場景），從離線的實驗結果來看，當結點的特征比較復雜且數據的規(guī)模比較龐大時，對異構性的建模效果還是比較明顯的。 1.4.2 代表工作
RGCN[14]：RGCN可能是最早考慮異構性的GNN模型了，通過Edge-Type-Specific Transformation建模邊的異構性。 HAN[15]：通過Node-Type-Specific Transformation建模結點的異構性，在計算Attention時不僅考慮了某Meta-Path下鄰居的重要性，還考慮了不同Meta-Path之間的重要性。不過HAN比較依賴Meta-Path的人工選擇。 KGAT[28]：通過Edge-Type-Specific Transformation + Ralation Embedding（類似于TransR）建模結點和邊的異構性。 HGT[29]：在Attention計算和Message Passing階段都考慮到了對異構性的建模，分別使用Node-Type-Specific Transformation和Edge-Type-Specific Transformation建模結點和邊的異構性（不過這參數量相當大呀）。 1.5 圖神經網絡的優(yōu)勢
在應用某項技術解決業(yè)務場景中的某個問題時，我們需要充分了解這項技術的特點和優(yōu)勢，以下從五個方面談談個人對GNN優(yōu)點的理解。 GNN VS MLP/CNN/RNN：圖數據中結點鄰居具有兩個特點，一是數量不定，二是順序不定，因此MLP/CNN/RNN無法直接處理這樣的非歐式數據而只能用GNN建模。實際上，我們可以將GNN看做一種更加泛化的模型，例如，RNN相當于線性圖上的GNN，而Transformer相當于完全圖上的GNN。 GNN VS Graph Embedding：在GNN火起來之前已經涌現出很多Graph Embedding方法，并被廣泛應用在搜推的向量召回階段，這類方法受Word2vec[30]啟發(fā)設計，從最初的的Item2Vec[31]的Item Sequence+Skip-Gram，到DeepWalk[32]的Random Walk+Skip-Gram；到Node2Vec[33]基于平衡同質性和結構性的考慮改進Random Walk部分；到MetaPath2Vec[34]基于對圖的異構性的考慮改進Random Walk部分；到EGES[35]引入屬性數據緩解行為數據的稀疏性，可以發(fā)現這類方法都遵循著Skip-Gram的范式。GNN相比這些方法的優(yōu)點主要體現在四處： GNN可以結合目標任務端到端地訓練，而Graph Embedding更像是預訓練的方式，其學習到的Embedding不一定與我們的目標任務相關，特別是在樣本規(guī)模龐大的業(yè)務場景，端到端訓練得到的Embedding比預訓練得到的Embedding更有效。 GNN的層級網絡結構方便與其他深度學習技術結合（縫合怪水論文最愛），例如GCN+Attention=GAT。 GNN可以適用Inductive的任務，即當圖的結構發(fā)生變化后，例如加入了一些新的結點，Graph Embedding方法就需要重新訓練模型，而GNN可以使用類似GraphSage Node-Wise Sampling的方式，使用已經訓練好的模型直接對新的結點進行推斷。 GNN可以使用更加豐富的特征，Graph Embedding方法本質上使用的是ID特征，GNN在消息傳遞的過程中可以使用多種特征。 GNN VS Feature Concat & Collaborative Filtering & Proximity Loss：GNN相比后三種方法的優(yōu)點可以統一歸納為：通過堆疊多層顯示地學習高階的關聯信息。Feature Concat表示將特征拼接到一起然后通過特征交叉（例如FM，NFM等）可以學習到一階的屬性關聯信息（區(qū)別于交叉特征的階數），例如，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提出時的出發(fā)點之一。
2. 論文總結
該章節(jié)對選取的工業(yè)界的文章的共性部分進行總結，除了有人比較喜歡用來水論文的模型結構也涉及了圖的構建，特征使用，采樣方法，結合方式等部分。可以看到，對GNN的應用基本遵循著這套框架。 2.1 應用階段
推薦系統不同階段的特點影響著我們對某項技術的使用，召回階段可以說是樣本的藝術，而排序階段可以說是特征的藝術。其中向量召回是一類常用的個性化召回方法，一般在離線訓練時存下User和Item的Embedding，線上推斷時通過LSH等方法從海量候選集中快速選出用戶可能感興趣的Items。以下總結了召回階段常見的幾個特點： 召回模型一般不會使用太多復雜的特征，以ID特征為主；排序模型會上很多特征盡可能描述用戶，物品及行為過程。 召回模型一般使用PairWise Loss，排序模型一般使用PointWise Loss。個人理解一方面是因為召回階段的目標是篩選出用戶可能感興趣的Item，至于感興趣的程度是多少那是排序模型的職責，因此只需要使用PairWise Loss將正負樣本盡可能區(qū)分開即可。另一方面是因為召回階段的負樣本不一定表示用戶不感興趣，只是沒有曝光而已，如果用PointWise Loss建模會導致模型受噪聲的干擾。 召回模型一般要從全庫隨機選取負樣本，排序模型一般將曝光未點擊作為負樣本。在訓練召回模型時時將曝光未點擊作為負樣本存在兩個問題，一是線下線上的不一致，線上召回時面對的是全庫的候選集；二是在上一輪能夠得到曝光的物品已經屬于用戶比較感興趣的，只不過同時曝光的還有更符合用戶需要的選項，將這些樣本直接作為召回模型的負樣本不太合適。這里的“全庫”也會根據場景變化，例如在搜索場景，由于Query的相關性限制，所以會在同類目下采樣負樣本。 GNN由于其構圖，采樣和計算的復雜性，更多被應用在召回階段做向量召回。常見的一種方式是將Item推薦建模為User結點與Item結點的鏈接預測任務，同樣在離線存下訓練好的User和Item Embedding用于線上召回。不過在建模鏈接預測任務時，很容易產生信息泄露的問題，即在做消息傳遞時，沒有將待預測的邊從圖中去掉，例如預測user a對item a是否感興趣，沒有去掉圖中兩者之間的邊，user a和item a作為鄰居直接融合了彼此的Embedding，導致模型難以學習到有效的信息。在復現一些論文的代碼時，我發(fā)現這個問題還挺常見的。當然在召回階段我們也可以結合目標任務端到端地訓練。GNN也可以應用在排序階段[36][37][38][39][40][41][42][43]，此時存在兩種結合方式，一種是先預訓練[42]，得到的Embedding以特征初始化或Concat的方式輔助排序模型的訓練，另一種是GNN模塊與排序模型整體一起做端到端地訓練，不過這樣需要考慮到線上打分時的效率，特別是GNN采樣以及聚合帶來的開銷。當然我們可以將GNN模塊作為Embedding Layer的一部分，在離線訓練時得到包含了圖信息的Embedding，在線上打分時直接使用該Embedding而無需調用GNN模塊。 2.2 圖的構建
“Garbage in, garbage out”，圖數據構建不好，GNN魔改得再花哨也難奏效。對于構建圖的數據，從數據來源來看，分為行為數據，屬性數據和社交數據；從時間跨度來看，分為短期數據和長期數據；從用戶粒度來看，分為單個用戶和群體用戶；不同種類的數據構建的圖蘊含著不同的特點，下面一一介紹。 行為數據：行為數據是搜推廣場景最常見也最重要的一類數據，應用很廣的行為序列建模就是建立在該數據上，詳情可以參考之前寫的一篇文章：沒什么大不了：淺談行為序列建模。該數據可以構建兩種類型的圖： 二分圖：最常見的方式是使用行為數據直接構建User-Item二分圖，在user和其行為過的Item之間構建邊，不過二分圖的1階鄰居往往非常稀疏，因此有工作通過二分圖的2階鄰居分別導出User-User和Item-Item同構子圖[39]，一方面通過2階鄰居的豐富性緩解了1階鄰居的稀疏性，另一方面也避免了對異構圖的復雜建模，可以直接在子圖上使用同構GNN。User-Item二分圖的另一個缺點是難以及時反映用戶的新的行為（即需要考慮圖的動態(tài)性）。 共現圖：共現關系表達了物品之間的關聯，一方面可以在行為序列相鄰的Item之間構建共現鄰居關系[36]，前后行為的Item一般比較相關；另一方面對于部分場景例如搜索場景，可以在某個Query下點擊過的Item之間構建共現鄰居關系，這些Item一般也比較相關。在這一過程中我們還可以統計共現頻數[44]，共現頻數一方面可以用來去噪，共現頻數較低的兩個Item相關程度也低；另一方面可以用來計算權重分布用于Node-Wise采樣，相比GraphSage隨機采樣，可以最大程度保留有效信息；對于計算的權重分布還可以用于指導對鄰居的聚合過程。值得注意的是，在由User-Item二分圖導出User-User或Item-Item子圖時也可以統計類似的共現頻數。 屬性數據：行為數據構建的圖往往是比較稀疏的，因此可以引入屬性數據構建屬性關系[45]。例如，Item a和Item b都具有屬性Brand a，即兩個商品都是同一個品牌的，這是我們可以引入Entity結點Brand，然后在Item a，b與Brand a之間構建屬性鄰居關系。這里讓人不禁疑問為什么不直接將Brand作為Item的特征呢（Feature concat）？在上文討論圖神經網絡的優(yōu)點時已經提到，將Brand作為圖的一部分可以用多層GNN學習高階的屬性關聯信息。此外，當我們用屬性數據與行為數據共同構建一張更復雜的異構圖，此時還可以用GNN學習到異構的復合關聯信息。 社交數據：我們還以用社交網絡進一步豐富User之間的鄰居關系，不過對于盲目使用社交數據的有效性我是存疑的。具有社交關系的人真的存在相似的偏好嗎？首先，不同的社交關系含義不同，例如，親戚關系更多表示血緣上的聯系，不足以表達偏好上的關聯。其次，社交關系表達的關聯真的適用于我的場景嗎？例如，朋友關系表達的更多是觀點或思想上的關聯，在電商場景下一對朋友不一定對商品擁有相似的偏好，但是在內容場景下例如抖音上，我和朋友確實都喜歡刷貓貓狗狗的視頻。 短期數據 & 長期數據：對于行為數據，我們可以用第T-1的數據構建圖用于第T天，也可以用連續(xù)N天的數據構建圖用于第T天。短期數據更容易保留最近的流行趨勢，例如，這兩天人們搶著買壓縮餅干啥的，但是構建的圖會非常稀疏；長期數據更容易保留穩(wěn)定的一般規(guī)律，例如，人們買完手機過陣子又買手機殼鋼化膜啥的。 單個用戶 & 群體用戶：單個用戶的行為數據構建的圖更具個性化[43]，所謂“一人一圖”，但是同樣會存在稀疏問題；群體用戶的行為數據構建的圖更具泛化性，并且可以緩解某些長尾物品的冷啟動問題。 以上幾種模式并不是孤立的，可以根據不同的場景進行組合。此外，還存在著其他一些圖模式。例如，GMCM[38]構建的圖的結點是各種微觀行為，邊是它們的轉移過程，權重是其轉移概率，并且將CVR預測建模為了圖分類任務。 2.3 特征使用
毫無疑問，ID特征是最重要的，但是利用其他特征諸如Item的Shop，Brand，Category等可以增強我們模型的泛化能力。對于這些泛化特征，一方面，我們可以直接使用Feature Concat的方式統一作為結點的特征，另一方面，也可以把這些特征建模為Entity結點從而學習高階的屬性關聯信息。利用它們的難點在于特征維度和語義空間的對齊（異構性），可以從圖的構建或模型結構方面加以解決。 2.4 采樣方法
在第一部分已經介紹了三種常用的采樣方法，搜推中用的比較多的是Node-Wise Sampling，在這里我們進一步完善討論下該方法。必須強調的是只有當圖的規(guī)模比較大時才需要采樣，對于像UaG[43]中用單個用戶行為數據構建的圖（一人一圖）就不需要采樣。我們可以將Node-Wise Sampling 抽 象為兩個步驟： Root結點的采樣和鄰居結點的采樣。 Root結點的采樣：Root結點是我們在訓練或推斷時需要直接用到的結點，例如，使用User和Item之間的鏈接預測任務建模Item推薦時，首先需要采樣一個Batch的待預測的邊，這些邊兩端的User和Item作為Root結點；或者我們想用圖信息豐富用戶行為序列中Item的表征，則行為數據中的Item作為Root結點[36]。 鄰居結點的采樣：這一步為每個Root結點采樣其鄰居結點，都是以迭代的方式采樣1-K階鄰居（包括Random Walk）。 全采樣：即保留所有1-K階鄰居，鄰居數量會非常龐大，適用于離線“預訓練”的方式，即線上只用到訓練好的Embedding，不然單采樣帶來的開銷就無法承受。 均勻分布采樣：即GraphSage中的采樣方式，每個鄰居結點被采樣到的概率相同。 概率分布采樣：區(qū)別于GraphSage的均勻分布采樣，例如上文提到的在構建圖時統計的共現頻數，歸一化后可以作為采樣的概率分布，這樣更容易采樣到重要的鄰居。 Meta-Path采樣[41]：按照預定義的Meta-Path去采樣鄰居，實際上相當于在異構圖中采樣高階鄰居，例如，按照Meta-Path User-Item-User采樣User的User鄰居。 Random Walk采樣[46]：使用Random Walk方法采樣鄰居，本質上也是一種概率分布采樣，每個鄰居被采用的概率由度數計算。我們可以使用不同的Random Walk策略，例如個性化PageRank。 2.5 模型結構
在第一部分已經介紹了一些常用的GNN模型，這里我們進一步將GNN抽象為兩個步驟：鄰居聚合和表征融合。在應用GNN到推薦系統時，主要從異構建模和特征交互兩個角度改進模型，Attention機制和Layer Aggregation貫穿其中。 鄰居聚合：顧名思義，即聚合鄰居結點的信息，得到中心結點的鄰域的表征。GCN是在每一層對每個結點聚合1階鄰居，則第K層的輸出則包含了K-Hop范圍的鄰居信息，但是它需要操作全圖無法擴展到大規(guī)模圖數據。這里我們討論Node-Wise Samling下鄰居聚合的過程。 迭代聚合：Node-Wise Sampling實際上圍繞中心結點構造了一個1-K階的層次鄰域結構，因此可以迭代地聚合K-1階的鄰居直到中心結點，這也是GraphSage采用的方式，它的一個缺點是計算是串行的，計算完第i階才能繼續(xù)第i-1階的計算，如果線上需要用到該過程會導致RT過高。 并行聚合：我們可以直接并行地聚合1，2，...，K階鄰居，然后再融合它們得到最終的鄰域表征，避免了串行計算帶來的高時間開銷。 表征融合：經過鄰居聚合得到鄰域表征后，我們還需要將它與自身表征融合。常用的幾種方式是：Add[11]，Concat[5]，Attention。Attention主要是考慮到自身與鄰域表征的重要性差異。 異構建模：第一部分提到真實場景中的圖數據大多是異構的，在使用GNN時需要考慮到結點與邊類型的差異性。考慮異構性后我們可以將上述過程擴展為三個步驟：鄰居聚合，鄰域融合，自身融合。在模型結構上基本都遵循著第一部分提到的Node or Edge Type-Specific Transformation+Attention的框架。 鄰居聚合：鄰居結點存在不同的類型，因此一般按類型分別聚合鄰居。一種比較特殊的方式是將原來的異構圖轉化為一系列的同構子圖，在這些子圖上可以直接使用同構GNN。 特征交互：部分工作認為GNN缺少對鄰居之間的交互[47][48]，鄰域之間的交互[48][49]，鄰域與自身的交互[50]的建模，因此引入元素積，self-Attention，co-attenive等方式增強特征交互。 Attention機制：Attention可以說是萬金油技術了，這里主要被用來建模鄰居之間的重要性差異，鄰域之間的重要性差異，自身與鄰域的重要性差異。 Layer Aggregation[51]：在Deeper GNN部分提到過，第K層輸出包含了K-Hop鄰居信息，Layer Aggregation即組合不同范圍的鄰居信息。 3. 論文介紹
3.1 Graph Convolutional Neural Networks for Web-Scale Recommender Systems[46] [PinSage]，KDD 2018，Pinterest
問題背景：現有的GNN難以在大規(guī)模圖數據場景落地 業(yè)務 場景： i2i Top N推薦（似乎因為場景復雜性低的問題，這里并沒有進一步分召回排序） 圖的構建：Pin-Board二分圖，Pin是照片，Board類似收藏夾 特征使用：Pin包含了圖像特征和文本特征，Board本身沒有特征，而是通過Average Pooling對應的Pin們得到 采樣方法：Node-Wise Random Walk Sampling，使用個性化PageRank采樣鄰居，得分既可以用來加權聚合鄰居，也可以用來構造Hard Sample。 Model Architecture：使用采樣時的得分加權聚合鄰居
User在某個Pin下點擊的Pin構成一對正例，然后從其他Pin中隨機采樣一部分作為Easy Negative，采樣時得分位于某個范圍的Pin鄰居作為Hard Negative。Easy Sample往往很好區(qū)分，模型無法從中學習到有效信息，而Hard Negative則可以迫使模型學得更好，但是也容易導致收斂困難，因此可以在起初幾個Epoch只使用Easy Sample，然后再逐步加入Hard Sample 3.2 Metapath-guided Heterogeneous Graph Neural Network for Intent Recommendation[41] [MEIRec]，KDD 2019，阿里
問題背景：當前的方法沒有充分利用關聯信息，作者利用異構 圖和相應模型來建模學習； 通過Term Embedding共享的方法來降低學習量。 圖的構建：群體用戶行為數據構建的Query-Item-User異構圖，目標是學習User和Query的Embedding。特征使用： Query和Item的Title共享Term Embedding，降低了需要學習的參數量，同時可以適應新的Query和Item User的embedding通過Q-I-U、I-Q-U兩條Meta-Path對應的鄰居聚合得到 User Profile等靜態(tài)特征最后與GNN得到的Embedding Concat后輸入MLP 采樣方法：Node-Wise Meta-Path隨機采樣 模型結構：主要是對于不同類型的鄰居采用了不同的Aggregator 對于Item的Query鄰居采用Mean Aggregator 對于User的Item和Query鄰居采用LSTM Aggregator，考慮到了User對Item和Query的行為是有時序的 對于Query的鄰居Item和User采用了CNN Aggregator
3.3 IntentGC：a Scalable Graph Convolution Framework Fusing Heterogeneous Information for Recommendation[45] [IntentGC]，KDD 2019，阿里
問題背景：已有的工作大多利用社交網絡或共現關聯分別為User-Item二分圖中的Users和Items擴充內部連接，卻忽略了屬性關聯這一類豐富的信息。 圖的構建：群體用戶行為數據+屬性數據構建以User和Item為主體的異構圖，接著通過User-Property-User和Item-Property-Item構建User-Item異構圖，屬性結點的類型決定了構建的邊的類型。 特征使用：雙塔結構，可以用多種特征（不存在特征對齊的問題） 采樣方法：先采樣一些User-Item Pairs（包括負樣本）作為mini-batch，然后對這些User和Item分別Node-Wise Sampling同構鄰居。Faster Convolutional Network: IntentNet Vector-wise convolution operation
公式（2）有兩個作用，一是以不同的重要性融合自身和鄰居信息，二是concat后的各維度間的特征交叉，作者認為自身Embedding和鄰居Embedding之間的特征交叉沒有意義，內部的特征交叉才是有意義的
公式（3）對公式（2）進行了簡化（時間復雜度和模型參數量都有所降低），在vector-wise的層次以不同重要性融合自身和鄰居信息，并且通過多組融合操作得到不同角度的信息（類似多個不同的卷積核），最終再進行一次加權融合。
IntentNet：再經過一個多層MLP進行特征交叉 Heterogeneous relationships：將Vector-wise convolution operation推廣到了存在多種類型關系的情形，對不同類型關系對應的鄰居分別聚合然后對得到的鄰域表征再加權融合
Dual Graph Convolution in HIN：對于User-User和Item-Item分別應用上述模型（雙塔結構），最終得到User和Item Embedding做點積，使用Pair-Wise Margin Loss訓練。
3.4 A Dual Heterogeneous Graph Attention Network to Improve Long-Tail Performance for Shop Search in E-Commerce[44] [DHGAT]，KDD 2020，阿里
問題背景：shop name和query的語義存在gap，很多時候shop name并不能表明含義；shop search場景的行為數據比較稀疏，特別是對于長尾的Query和Shop效果不佳 圖的構建：長期群體用戶行為數據構建的shop-query-item異構圖 對于Query，某個用戶同一個Session內的Query之間構成鄰居；引導點擊同一個Shop的Query之間構成鄰居 對于Shop，同一個Query下點擊的Shop之間構成鄰居 Query下點擊的Shop，它們之間構成鄰居（但是這種關系是非常稀疏的） 某個shop提供的item在某個query下被成交過，則該shop和query構成鄰居（本質上是二階鄰居，該關系相對豐富） shop提供的item，query下點擊的item，它們之間構成鄰居 DHGAT部分用的是Query、Shop、Item的ID特征 TKPS部分用的是Query、Shop、Item的Term特征 采樣方法：Node-Wise Sampling，對于Shop和Query，分別采樣N個Homogeneous和Heterogeneous鄰居，即2N個鄰居（防止熱門shop或query的影響）。 Dual Heterogeneous Graph Attention Network：
先對同構鄰居和異構鄰居分別Attention Pooling，然后再對不同類型的鄰域Embedding加權融合，最后再與自身Embedding進行concat融合 在對異構鄰居進行聚合時使用heterogeneous neighbor transformation matrix建模異構性 這里item不作為target node，最終需要的是query和shop的embedding Transferring Knowledge from Product Search：利用行為數據相對豐富的product search場景的數據促進對shop search場景的學習 這里使用的是query，item和shop的terms mean pooling特征
由于quey和shop name語義的模糊性，聚合時不適合用Attention pooling，而是直接使用mean pooling Incorporating User Features：用戶自身的特點也會影響偏好，預測用戶在某query下是否會點擊某shop需要考慮該信息 Two-tower Architecture：對shop和query embedding的學習可以并行進行，線下訓練時可以存下user，query和shop embedding，其中shop embedding存的是最后一層的輸出（線上不可能再將所有的shop過一遍右塔），線上打分時獲取到user和query embedding，然后需要經過左側的塔得到一個融合的embedding（這個過程只需要進行一次，其線上開銷是可以接受的），接著通過LSH等方法召回相關的shop Objective and Model Training
使用交叉熵損失訓練CTR預估任務，不過值得注意的是召回階段負樣本的選擇，不能是曝光未點擊的作為負樣本 CTR Loss可能會導致不能充分學習到圖的拓撲信息，這里又進一步加了graph loss，從loss角度促進同構鄰居更相似 3.5 M2GRL: A Multi-task Multi-view Graph Representation Learning Framework for Web-scale Recommender Systems[52] [M2GRL]，KDD 2020，阿里
問題背景：單個向量表達Multi-View（多種特征空間）信息可能會存在兩點問題，容量不足以及分布不同 圖的構建：文中沒有具體談到，應該是群體行為數據構建的多個Single-View同構圖。 但是值得注意的是，本文具體實現時并沒有用圖結構，而是類似Item2Vec的方法直接對行為序列用skip-gram建模。 本文構建了三個Single-View圖，基于Item本身構建的圖，基于Item Shop構建的圖，基于Item-Category構建的圖
Node sequence sampling：用于下文的Skip-Gram方法，通過Session劃分盡量保持滑動窗口內Item的同構性 Data Clean：去掉停留時間比較短的Item，用戶可能是誤點并不感興趣 Session split and merge：用戶打開和關閉淘寶的時間段作為一個Session，對于時間較長的Session（幾個小時，可能是后臺運行）進一步拆分，對于時間較短（小于30分鐘）的兩個連續(xù)的Session進行合并 Intra-view Representation Learning：隨機采樣上文劃分后的Session序列，然后使用Skip-Gram方法訓練。
Inter-view Alignment：不同View的信息存在關聯，例如，某個Item屬于某類Category或者某個Shop，這里進一步學習該關聯使得相關的Item-Category或者Item-Shop的Embedding更加接近，使用了一個變換矩陣期望將不同View的Embedding映射到同一個特征空間。
Learning Task Weights with HomoscedasticUncertainty：考慮到許多任務聯合訓練，人工設置加權Loss不太現實，這里利用homoscedastic uncertainty來自動學習不同任務的重要性，最終不確定性越大（可學習的參數）的任務權重越低。
3.6 Gemini: A Novel and Universal Heterogeneous Graph Information Fusing Framework for Online Recommendations[39] [Gemini]，KDD 2020，滴滴
問題背景：基于User-Item二分圖的方法，一種是直接在原圖上交叉聚合，另一種是借助輔助數據（如社交網絡）將其劃分為User-User，Item-Item同構圖。前者會存在鄰居稀疏的問題，后者則丟失了User-Item關聯信息，并且輔助數據限制了應用場景。 圖的構建：群體用戶行為數據構建的二分圖，接著通過User-Item-User，Item-User-Item關系導出User-User和Item-Item同構圖，由于是通過二階鄰居導出的子圖，在某種程度上緩解了鄰居稀疏的問題。 Node Embedding：同構子圖可以使用User和Item的多種特征，但是作者對邊的異構性進行了建模，因此實際只能使用ID特征。
User-User子圖中，邊由導出時的中間Items決定（保留了原來的一階鄰居信息） 直接對Items Sum pooling無法建模重要性差異，因此作者提出了TF-IDF Pooling，其中TF是某Item在該邊對應的所有Items中的占比，占比越大，說明對該邊來說越重要；IDF是某Item在所有邊對應的Items集合中的占比，占比越大，說明該Item重要性越低。TF-IDF=TF*IDF。 這里沒有直接用TF-IDF加權求和，而是將該得分分桶離散化然后Embedding，通過元素積的方式進行特征交叉 采樣方法：Node-Wise Sampling Attention based Aggregating：加性模型計算Attention，并且考慮了Edge Embedding，得到鄰域Embedding后與自身Embedding進行融合。
訓練推斷：使用MLP計算User點擊某Item的概率，損失函數交叉熵，點擊Item為正樣本，曝光未點擊Item為負樣本（因此可以斷定是排序模型） Joint training：在User-User上聚合鄰居時，Edge Embedding需要用到Item Embedding，反之亦然，所以User-User和Item-Item的聚合過程是相互依賴的。 Gemini-Collaboration Framework：似乎是將原來相互依賴的兩個聚合過程分開，先將其中一個訓練至收斂再進行另一個，從而降低訓練的復雜度，類似GAN的訓練方式。 3.7 Multi-view Denoising Graph Auto-Encoders on Heterogeneous Information Networks for Cold-start Recommendation[40] [MvDGAE]，KDD 2021，騰訊
問題背景：User-Item行為數據往往非常稀疏，新用戶或新商品存在冷啟動問題。一類方法通過引入更多屬性特征緩解，但是這會非常依賴特征數據的獲取和質量；另一類方法通過HIN引入屬性信息來緩解（這和上面的有什么區(qū)別），但是它們大多通過有監(jiān)督的方式訓練，會產生訓練和測試階段的不一致（訓練階段大多是old user或item，測試階段存在更多new user或item，它們在圖中的連接會比較稀疏，只存在一些屬性關聯）。 業(yè)務場景：文中沒有具體說，從損失函數與推斷方式來看似乎是物品推薦的排序階段
特征使用：從聚合方式來看，只用上了ID特征（需要注意的是，這里是是指單個結點的ID特征，實際上在HIN中，屬性特征被建模為了結點，例如，電影的演員特征，演員被建模為了結點） 采樣方法：分為兩個階段，Encoder階段基于Meta-Path（首尾不限） Node-Wise采樣，Decoder階段基于特定的Meta-Path（首尾相同）采樣出User-User和Item-Item子圖，每個Meta-Path對應一個View。Multi-view Graph Encoders Node-level Aggregation based on Meta-path：通過GAT聚合Node-Wise采樣到的鄰居，這里不同于HAN，對于Meta-Path上的鄰居（存在不同類型）都會聚合。 Dropout on Multi-views：這里是對View的Dropout，而不是某個View下Edge的Dropout，通過Dropout可以迫使學習到的Embedding更具泛化性，在測試時對于連接稀疏的new user或item有更好效果。
Multi-view Graph Denoising Decoding Construct Multi-View Graph：基于首尾相同的Meta-Path構建不同View的User-User和Item-Item子圖，使得那些相似的User或Item的表征也更接近。 Multi-View Graph Decoding：用Encoder得到的Embedding重構多個View的子圖，即鏈接預測任務。 Sampling Strategy：對所有結點對預測邊開銷太大，需要經過采樣預測部分邊，這里對Meta-Path 1-hop鄰居完全采樣，然后對2 hop鄰居部分隨機采樣，以緩解1-hop鄰居稀疏的問題。 Bayesian Task Weight Learner：多個View子圖的Encoder和Decoder是獨立的，最終需要將它們的Loss整合到一起聯合訓練，這里也用了異方差不確定性來自動學習權重。 Optimization Objective：Loss由兩部分組成，一部分是重構Loss，一部分是評分Loss（均方差）（如果只有點擊數據，那就是交叉熵），所以本文其實是利用到了標簽數據，是無監(jiān)督+有監(jiān)督的結合。 3.8 Graph Intention Network for Click-through Rate Prediction in Sponsored Search[36] [GIN]，SIGIR 2019，阿里
問題背景：使用單個用戶的歷史行為表征用戶興趣存在行為稀疏和泛化性弱的問題；圖神經網絡預訓練的方式得到的Embedding與目標任務不相關。 圖的構建：群體用戶行為數據構建Item同構圖。首先將Item點擊序列按照Query相關性劃分為多個Session，然后在Session內相鄰Item之間構建鄰居關系（防止不相關的兩個Item成為鄰居），邊的權重為共現頻數。具體使用近30天所有用戶的點擊序列構建商品相似圖。 采樣方法：Node-Wise Sampling，根據共現頻數計算概率分布 模型結構：為序列中的每個Item采樣鄰居用GNN聚合得到更一般的Embedding，即通過構建圖引入額外信息豐富行為序列從而緩解行為稀疏問題和泛化性弱的問題。得到更一般的Embedding后就是常規(guī)的Target Attention抽取序列中的偏好信息。 3.9 ATBRG: Adaptive Target-Behavior Relational Graph Network for Effective Recommendation[37] [ATBRG]，SIGIR 2020，阿里
問題背景：基于Meta-Path的方法，一方面需要人工經驗設計，另一方面會損失結構信息（各Meta-Path獨立）；基于GNN的方法，一方面對Target Item和User分別采樣，缺少它們之間的交互性，另一方面隨機采樣鄰居可能會引入噪聲（這個得看圖是怎么構建的吧，并且我們也可以按權重采樣）。
a中由于各Meta-Path獨立，襯衫和連衣裙沒能建立起關聯 b中一方面由于分別采樣，丟失了Target Item與用戶行為過的連衣裙的關聯，另一方面由于隨機采樣反而引入了開水壺噪聲 c中用本文特有的構建圖的方式，最終得到的KG圖既能較好地保留結構信息，又能去除一些與Target Item不相關的噪聲。 采樣方法：從Target Item和用戶行為過的Items構成的Root Nodes合集中，分別為每個結點在圖中采樣K-Hop鄰居，根據采樣的結點集合從原圖中誘導出子圖（區(qū)別于獨立采樣，可以建立Target Item與行為過的相關的Item的聯系），對于該子圖中只有一個鄰居的結點進行剪枝（這些結點很可能是噪聲）。
Embedding Layer：User和Target Item的Embedding（ID和其他特征），異構圖（KG圖）中實體和關系的Embedding。 Relation-aware Extractor Layer：這里是用中心結點計算鄰居結點的重要性，同時對“關系”進行了建模，即關系的類型會影響重要性，例如，點擊和購買兩種關系，顯然表現出的興趣程度不同
Representation Activation Layer：得到Target Item和Sequence Item的Embedding后，這里又進一步使用Target Attention篩選相關信息
Feature Interaction Layer：將所有Embedding Concat后送入MLP做特征交叉 3.10 GMCM: Graph-based Micro-behavior Conversion Model for Post-click Conversion Rate Estimation[38] [GMCM]，SIGIR 2020，阿里
微觀行為與最終是否成交高度相關，但是微觀行為不適合用序列建模，不同順序的微觀行為表達的可能是同一意圖，例如，用戶在購買前先看評論再看問大家，和先看問大家再看評論，表達的意圖一樣。（這里的微觀行為是指用戶點擊商品后，購買商品前發(fā)生的一系列行為，例如評論，收藏等）
CVR任務存在數據稀疏的問題（用戶的成交行為是稀疏的） CVR任務存在樣本選擇偏差的問題（用戶是先點擊后成交，但是線上CVR預估時，是從全域候選集經過召回后打分，而不是對用戶發(fā)生過點擊的Item打分） 業(yè)務場景：商品推薦排序階段 微觀行為圖，結點是微觀行為，邊是共現頻數歸一化后的權重 用所有用戶的微觀行為數據構建圖，即該圖反映的是一般性的群體規(guī)律，對于單個用戶其微觀行為數據體現在Node Loss中
特征使用：上游多種特征變換對齊后的Embedding 采樣方法：微觀行為圖是很小的，不需要進行采樣 Multi-task Learning Modul：底層共享部分Embedding（特別是ID Embedding）
Node Embedding Layer：將MLP的輸出通過N個1-Layer MLP映射為N個微觀行為結點Embedding
Graph Convolutional Networks
這里分成了兩個任務，一個是預測某個微觀行為結點是否存在，即在構建圖時是默認所有微觀結點都存在，并且圖的邊權也是所有用戶數據統計出的。單個用戶的微觀行為數據是在Node Loss中體現的。 另一個是將CVR預測轉化為了圖分類任務，即微觀行為圖可以反映用戶是否會發(fā)生成交 圖的Embedding通過Graph Pooling得到，例如Sum pooling，Mean pooling，Concat Pooling Loss Layer：相應的PMG Loss也由Node Loss和CVR Loss構成，最終Loss由PMG Loss和CTR Loss組合而成（也有分別訓練）。這里將CTR預估分數作為了IPV來Debias。
編輯：王菁
校對：林亦霖
