In the quest to improve efficiency, interdependence and complexity are becoming defining characteristics of modern complex networks representing engineered and natural systems. Graph theory is a widely used framework for modeling such complex networks and to evaluate their robustness to disruptions. Particularly, identification of critical nodes/links in a graph can facilitate the enhancement of graph (system) robustness and characterize crucial factors of system performance. Most existing methods of critical node identification are based on an iterative approach that explores each node/link of a graph. These methods suffer from high computational complexity and the resulting analysis is network specific. Additionally, uncertainty associated with the underlying graphical model further limits the potential value of these traditional approaches. To overcome these challenges, we propose a Bayesian graph neural network based node classification framework that is computationally efficient and systematically incorporates uncertainties. Instead of utilizing the observed graph for training the model, a MAP estimate of the graph is computed based on the observed topology and node target labels. Further, a Monte-Carlo (MC) dropout algorithm is incorporated to account for the epistemic uncertainty. The fidelity and the gain in computational complexity offered by the Bayesian framework is illustrated using simulation results.
翻译:为了提高效率,相互依存性和复杂性正在成为现代复杂网络的界定特征,这些复杂网络代表了工程和自然系统。图表理论是一个广泛使用的框架,用于模拟这些复杂网络,并评价其对中断的稳健性。特别是,在图形中识别关键节点/链接,可以促进图形(系统)稳健性,并描述系统性能的关键因素。大多数关键节点识别方法都基于探索每个图的节点/链接的迭接方法。这些方法存在高计算复杂性,因此产生的分析是具体的网络。此外,与基本图形模型相关的不确定性进一步限制了这些传统方法的潜在价值。为了克服这些挑战,我们提议以计算高效和系统化的方式纳入基于节点分类框架的巴伊斯图图形神经网络。使用观察到的图表来培训模型,而根据观察到的表层和节点标签计算出图表的估计数。此外,蒙特-卡洛(MC)的退出算法被并入了缩略图中的缩略图。通过模拟结果来说明巴伊西亚框架提供的计算复杂性。