将图神经网络作为平行图着色的排序启发式
使用深度强化学习,本研究使用新的深度神经网络结构FastColorNet,能在有效计算时间内更好地对大型图形进行着色,从而将计算转化为改进启发式方法,获得了新的图形着色启发式方法。
Feb, 2019
本文介绍了如何使用简单的 GNN 架构来解决图着色的基本组合问题,并且展示了该模型在独立于训练数据的图数据上的泛化能力以及优于其他基线模型的表现。同时,我们还展示了如何将节点嵌入在多维空间中进行聚类,从而获得构造性解决方案。我们的结果有助于缩小人们对 GNN 算法学习的差距,并提供了符号推理与深度学习系统集成的可靠方法。
Mar, 2019
该论文从理论角度研究了如何利用图神经网络解决组合问题的近似算法,并提出了一种新的GNN类别,揭示了GNN的相对近似比,并证明了在节点特征中添加染色可以提高学习算法的近似比。
May, 2019
通过在算法空间中训练Graph Neural Networks来解决基于图结构的问题,使用基于最大化的信息传递神经网络来实现离散决策,同时实现了任务迁移并提升学习效果。
Oct, 2019
利用图神经网络解决图着色问题,将图着色视为多类节点分类问题,利用基于统计物理学的Potts模型的无监督训练策略。我们展示了该方法在实际应用中的性能,并提供了数值基准结果。
Feb, 2022
本研究分析了现有图嵌入神经网络(GNN)在图着色问题中的表现差异主要是由于其无法应对节点异质性以及其局部性;通过研究聚集-合并 GNN(AC-GNN)的性能以及其基于局部搜索的特性,我们得出了一系列在实践中使 GNN 在图着色问题中更具有等变性和强大性的规则,并提出了一个简单的 AC-GNN 变体以验证我们的理论,并实现了比现有启发式算法更高质量和更快速运行的结果。
Aug, 2022
提出了一种通用的图神经网络架构,该架构可以作为任何约束满足问题的端到端搜索启发式进行训练。该方法基于一种新颖的 CSP 图形表示,可以以纯数据驱动的方式为任何 CSP 生成问题特定的启发式,对于从随机数据中学习启发式,该方法在已知的 CSP 上优于以前的 RL 方法,并且可以与传统搜索启发式竞争或更好地处理结构更为复杂的测试实例。
Aug, 2022
通过对图神经网络的公平性技术进行分类和研究,本文介绍了改善图神经网络公平性的先前工作,包括预处理步骤、训练过程和后处理阶段,同时提出了公平性评价指标的直观分类,并对用于基准测试的图数据集进行了总结,还针对未解决的关键问题和挑战进行了讨论。
Jul, 2023
最近几年来,有大量的研究专注于扩展图神经网络(GNNs)的表达能力,超越Weisfeiler-Lehman (1-WL)框架。在这项研究中,我们从图搜索的角度探讨了GNNs的表达能力,提出了一种新的顶点着色方案,并证明经典的搜索算法可以高效地计算超越1-WL的图表示。我们展示了这种着色方案从图搜索中继承的有用特性,可以帮助解决图的双连通性问题。此外,我们还展示了在某些条件下,GNNs的表达能力随着搜索邻域的半径逐层递增。为了进一步研究所提出的方案,我们基于广度优先搜索和深度优先搜索开发了一种新类型的GNN,突出了它们在1-WL之上所能捕捉到的图属性。
Mar, 2024
本研究解决了图着色问题,该问题是一个NP困难的优化问题,特别是在大规模图中。我们提出了一种新颖的算法,利用图神经网络及物理启发的方法来提高训练效率和算法性能。研究结果表明,该方法在传统方法难以解决的连通性区域中依然有效,具有广泛的应用潜力。
Aug, 2024