Pith. sign in

REVIEW 3 major objections 6 minor 43 references

A learned cardinality estimator for SPARQL graph patterns works on entirely new knowledge graphs without retraining.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

An encoder-decoder GNN over a factor-graph view of RDF KGs estimates BGP cardinalities on entirely unseen graphs without retraining, cutting median q-error roughly in half versus the best baseline.

T0 review reviewed 2026-07-31 challenge →

load-bearing objection Real first fully inductive BGP cardinality estimator with a clean locality theorem and strong leave-one-out wins—but the Wikidata fold undercuts the adoption claim until the training mixture is fixed. the 3 major comments →

arxiv 2607.28311 v1 pith:KJ7HOLR3 submitted 2026-07-30 cs.DB cs.LG

Fully Inductive Cardinality Estimation

Tim Schwabe , Lukas Ketzer , Maribel Acosta This is my paper
classification cs.DB cs.LG
keywords cardinality estimationSPARQLknowledge graphsgraph neural networksinductive learningquery optimizationfactor graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Query optimizers for knowledge graphs need fast, accurate guesses of how many results a Basic Graph Pattern will return. Existing neural estimators beat classical statistics, but they must be retrained whenever the graph changes or a new graph appears—blocking real deployment. This paper introduces FICE, an encoder–decoder graph neural network that never stores entity- or relation-specific parameters. It builds embeddings from a factor-graph view of the raw triples, then composes those embeddings along the query’s join structure to predict log-cardinality. Because the embeddings are generated offline and the decoder alone runs online, estimates stay under a millisecond. Across ten held-out graphs the method cuts median error roughly in half versus the strongest prior approach and produces better join plans than a production triplestore planner.

Core claim

FICE is the first learned BGP cardinality estimator that generalizes to entirely unseen knowledge graphs, including unseen relations, with no retraining. Jointly training a local encoder on a factor-graph view of the KG with a decoder that reads the query topology yields embeddings specialized for cardinality; on ten leave-one-graph-out KGs it lowers overall median q-error from 13.54 to 5.34 and first-order stochastically dominates every baseline in the high-error tail.

What carries the argument

The 2-hop locality theorem on the factor-graph view: BGP cardinality depends only on the 2-hop neighborhood around bound terms. That fact justifies a local message-passing encoder that produces entity and relation embeddings, which a decoder GNN then composes along the query join topology to predict log-cardinality.

Load-bearing premise

The nine training graphs must be diverse enough that the jointly trained model still works when the held-out graph is much larger, denser, or has far bigger cardinalities than anything seen in training.

What would settle it

Hold out a large, dense graph such as Wikidata (or a new graph whose size and cardinality distribution lie outside the training mixture) and check whether median q-error and tail q-error remain better than the strongest baseline; a clear reversal would falsify the claim of reliable full inductivity.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • A triplestore can ship one pretrained FICE model and apply it to any new RDF graph after a single offline embedding pass, without per-graph retraining.
  • Embedding refresh is local: only the two-hop neighborhood of changed triples needs re-encoding when the KG is updated.
  • Adding a lightweight ranking loss over sibling sub-queries turns the same model into a join-order signal that already beats a production planner’s Cout cost on held-out data.
  • Sub-millisecond decoder latency makes the estimator practical inside the optimizer’s plan search loop.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the same locality idea holds for richer SPARQL fragments (optional patterns, property paths), a single inductive backbone could serve more of the optimizer than BGP alone.
  • The observed under-performance on dense, high-cardinality graphs suggests that pairing the GNN encoder with non-smoothing features (for example spectral or random-walk descriptors) could close the remaining gap without losing inductivity.
  • Because embeddings are optimized end-to-end for cardinality rather than for generic link prediction, the same training recipe might transfer to other graph-workload statistics that classical summaries miss.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper introduces FICE, an encoder–decoder GNN for BGP cardinality estimation over RDF knowledge graphs that is designed to be fully inductive: entity/relation embeddings are produced from a factor-graph view of the KG using only structure (degree, constant, node-type), and a query decoder composes those embeddings along the join topology to predict log-cardinality. A 2-hop locality theorem (Theorem 1, Appendix B) motivates the factor-graph encoder. Training uses neighborhood sampling and joint encoder–decoder optimization; at inference, embeddings are generated offline and decoding is sub-millisecond. In leave-one-graph-out experiments over 10 KGs, FICE reports overall median q-error 5.34 (best competitor 13.54), first-order stochastic dominance on the q-error CCDF, competitive latency, and improved Cout/p-error versus QLever’s planner when augmented with a ranking loss.

Significance. If the inductive transfer result holds under the stated protocol, this is a genuine advance for learned cardinality estimation on KGs: prior learned estimators (GNCE, LSS, LMKG) are transductive or only semi-inductive and require retraining or graph-specific pretrained embeddings, which blocks adoption under continuous KG change. The factor-graph formulation plus a clean locality theorem, end-to-end cardinality-specialized embeddings, offline/online decoupling, and a careful leave-one-out plus structural-JSD analysis are concrete technical contributions. Code and datasets are released. The join-ordering extension with ranking loss and comparison to a production triplestore planner strengthens the systems relevance beyond pure q-error.

major comments (3)
  1. [§4.1, Table 2, Fig. 2, Abstract] Table 2 and §4.1: the headline claim of generalizing to “entirely unseen graphs” with overall median q-error 5.34 and CCDF dominance (Abstract; Fig. 2) is an unweighted macro-aggregate. On the largest production-like held-out graph (Wikidata), FICE’s median q-error is 16.48, worse than LSS (8.00), SumRDF (9.00), and WJ (13.04); LMKG is better on its restricted shapes. The paper attributes this to distribution shift in size/density/cardinality and encoder oversmoothing. Theorem 1 only establishes sufficiency of 2-hop information, not that a model trained on the nine smaller/sparser graphs extracts transferable statistics under fan-out-10 sampling. Please either (i) report size- or density-stratified aggregates and qualify the abstract claim accordingly, or (ii) add at least one larger/denser training mixture experiment (even a partial one) so the adoption-facing half of the claim is not r
  2. [Theorem 1, Appendix B; §3.2] Theorem 1 (Appendix B) assumes every triple pattern contains at least one bound term. The main text notes FICE is “readily applicable” to all-variable patterns, but neither the theorem nor the experimental tables isolate fully unbound TPs. Please state clearly which evaluated queries satisfy the theorem’s hypothesis, and either extend the locality argument or report a separate breakdown for queries with unbound-only patterns so the gap between theory and practice is explicit.
  3. [§3.3, Appendix C] §3.3 / Appendix C: neighborhood sampling with fan-out [10,10,10,10] and depth 4 is load-bearing for both scalability and the inductive signal the encoder can see. There is no sensitivity study (fan-out or depth) linking sampling aggressiveness to q-error, especially on dense graphs where oversmoothing is already cited. A small ablation on held-out DBpedia100k or Hetionet would substantiate the axiom that fan-out 10 preserves enough co-occurrence signal for cardinality.
minor comments (6)
  1. [Fig. 2] Fig. 2 x-axis spans many orders of magnitude; a log-binned inset or truncated view for the practical q-error range (e.g., 1–10^4) would make the dominance claim easier to read without changing the result.
  2. [Table 1, Fig. 3b] Table 1: several cells are empty (“—”). Briefly state in the caption whether this means zero queries generated or queries excluded, to avoid ambiguity when interpreting shape-wise boxplots in Fig. 3b.
  3. [§2] §2: PRICE is correctly noted as relational; a one-sentence contrast on why hand-crafted histogram features do not transfer to multi-relational KG join topologies would help non-DB readers.
  4. [§3.2, Appendix C] Notation: ρ ∈ {−3,…,3} for edge roles is clear in §3.2, but Appendix C’s “absolute role |ρ|” should cross-reference the main-text definition to avoid confusion with signed direction.
  5. [§1–§2] Typos/spacing: “BasicGraphPatterns(BGP)”, “they aretransductive”, “GraphSAGE[13]demonstrated” and similar missing spaces appear in the introduction and related work; a pass for whitespace and compound words would improve polish.
  6. [Appendix H, §4.2] Appendix H ranking loss: λ=3.0, α=1.0, β=1.0 are stated without sensitivity; a short note that median q-error stayed ~3.22–3.23 under the combined loss is helpful—consider one sentence on whether λ was tuned on a validation split.

Circularity Check

0 steps flagged

No significant circularity: inductive claim rests on leave-one-out evaluation and an independent locality proof, not on fitted or self-defined quantities.

full rationale

FICE’s central claims are (i) a 2-hop locality theorem for BGP cardinality on a factor-graph view and (ii) empirical leave-one-graph-out transfer of a jointly trained encoder–decoder without test-graph labels or IRI features. Theorem 1 is proved from the factor-graph construction and SPARQL join semantics (Appendix B); it does not define cardinality in terms of the model or fit any free parameter. Embeddings are produced from graph-agnostic initial features (constant, log-degree, node-type) plus message passing; test IRIs never enter the model. Training minimizes Smooth-L1 on log-cardinalities of training graphs only; at inference the encoder is run offline once and the decoder is evaluated against ground-truth cardinalities obtained by execution. Self-citations (e.g. GNCE) appear as related work and as a competing baseline under the same leave-one-out protocol, not as load-bearing uniqueness or ansatz justifications. Distribution-shift failures on Wikidata/YAGO are openly reported and are generalization/representativeness issues, not circular reductions of predictions to inputs. No step equates a claimed prediction with a quantity fixed by construction from the same data.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 2 invented entities

The central inductive claim rests on standard GNN universality assumptions, the distributional similarity of training and test KGs, the factor-graph rewrite, and a set of architectural hyperparameters chosen by the authors. No new physical entities are postulated; the free parameters are ordinary ML knobs and the locality theorem’s bound-term precondition.

free parameters (4)
  • encoder/decoder hidden dimension d=128 (decoder readout 200) = 128 / 200
    Chosen by authors; directly affects capacity and the reported q-errors.
  • neighborhood sampling fan-out [10,10,10,10] and depth 4 = [10]*4
    Hand-chosen to fit GPU memory; Theorem 1 only requires 2 hops in theory, so the extra depth and cap are free design choices that can drop information.
  • Smooth-L1 beta, AdamW lr=1e-4, batch=32, dropout=0.1, ranking lambda=3.0 = lr=1e-4, lambda=3.0
    Standard training hyperparameters that influence the final median q-error and join-ordering numbers.
  • initial node feature constant z_base=0.1 = 0.1
    Ad-hoc constant introduced so the linear projection has a non-zero channel; not derived.
axioms (5)
  • standard math BGP cardinality on the factor-graph view equals cardinality on the 2-hop neighborhood of bound terms when every triple pattern contains at least one bound term (Theorem 1).
    Proved in Appendix B from the bijection between triple nodes and edges and the bipartite structure of G_f; load-bearing for the local encoder design.
  • domain assumption The family of training KGs and the held-out test KGs are drawn from a common distribution over graph topologies and query workloads so that encoder embeddings transfer.
    Stated as the optimization objective in §3.1; empirically strained by Wikidata/YAGO results in §4.1.
  • domain assumption A relational GINE encoder plus GINE decoder with attention pooling is a sufficiently expressive universal approximator of the local cardinality function.
    Implicit throughout §3.2; standard GNN expressivity assumption, not proved for this architecture.
  • domain assumption Occurrence counts (o_s, o_p, o_o) concatenated with embeddings are legitimate, graph-agnostic features that do not break inductivity.
    Used in the decoder featurization; they are simple statistics recomputed per graph, analogous to classical summaries.
  • ad hoc to paper Neighborhood sampling with fan-out 10 preserves enough co-occurrence signal for the cardinality task.
    Justified by appeal to GraphSAGE but not proved; directly affects what the encoder can see on dense graphs.
invented entities (2)
  • Factor-graph view G_f of an RDF KG (triple nodes + role-labeled edges) independent evidence
    purpose: Expose relations as first-class nodes and localize cardinality to a 2-hop neighborhood so a standard MPNN can produce inductive entity/relation embeddings.
    Standard factor-graph construction applied to RDF; not a new ontological primitive, but the paper’s central representational move.
  • Cardinality-specialized entity/relation embeddings produced by joint encoder-decoder training no independent evidence
    purpose: Replace general-purpose pretrained embeddings (RDF2Vec, ProNE) with vectors optimized end-to-end for log-cardinality regression.
    Defined operationally by the training loop; their quality is measured only by downstream q-error on held-out graphs.

reviewed 2026-07-31 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Fully Inductive Cardinality Estimation." pith.science (2026). https://pith.science/paper/KJ7HOLR3

@misc{pith2026260728311,
  author       = {Pith},
  title        = {Pith review of: Fully Inductive Cardinality Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KJ7HOLR3}},
  note         = {Machine review of arXiv:2607.28311}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Query optimization of Basic Graph Patterns (BGP) SPARQL queries over Knowledge Graphs (KG) requires accurate cardinality estimation. Recently published learned estimators outperform statistics- and sampling-based approaches, but share a limitation preventing their adoption in real-world triplestores: they are transductive and require retraining when the underlying graph changes or when applied to new graphs. We present FICE (Fully Inductive Cardinality Estimation), the first learned cardinality estimator for BGP queries over KGs that generalizes to entirely unseen graphs (including unseen relations), without any retraining. FICE is a graph neural network (GNN) with two coupled components. First, an encoder GNN over a factor-graph view of the KG produces entity and relation embeddings. We prove that BGP cardinality is a local function of the 2-hop neighborhood around bound terms in this view, motivating the local message-passing encoder. A decoder GNN then composes these embeddings along the join topology of the query to predict log-cardinality. The encoder and decoder are trained jointly, making the embeddings specialized for cardinality estimation. FICE is trained using neighborhood sampling to scale to KGs with millions of triples, and decouples embedding generation from cardinality decoding to enable estimation latency below a millisecond. Compared to learned and non-learned baselines over 10 KGs, FICE reduces the overall median q-error from 13.54 (for the best competitor) to 5.34 and dominates all approaches in tail behavior.

Figures

Figures reproduced from arXiv: 2607.28311 by Lukas Ketzer, Maribel Acosta, Tim Schwabe.

Figure 1
Figure 1. Figure 1: Overview of the FICE architecture. The Encoder GNN produces embed [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Complementary cumulative distribution function (CCDF) of q-errors [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Signed q-error boxplots across all compared approaches [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Estimation latency (median with 25th–75th percentile error bars) of all [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration for the proof on locality. All triple nodes and hence subjects, [PITH_FULL_IMAGE:figures/full_fig_p022_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Complementary CDF of p-error for FICE and Qlever’s optimizer on held [PITH_FULL_IMAGE:figures/full_fig_p032_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Detailed Illustration of the encoder GNN, showing the transformation [PITH_FULL_IMAGE:figures/full_fig_p033_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Detailed Illustration of the decoder GNN, showing how a query graph gets [PITH_FULL_IMAGE:figures/full_fig_p034_8.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 8 canonical work pages

  1. [1]

    In: Hitzler, P., Dalal, A., Mahdavinejad, M.S., Norouzi, S.S

    Acosta, M., Qin, C., Schwabe, T.: Neuro-symbolic query optimization in knowl- edge graphs. In: Hitzler, P., Dalal, A., Mahdavinejad, M.S., Norouzi, S.S. (eds.) Handbook on Neurosymbolic AI and Knowledge Graphs, Frontiers in Artificial In- telligence and Applications, vol. 400, pp. 624–643. IOS Press, Amsterdam (2025). https://doi.org/10.3233/FAIA250225

    work page doi:10.3233/faia250225 2025

  2. [2]

    Ali, M., Berrendorf, M., Hoyt, C.T., Vermue, L., Sharifzadeh, S., Tresp, V., Lehmann, J.: Pykeen 1.0: A python library for training and evaluating knowledge graph embeddings. Journal of Machine Learning Research22(82), 1–6 (2021), http://jmlr.org 1 https://github.com/TimEricSchwabe/fully-inductive-cardinality-estimation Fully Inductive Cardinality Estimation 17

    2021

  3. [3]

    Aytimur, M., Chondrogiannis, T., Grossniklaus, M.: SPACE: cardinality estima- tion for path queries using cardinality-aware sequence-based learning. Proc. ACM Manag. Data3(3), 218:1–218:26 (2025).https://doi.org/10.1145/3725355, https://doi.org/10.1145/3725355

    work page doi:10.1145/3725355 2025

  4. [4]

    In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

    Bast, H., Buchhold, B.: Qlever: A query engine for efficient sparql+text search. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. p. 647–656. CIKM ’17, Association for Computing Machinery, New York, NY, USA (2017).https://doi.org/10.1145/3132847.3132921,https:// doi.org/10.1145/3132847.3132921

    arXiv 2017

  5. [5]

    CoRRabs/2104.13478(2021), https://arxiv.org/abs/2104.13478

    Bronstein, M.M., Bruna, J., Cohen, T., Velickovic, P.: Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. CoRRabs/2104.13478(2021), https://arxiv.org/abs/2104.13478

    Pith/arXiv arXiv 2021

  6. [6]

    In: Raedt, L.D., Wro- bel, S

    Burges, C.J.C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., Hullender, G.N.: Learning to rank using gradient descent. In: Raedt, L.D., Wro- bel, S. (eds.) Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005. pp. 89–96. ACM International Conference Proceeding Series, AC...

    arXiv 2005

  7. [7]

    In: Gottlob, G., Vardi, M.Y

    Cluet, S., Moerkotte, G.: On the complexity of generating optimal left-deep pro- cessing trees with cross products. In: Gottlob, G., Vardi, M.Y. (eds.) Database Theory - ICDT’95, 5th International Conference, Prague, Czech Republic, Jan- uary 11-13, 1995, Proceedings. pp. 54–67. Lecture Notes in Computer Sci- ence, Springer (1995).https://doi.org/10.1007/...

    work page doi:10.1007/3-540-58907-4_6 1995

  8. [8]

    W3c recommendation, W3C (Feb 2014),https: //www.w3.org/TR/rdf11-concepts/,https://www.w3.org/TR/2014/ REC-rdf11-concepts-20140225/

    Cyganiak, R., Wood, D., Lanthaler, M.: RDF 1.1 concepts and abstract syntax. W3c recommendation, W3C (Feb 2014),https: //www.w3.org/TR/rdf11-concepts/,https://www.w3.org/TR/2014/ REC-rdf11-concepts-20140225/

    2014

  9. [9]

    Davitkova, A., Gjurovski, D., Michel, S.: Lmkg: Learned models for cardinality estimation in knowledge graphs (2021),https://arxiv.org/abs/2102.10588

    Pith/arXiv arXiv 2021

  10. [10]

    CoRRabs/2507.16991(2025).https://doi.org/ 10.48550/ARXIV.2507.16991,https://doi.org/10.48550/arXiv.2507.16991

    Fey, M.,Sunil,J., Nitta,A., Puri, R.,Shah,M., Stojanovic, B., Bendias,R., Barghi, A., Kocijan, V., Zhang, Z., He, X., Lenssen, J.E., Leskovec, J.: Pyg 2.0: Scalable learning on real world graphs. CoRRabs/2507.16991(2025).https://doi.org/ 10.48550/ARXIV.2507.16991,https://doi.org/10.48550/arXiv.2507.16991

    Pith/arXiv arXiv doi:10.48550/arxiv.2507.16991 2025

  11. [11]

    Galkin, M., Yuan, X., Mostafa, H., Tang, J., Zhu, Z.: Towards foundation models for knowledge graph reasoning.https://doi.org/10.48550/arXiv.2310.04562, http://arxiv.org/abs/2310.04562

    Pith/arXiv arXiv doi:10.48550/arxiv.2310.04562

  12. [12]

    Synthesis Lectures on Artifi- cial Intelligence and Machine Learning, Morgan & Claypool Publishers (2020)

    Hamilton, W.L.: Graph Representation Learning. Synthesis Lectures on Artifi- cial Intelligence and Machine Learning, Morgan & Claypool Publishers (2020). https://doi.org/10.2200/S01045ED1V01Y202009AIM046,https://doi.org/10. 2200/S01045ED1V01Y202009AIM046

    doi:10.2200/s01045ed1v01y202009aim046 2020

  13. [13]

    In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R

    Hamilton, W.L., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R. (eds.) Advances in Neu- ral Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach,...

    2017

  14. [14]

    Schwabe et al

    Han, Y., Wu, Z., Wu, P., Zhu, R., Yang, J., Tan, L.W., Zeng, K., Cong, G., Qin, Y., Pfadler, A., Qian, Z., Zhou, J., Li, J., Cui, B.: Cardinality es- 18 T. Schwabe et al. timation in dbms: a comprehensive benchmark evaluation. Proc. VLDB En- dow.15(4), 752–765 (Dec 2021).https://doi.org/10.14778/3503585.3503586, https://doi.org/10.14778/3503585.3503586

    arXiv 2021

  15. [15]

    W3c rec- ommendation, World Wide Web Consortium (W3C) (Mar 2013), https://www.w3.org/TR/sparql11-query/,https://www.w3.org/TR/2013/ REC-sparql11-query-20130321/

    Harris, S., Seaborne, A.: SPARQL 1.1 Query Language. W3c rec- ommendation, World Wide Web Consortium (W3C) (Mar 2013), https://www.w3.org/TR/sparql11-query/,https://www.w3.org/TR/2013/ REC-sparql11-query-20130321/

    2013

  16. [16]

    In: The Semantic Web: 17th International Conference, ESWC 2020, Heraklion, Crete, Greece, May 31–June 4, 2020, Proceedings

    Heling, L., Acosta, M.: Estimating characteristic sets for rdf dataset profiles based on sampling. In: The Semantic Web: 17th International Conference, ESWC 2020, Heraklion, Crete, Greece, May 31–June 4, 2020, Proceedings. p. 157–175. Springer-Verlag, Berlin, Heidelberg (2020).https://doi.org/10.1007/ 978-3-030-49461-2_10,https://doi.org/10.1007/978-3-030...

    work page doi:10.1007/978-3-030-49461-2_10 2020

  17. [17]

    Semantic Web14(3), 491–526 (2023)

    Heling, L., Acosta, M.: Characteristic sets profile features: Estimation and ap- plication to SPARQL query planning. Semantic Web14(3), 491–526 (2023). https://doi.org/10.3233/SW-222903,https://doi.org/10.3233/SW-222903

    work page doi:10.3233/sw-222903 2023

  18. [18]

    arXiv preprint arXiv:1905.12265 (2019)

    Hu,W.,Liu,B.,Gomes,J.,Zitnik,M.,Liang,P.,Pande,V.,Leskovec,J.:Strategies for pre-training graph neural networks. arXiv preprint arXiv:1905.12265 (2019)

    Pith/arXiv arXiv 1905

  19. [19]

    In: 9th Biennial Conference on Innovative Data Systems Re- search, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings

    Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., Kemper, A.: Learned cardinalities: Estimating correlated joins with deep learn- ing. In: 9th Biennial Conference on Innovative Data Systems Re- search, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org (2019),https://vldb.org/cidrdb/2019/ learned-cardinalities-estimati...

    2019

  20. [20]

    VLDB Endow.9(3), 204– 215 (2015).https://doi.org/10.14778/2850583.2850594,http://www.vldb

    Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How good are query optimizers, really? Proc. VLDB Endow.9(3), 204– 215 (2015).https://doi.org/10.14778/2850583.2850594,http://www.vldb. org/pvldb/vol9/p204-leis.pdf

    arXiv 2015

  21. [21]

    In:Özcan,F.,Koutrika,G.,Madden,S.(eds.)Proceedingsofthe2016International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016

    Li, F., Wu, B., Yi, K., Zhao, Z.: Wander join: Online aggregation via random walks. In:Özcan,F.,Koutrika,G.,Madden,S.(eds.)Proceedingsofthe2016International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016. pp. 615–629. ACM (2016).https://doi.org/ 10.1145/2882903.2915235,https://doi.org/10.1145/2882...

    arXiv 2016

  22. [22]

    In: Chaudhuri, K., Salakhutdi- nov, R

    Li, Y., Gu, C., Dullien, T., Vinyals, O., Kohli, P.: Graph matching networks for learning the similarity of graph structured objects. In: Chaudhuri, K., Salakhutdi- nov, R. (eds.) Proceedings of the 36th International Conference on Machine Learn- ing, ICML 2019, 9-15 June 2019, Long Beach, California, USA. pp. 3835–3845. Proceedings of Machine Learning Re...

    2019

  23. [23]

    In: 7th Inter- national Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019

    Loshchilov, I., Hutter, F.: Decoupled weight decay regularization. In: 7th Inter- national Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net (2019),https://openreview.net/forum? id=Bkg6RiCqY7

    2019

  24. [24]

    In: Proceedings of the 2021 International Conference on Management of Data

    Marcus, R., Negi, P., Mao, H., Tatbul, N., Alizadeh, M., Kraska, T.: Bao: Making learned query optimization practical. In: Proceedings of the 2021 International Conference on Management of Data. p. 1275–1288. SIGMOD ’21, Association for Computing Machinery, New York, NY, USA (2021).https://doi.org/10.1145/ 3448016.3452838,https://doi.org/10.1145/3448016.3452838

    arXiv 2021

  25. [25]

    Marcus, R., Negi, P., Mao, H., Zhang, C., Alizadeh, M., Kraska, T., Papaem- manouil, O., Tatbul, N.: Neo: A learned query optimizer. Proc. VLDB Endow.12, 1705–1718 (2019),https://api.semanticscholar.org/CorpusID:102352007 Fully Inductive Cardinality Estimation 19

    2019

  26. [26]

    In: Dayal, U., Whang, K., Lomet, D.B., Alonso, G., Lohman, G.M., Kersten, M.L., Cha, S.K., Kim, Y

    Moerkotte, G., Neumann, T.: Analysis of two existing and one new dynamic pro- gramming algorithm for the generation of optimal bushy join trees without cross products. In: Dayal, U., Whang, K., Lomet, D.B., Alonso, G., Lohman, G.M., Kersten, M.L., Cha, S.K., Kim, Y. (eds.) Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, K...

    2006

  27. [27]

    Negi, P., Marcus, R., Kipf, A., Mao, H., Tatbul, N., Kraska, T., Alizadeh, M.: Flow-loss: Learning cardinality estimates that matter. Proc. VLDB Endow. 14(11), 2019–2032 (2021).https://doi.org/10.14778/3476249.3476259,http: //www.vldb.org/pvldb/vol14/p2019-negi.pdf

    arXiv 2019

  28. [28]

    In: Abiteboul, S., Böhm, K., Koch, C., Tan, K

    Neumann, T., Moerkotte, G.: Characteristic sets: Accurate cardinality estima- tion for RDF queries with multiple joins. In: Abiteboul, S., Böhm, K., Koch, C., Tan, K. (eds.) Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany. pp. 984–994. IEEE Computer Society (2011).https://doi.org/10.110...

    arXiv 2011

  29. [29]

    In: Maier, D., Pottinger, R., Doan, A., Tan, W., Alawini, A., Ngo, H.Q

    Park, Y., Ko, S., Bhowmick, S.S., Kim, K., Hong, K., Han, W.: G-CARE: A frame- work for performance benchmarking of cardinality estimation techniques for sub- graph matching. In: Maier, D., Pottinger, R., Doan, A., Tan, W., Alawini, A., Ngo, H.Q. (eds.) Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online ...

    arXiv 2020

  30. [30]

    In: Cruz, I.F., Decker, S., Allemang, D., Preist, C., Schwabe, D., Mika, P., Uschold, M., Aroyo, L

    Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. In: Cruz, I.F., Decker, S., Allemang, D., Preist, C., Schwabe, D., Mika, P., Uschold, M., Aroyo, L. (eds.) The Semantic Web - ISWC 2006, 5th International Semantic Web Conference, ISWC 2006, Athens, GA, USA, November 5-9, 2006, Proceedings. pp. 30–43. Lecture Notes in Computer Scien...

    work page doi:10.1007/11926078_3 2006

  31. [31]

    MADOC (2016),https://madoc.bib.uni-mannheim.de/41307/1/Ristoski_ RDF2Vec.pdf, data and Web Science Group, University of Mannheim

    Ristoski, P., Paulheim, H.: Rdf2vec: Rdf graph embeddings for data min- ing. MADOC (2016),https://madoc.bib.uni-mannheim.de/41307/1/Ristoski_ RDF2Vec.pdf, data and Web Science Group, University of Mannheim

    2016

  32. [32]

    IEEE Trans

    Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE Trans. Neural Networks20(1), 61–80 (2009). https://doi.org/10.1109/TNN.2008.2005605,https://doi.org/10.1109/TNN. 2008.2005605

    arXiv 2009

  33. [33]

    Schwabe, T., Acosta, M.: Cardinality estimation over knowledge graphs with em- beddings and graph neural networks. Proc. ACM Manag. Data2(1), 44:1–44:26 (2024).https://doi.org/10.1145/3639299,https://doi.org/10.1145/3639299

    work page doi:10.1145/3639299 2024

  34. [34]

    5281/zenodo.19729262,https://github.com/DE-TUM/rdf-subgraph-sampler

    Schwabe, T., Acosta, M.: rdf-subgraph-sampler: Sampling Subgraph Templates and Cardinalities from RDF Knowledge Graphs (Apr 2026).https://doi.org/10. 5281/zenodo.19729262,https://github.com/DE-TUM/rdf-subgraph-sampler

    2026

  35. [35]

    In: Bernstein, P.A

    Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Ac- cess path selection in a relational database management system. In: Bernstein, P.A. (ed.) Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30 - June 1. pp. 23–34. ACM (1979).https://doi.org/10.1145/582095.582099...

    arXiv 1979

  36. [36]

    In: Champin, P., Gandon, 20 T

    Stefanoni, G., Motik, B., Kostylev, E.V.: Estimating the cardinality of conjunctive queries over RDF data using graph summarisation. In: Champin, P., Gandon, 20 T. Schwabe et al. F., Lalmas, M., Ipeirotis, P.G. (eds.) Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018. pp. 1043–1052. ACM (2018).h...

    arXiv 2018

  37. [37]

    Sun, J., Zhang, J., Sun, Z., Li, G., Tang, N.: Learned cardinality estimation: a design space exploration and a comparative evaluation. Proc. VLDB Endow.15(1), 85–97 (Sep 2021).https://doi.org/10.14778/3485450.3485459,https://doi. org/10.14778/3485450.3485459

    arXiv 2021

  38. [38]

    OpenReview.net (2019),https://openreview

    Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? In: 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net (2019),https://openreview. net/forum?id=ryGs6iA5Km

    2019

  39. [39]

    Yang, Z., Kamsetty, A., Luan, S., Liang, E., Duan, Y., Chen, X., Stoica, I.: Neu- rocard: One cardinality estimator for all tables. Proc. VLDB Endow.14(1), 61– 73 (2020).https://doi.org/10.14778/3421424.3421432,http://www.vldb.org/ pvldb/vol14/p61-yang.pdf

    arXiv 2020

  40. [40]

    Zeng, T., Lan, J., Ma, J., Wei, W., Zhu, R., Zhou, Y., Li, P., Ding, B., Lian, D., Wei, Z., Zhou, J.: Price: A pretrained model for cross-database cardinality estimation. Proc. VLDB Endow.18(3), 637–650 (Nov 2024).https://doi.org/ 10.14778/3712221.3712231,https://doi.org/10.14778/3712221.3712231

    arXiv 2024

  41. [41]

    In: Kraus, S

    Zhang, J., Dong, Y., Wang, Y., Tang, J., Ding, M.: Prone: Fast and scalable net- work representation learning. In: Kraus, S. (ed.) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019. pp. 4278–4284. ijcai.org (2019).https://doi.org/ 10.24963/IJCAI.2019/594,https://doi.org...

    work page doi:10.24963/ijcai.2019/594 2019

  42. [42]

    In: Proceedings of the 2021 International Conference on Management of Data

    Zhao, K., Yu, J.X., Zhang, H., Li, Q., Rong, Y.: A learned sketch for subgraph counting. In: Proceedings of the 2021 International Conference on Management of Data. p. 2142–2155. SIGMOD ’21, Association for Computing Machinery, New York, NY, USA (2021).https://doi.org/10.1145/3448016.3457289,https:// doi.org/10.1145/3448016.3457289

    arXiv 2021

  43. [43]

    At each of theLlayers, every node updates its own embedding by aggregating the embeddings of its immediate neighbors, together with edge features between them

    Zhu, R., Chen, W., Ding, B., Chen, X., Pfadler, A., Wu, Z., Zhou, J.: Lero: A learning-to-rank query optimizer (2023),https://arxiv.org/abs/2302.06873 Fully Inductive Cardinality Estimation 21 A Preliminaries Graph Neural Networks.A GNN [32,5,12], produces a numerical vector, i.e., embedding, for each node of a graph. At each of theLlayers, every node upd...

    Pith/arXiv arXiv 2023

This paper was first reviewed by grok-4.5 on July 31, 2026.