Research on Approximate Subgraph Matching Algorithm Based on Dense Substructure and Double Indexing
Taiming Lei, Zongkang Zou · 2025
Driven by rapid advancements in the Internet, social networks, graph databases, and bioinformatics, vast amounts of graph data have emerged as a crucial medium for representing complex inter-entity relationships. However, traditional exact graph matching methods typically encounter significant challenges including high computational costs and suboptimal matching performance when addressing practical issues such as noise, missing data, and local structural deformations. To overcome these challenges, this study introduces an approximate subgraph matching algorithm that leverages dense substructure partitioning coupled with dual-index construction. By partitioning large graphs locally and efficiently pre-selecting candidate nodes, the proposed algorithm markedly reduces computational complexity while preserving high matching accuracy. Experimental results on the Protein, DBLP, and YAGO datasets show that the proposed method performs well in terms of accuracy and computational efficiency while exhibiting robust performance in noisy environments.