AEDNet: Adaptive Edge-Deleting Network For Subgraph Matching. (January 2023)

• Record Type: Journal Article
• Authors: Lan, Zixun; Ma, Ye; Yu, Limin; Yuan, Linglong; Ma, Fei
• Is Part Of: Pattern recognition. Volume 133(2023)
• Publication Date: 2023-01
• Subjects: Subgraph matching -- Graph neural network -- Neural matching; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.109033
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: An end-to-end approach for subgraph matching integrating two novel mechanisms is proposed. A novel sample-wise adaptive edge-deleting mechanism ensures that two matched nodes have close adjacent structures. A unidirectional cross-propagation mechanism ensures that the node features of the corresponding nodes are similar enough. Our evaluations on six open datasets show that the proposed AEDNet outperforms six comparison state-of-the-arts. The proposed AEDNet works on graphs with sizes varying from 20 to 2300. Once trained, the proposed method typically completes a subgraph matching task within a second, which is much faster than exact algorithms. The running time of exact methods is generally not on the same order of magnitude. Abstract: 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.