Sublime: Selecting Subgraph Matching Algorithms via Machine Learning
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-25
DOI: 10.1145/3802115 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Genryu Kuraya und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: DFF, JST.
Abstract (Originalsprache)
Subgraph matching is a fundamental problem in graph analysis that seeks all instances (or embeddings) of a query subgraph within a larger data graph. Numerous subgraph matching algorithms have been developed for efficient processing. However, the best-performing algorithm differs across query and data graphs. A previous study proposed manually designed rule-based models for selecting the algorithm to use depending on query and data characteristics. However, this rule-based model is often ineffective even on in-distribution data, let alone on graphs having the same distribution. In this paper, we propose SUBLIME, a machine-learning-based framework that selects a subgraph matching algorithm to use for the sake of efficiency, based on the query and the data. SUBLIME learns from observations of the performance of subgraph matching algorithms on different data. It comprises two key components: a labeling strategy, which adds labels to experimental results, and a featurizer, which extracts handcrafted features from datasets and queries. Our experiments in subgraph matching and subgraph coverage problems show that SUBLIME selects high-performing algorithms and improves embeddings per second by up to 36.0% and coverage by up to 46.3% over baselines.
Förderung
- DFF
- JST
Zitieren
APA
Kuraya, G., Skitsas, K., Mottin, D., Karras, P., Amagata, D., & Sasaki, Y. (2026). Sublime: Selecting Subgraph Matching Algorithms via Machine Learning. Proceedings of the ACM on Management of Data, 4(3), 1-25. https://doi.org/10.1145/3802115
Vancouver
Kuraya G, Skitsas K, Mottin D, Karras P, Amagata D, Sasaki Y. Sublime: Selecting Subgraph Matching Algorithms via Machine Learning. Proceedings of the ACM on Management of Data. 2026;4(3):1-25. doi:10.1145/3802115
BibTeX
@article{Kuraya2026,
author = {Kuraya, Genryu and Skitsas, Konstantinos and Mottin, Davide and Karras, Panagiotis and Amagata, Daichi and Sasaki, Yuya},
title = {Sublime: Selecting Subgraph Matching Algorithms via Machine Learning},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--25},
doi = {10.1145/3802115}
}
EUVIMED