Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach
Proceedings of the VLDB Endowment · 2025-04 · 18 (8) · 2695-2708
DOI: 10.14778/3742728.3742758 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 03.09.2025. Verfasst von Qiuyu Guo und 5 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 73 Literaturangaben.
Abstract (Originalsprache)
Subgraph counting is a fundamental problem in graph analytics with broad applications, yet remains computationally intractable due to its #P-hardness. To address this, numerous approximate solutions have been proposed, though they often suffer from limited efficiency and accuracy. In this paper, we introduce FlowSC, a novel approach that achieves both high accuracy and efficiency in subgraph counting. Our method starts with an enhanced candidate filtering algorithm, which significantly improves the pruning capability of bipartite graph-based techniques with minimal overhead. Building on this, we propose a bottom-up flow-learning model based on a new Graph Neural Network (GNN) architecture. By employing a carefully designed message-passing mechanism, the model explicitly controls the direction, range, and iterations of information flow, enabling a simulation of the candidate tree-based counting process. This mechanism is further empowered by a customized message aggregation technique, alongside a pretraining strategy that facilitates model training. Extensive experiments show that FlowSC can achieve up to 4 orders of magnitude improvement in accuracy and 3× improvement in efficiency over the baselines across datasets, while scaling to billion-edge graphs.
Zitieren
APA
Guo, Q., Yang, J., Zhang, W., Wang, H., Zhang, Y., & Lin, X. (2025). Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach. Proceedings of the VLDB Endowment, 18(8), 2695-2708. https://doi.org/10.14778/3742728.3742758
Vancouver
Guo Q, Yang J, Zhang W, Wang H, Zhang Y, Lin X. Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach. Proceedings of the VLDB Endowment. 2025;18(8):2695-2708. doi:10.14778/3742728.3742758
BibTeX
@article{Guo2025,
author = {Guo, Qiuyu and Yang, Jianye and Zhang, Wenjie and Wang, Hanchen and Zhang, Ying and Lin, Xuemin},
title = {Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {18},
number = {8},
pages = {2695--2708},
doi = {10.14778/3742728.3742758}
}
EUVIMED