← Back to all news
arXiv Machine Learning

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

The paper tackles the problem of designing graph topologies that maximize algebraic connectivity while keeping the number of vertices and edges fixed. It introduces a two‑stage, density‑dependent approach: first constructing a low‑cost structural backbone—using complete multipartite graphs in dense settings and Cayley graphs in low‑to‑intermediate settings—then refining the remaining edges with a reinforcement learning completion stage. Numerical experiments demonstrate that this method achieves high algebraic connectivity with good runtime scalability, outperforming existing techniques and supporting a structural‑family‑first strategy for scalable network design.

Related stories

arXiv AI
Sep 18

Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint

The paper presents a reinforcement learning approach to generate graph ensembles that satisfy a hard assortativity constraint, a measure of degree–degree correlation between adjacent nodes. Unlike traditional soft-constraint methods, the learned policy performs degree-preserving rewiring to meet the exact target, reducing generation cost by at least an order of magnitude while preserving over 98% of configurational diversity. Trained on small graphs, the method generalizes to larger sizes and different topologies, allowing precise control over secondary observables such as the clustering coefficient.

By Hoyun Choi, Junghyo Jo, Deok-Sun Lee
reinforcement-learning
More like this →
arXiv Machine Learning
Sep 11

From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs

The paper introduces Graph-Guided Quasimetric Dense Reward (G2QDR), a framework that learns a state connectivity model to predict pairwise connectivity strengths in asymmetric environments. These strengths are converted into scalar auxiliary dense rewards, offering continuous guidance across hierarchical levels. G2QDR can be integrated into any existing Goal-Conditioned Hierarchical Reinforcement Learning architecture and shows empirical performance improvements in sparse reward settings with modest computational cost.

By Shuyuan Zhang, Zihan Wang, Xiao-Wen Chang, Doina Precup
reinforcement-learning
More like this →
arXiv AI
Jul 13

Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning

arXiv:2605. 17393v2 Announce Type: replace Abstract: Coordination graphs are a central abstraction in cooperative multi-agent reinforcement learning (MARL), yet existing sparse-graph learners lack a theoretically grounded mechanism to decide which edges should exist and how much information each edge should carry.

By Wei Duan, Junyu Xuan, En Yu, Xiaoyu Yang, Jie Lu
agentsreinforcement-learning
More like this →