近日，来自中国国防科技大学、加州大学洛杉矶分校和哈佛医学院的研究人员开发了深度强化学习框架FINDER。与现有解决方案相比，FINDER可以更快、更高效地找到一组复杂网络中最关键的节点，从而使复杂网络以更高的效率运行。该研究发表于《自然–机器智能》国际期刊《自然》，题为《用深度强化学习找到复杂网络的关键参与者（Finding key players in complex networks through deep reinforcement learning）》。论文链接：https://www.nature.com/articles/s42256-020-0177-21.FINDER：适用场景更广，在物理科学领域运行速度提升几个数量级、信息科学和生物科学。在研究中，研究人员可以通过建立网络拓扑来模拟实际情况，进而做出预测。在这样一个复杂网络的运行过程中，节点之间的协作直接决定了复杂网络运行的效率。当它用于解决NP-hard问题时，复杂网络中节点的“分工与合作”尤为重要。NP难问题是指可以在多项式时间内验证正确的问题。比如在疫情防控领域，复杂的网络模型可以模拟疫情的传播，帮助寻找疫苗药物分子。在运行这些任务时，复杂的网络会推导和验证各种情况，例如病毒是否会传播给下一个人，或者某种药物分子是否有效。在这个过程中，找到最关键的节点可以提高复杂网络的运行效率。对于这类问题，现有的解决方案通常是基于大规模的网络训练和针对特定场景的策略，缺乏统一的框架。相比之下，由中国国防科技大学、加州大学洛杉矶分校和哈佛医学院的研究人员提出的FINDER，可以应用于广泛的复杂网络场景，其运行速度快了几个数量级。2.分两个阶段训练，分别使用不同的奖励函数。FINDER框架采用纯数据驱动的方式，分两个阶段进行训练。研究人员分两个阶段用不同的奖励函数训练FINDER。第一阶段使用经典模型生成的小型合成网络离线训练FINDER。离线训练采用ε-greedy策略。离线训练阶段分为三个步骤：首先，研究人员生成一批合成图；然后，研究人员从合成图中随机抽取一个图；接下来，FINDER框架执行在此图上查找关键节点的整个过程。在这个过程中，智能体通过一系列状态、动作和激励与图进行交互。为了确定状态的正确动作，代理首先对当前图进行编码，并获得每个节点的嵌入向量。节点的嵌入向量捕获节点的结构信息和节点特征之间的远程交互。接下来，代理将嵌入向量解码为标量Q值，以便所有节点都可以预测部署动作的长期增益。▲离线训练阶段示意图离线训练结束后，FINDER将进入第二个训练阶段，应用于真实的网络拓扑。研究人员在浣熊联系网络的最大连接组件上进行了测试。最大的连通元由14个节点和20条边组成。在这个阶段，代理首先将当前网络编码成低维嵌入向量，然后使用这些向量解码每个节点的Q值。第二阶段采用“批量节点选择”策略。该策略在每个自适应步骤中选择有限部分的最高Q节点，避免迭代选择和重新计算嵌入向量和Q值。批量节点选择策略不影响最终结果，但可以将时间复杂度降低几个数量级。研究人员重复这个过程，直到复杂网络达到用户定义的终端状态，并且移除的节点形成一组最优节点。▲用真实的复杂网络训练示意图3.对比三种模型的性能，FINDER在寻找关键节点的效率最高相较于机器人（状态和动作都比较简单）、复杂网络等传统强化学习技术技术更复杂，更难表达。据课题组高级研究员孙一洲介绍，这是因为复杂网络具有离散的数据结构，处于极高维空间。在这项研究中，研究人员使用图神经网络（GNN）来解决这个问题。图神经网络中的节点代表动作，图代表状态。以911恐怖袭击预测网络为例，网络中的每个节点代表参与911恐怖袭击的恐怖分子，每条边（edge）代表他们的社会交往。研究人员在9/11恐怖袭击预测网络上运行FINDER框架，并运行现有的高维（HD）方法和集体影响（CI）方法进行比较。下图d为三种方法的ANC曲线。框架部署动作后，剩余节点的重要性越低，框架的性能越好。可以看出，FINDER框架在复杂网络中寻找关键节点的效率最高。与其他两种解决方案相比，随着被移除节点的重要性增加，运行FINDER框架的复杂网络中剩余节点的重要性最小。▲911恐怖袭击预测网络（蓝点代表剩余图中的节点，红点代表FINDER在当前时间步找到的关键节点，灰点代表剩余的孤立节点）结论：它将用于更多的in未来的TypeComplexNetworksFINDER框架通过深度强化学习方法训练，可以找到复杂网络中的关键节点。未来，FINDER框架可能用于优化社交网络、电力网络、传染病传播网络等模型的性能。目前，UCLA研究团队正计划使用FINDER框架进行网络科学研究。哈佛医学院团队希望将FINDER应用于生物网络，以识别蛋白质相互作用网络和基因调控网络中的关键参与者。此外，研究人员表示，未来他们将从以下三个方面入手，提升框架寻找关键节点的性能：设计更好的图表示学习架构；探索如何跨图甚至跨领域传输知识；研究和解决复杂网络上的其他问题。NP难问题。
