Efficient Partition-Based Approaches for Diversified Top- k Subgraph Matching
Proceedings of the VLDB Endowment · 01.12.2025 · 19 (4) · 698-712
DOI: 10.14778/3785297.3785310 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 18.03.2026. Verfasst von Liuyi Chen und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 107 Literaturangaben.
Abstract (Originalsprache)
Subgraph matching is a core task in graph analytics, widely used in domains such as biology, finance, and social networks. Existing top- k diversified methods typically focus on maximizing vertex coverage, but often return results in the same region, limiting topological diversity. We propose the Distance-Diversified Top- k Subgraph Matching (DT k SM) problem, which selects k isomorphic matches with maximal pairwise topological distances to better capture global graph structure. To address its computational challenges, we introduce the Partition-based Distance Diversity (PDD) framework, which partitions the graph and retrieves diverse matches from distant regions. To enhance efficiency, we develop two optimizations: embedding-driven partition filtering and densest-based partition selection over a Partition Adjacency Graph. Experiments on 12 real world datasets show our approach achieves up to four orders of magnitude speedup over baselines, with 95% of results reaching 80% of optimal distance diversity and 100% coverage diversity.
Zitieren
APA
Chen, L., Hu, Y., Yang, Z., Zhou, X., Zhang, W., & Li, K. (2025). Efficient Partition-Based Approaches for Diversified Top- k Subgraph Matching. Proceedings of the VLDB Endowment, 19(4), 698-712. https://doi.org/10.14778/3785297.3785310
Vancouver
Chen L, Hu Y, Yang Z, Zhou X, Zhang W, Li K. Efficient Partition-Based Approaches for Diversified Top- k Subgraph Matching. Proceedings of the VLDB Endowment. 2025;19(4):698-712. doi:10.14778/3785297.3785310
BibTeX
@article{Chen2025,
author = {Chen, Liuyi and Hu, Yuchen and Yang, Zhengyi and Zhou, Xu and Zhang, Wenjie and Li, Kenli},
title = {Efficient Partition-Based Approaches for Diversified Top- k Subgraph Matching},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {19},
number = {4},
pages = {698--712},
doi = {10.14778/3785297.3785310}
}
EUVIMED