EUVIMEDEUVIMED entdecken
Crossref

Accelerating Top-K Subgraph Matching With Topology-Aware Pruning and Parallel Processing

Linglin Yang, Yuqi Zhou, Yue Pang, Lei Zou

IEEE Transactions on Knowledge and Data Engineering · 2026-08 · 38 (8) · 4836-4850

DOI: 10.1109/tkde.2026.3702627 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Knowledge and Data Engineering, 2026-08. Verfasst von Linglin Yang und 3 weiteren Autor:innen. Die Arbeit nennt 36 Literaturangaben. Gefördert von: New Generation Artificial Intelligence-National Science and Technology Major Project, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a query graph, top-k subgraph matching finds up to $k$ k matches in a data graph with the highest scores according to a user-defined scoring function. It has wide applications across many fields, including knowledge graphs and social networks. Due to the enormous search space, existing methods are not efficient enough on large graphs. In this paper, we propose PTAB , an efficient serial algorithm for top-k subgraph matching. It traverses an efficiently pruned search space by topology-aware subspace score upper bounds computed from a novel hop index, which stores the range of node properties in a constrained multi-hop neighborhood of each node. Additionally, PTAB integrates a cost-aware root selection strategy, which chooses query nodes leading to a search process that utilizes the pruning power of the hop index as much as possible. Furthermore, we use a novel edge-cut strategy to handle general query graphs with cycles. We also extend PTAB to a parallel version, PTABP , which further improves performance via multi-threading and enhanced pruning techniques. Experimental results on real and synthetic datasets demonstrate that our methods outperform existing methods.

Förderung

  • New Generation Artificial Intelligence-National Science and Technology Major Project
  • National Natural Science Foundation of China

Zitieren

APA

Yang, L., Zhou, Y., Pang, Y., & Zou, L. (2026). Accelerating Top-K Subgraph Matching With Topology-Aware Pruning and Parallel Processing. IEEE Transactions on Knowledge and Data Engineering, 38(8), 4836-4850. https://doi.org/10.1109/tkde.2026.3702627

Vancouver

Yang L, Zhou Y, Pang Y, Zou L. Accelerating Top-K Subgraph Matching With Topology-Aware Pruning and Parallel Processing. IEEE Transactions on Knowledge and Data Engineering. 2026;38(8):4836-4850. doi:10.1109/tkde.2026.3702627

BibTeX
@article{Yang2026,
  author = {Yang, Linglin and Zhou, Yuqi and Pang, Yue and Zou, Lei},
  title = {Accelerating Top-K Subgraph Matching With Topology-Aware Pruning and Parallel Processing},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  year = {2026},
  volume = {38},
  number = {8},
  pages = {4836--4850},
  doi = {10.1109/tkde.2026.3702627}
}
Kostenlos starten →