Structural Summarization of Semantic Graphs Using Quotients

Ansgar Scherp, David Richerby, Till Blume, Michael Cochez, Jannik Rau

Research output: Contribution to journalArticlepeer-review

Abstract

Graph summarization is the process of computing a compact version of an input graph while preserving chosen features of its structure. We consider semantic graphs where the features include edge labels and label sets associated with a vertex. Graph summaries are typically much smaller than the original graph. Applications that depend on the preserved features can perform their tasks on the summary, but much faster or with less memory overhead, while producing the same outcome as if they were applied on the original graph. In this survey, we focus on structural summaries based on quotients that organize vertices in equivalence classes of shared features. Structural summaries are particularly popular for semantic graphs and have the advantage of defining a precise graph-based output. We consider approaches and algorithms for both static and temporal graphs. A common example of quotient-based structural summaries is bisimulation, and we discuss this in detail. While there exist other surveys on graph summarization, to the best of our knowledge, we are the first to bring in a focused discussion on quotients, bisimulation, and their relation. Furthermore, structural summarization naturally connects well with formal logic due to the discrete structures considered. We complete the survey with a brief description of approaches beyond structural summaries.
Original languageEnglish
JournalTransactions on Graph Data and Knowledge
Volume1
Issue number1
StatePublished - Dec 1 2023
Externally publishedYes

Fingerprint

Dive into the research topics of 'Structural Summarization of Semantic Graphs Using Quotients'. Together they form a unique fingerprint.
  • DL: ICAI Discovery Lab

    van Harmelen, F., De Rijke, M., Siebert, M., Hoekstra, R., Tsatsaronis, G., Groth, P., Cochez, M., Pernisch, R., Alivanistos, D., Mansoury, M., van Hoof, H., Pal, V., Pijnenburg, T., Mitra, P., Bey, T. & de Waard, A.

    10/1/1903/31/25

    Project: Research

Cite this