Feb, 2024

重新考虑图神经网络在分支策略中的容量

PDF
TL;DR研究表明图神经网络能够有效地表示和学习基于混合整数线性规划的解决策略，其中包括强分支评分。另外，该研究还证明第二阶基因网络结构能够以高准确率和高概率近似强分支评分。
graph neural networksmixed-integer linear programsheuristicsbranchingbranch-and-bound algorithm
发现论文，激发创造
  • 学习分支的混合模型

    本文提出了一种基于 GNN 和 MLP 的混合模型，可在没有高端 GPU 的情况下有效地优化 Mixed Integer Linear Programming 问题求解器的性能。

    Jun, 2020

  • 图形算法的神经执行

    通过在算法空间中训练 Graph Neural Networks 来解决基于图结构的问题，使用基于最大化的信息传递神经网络来实现离散决策，同时实现了任务迁移并提升学习效果。

    Oct, 2019

  • 神经网络验证的神经网络分支

    通过训练图神经网络来设计一个有效的分支策略，能够在形式化验证神经网络的过程中减少验证时间并获得更好的验证结果。

    Dec, 2019

  • 用于二进制规划的图神经网络

    该研究探讨了图神经网络（GNNs）和二进制编程（BP）问题之间的联系，为 GNNs 在解决这些计算难题上提出了设计。通过分析 BP 问题的灵敏度，我们将 BP 问题的解决方案框架化为异质节点分类任务。随后，我们提出了 Binary-Programming GNN（BPGNN），一种将图表示学习技术与 BP 感知特征相结合的架构，以有效地近似 BP 解决方案。此外，我们引入了一种自我监督的数据生成机制，以便在处理大规模 BP 问题时实现高效和可操作的训练数据获取。对不同 BP 问题规模的 BPGNN 进行实验评估显示其性能优于穷举搜索和启发式方法。最后，我们讨论了 GNNs 在 BP 问题这个尚未充分探索的领域中的挑战。

    Apr, 2024

  • 使用分级支持图进行下一级的消息传递

    通过引入分层支持图 (HSG)，该研究在 MPNN 中提出了一种解决局限性的策略，以促进图中的全局信息交流，经过理论分析和实证研究发现，HSG 能够在多个数据集上达到最先进的性能。

    Jun, 2024

  • 从图神经网络中学习分支启发式算法

    本研究提出了一种新的基于图神经网络的分支启发式方法，用于求解组合优化问题中的最小支配团问题，实验结果表明，该方法相较于最小剩余量策略在分支数上表现更优，为使用图神经网络改进传统的 AI 回溯算法提供了新思路。

    Nov, 2022

  • 两层图神经网络

    我们提出了一种被称为 Two-level GNN 的新型 GNN 框架，通过将子图级别信息与节点级别信息合并来克服现有 GNN 的局部置换不变性问题，并提出了一个基于动态规划算法的子图计数方法，实验证明 TL-GNN 优于现有 GNN，并实现了最先进的性能。

    Jan, 2022

  • 灵活表示多模块图神经网络以实现更好的泛化

    本文研究了图神经网络的可扩展性和推广性，并提出了灵活的 GNNs 框架，通过多种节点更新函数和内部循环优化，使网络能够灵活适应新图并在多项推理任务中提高泛化能力。

    Sep, 2022

  • 图神经网络是内在良好的泛化器：通过建立 GNN 和 MLP 之间的联系进行深入探究

    本文通过引入中间模型 PMLP，揭示了 GNN 的性能提升主要源于其本质上的泛化能力，而非原理层面上的增强表现力。同时，本文发现 PMLP 表现与 GNN 相当，但训练效率更高。该发现为解析 GNN 相关问题提供了新的视角。

    Dec, 2022

  • 图神经网络与图增强型多层感知机比较

    本文比较了多层图神经网络和一种被称为图增强多层感知器的简化替代品之间的表现，其中后者首先通过图上的某些多跳算子增强节点特征，然后以节点方式应用 MLP；并证明了 GA-MLP 具备适当算子的情况下，能像 Weifeiler-Lehman（WL）测试一样，理论和数值上能够区分几乎所有非同构图，但是 GA-MLP 与 GNN 之间在表达能力方面的差距随着深度呈指数增长，并且 GA-MLP 不能计算属性步行的数量，表明 GA-MLP 受其操作符族的选择限制比拥有更高学习灵活性的 GNN 更为受限，这在社区检测实验中也得到了证明。

    Oct, 2020