EUVIMEDEUVIMED entdecken
Crossref

AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling

Seoyong Lee, Jinho Lee

Proceedings of the VLDB Endowment · 01.10.2025 · 19 (2) · 238-251

DOI: 10.14778/3773749.3773761 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 17.03.2026. Verfasst von Seoyong Lee und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 91 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Approximate Graph Pattern Mining (AGPM) is essential for analyzing large-scale graphs where exact counting is computationally prohibitive. While there exist numerous sampling-based AGPM systems, they all rely on uniform sampling and overlook the underlying probability distribution. This limitation restricts their scalability to a broader range of patterns. In this paper, we introduce AGIS, an extremely fast AGPM system capable of counting arbitrary patterns from huge graphs. AGIS employs structure-informed neighbor sampling, a novel sampling technique that deviates from uniformness but allocates specific sampling probabilities based on the pattern structure. We first derive the ideal sampling distribution for AGPM and then present a practical method to approximate it. Furthermore, we develop a method that balances convergence speed and computational overhead, determining when to use the approximated distribution. Experimental results demonstrate that AGIS significantly outperforms the state-of-the-art AGPM system, achieving 28.5X geometric mean speedup and more than 100,000X speedup in specific cases. Furthermore, AGIS is the only AGPM system that scales to graphs with tens of billions of edges and robustly handles diverse patterns, successfully providing accurate estimates within seconds. We will open-source AGIS to encourage further research in this field.

Zitieren

APA

Lee, S., & Lee, J. (2025). AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling. Proceedings of the VLDB Endowment, 19(2), 238-251. https://doi.org/10.14778/3773749.3773761

Vancouver

Lee S, Lee J. AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling. Proceedings of the VLDB Endowment. 2025;19(2):238-251. doi:10.14778/3773749.3773761

BibTeX
@article{Lee2025,
  author = {Lee, Seoyong and Lee, Jinho},
  title = {AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling},
  journal = {Proceedings of the VLDB Endowment},
  year = {2025},
  volume = {19},
  number = {2},
  pages = {238--251},
  doi = {10.14778/3773749.3773761}
}
Kostenlos starten →