Knowledge graphs (KGs) have become an undisputed source of semantic knowledge for various tasks, e.g., Question Answering (QA) or Entity Linking [1,2]. Hence, techniques that simplify access for end-users are in great demand. Keyword Search over Knowledge Graphs (KSKG) is a familiar method enabling information retrieval. KSKG systems generally attempt to answer a user query by retrieving graph connections between query keywords. In general, the output of interest of KSKG systems is a set of uniquely identified relevant entities. Recently, KSKG research resulted in a wide range of methods developed [3,4,5,6,7,8,9,10].
Benchmarks for effectiveness evaluation play a key role in enhancing systems and enabling inter-system comparison. They provide a target KG, user queries, and corresponding results together with their relevance judgments (RJs), e.g., using binary 1 or 3-point scales. Queries are often either manually crafted [11] or manually selected from search engine query logs [12], which results in small datasets. Relevant results are generally provided by pooling a subset Wikidata'23: Wikidata workshop at ISWC 2023 leila.feddoul@uni-jena.de (L. Feddoul); frank.loeffler@uni-jena.de (F. Löffler); sirko.schindler@dlr.de (S. Schindler) 0000-0001-8896-8208 (L. Feddoul); 0000-0001-6643-6323 (F. Löffler); 0000-0002-0964-4457 (S. Schindler) of system's top results and judged via crowd-sourcing [13,11,14]. This approach is timeconsuming and depends on systems' results. To the best of our knowledge, there is only one dataset specifically for KSKG [15]. Its focus was not on creating queries, but on mapping relevant results from previous evaluation campaigns to DBpedia [16] entities.
In this paper, we present KeySearchWiki, an automatically generated dataset for keyword search over Wikidata [17]. We focus on Type Search (TS) [18] with queries retrieving entities of a specific type (target), e.g., Paul Auster novels with novels as a target. This relates to common real-world scenarios: (1) users explicitly mentioning the target in traditional search engines, (2) users selecting a target category, e.g., books in an online shop, or (3) search systems providing access to only a single type of results, e.g., portals offering access to datasets. To the best of our knowledge, this is the first automatically generated, large-scale, and diverse dataset that also includes complex queries. The general idea is to leverage Wikipedia set categories 2 that are mapped to Wikidata (e.g., Category:American television directors (Q8032156)) as a source of queries and their members as relevant entities. KeySearchWiki is more closely related to humancurated datasets than purely synthetic ones. The queries represent an actual information need as witnessed by the manually maintained, corresponding Wikipedia categories. Furthermore, Our approach is both multilingual (all Wikipedia languages are considered) and hierarchical (exploiting the Wikipedia category hierarchy). We summarize the key contributions as follows:
• We present a workflow for the automatic generation of the KeySearchWiki dataset. The source code for the dataset generation is publicly available. • We introduce KeySearchWiki, a diverse dataset consisting of 16, 605 queries of different complexity levels together with their relevant entities. • We provide for each query an annotated version that tags each query term with its corresponding Wikidata identifier. Mappings between natural language queries and corresponding Wikidata entities can, e.g., be used to evaluate entity linking systems.
In addition to challenges, several datasets have been created to support the evaluation of KSKG approaches and related topics such as QA. Table 1 summarizes major existing datasets/challenges. They vary with respect to the task, the target data and its format, size, query creation method, source of relevant entities, RJs types, and RJs source. We distinguish between four types of tasks:
• Entity Search (ES) [18]: finding a specific entity, e.g., University of Phoenix in SemSearch Challenge 2010's Entity Search Track (SemSearch2010 ES). • Type Search (TS) [18]: finding a (ranked) list of entities having a specific type, e.g., Paul
Auster novels from the Entity Ranking Task of The INitiative for the Evaluation of XML retrieval (INEX2009 ER). • Ad-Hoc Search (AHS): finding a (ranked) list of entities that are described with a set of random keywords (could include ES and TS style queries but also other random ones), ES, TS, and AHS are directly related to KSKG. We include datasets for QA over KGs, as they share characteristics with KSKG datasets and have been adapted to evaluate KSKG systems (e.g., in [3]). KSKG systems require a target KG represented as triples. Most of the described datasets (cf. Table 1) provide underlying data in RDF format. INEX campaigns usually focus on XML retrieval, but organized a Linked Data (LD) Track to close the gap with the Semantic Web. The target data provided by INEX2012 LD was in a semantically annotated XML format: Wikipedia-LOD v1.13 using DBpedia and YAGO [23] annotations. In INEX2013 LD different dataset collections allowed for various retrieval techniques: XML + RDF (English Wikipedia + DBpedia and YAGO), semantically annotated XML (Wikipedia-LOD v2.04 ), and text (extracted from Wikipedia-LOD v2.0). However, INEX LD tracks mainly target textual data, while KSKG systems work on data represented by KGs.
Queries are often either manually crafted by humans [11] or collected from previous campaigns where source queries were also manually created [15]. The manual approach is timeconsuming and requires effort not only for query creation but also for finding interested volunteers. This impacts the size of the dataset, since it results in a small number of queries, usually fifty 5 to one hundred queries per dataset. Furthermore, if the dataset is created in the context of a project that also aims at developing a KSKG system, manual query creation increases the risk of designing biased queries that favor ones own approach, especially if this is done by researchers directly related to the project. Other works select queries manually from search engine query logs [12]. They argue that log queries are more realistic and representative to user needs. However, users often try to overcome the limitations of a search engine by adapting to its capabilities and by avoiding complex queries that involve relations between different entities [24]. On the other hand, query logs are often not in-line with the specified underlying data (e.g., KGs). This shortcoming requires additional efforts for selecting queries to have at least some answers within the considered data. Datasets should also contain queries with unambiguous intentions. This is important for judging whether a potential entity is relevant to the query or not. Thus, another step is the selection of queries whose intentions could be derived. LC-QuAD 2.0 [22] is, to the best of our knowledge, the only dataset that applies a semi-automatic approach for query creation and thus has the largest size (30, 000 queries). SPARQL queries are automatically generated, transformed to template questions, and finally verbalized into natural language questions. However, QA datasets are not initially geared towards KSKG tasks. Hence, their usage requires pre-processing and selection of suitable queries. Another approach to evaluate KSKG systems is the use of randomly generated queries (arbitrary combinations of keywords appearing in the data source). This is generally not a good practice, since resulting queries would not reflect real information needs [25].
All challenges (besides QA) use runs 6 submitted by participants as source of relevant entities. They pool a subset of top results and assess them either via crowd-sourcing (e.g., MTurk7 ) or by the participants themselves [19]. This depends on the participating systems, though, and provides no independent list of relevant entities. QA datasets use either automatically or manually created SPARQL queries to generate the list of relevant entities. Here, results do not need to be judged, and only relevant entities are presented. However, we believe that relevant entities could originate from different SPARQL queries depending on the underlying KG. Using a single SPARQL query may omit some potentially relevant entities. KSKG datasets should also contain complex queries. We distinguish between two degrees of complexity. Multi-keyword: queries that contain more than one keyword, and multi-hop (for TS): there is no direct relation between target and keywords 8 . Most of the listed datasets contain multi-keyword queries. However, none of them explicitly claims to provide multi-hop queries. For QA datasets this could be verified since SPARQL queries are provided.
All datasets provide queries as mere strings. Systems thus have to deal with keyword/target to knowledge graph entity mapping. Providing semantically annotated queries is also useful and allows for using the queries also to evaluate entity linking systems. Another significant quality for such datasets is diversity, which means avoiding similar queries (e.g., cities in Germany and cities in France). It is difficult to programmatically verify the diversity of a dataset, so researches have to rely on the claims made by its creators (e.g., LC-QuAD [26] claims to avoid generating similar queries). Methods for constructing synthetic benchmarks are proposed in [27,28]. They follow exactly the steps that a KSKG/QA system would perform to solve the task. In our view, this self-reference (evaluating one system with the output of another) defeats the idea of an objective evaluation and is not based on human judgment.
We conclude that there is a lack of established evaluation datasets dedicated to KSKG. We overcome the previously described shortcomings by proposing the first (1) automatically generated, (2) complex, (3) large-scale, (4) diverse dataset to evaluate KSKG systems on the TS Task over Wikidata, and providing semantically annotated queries. We propose an innovative approach by using Wikidata/Wikipedia set categories, existing human-edited sources of relevant entities and TS queries. We leverage the multilingual and hierarchical nature of Wikipedia set category pages to improve the completeness of relevant entities. Our automated approach does not mirror the steps of KSKG systems, but automatically extracts and combines information from manually curated resources to reduce the additional manual effort. Consequently, we consider KeySearchWiki more closely related to human-curated datasets than purely synthetic ones.
KeySearchWiki specifically focuses on the TS Task. Our primary goal is to lower manual effort and propose a fully automated workflow for dataset generation. A further goal is the creation of complex and diverse queries. We notice that Wikidata set categories exhibit TS-like characteristics (cf. Figure 1). Most set categories have a property category contains (P4224) providing the type (target) of entities contained and additional qualifiers (keywords). This provides the building blocks to construct TS-like queries. Links to corresponding Wikipedia pages can provide relevant entities, as they represent human-curated collections of Wikipedia articles (Wikidata entities) for these categories. Figure 2 depicts the dataset generation workflow whose details will be described in the following.
The pipeline starts by generating candidate entries (queries and their relevant entities). Set categories are retrieved from Wikidata in one of two ways: (1) sending SPARQL queries to the Wikidata public endpoint9 or (2) parsing a Wikidata JSON dump 10 . Both options retrieve set categories with additional information such as category contains (P4224) and its qualifiers used to determine target and keywords respectively. Next, for each available language, the Wikipedia subcategory hierarchy is explored in a Breadth-First-Search-manner to retrieve member pages and their corresponding Wikidata entities. Again, these may be retrieved online using the MediaWiki API 11 or offline from a local database built from SQL Dumps for all needed languages 12 . For each subcategory, we perform a type check: if fewer than 50% of its members are instances of the target or any of its subclasses 13 , traversal in this branch will be stopped. The output of this phase is a list of raw entries. In a cleaning phase, we then remove entries without target or keywords, with more than one keyword/target (ambiguous), without relevant entities, or with a keyword having either an unknown value or no label. The resulting intermediate entries act as input for the two following branches.
This phase contains a single operation, Intermediate Entry Filtering. We define two criteria: (1) number of relevant entities (#RE) of intermediate entries and (2) number of keywords/target (#Concepts) of corresponding queries 14 . We keep entries whose #RE is at least equal to two, since TS aims at retrieving a list of entities that could be ranked afterwards. Furthermore, we only keep queries having #Concepts below 7. The rationale is to reflect real-world user behavior, where generally a small number of keywords is used [29,30].
At this stage, two types of complex queries are constructed: multi-keyword and multi-hop queries 15 .
Multi-keyword. The process for multi-keyword entries generation is illustrated in Figure 3 based on an example iteration from the actual generation pipeline. The pipeline takes the intermediate entries as input. For the sake of simplicity, consider having three intermediate entries. Each entry corresponds to a set category given by a Wikidata IRI (e.g., Category:Computer programmers (Q6624060)) and contains a query and a set of relevant entities. Similarly, relevant entities are represented by Wikidata IRIs. For convenience, we use simple identifiers in the illustration (e.g., entry1, iri1). Each query is given by a target and a set of keywords (e.g., query1: "Programmer" "human" corresponds to instances of human that are described by the keyword Programmer). Multi-keyword queries combine a number of queries that have the same target to create a new query (e.g., query1 and query2 result in a new query "programmer" "University of Houston" "human"). To detect possible combinations, a RelevantEntities-Entry Inverted Index is created in step 1 ○. This index aggregates entries that share at least one relevant entity. Separate indices are created for each target to group only compatible queries. From those indices, we select elements containing at least two different entries as Possible Entry Combinations in step 2 ○. The New Entry Construction step 3 ○ involves the creation of new queries and the new relevant entity sets. New queries are created by merging the keywords and maintaining the shared target: "programmer" "University of Houston" "human". The new relevant entity set is the intersection of relevant entities of the involved entries: (iri1, iri2). Multi-keyword entries are then filtered in step 4 ○ based on the criteria defined in Subsection 3.2. Multi-hop. The steps for multi-hop entry generation are explained in Figure 4, also using a real iteration. The pipeline takes the intermediate entries as input. We consider four intermediate entries as example and use simple identifiers for the sake of convenience (e.g., entry1, CH (first two letters of entity label), or iri1). The algorithm traverses all intermediate entries by applying steps 1 ○ to 4 ○. We consider one iteration (entry1). Multi-hop queries (2 hops for now) link two entries where a relevant entity of one query is equal to a keyword of another query. For example, from query1 "World Music Awards" "human" and query2 "EL" "album", we can derive a new query "World Music Awards" "album". In contrast to query1 and query2, in the new query there is no direct relation between target and keywords, i.e., album and World Music Awards. A system needs to use another intermediate entity (e.g., EL, an artist that won a World Music Awards) to connect keyword(s) and target. The Transitive Entry Linking 1 ○ links Relevant Entities of the Current Entry (CERE) to other entries using one of those relevant entities as keyword. Then an Entry Clustering 2 ○ groups linked entities by target and keywords different from the CERE. With this, new entries can be constructed. The new multi-hop query is built in step 3 ○ by merging cluster keys (album) and current entry keywords (World Music Awards, album). 15 Based on Figure 1, native queries could be seen as 1-hop queries since they include keywords that are directly related to the target (e.g., entities of type human (Q5) directly related to television director (Q2059704) via the property occupation (P106)). Clusters with the same target as the current entry are removed since they generate the same query (if the cluster has no keywords), or multi-keyword queries. Relevant entities of the new entry are derived from the union of relevant entities in the corresponding cluster. For example, "World Music Awards" "albums" are albums from all human artists that won the World Music Awards (here, CH, MI and EL). Applying the same algorithm recursively, yields queries of more than two hops. For now, we limit the number of hops to two, though. The last step is Filtering 4 ○ using the criteria of Subsection 3.2 (#RE and #Concepts) as well as coverage. We define the coverage as 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 𝑠𝑖𝑧𝑒 𝐶𝐸𝑅𝐸 𝑠𝑖𝑧𝑒 , where 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 𝑠𝑖𝑧𝑒 is the number of entries in the respective cluster and 𝐶𝐸𝑅𝐸 𝑠𝑖𝑧𝑒 is the number of relevant entities of the current entry. This metric represents the completeness of the relevant entity set with regard to the new query. In the example of Figure 4, the coverage of the new query is 0.66 ∼ 2 3 (in the actual dataset, the query World Music Awards album has 𝑐𝑜𝑣𝑒𝑟𝑎𝑔𝑒 = 0.44 with 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 𝑠𝑖𝑧𝑒 = 109 and 𝐶𝐸𝑅𝐸 𝑠𝑖𝑧𝑒 = 250). A coverage of 1 is not reached here as no linking with relevant entity MI was found, i.e., the entry MI album does not exist among the input entries. In general, this indicates a missing set category for this combination. We empirically derived a minimum coverage requirement of 0.1 after analyzing the distribution for all multi-hop queries.
This step aims to ensure the diversity of generated entries. From sets of structurally highly similar queries, one representative is chosen while others are discarded (e.g., "California State University, Fullerton" "human" is semantically highly similar to "University of Houston" "human"). We define the query signature as: <Target> <Keyword-Types> (e.g., signature of "University of Houston" "human" is <human (Q5)> <university (Q3918), public educational institution of US (Q23002039)>). The three types of entries are merged (native/multi-keyword/multi-hop) and grouped by their signature. From each group, one representative of each entry type is selected.
For native/multi-keyword entries, a pseudo-random 16 selection is performed, whereas from multi-hop entries, the one with the highest coverage is selected.
The current dataset version is generated using Wikidata JSON dump and Wikipedia SQL dumps of 2021-09-20 17 . The final KeySearchWiki dataset consists of 16, 605 final entries (native: 1, 138, multi-keyword: 15, 354, multi-hop: 113) with 3, 899, 135 unique relevant entities. It involves 73 different targets, 2, 797 unique keywords, and 739 different keyword types. Human (Q5) is the most frequent target (13, 260), followed by album (Q482994) (1, 815), video game (Q7889) (757), and song (Q7366) (303). Other insights about the dataset are documented on GitHub 18 .
The source code for KeySearchWiki is publicly available [31,32] under an MIT License, including a description of the dataset, its usage and characteristics, examples, and steps needed to reproduce it. We publish our data on Zenodo [33] under a CC-BY 4.0 License to ensure persistent and public access to all resources. The current dataset is provided in both TREC 19and JSON formats. The TREC format represents relevant entities and their RJs as follows 20 : <queryID> 0 <RelevantEntityIRI> <judgment>. Queries are in a separate text file, following the format in DBpedia-Entity v2 [15]: <queryID> <query>. We provide two types of query files: one where queries are given by labels (e.g., <MK79540> <programmer University of Houston human> and a second with entity IRIs (e.g., <MK79540> <Q5482740 Q1472358 Q5>). The latter can be directly used by systems that omit a preceding entity linking step. We also provide an additional list of queries that was partially adjusted (naturalized) to better reflect natural language query formulation. For example, by transforming the query diplomat Germany 20th century human into diplomat Germany 20th century. This is done by removing the target from the query if one of its keywords is a descendant of the target via subclass of (P279). In the previous example, diplomat is in the subclass hierarchy of human. Following this process, 1, 826 queries were adjusted and the whole list was provided using the same format: <queryID> <query>. The provided data contains:
• KeySearchWiki-JSON -the final dataset in JSON format.
• KeySearchWiki-queries-label -a text file containing the 16, 605 queries, each line containing space-separated queryID and query text (labels). • KeySearchWiki-queries-iri -a text file containing the 16, 605 queries, each line containing space-separated queryID and IRIs of query elements. • KeySearchWiki-queries-naturalized -a text file with all 16, 605 queries, including 1, 826 adjusted queries, each line containing space-separated queryID and query text (labels). • KeySearchWiki-qrels-trec -a text file containing relevant entities in TREC format.
• KeySearchWiki-cache [34] -a collection of SQLite database files containing all the data retrieved from Wikidata JSON Dump and Wikipedia SQL Dumps of 2021-09-20.
Users can update KeySearchWiki anytime by running our code on a new dump of Wikidata and Wikipedia. We plan to periodically publish new dataset releases.
We use KeySearchWiki to evaluate Elas4RDF [35], a system based on indexing the textual information of entities. Elas4RDF relies on a triple-based indexing using Elasticsearch 21 . We use the best-performing approach where each triple is represented by a document with the following fields: subject/predicate/object keywords 22 , description of IRI object/subject, and label of IRI object/subject. Object fields are given higher weight. We use the Elas4RDF-index Service 23 to create an index of Wikidata entity triples. We perform our experiments on a subset of queries. Considering all dataset queries would imply indexing triples involving all Wikidata entities. We avoid that to keep the indexing time reasonable by selecting queries with one of the top-10 targets and thus index triples involving Wikidata entities that are either instances of the target itself or any of its subclasses. This way we keep 99% (only 112 queries discarded) of the queries from all the types (native: 1, 037, multi-keyword: 15, 343, multi-hop: 113). 146, 211, 253 triples were indexed with an index size of 16.8 GB. We evaluate four ranking methods provided by Elasticsearch with default settings as in [35]: BM25 [36], DFR [37], LM Dirichlet [38], and LM Jelinek-Mercer [38]. For each baseline (run), the Elas4RDF-search Service 24 is used to retrieve the results which are then written in TREC format: <queryID> Q0 <RetrievedEntityIRI> <rank> <score> <runID>. The second column is unused and should always be "Q0". Table 2 summarizes the experiment results. We use Mean Average Precision (MAP) and Precision at rank 10 (P@10) (considering the top-1000 results). We notice that the different query types reflect various degrees of difficulty. This corresponds to our intention of adding complex queries. Native queries are less challenging and thus achieve better results across retrieval methods. These queries usually involve keywords that are directly related and hence their textual information is mostly occurring within the triples of the same entity. Complex queries are more difficult and show poor performance in general. Even though multi-keyword queries still involve directly related keywords, they tend to be longer and thus seem more challenging. Here, the performance has dropped by ∼ 0.18 points for both MAP and P@10 compared to native queries. Multi-hop queries are more difficult than their multi-keyword counterparts as they involve keywords not directly related and thus their textual information does not occur within triples of the same entity. This lowers the performance by ∼ 0.19 points compared to native queries and by ∼ 0.01 points compared to the multi-keyword ones. The results reveal no noticeable difference between the different retrieval methods. We only notice an improvement between ∼ 0.01 − 0.05 points of the P@10 using BM25 for native queries. A more detailed investigation is out of the scope for this paper. Overall, the performance of the ranking methods over KeySearchWiki is in line with other published results (e.g., in [15] and [39]). Further details about experiment data preparation, indexing, and the experimental setup are provided in the dataset's GitHub repository [31]. Runs, experiment results, queries, and relevance judgments are published on Zenodo [40].
Evaluation. We evaluate the accuracy of relevant entities in KeySearchWiki by using existing SPARQL queries as a baseline and comparing KeySeachWiki's relevant entities with the results of these queries. Evaluation scripts and results are available on GitHub. Some Wikidata set categories have associated SPARQL queries using the property Wikidata SPARQL query equivalent (P3921). These queries retrieve results corresponding to the set category and are handcrafted by humans. They can be considered as another source of relevant entities (baseline) that can be used for comparison and verification of the relevant entities provided by KeySearchWiki. We extract native entries that contain such SPARQL queries (67 native entries) and manually verify whether the corresponding SPARQL queries correctly represent the information need expressed by the set category. One query was excluded which results in 66 queries used in this evaluation. For the selected queries, we calculate the . Results reveal that KeySearchWiki is capable of catching most of the relevant entities retrieved by SPARQL resulting in an Average Recall of ∼ 0.70 and an Average Precision of ∼ 0.54. A more detailed analysis of the results is provided in GitHub25 .
In the following we describe the limitations of KeySearchWiki.
Matching between data sources and the target KG. In general, even though each Wikipedia page has its corresponding Wikidata entity, the two sources do not always match with respect to the knowledge contained. This is due to the fact that both are mostly independently maintained by volunteers. Despite the overlap and collaboration between both communities, the information in both projects will probably continue to differ in the foreseeable future. Other benchmarks also suffer from this -especially those that collect queries independently from the actual KG (e.g., from logs). We attempt to mitigate the effects by using closely related sources (Wikipedia and Wikidata) for queries and relevant entities.
Completeness of relevant results. Depending on the approach, completeness is rather hard to achieve for benchmarks of reasonable size. Human relevance judgments may be feasible for smaller datasets, but fail for larger ones that are built using pooling [42]. We try to increase the completeness by considering all Wikipedia languages and traversing its hierarchy. Furthermore, KeySearchWiki uses Wikipedia as relevant entity source to include also Wikidata entities with missing semantic description.
Evaluation of approaches exploiting Wikipedia categories. Systems following KeySearch-Wiki's strategy of exploiting Wikipedia categories may achieve close to perfect scores. However, the task of KSKG assumes only two inputs: a query and a target KG. Additional sources alter this task and result in systems heavily depending on a particular KG. In such scenarios (system using Wikipedia categories), the dataset should not be used to avoid any bias.
We introduced KeySearchWiki -a fully automatically generated, complex, large-scale, and diverse dataset for evaluating keyword search systems over Wikidata. We leverage Wikidata and Wikipedia set categories as data sources for both relevant entities and queries. We gather relevant entities by carefully navigating the Wikipedia set categories hierarchy in all available languages. In the future, we plan to extend the dataset by also generalizing to Wikimedia categories (Q4167836) that are superclasses of the currently used set categories. This will allow us to increase the number of dataset entries and to also generate more high-coverage multi-hop entries.
This work has been funded by the German Aerospace Center (DLR). We thank Prof. Dr. Birgitta König-Ries for guidance and feedback.