摘要

面對(duì)疫情防控、關(guān)鍵基礎(chǔ)設(shè)施保護(hù)、交通電網(wǎng)安全乃至現(xiàn)代戰(zhàn)爭(zhēng)中的網(wǎng)絡(luò)攻防轉(zhuǎn)換等現(xiàn)實(shí)挑戰(zhàn)，如何高效識(shí)別并拆除異質(zhì)多層網(wǎng)絡(luò)中的“關(guān)鍵節(jié)點(diǎn)”已成為網(wǎng)絡(luò)科學(xué)領(lǐng)域的核心難題。傳統(tǒng)方法大多依賴中心性等啟發(fā)式指標(biāo)，難以全面刻畫異質(zhì)節(jié)點(diǎn)之間復(fù)雜而多變的交互關(guān)系，導(dǎo)致拆解效率低、泛化能力差，難以滿足現(xiàn)實(shí)復(fù)雜系統(tǒng)中大規(guī)模、多層次、多樣化網(wǎng)絡(luò)結(jié)構(gòu)的實(shí)際需求。近日，集智社區(qū)科學(xué)家，北京化工大學(xué)谷偉偉副教授帶領(lǐng)本科生楊宸和李磊創(chuàng)新性地提出MultiDismantler算法，相關(guān)成果發(fā)表在Nature Machine Intelligence。算法融合了圖神經(jīng)網(wǎng)絡(luò)與深度強(qiáng)化學(xué)習(xí)優(yōu)勢(shì)，實(shí)現(xiàn)對(duì)多層異質(zhì)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的高效識(shí)別與動(dòng)態(tài)瓦解，在復(fù)雜系統(tǒng)的智能拆解與安全防護(hù)領(lǐng)域填補(bǔ)了關(guān)鍵空白，推動(dòng)網(wǎng)絡(luò)干預(yù)智能化向前邁出重要一步。

關(guān)鍵詞：網(wǎng)絡(luò)瓦解，異質(zhì)網(wǎng)神經(jīng)網(wǎng)絡(luò)，深度強(qiáng)化學(xué)習(xí)，級(jí)聯(lián)失效

楊宸，谷偉偉丨作者

論文題目：Deep-learning-aided dismantling of interdependent networks 論文來源：Nature Machine Intelligence 論文鏈接：https://www.nature.com/articles/s42256-025-01070-2

一、研究背景：多層網(wǎng)絡(luò)瓦解的挑戰(zhàn)與突破

網(wǎng)絡(luò)結(jié)構(gòu)被廣泛應(yīng)用于描述自然與人造系統(tǒng)中的復(fù)雜交互關(guān)系，例如氣候網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)以及基礎(chǔ)設(shè)施網(wǎng)絡(luò)等。這些復(fù)雜網(wǎng)絡(luò)普遍呈現(xiàn)出高度異質(zhì)的結(jié)構(gòu)特性，系統(tǒng)的整體連通性往往依賴于少數(shù)關(guān)鍵節(jié)點(diǎn)。識(shí)別并移除這些關(guān)鍵節(jié)點(diǎn)，以最小代價(jià)將網(wǎng)絡(luò)瓦解為多個(gè)小規(guī)模、互不連通的子圖，被稱為網(wǎng)絡(luò)瓦解問題（network dismantling problem）。

網(wǎng)絡(luò)瓦解問題在眾多現(xiàn)實(shí)場(chǎng)景中具有重要意義。例如：在藥物設(shè)計(jì)中，有選擇性地抑制關(guān)鍵蛋白質(zhì)以阻斷病理過程；在基礎(chǔ)設(shè)施網(wǎng)絡(luò)中，識(shí)別并加固關(guān)鍵節(jié)點(diǎn)以提升系統(tǒng)穩(wěn)健性；在傳染病防控中，通過優(yōu)先接種關(guān)鍵個(gè)體來高效阻斷病毒傳播路徑。盡管網(wǎng)絡(luò)瓦解是一個(gè)基礎(chǔ)而關(guān)鍵的優(yōu)化問題，但其本質(zhì)屬于 NP-hard 問題，精確求解僅適用于小規(guī)模網(wǎng)絡(luò)。為此，研究者們提出了多種啟發(fā)式算法，如基于中心性指標(biāo)的 HDA（High Degree Adaptive）、CI（Collective Influence）、MinSum（Minimum Sum Influence） 等方法。這類方法具備較高的計(jì)算效率，但通常難以獲得全局最優(yōu)解，且泛化能力有限。

近年來，機(jī)器學(xué)習(xí)方法逐漸被引入網(wǎng)絡(luò)瓦解研究中。例如，GDM 和 NIRM 通過在小型合成網(wǎng)絡(luò)上學(xué)習(xí)近似最優(yōu)策略，嘗試實(shí)現(xiàn)對(duì)更大規(guī)模網(wǎng)絡(luò)的泛化；FINDER 則采用深度強(qiáng)化學(xué)習(xí)框架，通過與網(wǎng)絡(luò)環(huán)境的交互過程自主學(xué)習(xí)瓦解策略，擺脫了對(duì)人工標(biāo)簽的依賴。這些方法在大規(guī)模網(wǎng)絡(luò)上的初步應(yīng)用展現(xiàn)出一定成效，但主要仍局限于單層網(wǎng)絡(luò)的瓦解場(chǎng)景。

針對(duì)這一局限性，本文聚焦于多層異質(zhì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別難題，提出了一種融合異質(zhì)圖神經(jīng)網(wǎng)絡(luò)表示學(xué)習(xí)與深度強(qiáng)化學(xué)習(xí)優(yōu)化策略的智能瓦解框架——MultiDismantler。該方法基于幾何多層模型構(gòu)建大規(guī)模訓(xùn)練數(shù)據(jù)集，并引入跨層注意力機(jī)制與 DQN 學(xué)習(xí)機(jī)制，實(shí)現(xiàn)對(duì)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)及其層間依賴關(guān)系的高效建模與策略優(yōu)化。實(shí)驗(yàn)結(jié)果表明，MultiDismantler 在單層及多層網(wǎng)絡(luò)的瓦解任務(wù)中均顯著優(yōu)于現(xiàn)有主流算法，作為首個(gè)深度學(xué)習(xí)驅(qū)動(dòng)的多層網(wǎng)絡(luò)瓦解方法，具備重要的理論價(jià)值與現(xiàn)實(shí)應(yīng)用前景。

2. 方法概述：MultiDismantler框架

現(xiàn)實(shí)中的許多復(fù)雜系統(tǒng)，如社會(huì)網(wǎng)絡(luò)、電力交通系統(tǒng)或蛋白質(zhì)調(diào)控網(wǎng)絡(luò)，并非由單一層次的交互構(gòu)成，而是呈現(xiàn)出多層相互依賴結(jié)構(gòu)（multi-layer interdependent networks）。在這樣的系統(tǒng)中，一個(gè)節(jié)點(diǎn)在一層中的故障可能通過跨層依賴關(guān)系引發(fā)連鎖反應(yīng)，最終導(dǎo)致整個(gè)系統(tǒng)的級(jí)聯(lián)崩潰（cascading failure）。因此，簡(jiǎn)單地將單層瓦解算法應(yīng)用于每一層并不能有效解決問題，甚至可能導(dǎo)致嚴(yán)重低估系統(tǒng)脆弱性。

在已有方法中，F(xiàn)INDER 是一項(xiàng)具有代表性的進(jìn)展，它通過強(qiáng)化學(xué)習(xí)方式，不依賴精確標(biāo)簽，在單層網(wǎng)絡(luò)中自動(dòng)學(xué)習(xí)最優(yōu)節(jié)點(diǎn)移除策略，顯著提升了瓦解效果。FINDER 在策略學(xué)習(xí)能力方面表現(xiàn)優(yōu)越，展現(xiàn)出超越傳統(tǒng)啟發(fā)式方法的潛力。

然而，F(xiàn)INDER主要針對(duì)單層網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)，其表征學(xué)習(xí)架構(gòu)無法識(shí)別或處理跨層信息傳遞所帶來的系統(tǒng)性風(fēng)險(xiǎn)，限制了其在現(xiàn)實(shí)多層系統(tǒng)中的應(yīng)用效果。為克服上述局限，MultiDismantler在其強(qiáng)化學(xué)習(xí)架構(gòu)基礎(chǔ)上，進(jìn)一步融合多層網(wǎng)絡(luò)建模和多層表示學(xué)習(xí)機(jī)制，面向多層網(wǎng)絡(luò)瓦解問題提供全新的解決方案。

MultiDismantler整體架構(gòu)由三大模塊協(xié)同組成，實(shí)現(xiàn)端到端的多層網(wǎng)絡(luò)瓦解方案：

核心術(shù)語釋義

• LMCC（largest mutually connected component，最大互連分量）
  指在多層網(wǎng)絡(luò)中，所有節(jié)點(diǎn)在所有層均保持可達(dá)性時(shí)形成的最大連通區(qū)域，其大小是衡量多層系統(tǒng)整體連通性的重要指標(biāo)。

• AUDC（Area Under the Dismantling Curve，瓦解曲線下的面積）
  反映節(jié)點(diǎn)逐步移除過程中，最大互連分量的大小隨移除代價(jià)變化的累積情況，值越小表示瓦解越高效。

• C*（normalized dismantling cost，最小歸一化瓦解成本）
  表示將 LMCC 削減至非廣延規(guī)模（通常小于原始網(wǎng)絡(luò)平方根大小）所需的最小移除成本，并進(jìn)行歸一化處理，方便不同網(wǎng)絡(luò)間橫向比較。

圖 1. MultiDismantler訓(xùn)練流程：首先，通過GMM生成大量多層網(wǎng)絡(luò)；然后，利用MGNN對(duì)多層網(wǎng)絡(luò)進(jìn)行編碼（對(duì)應(yīng)圖中 f E 過程）；接著，使用DQN進(jìn)行解碼（對(duì)應(yīng)圖中 f D 過程），并選擇在網(wǎng)絡(luò)拆解過程中最關(guān)鍵的節(jié)點(diǎn)(對(duì)應(yīng)途中Greedy Selection)。該過程反復(fù)迭代，最終學(xué)習(xí)到多層網(wǎng)絡(luò)瓦解的綜合策略。

· 多層網(wǎng)絡(luò)建模（GMM，Geometric Multiplex Model）

在訓(xùn)練數(shù)據(jù)準(zhǔn)備階段，MultiDismantler 引入 GMM 作為合成網(wǎng)絡(luò)生成器。相比傳統(tǒng)單層 BA 或 ER 網(wǎng)絡(luò)，GMM 能更真實(shí)地復(fù)現(xiàn)現(xiàn)實(shí)網(wǎng)絡(luò)中的層間幾何相關(guān)性和耦合結(jié)構(gòu)，從而在訓(xùn)練階段提供具有代表性和結(jié)構(gòu)多樣性的語料，增強(qiáng)模型的泛化能力。這種對(duì)真實(shí)結(jié)構(gòu)特性的模擬，使得算法在面對(duì)未見過的網(wǎng)絡(luò)拓?fù)淙跃邆鋸?qiáng)魯棒性和轉(zhuǎn)移能力。

· 多層表示學(xué)習(xí)機(jī)制（MGNN，Multiplex Graph Neural Network）

在表征學(xué)習(xí)階段，MultiDismantler 使用 MGNN 模型對(duì)多層網(wǎng)絡(luò)進(jìn)行編碼，不僅在每一層內(nèi)部通過圖卷積提取局部結(jié)構(gòu)特征，還通過節(jié)點(diǎn)級(jí)的跨層注意力機(jī)制實(shí)現(xiàn)層間信息融合。MGNN 能動(dòng)態(tài)建模節(jié)點(diǎn)級(jí)別的注意力，量化不同層中的跨層節(jié)點(diǎn)相對(duì)重要性，生成具有全局語義、一體化的結(jié)構(gòu)表示，精準(zhǔn)捕捉跨層耦合對(duì)網(wǎng)絡(luò)瓦解路徑的影響。

· 強(qiáng)化學(xué)習(xí)策略優(yōu)化（N-step Deep Q-Network）

在策略學(xué)習(xí)方面，MultiDismantler 基于 N-step Deep Q-Network設(shè)計(jì)了強(qiáng)化學(xué)習(xí)模塊，以學(xué)習(xí)網(wǎng)絡(luò)瓦解中的最優(yōu)節(jié)點(diǎn)移除順序。算法通過引入虛擬節(jié)點(diǎn)構(gòu)建網(wǎng)絡(luò)狀態(tài)，結(jié)合LMCC大小的變化作為獎(jiǎng)勵(lì)信號(hào)，引導(dǎo)智能體學(xué)習(xí)長(zhǎng)遠(yuǎn)且系統(tǒng)性強(qiáng)的拆解策略。N-step Q-learning 能夠有效建模節(jié)點(diǎn)移除對(duì)未來狀態(tài)的滯后影響，使得所學(xué)策略不僅關(guān)注當(dāng)前瓦解效果，更能識(shí)別潛在的結(jié)構(gòu)斷裂點(diǎn)。考慮到多層網(wǎng)絡(luò)中各層功能和結(jié)構(gòu)的重要性不盡相同，MultiDismantler 為每一層分別計(jì)算節(jié)點(diǎn)的 Q value，再通過層級(jí)注意力機(jī)制自適應(yīng)地融合這些值，形成綜合的策略評(píng)估結(jié)果。

3. 網(wǎng)絡(luò)瓦解過程可視化

為更直觀地展示不同算法在多層網(wǎng)絡(luò)瓦解過程中的表現(xiàn)，我們以一個(gè)包含 15 個(gè)節(jié)點(diǎn)的合成互依網(wǎng)絡(luò)為例，對(duì)比分析了 HDA 算法與 MultiDismantler 的操作流程和瓦解效果。

· 圖中每一層表示網(wǎng)絡(luò)的一個(gè)子層，上下層節(jié)點(diǎn)一一對(duì)應(yīng)，灰色豎線表示層間依賴關(guān)系。藍(lán)色節(jié)點(diǎn)與連邊表示當(dāng)前網(wǎng)絡(luò)中的LMCC，紅色節(jié)點(diǎn)表示當(dāng)前被移除的節(jié)點(diǎn)。

· 圖 (a)–(c) 展示的是 HDA 算法的瓦解過程。HDA 首先移除節(jié)點(diǎn) 9，但其后選擇了節(jié)點(diǎn) 8，未能顯著破壞網(wǎng)絡(luò)結(jié)構(gòu)，最終留下了一個(gè)包含 13 個(gè)節(jié)點(diǎn)的 LMCC，瓦解效果有限。

圖 (d)–(f) 展示的是 MultiDismantler 的瓦解過程。該方法同樣以節(jié)點(diǎn) 9 作為首個(gè)移除目標(biāo)，但在第二步選擇了橋接節(jié)點(diǎn) 3。這一策略將原網(wǎng)絡(luò)有效分割為兩個(gè)較小的連通子圖（分別為 5 節(jié)點(diǎn)與 6 節(jié)點(diǎn)），與HDA相比，LMCC所包含的節(jié)點(diǎn)減少了7個(gè)，加速了網(wǎng)絡(luò)崩解的進(jìn)程。

該例子清晰地說明：相比于基于度數(shù)的啟發(fā)式方法，MultiDismantler 能夠捕捉關(guān)鍵結(jié)構(gòu)特征（如橋接節(jié)點(diǎn)），并制定更具全局破壞性與連鎖瓦解潛力的節(jié)點(diǎn)移除序列，從而展現(xiàn)出更優(yōu)的瓦解策略。

4. MultiDismantler網(wǎng)絡(luò)瓦解性能評(píng)估

為全面驗(yàn)證 MultiDismantler 的有效性，作者在大量合成網(wǎng)絡(luò)和真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)上對(duì)比評(píng)估其瓦解性能。合成數(shù)據(jù)由GMM生成，具有可控的層間相關(guān)性和節(jié)點(diǎn)度分布，可模擬現(xiàn)實(shí)中的多種結(jié)構(gòu)屬性；真實(shí)數(shù)據(jù)則涵蓋生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等多類復(fù)雜系統(tǒng)。

結(jié)果表明：

· 在合成網(wǎng)絡(luò)上，MultiDismantler 在不同結(jié)構(gòu)參數(shù)設(shè)定下均顯著優(yōu)于基線算法，AUDC在單位代價(jià)和度數(shù)代價(jià)下分別優(yōu)于次優(yōu)算法 EMD 約 5.9% 和 8.3%。

· 在真實(shí)多層網(wǎng)絡(luò)中，MultiDismantler 同樣表現(xiàn)優(yōu)越。在單位代價(jià)下，C* 相較 FINDER 降低了 3%；在度數(shù)代價(jià)下，AUDC 相較 EMD 下降了 8.4%。

此外，實(shí)驗(yàn)還驗(yàn)證了 MultiDismantler 在未知代價(jià)分布（如正態(tài)分布、泊松分布）下的穩(wěn)健性與泛化能力，即便僅在統(tǒng)一分布下訓(xùn)練，仍能在新分布下取得最優(yōu)結(jié)果，展示出良好的實(shí)用性與魯棒性。

5. MultiDismantler

在疾病傳播防控與網(wǎng)絡(luò)魯棒性增強(qiáng)中的應(yīng)用

MultiDismantler 不僅在理論層面具備最優(yōu)瓦解能力，其輸出的節(jié)點(diǎn)序列也在實(shí)際應(yīng)用中展現(xiàn)出顯著效用。本文聚焦兩個(gè)典型應(yīng)用場(chǎng)景：

（1）疾病傳播防控：
在多層社交網(wǎng)絡(luò)中，作者利用 MultiDismantler 提供的節(jié)點(diǎn)序列，設(shè)計(jì)疫苗接種策略。通過移除前 50% 的關(guān)鍵節(jié)點(diǎn)（即模擬接種），并在殘余網(wǎng)絡(luò)上進(jìn)行 SIR 傳播模擬，MultiDismantler減少了最終感染人數(shù)。與其他方法相比，其策略更有效地阻斷了疫情的傳播路徑，達(dá)到了較低的感染率，展示出其在公共健康管理中的潛在應(yīng)用價(jià)值。

（2）網(wǎng)絡(luò)魯棒性提升：
在抗攻擊實(shí)驗(yàn)中，作者考察了在已知關(guān)鍵節(jié)點(diǎn)序列的前提下，若對(duì)其中前 1% 節(jié)點(diǎn)進(jìn)行保護(hù)，網(wǎng)絡(luò)在遭遇隨機(jī)失效或定向攻擊時(shí)的穩(wěn)健性變化。結(jié)果表明，無論是隨機(jī)擾動(dòng)還是定向攻擊，基于 MultiDismantler 策略保護(hù)的網(wǎng)絡(luò)都保持了更大的主連通組件，證明其具備良好的“先識(shí)別、后保護(hù)”能力，適用于關(guān)鍵基礎(chǔ)設(shè)施系統(tǒng)的抗毀設(shè)計(jì)。

總的來看，MultiDismantler 不僅是一種強(qiáng)有力的瓦解優(yōu)化工具，其在疾病控制、網(wǎng)絡(luò)設(shè)計(jì)與風(fēng)險(xiǎn)防范等領(lǐng)域的落地潛力也得到了初步驗(yàn)證。

6. 未來展望

盡管 MultiDismantler 在多層網(wǎng)絡(luò)瓦解任務(wù)中展現(xiàn)出顯著優(yōu)勢(shì)，仍有若干值得進(jìn)一步探索的方向。比如當(dāng)前模型主要面向一對(duì)一節(jié)點(diǎn)映射的互依網(wǎng)絡(luò)結(jié)構(gòu)，未來可以擴(kuò)展至多對(duì)多依賴關(guān)系或部分冗余互聯(lián)結(jié)構(gòu)，以更貼近現(xiàn)實(shí)中復(fù)雜系統(tǒng)（如電網(wǎng)-通信、社交-交通耦合網(wǎng)絡(luò)）中存在的異構(gòu)依賴模式。

作者介紹

谷偉偉，北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系副教授，集智科學(xué)家，主要研究方向包括多層網(wǎng)絡(luò)表征學(xué)習(xí)、圖組合優(yōu)化與AI For Science；近五年以第一作者在《Nature Machine Intelligence》《Nature Communications》等高水平期刊發(fā)表多項(xiàng)研究成果。

個(gè)人主頁：https://lanyu617.github.io/weiweigu/

楊宸，北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院2020級(jí)本科生，香港理工大學(xué)研究助理。研究興趣為AI for Science，圖神經(jīng)網(wǎng)絡(luò)。郵箱：chenyangmiles@gmail.com。

推薦讀書會(huì)

關(guān)于Finder的詳細(xì)解讀，請(qǐng)看視頻

「重整化群分析在非線性物理中的應(yīng)用」系列課程

你知道嗎？費(fèi)根保姆常數(shù)可以由重整化群計(jì)算，相變臨界點(diǎn)可以由重整化方法得出，深度神經(jīng)網(wǎng)絡(luò)的多層計(jì)算就是在對(duì)圖像做重整化。重整化群是考察不同尺度下物理規(guī)律變化的數(shù)學(xué)工具，幫助我們理解系統(tǒng)在大范圍內(nèi)或臨界點(diǎn)附近的行為。集智學(xué)園聯(lián)合北京郵電大學(xué)蘭岳恒教授開設(shè)，系統(tǒng)講述重整化群這一理論框架，怎樣用來分析高維非線性系統(tǒng)的性質(zhì)，實(shí)現(xiàn)方程的求解與約化。

本系列課程將回答如下問題：

• 從有限的觀測(cè)提取一般性規(guī)律建模的原則和常見框架是什么？

• 怎樣寫出系統(tǒng)重要結(jié)構(gòu)和運(yùn)動(dòng)模式的近似解析表達(dá)式？

• 怎樣將對(duì)稱性、不變性、基本范式等先驗(yàn)知識(shí)放到系統(tǒng)解析描述中？

• 怎樣建立系統(tǒng)不同層級(jí)動(dòng)力學(xué)間聯(lián)系的方程？

歡迎感興趣的研究者加入課程。

詳情請(qǐng)見：

1.

2.

3.

4.

5.

6.

7.