Projects per year
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 graphbased output. We consider approaches and algorithms for both static and temporal graphs. A common example of quotientbased 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 language  English 

Journal  Transactions on Graph Data and Knowledge 
Volume  1 
Issue number  1 
State  Published  Dec 1 2023 
Externally published  Yes 
Fingerprint
Dive into the research topics of 'Structural Summarization of Semantic Graphs Using Quotients'. Together they form a unique fingerprint.Projects
 1 Active

DL: ICAI Discovery Lab
van Harmelen, F. (CoPI), De Rijke, M. (CoI), Siebert, M. (CoI), Hoekstra, R. (CoPI), Tsatsaronis, G. (CoPI), Groth, P. (CoPI), Cochez, M. (CoI), Pernisch, R. (CoI), Alivanistos, D. (CoI), Mansoury, M. (CoI), van Hoof, H. (CoI), Pal, V. (CoI), Pijnenburg, T. (CoI), Mitra, P. (CoI), Bey, T. (CoI) & de Waard, A. (CoPI)
10/1/19 → 03/31/25
Project: Research