Track trials, findings, and clinical evidence as it lands.
Search papers, labs, and topics across Lattice.
This paper introduces FICE (Fully Inductive Cardinality Estimation), a novel learned estimator for cardinality in SPARQL queries over Knowledge Graphs that effectively generalizes to unseen graphs without requiring retraining. By leveraging a graph neural network architecture with a coupled encoder-decoder design, FICE achieves significant improvements in cardinality estimation accuracy, reducing the median q-error from 13.54 to 5.34 compared to the best existing methods. The approach's ability to operate efficiently on large-scale KGs with low latency positions it as a transformative tool for query optimization in real-world applications.
FICE slashes cardinality estimation error by over 60% while eliminating the need for retraining on new graphs, a game-changer for real-time query optimization in knowledge graphs.
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.