Subgraph Enumeration: Beyond Tree Decomposition
Proceedings of the VLDB Endowment · 01.05.2026 · 19 (9) · 2303-2316
DOI: 10.14778/3819518.3819552 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 19.08.2026. Verfasst von Qiyan Li und 2 weiteren Autor:innen. Die Arbeit nennt 78 Literaturangaben.
Abstract (Originalsprache)
We address the subgraph enumeration problem: given an unlabeled pattern graph p and an unlabeled data graph G , find all subgraphs in G isomorphic to p. Unlike labeled matching, the absence of label constraints creates exponentially larger search spaces with limited pruning opportunities. To address this challenge, we follow tree decomposition (TD) approaches that break complex patterns into smaller subgraphs (bags), compute matches for each bag, and join them to obtain final results. However, existing TD approaches suffer from suboptimal decomposition selection, incomplete symmetry-breaking usage, and expensive intermediate result materialization. We present MDSE (Minimal Decomposition-based Subgraph Enumeration) with three key contributions. We introduce minimal fractional hypertree decompositions (MinFHDs) that ensure compact bags and an efficient algorithm to explore all optimal-width decompositions. We develop new symmetry-breaking integration using complete rule sets with systematic selection for maximum pruning effect. To reduce materialization costs, we design MixJoin by embedding final result assembly within bag processing and formulate an enhanced cost model for attribute orders, incorporating both intersection and materialization overhead. Evaluation across 101 pattern graphs and 8 real-world datasets shows MDSE substantially outperforms existing algorithms.
Zitieren
APA
Li, Q., Yu, J. X., & He, Z. (2026). Subgraph Enumeration: Beyond Tree Decomposition. Proceedings of the VLDB Endowment, 19(9), 2303-2316. https://doi.org/10.14778/3819518.3819552
Vancouver
Li Q, Yu JX, He Z. Subgraph Enumeration: Beyond Tree Decomposition. Proceedings of the VLDB Endowment. 2026;19(9):2303-2316. doi:10.14778/3819518.3819552
BibTeX
@article{Li2026,
author = {Li, Qiyan and Yu, Jeffrey Xu and He, Zongyan},
title = {Subgraph Enumeration: Beyond Tree Decomposition},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {9},
pages = {2303--2316},
doi = {10.14778/3819518.3819552}
}
EUVIMED