Verbalizing the Evolution of Knowledge Graphs with Formal Concept Analysis Martín Arispe Riveros1 , Mayesha Tasnim2 , Damien Graux3 , Fabrizio Orlandi3 , Diego Collarana2(B) 1 Universidad Privada Boliviana, Bolivia 2 Fraunhofer IAIS and University of Bonn, Germany 3 ADAPT SFI Centre, Trinity College Dublin, Ireland {diego.collarana.vargas|mayesha.tasnim}@iais.fraunhofer.de, martinarispe@upb.edu, {orlandif|grauxd}@tcd.ie Abstract. Questioning Answering and Verbalization over Knowledge Graphs (KGs) are gaining momentum as they provide natural interfaces to knowledge harvested from a myriad of data sources. KGs are dynamic: new facts are added and removed over time, producing multiple versions, each representing a knowl- edge snapshot of a point in time. Verbalizing a report of the evolution of entities is useful in many scenarios, e.g., reporting digital twins’ evolution in manufactur- ing or healthcare. We envision a method to verbalize a graph summary capturing the temporal evolution of entities across different KG versions. Technically, our approach considers revisions of a graph over time and converts them into RDF molecules. Formal Concept Analysis is then performed on these RDF molecules to synthesize summary information. Finally, a verbalization pipeline generates a report in natural language. 1 Introduction Talking Knowledge Graphs in the form of Question Answering and Story Telling com- ponents have gained momentum as natural user interfaces to heterogeneous data struc- tures. On the one hand, Question Answering (QA) technology, including QAnswer [3] and WDAqua-core1 [4] paved the way to knowledge graph agnostic QA systems. On the other hand, the ability to verbalize part of a knowledge graph (KG) to create re- ports (storytelling), is considered another critical application in many domains, e.g., healthcare and finance. Diverse approaches have been proposed to verbalize semi- and fully-structured data. The most recent approaches focus on data-hungry deep learning architectures, e.g., [1,12]. However, these approaches perform poorly on unseen do- mains. Although much attention has been put on QA and Verbalization over KGs, few have considered the dynamic nature of KGs. Knowledge graphs are becoming increas- ingly dynamic, and approaches have been proposed [19] to (i) detect changes during their evolution, (ii) represent change information (using vocabularies) [16], and (iii) propagate changes to replicas or federated systems [5]. In this context, change detec- tion is typically performed computing “deltas” (or changesets1 ) between two versions Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons Li- cense Attribution 4.0 International (CC BY 4.0). 1 https://www.w3.org/2009/12/rdf-ws/papers/ws07 (accessed on 08/09/2020) 2 M. Arispe et al. Cristiano Cristiano Cristiano Madeira Ronaldo Madeira Ronaldo Madeira Ronaldo 5 February 5 February 5 February Cristiano Ronaldo was born in Sporting 1985 Man. 1985 Portuguese 1985 CR7 CR7 Madeira on the 5th of February of United Football 2002 2008 1985. He is a Football Player. In Fashion Player Entrepreneur 2002,2008,2013,2020 = ALL 2002 Cristiano Ronald was playing Football Portuguese Sporting Portuguese Player English Football for Sporting. In 2008 he was a Player English 2002 player of Man United and started CR7 Man his career as a Fashion Cristiano Cristiano FCA + 2008 United Verbalization Entrepreneur, he as well learned Madeira Ronaldo Madeira Ronaldo Ontology 2008,2013,2020 Pipeline 2013,2020 Fashion English. In 2013, Cristiano Ronald Real 5 February 5 February 2013 Entrepreneur was playing for Real Madrid and Madrid Juve Spanish 1985 1985 2020 was dating Irina Shayk. He learned CR7 CR7 Christiano Real 2013 2020 Spanish, started his modeling Model Model Jr. Model Portuguese Portuguese Madrid career, and got a son Chriation Jr. English Football English Football Irina Now he plays for Juve and is Spanish Player Spanish Player Georgina Juve Shayk dating Georgina Rodriguez. Rodriguez Christiano Irina Christiano Georgina Jr. Shayk Jr. Rodriguez Fig. 1: Motivating example: Four-yearly RDF entities, describing the professional evo- lution of the football player Cristiano Ronaldo, pass through an entity-evolution sum- mary creation step. Finally, a verbalization step produces an understandable human summary of the entity’s evolution. of a knowledge graph at different granularity levels [19]: dataset, resource or statement. Let us consider four different entity descriptions depicted in Figure 1. These graphs rep- resent four different years of the football player Cristiano Ronaldo, aka., CR7. Through time, CR7 evolved in different contexts of his professional career and personal life. He changed teams several times; thus, the relation team changed as well. He also became an entrepreneur in 2008 and a father in 2013. Developing an approach to verbalize the evolution of entities in a knowledge graph would be useful to encompass in a glance CR7’s life. More generally, creating a story (report) for KG evolution is useful in many do- mains and challenging as it should be schema-agnostic. For example, 1) in industry 4.0 to report the evolution of digital twins, or 2) in healthcare to understand the evolution of patients according to their records, or 3) to produce financial reports of the evolution of companies and industries. In this study, we present the vision of an approach to produce a summary of the evolution of entities in knowledge graphs. The approach is based on Formal Concept Analysis to automatically create entity summary in a schema-agnostic manner. Finally, we employ a template-based approach to verbalize the evolution. This paper is structured as follows. Section 2 presents the state of the art. Then, Section 3 de- fines the approach and techniques envisioned. Finally, Section 4 wraps up and outlines future work. 2 Related Work The associated literature is threefold. First, we review verbalization efforts on structured data and KGs. Then, we present applications and benefits of FCA on KGs. Finally, we provide an overview of the current techniques developed to manage KG evolution. KGs Verbalization. A variety of works have proposed methods for verbalizing struc- tured data and KGs. We start with the early (but widely used) heuristic-driven methods where the main objective is to choose the right set of rules or templates to verbalize Verbalizing the Evolution of Knowledge Graphs with FCA 3 KGs. One of the most representative works here is SimpleNLG [10] and its differ- ent variants, French, Spanish, German, and Italian. SimpleNLG defines a three-stage pipeline for Natural Language Generation (NLG). Hence, these approaches are hard to adapt to different domains requiring many tunning efforts, so recent NLG approaches employ neural network architectures. These neural approaches mostly use the seq2seq architectures with attention mechanisms [1,12] and replace the three-phase pipeline with an end-to-end approach. However, these approaches required large training data, and tend to perform poorly on unseen domains. FCA and KGs. Recent work in the literature aimed at applying FCA to knowledge graphs for concept analysis. For example, in [9] the authors propose an extension of FCA where a dataset is a hypergraph instead of a binary table. Motivated by the fact that, thus far, FCA has been successfully applied to discover conceptual structures in tabular/relational data. Similarly, [14] proposes the Relational Concept Analysis (RCA), where FCA is adapted to graphs and applied to individual entities of different types sin- gularly. The only relevant work applying FCA to KGs in order to analyse their evolution is presented in [11] and [18]. In both cases FCA is leveraged for the identification of differences/similarities between different versions of a KG. In this paper we extend that work by applying it to KG verbalization/summarization tasks. KG Evolution. The increasingly dynamic nature of KGs has driven researchers into in- vestigating solutions for managing their evolution [7]. Approaches have been proposed to: (i) detect changes during their evolution [19], (ii) represent their changes and dy- namics using ontologies [16] (iii) archive their history [6], (iv) propagate their changes over federated systems [5]. Approaches for change detection mainly focus on comput- ing “deltas” (or changesets between different versions of a KG at various granularity levels [19]: dataset, resource and statement level. The Changeset Vocabulary2 defines a set of terms for describing changes on a resource and statement level. The DELTA-LD framework detects changes between two versions of a KG and represents them using a specific ontology [16]. In [15], in order to study the dynamics of LOD, the authors pro- pose a framework for extracting and analysing the evolution history of LOD datasets. A commonality of all these approaches is that specific SPARQL queries need to be con- structed in order to extract the changes, and the history, of a particular resource over time. This is because they all use specific ontologies to model this information. In con- trast, our approach allows for automatic extraction and exploration of all changes of a class/entity over time, in an easy and accessible way. 3 Proposed Approach Given different deltas of a knowledge graph, e.g., 2002, 2008, 2013, and 2020, and an entity type, e.g., Person. Our approach automatically produces a summary of evolution over time of the entities under the specified type. Each entity summary is comprised of the evolution of properties and relations among these entities along a temporal di- mension. Finally, a verbalization step produces a summary in natural language of all 2 http://vocab.org/changeset/schema (accessed on 04/09/2020) 4 M. Arispe et al. the changes identified among the knowledge graph deltas. To better understand our ap- proach, we define the central concepts it employs, i.e., RDF Molecule, Formal Concept Analysis, Evolution Summary, and Entity Verbalization. 3.1 Preliminaries Definition 1 (RDF Molecule [8]). If G is a given RDF Graph, we define an RDF Molecule M as a sub-graph of G such that, M = {t1 , . . . , tn }, ∀(i, j) ∈ {1, . . . , n}2 (subject(ti ) = subject(tj )) where t1 , . . . , tn denote the triples in M . An RDF Molecule M consists of triples having the same subject. In this work, molecules are used as units to produce entity summaries. Definition 2 (Formal Concept Analysis [20]). is an algorithm aiming at grouping ob- jects based on the overlap between their attributes. In our approach, we apply an algo- rithm proposed by V. Vychodil [20], after transforming RDF molecules into the binary data table it requires. Formal concepts are defined as conceptual clusters found within entity-property data tables. These data tables have rows corresponding to entities, and columns corresponding to the properties of those entities. Formal concepts are a set of < A, B > pairs where A is the entity set, B is the property set, and all the entities in A contain all the properties in B. A is known as extent and B is known as intent. Definition 3 (Evolution Summary [18]). To produce a temporal evolution summary of entities spread over different versions of a knowledge graph, we resort to the concept of fusion policies defined by Collarana et al. [2]. A fusion policy is a set of rules op- erating on the triple level, which are triggered by a certain combination of predicates and objects. Fusion policies resort to an ontology O to resolve possible conflicts and inequalities on the levels of resources, predicates, objects and literals. Definition 4 (Verbalization Function). We define a verbalization function V (t) which takes as input a set of triples t = {t1 , . . . , tn } and produces SEng , a text description of the given triples in natural (English) language. 3.2 Architecture Based on the summarization technique proposed by Tasnim et al. [17,18], we propose a pipeline capable of automatically verbalizing the evolution of RDF entities. Thus providing a solution to the problem of generating natural language reports on the tem- poral evolution of entities over different versions of a Knowledge Graph. We propose a three-fold approach, namely: identifying equivalent entities in different versions of a knowledge graph, summarizing the temporal evolution of these entities, and finally verbalizing the obtained summary. Figure 2 depicts the main components of our architecture. First, the pipeline takes as input a set of knowledge graphs; each graph represents different time version of the same knowledge graph. These graphs are then turned into a set of RDF molecules representing groups of equivalent entities, i.e., different temporal versions of the same Verbalizing the Evolution of Knowledge Graphs with FCA 5 Fig. 2: Architecture. real-world entity (CR7 for example). Each group of equivalent molecules is then con- verted into a binary M × N matrix. Second, the M × N matrix is provided to the FCA component which performs formal concept analysis to summarize the evolution of the entities along a temporal axis. Third, a summary merger policy is applied to each output of the FCA component to produce a set of abstract molecules. Each abstract molecule represents the temporal evolution of a single entity between the versions of the knowl- edge graphs taken as input. Fourth, said summary knowledge graph will go through a verbalization process that converts the summary graph to a readable and chronological text using a verbalization pipeline. Each summary molecule represents a single entity’s temporal evolution over the knowledge graph versions taken as input. 3.3 Conversion of Knowledge Graphs to Groups of Equivalent RDF Molecules The pipeline receives any number of KGs φ1 (D),. . . ,φn (D) as input where 1, . . . , n represent the different temporal versions of the same KG φ(D). First each graph is in- dividually converted into sets of RDF molecules. Thus we obtain RDF molecule sets S1 , . . . , Sn which correspond to graphs φ1 (D), . . . , φn (D) respectively. The pipeline then identifies equivalent molecules within S1 , . . . , Sn . As φ1 (D), . . . , φn (D) are dif- ferent temporal versions of the same KG, it can be inferred that there exists equivalent molecules M1 , . . . , Mn such that M1 ∈ S1 , . . . , Mn ∈ Sn and M1 , . . . , Mn all rep- resent the same real-world entity. For the sake of simplicity it is assumed here that equivalent entities retain the same URI. Practically, semantic similarity measures as demonstrated in [2] can also be integrated with this pipeline to identify equivalent enti- ties in cases the URI is different. 3.4 Applying Formal Concept Analysis to Obtain a Summary of Evolution Formal concept analysis studies binary object-attribute tables to describe the relation- ship between objects and their attributes. Our approach first converts KGs to RDF molecules. Within a single KG, an RDF molecule can be considered as an object while its object or data properties can be considered as attributes. When RDF molecules are modeled in this way, we are able to apply the formal concept analysis algorithm to compute formal concepts. 6 M. Arispe et al. 1. Content Planning: Content Selection 2. Sentence Planning: Sentence Final Text and Ordering. Ranking the triples of the aggregation, Lexicalization, and summary with a chronological order Referring expression generation team  is player of Cristiano Ronaldo was born in ALL, name, Cristiano Ronaldo . occupation  is a Madeira on the 5th of February of ALL, born in, Madeira . language  speaks 1985. He is a Football Player. In 2002 ... ... Cristiano Ronald was playing for 2002, team, Sporting . 4) In 2008, CR7 is player of Man United. Sporting. In 2008 he was a player of 2008, team, Man. Unit . 5) In 2008, CR7 is a Fashion Entrepreneur. Man United and started his career as 2008, profession, Fashion Entrepreneur 6) From 2008 to 2020, CR7 speaks English. a Fashion Entrepreneur, he as well . ... 3. Realization: Lexical rules for learned English. In 2013, Cristiano 2008-2013-2020, language, English . realization, Syntax / Grammar rules Ronald was playing for Real Madrid … and was dating Irina Shayk. He 2013, team, Real Madrid . In 2008 (TE), CR7 (PN , he) is player of (VP, learned Spanish, started his 2013, partner, Irina Shayk . TENSE: PAST), and CR7 (Removed) is a (VP, modeling career, and got a son 2013-2020, son, Cristiano Jr . TENSE: PAST) Fashion Entrepreneur, CR7 as Cristiano Jr. Now he plays for Juve … well speaks (VP, TENSE: PAST) English. and is dating Georgina Rodriguez. 2020, team, Juve . 2020, partner, Georgina Rodriguez . Fig. 3: Verbalization Pipeline. In the previous step we obtained sets of molecules that correspond to different tem- poral versions of the same real-world entity, e.g., in our motivation example we refer to the life events of CR7. We apply V. Vychodil’s algorithm [20] on each group of RDF molecules. The algorithm returns a set of formal concepts < M, P > where M is a set of all the molecules that have all the properties contained in P . In our approach the output < M, P > from formal concept analysis gives us a set of molecules that have the same properties throughout different KG versions. Following our motivating state- ment, we now can obtain the information that throughout the years 2002 and 2008 CR7 remained a football player and spoke Portuguese. Next, a summary fusion policy is ap- plied to the output of the Formal Concept Analysis algorithm to obtain the temporal summary of all the different versions of the molecules. 3.5 Verbalizing the entity summary In this step, we take as input the graph summary freshly produced, and generate a report of entity evolution. We define the task of verbalization as a function, and therefore it is possible to choose from the different approaches reviewed in Section 2. In this study, however, we explore a template-based approach, mainly because we have a controlled vocabulary providing us an exact phenomenon to verbalize: the evolution of an entity. Following the Natural Language Generation (NLG) pipeline described by Reiter et al. [13], we divide the summary verbalization into three steps: 1) Content Planning, 2) Sentence Planning, and 3) Realization (see Figure 3). First, we plan the content by ordering the triples chronologically; the triples that cover all the years ranked at the top. Thus, we order triples from the oldest changes to more recent ones. As the second step, we start building sentences using lexicalization, and referring expressions. We as- sume that there are rdfs:label descriptive enough to plan sentences with relative readiness. For example to transform the relation team to “is player of ”. Addition- ally we define group of sentences that should be verbalize together to form a concise idea and message. Finally, in step three, lexical and grammar rules are used to produce Verbalizing the Evolution of Knowledge Graphs with FCA 7 [data to realize ] : [Related information] Cristiano Ronaldo : subject - In 2008 : determinant is player of : verb, past tense Man. Unit : object And : complementizer In 2008, he was a player of Man He : possessive pronoun SimpleNLG United and started his career as Start : verb, past tense (Realization Engine) a Fashion Entrepreneur, he as Occupation : verb, past tense well learned English. Fashion Entrepreneur : object Comma : complementizer punctuation He : personal pronoun Learn : verb, past tense English : object Fig. 4: Realization Engine. the final text. Thus, a Realization Engine is required at this step. We propose to use SimpleNLG [10]. SimpleNLG requires two elements: the data to realize, and related information. Figure 4 shows an example of how SimpleNLG works. 4 Conclusion and Future Lines of Work In this article, we introduced our approach to verbalize the evolution of entities in KGs. Our approach leverages the concepts of RDF molecules, Formal Concept Analysis, Entity Summary, and a Verbalization Function. We explain the architecture and pipeline where only one parameter is needed, i.e., an entity filter. The report created can be useful in several domains e.g., manufacturing, healthcare, or financial domain. Future lines of work. To date, several lines of research are ahead of us, including the performance and evaluation of the approach, and the use of FCA for QA systems. FCA has scalability limitations when applied to big knowledge graphs. Therefore a newly adapted version of FCA for Big Data scenarios needs to be employed. We need to define a fair evaluation framework for our approach, including different datasets and metrics, e.g., BLUE score. Finally, we believe the summaries produced by FCA may be useful for QA systems, for example, to answer evolutionary questions on knowledge graphs and answer questions about differences between entities in a Knowledge Graph. Acknowledgements. We acknowledge the support of the EU projects Cleopatra (GA 812997) and TAILOR (GA 952215), the Federal Ministry for Economic Affairs and Energy (BMWi) project SPEAKER (FKZ 01MK20011A), the German Federal Min- istry of Education and Research (BMBF) projects and excellence clusters ML2R (FKZ 01 15 18038 A/B/C), MLwin (01S18050 D/F), ScaDS.AI (01/S18026A), the Fraun- hofer Zukunftsstiftung project JOSEPH, as well as the Marie Skłodowska-Curie fel- lowship programmes GA 801522 and GA 713567 at the ADAPT SFI Research Centre (grant 13/RC/2106). 8 M. Arispe et al. References 1. Bahdanau, D., Cho, K., Bengio, Y.: Neural machine translation by jointly learning to align and translate. In: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. (2015) 2. Collarana, D., Galkin, M., Ribón, I.T., Vidal, M., Lange, C., Auer, S.: MINTE: semanti- cally integrating RDF graphs. In: Proceedings of the 7th International Conference on Web Intelligence, Mining and Semantics, WIMS. (2017) 22:1–22:11 3. Diefenbach, D., Giménez-García, J.M., Both, A., Singh, K., Maret, P.: Qanswer KG: de- signing a portable question answering system over RDF data. In: ESWC 2020 Proceedings. Volume 12123. (2020) 429–445 4. Diefenbach, D., Singh, K.D., Maret, P.: Wdaqua-core1: A question answering service for RDF knowledge bases. In: Companion of the The Web Conference 2018 on The Web Con- ference 2018, WWW 2018, Lyon , France, April 23-27, 2018, ACM (2018) 1087–1091 5. Endris, K.M., Faisal, S., Orlandi, F., Auer, S., Scerri, S.: Interest-Based RDF Update Propa- gation. In: The Semantic Web - ISWC 2015. Volume 9366. (2015) 513–529 6. Fernández, J.D., Umbrich, J., Polleres, A., Knuth, M.: Evaluating query and storage strate- gies for rdf archives. In: SEMANTiCS 2016. (2016) 7. Fernández, J.D., Debattista, J., Orlandi, F., Vidal, M.E.: Mepdaw chairs’ welcome. In: Companion of The 2019 World Wide Web Conference, WWW. (2019) 13–17 8. Fernández, J.D., Llaves, A., Corcho, O.: Efficient rdf interchange (eri) format for rdf data streams. In: International Semantic Web Conference, Springer (2014) 244–259 9. Ferré, S., Cellier, P.: Graph-fca: An extension of formal concept analysis to knowledge graphs. Discret. Appl. Math. 273 (2020) 81–102 10. Gatt, A., Reiter, E.: Simplenlg: A realisation engine for practical applications. In: ENLG 2009 - Proceedings of the 12th European Workshop on Natural Language Generation, March 30-31, 2009, Athens, Greece. (2009) 90–93 11. González, L., Hogan, A.: Modelling dynamics in semantic web knowledge graphs with formal concept analysis. In: Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, ACM (2018) 1175–1184 12. Nema, P., Shetty, S., Jain, P., Laha, A., Sankaranarayanan, K., Khapra, M.M.: Generating descriptions from structured data using a bifocal attention mechanism and gated orthogonal- ization. In: NAACL-HLT, New Orleans, Louisiana, USA, June 1-6, 2018. (2018) 1539–1550 13. Reiter, E., Dale, R.: Building natural language generation systems. Cambridge Press (2000) 14. Rouane Hacene, A.M., Huchard, M., Napoli, A., Valtchev, P.: Relational Concept Analysis: Mining Concept Lattices From Multi-Relational Data. Annals of Mathematics and Artificial Intelligence 67(1) (2013) 81–108 15. Roussakis, Y., Chrysakis, I., Stefanidis, K., Flouris, G., Stavrakas, Y.: A flexible framework for understanding the dynamics of evolving RDF datasets. In: ISWC 2015 - International Semantic Web Conference. Volume 9366. (2015) 495–512 16. Singh, A., Brennan, R., O’Sullivan, D.: DELTA-LD: A Change Detection Approach for Linked Datasets. In: 4th MEPDaW Workshop at ESWC. (2018) 17. Tasnim, M., Collarana, D., Graux, D., Galkin, M., Vidal, M.: COMET: A contextualized molecule-based matching technique. In: International Conference on Database and Expert Systems Applications, Springer (2019) 175–185 18. Tasnim, M., Collarana, D., Graux, D., Orlandi, F., Vidal, M.: Summarizing entity temporal evolution in knowledge graphs. In: Companion of The 2019 World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, ACM (2019) 961–965 19. Umbrich, J., Villazón-Terrazas, B., Hausenblas, M.: Dataset Dynamics Compendium: A Comparative Study. In: 1st Workshop on Consuming Linked Data (COLD2010). (2010) 20. Vychodil, V.: A new algorithm for computing formal concepts. na (2008)