  Subgraph matching is to find all subgraphs in a data graph that are
isomorphic to an existing query graph. Subgraph matching is an NP-hard problem,
yet has found its applications in many areas. Many learning-based methods have
been proposed for graph matching, whereas few have been designed for subgraph
matching. The subgraph matching problem is generally more challenging, mainly
due to the different sizes between the two graphs, resulting in considerable
large space of solutions. Also the extra edges existing in the data graph
connecting to the matched nodes may lead to two matched nodes of two graphs
having different adjacency structures and often being identified as distinct
objects. Due to the extra edges, the existing learning based methods often fail
to generate sufficiently similar node-level embeddings for matched nodes. This
study proposes a novel Adaptive Edge-Deleting Network (AEDNet) for subgraph
matching. The proposed method is trained in an end-to-end fashion. In AEDNet, a
novel sample-wise adaptive edge-deleting mechanism removes extra edges to
ensure consistency of adjacency structure of matched nodes, while a
unidirectional cross-propagation mechanism ensures consistency of features of
matched nodes. We applied the proposed method on six datasets with graph sizes
varying from 20 to 2300. Our evaluations on six open datasets demonstrate that
the proposed AEDNet outperforms six state-of-the-arts and is much faster than
the exact methods on large graphs.
