Deep learning model dramatically improves subgraph matching accuracy by eliminating noise

A research team from Kumamoto University has developed a promising deep learning model that significantly enhances the accuracy of subgraph matching—a critical task in fields ranging from drug discovery to natural language processing.

The work is published in the journal IEEE Access.

Subgraph matching involves identifying specific patterns (or subgraphs) within large and complex networks. However, conventional Graph Neural Networks (GNNs) often struggle with accuracy when “extra” or irrelevant nodes in the data interfere with the matching process.

To address this, the Kumamoto University team, led by Professor Motoki Amagasaki and Assistant Professor Masato Kiyama from the Faculty of Science and Technology, created ENDNet (Extra-Node Decision Network)—an innovative AI model that can identify and neutralize the influence of these extra nodes.

ENDNet introduces three key mechanisms:

1. Extra-node detection using a denormalized matching matrix, which pinpoints irrelevant nodes and suppresses their influence by setting their feature values to zero.
2. One-way propagation, a mechanism that sharpens feature alignment between query and data graphs.
3. Shared-graph convolution, a new convolution method using sigmoid functions to refine feature extraction.

Tests across four open datasets showed ENDNet outperforms existing models, achieving up to 99.1% accuracy on the COX2 dataset, a significant jump from 91.6% with previous methods. Ablation studies confirmed that each component of ENDNet contributes to its high performance.

“ENDNet opens up exciting possibilities for applying subgraph matching to real-world data like biological networks, molecular structures, and social graphs,” says Assistant Professor Kiyama. “We also anticipate its extension to larger datasets in the future.”

The source code is openly available on GitHub, encouraging further development by the broader AI community.