Oct, 2023

最大独立集：动态规划自学习

PDF
TL;DR本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。
graph neural networkmaximum independent setdynamic programmingrecursive algorithmself-training process
发现论文，激发创造
  • 现代图神经网络在解决诸如最大独立集等组合优化问题方面表现不如传统的贪心算法

    该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。

    Jun, 2022

  • 最大独立集问题的自适应重复交集约简局部搜索

    本文研究了应用广泛的 NP-hard 问题之一，最大独立集问题（ M IS），提出了局部搜索框架 ARIR 及其三种算法，采用三种不同的减少策略，在五组基准测试中显示出明显的优越性。

    Aug, 2022

  • 最大独立集的精确算法

    本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。

    Dec, 2013

  • 现代图神经网络在解决像最大独立集这样的组合优化问题时表现不及经典的贪心算法

    在回复评论者的回复中，我们指出其关注的最大独立集（MIS）在稀疏图中和贪心算法优秀表现无关，我们还强调了原始框架中广泛的算法开发，并通过提供额外的数值结果证明了我们原来的结果的可观改进，进而驳斥了评论中的性能声明。我们同时通过实验证明了我们提出的随机 d - 正则图不提供用于基准测试的通用实例集，贪心算法不提供通用算法基线。最后，我们指出图神经网络的内在（并行）解剖与贪心算法的（顺序）本质非常不同，并强调图神经网络已经展示出了比现有启发式方法（如并行退火）更高的可扩展性潜力。这份工作的概念创新值得探讨并有潜力进一步拓展。

    Feb, 2023

  • 最大独立集问题的无数据二次神经网络

    通过引入一种新颖的无数据二次神经网络，该论文解决了最大独立集问题，并展示了与现有学习方法相比具有竞争力或更好性能的优势。

    Jun, 2024

  • 贪心顺序极大独立集和匹配在平均情况下是并行的

    本文通过研究贪婪顺序算法中迭代间的依赖结构，证明了随机排序后的贪婪最大独立集算法以及贪婪最大匹配算法的依赖深度为对数级别，提出了基于该结论设计的简单线性工作并行算法，该算法能在更高的并行度与更小的工作开销之间平衡，并且保证结果与顺序贪婪算法相同。

    Feb, 2012

  • 大规模最大独立集问题的元启发式算法

    针对实际的车辆路径问题，研究了最大权独立集问题，通过开发一个新的本地搜索算法，该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构，引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。

    Mar, 2022

  • 图神经网络中的最大独立集合用于汇聚

    在图像分类中，卷积神经网络通过卷积和池化实现了重大进展；然而，对于图中的池化方法存在着一些问题，如图的断开或过连接、低减少率和删除大部分图等。本文基于最大独立集的概念提出了三种池化方法，并通过实验结果确认最大独立集约束对图池化的相关性。

    Jul, 2023

  • 学习最大独立集的推迟策略

    本文提出了一种称为学习何时推迟（LwD）的新型深度强化学习算法，将其应用于最大独立集（MIS）问题，展示出在处理大规模图形时比当前先进的 DRL 方案更具有优势。

    Jun, 2020

  • 深图信息最大化

    Deep Graph Infomax 提出了用于无监督学习图结构数据中节点表示的一般方法，可用于节点分类任务，并且相比大多数先前的方法，不依赖于随机游走目标。

    Sep, 2018