用强化学习寻找关键节点——复杂网络研究新范式

导语

牵一发而动全身，网络中有些节点一旦被去除，就会对网络的连通性产生断崖式的影响。该如何找到这样的节点。近日，发表在 Nature Machine Intelligence 上的一篇论文“通过深度强化学习识别复杂网络中的关键节点”中，提出的 FINDER 算法，开辟了解决该类问题的全新范式。

论文题目： Finding key players in complex networks through deep reinforcement learning 论文地址： http://www.nature.com/articles/s42256-020-0177-2

1. 找到关键节点，

四两拨千斤地改变网络结构

在传染病防控中，那些一旦被去除之后，就会让整个网络传播疾病的能力显著降低的节点被称为“超级传播者”；在营销方案设计中，需要找到关键用户，通过这些用户，让产品信息快速传遍全网；而在药物设计中，找到蛋白质相互作用网络的中心节点，同样能指导药物靶点的选择。

上述场景，都可以归类为这样一类问题：即在网络中寻找一组节点，当按照顺序从网络中去除这些节点之后，在所有可能情况下，网络的连通性会发生最大程度的改变。

图1：911恐怖分子网络在不同去除节点方案情况下，最大连通部节点数的情况

上图中 a 是参与 911 事件的恐怖分子的社交网络，如果从图中 62 个节点中，选择 16 个去除，去除后，要求网络中相互连接最多的恐怖分子数最低（图中紫色部分），图 b 代表去除的是度数最大的 16 个节点（浅蓝色），图 c 代表通过通过总影响力算法得出的去除的节点，而图 d 代表本文提出的算法去除的节点。

可以看出，相比传统的方法，通过新的算法，仅仅去除 14 个节点，就能够让恐怖分子的网络分崩离析互相能联系的恐怖分子是 9 个，而之前为 14 个）。该案例说明，找到网络中关键节点，在现实中有着诸多实际的用途。

2. 强化学习与图嵌入

强化学习是机器学习三种范式中的一种，其与其他范式的区别之处，在于实时的奖励。其学习的过程是：智能体根据初始策略，决定采取何种行动，外界环境会根据智能体的行动，为其提供奖励，智能体会基于奖励，调整策略，以此迭代提升智能体的决策力。

在寻找关键节点的问题上，策略是建立算法根据网络结构，在有限的计算中，找出应该去掉哪些节点。行动是依次去掉这些节点。而奖励则是去掉后，按照定义的网络连通性评价方式，网络连通性会有多大的改变。

复杂网络通常用图这种数据结构来记录，而将图用更低维度的数据进行表征，则被称为图嵌入。通过图嵌入，替代原图的数据，能保留原图中拓扑结构，节点之间的相互关系，以及关于图、子图的其他相关信息。通过图嵌入，能够在之后对图的分析任务中，获得更好的结果。

3. FINDER有何不同之处

寻找关键节点的问题，如果通过穷举法，随着网络中节点数的增加，会导致计算所需的时间呈指数级增加。这在计算机科学中被称为 NP-hard 问题，是优化算法领域的终极挑战。

之前的对该问题的解法，是通过网络中节点的局部特征，例如根据节点分布，属于的模体数，来决定去除哪些节点的。但网络节点的异质性，以及网络的涌现特征，会使得节点对连通性的贡献度，难以通过一个简单指标概括。

图2：FINDER 算法示意图

FINDER 先在模拟的，节点数较少的 BA 无标度网络中，能够通过穷举法找到最优解的网络中，进行离线学习。如上图前半部分所示。之后在真实场景下的网络中，使用之前训练好的智能体，让其不断根据当前网络，决定要去掉哪个节点。最终得到去除节点的顺序，并据此评价算法的表现，如上图下半部分所示。

具体分为两步：首先是编码。使用图嵌入算法 GraphSAGE，通过迭代，提取网络中每个节点的特征。例如最初每个节点的特征是其度数，之后，每个节点的特征向量会向周围的节点传递该节点的特征。

之后的解码步骤：利用强化学习中的 Q-learning，基于当前去除节点后连通度的变化，相比最优连通度的变化差距多少，调整产生策略（下一步去除哪个节点）的神经网络的参数。该神经网络为两层的全连接结构，Relu 为激活函数。在端对端的训练过程中，待优化的损失函数为网络重构误差与 n 步之后的 Q-learning 的奖励函数之和。

4. FINDER效果如何

随着网络中节点数的增加，实用的算法其运行时间，不应该有明显的增加。对于 FINDER，其时间复杂度为 O（E+V+V * logV），其中 E 代表网络中边的个数，V 代表节点个数。这意味着该算法可以在大数据集上高效执行。

为了说明算法的灵活性，在训练时，采取了两种连通度的评价方法（连接边/最大连通部大小），并分别在节点有权重和无权重的情况下，进行训练和评测。结果表明 FINDER 在上述四种组合下，都表现优异。

评价 FINDER 的效果，分为两步，首先是在 BA，ER 和 WS 模型生成的随机网络上进行评价。由于 FINDER 训练时，使用的是由 BA 模型生成数据，因此其在 BA 模型生成的测试集中表现最佳。如果将训练数据的生产模型替换为 ER 或者 WS 模型，则其在真实网络中的效果会下降。

这一点反映了巴拉巴西的无标度网络模型，其模型组成虽然简单，但其包含了真实网络中具有的节点异质性等特征。若非如此，在模拟网络中训练出的智能体，也难以在真实网络中，同样表现出色。

真实世界的网络中，评价 FINDER 时，文中使用了 9 种不同来源的网络。其中包含 4 种社交网络，电子邮件通信网、P2P 文件共享网络、社交新闻评价网络、人体内蛋白质互作网络及不同罪犯和所犯罪行的二分网络。在所有 9 种网络中，FINDER 的性能都显著优于之前的方法。

图3：FINDER效果对比举例

上图的网络，是随机生成的网络，图中横轴是去除的节点比例，纵轴是网络连通性相比之前的比例。从左到右，依次代表节点无权重，节点权重为其度数，节点随机权重的场景。图中红色代表的 FINDER 算法，效能显著优于其他方法。

5. FINDER代表了解决

一类问题的通用范式

该方法为如何解决网络上的优化问题，尤其是那些与具体知识无关，但是由于节点异质性而变得难以解决的问题，提供了一种全新的范式。即将问题转换为，如何通过强化学习，在已知答案的模拟网络上训练智能体找到最优策略。

之前的方法，基于的是一般性的统计规律，例如度数大的节点，连接的节点更多。因此去掉后可能会影响网络的连通性，这种基于相关性推演出的启发式规则，对于特定的场景下，不一定适用。例如小世界网络中，连通两个部分的关键节点，其本身的连接数不多，其重要性来自与其在网络中所处的位置。

而强化学习加图嵌入，则能够让算法基于训练中学到的复杂规则，针对特定场景，动态地制定解决方案。基于这种模式，可以找到解决很多其他问题算法，例如在网络中，识别出该保存哪些节点，能够使网络的连通性最大程度的得到保存。

图4：通过强化学习解决最小渗滤阀值问题示意图

由于强化学习能够处理延迟反馈带来的问题，即第一步的行动，在第四步才得到反馈，因此对需要多步操纵网络的任务，该方法也是使用的。上图描述的是用该类方法，解决网络中最小渗滤阀值这一问题。由于该问题中，每一步的决策依赖于之前的决策，因此相比寻找关键节点这个问题，在离线训练过程中，其不同点在于，会让智能体先行动 N 轮，之后再给出反馈。

基于强化学习，找出网络中为达成某一目标的最优行动，进一步的研究，需要关注的是算法的可解释性。即为何算法会给出这样的策略，如何对其解释。可解释性的增强，可以让这类算法应用到更真实的场景当中。

例如警察决定起诉黑帮中的关键成员，通过网络分析，得出了应该起诉哪些人。但还需要有额外的算法，说明如果不起诉这些人，为什么就不能打击该黑帮。否则，公众会怀疑算法是否公平，是否会造成对女性或少数族裔的歧视。

作者：郭瑞东 审校：王舒凡 编辑：张爽、曾祥轩

文字不过瘾，直播搞起来？

强化学习+图嵌入，复杂网络传统方法会被颠覆吗？你一定意犹未尽~最好论文作者直播搞起~

然而人气、人气、人气呀，人够多才搞得起。主编说，要没100位听众，咱都不好意思联系作者(-ι_-｀)

所以我们在此发起投票：

-如果超过100人报名，集智编辑部承诺会邀请论文作者作客集智直播间，讲透论文。你的问题，统统当面回应！

-如果超过200人报名，编辑部会尽力邀请领域专家，针对强化学习、图嵌入在网络科学中前沿应用，撰写专题综述文章！（只在集智才有的那种，你懂得）

具体投票方法：扫描下方二维码，在集智斑图上点击「我要听」报名，推动这次直播的行动，你的一票很重要！

特别是读到文末的你( ω )

扫码登录集智斑图报名「我要听」。集智斑图是由集智俱乐部发起、以复杂性科学为主题的自组织学习社区，承载了集智俱乐部的论文解读活动。

集智俱乐部QQ群｜877391004

◆ ◆ ◆

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！