EvoNet: A Neural Network for Predicting the Evolution of Dynamic Graphs
Authors: Changmin Wu
Giannis Nikolentzos
Michalis Vazirgiannis
Venue:  (2020)
Keywords: temporal graphs
graph neural network
graph generative model
graph topology prediction

Abstract: 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. 

Under review as a conference paper at ICLR 2020
EVoNET: A NEURAL NETWORK FOR PREDICTING THE EVOLUTION OF DYNAMIC GRAPHS
Anonymous authors Paper under double-bling review
ABSTRACT
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 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 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, employ 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.
INTRODUCTION
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 al. 2018 Wu et al. (201)) These architectures bring the expressive power of deep learning into non non-Euclidean data such as graphs, and have demonstrated convincing performance
several graph mining tasks, including
graph classification (Morris et al. 2019), link prediction (Zhang & Chen 2018 and community detection (Bruna Li][0017 Chen 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 diwe-siinnion representation
(i.e., embedding) of the graph for the next time step (Li al. 2016; 2017; Nguyen et al. 2018
Goyal et al. 2018 Seo et al. 2018: Pareja et al.] 2019). These representations can then be used downstream tasks (Li et 2016 Goyal al. 2018 Meng et al., 2018 Pareja al. 2019).
Predicting the topology of the graph is task that has not been properly addressed yet.
Graph generation, another important task in graph mining, has attracted 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 Brdōs-Rééyj 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 Boochevski et al., 2018: Grover et al. 2018). These architectures minimize a loss function such the reconstruction error of the adjacency matrix the value a graph comparison algorithm.
Capitalizing recent developments in neural networks for graph-structured data and graph genera- tion, we propose in this paper, to the best our knowledge, the first framework for predicting the evolution of the topology of networks in time. The proposed framework can be viewed as encoder- decoder architecture. The "encoder" network takes a sequence of graphs as input and uses a GNN to produce low-dimensional representation for each one of these graphs. These representations capture

---

Under review as a conference paper at ICLR 2020
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 graph generation model which utilizes the predicted representation, and generates the topology of the graph for the next time step. The proposed model 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-Lchmal subtree kernel which scales very large graphs and has achieved state-of-the-art results on many graph datasets (Shervashidze et al. (011). 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 introduuce some preliminary concepts and definitions related to the graph generation problem, followed by a detailed presentation of the components of the proposed model. Section evaluates the proposed model on several tasks. Finally, Section concludes.
2 RELATED WORK
Our work is related to random graph models. These models are very popular in graph theory and network science. The Erdös-Rényi model (Erdōs & Rényi 1960), the preferential attachment model (Albert & Barabási 2002), and the Kronecker graph model (Leskovec et al. 2010) are some typical examples of such models. To predict how a graph structure will evolve over time, the values of the parameters of these models can be estimated based on the corresponding values of the observed graph instances, and then the estimated values can be passed on to these models to generate graphs
Other work along similar direction includes neural network models which combine GNNs with RNNs (Seo et af.) 2018: Manessi et al., 2017 Pareja et al., 2019). These models use GNNs to extract features from graph and RNNs for sequence learning from the extracted features. Other similar approaches do not use GNNs, but they instead perform random walks or employ deep autoencoders (Nguyen et al. 2018 Goyal et al. 2018). All these works focus on predicting how the node representations or the graph representations will evolve over time. However, some applications require predicting the topology of the graph, and not just its owwdiimesionnl representation. The proposed model constitutes the first step towards this objective.
EVoNET: A NEURAL NETWORK FOR PREDICTING GRAPH EVOLUTION
In this Section, we first introduce basic concepts from graph theory, and define our notation. We then present EvoNet, the proposed framework for predicting the evolution graphs. Since the proposed model comprises of several components, we describe all these components in detail.
3.1 PRELIMINARIES
Let G = (V, E) be an undirected, unweighted graph, where V is the set of nodes and E is the set of edges. We will denote by n the number of vertices and by m the number of edges. We define permutation of the nodes of G as a bijective function я : V - V. under which any graph property of G should be invariant. We are interested in the topology of graph which is described by its adjacency matrix A E Raxx with a specific ordering of the nodes m Each entry of the adjacency matrix is defined as Ab,- = (((r(t)))tt)))) NeE where Vi, Vj V. In what follows, consider the "topology", "structure" and "adjacency matrix" of a graph equivalent to each other.
In many real-world networks, besides the adjacency matrix that encodes connectivity information, nodes and/or edges are annotated with a feature vector, which we denote as X E Rn and L e gm respectively, Hence, graph object can be also written in the form of a triplet G (A, X, L). In this paper, we use this triplet to represent all graphs. If a graph does not contain node/edge attributes, we assign attributes based on local properties (e. g., degree, c-core number, number of triangles, etc).
For simplicity, the ordering я will he omitted in what follows.
2

---

Under review as a conference paper at ICLR 2020
Pradicted gragh arc,
Gouph gennatex (Dvooder)
ECTM
IATM
Lind
1STM
IUBIO
Dysunsc graph, aubebiling
3.4M
ERTM
BBC
Geagt smabeddtgg
Message Fassing Graph Neural Netwerk
frow
Ep-1
Figure 1: Illustration of the proposed architecture
An evolving network is graph whose topology changes function of time. Interestingly, almost all real-world networks evolve over time by adding and removing nodes and/or edges. For instance, in social networks, people make and lose friends and others who leave the network. An evolving graph is sequence of graphs (9o. 9I.... ... Gr where G. (Ae, X,, E,) represents the state of the evolving graph time step should be noted that not only nodes and edges can evolve over time, but also node and edge attributes. However, in this paper, we keep node and edge attributes fixed, and we allow only the node and edge sets of the graphs to change as function of time. The sequence can thus be written as {G, = (Ae, X, E) (e..or) We are often interested in predicting what "comes next" in a sequence, based on data encountered in previous time steps. In our setting, this is equivalent to predicting G. based on the sequence {Gi Jkct. In sequential modeling, we usually do not take into account the whole sequence, but only those instances within fixed small window of size before G.. which we denote {Gr-ar, Gt -r-w+t-........ Gr-1) refer to these instances as the graph history. The problem then to predict topology of G. given its history.
time, while there people who join the network
3.2 PROPOSED ARCHITECTURE
The proposed architecture is very similar to typical sequence learning framework. The main difference lies in the fact that instead of vectors, in our setting, the elements the sequence correspond to graphs. The combinatorial nature of graph-structured data increases the complexity of the problem and calls for more sophisticated architectures than the ones employed in traditional sequence learning tasks. Specifically, the proposed model consists of three components: (1) graph neural network (GNN) which generates vector representation for each graph instance, (2) recurrent neural network (RNN) for sequential learning, and (3) graph generation model for predicting the graph topology at the next time step. This framework can also be viewed as an autoencoder-decoderr model. The first two components correspond to an encoder network which maps the sequence of graphs into a sequence of vectors and predicts representation for the next in the sequence graph. The decoder network consists of the last component of the model, and transforms the above representation into graph. Figure [ illustrates the proposed model. In what follows, we present the different components of EvoNet in detail.
3.2.1 GRAPH NEURAL NETWORK
Graph Neural Networks (GNNs) have recently emerged as a dominant paradigm for performing machine learning tasks graphs. Several GNN variants have been proposed in the past years. All these models employ some message passing procedure to update node representations. Specifically, each node updates its representation by aggregating the representations of its neighbors. After
3

---

Under review as a conference paper at ICLR 2020
iterations of the message passing procedure, each node obtains feature vector which captures the structural information within its h-hop neighborhood. Then, GNNs compute a feature vector for the entire graph using some permutation invariant readout function such summing the representations of all the nodes of the graph. As described below, the learning process can be divided into three phases: (1) aggregation, (2) update, and (3) readout.
Aggregation In this phase, the network computes a message for each node of the graph. To compute that message for node, the network aggregates the representations of its neighbors. Formally, at time + 1, a message vector n 1+1 is computed from the representations of the neighbors N (v) of u:
my AGGREGATE (f | w E [))
(1)
where AGGREGATE is a permutation invariant function. Furthermore, for the network to be end-to- end trainable, this function needs to be differentiable. In our case, AGGREGATE is multi-layer perceptron (MLP) followed by sum function.
Update The new representation h++1 of v is then computed by combining its current feature vector hy with the message vector m (+1; I;
h+t UPDATE*+1 (hi (6
The UPDATE function also needs to be differentiable. To combine the two feature vectors (i. e., h and 1 we have employed the Gated Recurrent Unit proposed in (Li et al. 2015):
A = GRU (hG,m,"1)
(3)
Omitting biases for readability, we have:
r oW m + Ukt hi))
++1 + +UZ+11 h+)) 2 oW m
(4)
h41 tanh( m 1+1 + UC+ (r の Mt)
A. = (1 - o @ hi + + @ h
where the W and U matrices trainable weight matrices, o is the sigmoid function, and r, and 2y are the parameters of the reset and update gates for given node.
Readout The Aggregation and Update steps are repeated for 7 time steps. The emerging node repre- sentations {hi²) } vev are aggregated into a single vector which corresponds to the graph representation, as follows:
hG = READOUT((1,, VVV
(5)
where READOUT is a differentiable and permutation invariant function. This vector captures the topology of the input graph. To generate hG. we utilize Ser2Ser (Vinyals et al.) 2015). Other functions such as the sum function were also considered, but were found less effective in preliminary experiments.
3.2.2 RECURRENT NEURAL NETWORKS
Given an input sequence of graphs, we use the GNN described above to generate a vector repre- sentation for each graph in the sequence. Then, to process this sequence, we a recurrent neural network (RNN). RNNs use their internal state (i. e., memory) to preserve sequential information. These networks exhibit temporal dynamic behavior, and can find correlations between sequential events Specifically, an RNN processes the input sequence in a series of time steps (i. e.. one for each element in the sequence). For a given time step t, the hidden state h2 at that time step is updated as:
h411 = f(,,, T1+1)
(6)
where f is non-linear activation function. A generative RNN outputs probability distribution over the next element of the sequence given current state ht RNNs can be trained to predict the next el- ement (e. g., graph) in the sequence, i. e., it can learn the conditional distribution GGG.GG....... G.-1), In our implementation, we use a Long Short-Tern Memory (LSTM) network that reads sequentially the vectors {ha, Jiejsw..--w produced by the GNN, and generates a vector hGr that represents the embedding of Gr. e., the graph at the next time step. The embedding incorporates topological information and will serve as input the graph generation module. Along with the GNN component, this architecture can be seen as a form of an encoder network. This network takes as input a sequence of graphs and projects them into low-dimensional space.
4

---

Under review as a conference paper at ICLR 2020
3.2.3 GRAPH GENERATION
To generate graph that corresponds the evolution of the current graph instance, capitalize on a recently-proposed framework for learning generative models of graphs Yoou et al. 2018). This framework models a graph in an autoregressive manner (i. e., a sequence additions of new nodes and edges) to capture the complex joint probability of all nodes and edges in the graph. Formally, given a node ordering n, it considers a graph G sequence of vectors:
Sg = (S ......,
Siv
where S." = [a1....................... a: 9-11. E (0, 1 is the adjacency vector between node rii) and the nodes preceding it (1T(1), ...,, 7i ())). We adapt this framework our supervised setting.
The objective of the generative model is to maximize the likelihood of the observed graphs of the training set. Since graph can be expressed sequence of adjacency vectors (given node ordering), we can consider instead the distribution p( p(ST:0) 0), which can be decomposed in an autoregressive manner into the following product:
IV
VI 1-1 IIIII
p(S":0) = II P(S S 0)
p(aja Claeey.
Su Stakei 0)
(8)
==1==1
This product can be parameterized by neural network. Specifically, following YYuu et al. 2018).
use hierarchical RNN consisting of two levels: (1) the graph-level RNN which maintains the state of the graph and generates nodes and thus learns the distribution 1 ( and (2) the
edge-level RNN which generates links between each generated node and nreviously-general nodes and thus learns the distribution p(āz, (āt,)))) More formally, we have:
ho = her
h; RNNI(1i-1) ST-))
mg, hi m = RNN 05 -5-1,)
(9)
p p(a j,1 = 1) = a(mja))
7 P
where h; is the state vector of the graph-level RNN ei. RNN;) that encodes the current state of the graph sequence and initialized by higr the predicted embedding of the graph at the next time step T. The output of the graph-level RNN corresponds the initial state of the edge-level RNN (i. e.. RNN2). The resulting value is then squashed by a sigmoid function to produce the probability of existence of an edge aj,s- In other words, the model learns the probability distribution of the existence of edges and graph can then be sampled from this distribution, which will serve as the predicted topology for the next time step T.
To train the model, the cross-entropy loss between existence of each edge and its probability of existence is minimized:
V 1-1 ΣΣ 21j=1
= 1)) + =)) (1-05,)00cs =
(10)
Node ordering should mentioned that node ordering has a large impact on the efficiency of the above generative model. Note that a good ordering can help avoid the exploration of all possible node permutations in the sample space. Different strategies such as the Breadth-First Firrt------t ordering scheme can be employed improve scalability (You et al., 2018). However, in setting, the nodes are distinguishable, i. e., node v of G, and node v of G correspond to the same entity. Hence, we can impose ordering onto the nodes of the first instance of our sequence of graphs, and then utilize the same node ordering for the graphs of all subsequent time steps (we place new nodes at the end of the ordering).
4 EXPERIMENTS AND RESULTS
In this Section, we evaluate the performance of EvoNet on synthetic and real-world datasets for predicting the evolution of graph topology, and compare it against several baseline methods.
5

---

Under review as a conference paper at ICLR 2020
4.1 DATASETS
We use both synthetic and real-world datasets. The synthetic datasets consist of sequences of graphs where there specific pattern on how each graph emerges from the previous graph instance, i. add/remove some graph structure at each time step. The real-world datasets correspond to single graphs whose nodes incorporate temporal information. We decompose these graphs into sequences of snapshots based on their timestamps. We fix the length of the sequences to 1000 time steps. The size of the graphs in each sequence ranges from tens of nodes to several thousand of nodes.
4.1.1 SYNTHETIC DATASETS
Path graph A path graph can be drawn such that all vertices and edges lie on straight line. We denote a path graph of n nodes as Pn. In other words, the path graph P. is a tree with two nodes scenarios. In both cases the
of degree 1, and the other n 2 nodes of degree We consider first graph in the sequence is P3. In the first scenario, at each time step, we add one new node to the previous graph instance and we also add an edge between the new node and the last according the previous ordering node. The second scenario follows the same pattern, however, every three steps, instead of adding a new node, we remove the first according to the previous ordering node (along with its edge).
Cycle graph A cycle graph C, a graph on n nodes containing single cycle through all the nodes. Note that if we add an edge between the first and the last node of Pn, we obtain C.. Similar to the above case, we use C'3 as the first graph in the sequence, and we again consider two scenarios. In the first scenario, each time step, we increase the size of the cycle, i. c.. from C₁, we obtain C++1 by adding a new node and two edges, the first between the new node and the first according to the previous ordering node and the second between the new node and the last according the previous ordering node. In the second scenario, every three steps, we remove the first according to the ordering node (along with its edges), and add an edge between the second and the last according to the ordering nodes.
Ladder graph The ladder graph 4., a planar graph with 2n vertices and 3n 2 edges. It the cartesian product of two path graphs, as follows: L, Pa x P2. As the name indicates, the ladder graph L, can be drawn as a ladder consisting of two rails and rungs between them. We consider the following scenario: at each time step, we attach one rung (P2) to the tail of the ladder (the two nodes of the rung are connected to the two last according to the ordering nodes).
For all graphs, we set the attribute of each node equal to its degree, while we set the attribute of all edges to the same value (e. g., to 1).
4.1.2 REAL-WORLD DATASETS
Besides synthetic datasets, we also evaluate EvoNet on real-world datasets. These datasets contain graphs derived from the Bitcoin transaction network, a who-trust-whom network of people who trade using Bitcoin (Kumar al., 2016 2018). Due the anonymity of Bitcoin users, platforms seek to maintain a record of users' reputation in Bitcoin trades to avoid fraudulent transactions. The nodes of the network represent Bitcoin users, while an edge indicates that a trade has been executed between its two endpoint users. Each edge is annotated with an integer between - 10 and 10, which indicates the rating of the one user given by the other user. The network data are collected separately from two platforms: Bitcoin O and Bitcoin Alpha More details about these two datasets given in Table I For all graphs, we set the attribute of each node equal to the average rating that the user has received from the rest of the community, and the attribute of each edge equal to the rating between its two endpoint users.
4.2 BASELINES
We compare EvoNet against several random graph models: (1) the Erdös-Rényi model (Erdós & Rényī 1960), (2) the Stochastic Block model (Holland et al. 1983 Airoldi et al. 2008). ) (3) the

---

Under review as a conference paper at ICLR 2020
TIMESPAN
[V]
[8]
% POS.EDGES
BEGIN
END
BTC-OTC
5,881
35, 592
89%
2010-11-8 2010-11-8
2016-1-25
BTC-ALPBA
3, 783
24, 186
93%
2016-1-22
Table 1: Statistics of the two real-world datasets used in our experiments.
groder.rpphhhoooooooooooo Sizc. Rs Prodict
Cycle graph Real Predict
140
3900
140
2000
100
1000
Chuphh Brdeos
200
289
Graphindes
Figure 2: Results of synthetic datasets. Comparison of graph size (path, ladder and cycle graphs from left to right): predicted size (blue) VS. real size (orange).
Barabási-Allert model (Albert & Barabási 2002), and (4) the Kronecker Graph model (Leskoved et al. 2010). These are the traditional methods to study the topology evolution of temporal graphs, by proposing a driven mechanism behind the evolution.
4.3 EVALUATION METRIC AND EXPERIMENTAL SETUP
In general, it is very challenging to measure the performance of graph generative model since it requires comparing two graphs to each other, long- songg-ianiing problem in mathematics and computer seience (Conte al., 2004). We propose to graph kernels to compare graphs to each other, and thus to evaluate the quality of the generated graphs. Graph kernels have emerged as one of the most effective tools for graph comparison in recent years (Nikolentzos et al., 2019). A graph kernel is a symmetric positive semidefinite function which takes two graphs as input, and measures their similarity. In our experiments, we employ the Weisfeiler-Lehman subtree kernel which counts label- subtree- subtree-pateers patterns (Shervashidze et al. 2011). Note that we also normalize the kernel values, and thus the emerging values lie between and 1.
As previously mentioned, each dataset corresponds to a sequence of graphs where each sequence represents the evolution of the topology of a single graph in 1000 time steps. We use the first 80% of these graph instances for training and the rest of them serve as our test set. The window size w is set equal to 10, which means that we feed 10 consecutive graph instances to the model and predict the topology of the instance that directly follows the last of these 10 input instances. Each graph of test set along with its corresponding predicted graph is then passed on to the Weismeiler-Lehman subtree kernel which measures their similarity and thus the performance of the model.
The hyperparameters of EvoNet are chosen based on its performance on a validation set. The parameters of the random graph models are set under the principle that the generated graphs need to share similar properties with the ground-truth graphs. For instance, in the case of the Réngi edge between two nodes is set to some value such that the density
model, the probability of adding of the generated graph is identical to that of the ground-truth graph. However, since the model should not have access to such information (e. g., density of the ground-truth graph), we use MLP to predict this property based on past data (i. e., the number of nodes and edges of the previous graph instances). This is in par with how the proposed model computes the size of the graphs be generated ei. using also an MLP).
4.4 RESULTS
Synthetic datasets Figure iillustrates the experimental results on the synthetic datasets. Since the graph structures contained in the synthetic datasets are fairly simple, it is easy for the model to
7

---

Under review as a conference paper at ICLR 2020
butiion of Similanties between real and predicted graphs (BTC-GTC) Peproce
Distribution Simlanbles between real predicted grapts (BTC-AL
more Rerel
moss Kary
37
Powetize
Purbeet rosante
201
Sinkurtyy
Figure 3: Similarity histograms on BTC-OTC (left) and BTC-Alpha (right) datasets. Blue one is the result of EvoNet, which is compared against 6 random graph models.
STAT.
ВTC-OTC
BTC-ALPHA
MODEL
MEAN
90%ILE
MEAN
90%ILE
ER
0.28
0.40
0.22
0.32
SBM
0.21
0.30
0.18
0.27
BA
0.35
0.48
0.23
0.28
POWER
0.35
0.48
0.23
0.28
KRON-RAM
0.62
0.64
0.44
0.47
KRON-FIX
0.21
0.23
0.08
0.11
EVONET
0.82
0.84
0.55
0.59
Table 2: Statistics on the similarity distribution of different models: ER stands for Erdös-Rényi model. SBM stands for Stochastic Block Model. BA Barabási-Albert Model. POWER another model, similar to the Barabási-Albert that grows graphs with powerlaw degree distribution. Kron-Rate represents the Kronecker Graph Model with learnable parameter while Kron-Fix represents the Kronecker Graph Model with fixed parameters which depend on the initial graph.
generate graphs very similar to the ground-truth graphs (normalized kernel values 0.9). Hence, instead of reporting the kernel values, we compare the size of the predicted graphs against that the ground-truth graphs. The figures visualize the increase graph size on real sequence (orange) and predicted sequence (blue). For path graphs, in spite of small variance, we have an accurate prediction on the graph size. For ladder graph, we observe mismatch at the beginning of the sequence for small size graphs but then coincidence of the two lines on large size graphs. This mismatch on small graphs may be due to more complex structure ladder graphs such as cycles, as supported by the results of cycle graph on the right figure, where we completely mispredict the size of cycle graphs. In fact, we fail to reconstruct the cycle structure in the prediction, with all the predicted graphs being path graphs This failure could be related to the limitations of GNN mentioned in Xu et al. (2018)
Real- World datasets Finally, analyze the performance of our model real datasets: the Bitcoin-OTC and Bitcoin-Alpha. We obtain the similarities between each pair of real and predicted graphs in the sequence and draw histogram to illustrate the distribution of similarities. The results are shown in Figure respectively for the two datasets. Among all the traditional random graph models, Kronecker graph model (with Iearnable parameter) performs the best, however on both datasets, our proposed method EvoNet (in blue) outperforms tremendously all other methods, with an average similarity of 0.82 on BTC-OTC dataset and 0.55 on BTC-Alpha dataset. Detailed statistics can be found in Table
Overall, our experiments demonstrate the advantage of EvoNet over the traditional random graph models on predicting the evolution of dynamic graphs.
CONCLUSION
In this paper, we proposed EvoNet, a model that predicts the evolution of dynamic graphs, following encoder-decodee 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.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Edoardo M Airoldi, David M Blei, Stephen E Fienberg, and Eric P Xing. Mixed membership stochastic blockmodels. Journal of machine learning research, 9(Sep))191122014 2008.
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47) 2002.
Aleksandar Bojchevski, Oleksandr Shchur. Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. arXiv preprint 1rXiv:1803.00883 2018.
Joan Bruna and X Li. Community detection with graph neural networks. stat, 1050:27,
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks. arXiv preprint arXiv: 1 170.008415, 2017.
Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18 (03):265 228, 2004.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Voi Volume 70, pp. 1263-1272. JMLR. org, 2017.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. arXiv preprint arXiv: 1805. /273, 2018.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. arXiv preprint arXiv: 1803. 00903.10454 10459, 2018.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 109-137, 1983.
Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos. Edge weight predic- tion in weighted signed networks. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 221-230. IEEE, 2016.
Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and VS Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference Web Search and Data Mining, pp. 333-341. ACM, 2018.
Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11 (Feb):985-1042, 2010.
Cheng Li, Xiaoxiao Guo, and Qiaozhu Mei. Deepgraph: Graph structure predicts network growth. arXiv preprint arXiv:1610.06251 2016.
Jundong Li. Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu. Attributed network embedding for learning in a dynamic environment. In Proceedings of the 2017 on Conference on Information and Knowledge Management, pp. 387-396. ACM, 2017.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint /51 1.00543,, 2015.
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. arXiv preprint arXiv: 070..06/9499 2017.
Changping Meng, S Chandra Mouli, Bruno Ribeiro, and Jennifer Neville. Subgraph pattern neural networks for high-order graph evolution prediction. In Thirty-Secome AAAI Conference on Artificial Intelligence, 2018.

---

Under review as a conference paper at ICLR 2020
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp.
2019.
Giang Hoang Nguyen, John Boaz Lee, Ryan Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pp. 969-976. International World Wide Web Conferences Steering Committee, 2018.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph Kernels: A Survey, arXiv preprint arXiv:1904. 12218, 2019.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, and Charles E Leisersen. Evolvegen: Evolving graph convolutional networks for dynamic graphs. arXiv preprint arXiv: 10191, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pp. 362-373. Springer, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep): 2539-2561, 2011.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. arXiv preprint arXiv: 15l:::5111:0330 1.06911, 2015.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. A comprehensive survey graph neural networks. arXiv preprint arXiv:1901.00566, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXiv:1810.00830 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint / 08773, 2018
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang. Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. arXiv preprint
2018.
A EXTRA EXPERIMENT RESULTS WITH SYNTHETIC DATASETS
A.1
GRAPH SIZE COMPARISON
See Figure 4
A.2
HISTOGRAM OF SIMILARITIES
See Figure 5
A.3
SOME EXAMPLES OF PREDICTED GRAPIIS
respectively for Path graphs, Ladder graphs with small size, Ladder graphs with large size, Cycle graphs, Path graphs with removal, Cycle graphs with adding extra structures.
See Figure 7
10
10

---

Under review as a conference paper at ICLR 2020
Path graph (with removal) Size: Real Predict
Cycle graph (with extra structure) Size: vs. Predict
Graph (number of nodes)
400-
Graph Size (number of nodes?
2000
300-
1500
200
1000
200
000
1200
1600
Graph Index
Graph
Figure 4: Comparison of graph size: predicted size (blue) VS. real size (orange). Left: Path graphs with removal; Right: Cycle graphs with adding extra structures
Distribution Similarities between real
Distribution between graphs (Ladder)
Endes-lery
Prposied
Netter ofauune
53M
Number Inntaand
Prvertan Charter
Ira
20
Simllars
Sirelarity
(b)
Distributien of Similarities between real and predicted graphs (Circle)
graphs
140
Drde--aay
Trspoes
Rymboc hen
171
Power Cluster
Poerdhe Clucter
Moonskeritt eie
Koomskknnts
Namber
400
Smilelly
(c)
(d)
Dikttibution Simiarities between real and predicted graphs (Cyrle-Add)
Irsptoed
Du tany!
Aburt-bbrt
Number dfricaace
Konscee-andam
(e)
Figure 5: Similarity histograms synthetic datasets. Blue one is the result of EvoNet, which is compared against random graph models. [a Path graphs; 5b) Ladder graphs; 5c Cycle graphs: Path graphs with removal; 5e) Cycle graphs with adding extra structures.
11

---

Under review as a conference paper at ICLR 2020
Real graphs
Predicted graphs
Figure 6: Some examples of predictions on Path datasets: the left column is the real graphs and the right column is the predicted ones.
12

---

Under review as a conference paper at ICLR 2020
Real graphs
Predicted graphs
Figure 7: Some examples of predictions on Ladder datasets (with small size graphs): the left column the real graphs and the right column is the predicted ones.
13

---

Under review as a conference paper at ICLR 2020
Real graphs
Predicted graphs
Figure 8: Some examples of predictions on Ladder datasets (with large size graphs): the left column the real graphs and the right column is the predicted ones.
14

---

Under review as a conference paper at ICLR 2020
Real graphs
Predicted graphs
Figure 9: Some examples of predictions on Cycle datasets: the left column the real graphs and the right column is the predicted ones.
15

---

Under review as a conference paper at ICLR 2020
Real graphs
Predicted graphs
Figure 10: Some examples of predictions on Path datasets with removal: the left column is the real graphs and the right column the predicted ones.
16

---

Under review as a conference paper at ICLR 2020
Real graphs
Predicted graphs
Figure 11: Some examples of predictions on Cycle datasets with adding extra structures: the left column is the real graphs and the right column is the predicted ones.
17


Reviews:
[{"review_id": "rJl6gxxRYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a new neural network architecture for predicting the next graph conditioned on a past graph sequence. It seems that the proposed model is the first deep learning model for graph sequence prediction. The model consists of three major components: a graph encoder that maps a graph to an encoding represented as a vector, an LSTM for graph sequence embedding, and a graph decoder for generating an affinity matrix. \n\nThere are two main concerns I have with this paper:\n- The model has some inherent limitations in the graph embedding step. First, the graph encoder embeds a graph into a feature vector that represents the topology of the graph. I assume that the feature vector has a small size, and it is hard to encode a large graph (i.e. 1000x1000). This representation is quite sub-optimal to me. The model will not be able to utilize the complete information of a large dense graph.  Second, the model only takes 10 graphs as input and ignores other graphs in the input graph sequences. This sounds suboptimal to me. \n\n- The performance of the proposed model is not satisfactory. The model does not output a graph with the right size for very simple synthetic graphs. The model completely fails for generating circles. A better model should be proposed to address this challenge. Evaluation is not convincing enough. Simply comparing the graph size between the output and ground truth is not sufficient. We can further predict where graph structure matches the ground truth exactly. I believe this can be done for simple graphs like circles, paths, and ladders.\n\nOther comments:\n- The authors claim that all the sequences in the datasets are fixed to 1000. However, in Figure 4, the graph index goes up to 1600.  Why?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HylezQvAKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a framework to model the evolution of dynamic graphs for the task of predicting the topology of next graph given a sequence of graphs. Specifically, the paper uses a combination of recently proposed techniques in graph representation learning (Graph Neural Network) and Graph Generation (GraphRNN [You et. al. 2018]). Given a sequence of graphs as input, a GNN (to obtain low-dimensional representations of the graphs in this sequence) and LSTM (to model the sequence of these representations)  based encoder is used to compute a vector representation of the topology of next graph in the sequence. The learned vector is then used as input to a GraphRNN decoder to generate a graph that would serve as a predicted next graph in the sequence. The proposed approach is validated with experiments on three synthetic datasets and one real-world dataset (Bitcoin is same dataset from two different resources with little difference in characteristics) and compared against random graph models.\n\nThis paper should be rejected due to following reasons: \n(1) The authors do not justify/discuss the motivation and importance of the task and corresponding applications that would require to predict topology of complete graph in the next step. \n(2) The proposed techniques are an adhoc combination of existing techniques with major concerns (details below) but also with little novelty (if any) for achieving this combination.\n(3) The empirical efforts are very limited and does not provide enough evidence about the efficacy of the method, miss several details and does not serve as motivation for designing such a method in first place. Please note that negative results on cycle graphs has no role to play in this assessment. In fact,\nI appreciate the authors for reporting negative results as it provides a transparent insights into the effectiveness of model in different settings.\nOverall, the paper needs lot of work on all aspects - motivation, technique and experiments to make it fit for a conference publication.\n\nMajor Concerns:\n\n(a) Motivation: The authors do not discuss or motivate the problem and why it is important to the community. The authors mention that many existing work on dynamic graphs focus on learning representations. This is the case because learned representations can then be used for various downstream applications and even future event predictions. When such methods can be used to do future predictions required for most applications, why does one need to predict the topology of complete next graph? The authors need to provide concrete justification for the problem they address, instances where such a task would be useful and discussion on other techniques that can do similar tasks but lack in aspects that such a method can capture. For instance, as a preliminary step, can the authors explain how solving this problem would be helpful to bitcoin?\n\n(b) Technical: The technical contributions of this paper lack novelty and has several flows:\n\n- Figure 1 seems to show that graph only grows in size. While the authors do provide an experiment with removal process, that experiment does not seem to perform well. So, does the method is only good to support growing graphs?\n- Authors mention that the edge and node attributes are considered to be fixed. However, if the number of nodes and edges change, X and L should also change in terms of dimensions and adding values for new nodes/edges. so why should it not be considered time-varying?\n- What was the motivation for using GRU for update function in Eq 3? Was simple MLP tried and not useful? Was GRU used to capture some long term dependencies in structure? If so, the authors must explain how it is useful for this task.\n- Why Set2Set was used for ReadOut function? This seems to be a particularly adhoc and odd choice. when sum did not work well, jump to Set2Set is not justified. Can the authors provide an explanation for the same?\n- The authors claim that the embedding h_G_T incorporates topological information -- I find this claim highly unsubstantiated and needs justification. For instance, can you provide some rigorous analysis to demonstrate that this is the case? At the least, can the authors use this vector and pass it through a graph decoder to recover the original graph? \n- What is novel in 3.2.3 as compared to You et. al.? Infact, it is hard to see any novelty in the entire combination. Was it challenging to achieve this combination? If so, what was the challenging part? It is not clear what the authors contributed to address such a challenge. Was the training challenging? If so, please explain. If not, why is this a novel approach?\n\n(c) Empirical: The empirical efforts are inadequate and raises more questions than answers. \n\n- Synthetic datasets are simple and more datasets should be used e.g. You et. al. 2018 to validate the performance. Only one real-world dataset from two different sources is used. It is hard to understand author's motivation in doing so. Why not use various graph datasets available in papers that learn representations (e.g. cited by authors themselves) What is special about bitcoin dataset that makes it suitable for this task?\n\n- Node/edge attributes are chosen in adhoc manner and it is unclear what role they perform. Do they help with prediction? If not, would it be useful to first show experiments without them? Or does this method absolutely need attributes? It is not clear why it is useful to set all attributes for edge as 1.\n\n- How was window size of 10 chosen? Why is the same window size good for all graphs? What impact does window size has on performance?\n\n- What is the motivation for using Graph kernel for similarity? The authors borrow the decoder from You et. al. 2018 which also provides a principled method to compare graphs using MMD based on statistics. Why not employ the same?\n\n- GraphRNN (You et. al.) and other generative models can learn over multiple graphs? Did the authors try to feed the sequence of graphs to such models and then try to generate a new graph to see if they can produce similar results? It is true that those generative models do not specifically model temporal sequence, but such an experiment would help to distinguish the efficacy of the proposed method.\n\n-The technique of using MLP for generating predictions using random graph models seem to be highly unfair for the baselines. Can you elaborate more as it is difficult to understand why one should handicap those models by using learned information instead of data information?\n\n- A rigorous discussion on insights explaining the results is required. The authors show high performance on Bitcoin dataset. However,  it is not clear what part is contributing to the performance. Similarly, authors should dig deep into the failure cases and provide justification of why such a method would fail in particular cases and propose alternatives.\n\n- Why was Graph size used as a statistic to report? Two graphs of same size can be entirely different and I do not see any merit in using such a metric. Again, something like MMD based metric may be useful.\n\n\nImprovements that would make future revision strong but has not impacted current assessment:\n\nOverall, the presentation of the paper is very unpolished. The authors are missing many important details as described above while spending a lot of time in describing (repeating) known techniques verbatim as original works. This can be removed and condensed into very short preliminary section.\n\n- Notations: The authors must use clear notations. For instance, on Page 2, L is used to  describe edge attributes but then it is replaced by E in Page 3. Also, both X and L are shown to have dimension d. Are edge and node attributes of same dimension? w is used for window-size of sequence used as input and also as neighbor node. When modeling evolution of graphs where a sequence is available over time points 0...T, it is not useful to use T to also represent time step of GNN propagation. Infact, authors should avoid using time steps to signify GNN iterations.\n\n- Empirical details: The details provided for datasets and experimental setup is inadequate. Why are the two Bitcoin datasets different from each other? What does Pos. Edges in Table 1 mean? What does  Mean and 90th percentile in Table 2 signify? Authors only talk about train-test split but then mention\nvalidation set for hyper-param tuning. How was this validation set obtained? Also, what hyper-params were tuned and what was sensitivity of those hyper-params? Authors use GNN and multiple RNN's, what was the model capacity used and how it impacted the performance? Figure 5 (c) what is a circle graph?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Bylnso_aKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a system for predicting evolution of graphs. It makes use of three different known components - (a) Graph Neural Networks (GNN); (b) Recurrent Neural Networks (RNN); (c) Graph Generator. A significant portion of the paper is spent in explaining these known concepts. The contribution of the paper seems to be a system of combining these to achieve graph evolution prediction. As stated, this system is effectively a recurrent auto-encoder of sorts. \n\nThe main objection I have in this paper is that they have only used two real datasets (both of which are from the same domain). There are several only available datasets that have temporally annotated graph evolution. It is not possible to conclude the empirical superiority of a system based on such little evidence. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a combination graph neural networks and graph generation model (GraphRNN) to model the evolution of dynamic graphs for predicting the topology of next graph given a sequence of graphs.

The problem to be addressed seems interesting, but lacks strong motivation. Therefore it would be better if some important applications can be specified.  

The proposed approach lacks novelty. It would be better to point out why the specific combination of two existing models is the most appropriate approach to address the task. 

The experiments are not fully convincing. Bigger and comprehensive datasets (with the right motivating applications) should be used to test the effectiveness of the proposed model. 

In short, the current version failed to raise excitement from readers due to the reasons above. A major revision addressing these issues could lead to a strong publication in the future. 
Decision: Reject