HOME

New AI Model Dramatically Improves Subgraph Matching Accuracy by Eliminating Noise

Kumamoto University researchers develop ENDNet, a powerful deep learning model that detects and neutralizes "extra nodes" to boost performance in pattern recognition tasks.

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.

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


Image Title: Comparison of Conventional and Proposed ENDNet Methods
Image Caption: Node colors represent different characteristics, with white showing extraneous (unnecessary) nodes. In the conventional method, these extraneous nodes affect necessary ones, leading to incorrect matches. The proposed method solves this by identifying and excluding extraneous nodes.


Reference
Authors MASAKI SHIROTANI, MOTOKI AMAGASAKI, MASATO KIYAMA
Title of original paper ENDNet: Extra-Node Decision Network for Subgraph Matching
Journal IEEE Access
DOI 10.1109/ACCESS.2025.3543206

Archive