.png){kind=icon}
返回
A Graph Machine Learning Framework to Compute Zero Forcing Sets in Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TNSE.2023.3337750.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This article studies the problem of computing zero-forcing sets (ZFS) in graphs and provides a machine-learning solution. Zero-forcing is a vertex coloring process to color the entire vertex set from a small subset of initially colored vertices constituting a ZFS. Such sets have several applications in network science and networked control systems. However, computing a minimum ZFS is an NP-hard problem, and popular heuristics encounter scalability issues. We investigate the greedy heuristic for this problem and propose a combination of the random selection and greedy algorithm called the random-greedy algorithm, which offers an efficient solution to the ZFS problem. Moreover, we enhance this approach by incorporating a data-driven solution based on graph convolutional networks (GCNs), leveraging a random selection process. Our machine-learning architecture, designed to imitate the greedy algorithm, achieves significant speed improvements, surpassing the computational efficiency of the greedy algorithm by several orders of magnitude. We perform thorough numerical evaluations to demonstrate that the proposed approach is considerably efficient, scalable to graphs about ten times larger than those used in training, and generalizable to several different families of synthetic and real-world graphs with comparable and sometimes better results in terms of the size of ZFS. We also curate a comprehensive database comprising synthetic and real-world graph datasets, including approximate and optimal ZFS solutions. This database serves as a benchmark for training machine-learning models and provides valuable resources for further research and evaluation in this problem domain. Our findings showcase the effectiveness of the proposed machine-learning solution and advance the state-of-the-art in solving the ZFS problem.
Keyword:
Machine learning
Greedy algorithms
Training
Optimization
Computer architecture
Controllability
Scalability
Zero-forcing Set
graph convolutional network
network controllability
leader selection problem
期刊
I
IF:
7.9
论文数:
2.5K
被引数:
10.0K
机构
引用论文
.png){kind=icon}
Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks网络上演化的系统的零强迫，线性和量子可控性
OAAI
OAAI分享收藏分享收藏Deep reinforcement learning for transportation network combinatorial optimization: A survey交通网络组合优化的深度强化学习研究综述
PREAI
分享收藏
查看更多内容