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

arXiv: https://arxiv.org/abs/2610.12697 · HTML: https://mlsanity.com/paper/2610.12697/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 7 of 7)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A Distributed Algorithm for Solving a Linear Algebraic Equation](https://mlsanity.com/paper/1503.00808/) (2015)
- [Spectral Measurement Sparsification for Pose-Graph SLAM](https://mlsanity.com/paper/2203.13897/) (2022)
- [Algebraic connectivity: local and global maximizer graphs](https://mlsanity.com/paper/2110.01918/) (2021)
- [Split-Spectrum Based Distributed State Estimation for Linear Systems](https://mlsanity.com/paper/2210.01232/) (2022)
- [Optimal Robust Network Design: Formulations and Algorithms for Maximizing Algebraic Connectivity](https://mlsanity.com/paper/2304.08571/) (2023)
- [Spectral Graph Theoretic Methods for Enhancing Network Robustness in Robot Localization](https://mlsanity.com/paper/2409.15506/) (2024)

## 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.