Neural networks for structured data like graphs have been studied extensively in recent years.
 To date, the bulk of research activity has focused mainly on static graphs.
 However, most real-world networks are dynamic since their topology tends to change over time.
 Predicting the evolution of dynamic graphs is a task of high significance in the area of graph mining.
 Despite its practical importance, the task has not been explored in depth so far, mainly due to its challenging nature.
 In this paper, we propose a model that predicts the evolution of dynamic graphs.
 Specifically, we use a graph neural network along with a recurrent architecture to capture the temporal evolution patterns of dynamic graphs.
 Then, we employ a generative model which predicts the topology of the graph at the next time step and constructs a graph instance that corresponds to that topology.
 We evaluate the proposed model on several artificial datasets following common network evolving dynamics, as well as on real-world datasets.
 Results demonstrate the effectiveness of the proposed model. Graph neural networks (GNNs) have emerged in recent years as an effective tool for analyzing graph-structured data (Scarselli et al., 2008; Gilmer et al., 2017; Zhou et al., 2018; Wu et al., 2019) . These architectures bring the expressive power of deep learning into non-Euclidean data such as graphs, and have demonstrated convincing performance in several graph mining tasks, including graph classification (Morris et al., 2019) , link prediction (Zhang & Chen, 2018) , and community detection Chen et al., 2017) . So far, GNNs have been mainly applied to tasks that involve static graphs. However, most real-world networks are dynamic, i. e. , nodes and edges are added and removed over time. Despite the success of GNNs in various applications, it is still not clear if these models are useful for learning from dynamic graphs. Although some models have been applied to this type of data, most studies have focused on predicting a low-dimensional representation (i. e., embedding) of the graph for the next time step (Li et al., 2016; Nguyen et al., 2018; Goyal et al., 2018; Seo et al., 2018; Pareja et al., 2019) . These representations can then be used in downstream tasks (Li et al., 2016; Goyal et al., 2018; Meng et al., 2018; Pareja et al., 2019) . Predicting the topology of the graph is a task that has not been properly addressed yet. Graph generation, another important task in graph mining, has attracted a lot of attention from the deep learning community in recent years. The objective of this task is to generate graphs that exhibit specific properties, e. g. , degree distribution, node triangle participation, community structure etc. Traditionally, graphs are generated based on some network generation model such as the Erdős-Rényi model. These models focus on modeling one or more network properties, and neglect the others. Neural network approaches, on the other hand, can better capture the properties of graphs since they follow a supervised approach (You et al., 2018; Bojchevski et al., 2018; Grover et al., 2018) . These architectures minimize a loss function such as the reconstruction error of the adjacency matrix or the value of a graph comparison algorithm. Capitalizing on recent developments in neural networks for graph-structured data and graph generation, we propose in this paper, to the best of our knowledge, the first framework for predicting the evolution of the topology of networks in time. The proposed framework can be viewed as an encoderdecoder architecture. The "encoder" network takes a sequence of graphs as input and uses a GNN to produce a low-dimensional representation for each one of these graphs. These representations capture structural information about the input graphs. Then, it employs a recurrent architecture which predicts a representation for the future instance of the graph. The "decoder" network corresponds to a graph generation model which utilizes the predicted representation, and generates the topology of the graph for the next time step. The proposed model is evaluated over a series of experiments on synthetic and real-world datasets. To measure its effectiveness, the generated graphs need to be compared with the corresponding ground-truth graph instances. To this end, we use the Weisfeiler-Lehman subtree kernel which scales to very large graphs and has achieved state-of-the-art results on many graph datasets (Shervashidze et al., 2011) . The proposed model is compared against several baseline methods. Results show that the proposed model is very competitive, and in most cases, outperforms the competing methods. The rest of this paper is organized as follows. Section 2 provides an overview of the related work and elaborates our contribution. Section 3 introduces some preliminary concepts and definitions related to the graph generation problem, followed by a detailed presentation of the components of the proposed model. Section 4 evaluates the proposed model on several tasks. Finally, Section 5 concludes. In this paper, we proposed EvoNet, a model that predicts the evolution of dynamic graphs, following an encoder-decoder framework. We also proposed an evaluation methodology for this task which capitalizes on the well-established family of graph kernels. Experiments show that the proposed model outperforms traditional random graph methods on both synthetic and real-world datasets.
Combining graph neural networks and the RNN graph generative model, we propose a novel architecture that is able to learn from a sequence of evolving graphs and predict the graph topology evolution for the future timesteps
{"src": "scitldr-AIC_train", "paper_id": "Byg5flHFDr"}