ICMLFeb, 2020

GLSearch: 基于学习搜索的最大公共子图检测

PDF
TL;DRGLSearch 采用基于图神经网络的深度 - Q 网络的学习搜索模型来解决图之间最大公共子图的计算问题，通过枝绑定算法选择最佳节点对以加速和适应搜索过程，提供监督帮助训练 DQN，并通过实验表明该模型可以显著提高大规模图对的计算效率，为其他基于图约束的组合问题提供了潜在的解决方案。
maximum common subgraphgraph neural networkdeep-q networkbranch and boundcombinatorial problems
发现论文，激发创造
  • SimGNN：一种快速图相似度计算的神经网络方法

    本文提出一种新颖的神经网络方法 SimGNN，该方法通过可学习的嵌入函数和注意力机制实现了对图形编辑距离等图形相似性计算的高效计算和良好性能的综合优化，并在三种真实图数据集上取得了比现有基线算法更小的误差率和更大的时间降低。

    Aug, 2018

  • 用新的价值函数进行混合学习解决最大公共子图问题

    本研究提出了一种新的基于深度强化学习的顶点选择方法与价值函数，应用于求解最大诱导公共子图问题的分支定界算法，并实验验证了新算法的效果明显优于目前最先进的算法 McSplit+LL 和 McSplit+RL，同时分析证明了新的选择方法和价值函数的有效性。

    Aug, 2022

  • 基于学习的分支定界算法求解最大公共子图问题

    本文提出了一种受强化学习启发式的分枝策略，旨在尽早到达树叶以大大减小搜索树的大小，对于解决典型的最大公共子图（MCS）问题的分枝限界算法具有显著的效果优势。

    May, 2019

  • 利用神经网络辅助的蒙特卡罗树搜索对图进行稀疏化

    图神经网络与蒙特卡罗树搜索相结合的方法对多种类型的图进行计算，超过了多个标准近似算法，并经常找到最优解。

    Nov, 2023

  • 一个模型，适用于任何 CSP: 图神经网络作为快速全局搜索启发式算法用于约束满足

    提出了一种通用的图神经网络架构，该架构可以作为任何约束满足问题的端到端搜索启发式进行训练。该方法基于一种新颖的 CSP 图形表示，可以以纯数据驱动的方式为任何 CSP 生成问题特定的启发式，对于从随机数据中学习启发式，该方法在已知的 CSP 上优于以前的 RL 方法，并且可以与传统搜索启发式竞争或更好地处理结构更为复杂的测试实例。

    Aug, 2022

  • 最大公共子图推断，增强图相似性计算的可解释性

    该研究提出了一种更易解释的基于最大公共子图推断的图相似性学习的端到端学习范式，并使用变压器编码器层和图卷积层堆叠一些基本组件，以捕获更全局的信息，并且通过可视化和统计结果验证了 INFMCS 的可解释性和对基于图的分类和回归任务的性能优于现有模型的能力。

    Aug, 2022

  • 通过深度强化学习在大规模图上学习启发式算法

    本文介绍了一种名为 GCOMB 的框架，利用概率贪心机制通过训练图卷积网络 (GCN) 预测一个节点的质量，以此解决图上的组合问题。实验表明，GCOMB 比学术界最先进的组合算法快 100 倍、质量略高。此外，GCOMB 在实际的 Influence Maximization（IM）组合问题上也展现了强大的性能。

    Mar, 2019

  • 图卷积网络与引导树搜索的组合优化

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018

  • 伪装目标检测的互相图学习

    设计了一种新型的互动图学习（MGL）模型，它可以将图像分解成具有不同任务相关特征的两个特征图，并通过递归推理它们之间的高阶关系进行信息交互，从而实现目标检测和分割，取得了优于现有技术水平的成果。

    Apr, 2021

  • 学习图神经网络中的图网络

    本篇论文提出了一种新的图形神经网络 GL-GNN，通过学习关系的图形和选择重要数据特征以解决未知图形、节点具有嘈杂特征和图形含有噪声连接等三个问题，并在多个数据集上与基线方法进行对比， 能够选择重要特征和图形边缘。

    Oct, 2022