Querying Knowledge Graphs by Example Entity Tuples

1 1 Querying Knowledge Graphs byExample Entity Tuples Nandish Jayaram, Arijit Khan, Chengkai LiMember, IEEE, Xifeng YanMember, IEEE, Ramez ElmasriAbstract We witness an unprecedented proliferation of Knowledge Graphs that record millions of entities and their Knowledge Graphs are structure-flexible and content-rich, they are difficult to use. The challenge lies in the gap between theiroverwhelming complexity and the limited database Knowledge of non-professional users. If writing structured queriesover simple tables is difficult, complex Graphs are only harder to an initial step toward improving the usability of Knowledge Graphs ,we propose to query such data by Example Entity Tuples , without requiring users to form complex graph queries.

2 Our system,GQBE( graph Query By Example ), automatically discovers a weightedhidden maximum query graph based on input query Tuples , to capturea user s query intent. It then efficiently finds and ranks the top approximate matching answer Graphs and answer Tuples . Weconductedexperiments and user studies on the large Freebase and DBpedia datasets and observed appealing accuracy and provides a complementary approach to the existing keyword-based methods, facilitating user-friendly graph Querying . To thebest of our Knowledge , there was no such proposal in the past in the context of Terms Knowledge Graphs , Entity Graphs , Query by Example , graph Query Processing 1 MotivationThere is an unprecedented proliferation ofknowledge graphsthat record millions of entities ( , persons, products,organizations) and their relationships.

3 Is an excerptof a Knowledge graph , in which the edge labeledfoundedbetween nodesJerry YangandYahoo!captures the fact thatthe person is a founder of the company. Examples of real-world Knowledge Graphs include DBpedia [3], YAGO [19],Freebase [4] and Probase [24]. Users and developers aretapping into Knowledge Graphs for numerous applications,including search, recommendation, and business users and application developers are often over-whelmed by the daunting task of understanding and usingknowledge Graphs . This largely has to do with the sheersize and complexity of such data. As of March 2012, theLinking Open Data community had interlinked over 52 billionRDF triples spanning over several hundred datasets. Morespecifically, the challenges lie in the gap between complexdata and non-expert users.

4 Knowledge Graphs are often storedin relational databases, graph databases and triplestores. Inretrieving data from these databases, the norm is often to use N. Jayaram, C. Li and R. Elmasri are with the Department of ComputerScience and Engineering, The University of Texas at Arlington. A. Khan is with the Systems Group, ETH Zurich. The work was done atUCSB. E-mail: X. Yan is with the Department of Computer Science, University ofCalifornia, Santa Barbara. E-mail: *This work is partially supported by NSF IIS-1018865, IIS-14-08928,CCF-1117369, the Army Research Laboratory under cooperative agreementW911NF-09-2-0053 (NSCTA), 2011 and 2012 HP Labs Innovation ResearchAwards, and the National Natural Science Foundation of China Grant61370019.

5 We also thank Ning Yan for his useful contributions during 1: An Excerpt of a Knowledge Graphstructured query languages such as SQL, SPARQL, and thosealike. However, writing structured queries requires extensiveexperiences in query language, data model, and a goodunderstanding of particular datasets [10].If Querying simple tables is difficult, aren t complex Graphs harder to query?Motivated by the aforementioned usability challenge, webuildGQBE1( graph Query by Example ), a system thatqueries Knowledge Graphs by Example Entity Tuples instead ofgraph queries. Given a data graph and a query tuple consistingof entities,GQBE finds similar answer Tuples . Consider thedata graph in and an scenario where a Silicon Valleybusiness analyst wants to find entrepreneurs who foundedtechnology companies head-quartered in California.

6 Supposeshe knows an Example query tuple such ashJerry Yang,Yahoo!ithat satisfies her query intent. Entering such an Example tupletoGQBEis simple, especially assisted by user interface toolssuch as auto-completion in identifying the exact entities in thedata graph . The answer Tuples can behSteve Wozniak,Apple Brin,Googlei, which are founder-company A demonstration video of the system can be found 2: The Architecture and Components ofGQBEIf the query tuple consists of 3 or more entities ( ,hJerry Yang,Yahoo!,Sunnyvalei), the answers will be similar tuplesof the same cardinality ( ,hSteve Wozniak,Apple Inc.,Cupertinoi). Overview and ContributionsGQBEis among the first to query Knowledge Graphs byexample Entity Tuples .

7 An brief overview of the entire systemand a demonstration description can be found in [12] and [11],respectively. There are several challenges in we provide a brief overview of our approach in tacklingthese challenges. The ensuing discussion refers to the systemarchitecture and components ofGQBE, as shown in Fig. 2.(1) With regard toquery semantics, since the input toGQBEis a query tuple instead of an explicit query graph , it mustderive a hidden query graph based on the query tuple, tocapture the user s query squery graph discoverycomponent ( ) fulfills this requirement and the derivedgraph is termed amaximum query graph (MQG). The edgesin MQG, weighted by several frequency-based and distance-based heuristics, represent important features of the querytuple to be matched in answer Tuples .

8 More concretely, theycapture how entities in the query tuple ( , nodes in a datagraph) and their neighboring entities are related to each Graphs matching the MQG are projected to answertuples, which consist of answer entities corresponding to thequery tuple supports multiple querytuples as input which collectively better capture the user intent.(2) With regard toanswer space modeling( ), therecan be a large space of approximate answer Graphs ( Tuples ),since it is unlikely to find answer Graphs exactly matchingthe the space of answer Tuples by aquery latticeformed by the subsumption relation between allpossible query Graphs . Each query graph is a subgraph of theMQG and contains all query entities. Its answer Graphs are alsosubgraphs of the data graph and are edge-isomorphic to thequery graph .

9 Given an answer graph , its entities correspondingto the query tuple entities form an answer tuple. Thus theanswer Tuples are essentially approximate answers to theMQG. For ranking answer Tuples , their scores are calculatedbased on the edge weights in their query Graphs and the matchbetween nodes in the query and answer Graphs .(3) The query lattice can be large. To obtain top-krankedanswer Tuples , the brute-force approach of evaluating all querygraphs in the lattice can be prohibitively expensive. Forefficient query processing( ),GQBE employs a top-klattice exploration algorithm that only partially evaluates thelattice nodes in the order of their corresponding query Graphs upper-bound summarize the contributions of this paper as follows: For better usability of Knowledge graph Querying systems,we propose a novel approach of Querying by Example entitytuples, which saves users the burden of forming explicitquery Graphs .

10 The query graph discovery component ofGQBE derives ahidden maximum query graph (MQG) based on input querytuples, to capture users query thespace of query Graphs (and thus answer Tuples ) by a querylattice based on the MQG. GQBE s efficient query processing algorithm only partiallyevaluates the query lattice to obtain the top-kanswer tuplesranked by how well they approximately match the MQG. We conducted extensive experiments and user study on thelarge Freebase and DBpedia datasets to evaluateGQBE saccuracy and efficiency ( ). The comparison with astate-of-the-art graph Querying frameworkNESS[14] and anexemplar query systemEQ[18] shows thatGQBEis overtwice as accurate outperformsNESSon efficiency in most of the PROBLEMFORMULATIONGQBE runs queries on Knowledge data Graphs .