文章信息
「来源」：Proceedings of the 39th International Conference on Machine Learning（ICML） 2022
「标题」：LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation
「作者」：David Ireland, Giovanni Montana
「链接」：https://proceedings.mlr.press/v162/ireland22a.html
「代码」：https://github.com/davidireland3/LeNSE
内容简介
组合优化问题出现在几个应用领域中，并且通常用图来表示。其中许多问题都是 NP 难的，但并不总是需要精确的解决方案。已经开发了几种启发式方法来提供接近最优的解决方案，但是，它们通常不能很好地随着图形的大小而缩放。本文提出了一种低复杂度的方法来识别原始图的（可能小得多的）子图，其中启发式可以在合理的时间内运行，并且很有可能找到全局接近最优的解决方案。本文方法的核心组件是 LeNSE，这是一种强化学习算法，它学习如何使用欧几里德子图嵌入作为其映射来导航可能子图的空间。为了解决 CO 问题，LeNSE 提供了一个判别嵌入，使用任何现有的启发式方法训练，仅使用原始图的一小部分。当使用具有多达 1000 万条边的真实图对三个问题（顶点覆盖、最大切割和影响最大化）进行测试时，LeNSE 识别出的小子图产生的解决方案与通过在整个图上运行启发式算法找到的解决方案相当，但只有一小部分总运行时间。
组合优化 (Combinatorial optimisation，CO) 问题涉及搜索目标函数的最大值或最小值，其域是离散但较大的配置空间。本文提出了一个基于监督学习和强化学习的通用框架，用于利用启发式算法，这些启发式算法是用广泛的领域知识制作的，但可能无法很好地扩展到大型问题实例。本文提出的算法 LeNSE（Learning to Navigate Subgraph Embeddings）学习如何修剪图，通过删除顶点和边显著减小问题的规模，以便启发式算法可以在很短的时间内找到接近最优的解决方案使用整个图表时会采取。本文的方法的动机来自于这样一个事实，即与精确解决方案相比，子图是更容易识别的目标。本文的方案不是在大海捞针，而是学习如何从大海捞针中取出不可能有针的部分。
图修剪过程被定义为一个顺序决策问题，使用 Q-learning (Watkins & Dayan, 1992) 来解决。从任何随机选择的固定大小的子图开始，LeNSE 依次将当前子图修改为稍微改变的子图，并重复此过程，直到当前子图被认为极有可能包含近乎最优的解决方案。为了有效地导航可能的子图空间，以便在最少的步骤中达到最高质量，LeNSE 依赖于一个有区别的子图嵌入作为其导航图。为了学习这种嵌入，本文利用几何深度学习的最新进展，特别是具有图粗化层的图神经网络 (GNN)。通过构造，嵌入子图的位置反映了它的预测质量。LeNSE 利用这些质量估计来学习最优的图修改，逐步将子图移向更有希望的区域。
在实验上，本文使用已建立的启发式方法在三个众所周知的 CO 问题上测试 LeNSE。本文广泛的实验结果表明，与完全不进行修剪相比，LeNSE 能够去除图的大部分，包括顶点和边，而性能没有任何显着下降，但只占整个运行时间的一小部分。本文还将 LeNSE 与两个基线、一个 GNN 顶点分类器和最近引入的修剪方法（Manchanda等人，2020）进行了比较。值得注意的是，本文表明所有训练都可以在问题图的一些小的随机样本上完成，同时能够在推理时扩展到更大的测试图。这意味着训练 LeNSE 所需的所有昂贵计算，例如运行启发式算法以获得解决方案，都只能在小图上完成。本文还表明，与不进行任何修剪相比，在大型图上使用 LeNSE 处理 IM 问题的速度提高了 140 倍以上。
方案介绍
问题定义
本文在图 上定义了一个 CO 问题，其中 是顶点集， 是边集。作者关注预算受限的问题，并依靠现有的启发式算法来找到接近最优的解决方案。最优解定义为顶点的子集 最大化目标函数 ，即
其中 是可行解的空间， 是可用预算。本文着手解决的问题包括找到 的最优子图，其中包含最优 个顶点，但顶点比 少得多。更准确地说，如果让 表示以图 作为输入的启发式求解器并返回最优解 ，有兴趣找到包含 个顶点的子图 ，其中 并且:
在实际中，这通常会产生 。
学习判别子图表示
本文最初的目标是为 的所有具有所需顶点数的子图学习欧几里得子图嵌入，稍后将其用作 LeNSE 的导航图。为此引入了一个编码器 将这些子图映射到 维空间，其中 是 的子图集。需要的一个基本属性是嵌入子图的坐标是关于子图包含接近最优解的可能性。为了促进学习导航策略的过程，编码器应该学习一种表示，使得共享相同标签的子图聚集在一起，形成近似单模态的点云，同时还保持跨集群的严格单调排序。考虑到这些要求，作者将 参数化为由卷积和可微粗化层组成的 GNN，其权重是通过最小化 InfoNCE 损失来学习的：
子图导航作为马尔可夫决策过程
从随机选择的子图开始逐步探索子图的过程被委托给遵循最优策略的代理。为了学习这样的策略，作者考虑了传统的马尔可夫决策过程 (MDP) 设置 (Bellman, 1957)。给定一个图 和一个子图映射函数 ，其中 是 的幂集， 是 的子图集。原则上， 可以是返回给定子图的任何函数一组节点。MDP 由元组 定义。
子图更新操作
在子图更新操作的设计中面临着保持动作空间小的挑战，同时能够改变当前子图的连接结构。本文提出的解决方案是允许代理的操作通过一次替换单个顶点来更新 。对于每个顶点 ，从 的单跳邻域中随机抽取一个候选顶点 ，然后代理可以决定将 与 交换；这由 表示。由于 ，有个可能的动作，如下图所示。
一旦得到，新的子图由确定，如下：
从这里可以看出，尽管每个时间步仅替换 中的单个顶点，但由于更新的顶点集邻域的变化，可以实现实质性的拓扑变化。这允许 LeNSE 学习如何有效地在嵌入式空间中移动。
引导式探索的 Q-Learning
为了学习子图导航策略，本文使用 Q-learning (Watkins & Dayan, 1992)。具体来说，考虑到问题的复杂性，实现了一个深度 Q 网络 (DQN) 算法 (Mnih et al., 2015)，其网络权重由 θ 参数化。通常，在 Q-learning 中采用 ϵ-greedy 探索策略，其中策略采用贪婪动作，概率为 1 - ε，随机动作，概率为 ε。当在图的一小部分上训练 LeNSE 时，可以利用这样一个事实，即在学习子图嵌入的初始阶段，在整个训练图上运行启发式算法，因此知道最佳 顶点是先验的。作者建议通过强制代理在可能的情况下选择这些最佳顶点之一，将这种先验知识注入到探索策略中，从而引导代理朝着目标前进。
「带有引导探索的完整 LeNSE 算法如下:」
实验分析
本文希望评估 LeNSE 修剪图的能力，以及可以在修剪后的图上找到的解决方案的质量。为此本文报告了两个主要指标：1）最终子图中的顶点/边数；2) 达到的最终比率。请注意，使用由启发式在测试图上找到的集合 。在下表中报告了 LeNSE 和竞争方法的这些指标。
可以看到，对于每个问题和数据集，LeNSE 都能够找到一个最佳子图（即比率大于 0.95）。有趣的是，可以看到对于 Wiki-MVC，启发式能够在子图上找到比在原始图上更好的解决方案。这是可能的，因为用于 MVC 的贪心启发式算法具有 60% 的近似率，因此在噪声较少的情况下，启发式算法能够找到比在整个图上更好的解决方案。
总结
本文介绍了「LeNSE，这是一种新颖的图修剪算法，可以找到包含 CO 问题解决方案的最优子图」。LeNSE 不是一个单一的算法，而是一个通用框架，可以与任何现有的启发式方法结合使用，以解决大规模问题。
在使用真实世界图数据集调查的所有设置中，本文发现可以在图的一小部分上进行训练，能够扩展到图的保留部分而不会降低性能。本文还发现，LeNSE 找到的子图比原始图小很多，在最好的情况下，超过 90% 的图顶点和边都被删除了。除此之外，本文还证明，在大多数情况下，LeNSE 找到的子图是预算低于编码器被训练识别的预算的最佳子图。本文将 LeNSE 与两种基线方法进行了比较，本文发现 LeNSE 能够提供更好的比率，或者在仍然找到最佳子图的同时修剪更多的图。除此之外，LeNSE 能够在所有问题上始终如一地表现出色。
最后，本文展示了在具有近 500 万条边的图上使用 LeNSE 的好处，表明与不进行任何修剪相比，LeNSE 实现了 140 多倍的速度提升。未来工作的潜在途径包括替代图修改操作，本文只考虑用其邻居之一替换顶点，并在子图中包括某个顶点子集的所有单跳邻居。除了此处介绍的预算受限版本之外，作者还计划进一步研究 LeNSE 在其他 CO 问题上的表现。
