本文系统地介绍了图割方法，着重介绍了归一化图割方法及其在加权无向图和有向图聚类中的应用，并提出了解决带符号图的问题的方法。此外，本文还表明了比率割方法是归一化割方法的特例。

Jan, 2016

本文介绍了如何使用简单的 GNN 架构来解决图着色的基本组合问题，并且展示了该模型在独立于训练数据的图数据上的泛化能力以及优于其他基线模型的表现。同时，我们还展示了如何将节点嵌入在多维空间中进行聚类，从而获得构造性解决方案。我们的结果有助于缩小人们对 GNN 算法学习的差距，并提供了符号推理与深度学习系统集成的可靠方法。

Mar, 2019

本文提出了基于面积凸性的混合装箱问题LP的宽度相关算法并进一步将其应用于最密子图问题中，实现了比宽度独立算法更高的精度。

Sep, 2019

该研究提出了一种通用框架，将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法，并显示了在树宽度为$k$的所有图上验证图论猜想的算法，时间为$ k^{O(1)}$ 双指数级。

May, 2022

本文研究了二元约束满足问题 (BINARY-CSPs) 的多种推广的复杂性及参数化复杂性，探讨了基于半环的代数方法，提出了组件双宽属性的 generalization。研究表明，在受限制的条件下，该方法在多种问题中取得了优秀算法复杂度上界。

Jul, 2022

我们提出了一种名为FNM的二阶段谱算法，通过在目标函数中添加公平性准则来获取更公平的谱节点嵌入，然后设计一个舍入方案从该公平嵌入中生成k个簇，从而在维持公平性的同时达到良好的分区质量。通过对九个基准数据集进行全面实验，我们证明了FNM相对于三种基准方法的卓越性能。

Jul, 2023

提出了一种新的基于图分割技术的上界方法（PUB），用于最大s-束问题（MBP）的精确算法中，同时使用初始下界和上界对图进行预处理和分支剪枝。通过与其他BnB MBP算法的实验证明了该算法的显著进展。

Feb, 2024

提出了基于SAT编码的偏序基于整数线性规划模型，应用于图着色问题和带宽着色问题，实验和理论分析结果表明，这种SAT编码在稀疏图上非常有效，超过了现有方法的性能。

Mar, 2024

本研究解决了图着色问题，该问题是一个NP困难的优化问题，特别是在大规模图中。我们提出了一种新颖的算法，利用图神经网络及物理启发的方法来提高训练效率和算法性能。研究结果表明，该方法在传统方法难以解决的连通性区域中依然有效，具有广泛的应用潜力。

Aug, 2024

本文解决了图着色问题，这是一种在无向图中为顶点分配不同颜色的NP难题。提出了一种基于图神经网络的排序启发式，显著提升了着色质量和执行效率。研究表明，在平行处理能力上，GNN模型在质量和性能上超越了现有的贪心排序启发式方法。

Aug, 2024