图神经网络的组合优化和推理

摘要

组合优化是运筹学和计算机科学领域公认的领域。 直到最近，它的方法仍专注于孤立地解决问题实例，而忽略了它们通常源自实践中相关数据分布这一事实。 但是，近年来，人们对使用机器学习，尤其是图神经网络（GNN），作为组合任务（作为求解器或辅助函数）的关键构建块的兴趣激增。 GNN是归纳偏差，由于其排列不变性和稀疏性意识，可以有效地编码组合和关系输入。 本文针对优化领域和机器学习领域的研究人员，对这一新兴领域的最新关键进展进行了概念性回顾。

引言

如今，组合优化（CO）是跨学科领域，涵盖了优化，运筹学，离散数学和计算机科学，具有许多重要的实际应用，例如车辆路线选择或调度。 有关一般概述，请参见[71]。 直观上，CO处理从优化成本或目标函数的nite集合中选择一个子集。 尽管从复杂性理论的角度来看，许多CO问题由于其离散性而很难解决，但许多问题通常在实践中得到解决。 从历史上看，优化和理论计算机科学界一直在关注针对单个问题实例的最佳[71]，启发式[12]或逼近[130]解决方案。 但是，在感兴趣的许多实际情况下，通常需要解决重复共享模式和特征的问题实例。 因此，依赖数据的算法或机器学习方法，可能会利用这些模式，最近在CO领域获得了关注[9]。 这里的承诺是，通过利用给定实例中的通用模式，可以为实际情况开发更快的算法。
由于大多数CO问题的离散性以及现实世界中网络数据的普遍性，在CO领域中，图形（及其关系概括）是研究的主要对象。
例如，众所周知的相关问题（例如，旅行推销员问题和其他车辆路线问题）自然会导致图形结构（图1）。 实际上，从1972年Karp识别出的21个NP完全问题中，有10个是图优化问题的决策版本[66]。 其他大多数问题（例如集合覆盖问题）也可以在图形上建模。 此外，约束优化问题中变量与约束之间的相互作用自然会产生二部图。 这些图通常在其结构和特征上表现出模式，应采用机器学习方法。
1.1机器学习面临的挑战是什么？
在CO中成功应用机器学习方法存在若干关键挑战，尤其是涉及图形的问题。 图没有唯一的表示，即，重命名或重新排序节点不会导致不同的图。 因此，对于任何机器学习考虑到排列不变性的图形处理方法至关重要。 组合优化问题的实例很大，并且通常是稀疏的，尤其是那些来自现实世界的实例。 因此，所采用的机器学习方法必须具有可扩展性和稀疏性。 同时，所采用的方法必须具有足够的表现力，以检测和利用给定实例或数据分布中的相关模式。 机器学习方法应该能够处理辅助信息，例如客观和用户定义的约束。 当前大多数机器学习方法都在监督机制内。
也就是说，他们需要大量的训练数据来优化模型的参数。 在CO的背景下，这意味着解决许多可能困难的问题实例，这可能会阻止这些方法在现实世界中的应用。 此外，机器学习方法必须能够概括其训练数据之外的内容，例如，转移到不同大小的实例。
总体而言，可伸缩性，表达性和概括性之间存在折衷方案，其中任何一项都可能会产生冲突。 总之，主要挑战是：1.处理图数据的机器学习方法必须考虑节点排列的不变性。 他们应该利用给定图的稀疏度。
2.模型应区分所提供数据中的关键结构模式，同时仍能够扩展到大型实际实例。
3.需要考虑附加到节点和边缘的高维向量形式的辅助信息，即建模目标和附加信息。
4.模型应具有数据效率。 也就是说，理想情况下，它们应该工作而不需要大量标记的数据，并且它们应该可以转移到样本外实例。
1.2 GNN如何解决这些挑战？
最近，图神经网络（GNN）[49，113]成为一种机器学习架构，以（部分）应对上述挑战。
GNN的思想是通过聚合相邻节点的特征来迭代地计算输入图中每个节点的矢量表示，例如实矢量。 通过参数化此聚合步骤，使用（随机）一阶优化技术来适应给定的数据分布，以端到端的方式针对损失函数对GNN进行训练。 这里的承诺是，学习到的向量表示形式对关键的图结构进行编码，这些图结构有助于更有效地解决CO问题。 GNN在设计上是不变和等变的，即像CO求解器一样，它们会自动利用给定实例或数据分布固有的对称性。 由于其本地性，GNN通过汇总邻域信息，自然会利用稀疏性，从而导致稀疏输入的模型更具可扩展性。 而且，尽管可伸缩性仍然是一个问题，但它们会根据边的数量和所采用的参数线性缩放，同时考虑到多维节点和边的特征[49]，自然会利用成本和目标函数信息。 但是，了解数据效率仍然是很开放的尽管GNN具有明显的局限性（我们还将对此进行探讨和概述），但它们已被证明在CO环境中很有用。实际上，它们已在各种环境中应用，可以直接预测解决方案或作为集成解决方案。 现有求解器的组件。 我们将在调查范围内对这两个方面进行广泛调查。
1.3超越经典算法
先前的讨论主要涉及机器学习方法（尤其是GNN）的思想，替换和模仿经典组合算法或其中的一部分，可能会更好地适应自然出现的问题实例的特定数据分布。 但是，经典算法通过提取原始的真实世界输入，严重依赖于人工预处理或特征工程。 构成大多数CO问题的基础的离散图形输入很少是由原始数据直接引发的，因此需要昂贵且易于出错的特征工程。 这可能会导致与现实世界不符的偏见，从而导致决策不精确。 从长远来看，机器学习方法有可能进一步改善CO管道，从原始输入处理到以端到端的方式帮助解决抽象的CO问题。 最近已经提出了在此方向上可行的几种方法，我们将对其进行详细调查。
1.4 当前工作
在本文中，我们针对CO和机器学习研究人员，概述了在CO的背景下使用GNN的最新进展。 为此，我们对CO，各种机器学习机制和GNN进行了严格的介绍。 最重要的是，我们对CO环境中GNN的最新应用进行了全面，结构化的概述。
最后，我们讨论了使用GNN和未来工作所带来的挑战。 总而言之，我们的贡献如下：1.给出GNN在CO设置中的应用的完整，结构化概述，包括启发式和精确式。 此外，我们调查了使用基于GNN的端到端算法推理器的最新进展。
2.强调在合作组织背景下的GNN的缺点，并提供有关如何解决这些问题的指南和建议。
3.提供一份开放的研究方向清单，以刺激未来的研究。
1.5相关工作
GNN最近，图神经网络[49，113]（重新）作为图结构输入的领先机器学习方法而出现。 该体系结构的显着实例包括，例如，[34、57、131]和例如在[16、27、68、90]中提出的频谱方法，所有这些方法都源自[69、​​88、120]中的早期工作。 ，113]。 与该领域最近的普及程度相吻合，关于GNN技术的最新进展，存在大量的调查。 最近的一些包括[19，141，153]。
调查Bengio等。 [9]对CO的机器学习方法进行了高级概述，而没有将重点完全放在图结构的输入上，而[80]则在混合整数编程的上下文中着重研究了用于分支的机器学习。 此外，调查[87，147]侧重于对CO使用强化学习。[134]中的调查涉及针对电信中出现的网络问题的机器学习，重点是非精确的启发式方法，并且不包括最近的进展。 最后，[74]对GNN在各种推理任务中的应用进行了高层次的概述，而忽略了最新的发展，例如： 我们在这里详细研究算法推理的方向。

图卷积

直观地，GNN通过聚集来自相邻节点的信息来计算矢量表示，即a维矢量，表示一个图中的每个节点。 有关说明，请参见图3。 形式上，令（