基于图神经网络的图优化问题求解框架

背景及研究动机

在解决约束满足问题（CSPs）和组合优化问题（COPs）时，回溯法与分支启发式结合是一种常见的方法。尽管为特定问题设计的分支启发式理论上是高效的，但其复杂性和实施难度使实践应用受限。反之，通用的分支启发式尽管适用范围广，但通常表现出次优性能。本文作者提出了一个新的求解框架，通过在分支启发式中引入香农熵（Shannon Entropy），在通用性和特定性之间找到平衡。具体地，利用图神经网络（GNN）模型从概率方法中训练得出的损失函数学习这些概率分布，并将其应用于两个NP-hard问题：最小支配团问题（Minimum Dominating Clique Problem）和边团覆盖问题（Edge Clique Cover Problem）。

作者与发表情况

本文由Congsong Zhang、Yong Gao和James Nastos撰写，作者分别来自加拿大不列颠哥伦比亚大学和Okanagan College，文章发表在《IEEE Transactions on Neural Networks and Learning Systems》上，接收日期为2024年4月30日。

研究详细流程

1. 研究流程

a. 问题建模与概率分布学习：首先，作者使用图作为输入，并定义了上述两个NP-hard问题的对应模型。在这些图模型中，节点特征被映射至多维概率分布。这些概率分布是通过图神经网络训练所得的。

b. 香农熵的分支启发式：基于从GNN模型中学得的概率分布，文章使用香农熵作为启发式来进行分支选择；即，在当前部分赋值下，引导搜索路径向不确定性最小的区域。

c. 损失函数的设计：作者在损失函数中引入了概率方法，用以优化概率空间，使得图优化问题的解能够在概率最大的区域找到。同时，为了最小化期望解的大小，损失函数还被设计为结合香农熵与最小支援团的其他属性。

d. 实现与测试：GNN模型的实现基于PyTorch，并通过大量基于图模型的数据进行训练和测试。然后，将训练好的模型应用于实际数据集进行验证。

2. 实验与结果

a. 与现有方法的对比：文章通过与已有算法的比较，展示了本框架在减少分支数目方面的有效性能。例如，与Culberson et al. (2005) 的方法相比，本框架在解决最小支配团问题时生成的分支数明显减少。

b. 性能和运行时间：尽管在某些情况下使用本文框架运行时间较长，但分支数目的减少证明了该方法在实际应用中的潜在长期优势。此外，通过引入并行计算和泰勒展开（Taylor Expansion）近似求解香农熵函数，运行时间有望大幅改善。

c. 实际数据验证：在”GitHub Stargazers”数据集上的实验，进一步验证了本文框架在真实网络中的有效性。尽管训练数据来自随机图模型，该框架在实际数据上的表现依然优于传统算法。

结论与扩展

本文提出的基于图神经网络的框架成功在图优化问题的求解中展示了有效性，特别是在最小支配团和边团覆盖问题上。此外，文章指出，未来将进一步探索此方法在其他类型图优化问题中的应用，如SAT问题。这一方法的提出为结合GNN技术改进经典AI算法打开了新的方向。

研究亮点

• 创新点：利用香农熵结合图神经网络的概率分布，提出了一种新的分支选择启发式。
• 泛化能力：尽管训练在随机图模型上进行，但在真实数据集上同样表现出色。
• 结果改进：相较于传统方法，本框架在减少分支数目方面表现优异，为降低最差运行时间提供了新思路。