KDD'22：能屈能伸大不同——自放縮圖神經網絡及其應用

社交推薦（Friend Recommendation）逐漸成為許多線上社交平臺的一項重要業務。近年來，相較于淺層的圖嵌入模型，圖神經網絡（Graph Neural Networks, GNNs）在社交推薦中表現出了優秀的性能，這主要歸功于GNN顯式聚合鄰居節點信息的操作。然而，現有的許多GNN在鄰居聚合時使用了靜態的、事先手工設定的歸一化權重，這將導致模型難以對嵌入向量的尺度做出適應性的調整，從而產生“尺度扭曲”問題。

為了克服這一問題，我們提出了一種簡單而有效的GNN嵌入向量尺度自適應調整方法。該方法通過一個自放縮網絡（self-rescaling network，SSNet）來為GNN模型輸出的每個嵌入向量生成一個對應的標量放縮系數，進而對嵌入向量的尺度進行放縮調整。SSNet非常輕量，僅由一個兩層的感知機構成，同時，SSNet也與模型無關，可以施加在現有的多種GNN模型上進行端到端的訓練。實驗中，我們在七種現有GNN模型和三個大規模社交網絡數據集上驗證了SSNet的有效性。此外，我們在Xbox社交推薦平臺進行了為期一個月的在線A/B測試，并觀察到SSNet模型在“添加推薦朋友”這一用戶行為統計上帶來了24%的性能提升。

為了促進社交推薦領域研究與應用的發展，我們還對社交推薦中的一些關鍵問題進行了觀察分析。我們觀察到，基于網絡規則的模型與圖嵌入模型能夠分別從不同的角度進行目標召回；相較于基于網絡規則的模型，圖嵌入模型能夠顯著改善過濾氣泡問題（Filter Bubble）和回聲室效應（Echo Chamber）；將兩類模型的特征輸入決策樹模型進行集成，能夠形成一個更加完備的線上預測方法--這一策略目前已被應用在Xbox游戲社交平臺的社交推薦中。

該成果“Friend Recommendations with Self-Rescaling Graph Neural Networks”發表于第28屆ACM SIGKDD知識發現與數據挖掘大會上（KDD’22），KDD是數據挖掘領域的頂級會議之一，是中國計算機學會（CCF）推薦的A類會議。

• 論文鏈接：
• https://dl.acm.org/doi/10.1145/3534678.3539192

背景與動機

線上社交平臺正在逐漸融入并充實著我們的日常生活。例如，我們通過Facebook或TikTok與朋友分享個人生活；我們在LinkedIn上建立自己的職業網絡；我們在Xbox上和朋友一起享受游戲。隨著線上社交網絡（Online Social Network）規模的不斷增長，社交推薦（Friend Recommendation）逐漸成為許多平臺的一項重要業務。傳統的社交推薦方法主要基于手工設計的規則來表征社交網絡中兩個節點的接近度，例如Common Neighbors (CN)、Local Naive Bayes based Common Neighbors (BCN), 和Personalized PageRank (PPR)。這些方法的主要缺點有：（1）手工設計的規則只能刻畫社交網絡中有限的特征，并不全面；（2）一些規則，如BCN和PPR，需要一對節點的高階網絡信息，難以拓展到實時的推薦業務中；（3）推薦節點通常集中在源節點的較近鄰域，這些鄰域高度同質化，加劇了過濾氣泡問題（Filter Bubble）和回聲室效應（Echo Chamber）。

近年來，相較于淺層的圖嵌入模型，圖神經網絡（Graph Neural Networks, GNNs）在社交推薦中表現出了優秀的性能，這主要歸功于GNN顯式聚合鄰居節點信息的操作。然而，我們觀察到現有的許多GNN在鄰居聚合時使用了靜態的、事先手工設定的歸一化權重。例如，LightGCN使用了一種加權求和的鄰居聚合操作：。其中的權重固定為，基于節點的度計算得到。PPRGo的鄰居聚合基于節點的PPR得分：，其中是PPR得分向量。這種靜態的、基于手工設定的方式難以對嵌入向量的尺度做出適應性的調整，將產生“尺度扭曲”問題（我們以LightGCN為例分析了兩個具體的尺度扭曲案例，詳情參見論文2.3節）。

模型設計

為了克服這一問題，我們提出了一種簡單有效的GNN嵌入向量尺度自適應調整框架，可以施加在現有的多種GNN模型上進行端到端的訓練。該方法通過一個自放縮網絡（self-rescaling network，SSNet）來為GNN模型輸出的每個嵌入向量生成一個對應的標量放縮系數，進而對嵌入向量的尺度進行放縮調整，如圖1（a）所示。具體地，給定GNN模型輸出的嵌入向量z，SSNet通過一個輕量的兩層感知機生成一個標量放縮系數：。該系數G(z)將用于調整嵌入向量z的尺度，生成調整后的嵌入向量：。

我們考慮了三種SSNet結構上的變體，如圖1（b-d）所示，分別為：L2歸一化（L2 Normalization）、前饋網絡（Feed-Forward Net）和加性網絡（Additive Network）。實驗結果表明，這些變體的性能均無法超過SSNet。除了端到端（End-to-End Training）的訓練方式外，我們還設計了其它兩種SSNet訓練方式，分別為：預訓練加微調（Pretrain-then-Finetune）和對抗訓練（Adversarial Training）。在預訓練加微調的方式中，我們首先訓練得到一個GNN模型，再固定該模型的參數并訓練SSNet網絡。在對抗訓練的方式中，我們使用一個鑒別器嘗試根據嵌入向量推測節點的度，而GNN和SSNet不僅要優化社交推薦的損失函數，還要設法降低鑒別器的準確性，從而弱化節點的度對嵌入向量尺度的影響。實驗表明，三種訓練方式的效果相近，簡單的端到端訓練就能得到最佳的性能。

圖1 SSNet模型（a）與其它三種變體（b-d）

理論方面，我們從譜分析和圖同構兩個視角進行了討論。譜分析視角下，從卷積核參數數量來看，SpectralCNN傾向于使用了過多的參數，LightGCN則傾向于使用了過少的參數，SSNet則是一種介于兩者之間的適中的參數化方式。從圖同構的角度來看，GIN提出在卷積層中使用MLP來學得一個和Weisfeiler-Lehman圖同構測試能力相當的GNN模型。然而在我們的社交推薦場景下，簡化的卷積層（如LighGCN和PPRGo）往往表現出更好的性能。SSNet則在模型的輸出端增加一個自放縮網絡，能夠結合GIN模型與諸如LightGCN等簡化GNN模型各自的優勢。

實驗結果

實驗中，我們在七種現有GNN模型（GraphSAGE、GIN、GAT、SAGN、FAGCN、LightGCN和PPRGo），三個大規模社交網絡數據集（Pokec、LiveJournal和Xbox）,以及兩大推薦任務（目標召回和目標排序）上進行了模型性能評估。如表1和表2所示，我們觀察到SSNet能顯著提升多種GNN模型的性能。

我們在Xbox社交推薦平臺進行了為期一個月的在線A/B測試，覆蓋了美國市場上約10%的主要流量。我們觀察到SSNet模型在“添加推薦朋友”這一用戶行為統計上帶來了24%的性能提升。此外，在高質量朋友推薦的推動下，我們觀察到了一些連鎖反應，包括“瀏覽用戶資料”行為的267%的提升，“搜索玩家”行為的89%的提升等。

表1 SSNet在目標召回任務上的實驗結果（“SS”表示施加了SSNet）。表格中標亮了SSNet獲得提升的情形。

表2 SSNet在目標排序任務上的實驗結果（“SS”表示施加了SSNet）。表格中標亮了SSNet獲得提升的情形。

為了進一步推動社交推薦領域研究與應用的發展，我們還對其中的一些關鍵問題進行了經驗結果的分享：

1、稠密檢索（Dense Retrieval）與基于規則的檢索（Rule-based Retrieval）。作為一種稠密檢索方法，結合ANN算法的嵌入模型已被廣泛地應用于目標召回任務中。盡管有著諸如自動編碼圖結構信息的優越性，我們發現在目標召回階段，圖嵌入是基于規則的方法的一種補充，而不是其替代品。從圖2（a）可以看出，圖嵌入的得分差于CN和PPR。然而圖2（b）表明，不同的召回方法捕捉了不同方面的候選者。例如，PPR和PPRGo（SSNet）的top-100推薦里僅有8%重疊。從這個意義上說，各種不同的檢索方法可以相互補充，從而共同構成一個全面和多樣的檢索機制。

圖2 Xbox數據集上不同召回方法的比較

2、過濾氣泡問題（Filter Bubble）與回聲室效應（Echo Chamber）。研究表明，基于規則的方法可能造成過濾氣泡問題或回音室效應，這意味著用戶的社交圈變得越來越同質化和狹窄，不利于社交網絡的長期發展。圖3比較了PPR和PPRGo（SSNet）的top-k推薦相對于源節點的距離分布。可見PPR的大部分推薦節點都位于源節點的自我中心網絡（Ego Network）附近，如1跳距離和2跳距離的鄰居。相比之下，圖嵌入方法的推薦結果對網絡有更廣泛的覆蓋。

圖3 Xbox數據集上top-k推薦相對于源節點的距離分布

3、線上推薦模型。Xbox游戲社交平臺的線上推薦方法基于決策樹（Decision Tree）模型。輸入決策樹的特征包括：（1）若干簡單的網絡特征，例如節點的度和CN；（2）圖嵌入特征，即源節點與目標節點的圖嵌入向量的點乘得分。決策樹能夠結合不同的檢索方法，從而形成一個更加全面的推薦模型。并且決策樹具有良好的可解釋性，可以量化輸出不同特征的重要程度。我們的實驗表明，在所有輸入特征中，圖嵌入特征貢獻了65%的重要程度，并且能夠帶來20.7%的NDCG指標提升。

詳細內容請參見：

Xiran Song, Jianxun Lian, Hong Huang, Mingqi Wu, Hai Jin, and Xing Xie. 2022. Friend Recommendations with Self-Rescaling Graph Neural Networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '22). Association for Computing Machinery, New York, NY, USA, 3909–3919. https://doi.org/10.1145/3534678.3539192