arXiv CS open access

Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs

Georgios Chatzigeorgakidis et al. · arxiv_cs

arXiv CS · Papers

Over the past decades, query cardinality estimation on relational databases has been proven crucial, enabling the result size estimation of all sub-plans of each query. This allowed query optimizers to design efficient query plans, towards minimizing the query response time. Lately, knowledge graphs

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

“This is the authors’ version of the work. It is posted here for your personal use. Not for redistribution. The definitive version has been presented at Int. J. of Semantic Computing 2026.”

Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs Georgios Chatzigeorgakidis, Dimitrios Skoutas, and Alkis Simitsis

arXiv:2610.41669v1 [cs.DB] 30 Oct 2026

Athena Research Center, Greece gchatzi@athenarc.gr, dskoutas@athenarc.gr, alkis@athenarc.gr

Abstract Over the past decades, query cardinality estimation on relational databases has been proven crucial, enabling the result size estimation of all sub-plans of each query. This allowed query optimizers to design efficient query plans, towards minimizing the query response time. Lately, knowledge graphs are being preferred over traditional databases in various applications, due to their ability to represent complex relationships and semantic meaning in a domain-specific context. In this work, we present a novel approach for supervised similarity-aware cardinality estimation on knowledge graphs that incorporates similarities into the model training process, thus treating them as first-class citizens. To this end, we present SCE-KG, a model that employs a novel encoding scheme for cardinality estimation, named SGsplit . We further extend our approach by leveraging a Large Language Model (LLM) to generate training queries that resemble realistic user workloads, and show that combining LLM-generated and random walk samples consistently improves estimation accuracy on test workloads generated by two independent LLMs. Our experimental evaluation reveals that our approach outperforms the state-of-the-art techniques in terms of prediction error, achieving 40x and 37x improvement for star and chain queries, respectively (95th percentile), whereas its online overhead accounts for less than 0.05% of the average query execution time and less than 1% of the average query planning time, showing a sub-millisecond latency in all cases. Keywords: cardinality estimation; knowledge graphs; similarity queries; machine learning; query optimization.

Introduction

A Knowledge Graph (KG) is a network that semantically describes entities in a domain of interest and the relationships between them. Over the last years, the interest in KGs and their adoption has been increasing, both in academia and in industry [19]. There exist both open KGs, which are published online, e.g., Wikidata, as well as enterprise KGs, which are internal to a company, e.g., describing products and customers. Moreover, depending on their contents and focus, KGs can be encyclopedic, providing general knowledge about the world, commonsense, describing daily-life concepts, or domain-specific, representing specialized knowledge in a certain domain. KGs have several applications, including advanced search and recommendations [13], while also having a promising synergistic role with Large Language Models, which they can complement and enhance by offering factual, up-to-date knowledge and interpretability [33]. The two most commonly used data models to represent KGs are RDF and Property Graphs [37]. The former, which is a recommendation by the World Wide Web Consortium (W3C), represents facts as triples in the form <subject, predicate, object>, using Internationalized Resource Identifiers (IRIs) to refer to entities and relationships. The latter offers more flexibility, allowing each entity or relationship to be associated with a label and a set 1

of key-value pairs. The SPARQL query language, which is also a W3C recommendation, is used to query RDF graphs, whereas Cypher, Gremlin and G-CORE are languages for querying property graphs [2]. Storing, indexing, and querying KGs, especially RDF graphs, has received a lot of attention [36]. Yet, cardinality estimation, which is a crucial component for query optimization [23], is still underexplored for KGs. Cardinality estimation refers to predicting the result size of a given query. It is a difficult and long-standing problem that has been primarily studied in the context of relational databases, with most recent approaches moving from techniques such as histograms and samplings to learned cardinality estimation based on deep learning [21, 42]. However, unlike relational databases, KGs do not have a fixed, predefined, and binding schema. Although in many aspects this is an advantage offering greater flexibility, it makes querying a KG, including cardinality estimation, more challenging. Recent work has shown that state-of-the-art techniques for relational databases do not perform as well for KGs [8]. To fill this gap, LMKG [8] has proposed a deep-learning approach for cardinality estimation in RDF graphs. The main novelty of the work lies in designing an encoding, termed SG encoding, that represents the queries as subgraph patterns. However, LMKG only supports queries without similarity predicates and, as verified experimentally, fails to estimate query cardinalities in such scenarios accurately. Learned cardinality estimation has also been investigated for similarity queries [38, 43]. In this type of query, given a query point p, a distance function, and a threshold r, the goal is to estimate the number of data points that have distance to p no more than r. Similarity search is a fundamental problem in information retrieval, data integration, and recommendation, all of which are also typical application areas of KGs [13]. Motivated by this, in this paper, we introduce and address the novel problem of learned cardinality estimation for KG queries, including similarity predicates. This paper extends our previous research [6] by (a) elaborating on the theoretical foundations of MLPs, (b) introducing a clustering-based segmentation scheme, (c) proposing an LLM-augmented strategy for training data generation, and (d) expanding our experimental analysis to include four new studies. In particular, we present SCE-KG, a method that employs a fine-grained MLP architecture, which, in synergy with the novel SGsplit encoding, treats node similarities as first-class citizens. SCE-KG shows excellent performance and effectiveness compared to the state of the art, and especially for queries containing many triples. The main contributions of our work are as follows: • We introduce the novel problem of learned cardinality estimation for KG queries, including similarity predicates. • We propose SGsplit , an encoding for incorporating the similarity predicates in learned models. • We present SCE-KG, a novel method that treats similarities as first-class citizens. • We improve estimation accuracy via a clustering-based segmentation scheme that operates on similarity thresholds and partitions the training set into smaller subsets. • We present the results of an extensive experimental evaluation on three real-world and one synthetic datasets. The rest of the paper is structured as follows. Section 2 discusses related work. Section 3 formulates the similarity-aware cardinality estimation problem on KG. Section 4 describes the SCE-KG method. Section 5 presents our experimental evaluation, and Section 6 concludes the paper.

Related Work

The work most related to ours can be classified into the following areas: (a) cardinality estimation in relational databases, (b) learning approaches to cardinality estimation in relational databases, (c) similarity-aware cardinality estimation, and (d) cardinality estimation on knowledge graphs. Cardinality estimation in relational databases Query optimizers depend on accurate cardinality and selectivity estimates, especially for intermediate results, to produce reasonable plans. Toward this direction, many approaches have been proposed employing a variety of techniques, e.g., histograms [4, 9, 12, 27, 34], entropy [25, 35], samples [10, 15] and index-based sampling [22], histograms and samples [28], probabilistic models [7, 11, 40], randomized hashing and data sketching [5], exponential back-off [20], dynamic sampling [31], and so on. These approaches work with assumptions (e.g., attribute value independence – AVI, uniformity, data independence) and when these assumptions cannot be met, the techniques usually fall back to an educated guess. However, in practice the estimates are routinely wrong by orders of magnitude, causing slow queries and unpredictable performance. Recently, a significant amount of works have studied various learning techniques for cardinality estimation in the context of relational databases [16, 39]. [44] builds local models, each focusing on one part of the DB schema. [32] evaluates deep learning techniques with respect to trade-offs among model size, training time, and prediction accuracy. CRN [17] uses deep learning to estimate cardinalities using the containment rates among queries. DeepDB [18] proposes a data-driven approach that supports workload and data changes, fast retraining, and reasonable accuracy for unseen queries. FLAT [48] builds on top of DeepDB [18], considering the level of dependency between attributes. Naru [47] and NeuroCard [46] use autoregressive models to learn the joint distribution of relations, with the latter focusing on learning the full outer join of all tables. UAE [45] uses data and queries to accurately estimate cardinalities, even when data or workload shifts. [38,43] learn estimating the cardinality for similarity search. Supervised methods work better in static environments, where they avoid re-training. Several data-driven approaches adopt incremental training, thus becoming more dynamic. Most approaches use q-error as the de facto loss function or quality metric. Flow-Loss [29] presents a novel loss function that considers the quality of the estimated cardinalities in terms of query runtime. [42] argues that the proposed solutions are not yet production-ready due to issues like high training/inference time, black-box decisions, and difficulty in recovering after data updates. Similarity-aware cardinality estimation The above approaches deal with cardinality estimation for queries without similarity predicates. Recently, a new line of work has emerged that focuses on estimating the cardinality for similarity queries. In [41], the authors introduce a machine learning-based query optimizer for spatial joins that considers dataset skewness and algorithm complexity. The optimizer consists of three models, the first of which performs cardinality estimation. Sun et al. [38], employ Deep Neural Networks (DNNs) for learned cardinality estimation on similarity queries. To overcome the inherent complexity of DNNs, the authors derive a query and data segmentation technique before training a separate model for each segment. In [43], Wang et al. attempt to leverage the monotonicity of the cardinality with respect to the similarity threshold by quantizing the similarity thresholds to a pre-defined number of bins before training. Then, they forward them to an encoder-decoder-based DNN. The decoder consists of several smaller decoder modules, one for each separate threshold bin. Their output is then aggregated to provide the estimated cardinality. Cardinality estimation on knowledge graphs Although the problem of learned cardinality estimation in KGs is critical in many applications, the research community has only recently 3

considered it. To the best of our knowledge, LMKG [8] is the only research approach to the learned cardinality estimation problem in KGs. LMKG addresses SPARQL queries, especially star and chain queries, over RDF graphs. To avoid introducing a high overhead, the neural network employed by LMKG is a multilayer perceptron (MLP). To achieve better performance, LMKG constructs different models per query type and/or size. LMKG feeds queries to the model using a novel encoding that represents each query as a subgraph pattern: each query triple is first converted to numerical form by encoding its terms with either one-hot or binary encoding, after which the full query is encoded via subgraph (SG) encoding, consisting of two binary vectors, X of size n and E of size e, and a matrix A ∈ {0, 1}n∗n∗e , where n is the number of nodes within the subgraph and e the number of predicates within the subgraph; together, A, X, and E capture the query’s structure, with A indicating node connections and predicates, X representing node features, and E representing predicate features (see Figure 2(b)). However, LMKG only supports equality predicates. Hence, it cannot effectively estimate the cardinality of queries that include similarity predicates, which is the focus of our paper.

Problem Formulation

3.1

The cardinality estimation problem on KG

In this work, we focus on RDF graphs and SPARQL queries. This is without loss of generality because a translation between property graphs and directed edge-labeled graphs is possible without loss of information [3]. Accordingly, a KG G consists of a finite set of triples t, where each triple t = (s, p, o) comprises a subject s, a predicate p and an object o. Subjects and predicates are URIs, whereas an object may be a URI or a literal. A SPARQL query q consists of triples forming a graph pattern, where each triple t can have an arbitrary number of variables (unbound terms). Moreover, we assume a similarity function sim which assigns a similarity score to any pair of nodes in the graph. For instance, this may refer to Jaccard similarity or edit similarity for string literals, or cosine similarity computed on node embeddings. In any case, we assume that the similarity score is normalized in the range [0, 1]. Problem statement. Given a graph G and a query q, which may contain one or more similarity filters based on a given similarity function sim and respective user-defined similarity thresholds θi , our goal is to estimate the cardinality of results for q.

3.2

Graph queries

We focus on the two most common types of queries: star queries and chain queries. Previous work [8] has shown that (a) building separate models for different types of queries increases performance, and (b) more complex queries (e.g., snowflake) can be decomposed into simpler ones. Star queries consist of triples centered around the same subject, whereas chain queries consist of a set of triples in which the object of the preceding triple is the subject of the next one. We refer to queries containing n triples as n-star and n-chain queries. Example. Consider the KG depicted in Figure 1 (left), together with an example 2-star similarity query (top right) and an example 2-chain similarity query (bottom right) over it. The 2-star query seeks all movies whose genre has similarity to Sci-Fi at least 0.6 and that are directed by a director with similarity to James Cameron at least 0.8. The 2-chain query seeks all movies directed by Yorgos Lanthimos or a similar director (similarity at least 0.6), where that director was born in Greece or a similar country (similarity at least 0.8).

enre hasG

Titanic

The Terminator

direc tedB y

tedBy direc

In born

James Cameron

hasG enre

enre hasG

Poor Things

Drama

direct edBy

USA

direc tedBy

enre hasG

Aliens

Sci-Fi bornIn

SELECT ?Movie, ?Genre, ?Director WHERE { ?Movie :hasGenre ?Genre AND sim(:Sci-Fi, ?Genre) > 0.6; ?Movie :directedBy ?Director AND sim(:James Cameron, ?Director) > 0.8. }

Greece

Yorgos Lanthimos

SELECT ?Movie, ?Director, ?Country WHERE { ?Movie :directedBy ?Director AND sim(:Yorgos Lanthimos, ?Director) > 0.6; ?Director :bornIn ?Country AND sim(:Greece, ?Country) > 0.8. }

Figure 1: A knowledge graph (left) and example 2-star (top right) and 2-chain (bottom right) similarity queries over it

3.3

Multilayer perceptron (MLP) neural networks

In this work, we follow a supervised learning approach to the problem at hand. Before we present our solution, we discuss basic background concepts. Supervised learning methods for graph data vary. However, lightweight MLP models have the advantages of faster speed and lower memory usage while being quite effective for estimating the number of rows in a relational database query [40]. Such an MLP model takes as input workloads of star and chain queries. As an example, for star queries containing two joins, the MLP input would be: p1 − s1, p2 − s2 : c

(1)

where p1 is the first predicate of the star query that connects the query node to node s1, p2 and s2 are the second predicate and node respectively, and c is the resulting cardinality given these predicates and nodes. Each such training element is encoded and fed into the MLP for training using q-loss as a loss function. The q-loss function is derived from the q-error, which is often used in cardinality estimation, and it can be formulated as follows: L(c, ĉ) = max

ĉ c , c ĉ

(2)

where c is the actual cardinality and ĉ is the estimated one. The intermediate fully connected layers employ the rectifier (ReLU) activation function, defined as: f (x) =

( x 0

if x > 0 otherwise

(3)

where x is the input to a neuron. The cardinalities are log-scaled to alleviate the effect of skewed data and min-max-scaled to allow a sigmoid function at the output. Thus, since cardinality estimation is a regression task, a sigmoid activation function is employed for the output layer that outputs a number in the [0, 1] interval. The sigmoid activation function is defined as: f (x) =

1 1 + e−x

(4)

where x is the input to a neuron.

Similarity-Aware Cardinality Estimation

As discussed, LMKG does not consider similarity queries. Hence, a straightforward attempt to solve the problem would be to extend the SG encoding (see also Section 2) to capture such queries. To this end, we can incorporate the similarity corresponding to each object of a query’s 5

SELECT ?Movie WHERE { ?Movie :hasGenre ?Genre AND sim(:Sci-Fi, ?Genre) > 0.6; ?Movie :directedBy ?Director AND sim(:James Cameron, ?Director) > 0.8}

hasGenre directedBy 0 0 0 0 0 0 A = n 0 0 1 1 0 0 0 0 0 0 0 0 n X = [?0000 0110 0111] E = [01 10]

hasGenre A1 = X1 = [?0000 0110] E1 = [01] s1 = 0.6

(b) hasGenre directedBy 0 0 0 0 0 0 Asim = n 0 0 0.6 0.8 0 0 0 0 0 0 0 0 n X = [?0000 0110 0111] E = [01 10] (a)

(c)

directedBy A2 = X2 = [?0000 0111] E2 = [10] s2 = 0.8

(d)

Figure 2: (a) Query/term mapping, (b) LMKG encoding, (c) SGsim encoding, (d) SGsplit encoding

triplets, in order to enable the training of an MLP model on such data. Conceptually, in star and chain similarity queries, similarities relate to the subject, predicate, and object of the triplet. Example. Consider the query of Figure 2(a) defined over the KG of Figure 1. This query seeks all Sci-Fi movies directed by James Cameron. It also contains similarity predicates. The similarity 0.6 of the first triplet relates directly to the object, i.e., ?Genre, since we seek genres similar to Sci-Fi and indirectly to the subject of the query, i.e., ?M ovie, since we seek movies that have a genre similar to the given one. We proceed as follows. Assume that an ID has been assigned to each node and predicate of the knowledge graph. For example, these could be the integer IDs assigned while building the knowledge graph. Then, all the nodes and predicates within a query are sorted based on their initial IDs and assigned new IDs based on their new order. In the SG encoding –see also Figure 2(b)– a tensor A is derived by assigning ‘1’ for each predicate to the corresponding position of the nodes it connects. Vectors X and E contain the binary encoding of the nodes and predicates according to their initial IDs, respectively (i.e., the unbound variables are represented with zeroes). Still, the SG encoding does not support similarities. Apparently, however, tensor A is the only part of the SG encoding that combines information about subjects, predicates, and objects of query triplets. Thus, to enable a model to be trained on data containing similarities, we differentiate the A tensor by swapping the ‘1’s –which previously denoted the presence of a relationship– with the corresponding similarity. The new tensor is termed Asim . We retain the format of vectors X and E. Figure 2(c) illustrates this baseline approach. Notice the swapped similarities in tensor Asim , annotated with the blue color. To apply cardinality estimation on star and chain queries, using this extended SG encoding, any MLP that is able to receive X, Asim and E as input can be used. Figure 3 depicts a generic architecture of such a model, defined as follows: ŷ = F2 (F1,1 (X), F1,2 (Asim ), F1,3 (E))

(5)

where F1,1 , F1,2 , F1,3 are fully connected layers and ŷ is the estimated cardinality. X, Asim and E are initially passed from three fully connected layers and then are concatenated before passing from an output fully connected layer. The case of similarity-aware cardinality estimation is a superset of the cardinality estimation for queries without similarity predicates (i.e., the similarities would always be equal to 1).

Thus, this generic model using the extended SG encoding can answer both.

F1,1

Asim

F1,2

F1,3

CONCATENATE

KGC-ME Encoding

ESTIMATED CARDINALITY

Figure 3: Generic MLP architecture for similarity-aware queries

4.1

The SCE-KG Model

By considering only the nodes of the query, the extended SG encoding avoids large adjacency matrices and utilizes a size-optimized tensor Asim . Still, Asim is a sparse matrix, which usually contains many zeros and only a few values signifying predicate similarity. For example, in Figure 2c, for each predicate, the corresponding similarity is a single value in an n × n matrix. This is a significant drawback, as the impact of the similarity values on the computation of the cardinality estimation gets diminished with the significant number of linear algebra computations taking place during training and the inherent sparsity of the matrix. To mitigate this, we introduce SCE-KG, a novel model for similarity-aware cardinality estimation. SCE-KG employs the SGsplit encoding, which splits the encoding process into multiple simple sub-encodings, enabling similarities to be handled outside the encoding and treated as first-class citizens in the estimation process. 4.1.1

SGsplit Encoding

Figure 2d depicts an example of SGsplit encoding computation for the query in Figure 2a, which seeks all Sci-Fi (or similar genre) movies directed by James Cameron (or similar director). Ignoring the similarities, this query contains the following two triples: <?Movie :hasGenre ?Genre> <?Movie :directedBy ?Director>

SGsplit encoding considers separate X1 , X2 E1 , E2 vectors and A1 , A2 tensors for each triple of the query. This further reduces the sparsity and dimensionality of Ai tensors, i.e., Ai ∈ {0, 1}n∗n , 0 ≤ i ≤ |t|, where t is the set of triples (joins) in the query. The dimensionality of each tensor Ai , 0 ≤ i ≤ |t| will be 2 × 2 for each triple and vectors Xi and Ei , 0 ≤ i ≤ |t| will always have a length of 2 and 1 respectively. 4.1.2

Model Architecture

SCE-KG is a 3-level multilayer perceptron (MLP) that performs regression tasks. Figure 4 depicts the architecture of SCE-KG for the cardinality estimation of n-star queries. The idea behind it is that a n-star query can be broken into n separate estimation sub-tasks (LEVEL1 in Figure 4) since each triple of the query attributes to the final cardinality (LEVEL2 in Figure 4). To incorporate the contribution of the query’s similarities to each sub-estimation, the subestimations are multiplied by the corresponding similarity. Then, the latent vectors produced are concatenated and passed from a fully connected layer that determines the contribution of each triple to the cardinality and attempts to produce a final estimation (LEVEL3 in Figure 4). More formally, the model is defined as follows:

LEVEL 1 s1

LEVEL 3

F1,1,3

......

F1,t,1

F1,t,2

F1,t,3

FLAT

F2,1

......

F2,t

CONCATENATE

F1,1,1

F1,1,2

CONCATENATE

X1 A1

......

LEVEL 2

FLAT

ESTIMATED CARDINALITY

(1) ?M :hasGenre ?G AND sim(:G1, ?G) > 0.9 (2) ?M :hasGenre ?G AND sim(:G2, ?G) > 0.5 (3) ?M :hasGenre ?G AND sim(:G2, ?G) > 0.8 (4) ?M :hasGenre ?G AND sim(:G1, ?G) > 0.4 (5) ?M:hasGenre ?G AND sim(:G3, ?G) > 0.9

50 250 30 350 10

Group 1 (1) ?M :hasGenre ?G AND sim(:G1, ?G) > 0.9 (3) ?M :hasGenre ?G AND sim(:G2, ?G) > 0.8 (5) ?M :hasGenre ?G AND sim(:G3, ?G) > 0.9

50 30 10

Group 2 (2) ?M :hasGenre ?G AND sim(:G2, ?G) > 0.5 (4) ?M :hasGenre ?G AND sim(:G1 ?G) > 0.4

Figure 4: SCE-KG architecture

250 10

Figure 5: Clustering based on similarities

ŷ = F3 (F2,1 (F1,1,1 (X1 ), F1,1,2 (A1 )), F1,1,3 (E1 )))) × s1 , ... ..., F2,t (F1,t,1 (X1 ), F1,t,2 (A1 )), F1,t,3 (E1 )) × sn )

(6)

where Fi,x,x , i ∈ [1, 3] are the fully connected layers of levels 1-3, Fx,i,x , 0 ≤ i ≤ |t| are the fully connected layers that correspond to each triple of the query and Fx,x,i , i ∈ [1, 3] are the fully connected layers for Xi , Ei , Ai , 0 ≤ i ≤ |t|. First, the input is encoded using SGsplit encoding. Then, each Xi , Ei vectors, and Ai tensor are passed through a fully connected layer and then concatenated per query triple before being passed again from a second group of fully connected layers. The output of each of these layers is then multiplied by the corresponding similarity (i.e., flattening is applied to the similarities to be compatible with the outputs of each fully connected layer). Finally, the outputs of the fully connected layers are concatenated again and passed by a third layer, which estimates the final cardinality. The architecture of SCE-KG allows us to treat similarity as a first-class citizen, by multiplying each similarity with the output of the corresponding triple estimation (i.e., the output of F2,1 ...F2,t , as shown in the figure). This way, since the outputs of these fully connected layers are not sparse, the impact of similarity in cardinality estimation is presumably higher. The advantage of SCE-KG over the baseline approach becomes more apparent for queries that contain a higher amount of triples. A 5-star query would result in a 6 × 6-dimensional A vector in SGsim , which is significantly more sparse than the one for 2-star queries. Our experiments (discussed shortly) also corroborate this observation.

4.2

Improving Accuracy with Clustering

When performing similarity selection, the actual cardinality is increasing monotonically as the threshold θ is relaxed (see Section 3). Overall, lower similarity thresholds tend to produce more results. Motivated by this, the authors in [43] consider a maximum possible threshold and map the thresholds to an integer space, thus generating a finite number of thresholds. Then, for each threshold group, they train a separate model. In our case, this is not possible, since we are dealing with more than one similarity thresholds per training sample; except for the case of queries that contain one triple. To tackle this issue, we apply multidimensional clustering of the training data based on the given similarities on each literal. This way, we end up with a set of training sets. For each set, we train a separate model. Upon estimation, we classify each testing element into one of the available clusters and run the corresponding model. To provide an intuition of our clustering approach, consider the example of a training set consisting of five 1-star queries illustrated in Figure 5. Notice that, there are various similarities for each triple, ranging from 0.4 to 0.9. As already discussed and also shown in our experiments, as we keep relaxing the threshold the cardinality also increases. Thus, a model that will be trained on these data will have to learn that queries involving genre G1 have cardinalities 50 (query (1)) and 350 (query (4)), and those with genre G2 have cardinalities 30 (query (3)) and 250 (query (2)). This imposes a challenge for an MLP, which is an inherent difficulty of 8

the problem that we tackle in this paper: correlating these genres with both low and high cardinalities would require more training data. After clustering the training elements into two groups, notice that the grouped cardinalities are now similar, which is expected to facilitate the training process.

4.3

Answering Complex Queries

As discussed in Section 3, without loss of generality, we presented our approach considering two query types: star and chain queries. However, SCE-KG can answer more complex similarityaware queries on knowledge graphs, such as tree, cycle, clique, petal, and flower queries. This is straightforwardly achieved as the queries can be broken down into triples and fed into the models via the SGsplit encoding. For space considerations, we omit here a detailed description.

4.4

Training Data Creation

[24] argue that generating “realistic” samples of graphs is essential. In our problem, the training set must cover as many graph patterns as possible (the more so given the added complexity of similarities) to let models learn the relationships between node/predicate IDs and cardinalities. As suggested in [24] and also implemented in [8], an optimal way to sample the graph is via random walks. In our case, to simulate this we pick random sub-graphs from within a graph, insert unbound terms where necessary (i.e., to support queries containing one or more unbound variables), and issue the result as a query to the graph. For example, for a 2-star similarity query the obtained cardinalities along with the node/predicate IDs and corresponding similarities can then be formatted as follows: p1 − s1 − sim1, p2 − s2 − sim2 : c

(7)

where sim1 and sim2 are the corresponding similarities. 4.4.1

Using an LLM to generate training data

The random walk approach above uniformly covers the graph, but does not necessarily reflect how users phrase queries in practice. We thus also explore generating training data with a Large Language Model (LLM), composing query patterns that resemble realistic user workloads. Given the predicate vocabulary and a pool of real object identifiers from the graph, we prompt the LLM to produce star query patterns directly in the canonical training format pi -si -simi . The core part of the prompt is the following: A STAR-3 query has 3 outgoing edges from a common source: p1-s1-sim1, p2-s2-sim2,p3-s3-sim3. p_i is a predicate ID; s_i is a real object ID or "*"; sim_i in {0.2, 0.4, 0.6, 0.8, 1.0}. Choose sim values to reflect realistic user search: sim=1.0 = exact match; lower = more tolerance.

The generated patterns are labelled with their actual cardinality on the graph, as the random walk samples are. Since the two reflect complementary views (realistic phrasing vs. uniform graph coverage) they can also be combined into a hybrid training set, as studied in Section 5.3.

Experimental Evaluation

In this section, we present the results of our experimental analysis. We start with a description of our setup and then proceed with the evaluation of the methods proposed. Our code is available online1 . 1

https://github.com/chgeorgakidis/kgc

20000

Dataset SWDF Yelp Wikidata LUBM

5.1

Values star, chain 1, 2, 3 2, 3, 5, 7 20, 50, 100, 200 equi-sized, equi-width, order-of-mag.

Parameter Query type Clusters Joins Epochs Binning

Table 1: Datasets Nodes Rels. Triples Size 106K 65 347K 24MB 9.2M 6 14.4M 14GB 739M 8605 1.25B 99GB 545K 13 1.6M 331MB

15000

Cardinality

Table 2: Parameters

10000 5000 0

0.75 0.5 Similarity

0.25

Figure 6: Cardinality for various thresholds

Experimental Setup

1.0

3 466 o 25 187 32 t 287 to 2 254 Cardinality bins

3 to

7 to

(f) Median q-err.

3 466 o 25 187 32 t 287 to 2 254 Cardinality bins

3 to

7 to

10000

6184 17708 8820 1592 158

4269 7460 6729 1697 160 1201 7166 14564 6167 827 81 1745 1042316181 4728 1 0

(g) Class. acc.

102 1429 7881 25108 1 2 3 4 Predicted bin

21624 4809 196

20000 15000 10000 5000

4732 1202312721 3651 497 1155 6074 10104 4396 778 542 5406 13916 9262 2146 105 2471 1121713233 5791 30 0

(h) SGsim -MLP

40000

30000

1602117332 1250 31

20000

2545 2008811429 410

59 2057 1508013295 3641 0 1 2 3 4 Predicted bin

10000 0

(e) SCE-KG

15000

25000

5062 7791 6361 1006 58

20000

981 6590 16471 6005 277

15000

829 8661 20070 4018

10000

0 0

20 393 5767 28427 1 2 3 4 Predicted bin

25000 0

1832 1039112829 7563 1746 0 1 2 3 4 Predicted bin

(d) LMKG

True bin 2 1

19307 8389 4422 777

10000

True bin 2 1

297 4533 1451511866 3002 0 1 2 3 4 Predicted bin

True bin 2 1

4650 19068 9811 905

20000

1271117149 4227 508

40881 2051 77

10000 5000

647 4967 1132417115 1 2 3 4 Predicted bin

(i) LMKG

24193 6726 3112 373

5000

(j) SCE-KG

Classification accuracy (%)

1.0

4.15

1 to

20000

30000

1 to

1416610608 1699 157

0.2 0.0

0.4

True bin 2 1

1707415263 2140 151

20522 5600 483

0.6

0 0 0 0 100 000 000 o 10 10 t 100 to 00 to 1 0 to 10 10 1000 Cardinality bins

(b) Class. acc. Classification accuracy (%)

7.38

3.9

1 1 to

74 718

o 22 15 t Cardinality bins

(k) Median q-err.

1 1 to

o 22 15 t Cardinality bins

(l) Class. acc.

46 187

59888

26647

18076

66243

20000

(m) SGsim -MLP

50000

77866

9393

11370

73124

40000

Predicted bin

60000 0

69050

15418

60000

True bin

0.0

11668

Predicted bin

(n) LMKG

30000 20000

0.2

75553

True bin

0.4

True bin

0.6

Median q-error

0.8

Median q-error

3.68

(a) Median q-err.

1 to

0.0

0 0 0 0 100 000 000 o 10 10 t 100 to 00 to 1 0 to 10 10 1000 Cardinality bins

3049611187 1236 87

30000

1 to

0.2

True bin 2 1

0.4

39545 3237 206

True bin 2 1

0.6

0.8

Classification accuracy (%)

8.51

Median q-error

4.89

16.11

System The KGs were built using neo4j 5.13, with our methods implemented in Python and Tensorflow 2.7.1. Experiments ran on a server with an AMD Ryzen Threadripper 3960X (24 cores), 256GB RAM, and an NVIDIA GeForce RTX 2080 Ti GPU.

60000 40000

Predicted bin

20000

(o) SCE-KG

Figure 7: (a-e) Order-of-magnitude binning approach; (f-j) equi-sized binning approach for 5 bins; (k-o) equi-sized binning approach for 2 bins Datasets We employ three real-world datasets (SWDF, Yelp and Wikidata) and a synthetic one (LUBM): SWDF (Semantic Web Dog Food) [26], a benchmark linked dataset of academic entities and relations (e.g., people, publications, organizations), built from Scholarlydata2 dump files; Yelp3 , an open U.S. business dataset including users, check-ins, reviews, and business metadata (e.g., state, city), where user reviews were omitted due to their length and the prohibitive query-generation cost driven mainly by Levenshtein distance calculations; Wikidata4 , a large 2

http://www.scholarlydata.org https://www.yelp.com/dataset 4 https://www.wikidata.org/wiki/Wikidata:Main_Page 3

open knowledge base hosted by the Wikimedia Foundation, for which we used the WDBench [1] benchmark and restricted training to a UK-people subgraph of approximately 160K nodes to control scale; and LUBM (Lehigh University Benchmark) [14], a synthetic dataset based on the Univ-Bench ontology, generated using their official tool5 for 20 academic organizations. For each dataset, we build a knowledge graph using the neo4j 6 graph database system. The training samples are then generated as described in Section 4.4, using the Levenshtein distance as a similarity measure, which is supported by the neo4j APOC 7 library. Note that the choice of a similarity measure is orthogonal to how our methods operate; any similarity measure suitable for graphs would work. Each query element contains zero or more unbound terms (i.e., denoted by ‘∗’), where their number and placement are picked randomly. Before training, each training sample is shuffled and split into training and testing datasets. Table 1 lists, for each dataset, the number of nodes, relationships, and triples in the initial graph, as well as the size of the corresponding training samples. Methods We evaluate the following methods: (a) LMKG: As it does not support similarity predicates, for each training element we remove the similarities and treat it as a graph query without similarity predicates. (b) SGsim -MLP: Our MLP based technique that employs the extended SG encoding. (c) SCE-KG: Our approach that treats similarities as first-class citizens, employing the SGsplit encoding. Parameters Table 2 lists the parameters used in our experimental evaluation. We conducted tuning tests for each one to determine their ranges and default values, which are shown in bold in the table. We selected star similarity queries as the default because the datasets lack long enough paths for chain queries. To showcase the advantage of SCE-KG in queries with a larger number of joins, we selected 5 joins as default for star similarity queries and 2 joins for chain similarity queries. As SGsim -MLP does not cope well with clustering (discussed below), we report results with 1 cluster as the default. In several cases in query optimization, especially when the qualifying results are too many, the exact cardinality value is hard to be detected; it suffices, though, for the estimator to at least produce a value of the same order of magnitude as the actual result. Hence, we consider two types of cardinality binning and treat the problem as a classification task. Specifically, the binning types are (i) equi-sized, where each bin contains approximately the same number of cardinalities, and (ii) order-of-magnitude, where the cardinalities differ by an order-of-magnitude. Unless otherwise stated, the equi-sized binning method is used. All the ML models used in this work are MLPs. For performing a fair comparison, we tried to configure them as even as possible. Specifically, each MLP consists of four hidden layers, with 256 neurons each (except the input and the output layer). We use the ReLU activation function for each layer except the output, where we use sigmoid. We use q-loss, which is based on q-error, for a loss function. Finally, we used 50 training epochs as default, a number that we found achieves a good estimation in our experiments. LLM-generated test sets We explore two different LLM-generated test sets. Both are produced by prompting an LLM with a short natural-language description and asking it to phrase realistic multi-hop questions, each with its relations and a per-fact confidence level; the outputs are then mapped to the canonical pi -si -simi format and validated against the graph. The core part of the prompt is the following: 5

http://swat.cse.lehigh.edu/projects/lubm/ https://neo4j.com 7 https://neo4j.com/developer/neo4j-apoc/ 6

You are a person searching a knowledge graph that catalogs a university system. Imagine you are a real person -- a student looking up an advisor, a curious outsider browsing -- what multi-step questions would you ask? Produce one line per query: <NL query> | r1|r2|r3 | c1|c2|c3, where c_i in {exact, near, loose, vague} = your confidence in the name spelling.

The first test set is generated with the same LLM used for the training data (gemini-2.5flash), but through the above natural-language prompt rather than the canonical-format one of Section 4.4.1; it thus probes a different query distribution while keeping the model fixed (1,707 queries). To rule out that any improvement is a product of training and testing with the same model, and to verify that the benefit generalises across LLM families, we employ a different LLM (gpt-4o) for a second test set (1,404 queries). Similarity effect on cardinality In similarity queries, the selectivity relates to the similarity provided for each triple. This motivates the need to employ a different approach than existing, non-similarity-aware methods such as LMKG. If the resulting cardinalities change by relaxing the similarity threshold, it becomes inherently harder to perform estimation solely based on node and predicate IDs. Indicatively, Figure 6 shows the behavior of cardinality with varying similarity for a 1-star query on the SWDF dataset. As expected, relaxing the similarity threshold causes the cardinality to increase exponentially, which justifies approaching similarity-aware cardinality estimation as a different problem.

5.2 5.2.1

Similarity-Aware Cardinality Estimation Cardinality estimation without similarity predicates

A natural question that arises regarding the applicability of our approach is whether it can be applied for cardinality estimation of queries without similarity predicates. To test this, we generate training sets by only issuing queries where similarity equals 1. Figure 8 shows the results. The performance of SCE-KG and SGsim -MLP is similar to the one of LMKG for both star and chain similarity queries with minimal differences; see Figures 8a, 8c and 8b, 8d respectively. In other words, in the scenario that the related work excels (similarity=1), our methods are at least as good as the state of the art. In what follows, we show that our methods provide excellent results for a scenario (similarity<=1) that the related work has not dealt with so far. 5.2.2

Effect of cardinality binning

Depending on the application domain, the provided cardinality estimation can be evaluated separately for a cardinality interval of interest. In a case where the cardinality of the answered queries is skewed to the left (i.e., towards 1), it is preferable to assess the error and accuracy of the estimation by considering cardinality bins whose range increases in an order-of-magnitude manner. Figure 7a depicts the median q-error for this case using the Wikidata dataset, which is rather heavily skewed towards cardinality 1. Notice that, in all cases, SCE-KG achieves the lowest median q-error (up to 40% lower than SGsim -MLP), while LMKG cannot cope well due to its inability to consider the provided similarities (i.e., 8x larger q-error in the worst case). Another way to evaluate the quality of the estimation is by treating the problem as a classification task, where the classes are a set of selected bins on the cardinality axis. Figure 7b depicts this accuracy for bins of order-ofmagnitude-increasing size. As expected, the results are similar here, with LMKG yielding the worst accuracy. SCE-KG is more accurate than SGsim -MLP in all cases, reaching more than 80% accuracy in some cases. Notice that, due to the skewness of the Wikidata dataset, the accuracy tends to be higher for cardinalities closer to 1, since there are more training data for that specific range of cardinalities. Figures 7e 7c and 7d illustrate the corresponding confusion matrices for the classification task. 12

q-error

3 2

1 0 Median

75th perc.

0 Median

95th perc.

(a) Star (q-error)

Classification accuracy (%)

1.0

Classification accuracy (%)

1.0 0.8 0.6 0.4 0.2 0.0

75th perc.

0.8 0.6 0.4 0.2

1 to

95th perc.

(b) Chain (q-error)

189 o 1568 14244 84924 39876 5 t o o 190 1573 t 4457 t 477 to 1 89 Cardinality bins

0.0

1 to

51 78 554 o 17 57 t 3 to 183 Cardinality bins 8 to

(d) Chain (accuracy)

Figure 8: Cardinality estimation without similarity predicates: median, 75th and 95th percentile q-errors

1.0 0.0 0.47

0.61 0.72 0.82 Avg. Similarity

0.92

(a) Wikidata

0.57 0.71 0.83 Avg. Similarity

7.82

6.48

8.81

0.5

0 0.44

0.96

14.9

1.0

0.0 0.41

46.66

3.52

1.5

0.5

Median q-error

1.0

1.5

2.0

Median q-error

6.44

4.1

8.2

7.56

16.82

Median q-error

4.2

3.51

3.38

1.5

Median q-error

2.0

3.11

2.5

3.81

Another way to generate the cardinality bins is by considering intervals containing approximately equal numbers of elements. This way of binning would be preferable for less skewed datasets. Figures 7f and 7g depict the q-error and corresponding accuracies for a set of 5 equisized bins. Notice that, in this case, even though the q-error is again rather low in all cases (except LMKG), the classification accuracy is significantly worse due to the left-wise skewness of the dataset that causes the first three bins’ intervals to be rather narrow. Consequently, a miss that may yield low q-error, for example, estimating cardinality 3 instead of 2, might lead to falsely classifying the element and thus to lower accuracy. This can be verified by the corresponding confusion matrices in all cases (Figures 7j, 7h and 7i) where the falsely predicted cardinalities tend to be for a neighboring bin. Figures 7k and 7l show the results for a commonly considered case involving 2 equi-sized bins (i.e., binary classification). The classification accuracy is much better here for both classes, with SCE-KG demonstrating the higher numbers. This can also be verified by the corresponding confusion matrices, depicted in Figures 7o, 7m and 7n.

0.57 0.68 0.8 Avg. Similarity

(b) Yelp

0.0 0.47

0.92

0.61 0.72 0.82 Avg. Similarity

0.92

(d) LUBM

Figure 9: Median q-error with varying similarity

2 # Clusters

(a) Wikidata

0.0

1.0

0.5

Median q-error

1.5

1.0

0.0

1.5

0.5

2 # Clusters

0.0

(b) Yelp

2 # Clusters

0.0

2 # Clusters

(d) LUBM

Figure 10: Median, 75th and 95th percentile q-errors with varying number of clusters

75th perc.

0 Median

95th perc.

(e) Wikidata (chain)

75th perc.

95th perc.

(f) Yelp (chain)

32.93

417.72 95th perc.

4.48

66.32

0 Median

75th perc.

(d) LUBM (star)

75th perc.

95th perc.

q-error

10 8 6 4 2 0 Median

0 Median

95th perc.

75th perc.

q-error

55.13

29.24

0 Median

95th perc.

(b) Yelp (star)

124.91

(a) Wikidata (star)

75th perc.

153.44

0 Median

95th perc.

32.29

75th perc.

767.57

0 Median

q-error

15 q-error

87.65

9.74

162.47

32.32

7.1

57.01

75th perc.

0 Median

95th perc.

(g) SWDF (chain)

(h) LUBM (chain)

0.4 0.2 6

3 6 746 o 25 718 32 t 228 o t 254 Cardinality bins

3 to

7 to

1 to

Classification accuracy (%)

546

549 502 136 5 1 to 755 Cardinality bins

o 28 t

o7 47 t

7 5 3 266 074 o 17 14 t 178 to 6 to 10 6 6 2 Cardinality bins

0.0

(e) Wikidata

6 8 4 0 6 141 o 1198 o 6974 53802 07981 to o2 0t 0t 142 1199 69758 8344 t 53 Cardinality bins

1 to

(d) LUBM

0.2

o 11

0.0

25 t

0.4

0.2

0.6

0.4

7 to

0.8

0.6

2 4 o 12 745654 to 1 123 Cardinality bins

3 to

1.0

0.8

3 to

1 to

1.0

0.8

0.0

0.2

(b) Yelp

1.0

1 to

0.4

0.2

(a) Wikidata

0.0

0.6

0.4

Classification accuracy (%)

0.8

0.6

Classification accuracy (%)

1 to

1.0

Classification accuracy (%)

0.6

1.0 0.8 0.6 0.4 0.2 0.0

Classification accuracy (%)

0.8

0.0

0.8

Classification accuracy (%)

Figure 11: Median, 75th and 95th percentile q-errors for star (a-d) and chain similarity queries (e-h)

5 9 7 6 208 270 118 o 40 12 t 06 to 1 4 to 41 to 586 4 1 5 1 9 12 4127 Cardinality bins

0.0

1 to

(f) Yelp

2 8 9 281 692 o 13 37 t 133 to 2 to 67 2 8 2 Cardinality bins

3 to

1.0 0.8 0.6 0.4 0.2 0.0 1 to

6 802 319 739 354 871 102 to 202 to 312 to 607 0 to 8 6 3 872 10347 20253 34606 Cardinality bins

(g) SWDF

(h) LUBM

0.00

(a) Wikidata

# Joins

(b) Yelp

7.32

8.16

8.85

# Joins

6.02

3 2

0.25

3 2

0.50

5.26

0.75

4 Median q-error

Median q-error

4 Median q-error

1.00

7.1

4.24

1.25

Median q-error

3.31

Figure 12: Classification accuracy for star (a-d) and chain (e-h) queries

# Joins

(d) LUBM

Figure 13: Median q-error with varying number of joins 5.2.3

Varying selectivity

In Figure 9, we evaluate the q-error of each approach according to the selectivity of the issued queries, which, as discussed, depends on the given similarity thresholds. Specifically, we grouped the queries based on their similarities and calculated the average similarity per group. Clearly, 14

SCE-KG outperforms the rest of the approaches in almost all cases (i.e., up to approx. 30% lower q-error compared to SGsim -MLP), except for larger similarities in the Yelp dataset, where the estimation accuracy is similar. LMKG again yields significantly worse performance, with up to 25x larger q-error. For smaller similarity thresholds, SCE-KG performs even better, due to giving more emphasis on the similarities during training and estimation. As the similarities approach 1, we fall back to the case discussed in Section 5.2.1. 5.2.4

Effect of clustering

Figure 10 depicts the q-error of SGsim -MLP and SCE-KG with the test datasets using the clustering optimization for 1, 2, and 3 clusters. Note that as clustering is performed on similarities, LMKG is not evaluated in this experiment as it does not support similarity. For SCE-KG, increasing the number of clusters improves the q-error. This reveals an interesting trade-off. Increasing the number of clusters tends to improve the quality of the estimation due to narrowing down the –increased due to similarities– diversity of the training data. But at the same time, the task becomes harder due to decreasing the number of training elements to train in each sub-model. Recall from Section 4.2 that a separate model is trained for each cluster. Interestingly, SGsim -MLP cannot cope well for more than 1 clusters, presenting up to 50% larger q-error. This is attributed to the reduction of training data size and its inherent characteristic of downplaying the provided similarities. This experiment drove our decision to select 1 cluster as default for the experimental evaluation, to maintain a fair setting for all methods.

# Joins

(a) Wikidata

600

750

200

400

500

100

200

250 0

Training time (sec)

1000

300

800

Training time (sec)

1250

Training time (sec)

1250 1000 750 500 250 0

# Joins

(b) Yelp

# Joins

(d) LUBM

Figure 14: Training times (offline phase) with varying query complexity

5.2.5

Query types

In Figure 11, we evaluate in more detail the quality of cardinality estimation separately for similarity star (Figures 11a, 11b, 11c and 11d) and similarity chain queries (Figures 11e, 11f, 11g and 11h). We show for each dataset the median, the 75th and 95th percentile of q-errors; that is, the maximum error ignoring the 25% and 5% of the largest errors, respectively. For the same reasons we explained above, LMKG does not perform well in this scenarios either. For star similarity queries, SCE-KG performs better in all cases. For Yelp, SCE-KG has a comparable median q-error with SGsim -MLP. The 75th and 95th percentiles, however, show an increasing rate of q-error differences as a result of SCE-KG’s ability to better exploit the given similarities. For the same reason, the differences are even larger in the other datasets. For instance, SCE-KG has up to 3x lower q-error for the 95th percentile in the LUBM dataset. Note that for chain similarity queries we only have 2 joins as the datasets under evaluation did not contain large enough paths within the graphs to generate an adequately large training set. Consequently, the differences are smaller here but still apparent. The results are similar for the classification accuracy of 5 equi-sized bins, as shown in Figure 12. Notice that the accuracy is better (up to 20%) for star similarity queries on the LUBM dataset (Figures 12b and 12d) since they are less skewed than Wikidata and SWDF. As in the case of q-errors, SCE-KG outperforms both SGsim -MLP and LMKG in all cases, except for the Yelp dataset, where the accuracy, especially for star similarity queries, is similar. 15

(a) Wikidata

# Joins

(b) Yelp

558 5185

90 2700

53 789

Time (millisec)

0.04

0.1

281 1049

56 1629

# Joins

23 1173

0.06

0.2

0.0

0.08

16 787

73 466

Time (millisec)

0.02

0.3

26 353

Time (millisec)

0.04

0.00

0.05 0.04 0.03 0.02 0.01 0.00

34 266

333 2094

183 1857

48 3188

29 4333

Time (millisec)

0.06

0.02

# Joins

0.00

# Joins

(d) LUBM

Figure 15: Estimation overhead (online phase) vs. avg query planning and execution times with varying query complexity

Figure 16: Resource utilization: cpu, memory, and disk (training on Wikidata with 5 joins). (a) LMKG, (b) SGsim -MLP, (c) SCE-KG. 5.2.6

Varying query joins

Increasing the query triples (i.e., joins) is expected to introduce additional complexity to the model training and hinder the process of cardinality estimation. Adding similarities to the mix, the whole process becomes significantly more complex. Figure 13 depicts the results in terms of q-error for a varying number of joins (#joins) in the queries. Note that for the Yelp dataset (Figure 13b), the largest possible #joins is 3. LMKG cannot cope well in this scenario either. As the query becomes more complex (i.e., the #joins increase), SCE-KG clearly outperforms SGsim -MLP. For 2 and 3 joins on Yelp and LUBM (Figure 13d) datasets, the two approaches are on par. However, on the latter dataset the difference increases significantly in favor of SCE-KG as the #joins increase (up to 2x lower q-error). This is due to the similarities have significant impact in model training and estimation, as described in Section 4.1. The key takeaway from this experiment is that SCE-KG scales excellently with increasingly complex queries involving a large #joins. 5.2.7

Offline and online overheads

Figure 14 depicts the model training times (offline phase) for all approaches. SCE-KG employs a more complex model structure as a result of the SGsplit encoding that increases the number of MLPs required in the levels 1 and 2 of the model (see Figure 4). This reflects to its training time, which is higher that those of the SGsim -MLP and LMKG models that employ a simpler architecture. For the same reason, SCE-KG has higher average query estimation time (online phase), as shown in Figure 15. To put things into perspective, we should compare the query estimation time overhead imposed by SGsim -MLP and SCE-KG to the query planning and total execution time. Typically, query execution involves multiple preparation steps (e.g., parsing, semantic analysis, planning) before the query is dispatched for execution [30]. Figure 15 shows that the time overhead of all three methods tested are a small fraction of the average planning (purple) and execution time (dark green) of the queries considered in this experiment. In fact, the three methods’ overhead

Table 3: Memory consumption SCE-KG 2 joins 7 joins SWDF 4.7MB 25MB Wikidata 4.8MB 28MB LUBM 4.4MB 25MB Dataset

SGsim -MLP 2 joins 7 joins 2.6MB 4.3MB 2.8MB 4.7MB 2.6MB 4.3MB

LMKG 2 joins 7 joins 2.6MB 4.3MB 2.8MB 4.7MB 2.6MB 4.3MB

is sub-millisecond, while the planning times are in the order of 10s-100s of milliseconds and the execution times in the order of seconds. At the same time, 95% of the time the q-error of SCE-KG is significantly smaller than SGsim -MLP and LMKG (see also Figure 11). Hence, we anticipate that the more accurate cardinality estimates will result into better query plans, which will significantly compensate for the difference in both the offline and online phase of SCE-KG compared to SGsim -MLP and LMKG. Our analysis however reveals another interesting observation. A lightweight approach such as MLP consistently offers reasonably satisfactory estimates at a very low cost. Hence, an interesting future direction would be to explore more complex architectures aiming at even more accurate cardinality estimates at the expense of some additional budget. 5.2.8

Resource utilization

Finally, we measured the resource utilization of the three methods. In particular, we monitored the training phase of each method on the Wikidata dataset with queries containing 5 joins. Figure 16 plots for each method the CPU utilization, the memory used, and the disk reads for the duration of the training phase. We observe that LMKG after a short warm-up phase has a stable CPU utilization around 10%. SGsim -MLP and SCE-KG show a similar behavior with a short peak before they also get stabilized around 10% as well. The peak in CPU usage accounts for the clustering step (see Section 4.2). Memory usage seems quite stable with SCE-KG requiring somewhat more memory in the initial iterations. We drilled down a bit more on memory consumption for two extreme cases of query types: simple queries with 2 joins and more complex ones with 7 joins (Yelp is omitted as it allows up to 3 joins). Table 3 depicts the size of each model (in MBs). The table verifies that SCE-KG, due to its more elaborate encoding and architecture, uses memory more aggressively than the other two models for more complex queries. The disk utilization shows some interesting patterns representing the layered architecture of each model in the duration of training (50 epochs). SCE-KG demonstrates a busier activity as it processes in parallel many smaller tensors. One could also see the training times on the x-axis: approximately, 27min (LMKG), 22min (SGsim -MLP), and 52min (SCE-KG). SCE-KG and SGsim -MLP present a nice trade-off of better accuracy/slower training vs. decent accuracy/faster training.

5.3

Augmenting Training Data with an LLM

We compare three training set sources for SCE-KG on the LUBM dataset and star queries with 3 joins: RW (random walks), LLM (queries generated by an LLM following the prompt of Section 4.4.1), and Hybrid (a mix of the two). All conditions are evaluated on both LLMgenerated test sets of Section 5.1. Table 4 reports the q-error for the full training set and a reduced, 30K-sample one on each test set. Full training set As shown in (Table 4(a),(b)), the hybrid approaches outperform the pure RW baseline on every metric and on both test sets. The 50/50 split has a 12–22% lower median q-error (28–35% for the 95th percentile) relative to RW. The pure LLM approach has a lower median q-error (it achieves the lowest median on the Gemini test set), however, its max qerror is the largest of all cases. This confirms that LLM-generated queries shift the workload 17

Table 4: q-error on the GPT-4o and Gemini test sets; LUBM, 3-star queries. Best per metric in bold. (a) Full training set – GPT-4o Metric RW LLM H 50/50 H 30/70 H 10/90 median 1.89 1.77 1.66 1.72 1.74 p75 3.05 2.83 2.39 2.53 2.62 p95 7.43 8.37 5.32 5.78 5.86 max 53.37 165.68 53.21 34.63 37.38

(b) Full training set – Gemini RW LLM H 50/50 H 30/70 H 10/90 2.16 1.67 1.70 1.77 1.87 3.52 2.44 2.39 2.54 2.78 8.09 6.97 5.25 5.49 5.97 74.20 374.63 62.55 77.08 53.20

(c) Reduced (30K) training set – GPT-4o Metric RW LLM H 50/50 H 30/70 H 10/90 median 4.51 2.97 4.59 4.39 5.57 p75 11.77 6.58 10.30 10.15 13.23 p95 64.05 33.99 38.84 35.74 53.17 max 1586.49 1085.30 1343.64 1341.02 857.68

(d) Reduced (30K) training set – Gemini RW LLM H 50/50 H 30/70 H 10/90 6.88 2.61 5.90 6.36 7.99 18.45 5.08 12.12 13.39 18.01 102.88 26.80 40.03 49.39 74.29 2716.19 3492.12 3207.92 2553.30 3166.27

distribution differently than random walks. By mixing these two, we take advantage of the tighter center of the LLM data and the bounded tail of the random walk data. Reduced training set (30K samples) For the reduced (30K) training set (Table 4(c),(d)), pure LLM is the clear winner on both test sets, with a median q-error 34–62% lower (47–74% for the 95th percentile) relative to RW. The advantage of the LLM-generated data thus grows as the training set size shrinks, indicating that LLM-generated queries are more data-efficient than uniformly sampled random walks. Interestingly, the same ranking holds whether the test queries are created by Gemini or by GPT-4o, even though only Gemini was used to generate the training data; the differences are larger on the Gemini test set, but remain significant on the independent GPT-4o set. Conclusively, an LLM can produce training samples whose distribution complements that of random walks. Combining the two yields the best results when the training set size is large. On the other hand, when training data is scarce, pure LLM data are more effective.

Conclusions

We study the problem of supervised similarity-aware cardinality estimation on KGs. We propose a novel approach that explores implicit and explicit means to incorporate similarities into the training process. Specifically, we presented SCE-KG, a model that employs a novel encoding scheme for cardinality estimation. Our experiments reveal that SCE-KG outperforms state-of-the-art approaches in terms of prediction error, while its online overhead accounts for less than 0.05% of the average query execution time and less than 1% of the average query planning time, showing a sub-millisecond latency in all cases. We further demonstrated that an LLM can be leveraged to generate training data resembling realistic user workloads, and that combining such samples with the random walk ones consistently improves estimation accuracy. Promising future directions include extending our approach to other query types (tree, cycle, clique, petal, and flower queries) and investigating unsupervised learning for similarity-aware cardinality estimation on knowledge graphs.

Acknowledgements This work was partially supported by the EU projects STELAR (101070122), WiseFood (101181895), and DataGEMS (101188416).

References [1] R. Angles, C. B. Aranda, A. Hogan, C. Rojas, and D. Vrgoč. WDBench: a wikidata graph query benchmark. In ISWC, pages 714–731, 2022. [2] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter, and D. Vrgoc. Foundations of modern query languages for graph databases. ACM Comput. Surv., 50(5):68:1–68:40, 2017. [3] R. Angles, H. Thakkar, and D. Tomaszuk. RDF and property graphs interoperability: Status and issues. AMW, 2369:1–11, 2019. [4] N. Bruno, S. Choudhury, and L. Gravano. STHoles: A Multidimensional Workload-Aware Histogram. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, pages 211–222, 2001. [5] W. Cai, M. Balazinska, and D. Suciu. Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, pages 18–35, 2019. [6] G. Chatzigeorgakidis, D. Skoutas, and A. Simitsis. Supervised Cardinality Estimation for Similarity Queries on Knowledge Graphs. In Proceedings of the 2026 IEEE International Conference on Semantic Computing (ICSC), ICSC ’26, pages 271–277, 2026. [7] L. Cherkasova, C. Gupta, A. Simitsis, J. Wang, and W. Wilkinson. Predicting execution times of concurrent queries, 2016. US Patent Application US20160203404A1, published July 14, 2016. [8] A. Davitkova, D. Gjurovski, and S. Michel. LMKG: learned models for cardinality estimation in knowledge graphs. In EDBT, pages 2:169–2:182, 2022. [9] A. Deshpande, M. Garofalakis, and R. Rastogi. Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, pages 199–210, 2001. [10] C. Estan and J. F. Naughton. End-biased Samples for Join Cardinality Estimation. In Proceedings of the 22nd International Conference on Data Engineering, ICDE ’06, page 20, 2006. [11] L. Getoor, B. Taskar, and D. Koller. Selectivity Estimation using Probabilistic Models. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, pages 461–472, 2001. [12] D. Gunopulos, G. Kollios, V. J. Tsotras, and C. Domeniconi. Selectivity estimators for multidimensional range queries over real attributes. VLDB J., 14(2), 2005. [13] Q. Guo, F. Zhuang, C. Qin, H. Zhu, X. Xie, H. Xiong, and Q. He. A survey on knowledge graph-based recommender systems. IEEE Trans. Knowl. Data Eng., 34(8):3549–3568, 2022. [14] Y. Guo, Z. Pan, and J. Heflin. LUBM: A benchmark for OWL knowledge base systems. Journal of Web Semantics, 3(2-3):158–182, 2005. [15] P. J. Haas, J. F. Naughton, S. Seshadri, and A. N. Swami. Selectivity and cost estimation for joins based on random sampling. J. Comput. Syst. Sci., 52(3), 1996.

[16] Y. Han, Z. Wu, P. Wu, R. Zhu, J. Yang, L. W. Tan, K. Zeng, G. Cong, Y. Qin, A. Pfadler, Z. Qian, J. Zhou, J. Li, and B. Cui. Cardinality estimation in DBMS: A comprehensive benchmark evaluation. Proc. VLDB Endow., 15(4):752–765, 2021. [17] R. Hayek and O. Shmueli. Improved cardinality estimation by learning queries containment rates. In EDBT, pages 157–168, 2020. [18] B. Hilprecht, A. Schmidt, M. Kulessa, A. Molina, K. Kersting, and C. Binnig. DeepDB: Learn from data, not from queries! PVLDB, 13(7):992–1005, 2020. [19] A. Hogan, E. Blomqvist, M. Cochez, C. d’Amato, G. de Melo, C. Gutierrez, S. Kirrane, J. E. L. Gayo, R. Navigli, S. Neumaier, A. N. Ngomo, A. Polleres, S. M. Rashid, A. Rula, L. Schmelzeisen, J. F. Sequeda, S. Staab, and A. Zimmermann. Knowledge graphs. ACM Comput. Surv., 54(4):71:1–71:37, 2022. [20] Joseph Sack. Optimizing your query plans with the SQL Server 2014 cardinality estimator, 2014. Available at: https://docs.microsoft.com/en-us/previous-versions/ dn673537(v=msdn.10)?redirectedfrom=MSDN. [21] K. Kim, J. Jung, I. Seo, W.-S. Han, K. Choi, and J. Chong. Learned cardinality estimation: An in-depth study. In Proceedings of the 2022 International Conference on Management of Data, pages 1214–1227, 2022. [22] V. Leis, B. Radke, A. Gubichev, A. Kemper, and T. Neumann. Cardinality Estimation Done Right: Index-Based Join Sampling. In Proceedings of the 8th Biennial Conference on Innovative Data Systems Research (CIDR 2017), CIDR ’17, pages 1–12, 2017. [23] V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. A. Boncz, A. Kemper, and T. Neumann. Query optimization through the looking glass, and what we found running the Join Order Benchmark. VLDB J., 27(5):643–668, 2018. [24] J. Leskovec and C. Faloutsos. Sampling from large graphs. In SIGKDD, pages 631–636, 2006. [25] V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T. M. Tran. Consistent selectivity estimation via maximum entropy. VLDB J., 16(1), 2007. [26] K. Möller, T. Heath, S. Handschuh, and J. Domingue. Recipes for semantic web dog food—the ESWC and ISWC metadata projects. In International Semantic Web Conference, pages 802–815. Springer, 2007. [27] M. Muralikrishna and D. J. DeWitt. Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. In Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, SIGMOD ’88, pages 28–36, 1988. [28] M. Müller, G. Moerkotte, and O. Kolb. Improved selectivity estimation by combining knowledge from sampling and synopses. PVLDB, 11(9), 2018. [29] P. Negi, R. C. Marcus, A. Kipf, H. Mao, N. Tatbul, T. Kraska, and M. Alizadeh. Flow-Loss: Learning cardinality estimates that matter. PVLDB, 14(11):2019–2032, 2021. [30] Neo4J. Introducing the new Cypher query optimizer, 2015. Available at: https://neo4j. com/blog/introducing-new-cypher-query-optimizer. [31] Nigel Bayliss. Improving cardinality estimates with dynamic statistics, 2021. Available at: https://blogs.oracle.com/optimizer/post/cardinality-and-dynamic-statistics.

[32] J. Ortiz, M. Balazinska, J. Gehrke, and S. S. Keerthi. Learning State Representations for Query Optimization with Deep Reinforcement Learning. In Proceedings of the Second Workshop on Data Management for End-to-End Machine Learning, DEML ’18, pages 1–4, 2018. [33] S. Pan, L. Luo, Y. Wang, C. Chen, J. Wang, and X. Wu. Unifying large language models and knowledge graphs: A roadmap. arXiv:2306.08302, 2023. [34] V. Poosala, V. Ganti, and Y. E. Ioannidis. Approximate query answering using histograms. IEEE Data Eng. Bull., 22(4), 1999. [35] C. Ré and D. Suciu. Understanding cardinality estimation using entropy maximization. ACM Trans. Database Syst., 37(1), 2012. [36] T. Sagi, M. Lissandrini, T. B. Pedersen, and K. Hose. A design space for RDF data representations. VLDB J., 31(2):347–373, 2022. [37] S. Sakr, A. Bonifati, H. Voigt, A. Iosup, K. Ammar, R. Angles, W. G. Aref, M. Arenas, M. Besta, P. A. Boncz, K. Daudjee, E. D. Valle, S. Dumbrava, O. Hartig, B. Haslhofer, T. Hegeman, J. Hidders, K. Hose, A. Iamnitchi, V. Kalavri, H. Kapp, W. Martens, M. T. Özsu, E. Peukert, S. Plantikow, M. Ragab, M. Ripeanu, S. Salihoglu, C. Schulz, P. Selmer, J. F. Sequeda, J. Shinavier, G. Szárnyas, R. Tommasini, A. Tumeo, A. Uta, A. L. Varbanescu, H. Wu, N. Yakovets, D. Yan, and E. Yoneki. The future is big graphs: a community view on graph processing systems. Commun. ACM, 64(9):62–71, 2021. [38] J. Sun, G. Li, and N. Tang. Learned cardinality estimation for similarity queries. In SIGMOD, pages 1745–1757, 2021. [39] D. Tsesmelis and A. Simitsis. Database optimizers in the era of learning. In IEEE ICDE, pages 3213–3216, 2022. [40] K. Tzoumas, A. Deshpande, and C. S. Jensen. Lightweight graphical models for selectivity estimation without independence assumptions. PVLDB, 4(11), 2011. [41] T. Vu, A. Belussi, S. Migliorini, and A. Eldawy. A learned query optimizer for spatial join. In SIGSPATIAL, pages 458–467, 2021. [42] X. Wang, C. Qu, W. Wu, J. Wang, and Q. Zhou. Are we ready for learned cardinality estimation? PVLDB, 14(9):1640–1654, 2021. [43] Y. Wang, C. Xiao, J. Qin, X. Cao, Y. Sun, W. Wang, and M. Onizuka. Monotonic cardinality estimation of similarity selection: A deep learning approach. In SIGMOD, pages 1197–1212, 2020. [44] L. Woltmann, C. Hartmann, M. Thiele, D. Habich, and W. Lehner. Cardinality Estimation with Local Deep Learning Models. In Proceedings of the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM ’19, pages 1–8, 2019. [45] P. Wu and G. Cong. A unified deep model of learning from both data and queries for cardinality estimation. In SIGMOD, pages 2009–2022, 2021. [46] Z. Yang, A. Kamsetty, S. Luan, E. Liang, Y. Duan, X. Chen, and I. Stoica. NeuroCard: One cardinality estimator for all tables. PVLDB, 14(1):61–73, 2020. [47] Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, P. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, and I. Stoica. Deep unsupervised cardinality estimation. PVLDB, 13(3), 2019. 21

[48] R. Zhu, Z. Wu, Y. Han, K. Zeng, A. Pfadler, Z. Qian, J. Zhou, and B. Cui. FLAT: fast, lightweight and accurate method for cardinality estimation. PVLDB, 14(9):1489–1502, 2021.

Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs

Analyze & explore related research in Conceptio

Related documents