# Minimize Control Inputs for Strong Structural Controllability Using Reinforcement Learning with Graph Neural Network

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

## 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 12 of its 27 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## 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, 12 of 12)

- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Directed Graph Convolutional Network](https://mlsanity.com/paper/2004.13970/) (2020)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/1807.01672/) (2018)
- [Co-training for Policy Learning](https://mlsanity.com/paper/1907.04484/) (2019)
- [A Framework for Structural Input/Output and Control Configuration Selection in Large-Scale Systems](https://mlsanity.com/paper/1309.5868/) (2013)
- [Minimum Input Selection for Structural Controllability](https://mlsanity.com/paper/1407.2884/) (2014)
- [Minimizing Inputs for Strong Structural Controllability](https://mlsanity.com/paper/1810.07220/) (2018)
- [A Unifying Framework for Strong Structural Controllability](https://mlsanity.com/paper/1903.03353/) (2019)

## Abstract (arXiv)

Strong structural controllability (SSC) guarantees networked system with linear-invariant dynamics controllable for all numerical realizations of parameters. Current research has established algebraic and graph-theoretic conditions of SSC for zero/nonzero or zero/nonzero/arbitrary structure. One relevant practical problem is how to fully control the system with the minimal number of input signals and identify which nodes must be imposed signals. Previous work shows that this optimization problem is NP-hard and it is difficult to find the solution. To solve this problem, we formulate the graph coloring process as a Markov decision process (MDP) according to the graph-theoretical condition of SSC for both zero/nonzero and zero/nonzero/arbitrary structure. We use Actor-critic method with Directed graph neural network which represents the color information of graph to optimize MDP. Our method is validated in a social influence network with real data and different complex network models. We find that the number of input nodes is determined by the average degree of the network and the input nodes tend to select nodes with low in-degree and avoid high-degree nodes.