对该领域了解不多，建议参考其他推送或论文原文：
Nat. Mach. Intell.：图神经网络(GNN)，组合优化
亚马逊团队使用受物理启发的图神经网络来解决组合优化等问题
…

组合优化问题：同时面对许多决策，每一个决策只有yes/no这两个值被视为0-1变量。然后解决空间是所有0-1变量的组合。每个不同的决策组合都会得到一个目标函数值（如成本或收入），这是优化的对象。

组合优化问题的两个相关例子是最大的切割和最大的独立集。给出一张图片，可以简单地理解为对每个节点进行一次分类：

这篇论文可能做了这样一件事：将组合优化问题转化为图片上的最大切割或最大独立集QUBO进一步转化为图节点二分类问题。然后用图神经网络处理节点间的邻接信息QUBO作为神经网络，目标函数松弛用连续分类概率代替离散的0-1变量loss训练图神经网络(输出节点类别概率)的函数。最后，每个节点/变量的0-1值用阈值分割。

一般流程如论文插图所示：

将组合优化问题的每个变量视为图中的一个节点。如果两个变量之间存在某种关系，则两个节点用一个无向边连接。组合优化问题可以表示为图，作为图中的二分类问题，目标是将图中的节点分为0-1两类。更具体的是，本文中提到的例子被转换为最大切割或最大独立集问题，或其加权或约束。

图中的二分类问题使用图神经网络GNN解决方案。由于该图的节点没有特征，只有一个节点的序列号，因此首先将图输入神经网络，以随机初始化图的每个节点。神经网络的输出是每个节点类别的概率。

二分类问题loss函数设置为松弛的哈密顿量，即前面提到的QUBO表示的目标函数。用神经网络输出的每个节点的类别概率(0-1之间的浮点数)代替0-1变量，用同样的方法计算哈密顿量获得loss值，然后进行梯度下降训练神经网络。放松是为了使目标函数连续化和可导化（否则梯度无法获得）。

如上图所示，组合优化的原始目标函数是$H_{QUBO}=X^{T}QX$，其中的$X$是所有变量/节点取值按顺序排列的0-1组合，例如$[0,1,0,0,...,1{]}^T$这样的一个矩阵。而$Q$是对应问题的QUBO矩阵，该矩阵如何写出参考前面的内容，上图a部分给出了最大割与最大独立集对应的$Q$矩阵形式。

松弛后的目标函数变为${\mathcal{L}}_{QUBO}=P(\theta {)}^{T}QP(\theta )$，其中$P(\theta )$是神经网络的输出，是一个被sigmoid函数压缩到0-1之间的浮点值，例如$[0.1,0.9,0.5,...,0.8{]}^T$这样一个值。

最终，当目标函数收敛的之后，拿到神经网络的输出$P(\theta )$，按照阈值选择节点的类别。在源码中，该参数是PROB_THRESHOLD=0.5。

在代码实现上，该论文使用了基于pytorch后端的dgl库，使用dgl.nn.pytorch.conv.GraphConv(in_feats, out_feats, norm='both', weight=True, bias=True, activation=None, allow_zero_in_degree=False)（官方文档）实现了一个简单的两层图卷积，用来解决最大独立集的问题。其他的问题并未包含其中，在其他问题中使用需要在gen_q_dict_mis()函数中定义具体问题的Q矩阵。

初始化图节点张量的方法在源码./utils.py的get_gnn()函数中，使用nn.Embedding(n_nodes, dim_embedding)初始化了一个查词表，作为1.1中提到的节点集（形状[节点数量，节点特征长度]）作为输入。

从源码来看，神经网络的输出的图卷积层定义如下：self.conv2 = GraphConv(hidden_size, number_classes).to(device)，而相应的参数被设置为'number_classes': 1，最后输出时用h = torch.sigmoid(h)过了一层sigmoid。这说明神经网络输出的$P(\theta )$维度是与原0-1变量$X$一致的，在0-1之间的浮点值。

在loss_func(probs, Q_mat)这一函数中，直接看到该loss的求法是cost = (probs_.T @ Q_mat @ probs_).squeeze()，这与1.2.1是一致的。源码的probs或probs_变量就是1.2.1的神经网络的输出$P(\theta )$，也就是源码中的probs = net(dgl_graph, inputs)[:, 0]。

个人感觉这篇文章有意思的地方在于：这番操作简洁的有点反直觉，甚至有点艺术，然而效果很好，甚至达到sota。它把一个离散的目标函数简单地松弛为连续量，作为loss函数拿神经网络简单训练一下，就能求解离散的组合优化问题，甚至是一个NP难问题。同时，它泛用性很强，一次性的将图上的组合优化问题统一在二分类的框架下，一并解决了，并且能用于许多现实问题。除此之外，这一方法能够求解百万级别变量的大规模问题，而其他方法有些困难。最后，这个方法跨越几个领域，其QUBO的操作和量子退火算法有些关系（毕竟论文标题就是物理启发的图神经网络组合优化），能在量子退火上处理的问题应该也能用这个方法处理。另外涉及到了运筹优化、图论、机器学习等领域的一些知识。

前面的部分比较抽象，这一部分就举几个简单的例子演示一下这个组合优化求解器在实际问题中的应用。这一部分对应论文第六部分APPLICATION IN INDUSTRY，更具体的内容（如目标函数）可以直接阅读原文及对应参考文献。应用的方法就是将实际问题转化为一个图上的问题，用这个GNN求解器求解图的最大割或最大独立集等QUBO问题。

面对大量的投资项目，风险分散是很有必要的。两个项目的关联越紧密，其面对的风险就越一致。为了分散风险，我们希望找到这些项目中关联性最小的一批项目来进行投资，每个项目的投资只有是或否两种状态。

这可以转化为一个图上的最大独立集问题。我们将每一个投资项目视为一个节点，如果两个投资项目比较相关，那么把它们用一条边相连。由于图的最大独立集的节点之间没有边相连，那么最大独立集节点所代表的项目之间关联就最不紧密。

这样，将项目构建的图送进该论文的GNN求解器，用它求最大独立集，就可以得到可以投资的项目组合。

考虑如下场景：只有一台机器，但是有多个任务需要执行，每个任务有确定的起点与终点时间，在每个任务执行的期间不能做其他的事情。最多能够完成几个任务呢？（是任务个数而不是总工作量）

这个问题可以转化为一个求最大独立集的问题。把每个任务视作一个节点，如果两个任务间存在冲突（即两个任务持续的时间区间存在重合），那么就将两个任务用一条边相连。这样，任务间的互相冲突可以表达为一个图。这个图上的最大独立集所代表的任务，就是最多能够完成的任务集，因为这些节点互相之间没有边相连，所代表的任务也不存在冲突。

把这一冲突关系图送入求解器，求最大独立集，就可以解决问题。

如果希望总工作量最大，那就是一个加权的最大独立集问题，同样能够用QUBO表示，并松弛后用该求解器求解。

源码比较简单，而且注释等写的很详细，值得学习。相关代码只有./utils.py和./gnn_example.ipynb两个文件。./utils.py中是一些依赖的具体的方法，内容包括图神经网络的定义class GCN_dev(nn.Module)、用以测试的随机图的生成generate_graph()、损失函数的构建（这里只有MIS最大独立集的）loss_func(probs, Q_mat)、神经网络的训练逻辑（也就是该求解器的求解过程）run_gnn_training()。./gnn_example.ipynb是运行的主文件，包括超参数的设置，用图神经网络求解器、networkx自带的图求解器，分别求解MIS问题等。.ipynb文件需要在jupyter notebook中运行，如果想在其他IDE中运行，在jupyter notebook打开后可以将其导出为.py文件，参考JupyterLab中如何导出py格式文件。

跑示例代码，只需要将官方源码下载解压，并按照./requirements.txt安装所有依赖库，直接运行./gnn_example.ipynb即可。

requirements.txt是几乎每个深度学习仓库中都会存在的内容，里面写明了该仓库的依赖库及其版本，直接利用该文件可以快速配置仓库的运行环境。在这一官方源码中也存在。下面的内容在win10下进行，其他操作系统流程应该差不多。

1、首先下载项目文件https://github.com/amazon-research/co-with-gnns-example，并解压到文件夹中。
使用anaconda来管理虚拟环境，官方库提供以下命令来安装依赖库：

conda create -n <environment_name> python=3.8 --file requirements.txt -c conda-forge -c dglteam -c pytorch

2、安装anaconda并设置环境变量，参考该文章Anaconda安装（过程详细）。
3、安装好之后，打开anaconda prompt，并cd到项目文件夹，也就是requirements.txt所在文件夹下，打开参考打开anaconda prompt的操作步骤，cd参考anaconda prompt中cd到指定目录。

上面那行命令的意味着该处需要填写一个变量名，随便设置一个名字就行。例如下面这样：

conda create -n pytorch python=3.8 --file requirements.txt -c conda-forge -c dglteam -c pytorch

4、直接在刚刚cd好的anaconda prompt中运行该命令即可创建一个虚拟环境并安装依赖库。

5、运行该虚拟环境的jupyter notebook（在requirement.txt里面一并安装了），然后导入该项目，直接运行./gnn_example.ipynb即可，需要注意路径需要在项目文件夹下。

由于我已经有了一套pytorch的虚拟环境，因此只需要单独安装一部分依赖库即可。但是如果所安装库与python版本和requirement.txt不对应，可能会产生一些bug，这是由于一些库版本不同，相同功能的接口可能改变或者取消。需要找到新版本中对应的功能，稍微改变一下源码才能跑。

1、安装pytorch：pytorch是依赖的深度学习库，进入pytorch官方网站，选择cuda版本进行conda安装，cuda版本的选择与gpu的驱动、pytorch的版本支持有关。需要注意的是，不需要像前几年那样在电脑上配置任何cuda、cudnn软件，只需要安装conda命令下的cudatoolkit这个库即可，安装tensorflow也是如此。

2、安装dgl：dgl是基于pytorch等库实现的图神经网络库，进入dgl官方网站，同样像上述pytorch那样安装即可。

3、安装networkx：networkx是用以处理图结构的python库，直接conda install networkx。

安装完后，同样在ide中直接运行./gnn_example.ipynb即可。

在运行时，我出现了如下问题：ModuleNotFoundError: No module named 'networkx.algorithms.approximation.independent_set'，这是由networkx版本不对应导致的，independent_set这个模块用来求图的一个独立集，只影响到源码第6步，图神经网络求解器还是能够正常使用的。requirements.txt中的networkx库版本是2.5，而我直接安装的版本是2.7.1，在2.7.1中这一方法的接口改变了，参考networkx官方文档。

解决的方法是：把./gnn_example.ipynb中的该行代码（上面那行），换成下面一行：

from networkx.algorithms.approximation.independent_set import maximum_independent_set as mis #2.7.1找不到该库，仅影响第6步
from networkx.algorithms.mis import maximal_independent_set as mis #2.7的写法，上面那个是2.5

官方的requirements.txt与我使用的库的版本如下，我使用的gpu是3060：

./co-with-gnns-example/requirements.txt内容：
# -c dglteam
dgl==0.5.3
# -c pytorch
pytorch==1.7.1
# -c conda-forge
numpy==1.19.5
networkx==2.5
jupyter==1.0.0
requests==2.25.1
matplotlib==3.3.2

我的虚拟环境库版本：
dgl-cuda11.1              0.8.2
torch                     1.8.1+cu111
numpy                     1.22.3
networkx                  2.7.1
matplotlib                3.2.2
python                    3.8.8
cudatoolkit               11.1.1

当配置好虚拟环境后，在ide中打开./gnn_example.ipynb，并按需要对库接口做上述修改后，直接运行即可。注意ide里的路径需要是项目文件夹./co-with-gnns-example/，这是由于./gnn_example.ipynb中调用了同目录下的./utils.py文件的函数，若路径不对是找不到它的。

示例代码产生一个随机图，演示了一下该论文求解器求解该随机图最大独立集（MIS）问题的方法，其他如求最大割的内容并未涉及到。

生成随机图的函数是generate_graph()，直接在./utils.py下找到该方法，有详细的说明。示例的参数是n=100，d=3，graph_type=‘reg’，这意味着生成一个随机图，有100节点，度为3。这个接口还实现了多种类型的图生成方法。

对于用该函数生成的随机图nx_graph，该文件中用该论文的GNN求解器、networkx库的maximal_independent_set()方法分别求解并比较了结果，做了一个简单的可视化。直接运行结果如下：

runfile('C:/Users/Administrator/Desktop/co-with-gnns-example-main/gnn_example.py', wdir='C:/Users/Administrator/Desktop/co-with-gnns-example-main')
Will use device: cuda, torch dtype: torch.float32
Generating d-regular graph with n=100, d=3, seed=1
Running GNN...
Epoch: 0, Loss: 44.14915466308594
Epoch: 1000, Loss: 16.639339447021484
Epoch: 2000, Loss: 4.808122634887695
Epoch: 3000, Loss: 1.1103489398956299
Epoch: 4000, Loss: -0.938180685043335
Epoch: 5000, Loss: -3.6288394927978516
Epoch: 6000, Loss: -11.529044151306152
Epoch: 7000, Loss: -21.938472747802734
Epoch: 8000, Loss: -31.172693252563477
Epoch: 9000, Loss: -36.286048889160156
Epoch: 10000, Loss: -39.039188385009766
Epoch: 11000, Loss: -40.35068893432617
Epoch: 12000, Loss: -40.703224182128906
Epoch: 13000, Loss: -40.85045623779297
Epoch: 14000, Loss: -40.92048645019531
Stopping early on epoch 14816 (patience: 100)
GNN training (n=100) took 61.955
GNN final continuous loss: -40.95294952392578
GNN best continuous loss: -40.95294952392578
Calculating violations...
Independence number found by GNN is 41 with 0 violations
Took 61.97s, model training took 61.956s
Running built-in MIS solver (n=100).
Calculating violations...
Independence number found by nx solver is 39 with 0 violations.
MIS solver took 0.001s

输出的解释如下：示例代码用d-regular方法生成了一个随机图，参数是n=100, d=3, seed=1，代表100节点，平均度3。共训练了14816轮，patience=100意味着最后100轮loss没有提升，达到耐心上限早停（提前停止）了，这一部分见./utils.py下的run_gnn_training()函数。最佳的loss值是-40.95294952392578，也就是MIS问题松弛的QUBO目标函数的最好解。GNN找到的独立集节点数是41个，违背最大独立集限制条件的节点数为0。使用networkx的MIS求解器求解得到的独立集节点数是39个，违背最大独立集限制条件的节点数为0。

从结果来看，GNN求解器求解得到的最大独立集结果，好于networkx的MIS求解器求解得到的最大独立集。

输出图片如下，根据color_map = ['orange' if (best_bitstring[node]==0) else 'lightblue' for node in nx_graph.nodes]这行代码可以得知，蓝色的节点是最大独立集节点，而橙色的是非最大独立集节点：

在1.3.2中，我们提到了该求解器能够解决区间调度问题，下面来仔细分析一下这个问题，并看看这个求解器的示例代码如何运用在自己的区间调度问题上。

A Unified Approach to Approximating Resource Allocation and…这篇文章的第10页ppt展示了一个具体的区间调度问题，并展示如何将其表示为最大独立集。我将该页的问题扒下来，尝试了一下GNN求解器的使用。

我们需要解决的问题是：如果只有一台机器，这台机器每一时刻只能做一个任务，且在正在执行的任务结束前不能去做其他任务。现在有多个任务，每个任务有固定的起止时间与持续区间，最多能够完成多少个任务？

任务分布情况的可视化如下：

左图是第10页ppt的区间图，横轴代表时间的变化，而纵轴代表9个任务，每个任务有固定的开始与结束区间，每个任务持续的时间区间用粗黑线画出。

如果每一时刻只能做一个任务，那么部分任务在持续的时间区间上存在重合与冲突，例如任务0与任务1、3、7存在冲突，任务0就不能与任务1、3、7一起被选中执行。在右图便使用一个冲突关系图来表明了任务之间的互相冲突。我们将每个任务视为一个节点，如果两个任务在时间上冲突，那么就用一条边将两个节点连接起来。因此可以看到右图上，节点0只与节点 1、3、7相连接，而与其他节点之间不存在边。

那么我们能够完成任务的最大数量，就是右图的最大独立集数量。右图的最大独立集所代表的任务之间，彼此不存在冲突关系，都可以同时做。并且根据最大独立集的定义，这样选择出的节点数目，或者说任务数，是在这一约束下最好的选择。可视化如下：

可以看到，右图的最大独立集用橙色标出，是0、4、6。相应的，任务0、4、6就是最终选择去做的任务，也就是该区间调度问题的解。因此最多能做的任务数是3个。

示例源码的GNN求解器正好是解决最大独立集问题的，这与区间调度问题抽象为图问题后是一致的。源码的使用非常简单，只需要将区间调度的冲突关系图保存，并在求解器中读取这张图，代替随机生成的图作为图神经网络的输入，然后改几个参数，即可求解这个冲突关系图的最大独立集。

首先根据区间调度问题的冲突关系生成并保存图：

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from networkx.algorithms.mis import maximal_independent_set as mis

aclist = np.arange(9)
activities = np.array([[1,3], [0,5], [10,13], [1,6], [4,9], [8,12], [10,11], [2,7], [8,12]])
times = np.array([0,2,4,6,7,8,12,14,14.5,16,20,22,25,30])

def conflict(act12):
    # conflict if max(act1.start, act2.start)
    return True if act12.max(axis=0)[0]<act12.min(axis=0)[1] else False

# 遍历检测冲突，有冲突则构建一条边
edgelist=[]
for i in range(aclist.shape[0]):
    for j in range(i+1,aclist.shape[0]):
        if conflict(activities[[i,j]]):
            edgelist.append((aclist[i], aclist[j]))

# 建冲突关系图 https://www.osgeo.cn/networkx/tutorial.html
G = nx.OrderedGraph() #参考源码，用该函数建图
G.add_nodes_from(aclist)
G.add_edges_from(edgelist)

print(f'nodes:{ 
          G.nodes}\nedges:{ 
          G.edges}\nadj:{ 
          G.adj}\ndegree:{ 
          G.degree}')
print(f'mis(maximal_independent_set) nodes:{ 
          mis(G)}') #[0, 6|2, 4], 贪心找的，不是最优解，要多跑几次
nx.draw(G, with_labels=True)

nx.write_gpickle(G,'IntervalGraph.gpickle') #保存图

需要注意的是：节点标签必须是[0,1,2,…,8]这样的从0开始的整数，因为源码中直接用节点标签做切片，不这样设置节点标签会报错。

同时这里也用networkx2.7自带的最大独立集方法求解了一下该图的最大独立集，但是基本都只能找到2个，只有少数的机会能找到全部3个。这是由于自带的方法是随机贪心搜索的，实质上只能给出一个还不错的独立集，而不能解决最大独立集问题。所以前面的示例源码中，这一方法只找到39个，而GNN求解器能找到41个。

接着回到./gnn_example.ipynb中，在代码块In [6]找到随机生成图的一行：

# Constructs a random d-regular or p-probabilistic graph
nx_graph = generate_graph(n=n, d=d, p=p, graph_type=graph_type, random_seed=seed_value)

把这行改为加载刚刚自己构建的冲突关系图，以代替随机生成的测试图，注意路径要改为自己的路径：

nx_graph = nx.read_gpickle('./interval graph/IntervalGraph.gpickle')

接下来找到In [5]中# Problem size (e.g. graph size)下定义问题规模的超参数n = 100，将其修改为n = 9，这是由于刚刚的图有9个节点，原来随机生成的图是100个。需要注意的是在这上面还有一个n = 100，那个n被这个覆盖掉了，因此没用了。再次直接运行./gnn_example.ipynb即可。

不过这次，GNN求解器寄了。它并没有像之前那样找到这张图的一个最大独立集，输出的结果如下：

Epoch: 31000, Loss: 0.09334098547697067
Stopping early on epoch 31647 (patience: 100)
GNN training (n=9) took 127.82
GNN final continuous loss: 0.08423598855733871
GNN best continuous loss: 0.0
Calculating violations...
Independence number found by GNN is 0.0 with 0 violations
Took 127.822s, model training took 127.82s
Running built-in MIS solver (n=9).
Calculating violations...
Independence number found by nx solver is 2 with 0 violations.
MIS solver took 0.0s

显然，GNN求解器跑了30000多个epoch，但是没能找到任何一个图上的最大独立集，反倒networkx自带mis求解器找到2个，这是怎么回事呢？

我首先猜测是因为问题规模太小，因为不论从论文实验部分还是示例源码来说，GNN求解器跑的图节点数都是100起步。因此我用泊松分布生成了一个100个任务的区间调度问题，如下：

np.random.seed(9527)
aclist = np.arange(100)
bias = np.random.poisson(lam=5,size=[100,1])+1
activities = 3*np.arange(100).reshape(-1,1)+np.column_stack((-1*bias,bias))+25
# 查看图的基本属性，如下：
# mis(maximal_independent_set) nodes:[65, 44, 87, 53, 79, 34, 73, 60, 90, 0, 39, 96, 69, 9, 48, 82, 19, 27, 5, 29, 24, 15, 84, 76]
# num of coflicts(edges):325
# average degree:6.5

生成的冲突图有100个节点，325条边，平均度为6.5。把这个图用同样的方法送进GNN求解器中，结果如下：