Accurate and Fast Approximate Graph Pattern Mining at Scale

Summary: ScaleGPM: an A-GPM system with on-the-fly convergence detection that provides provable confidence and low overhead, plus eager-verify pruning and hybrid sampling to overcome low-hit “needle-in-the-hay” cases. Delivers geomean 565× (up to 610k×) speedups vs Arya and scales to billion-node graphs with stable, rapid termination. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14249
Venue: VLDB
Year: 2025
Pagerank: 4.7639399e-05
Overall Rank: 7,317 | 49.10%
DOI: 10.14778/3705829.3705831

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,078	Estimating Biclique Counts with Accuracy Guarantees	2026	SIGMOD	4.1945683e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1945683e-05
10,276	AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling	2026	VLDB	4.1945683e-05
10,658	LLMLog: Advanced Log Template Generation via LLM-driven Multi-Round Annotation	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
1,740	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	0.0001071792
3,009	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	7.7214924e-05
3,215	Fractal: A General-Purpose Graph Pattern Mining System	2019	SIGMOD	7.3645742e-05
3,410	Motivo: fast motif counting via succinct color coding and adaptive sampling	2019	VLDB	7.1253867e-05
6,468	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS	5.0526408e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,542	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5794502e-05
9,565	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD	4.3254416e-05
9,614	Auto-Approximation of Graph Computing	2014	VLDB	4.3177432e-05
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
6,704	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	4.9554912e-05
5,436	Output Space Sampling for Graph Patterns	2009	VLDB	5.5042223e-05
11,565	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1945683e-05
8,273	GraphINC: Graph Pattern Mining at Network Speed	2023	SIGMOD	4.5450209e-05
11,559	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1945683e-05
10,276	AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling	2026	VLDB	4.1945683e-05