EUVIMEDEUVIMED entdecken
Crossref

Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach

Qiuyu Guo, Jianye Yang, Wenjie Zhang, Hanchen Wang, Ying Zhang, Xuemin Lin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →