Timezone: »

 
Poster
GLSearch: Maximum Common Subgraph Detection via Learning to Search
Yunsheng Bai · Derek Xu · Yizhou Sun · Wei Wang

Tue Jul 20 09:00 AM -- 11:00 AM (PDT) @ Virtual
in Poster Session 1 »

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. We propose a novel GNN-based Deep Q-Network (DQN) to select the node pair, making the search process much faster. Experiments on synthetic and real-world graph pairs demonstrate that our model learns a search strategy that is able to detect significantly larger common subgraphs than existing MCS solvers given the same computation budget. GLSearch can be potentially extended to solve many other combinatorial problems with constraints on graphs.

Keywords: Networks and Relational Learning · Algorithms · Probabilistic Methods · Causal Inference
[ Slides] 

Author Information

Yunsheng Bai (UCLA)
Derek Xu (University of California, Los Angeles)
Yizhou Sun (UCLA)
Wei Wang (UCLA)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors