提高复杂网络分析效率！中国科学家研发强化学习新框架

近日，中国国防科技大学、美国加州大学洛杉矶分校和哈佛医学院的研究人员研发了一个深度强化学习框架FINDER。相比于现有的解决方案，FINDER能够更快速、更高效地找到复杂网络中一组最关键的节点，进而使复杂网络以较高的效率运行。

这项研究发表在国际期刊《自然》旗下的《自然–机器智能》上，论文标题为《用深度强化学习找到复杂网络的关键参与者（Finding key players in complex networks through deep reinforcement learning）》。

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

一、FINDER：适用场景更广泛，运行速度快出几个数量级

在物理科学、信息科学、生物科学等领域的研究中，研究人员可以通过建立网络拓扑结构来模拟实际情况、进而作出预测。

在这类复杂网络的运行过程中，节点间的配合直接决定了复杂网络运行的效率。当被用于解决NP难题（NP-hard）时，复杂网络中节点的“分工协作”尤其重要。

NP难题指的是在多项式时间内可以被验证其正确性的问题。比如，在疫情防控领域，复杂网络模型可以模拟出疫情传播情况、帮助找到疫苗药物分子等。运行这些任务时，复杂网络要推演和验证病毒是否会传染给下一个人、某种药物分子是否有效的各种情况。在这个过程中，找到最关键的节点能够提升复杂网络的运行效率。

对于这类问题，现有的解决方案通常基于大型网络进行训练、针对特定场景提出策略，但缺乏统一的框架。相比之下，中国国防科技大学、加州大学洛杉矶分校、哈佛医学院的研究人员提出的FINDER可以应用于广泛的复杂网络场景，其运行速度快了几个数量级。

二、分两阶段进行训练，分别采用不同奖励函数

FINDER框架采用纯数据驱动的方法，分两个阶段进行训练。在两个阶段中，研究人员用不同的奖励函数来训练FINDER。

第一阶段用经典模型生成的小型合成网络对FINDER进行离线训练。离线训练采用ϵ-greedy策略。

离线训练阶段分三步进行：首先，研究人员生成一批合成图形；然后，研究人员从合成图形中任意取样一个图形；接下来，FINDER框架在这一图形上进行整个寻找关键节点的流程。这一流程中，代理与图形通过一系列状态、动作、激励进行交互。

为了确定状态的正确动作，代理先在当前的图形上编码，并获取每个节点的嵌入向量。节点的嵌入向量会捕获节点的结构信息和节点特征之间的长程相互作用（long-range interaction）。接下来，代理将嵌入向量解码为标量Q值，以便所有节点能够预测部署某个动作的长程增益。

▲离线训练阶段示意图

一旦离线训练结束，FINDER就进入第二个训练阶段，被应用于真实网络拓扑结构中。研究人员在浣熊接触网络（the raccoon contact network）的最大连通元件（connected component）上进行测试。最大连通元件包括14个节点和20条边。

这一阶段中，代理首先将当前网络编码为低维嵌入向量，然后利用这些向量对每个节点的Q值进行解码。

第二阶段采用“批量节点选择（batch nodes selection）”策略。该策略在每个自适应步骤中选择一个有限分数的最高Q节点，避免了对嵌入向量和Q值的逐个迭代选择和重新计算。批量节点选择策略不会影响最终的结果，但可以降低几个数量级的时间复杂度。

研究人员会重复这个过程，直到复杂网络达到用户定义的终端状态、被移除的节点构成最优的节点集合。

▲用真实复杂网络进行训练示意图

三、对比3个模型性能，FINDER找出关键节点的效率最高

相比于机器人等传统的强化学习技术（状态和动作较为简单），复杂网络技术更加复杂和难以表示。研究团队高级研究员孙怡舟称，这是因为复杂网络具有离散的数据结构和处于极其高维的空间。

本项研究中，研究人员用图神经网络（GNN）来解决这个问题。图神经网络中的节点代表动作、图形代表状态。

以911恐怖袭击事件发生预测网络为例，网络中每个节点代表参与911恐袭的恐怖分子、每个边（edge）代表他们的社会交流。

研究人员在911恐怖袭击事件发生预测网络上运行FINDER框架，并运行现有的高维（HD）方法和集体影响（CI）方法做对比。

下图d显示了三种方法的ANC曲线。在框架部署动作后，剩余节点的重要性越低，代表框架性能越好。

可以看到，FINDER框架最有效地找到了复杂网络中关键节点。相比于其他两个解决方案，随着被移除节点的重要性升高，运行FINDER框架的复杂网络中剩余的节点重要性最低。

▲911恐怖袭击事件发生预测网络（蓝色点代表剩余图形中的节点，红色点代表当前时间步长中FINDER找出的关键节点，灰色点代表剩余的孤立节点）

结语：未来将可用于更多类型复杂网络

FINDER框架通过深度强化学习方法进行训练，可以找到复杂网络中的关键节点。在未来，FINDER框架或可被用于优化社交网络、电力网络、传染病蔓延网络等模型的性能。

目前，加州大学洛杉矶分校的研究团队正计划将FINDER框架用于网络科学研究。哈佛医学院的团队希望将FINDER用于生物网络，以确定蛋白质交互网络和基因调控网络中的关键参与者。

另外，研究人员称未来将从以下三方面着手，提升框架寻找关键节点的性能：设计出更好的图形表示学习架构；探索如何在跨图形甚至跨域转移知识；研究并解决复杂网络上的其他NP难题。