Identifying Mappings among Knowledge Graphs by Formal Concept Analysis

Abstract

Formal Concept Analysis (FCA) is a well-developed mathematical model for clustering individuals and structuring concepts. In one of our previous studies, we proposed to incrementally match classes and properties across complex biomedical ontologies based on FCA. We intend to apply the approach to matching knowledge graphs (KGs) and this paper reports a preliminary result. Compared with ontologies which model the schema knowledge of classes, KGs are much larger and focus on instances and their properties. We build three token-based formal contexts for classes, properties, and instances to describe how their names/labels share lexical tokens, and from the concept lattices computed, lexical mappings can be extracted across KGs. An evaluation on the 9 matching tasks of OAEI Knowledge Graph Track shows that our system obtains the highest recall in class, property, instance, and overall matching over the seven systems participated in the track in OAEI 2018. Additionally, our system is able to identify cases when one entity in a KG does not have any correspondence in another KG. Based on the lexical instance mappings, we further construct a property-based formal context to identify commonalities among properties in a structural way, which indicates a promising direction for taking full advantage of the knowledge within KGs.

Keywords

• knowledge graph
• formal concept analysis
• ontology matching

1 Introduction

Ontologies serve as the foundation of the Semantic Web by defining basic classes and their structures that constitute various domain knowledge, thus can be used to semantically annotate the Web resources. Ontology matching (OM) techniques [ 1 ] have been developed to detect the correspondence among diverse yet overlapping ontologies so that search engines and applications can understand the equivalence on the Web as well as mismatches. Since Google invented the notion of Knowledge Graph (KG) and made its own system in 2002, and with the prevailing of the TransE series algorithms [ 2,3 ] for embedding KGs in a numerical way, the Semantic Web has evolved into the KG time. Soon the OM community realized the inevitable of identifying semantic connections among KGs. Started in 2018, the annual OAEI competition 3 presents a KG track where 9 KGs in the category of Games, Comins, and TV&Books, respectively, yield a total of 9 pairwise matching tasks [ 5,6 ]. Seven OM systems were able to participate in the KG track in 2018, including the well-known AML [ 7 ], LogMap family [ 8 ], POMAP++ [ 9 ], Holontology [ 10 ], and DOME [ 11 ].

By design, both ontologies and KGs have classes, properties and instances. Ontologies primarily model the schema knowledge of classes whereas KGs are much larger and mostly describe instances and their properties. This means that techniques for mapping KGs focus more on instance matching [ 12 ]. In one of our previous studies [ 18,19,20 ], we proposed the FCA-Map system that incrementally matches classes and properties across complex biomedical ontologies based on Formal Concept Analysis (FCA). FCA is a well-developed mathematical model for clustering individuals and structuring concepts [ 14 ]. The purpose of FCAMap is to push the envelop of the FCA formalism in exploring as much knowledge as possible within ontologies, including class names, subclass relations, partwhole relations, disjointedness, and other logical axioms. In this paper, we intend to apply the approach to matching knowledge graphs and a preliminary result is reported.

Concretely, based on the rationale of lexical matching in FCA-Map, we construct three token-based formal contexts for classes, properties, and instances, respectively, to describe how their names/labels share lexical tokens. The derived formal concept lattices represent the clustering of classes/properties/instances by names, and thus lexical mappings can be extracted across KGs. An evaluation on the OAEI KG Track shows that, when compared with the seven OAEI 2018 participants, our system obtains the highest recall and comes second in F-measure in terms of average performances on 9 tasks. In addition, our system can identify most of the null mappings provided in the OAEI gold standard for entities that do not have any correspondence in another KG. Based on the lexical mappings, we further build a structural formal context to describe how properties across KGs have common in linking the same instances. The mappings identified solely by structural matching indicate a promising direction for taking full advantage of the knowledge within KGs.

Although FCA has been applied to modeling KGs [ 13 ], to the best of our knowledge, this is a first attempt to identify the correspondence among KGs by a FCA-based approach. In Section 2 of the paper, we will present the lexical matching part and its evaluation on the OAEI KG Track. A first step of structural matching is described in Section 3, and our on-going work is discussed in Section 4 at last. 3 http://oaei.ontologymatching.org/ 2 Identifying lexical mappings between KGs FCA is a principled approach of deriving a concept hierarchy from a collection of objects and their attributes. The fundamental notions are formal context and formal concept, and the former is defined as a binary table K := (G; M; I), where G is a set of objects as rows, M a set of attributes as columns, and I a binary relation between G and M in which (g; m) 2 I reads object g has attribute m , generally represented by “ ” in the table cell. A formal concept of context K is a pair (A; B) consisting of a subset of objects A G and a subset of attributes B M such that B equals all the attributes common to objects in A and at the same time, A equals the set of objects that have all the attributes in B. The subconcept-superconcept relation can be defined as: (A1; B1) (A2; B2) :, A1 A2(, B1 B2), leading to a lattice structure of formal concepts.

For the instances in two KGs, we use the following example to illustrate the construction of token-based formal context, the derivation of concept lattice and the extraction of instance mappings. The similar process applies to the classes and properties in two KGs.

Example 1. Given two KGs memory-beta (MB), stexpanded (STEX) from OAEI 2018, the left of Fig. 1 shows some instances and their label strings. Note that one string can be shared by instances across KGs, as listed on the right of Fig. 1. We extract names and labels of all instances in the two KGs and separate the tokens in them through normalization techniques [ 17 ]. As shown in Fig. 2 on the left, the token-based formal context is constructed with each string as an object, each token as an attribute, and the cell in the context marked when the string contains the token. The gray area in the table presents a formal concept indicating the duality between its objects and attributes, i.e., the subset of tokens are identified to co-exist solely in the two strings.

From the token-based formal context, formal concepts and their lattice structure can be derived automatically, as shown on the right of Fig. 2, where each node represents a formal concept and the line denotes the subconceptsuperconcept relation from the lower to the upper node 4. For identifying mappings, we pay attention to formal concepts that contain exactly two strings relevant to instances across KGs. Take for example the gray node on the right of Fig. 2 which corresponds to the gray area in the context on the left. Four instance mappings can be extracted from this formal concept: ⟨MB:USS_Fredrickson; STEX:USS_Fredrickson⟩ ⟨MB:USS_Fredrickson_(NCC-42111); STEX:USS_Fredrickson_(NCC-42111)⟩ ⟨MB:USS_Fredrickson; STEX:USS_Fredrickson_(NCC-42111)⟩ ⟨MB:USS_Fredrickson_(NCC-42111); STEX:USS_Fredrickson⟩ The first two are exact matches and the latter partial matches. 4 For the sake of eficiency, we use the Galois Sub-Hierarchy (GSH) [ 15 ] which preserves solely the necessary elements of the lattice and implement the Hermes[ 16 ] algorithm for computing the lattice.

"NCC-42111" USS_Fredrickson_(NCC-42111) USS_Fredri… rdfs:label rdfs:label

NCC-42111 "USS Fredrickson (NCC-42111)" USS_Fredrickson rdfs:label

rdfs:label

USS_Fredrickson_(NCC-42111) "USS Fredrickson" Fredrickson_system

rdfs:label instances of MB instances of STEX rdfs:label

USS_Fredrickson "Fredrickson system"

String Instances uss fredrickson SMTBE:UXS:SU_SFSr_eFdrreidcrkiscoknson

MB:USS_Fredrickson_(NCC-42111) uss fredrickson (ncc-42111) STEX:USS_Fredrickson_(NCC-42111) ncc-42111 MB:NCC-42111 fredrickson system MB:Fredrickson_system

There are 9 knowledge graphs in the OAEI KG Track, as listed in Table 1, and on its corresponding 9 KG matching tasks, we evaluate our FCA-based lexical matching approach. The results are shown in Fig. 3 according to the gold standard5 and evaluation tool6 provided by OAEI 2018. One can see that our approach is able to achieve high performances in recall, and the quality of class mappings is better than that of property mappings which is then better than instance mappings while at the same time the number of mappings identified for class, property and instance increases.

A comparison with the seven OAEI 2018 KG Track participants is listed in Table 2. Again, our approach favors recall and ranks the first in average over 9 tasks for class, property, instance and overall matching. Moreover, our approach obtains the second best F-measures in all matching types, indicating that a bal5 https://github.com/sven-h/dbkwik/tree/master/e_gold_mapping_interwiki/ gold 6 http://oaei.ontologymatching.org/2018/results/knowledgegraph/kg_track_ eval.zip Fig. 3. The results of FCA-based KG matching. Charts in the same row are about the same category, i.e., Games, Comics, and TV&Books. In each chart, the bars show precision, F-measure and recall of each task, whereas the lines show the number of mappings identified by our approach. ance can be achieved between quality and quantity. Overall, the DOME system [ 11 ] stands out by having the best precision and F-measure in both property matching and instance matching for most cases, followed by Holontology [ 10 ] which ranks the first in overall precision.

The gold standard of OAEI KG Track contains not only 1:1 mappings but also cases where one entity in a KG is matched to “null” in the other KG. They represent the uniqueness of classes, properties and instances to one knowledge base with respect to another, which is complementary to 1:1 and complex mappings in revealing the whole picture of the relationship between two systems. We call them null mappings, and the OAEI evaluation takes them into account solely for calculating false positives in 1:1 mappings. By taking advantage of the inherent feature of the FCA formalism, our system is able to identify such null mappings. When a formal concept in the derived lattice contains strings solely from one entity in a KG, the corresponding entity contributes to a null mapping. As shown in Table 3, there are 571 null mappings in the gold standard and our system has successfully detected 473 of them, accounting for 83%, as exemplified by ⟨darkscape:Room; oldschoolrunescape:null⟩ for class null mapping, ⟨marvel:null; dc:runtime⟩ for property, and ⟨memory-beta:Victoria, stexpanded:null⟩ for instance. At the same time, a large number of null mappings identified are not in the gold standard, and their validity needs further investigation as the gold standard is only partial as reported by OAEI. 3 Identifying structural mappings between KGs We call the obtained lexical mappings anchors, based on which we can build formal contexts from the structural knowledge in KGs so as to extract additional mappings. A KG can be seen as an RDF graph where the vertex generally represents a class or an instance and the edge a property from one instance to another, or a type relation from an instance to a class. For given two KGs, a property-based formal context is constructed by taking properties from two KGs as objects, and pairing the lexical instance anchors across KGs as attributes. When a property is used to link two instances in an anchor pair, the corresponding cell in the formal context is marked. After the lattice is derived, if a formal concept contains solely two properties from two KGs, respectively, they can be extracted as a structural mapping. Again, in the following we use an example to illustrate the matching process.

Example 2. Given two KGs memory-alpha (MA), memory-beta (MB) from OAEI 2018, a part of their (subject, predicate, object) (SPO triples) are listed in Table 4.

MB:Rules_of_Acquisition_(episode) MB:story

MB:Rules_of_Acquisition_(episode) MB:teleplay MB:The_Nagus MB:teleplay MB:Battle_Lines_(episode) MB:story MB:Paradise_Lost_(episode) MB:teleplay

Some lexical instance anchors between MA and MB are as follow: a = ⟨MA:Battle_Lines_(episode); MB:Battle_Lines_(episode)⟩ b = ⟨MA:Hilary_J._Bader; MB:Hilary_J._Bader⟩ c = ⟨MA:Ira_Steven_Behr; MB:Ira_Steven_Behr⟩ d = ⟨MA:Paradise_Lost_(episode); MB:Paradise_Lost_(episode)⟩ e = ⟨MA:Rules_of_Acquisition_(episode); MB:Rules_of_Acquisition_(episode)⟩ f = ⟨MA:Richard_Danus; MB:Richard_Danus⟩ g = ⟨MA:Robert_Hewitt_Wolfe; MB:Robert_Hewitt_Wolfe⟩ h = ⟨MA:The_Nagus; MB:The_Nagus⟩:

;)(gd ;)(ce ;)(be ;()ba ;()fa ;()ch

MA:wsteleplayby × × MB:teleplay × × MA:wsstoryby MB:story

× × × × × ×

MA:wsteleplayby MA:wsstoryby MB:teleplay MB:story MMAB::wtsetleelpelpalyayby (d,g) (e,c) MA:wsteleplayby (d,g) (e,c) (a,f)

(MdB,g:t)e(lee,cp)la(hy,c) (MMeAB,b::ws)st(soatr,boy)ryby (d,g) (e,c) (e,b) (a,b) (a,f) (h,c)

The constructed property-based formal context is presented on the left in Fig. 4 and the lattice derived on the right. As shown by the gray area, a property mapping ⟨MA:wsteleplayby; MB:teleplay⟩ is identified by structural knowledge rather than by names. For the matching task between KGs MA and MB, 7 property mappings are detected solely by the structural matching, as listed in Table 5, of which 2 are true positives. Note that the OAEI 2018 KG gold standard is declared to be only partial, and the lower part of Table 5 shows promising candidates. With these additional structural mappings, the precision, F-measure and recall for the property task have all increased compared with the lexical matching step, as shown by Fig. 5. memory-alpha~memory-beta

Precision F-measure Recall #mappings 140 120 100 80 60 40 20 Lexical

Structural

Lexical Structural 0

On the other hand, the structural property matching does not afect the performance of the other 8 tasks, either because the mappings found are not in the gold standard or none mappings are found at all. Note that as shown by Fig. 3, these 8 property tasks have already obtained a higher performance compared with the MA-MB task at the lexical matching step. To further improve, comprehensive ways shall be explored to augment the structural formal contexts with extended knowledge in KGs. 4

Discussion and conclusions

This paper reports an on-going study of constructing multiple FCA structures for the purpose of matching knowledge graphs. Its lexical matching part already receives the best recall and the second best F-measure in class, property, instance, and overall matching for the OAEI 2018 KG Track tasks, revealing the advantage of our FCA-based approach. Moreover, our system has identified 83% of null mappings provided in the OAEI gold standard. All these come from the inherent capability of FCA formalism in detecting commonalities among individuals and accordingly forming concepts and classifying them in a lattice structure. For the structural matching, we have realized a property-based lattice from the knowledge of property linking one instance to another in KGs. Obviously, further an instance-based lattice shall be computed similarly to identify structural instance mappings. Moreover, the knowledge of instance belonging to class in KGs can be used as well to explore commonalities among instances. As a matter of fact, we are developing an iterative framework so as to perform class, property, and instance matching in an augmented way until no further matches can be found.

Our previous system FCA-Map is for matching ontologies and thus targets classes. Although there are classes in the OAEI KGs, they are much fewer than instances and properties, and basically none schema knowledge is specified. This says that the structural matching part in FCA-Map cannot be applied directly, and alternative types of formal contexts are being designed targeting instances and properties. In addition to matching, FCA-Map includes a structural validation step to eliminate wrong mappings based on the disjoint axioms in ontologies. When there is no such knowledge in KGs, we shall develop alternative validation strategies so as to ensure the quality of mappings and prevent the mismatches from propagating in the iterative framework.

What is worth noting is that the systems participated in OAEI 2018 are basically ontology matching systems and not specifically tailored for knowledge graph matching. Therefore it is understandable that the performance can be unsatisfactory for some tasks. Nevertheless, systems like DOME still managed to outperform. DOME uses the doc2vec approach to train vector representations for ontology classes and instances based on large texts, so that the similarity among entities can be computed according to the distance of vectors. Such numerical ways of embedding KG entities into a high-dimensional, continuous space are called representation learning, which have already been adopted for matching ontologies, as in [ 21,22,23 ]. To compare our FCA-based approach with these works will be of interest, not only by conducting comparative experiments but also exploring the possible combining ways.

Acknowledgements. This work has been supported by the National Key Research and Development Program of China under grant 2016YFB1000902 and the Natural Science Foundation of China under No. 61621003.

References

1. Euzenat , J. , & Shvaiko , P. ( 2013 ). Ontology matching, 2nd Edition . Heidelberg: Springer.

2. Bordes , A. , Usunier , N. , Garcia-Duran , A. , Weston , J. , & Yakhnenko , O. ( 2013 ). Translating embeddings for modeling multi-relational data . In Advances in neural information processing systems (pp. 2787 - 2795 ).

3. Wang , Q. , Mao , Z. , Wang , B. , & Guo , L. ( 2017 ). Knowledge graph embedding: A survey of approaches and applications . IEEE Transactions on Knowledge and Data Engineering , 29 ( 12 ), 2724 - 2743 .

4. Da Silva , J. , Revoredo , K. , Baiao , F. A. , & Euzenat , J. ( 2018 , October) . Interactive ontology matching: using expert feedback to select attribute mappings . In 13th ISWC workshop on ontology matching (OM) (pp. 25 - 36 ). No commercial editor..

5. Sven Hertling , Heiko Paulheim: DBkWik: A Consolidated Knowledge Graph from Thousands of Wikis . International Conference on Big Knowledge 2018 .

6. Alexandra Hofmann , Samresh Perchani, Jan Portisch, Sven Hertling, and Heiko Paulheim. DBkWik: Towards Knowledge Graph Creation from Thousands of Wikis . International Semantic Web Conference (Posters & Demos) 2017 .

7. Faria , D. , Pesquita , C. , Balasubramani , B. S. , Tervo , T. , Carriço , D. , Garrilha , R. , ... & Cruz , I. F. ( 2018 , December). Results of AML participation in OAEI 2018 . In Ontology Matching: OM-2018 : Proceedings of the ISWC Workshop (p. 125 ).

8. Jiménez-Ruiz , E. , Grau , B. C. , & Cross , V. ( 2018 , December). LogMap family participation in the OAEI 2018 . In Ontology Matching: OM-2018 : Proceedings of the ISWC Workshop (p. 187 ).

9. Laadhar , A. , Ghozzi , F. , Megdiche Bousarsar , I. , Ravat , F. , Teste , O. , & Gargouri , F. ( 2018 ). OAEI 2018 results of POMap++ . In Ontology Matching: OM-2018 : Proceedings of the ISWC Workshop (p. 192 ).

10. Roussille , P. , Megdiche Bousarsar , I. , Teste , O. , & Trojahn , C. ( 2018 ). Holontology: results of the 2018 OAEI evaluation campaign . In Ontology Matching: OM-2018: Proceedings of the ISWC Workshop (p. 167 ).

11. Hertling , S. , & Paulheim , H. ( 2018 , December) . DOME results for OAEI 2018 . In Ontology Matching: OM-2018 : Proceedings of the ISWC Workshop (p. 144 ).

12. Pershina , M. , Yakout , M. , & Chakrabarti , K. ( 2015 , October) . Holistic entity matching across knowledge graphs . In 2015 IEEE International Conference on Big Data (Big Data) (pp. 1585 - 1590 ). IEEE.

13. Ferré , S. , & Cellier , P. ( 2019 ). Graph-FCA: An extension of formal concept analysis to knowledge graphs . Discrete Applied Mathematics.

14. Ganter , B. , & Wille , R. ( 2012 ). Formal concept analysis : mathematical foundations . Springer Science & Business Media.

15. Godin , R. , & Mili , H. ( 1993 , September) . Building and maintaining analysis-level class hierarchies using galois lattices . In OOPSLA (Vol. 93 , pp. 394 - 410 ).

16. Berry , A. , Gutierrez , A. , Huchard , M. , Napoli , A. , & Sigayret , A. ( 2014 ). Hermes: a simple and eficient algorithm for building the AOC-poset of a binary relation . Annals of Mathematics and Artificial Intelligence , 72 ( 1-2 ), 45 - 71 .

17. Porter , M. F. ( 1980 ). An algorithm for sufix stripping . Program , 14 ( 3 ), 130 - 137 .

18. Zhao , M. , & Zhang , S. ( 2016 , October) . Identifying and validating ontology mappings by formal concept analysis . In OM@ ISWC (pp. 61 - 72 ).

19. Zhao , M. , Zhang , S. , Li , W. , & Chen , G. ( 2018 ). Matching biomedical ontologies based on formal concept analysis . Journal of biomedical semantics , 9 ( 1 ), 11 .

20. Chen , G. , & Zhang , S. ( 2018 , December). FCAMapX results for OAEI 2018 . In Ontology Matching: OM-2018 : Proceedings of the ISWC Workshop (p. 160 ).

21. Xiang , C. , Jiang , T. , Chang , B. , & Sui , Z. ( 2015 ). Ersom: A structural ontology matching approach using automatically learned entity representation . In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (pp. 2419 - 2429 ).

22. Kolyvakis , P. , Kalousis , A. , & Kiritsis , D. ( 2018 , June). Deepalignment: Unsupervised ontology matching with refined word vectors . In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies , Volume 1 ( Long Papers) (pp. 787 - 798 ).

23. Kolyvakis , P. , Kalousis , A. , Smith , B. , & Kiritsis , D. ( 2018 ). Biomedical ontology alignment: an approach based on representation learning . Journal of biomedical semantics , 9 ( 1 ), 21 .