--- title: "Keyword-Based Knowledge Graph Exploration Based on Quadratic Group Steiner Trees" authors: - "Yuxuan Shi" - "Gong Cheng" - "Trung-Kien Tran" - "Jie Tang" - "Evgeny Kharlamov" doi: "10.24963/ijcai.2021/215" url: "https://ijcai.org/proceedings/2021/215" pdf: "https://ijcai.org/proceedings/2021/0215.pdf" venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence" year: 2021 pages: "1555-1562" track: "Main Track" keywords: - "Data Mining: Mining Graphs, Semi Structured Data, Complex Data" - "Knowledge Representation and Reasoning: Semantic Web" - "Data Mining: Information Retrieval" --- # Keyword-Based Knowledge Graph Exploration Based on Quadratic Group Steiner Trees Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Jie Tang, Evgeny Kharlamov *Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1555-1562. DOI: [10.24963/ijcai.2021/215](https://doi.org/10.24963/ijcai.2021/215) ## Abstract Exploring complex structured knowledge graphs (KGs) is challenging for non-experts as it requires knowledge of query languages and the underlying structure of the KGs. Keyword-based exploration is a convenient paradigm, and computing a group Steiner tree (GST) as an answer is a popular implementation. Recent studies suggested improving the cohesiveness of an answer where entities have small semantic distances from each other. However, how to efficiently compute such an answer is open. In this paper, to model cohesiveness in a generalized way, the quadratic group Steiner tree problem (QGSTP) is formulated where the cost function extends GST with quadratic terms representing semantic distances. For QGSTP we design a branch-and-bound best-first (B3F) algorithm where we exploit combinatorial methods to estimate lower bounds for costs. This exact algorithm shows practical performance on medium-sized KGs. ## Full text ## 1 Introduction A knowledge graph (KG) is a collection of annotated and interconnected entities. By offering a flexible way to structure and integrate information, KGs have been widely used in AI applications. Consider a sample KG in Fig. 1 which describes various relations between physicists, institutions, and cities. Task. When a user such as a data journalist looks into a machine-readable KG, a fundamental task is KG exploration. Users often explore a complex structured KG with difficulty. For those who lack expertise in formulating formal queries or whose vague information needs can hardly be formalized, machine-assisted KG exploration is crucial [Lissandrini et al., 2020]. While various AI-empowered methods have been devised to support this task, such as KG summarization [Cheng et al., 2016; Cheng et al., 2017a] and relevance-based entity recommendation [Gu et al., 2019; Zhou et al., 2020], the most commonly adopted user interface is based on keyword queries: a user explores a KG by easily submitting a set of keywords expressing an information need. State-of-the-art methods [Shi et al., 2020] efficiently find and present an optimum subgraph extracted from the KG that contains all the keywords in the query. For example, Fig. 1 shows two extracted subgraphs T1 and T2 for answering the query "melvin schwartz, emil wolf". An optimum subgraph will be computed and returned as an answer. ∗Contact Author Figure 1: An example KG and two extracted subgraphs: a semantically cohesive subgraph T1 and a semantically incohesive subgraph T2 for answering the query "melvin schwartz, emil wolf". ![Image](https://ijcai.org/proceedings/2021/fulltext/215/image_000000_4ad65921c5e455baa3c1d0abb752f043a7d8244a2d94107c26447805e4ae63de.png) Motivation. In the literature it was standard to assign weights to vertices or edges in a KG and then compute a minimum-weight connected subgraph that contains all the keywords in a query as an optimum answer [Ding et al., 2007; Li et al., 2016; Shi et al., 2020], aka a group Steiner tree (GST) [Ihler, 1991]. The underlying assumption is: an aggregation of salient graph elements (i.e., with small weights) constitute a good answer. However, the assumption has recently been challenged: by analyzing industrial KGs, it was suggested to improve the cohesiveness of an answer where entities (i.e., vertices) have small semantic distances from each other [Cheng and Kharlamov, 2017], e.g., having similar types, textual annotations, or topics. The suggestion has been supported by empirical studies focusing on different concrete measures of semantic distance [Cheng et al., 2017b; Bryson et al., 2020]. As an example, T2 in Fig. 1 is an uninteresting mixture of disparate entities despite their salience, while T1 cohesively and meaningfully describes physicists and their advisors. Although the effectiveness of such cohesive answers in KG exploration has been accepted, one problem remains: how to efficiently compute a cohesive answer. This is our research target in this paper. Quadratic GST problem. The standard GST problem minimizes the total weight of the vertices or edges in a subgraph. This cost function cannot model implicit relationships between graph elements such as semantic distances. Recently we have extended it to calculate the total weight of graph elements and their semantic distances [Shi et al., 2021]. This extended optimization problem is referred to as the quadratic group Steiner tree problem (QGSTP) since semantic distance is a quadratic term involving two graph elements. QGSTP is fundamentally more difficult than the GST problem. Indeed, quadratic terms are harder to optimize. Moreover, weights and semantic distances require joint optimization while their values could be independent from each other. AlgorithmB3F. To solve QGSTP, we design an exact algorithm named B3F that guarantees to find an optimum solution. B3F is an iterative branch-and-bound algorithm and it performs best-first search in each iteration. We define a branch of the search space as a set of subgraphs that subsume a common path. We leverage the path to develop a lower bound estimation for the costs of the subgraphs in the branch, where we manipulate and integrate combinatorial methods including set covering and maximum matching. Contributions. Belowwe summarize our contributions. - We design the first exact algorithm B3F for QGSTP. We significantly prune the search space of B3F by devising an effective lower bound estimation for costs. - We conduct extensive experiments on public KGs and queries. B3F computes more cohesive answers than the classical GST and it runs in comparable time. ## 2 RelatedWork ## 2.1 GST-Based Exploration Keyword-based KG exploration has been commonly formulated as a GST problem to extract a minimum-weight tree that contains all the keywords in a query [Ding et al., 2007; Li et al., 2016; Shi et al., 2020], or as a variant of this problem [Kargar and An, 2011; Le et al., 2014; Yang et al., 2019]. They assume that aggregating salient graph elements with small weights produces a good answer, but they ignore the semantic relationships between elements. Indeed, a set of salient elements may not form a semantically cohesive subgraph and hence not a meaningful answer. Our work extends this line of research by incorporating semantic distances between elements and formulating QGSTP to compute cohesive answers. Our cost function contains quadratic terms that are harder to optimize. ## 2.2 Cohesiveness Computation The above shortcoming of GST-based exploration has been noticed when researchers processed industrial KGs and they suggested computing cohesive answers [Cheng and Kharlamov, 2017]. The suggestion is supported by a user study where a concrete measure of semantic distance was implemented based on entity types [Cheng et al., 2017b]. By comparing pairs of answers, users preferred more cohesive answers where entities have similar types. Another implemented measure of semantic distance relies on random walk with restart [Bryson et al., 2020], to which a specific heuristic algorithm was presented to compute such cohesive answers. Our work addresses efficient computation of cohesive answers, which is not considered in [Cheng and Kharlamov, 2017; Cheng et al., 2017b]. Our algorithm computes an optimum solution to QGSTP while the algorithms in [Bryson et al., 2020; Shi et al., 2021] cannot guarantee to find an optimum solution. Regarding other studies of "cohesiveness" in graph search and exploration [Dass et al., 2015; Zhu et al., 2018], their definitions are orthogonal to ours. ## 2.3 Query Interpretation To interpret a keyword query (or a natural language question) for KG exploration, one popular approach is to transform the keyword query into a formal query and then execute the formal query over a standard query engine [Tran et al., 2009; Pound et al., 2012; Shekarpour et al., 2013; Sun et al., 2020]. The formal query is typically a graph pattern that formally represents the meaning of the keyword query and is matched with the KG to retrieve answers. Our work is suitable for vague information needs that can hardly be interpreted as a precise graph pattern, e.g., exploring relationships between a set of entities [Cheng, 2020; Li et al., 2020; Cheng et al., 2020]. The above transformationbased methods are targeted at information lookup where there is a specific query intent that can be represented by a graph pattern. The two lines of research are complementary. ## 3 Problem ## 3.1 Preliminaries A KG is a directed graph denoted by G = 〈V, E〉, where V is a set of vertices representing entities, and E ⊆ V ×V is a set of directed edges representing relations between entities. We allow the edges in a path/tree to be in different directions. Let K be the set of all keywords. A matching function hits : K ↦→ 2V maps each keyword to a subset of vertices. The concrete implementation of hits, e.g., either syntactically or semantically matching keywords with vertex annotations, is not our focus. For simplicity our formulation omits edge mapping but it can be transformed into vertex mapping: for each edge (u, v) we create a vertex w with the annotation of (u, v); then replace (u, v) by two edges (u, w) and (w, v). A query Q ⊆ K is a set of g keywords Q = {k1, . . . , kg}. To ease the notation we write hits(ki) as Ki for 1 ≤ i ≤ g. We call Ki keyword vertices. Similar to the GST problem [Ihler, 1991], given G = 〈V,E〉 we define a feasible answer to Q as a subgraph of G denoted by T = 〈VT ,ET 〉 such that: (1) T is connected, (2) T contains at least one keyword vertex from each Ki for 1 ≤ i ≤ g, and (3) T is structurally minimal for (1) and (2), i.e., none of its proper subgraphs satisfy both (1) and (2), so T is a tree where leaf vertices must be keyword vertices. For example, T1 and T2 in Fig. 1 are two feasible answers to the query "melvin schwartz, emil wolf". ## 3.2 ProblemFormulation Let wt(v) be the non-negative weight of vertex v; small wt represents salience. Let sd(vi, vj) be the non-negative semantic distance between vertices vi and vj; small sd represents cohesiveness. The concrete computation of wt and sd is independent from our approach. The cost of a feasible answer T = 〈VT , ET 〉 is the total weight of its vertices and their semantic distances: where α ∈ [0, 1] is a parameter. An optimum answer is a feasible answer that minimizes cost. This optimization problem is referred to as the quadratic group Steiner tree problem (QGSTP) [Shi et al., 2021]. It extends the cost function of the vertex-weighted GST problem [Ihler, 1991; Klein and Ravi, 1995] by introducing a quadratic term sd(vi, vj) representing an extra cost that will be paid if two vertices vi and vj are both included in T . ## 3.3 ProblemComplexity Theorem 1. QGSTP is an NP-hard optimization problem. Proof. We can reduce two NP-hard problems to QGSTP. It is straightforward to reduce the vertex-weighted Steiner tree problem to an instance of QGSTP where α = 1 and |Ki| = 1 for 1 ≤ i ≤ g. Alternatively, we reduce the quadratic set cover problem to an instance of QGSTP where α = 1 - α and vertices in G are pairwise adjacent. Thus, sets containing an element correspond to vertices mapped to from a keyword. Compared with the vertex-weighted GST problem, QGSTP is more difficult due to the extended optimization of the quadratic sd which is independent from wt. For example, vertices that are adjacent in KGs can be semantically distant. ## 4 Approach QGSTP is an NP-hard optimization problem, for which a brute-force algorithm would be computationally prohibitive even on small KGs. We present a Branch-and-Bound BestFirst algorithm, abbreviated to B3F. It is the first exact algorithm for QGSTP. As we will see in the experiments it shows promising performance on medium-sized KGs. Before presenting B3F, we define some terms. For path p, its length len(p) is the number of edges in p. The distance between two vertices is the length of a shortest path connecting them. The eccentricity of vertex v is the greatest distance between v and other vertices. The radius and diameter of graph T , denoted by rad(T ) and diam(T ), are the minimum and maximum eccentricity of the vertices in T, respectively. A central vertex is a vertex of minimum eccentricity. For two graphs T and T ′ , we write T ⪯ T ′ if T is a subgraph of T ′ . ## 4.1 Basic Idea In general, B3F iteratively explores the search space in a topdown manner (i.e., branching). Branches where feasible answers cannot be better than the optimal answer found so far are discarded (i.e., bounding). In each iteration, the most promising branch is explored (i.e., best-first). ## Algorithm 1 B3F Input: G = 〈V, E〉, Q = {k1, . . . , kg}, integer d ``` Output: Topt 1: Topt ←null; /*We define cost(null) =∞. */ 2: PQ ← an empty min-priority queue of paths; 3: for all v ∈ g⋃ i=1 Ki do 4: PQ.insert(v); 5: for i = 1 to g do 6: Pi ←an empty set of paths; 7: while PQ is not empty do 8: ptop ←PQ.pull(); 9: if cost(ptop) ≥ cost(Topt) then 10: break the while loop; 11: for all ki ∈ QK(Vptop ) do 12: Pi ←Pi ∪ {ptop}; 13: for all 〈p1, . . . , pg〉 ∈ P1 × · · · × Pg containing ptop and having a common end vertex do 14: T ←merge p1, . . . , pg; 15: if T is structurally minimal then 16: if cost(T ) < cost(Topt) then 17: Topt ← T ; 18: if len(ptop) < d then 19: for all v ∈ V that is adjacent from/to the end vertex of ptop and is outside ptop do 20: p ← grow ptop to v with one edge; 21: P Q.insert(p); 22: return Topt ``` Answer construction. B3F constructs a feasible answer by merging g paths p1, . . . , pg where each pi starts from a keyword vertex in Ki and they end at a common vertex. For example, T1 in Fig. 1 is constructed by merging two paths: ``` M. Schwartz doctoral advisor -------→ J. Steinberger academic advisor --------→ E. Fermi E. Wolf notable student ←-------M. Born notable student -------→ E. Fermi ``` Branching. Each path p defines a branch of the search space where each feasible answer T satisfies p ⪯ T . A longer path defines a smaller search space; thus, path growing corresponds to branching. B3F iteratively enumerates paths that grow from keyword vertices. For each enumerated path p, we estimate cost(p). It is a lower bound for the costs of the feasible answers in the branch defined by p: Best-first search and bounding. B3F performs best-first search. In each iteration, it processes an enumerated path ptop that minimizes cost. If cost(ptop) ≥ cost(Topt) where Topt denotes the optimal answer found so far, B3F will be terminated and return Topt; such bounding discards all feasible answers in the unprocessed branches. If cost(ptop) < cost(Topt), new feasible answers will be constructed by merging ptop with other processed paths that end at the same vertex as ptop; then Topt may be updated. B3F completes the current iteration by growing ptop to enumerate longer paths. ## 4.2 AlgorithmB3F B3F is detailed in Algorithm 1. Following common practice [Kacholia et al., 2005; Cheng et al., 2017b], we introduce an extra input d representing the largest allowed depth of search to prevent large subgraphs (i.e., diam > 2d) which are not favored by users [Cheng et al., 2017b]. Topt denotes the optimal answer found so far (line 1). Paths to be processed are kept in priority queue PU and sorted by their cost values in ascending order (line 2); we will elaborate the computation of cost in Section 4.4. Paths that grow from keyword vertices are iteratively enumerated. Initially, each keyword vertex is treated as a path of length zero and inserted into PQ to be processed (lines 3-4). For each keyword ki ∈ Q, we maintain the set Pi of processed paths that contain a keyword vertex in Ki (lines 5-6). In each iteration (line 7), ptop which minimizes cost in PQ is pulled to process (line 8). If cost(ptop) ≥ cost(Topt), the algorithm will be terminated (lines 9-10). Otherwise, ptop is added to each proper Pi (lines 11-12). Specifically, Vptop is the set of vertices in ptop, and we define New feasible answers are constructed with ptop. We consider each combination of paths in P1 × · · · × Pg such that ptop is in this combination where all the paths have a common end vertex (line 13). They are merged into a subgraph T which clearly is connected and covers all the keywords in Q (line 14). If T is also structurally minimal (line 15), i.e., it is a feasible answer, and its cost is smaller than cost(Topt) (line 16), it will replace Topt (line 17). Longer paths are enumerated by growing ptop with one edge (lines 19-20), and are inserted into PQ to be processed (line 21). Growing is conditioned on the length of ptop (line 18), subject to the largest allowed depth of search. Finally, Topt is an optimum answer and is returned (line 22). ## 4.3 AlgorithmAnalysis Correctness. Consider Lemma 2 which decomposes a feasible answer into a set of paths. Lemma 2. Every feasible answer T s.t. diam(T) ≤ 2d can be constructed by merging g paths p1, . . . , pg such that for 1 ≤ i ≤ g: (1) len(pi) ≤ d, (2) the start vertex of pi is in Ki, and (3) all pi have a common end vertex. Proof. Since T = 〈VT ,ET 〉 is a tree, it is known in graph theory that: rad(T) = ⌊ diam(T)+1 2 ⌋ ≤ ⌊ 2d+1 2 ⌋ = d. Therefore, T has a central vertex c that is at most d hops away from every vertex in T. For 1 ≤ i ≤ g, since VT ∩ Ki ̸= ∅, we choose vi ∈ VT ∩Ki and let pi be the unique path between vi and c in T. All such pi satisfy (1)-(3) of the lemma, and by merging them we can construct T . The correctness theorem follows directly from Lemma 2. Theorem 3. B3F returns an optimum answer s.t. diam ≤ 2d. Proof. Consider a variant of B3F where we fix cost = -∞; thus branches are never discarded. When this variant is finished, P1, . . . , Pk contain all possible paths that start from keyword vertices and are at most d long. All their combinations have been used to construct feasible answers, including the combination that produces an optimum answer according to Lemma 2. Therefore, Topt is an optimum answer. Now consider the standard version of B3F where cost is properly estimated. When it is terminated early, according to the definition of cost, it is impossible to discard a feasible answer better than Topt, so Topt is an optimum answer. Time complexity. For G = 〈V,E〉, let |V | = n and |E| = m. There are O(n) keyword vertices, starting from which O(nd+1 ) paths are enumerated and processed. Fibonacci heap allows O(lognd+1 ) time for pull and O(1) time for insert. All the queue operations take O(nd+1 (d+1) log n) time. To construct feasible answers, O(ng(d+1) ) combinations of paths are merged. Each combination uses O(gd+1) time for merging and O((gd+1)2 ) time for calculating cost, assuming O(1) for computing sd. Therefore, finding an optimum answer takes O((gd+1)2ng(d+1) ) time. The total time complexity of B3F is O(nd+1 (d + 1) log n + (gd + 1)2ng(d+1) ). It increases exponentially with g and d, which are very small in practice. By early termination based on our lower bound estimation of cost described in Section 4.4, B3F can achieve promising performance on medium-sized KGs. ## 4.4 Lower Bound Estimation For path p = 〈Vp,Ep〉, properly estimating cost(p) is the key to the performance of B3F and is one of our main technical contributions. To ensure Eq. (2), we analyze the cost of an arbitrary feasible answer T = 〈VT , ET 〉 that satisfies p ⪯ T . For convenience, we decompose the cost function in Eq. (1): We will separately estimate a lower bound for each part. Note that the estimated bounds must be independent from T . Moreover, the estimation per se should be computationally inexpensive to improve the overall performance of B3F. Lower Bound Estimation for costwt(T ) We expand costwt(T) in Eq. (4): The first sum is independent from T and is directly calculated. For the second sum, we estimate its lower bound using the smallest total weight of other vertices besides Vp that are needed for T to cover all the keywords in Q. The computation of this total weight is formulated as the following instance of the weighted set cover problem (WSCP): Let Q′ opt be an optimum solution to Eq. (6) computed by dynamic programming. The total weight of the sets in Q′ opt forms a lower bound for the second sum in Eq. (5). To conclude, we estimate the following lower bound for costwt(T ): which is independent from T. Although WSCP is NP-hard, there are at most (2g - 1) unique instances of WSCP to solve, where g is the number of keywords in Q; each instance takes a unique proper subset of Q as the universe. Since g is very small in practice, both the number of unique instances of WSCP and the size of each instance are small. Therefore, in practice the time for the above estimation is relatively neglectable in B3F. ## Lower Bound Estimation for costsd(T ) We assume sd satisfies symmetry and triangle inequality. We expand costsd(T) in Eq. (4): The first sum is independent from T and is directly calculated. In the second sum, r represents the smallest number of other vertices besides Vp that are needed for T to cover all the keywords in Q. The computation of r is formulated as the following instance of the set cover problem (SCP): Let Q′′ opt be an optimum solution to Eq. (9) computed by dynamic programming. The number of sets in Q′′ opt forms r in Eq. (8), i.e., r = |Q′′ opt |. To estimate a lower bound for the minimum in Eq. (8), our idea is: for vi ∈ V , its semantic distance from some vertices in Vp may be very small, but its total semantic distance from all the vertices in Vp cannot be arbitrarily small due to triangle inequality. Therefore, we construct a complete undirected graph H where vertices are Vp and the edge between vi, vj ∈ Vp has weight sd(vi, vj). Let M be a maximum weighted matching in H, which puts 2⌊ |Vp| 2 ⌋ vertices in pairs. Let ˜ M be the sum of edge weights in M. Since sd satisfies triangle inequality, we have Now we can turn to estimate a lower bound for ˜ M. When |Vp| is even, the edges in H can be partitioned into |Vp| - 1 perfect matchings according to graph theory, so When |Vp| is odd, let Hk be the subgraph of H from which vk ∈ Vp and its incident edges are removed. Let Mk be a maximum weighted matching in Hk, and let ˜ Mk be the sum of edge weights in Mk. For each vk ∈ Vp, we have Summing this equation over all vk ∈ Vp, we have from which we obtain that is, Combining Eqs. (8)(10)(11)(15), we estimate the following lower bound for costsd(T): which is independent from T. In practice, the time for the above estimation is relatively neglectable in B3F because: first, following our analysis about WSCP, the time for computing |Q′′ opt| is relatively neglectable; second, the sum in Eq. (16) can be incrementally calculated when p is enumerated by growing its sub-path. ## 5 Experiments We experimented with a 3.5GHz CPU and 24GB memory. Code: https://github.com/nju-websoft/B3F . ## 5.1 Datasets We used five versions of three public KGs. They represent small to medium-sized KGs as shown in Table 1. Table 1: KGs and Queries | | KG - Source | |V | | |E| | Query - Qty | g | |-------|---------------|------------------|-----------------|---------------|-----| | MND | MONDIAL | 40,890 | 120,690 | 34 | 2-4 | | L1 | LUBM | 20,797 | 82,590 | 200 | 2-6 | | L4 | LUBM | 91,045 | 370,654 | 200 | 2-6 | | D20K | DBpedia | 20,000 | 37,017 | 128 | 2-6 | | D100K | DBpedia | 100,000 | 205,743 | 241 | 2-6 | MONDIAL 1 (MND) is a geographical KG that has been popularly used for evaluating keyword querying. We reused 50 queries provided by [Coffman and Weaver, 2014] but removed those containing unmatchable keywords. Our matching function returns vertices whose textual annotations (i.e., literals) contain the given keyword. LUBM 2 is a benchmark for generating synthetic KGs in the university domain. We generated two KGs describing one university (L1) and four universities (L4). We generated 200 synthetic queries following the procedure in [Li et al., 2016]. Specifically, we varied two parameters: the number of keywords in a query (i.e., g) and the average number of vertices matched with each keyword in a query (denoted by f). For each g ∈ {2, 3, 4, 5, 6} and each f ∈ {5, 10, 50, 100} we generated 10 queries. Given g and f, to generate a query we created g pseudo keywords and we let each pseudo keyword match with an average of f random vertices. From the well-known encyclopedic KG of DBpedia 3 we extracted two subgraphs D20K and D100K consisting of different numbers of vertices with the largest degrees and all the edges between them. We reused 429 queries provided by [Hasibi et al., 2017] but removed those containing unmatchable keywords, i.e., the given keyword is not contained in any label annotations (rdfs:label) of vertices. ## 5.2 Cost Function and Parameters Concrete implementations of wt and sd are not our research focus. We reused existing normalized PageRank for wt: For semantic distance sd, we followed [Cheng et al., 2017b] to compute the Jaccard distance between sets of types of entities in DBpedia to capture ontological semantics. This is not suitable for MONDIAL and LUBM where each entity has a single type. On these datasets, we computed the angular distance between 10-dimensional embedding vectors of entities generated by pyRDF2Vec 4 to capture structural semantics. For the parameter α in the cost function we compared two values: α = 0.3 and α = 0.7. For the largest allowed depth of search in B3F we set d = 3 since subgraphs of diam > 6 would be too large to present in real applications. [1 https://www.dbis.informatik.uni-goettingen.de/Mondial](https://www.dbis.informatik.uni-goettingen.de/Mondial) [2 http://swat.cse.lehigh.edu/projects/lubm/](http://swat.cse.lehigh.edu/projects/lubm/) [3 https://wiki.dbpedia.org/ (version 2016-10)](https://wiki.dbpedia.org/) [4 https://github.com/IBCNServices/pyRDF2Vec](https://github.com/IBCNServices/pyRDF2Vec) Table 2: Mean Run Time (seconds) and Mean Cohesiveness Ratio | | | MND | L1 | L4 | D20K | D100K | |-------|---------------|-------|-------|--------|--------|---------| | Time | B3F (α = 0.3) | 1.68 | 1.84 | 30.96 | 4.09 | 261.14 | | Time | B3F (α = 0.7) | 1.31 | 2.42 | 32.50 | 6.52 | 101.12 | | Time | DPBF | 0.19 | 16.15 | 113.00 | 2.29 | 25.41 | | Ratio | B3F (α = 0.3) | 0.89 | 0.47 | 0.53 | 0.79 | 0.64 | | Ratio | B3F (α = 0.7) | 0.92 | 0.56 | 0.63 | 0.80 | 0.65 | ## 5.3 Baseline We are the first to propose an exact algorithm for QGSTP. We compared our algorithm with DPBF [Ding et al., 2007], a state-of-the-art exact algorithm for the standard vertexweighted GST problem which is a simple special case of QGSTP. DPBF minimizes the total weight of the vertices in an answer but is unaware of semantic distance. Recent faster algorithms for the GST problem [Li et al., 2016; Shi et al., 2020] were not compared because they were designed for edge weights but could not handle vertex weights. ## 5.4 Efficiency Results Recall that our research target in this paper is to efficiently solve QGSTP. Thus, run time is our main evaluation metric. Metric. We measured the mean run time of each algorithm for answering a query. The results are shown in Table 2. Comparison with baseline. The run time of B3F and DPBF was generally at the same level of magnitude. B3F was 3.48-8.78 times as fast as DPBF on L1 and L4, but was 1.79-10.28 times as slow as DBPF on the other KGs. Scalability. B3F was fast on small KGs of 20k-40k vertices. It only used 1.31-6.52 seconds to answer a query on MND, L1, and D20K. However, it took 30.96-261.14 seconds on medium-sized KGs of about 100k vertices like L4 and D100K, i.e., the run time grew superlinearly with the number of vertices. In Fig. 2 we break down the results under α = 0.3 by g, the number of keywords in a query. The run time grew noticeably when g was increased. Similar results under α = 0.7 are shown in Fig. 3. Discussion. On small and medium-sized KGs, B3F showed promising performance comparable to DPBF but note that B3F solved a harder problem where cohesiveness was modeled by quadratic terms to produce better answers. The performance is acceptable for many enterprise-level applications such as analytics-oriented exploration which is more focused on answer quality rather than run time. Moreover, one could easily improve the performance by parallelizing the execution of B3F, e.g., by processing multiple combinations of paths in parallel. However, B3F and DPBF are exact algorithms for NP-hard problems and they have exponential run time in the worst case. They may not be the best choice for applications where KGs are extremely large and run time rather than answer quality is the main concern. For such applications, one may consider more scalable approximation algorithms [Shi et al., 2021; Shi et al., 2020]. ## 5.5 Effectiveness Results Our research is focused on efficient algorithms for the generalized QGSTP, rather than the effectiveness of its concrete implementation in KG exploration which has been empirically demonstrated by case or user studies [Cheng et al., 2017b; Bryson et al., 2020]. Here we mainly aimed to extend such qualitative studies by quantitatively comparing the cohesiveness of our quadratic GSTs with standard GSTs. Figure 2: Mean cohesiveness ratio and run time of B3F (α = 0.3) under different values of g. ![Image](https://ijcai.org/proceedings/2021/fulltext/215/image_000001_f55b73a077269469ff9427864ec33f1cab8d2e5ea97bfd008461f3856177effd.png) Figure 3: Mean cohesiveness ratio and run time of B3F (α = 0.7) under different values of g. ![Image](https://ijcai.org/proceedings/2021/fulltext/215/image_000002_6be108cd98d644da5010c416539c5750ba34595ddfef4b92644d87d7c111e954.png) Metric. For each query we measured cohesiveness ratio: where costsd is defined in Eq. (4); TB3 F and TDPBF represent the answers computed by B3F and DPBF, respectively. The mean cohesiveness ratios for a query are shown in Table 2. Comparisonwith baseline. The ratios were in the range of 0.47-0.92, i.e., quadratic GSTs were 8%-53% more cohesive than standard GSTs. It partially justified the advantage of cohesive answers reported in [Cheng et al., 2017b]. Similar to our efficiency experiment, in Fig. 2 and Fig. 3 we break down the results by g, the number of keywords in a query. We did not observe explicit correlation between them. Case study. In Fig. 4 we show two answers computed by different methods for a query on DBpedia in our experiments. The GST computed by DPBF is more compact and contains more salient entities such as France, but it is not a cohesive subgraph. The four entities have different types and are semantically distant from each other. They do not constitute a meaningful answer. By comparison, the quadratic GST computed by B3F is a cohesive subgraph where the five entities have the same type and are semantically close to each other. It meaningfully describes relations between military conflicts. ## 6 Conclusion QGSTP has been formulated for improving the cohesiveness of answers for KG exploration. This generalized model offers the flexibility to measure weights, semantic distances, and tune their combination. To solve QGSTP we proposed B3F. Compared with exact algorithms for computing standard GSTs, our exact algorithm for QGSTP computed more cohesive answers in comparable run time. It showed promising performance on medium-sized KGs which have supported many real-life applications. It can also be used as a baseline for evaluating approximation algorithms for QGSTP. (b) A quadratic GST computed by B3F. ![Image](https://ijcai.org/proceedings/2021/fulltext/215/image_000003_a0da057a9edb73244919ab0cd0e1795ce2fa5161ec49e951be03fdfef70bd3ed.png) Figure 4: Two answers computed by different methods for the query "France, World War II, Normandy" on DBpedia. ## Acknowledgments This work was supported in part by the National Key R&D Program of China (2018YFB1005100), in part by the NSFC (62072224), and in part by the Fundamental Research Funds for the Central Universities (0202-14380084). ## References 1. [Bryson et al., 2020] Spencer Bryson, Heidar Davoudi, Lukasz Golab, Mehdi Kargar, Yuliya Lytvyn, Piotr Mierzejewski, Jaroslaw Szlichta, and Morteza Zihayat. Robust keyword search in large attributed graphs. Inf. Retr. J., 23(5):502-524, 2020. 2. [Cheng and Kharlamov, 2017] Gong Cheng and Evgeny Kharlamov. Towards a semantic keyword search over in- dustrial knowledge graphs (extended abstract). In IEEE BigData 2017, pages 1698-1700, 2017. 3. [Cheng et al., 2016] Gong Cheng, Cheng Jin, and Yuzhong Qu. HIEDS: A generic and efficient approach to hierarchi- cal dataset summarization. In IJCAI 2016, pages 3705- 3711, 2016. 4. [Cheng et al., 2017a] Gong Cheng, Cheng Jin, Wentao Ding, Danyun Xu, and Yuzhong Qu. Generating illustrative snip- pets for open data on the web. In WSDM 2017, pages 151- 159, 2017. 5. [Cheng et al., 2017b] Gong Cheng, Fei Shao, and Yuzhong Qu. An empirical evaluation of techniques for ranking semantic associations. IEEE Trans. Knowl. Data Eng., 29(11):2388-2401, 2017. 6. [Cheng et al., 2020] Gong Cheng, Shuxin Li, Ke Zhang, and Chengkai Li. Generating compact and relaxable answers to keyword queries over knowledge graphs. In ISWC 2020, Part I, pages 110-127, 2020. 7. [Cheng, 2020] Gong Cheng. Relationship search over knowledge graphs. ACM SIGWEB Newsl., 2020(Sum- mer):3, 2020. 8. [Coffman and Weaver, 2014] Joel Coffman and Alfred C. Weaver. An empirical performance evaluation of relational keyword search techniques. IEEE Trans. Knowl. Data Eng., 26(1):30-42, 2014. 9. [Dass et al., 2015] Ananya Dass, Aggeliki Dimitriou, Cem Aksoy, and Dimitri Theodoratos. Incorporating cohesive- ness into keyword search on linked data. In WISE 2015, Part II, pages 47-62, 2015. 10. [Ding et al., 2007] Bolin Ding, Jeffrey Xu Yu, Shan Wang, Lu Qin, Xiao Zhang, and Xuemin Lin. Finding top-k min- cost connected trees in databases. In ICDE 2007, pages 836-845, 2007. 11. [Gu et al., 2019] Yu Gu, Tianshuo Zhou, Gong Cheng, Ziyang Li, Jeff Z. Pan, and Yuzhong Qu. Relevance search over schema-rich knowledge graphs. In WSDM 2019, pages 114-122, 2019. 12. [Hasibi et al., 2017] Faegheh Hasibi, Fedor Nikolaev, Chenyan Xiong, Krisztian Balog, Svein Erik Bratsberg, Alexander Kotov, and Jamie Callan. DBpedia-Entity v2: A test collection for entity search. In SIGIR 2017, pages 1265-1268, 2017. 13. [Ihler, 1991] Edmund Ihler. The complexity of approximat- ing the class Steiner tree problem. In WG 1991, pages 85-96, 1991. 14. [Kacholia et al., 2005] Varun Kacholia, Shashank Pandit, Soumen Chakrabarti, S. Sudarshan, Rushi Desai, and Hrishikesh Karambelkar. Bidirectional expansion for key- word search on graph databases. In VLDB 2005, pages 505-516, 2005. 15. [Kargar and An, 2011] Mehdi Kargar and Aijun An. Key- word search in graphs: Finding r-cliques. PVLDB, 4(10):681-692, 2011. 16. [Klein and Ravi, 1995] Philip N. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms, 19(1):104-115, 1995. 17. [Le et al., 2014] Wangchao Le, Feifei Li, Anastasios Ke- mentsietsidis, and Songyun Duan. Scalable keyword search on large RDF data. IEEE Trans. Knowl. Data Eng., 26(11):2774-2788, 2014. 18. [Li et al., 2016] Rong-Hua Li, Lu Qin, Jeffrey Xu Yu, and Rui Mao. Efficient and progressive group Steiner tree search. In SIGMOD 2016, pages 91-106, 2016. 19. [Li et al., 2020] Shuxin Li, Gong Cheng, and Chengkai Li. Relaxing relationship queries on graph data. J. Web Se- mant., 61-62:100557, 2020. 20. [Lissandrini et al., 2020] Matteo Lissandrini, Torben Bach Pedersen, Katja Hose, and Davide Mottin. Knowledge graph exploration: where are we and where are we going? ACM SIGWEB Newsl., 2020(Summer):4, 2020. 21. [Pound et al., 2012] Jeffrey Pound, Alexander K. Hudek, Ihab F. Ilyas, and Grant E. Weddell. Interpreting keyword queries over web knowledge bases. In CIKM 2012, pages 305-314, 2012. 22. [Shekarpour et al., 2013] Saeedeh Shekarpour, Axel- Cyrille Ngonga Ngomo, and Sören Auer. Question answering on interlinked data. In WWW 2013, pages 1145-1156, 2013. 23. [Shi et al., 2020] Yuxuan Shi, Gong Cheng, and Evgeny Kharlamov. Keyword search over knowledge graphs via static and dynamic hub labelings. In WWW 2020, pages 235-245, 2020. 24. [Shi et al., 2021] Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Evgeny Kharlamov, and Yulin Shen. Efficient com- putation of semantically cohesive subgraphs for keyword- based knowledge graph exploration. In WWW 2021, 2021. 25. [Sun et al., 2020] Yawei Sun, Lingling Zhang, Gong Cheng, and Yuzhong Qu. SPARQA: skeleton-based semantic parsing for complex questions over knowledge bases. In AAAI-IAAI-EAAI 2020, pages 8952-8959, 2020. 26. [Tran et al., 2009] Thanh Tran, Haofen Wang, Sebastian Rudolph, and Philipp Cimiano. Top-k exploration of query candidates for efficient keyword search on graph-shaped (RDF) data. In ICDE 2009, pages 405-416, 2009. 27. [Yang et al., 2019] Yueji Yang, Divyakant Agrawal, H. V. Ja- gadish, Anthony K. H. Tung, and Shuang Wu. An efficient parallel keyword search engine on knowledge graphs. In ICDE 2019, pages 338-349, 2019. 28. [Zhou et al., 2020] Tianshuo Zhou, Ziyang Li, Gong Cheng, Jun Wang, and Yuang Wei. GREASE: A generative model for relevance search over knowledge graphs. In WSDM 2020, pages 780-788, 2020. 29. [Zhu et al., 2018] Yuanyuan Zhu, Qian Zhang, Lu Qin, Lijun Chang, and Jeffrey Xu Yu. Querying cohesive subgraphs by keywords. In ICDE 2018, pages 1324-1327, 2018.