提高復(fù)雜網(wǎng)絡(luò)分析效率！中國(guó)科學(xué)家研發(fā)強(qiáng)化學(xué)習(xí)新框架

近日，中國(guó)國(guó)防科技大學(xué)、美國(guó)加州大學(xué)洛杉磯分校和哈佛醫(yī)學(xué)院的研究人員研發(fā)了一個(gè)深度強(qiáng)化學(xué)習(xí)框架FINDER。相比于現(xiàn)有的解決方案，F(xiàn)INDER能夠更快速、更高效地找到復(fù)雜網(wǎng)絡(luò)中一組最關(guān)鍵的節(jié)點(diǎn)，進(jìn)而使復(fù)雜網(wǎng)絡(luò)以較高的效率運(yùn)行。

這項(xiàng)研究發(fā)表在國(guó)際期刊《自然》旗下的《自然–機(jī)器智能》上，論文標(biāo)題為《用深度強(qiáng)化學(xué)習(xí)找到復(fù)雜網(wǎng)絡(luò)的關(guān)鍵參與者（Finding key players in complex networks through deep reinforcement learning）》。

論文鏈接：
https://www.nature.com/articles/s42256-020-0177-2

一、FINDER：適用場(chǎng)景更廣泛，運(yùn)行速度快出幾個(gè)數(shù)量級(jí)

在物理科學(xué)、信息科學(xué)、生物科學(xué)等領(lǐng)域的研究中，研究人員可以通過(guò)建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)模擬實(shí)際情況、進(jìn)而作出預(yù)測(cè)。

在這類復(fù)雜網(wǎng)絡(luò)的運(yùn)行過(guò)程中，節(jié)點(diǎn)間的配合直接決定了復(fù)雜網(wǎng)絡(luò)運(yùn)行的效率。當(dāng)被用于解決NP難題（NP-hard）時(shí)，復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的“分工協(xié)作”尤其重要。

NP難題指的是在多項(xiàng)式時(shí)間內(nèi)可以被驗(yàn)證其正確性的問(wèn)題。比如，在疫情防控領(lǐng)域，復(fù)雜網(wǎng)絡(luò)模型可以模擬出疫情傳播情況、幫助找到疫苗藥物分子等。運(yùn)行這些任務(wù)時(shí)，復(fù)雜網(wǎng)絡(luò)要推演和驗(yàn)證病毒是否會(huì)傳染給下一個(gè)人、某種藥物分子是否有效的各種情況。在這個(gè)過(guò)程中，找到最關(guān)鍵的節(jié)點(diǎn)能夠提升復(fù)雜網(wǎng)絡(luò)的運(yùn)行效率。

對(duì)于這類問(wèn)題，現(xiàn)有的解決方案通?；诖笮途W(wǎng)絡(luò)進(jìn)行訓(xùn)練、針對(duì)特定場(chǎng)景提出策略，但缺乏統(tǒng)一的框架。相比之下，中國(guó)國(guó)防科技大學(xué)、加州大學(xué)洛杉磯分校、哈佛醫(yī)學(xué)院的研究人員提出的FINDER可以應(yīng)用于廣泛的復(fù)雜網(wǎng)絡(luò)場(chǎng)景，其運(yùn)行速度快了幾個(gè)數(shù)量級(jí)。

二、分兩階段進(jìn)行訓(xùn)練，分別采用不同獎(jiǎng)勵(lì)函數(shù)

FINDER框架采用純數(shù)據(jù)驅(qū)動(dòng)的方法，分兩個(gè)階段進(jìn)行訓(xùn)練。在兩個(gè)階段中，研究人員用不同的獎(jiǎng)勵(lì)函數(shù)來(lái)訓(xùn)練FINDER。

第一階段用經(jīng)典模型生成的小型合成網(wǎng)絡(luò)對(duì)FINDER進(jìn)行離線訓(xùn)練。離線訓(xùn)練采用?-greedy策略。

離線訓(xùn)練階段分三步進(jìn)行：首先，研究人員生成一批合成圖形；然后，研究人員從合成圖形中任意取樣一個(gè)圖形；接下來(lái)，F(xiàn)INDER框架在這一圖形上進(jìn)行整個(gè)尋找關(guān)鍵節(jié)點(diǎn)的流程。這一流程中，代理與圖形通過(guò)一系列狀態(tài)、動(dòng)作、激勵(lì)進(jìn)行交互。

為了確定狀態(tài)的正確動(dòng)作，代理先在當(dāng)前的圖形上編碼，并獲取每個(gè)節(jié)點(diǎn)的嵌入向量。節(jié)點(diǎn)的嵌入向量會(huì)捕獲節(jié)點(diǎn)的結(jié)構(gòu)信息和節(jié)點(diǎn)特征之間的長(zhǎng)程相互作用（long-range interaction）。接下來(lái)，代理將嵌入向量解碼為標(biāo)量Q值，以便所有節(jié)點(diǎn)能夠預(yù)測(cè)部署某個(gè)動(dòng)作的長(zhǎng)程增益。

▲離線訓(xùn)練階段示意圖

一旦離線訓(xùn)練結(jié)束，F(xiàn)INDER就進(jìn)入第二個(gè)訓(xùn)練階段，被應(yīng)用于真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中。研究人員在浣熊接觸網(wǎng)絡(luò)（the raccoon contact network）的最大連通元件（connected component）上進(jìn)行測(cè)試。最大連通元件包括14個(gè)節(jié)點(diǎn)和20條邊。

這一階段中，代理首先將當(dāng)前網(wǎng)絡(luò)編碼為低維嵌入向量，然后利用這些向量對(duì)每個(gè)節(jié)點(diǎn)的Q值進(jìn)行解碼。

第二階段采用“批量節(jié)點(diǎn)選擇（batch nodes selection）”策略。該策略在每個(gè)自適應(yīng)步驟中選擇一個(gè)有限分?jǐn)?shù)的最高Q節(jié)點(diǎn)，避免了對(duì)嵌入向量和Q值的逐個(gè)迭代選擇和重新計(jì)算。批量節(jié)點(diǎn)選擇策略不會(huì)影響最終的結(jié)果，但可以降低幾個(gè)數(shù)量級(jí)的時(shí)間復(fù)雜度。

研究人員會(huì)重復(fù)這個(gè)過(guò)程，直到復(fù)雜網(wǎng)絡(luò)達(dá)到用戶定義的終端狀態(tài)、被移除的節(jié)點(diǎn)構(gòu)成最優(yōu)的節(jié)點(diǎn)集合。

▲用真實(shí)復(fù)雜網(wǎng)絡(luò)進(jìn)行訓(xùn)練示意圖

三、對(duì)比3個(gè)模型性能，F(xiàn)INDER找出關(guān)鍵節(jié)點(diǎn)的效率最高

相比于機(jī)器人等傳統(tǒng)的強(qiáng)化學(xué)習(xí)技術(shù)（狀態(tài)和動(dòng)作較為簡(jiǎn)單），復(fù)雜網(wǎng)絡(luò)技術(shù)更加復(fù)雜和難以表示。研究團(tuán)隊(duì)高級(jí)研究員孫怡舟稱，這是因?yàn)閺?fù)雜網(wǎng)絡(luò)具有離散的數(shù)據(jù)結(jié)構(gòu)和處于極其高維的空間。

本項(xiàng)研究中，研究人員用圖神經(jīng)網(wǎng)絡(luò)（GNN）來(lái)解決這個(gè)問(wèn)題。圖神經(jīng)網(wǎng)絡(luò)中的節(jié)點(diǎn)代表動(dòng)作、圖形代表狀態(tài)。

以911恐怖襲擊事件發(fā)生預(yù)測(cè)網(wǎng)絡(luò)為例，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)代表參與911恐襲的恐怖分子、每個(gè)邊（edge）代表他們的社會(huì)交流。

研究人員在911恐怖襲擊事件發(fā)生預(yù)測(cè)網(wǎng)絡(luò)上運(yùn)行FINDER框架，并運(yùn)行現(xiàn)有的高維（HD）方法和集體影響（CI）方法做對(duì)比。

下圖d顯示了三種方法的ANC曲線。在框架部署動(dòng)作后，剩余節(jié)點(diǎn)的重要性越低，代表框架性能越好。

可以看到，F(xiàn)INDER框架最有效地找到了復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)。相比于其他兩個(gè)解決方案，隨著被移除節(jié)點(diǎn)的重要性升高，運(yùn)行FINDER框架的復(fù)雜網(wǎng)絡(luò)中剩余的節(jié)點(diǎn)重要性最低。

▲911恐怖襲擊事件發(fā)生預(yù)測(cè)網(wǎng)絡(luò)（藍(lán)色點(diǎn)代表剩余圖形中的節(jié)點(diǎn)，紅色點(diǎn)代表當(dāng)前時(shí)間步長(zhǎng)中FINDER找出的關(guān)鍵節(jié)點(diǎn)，灰色點(diǎn)代表剩余的孤立節(jié)點(diǎn)）

結(jié)語(yǔ)：未來(lái)將可用于更多類型復(fù)雜網(wǎng)絡(luò)

FINDER框架通過(guò)深度強(qiáng)化學(xué)習(xí)方法進(jìn)行訓(xùn)練，可以找到復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。在未來(lái)，F(xiàn)INDER框架或可被用于優(yōu)化社交網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、傳染病蔓延網(wǎng)絡(luò)等模型的性能。

目前，加州大學(xué)洛杉磯分校的研究團(tuán)隊(duì)正計(jì)劃將FINDER框架用于網(wǎng)絡(luò)科學(xué)研究。哈佛醫(yī)學(xué)院的團(tuán)隊(duì)希望將FINDER用于生物網(wǎng)絡(luò)，以確定蛋白質(zhì)交互網(wǎng)絡(luò)和基因調(diào)控網(wǎng)絡(luò)中的關(guān)鍵參與者。

另外，研究人員稱未來(lái)將從以下三方面著手，提升框架尋找關(guān)鍵節(jié)點(diǎn)的性能：設(shè)計(jì)出更好的圖形表示學(xué)習(xí)架構(gòu)；探索如何在跨圖形甚至跨域轉(zhuǎn)移知識(shí)；研究并解決復(fù)雜網(wǎng)絡(luò)上的其他NP難題。