基于深度学习求解图优化问题初探

摘要：图优化问题是组合优化问题的重要子类，在很多实际场景中有非常广泛的应用，例如网络分析、芯片设计、图像处理等。大部分图优化问题都是 NP 困难的。Karp 提出了 21 个 NP 完全问题，其中有 10 个是图优化问题，还有一些问题可以转化成图优化问题。大家熟知的

导读今天分享的内容是关于运用深度学习求解图优化的问题。

主要分为以下四个部分，欢迎大家讨论：

1. 背景介绍

2. 现有研究及挑战

3. 解决思路及实现

4. 未来展望

图优化问题是组合优化问题的重要子类，在很多实际场景中有非常广泛的应用，例如网络分析、芯片设计、图像处理等。大部分图优化问题都是 NP 困难的。Karp 提出了 21 个 NP 完全问题，其中有 10 个是图优化问题，还有一些问题可以转化成图优化问题。大家熟知的旅行售货商问题、最大独立集问题、最大割问题都属于图优化问题的范畴。

传统解决图优化问题的算法包括三类：精确算法、近似算法、启发式算法。

精确算法的优点是可以得到问题的精确解，但对于 NP 困难问题，精确算法的时间复杂度是指数级别的，计算量非常大。当问题规模扩大的时候，精确算法的消耗非常巨大，就变得不实用了。

近似算法在可以接受的时间内得到问题的一个近似解，好处是有近似比这个理论上的保证。缺点也是当问题规模扩大的时候，仍然会产生比较大的耗时。

启发式算法，例如模拟退火算法、遗传算法、蚁群算法等，这类算法的优点是比较快，缺点是解的质量没有保证。

传统算法面临着一些挑战：

泛化能力弱：为一个图优化问题设计的算法，往往很难用于求解其他的图优化问题。比如为 TSP 问题的算法，很难运用到解决最大独立集问题。效率不高：对于问题的每一个实例都要从头开始运行算法，需要迭代很多次求出最终的解，即使两个实例之间，只是数据上做了一点点的修改，也需要重新运行算法，效率不高。难度较大：现实中出现的问题规模和复杂度越来越大，如果只靠人工设计算法会越来越困难。

深度学习是机器学习的一个子类，是利用深度神经网络进行求解。深度学习的优势主要在于它的自动学习，它可以从大量的数据中自动学习经验和规律，得到问题的近似解。把深度学习用到图优化问题上会带来以下几个优势：

深度学习算法可以从大量的数据或经历中自动学习规律或经验，来得到问题的近似解；而人工算法需要利用领域的专业知识及数学直觉，并经历很多试错和调试的过程。机器学习算法可以适用于多个图优化问题，如 S2V-DQN（Learning combinatorial optimization algorithms over graphs. NeurlPS，2017）可以解决 TSP、MVC、MaxCut；而传统算法一般只针对一个图优化问题，很难推广到其他图优化问题。深度学习算法有可能挖掘人工算法很难发现的有用性质。解决最小点覆盖问题的时候，以往用启发式策略，贪婪选取度数比较大的点来覆盖尽可能多的边。在上文提到的 2017 年发表的文章中，利用深度学习算法发现，在取度数较大点的同时，还需要去保证把这些点删掉后剩下的图的连通性也要比较好，这两种启发式策略相结合能得到更优的解。

现有研究及挑战

我们的终极目标是基于深度学习得到一个通用的图优化问题求解器，距离这一目标还有很远的路要走。下面介绍一些现有的研究工作。

深度学习有三种范式：监督学习、强化学习和无监督学习。

1. 监督学习

监督学习，就是将一个问题实例输入模型当中得到一个预测值，然后把这个预测值和真实值（也就是这个问题的最优解）进行对比，算出其差异，再通过这个差异去调节模型的参数。但大多数图优化问题是 NP 困难问题，它的真实值或者说最优解是很难获取的，所以这种方式会面临着数据标签获取上的挑战。监督学习在初期 2018 年、2019 年的时候有一些研究成果。

2. 强化学习

强化学习是从奖励中学习策略，从而克服缺乏标签（最优解）的限制。但是在大规模图中，它的训练速度会比较慢。我们可以把强化学习定义成一个马尔可夫决策过程，有智能体、环境和状态空间、动作空间以及奖励函数，预期最大化累计折扣奖励期望。这个方面的文章也有许多，上图中列出了其中两篇。

3. 无监督学习

无监督学习，是通过一些无监督的损失函数来学习的，损失函数中不牵涉到最优值，从经验上来看速度更快，比较适合处理大规模的图优化实例。但难点在于无监督损失函数不容易设计。

4. 几篇相关的论文

ClusterNet，用到了图卷积神经网络 GCN 和 K-means 的方式去做聚类，应用于去解决社区发现问题和设施选址问题。

EGN ，里面用到了比较经典的 Erdős 概率方法，定义了可微的损失函数，使用导出的损失以无监督的方式训练图神经网络 GNN，输出节点上的概率分布，并从概率上证明了低成本可行解的存在性。得到的解不一定是最优解，而是一个质量比较高的解，可以应用于解决最大团问题和图划分问题。

GON，其中的网络结构比较简单，利用拉格朗日乘子算法和 KKT 条件，把约束条件以惩罚项的形式整合到损失函数里面，将有约束的问题转化成无约束的问题来进行求解，用来解决了最大独立集问题和均衡图划分问题。

以上研究工作主要集中在设计无监督的损失函数以及设计网络结构上，比如在损失函数上加一些惩罚项，或者运用一些经典的理论方法（如概率方法、K-means、最优传输理论等）。

5. 挑战

目前，我们认为仍然存在两大挑战：

现有工作在捕获潜在的结构信息和语义信息方面有所欠缺。大多数现有工作是对每个测试实例直接优化，导致过拟合，从而泛化性能不高。

解决思路及实现

我们主要聚焦图聚类优化问题，即把图中的顶点划分成若干个簇，在一些约束条件下最大化或者最小化特定的目标。

1. 图聚类优化问题分类

我们将图聚类优化问题分成两类：基于质心的和非基于质心的。基于质心的是从图中选出若干个点作为质心，而将其余点分配给质心；非基于质心的不会挑出一些特殊的点，只是关注于将整个图的顶点划分到不同的簇中。

基于质心的图聚类优化问题

基于质心的非常经典的问题是设施选址问题，给定 n 个节点的坐标，需要从这 n 个节点中选出 k 个，这 k 个节点称为设施点，会在这些节点上安排一些设施（比如超市），其他没有被选中的节点称为客户点，客户点会选择一个距离最近的设施点为其提供服务。目标就是要使得每个客户点与之距离最近的设施点之间的距离之和最小，这里给出了相应的数学规划形式。

非基于质心的图聚类优化问题

非基于质心的图聚类优化问题，例如平衡图划分问题 BGP，即给定 n 个节点，想把这个 n 个节点分成 k 个簇，希望这 k 个簇所含的点数尽可能相等，还有另外一个目标是要使得这 k 个簇之间的边尽可能的少，就是不同部分之间的边尽可能的少。由于一个图的总边数是固定的，想要最小化子图之间的边数，就等价于使得子图内部的边数最大化，所以就转化成了使得内部边数最大化的问题，上图中给出了相应的数学规划形式。

2. 自监督模型

我们提出了一个自监督的模型，自监督是无监督的一个子类，通过数据变换产生自监督的信号来训练模型。

模型框架

整个框架分成了三个部分，第一部分是 Pre-Training 预训练；第二部分是 Fine-Tuning 微调，第三部分是 Rounding 舍入，最终输出问题的一个解。

在 Pre-Training 阶段，输入一个训练图，进行图对比学习，对中心节点选取一些正样本，再选取一些负样本，把正样本和负样本输入到图编码器中，得到相应的表示，利用表示计算对比损失，然后根据对比损失反向传播，并根据梯度下降去调节图编码器的参数。这里的对比损失函数是在经典的 InfoNCE 损失函数上做了改进，给负样本添加了权重，从而避免假负样本（false negative sample）的问题。

第二阶段是 Fine-Tuning，把一个测试图输入到训练好的图编码器中，得到表示，再经过线性层、Softmax 层，输出有两种形式，二维矩阵的形式比较适用于均衡图划分问题，每个节点在不同的类别中有不同的概率，另一种是对矩阵的行向量求和得到一个向量，向量的形式比较适用于设施选址问题，每一个节点有一个值，代表它被选中作为设施点的概率。然后计算目标损失 Target Loss，通过反向传播去调节模型参数。调的时候有两种模式，一种是 Partial fine-tuning，只调线性层，另一种是 Full fine-tuning ，同时调线性层和图编码器层。

经过若干次迭代后，进入第三个阶段 Rounding，前一阶段输出的是概率，0 到 1 之间的一个值，现在通过舍入得到问题的可行解，比如均衡图划分问题，对每一个节点给它划分到某一个类别；对于设施选址问题，输出最终被选为设施点的编号。

图编码器

图编码器是框架中非常重要的一个结构，主要有三个部分：特征编码，度数编码和距离编码。后两个编码主要是挖掘图的结构信息，提高模型的表达能力。这三部分会拼接在一起，经过线性层得到图的表示。

此外，在预训练阶段还用到了图对比学习，产生自监督信号。图对比学习可以学习到节点之间的相同或不同，帮助形成更好的聚类。

3. 实验部分

（1）设施选址问题

设施选址问题的评价指标是目标函数值、与最优值之间的间隙，还有运行时间（这里的运行时间是测试时间，不含训练时间）。

合成数据集测试

以上是在合成数据集（ER 随机图）上的实验结果，GCOM 是我们提出的模型，其中 GCOM(F)代表 Full fine-Tuning 模式，GCOM(P)代表 Partial fine-tuning 模式，GCOM(F)的性能会比 Gurobi(60s) ——Gurobi运行 60s 得到的解、Greedy 以及三种深度学习算法更优一些。相较于 Gurobi(Opt)这个最优解而言，GCOM(F)的 gap 是 5% 左右，但时间会少很多。

真实数据集测试

我们也在星巴克门店的实际数据集上进行了测试。用一张 500 个点的随机图做了训练，然后在上海市和首尔市的星巴克数据集上做了测试，以上是测试结果，性能都是比较好的。星巴克数据集的数据分布，跟训练集的随机图分布是不一样的，这说明了模型具有比较好的分布外泛化能力，而且预训练的时候只用了一张图，说明模型有比较良好的采样有效性。

测试发现，当点数固定，设施点数 k 增大的时候，参数的敏感性也表现得比较稳定。

在 500 个点的随机图上预训练，然后分别在 300 个点、800 个点和 1000 个点的随机图上做了测试，性能变化也不大，展现了比较好的泛化能力。

（2）均衡图划分问题

均衡图划分问题评价指标有两个：一个是子图内的边数，越大越好；另一个是平衡约束度量 BCI，用来测试划分的均衡程度，越小越好。

合成数据集测试

合成数据集采用的是聚类问题中比较常用 SBM 模型，可以设定划分成几个簇，簇内连边概率 Pin 和与其他簇连边的概率 Pout。在这个实验里，我们设置了五种情形（见 Table 1），Table 6 是实验结果。此处的预训练使用了 Case4，Pin=0.2，Pout=0.05，在五种情形下都做了测试，性能都取到了最优。

真实数据集测试

对三个引文网络的真实数据进行了实验，实验结果见 Table 7。这个实验中的对比算法有图划分方面比较经典的 METIS 算法和 5 种深度学习模型，我们的模型均取得了最优的表现。

此处预训练使用了一张 1,000 个点，Pin=0.2，Pout=0.05 的 SBM 图，与用来测试的真实引文网络的数据分布不一样，再次验证了模型优秀的分布外泛化能力。另外三个测试数据集分别有两千多个点、三千多个点和 1 万多个点，但预训练的图只有 1,000 个点，说明模型也有比较良好的采样有效性。

参数 λ 的敏感性

LBGP 是均衡图划分问题中的损失函数，其中前一部分表示内部边数，后一部分表示均衡程度，并在均衡程度前面加了一个系数 λ。λ 越大，第二部分就看得越重，也就是说均衡性会越好，BCI 指标会越低，实验结果也证明了这一点。但是λ越大，内部边数可能会变差。最终通过实验发现 λ=10 的时候是两个指标都比较好的情形，所以实验当中也是这样设置的。

最后，我们还做了消融实验，证明了这几种策略——对比学习、度数编码、距离编码都是有效的。