2021-07-01-bai21e.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
GLSearch: Maximum Common Subgraph Detection via Learning to Search	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	bai21e	0	GLSearch: Maximum Common Subgraph Detection via Learning to Search	588	598	588-598	588	false	Bai, Yunsheng and Xu, Derek and Sun, Yizhou and Wang, Wei	given family Yunsheng Bai given family Derek Xu given family Yizhou Sun given family Wei Wang	2021-07-01		Proceedings of the 38th International Conference on Machine Learning	139	inproceedings	date-parts 2021 7 1	http://proceedings.mlr.press/v139/bai21e/bai21e.pdf	label link Supplementary PDF http://proceedings.mlr.press/v139/bai21e/bai21e-supp.pdf