圖是一種通用的數據表現形式，圖算法逐漸在大數據處理中展現其價值。網絡表征學習算法作為目前比較主流的一種圖數據處理算法，引起學術界和工業界的極大興趣。
本文介紹了 IEG 在網絡表征學習方面的一個自研學術成果，最近被國際頂級學術會議 13th ACM International Conference on Web Search and Data Mining (WSDM 2020) 接收為學術長文。個人始終認為并且堅持研究與業務是可以相輔相成的。因此，該技術起源于對游戲業務優化的需求，升華于對技術細節的精益求精。

背景

網絡表征學習算法將網絡中的每個節點映射為一個長度固定的向量，并且這個向量的長度遠遠小于網絡中節點數量。因此，網絡表征學習算法得到的節點向量可以作為大部分機器學習模型的輸入，從而能夠應用到各種業務中。比如，在某RPG游戲的好友召回活動中，采用網絡表征的算法比其他算法在回流率上相對提升了32.6%；在某MOBA游戲的師徒推薦功能中，采用網絡表征的算法比其他算法在點擊率上相對提升了4.48%。

網絡表征學習的算法主要有DeepWalk、node2vec和LINE。然而，這些算法采用了非凸優化技術來求解模型，比如隨機梯度下降算法（SGD）。但是，非凸優化技術的初始化對該技術的性能和效果都會產生較大的影響。如果選擇了不好的初始化值，可能會導致計算結果集中在不好的局部最優（local minima）上。

國際人工智能學術會議AAAI 2018有個技術HARP也是為了解決網絡表征學習初始化的問題。HARP采用多層次的網絡壓縮方法，容易將本應屬于兩個不同分區的節點合并為一個節點，比如網絡結構中橋（bridge）上的兩個節點，因此也不能很好地反映出網絡結構的整體特點。另外，多層次的計算需要較高的計算量，特別是當網絡結構比較大的時候。

為了克服上述問題和提高網絡表征學習算法的性能，我們提出了考慮網絡結構的基于圖分割的網絡表征學習初始化技術（Graph Partition Approach），簡稱為GPA。GPA技術先采用圖分割算法將網絡圖結構分割成若干區塊，接著將所得到的區塊當作抽象節點，于是構建了一個抽象網絡。最后通過計算抽象網絡的表征，從而得到原網絡的表征初始值。基于圖分割算法，抽象節點之間的邊具有最小分割邊數（minimal edge cut）的特點，因此可以更好地刻畫網絡的整體結構。另外，基于圖分割的技術不需要多層次的計算方式，可以減少計算量。

在多個實驗中，驗證了GPA可以明顯地提高網絡表征學習算法的效率和性能。具體來說，鏈路預測任務上相對于采用HARP技術初始化的方案提升了7.76%，在節點分類任務上則相對提升了8.74%。另外，在運行時間上，GPA也相對HARP減少了至少20%。

此外，我們還在一些游戲場景中驗證了GPA技術對線上業務效果的提升作用。比如，在某類游戲的回流激勵活動中，相對于無特殊初始化的方案，采用GPA技術的網絡表征學習算法在點擊率上相對提升了1.83%，在回流率上相對提升了6.43%。

2. 算法簡述

本技術方案GPA采用四個步驟來生成網絡的表征初始值，如圖1所示。首先，GPA利用圖分割算法將網絡圖結構分割成若干區塊。然后基于分割區塊，構建抽象網絡，其大小將遠遠小于原始網絡結構大小。在構建抽象網絡時，我們把每個區塊表示為一個節點（稱為抽象節點），把區塊之間的邊合并成一條邊（稱為抽象邊）。接著，我們采用網絡表征學習算法計算抽象網絡的每個抽象節點的節點向量。最后，基于傳播算法，我們將抽象節點的節點向量傳回該節點所表示的原網絡結構里的節點，從而計算得到原網絡結構里每個節點的節點向量的初始值。

圖 1：基于圖分割的網絡表征學習初始化技術

在計算抽象網絡的表征時，需要通過設置特定的超參數來運行網絡表征學習算法，比如node2vec的超參數包括隨機游走路徑的長度和個數。這些超參數往往對模型和算法的性能起到了關鍵性的作用。然而，現有的網絡表征學習算法沒有提出如何快速地尋找合適的超參數，并且傳統的超參數選擇方法（比如網格搜索）具有較高的運行代價。因此，本技術方案還包括一個基于圖屬性和回歸模型的超參數選擇方法，如圖2所示。

圖 2：基于圖屬性和回歸模型的網絡表征學習算法超參數選取技術

更多技術細節請看提前發布的論文：https://arxiv.org/abs/1908.10697

3. 相關成果

3.1 業務效果

我們將本技術GPA應用在游戲的多個業務場景中，從而提升相關業務的效果。比如在某類游戲的好友召回活動中，我們需要為每個活躍玩家計算一個長度有限（比如10個）的推薦列表。每個活躍玩家的推薦列表上是流失玩家，并且是該玩家的好友。也就是說，好友召回活動是使用活躍玩家去召回流失玩家。基于本技術方案GPA，我們首先計算該游戲的社交網絡上每個玩家的節點向量初始值，然后把這個初始值輸入到node2vec算法中，得到玩家最終的節點表征向量。基于節點向量，我們計算活躍玩家與流失玩家之間的歐式距離相似度。然后，按歐式距離相似度，從小到大依次排序，從而得到每個活躍玩家的推薦列表。基于A/B test的評測方法，相對于無特殊初始化的方案，以及其他算法（比如Personalized PageRank），采用GPA技術的網絡表征學習算法在點擊率上相對提升了1.83%，在回流率上相對提升了6.43%。

3.2 論文

• Wenqing Lin, Feng He, Faqiang Zhang, Xu Cheng, Hongyun Cai.

  Initialization for Network Embedding: A Graph Partition Approach.

• Proceedings of the 13th ACM International Conference on Web Search and Data Mining (WSDM), full research paper, 2020.

WSDM是數據挖掘和分析領域成長較快的國際頂級學術會議，通常讀作“wisdom”。如圖3所示，在Google Scholar上的學術會議和期刊影響力排名中，WSDM在數據挖掘領域和數據庫領域分別排名第4和第6。明年會議WSDM 2020的網址是?http://wsdm-conference.org/2020/。

圖 3：Google Scholar上與數據挖掘相關的學術會議和期刊影響力排名

3.3 專利

• 《網絡表征學習的初始化技術》，申請號：201910309766.0

  《網絡表征學習的超參數選取方法》，申請號：201910220752.1

• 《提升網絡表征學習算法性能的數據壓縮技術》，申請號：201910557086.0

你可能還喜歡

總結

以上是生活随笔為你收集整理的腾讯游戏自研学术成果：基于图分割的网络表征学习初始化技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。