A Data-Driven Graph Schema

Abstract

In this paper, we summarise our results on Modelling Dynamics in Semantic Web Knowledge Graphs published at WWW 2018 where we proposed a novel data-driven schema for graphs and apply it for the use-case of predicting high-level changes in Wikidata.

Introduction

Graph-based data models [ 1 ] have become increasingly common in data management scenarios that require exibility beyond what is o ered by traditional relational databases. Such exibility is particularly important in Web scenarios, where potentially many users may be involved (either directly or indirectly) in the creation, management, and curation of data. An example of such a scenario is the Wikidata knowledge graph [ 2 ] where users can add new properties and types that can be used to de ne further data.

The ip-side of exibility is higher levels of heterogeneity. Conceptually understanding the current state of a knowledge graph { in terms of what data it contains, what it is missing, how it can be e ectively queried, what has changed recently, etc. { is thus a major challenge: it is unclear how to distil an adequate, high-level description that captures an actionable overview of knowledge graphs.

We thus need well-founded methodologies to make sense of knowledge graphs, where an obvious approach is to de ne some notion of schema for such graphs. The traditional approach in the Semantic Web has been what Pham and Boncz [ 3 ] call the schema rst approach, which de nes the schema that the data should follow. The most established language for specifying such schemas is RDFS. An alternative to the schema rst approach is the schema last approach [ 3 ], which foregoes an upfront schema and rather lets the data evolve naturally; thereafter, the goal is to understand what the legacy graph data contain by extracting highlevel summaries that characterise the graph, resulting in a data-driven schema.

In this paper, we summarise recently published results [ 4 ] on a novel approach to compute a data-driven schema from knowledge graphs. We believe that such schemas are useful for understanding what a knowledge graph contains, and how it can be queried, among several other use-cases. Nevertheless, in this work we focus on the use-case of predicting how the knowledge graph will evolve in future versions, which could be used for measuring the time-to-live of cached SPARQL results, identifying missing properties for entities, etc.

Preliminaries

RDF is a graph-structured model based on three disjoint sets of terms: IRIs (I), literals (L) and blank nodes (B). Claims involving these terms can be organised into RDF triples (s; p; o) 2 (I [ B) I (I [ B [ L), where s is called subject, p is called predicate, and o is called object. An RDF graph G is then a nite set of RDF triples; each such triple (s; p; o) 2 G can be viewed as a directed labelled edge of the form s !p o. The terms used in the predicate position are referred to as properties. We use the term entity to refer to the real-world objects identi ed by the subjects of the graph. Given an RDF graph G, for 2 fs; p; og, we denote by (G) the projection of the set of terms appearing in a particular triple position in G; e.g., s(G) := fs j 9p; o : (s; p; o) 2 Gg. We also use this notation for more than one triple position, for example, s;p(G) := f(s; p) j 9o : (s; p; o) 2 Gg. 3

A Data-Driven Schema for (RDF) Graphs

To de ne our data-driven schema proposal, let JGK 2 s(G) 2 p(G) denote a set such that S(S;P )2JGK S P = s;p(G), and where for all (S; P ) 2 JGK, it holds that S 6= ;, P 6= ;, and there does not exist (S0; P 0) 2 JGK, (S; P ) 6= (S0; P 0) such that S \ S0 6= ; or P = P 0. Intuitively, letting JsKG := fp j 9o : (s; p; o) 2 Gg denote the characteristic set of s in G [ 5 ], then each pair (S; P ) 2 JGK represents the (non-empty) set of all subjects S with the (non-empty) characteristic set P . We further de ne JP KG = S such that (S; P ) 2 JGK (or JP KG = ; if no such S exists), and JSKG = P such that (S; P ) 2 JGK (or JSKG = ; if no such P exists). Abusing notation, we say that (S; P ) (S0; P 0) i P P 0. We then also de ne JGK := JGK [ f(;; ;); (J p(G)KG; p(G))g, adding a bottom and top concept (if needed) respectively in the order. Finally, for a graph G, our data-driven schema proposal is then given by the lattice L = (JGK ; ).

Given that large-scale knowledge graphs may often have orders of magnitude more subjects than predicates, we can greatly reduce the overall (e.g., in-memory) size of the lattice by encoding the number of subjects rather than the full set of subjects. In other words, given a lattice L = (JGK ; ), we de ne JGK# := f(n; P ) j 9S : (S; P ) 2 JGK ; n = jSjg with lattice L# := (JGK#; ). We denote by JP KG# = jJP KGj the number of subjects that P has. Figure 1 provides an example RDF graph and the Hasse diagram for its corresponding L#. 4

Lattice Di -Algebra

Though we believe that the lattices de ned previously may satisfy a number of applications, we currently focus on the use-case of modelling and predicting changes in a graph. More speci cally, if we have the lattices for two versions of a knowledge graph, we can apply a di to see high-level changes between both versions. Furthermore, given such a di , we could further consider adding that di to the most recent version to try predict future changes. :UT :name "U Thurman" ; :star :Gattaca . :GO :name "G Orwell" ; :writer :1984 . :AK :name "A Kurosawa" ; :director :Ikiru , :Ran . :PD :name "PK Dick" ; :writer :Ubik , :Valis . :CE :name "C Eastwood" ; :director :Sully ; :star :Unforgiven , :Tightrope .

(0; fd; n; s; wg) (1; fd; n; sg) (1; fd; ng)

(2; fn; wg) (1; fn; sg) De ning lattice di s Let Li = (JGiK ; ) and Lj = (JGj K ; ) be the lattices for two versions (i and j) of an RDF graph G. We de ne the di between these two lattices as j;i := f(JsKGj ; s; JsKGi ) j s 2 s(Gi [ Gj )g; note that JsKGj = ; for deleted subjects and j;i, we also de ne a cardinality-only version Jsj#K;Gii:==f;(Pfo0;rnn;ePw) s:unbj=ecjtfss. G:(iPve0n;s; P ) 2 j;igjg, where by j#;i(P 0; P ) we denote n such that (P 0; n; P ) 2 j#;i or 0 if no such n exists. Predicting future #-lattices Given j#;i, and Lk# (for k a third version of the graph), we can \add" the changes between the ith and jth versions to the kth version to predict the (k+j i)th version (where typically i < j k). We will thus de ne the operation Lk# + j#;i as producing a #-lattice Lk#;j;i predicting L[#k+j i]. To apply this operation we consider the ratio of subjects moving from a source to a target characteristic set. Formally, we de ne the ratio of subjects of P (where JP KG#i 6= 0, P 6= ;) moving to P 0 (where P 0 6= ;) as j;i(P 0; P ) := j#;i(P#0;P ) ; in JP KGi the case that JP KG#i = 0, we de ne j;i(P 0; P ) = 1 i P 0 = P , or 0 otherwise. We then de ne Lk;j;i := (f( (P ); P ) j P 6= ; and (P ) 6= 0g; ), where: 0 (P ) := round @

X Pk2fP j9S:(S;P )2JGkKg 1 j;i(P; Pk)

# JPkKGk A + j#;i(P; ;) : The summand j#;i(P; ;) adds the number of fresh subjects (not appearing in version i) added to P in version j. Finally, we add top and bottom concepts (as # before) to Lk;j;i to generate the predicted #-lattice Lk;j;i. 5

Evaluation

We consider 11 weeks of \truthy" RDF dumps of Wikidata from 2017-04-18 to 2017-06-27; the rst version has 1,102,242,331 triples, 54,236,592 unique subjects and 3,276 unique properties, while the last version has 1,293,099,057 triples (+17%), 57,197,406 unique subjects (+5%) and 3,492 unique properties (+6%). From the last version, with a MapReduce implementation, we extract 2,118,109 characteristic sets in approximately 2.5 hours; computing the lattice by the relation then took almost 8 hours on a single machine [ 4 ].

To test the quality of the future #-lattices we predict { speci cally the number of subjects per characteristic set in the future unseen version { we run experiments where we consider from 2{5 previous weekly versions to predict the next version of the #-lattice. As a baseline, for each characteristic set, we apply linear regression over the number of subjects in that characteristic set for the previous weeks to predict the number of subjects for the next week; we compare this baseline with our di algebra ( ), computing the error with respect to the real lattice of the predicted week. The results are available in [ 4 ], where we show that our di algebra outperforms the linear regression baseline method in all cases; we believe that this is because our di algebra considers the number of subjects remaining in source characteristic sets for its predictions whereas the baseline does not consider where predicted new subjects will come from. 6

Conclusion

We have proposed a form of data-driven schema for large-scale knowledge graphs and shown it to be feasible to compute. As a concrete use-case, we presented an algebraic method by which these schemas can be used to predict high-level changes in the dataset. Our evaluation over 11 weeks of Wikidata demonstrates that such predictions are feasible to compute; furthermore, we validated the quality of predictions made by our algebraic approach against a linear-model baseline. We refer the interested reader to the full paper [ 4 ] for additional details on the proposed schema, examples of di s, algorithms to compute the lattices, statistics on the lattices produced, details of the experiments, and further discussion. Acknowledgements: This work was supported by the Millenium Scienti c Initiative, by Fondecyt Grant No. 1181896 and by the German Research Foundation (DFG) in CRC 912 (HAEC) and in Emmy Noether grant KR 4381/1-1.

References

1. Angles , R. , Arenas , M. , Barcelo , P. , Hogan , A. , Reutter , J. , Vrgoc , D. : Foundations of modern query languages for graph databases . ACM Comp. Surveys 50 ( 5 ) ( 2017 )

2. Vrandecic , D. , Krotzsch, M.: Wikidata: a free collaborative knowledgebase . Commun. ACM 57 ( 10 ) ( 2014 ) 78 { 85

3. Pham , M. , Boncz , P.A. : Exploiting Emergent Schemas to Make RDF Systems More E cient . In: ISWC. Lecture Notes in Computer Science , Springer ( 2016 ) 463 { 479

4. Gonzalez , L. , Hogan , A. : Modelling dynamics in semantic web knowledge graphs with formal concept analysis . In: WWW . ( 2018 )

5. Neumann , T. , Moerkotte , G.: Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins . In: ICDE, IEEE Comp. Society ( 2011 ) 984 { 994