Graph Neural Transport Networks with Non-local
Attentions for Recommender Systems
用于推薦系統(tǒng)的非局部注意的圖神經(jīng)傳輸網(wǎng)絡(luò)
來源：WWW 2022
摘要：通常，GNN通過在本地鄰居之間傳播和聚合消息來生成用戶/項的嵌入。因此咆槽，GNN捕獲遠(yuǎn)程依賴關(guān)系的能力在很大程度上取決于它們的深度。然而吝羞，簡單地訓(xùn)練深度gnn會產(chǎn)生瓶頸效應(yīng)，例如過擬合和過平滑等内颗，無法得到較好的訓(xùn)練效果钧排。為了解決這個問題，作者提出了圖最優(yōu)傳輸網(wǎng)絡(luò)(GOTNet)來捕獲在不增加GNN深度的情況下的長期依賴關(guān)系均澳。GOTNet能夠只使用淺層GNN來同時捕獲圖中的本地和非本地消息恨溜，從而避免了深度GNN的瓶頸效應(yīng)。實(shí)驗結(jié)果表明找前，與現(xiàn)有的GNN相比糟袁，GOTNet取得了更好的性能。
1 背景與簡介
? ? 圖神經(jīng)網(wǎng)絡(luò)現(xiàn)已被廣泛應(yīng)用在推薦任務(wù)中躺盛，并且目前成熟的圖神經(jīng)網(wǎng)絡(luò)推薦模型往往采用兩層到四層的結(jié)構(gòu)系吭。雖然在理論上，深度GNN應(yīng)該具有更強(qiáng)的建模復(fù)雜圖結(jié)構(gòu)的表達(dá)能力颗品，能夠?qū)W習(xí)到遠(yuǎn)距離依賴關(guān)系，但深度GNN在實(shí)踐中遇到了幾個挑戰(zhàn)沃缘。首先躯枢，由于GNN的復(fù)雜度與層數(shù)呈指數(shù)關(guān)系，因此計算效率不高槐臀，導(dǎo)致對訓(xùn)練時間和GPU內(nèi)存的需求很高锄蹂。其次，它使優(yōu)化變得困難水慨。具體地說得糜，深度GNN存在過擬合敬扛、過平滑和可能的梯度消失的問題。這些“瓶頸效應(yīng)”可能會抑制深層GNN的潛在優(yōu)勢朝抖。第三啥箭，隱式用戶項圖，通常是復(fù)雜的治宣，并表現(xiàn)出拓?fù)渫|(zhì)性或異質(zhì)性的混合急侥。因此，如果gnn沒有很好地正則化侮邀，簡單地訓(xùn)練深度GNN可能會導(dǎo)致意想不到的結(jié)果坏怪。
? ? 作者提出了一個高度可伸縮的圖最優(yōu)傳輸網(wǎng)絡(luò)(GOTNet)，以在不增加GNN深度的情況下捕獲長期依賴關(guān)系绊茧。GOTNet結(jié)合了圖的卷積和聚類方法铝宵，分別實(shí)現(xiàn)了有效的局部編碼和非局部編碼。具體來說华畏，在每一層中鹏秋，都使用圖卷積，通過聚合來自本地鄰居的信息來計算節(jié)點(diǎn)嵌入唯绍。然后拼岳，GOTNet對用戶和項目的嵌入進(jìn)行k-Means聚類，以獲得他們的圖級表示（例如况芒，用戶/項目質(zhì)心）惜纸。進(jìn)一步提出了一種非局部注意算子來度量每對（節(jié)點(diǎn)、質(zhì)心）之間的相似性绝骚，使遠(yuǎn)程消息能夠在遙遠(yuǎn)但相似的節(jié)點(diǎn)之間進(jìn)行通信耐版。
? ? 同時，很關(guān)鍵的一點(diǎn)是压汪，作者提出了一個全微分的k-均值聚類方法粪牲，通過將其轉(zhuǎn)換為一個等價的最優(yōu)傳輸任務(wù)，通過貪婪的辛克霍恩算法有效地求解止剖。因此腺阳，gnn和k-Means的參數(shù)可以在尺度上進(jìn)行聯(lián)合優(yōu)化。并且穿香，GOTNet是與模型無關(guān)的亭引，可以應(yīng)用于任何gnn。作者對四個公共數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗皮获。結(jié)果表明焙蚓，GOTNet在捕獲遠(yuǎn)程消息的有效性方面的好處，導(dǎo)致5.21%的～19.45%的性能提高。
2 基于GNN的推薦簡介
? ??GNN的設(shè)計包括嵌入购公、聚合萌京、池化和優(yōu)化。
? ? 嵌入層：首先對每個用戶和項目的嵌入進(jìn)行初始化宏浩，這里使用的是潛入查找表的方法：
????其中知残，u和i表示一個用戶和一個項目的id；eu（0）∈Rd和ei（0）∈Rd分別為用戶u和項目i的初始嵌入绘闷，d為嵌入大小橡庞。
? ? 聚合層：GNN進(jìn)行圖卷積來聚合鄰居的特征：
? ? 池化層：GNN通常采用池化技術(shù)來獲取一個節(jié)點(diǎn)的最終嵌入：
? ? ? 優(yōu)化：最后可以通過內(nèi)積來估計用戶對目標(biāo)項目的偏好如下：
? ??貝葉斯個性化排序損失可以采用[32]來優(yōu)化模型參數(shù)，這可以通過最小化下面的式子來實(shí)現(xiàn)：
? ? 其中i表示u的正樣本印蔗，j表示u的負(fù)樣本扒最，u，i华嘹，j一起組成了一個正負(fù)樣本對吧趣。用α控制Θ的L2范數(shù)以防止過擬合。
? ??在等式中的聚合器（2）在從鄰居那里收集消息方面起著關(guān)鍵的作用耙厚。然而强挫，圖的卷積本質(zhì)上是局部算子，即eu在每次迭代中只從其一階鄰居Nu中收集信息薛躬。很明顯俯渤，LightGCN捕獲遠(yuǎn)程依賴關(guān)系的能力在很大程度上取決于它的深度：至少需要k個GNN層來捕獲距離目標(biāo)節(jié)點(diǎn)有k個跳數(shù)的信息。然而在上面我們已經(jīng)闡述了深層GNN遇到的種種困難型宝。于是八匠，作者提出了這樣一個問題，即是否可以通過使用gnn的淺層架構(gòu)來捕獲長期依賴關(guān)系趴酣。
3 GOTNET方法
????GOTNet主要包括兩個階段：1)通過k-Means聚類獲得用戶和項目的聚類感知表示梨树；2)通過成對的節(jié)點(diǎn)-質(zhì)心注意力而不是節(jié)點(diǎn)-節(jié)點(diǎn)注意力來捕獲長期依賴關(guān)系。如圖1所示岖寞，雖然用戶u1和u2彼此相距2跳抡四，但u2的信息可以用質(zhì)心c1緊湊地表示，質(zhì)心c1可以通過一層GNN傳遞給u1仗谆。接下來指巡，我們將詳細(xì)介紹GOTNet。
? 3.1 k-means
? ??由于具有相似興趣的用戶會購買相似的項目隶垮，作者將每一層gnn的用戶/項目嵌入集群到不同的簇中厌处。這允許在任何位置的節(jié)點(diǎn)感知來自所有節(jié)點(diǎn)的上下文消息，這將有利于gnn學(xué)習(xí)長期依賴關(guān)系岁疼。
? ??讓表示等式中g(shù)nn的第l層中的所有N個用戶嵌入，作者對用戶嵌入執(zhí)行k-Means聚類。為了使模型更加靈活捷绒，作者進(jìn)一步通過投影函數(shù)
把用戶投影到空間
瑰排，
可以是一個神經(jīng)網(wǎng)絡(luò)，甚至是一個線性投影暖侨。這里作者簡單地定義
椭住，1≤i≤N，其中W∈Rd×d是一個可訓(xùn)練的權(quán)重矩陣字逗。然后在該低維空間中執(zhí)行k-means聚類京郑，通過最小化（6）獲得K個用戶質(zhì)心
? ?其中，?表示用戶i是否為質(zhì)心k的簇成員葫掉，即些举，如果數(shù)據(jù)點(diǎn)
被分配給集群ck，則為
=1俭厚，否則為0户魏。
? ??然而，解決等式（6）并不簡單挪挤，因為涉及到另一個優(yōu)化任務(wù)叼丑。由于k-Means中離散聚類分配的不可微性，em型方法不能使用標(biāo)準(zhǔn)的基于梯度的端到端學(xué)習(xí)與gnn或fθ聯(lián)合優(yōu)化扛门。即如果把式6與bprloss做聯(lián)合優(yōu)化鸠信，由于這里
=0或1，將會出現(xiàn)π·fθ在loss中進(jìn)行反向傳播更新參數(shù)時出現(xiàn)不可微的情況论寨。于是作者將k-均值重寫為一個最優(yōu)傳輸（OT）任務(wù)星立，并推導(dǎo)出了一個聯(lián)合訓(xùn)練的完全可微損失函數(shù)。
3.2?通過OT的可微k-means聚類
? ??k-Means和OT之間的聯(lián)系是由Pollard發(fā)現(xiàn)的政基。粗略地說贞铣，OT算法等價于約束k-Means聚類。利用等式中的最優(yōu)運(yùn)輸計劃來參數(shù)化k-均值沮明，便可以提出一個新的k-Means目標(biāo)如下：
? ??其中w=[n1辕坝，……，nK]表示簇比例荐健，即nk是分區(qū)k中的點(diǎn)的數(shù)目酱畅，。
表示K*1維的單位向量江场，
表示N*1維的單位向量纺酸。S.T.1
則可以表示為每個點(diǎn)對于k個中心的π和為1（是個軟分配）。S.T.2則表示每個中心點(diǎn)對于所有點(diǎn)的比重加和為w址否。作者簡單地為平衡分區(qū)設(shè)置n1=···=nK=N/K餐蔬。此外碎紊，作者在這兩個約束條件上都明確地引入了歸一化因子1/N，它遵循了OT中的概率單純形的條件樊诺，并且不影響損失仗考。通過這樣做，等式（7）成為一個標(biāo)準(zhǔn)的OT問題词爬，可以將集群分配π視為一個傳輸計劃秃嗜，而將歐氏距離∥fθ(eui)?ck∥22視為傳輸成本。
? ??使用的等式（7）可以通過線性規(guī)劃(LP)求解顿膨，但計算負(fù)擔(dān)較大锅锨。通過在該領(lǐng)域常用的Sinkhorn算法引入熵正則化，通過限制最優(yōu)傳輸問題解的復(fù)雜度恋沃，可以大幅降低的復(fù)雜度得到最優(yōu)傳輸問題的近似解：
? ??其中必搞，ε>0是一個正則化參數(shù)。已知LP算法在頂點(diǎn)上達(dá)到最優(yōu)值芽唇，而熵項使最優(yōu)值遠(yuǎn)離頂點(diǎn)顾画，得到更平滑的可行區(qū)域。請注意匆笤，所有辛克霍恩算子都是可微的研侣，這使得k-Means完全可微，并允許以隨機(jī)方式與gnn和fθ進(jìn)行聯(lián)合訓(xùn)練炮捧。類似地庶诡，我們也可以用類似的方式來定義項目集群損失。
? ??當(dāng)計算出最優(yōu)運(yùn)輸計劃π?時咆课，我們可以細(xì)化質(zhì)心：,k=1,2...k末誓。
3.3 注意力混合
單頭非本地注意力機(jī)制
? ??在gnn中，節(jié)點(diǎn)嵌入通過迭代消息傳遞進(jìn)行更新书蚪。對于每一層0≤l≤L喇澡，我們通過微分k-Means聚類獲得一組用戶集群。類似地殊校，項目集群
可以通過聚類項目嵌入計算晴玖，其中K和P分別是用戶和項目集群的數(shù)量。需要注意的是为流，作者假設(shè)K和P的值在gnn內(nèi)是不變的呕屎。
????受注意機(jī)制的啟發(fā)，作者試圖通過非局部節(jié)點(diǎn)質(zhì)心注意來收集相關(guān)的遠(yuǎn)程信息敬察，給定等式中的GNN嵌入和
秀睛，以及來自(l?1)第一層的用戶/項目中心，注意機(jī)制給出了輸出向量：
? ??其中莲祸，ATTEND(·)表示輸出注意力分?jǐn)?shù)的函數(shù)蹂安，利用注意力分?jǐn)?shù)來聚合每個質(zhì)心的消息特征椭迎。本質(zhì)上公式9依舊使用的是QKV鍵值對的注意力機(jī)制。e‘u(l)和e’u(l)分別是第l層中用戶u和第i項的集群感知表示田盈。這些具有集群感知功能的表示緊湊地總結(jié)了所有用戶和項的拓?fù)湫畔⑾辣蹋渲邪藞D中的遠(yuǎn)程消息。
多頭非本地注意力機(jī)制
? ??作者通過使用多個OT頭進(jìn)一步改進(jìn)了GOTNet缠黍。作者將用戶的嵌入投影到H個單獨(dú)的子空間，即
药蜻，其中
是頭h的權(quán)重矩陣瓷式。于是，我們可以獲得H個集群感知的用戶表示
和項目表示
语泽，其中每個元素都使用等式 (9)進(jìn)行計算.然后贸典，將它們連接起來：
? ??其中，{踱卵、
}∈Rd分別是用戶u和項目i的多頭集群感知表示廊驼；{Wu，Wi}是學(xué)習(xí)到的權(quán)重矩陣惋砂，將用戶和項目的多頭注意力投射到d維空間妒挎。
本地與非本地混合注意力機(jī)制
? ??在等式（2）中的和
從鄰居那里收集本地消息，而等式（10）的
和
從質(zhì)心捕獲非本地消息西饵，作者進(jìn)一步介紹了通過使用混合技術(shù)來混合局部和非局部注意的想法：
? ?其中酝掩， ∈[0,1]是l跳混合系數(shù)，服從（0,1）均勻分布眷柔。
3.4 GOTNet的優(yōu)化
? ? GOTNet的總體目標(biāo)是：
? ? 其中期虾，β和γ為對應(yīng)的正則化系數(shù)。
????由于GOTNets建立在gnn之上驯嘱，而主要的網(wǎng)絡(luò)架構(gòu)保持不變镶苞，GOTNets是與模型無關(guān)的，可以無縫地應(yīng)用于任何gnn鞠评，如PinSage茂蚓、NGCF和LightGCN。事實(shí)上谢澈，如果我們簡單地在等式（12）中設(shè)置β=γ=0和在等式（11）中設(shè)置混合系數(shù)λ(l)=1煌贴，GOTNets本質(zhì)上等同于原始的gnn。
4 實(shí)驗
?????4.1 數(shù)據(jù)集
? ? 數(shù)據(jù)集采用Movielens-1M, Gowalla, Yelp-2018, and Amazon-Book
? ? 4.2 實(shí)驗結(jié)果
? ? 4.3 實(shí)驗分析
? ? 過平滑的影響：
? ??訓(xùn)練深度gnns時存在過平滑現(xiàn)象锥忿。為了說明這種影響牛郑，作者在{2、4敬鬓、6淹朋、8}范圍內(nèi)進(jìn)行了不同數(shù)量的L層的實(shí)驗笙各。圖3顯示了在NDCG@20方面的結(jié)果。我們觀察到础芍，在疊加2層或4層時達(dá)到峰值杈抢，但深度的增加會導(dǎo)致性能下降。相比之下仑性，非本地gnn(例如惶楼，Geom-GCN、NLGCN和GOTNet)繼續(xù)受益于更深層次的架構(gòu)诊杆。具體來說歼捐，GOTNet在所有數(shù)據(jù)集上都明顯優(yōu)于Geom-GCN和NLGCN。原因是GOTNet顯式地采用了局部和非局部聚合的混合晨汹，以防止所有節(jié)點(diǎn)表示收斂到相同的值豹储，即使是使用更深層次的結(jié)構(gòu)。此外淘这，我們的多頭投影允許用戶和項目在多個不同的空間中具有可區(qū)分的表示剥扣，這使得節(jié)點(diǎn)表示不那么相似，并緩解了過度平滑的問題铝穷。
稀疏推薦：
? ??如前所述钠怯，圖卷積本質(zhì)上是局部算子，這有利于高度節(jié)點(diǎn)從其鄰居那里收集足夠的信息氧骤。然而呻疹，許多真實(shí)世界的圖通常是長尾的和稀疏的，其中有相當(dāng)一部分節(jié)點(diǎn)具有較低的度筹陵。對于這些尾部節(jié)點(diǎn)刽锤，gnn只聚合來自少量鄰居的消息，這可能是有偏倚的或代表不足的朦佩。為此并思，GOTNet展現(xiàn)了了非局部gnn對稀疏建議的有效性。為此目的语稠，作者關(guān)注至少有5個交互宋彼，但少于10個交互的用戶和項目。表2顯示了Yelp和Amazon的結(jié)果仙畦。
參數(shù)設(shè)置實(shí)驗：
