research-article

Open access

Fast Computation of Explanations for Inconsistency in Large-Scale Knowledge Graphs

Authors:

Trung-Kien Tran,

Mohamed H. Gad-Elrab,

Daria Stepanova,

Evgeny Kharlamov,

Jannik StrötgenAuthors Info & Claims

WWW '20: Proceedings of The Web Conference 2020

Pages 2613 - 2619

https://doi.org/10.1145/3366423.3380014

Published: 20 April 2020 Publication History

All formats PDF

Abstract

Knowledge graphs (KGs) are essential resources for many applications including Web search and question answering. As KGs are often automatically constructed, they may contain incorrect facts. Detecting them is a crucial, yet extremely expensive task. Prominent solutions detect and explain inconsistency in KGs with respect to accompanying ontologies that describe the KG domain of interest. Compared to machine learning methods they are more reliable and human-interpretable but scale poorly on large KGs. In this paper, we present a novel approach to dramatically speed up the process of detecting and explaining inconsistency in large KGs by exploiting KG abstractions that capture prominent data patterns. Though much smaller, KG abstractions preserve inconsistency and their explanations. Our experiments with large KGs (e.g., DBpedia and Yago) demonstrate the feasibility of our approach and show that it significantly outperforms the popular baseline.

References

[1]

Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. 2016. Query-Driven Repairing of Inconsistent DL-Lite Knowledge Bases. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016. 957–964.

[2]

Stefan Bischof, Markus Krötzsch, Axel Polleres, and Sebastian Rudolph. 2014. Schema-Agnostic Query Rewriting in SPARQL 1.1. In The Semantic Web - ISWC 2014 - 13th International Semantic Web Conference, Riva del Garda, Italy, October 19-23, 2014. Proceedings, Part I. 584–600.

[3]

Kurt D. Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008. 1247–1250.

Digital Library

[4]

Julian Dolby, Achille Fokoue, Aditya Kalyanpur, Edith Schonberg, and Kavitha Srinivas. 2009. Scalable highly expressive reasoner (SHER). J. Web Semantics (2009).

[5]

Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. 2014. Knowledge vault: a web-scale approach to probabilistic knowledge fusion. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014. 601–610.

Digital Library

[6]

David A. Ferrucci, Eric W. Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya Kalyanpur, Adam Lally, J. William Murdock, Eric Nyberg, John M. Prager, Nico Schlaefer, and Christopher A. Welty. 2010. Building Watson: An Overview of the DeepQA Project. AI Magazine 31, 3 (2010), 59–79.

Digital Library

[7]

Mohamed H. Gad-Elrab, Daria Stepanova, Jacopo Urbani, and Gerhard Weikum. 2019. ExFaKT: A Framework for Explaining Facts over Knowledge Graphs and Text. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining(WSDM ’19). 87–95.

Digital Library

[8]

Birte Glimm, Ian Horrocks, Boris Motik, Giorgos Stoilos, and Zhe Wang. 2014. HermiT: An OWL 2 Reasoner. J. Autom. Reasoning 53, 3 (2014), 245–269.

Digital Library

[9]

Birte Glimm, Yevgeny Kazakov, Thorsten Liebig, Trung-Kien Tran, and Vincent Vialard. 2014. Abstraction Refinement for Ontology Materialization. In The Semantic Web – ISWC 2014. Springer, 180–195.

Digital Library

[10]

Birte Glimm, Yevgeny Kazakov, and Trung-Kien Tran. 2016. Scalable Reasoning by Abstraction Beyond DL-Lite. In Web Reasoning and Rule Systems. Springer, 77–93.

[11]

Birte Glimm, Yevgeny Kazakov, and Trung-Kien Tran. 2017. Ontology Materialization by Abstraction Refinement in Horn SHOIF. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (San Francisco, California, USA) (AAAI’17). AAAI Press, 1114–1120.

Digital Library

[12]

Stefan Heindorf, Martin Potthast, Benno Stein, and Gregor Engels. 2016. Vandalism Detection in Wikidata. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016. 327–336.

Digital Library

[13]

Matthew Horridge, Bijan Parsia, and Ulrike Sattler. 2009. Explaining Inconsistencies in OWL Ontologies. In Scalable Uncertainty Management. Springer, Berlin, Heidelberg, 124–137.

[14]

Ian Horrocks. 2008. Ontologies and the semantic web. Commun. ACM 51, 12 (2008), 58–67.

Digital Library

[15]

Shengbin Jia, Yang Xiang, Xiaojun Chen, Kun Wang, and Shijia E. 2019. Triple Trustworthiness Measurement for Knowledge Graph. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019. 2865–2871.

[16]

Holger Knublauch and Dimitris Kontokostas. 2017. Shapes constraint language (SHACL). Technical Report. W3C. https://www.w3.org/TR/shacl/

[17]

Dimitris Kontokostas, Patrick Westphal, Sören Auer, Sebastian Hellmann, Jens Lehmann, Roland Cornelissen, and Amrapali Zaveri. 2014. Test-driven evaluation of linked data quality. In 23rd International World Wide Web Conference, WWW ’14, Seoul, Republic of Korea, April 7-11, 2014. 747–758.

Digital Library

[18]

Freddy Lécué and Jeff Z. Pan. 2015. Consistent Knowledge Discovery from Evolving Ontologies. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA.189–195.

Digital Library

[19]

Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. 2015. DBpedia - A large-scale, multilingual knowledge base extracted from Wikipedia. Semantic Web 6(2015), 167–195.

[20]

Jiaqing Liang, Yanghua Xiao, Yi Zhang, Seung-won Hwang, and Haixun Wang. 2017. Graph-Based Wrong IsA Relation Detection in a Large-Scale Lexical Taxonomy. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA.1178–1184.

Digital Library

[21]

Yanfang Ma, Huan Gao, Tianxing Wu, and Guilin Qi. 2014. Learning Disjointness Axioms With Association Rule Mining and Its Application to Inconsistency Detection of Linked Data. In The Semantic Web and Web Science - 8th Chinese Conference, CSWS 2014, Wuhan, China, August 8-12. 29–41.

[22]

André Melo and Heiko Paulheim. 2017. Detection of Relation Assertion Errors in Knowledge Graphs. In Proceedings of the Knowledge Capture Conference, K-CAP 2017, Austin, TX, USA, December 4-6, 2017. 22:1–22:8.

Digital Library

[23]

T. Mitchell, W. Cohen, E. Hruschka, P. Talukdar, J. Betteridge, A. Carlson, B. Dalvi, M. Gardner, B. Kisiel, J. Krishnamurthy, N. Lao, K. Mazaitis, T. Mohamed, N. Nakashole, E. Platanios, A. Ritter, M. Samadi, B. Settles, R. Wang, D. Wijaya, A. Gupta, X. Chen, A. Saparov, M. Greaves, and J. Welling. 2015. Never-Ending Learning. In Proc. of AAAI. 2302–2310.

[24]

Boris Motik, Peter F. Patel-Schneider, and Bernardo Cuenca Grau. 2012. OWL 2 Web Ontology Language Direct Semantics (Second Edition). Technical Report. https://www.w3.org/TR/owl-direct-semantics/

[25]

Ndapandula Nakashole, Mauro Sozio, Fabian M. Suchanek, and Martin Theobald. 2012. Query-Time Reasoning in Uncertain RDF Knowledge Bases with Soft and Hard Rules. In Proceedings of the Second International Workshop on Searching and Integrating New Web Data Sources, Istanbul, Turkey, August 31, 2012. 15–20.

[26]

Heiko Paulheim. 2017. Knowledge graph refinement: A survey of approaches and evaluation methods. Semantic Web 8, 3 (2017), 489–508.

Digital Library

[27]

Heiko Paulheim and Christian Bizer. 2014. Improving the Quality of Linked Data Using Statistical Distributions. Int. J. Semantic Web Information Systems 10, 2 (2014), 63–86.

Digital Library

[28]

Heiko Paulheim and Aldo Gangemi. 2015. Serving DBpedia with DOLCE – More than Just Adding a Cherry on Top. In The Semantic Web - ISWC 2015. Springer, 180–196.

Digital Library

[29]

Evren Sirin, Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and Yarden Katz. 2007. Pellet: A practical OWL-DL reasoner. J. Web Semant. 5, 2 (2007).

Digital Library

[30]

Martin G. Skjæveland, Espen H. Lian, and Ian Horrocks. 2013. Publishing the Norwegian Petroleum Directorate’s FactPages as Semantic Web Data. In The Semantic Web – ISWC 2013, Harith Alani, Lalana Kagal, Achille Fokoue, Paul Groth, Chris Biemann, Josiane Xavier Parreira, Lora Aroyo, Natasha Noy, Chris Welty, and Krzysztof Janowicz (Eds.). 162–177.

Digital Library

[31]

Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007. Yago: A Core of Semantic Knowledge. In Proc. of WWW. 697–706.

Digital Library

[32]

Thomas Pellissier Tanon, Camille Bourgaux, and Fabian M. Suchanek. 2019. Learning How to Correct a Knowledge Base from the Edit History. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019. 1465–1475.

Digital Library

[33]

Andrei Voronkov. 2006. Inconsistencies in Ontologies. In JELIA(Lecture Notes in Computer Science), Vol. 4160. Springer, 19.

[34]

Denny Vrandecic and Markus Krötzsch. 2014. Wikidata: a free collaborative knowledge base. CACM 57, 10 (2014), 78–85.

Digital Library

[35]

Sebastian Wandelt and Ralf Möller. 2012. Towards ABox Modularization of semi-expressive Description Logics. Applied Ontology 7, 2 (2012).

[36]

Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. 2017. Knowledge Graph Embedding: A Survey of Approaches and Applications. IEEE Trans. Knowl. Data Eng. 29, 12 (2017), 2724–2743.

[37]

Jiewen Wu and Freddy Lécué. 2014. Towards Consistency Checking over Evolving Ontologies. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, CIKM 2014, Shanghai, China, November 3-7, 2014. 909–918.

Digital Library

Cited By

Schatz KTropsha AChirkova R(2023)GAME: Improving Efficiency and Effectiveness of Knowledge-Graph Rule Mining via Data Reduction2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386384(4248-4257)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386384
Rincon-Yanez DGad-Elrab MStepanova DTran KChu Xuan CZhou BKarlamov E(2023)Addressing the Scalability Bottleneck of Semantic Technologies at BoschThe Semantic Web: ESWC 2023 Satellite Events10.1007/978-3-031-43458-7_33(177-181)Online publication date: 21-Oct-2023
https://doi.org/10.1007/978-3-031-43458-7_33
Xue BZou L(2022)Knowledge Graph Quality Management: a Comprehensive SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3150080(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3150080
Show More Cited By

Index Terms

Fast Computation of Explanations for Inconsistency in Large-Scale Knowledge Graphs

Index terms have been assigned to the content through auto-classification.

Recommendations

Representation Learning of Large-Scale Knowledge Graphs via Entity Feature Combinations
CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

Knowledge graphs are typical large-scale multi-relational structures, which comprise a large amount of fact triplets. Nonetheless, existing knowledge graphs are still sparse and far from being complete. To refine the knowledge graphs, representation ...
Knowledge Graphs: An Information Retrieval Perspective

In this survey, we provide an overview of the literature on knowledge graphs (KGs) in the context of information retrieval (IR). Modern IR systems can benefit from information available in KGs in multiple ways, independent of whether the KGs are publicly ...
Building relatedness explanations from knowledge graphs
Knowledge Graphs: Construction, Management and Querying

Knowledge graphs (KGs) are a key ingredient to complement search results, discover entities and their relations and support several knowledge discovery tasks. We face the problem of building relatedness explanations, that is, graphs that can explain how a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '20: Proceedings of The Web Conference 2020

April 2020

3143 pages

ISBN:9781450370233

DOI:10.1145/3366423

Editors:
Yennun Huang
Acadmica sinica, Taiwan
,
Irwin King
The Chinese University of Hong Kong, Hong Kong
,
Tie-Yan Liu
Microsoft Research Asia, China
,
Maarten van Steen
University of Twente, Netherlands

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '20

Sponsor:

SIGWEB

WWW '20: The Web Conference 2020

April 20 - 24, 2020

Taipei, Taiwan

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
974
Total Downloads

Downloads (Last 12 months)197
Downloads (Last 6 weeks)44

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schatz KTropsha AChirkova R(2023)GAME: Improving Efficiency and Effectiveness of Knowledge-Graph Rule Mining via Data Reduction2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386384(4248-4257)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386384
Rincon-Yanez DGad-Elrab MStepanova DTran KChu Xuan CZhou BKarlamov E(2023)Addressing the Scalability Bottleneck of Semantic Technologies at BoschThe Semantic Web: ESWC 2023 Satellite Events10.1007/978-3-031-43458-7_33(177-181)Online publication date: 21-Oct-2023
https://doi.org/10.1007/978-3-031-43458-7_33
Xue BZou L(2022)Knowledge Graph Quality Management: a Comprehensive SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3150080(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3150080
Gomes Jde Mello RStröele Vde Souza J(2022)A study of approaches to answering complex questions over knowledge basesKnowledge and Information Systems10.1007/s10115-022-01737-x64:11(2849-2881)Online publication date: 20-Aug-2022
https://doi.org/10.1007/s10115-022-01737-x
Jain NTran TGad-Elrab MStepanova D(2021)Improving Knowledge Graph Embeddings with Ontological ReasoningThe Semantic Web – ISWC 202110.1007/978-3-030-88361-4_24(410-426)Online publication date: 30-Sep-2021
https://doi.org/10.1007/978-3-030-88361-4_24

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents