Subgraph matching is a fundamental problem in various fields that use graph
structured data. Subgraph matching algorithms enumerate all isomorphic
embeddings of a query graph q in a data graph G. An important branch of
matching algorithms exploit the backtracking search approach which recursively
extends intermediate results following a matching order of query vertices. It
has been shown that the matching order plays a critical role in time efficiency
of these backtracking based subgraph matching algorithms. In recent years, many
advanced techniques for query vertex ordering (i.e., matching order generation)
have been proposed to reduce the unpromising intermediate results according to
the preset heuristic rules. In this paper, for the first time we apply the
Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to
generate the high-quality matching order for subgraph matching algorithms.
Instead of using the fixed heuristics to generate the matching order, our model
could capture and make full use of the graph information, and thus determine
the query vertex order with the adaptive learning-based rule that could
significantly reduces the number of redundant enumerations. With the help of
the reinforcement learning framework, our model is able to consider the
long-term benefits rather than only consider the local information at current
ordering step.Extensive experiments on six real-life data graphs demonstrate
that our proposed matching order generation technique could reduce up to two
orders of magnitude of query processing time compared to the state-of-the-art
algorithms.

本研究首次应用强化学习和图神经网络技术生成高质量的子图匹配算法匹配顺序，相比现有算法，该算法可减少两个数量级的查询处理时间。