本文提出了一种新的最大权独立集问题分支和缩减策略，结合核心化与局部搜索能够比局部搜索单独得出更高质量的解，通过实验表明，在实践中这种方法比现有的算法更加有效，可以处理高达数百万个顶点和边的实际问题。

Oct, 2018

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

Aug, 2022

探讨在图中找到最大独立集的最大权重问题中使用信息传递算法的方法，并介绍了经典的 max-product 信念传播算法的性能，以及最大化固定点的自然初始化方法对算法收敛的影响。同时发现，在概率分布的 MAP 估计问题中，可以将任何问题都简化为 MWIS 问题，从而为 MAP 估计提供新的洞见和算法。

Jul, 2008

本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。

Oct, 2023

本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

Jul, 2019

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

Feb, 2012

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

Jun, 2022

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

Feb, 2023

该论文提出了一种基于图卷积网络的分布式最大权独立集求解器，通过学习拓扑感知节点嵌入和网络权重相结合，并调用贪心算法，即使在小型至中型无线网络中，浅层的基于 GCN 的 MWIS 调度器也可以利用图的拓扑信息将分布式贪心求解器的次优误差减半，在保持图形一般性的同时，增加的计算复杂性很小。

Nov, 2020

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

Jun, 2020