AEDNet: Adaptive Edge-Deleting Network For Subgraph Matching

作者:

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.

摘要

•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.

论文关键词:Subgraph matching,Graph neural network,Neural matching

论文评审过程:Received 14 April 2022, Revised 1 September 2022, Accepted 5 September 2022, Available online 9 September 2022, Version of Record 15 September 2022.

论文官网地址:https://doi.org/10.1016/j.patcog.2022.109033