如何以最小代价破坏系统结构？一套基于机器学习的方法( 二 )

该框架采用有监督学习的方式进行训练，首先要获取大量有标签的训练样本。本文中作者生成了一些小规模的模型网络，例如无标度网络、随机网络等，计算节点的不同中心性和拓扑特征，例如节点度值、聚类系数等，通过穷举法获得其所有的最小拆解集合，进而计算每个节点位于拆解集合的概率，由此就得到了大量的训练样本。运用这些样本，可以对深度学习模型进行有效训练，以获得合适的节点特征聚合方式，而框架中采用的图注意力网络通过注意力机制来对邻居节点做聚合操作，实现了不同邻居权重的自适应分配。
为了评估算法的有效性，文章运用节点移除过程中最大连通集团规模曲线（如图1a所示）下的面积（AUC,AreaUndertheCurve）作为评估算法有效性的指标，通过在大量的节点规模达到十万、百万量级的真实网络和模型网络的实验，发现本算法的平均表现要优于当前已有的结构启发式算法，且具有较低的时间复杂度。同时，文章通过网络的连边重写扰动实验和单一特征的增强实验，进一步证明了本框架的有效性。

文章图片
3.打开深度学习的黑箱，揭秘方法有效背后的原因
在验证了算法的初步性能后，为探究模型具体是怎样学习和做出长期预测的，作者引入这一类图卷积网络模型的解释器GNNExplainer ，提取由节点和连边子图组成的解释子图，来揭示模型对每个节点的预测值。
如图3所示，通过测试几种网络的解释子图发现，得分排名前四的节点均为连接多个簇的桥节点，且是通过结合输入特征和查找K阶邻居中的其他桥节点发现的，在算法中通过聚合局部和二阶特征来实现。这一思路实际上和一种已有的基于组合影响（CollectiveInfluence ， CI）的启发式方法的机理类似，区别在于CI仅对节点及其k阶邻居的度值特征进行聚合，而本方法通过深度学习方法聚合了更多节点及其邻居的特征。

文章图片
图3.巴西贪腐网络中排名前四节点的解释子图
在理解了模型学习的内容后，进一步运用GNNExplainer分析特征在输出值计算中的作用，并了解模型如何选择节点。通过图4的分析可以看出，并没有一个在所有网络中都处于支配地位的特征，而且不同特征的权重比例还会随着节点的得分而变化。这些结果也说明，基于这些GDM框架的结果来定义一种启发式方法是极其困难的，因为每个特征的权重是由模型根据拓扑和网络中的模式进行调整的。

文章图片
图4.节点不同特征的重要性趋势
网络中如果移除会产生新的连通片的节点被称为“关节点” ，对于维持网络连通性有重要作用，随着网络中节点的移除，也会产生新的关节点。作者通过分析节点移除过程中，网络中的关节点数量，移除节点中关节点数量和新产生的关节点数量的变化，来分析框架识别出的节点的特点。值得注意的是，单纯关节点的移除并不会对网络连通性造成很大的损伤，因为有些关节点可能只会影响网络中的少量节点。本文通过如图4所示的分析说明， GDM方法能够通过学习找到那些更有效瓦解网络的关节点。

文章图片
图5.节点移除过程中关节点的移除与产生
4.系统崩溃发生前夕的早期预警信号
在文章的研究中使用最大连通片的规模作为系统连通性的评价，事实上，仅关注这一指标并不能完全把握系统的状态。我们所担心的系统的崩溃风险并不仅仅来源于系统连通规模的下降，更多来源于节点失效累积而造成的系统性能的骤降。