GNN小编专栏 | GNN与求解组合优化问题

【ICASSP 2021】Distributed Scheduling Using Graph Neural Networks

• 链接：https://arxiv.org/abs/2011.09430
• 作者：Zhongyuan Zhao; Gunjan Verma; Chirag Rao; Ananthram Swami; Santiago Segarra (来自Rice University & US Army’s CCDC Army Research Laboratory)

导读：以分布式方式有效地调度传输是无线网络设计中的一个基本问题。主要的挑战来自于最佳链路调度涉及到解决最大加权独立集（maximum weighted independent set, MWIS）问题，这是一个NP-hard问题。对于实际的链路调度方案，分布式的greedy方法通常被用来近似解决MWIS问题。然而，这些贪婪的方案大多忽略了无线网络的重要拓扑信息。为了克服这一缺陷，作者提出了一种基于图卷积网络（GCN）的分布式MWIS求解器。一个可训练的GCN模块学习拓扑感知的节点嵌入，在调用贪婪求解器之前与网络权重相结合。实验结果表明，在有数十条链路的中小型无线网络中，即使是基于GCN的浅层MWIS调度器也可以利用图的拓扑信息，将分布式贪婪求解器的次优差距减少一半。此外，该方法在不同的图中具有良好的泛化性，且复杂度增加较小。

【ECCV 2020】Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers

• 链接：https://arxiv.org/pdf/2003.11657.pdf
• 作者：Michal Rolınek，Paul Swoboda，Dominik Zietlow，Anselm Paulus， Vıt Musil， Georg Martius分别为德国图宾根 马克斯 · 普朗克智能系统研究所，德国萨尔布鲁肯，  马克斯·普朗克计算机科学研究所 和 意大利佛罗伦萨大学 的学者

导读：在本文中，作者提出了一种包含未修改的组合求解器的端到端可训练的深度图匹配体架构。基于高度优化的组合解算器及改进架构设计，作者提出了一种用于键点对应的深度图匹配基准测试的技术。此外，作者还强调了将解算器整合到深度学习架构的概念优势，例如，使用强大的多图匹配解算器进行后处理的可能性，或者对训练设定中的变化无关。最后，作者提出了两个新的具有挑战性的实验方案。

【NeurIPS 2019】Exact Combinatorial Optimization with Graph Convolutional Neural Networks

• 链接：https://arxiv.org/pdf/1906.01629.pdf
• 作者：Maxime Gasse，Didier Chételat，Nicola Ferroni，Laurent Charlin

导读：组合优化问题通常可以由分支定界方法进行求解。在本文中，作者提出了一种GCN模型来学习分支定界变量选择策略，利用二部图表示混合整数线性规划的变量与约束。通过模仿学习学习强分支专家规则来训练模型，并在一系列难题上证明该方法的有效性。此外，作者首次改进了最先进的大型问题求解器中专家设计的分支规则。

内容中包含的图片若涉及版权问题，请及时与我们联系删除