Efficient Partition-Based Approaches for Diversified Top-k Subgraph Matching

RAIDS Lab Authors

Zhengyi Yang

(corresponding author)

Director

Details

Research Area

Tags

Resources

Abstract

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 (DTkSM) 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.

Author Affiliations

@article{chen2026efficient,
  title = {Efficient Partition-Based Approaches for Diversified Top-k Subgraph Matching},
  author = {Chen, Liuyi and Hu, Yuchen and Yang, Zhengyi and Zhou, Xu and Zhang, Wenjie and Li, Kenli},
  volume = {19},
  issn = {2150-8097},
  url = {http://dx.doi.org/10.14778/3785297.3785310},
  doi = {10.14778/3785297.3785310},
  number = {4},
  journal = {Proceedings of the VLDB Endowment},
  publisher = {Association for Computing Machinery (ACM)},
  year = {2025},
  month = Dec,
  pages = {698-712}
}