原创投稿 行业报告 AI展会 数据标注
投稿发布
您的当前位置:主页 > 机器学习 > 正文

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

来源: 时间:2020-06-16
牵一发而动全身,网络中有些节点一旦被去除,就会对网络的连通性产生断崖式的影响。该如何找到这样的节点。近日,发表在 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 轮,之后再给出反馈。
 
基于强化学习,找出网络中为达成某一目标的最优行动,进一步的研究,需要关注的是算法的可解释性。即为何算法会给出这样的策略,如何对其解释。可解释性的增强,可以让这类算法应用到更真实的场景当中。
 
例如警察决定起诉黑帮中的关键成员,通过网络分析,得出了应该起诉哪些人。但还需要有额外的算法,说明如果不起诉这些人,为什么就不能打击该黑帮。否则,公众会怀疑算法是否公平,是否会造成对女性或少数族裔的歧视。
 
声明:文章收集于网络,版权归原作者所有,为传播信息而发,如有侵权,请联系小编删除,谢谢!
 
 

人工智能交流群扫码邀请
人工智能交流群扫码邀请


转发量:

网友评论:

发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
数据标注服务

Copyright©2005-2020 Sykv.com 可思数据 版权所有    京ICP备14056871号

关于我们   免责声明   广告合作   版权声明   联系我们   原创投稿   网站地图  

可思数据 数据标注行业联盟

人工智能资讯   人工智能资讯   人工智能资讯   人工智能资讯

扫码入群
咨询反馈
扫码关注

微信公众号

返回顶部
关闭