Abstract: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.