A Differentiable Approach to the Maximum Independent Set Problem Using Graph-Based Neural Network Structures
A Differentiable Approach to the Maximum Independent Set Problem Using Graph-Based Neural Network Structures
复制标题
DOI：
10.1109/mlsp55214.2022.9943476
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Ismail R. Alkhouri;George K. Atia;Alvaro Velasquez
中科院分区：
文献类型：
--
作者：
Ismail R. Alkhouri;George K. Atia;Alvaro Velasquez
在给定的图中寻找最大独立集问题是一个已知的NP-Hard问题，在各个领域有着广泛的应用。在这项工作中，我们提出了一种新的方法来解决管理信息系统问题，它依赖于将图简化为神经网络(MISNN)，其结构由底层图的连通性导出。MISNN的输入被作为一个公式化的箱约束非线性优化规划的解来获得，然后根据最小化输入的定义映射得到该管理信息系统。基于不同模型生成的图的实验结果表明，无论是在所发现的管理信息系统的规模上，还是在运行时间上，所提出的方法都优于著名的NetworkX python库的近似求解器。
The problem of finding a Maximum Independent Set (MIS) in a given graph is a known NP-hard problem with many applications in various domains. In this work, we propose a novel approach to the MIS problem which rests on a reduction of the graph to a Neural Network (MISNN) whose structure is derived from the connectivity of the underlying graph. The input to the MISNN is obtained as a solution to a formulated box-constrained non-linear optimization program, then the MIS is obtained from a defined mapping of the minimizing input. Our experimental results using graph generated from various models demonstrate that the proposed method outperforms the approximate solver of the well-known NetworkX python library, both in the size of the found MIS and the run-time.