Compact Summaries of Rich Heterogeneous Graphs

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.Les grands graphes de données, à structure potentiellement complexe et hétérogène, com- prenant parfois des noeuds typés et/ou une ontologie décrivant la sémantique d’un domaine d’application, sont utilisés largement de nos jours. Des nombreuses méthodes pour résumer de tels graphes ont été pro- posées; chacune aboutit à une structure compacte représentant l’essentiel de l’information sur la structure du graphe. Une famille de telles méthodes est basée sur la construction d’un graphe quotient, à partir d’une relation d’équivalence entre les noeuds du graphe d’origine.Dans ce travail, nous nous intéressons à la construction efficace de résumés compacts pour des graphes de données hétérogènes, en particulier des graphes RDF, qui peuvent comporter des données, des noeuds typés, et une ontologie. Nous proposons de nouvelles relations d’équivalence entre les noeuds d’un graphes, relations particulièrement adaptées à la hétérogénéité souvent rencontrée dans des graphes RDF. Ces relations conduisent à des résumés quotients qui sont compacts, tout en préservant de l’information sur la structure du graphe. Nous montrons comment tout relation d’équivalence entre les noeuds d’un graphe (comprenant, mais ne se limitant pas aux relations que nous introduisons) peut être étendue aux noeuds comportant des types, ainsi qu’aux ontologies. Par la suite, nous présentons la première étude approfondie de l’interaction entre les résumés par quotient et la saturation d’un graphe RDF, qui définit sa sémantique en présence d’une ontologie. Nous identifions une condition suffisante sur une relation d’équivalence entre des noeuds du graphe, condition qui, lorsqu’elle est satisfaite, conduit à une méthode rapide, appellée shortcut (raccourci) pour la construction du résumé d’un graphe RDF. Nous présentons des nouveaux algorithmes efficace, en particulier des algorithmes incrémentaux, pour résumer des graphes par nos nouvelles relations d’équivalence. Enfin, nous présentons des expériences qui valide la performance de nos algorithmes et l’intérêt des résumés étudiés