.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Machine learning
Greedy algorithms
Training
Optimization
Computer architecture
Controllability
Scalability
Zero-forcing Set
graph convolutional network
network controllability
leader selection problem
Journal
I
IF:
7.9
Papers:
2.6K
Citations:
10.0K
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSave
View more