Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> Abstract It is a known problem that state spaces can grow very big, which makes operating with them (including reducing them) difficult because of memory shortage. In the attempt to extend the size of the state spaces that can be dealt with, we designed and implemented a bisimulation reduction algorithm for distributed memory settings using message passing communication. By using message passing, the same implementation can be used on both large SMP machines and clusters of workstations. The algorithm performs reduction of large labeled transition systems modulo strong bisimulation. We justify its correctness and termination. We provide an evaluation of the worst-case time and message complexity and some performance data from a prototype implementation. Both theory and practice show that the algorithm scales up with the number of workers. <s> BIB001 </s> Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> One of the reasons for the slow adoption of SPARQL is the complexity in query formulation due to data diversity. The principal barrier a user faces when trying to formulate a query is that he generally has no information about the underlying structure and vocabulary of the data. In this paper, we address this problem at the maximum scale we can think of: providing assistance in formulating SPARQL queries over the entire Sindice data collection - 15 billion triples and counting coming from more than 300K datasets. We present a method to help users in formulating complex SPARQL queries across multiple heterogeneous data sources. Even if the structure and vocabulary of the data sources are unknown to the user, the user is able to quickly and easily formulate his queries. Our method is based on a summary of the data graph and assists the user during an interactive query formulation by recommending possible structural query elements. <s> BIB002 </s> Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> It is common to find graphs with millions of nodes and billions of edges in, e.g., social networks. Queries on such graphs are often prohibitively expensive. These motivate us to propose query preserving graph compression, to compress graphs relative to a class Λ of queries of users' choice. We compute a small Gr from a graph G such that (a) for any query Q E Λ Q, Q(G) = Q'(Gr), where Q' E Λ can be efficiently computed from Q; and (b) any algorithm for computing Q(G) can be directly applied to evaluating Q' on Gr as is. That is, while we cannot lower the complexity of evaluating graph queries, we reduce data graphs while preserving the answers to all the queries in Λ. To verify the effectiveness of this approach, (1) we develop compression strategies for two classes of queries: reachability and graph pattern queries via (bounded) simulation. We show that graphs can be efficiently compressed via a reachability equivalence relation and graph bisimulation, respectively, while reserving query answers. (2) We provide techniques for aintaining compressed graph Gr in response to changes ΔG to the original graph G. We show that the incremental maintenance problems are unbounded for the two lasses of queries, i.e., their costs are not a function of the size of ΔG and changes in Gr. Nevertheless, we develop incremental algorithms that depend only on ΔG and Gr, independent of G, i.e., we do not have to decompress Gr to propagate the changes. (3) Using real-life data, we experimentally verify that our compression techniques could reduce graphs in average by 95% for reachability and 57% for graph pattern matching, and that our incremental maintenance algorithms are efficient. <s> BIB003 </s> Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> Semantic mining is a research area that sprung up in the last decade. With the explosively growth of Linked Data, instance-focused Semantic Mining technologies now face the challenge of mining efficiency. In our observation, graph compression strategies can effectively reduce the redundant or dependent structures in Linked Data, thus can help to improve mining efficiency. In this paper, we first describe Typed Object Graph as a generic data model for instance-focused Semantic Mining; and then we propose two graph compression strategies for Linked Data: Equivalent Compression and Dependent Compression, each of which is demonstrated in specific mining scenarios. Experiments on real Linked Data show that graph compression strategies in Semantic Mining is feasible and effective for reducing the volume of Linked Data to improve mining efficiency. <s> BIB004 </s> Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> RDF is considered to be an important data model for Semantic Web as a labeled directed graph. Querying in massive RDF graph data is known to be hard. In order to reduce the data size, we present ASSG, an Adaptive Structural Summary for RDF Graph data by bisimulations between nodes. ASSG compresses only the part of the graph related to queries. Thus ASSG contains less nodes and edges than existing work. More importantly, ASSG has the adaptive ability to adjust its structure according to the updating query graphs. Experimental results show that ASSG can reduce graph data with the ratio 85% in average, higher than that of existing work. <s> BIB005 </s> Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> The Resource Description Framework (RDF) is a graph-based data model promoted by the W3C as the standard for Semantic Web applications. Its associated query language is SPARQL. RDF graphs are often large and varied, produced in a variety of contexts, e.g., scientific applications, social or online media, government data etc. They are heterogeneous, i.e., resources described in an RDF graph may have very different sets of properties. An RDF resource may have: no types, one or several types (which may or may not be related to each other). RDF Schema (RDFS) information may optionally be attached to an RDF graph, to enhance the description of its resources. Such statements also entail that in an RDF graph, some data is implicit. According to the W3C RDF and SPARQL specification, the semantics of an RDF graph comprises both its explicit and implicit data; in particular, SPARQL query answers must be computed reflecting both the explicit and implicit data. These features make RDF graphs complex, both structurally and conceptually. It is intrinsically hard to get familiar with a new RDF dataset, especially if an RDF schema is sparse or not available at all. <s> BIB006 </s> Summarizing semantic graphs: a survey <s> Other structural quotient summaries <s> Large data graphs with complex and heterogeneous structure, possibly featuring typed data and an ontol- ogy encoding the application-domain semantics, are widely used nowadays. The literature provides many solutions for building succinct representations of graphs, called summaries, in particular based on graph quotients through an equivalence relation between graph nodes. ::: We consider efficient and compact summarization of rich heterogeneous graphs, in particular RDF ones, which may feature data edges, typed nodes, and an ontology. First, we devise new graph node equivalence relations, particularly tolerant of structural heterogeneity; they lead to compact yet informative quotient summaries. Second, we show how to extend any node equivalence relation (including, but not limited to ours) to types and ontologies, and provide the first in-depth study of the interplay between quotient sum- marization and RDF graph saturation, which defines the semantics of an RDF graph, in particular in the presence of an ontology. We establish a sufficient condition on a node equivalence relation, which if met allows an efficient method, called shortcut, for summarizing RDF graphs. We describe novel, efficient, incremental algorithms for summarizing graphs with our node equivalence relations, and experiments validating their performance. <s> BIB007
To assist users whose task is query formulation, Campinas et al. BIB002 creates the summary graph, the so-called node collection layer, by grouping nodes having the exact same types, or in the absence of types, the same outgoing properties, into entity nodes; further, nodes from the input with no outgoing properties, and having the same incoming properties from subjects with the same set of types, are represented by blank nodes (Fig. 6 ). An edge exists between two summary nodes v 1 and v 2 , labeled by a property p, if there exist two nodes v 1 and v 2 in G, such that v 1 is represented by v 1 , v 2 is represented by v 2 , and there exists an edge labeled by p in G from v 1 to v 2 . The number of represented nodes from the input is attached to each summary node, and the number of represented edges from the input to each summary edge. This summary graph may group resources from multiple datasets. The proposed dataset layer groups together nodes of the node collection layer which belong to the same dataset. Schema triples are not considered. The approach bears similarities with ExpLOD, since nodes in the first layer are partitioned by types, and partitions are represented by distinct summary nodes. However, unlike ExpLOD, the G nodes having a type are not further distinguished by their data properties, i.e., two nodes of the same type A, one having the data properties a, b and c and the other having the properties a and d will be represented by the same summary node. Unlike ExpLOD, their summary graph is an RDF graph. RDF summaries are defined in a rather restricted setting in BIB004 . The authors assume that all subjects and objects are typed, and that each has exactly one type; class and property URIs are not allowed in subject and object position, and no usage is made of possible schema triples. Under this hypothesis, they construct from the RDF graph a typed object graph (TOG) comprising (s, p, o) triples and assigning an RDF type for each such s and o. Two methods are proposed for summarizing the TOG, namely, equivalent compression and dependent compression. The equivalent compression produces a quotient of the TOG by grouping together nodes having the same type and the same set of labels on the edges adjacent to the node. In the dependent compression, two nodes v 1 and v 2 of the TOG are grouped together if v 1 is adjacent only to v 2 , or vice-versa. As application scenarios of this approach the authors indicate mining semantic associations, usually defined as graph or path structures representing group relationships among several instances. Based on query-preserving graph compression BIB003 (Sect. 4.1.2), an Adaptive Structural Summary for RDF graphs (ASSG, in short) is introduced in BIB005 . ASSG aims at building compressed summaries of the part of an RDF graph which is concerned by a certain set of queries. The authors compute a structural rank of nodes, which is 0 for leaves, and grows with the shortest distance between the node and a leaf; then, nodes having the same label and the same rank are considered equivalent, and are all compressed together in a single ASSG node. To partition the N nodes of a graph G to different equivalent classes by their label and rank the cost is O (N + M) , where M the number of the edges of the graph. RDF summaries defined in BIB007 BIB006 BIB006 adapt the idea of quotient summaries to two characteristic features of RDF graphs: (i) the presence of type triples (zero, one, or any number of types for a given resource), and (ii) the presence of schema triples. As we explained in Sect. 2.1, RDF Schema information is also expressed by means of triples, which are part of G. BIB007 shows that quotient summarization of schema triples does more harm than good, as it destroys the semantics of the original graph. To address this, they introduce a notion of RDF node equivalence which ensures that class and prop-erty nodes (part of schema triples) are not equivalent to any other G nodes, and define a summary as the quotient of G through one such RDF node equivalence. Such summaries are shown to preserve the RDF Schema triples intact, and to enjoy representativeness (Definition 4) for BGP queries having variables in all subject and object positions. The authors show how bisimulation summaries can be cast in this framework, and introduce four novel summaries based property cliques, which generalize property co-occurrence as follows. A clique c G is a set of data properties from G such that for any p 1 , p 2 ∈ c G , a resource of G is the source and/or target of both p 1 and p 2 . For instance, if resource r 1 has properties a and b, while r 2 has b and c, then a, b, c are part of the same source clique; if, instead, r 1 and r 2 are targets of these properties, then a, b, c are part of the same target clique. The so-called weak summary groups together nodes having the same source or target clique, while the strong summary requires the same source and the same target clique; their variant typed-weak and typed-strong summaries first group nodes according to their types, and then according to their cliques. All these summaries can be computed in linear time in the size of the input graph. A benefit of this specific approach is that clique summaries are orders of magnitude more compact than bisimulation summaries. The authors also study how to obtain the summary of G's semantics, which is the saturation of G. They provide a sufficient condition on the RDF equivalence relation, ensuring that the summary of G ∞ can be computed from G without saturating it, and show that this may be many times faster than the direct procedure of first saturating G, then summarizing G ∞ . The software tool implementing this approach is available as open source. BIB001 