4.1.2 最大割问题
给定一个无向图，最大割问题的目标是将图的节点分成两个不相交的子集，使得两个子集之间边的权重最大。最大割问题的求解过程涉及到对每个节点做二进制决策，这是非连续的。这种非连续性在神经网络中往往难以直接建模。传统的图神经网络主要基于节点和其邻居的局部信息进行推理，可能无法有效捕获整个图的全局信息。
在最大割问题的求解过程中，许多端到端图学习方法利用图神经网络学习顶点和其邻居的特征关系，并基于学习到的特征关系给出节点分类预测。Barrett 等人[16] 提出了一种探索性图神经网络，该方法通过逐步扩大探索域改进解节点分类和最大割问题的求解质量。 Khalil 等人[17] 利用图神经网络学习最大割问题的重复结构，并基于训练得到的网络设计贪心策略逐步构建每个节点的分类决策。直接的端到端图学习方法受解空间复杂性影响，往往难以适应大规模最大割问题实例的求解。为了改进端到端图学习方法的泛化性能，Barrett 等人[18] 提出 ECORD 学习算法。ECORD 算法在图数据进入递归探索单元前，预先将其在单一神经元进行预处理，提高了求解效率和模型泛化性能。Ireland 等人[19] 提出了 LeNSE 算法，用于学习基于割集得到的子图特征。LeNSE 算法调用启发式算法求解子问题，最终基于局部解合成全局解，提高了模型求解的效率和泛化能力。
为了进一步提高模型求解的质量，研究最大割问题中的全局结构对节点分类的影响是一个重要内容。基于对最大割问题全局结构的刻画，Yao 等人[20] 引入了一个通用全局结构学习框架，该方法首先利
用图神经网络提取问题实例的特征表示，然后应用深度 Q 学习通过全局翻转或交换顶点标签逐步改进解的质量。Zhang 等人[21] 认为最大割问题中高度结构化的全局约束会阻碍解的优化。在图神经网络中引入 GFlowNets 可以高效的从非标准化概率密度中进行采样，进而削弱组合优化问题中全局约束造成的不利影响。Zhang 等人[21] 针对最大割等多个组合优化问题，基于条件 GFlowNets 在解空间中进行采样，同时基于长期信度分配问题技术对图神经网络进行训练，提高了模型对全局结构约束的理解能力，提高了最大割问题解的质量与泛化性能。
基于决策配置学习的最大割问题求解方法通过利用图学习方法获得算法分类决策的重要性特征，进而指导搜索策略对最大割问题进行求解。Li 等人[22] 将图深度学习技术与经典启发式算法相结合来求解最大割问题。通过训练图卷积神经网络对图中每个顶点是否属于最优解进行打分，并利用树搜索方法探索解空间提升解的质量。Karalias等人[23] 提出了一种通过图神经网络学习求解最大割问题的无监督框架。该框架通过优化神经网络实现概率分布的学习，并确定最大割问题的搜所空间映射。该分布可以以一定的概率生成满足问题约束条件的低成本整数解。