A Comprehensive Survey on Graph Summarization with Graph Neural Networks
As large-scale graphs become more widespread, more and more computational
challenges with extracting, processing, and interpreting large graph data are
being exposed. It is therefore natural to search for ways to summarize these
expansive graphs while preserving their key characteristics. In the past, most
graph summarization techniques sought to capture the most important part of a
graph statistically. However, today, the high dimensionality and complexity of
modern graph data are making deep learning techniques more popular. Hence, this
paper presents a comprehensive survey of progress in deep learning
summarization techniques that rely on graph neural networks (GNNs). Our
investigation includes a review of the current state-of-the-art approaches,
including recurrent GNNs, convolutional GNNs, graph autoencoders, and graph
attention networks. A new burgeoning line of research is also discussed where
graph reinforcement learning is being used to evaluate and improve the quality
of graph summaries. Additionally, the survey provides details of benchmark
datasets, evaluation metrics, and open-source tools that are often employed in
experimentation settings, along with a detailed comparison, discussion, and
takeaways for the research community focused on graph summarization. Finally,
the survey concludes with a number of open research challenges to motivate
further study in this area.
Nasrin Shabani, Jia Wu, Amin Beheshti, Quan Z. Sheng, Jin Foo, Venus Haghighi, Ambreen Hanif, Maryam Shahabikargar
# A Comprehensive Survey on Graph Summarization with Graph Neural Networks

###### Abstract

As large-scale graphs become more widespread, more and more computational challenges with extracting, processing, and interpreting large graph data are being exposed. It is therefore natural to search for ways to summarize these expansive graphs while preserving their key characteristics. In the past, most graph summarization techniques sought to capture the most important part of a graph statistically. However, today, the high dimensionality and complexity of modern graph data are making deep learning techniques more popular. Hence, this paper presents a comprehensive survey of progress in deep learning summarization techniques that rely on graph neural networks (GNNs). Our investigation includes a review of the current state-of-the-art approaches, including recurrent GNNs, convolutional GNNs, graph autoencoders, and graph attention networks. A new burgeoning line of research is also discussed where graph reinforcement learning is being used to evaluate and improve the quality of graph summaries. Additionally, the survey provides details of benchmark datasets, evaluation metrics, and open-source tools that are often employed in experimentation settings, along with a discussion on the practical uses of graph summarization in different fields. Finally, the survey concludes with a number of open research challenges to motivate further study in this area.

 Graph summarization is a key task in managing large graphs, which are ubiquitous in modern applications such as social networks, knowledge graphs, recommendation systems, and bioinformatics. However, summarizing graphs is a challenging problem due to the intricate nature and structural variability of real-world graphs. The purpose of this article is to provide a detailed overview of the latest developments in graph summarization methods. The study covers a broad range of techniques, including both conventional and deep learning-based approaches, with a particular emphasis on GNNs. By combining and evaluating the advantages and limitations of various techniques, we highlight significant challenges and favourable avenues for future investigation in this field. Our survey will benefit researchers and practitioners working on graph summarization, enabling them to select appropriate methods and design new algorithms that can effectively summarize large and complex graphs for a variety of applications.

 Deep Learning, Graph Neural Networks, Graph Summarization

## I Introduction

Large graphs are becoming increasingly ubiquitous. With the increasing amount of data being generated, large graphs are becoming more prevalent in modelling a variety of domains, such as social networks, proteins, the world wide web, user actions, and beyond. However, as these graphs grow in size, understanding and analyzing them is becoming more challenging. Additionally, performing fast computations with large graphs and visualizing the knowledge they can yield is also becoming more difficult. Many claim that faster and more effective algorithms are needed to overcome these obstacles [1, 2, 3]. However, a growing cohort of researchers believe that summarization might hold the answer to this unyielding problem. Summarization not only helps existing algorithms to parse the data faster, it can also compress the data, reduce storage requirements, and assist with graph visualization and sense-making [4, 5].

Graph summarization is the process of finding a condensed representation of a graph while preserving its key properties [2]. A toy example of a typical graph summarization process is shown in Figure 1. The process includes removing the original graph's objects and replacing them with fewer objects of the same type to produce a condensed representation of the original graph.

Most traditional approaches to graph summarization involve using a conventional machine learning method or a graph-structured query, such as degree, adjacency, or eigenvector centrality, to find a condensed graphical representation of the graph [2]. A popular summarization technique is to group structures in the input graph by aggregating the densest subgraphs [6]. For example, the GraSS model [7] focuses on accurate query handling and incorporates formal semantics for answering queries on graph structure summaries based on a random walk model, while Graph Cube [8] is a data warehousing model that integrates both network structure summarization and attribute aggregation. This model also supports OLAP queries on large multidimensional networks.

Notably, clustering methods follow a similar approach to summarization, partitioning a graph into groups of nodes that can be further summarized. Most traditional graph clustering methods use conventional machine learning and statistical inference to measure the closeness of nodes based on their connectivity and structural similarities [9]. For instance, Karrer et al. [10] used a stochastic block model to detect clusters or communities in large sparse graphs. However, another method of graph summarization focuses more on node selection and
identifying sparse graphs that can be used to derive smaller graphs [11]. As an example, Doerr et al. [12] introduced a sampling method based on traversing a graph that begins with a collection of starting points, e.g., nodes or edges, and then adds to the sample pool depending on recent information about the graph objects. However, despite the popularity of these approaches in the past, they are very computationally-intensive. They also require a great deal of memory to store, making them unsuitable for today's modern, complex, and large-scale datasets.

Deep learning on graphs is a powerful computational technique for graphs of all sizes that continues to interest both academics and industry. Graph neural networks (GNNs) are the most successful paradigm among the deep learning techniques for graphs. Their multilayer deep neural networks are not only able to reduce the dimensionality of tasks, they also support high-speed calculations with large-scale graphs [13, 14]. Several strategies that use a GNN as a summarization engine have been proposed over the last few years, and this line of research is expected to generate even more fruitful results in the future. These GNN-based methods have demonstrated promising performance with a diverse range of tasks, such as graph classification, node representation learning, and link prediction. Further, as research in this area continues to evolve, we can anticipate even more innovative and effective approaches to graph summarization that rely on GNNs.

### _Challenges with GNN-based Graph Summarization_

Although GNNs have helped to advance new techniques for summarizing complex graphs, such as social networks, citation networks, and informatics networks, applying these techniques is not without its challenges. Some of the main issues include scalability, graph heterogeneity, evaluation, and overfitting.

**Scalability.** A key hurdle in GNN-based graph summarization is scalability. GNN-based graph summarization methods are computationally expensive, and processing large graphs demands a substantial investment of time and resources [15]. But scaling these techniques to handle huge graphs, which are common in many real-world applications, is challenging. Researchers are working on developing more efficient GNN-based graph summarization algorithms to address this problem [16, 17, 18]. The ability to summarize graphs effectively using deep learning-based models, such as GNNs, is critical to reducing the scale of a graph while preserving its key features [19]. Achieving this requires effective training methodologies that can extract the most relevant information from the graph and represent it in a compact form. Consequently, graph summarization remains an active research area with significant challenges to be addressed [20].

**Graph heterogeneity.** Real-world graphs can be highly heterogeneous, and developing GNN-based graph summarization techniques that can handle heterogeneous graphs is a significant challenge. Often, more complex models and pre-processing steps are required to extract meaningful information from the various types of nodes and edges heterogeneous graphs contain [21]. Moreover, the inherent differences in the semantics of the diverse node and edge categories might necessitate unique feature representation and aggregation methodologies. To address this challenge, researchers are exploring new GNN architectures that can handle heterogeneous graphs, such as graph attention networks (GATs) and relation-aware graph convolutional networks (R-GCNs) [22, 23]. However, if we are to improve the quality of summaries with heterogeneous graphs, more research will be needed to develop preprocessing techniques and feature representations that effectively capture the properties and information contained in these complex graphs.

**Evaluation.** Evaluating how well a technique has summarized a graph is another challenge. There is currently no agreed-upon standard for evaluating the quality of graph summarization methods, so researchers often use different metrics and benchmarks [24]. This makes it difficult to compare different techniques and determine which methods perform better in different scenarios. New evaluation metrics and benchmarks have been outlined in some recent studies [25, 4, 26]; however, selecting the best approach for evaluation is a big challenge with GNN-based deep learning techniques.

**Overfitting.** A common problem in GNN-based graph summarization is overfitting, which occurs when the model becomes overly complex and starts fitting the noise present in the data rather than the underlying patterns. Overfitting can lead to poor generalization, where the model fails to perform well on unseen data [27]. To tackle this problem, researchers must create regularization techniques and model architectures that are both more effective at preventing overfitting and also help to improve generalization performance. Some of the more recently proposed techniques to address this challenge include dropout [28], graph pooling [29], and graph coarsening [17]. But more research in this area is needed.

### _Existing Surveys on Graph Summarization_

Over the past decade, numerous reviews have been conducted that acknowledge the importance of graph summarization. They generally cover a range of topics, like graph partitioning, graph sampling, graph coarsening, and graph embedding, along with specific use cases for graph summarization, such as pattern discovery, community detection, fraud detection, and link prediction. Additionally, several comprehensive surveys on graph summarization techniques have been conducted based on scientific computing: [30, 31, 32, 33, 34, 2, 5]. Yet only the most current work by Chen et

Fig. 1: An example of a graph summarization process. Objects are removed from the original graph and replaced with fewer objects of the same type to result in a condensed representation of the original graph.
al. [30] compares the most recent machine learning techniques to traditional methods.

There are also several surveys on graph sampling [35, 11, 36, 37], graph partitioning [38, 39, 40, 41], and graph clustering [42, 43, 44]. Other surveys focus on graph representation learning [45, 46, 47] and graph embedding [48, 49, 50]. As these streams of research look to create low-dimension versions of a graph, they are strongly connected to the concept of graph summarization.

There are also surveys that focus specifically on certain applications of graph summarization, such as pattern discovery, community detection, fraud detection, and link prediction, e.g., [51, 52, 3] and [53, 54, 55]. However, although these studies provide in-depth analyses of how graph summarization techniques are being used in important and high-demand domains, GNN-based graph summarization methods are not their main area of focus. Consequently, these surveys do not provide a comprehensive and structured evaluation of all available techniques for graph summarization.

### _Contributions_

In this survey, we review developments in graph summarization with GNNs. Overall, we have tried to provide researchers and practitioners with a comprehensive understanding of past, present, and future approaches to graph summarization using GNNs. Our specific contributions include:

* **The first deep GNN-based graph summarization survey.** To our best knowledge, this paper is the first thorough survey that is devoted to graph summarization with GNNs. The majority of pertinent surveys primarily center on traditional graph summarization approaches and do not include deep learning techniques. To date, no comprehensive and specialized study has been conducted on graph summarization using deep learning. Our research addresses this gap with the aim of using this thorough and structured survey to promote further advancements in the field.
* **Comprehensive review.** We present a comprehensive review of GNN-based graph summarization methods. We also highlight the benefits of different GNN techniques compared to traditional methods. Within each method, we present a review of the most notable approaches and their contributions to the field.
* **Resources and applications.** We have put together a set of resources that support graph summarization with GNNs, including cutting-edge models, standardized datasets for comparison, publicly available codes, and practical use cases. Our goal is to provide a resource for those seeking to understand and apply GNNs for graph summarization.
* **Future directions.** We identify and discuss the open challenges and new directions that lie ahead. Through an exploration of the existing challenges and potential avenues for progress, we aim to guide future research and development in GNNs for graph summarization, ultimately contributing to the development of new and innovative solutions for summarizing complex graphs.

The majority of the papers we reviewed were published at prominent international conferences (e.g., SIGKDD, NeurIPS, ICLR, ICML, KDD, WWW, IJCAI, and VLDB) or in peer-reviewed journals (e.g, ACM, IEEE, Elsevier, and Springer) in the domains of artificial intelligence, big data, data mining, and web services. In our investigations, we found that different fields referred to graph summarization using different terms, e.g., "coarsening", "reduction", "simplification", "abstraction", and "compression". While these concepts were used relatively interchangeably, the terms coarsening, simplification, and summarization were generally more common.

The remaining sections of this survey are structured as follows: Section II introduces the concept of graph summarization with primary definitions and background information. Section III provides an overview of the development of graph summarization. Section IV outlines the recently developed GNN-based graph summarization methods. Section V discusses graph reinforcement learning methods for graph summarization. Sections VI and VII outline the structure of widely adopted implementation resources and real-world applications. Finally, Section VIII explores a number of open research challenges that would motivate further study before the conclusion in Section IX.

## II Definitions and background

This section provides an overview of the key definitions and commonly used notations presented in Table I. It also includes some background information on graph summarization techniques.

* _Definition 1 (Graph):_ A graph G is represented as a tuple \((V,E)\), where \(V\) is the set of nodes or vertices \(\{v1,v2,...,vn\}\), and \(E\) is the set of edges or links \(E=\{e_{ij}\}_{i,j=1}^{n}\) that connect pairs of nodes. An \(nn\) dimensional adjacency matrix \(A=[a_{ij}]\) is used to represent the graph, where \(a_{ij}\) equals \(1\) if the edge \(a_{ij}\) is in \(E\); otherwise, \(a_{ij}\) equals \(0\). If \(a_{ij}\) is not equal to \(a_{ji}\), the graph is a directed network; otherwise, it is an
undirected network. If \(a_{ij}\neq a_{ji}\), If graph G has directed edges, it is considered a directed network. If it does not have directed edges, it is an undirected network. When the edges of \(G\) are weighted with weights from the set \(W\), the graph is called a weighted network. When the edges are not weighted, it is called an unweighted network. G is labelled if there is a label associated with e for every \(e\in E\). Additionally, the nodes may also be labelled if there exists a unique label for every node \(v\in V\). Otherwise, \(G\) is considered to be unlabelled.
* _Definition 2 (Graph Summary)_: Given a graph \(G\), a summary \(G(V_{S},E_{s})\) is a condensed representation of \(G\) that preserves its key properties. Graph summarization techniques involve either aggregation, selection, or transformation on a given graph and produce a graph summary as the output.

As outlined in Definition 2, graph summarization approaches fall into three main categories: aggregation, selection, and transformation. While selection approaches make graphs sparser by simply removing objects without replacing them, aggregation approaches replace those removed objects with similar objects only with fewer of them. For example, a supernode might replace a group of nodes. Similar to selection and aggregation, the transformation approaches also involve removing objects from the graph, but this time the objects removed are transformed into a different type of object, such as an embedding vector [56, 57].

**Aggregation.** Aggregation is one of the most extensively employed techniques of graph summarization. Aggregation methods can be divided into two main groups: those that involve node grouping and those that involve edge grouping. Node grouping methods group nodes into supernodes, whereas edge grouping methods reduce the number of edges in a graph by aggregating them into virtual nodes. Clustering and community detection are examples of a grouping-based approach. Although summarizing graphs is not explicitly the primary objective of these processes, the outputs can be modified into non-application-specific summaries [2].

**Selection.** There are two main groups of selection techniques: sampling and simplification. While sampling methods focus on picking subsets of nodes and edges from the input graph [58], simplification or sparsification methods involve removing less important edges or nodes. In this way, they tend to resemble solutions to dimensionality reduction problems [11, 5].

**Transformation.** Graph projection and graph embedding are two categories of this method. Generally, graph projection refers to the summarization techniques that transform bipartite graphs with various inter-layer nodes and edges into simple (single-layer) summarized graphs. Conversely, graph embedding refers to the techniques that transform a graph into a lower dimensional representation while preserving the original graph's topology [56].

## III Graph Summarization: An Evolution

Graph summarization has been playing an important role in areas such as network analysis, data mining, machine learning, and visualization for some time. The evolution of graph summarization is illustrated in Figure 3, which shows how it has progressed from traditional computing methods to multi-layer GNNs. Both of these paradigms are summarized in Figure 2. This section briefly overviews the three different traditional methods within this field and explains the advantages of GNN techniques over traditional ones.

### _Clustering-based Approaches_

Graph clustering can be thought of as a graph summarization technique since it involves grouping together nodes in a graph that are similar or related and, in so doing, the complexity and size of the original graph are reduced. In simpler terms, graph clustering provides a way to compress or summarize a large and complex graph into a smaller set of clusters, each of which captures some aspect of the structure or function of the original graph [1]. Graph summarization techniques using clustering can be classified into three main categories: structural-based, attribute-based, and structural-attribute-based approaches. This last approach, structural-attribute-based clustering, is currently considered to be the state-of-the-art [59, 60].

Clustering methods that rely on the structure of a graph group nodes together based on their structural characteristics and do not take any attribute data into account. The objective of these methods is to recognize groups of nodes that exhibit strong connections among themselves but weak connections with nodes that are not part of the group [61, 62]. Attribute-based clustering methods aggregate the nodes in a graph based on their associated attributes or features [63]. The clustering algorithm forms clusters by considering only the similarity of the attribute values of the nodes. The result is clusters that have abundant attribute information but fail to capture the topological structures of the network [64, 65]. Many real-world applications have demonstrated that combining both structural and attribute-based information within a clustering method is more effective than relying solely on either structural or attribute-based methods alone [59, 66]. For instance, Boolanal et al. [66] proposed a graph clustering method called k-Neighborhood Attribute Structural Similarity (k-NASS) that incorporates both the structural and attribute similarities of the graph nodes in the clustering process. The method uses a combination of k-neighborhood graph connectivity and attribute similarity measures to generate a weighted adjacency matrix, which improves clustering accuracy with complex graphs that have rich attributes.

_Remarks:_ Despite the numerous graph clustering methods suggested in previous studies, the task of performing a clustering analysis on a large graph that contains many attributes is still a difficult undertaking, primarily because it requires a significant amount of memory and computational resources, as well as quick access to disk-based storage [67].

### _Statistical Inference_

Statistical inference techniques for graph summarization make inferences about the original graph, yet they maintain the most significant characteristics of the graph and simplify
its complexity. These techniques can be divided into two groups: pattern mining and sampling. Pattern mining methods recognize the patterns within a graph and use them to create a condensed representation of the graph, while sampling methods select a proportion of the graph's nodes and/or edges at random [32].

Pattern mining techniques use statistical methods to identify the patterns or subgraphs that are most representative of the whole graph. These patterns [68] or subgraphs [69] can then be used to create a summary of the graph that preserves its essential characteristics.

Conversely, the basic idea of graph sampling is to select a random subset of nodes or edges from a graph and use this subset to estimate the properties of the entire graph. By analyzing the properties of the sampled subset, we can draw conclusions and derive insights based on the graph data [11]. For example, graph sampling can be used to summarize large and complex graphs where it may be impractical or impossible to analyze the entire graph. Sampling can also be used to estimate some of a graph's properties, such as the degree distribution, clustering coefficient, or other graph statistics. These estimates can be used to construct a summary of the graph that captures its key characteristics [36]. There are various sampling techniques that can be used for graph summarization, including random sampling [70, 71], stratified sampling [72], and snowball sampling [73]. For example, the Node2vec approach [71] generates random sequences of nodes within a graph, known as walks, which can be used to sample the graph. The Node2vec algorithm employs a biased random walk technique to produce these random walks. This method ensures a balance between breadth-first sampling and depth-first sampling. Once the random walks are generated, the Node2vec algorithm uses the Skip-gram model to learn node embeddings from the random walks. The learned node embeddings capture the local graph structure and can be used to compute various graph summaries statistics, such as the clustering coefficient, the degree distribution, and the structures of communities.

_Remarks:_ There are benefits and drawbacks associated with each of these techniques, and the choice of technique depends on the specific problem and data at hand. For instance, one major drawback of sampling methods based on random walks is that the quality of the graph summary can be affected by the choice of the walk's starting node. Given different starting nodes, the random walk might cover different parts of the graph, which can lead to different graph summaries. This can make the results of the graph summarization less reliable and reproducible.

### _Goal-Driven_

Goal-driven techniques for graph summarization involve constructing a graph summary that is tailored to a specific application or task. They are a powerful tool for capturing specific features or relationships in a graph that are relevant to a specific application or task. By optimizing the graph summary to a specific goal, it is possible to create a more effective and efficient summary that can be used to derive better insights and make better decisions [74]. Significant goal-driven techniques for graph summarization include utility-driven [75] and query-driven [76] techniques.

Utility-driven techniques focus on the challenge of summarizing large graphs in a way that preserves their essential properties and structure, while also maximizing their utility for downstream tasks. In other words, the aim is to create a compact summary while preserving the "useful" information in the graph [75]. In this category, human reviewers evaluate the utility of the summary [77] against the specific downstream task the summarization is intended to support. Example downstream tasks include node classification and link prediction [78].

Query-driven techniques summarize graphs by identifying subgraphs or patterns in the larger graph that are relevant to the target downstream task [79]. Querying a graph involves formulating queries in a query language that specifies the particular subgraph or pattern to look for in the larger graph. The result is a subgraph that matches the query, which can then be used as a building block for the graph summary [76]. For example, in a node classification task [80], a graph query might be used to identify a subgraph of nodes that have comparable characteristics or connections. This subgraph can then be used as a summary representation of the larger graph to support the node classification task. Graph querying can also be combined with other graph summarization techniques, such as clustering [81] and feature selection [82], to create a more comprehensive summary that captures the essential properties of the original graph, while also being tailored to a specific downstream task.

_Remarks:_ Although goal-driven graph summarization can be helpful for improving the interpretability of large graphs because they reduce complexity, the choice of summarization technique will depend on the specific goals of the analysis. For example, some techniques may be better at preserving the global properties of the graph, while others may be better at capturing local structures. The choice of technique will also depend on the available computational resources and the complexity and size of the original graph.

### _Why GNNs for Graph Summarization?_

In recent times, deep learning has gained significant prominence and is now considered one of the most effective forms of AI due to its high accuracy. Conventional deep learning methods have shown that they perform extremely well with Euclidean data (e.g., images, signals, and text), and now there are a growing number of applications in non-Euclidean domains (e.g., graphs and manifold structures). As a deep learning approach, GNNs are multi-layer neural networks that learn on graph structures to ultimately perform graph-related tasks like classification, clustering, pattern mining, and summarization [83].

As mentioned, traditional graph summarization approaches are mostly based on conventional machine learning or graph-structured queries, such as degree, adjacency, and eigenvector centrality, where the aim is to find a condensed graphical representation of the whole graph [7, 8]. However, the
pairwise similarity calculations involved in these approaches demand a considerably high level of computational power. The explicit learning capabilities of GNNs skirt this problem. Additionally, powerful models can be built from even low-dimensional representations of attributed graphs [84]. Unlike standard machine learning algorithms, with a GNN, there is no need to traverse all possible orders of the nodes to represent a graph. Instead, GNNs consider each node separately without taking the order of the input nodes into account. This avoids redundant computations.

The major advantage of GNN models for graph summarization over traditional methods is the ability to use low-dimensional vectors to represent the features of large graphs [3]. Additionally, the message-passing mechanism used by GNNs to communicate information from one node to the next has been the most successful learning framework for learning the patterns and neighbours of nodes and the sub-graphs in large graphs [13]. It is also easy to train a GNN in semi- or unsupervised way to aggregate, select, or transform graphs into low dimensional representations [14]. In this regard, recent successes in graph summarization with GNNs point to promising directions for new research. For example, the GNN models developed by Brody et al. [85] and Goyal et al. [86] represent dynamic graphs in low dimensions, providing a good foundation for popularizing GNNs to more complex dynamic graphs.

## IV Graph Summarization with GNNs

This section provides an overview of recent research into graph summarization with GNNs. Each subsection covers four main categories of approach - these being: Recurrent Graph Neural Networks (RecGNNs), Convolutional Graph Neural Networks (ConvGNNs), Graph Autoencoders (GAEs), and Graph Attention Networks (GATs). Within each subsection, we review the most notable approaches and the contributions each has made to the field.

### _RecGNN-based Approaches_

RecGNNs are early implementations of GNNs, designed to acquire node representations through a generalized recurrent neural network (RNN) architecture. Within these frameworks, information is transmitted between nodes and their neighbours to reach a stable equilibrium [83, 87]. A node's hidden state is continuously updated by

\[h_{i}^{t}=\sigma(x_{i}^{t},h_{j}^{(t-1)},e_{ij}) \tag{1}\]

where \(h_{i}^{t}\) represents the hidden state of the RecGNN cell at time t, \(x_{i}^{t}\) is the feature vector of node \(u_{i}\) at time step \(t\), \(h_{j}^{(t-1)}\) is the hidden state vector of a neighboring node \(u_{j}\) in the previous time step (\(t-1\)), \(e_{ij}\) is the edge embedding between the nodes \(u_{i}\) and \(u_{j}\), and \(\sigma\) is a non-linear function that combines the inputs and produces the new embedding. RecGNNs update the hidden state of each node by considering the input and hidden states of neighbouring nodes. Message passing operations are computed based on: the input feature vector of each node; the hidden state vectors of its neighbouring nodes in the previous time step; and the edge feature vectors between the node and its neighbouring nodes [88].

RecGNN-based approaches for graph summarization mostly focus on graph sampling and embedding by generating sequences from graphs and embedding those sequences into a continuous vector space at lower dimensions. The architectures based on RNNs generally comprise long short-term memory units (LSTMs) and/or gated recurrent units (GRUs).

#### Iv-A1 LSTM-based Approaches

LSTMs are a class of RNNs that use a sequence of gates to concurrently model long- and short-term dependencies in sequential data [89]. The modified architecture of an LSTM to handle graph-structured data is known as a graph LSTM [90]. Typically, the input to the model consists of a sequence of either graph nodes or edges, which are processed in order using LSTM units. At each time step, the model updates its internal state based on the input node or edge and the previous state, as shown in Equation 2.

\[h_{t}=LSTM(x_{t},\sigma(h_{t-1},N(h_{t-1}))) \tag{2}\]

where \(h_{t}\) is the hidden state of the \(LSTM\) at time step t, \(x_{t}\) is the input feature vector of the graph at time step t, and \(\sigma\) is an aggregation function, such as a sum, mean, or a max pooling function, that combines the hidden states of neighbouring nodes. \(N(h_{t-1})\) represents the hidden states of the neighbouring nodes in the previous time step \(t-1\), and \(LSTM\) is a standard LSTM cell that updates the hidden state of the LSTM based on its input features and the previous hidden state.

By repeating this process over multiple time steps, the model captures the dependencies in the graph and generates a final hidden state that summarizes all the information contained in the entire graph. This makes it possible to preserve a record of both the previous inputs and the structure of the graph. After processing all the nodes and edges, the final state of the graph LSTM is used as the summary representation of the graph. This summary vector can then be used as input to downstream machine learning models or as a feature for other graph analysis tasks [91].

LSTM-based approaches for graph summarization have proven to be effective with a range of tasks, such as graph clustering, graph classification, and link prediction. For example, Taheri et al. [92] leveraged various graph-LSTM-based methods to generate sequences from a graph structure, including breadth-first search, random walk, and shortest path. Finally, they trained a graph LSTM to embed those graph sequences into a continuous vector space. The hidden states at time step \(t\) of the encoder are as follows:

\[h_{t}^{enc}=LSTM_{enc}(x_{t},h_{t-1}^{enc}) \tag{3}\]

where \(x_{t}\) is the input vector at time \(t\) and \(h_{t}^{enc}\) denotes the hidden state at time step t in a given trained encoder \(LSTM_{enc}\). Similarly, the hidden state at time step \(t\) of the decoder is defined in Equation 4.

\[h_{t}^{dec}=LSTM_{dec}(x_{t-1},h_{t-1}^{dec}) \tag{4}\]

Li et al. [93] proposed a graph summarization technique that uses a graph LSTM and a ConvGNN to improve question
answering with knowledge graphs. In this approach, the questions, entities, and relations are represented as vectors with very few dimensions, but the key properties of the relations are well preserved. Jin et al. [94] also developed an approach to learn representations of graphs based on a graph LSTM. Here, graph representations of diverse sizes are encoded into low-dimensional vectors.

Several studies have also focused on evolving node patterns in dynamic graphs. For instance, Zhang et al. [91] applied a graph LSTM, proposing a one-stage model called DynGNN. The model embeds an RNN into a GNN model to produce a representation in compact form. Similarly, Ma et al. [95] introduced a dynamic RecGNN model that relies on a graph LSTM to model the dynamic information in an evolving graph while reducing the graph's dimensionality and learning manifold structures. Node information is continuously updated by: recording the time intervals between edges; recording the sequence of edges; and coherently transmitting information between nodes. Another work by Goyal et al. [86] also presents a method for learning temporal transitions in dynamic graphs. This framework is based on a deep architecture that mainly consists of dense and recurrent layers. Model size and the number of weights to be trained can be a problem during training, but the authors overcome this issue with a uniform sampling of nodes.

#### Iii-B2 GRU-based Approaches

GRUs are a variant of graph LSTMs that include a gated RNN structure and have fewer training parameters than a standard graph LSTM. The key distinction between a GRU and an LSTM is the number of gates in each model. LSTMs have three gates, "input", "output", and "forget", while GRU units are less complex with only two gates, "reset", and "update" [96]. GRUs are typically formulated as:

\[h_{t}=GRU(x_{t},\sigma(h_{t-1},N(h_{t-1}))) \tag{5}\]

where \(h_{t}\) is the hidden state of a GRU-based RecGNN at time step t, \(x_{t}\) is the input feature vector of the graph at time step t, and \(\sigma\) is an aggregation function, such as sum, mean, or a max pooling function, that combines the hidden states of neighbouring nodes. \(N(h_{t-1})\) represents the hidden states of the neighbouring nodes in the previous time step t-1, and \(GRU\) is a GRU cell that updates the previous hidden state and the hidden state of the input features.

Again, by repeating this process over several time steps, the model learns the dependencies that exist between the nodes in the graph, allowing it to construct a final hidden state that summarizes all the graph's information. Taheri et al. [97] proposed the DyGrAE model, which is able to learn the structure and temporal dynamics of a dynamic graph while condensing its dimensions. A GRU model captures the graph's topology, while an LSTM model learns the graph's dynamics. Ge et al. [98] developed a gated recursive algorithm that not only solves some node aggregation problems but also extracts deeply dependent features between nodes. The resulting model, called GR-GNN, is based on a GRU which performs the aggregation and structure. Li et al.'s [99] GRU model encodes an input graph into a fixed-size vector representation, which is then fed into a sequence decoder to generate the summary as the output. The model effectively captures the structural information and dependencies among the nodes and edges in the input graph, which is crucial for producing a coherent and informative graph summary.

_Remarks_: RecGNN-based techniques can capture a substantial amount of information during their recursive neigh

Fig. 2: Traditional graph summarization approaches and the taxonomy of GNN-based methods.
bourhood expansions by using recurrent units to identify the long-term dependence across layers [100]. Further, this process is quite efficient. Notably, RecGNN models can also improve numerical stability during training if they incorporate convolutional filters.

### _ConvGNN-based Approaches_

The general idea of ConvGNN-based approaches is to generalize the CNNs on graph-structured data [83]. The primary distinction between a ConvGNN and a RecGNN is the way information is propagated. While ConvGNNs apply various weights at each timestep, RecGNNs apply the same weight matrices in an iterative manner until an equilibrium is reached [101].

In other words, ConvGNN models are a form of neural network architecture that supports graph structures and aggregates node information from the neighbourhood of each node in a convolutional manner. ConvGNN models have demonstrated a strong expressive capacity for learning graph representations, resulting in superior performance with graph summarization [101].

ConvGNN-based approaches fall into two categories: spectral-based and spatial-based methods [102].

#### Iii-B1 Spectral-based Approaches

Spectral-based methods describe graph convolutions based on spectral graph theory and graph signal filtering. In spectral graph theory, the multiplication of the graph with a filter (the convolution) is defined in a Fourier domain [103].

Although the computation contains well-defined translational properties, it is relatively expensive, and the filters are not generally localized. Since the level of complexity grows with the scale of the graphs, one solution is to only check a limited number of neighbours using Chebyshev's theory [104]. This theory has led to several studies that explore the idea of applying approximation to the spectral graph convolution. For example, Defferrard et al. [105] generalized the CNNs to graphs by designing localised convolutional filters on graphs. They also introduced a graph summarization procedure that groups similar vertices together and a graph pooling procedure that focuses on producing a higher filter resolution. This work has been used as the basis of several studies that draw on Chebyshev polynomials to speed up convolution computations. As a variant, Kipf et al. [106] introduced several simplifications to the original framework to improve the model's classification performance and scalability to large networks. These simplifications formed the basis of the GCN (Graph Convolutional Network) model, which has since become a popular choice for various graph-related tasks. Their propagation rule is expressed in Equation 6:

\[h_{i}^{(k+1)}=\sigma(W^{(k+1)}\sum_{j\in N_{i}}\frac{1}{c_{ij}}h_{j}^{k}) \tag{6}\]

where \(h_{i}^{(k+1)}\) represents the \(i\)-th node's hidden state at the \((k+1)\)-th iteration of the GCN, \(N_{i}\) is the set of neighboring nodes of the \(i\)-th node, and \(c_{ij}\) is a normalization constant that represents the number of edges that node \(i\) shares with its neighbor \(j\). \(W^{(k+1)}\) is the weight matrix for the \((k+1)\)-th layer of the GCN. The propagation rule computes the new feature vector \(h_{i}^{(k+1)}\) for node \(u\) in the \((k+1)\)-th layer by taking the sum of the feature vectors \(h_{j}^{k}\) of all its neighbors \(j\in N_{i}\)

Fig. 3: A timeline of graph summarization and reviewed techniques.
which is weighted by \(1/c_{ij}\). This sum is then multiplied by the weight matrix \(W^{(k+1)}\), and an activation function \(\sigma\) is applied.

More recently, several successful variations of the spectral method have been proposed, e.g., S-GCN [107] and later SIGN [108]. S-GCN is a simplified GCN model but does not come with any performance compromises in terms of graph summarization. The idea behind the S-GCN model is to first convert large convolutional filters into smaller ones and then to remove the final non-linear layers. Inspired by previous ConvGNN models, Rossi et al. [108] subsequently proposed SIGN, which scales ConvGNNs to extremely large graphs by combining various amendable graph convolutional filters for faster training and sampling purposes.

Another prominent line of research in spectral-based ConvGNN approaches revolves around transforming graph objects, e.g., embedding. For example, Jiang et al. [109] introduced a hierarchical ConvGNN for graph embedding. This team built upon a spectral ConvGNN to provide an effective representation learning scheme for end-to-end graph classification tasks. More specifically, they proposed a framework for learning graph feature embeddings while also taking the network architecture and relationships between subjects into account. Deng et al. [110] introduced a multilevel framework to enhance the scalability and accuracy of embedding in an unsupervised manner. The model initially generates a new, efficient graph that contains information about both the node properties and the topology of the original graph. It then repeatedly aggregates the nodes with high spectral similarity, breaking the graph down into numerous smaller graphs.

#### Iii-A2 Spatial-based Approaches

Spatial-based methods work on the local neighborhood of nodes, aggregating node representations from neighboring nodes to understand their properties. ConvGNNs of this kind imitate the convolution operations of CNNs by defining convolutions directly in the graph domain. Unlike spectral-based approaches, which are relatively expensive and time-consuming to compute, the structure of the spatial-based approaches is simple and has generated cutting-edge outcomes with graph summarization challenges [111].

As a closely-related approach to Kipf and Welling's model [106], GraphSAGE extends their framework to the inductive setting [112]. GraphSAGE was the first approach to introduce node-wise sampling coupled with minibatch training for node embeddings using spatial convolutions. The updated propagation rule, which uses a mean aggregator function, is formulated as follows:

\[h_{i}^{(k+1)}=\sigma(W^{(k+1)}CONCAT(h_{i}^{(k)},\frac{1}{|N_{i}|}\sum_{j\in N _{i}}h_{j}^{k})) \tag{7}\]

Here, a mean aggregator function computes the average of the feature vectors of the neighbors of node \(u_{i}\) in the \(k\)-th layer. The concatenation operation concatenates the feature vector of node \(u_{i}\) in the \(k\)-th layer with the average of the feature vectors of its neighbors. The resulting vector has twice the dimensionality of the input feature vector, as it contains both the original node features and the aggregated neighbor features. GraphSAGE is a more flexible model that allows for different types of aggregator functions to be used. This makes it a good choice for graphs with heterogeneous node types, where different types of information need to be aggregated differently. GraphSAGE has also been shown to perform well on tasks such as graph classification and node classification, which are related to graph summarization.

Chen et al. [113] proposed a similar node-wise sampling approach, named FASTGCN, which incorporates an importance sampling method to produce better summaries. Later, Huang et al. [114] and Zeng et al. [115] respectively introduced layer-wise and graph-wise sampling methods to further enhance performance. While Huang et al. [114] focused on the issue of redundancy in node-wise sampling, Zeng et al.'s GraphSAINT [115] looks to correct bias and variance in minibatch estimators when sampling subgraphs for training. However, the most recent variation of GraphSage was developed by Li et al. [116]. This implementation, called bipartite GraphSAGE, is designed for bipartite graphs that contain different node types and inter-layer edges. The framework contains a user-item graph that supports both user and item embedding, while the model embeds the nodes into two different feature spaces - one corresponding to information about the users, the other corresponding to the items.

Many aggregation-based methods have also been introduced to summarize graphs without sacrificing too much information within the original graphs. The summarized graph can then be used to assist in further network analysis and graph mining tasks. For example, Yan et al. [17] proposed a summarization within a ConvGNN for faster training, data denoising, and interpretability. They used an end-to-end neural network model with a node grouping layer to summarize the graph by minimizing its dimensionality. Hu et al. [117] took structural similarity into consideration, aggregating nodes that share a similar structure into hypernodes. The summarized graph is then refined to restore each node's representation. To this end, a deep hierarchical ConvGNN (H-GCN) architecture with several coarsening operation layers followed by several refinement operation layers performs semi-supervised node classification. The refinement layers are designed to restore the structure of the original graph for graph classification tasks.

The most recent developments in convGNNs demonstrate the exciting potential graph summarization holds for a range of applications in healthcare and human motion analysis [118, 119]. Wen et al. [118], for example, presented a promising approach to diagnosing autism spectrum disorder by parsing brain structure information through a multi-view graph convolution network. Dang et al. [119] introduced a new type of graph convolution network, called a multi-scale residual graph convolution network, that shows superior performance in predicting human motion compared to other state-of-the-art models.

_Remarks_: Most existing ConvGNN models for graph summarization simply presume the input graphs are static. However, in the real world, dynamically evolving graphs/networks are more common. For instance, in a social network the number of users, their connected friends, and their activities are constantly changing. To this end, learning ConvGNNs on static graphs may not yield the best results. Hence, more research on dynamic ConvGNN models is needed to increase
the quality of summaries with large-scale dynamic graphs.

### _GAE-based Approaches_

An autoencoder is a neural network that consists of an encoder and a decoder. Generally, the encoder transforms the input data into a condensed representation, while the decoder reconstructs the actual input data from the encoder's output [120]. Graph autoencoders, or GAEs, are a type of GNN that can be applied over graph structures, allowing the model to learn a compact and informative representation of a graph. Lately, GAEs have garnered increasing interest for their ability to summarize graphs due to their significant potential with dimensionality reduction [84]. The key formulation of a GAE is:

\[z=encoder(G,A) \tag{8}\]

where \(z\) is the latent representation of the graph, \(G\) is the graph structure, \(A\) is the adjacency matrix of the graph, and the \(encoder\) is a function that maps the graph and adjacency matrices to the latent space. A decoder function then maps the latent representation back into the original graph structure:

\[G^{\prime}=decoder(z) \tag{9}\]

The goal of a GAE is to learn an encoder and decoder that reduces the gap between the original graph and the reconstruction error of the decoded graph, while also encouraging the latent representation to capture meaningful information about the graph's structure [121]. GAEs can be trained using various loss functions, such as binary cross-entropy or mean squared error. They can also be extended to incorporate additional constraints or regularization techniques to improve the quality of the learned graph representation [122].

The majority of GAE-based approaches for graph summarization use combined architectures that include ConvGNNs or RecGNNs [123, 26, 124]. For example, Kipf et al. [26] proposed a variational graph autoencoder (VGAE) for undirected graphs based on their previous work on spectral convolutions [106]. VGAE incorporates a two-layer ConvGNN model based on the variational autoencoder in [123]. The main concept of VGAE is to embed the input into a distribution rather than a point and, from there, to choose a random sample from the distribution rather than having it created directly by the encoder. As an extension, Hajiramezanali et al. [124] constructed a variational graph RNN by integrating a RecGNN and a GAE to model the dynamics of the node attributes and the topological dependencies. The aim of the model is to learn an interpretable latent graph representation as well as to model sparse dynamic graphs.

There are also several aggregation-based approaches built on GAEs. These are generally designed to formulate the challenges with graph clustering tasks as a summarization problem [125, 126, 127, 128]. For example, Cai et al. [125] suggested a graph recurrent autoencoder model for use in clustering attributed multi-view graphs. The fundamental concept behind the approach is to consider both the characteristics that all views have in common and those that make each graph view special. To this end, the framework includes two separate models: the Global Graph Autoencoder (GGAE) and the Partial Graph Autoencoder (PGAE). The purpose of the GGAE is to learn the characteristics shared by all views, while the PGAE captures the distinct features. The cells are grouped into clusters using a soft K-means clustering algorithm after the output is obtained. Fan et al. [127] introduced the One2Multi Graph Autoencoder (OMGAE) for multi-view graph clustering. OMGAE leverages a shared encoder to learn a common representation from multiple views of a graph and uses multiple decoders to reconstruct each view separately. Additionally, OMGAE introduces a new attention mechanism that assigns different weights to each view during the clustering process based on their importance. The model is trained to minimize a joint loss function that considers both the reconstruction error and the clustering performance. Mrabah et al. [128] devised a new graph autoencoder model for attributed graph clustering called GAE-KL. The model uses a new formulation of the objective function, which includes a KL-divergence term, to learn a disentangled representation of the graph structure and the node attributes. The disentangled representation is then used to cluster the nodes based on their similarity in terms of both structure and attributes. The authors also introduced a new evaluation metric called cluster-based classification accuracy (CCA) to measure clustering performance.

Recently, Salha et al. [129] proposed a graph autoencoder architecture that uses one-hop linear models to encode and decode graph information. The approach simplifies the model while still achieving high performance with graph summarization tasks, such as node clustering and graph classification. Uniquely, this paper presents a direction for designing graph autoencoder models that balances performance with simplicity.

_Remarks_: Most GAE-based approaches are typically unregularized and mainly focus on minimizing the reconstruction error while ignoring the data distribution of the latent space. However, this might lead to poor graph summarization when working with sparse and noisy real-world graph data. Although there are a few studies on GAE regularization [130], more research is needed in this regard.

### _GAT-based Approaches_

The idea of an attention mechanism was first proposed by Bahdanau and his colleagues in 2014 [139]. The goal was to allow for modelling long-term dependencies in sequential data and to improve the performance of autoencoders. Essentially, attention allows the decoder to concentrate on the most relevant part of the input sequence with the most relevant vectors receiving the highest weights. Graph attention networks or GATs [140] are based on the same idea. They use attention-based neighborhood aggregation, assigning different weights to the nodes in a neighborhood. This type of model is one of the most popular GNN models for node aggregation, largely because it reduces storage complexity along with the number of nodes and edges. The key formulation for a GAT is:

\[h_{i}=\sigma(\sum_{i\in N(j)}\alpha_{ij}Wh_{j}) \tag{10}\]

where \(h_{i}\) is the hidden feature vector of node \(u_{i}\), \(N(j)\) is the set of neighbouring nodes of \(u_{i}\), \(h_{j}\) is the hidden state of
neighbouring node \(u_{j}\), \(W\) is a weight matrix, and \(\alpha_{ij}\) is the attention coefficient that measures the importance of node \(u_{j}\) to node \(u_{i}\). The attention coefficients are computed as:

\[\alpha_{ij}=softmax(e_{ij}) \tag{11}\]

where \(e_{ij}\) is a scalar energy value computed as:

\[e_{ij}=LeakyReLU(a^{T}.[Wh_{i}||Wh_{j}]) \tag{12}\]

where \(a\) is a learnable parameter vector, and \(||\) denotes concatenation. The \(LeakyReLU\) function introduces non-linearity into the model and helps prevent vanishing gradients. The softmax function normalizes the energy values across all neighboring nodes so that the attention coefficients sum to one.

By computing attention coefficients for neighboring nodes, GATs are able to selectively focus on the most important parts of the graph for each node. This allows the model to adaptively adjust to different graph structures and tasks. The attention mechanism also means GATs can incorporate node and edge features into the model, making them well-suited to summarization tasks, such as node classification with complex graphs [131].

Today, GATs are considered to be one of the most advanced models for learning with large-scale graphs. However, recently Brody et al. [85] argued that GATs do not actually compute dynamic attention; rather, they only compute a restricted form of static attention. To support their claim, they introduced GATv2, a new version of this type of attention network, which is capable of expressing problems that require computing dynamic attention. Focusing on the importance of dynamic weights, these authors argue that the problem of only supporting static attention can be fixed by changing the sequence of internal processes in the GAT equations, as shown in Equation 13.

\[e_{ij}=a^{T}LeakyReLU(W.[h_{i}||h_{j}]) \tag{13}\]

As another variation of GAT, Xie et al. [25] proposed a novel multi-view graph attention network named MGAT, to support low-dimensional representation learning based on an attention mechanism in a multi-view manner. The authors focus on a view-based attention approach that not only aggregates view-based node representations but also integrates various types of relationships into multiple views.

Tu et al. [134] explored the benefits of using graph summarization and refining bipartite user-item graphs for recommendation tasks. They applied a conditional attention mechanism to task-based sub-graphs to determine user preferences, which emphasizes the potential of summarizing and enhancing knowledge graphs to support recommender systems. Salehi et al. [132] defined a model based on an autoencoder architecture
with a graph attention mechanism that learns low-dimensional representations of graphs. The model compresses the information in the input graph into a fixed-size latent vector, which serves as a summary of the entire graph. Through the use of attention, the model is able to discern and prioritize critical nodes and edges within the graph, making it more effective at capturing the graph's structural and semantic properties.

More recent works on GATs conducted by Chen et al. [135] and Li et al. [141] demonstrate the potential of graph attention networks for summarizing and analyzing complex graph data in various domains. Chen et al. proposed a multi-view graph attention network for travel recommendations. The model takes several different types of user behaviors into account, such as making hotel reservations, booking flights, and leaving restaurant reviews, and, in the process, learns an attention mechanism to weigh the importance of different views for a recommendation. Li et al. developed a multi-relational graph attention network for knowledge graph completion. The model integrates an attention mechanism and edge-type embeddings to capture the complex semantic relations between entities in a knowledge graph.

_Remarks_: GAT-based approaches use attention layers to overcome the limitations of prior studies, particularly those that rely on graph convolutions. While convolutional-based approaches use predefined weights for the neighbors of a node, GAT-based approaches modify the aggregation process through attention. Given the recent advancements in this area, we expect to see more research in the future on using GATs to create condensed representations of both static [140] and dynamic [85] graphs.

## V Graph Reinforcement Learning

Reinforcement learning (RL) is a mathematical model based on sequential decisions that allows an agent to learn via trial and error in an interactive setting through feedback on its actions. Due to the success and fast growth of reinforcement learning in interdisciplinary fields, scholars have recently been inspired to investigate reinforcement learning models for graph-structured data, i.e., graph reinforcement learning or GRL [142]. GRL is largely implemented based on the Bellman theory [143], where nodes represent states and edges represent actions. The goal is to learn a policy that optimizes the expected total reward across a series of actions. This can be done using various algorithms, such as Q-learning, or through a policy gradient method, which updates the Q-values or policy parameters based on the observed rewards and transitions [144].

There is also a flourishing line of GRL research that seeks to use this paradigm to evaluate and improve the quality of graph summaries. For example, Amiri et al. [4] introduced a task-based GRL framework to automatically learn how to generate a summary of a given network. To provide an optimal solution for finding the best task-based summary, the authors made use of CNN layers in combination with a reinforcement learning technique. To improve the quality of the summary, the authors later proposed NetReAct [138], an interactive learning framework for graph summarization. The model uses human feedback in tandem with reinforcement learning to improve the summaries, while visualizing the document network. NetReAct also provides summaries at a range of sizes and allows the user to zoom in on each document group. In this way, the user can examine numerous summaries and, in so doing, comprehend the data at multiple levels. In another study, Wickman et al. [133] presented a graph sparsification framework empowered by a GRL to be used for any edge sparsification assignment with a specific target for reduction. The model takes an edge reduction ratio as its input, and a learning model decides how best to prune the edges. Notably, the graph's structural attributes are maintained throughout the process. Yan et al. [137] introduced a GRL approach to summarize geographic knowledge graphs. To obtain a more thorough understanding of the summarizing process, the model exploits components with spatial specificity and includes both the extrinsic and the intrinsic information in the graph. The authors also discuss the effectiveness of spatial-based models and compare the results of their model with models that include non-spatial entities.

Recently, many articles have discussed the potential of using GRLs to summarize and analyze complex graph data in domains like neuroscience and computer vision [136, 145]. For example, Zhao et al. [136] suggested a deep reinforcement learning scheme guided by a GNN as a way to analyze brain networks. The model uses a reinforcement learning framework to learn a policy for selecting the most informative nodes in the network and combines that with a GNN to learn the node representations. Also, Goyal et al. [145] presented a GNN-based approach to image classification that relies on reinforcement learning. The model represents images as graphs and learns graph convolutional filters to extract features from the graph representation. They showed that their model outperforms several state-of-the-art methods on benchmark datasets with both image classification and reinforcement learning tasks.

_Remarks_: GRLs for graph summarization have attracted increasing attention owing to their remarkable performance at improving the quality of graph summaries. Unlike other sequential data, such as images, text, or videos, the evolving patterns in graph-structured data usually have higher heterogeneity. Designing customized deep GRL architectures for the purpose of graph summarization stands to be a promising direction in the future.

## VI Published Resources

This section provides an overview of the benchmark datasets, evaluation metrics, and open-source implementations that are discussed in Sections IV and V of the surveyed literature.

### _Datasets_

Both synthetic and real-world datasets are used in the development of the field. Synthetic datasets are created by models based on manually-designed rules, while real-world datasets are collected from actual applications and used to evaluate the performance of proposed methods for practical use. The popular real-world datasets are divided into six
categories: citation networks, social networks, user-generated networks, bio-informatics networks, image/neuroimages, and knowledge graphs.

### _Evaluation Metrics_

GNNs are typically evaluated through tasks like node classification, graph classification, graph clustering, recommendation, and link prediction. To provide an overview of the evaluation criteria used in each study, we categorized each of the articles we reviewed based on the metrics they used to evaluate their methods. These metrics include accuracy, precision, recall, F1-score, and AUC-ROC. Table III lists the most-used evaluation metrics and their calculation formulas or descriptions.

### _Open-source Implementations_

Table IV provides a summary of the open-source implementations by model, language, platform, type of input graph, and repository link. The majority of these implementations are written in Python 3.x using popular frameworks such as PyTorch, TensorFlow, or Keras. The remaining implementations mostly use MATLAB.

## VII Applications

Graph summarization has several applications and spans a range of domains and tasks, as shown in Figure 4. In this section, we will delve into specific examples of how graph summarization might be used in typical applications in these areas.

### _Graph Partitioning_

Graph summarization is an important technique used in graph partitioning algorithms like clustering algorithms and community detection algorithms. This is because graph summarization reduces the size of large graphs while preserving their structural properties. Here, the basic idea behind graph summarization is to construct a smaller, coarser version of the original graph by merging nodes or edges together based on certain criteria, such as degree, attribute, or connectivity [146]. For example, in the field of biochemistry, where graph nodes represent atoms/proteins and edges represent their connections, a graph partitioning algorithm like community detection can be helpful for identifying chemical compounds [147] or the complexity of new proteins [148].

### _Graph Visualization_

Summarizing graphs is a key part of visualizing graphic information. This is because the summaries produced essentially provide an overview of a graph's structure, which can be visualized to help users explore and analyze large graphs. Additionally, because summarized graphs yield a more comprehensible representation of complex graphs, users can focus on the parts of the graph they deem most relevant [2]. This has been found useful in a wide range of applications, including social network analysis [149], bioinformatics [150], and cybersecurity [151]. Moreover, graph summarization can also be used to generate interactive visualizations that allow users explore different levels of detail [152].

### _Pattern Discovery_

Graph summarization has several applications in pattern discovery, i.e., finding meaningful patterns and relationships in large datasets. In the context of graph data, graph summarization can be used to identify frequent and/or meaningful subgraphs or motifs [153]. This process can involve identifying clusters of similar subgraphs or identifying important nodes or edges. The discovered patterns can then be interpreted to gain insights into the underlying data. Social network analysis [154], bioinformatics [155], and recommendation systems [156] are just a few of the areas that have benefitted from pattern discovery through graph summaries. For example, in bioinformatics, Koyuturk et al. [155] used graph summarization techniques to identify recurring patterns in protein-protein interaction networks (PPINs), yielding important insights into the structure and function of these networks.

### _Graph Compression_

Summarizing graphs to compress data can help address some of the problems associated with storing, processing, and visualizing large and complex graphs [157]. Large graphs can take up significant amounts of memory, making them difficult to store and retrieve. Thus, by compressing a graph using summarization, the resulting smaller graph can be stored and retrieved more efficiently. Plus, summarizing a graph can help reduce the computational complexity of analyzing and processing it. For example, Kang et al. [158] proposed a novel approach for summarizing large-scale graphs that takes user preferences and interests into account, as well as the structural properties of the graph.
### _Graph Querying and Matching_

Graph querying involves finding subgraphs or patterns in a larger graph that match a given query. Graph summarization can be used to speed up querying graphs by reducing the size of the graph and by creating a summary graph that captures the essential features of the original graph [1]. For instance, Chen et al. [159] proposed a graph stream summarization structure that efficiently handles temporal range queries over streaming graph data. The authors focused on the problem of summarizing and querying large-scale graph data that are constantly changing over time, such as social or traffic networks.

Conversely, graph matching is the problem of finding a correspondence between the vertices or edges of two graphs that maximizes some similarity metric. Here, graph summarization can also be used to enable approximate matching, where the query graph is matched against the summary graph with some tolerance for differences in the graph structure. This can be useful in applications where exact matching is not feasible or desirable, such as in natural language processing [160] or image recognition [161]. For example, Li et al. [162] proposed a two-step approach for evolving subgraph matching on temporal graphs where the graph structure changes over time. The paper presents a method for constructing a summary graph to identify candidate matches for a subgraph within a temporal graph. Graph summarization can also enable approximate matching with tolerance for differences in the graph structure.

## VIII Future Directions

Despite the significant progress that graph summarization has made with the advent of GNNs, there are still unresolved issues that require additional exploration, as summarized in Figure 4. This section proposes six potential areas for future research.

### _Multi-layer Graphs_

Multi-layer graphs are made up of multiple layers of interconnected entities. They have recently been used to represent complex graphs where the entities and their connections are of heterogeneous types. Working with real multi-layer graphs can be challenging because they often contain large amounts of redundant or irrelevant data. Moreover, the traditional methods are not practically suitable for analyzing large-scale multi-layer graphs. To make these graphs easier to analyze, a number of GNN-based methods have been developed to support transformation-based summarization [56]. But these techniques do not provide an interpretable representation the properties relating to the nodes, edges, actors, and layers. Hence, more focus needs to be given to developing effective and comprehensive summarization techniques for multi-layer graphs.

### _Dynamic Graphs_

In the real world, the data that graphs represent can evolve over time, creating changes in a graph's topology, such as new edges that appear, nodes that disappear, or attributes that change over time. These dynamics can cause fundamental changes to the entire graph. Summarizing dynamic graphs typically involves boiling the graph down into a series of snapshots taken at various time increments. The model is then trained over these snapshots, yet a number of challenges can arise when attempting to extract dynamic features. To
date, the approaches developed to tackle these problems have leveraged the methods and theories of attention mechanisms and GATs [85], and, currently, these are the most advanced models for learning with dynamic large-scale graphs and manifolds. However, this research is still in its infancy and further study is required to popularize these models to more complex graph networks.

### _Multi-label Graphs_

Deep graph convolutional models, particularly aggregation-based models, have shown great performance with single-label graph summarization tasks, such as classification. However, graphs in the real world are often naturally multi-label. Hence, it is necessary for researchers to move beyond single-label classification and consider the graphs where the nodes and edges have multiple labels. Despite a few recent works that manage to achieve some scalability [163], methods of dealing with multi-label graphs have not been fully investigated. In this learning scenario, identifying the information shared between multiple labels so as to reduce dimensionality is still a challenging task. Furthermore, the lack of labeled data for multi-label graph tasks poses a significant challenge in developing effective and scalable models for real-world applications. One potential solution for handling multi-label graphs is to explore the use of attention mechanisms, which can selectively emphasize relevant information from different labels and reduce the noise caused by irrelevant labels.

### _Task-based Summarization_

As the size of graphs continues to increase, our ability to understand them is suffering. Summarizing graphs is therefore essential to exposing important information, helping humans with sensemaking, and speeding up graph analysis. However, intuitively, we know that different purposes and tasks will require different summaries. For example, a graph summarization strategy to detect communities will almost certainly be different from the strategy taken to find the most influential nodes. This indicates that we should develop unique approaches to identifying similar patterns for each task we wish to undertake. Moreover, although task-based summarization is critical, this field of study has seen few successes [138, 4] and is still an underexplored area. Open research problems include how to perform task-based summarization on streaming and heterogeneous graphs and how to leverage human feedback in the learning process.

### _Evaluation Benchmarks_

The optimal outcome of a graph summarization process is a "good" summary of the original graph. However, evaluating the "goodness" of a summary is an application-specific task that depends on the task at hand. For example, sampling-based methods are evaluated based on the quality of the sampling, while aggregation-based methods are evaluated based on the quality of classification, and so on. Current studies commonly use comparisons between their method and one or more established methods to measure the quality of their results. For instance, metrics that have been used in the literature include information loss, ease of visualization, and sparsity [2]. However, more and different evaluation metrics are required for cases where the validation process becomes complex and more elements are involved, such as visualization and multi-resolution summaries.

Fig. 4: Applications and future directions.
### _Generative AI_

In the context of generative AI, graph summarization can be used to generate new graphs that have similar properties to the original ones. One application of graph summarization in generative AI is in the generation of molecules for drug discovery [164]. Molecules can be represented as graphs, where the nodes represent atoms and the edges represent chemical bonds. However, the space of possible molecules is vast, and generating all of them is computationally expensive. By using graph summarization techniques, researchers can generate a smaller set of representative molecules. In turn, this smaller dataset can be used to train a generative AI model to generate new molecules that have similar properties. Another application of graph summarization in generative AI is generating 3D shapes [165]. 3D shapes can be represented as graphs, where the vertices represent points in space, and the edges represent the connections between them. By summarizing the graphs of existing 3D shapes, a generative AI model can be trained to generate new shapes that are similar to the original ones in terms of their geometric properties.

Graph summarization can also be used to support personalized learning [166]. This can be a powerful tool for summarizing the progress of a learner, identifying gaps in their knowledge, and generating personalized learning paths for them. For example, suppose a student is learning a new subject and has completed several lessons. A graph summarization algorithm can be used to identify the essential concepts covered in those lessons and represent them in a condensed form. This condensed representation can then be used to generate a personalized learning path that is tailored to the student's current knowledge and learning goals, helping them to focus on the areas where they need the most support.

## IX Conclusion

New advancements in deep learning with multi-layer deep neural networks have made it possible to quickly and effectively produce a condensed representation of a large and complex graph. In this paper, we surveyed the technical trends and the most current research in graph summarization with GNNs. We provided an overview of different graph summarization techniques and categorized and described the current GNN-based approaches of graph summarization. We also discussed a new line of research focusing on reinforcement learning methods to evaluate and improve the quality of graph summaries.

To advance research in this field, we also outlined several frequently-used benchmarking tools, including datasets, open-source codes, and techniques for generating synthetic datasets. In addition, we identified six promising directions for future research based on our findings from the survey. We strongly believe that using GNNs for graph summarization is not just a passing trend. Rather, it has a bright future in a wide range of applications across different domains. As a potential area of focus for our future work, we aim to explore the capabilities of generative models such as variational autoencoders, generative adversarial networks, and graph reinforcement learning, generating new graphs based on their summarized representations.
