DBScholar

Back to papers

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
h6be0d606dc1bc100
Venue
SIGMOD
Year
2021
Pagerank
7.6278115e-05
Overall Rank
3,105 | 79.19%
DOI
10.1145/3448016.3457289

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{zhao_sigmod21,
        title = {{A Learned Sketch for Subgraph Counting}},
        author = {Zhao, Kangfei and Yu, Jeffrey Xu and Zhang, Hao and Li, Qiyan and Rong, Yu},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457289},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457289},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank Citing Paper Year Venue Pagerank
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
2,941 Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed 2022 VLDB 7.8196527e-05
3,461 Computing Graph Edit Distance via Neural Graph Matching 2023 VLDB 7.2629166e-05
4,479 Lightweight and Accurate Cardinality Estimation by Neural Network Gaussian Process 2022 SIGMOD 6.5665703e-05
5,271 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1891764e-05
6,485 Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks 2024 SIGMOD 5.7525455e-05
7,552 Fast Local Subgraph Counting 2024 VLDB 5.4802093e-05
7,895 Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items 2023 SIGMOD 5.4152499e-05
8,257 Computing Approximate Graph Edit Distance via Optimal Transport 2025 SIGMOD 5.3519906e-05
8,350 Machine Learning for Subgraph Extraction: Methods, Applications and Challenges 2023 VLDB 5.3325743e-05
8,499 TreeSensing: Linearly Compressing Sketches with Flexibility 2023 SIGMOD 5.3131213e-05
9,247 Inductive Attributed Community Search: to Learn Communities across Graphs 2024 VLDB 5.1862386e-05
9,684 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 5.1258854e-05
9,837 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1064323e-05
10,094 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.068372e-05
10,221 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.0460607e-05
10,379 Algebraic Subgraph Counting 2027 SIGMOD 4.9605343e-05
10,712 Enumerating Graph Pattern Matches with ML Oracles 2026 SIGMOD 4.9605343e-05
10,952 Efficient GPU-Accelerated Local Subgraph Counting 2026 VLDB 4.9605343e-05
11,343 Efficient and Adaptive Estimation of Local Triadic Coefficients 2025 VLDB 4.9605343e-05
11,349 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 29 of 29 cited papers.

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

Rank Cited Paper Year Venue Pagerank
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061463175
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035920657
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024929198
288 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022009138
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
320 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021128745
405 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019020138
439 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018247958
453 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001801482
594 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015814493
658 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00015032442
690 Selectivity Estimation for Range Predicates using Lightweight Models 2019 VLDB 0.00014703258
706 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014622696
752 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014234789
793 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013903938
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013623401
952 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012878316
1,090 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012062682
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
1,171 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011677799
1,253 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011316982
1,444 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010616242
1,583 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010148362
1,839 DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models 2019 SIGMOD 9.5187688e-05
1,843 Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank 2020 VLDB 9.512431e-05
2,228 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.7912743e-05
2,290 Active Learning for ML Enhanced Database Systems 2020 SIGMOD 8.6813363e-05
2,829 G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching 2020 SIGMOD 7.9469964e-05
2,931 Motivo: fast motif counting via succinct color coding and adaptive sampling 2019 VLDB 7.8284452e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR
2 3,282 Estimating Cardinalities with Deep Sketches 2019 SIGMOD
3 9,103 Machine Learning for Graph Data Management and Query Processing 2025 VLDB
4 8,350 Machine Learning for Subgraph Extraction: Methods, Applications and Challenges 2023 VLDB
5 7,440 Cardinality Estimation of Approximate Substring Queries using Deep Learning 2022 VLDB
6 2,523 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB
7 5,457 Sample-Efficient Cardinality Estimation Using Geometric Deep Learning 2024 VLDB
8 11,349 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB
9 10,379 Algebraic Subgraph Counting 2027 SIGMOD
10 2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD