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論文中的例子
*博客內容為網(wǎng)友個(gè)人發(fā)布,僅代表博主個(gè)人觀(guān)點(diǎn),如有侵權請聯(lián)系工作人員刪除。