Structural Summarization of Semantic Graphs Using Quotients

We are agnostic to the specific representation of graphs. We use the umbrella term semantic graph for the kinds of graphs considered in this work. We assume that a graph is a collection of vertices connected by directed edges. The vertices and/or edges may be labeled and one may perform some semantic inference on them, e. g., generalizations and specializations [16].

We also refer to the value ${\mathrm{\ell }}_V(v)$ as the type set of a vertex, and we use the function ${\mathrm{\ell }}_E$ to define the property set of a vertex, which is defined over its outgoing edges. Some variants of graph summarization also consider incoming edges (we discuss these in Section 3).

A semantic graph may be represented as a Resource Description Framework (RDF) graph [24], labeled property graph (LPGs), or some other approach. RDF graphs do not directly support vertex labels, but rdf:type edges can be used to simulate these, so RDF graphs and LPGs can be transformed into one another [8]. A comprehensive overview of different kinds of semantic graphs is given by Hogan et al. [48] under the term “Knowledge Graphs”. The term was coined in 2012 by Google as part of its knowledge representation and web search service extended by contextual knowledge such as mapping queries to persons, companies, etc.

Classical graph algorithms focus on finding structures such as shortest paths or minimum spanning trees, or invariants such as treewidth or chromatic number. In the context of graph-structured data, the focus of algorithms shifts from the graph per se to the data it represents. Typical tasks on such graphs include mere querying of the data, but also estimating cardinalities for queries in graph databases [77], subgraph-based indices for data search [59], data modeling recommendation [87], schema induction [99], data exploration [80], data visualization [41], and related entity retrieval [22].

The motivation for graph summaries lies in the growing size of semantic graphs. As the graphs can be extremely large, tasks become computationally expensive and might require a large amount of memory. Structural graph summaries have been developed as useful abstractions of large graphs to solve tasks more efficiently. A summary of a graph $G$ is a smaller graph $S$, which retains the information from $G$ that is required to perform the desired tasks, but which discards information that is not needed, and which may represent the retained information more compactly.

Summary graphs can be constructed in several ways. The survey by Čebirić et al. [19] classifies existing techniques into structural, pattern-mining, statistical, and hybrid approaches. A broad overview of these summarization approaches can be found there. In this paper, we focus on structural approaches based on quotients, due to their versatility and popularity for summarizing semantic graphs. The idea here is to partition the vertices into equivalence classes, assigning each vertex to exactly one equivalence class. These equivalence classes are used as the vertices of the summary. A structural summary is again a graph that can be used to answer a given application task exactly [19], i. e., as if it were executed on the original graph. Structural graph summaries defined using quotients [20] are closely related to $k$-bisimulation [88, 53]. Many summary approaches for semantic graphs are in fact stratified bisimulations.

Such structural summaries are “lossless” with respect to the features defined in a summary model: selected features of the original graph are accurately preserved to allow the task to be exactly computed on the summary. The features preserved by the graph summary are defined in the so-called graph summary model. Summaries can also be “lossy”, only allowing the task to be approximated on the summary.

Since different works and communities deal with graph summarization from different perspectives, we first need to provide a high-level clarification of the basic concepts. This shall provide the reader with an intuition about the nature of graph summaries and how they are used. The basic definitions are of a task (in the context of a graph summary) as well as the graph summary and its model, based on Blume, Scherp, and Richerby [10].

The set of parameters $\mathrm{\Psi }$ and the output of the function $T$, (the range $Y$) are specific to a given application domain.

Structural approaches summarize a graph $G$ w.r.t. an equivalence relation $\mathrm{EQR}\subseteq V\times V$ defined on the vertices $V$ of $G$ [19, 14]. The vertices $V(S)$ of the resulting summary graph $S$ correspond to equivalence classes of the equivalence relation $\mathrm{EQR}$, and to equivalence classes of subsidiary equivalence relations used in the definition of $\mathrm{EQR}$ – see Figure 1.

The model parameters $\mathrm{\Phi }$ are applied to control the output. $\mathrm{\Phi }$ can, e.g., limit the maximum summary size (in terms of number of vertices or edges), the weights assigned to some graph elements (preference for certain edges or vertices), or the minimum support of subgraph structures summarized by $S$ [19]. $\mathrm{PAY}$ describes what information must be stored about the summarized vertices to allow the task $T$ to be answered using the summary.

Different summary models serve different tasks. While a structural summary is a lossless representation of the input graph with respect to the features defined in a summary model, different summaries (with different payloads) will be needed for different tasks. Thus, the choice of features and the tasks have to be aligned. Finally, based on the graph summary model, we define the Graph Summary:

For the full definition of a graph summary with respect to a graph summary model, see [10].

Graph summarization is distinct from other related concepts, some of which also use the term summarization, but to mean something different.

The goal of compression is to allow the original graph to be exactly recovered (in the case of lossless compression, for example, RDF HDT [38]), or approximately recovered (lossy compression). Thus, compression must retain (or approximately retain) all information in the graph. Another term in this context is “corrections”  [89, 58]. Again, the goal is to (incrementally) compute a lossless compression of a graph by determining a so-called corrections set, i. e., a set of edges that must be added or removed to reconstruct the original graph [89, 58]. Another work on graph compression is by Hajiabadi et al. [44], who propose an approach to reconstruct a graph exactly (lossless) or with a small error (lossy). In contrast to compression and correction, summarization only retains the information that is needed for specific tasks.

An intermediate operation between summarization and compression is graph contraction [34], which uses the graph-theoretic concept of contraction minors [25]. Contraction makes graphs smaller by replacing regular structures such as cliques and paths with “supernodes”. Each supernode is annotated with a payload and a mechanism for recovering the original graph. This can also be done hierarchically, to produce even smaller graphs [35]. Compared to summarization, this only operates on parts of the graph; on the other hand, the entire graph can be recovered if needed, so the contracted graph is not task-specific (albeit that tasks that can be performed using the payload of the supernodes, without expanding out the graph, will run faster).

Further related research areas are graph transformation systems, graph rewriting, and model-driven engineering [30]. These approaches have in common that they have rules and mappings to manipulate input graphs to a desired output graph, e. g., to merge adjacent vertices by preserving (hyper-)edge structures [81, 57]. In general, the difference between structured graph summaries and the communities of graph transformation and graph rewriting is as follows: The goal of summarization is to provide concise representations of the input graph $G$ while preserving specific, defined features (e. g., structural features like which edges are attached to a vertex). The focus of graph rewriting is to perform operations on the graph to transform $G$ from one state to another via rewrite rules. Nonetheless, graph summarization is an example of graph rewriting in the most general sense.

The article is organized as follows: First, we consider applications of structural graph summaries in Section 2. In Section 3, we introduce features and models of structural graph summaries for static graphs that are based on quotients.

Bisimulation is a versatile and popular technique among structural graph summarization models, which we discuss in further detail in Section 4. Logics are a natural partner of structural summaries and this connection is discussed in Section 5. We consider graph summarization approaches for temporal graphs in Section 6.

Finally, in Section 7, we briefly discuss alternative approaches to graph summaries that are not based on graph quotients, such as pattern mining, and statistical approaches. We conclude this article with a brief reflection, as well as an outlook on future directions and open questions.

One application of structural graph summaries is to find semantically related entities in the Semantic Web [22]. Entities on the Semantic Web are represented using vertices, each identified with a unique IRI [29], and labeled edges indicate relations between them. Entities can have a set of types, each of which is indicated by an edge labeled rdf:type to a vertex representing that type. This graph data is typically stored as an RDF graph [1].

If two entities share the same set of RDF types and RDF properties (i.e., labels of outgoing edges other than rdf:type), we can say they are semantically related [22]. Hence, we can create a summary where the equivalence relation $\mathrm{EQR}$ represents that; i. e., it puts vertices in the same partition if their RDF types and set of RDF properties are the same.

This structural graph summary summarizes vertices (entities), based on such structural subgraph features. To find semantically related entities, we need to memorize the vertex identifiers of each summarized vertex in the computed structural graph summary, this index gets created by a function from $\mathrm{PAY}$ and is part of the output of the graph summary. We can now use that index for immediate retrieval of related vertices since all semantically related vertices are summarized together.

A variation of this task would be when the graph is dynamic. In that case, there is an interesting trade-off between recomputing the index, which can be costly, versus updating it in place, which requires more index information to be kept and leads to a more complex implementation.

Cardinality computation is often desired in databases [77, 84]. For graph databases, graph summaries can be used as an index to look up how many vertices will be returned by certain queries. If the graph summary is smaller than the original graph, as it usually is, the query runs faster on the graph summary than on the database. This task is related to the semantic entity retrieval task described above. However, for this purpose, we only need to memorize the number of summarized vertices rather than all vertex identifiers. Hence, $\mathrm{EQR}$ would be the same, but the function in $\mathrm{PAY}$ would only compute the counts, rather than keeping the full index.

A graph summary that memorizes the number of summarized vertices enables fast implementations of query size estimation [77]. Analogously to the semantically related entities task above, expensive re-computation of the graph summary from scratch when the database changes can yield an unwanted performance overhead, and hence a way to deal with online updates is necessary.

Knowledge bases often have a data schema or ontology that defines how entities should be modeled. Structural graph summaries can help determine how many entities strictly follow that schema, match the schema partially, or even contradict the schema. The stored numbers of summarized vertices can be used as an indicator of data completeness [84]. It is often desired to evaluate the evolution of data quality over time [84]; also in that case an incremental update mechanism is needed.

As part of data source search, one needs to find (sub)graphs in the Semantic Web that match a given schema structure [43]. Structural graph summaries can be used as an index that memorizes the location of summarized vertices on the Web. This is illustrated in Figure 2.

The EQR of the graph summary model in this scenario is defined such that it summarizes vertices that have the same set of RDF types, and are connected by edges with the same labels to target vertices with the same set of types, known as SchemEX [59]. The set of payload functions PAY is in this case a cardinality count and memorizing the data source URIs.

With a graph query, the structural graph summary is queried to get the URLs of relevant data sources. Then, the data sources are accessed to download the graphs matching the query. Search systems like LODatio [43], LODeX [6], Loupe [71], and LODatlas [80] rely on structural graph summaries to offer a search for relevant data sources or exploration of data sources.

To implement this task, we need to memorize the locations where each summarized vertex appears, which is computed by a function in $\mathrm{PAY}$. As the data on the Web changes [51], the summaries need to be updated as well. In contrast to the previous two tasks, for data source search we neither memorize vertex identifiers nor the number of summarized vertices but only their location.

Another application of graph summaries can be found in recent work by Generale, Blume, and Cochez [39], who address scalability issues when training graph neural networks (GNNs) on larger graphs. They suggest training the GNN on a summary, rather than on the original graph. The summaries used in this case are actually quotient graphs (see Section 3), using either $k$-bisimulation (see Section 4) or direct vertex attributes for $\mathrm{EQR}$.

The machine learning task solved with this GNN is the prediction of vertex types. In the normal training setting, the training set is a subset of the vertices of known type. The model parameters are then optimized such that the outputs of the GNN, when passed through a classifier, predict the correct vertex type for the test vertices. To evaluate whether the model works, one uses it to predict the types of vertices outside the training set and compares these predictions to the correct answer. An issue while training on the summary is that multiple vertices from the original graph are in the same equivalence class and hence mapped to the same vertex in the summary. Now, the difficulty is that we do not have a clear label for this vertex; it is not the case that all nodes in the equivalence class have the same label, since this is not taken into account when summarizing. The authors [39] suggest using a weighted multi-label classification task during training where the labels are weighted by their frequency. To compute this label, we need to collect the frequency of the labels of the vertices of each equivalence class, which is one of the functions in $\mathrm{PAY}$.

After training on the summary graph, the weights of the model are transferred back to the original graph, where inference is performed to predict the types of vertices from the test set. Inference can be done on the full graph because it is much faster than training and requires much less memory. In some cases, this method of training can not only provide reasonable results, but also the results can be improved if the model is further trained on the original graph. This two-stage process can give better results than training only on the original graph, without summarizing. To transfer the model weights, we include the index with the equivalence classes as part of $\mathrm{PAY}$.

A follow-up work by Bollen et al. [13] provides a theoretical foundation for the earlier work. They prove that it is possible to create a specific graph summary that for a specific class of GNN performs the same message-passing steps as on the original graph. In effect, this means that the same outcome is obtained at inference time. The prior work is not covered by this proof because the summary did not retain information about the cardinality of edges in the quotient graph, and therefore the conditions for equivalence are not met. Error bounds for the approximation remain open.

Triple features are solely based on outgoing triples of vertices. A triple corresponds to a directed edge between two vertices, namely the subject connecting to the object, which is labeled with the predicate.

The neighbor vertex identifier is the most direct approach to incorporate neighbor information and leads to a wider range of summary models that consider neighbor information, e. g., vertices in ${\mathrm{\Gamma }}^{+}(s)$. We classify features as subgraph features when they combine triple features of multiple vertices.

The last group of features for structural graph summaries defines explicit semantic rules. It deals with RDF Schema (RDFS) reasoning, OWL’s owl:sameAs reasoning, as well as inference on property sets in an OR-like fashion and via the inclusion of related properties.

As real-world graphs are quite heterogeneous, there may be only a few bisimilar vertices [19] if we consider full bisimulation. Thus, $k$-stratified bisimulation is often used, restricting the paths to length $k$. This increases the possibility that two vertices are bisimilar and, overall, reduces the size of the summary.

A $k$-bisimulation on a graph $G$ considers features a distance at most $k$ from a vertex that is to be decided equivalent to another vertex [85]. Formally, this can be defined for the forward bisimulation on the outgoing edges as follows (based on [85]). Backward bisimulation is defined similarly.

For bisimulation with vertex labels, we modify the base case of the definition so that $u{\approx }_{\mathrm{fw}}^{0}v$ iff $u$ and $v$ have the same labels. Note that stratified bisimulation defines a hierarchy of equivalence relations ${\approx }_{\mathrm{fw}}^0,{\approx }_{\mathrm{fw}}^1,\mathrm{\dots }{\approx }_{\mathrm{fw}}^k$, in contrast to complete bisimulation, which defines a single equivalence relation, recursively in terms of itself. Thus, stratified bisimulation is best suited to summarization, rather than quotienting. When producing a summary for $k$-bisimulation, the relation ${\approx }_{\mathrm{fw}}^k$ will be the primary equivalence relation, and ${\approx }_{\mathrm{fw}}^0,\mathrm{\dots },{\approx }_{\mathrm{fw}}^{k-1}$ are secondary.

Bisimulation stratified to paths of length $k$ is a popular technique to compute structural graph summaries, though often $k=1$ is used. We give examples in Table 1 and discuss them in detail in this section. Note that TermPicker [87] is a relaxed version of bisimulation. Conventional bisimulation requires the same edge label to the same type of neighbor, whereas TermPicker just requires the same edge labels and the same neighbor types, without the correlation.

Efficient algorithms for bisimulation have been developed by Paige and Tarjan [78], Kaushik et al. [53], Dovier et al. [27], Schätzle et al. [88], and others.

A notion of $k$-bisimulation w.r.t. graph indices is introduced by seminal works such as the $k$-RO index [76] and the T-index summaries [72]. Milo and Suciu’s T-index [72], the $A(k)$-Index by Kaushik et al. [53], and others summarize graphs using backward $k$-bisimulation. Qun et al. [83] extend the $A(k)$-Index to a $D(k)$-Index, which is also based on bisimulation but focuses on query optimization. To this end, the $D(k)$-Index dynamically adapts its structure according to the current query load. Another work using stratified bisimulation is by Fan et al. [33], for reachability and graph pattern matching on large graphs.

Conversely, the $k$-RO index, the Extended Property Paths of Consens et al. [23], the SemSets model of Ciglan et al. [22], Buneman et al.’s RDF graph alignment [17], and the work of Schätzle et al. [88] are based on forward $k$-bisimulation. Buneman et al. use forward $k$-bisimulation to summarize the union of two consecutive versions $G_{\text{union}}=G_1\cup G_2$ of an RDF graph with respect to $k$-bisimulation, which puts vertices to be aligned in the same partition. As well as to $k$-bisimulation, they use a similarity measure to further refine the initial $k$-bisimulation partition, as it does not capture all vertices to be aligned. The focus of their work is the optimization of the alignment process so that every node pair $(v_1,v_2)$, with $v_1\in G_1$ and $v_2\in G_2$, which have to be aligned is identified and not the construction of a $k$-bisimulation-based partition of $G$. Schätzle et al. compute a forward $k$-bisimulation on RDF graphs in sequential and distributed settings [88]. For a small synthetic dataset ($\sim 1M$ RDF-triples) the sequential algorithm slightly outperforms the distributed one; for larger datasets, the distributed algorithm clearly outperforms the sequential one.

Tran et al. compute a structural index for graphs based on backward-forward $k$-bisimulation [95]. Moreover, they parameterize their notion of bisimulation to a forward-set $L_1$ and a backward-set $L_2$, so that only labels $l\in L_1$ are considered for forward bisimulation and labels $l\in L_2$ for backward bisimulation. However, similar to Buneman et al., the particular focus of their work is not the construction of the bisimulation partition. Rather, they evaluate how one can efficiently optimize query processing on semi-structured data using an index graph based on bisimulation.

There are also structural summarization approaches that determine vertex equivalence only based on local information ($k\le 1$). As shown in Table 1, many of the summary models introduced in Section 3.2 are actually very shallow bisimulations.

Luo et al. [68, 67] examine structural graph summarization by forward $k$-bisimulation in a distributed, external-memory model. They empirically observe that, for values of $k>5$, the summary graph’s partition blocks change little or not at all. Therefore they state that, for summarizing a graph with respect to $k$-bisimulation, it is sufficient to summarize up to a value of $k=5$.

Martens et al. [69] introduce a parallel bisimulation algorithm for massively parallel devices such as GPU clusters. Their approach is tested on a single GPU with $24$GB RAM, which limits its use on large datasets. Nonetheless, their proposed blocking mechanism could be combined with our vertex-centric approach to further improve performance.

Konrath et al. [59] compute their graph summary over a stream of vertex-edge-vertex triples. They can deal with the addition of new vertices and edges to the graph but not the deletion of vertices or edges, or modification of their labels. Similarly, Goasdoué et al. [40] present the summarization tool RDFQuotient, which only supports iterative additions of vertices and edges to their structural graph summaries, and does not handle deletions. Thus, these approaches are not suited to updating structural summaries of evolving graphs. Goasdoué et al. also do not support payload information, which is needed for tasks such as cardinality estimations and data search. The purpose of their summaries is to visualize them to a human viewer. Finally, Blume, Richerby, and Scherp [9] propose an incremental algorithm to update graph summaries that also takes deletions and payload into account. Experiments on benchmark datasets show that using the incremental algorithm is beneficial even if up to half of the graph has changed from one version to the next.

Often, graph databases use path indices, tree indices, and subgraph indices [46]. A seminal approach to computing subgraph indices is DataGuide [42], implemented in the Lore database management system (DBMS) [102]. A DataGuide is a graph index built incrementally while executing queries on an XML database. It indicates to the query engine if and how a specific path defined in the query can be reached. To this end, a DataGuide represents all possible paths between two vertices in an XML file. While DataGuides operate on semi-structured data in terms of XML trees, a guide is essentially quotienting the graph.

Tran et al. [95, 96] took up this idea and applied it to quotienting RDF graphs. Representative Objects (ROs) by Nestorov et al. [76] take up the ideas of DataGuides and are also implemented in the Lore DBMS with focus on path queries, query optimization, and schema discovery. While the Full ROs capture a description of the global structure of the graph, the authors also introduce a notion of a $k$-RO. which only considers paths of length up to $k$. These are examples of bisimulation in graph summarization.

We now consider incremental subgraph indices based on frequent pattern mining. These techniques group graph patterns, similarly to structural summarization. For example, Yuan et al. [104] (see also extensions in [105, 52]) propose an index based on mining frequent and discriminative features in subgraphs. Their algorithm minimizes index lookups for a given query and regroups subgraphs based on newly added features.

A work directly based on quotients is Qiao et al. [82] who compute an index of isomorphic subgraphs in an unlabeled, undirected graph $G$. The goal is to find the set of subgraphs in $G$ that are isomorphic to a given query pattern. The result is a compression of the original graph that can be used to answer, e. g., cardinality queries regarding subgraphs. This is for static graphs, but the algorithm of Fan et al. [32] can deal with graph changes for the subgraph isomorphism problem. Their incremental computation of an index for isomorphic subgraphs is closely related to structural graph summarization but, unlike in summarization, the graph pattern $p$ is an input to the algorithm, not the output.

Min et al. [73] propose an algorithm for continuous subgraph matching using a summary-like data structure that stores the intermediate results between a query graph and a dynamic data graph. They consider undirected graphs where only vertices are labeled. Dynamic graphs are updated through a sequence of edge insertions and edge deletions. The TipTap [74] algorithm computes approximations of the frequent subgraphs on up to $k$ vertices w.r.t. a given threshold. This is similar to a quotient, but vertices may appear in multiple subgraphs. It does this to count occurrences of subgraphs in large, evolving graphs, modeled as a stream of updates on an existing graph. Tesseract [7] is a distributed framework for executing general graph mining algorithms on evolving graphs. It uses a vertex-centric approach to distribute updates to different workers. It assumes that most changes affect only local graphs, so few duplicate updates need to be detected. Tesseract supports the quotient-like ideas of $k$-clique enumeration, graph keyword search, motif counting, and frequent subgraph mining.

Another area of incremental subgraph indices considers an evolving set of queries over a static data graph. Duong et al. [28] propose a streaming algorithm using approximate pattern matching to determine subgraph isomorphisms. They use $k$-bisimulation to determine equivalent subgraphs and store them in an index. However, this index is computed offline for a static graph only and their algorithm considers a stream of graph queries as input.

Another area related to quotient-based summarization is incremental schema discovery. Vertices with the same schema are naturally equivalence classes that can be quotiented. Völker and Niepert mine logical patterns in the Web Ontology Language from static RDF graphs [99]. Wang et al. [100] incrementally discover attribute-based schemata from JSON documents. The schema is computed incrementally as more documents are processed. Baazizi et al. [4] also compute schemata from JSON objects, focusing on optional and mandatory attributes.

In addition to document-oriented formats like JSON, schema discovery is also used for graph data. For example, XStruct [47] follows a heuristic approach to incrementally extract the XML schema of XML documents. However, such schema discovery approaches cannot deal with modifications or deletions of nodes in the XML tree. Other schema discovery approaches focus on generating (probabilistic) dataset descriptions. Kellou-Menouer and Kedad [54] apply density-based hierarchical clustering on vertex and edge labels in a graph database. This computes profiles that can be used to visualize the schema of the graph. Recently, Bouhamoum et al. [15] used density-based clustering to extract schema information from an RDF graph and incrementally update the schema when new RDF instances arrive. While the work can deal with additions, the deletion of edges and vertices is not considered.

Non-quotient summaries do not use equivalence relations to summarize a graph. Rather, the summary graph is composed of vertex summaries $vs$, which group together vertices $v$ of the original graph $G$ according to certain criteria [19].

The main difference from quotient summaries discussed above is that, in the non-quotient summaries, a vertex $v$ can belong to zero, one, or multiple vertex summaries $vs$. In contrast, in quotient summaries every vertex $v$ has exactly one corresponding vertex summary $vs$, which is the equivalence class of $v$ under $\sim$ [19].

Early work on non-quotient summarization includes that of Goldman and Widom [42], who created a vertex summary $vs$ for every labeled path in the original graph $G$. A vertex $v$ of $G$ is associated with a vertex summary $vs$ if it is reachable by the corresponding label path. The summary graph is used as a path index, as well as a tool for understanding the schema structure in semi-structured databases, and hence finds application in query formulation and query optimization. Revisiting the summarization tool SchemEX [59], its first layer – the RDF class layer – consists of vertex summaries $v{s}_{c_j}$ representing all the classes $c_j$ present in the input RDF graph $G$. A vertex $v$ of $G$ is associated with a vertex summary $v{s}_{c_j}$, iff $v$ is of the corresponding type $c_j$. Since a vertex $v$ can have multiple types $c_{j_1},c_{j_2},\mathrm{\dots }$, it is possible that $v$ is associated with several vertex summaries $v{s}_{c_{j_1}},v{s}_{c_{j_2}},\mathrm{\dots }$ and therefore the index’s RDF class layer is considered a non-quotient summary. Kellou-Menouer and Kedad [54] perform schema extraction by using density-based clustering to establish a partition of the vertices based on type profiles. For each type $T_j$, a type profile $T{P}_j=\{(labe{l}_1,{\alpha }_1),(labe{l}_2,{\alpha }_2),\mathrm{\dots }\}$ is constructed, consisting of tuples of edge labels for outgoing edges $(v,w)$ and incoming edges $(w,v)$, with $v\in T_j$. The associated probabilities ${\alpha }_i$ denote how likely it is that a vertex $v\in T_j$ has an edge with the respective $labe{l}_i$. If a type profile $T{P}_j$ contains all entries $(labe{l}_i,{\alpha }_i)$ of another type profile $T{P}_k$ and every ${\alpha }_i$ is greater than a certain threshold $\theta$ (e. g., $\theta =0.6$), then the vertices in $T_k$ are added to $T_j$ to create overlapping classes. Clustering can be found in more structural non-quotient approaches [98, 56, 63, 75].

Other structural graph summarization methods that do not use quotients are based on structural measures such as centrality. They identify the most important vertices, cliques, and others, and connect them in the summary [19]. The difference from quotient-based summaries is that some graph vertices may not be represented in the summary, i. e., the summaries are approximate. Examples of summary methods using structural features are [107, 97, 79]. These guide the summaries using vertex centrality measures [12] such as vertex (in/out) degree, betweenness (how often a vertex lies on the shortest path between two other vertices), $(k,h)$-cores, and the well-known information retrieval measures PageRank and HITS (based on eigenvalue analysis over vertices), as well as further measures of vertex centrality such as those applied by Pappas et al. [79].

Pattern-mining approaches identify frequent patterns in the input graph $G$, which are then used to construct the summary graph $SG$ [19]. Song et al. [90] construct $d$-summaries to summarize a knowledge graph $G$. A summary $P$, which is a graph pattern found in $G$, is considered a $d$-summary, iff all the summary vertices $u\in P$ are $d$-similar ($R_d$) to all their respective original vertices $v\in V$. Informally, $u{R}_{d}v$ iff (1) $u$ and $v$ share the same label and (2) for every neighbor $u^{\prime }\in P$ of $u$ connected over an edge with label $p$ there exists a respective neighbor $v^{\prime }\in V$ connected via the same edge label and $u^{\prime }{R}_{d-1}{v}^{\prime }$. Their definition of $d$-similarity is very similar to $k$-bisimulation (Section 4) and mainly differs in the domain on which it is defined, namely summary vertices and original vertices.

Pattern mining methods for graph summarization discover frequently occurring patterns in the data [19]. Various algorithms exist for graph pattern mining, based either on the well-known Apriori principle (e. g., [61]) or pattern-growth algorithms (e. g., [103]). These define a minimum support (min-supp) threshold over subgraphs $X\subseteq G$. Only patterns that are frequent enough are included in the summary. Pattern mining methods are approximate summaries of the input graph $G$, as they do not include subgraphs that occur infrequently (thus, the summarization function is no longer homomorphic). However, setting $\text{min-supp}=1$ usually produces a lossless summary, equivalent to a structural summary computation, as no subgraphs are omitted. Pattern mining methods also have interesting features such as automatically mining specific types of subgraphs like cliques, (bipartite) cores, stars, and chains  [37, 60]. While star-shaped subgraphs and chains are in principle also supported by quotient summaries, the difference here is that the selection of edges in star patterns and the length of the chains is determined in a data-driven way, rather than being pre-defined in a summary model. Finally, some pattern mining methods are also approximate because they use approximate methods such as locality-sensitive hashing (LSH) to assign graph vertices to the summary [65]. This is an inaccuracy introduced by the LSH function but not a characteristic of the underlying frequent pattern mining algorithms.

Statistical methods for graph summarization summarize the contents of a graph quantitatively such as by counting occurrences of edge labels or computing histograms over the labels [19] and define further constraints on the summary models. For example, in $k$-SNAP [94], the number $k$ of summary vertices in a summary graph can be specified by the user, which controls the size of the summaries. The summarization operation $k$-SNAP [93] minimizes a function based on occurrences of user-selected edge labels to produce a summary graph $SG$, which contains exactly $k$ vertex summaries. In its top-down approach, it starts by partitioning the graph based on user-selected vertex attributes. Afterward, the algorithm splits elements (vertex summaries) of the partition based on the aforementioned function, until the partition’s size is $k$. Combining the first step, partitioning vertices by label, and the second step, minimizing a function that considers edge labels, $k$-SNAP can be considered a hybrid approach, combining structural and statistical concepts. CANAL is an extension of $k$-SNAP that supports numeric edge attributes [106]. Summarizing edges labeled with numeric values is approached by bucketing the values into predefined categories. Thus, the problem of supporting unbounded numerical values is reduced to summarizing graphs with discrete categories only.

We delved into the domain of graph summarization, a process aimed at generating concise representations of input graphs while preserving specific structural attributes. Particularly, we focus on structural graph summaries that can be applied to semantic graphs, i. e., labeled graphs such as in the RDF or provided as labeled property graphs.

Different approaches and algorithms have been developed to address graph summarization. Our focus has been on exploring the state-of-the-art methods for structural graph summarization based on quotients. We have examined the relationship of structural summarization with other pertinent fields, like the well-known $k$-bisimulation. A noteworthy observation is the natural connection between structural summarization and logics, owing to the discrete structures under consideration.

Finally, there are also hybrid approaches for graph summarization. They combine features of quotient-based structural and non-quotient statistical and pattern mining techniques [19]. One such example is the combination of bisimulation with clustering [3]. Hierarchical complete-link clustering is applied over vertex features to group the vertices. Similar, Wang et al. cluster paths in a graph to compute an approximate summary [101].

This research contributes to a deeper understanding of graph summarization techniques and opens avenues for future advancements in this domain. As directions of future research, we see:

1. 1.

   Multi summaries: Existing works summarize a graph with respect to a single, defined summary model only. Multi-summaries compute multiple condensed representations of the input graph at once, stored in a joined data structure.

2. 2.

   Summaries on temporal graphs: while there are already graph summarization approaches for temporal graphs, including incremental summarization [9], there is still a lot of work to be done. For example, we are currently missing approaches for summarization of rapidly evolving graphs such as social media graphs.

3. 3.

   Task-specific learned summaries: Graph summarization addresses different application needs. Example applications are outlined in Section 2. Interesting future work would be to automatically learn which features of a summary model are most relevant to a task (in general) or to the workload of a task (e. g., the kinds of queries executed in the data search scenario).

4. 4.

   Exploiting modern hardware such as GPUs: We have already briefly reflected on parallel and distributed computation of graph summaries in Section 4.3. First steps have been taken on using GPUs but there is still a lack of research in this direction.

5. 5.

   PyGraphSum: Each graph summarization model and algorithm typically comes with its own implementation, datasets, and evaluation measures. Comparing different algorithms and methods is difficult and cumbersome, as a common standard library for efficient distributed summarization of static and temporal graphs is missing. A standardized library that is used among industry and researchers alike will contribute not only to more transparency and comparability of the different approaches but also accelerate research in the field by facilitating reuse.