Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.19008 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908671554879488 |
|---|---|
| author | Chen, Liuyi Hu, Yuchen Yang, Zhengyi Zhou, Xu Zhang, Wenjie Li, Kenli |
| author_facet | Chen, Liuyi Hu, Yuchen Yang, Zhengyi Zhou, Xu Zhang, Wenjie Li, Kenli |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19008 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching Chen, Liuyi Hu, Yuchen Yang, Zhengyi Zhou, Xu Zhang, Wenjie Li, Kenli Databases 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. |
| title | Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching |
| topic | Databases |
| url | https://arxiv.org/abs/2511.19008 |