文章目录
- 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 的特征向量由一个函数 ψ