求解组合优化问题的具有递归特征的无监督图神经网络
文章目录
- ABSTRACT
- 1 Introduction
- 2 Related Work
- 3 QRF-GNN方法
- 4 数值实验
- 4.1 MAX-CUT
- 4.2 COLORING
- 5 conclusion
ABSTRACT
- 介绍了一种名为QRF-GNN的新型算法，有效解决具有二次无约束二进制优化（QUBO）表述的组合问题。依赖无监督学习，从最小化的QUBO放松导出的损失函数。
- 该架构的关键组成部分是中间GNN预测的递归使用、并行卷积层以及将人工节点特征作为输入的组合。
1 Introduction
二次无约束二进制优化（QUBO）问题是最小化一个二次伪布尔多项式F(x)的问题：
2 Related Work
在Tönshoff等人的研究中，作者提出了RUN-CSP作为最大约束满足问题的一种循环无监督神经网络。该架构包括一组线性函数，为图中的所有变量节点和所有约束的边提供消息传递。在消息传递步骤之后，当前状态以及内部长期状态通过LSTM单元进行更新。基于输出，网络产生变量在搜索域中取特定值的概率。
Amizadeh等人提出了一种无监督GNN来解决SAT和CircuitSAT问题[Amizadeh et al., 2018]。他们使用问题的有向无环图表示，并训练模型以最小化人工损失函数，其最小值对应于具有更高满意度的解决方案。
Karalias和Loukas以稍微不同的方式应用了GNN[Karalias & Loukas, 2020]。它获得了对应于候选解的节点分布。该模型通过最小化概率惩罚函数进行训练，并使用顺序解码来获得离散解，降低其不可行的概率。
在Wang等人的研究中，作者引入了GNN-1N，将负面消息传递技术适应到无监督GNN中，用于解决图着色问题[Wang et al., 2023]。使用特定问题的QUBO公式的连续放松作为损失函数的建议是由Schuetz等人在他们的物理启发式GNN（PI-GNN）中提出的[Schuetz et al., 2022a]。PI-GNN的基础架构包括一个可训练的嵌入层，用于生成节点的输入特征，以及几个图卷积层（GCN或GraphSAGE）。在Schuetz等人的研究中，这个模型被应用于解决图着色问题。
3 QRF-GNN方法
节点之间交换消息使用的是消息传递协议，分为两个部分：消息累积和消息聚合。
消息累积：
节点 i 的特征向量由一个函数 ψ