SUBMASSIVE: Resolving Subclass Cycles in Very Large Knowledge Graphs
Shuai Wang, Peter Bloem, Joe Raad, Frank van Harmelen · 2024
Read SUBMASSIVE: Resolving Subclass Cycles in Very Large Knowledge Graphs by Shuai Wang, Peter Bloem, Joe Raad, Frank van Harmelen (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15829.txt.
Introduction
Shuai Wang, Peter Bloem, Joe Raad, and Frank van Harmelen present SUBMASSIVE, an automatic method for repairing cyclic subclass relations in very large knowledge graphs. Knowledge graphs record class subsumption with subclass-of assertions. Publicly available graphs, the authors found, contain many potentially erroneous cycles in those assertions, a problem worsened when graphs are integrated as linked open data.
Their approach encodes the cycle-resolving problem for a MAXSAT solver, letting automated reasoning choose which triples to remove. It is tested on the LOD-a-lot dataset and compared against a semi-automatic version of the same algorithm. The comparison exposes a trade-off: the number of removed triples balances against the efficiency of the algorithm. Cleaning subclass cycles matters because reasoners drawing inferences over a cyclic hierarchy can derive nonsense. SUBMASSIVE offers a scalable way to keep integrated knowledge graphs logically usable.
Catalog record
| CREATOR | Shuai Wang, Peter Bloem, Joe Raad, Frank van Harmelen |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15829
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SUBMASSIVE: Resolving Subclass Cycles in Very Large Knowledge Graphs Shuai Wang, Peter Bloem, Joe Raad, Frank van Harmelen Abstract Large knowledge graphs capture information of a large number of entities and their relations. Among the many relations they capture, class subsumption assertions are usually present and expressed using the rdfs:subClassOf construct. From our examination, publicly available knowledge graphs contain many potentially erroneous cyclic subclass relations, a problem that can be exacerbated when different knowledge graphs are integrated as Linked Open Data. In this paper, we present an automatic approach for resolving such cycles at scale using automated reasoning by encoding the problem of cycle-resolving to a MAXSAT solver. The approach is tested on the LOD-a-lot dataset, and compared against a semi-automatic version of our algorithm. We show how the number of removed triples is a trade-off against the efficiency of the algorithm. 1 1 1 The paper has been presented at the 2020 workshop on Large Scale RDF Analytics (LASCAR), a workshop co-located with the Extended Semantic Web Conference (ESWC). The code, raw data, related intermediate results, and plotting scripts can be found on GitHub at https://github.com/MaestroGraph/SUBMASSIVE and Zenodo with DOI 10.5281/zenodo.14535281 . The resulting refined cycle-free subclass and subproperty subsumption relations are available on Zenodo with DOI 10.5281/zenodo.3693802 . 1 Introduction Among the many relations knowledge graphs capture, subsumption relations on classes are represented as triples of axioms using rdfs:subClassOf . Ideally, such triples form a structure of hierarchy, a.k.a. a directed acyclic graph (DAG), if not considering reflexive relations. From our research, not all knowledge graphs have such an acyclic class taxonomy. In the case of very large knowledge graphs, integrating information from different sources, the cyclic relations from integrated small knowledge graphs are inherited and there is potentially erroneous cyclic information across different domains. Only when given a cycle-free subclass hierarchy, can we obtain a reliable subclass transitive closure of an entity. It is required for the evaluation of the accuracy of transitive relations regarding different knowledge graph embeddings. This paper focuses on resolving potentially erroneous cyclic relations in the aim of obtaining a reliable cycle-free hierarchy with a minimum number of removed relations. In Section 1 , we first study some properties of cyclic subclass assertions (Section 1.1 ) and present related work (Section 1.2 ). Section 2 describes our algorithm for removing potentially erroneous cycles, followed by its implementation details. Finally we evaluate our system and present results in Section 3 followed by a discussion and our plan for future work in Section 4 . 1.1 Preliminaries A knowledge graph (KG) G consists of triples of relational information on entities. Such triples are in the form of (s,p,o) , where s is an entity called the subject , p is a predicate, and o is an entity called the object . A relation such as class A is a subclass of class B ( A\sqsubseteq B ) is encoded as (A, rdfs:subClassOf , B). From a graph theory point of view, these triples form a directed multigraph with self-loops (a.k.a. reflexive relations). When studying those triples where p is restricted to rdfs:subClassOf, the subgraph G_{\text{cat}} is solely about the subsumption relations on classes. Cyclic class relations come in the form A\sqsubseteq A (a reflexive relation; self-loop), or A\sqsubseteq B and B\sqsubseteq A (size two), or more generally A_{1}\sqsubseteq A_{2}\sqsubseteq\ldots\sqsubseteq A_{N}\sqsubseteq A_{1} (size N). Such cycles can be harmless. For example, reflexive cycles are simply tautologies (always true) and are therefore redundant. There are four possible inclusion relations between two classes A and B : A\sqsubseteq B , B\sqsubseteq A , A\equiv B ( A\sqsubseteq B and B\sqsubseteq A ), or none of them (including the case of unknown). Due to the transitivity, cycles are only correct when all classes in the cycle are equivalent, otherwise they represent a source of error. In this paper, we use a hybrid approach of logical and network/graph theory methods. To avoid confusion, we clarify the terminology: we use relation interchangeably with edge and triple; we let class to be the same as node and concept ; we use graph for knowledge graph or knowledge base . Similarly, we use cycle in reference to cyclic subclass assertions . 1.2 Related Work According to [ 1 ] , knowledge graph refinement methods can be divided into two main categories: completing the knowledge graph with missing knowledge, and identifying wrongly asserted information. This work falls into the latter category of approaches, as we attempt to resolve cyclic subclass relations by removing potentially incorrect relations. To the best of our knowledge, this is the first work that specifically focuses on detecting incorrect rdfs:subClassOf relations in large knowledge graphs. In contrast with other types of relations, finding such erroneous class subsumption assertions has attracted less attention, possibly due to the fact that the creation of such assertions is rarely automated, and hence are less prone to error. Focusing on other types of relations, Ma el al. [ 2 ] proposed a method for detecting wrong type assertions by relying on disjointness axioms which they lean using inductive logic programming. Paulheim and Bizer [ 3 ] proposed a statistical method for finding erroneous statements for each type of relation by identifying edges whose subject and object type strongly deviate from the characteristic distribution. The largest amount of work on knowledge graph refinement have focused on detecting erroneous equivalence and identity relations. In this family of approaches, various kinds of information have been exploited to identify erroneous statements, such as the description related to the linked resources [ 4 , 5 ] , domain knowledge that is included in the ontology or obtained from experts [ 6 , 7 ] , and different network metrics [ 8 , 9 ] . 2 Algorithm The algorithm consists of two parts: data pre-processing as in Section 2.1 and the automated refinement as in Section 2.2 . Implementation details are included in Section 2.3 . 2.1 Data Pre-processing The subgraph G_{\text{cat}} is a collection of all the triples in the form (s, rdfs:subClassOf , o). For the sake of efficiency, those classes without any subclasses (leaf nodes) are temporally removed, since by definition they can not be part of any cycle. We further remove all reflexive relations since they form trivial self-cycles. Both of these operations can be done in linear time regarding the number of nodes. In addition, we make use of existing equivalence and identity relations to make direct decisions regarding certain subsumption relations. Specifically, we remove all rdfs:subClassOf statements between s and o (as unnecessary relations) when there is an explicit assertion of owl:equivalentClass or the transitive closure of owl:sameAs . 2.2 Automated Cycle-resolving We resolve the cycles iteratively from local neighbourhoods to cross-domain cycles and eventually ensure the entire knowledge graph is cycle-free. This implies that the amount of edges we remove is not minimal but an approximation to it. In each iteration, there are two steps: obtain a small subgraph within which we detect the cycles, which we then encode in a MAXSAT solver which makes decision about which relations to remove. We repeat this process until there is no cycle in the entire graph, or until processing time runs out. This gives us