A Learned Sketch for Subgraph Counting

Summary: Active Learned Sketch for Subgraph Counting (ALSS) fuses a neural regression sketch with an active-learning loop to update on new query graphs. Targets large labeled graphs, enabling accurate, scalable subgraph counting and aiding optimizers for multi-way self-joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6180
Venue: SIGMOD
Year: 2021
Pagerank: 6.7747398e-05
Overall Rank: 3,778 | 73.72%
DOI: 10.1145/3448016.3457289

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,001	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7404487e-05
3,369	Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed	2022	VLDB	7.171452e-05
3,752	Computing Graph Edit Distance via Neural Graph Matching	2023	VLDB	6.7879009e-05
4,434	Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process	2022	SIGMOD	6.1929999e-05
6,289	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	5.1275309e-05
6,714	Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks	2024	SIGMOD	4.9512171e-05
7,732	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	4.6657123e-05
7,934	Fast Local Subgraph Counting	2024	VLDB	4.613363e-05
7,936	Machine Learning for Subgraph Extraction: Methods, Applications and Challenges	2023	VLDB	4.613363e-05
8,069	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	4.5934204e-05
9,041	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	4.4039656e-05
9,648	Inductive Attributed Community Search: to Learn Communities across Graphs	2024	VLDB	4.3109001e-05
9,728	SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning	2025	SIGMOD	4.2942813e-05
9,845	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	4.2721228e-05
10,096	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	4.1945683e-05
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1945683e-05
10,623	Efficient and Adaptive Estimation of Local Triadic Coefficients	2025	VLDB	4.1945683e-05
10,632	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.1945683e-05
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 28 of 28 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
608	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019235898
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
758	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.0001706608
806	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.00016434274
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
1,193	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013414989
1,254	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013027411
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,474	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB	0.00011825229
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
1,924	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010077055
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.9554751e-05
2,501	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6453446e-05
2,969	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7974762e-05
3,142	Active Learning for ML Enhanced Database Systems	2020	SIGMOD	7.4815444e-05
3,410	Motivo: fast motif counting via succinct color coding and adaptive sampling	2019	VLDB	7.1253867e-05
3,646	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8853079e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,726	Cardinality Estimation of LIKE Predicate Queries using Deep Learning	2025	SIGMOD	4.2943379e-05
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
10,843	Machine Learning for Graph Data Management and Query Processing	2025	VLDB	4.1945683e-05
3,725	Estimating Cardinalities with Deep Sketches	2019	SIGMOD	6.8170734e-05
7,936	Machine Learning for Subgraph Extraction: Methods, Applications and Challenges	2023	VLDB	4.613363e-05
7,474	Cardinality Estimation of Approximate Substring Queries using Deep Learning	2022	VLDB	4.7194345e-05
3,449	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0824319e-05
6,383	Sample-Efficient Cardinality Estimation Using Geometric Deep Learning	2024	VLDB	5.0884322e-05
10,632	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.1945683e-05
3,001	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7404487e-05