Skip to Main content Skip to Navigation

Compact Summaries of Rich Heterogeneous Graphs

Šejla Čebirić 1, 2, 3 François Goasdoué 4, 1 Pawel Guzewicz 1, 2, 3 Ioana Manolescu 1, 2, 3
1 CEDAR - Rich Data Analytics at Cloud Scale
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
4 SHAMAN - Symbolic and Human-centric view of dAta MANagement
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Ioana Manolescu Connect in order to contact the contributor
Submitted on : Wednesday, July 4, 2018 - 10:53:07 AM
Last modification on : Tuesday, January 4, 2022 - 4:47:33 AM
Long-term archiving on: : Monday, October 1, 2018 - 11:52:24 AM


Files produced by the author(s)


  • HAL Id : hal-01325900, version 6


Šejla Čebirić, François Goasdoué, Pawel Guzewicz, Ioana Manolescu. Compact Summaries of Rich Heterogeneous Graphs. [Research Report] RR-8920, INRIA Saclay; Université Rennes 1. 2018, pp.1-40. ⟨hal-01325900v6⟩



Les métriques sont temporairement indisponibles