NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs-猫眼课题宝

DOI：

发表时间：

2021

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Evan McCarty;Qi Zhao;Anastasios Sidiropoulos;Yusu Wang

近年来，使用神经网络来帮助解决组合优化问题（包括图优化问题）的方法激增。然而，对这种方法的理论理解仍然有限。在本文中，我们考虑几何设置，其中图是由固定维欧氏空间中的点诱导的。事实证明，几个图优化问题可以近似（在一个双准则的方式）通过一个算法，运行在时间上的线性图大小n通过一个框架，我们称之为贝克范式。贝克范式的一个关键优点是它将输入问题分解为（最多线性数量的）有界大小的小子问题（与输入的大小无关）。对于这类有界大小的子问题，我们现在可以设计具有通用近似保证的神经网络来解决它们。这导致了一个混合算法ML框架，我们称之为NN-Baker，它有能力在输入图大小的时间线性上近似解决一族图优化问题（例如，最大独立集和最小顶点覆盖）。我们通过CNN版本和GNN版本实例化了我们的NN-Baker，并通过一系列实验证明了我们方法的有效性和效率。

Recent years have witnessed a surge of approaches to use neural networks to help tackle combinatorial optimization problems, including graph optimization problems. However, theoretical understanding of such approaches remains limited. In this paper, we consider the geometric setting, where graphs are induced by points in a ﬁxed dimensional Euclidean space. It turns out that several graph optimization problems can be approximated (in a bicriteria manner) by an algorithm that runs in time linear in graph size n via a framework that we call the Baker-paradigm. A key advantage of the Baker-paradigm is that it decomposes the input problem into (at most linear number of) small sub-problems of bounded sizes (independent of the size of the input). For the family of such bounded-size sub-problems, we can now design neural networks with universal approximation guarantees to solve them. This leads to a mixed algorithmic-ML framework, which we call NN-Baker that has the capacity to approximately solve a family of graph optimization problems (e.g, maximum independent set and minimum vertex cover) in time linear in the input graph size. We instantiate our NN-Baker by a CNN version and GNN version, and demonstrate the effectiveness and efﬁciency of our approach via a range of experiments.

NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs

文献摘要

相似文献