\section{Introduction}

Large graphs/networks are becoming increasingly ubiquitous everywhere. Social networks, protein graphs, web graphs, and user action graphs are a few real-world examples of large-scale graphs. As these graphs grow in size exponentially, it is becoming more challenging to comprehend and analyze them. Performing fast computations and visualization on large graphs are also difficult to accomplish. To overcome these obstacles one approach is to expand current solutions by creating faster and more effective algorithms. A different strategy is to first summarize the large graphs, tackle problems on summarized ones, and finally map the outcomes back. In addition to accelerating existing algorithms, summarization has several other benefits, such as compressing large data, reducing storage requirements, and assisting with graph visualisation and sense-making~\cite{amiri2018netgist}. 

\begin{figure}[t]
    \centering
    \includegraphics[width=0.5\textwidth]{GS.png}
    \caption{An example of a graph summarization process by removing the original graph's objects and replacing them with fewer objects of the same type to attain a condensed representation of the original graph.}
    \label{fig:GS}
\end{figure}

Graph summarization is the process of finding a condensed representation of a graph while preserving its key properties~\cite{liu2018graph}. For a better understanding, a toy example of a graph summarization process is shown in Figure~\ref{fig:GS}. The process includes removing the original graph’s objects and replacing them with fewer objects of the same type to attain a condensed representation of the original graph.

Most existing traditional graph summarization approaches are based on conventional machine learning or graph-structured queries such as adjacency, degree, and eigenvector centrality to find a condensed graphical representation of the graph~\cite{liu2018graph}. A popular path for graph summarization is to group the input graph by aggregation of dense subgraphs, which can be effectively used to summarize the original graph. 
For example, GraSS~\cite{lefevre2010grass} focuses on accurate query handling and proposes formal semantics for answering queries on graph structure summaries based on a random walk model. Graph Cube~\cite{zhao2011graph} introduces a data warehousing model that integrates both network structure summarization and attribute aggregation. It also supports OLAP queries on large multidimensional networks. Clustering methods also follow the same path partitioning the graph into groups that can be further summarized. Most traditional graph clustering  methods measure the closeness of nodes based on connectivity and their structural similarities using conventional machine learning and statistical inference.
For instance,~\cite{karrer2011stochastic} 
introduced a method that uses a stochastic blockmodel to detect clusters or communities in large sparse graphs. Another path for graph summarization focuses more on sampling and obtaining sparse graphs that can be used to obtain a smaller graph.
For instance,~\cite{doerr2013metric} 
proposed 
a traversal-based 
sampling method, which begins with a collection of starting points (e.g, nodes or edges) and grows the sampling depending on recent information of the graph objects. However, despite being popular in the past, these approaches require high computation and storage costs,
making them 
not applicable when facing today's modern, complex, and large-scale datasets. 

Recently,
deep learning on graphs - a more powerful technique that is capable of high-speed computations on 
large-scale graphs - has recently gained a burgeoning interest among both academics and industry. Graph Neural Network (GNN) is the most successful deep learning-based with multi-layer deep neural networks that can achieve reduced dimensionality.
Recently, several works on GNNs with various summarization strategies have been proposed~\cite{wu2022graph}. 
In this survey, we review new developments in GNNs for graph summarization.
Specifically, our contribution is threefold as follows:
\begin{itemize}
    \item Reviewing the advantages of various GNN methods for graph summarization; and
    \item Categorizing the most recent studies from a technical standpoint; and
    \item Identifying and discussing the open challenges and new directions that lie ahead.
\end{itemize}

To our best knowledge, this paper represents the first thorough survey focusing on GNNs for graph summarization. The majority of the papers we reviewed were recently released at prominent international conferences (e.g., SIGKDD, Neurips, ICLR, ICML, KDD, WWW, IJCAI, and VLDB) and 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, different terms have been used to address graph summarization, e.g., ``coarsening", ``reduction", ``simplification", ``abstraction", and
``compression". 
Whereas these concepts are used interchangeably, the use of the terms coarsening, simplification, and summarization are more common. With this survey, we try to provide researchers and practitioners in related fields with a comprehensive understanding of recent approaches to follow the past, current, and future directions in the field of GNN for graph summarization.

The remaining sections are structured as follows. A brief introduction to the concept of graph summarization is provided in Section~\ref{gs}. Section~\ref{whyGNN} highlights the necessity of using GNNs for graph summarization. Recently developed GNN-based graph summarization methods are surveyed in Section~\ref{GNN}. Section \ref{GRL} discusses graph reinforcement learning methods for graph summarization. And Finally, the paper ends up in Section~\ref{conc} with a discussion on a number of open research challenges that would motivate further study in this area. A repository of the references is also available at \textcolor{blue}{\url{https://github.com/Nasrin-Shabani/GNN_for_Graph_Summarization}}.

\section{Graph Summarization}
\label{gs}
\begin{itemize}
    \item \textbf{Definition 1} \textit{(Graph)} \textit{Graph G = (V, E) is a tuple where V is a set of nodes or vertices and $E$ is a set of edges or links connecting a pair of nodes. G is labelled if for every $e \in E$ there is a label associated with e. Additionally, the nodes may also be labelled if there exists a unique label for every node $v \in V$. Otherwise, G is considered unlabelled.}


    \item \textbf{Definition 2} \textit{(Graph Summarization) Given a graph G, graph summarization (GS) aims to find a condensed representation of G in the form of a summarized graph while preserving its key properties. }
    
    \end{itemize}

Graph summarization approaches can be categorized under three main categories (see Figure \ref{fig:Taxonomy}): aggregation, selection, and transformation. While the selection approaches sparsify graphs by simply removing objects without replacing them, the aggregation approaches replace those removed objects with fewer similar objects (e.g., using a supernode to replace a group of nodes). On the other hand, although the transformation approaches, similar to the first two, involve the removal of objects from the original graph, the removed ones are transformed into a different type of objects (e.g., embedding vectors)~\cite{interdonato2020multilayer,jin2021graph}.

\begin{enumerate}[(i)]
    \item \textbf{Aggregation:} One of the most extensively employed techniques for graph summarization is aggregation methods. We categorize aggregation graph summarization techniques into two main groups: node grouping and edge grouping. While node grouping methods focus on grouping nodes into supernodes, edge grouping methods decrease the number of edges in a graph by aggregating edges into virtual nodes. Clustering and community detection are examples of grouping-based approaches that can be used for graph summarization. Although the primary objective of these approaches is not explicitly summarizing graphs, the outputs of the algorithms may simply be modified into summaries that are not application-specific~\cite{liu2018graph}. 
    \item \textbf{Selection:} Selection techniques are categorized into two main groups:  sampling and simplification. While sampling methods focus on picking subsets of nodes and edges from the input graph, simplification or sparsification methods involve removing less important edges or nodes, resembling the dimensionality reduction problem.
    \item \textbf{Transformation:} Graph projection and graph embedding are two categories of this method. Generally, graph projection refers to summarization techniques dealing with transforming bipartite graphs with various inter-layer nodes and edges into simple (single-layer) summarized graphs. And, graph embedding refers to transforming a graph into a lower dimensional representation, preserving the original graph’s topology~\cite{interdonato2020multilayer,yang2021graph}.
\end{enumerate}

In Section \ref{GNN}, we will go through several GNN methods that have been employed for some of the above-mentioned graph summarization techniques.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{Taxonomy.png}
    \caption{Taxonomy of the graph summarization techniques.}
    \label{fig:Taxonomy}
\end{figure} 

\section{Why GNN for Graph Summarization?}
\label{whyGNN}
Recently, deep learning has become one of the most enhanced existing AI research due to its high level of accuracy. While conventional deep learning methods have shown significant performance on Euclidean data (e.g., image, signal, and text), there are a growing number of applications in  non-Euclidean domains (e.g., graph or manifold structure). GNN as a deep learning approach can operate multi-layer neural networks on graph structure and address graph-related tasks like classification, clustering, pattern mining, and summarization ~\cite{wu2020comprehensive}. 


Traditional graph summarization approaches are mostly based on conventional machine learning or graph-structured queries such as adjacency, degree, and eigenvector centrality~\cite{zhao2011graph,lefevre2010grass} to find a condensed graphical representation of the whole graph. For example, kernel-based machine learning approaches  use similarity measures or kernels to implicitly compare the similarity of graph objects for embedding graphs in lower dimension spaces. Due to pairwise similarity computation, these approaches demand considerably high calculations. On the other hand, GNNs are more effective with explicit learning capabilities and powerful in low-dimensional representations of attributed graphs~\cite{cai2018comprehensive}. Moreover, unlike standard machine learning algorithms, there is no need to traverse all the possible orders of the nodes to represent a graph. Instead, to avoid redundancy in computations, GNNs propagate on each node independently, disregarding the nodes’ input order.

The major advantage of GNN models for graph summarization over traditional methods is their ability to represent large graph features by low-dimensional vectors~\cite{liu2020deep}. Additionally, GNNs are the most successful learning frameworks that can learn the pattern of nodes, neighbours, and sub-graphs using a message-passing mechanism between the nodes of graphs.
Moreover, GNNs can be easily trained in semi- or unsupervised ways  to  aggregate, select or transform graphs into low dimensional representations~\cite{wu2022graph}. In this regard, recent successes in graph summarization with GNNs have pointed to promising directions - for example, the GNN models in~\cite{brody2021attentive,goyal2020dyngraph2vec} for the representation of dynamic graphs in low dimensions. 

\section{Graph Summarization with GNNs}
\label{GNN}

In this section, a technical overview of the recent research in GNNs for graph summarization is provided. Each subsection covers four main categories of approaches Graph Recurrent Networks (GRNs), Graph Convolutional Networks (GCNs), Graph Auto-encoders (GAEs), and Graph Attention Networks (GATs), as shown in Table~\ref{table:GNN}. Within each subsection, we present a review of the most notable approaches with their contributions to the field. 

\begin{table*}[t]
\centering
\caption{Taxonomy and representative publications of Graph Neural Network (GNN) for graph summarization.}
        \begin{tabular}{m{6cm} m{2.5cm} m{6cm}}
        \hline
        \textbf{Category} & \textbf{ } & \textbf{Publications}\\
        \hline
            \multirow{2}{*}{Graph Recurrent Network (GRN)} &
                                   \multicolumn{1}{m{2.5cm}}{LSTM-based} & \multicolumn{1}{m{6cm}}{~\cite{li2021improving},~\cite{taheri2018learning},~\cite{zhang2022dynamic},~\cite{goyal2020dyngraph2vec},~\cite{jin2018learning},~\cite{ma2020streaming}.} \\\cline{2-3}
                                 & \multicolumn{1}{m{2.5cm}}{GRU-based} & \multicolumn{1}{m{6cm}}{ ~\cite{taheri2019learning},~\cite{ge2022gr}} \\\hline

            \multirow{2}{*}{Graph Convolutional Network (GCN)} &
                                   \multicolumn{1}{m{2.5cm}}{Spectral-based} & \multicolumn{1}{m{6cm}}{~\cite{defferrard2016convolutional},~\cite{kipf2016semi},~\cite{wu2019simplifying},~\cite{rossi2020sign},~\cite{jiang2020hi},~\cite{deng2019graphzoom}.} \\\cline{2-3}
                                 & \multicolumn{1}{m{2.5cm}}{Spatial-based} & \multicolumn{1}{m{6cm}}{~\cite{hamilton2017inductive},~\cite{chen2018fastgcn},~\cite{huang2018adaptive},~\cite{zeng2019graphsaint},~\cite{li2020hierarchical},~\cite{yan2019groupinn},~\cite{hu2019hierarchical}.} \\\hline
            
          Graph AutoEncoder (GAE) &
             &
           ~\cite{cai2018comprehensive},~\cite{kipf2016variational},~\cite{kingma2013auto},~\cite{hajiramezanali2019variational},~\cite{cai2021grae}.\\
            
        \hline
                Graph Attention Network (GAT)&
               &
           ~\cite{velivckovic2017graph},~\cite{brody2021attentive},~\cite{xie2020mgat},~\cite{tu2021conditional}. \\  
        
        
        \hline
        \end{tabular}
    \label{table:GNN}
\end{table*}


\subsection{GRN-based Approaches}
GRNs are the pioneer works of GNNs to learn node representations using a generalized RNN (Recurrent Neural Network) architecture. They are based on the exchange of information between nodes and their neighbours to reach a stable equilibrium~\cite{wu2020comprehensive}. For graph summarization, GRN-based approaches mostly focus on graph sampling and embedding by generating sequences from graphs and embed those sequences into a continuous vector space in lower dimensions. The approaches based on RNNs include Long Short-Term Memory Units (LSTMs) and Gated Recurrent Units (GRUs) architectures.

\subsubsection{LSTM-based Approaches}
LSTM is a class of RNNs that uses a sequence of gates to model long-term and short-term dependencies in sequential data at the same time. The modified architecture on graph structure data is known as Graph LSTM.

For example, \cite{taheri2018learning} leveraged various methods to generate sequences from a graph structure, including breadth-first search, random walk, and shortest path and finally trained a Graph LSTM model to embed those graph sequences into a continuous vector space. \cite{li2021improving} proposed a graph summarization technique using Graph LSTM and GCN to improve Question Answering on knowledge graphs and represent questions and entities/relations as low-dimension vectors, such that the key properties of the relations are well preserved in the vectors. In addition,~\cite{jin2018learning} developed an approach to learn representations of graphs with diverse sizes and encoded graphs into low-dimensional vectors based on the use of Graph LSTM.

Several studies also focused on evolving patterns of nodes in dynamic graphs. For instance, \cite{zhang2022dynamic} applied Graph LSTM and proposed a one-stage model called DynGNN. The model embeds an RNN into a GNN model to produce a representation in a compact form. Similarly, \cite{ma2020streaming} introduced a dynamic GRN model using Graph LSTM to model the dynamic information of the evolving graph to reduce dimensionality and manifold learning. Particularly, the model continuously updates the nodes’ information by recording the time intervals between edges, the sequential information of edges, and the coherent transmission of information. Another work by~\cite{goyal2020dyngraph2vec} also presented a method for learning temporal transitions in dynamic graphs utilising a deep architecture consisting mainly of dense and recurrent layers. The authors elaborated on the problem of model size and the number of weights to be trained, during the training phase by using a uniform sampling of the nodes.  

\subsubsection{GRU-based Approaches}
GRU is a variant of Graph LSTM with a gated RNN structure and compared to Graph LSTM, there are fewer training parameters. The number of gates in each model is the key distinction between them; LSTM has three gates consisting of ``input", ``output", and ``forget", while GRU units are less complex with only two gates of ``reset", and ``update". 

For the purpose of graph summarization, \cite{taheri2019learning} proposed the DyGrAE model that is able to learn the structure and temporal dynamics of a dynamic graph and transform it into a condensed dimension. To this end, the authors first deployed a GRU model to obtain a graph's topology and then combined it with an LSTM model to learn the graph’s dynamics. \cite{ge2022gr} also developed a gated recursive-based algorithm to solve the problems dealing with node aggregation and extracting deeply dependent features between nodes. Here, the GRU was employed to accomplish the aggregation task and structure the final model named GR-GNN. Moreover, 

\subsubsection{Remarks}
GRN-based techniques can efficiently capture significant information during recursive neighbourhood expansion by employing recurrent units to identify the long-term dependence across layers.
However, we would like to note that the performance of GRN models for graph summarization can largely improve the numerical stability during the training phase by using convolutional filters.

\subsection{GCN-based Approaches}  
The general idea of GCNs is to generalize the Convolutional Neural Networks (CNNs) on graph-structured data. The primary distinction between GCNs and GRNs is the way information is being propagated; while GCNs apply various weights at each timestep, GRNs apply the same weight matrices in an iterative manner until an equilibrium is reached.

In other words, GCN models are a sort of neural network architecture that supports graph structures and aggregates information of each node from its neighbourhood in a convolutional manner. GCN models have demonstrated a strong expressive capacity for learning graph representations and have achieved superior performance in graph summarization~\cite{zhang2019graph}. The works that have been done in this regard fall into two categories: Spectral-based and Spatial-based methods. 

\subsubsection{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. 

Although the computation contains well-defined translational properties, it is relatively expensive and the filters are not generally localized. Since the complexity grows with the scale of the graphs, one solution is to check only a limited number of neighbours using the Chebyshev theory~\cite{hammond2011wavelets}. This theory leads to several other research around applying approximation to the spectral graph convolution. For example, \cite{defferrard2016convolutional} generalized the CNNs to graphs by designing localised convolutional filters on graphs. They also introduced a graph summarization procedure that groups together similar vertices and a graph pooling procedure that focuses on producing higher filter resolution. The work has been regarded as the basis of several studies using Chebyshev polynomials to speed up convolution computations. As a variant, \cite{kipf2016semi} introduced several simplifications to the original framework that improves the performance of classification and scalability in large networks. More recent
successful variations of the mentioned methods, S-GCN~\cite{wu2019simplifying} and later SIGN~\cite{rossi2020sign}, have been proposed. S-GCN is a simplified GCN model that does not compromise the effectiveness and performance of graph summarization. The idea behind the S-GCN model is to first convert large convolutional filters to small ones and then remove the final non-linear layers. Inspired from the previous GCN models, ~\cite{rossi2020sign} proposed SIGN which scales GCNs 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 GCN approaches for graph summarization is around the transformation of graph objects, e.g, embedding. For example, \cite{jiang2020hi} introduced a hierarchical GCN for graph embedding. The authors built upon a spectral GCN to provide an effective representation learning for an end-to-end graph classification task. Particularly, they proposed a framework for learning graph feature embeddings while also taking into account the network architecture and relationships between the subjects. Plus, \cite{deng2019graphzoom} proposed a multilevel framework to improve the scalability and accuracy of embedding in an unsupervised manner. The model initially generates a new graph that efficiently contains both the information of 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.

\subsubsection{Spatial-based Approaches}
Spatial-based methods work on the local neighbourhood of nodes and aggregate node representations from the neighbour nodes to understand their properties. GCNs 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 for graph summarization challenges.

As a closely related approach to~\cite{kipf2016semi}, GraphSAGE extended the framework to the inductive setting~\cite{hamilton2017inductive}. GraphSAGE was the first to introduce node-wise sampling coupled with minibatch training for node embeddings using spatial convolutions. \cite{chen2018fastgcn}
also proposed a similar node-wise sampling approach named FASTGCN which is enhanced with importance sampling method. Later, 
\cite{huang2018adaptive}
and~\cite{zeng2019graphsaint}
introduced layer-wise and graph-wise sampling methods to enhance the performance of the summarization. 
While~\cite{huang2018adaptive} focused on the redundancy issue of node-wise sampling, GraphSAINT~\cite{zeng2019graphsaint} elaborated on correcting the bias and variance of the minibatch estimators when sampling subgraphs for training. The most recent variation of GraphSage for bipartite graphs with various node types and inter-layer edges is presented by~\cite{li2020hierarchical}. The authors introduced bipartite GraphSAGE on a user-item graph to perform both user and item embedding. In other words, the model embeds the nodes into two different feature spaces which are relevant to users and item nodes’ information.

Many aggregation-based methods have also been introduced to summarize graphs without sacrificing too much information within the original graphs. The summarized graph can assist on further network analysis and graph mining tasks. For example, \cite{yan2019groupinn} proposed a summarization within a GCN for faster training, data denoising and interpretability. The authors used an end-to-end neural network model with a node grouping layer to minimise dimensionality in order to achieve summarization.~\cite{hu2019hierarchical} took structural similarity into consideration and aggregated nodes that shared a similar structure into hypernodes and then refined the summarized graph to restore each node's representation. To this end, the authors introduced a deep hierarchical GCN (H-GCN) architecture for semi-supervised node classification with several coarsening operation layers followed by several refinement operation layers. The refinement layers are designed to restore the structure of the original graph for the graph classification task.

\subsubsection{Remarks}
Most existing GCNs 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 which makes it a dynamic network. To this end, learning GCNs on static graphs may not yield the best results. Hence, more research is needed to be done on dynamic GCN models to enhnce the performance of summarization tasks on large-scale dynamic graphs. 

\subsection{GAE-based Approaches} 
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. Graph Autoencoder or GAE is a type of GNN that can be applied over graph structures. Lately, GAE has gained increasing interest in graph summarization since it has demonstrated significant potential in dimensionality reduction~\cite{cai2018comprehensive}.

Most existing GAE-based approaches for graph summarization use combined architectures with GCNs or GRNs. For example, \cite{kipf2016variational} proposed the variational graph autoencoder (VGAE) using a two-layer GCN model based on their previous work on spectral convolutions~\cite{kipf2016semi} for undirected graphs. VGAE is based on variational autoencoders~\cite{kingma2013auto} whose main concept is to embed the input into a distribution rather than a point, and from there, choose a random sample from the distribution rather than having it created by the encoder directly. As an extension, \cite{hajiramezanali2019variational} constructed a variational graph recurrent neural network by integrating GRN and GAE to model dynamics of node attributes and topological dependencies. The introduced model aims to learn interpretable latent graph representation as well as modelling sparse dynamic graphs.

There are also several GAE aggregation-based approaches addressing the challenges in graph clustering tasks as a summarization problem. For example, \cite{cai2021grae} proposed a graph recurrent autoencoder model for attributed multi-view graph clustering. 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, two separate models are developed, global graph autoencoder (GGAE) and partial graph autoencoder (PGAE). While GGAE is designed to learn the common features of all the views, PGAE aims to capture the unique features.

\subsubsection{Remarks}
Most GAE-based approaches are typically un-regularized mainly focusing on minimizing the reconstruction error and ignoring the data distribution of the latent space. When working with sparse and noisy real-world graph data, this might lead to poor graph summarization. Although there are some works around GAE regularization \cite{pan2018adversarially}, more research is needed in this regard. 

\subsection{GAT-based Approaches} 
The attention mechanism was initially introduced by~\cite{bahdanau2014neural} to allow modelling long dependencies in sequential data and improve the performance of autoencoders. The main idea of the mechanism was to enable 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~\cite{velivckovic2017graph} is based on the same idea, using attention-based neighbourhood aggregation and providing different weights to various nodes in a neighbourhood. The model is one of the most popular GNN models for node aggregation which is able to reduce the storage complexity and the number of nodes and edges.

Today, GAT is considered the most advanced model for learning with large-scale graphs. However, recently~\cite{brody2021attentive} argued how attentive GAT are and discussed that GAT does not actually compute dynamic attention and it only computes a restricted static form of attention. Instead, they introduced GATv2, a new version of the attention network, which is capable of expressing problems that require computing dynamic attention. The authors focused on the importance of dynamic weights and argued that the problem can be fixed by changing the sequence of internal processes in the GAT equations.

As another variation of GAT,~\cite{xie2020mgat} proposed a novel Multi-view Graph Attention Network named as MGAT to develop low dimensional representation learning based on attention mechanism in a multi-view manner. The authors focused on a view-based attention approach to aggregate the view-based node representation and integrate various types of relationships in multiple views. Moreover,~\cite{tu2021conditional} discussed a recommendation task using graph summarization and refinement techniques for a bipartite user-item graph. The authors highlighted employing a conditional attention mechanism on task-based sub-graphs to determine users' preferences and emphasized the significance of summarizing and enhancing knowledge graphs in recommender systems.

\subsubsection{Remarks}
GAT-based approaches leverage attentional layers to address the shortcomings of prior studies based on graph convolutions. While convolutional-based approaches use predefined weights for the neighbours of a node, GAT-based approaches modify the aggregation process through the attention mechanism. Due to recent advancements in this area, we expect more research in using GATs for presenting a condensed representation of static~\cite{velivckovic2017graph} and dynamic~\cite{brody2021attentive} graphs or manifold structures in the future.

\section{Graph Reinforcement Learning}
\label{GRL}

Reinforcement Learning (RL) is a sequential decision mathematical model that allows an agent to learn to take actions via trial and error in an interactive setting while receiving feedback from its own experiences. Due to the success and fast growth of RL in interdisciplinary fields, recently scholars have been inspired to investigate RL models on graph-structured data as well and named it Graph Reinforcement Learning or GRL~\cite{mingshuo2022reinforcement}. 

There is a blooming line of research on GRL for graph summarization elaborating on using it for evaluating and improving the quality of graph summaries. For example, \cite{amiri2018netgist} introduced a task-based GRL framework to automatically learn how to generate a summary on a given network. In order to have an optimal solution for finding the best task-based summary, the authors made use of CNN layers in combination with an RL technique. To improve the quality of graph summary,~\cite{amiri2020netreact} proposed NetReAct, an interactive learning framework for graph summarization. The model uses human feedback with RL for the summarization and visualisation of document networks. NetReAct also provides summaries with various sizes, allowing the user to zoom in on each document group to examine numerous summaries, and so providing a multi-level comprehension of the data. Another work,~\cite{wickman2021sparrl}, presented a graph sparsification framework empowered by GRL to be used for any edge sparsification assignment with a specific target for reduction. The model uses the edge reduction ratio as input and uses a learning model to decide how best to prune edges and also maintain the required graph structural attribute at the same time. Moreover, \cite{yan2019spatially} introduced a GRL approach to summarize geographic knowledge graphs. To obtain a more thorough understanding of the summarising process, the model exploits components with spatial specificity and includes both extrinsic and intrinsic information in the graph. The authors then discussed the effectiveness of the spatial-based model and compared the results with models with non-spatial entities. 

\subsubsection{Remarks}
GRL for graph summarization has attracted increasing attention, owing to its remarkable performance in improving the quality of graph summaries. Unlike other sequential data such as images, texts or videos, the evolving patterns in graph structure data usually have higher heterogeneity. Designing customized deep GRL architectures for the purpose of graph summarization would be a promising direction in the future.


\section{Conclusion and Open Challenges}
\label{conc}

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

Through extensive efforts have been made and impressive results have been obtained on many benchmarks on GNNs for graph summarization, there are still several open challenges. We hope this study and the following discussions on emerging topics provide researchers and practitioners in related fields with a comprehensive understanding of recent approaches and shed some light on designing novel and practical methods for graph summarization.

\begin{itemize}    
    \item \textbf{Multi-layer Graphs} \\ 
    Multi-layer graphs are made up of multiple layers of interconnected entities. They have recently been used for the representation of complex graphs where the entities and their connections come in heterogeneous types. Working with real multi-layer graphs can be challenging due to the existence of large portions of redundant or irrelevant data. Moreover, the traditional methods are not practically suitable for analyzing large-scale multi-layer graphs. In order to make these graphs easier to analyze, a number of GNN-based have been developed to support transformation-based summarization in the literature~\cite{interdonato2020multilayer}. However, the current techniques fail to provide an interpretable representation of the layered graphs with properties related to nodes, edges, actors, and layers. Hence, more focus should be given to developing more effective and comprehensive summarization techniques for multi-layer graphs.
    
    \item \textbf{Dynamic Graphs} \\
    Graphs may evolve over time with changes in graph topology (e.g., appearing or disappearing nodes and/or edges) or their node attributes which may cause fundamental changes to the entire graph. They evolve over time and are typically regarded as a series of graph snapshots that are taken at various time increments. With dynamic graphs, GNN-based models should be trained over these snapshots which cause a number of challenges with the extraction of dynamic features. Recently, several GNN-based approaches have been developed to tackle the problem by leveraging methods and theories in attention mechanism and GATs~\cite{brody2021attentive} as the most advanced model for learning with dynamic large-scale graphs and manifolds. However, the research is still in its infancy and requires further study on popularizing the model to more complex graph networks.
    
    \item \textbf{Multi-label Graphs}\\
    Deep graph convolutional models have shown great performance for single-label graph summarization tasks such as classification as an aggregation-based method. However, graphs in the real world are often naturally multi-label, hence it is required to go beyond the single-label classification and consider the graphs with multiple specific labels on their nodes and edges. Despite a few recent works to achieve scalability~\cite{zong2020gnn}, it has not been fully investigated how to deal with graphs with multiple labels. In this learning scenario, identifying the shared information among multiple labels is still a challenging task for the purpose of dimensionality reduction.

                
    \item \textbf{Task-based Summarization} \\
    As the size of the graphs is increasing exponentially our understanding of them is dropping. Instead, these graphs may be summarized to expose important information, aid in sensemaking, and speed up current graph analysis techniques. 
    Graph summarization is essential to expose important information, aid in sensemaking, and speed up current graph analysis techniques. 
    Different summaries are intuitively required for various purposes and tasks. For example, the graph summarization strategy to detect communities is different from the strategy that should be taken for finding the most influential nodes. This indicates that we should develop a unique approach to identify similar patterns for each task. Even while task-based summarization is highly essential with a few successes~\cite{amiri2018netgist,amiri2020netreact}, this field of study to generate high-quality graph summaries is still underexplored. The 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.
            
    \item \textbf{Evaluation Benchmarks} \\
    When the process of graph summarization is terminated, it is expected to come with a ``good" summary of the original graph. Evaluating the goodness of the summarized graphs is an application-specific task and can be done from different perspectives. For example, sampling-based methods are evaluated on the quality of sampling; aggregation-based methods are evaluated on the quality of classification; and so on. Current studies use common evaluation metrics based on a comparison between a novel  and an established well-known method. For instance, the metrics that have been used in the literature mostly focus on information loss, ease of visualization, or sparsity~\cite{liu2018graph}. Further elaboration on evaluation metrics is required for cases where the validation becomes complex and more elements are involved, such as visualization and multi-resolution summaries.
                
\end{itemize}

 \section*{Acknowledgments}
We acknowledge the Centre for Applied Artificial Intelligence \footnote{https://www.mq.edu.au/research/research-centres-groups-and-facilities/centres/centre-for-applied-artificial-intelligence} at Macquarie University for funding this study.

\bibliographystyle{named}
