Querying Knowledge Graphs by Example Entity Tuples

I. INTRODUCTION

• Knowledge graphs’ size and complexity make them difficult for non-experts, while structured querying requires knowledge of query languages, data models, and specific datasets.The paper notes that schema-less graph data can be especially intangible to understand and query.Source: §I · p. 1
• GQBE takes example entity tuples instead of graph queries, letting users provide entities without specifying how they are related.For example, a founder-company pair can retrieve similar pairs such as Steve Wozniak–Apple Inc. and Sergey Brin–Google.Source: §I · pp. 1–2
• The authors present tuple-based querying as a first graph-query-by-example proposal and as complementary to keyword-based methods.They note that keyword querying can suit users who do not know sample answers, whereas GQBE requires example entities.Source: §I · p. 2
• GQBE derives a weighted maximal query graph from input tuples, models candidate query graphs as a lattice, and partially evaluates that lattice to find top-k answers.The graph’s weighted edges represent tuple features, and multiple input tuples can collectively capture user intent.Source: §I · pp. 2–3
• GQBE is twice as accurate as NESS and outperforms it on efficiency in most queries.The comparison uses NESS with the maximal query graph as input.Source: §I · p. 3

II. PROBLEM FORMULATION

• Given a data graph and query tuple, the task is to find the top-k answer tuples with the highest similarity scores.A tuple is an ordered list of graph entities.Source: §II · p. 3
• The neighborhood graph includes query entities and nodes reachable from them by undirected paths of at most d edges, together with edges on those paths.It represents nearby relationships as features of the tuple; exact matches to its subgraphs provide approximate answers.Source: §II · p. 3
• A query graph is a weakly connected neighborhood-graph subgraph containing every query entity, and an answer graph is an isomorphic subgraph of the data graph.The answer tuple is the projection of the query entities through the graph isomorphism.Source: §II · pp. 3–4
• An answer tuple’s score is the highest score among answer graphs that project to it, capturing how well it matches the query tuple.A tuple may be projected from answer graphs matching different query graphs.Source: §II · p. 4

A. Maximal Query Graph

• The MQG is a weakly connected subgraph of the neighborhood graph containing every query entity and exactly m edges, maximizing total edge weight.The neighborhood graph can be very large; for ⟨Jerry Yang, Yahoo!⟩, it has 800K nodes and 900K edges at d=2.Source: A. Maximal Query Graph · p. 4
• Finding the decision version of the maximal query graph is NP-hard, and an appropriate m may not yield any feasible subgraph.Even when a feasible graph exists, maximizing its total edge weight is hard.Source: A. Maximal Query Graph · p. 4
• A greedy algorithm orders neighborhood-graph edges by weight and selects a connected component containing all query entities with edge count close to target m.It searches for the smallest number of top-weight edges yielding a component of size m, with fallback choices just below or above m.Source: A. Maximal Query Graph · p. 5
• To balance query-entity representation, the method splits the neighborhood graph into a core and entity-specific subgraphs, then applies the greedy search to each.The core connects all query entities; the resulting components together form the MQG.Source: A. Maximal Query Graph · p. 5
• For Freebase experiments with target size r=15, the search averaged c=22 iterations; the stated total discovery time is O((n+1)×(r′ log r′+c×(m+c))).Here r′ is the average edge count per subgraph, and n is the number of query entities.Source: A. Maximal Query Graph · p. 5

B. Edge Weighting

• An edge’s weight is proportional to its inverse edge-label frequency and inversely proportional to its participation degree.Both quantities are precomputed offline because they depend only on the data graph.Source: B. Edge Weighting · pp. 5–6
• Inverse edge-label frequency discounts labels that occur frequently across the data graph.The passage contrasts rarer founded edges with more common nationality edges.Source: B. Edge Weighting · p. 5
• Participation degree discounts edges when many same-label edges meet an endpoint, capturing local rather than global frequency.The paper contrasts company employment edges with the less numerous board-member edges.Source: B. Edge Weighting · p. 6

C. Preprocessing: Reduced Neighborhood Graph

• Preprocessing removes edges classified as unimportant before MQG discovery, reducing the graph and preventing those edges from entering the MQG.Removal may disconnect the neighborhood graph, but the reduced neighborhood graph containing all query entities always exists.Source: C. Preprocessing: Reduced Neighborhood… · p. 6
• At Stanford, the education edge from Jerry Yang is important, while same-label edges to other graduates are treated as unimportant.This illustrates how the filter distinguishes a query-relevant connection from other edges incident on the same node.Source: C. Preprocessing: Reduced Neighborhood… · p. 6
• An edge is unimportant from an endpoint when it is not on a qualifying path to a query entity but duplicates the label and direction of an important incident edge.Important incident edges lie on paths of length at most d from that endpoint to a query entity.Source: C. Preprocessing: Reduced Neighborhood… · p. 6

D. Multi-tuple Queries

• Multiple example tuples can express user intent more precisely, and a merged, reweighted MQG avoids relying on separate top-k answer lists and repeated MQG evaluation.The paper notes that a good answer may not appear in enough individual top-k lists, while evaluating multiple MQGs can be expensive.Source: D. Multi-tuple Queries · pp. 6–7
• GQBE maps each tuple’s query entities to shared virtual entities, then combines the resulting MQGs and merges identical vertices and edges.An edge’s merged weight is its maximum individual weight multiplied by the number of virtual MQGs containing it; the merged graph may then be trimmed toward size r.Source: D. Multi-tuple Queries · p. 7
• Handling multiple tuples adds the cost of discovering each individual MQG and a merge step linear in their total edge count.The discovery cost scales with the number of tuples times the average cost per MQG.Source: D. Multi-tuple Queries · p. 7

A. Query Lattice

• The query lattice contains query graphs that are subgraphs of the MQG, ordered by subgraph-supergraph subsumption; its root is the MQG.Children have one fewer edge and parents one more, while valid query graphs remain weakly connected and contain all query entities.Source: A. Query Lattice · p. 7
• The lattice is generated lazily during exploration, adding one appropriate edge to a child when a node must be evaluated.This builds the lattice bottom-up rather than generating every node in advance.Source: A. Query Lattice · p. 8
• Minimal query trees are generated by enumerating spanning trees of the core component and iteratively trimming non-query leaves.The paper reports that this enumeration cost is negligible in its Freebase experiments because the MQG usually has fewer than 15 edges.Source: A. Query Lattice · p. 8

B. Answer Graph Scoring Function

• The answer-graph score combines the total edge weight of query graph Q with extra credit for identical nodes among matched nodes in answer graph A and Q.The score captures A’s similarity to Q and is used to define the answer-tuple score.Source: B. Answer Graph Scoring Function · p. 8
• Identical-node matches receive only a fraction of an edge’s weight, using an incident-edge count as the denominator to avoid excessive credit.The heuristic reflects that identical nodes may have many identical matching neighbors.Source: B. Answer Graph Scoring Function · p. 8
• Edge depth is the smallest distance of either endpoint to any query entity, with more distant edges treated as less important.Distance is the shortest undirected-path length in MQGt; edge weights in MQGt incorporate this depth, unlike the weights in Ht.Source: B. Answer Graph Scoring Function · p. 8

V. QUERY PROCESSING

• Query processing takes MQGt and its query lattice L, then finds answer graphs matching the query graphs in L.The section next introduces the storage model and query plan for processing one query graph.Source: §V · p. 8

A. Processing One Query Graph

• The data graph is partitioned into two-column tables, one for each edge label, with subject and object as the columns.In-memory hash tables are built on each table using both subject and object as keys before queries arrive.Source: A. Processing One Query Graph · p. 9
• Evaluating a query graph becomes a multi-way join over the edge-label tables.The example query is expressed as joins between relations for edges F, G, H, L, and P.Source: A. Processing One Query Graph · p. 9
• GQBE processes the join with a right-deep hash-join plan, using an edge hash table as the build relation and another edge table or join subtree as the probe relation.The operator matches probe tuples against the build hash table and joins the matches into answer tuples.Source: A. Processing One Query Graph · p. 9

B. Best-first Exploration of Query Lattice

• Alg. 2 explores the lattice bottom-up and materializes each processed query graph’s answers so a parent can reuse a child’s results.The child’s materialized results serve as the probe relation, while a hash table for the added edge serves as the build relation.Source: B. Best-first Exploration of Query… · p. 9
• The algorithm selects the candidate node with the highest upper-bound score and stops when k answers outrank every unevaluated node’s possible score.If the selected node has no answer graph, it and all its ancestors are pruned, and candidate upper bounds are recalculated.Source: B. Best-first Exploration of Query… · p. 9
• A loose upper bound assumes perfect matching for the content score, making early termination difficult without evaluating the query graph.The bound combines the query graph’s structure score with a content score that depends on matching nodes.Source: B. Best-first Exploration of Query… · p. 9
• GQBE first finds top-k′ answers using structure score alone, then reranks them with the full score; k′ around 100 gave the best accuracy for k from 10 to 25.Smaller k′ lowered accuracy, while larger k′ increased running time.Source: B. Best-first Exploration of Query… · p. 9

C. Details of the Best-first Exploration Algorithm

• The lower frontier contains minimal query trees initially and gains parents of evaluated nodes; upper boundaries identify unpruned maximal ancestors used to bound candidate scores.The upper frontier consists of unpruned nodes without unpruned parents.Source: C. Details of the Best-first… · pp. 9–10
• If Q1 is a subgraph of Q2, every answer graph for Q2 has a corresponding subgraph answer for Q1 projecting to the same tuple.This lets answer tuples at a lattice node be grown from descendant nodes; adding edges also increases structure score.Source: C. Details of the Best-first… · p. 10
• A candidate’s upper-bound score is the maximum score among its upper-boundary nodes, and the algorithm evaluates the candidate with the highest bound.The bounds support choosing promising lattice nodes before evaluating them.Source: C. Details of the Best-first… · p. 10
• When a best candidate is null, upward closure makes all its ancestors null, so the algorithm prunes them and updates affected frontiers.A node is dirty when its upper boundary includes a pruned node; its boundary and sometimes its upper-bound score must then be recomputed.Source: C. Details of the Best-first… · pp. 10–11
• For each dirty node and pruned upper-boundary node, recomputation generates candidate subgraphs by removing each relevant Qbest-only edge in turn, then keeps valid components containing all query entities.The algorithm adds candidates not subsumed by existing upper-frontier or candidate nodes; Theorem 3 states it identifies all new upper-boundary nodes.Source: C. Details of the Best-first… · p. 11
• Upper-frontier recomputation has worst-case time O(|Ln|×Dp × q × |E(MQGt)|); experiments report |Ln| at 1% of |L|, Dp around 8, and q around 9.The authors report that the recomputation algorithm quickly computes the dynamically changing lattice in practice.Source: C. Details of the Best-first… · p. 12
• The current score of an answer tuple is its highest score so far, and evaluation terminates when the kth tuple’s score exceeds the next candidate’s upper bound.Theorem 4 guarantees the current top-k tuples then outrank the structure scores of all unevaluated query graphs.Source: C. Details of the Best-first… · p. 12

Experimental Setup

• The experiments used Freebase and DBpedia, comparing GQBE with NESS and a baseline across 28 queries drawn from varied domains.The evaluation used table-derived ground truth and named entities and abstract concepts from the two graphs.Source: §VI · pp. 12–13

Accuracy Based on Ground Truth

• GQBE’s P@25 exceeded 0.8 on Freebase, and its accuracy across three measures was almost always twice NESS’s.The authors attribute the difference to GQBE prioritizing query entities and important MQG edges, unlike NESS’s more uniform weighting.Source: §VI · p. 13, Figure 13 · p. 13
• On DBpedia queries at k=10, GQBE showed high accuracy across all queries, with perfect precision on several.Table III reports accuracy for individual DBpedia queries.Source: §VI · p. 13, Table III · p. 13

Accuracy Based on User Study

• Across 20 Freebase queries, GQBE had strong, medium, and small positive correlation with MTurk preferences on 9, 5, and 3 queries, respectively; F7 showed none.PCC was undefined for F12 and F13 because all top-30 answers had the same rank.Source: §VI · pp. 13–14, Table IV · p. 14

Accuracy on Multi-tuple Queries

• For most tested queries, combining two example tuples improved accuracy over individual tuples, and combining three improved it further.For F4, including Tuple2 already yielded perfect precision, so Tuple3 was not used.Source: §VI · p. 14, Table V · p. 14

Efficiency

• GQBE outperformed NESS on 17 of 20 Freebase queries and was more than 3 times faster on 10; it finished within 10 seconds on 17.GQBE evaluated at least 2 times fewer lattice nodes on 11 queries, while poor join selectivity hurt performance on F4 and F19.Source: §VI · p. 14, Figure 14 · p. 14, Figure 15 · p. 14
• For GQBE, MQG discovery time averaged roughly the time spent evaluating the discovered MQG, and discovery time varied with query-neighborhood size.MQG discovery precedes processing and is shared by all three compared methods.Source: §VI · p. 14, Table VI · p. 14
• Merged MQGs for two-tuple queries processed 10 of 20 queries in under a second, while the fastest separate evaluation took a second.The authors suggest merged MQGs emphasize more selective edges; merging time was negligible compared with discovering the individual MQGs.Source: Table VI · p. 14, §VI · p. 15, Figure 16 · p. 15

• Lim et al. use example tuples to find similar tuples in ontology-coupled database tables, but not graph data or entity tuples.Source: §VII · p. 15
• Set-expansion systems generally grow object sets from seeds, while GQBE accepts tuples containing multiple entities; most listed systems do not operate on data graphs.Chang et al. identify correlated keyword terms in an information network, and several systems search answers in web-page structures such as tables and lists.Source: §VII · p. 15
• [28] uses one node type and one relationship type, whereas GQBE,, and [9] handle many entity and relationship types; GQBE also includes edges incident on individual query entities and uses discovered query graphs to find answer graphs and tuples.REX [9] is limited to two input entities.Source: §VII · p. 15
• GQBE gives query entities greater importance and requires them in minimal query trees, unlike methods such as NESS that weight query-graph nodes equally.The authors report that this difference makes NESS produce less accurate answers; query relaxation in uses a different, XML-based scoring mechanism.Source: §VII · p. 15

• GQBE avoids requiring users to form explicit query graphs by deriving a hidden query graph from example tuples and partially evaluating its query lattice.Source: §VIII · p. 15
• Experiments on Freebase and DBpedia found that GQBE outperformed NESS in both accuracy and efficiency.Source: §VIII · p. 15