mlsanityData to 14 Oct 2026

Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion

arXiv 2610.12697 ↗First posted 8 Oct 2026math.OC cs.LG math.COcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization also fits: RL for energy, networks and operations

Abstract (arXiv)

This paper studies an open network design problem of constructing graph topologies with maximum algebraic connectivity under fixed numbers of vertices and edges. A density-dependent approach is proposed that decomposes the design task into two stages: a high-quality, low-cost structural backbone construction and a reinforcement learning completion stage. The method selects the backbone based on density, using complete multipartite graphs in dense regimes and Cayley graphs in low-to-intermediate regimes, and then refines the remaining edges through a learning-based procedure. Numerical results show that the proposed method achieves high algebraic connectivity with favorable runtime scalability, outperforming existing methods. These results support a structural-family-first strategy for scalable network design.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 7 of its 33 references that are in the map. First posted on arXiv 8 Oct 2026.

Builds on

7 of 33 references.

References · 7

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015A Distributed Algorithm for Solving a Linear Algebraic Equationcited by 4
  3. 2022Spectral Measurement Sparsification for Pose-Graph SLAMcited by 4
  4. 2021Algebraic connectivity: local and global maximizer graphscited by 2
  5. 2022Split-Spectrum Based Distributed State Estimation for Linear Systemscited by 1
  6. 2023Optimal Robust Network Design: Formulations and Algorithms for Maximizing Algebraic Connectivitycited by 1
  7. 2024Spectral Graph Theoretic Methods for Enhancing Network Robustness in Robot Localizationcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint
  2. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  3. 2020GraphOpt: Learning Optimization Models of Graph Formation
  4. 2026From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs
  5. 2026Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning
  6. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
  7. 2025Reinforcement learning for graph theory, Parallelizing Wagner's approach
  8. 2025RIDGECUT: Learning Graph Partitioning with Rings and Wedges