# SumMER: Structural Summarization for RDF/S KGs
## 3 Preliminaries  
In this paper we consider RDF/S KGs. Representation of data in RDF is based on three disjoint and infinite sets of resources, namely: URIs (\(U\)), literals (\(L\)) and blank nodes (\(B\)). We impose typing on resources, so we consider 3 disjoint sets of resources: classes (\(\mathbf{C}\subseteq U\cup B\)), properties (\(\mathbf{P}\subseteq U\)), and individuals (\(\mathbf{I}\subseteq U\cup B\)). The set \(\mathbf{C}\) includes all classes, including RDFS classes and XML datatypes (e.g., _xsd:string_, _xsd:integer_). The set \(\mathbf{P}\) includes all properties, except _rd:type_, which connects individuals with the classes they are instantiated under. The set \(\mathbf{I}\) includes all individuals, but not literals. In addition, we should note that our approach adopts the unique name assumption, i.e., that resources that are identified by different URIs are different.  
As commonly done in other works [1], we separate between the schema and instances of an RDF/S KGs, represented in separate graphs (\(G_{S}\), \(G_{I}\), respectively). The schema graph contains all classes and the properties they are associated with. Multiple domains/ranges per property are allowed, by having the property URI be a label on the edge (via a labelling function \(\lambda\)) rather than the edge itself. On the other hand, the instance graph contains all individuals, and the instantiations of schema properties. The labelling function \(\lambda\) applies here as well for the same reasons. The instance and the schema graphs are related via the function \(\tau_{c}\), which determines in which class(es) each individual is instantiated under. Formally:  
**Definition 1**.: **(RDF/S KGs)** _An RDF/S KGs is a tuple \(V=\langle G_{S}\), \(G_{I}\), \(\lambda\), \(\tau_{c}\rangle\), where:_  
* \(G_{S}\) _is a labelled directed graph_ \(G_{S}=(V_{S}\)_,_ \(E_{S})\) _such that_ \(V_{S}\)_,_ \(E_{S}\) _are the nodes and edges of_ \(G_{S}\)_, respectively, and_ \(\mathit{vs.}\subseteq\mathbf{C}\cup L\)__
* \(G_{I}\) _is a labelled directed graph_ \(G_{I}=(V_{I}\)_,_ \(E_{I})\) _such that_ \(V_{I}\)_,_ \(E_{I}\) _are the nodes and edges of_ \(G_{I}\)_, respectively, and_ \(V_{I}\subseteq\mathbf{I}\cup L\)_._
* _A labelling function_ \(\lambda\)_:_ \(E_{S}\cup E_{I}{\rightarrow}2^{P}\) _determines the property URI that each edge corresponds to (properties with multiple domains/ranges may appear in more than one edge)--_\(2^{P}\) _the powerset of P._
* _A function_ \(\tau_{c}\)_:_ \(\mathbf{I}{\rightarrow}2^{C}\) _associating each individual with the classes that it is instantiated under._  
For simplicity, we forego extra requirements related to RDFS inference (subsumption, instantiation) and validity (e.g., that the source and target of property instances should be instantiated under the property's domain/range, respectively), because these are not relevant for our results below and would significantly complicate our definitions. We denote by \(p(v_{1}\), \(v_{2})\) an edge \(e\in G_{S}\) (where \(v_{1}\), \(v_{2}\in V_{S}\)) or \(G_{I}\) (where \(v_{1}\), \(v_{2}\in V_{I}\)) from node \(v_{1}\) to node \(v_{2}\) such that \(\lambda(e)=p  
unless stated otherwise. This is to ensure that the result will be the same, independent of the number of inferences applied an input schema graph \(G_{S}\).  
Furthermore, we assume for our input KGs that all instances are fully described by the schema graph. If this is not the case, we assume that a schema discovery tool is able to effectively infer it. In our case we used HInT [12], our state-of-the-art schema discovery tool, for efficiently and effectively completing the existing schema graphs.  
**Example 1**.: _Consider the DBpedia v3.8 which is shown in Figure 1a. Understanding the contents of the schema is difficult due to the numerous nodes available in the DBpedia schema graph. However, having a mechanism helping us to focus only on the most important subgraph it would allow us to get a quick overview of the contents of the KG. An example such summary is shown in Figure 1b._