基于图神经网络的最大化代数连通度算法

随着智能体数量的增加, 多智能体系统中潜在的通信链路数量呈指数级增长. 过多冗余链路的存在给系统带来了大量的能源浪费和维护成本, 而盲目地去除链路又会降低系统的稳定性和安全性. 代数连通度是衡量图连通性的重要指标之一. 然而, 传统的半正定规划(SDP)方法和启发式算法在求解大规模场景下的最大化代数连通度问题时非常耗时. 在本文中, 我们提出了一种监督式的图神经网络模型来优化多智能体系统的代数连通度. 我们将传统的SDP方法应用于小规模任务场景中, 得到足够丰富的训练样本和标签. 在此基础上, 我们训练了一个图神经网络模型, 该模型可用于更大规模的任务场景中. 实验结果表明, 当需要去除15条边时, 我们的模型的平均性能达到了传统SDP方法的98.39%. 此外, 我们的模型计算时间极其有限, 可以推广到实时场景中去.

Algorithm for Maximizing Algebraic Connectivity Based on Graph Neural Network

As the number of agents increases, the number of potential communication links in a multi-agent system grows exponentially. Excessive redundant links lead to a significant waste of energy and maintenance costs for the system, while blindly removing links will reduce the stability and security of the system. Algebraic connectivity is one of the important metrics to measure the connectivity of a graph. However, traditional semidefinite programming (SDP) methods and heuristic algorithms for maximizing algebraic connectivity in large-scale scenarios are time-consuming. This study proposes a supervised graph neural network model to optimize the algebraic connectivity of multi-agent systems. The study applies the traditional SDP method in small-scale task scenarios, obtaining a sufficient amount of diverse training samples and labels. Based on this, it trains a graph neural network model that can be used in larger-scale task scenarios. The experimental results indicate that when removing 15 edges, the proposed model achieves an average performance of 98.39% of the traditional SDP method. In addition, the model has extremely limited computational time and can be extended to real-time scenarios.