GLSearch: Maximum Common Subgraph Detection via Learning to Search
GLSearch: Maximum Common Subgraph Detection via Learning to Search
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Yunsheng Bai;Derek Xu;Yizhou Sun;Wei Wang
中科院分区：
文献类型：
--
作者：
Yunsheng Bai;Derek Xu;Yizhou Sun;Wei Wang
在药物合成、恶意软件检测、云计算等应用中，检测两个输入图之间的最大公共子图(MCS)是基本的。然而，MCS的计算是NP难的，现有的MCS求解器依赖于启发式搜索算法，在有限的计算预算下，这种算法不能为大型图对找到好的解。提出了一种基于图神经网络(GNN)的学习搜索模型GLSearch。我们的模型建立在分支定界算法的基础上，该算法一次从两个输入图中选择一对节点进行扩展。我们提出了一种新的基于GNN的深度Q网络(DQN)来选择节点对，而不是使用启发式算法，使得搜索过程更快，更具适应性。为了进一步加强DQN的培训，我们利用搜索过程在培训前阶段提供监督，并在模仿学习阶段指导我们的代理。在合成的和真实世界的大型图对上的实验表明，我们的模型学习了一种搜索策略，该策略能够在相同的计算预算下发现明显更大的公共子图。我们的GLSearch可以潜在地扩展到解决许多其他带有图上约束的组合问题。
Detecting the Maximum Common Subgraph (MCS) between two input graphs is fundamental for applications in drug synthesis, malware detection, cloud computing, etc. However, MCS computation is NP-hard, and state-of-the-art MCS solvers rely on heuristic search algorithms which in practice cannot find good solution for large graph pairs given a limited computation budget. We propose GLSearch, a Graph Neural Network (GNN) based learning to search model. Our model is built upon the branch and bound algorithm, which selects one pair of nodes from the two input graphs to expand at a time. Instead of using heuristics, we propose a novel GNN-based Deep Q-Network (DQN) to select the node pair, allowing the search process faster and more adaptive. To further enhance the training of DQN, we leverage the search process to provide supervision in a pre-training stage and guide our agent during an imitation learning stage. Experiments on synthetic and real-world large graph pairs demonstrate that our model learns a search strategy that is able to detect significantly larger common subgraphs given the same computation budget. Our GLSearch can be potentially extended to solve many other combinatorial problems with constraints on graphs.