今天給大家介紹哈佛大學Yang-Yu Liu課題組和加利福尼亞大學洛杉矶分校Yizhou Sun課題組發表在nature machine intelligence上的一篇文章“Finding key players in complex networks through deep reinforcement learning”，作者提出一種基于深度強化學習架構FINDER來尋找一組能對網絡功能産生最大影響的關鍵節點序列。
1
研究背景
尋找網絡中一組最優節點集合是網絡科學中的重要課題。删除（增添）一部分重要的節點能極大減弱（增強）網絡的連通性，進而影響網絡的功能，利用這一特性，可以高效地破壞網絡結構，也可以設計出對于攻擊或者擾動表現出更優魯棒性的網絡。傳統方法難以兼顧效率和性能，且大多數隻針對特定的場景。得益于近年來深度學習在組合優化問題的發展，Fan Changjun等提出了一種基于深度強化學習的方法來尋找網絡中的關鍵節點序列。
2
研究方法
整個深度學習過程的目的：使累積歸一化的連通性ANC最小。對于節點無權值的網絡，作者定義ANC為：
critical node（CN）問題中，被定義為
其中為原網絡的節點個數，為第塊連通塊的大小（節點個數），為原網絡的連通性，為從原網絡中移除節點序列後的連通性。網絡分解問題(ND)中，被定義為，即極大連通子圖的大小。對于有些問題，節點被配置設定了不同的權值，ANC被重新定義為：
其中為節點移除後損失系數，且
整個深度強化學習過程中，将移除節點後的殘餘網絡定義為狀态，決策為移除（或激活）已經确定的關鍵節點，收益為累積歸一化連通性的衰減。具體的深度學習過程主要包括以下四個步驟：
(1) 編碼
編碼的目的是利用基于神經網絡的圖表征學習，将網絡的結構資訊轉化為低維嵌入向量。具體做法是采用一種類似于GraphSAGE的歸納式圖表征學習方法來聚合節點嵌入向量，這些向量被初始化為該節點的鄰居的特征（如度，移除代價），接着通過一個附帶可學習參數的非線性算子轉換,将網絡節點資訊聚合K次，可以将其視為K次神經網絡，目前層節點的嵌入向量由上一層該節點以及它鄰居的嵌入向量獲得，最後一層為輸出層，即得到關于每個節點的嵌入向量，這些向量包含了節點的結構位置以及節點特征間的長期互動作用資訊。
為了得到網絡更為複雜的資訊，引入一個虛拟節點，該節點以網絡中所有真實節點為鄰居，而這些真實節點的鄰居不包含該虛拟節點。重複上面的圖表征學習方法，得到該節點的嵌入向量。
（2）解碼
在解碼過程中，作者定義一個評分函數Q function, 利用編碼過程得到狀态和決策的嵌入資訊，計算出一個關于節點的得分Q來評價可能的決策的優劣。根據得分Q采取貪心政策，具體做法是以機率選中Q值最大的節點，以1-的機率随機選擇其他節點。作者在實驗過程中實際采取的政策是以機率選擇Q值最大的前k個節點，以微小的精度損失來減小時間複雜度。
當殘餘網絡隻包含孤立節點，收集n步轉移資訊，即4元組并将它們存入經驗回放緩沖區，執行貪心政策50000次，同時更新參數。
（3）訓練模型
該過程是為了得到合适的參數。作者定了損失函數如下：
其中,,為在經驗回收緩沖區采樣得到關于未來收益更為精确的值，表示折扣因子，為更新後的網絡參數，表示節點有連邊，為節點的嵌入向量，為原始網絡的節點數，函數包含兩部分：1. Q-learning loss使預測值和目标值誤差最小；2. 在嵌入空間中，Graph reconstruction loss用來保留原始網絡結構。實驗中作者采用30-50個節點的BA網絡模型，進行大量訓練，最終使以上損失函數的值最小。
（4） 應用
将訓練好的模型用于合成網絡和真實網絡，這個過程中為了減小時間複雜度，作者每次移除一部分節點而不是每次移除一個。實驗最終發現：移除網絡1%的節點對網絡的性能幾乎沒有影響。
3
資料
作者将訓練的模型分别用于兩類網絡資料集：1. 人工生成的網絡不同規模的BA網絡各100個，節點個數分為為30-50,50-100，100-200,200-300,300-400以及400-500。2. 真實網絡：Crime,HI-II-14,Digg,Enron,Gnutella31,Epinions,Facebook,Youtobe，Flickr,具體資訊如下：
4
實驗
對于人工生成三類網絡資料：節點無權值網絡，節點權值與度成比例的網絡以及随機節點權值網絡，針對關鍵節點(CN)和網絡分解(ND)兩個問題，作者将提出FINDER架構與其他方法進行比較，最終得出結論：在節點權值分布不同的網絡中，無論是CN問題還是ND問題，FINDER始終優于其他方法。具體表現為采用FINDER方法移除相同百分比的節點，對網絡的連通性破壞更嚴重。
對于真實網絡，節點都是無權的，為了改變節點權值，作者采取了兩種政策：1. 将與度成比例非負數賦予節點獲得node-degree網絡，2. 随機将權值賦予節點獲得node-random-weight網絡。依然針對CN問題和ND問題，作者将FINDER方法與其他方法進行對比，下圖顯示，移除相同比例的節點，FINDER能更大程度破壞這些真實網絡的連通性，圖表示随着移除節點的比例變化，網絡的連通性的變化。對于CN問題，網絡連通性表示為
對于ND問題，連通性為
對于不同的情況（網絡權值分布差異，CN與ND問題的不同），FINDER優于其他方法。特别地，對于節點權值不同的網絡，即 node-degree-weight以及node-random-weight網絡，FINDER應用後的表現遠遠超過其他方法。如圖k中，為了實作網絡連通性衰減為50%，其他方法需要移除整個網絡中超40%的節點，應用FINDER則隻需要移除大約14%的節點，即實作對網絡相同的破壞效果 ，FINDER方法更為高效。
FINDER性能分析
當網絡節點權值存在差異時，FINDER在尋找關鍵節點時性能遠勝過其他方法。為了探究其原因，作者在真實網絡crime中給節點随機配置設定權值（節點移除的代價），并繪制出不同方法尋找到的關鍵節點的代價分布直方圖，從圖中可以看到：無論是CN問題還是ND問題，FINDER尋找出的關鍵節點往往移除代價較小，進而能夠實作一種更為高效的節點移除政策。
5
結論
作者提出了一種深度強化學習架構FINDER，該方法隻采用小規模的BA網絡進行訓練，而将它應用于尋找大型真實網絡的關鍵節點時，無論在效率還是性能上都表現優異。針對不同的網絡問題，依據定義的連通性度量方式選擇對應獎勵機制即可。FINDER的表現展現了BA網絡模型的應用價值，加深了深度學習技術與複雜網絡的融合。應用FINDER也有助于設計出魯棒性更強的網絡系統。