Graph Edit Networks
Authors: Benjamin Paassen
Daniele Grattarola
Daniele Zambon
Cesare Alippi
Barbara Hammer
Venue: ICLR 2021 Poster (2021)
Keywords: graph neural networks
graph edit distance
time series prediction
structured prediction

Abstract: While graph neural networks have made impressive progress in classification and regression, few approaches to date perform time series prediction on graphs, and those that do are mostly limited to edge changes. We suggest that graph edits are a more natural interface for graph-to-graph learning. In particular,  graph edits are general enough to describe any graph-to-graph change, not only edge changes; they are sparse, making them easier to understand for humans and more efficient computationally; and they are local, avoiding the need for pooling layers in graph neural networks. In this paper, we propose a novel output layer - the graph edit network - which takes node embeddings as input and generates a sequence of graph edits that transform the input graph to the output graph. We prove that a mapping between the node sets of two graphs is sufficient to construct training data for a graph edit network and that an optimal mapping yields edit scripts that are almost as short as the graph edit distance between the graphs. We further provide a proof-of-concept empirical evaluation on several graph dynamical systems, which are difficult to learn for baselines from the literature.

Published as a conference paper at ICLR 2021
GRAPH EDIT NETWORKS
Benjamin Paassen
Daniele Grattarola
The University of Sydney ben jamin wwwpppaassssassaee...eaaa www.needddddddddeeee edu. au
Università della Svizzera italiana daniele. daniele.grattaroll www.taroltaaauusss....om
Daniele Zambon
Cesare Alippi
Università della Svizzera italiana daniele. cambon@usi.. ch
Università della Svizzera italiana Politecnico di Milano cesare a aaapppppussss ppiiuus.... .ch
Barbara Hammer
Bielefeld University
www.aakkiuibbbbbleill...ee. bhamme x bhaamaeeeeeallaa.....bbbbeeeeeee
ABSTRACT
While graph neural networks have made impressive progress in classification and regression, few approaches to date perform time series prediction on graphs, and those that do are mostly limited to edge changes. We suggest that graph edits more natural interface for graph-to-gras general enough describe any graph-to-graph change, only edge changes; they are sparse, making them easier to understand for humans and more efficient computationalll: and they are local, avoiding the need for pooling layers in graph neural networks. In this paper, we propose a novel output layer- the graph edit network which takes node embeddings as input and generates a sequence of graph edits that transform the input graph to the output graph. We prove that a mapping between the node sets of two graphs is sufficient construct training data for graph edit network and that optimal mapping yields edit scripts that are almost as short as the graph edit distance between the graphs. We further provide a proof-of-concepp empirical evaluation several graph dynamical systems, which are difficult to learn for baselines from the literature.
learning. In particular, graph edits are
INTRODUCTION
Recent advances in graph representation learning have mostly focused tasks of classification regression, i.e, tasks with graph-structured input but numeric output (Battagha et al.] 2018 Kipl
& WWlling 2016a Velicković et al., 2018). By contrast, few approaches to date can transform graph-structured input to a graph-structured output (Hajiramezanali et al., 2019 Paaßen et al.) 2018 Zambon et al., 2019). This lacuna crucial because time series prediction on graphs requires graph- structured output, namely the next graph in a time series. Applications of time series prediction on graphs include epidemiological models (Keeling & Eames 2005), social (Liben-Nowell & Kleinberg 2007 Masuda & Holme 2019). telecommunications (Nanavati et al. 2006), traffic (Cui et al. 2219)) citation (Shibata et al.) 2012). and financial transaction networks (Chan Olmsted 2017). as student solutions in intelligent tutoring systems (Paaßen et al. 2018). In each of these settings, predicting the changes graphs can deepen the understanding of the domain and provide useful knowledge for designing interventions.
well
Currently, methods for time series prediction on graphs are limited to the dynamics the node attributes (Yu et al. 2018), or changes in connectivity (Goyal et al. 2020 Hajiramezanali et al.) 2019) but do not cover changes in the node set. Fortunately, there exists rich research tradition of edit distances (c.g. [Leeensteein 1965] Zhang & Shasha 1989; Sanfeliu & Fu 1983) which can describe any change between two graphs. Further, edits are sparse and have simple semantic (delete, insert, relabel), which makes them easier to interpret for human observers and makes them computationally

---

Published as a conference paper at ICLR 2021
more efficient (linear instead of quadratic) compared dense representation. Finally, edits local, enabling us to make edit decisions at each node instead of coordinating information across the entire graph.
In this work, we connect graph neural networks to edit distances by developing a simple, linear output layer that maps node embeddings to graph edits. We call our output layer the graph edit network (GEN). We also develop a general training and inference scheme to transform any graph G, to its successor G4+1 using only local binary edit decisions and regression for node attributes.
Theoretically, we prove that a) a mapping between the nodes of G. and G++1 is sufficient to construct training data for the GEN, b) this construction yields almost no overhead compared to directly transforming the mapping to graph edits, and c) provided that the mapping between G3 and G++1 is optimal and the GEN can perfectly reproduce the training data, the edit script almost as short the graph edit distance (Sanfeliu & Fu 1983).
In addition to this core theoretical contribution, we provide a proof-of conccet of our model by demonstrating that GENs can learn a variety of dynamical systems on graphs which are more difficult to handle for baseline systems from the literature. We also show that the sparsity of edits enables GENs to scale up to realistic graphs with thousands of nodes.
2
BACKGROUND
Graph Neural Networks: Graph neural networks (GNNs) compute representations of nodes in a graph by aggregating information of neighboring nodes (Bacciu et al.] 2020; Defferrard et al. 2016: Kipf& & Welling, 2016a Micheli 2009 Scarselli et al. 2009 In particular, the representation
2.4 of node y in layer is computed as follows:
o' (v) = meere
(w)))E((())
where (()) is some neighborhood of in the graph and fieegg as well as fa are functions that aggregate the information of their arguments, returning a single vector (Xu et al. 2019). The representation in the Oth layer usually defined as the initial node attributes nodes (Kipf& & Welling 2016a). Recently, many implementations of fueegee facer. and neighborhood A have been suggested, such as a weighted sum via the graph Laplacian (Kipf & Welling (0) recurrent neural networks (Hamilton et al.) (017), or attention mechanisms (Veličković et al. 8). Our approach is agnostic to the choice of graph neural network. We merely require some vectorial embedding for each node in the input graph.
constant vector for all
Graph Generators: Multiple works in recent years have proposed recurrent models to generate graphs (Bacciu et al. 2019 Li et al. 2018 You al. 2018a Zhang al. 2019). Roughly speaking, these recurrent models first output a node, and then all connections of this node to previous nodes until special mad-of-sentenn prediction, it only works for insertions, i.e. starting at an empty graph and inserting nodes and edges over time. If one wishes account for general graph changes, one first has to encode graph into vector and then decode from this vector the graph in the next time step, similar to molecular design (Jin et al.) 2019 Fu et al. 2020)). However, such models have to generate the next graph from scratch and can not exploit the sparsity and interpretability of edits, as we suggest.
token is produced. While such a scheme does enable time series
Link Prediction: Link prediction is complementary graph generation. It assumes constant number of nodes, but changing connectivity between them (Liben-Nowell & Kleinberg, 2007 Richard al. 2014, (Shibata et al. 2012). Typical link prediction approaches compute node features first, Tollowed by an affinity index between nodes based on their features. Finally, edges with low index are predicted to vanish, while edges with high index are predicted appear. For example, Goyal et al. (2020) combine dense and recurrent blocks to build an autoencoder for link prediction, while Hajiramezanali et al. (2019) combine a GNN and a RNN to obtain a spatio-temporal variational graph autoencoder. In GENs, we predict edge changes with similar scheme, using a graph neural network to obtain the node features and then mapping these node features to the graph changes. However, in contrast to prior work, we do not predict the next adjacency matrix but only the change in adjacencies, which is a much sparser signal, reducing the time complexity from quadratic to linear. Additionally, GENs can not only handle edge changes, but also node changes.
2

---

Published as a conference paper at ICLR 2021
We note that our current paper is limited Markovian setting. i.e. we do not consider the past for computing node representations. This limitation could be addressed by combining our output layer with EvolveGCN (Pareja et al. 20200 which uses recurrent net to predict the weights of graph neural net, thus being able to handle changes in the node set.
Dynamic Attributes:
Recently, graph neural networks have been extended predict changes to node attributes, while the nodes and edges remain fixed (Cui et al.) 2019 Seo et al. 2018). which is particularly useful for traffic networks. GENs are complementary these works, in that we consider the more general case of graph topology changes.
Time Series Prediction on Graphs: To our knowledge, only very few works date have addressed the most general case of time series of graphs, where both nodes and edges are permitted to change. In particular, Paatsen al. (018) suggest several kernel-based time series prediction methods for graphs. However, their scheme is limited to predictions in the kernel space and mapping a prediction back to graph requires solving an inverse kernel problem, relying on approximations that impact accuracy (PaaBen et al. 2018). Zambon et al. (2019) embed the time series into vector space using a GNN and use a recurrent neural network to predict the next time step. To obtain the corresponding graph, a multi-layer perceptron is used to compute the adjacency matrix and node features from the predicted embedding. Besides being computationally expensive, this dense decoder also assumes a fixed order of the nodes.
Graph Edits: The basis for our approach are graph edits, which are functions that describe changes in graphs (Santeliu & Fu 1983). Formally, we first define an attributed, directed graph as triple .1....,,j is a finite set of node indices, E S V x V is a set of edges, and X IR-V=" is matrix of node attributes for some n E N. We define the nodes as indices for notational simplicity, but we do not assume any specific order, i.e. we treat isomorphic graphs as the same. Now, let G be the set of all possible attributed directed graphs We define graph edit as some function 5 G + G. In particular, we consider the graph edits of (Snfflll & Fu (1983), namely node deletions del, which delete the ith node from a graph, node replacements repi... which set the attribute of node to node insertions ins,, which add a new node with attribute x to a graph, edge deletions edcla,j. which delete the edge (i. from graph, and edge insertions eins..j. which insert the edge (i, into graph. We then define an edit script ō as finite sequence J .1.....0. ôT of graph edits and we define the application of 8 as the composition of all edits, i.e. 8(G) = ÔT o........ (G).
G G= (V, E, X), where
Finally, we define the graph edit distance (G G') between two graphs G and G' as the length of the shortest script d such that 5(G) _ G', where E means isomorphic. The GED is well-defined and a proper metric, i.e. script connecting any two graphs always exists, the GED between two isomorphic graphs is zero, the GED is symmetric, and it conforms to the triangular inequality (Abu-Aisheh et al., 2015 Sanfeliu Fu 1983). While prior work has already attempted to approximate the graph edit distance with graph neural nets (Bai et al. [2199] Li et al. (019)) our work is, to our knowledge, the first to produce actual graph edits as network output, and to avoid graph pooling layers.
3 GRAPH EDIT NETWORKS
Let G2,G2,... GT be a time series of graphs. Our goal is to develop a neural network that takes a graph G, as input and outputs graph edits that transform G, to G++1- For simplicity we make a Markov assumption, i.e. G, is assumed to be sufficient to predict G++1 (future research could address this limitation, e.g. by applying EvolveGCN of Pareja et al. 2020).
Now, let G. (V, F, X) be an attributed graph with N nodes. Our proposed processing pipeline has three steps. First, we use some graph neural network (refer to Equation IT) to compute a matrix of node embeddings & E Nx Second, we use linear layer to compute numerical edit scores that express which nodes and edges should be deleted, inserted, and relabeled, respectively. Third, we translate these scores via Algorithm| ] to an edit script 5 and apply this script to the input graph to obtain the output graph (G.). This pipeline is also illustrated in Figure
In the remainder of this section, describe the graph edit network layer (Section B.1p. our train- ing scheme (Section 3.2). our inference scheme (Section 3.3), and finally our theoretical results (Section 3.4).
3.4))
3

---

Published as a conference paper at ICLR 2021
GEN
G.N.
G.E.N.
Edit Scripe
V Node scores
Alg.
G Original graph
((G) Predicted graph
E Edge
Figure I: An illustration of the processing pipeline. An input graph G' is processed by message passing network (Equation I The output layer is a GEN, and produces node scores i7 and edge scores E. Algorithm translates the node and edge scores into edit script å which, when applied to the input graph G, constructs the predicted graph 8(G).
3.1 GRAPH EDIT NETWORK LAYER
Our proposed graph edit network (GEN) is linear layer to compute edit scores that express which nodes and edges should be deleted, inserted, or relabeled. The input our GEN is a matrix & E RNNx of node embeddings returned by graph neural network (refer to Equation Dt. We then compute node edit scores E RN, edge filter scores et E RN as well as e E R. and new node attributes Y via linear maps from o. After this is done, consider only those pairs (i.j) where et > and E > O and compute an edge edit score Ci via another linear layer that receives 6e Φ5. and the inner product oy - as inputs. The interpretation of these scores is that v; should be positive if new node connected i is inserted, v, should be negative if node is deleted, et. eyy as well as et should be positive if edge (i is inserted and e,- CJ as well as -C, should be positive if edge (i,5) is deleted. Note that only compute the edge edit score ei, for edges (i, where e; >> 0 and ej > O. Thus, if edge changes concern only number of nodes in (V/T), the GEN layer operates in linear instead of quadratic time. We can also enforce the linear time by setting all e," and ej to zero that are not in the top R for some R that is either constant or in OVv
From scores to edits: Next, translate these scores into edits. The formal translation scheme is given in Algorithm[] | Roughly speaking, we delete any node where the node edit score v; is smaller than 3. we insert new node with attribute T7, connected
whenever 1/ is larger than + and we replace the attribute T7 with Th otherwise. For edges, we delete any edge (i,j) where εi,j < -
I where Vn < 1-2 2- or where < 2- and we insert any edge where Ci,j > + The complexity of Algorithm D is as follows. In line 2, we first construct | n {(i,j)) < --3 or UJ < H edits, which is bounded by EE, which in turn is in O(N) for a sparse graph and O(N2) for a dense graph. Lines 3-8 perform ((,,j))e; > 0, 0}| iterations, which can be bounded to some constant 1t2 by the edge filtering trick above. Lines 9-15 iterate over all nodes several times, which is in O(N). The space complexity is the same since we add one edit each iteration, which needs to be stored. The overall time and space complexity is thus ((N) for sparse graphs and O(N2) ) for dense graphs.
Note the special case of node insertions in this scheme. As with other edits, we make the decision to insert a new node locally at each node instead of globally for the graph. This relieves the need to aggregate information across the entire graph. Further, by connecting new node directly with an existing one, we ensure that any two new nodes can be distinguished purely based on their graph connectivity, without relying on auxiliary information.
3.2 TRAINING
The key challenge in training GENs is to identify which scores the network should produce such that the GEN transforms the input graph G, into its desired successor G(+1- In other words, we require teaching signal consisting of ground truth scores (ù, Y at _,_,),, such that the edit script 5 returned by Algorithm yields ((G)) G
Unfortunately, such one-step teaching signal is sometimes insufficient. Consider the two ample graphs G, = ({1).0 0. (0)) and G = ((1, 2, 3), {(1, 2). (1,3)), (0, ())),) In this case, there exists one-step teaching signal that transforms G. G because can only insert
4

---

Published as a conference paper at ICLR 2021
Algorithm The scheme to translate the outputs of the GEN layer Us Vi e," eq and <t to graph edits.
1:
function TRAp G - (V, X), node edit scores i RR- attributes Y e RN*" edge filter scores e e E RR and edge edit scores & E IR N IR=x
2: Initialize script 8 with edel,,; for all (i,j) with 24 - or Vj 1/2 in lexicographic order.
3: for with e > 0 and V4 2 - do
4:
for j with Ej > 0 and 2- - do
5:
Append edek., to 8 if (i,j) E E and Gij < -
6:
Append j to 8 if (i,j) $ E and Gi. +
7:
end for end for
8:
9: Append rePi,g to ô for all i with | S and T. + T..
10:
1-
11:
for i with V/ > + do
12:
Append insg, and ein to 6. 4 k + 1. end for
13:
14:
15:
Append del, to ō for all with vs < - in descending order.
16:
return
end function
as many new nodes as already exist. However, it is possible to set up two-step teaching signal (21, e éj
E1), (b2, F2, é e,, E2) with á (1), 22 = (1,0)² and all other scores set to
zero. When plugging these values into Algorithm [ we obtain the edits d1 = ins, eins and 82 = ims, einsj.3, such that the concatenation ô = ,1, 02 does indeed yield 8(Gr) _ G++1- In general, Theorem (below) shows that a teaching signal with K + 1 steps suffices transform any input graph G2 into any output graph Gi+1, where K is the number of insertions necessary to transform G, into G and the first K steps only perform these insertions.
Provided that a teaching signal exists, our training procedure should ensure that the actual edit scores (7,, Y2, G ET), (ŪK+1. YK+1, (K 1x+1: Ex+1) result in the same edits as the teaching signal when being plugged into Algorithm []] To do so we treat every edit decision in Algorithm [ aas a binary classification and punish different decisions with a classification loss, such as the hinge Toss
(Zhao et al. 2017) or crossentropy (refer to Appendices B C for more details on loss functions).
In particular, in the first K steps of teaching signal, we have a classification loss for the decision of inserting node (My, > + not (Kk, S +2),, plus a loss for punishing deviations between
predicted attributes Tk.i and desired attributes ÿk.; for all with ék, + For step K + 1, the same idea applies. For each node we have a binary classification loss for the decision of deleting a node: i (VK+1,5 < - or not; plus the regression loss between + and 0K+1,; for non-deleted nodes i; plus the classification loss regarding whether to change the outgoing edges of node i (ck+1,, > 0) or not; plus the classification loss regarding whether to change the incoming edges of
node i (, > 0) or not; plus the classification loss regarding whether to delete an existing edge (i, (eig < -1) or not; plus the classification loss regarding whether to insert non-existing edge (1,5) (Ei. > 1) or not. The sum of all these losses forms our training loss for single graph pair train our neural net end-to-end by performing a gradient descent scheme on this loss, e.g. using Adam (Kingma & Ba 2015).
(Ge, G(+1). Because this loss is differentiable,
Importantly, edge filtering needs to be adjusted to the training data. In particular, if we impose limit on the maximum number of nodes with et" > or e > O, this limit should be higher than the maximum number of those nodes in the teaching signals for the training data otherwise, the training can never achieve zero loss. If the limit is high enough, however, the training procedure is the same with without the limit. The limit only impacts inference.
5

---

Published as a conference paper at ICLR 2021
3.3 INFERENCE
Once training is complete, wish use our GEN for inference. In particular, given previously unseen graph G, we want to know its successor G1+1. Because G1+1 is unknown, we can not construct teaching signal. Instead, compute node features $, then use the GEN to compute scores (17, Y, _t, E and plug these into Algorithm retrieve edit script 8, which then yields our predicted graph G++1 ((G)) (also refer to Figure[] This is the simple one-step scheme that we will also use in our graph dynamical system experiments.
plug the current graph G, into our graph neural net to
In case our training data requires multi-step teaching signals, our inference also needs multiple steps. In particular, we use the following scheme: Color all nodes red. 2) If no red nodes are left, go 4. Otherwise, re-compute the node features és. the node edit score V3, and the attributes Y/ for all red nodes i. 3) For all with > +2. insert new node with attributes Yi. draw edge from i to the new node, and color the new node red. Color all nodes i with v; S +2 blue. Then go 2. 4) Compute the node features o and the edit scores (77 E e .) for all nodes. Set all v; 1 to zero. Then, call Algorithm [ and apply the resulting script to the graph.
In general, may be necessary to provide state information (e.g. via recurrent neural net) to ensure that the network can distinguish whether it still needs to insert nodes or not. In our experiments, however, it sufficient to either summarize all edits in single step or to supply the network with a binary node attribute that flags whether we are still in 'insertion mode or not.
3.4 THEORY
In this section, we wish to answer two questions. First, how to construct teaching signal for graph edit network? Second, how short can the output edit script of GEN get, provided that it still transforms graph G, to graph G++1?
The answer to both questions lies in making the theoretical connection to graph edit distances more explicit. To do so, we first introduce a key concept that will help us, namely that of graph mapping.
(V' [I....,N.. }, E", ,²) be two non-empty graphs, i.e. M,N > 0. Then, we define a graph map- ping & between G and G' as bijective mapping with the additional restriction that for the set Insp = (j < N NW > M} we obtain (Insp) = (M + +,..... M + [ns
Definition 1 (Graph Mapping). Let G (V {1, ...,... MM. E, X) and G'
[1, (l...., M + N) + (I....,.l M N}
Graph mappings are useful because they are intimately connected to edit scripts. In particular, we re-state result from the literature that any edit script converts to graph mapping and back and that this conversion never increases the length of the script.
Theorem 1
(Script to mapping). Let G and G' be any two graphs. There exist two polynomial algorithms to translate any edit script ō with 8(G) = G' to a graph mapping by between G and G², and translate any graph mapping vi between G and G' into edit script dg with (G) = G',
such that for any 8 with 8(G)) 2 G" we obtain |60g < 8).
One proof is contained in Bougleux et al.] (2017). We provide more extensive version in Ap- pendix A.1 which also gives more details on the structure of why and 6,g.
Next, we show that graph mapping can also be used construct teaching signal for GEN. Even better, the conversion from mapping to teaching signal to edit script yields almost as short scripts as the direct conversion from mappings to edit scripts. Indeed, we can provide a sharp bound for the overhead in terms of the connected components in the target graph.
Theorem 2 (Mapping to teaching signal). Let G and G' be any two graphs with M and N nodes, re- spectively. There exists an O(2 + N2) algorithm (namely Algorithm 2 in the appendix) that translates any graph mapping vb with [lnsøl < N between G and G into teaching signal (D1, Y1, Et), (DK+1. YK+I, c 1: e is a script 8. where the following holds: 1) 8(G) S G'; 2) |6| S 16gg 2 (C - 1), where C' is the number of connected components in G' (this bound is sharp); 3) the first K steps contain only
& EK+1) such that the output of Algorithm /

---

Published as a conference paper at ICLR 2021
insertions, with V,, = 0 = 14+1,1
PK+1,1 0; 4) the last step contains insertions; 5)
K $ [nsp]] (this bound is sharp).
Refer to Appendix for the proof. So this result tells us that we obtain a (sparse) teaching signal if we have good graph mapping th But how to obtain ? In many cases, knowledge. For example, we know that the input graphs are trees, we can use the polynomial tree edit distance algorithm infer mappings that correspond short edit scripts (Zhang & Shasha 1989); or, if node IDs are given (like user IDs in social networks), we can set vb such that it maintains IDs. In our experiments, we follow such Nomain-specifie schemes construct the mappings es.
exploit domain
But there is also a general strategy connected to the graph edit distance. While computing the graph edit distance itself NP-hard (Bougleux et al., 2017). one can achieve a good approximation by constructing a graph mapping via the Hungarian algorithm and then converting this mapping to an edit seript via Theorem (Riesen & Bunke 2009, Abu-Aisheh al., 2017 Blumenthal et al. 2020). For our purposes, we can simply apply such an approximator and then use the graph mapping to construct our teaching signal. Importantly, if the approximator happens to find the optimal mapping and if our graph edit network is powerful enough achieve zero loss on one graph tuple (Ge, G++1), then the output of our graph edit network is close to the graph edit distance.
Corollary (Near- Optimalpt of Graph Edit Network Architecture). Let G and G' be any two non-empty graphs and let C be the number of connected components in G'. Further, let d be graph mapping between G and G' such that 1óyl = dGED (G,, G++1). Finally, let J be a graph edit network that reproduces the teaching signal, i.c. f(G) = ö with being the same script as the result of Theorem for th. Then, it holds: [5] I dGED(G, G') 2 11.
As mentioned before, this corollary only holds if the mapping is optimal and if the GEN can reproduce the teaching signal. The latter only holds if the node features & are rich enough to make each edit classification problem linearly separable (because any edit decision is linear binary classification). Typically, this fails graph neural net can not distinguish two nodes that would need to be treated differently. For example, an unlabeled ring graph G (fl,..... .V. }. {(1, 2)..... (N, 1)})- Equation [ assigns the same node embedding to all nodes and, hence, the GEN returns the same edits. In such cases, distinguishing information must be integrated via an alternative architecture or via node attributes (which is the strategy we take in the experiments). For further work on the expressiveness of graph neural nets we point the reader to Xu al.] (2019).
To summarize: The proposed way to use a GEN is 1) to gather training time series of graphs GI...., GT.1; 2) to set up reference graph mappings vhy between G, and G++1 for all / & (1, (1..... 7}, e.g. via graph edit distance approximators; 3) to compute teaching signals via Theorem 2 4) to initialize an appropriately powerful graph neural net with a final GEN layer and train it to reproduce the teaching signals on the training data; 5) to use the trained GEN in inference.
4 EXPERIMENTS
Our experimental evaluation displays the capability of GENs on a set of graph dynamical systems in comparison to baselines from the literature. Experiments are reported three groups and cover graph dynamical systems, tree dynamical systems, and social network dataset. All experiments require the possibility of changing nodes, and almost all require additional edge changes. The data discussed in more detail in Appendix D We perform all experiments consumer grade laptop with core i7 CPU. All experimental code is available at /htttts:////// //gitaa///tttbb com com/bpaassen/ traph-edit-netweee
First, we consider the following three graph dynamical systems.
Edit Cycles: A manually defined dataset of cycles in the set of undirected graphs with up to four nodes. The teaching protocol is hand-crafted to perform optimal edits between each graph and its successor. To sample time series we let the cycle run for 4-12 time steps random. The node features 60 (r) were set to zero
Degree Rules: A dynamical system on undirected graphs of arbitrary size with the following rules. First, delete every node with a degree larger than 3. Second, connect nodes that share at least one common neighbor. Third, insert node any node with degree lower than 3. We used the
7

---

Published as a conference paper at ICLR 2021
2
2
2
1
2
rule 3
rule 2
rule
rule 2
rule 2
2
1
1
2,3
1
2,4
f
3
3
2
2
2
2
3 rule 2
3
rule 2
3
rule 2
rule
rule 2
X
2,4
3,,5
61,4
11
E 1,4
Two graph time series from the degree rules dataset. Blue arrows indicate graph dynamics, labelled with the teaching signal.
Figure 2:
Table 1: The average precision and recall values (+ std.) across five repeats for all edit types on the graph dynamical systems.
node insertion
mode deletioo
edge insection
odge deletion
model recall
precision
recall
precision
recall
precision
recall
precision
odit cycles
VGAE
0.62
0.0
1.00
0.0
1.00 0.0
0.69
0.1
1.00 1: 0.0
1,00 + 0.0
1.00
0 0.0
1.00
0.0
VGRNN
0.64
+ 0.0
1.00
+ 0.0
0.63
0.0
1.00
+ 0.0
0.95
+ 0.0
0,06
+ 0.0
1.00
+ 0.0
0.71
0.1
XE-GEN
1.00 1 0.0
1.00 0.0
1.00
0.0
1.00
0.0
1.00
1: 0.0
1.00
1 0.0
1.00
0.0
1.00
GEN
+ 0.0
1.00
1.00
1.00
+ 0.0
+ 0.0
1.00
0.0
1.00
degroe miles
VGAE
0.15 1: 0.0
1.00 0.0
1.00
0.96
0.0
0.88 1: 0.0
0.97 1 0.1
1.00 2: 0.0
0.97 0.1
VGRNN
1.00
0.72
1.00
0.0
0.0
0.0
0.02
XE-GEN
1.00 + 0.0
1.00
+ 0.0
1.00
0.0
1.00
0.0
0.97
+ 0.0
0.99
+ 0.0
1.00
0.0
1.00
0.0
GEN
1,00 1: 0.0
1.00 4: 0.0
1.00
0.0
1.00
à: 0.0
0.97
1: 0.1
0.99
4 0.0
1,00
2 0.0
1.00
0.0
game of life
YGAB
0.27
0.1
1.00 0.0
1.00 0.0
0.03 0.0
1.00 + 0.0
1.00 + 0.0
1.00 0.0
1.00 0.D
VGRNN
0.31
1: 0.1
1.00
1: 0.0
0.32 2 0.1
1.00 1: 0.0
1.00 1 0.0
0.00
1 0.0
1.00
2: 0.0
0.01 2 0.0
XE-GEN
1.00
0.0
1.00
1.00
0.0
0.0
1.00
1.00
GEN
0.0
1.00
1.00
0.0
1.00
node index in one-hot coding as node features (x). For every connected component in the input graph, this dynamical system provably converges to a 4-clique. We started with a random undirected adjacency matrix of size 8 x and let the system run until convergence. Refer to Figure 2 for two example time series.
We simulated one of five oscillatory shapes in Conway's 's game life (Gardner 1970), namely blinker, glider, beacon, toad, and clock, for 10 time steps, placed on random location on a 10 x 10 grid and additionally activated 10% of the grid cells at random. We represented the grid graph with 100 nodes and represented the 8-neighborhood via the adjacency matrix. The desired edits were node deletions for all nodes that should switch from alive to dead and node insertions for all nodes that should switch from dead to alive. As node features we used the alive-state of the node.
Game of Life:
Note that a single-step teaching signal sufficient in all cases. We compare our graph edit network against variational graph autoencoders (VGAE) and variational graph recurrent nets (VGRNN) which predict the adjacency matrix of the next graph via an outer product of the node features, similar to our edge prediction scheme (Kip' & Welling 2016b Hajiramezanali et al. 2019). Note that neither net can predict node changes directly, but we predict node deletion whenever all edges of node are deleted. To train our GEN model, we apply both the hinge loss (GEN; Appendix (B) as well as the crossentropy loss (XE-GEN; Appendix C). For all models, we use two graph neural network layers with 64 neurons each, sum as aggregation function and concatenation as merge function (refer to Equation l). We train all networks with an Adam optimizer in py Torch using a learning rate of 10-3 and stopping training after 30,000 time series or the loss dropped below 10-3, -3, After training, we evaluated the predictive performance on 10 additional time series. We repeated each experiment five times.
The recall and precision for all edit types, all models, and all datasets is shown in Table [ Node insertion precision, node deletion recall, and edge deletion recall where consistently at 100% for all models, and edge insertion precision as well as edge deletion precision very close 100%. This is
8

---

Published as a conference paper at ICLR 2021
the case for both hinge and crossentropy loss. Unsurprisingly VGAE and VGRNN perform poorly on node edits, for which they are not designed, but also underperform on some edge edit scores; especially VGRNN edge edit precision. We note that datasets strictly Markovian, such that the added recurrent capability of VGRNNs may not provide much value and that, indeed, the difficulty of maintaining the state across node set changes may hurt VGRNN in these cases.
Next, we consider the following two tree dynamical systems, where node labels are represented via one-hot coding.
Boolean Formulae: Random Boolean formula with up to three binary operators (e.g. V -y) A A y), which get simplified with rules like A - 1 until the formula could not be simplified anymore.
Peano addition: Random additions of single-digit integers with at most 3 + operators, which get re-written using Peano's 's definition of addition, i.e. m - succ(n) suco(m) + n and m + 0 = m.
The purpose of these datasets is test whether our GEN is able to correctly predict node attributes. We compare against Gaussian process prediction approach for tree time series prediction suggested by Paaleen et al. (2018) which uses Gaussian process regression with an RBF kernel on the tree edit distance to predict the next tree in kernel space and then solves a kernel pre-image problem to find the actual next tree (PaaBen et al. 2018). We use the same GEN hyper parameters as for the graph dynamical systems.
As results we observe that the GEN is able to achieve perfect predictive accuracy for both datasets on all five repeats of the experiment. By contrast, the Gaussian process prediction scheme yields an RMSE (as measured by the tree edit distance) 2.39 (std.: 0.24) on Boolean and 4.54 (std.: 0.77) on Peano, indicating that the datasets are not trivial to predict.
We evaluated the runtime of GENs on a variation of the HEP-Th paper dataset of Leskovec et al. (2007). In particular, we considered all authors as nodes and included an edge if two authors submitted a joint HEP-Th paper within the last T month from some month t. We removed authors without any papers from the graph and resolved duplicates. We varied over the entire range between January 1992 and April 2003 in the HEP-Th dataset and T E (1,..., 12). thus obtaining 1554 different graphs of sizes in the range [100, 2786]. For all these graphs, we measured the time needed compute forward and backward pass with GEN without edge filtering (i.e. ह ē I in all cases) and with edge filtering, respectively. For forward computations, both variants scaled sub-quadran sub-quadratically with empiric exponents of 1.65 and 1.37, respectively. For the backward pass, GENs without node filtering scaled with exponent of 4.11, whereas GENs with edge filtering scaled roughly linearly (exponent 0.93). yielding faster times by several orders of magnitude.
We emphasize that edge filtering can not be made arbitrarily strict. As discussed in Section 3 the limit on the number of edited nodes must be adjusted to the training data; otherwise accuracy will suffer. Still, the precise value of the limit only influences a constant factor in the linear efficiency.
5 CONCLUSION
We introduced the graph edit network, a novel output layer for graph neural networks to predict graph edits. In contrast to prior work. graph edits cover all possible graph-to-graph transformations, including changes in the node set. Importantly, graph edits are sparse, reducing the time complexity from quadratic linear and facilitating interpretation. Further, graph edits can be locally decided at each node, avoiding the need for pooling layers. In addition to the novel output layer, we also provided training scheme which only requires a mapping between nodes as input and then returns target values for all outputs of the linear layer, turning the training into combination of binary classification and regression tasks that can be solved with established methods. We further showed that, if the input node mapping is optimal and the graph neural network layers are expressive enough, graph edit network can achieve edit scripts almost as short as the graph edit distance.
Empirically, we evaluated graph edit networks against variational graph autoencoders, variational graph recurrent nets, and kernel time series prediction on three graph and two tree dynamical systems, proving the concept of graph edit networks. We hope that our work is the starting point for exciting further research in the field of graph-to to-graph learning and time series prediction on graphs, especially in combination with recurrent graph neural networks go beyond the Markovian setting.
9

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
Funding by the German Research Foundation (DFG) under grant number PA 3460/1-1 as well as the Bielefeld Young Researchers' Fund is gratefully acknowledged. D.Z. and D.G. gratefully acknowledge the support of the Swiss National Science Foundation under grant 100021/172671.
REFERENCES
Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau. An exact graph edit distance algorithm for solving pattern recognition problems. In Ana Fred, Maria De Marsico, and Mario Figueiredo (eds.), Proceedings of the 4th International Conference on Pattern Recognition Applications and Methods (ICPRAM 2015), pp. 271-278, 2015, doi |001000220000050222007777777
Zeina Abu-Aisheh, Benoit Gaüzere, Sébastien Bougleux, Jean- Yves Ramel, Luc Brun, Romain Raveaux, Pierre Héroux, and Sébastien Adam. Graph edit distance contest: Results and future challenges. Patfern Recognition Letters, 100:96 103, 2017. doi 10.10066/.parrec2017.00000
Davide Bacciu, Alessio Micheli, and Marco Podda. Graph generation by sequential edge prediction. In Michel Verleysen (ed.), Proceedings of the 27th European Symposium on Artificial Neural Networks (ESANN 20/9), pp. 95- 100, 2019. URL http: www www.. ucl wttpp//.......eee.eeeeei..o...e.
esann/ esann/
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 129:203-221, 2020. doi ne..e.66...
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In J. Shane Culpepper, Alistair Moffat, Paul Bennett, Kristina Lerman, and Joel Mackenzie (eds.), Proceedings of the Twelfth ACM International Conference Web Search and Data Mining (WSDM 2019), pp. 384 392, 2019.
10.1114/332896000 3290967
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez,, Vinicius Zambaldi, Mateusz Malinowski. Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 2018. URL/attss://axx.v.oro
http//axvvv..// org abs http://rrggaas//l000e0 01261
David B. Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, and Lue Brun. Com- paring heuristics for graph edit distance computation. The VLDB Journal, 29:419 458, 2020.
100.00.0007/007788...8
Sebastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. Graph edit distance quadratic assignment problem. Pattern Recognition Letters, 87: 38-46, 2017. doi patree/.....eeee21111.
Wren Chan and Aspen Olmsted. Ethereum transaction graph analysis. In Ella Pereira and Michael Mackey (eds.), Proceedings of the 12th International Conference for Internet Technology and Secured Transactions (ICITST 2017), pp. 498-500, 2017. doi 1T0.00091///TTTT22217....8833 2317333349
Zhiyong Cui, Kristian Hemrickson, Ruimin Ke, and Yinhai Wang. Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting. IEEE Transactions on Intelligent Transportation Systems, 21(11):4888 1:4483-4899 2019.
doi. SOTTTS..11.22955.. 2019.2950416
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In D. Lee. M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.). Proceedings of the 20th Interna- tional Conference 2016), pp. 3852. 2016. URL fatppss//paprrs.iibs..cc 6081 wetel-coooluiiio -euralll www.eurrl-eetwossssssoes o
Advances in Neural Information Processing Systems (NIPS
terin
10

---

Published as a conference paper at ICLR 2021
Tianfan Fu, Cao Xiao, and Jimeng Sun. Core: Automatic molecule optimization using copy & refine strategy. In Francesca Rossi, Vincent Conitzer, and Fei Sha (eds.), Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 638-645 2020. 10. (1l.0./600//aaiv//./..
Martin Gardner. The fantastic combinations of John Conway's new solitaire game "life". Scien- tific American, 223:120-122: 1970. URL http::::/www.scienifffiii.. com
19700-11
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. Dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Bood Based Systems, 187:104816,
2020. doi To.
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Gameet (eds.), Proceedings of the 32nd International Conference on Advances in Neural Information Processing Sys- tems (NeurIPS 2019), pp. 10700-10710, 2019. URL http: 1224-va11 at ona lonal-grese graph recurrecureeee
httphhttt://pprrreeeeeee /papers.pppp.p.peppp nips. weriis.cc/pppe ccppaper///ppaacceecp neural -
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U.V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Proceedings of the 30th Conference on Advances in Neural Information Processing Systems (NIPS 2017). pp. 1024-1034, 2017. URL waw.onnaaarrrrrrraee
wnw.s.iiiic.............. cc.ppperr
1103-induee i ve representa on- lea rn
Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecule optimization. In Tara Sainath, Alexander Rush, Sergey Levine, Karen Livescu, and Shakir Mohamed (eds.), Proceedings of the 7th International Conference Learning Representations (ICLR 2019), 2019. URL
.ntt forum?
id=Bl xJA
Matt J. Keeling and Ken T.D. Eames. Networks and epidemic models. Journal of the Royal Society Interface, 2(4):295-307, 2005. doi/doi.org/I0 100 1098//siff.0005000551
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio, Yann LeCun, Brian Kingsbury, Samy Bengio, Nando de Freitas, and Hugo Larochelle (eds.), Proceedings of the 3rd International Conference on Learning Representations (ICLR 2015), 2015. URL httthhtts://aatt /awxiv www.wawwww..w...attt........ootp abs/1412. 6980
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Hugo Larochelle, Samy Bengio. Brian Kingsbury, Yoshua Bengio, and Yann LeCun (eds.), Proceedings of the 4th International Conference on Learning Representations (ICLR 2016), 201
URL https: arxiv. org/ abs 02907
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. In Yarin Gal, Christos Louizos, Zoubin Ghahramani, Kevin Murphy, and Max Welling (eds.), Proceedings of the NIPS 2016 Workshop on Bayesian Deep Learning, 2016b. htl.http://// htttp::/bbayssiadeeepp....
org/ 221220166 6/ http://apppseeeeeeeeeeee BBL_ 1ell__6pppp.. pdd
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 1(1):2 es, March 2007.
0o0/10.1145/2212999117733
Vladimir Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8):707-710, 1965.
Yujia Li, Oriol Vinyals, Chris Dyer. Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv, 2018.
http//axxxv.rr.rraa////// abs 1803.810 03324
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine
11

---

Published as a conference paper at ICLR 2021
Learning (ICML 2019), pp. 3835-3844 2019. URL BtLLtttp/pppcceealggg...tt press/ v97/1i19d. html
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Jour- nal of the American Society for Information Science and Technology, 58(7):1019-1331, 2007. doi 1002//si..2055)))
Naoki Masuda and Petter Holme Detecting sequences of system states in temporal networks. Scientific reports, 911):1-11, 2019, 401110.100884411996777333334---
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498-511 -11, 2009. doi 200110..109//NN.20822000000
Amit A. Nanavati, Siva Gurumurthy, Gautam Das, Dipanjan Chakraborty, Koustuv Dasgupta, Sougata Mukherjea, and Anupam Joshi. On the structural properties of massive telecom call graphs: Findings and implications. Philip Yu, Vassilis Tsotras, and Edward Fox (eds.), Proceedings of the 15th ACM International Conference on Information and Knowledge Management (CIKM '06), pp. 435-444, 2006. 461110.145/113311111888
Benjamin Paaßen, Christina Göpfert, and Barbara Hammer. Time series prediction for graphs in kernel and dissimilarity spaces. Neural Processing Letters, 48(2):669-68) 689, 2018. 10.100//// 1063/ 017-9684-5
Benjamin Paaßen, Barbara Hammer, Thomas Price, Tiffany Barnes, Sebastian Gross, and Niels Pinkwart. The continuous hint factory providing hints vast and sparsely populated edit distance spaces. Journal of Educational Datamining, 10(1):1-35, 2018. URL / leducations datamin
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B Schardl, and Charles E Leiserson. EvolveGCN: Evolving graph convolutional networks for dynamic graphs. In Proceedings of the Thirty-Fourth AAAI Conference Artificial
Intelligence (AAAI-20), pp. 3363-5370, 2020. doi/httss//doi..org http:////ooiooo//.... 1ttp//1....100000 160116600. v34404.5984
Emile Richard, Stéphane Gaïffas, and Nicolas Vayatis. Link prediction in graphs with autoregressive features. Journal of Machine Learning Research, 15(1):565-55 593, 2014. URL http::/wwti
jmlr. htt.r.ooo/papers/11//.......
html
Kaspar Riesen and Horst Bunke. of bipartite graph matching.
Approximate graph edit distance computation by means Image and Vision Computing, 27(7):950 959, 2009. 7th IAPR-TC15 Workshop Graph-based Representations
wtw.://6...mavi.2008...oo (GbR 2007).
Alberto Sanfeliu and King-Sun Fu. A distance measure between attributed relational graphs for pattern recogmition. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13())3333-36, 1983. 10010001100TSMMC.838.3661111
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, 2009. d0. 100.1119//NN..00 2008 2005605
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In Jun Wang, Long Cheng, Andrew Leung, and Seicchi Ozawa (eds.), Proceedings of the 25th International Conference on Neural Information Processing (ICONIP 2018), pp. 362-373. Springer, 2018. 011111..007/978---0000000000
Naoki Shibata, Yuya Kajikawa, and Ichiro Sakata. Link prediction in citation networks. Jour- nal of the American Society for Information Science and Technology, 63(1):88-85, 2012. doi 100.000.00//s..211666
Johan A K Suykens, Tony Van Gestel, Jos De Brabanter, Bart De Moor, and Joos Vandewalle, Least Squares Support Vector Machines. World Scientifie, Singapore, 2002. do.
12

---

Published as a conference paper at ICLR 2021
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Yoshua Bengio, Yann LeCun, Tara Sainath, lan Murray, Mare Aurelio Ranzato, and Oriol Vinyals (eds.), Proceedings the 6th International Conference Learning Representations (ICLR 2018), 2018. URL https:/ http:://ppeerevieeee net./ feat/fforin forum?
id=rJXMpikC2.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Tara Sainath, Alexander Rush, Sergey Levine, Karen Livescu, and Shakir Mohamed (eds.), Proceedings of the 7th International Conference on Learning Representations (ICLR 2019), 2019.
/ arxiv.v..... www.i..rr .rg. abs 0ttp//110.000800
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovee. Graph con- volutional policy network for goal-directed molecular graph generation. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 6410-6421.
Curran Associates, Inc., 2018a. URL http::/paperre .nprrrsniiiie wtppscccppppprr.///ppppppppppppe
7877 graph convolut iinnall polllcooollyy-iee network for goal di direcced wowcoeeddmolocee molecu Mar- wrw.eeeela....aaaggeeeeeeee.ee
pdf
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovee. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning (ICML 2018), pp. 5708- 5717, 2018b.
.mlr wwwpppresssv. v80 youllyyollll 8a html wtt.sem......ees.......
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In Jérôme Lang (ed.), Proceedings of the International
Joint Conference Artificial Intelligence (IJCAI 2018), pp. 3634-3640, 2018. URL https pdf
www. 1 wtw.ea/.org/rroceecnggg/////////
Daniele Zambon, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Autoregressive models for sequences of graphs. Chrisina Jayne, Zoltan Somogyvari, Plamen Angelov, and Manuel Roveri (eds.), Proceedings of the 2019 International Joint Conference on Neural Networks (ICNN 2019),
pp. 1-8, 2019. doi 1009//CNN..011..88222111
Kaizhong Zhang and Dennis Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal Computing, 1245):244-122 1989. doi 113.000.17//118000
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-VAE: A variational autoencoder for directed acyelic graphs. In H. Wallach, H. Larochelle, A. Beygelzimer, d' A'cch Buc, Fox, and Garnett (eds.), Proceedings of the 32nd International Conference on Advances in Neural Information Processing Systems (NeurIPS 2019), pp. 1586-1598, 2019. URL http: http::/pppprrs...t www.nipppppcpp.....cppppppp 1437-d-va
aut for directed acyeetted-acylli--rraaa..
Junbo Zhao, Michael Mathieu, and Yann LeCun. Energy-based generative adversarial network. In Yoshua Bengio, Yann LeCun, Mare Aurelio Ranzato, Hugo Larochelle, Oriol Vinyals, and Tara Sainath (eds.). Proceedings of the 5th International Conference Learning Representations wwwp:/www...g////...o.///.. 03126
(ICLR 2017), 2017. URL
13

---

Published as a conference paper at ICLR 2021
A PROOFS
A.1 PROOF OF THEOREM 1
We structure our proof into three lemmas. Lemma translates a graph mapping into script, Lemma 2 translates script to graph mapping, and Lemma 3 shows that the length never gets longer by doing
so. This argument is analogous to Proposition by Bougleux et al. (2017), who show a one-to-one correspondence between bijective mappings and reduced set of edit scripts, called restricted paths. In this work, we aim to connect the notion of graph mappings to teaching signals for graph edit networks. To make this connection, we require stronger statements about the structure of such graph mappings and a different order of operations compared to |Bougleux et al. (2017), such that we provide full argument here, without relying on [Bougleux et al. (2017) directly.
First, we define the corresponding script to a graph mapping.
Definition 2. Let G = (V = {l...., M), E, X) and H = (V'= {l..... N}, X') be two non- empty graphs, i.e. M, N > O, and let v be a graph mapping between G and H. We then define the script 6g. corresponding to a between G and H as follows. First, we construct a replacement rop,,
for all i (in ascending order) where i S M, (i) S N and म. + I (())) Let 03 be the script of all these replacements. Next, we construct an insertion ins for all (in ascending order) where i >> M and (i) S N. Let Rig be the script of all these insertions. Next, we construct an edge insertion eins,,; for all (i,j) (in lexicographically ascending order) where (i, & E' but (1)1), +i)) E E.. Let 8etus be the script of all these edge insertions. Next, we construct an edge deletion edel for all (1 (in lexicographically ascending order) where (i.j)= E but (v))), (()) & E'. Let dgdel be the script of all these edge deletions. Finally, we construct node deletion del, for all i S M (in descending order) where (1) > N. Let Jdel be the script of all these node deletions. We then define the overall script d. as the concatenation 8z 5 Jins Jeins Jodel Fdel
We next show that the scripts resulting from graph mappings do what they should, i.e. they to indeed convert G to a graph that is isomorphic to H.
Lemma 1. Let G = (V = (l...., M), E, X. and H = (V' = fl....., N). ")EE E',X'' empty graphs, i.c M, N 0, let vp be graph mapping between G and H, and let by be the corresponding script. Then, H 8g isomorphic to H.
......,,,
X') be two non-
Proof. In particular, by applying b% and Jine to G, we obtain a node set V and attributes X with
the following properties. First, consider U == ii E Vib(i) < N}. Due to our construction and Definition of a graph mapping, it holds U ii < MlF(1) S U < < M + Inss } and (U) Lj < N < M) J Insp V". Further, for all E U we have by construction I; 20) because either i & M and Z = F (ig in which case this holds trivially, or S M and T + F *()) in which case replacement was applied which ensured the condition, or M < i M + [ in which case an insertion was applied that ensured the condition.
Next, we consider the graph G = EV, = g Big Jeins (edee())) (G), i.e. the graph that results from additionally applying all edge insertions and edge deletions. For this graph we can show that the subgraph restricted to the node set U is isomorphic to Hl with the isomorphism & restricted to U. In particular, we have already shown that (U) = V' and that ã; = F Zot It remains to show
that for all j E holds: (i.j) E E and only if (+(1), (t)) E E'. This, however, is exactly the condition enforced by the edge deletion/insertion construction above. Accordingly, the subgraph restricted to the nodes U is indeed isomorphic to H.
Additionally, we also obtain that for any node & U. there exists no edge (i. or (j. in E. because these would have been deleted by Jedel, Finally, Edel deletes all nodes & U (in descending order to prevent interference in node ordering) and the remaining graph = 8(G) is isomorphic to H, because it is exactly the subgraph we have analyzed before. This concludes the proof.
In next step, we define the conversion back from script graph mapping.
14

---

Published as a conference paper at ICLR 2021
Definition 3. Let G = (V = (1...., E, and H (V' = "II...,,,,EE, be two non-empty graphs, Le. M,N > 0. Further, let H- = (V' -1,...,,NN NN,,',, ",,,,x"" x') be graph that is isomorphic to H via isomorphism 3 fl......) NN + (I.....N) from V to V". ..e. for all i V i = = and (i. E F. if and only if (((1).))) E F.. Finally, let 5 = ōi.-..,00 5r be an edit script, such that (G) = H. Then, we define the mapping 4/ [L..... M M+ N3 + {1 {L...., M NN recursively as follows.
First, if T = 0 (i.e. 8 is empty), we set 1/g = 3ي extended by the identity on the inputs N + +1..... M N. Next, if T O, let ey == 26.....87 and consider the first edit 81. If 61 (G) G, i.e. the edit has no effect, we set 4/3- = uf.
If 51 = del, for some j. we set (1) = 1/ (1) for all i < j. (i)(1) = li - 1) for all i > J. and (i)() = M + N.
If 61 ins for some T. let i == /''0" (M + N + 1) and distinguish four cases. First, if 1 S M
and (M(M + +1) S NN, we set (1) = (i) for all i o 1" and vz((") = e'( + N + 1). Second, if vf (i) for all i + i" with i E M, (2((")) = (M
i" S .M and (s'M 11 > N. we set tbx(t)
and (i) = '
for all i > M. Third, if i" = M + 1, we set (1) = (1))) for all i S M
and (1) di ((i+1) for all i > M. Fourth, if it > M + 1, we set vi((1) = v., restricted to
{1, M + N..
Finally, if o1 is any other edit, we set thy v¹
We will later prove in Corollary 2 that the resulting mapping 1/3 is indeed graph mapping.
Refer to Figure 3 for example of the construction. In particular, we consider the script 3 del2, insg, insg,, del3, transforming the graph G = (V [1, F 0, X) the graph N
(V" = 21, E' 0, X'), which in turn is isomorphic the graph H/ = (V' 21, 3), E' 0, X'' for some attributes X, X", X', and for the isomorphism d between H and H with (1) = (2) = 1, and (3) = 2.
Now, we construct the mapping 43 recursively from the last edit to the first The initial mapping for the empty script is vh. 31,...,3 + (i) = for i > 3. Next, we incorporate the last edit of the script delg. Because this is a deletion, the graph before the deletion must have had one node more. Accordingly. viael, is now defined on the domain and image {l,.... 4 + 3]. In more detail, following Definition 3 we obtain the mapping
3) - (1..... 3 3} with (i) (i) for i < 3 and
didel, (1) = (1) = 3, del, (2) = (2)
dh (4 - 1) = Mdel, (5) (5 - 1) = 4, Ddel, (6) = (6 ---1 11 = 5, and t'del, (7) = 1. 117-1 1) = 6. In the figure,
1, dedel, (3) 4 4 7, Vaels (4)
this mapping is obtained by following all arrows from the graph right of H to their end point.
Next, we incorporate the edit ins Because we consider an insertion, the graph before the insertion had one node less. Accordingly, the mapping thinss, delg is now defined on the domain and image 3 + 3}; it is crucial that we remove the entry 3 + 3 + 1 7 from the codomain of our mapping, The pre-image of 7 is i* = Videlg (7) = 3. Further, we need to consider whether the inserted node 3 + 1 4 gets deleted later in the script. Because dldel (3 1) = 2 < 3, we know that this is not the case. Accordingly, the first of the four cases in Definition 3 applics and we obtain Viuss, (i) d'eets (i) for all + i" = 3 and Wimss, (3) t'aas (7) = 6. Note that this is still a proper graph mapping, i.e. the bijectivity is never violated and the only node j E Ins delg is
3
with the pre-image dels, (2) = 4 = 3 + 1, as required.
Now, we incorporate another insertion ins;, We observe that the newly inserted node 2 2+1=3 3 will get deleted later, since we have t'ine del, (2 + 1) = > 3. Furthermore, the newly inserted node 3 the same time the pre-image of entry 2 3 + 1 6, which we need to delete later. Accordingly,
the third case in Definition 3 appliee and we obtain 4/insz, inssg. (i) plinsyy (i) for < 2 and
Viner, jins,, ,del (i) = Vinse, dels (i + 1) for > 2. Because we do not refer to Vinss, ddel dels (2 + 1) = 6,
we do not leave the desired range {1...., 2 3}. Also note that Ins anagg dely still contains only
the node 2, which has the pre-image Virma,, inss, delg (2) = 3 =
2 + 1 as required.
15

---

Published as a conference paper at ICLR 2021
H
H
delg
ins
insg,
del2
G
H
1
1
2
2
2
2
+
2
4
2
1
2
3
3
3
3
4
4
4
4
4
5
5
6
6
7
Figure 3: An illustration of the conversion of a script 8 = delg, insg, insg,, del3 to a graph mapping
4/g. We start with an initial isomorphism v/ between the graph H and the graph H = ( (left) and then adjust the mapping from left to right until we arrive at final graph map between G and H (right). The mapping is obtained by following the arrows from G to H. For simplicity we assume that the graphs have no edges. Also note that we include the 'virtual nodes' M + I,..., M + N in the illustration.
Finally, we incorporate the deletion del2. As stated in Definition 3 we thus obtain ())
Viusz, jussg dely (t) for i 2, (2) 3 3 6, and (i) Pins jins,, dely (i - 1) for > 2. The
final mapping is thus (1) 3, (2) 6, (3) 1, 1/3 (4) = 2, ( 4, and (6) = 5. In
Figure we obtain this mapping by starting at G and following the arrows to their end points.
Our next step is to show that the mapping constructed from a script is indeed graph mapping and that additional structure applies, which we can exploit later on.
Lemma 2.
Let G. A, H be graphs as in the previous definition with isomorphism & between H and H, let 8 = 81, ò1,..., 86 be a script, such that 8(G) = H, let vha be the corresponding mapping, and let vo (1...., M + N} + (1....,M + N} be defined as vb(i) = s (db((i)
V....,,. if (1) < N and (i) (1)(1) otherwise, i.e. the mapping composed with oh-1. Further, let Del = fi M w(i) > N}. Then, vp is bijective. Further, for all & Delg, vb is monotonously increasing (constraint 1), and the image of to on Delg is {M + N + +1+1-1 Delpl..... M + N} (constraint 2).
Proof. We perform this proof via induction over the length T of the script = 8i,..., 87. If 0, is the identity, which is obviously bijective, yields Del, = 0 (such that constraint 2 fulfilled), and is monotonously increasing (such that constraint 1 is fulfilled).
Now, T > let s be defined as v above. but between the graphs 81 (G) and H. Accordingly. zi is a bjective mapping from and to {I,..., + N by induction. where M' is the size of the node set of 8, (G). Further, by induction we also know that & is monotonously increasing on all inputs except on Del == (i < M')x((() (i) > N} (constraint 1) and that the image of v on Del is precisely {M' + N 1 | M' NN (constraint 2). Now, consider the first edit 8,- If 81 leaves the node set as-is, we obtain M = M', 1b v', and both constraints hold by induction.
If 5, del, for some j S M, we obtain M' M - 1. Further, by the definition of v/z. we obtain vi)) = (i) for < j. (0)) = li
1) for i > j. and vi(i) = M - N. Accordingly, -1 I...,, + N bijectively to [l..... M + N - 1} and the setting (()) M + N completes the bijective map. Further, j E Delg and is mapped to M + N, conforming to constraint 2. Finally, for all other inputs both constraints hold by induction.
& maps the set {1.....j -
If 51 inss for some H, we obtain M' M + 1 and thus e is bijective map from and to (1 (1....,M M N + 1}. Now, let i 1 M + N 1) and distinguish four cases.
16

---

Published as a conference paper at ICLR 2021
First, if 1" & M and (M + I N we obtain (11)
and xb(+t) e (i) for all i i + 1'
N + 1). First, observe that &5' (M + +++1) < M+ +1, otherwise v + M + N +1 and i* M + N + > M, which is a contradiction. Accordingly, 3/ is a bijective map from and to (1.-.., M + N) because by definition ve maps the set (1...., 8 1) U (i" + +,...., M + N} to (1, M N) map. Furthermore, we obtain ('M + N + 1) N. Otherwise, the monotonicity of w would require all values M + 2...., . + N to be mapped values I N as well. However, there exist only N such values and one is already blocked by (MM + 1), which is contradiction. Accordingly, (M + N + 1) > N and thus i" E Delg. Both constraints hold by induction.
N ( (+ +1)) and the setting (= M (M++++++++
completes the bijective
Second, if 1 < M and (M + > N we obtain (1) (i) for all i i 1' with i S M, (x((*) = 15 (M + 1), and va(1) di + for all > M. Accordingly, to is a bijective map from and to (1..... M + ] because by definition dp maps the set {1..... 8" 1.i"
M + N) to the image of v/ for the inputs {1..... i" -1,1 +,," M, M .. M M + 1), which exactly (I...., M + +N} {M + 1)}. Setting (i"("") 2 + 1) then completes the bijective map. Further, on all inputs except i* both constraints still hold due to induction. For i", we obtain 1" E Delp because eb(i*) v (M 1) N and because M + Del constraint also holds for i" due to induction.
Third, if MM + 1. obtain (i) = v0(i)) for all i M. (i) (' 1) for all i > This a bijective map from and to {1...., M + N} because by definition & maps (i..... M + N) to the , image of v/ for {1...... M, M + 2..., M + N + 1}, which is exactly {1...., M + N}. Further, the constraints hold due to induction.
Fourth, if M + we obtain vbz(1) of restricted {1, .1,.... M + N]. In this case, we observe
that 1" must be M + N +1 1. Otherwise, we would obtain v (i" +1) < M + N +1 = vi(("). which contradicts monotonicity of J. Accordingly, restricting e {l..... M + N] does indeed yield a bijective map to {l,.... M + N} which conforms to both constraints due to induction.
Because this covers all possible edits, this concludes our proof.
Corollary 2. Let G, H, H, 3. 8, voz. and tb be defined as in the previous Lemma. then, dyy is graph mapping between G and H.
Proof. First, observe that (i) = ((((t)) for all i with vg(()) S N, and (1) (ii otherwise. Further, observe that wy must thus be bijective. Otherwise, 16 or 3 could not be bijective. Next, assume that there exists some E Insø, such that 1/7 (j) > M + [Iss,g] Then, because t/g is bijective, there also exists some i with M- < i S M + |[ns with v/x(1) & Inspg. This implies which contradiets the monotonicity constraint tb.
that (h)(t) N 2 j. even though ( Accordingly, gly, thg is indeed a graph mapping between G and H.
Lemma 3. Let G = (V= = Bh...,,M.H. E, X) and H- = = M, empty graphs, i.e. M,N > O. Further, let H (V'' = -1,...,NNJ NY. X') be graph that is isomorphic to H via isomorphism &b (1....,N) NJ - (I,...,N,, and let ō be an edit script with B(G) H. Finally, let v0z be the corresponding graph mapping between G and H and let 8 be the edit script corresponding to that graph mapping. Then, it holds: [60g (8).
be two non-
Proof. We again prove this claim via induction over the length T of the script 5 = 51,-..,57 Er.
First, = G = G = A. Accordingly, V/ is ; (extended with the identity on M 1,...... M N). It then follows that 8 is empty. In particular, there can not exist any S M with 7 # F 2000
F s0)
otherwise è would not be isomorphism between H and H. Accordingly. 553 is empty. Further, there can not exist any i > M with (i) < N, because wxx(1) i> M = NN Accordingly. Rins is empty. Next, for all i I . it holds (i.j) E + (i)(1), .g(5)) (w(11, +()) E',
otherwise vp would not be an isomrrphism between H and H; and for all i.j > M = N it holds (i.j) & E and (1z(1), vx())) (i.j) $ E' per definition. Accordingly, both Jeins and godel are empty. Finally, there can not exist an S M with viz(i) (() N because the image of $ is
17

---

Published as a conference paper at ICLR 2021
8 gins goins godel is overall empty as {I, {I...., NN. Accordingly, 5% is empty and thus døg well, i.e. 16 = 0 & 0 = (5), as claimed.
Now, consider the case T > 0, let v/ := 1889 Br and let G (V, E, = 81 (G). Further, let
Jir be the script that ş is transformed into based on G and H. By induction, 1Jgr1 s T 1. We now consider the first edit 8,.
If 51 has no effect G, we obtain 1/3 = v/ and by definition قØz d which in turn yields
|ō - 10 s - T as claimed.
for j f i, and ã; = मे + T. Now, distinguish two cases. If x = To) i.e. 5; = F For + F.. Bay contains by construction an edit rept,æ and otherwise the same edits as 8er, such that we obtain |d = ا + = T 1 1 = as claimed. If ā * "0)( i.e. ô1 sets ã, to a value which is temporary and not equal to the final value of / po()) we obtain dwz = dw because & by construction already contains an edit rep (1)))
If 8 = rept.s for some S M and some म. we obtain dy = V. = -V
Accordingly, we obtain 1ō,g - 10 S T - 1 < T as claimed.
If 61 ins; for some F, we obtain V -U + 13, 1), F. = Fe for i M, and ēM+1 F. Now, let let 1" == &' (M + N + 1) and distinguish four cases.
First, if < M and (M + 1) < N. we obtain (1( (1) for + i* and (3( 3M - N + 1). As argued the proof of the previous lemma, v/ + N + 1) > due to monotonicity of
v. Accordingly, 8 is deleted both in day and in pøg. Further, M + 1 is inserted in 65, but not in
8w while all other edits remain the same such that we obtain 18 |6 115T-1+1=10 as claimed.
Second, if < M and (M + 1) > N, we obtain = for all i with i S M and i it, +)((i)) = (M + 1), and (i) = vi (i + 1) for all i> M. Because v' (M + 1) > N, i" is deleted both in 8ur and in dgz. Further, M + 1 is deleted in 8 but not in ōøg. while all other edits remain
=
the same, such that obtain |ō0g| | - < T - 2 < T claimed.
Third, if 8- = M + 1, we obtain (1) = v/( (i) for all i S M and (1)(1) = e' + 1) otherwise.
Again, M is deleted in d but not in 8eg. while all other edits remain the same, such that
obtain |6 = |6 - < T 2 < T claimed.
Fourth, i > M +++ 1, we obtain v/z = v restricted to (1...., M + NJ. Further, 1" = + N +
as argued in the proof of the previous lemma. Accordingly, M 1 is inserted in 6,, but not in 8 while all other edits remain the same, such that we obtain |ō = 10 + +1 claimed.
+15 T
1 T as
Next, 81 cinss.j. we obtain 2/s = v6 as well as V = =V, V.X- = X', and E E= = EU (i. Now, distinguish two cases. If (W((i), (f(i)) E F', d0, inserts (i.j) whereas Jur does not, while all other edits remain the same, such that we obtain 18
10 - 1+1 ' as claimed. Conversely, if ( (i), of (7)) & E', & deletes (i,j) whereas 83g does not, while all other edits remain the same, $ T 2 < T as claimed.
such that we obtain | = 00.l
Next, if 6 = edeli.j. we obtain 4/8 = w/ as well as V= = =V, X = X', and À. = E (i.j))) Now, distinguish two cases. If (x), e (f)) & E', Jøs deletes (i.j) whereas 8nr does not, while all other edits remain the same, such that we obtain 18pg = - 1 11 < 1111+1 = T as claimed. Conversely, if (w)(1), (f)) E E", & inserts (i,j) whereas J does not, while all other edits remain the same, such that we obtain |50g1 = 1 - < T 2 << T as claimed.
Finally, if 6, = del, we obtain (5) v' for all j i. =( and () M + N, as well as V = (1....,
= -' 1) for all j > i. ........ M 1). By = H, for all j V. and E = E. Accordingly, døg deletes whereas &gr does not, while all other edits remain the same, such that we obtain 15pz 1 + S T 1 + T as claimed.
Because this covers all possible edits, this concludes our proof.
18

---

Published as a conference paper at ICLR 2021
We note again that the entire argument up this point is analogous to Proposition of Bougleux jet al. (2017). However, in contrast to Bougleux et al. (2017), we do not rely on a notion of restricted edit scripts, instead comparing to all possible edit scripts, and provide stronger results regarding We also slightly change the order of operations for
the structure of our graph mappings via Lemma 2 consistency with Algorithm| 1.
A.2 PROOF OF THEOREM? 2
The heart of our proof is Algorithm 2 which translates graph mapping to a corresponding teaching signal for a graph edit network. We prove the correctness of this algorithm with the following Lemma. Refer to Figure 4 for graphical intuition.
In particular we consider in this example the graphs G= (41.2, [ (1,,), 3), 13,1)) x) and H = (11, 2, 4, 5,6), {(1, 2), (2, 3), (3, 1), (4, 5), (5, 4)), X') as well as the graph mapping & with (1) =3, 3, (2) = 2. and (3) = 1. Note that H is not fully connected. In particular, we have the connected components 2,3,, 54,5), and {6}. In itself, this would not be a problem, but note that Algorithm
| can only insert a new node that is connected to an existing node. Accordingly, we can not insert node without any connection the pre-existing graph. However, this would be required for the insertion of nodes 4, 5, and 6. To manage this, A Algorithm 2 first constructs auxiliary edges (in lines 2-5) connecting the new nodes to the already existing part of the graph. In our example, these auxiliary edges are (3, 4) and (3, 6). Then, the algorithm computes (in lines 6-9) the shortest path to any inserted node from any already existing node, yielding the paths n/ (3, 4), x. = (3. 4. 5), and TO = (3, 6). Line 13 then re-defines the shortest paths as a shortest-path tree with children (3) = (4, 6) and ch(4) (5).
Lines 14-22 then take care of performing the actual node insertions, where insertions are put into different steps of the teaching signal they can not be performed at the same time. In particular, we need to use multiple steps whenever a single node has multiple children in the shortest-path tree and whenever a node that does not yet exist needs to make an insertion. Both is covered by the cepth-first-scard in lines 14-22. In particular, we first insert parents, then children, and we insert children in succession. In our example, this results in node 4 being inserted in the first step (by node 1) and nodes and 6 being inserted in the second step (by nodes 1 and 4, respectively).
Then, line 24 initializes the third and final step of our teaching signal which performs all remaining edits. In particular, line 25 sets up all replacements (irrelevant this case), line 26 all edge insertions ((2, 1). (3, 2), and (5, 4) in this case), line 27 all edge deletions ((1, 2). (3, 1). (1, 4), and (1, 6) in this case), and line 28 all node deletions (none in this case). Lines 29-30 ensure that the edge filter scores at K+ and k++1 are consistent with the edge edit scores & K++ Finally, we return the result.
The resulting script shown in the bottom of the figure. Note that this script is not short as possible because it contains four additional auxiliary edits, namely the edge insertions (1, 4) and (1, 6). which are then deleted in the end. These additional edges occur because we need insert new nodes connected to existing nodes. Accordingly, the disconnected components C1 and C2 from H are first connected and then disconnected at the end of the script, yielding the desired graph.
We first consider the time complexity of the algorithm. First, note that computing connected components in line 2 is possible in O(N). Similarly, the minimum computations in lines 3-4 are possible in ONN. Constructing the auxiliary graph in line 5 may need O(N2) for dense graph. Because we have unit edge weights for the shortest path computation, a simple breadth-first-sarde suffices, making the computation in line 7 O(N). Because we need to repeat this computation for each insertion, lines 6-9 are overall in O
Lines 10-12 are slightly implementation dependent. In principle, constructing & for each step would require ((M + _))).. J. But because this matrix is always zero, we can construct it once and re-use for every step. All other operations are linear, yielding ((M + ?)² overall.
The computation of the children in the shortest-path tree in lines 13 is linear in the number of insertions, which is in ONN).
Lines 14-22 perform a depth first search through the mootesst-path trees, which is in O(N) again.
This also includes recording the inserted edges for line 23.
19

---

Published as a conference paper at ICLR 2021
shortest paths (lines 6-9): n = (3, 4), x (3, 4, 5). 75 = (3. 6)
Shortest path tree (line 13): ch(3) (4, 6), ch (5)
G
H
5
C1
insertions (lines 14-22): 11. +1, 221 +1, 22,4 +1
2
3
edge insertions (line 26):
63,2, = f3,322 63,5,4 +1
edge deletions (line 27):
C,,,2 C3 C3,1,4 C3,1,6 -1
script: 8 = ins, 1,1 ins, eins ins, eins eins eins3,2 einss,1: edel 2, edel edel edel3,1
Figure 4: A graphical illustration of the construction of teaching signal via (f1,2,3), ((1,2), (1,3), (3. 1))
Algorithm 2 for the inputs G (11,2, 4,5, 6), (1, (2, (3,1), (5, 4)), X'), and vo with (1) = 3. (2) = 2. and v²3 1. The mapping & is shown in blue, the auxiliary construction of H (lines 2-5 in the algorithm) in red and dashed. After constructing H, first compute shortest paths from 3 to each node in C₁ and C2 (top right). This defines the shortest path tree with children ch(3) (4, 6) and c4) wi (4) = 4 needs to insert one node (5). Since this is not possible in one step, the first step inserts only node 4 (P1.1 +1) and the second step nodes and (v2.1 +1, F2,1 +1). The remaining edit scores ensure that the correct edges are inserted and deleted, yielding the final script at the bottom. This is exactly the script generated by vh, except for four superfluous auxiliary edits, namely eins1,4, cins1. 6, edc11,4 and edel1,6-
X). H
5. Accordingly. node v/- -3)
needs insert nodes (4 and 6), and node
20

---

Published as a conference paper at ICLR 2021
Algorithm 2 An algorithm to turn graph mapping between two graphs G and H into a teaching signal for a graph edit network, such that the teaching signal yields the same edit script as v, up to 2 2C -11 1) auxiliary edits, where C' is the number of connected components in H.
1: function MAP-TO-SIGNAL
non-empty graphs G = (V = (I,...,M,, E, x) and H -l,...,,A. [['=[],.... N,, , E", X'), graph mapping between them)
(V'
2:
Compute the connected components of H Cı....,Ce C2 where C C Ins..
3: Set c f minjec, j for all L}.
4: Set +- Mi
5:
Construct H = (V', E' U' ((T)))))) eL)r), for j E Ins, do
6:
7:
Compute shortest path r/....,, Fk from the closest node .ं E fI,...., N) Inss to RB in H.
8:
9: end for
10: for E (1,..., [Ins do
11: Initialize ih Ö, Yv X, +- -I, -i, + 0.
12: end for
13: Let ch(j) be the children of node j in the shortest path trees from roots क| to inserted nodes.
Initialize stack S with entries (m 0) for all j Insg. Set K 0.
15: while S is not empty do
Pop (j, k) from S. Set + 1. Set (j).
17:
for j' E ch(j) do
Set Me-to 6- +1. Uhtes t Tyy.
19:
Add (j', + cc S.
20:
c c+ 1. K t- max K, k + cj.
21:
end for end while
22:
23:
Let E" be the set of inserted edges (1,j) due to line 18.
24:
Initialize ūK+1 + 0, YK-1 + 0, [K+ + -I, oker + -I, EK+1 + 0.
25:
Set 1K+ t To(0) if (() < N.
b performs replacements
26:
Set +- if (i,j) EUE" and (+)))+()) E E'.
performs edge insertions D performs edge deletions
27:
Set ( &- if (i.j) ()))) E EUE" and
$ F'.
28:
Set Vk+1, f- -f (0() > N.
performs node deletions
29:
Set k+1, f- -+1 E + 0 for any j.
30:
Set Sete K+1,j +- +1 if (K+,is + for any i.
31:
return (V), X1, C 2 E E)....., (ūk+1, X XK+I, (+1 E
32:
end function
21

---

Published as a conference paper at ICLR 2021
Lines 24-30 require only matrix and set lookups. making them overall ((M + N))). In summary, we obtain the claimed efficiency class of OMM² N2).
Now, let G and H be any two non-empty graphs, let C be the number of connected components in H, and let &b be a graph mapping between them with ||nsø] < .N, i.e. at least one node is not inserted. Further, let 3 = (6) ( f., teaching signal returned by Algorithm 2 for mapping 4, and let 5 be the output of Algorithm for input s. Then, we wish to prove the following properties for
(Dx+1- X 1
kK+) 1) be the
1. B(G)=1) H.
2. |8 S 2
3. The first K steps of s contain only insertions with Vk,i = 0 = V441, = .... ...VK+I, = O.
4. The K+ 1th step contains no insertions.
5. K S [Insp].
First, observe that lines 1-3 of Algorithm 2 are guaranteed to work because H is non-empty and thus at least one connected component exists, and that each connected component is per definition non-empty. Further, line works because we restricted e such that at least one exists with (i) I N, which means that the minimum is well-defined. Accordingly, the graph H in line is well-defined as well. This preparation was necessary to ensure that the shortest-path computations in lines 6-9 are valid. In particular, assume that there exists some j E Ins, such that j is disconnected in H from any node & Ins,. Now, distinguish two cases. First, if j lies in a connected component of H which contains some node with i & Insp, then is connected to i, which directly yields contradiction. Otherwise, j lies in one of the connected components C. Accordingly, j is connected to c₁ However, then j is also connected to (r) in by construction, where r & Insp, which is also a contradiction. Thus, the shortest path required in lines 6-9 is well-defined.
Next, observe that any shortest path computation gives rise to shortest path trees as required by line 13. If multiple shortest paths overlap, we obtain proper trees, otherwise trivial trees which are just copies of the shortest paths.
Lines 14 to 22 now insert all nodes in the shortest paths trees according particular ordering, namely that any parent is inserted at least one step before its child and each child is inserted one step before its right sibling. By using this ordering per step, that whenever a node stops to do insertions, it never needs to start again, and that all nodes enumerates all nodes in the shortest path trees).
ensure that no node makes more than one insertion
reached (because the Septh-first-seanee
Accordingly, note that the K first steps of the generates script, when plugged into Algorithm | yield exactly the insertions in gins as given in Definition 2 (up to reordering). in addition to edge insertions between an inserted node and its predecessor in the shortest paths tree. These inserted edges are stored in E" in line 23.
The remainder of the algorithm takes care of all remaining edits. In particular, line 24 initializes a trivial teaching signal with zero node edit scores, zero attribute matrix, negative edge filter scores, and zero edit score matrix.
Then, line 25 sets all attributes the target attributes, which yields all desired replacements of already existing nodes and leaves the attributes of inserted nodes as they were. In other words, line 25 yields, via Algorithm| exactly the script grep as given in Definition
Line 26 sets edge insertion scores EK+13J = 1 for all edges (i,j) such that (v(1), +()) is in E" but not already in E E". In effect, after line 26 we have accumulated all edge insertions in Roins as given in Definition [ plus exactly L edge insertions cins, (a))- This is the case because the shortest path any node e necessarily की and n a. If any other, equally short path would exist, would be in a connected component with some node i & Insg. which is a contradiction. Accordingly, lines 14-22 have ensured that node r inserts node ai ( at some point.
Next, line 27 sets edge deletion scores CK+16 1 for all edges (i, that are in E U E" but where (1)))), (r)) is not in E" anymore. Note that there is no overlap between these edges and the edges considered in line 26, such that handle both cases within the same step. Also note
22

---

Published as a conference paper at ICLR 2021
that this step yields all edge deletions from from dodel given in Definition plus exactly L edge deletions vd))), due to our previous argument.
Finally, line 28 sets node edit scores VK +1, = 1 for all nodes i with (b()) > N. This yields exactly
the node deletions from ovol as given in Definition 2
Lines 29-30 merely ensure that the edge filter scores are consistent with &
In summary, when we plug the teaching signal returned by Algorithm 2 into Algorithm 1 the resulting script contains exactly the same edits as 0g from Definition 2 up to reordering inserted nodes, plus L edge insertions eins,, and L edge deletions edel, y (e)) Because the edge deletions remove precisely the edges which have been additionally inserted before, we obtain 8(G) (G).
Further, Lemma shows that (G) = H, which implies property above.
Next, observe that is exactly the number of connected components of H which are subsets of Tn8.- Because we required that does not insert all nodes of H, there must exist at least one connected component of H which is not subset of Insg. Accordingly, L is upper-bounded by C' and we obtain the bound required in the second property.
For the third property, observe that the first K steps do indeed only insert nodes. Further, node i only stops insertions when all its children in the shortest path tree are inserted. Once that is done, does not start inserting anymore, implying the desired property.
The fourth property holds trivially because lines 24-30 never set node score to value >>
Finally, the fifth property holds because each insertion step in lines 14-22 contains at least one insertion. This is because K set via line 20 exactly a step in which the last insertion occurs and in insertion occuring in step K implies that either a left sibling insertion or the parent insertion had However, if at least one insertion occurs in each step, there can at most K S [Ins,]] steps, as claimed.
to occur in step K
only remains to show that the bounds properties and 5 are sharp. To do so, consider the example graphs G ({1), 0, 0) and H ({1,.... C), 0, 0). Note that all nodes in /f are isolated, such that they form trivial connected components. We note in passing that it also possible to construct an example for non- trivial connected components, e.g. by constructing H as C copies of G, where G can be arbitrarily shaped. Here, we consider the simplest case.
Now, let vp be any mapping between G and H such that [lnsø] < C. In other words, (1) < C. Then, line 2 of 2 yields C₁ = {{} for I < (1). and C, = {I +1+ 1} for 2 (1) with 1 (1...., ...
C - 1} and at becomes the only element of C₁ in line 3. Line yields r 1. Accordingly, N = - C}. (#111,c))) ci),..., ((
cc-1)) .)}, X'). Following the arguments above, the script resulting via Algorithm [ from the output of Algorithm 2 then includes one edge insertion and one edge deletion for each edge in H, in addition to the C' - 1 insertions that are contained in óg. Accordingly, we obtain |6| = 18pl + 2 (C 1), which precisely the bound. Further, because node |lnsø]
1 can only perform single insertion per step we obtain K C
23

---

Published as a conference paper at ICLR 2021
B AN EXAMPLE LOSS FUNCTION
For training, we propose a simple loss inspired by the margin hinge loss of the support vector machine (Suykens et al. 2002). Recall that the SVM hinge loss is given
eSVM (wT, ((E
[- (E.9)
>
w." 3 --0+1 2
where 1 E [-1, is the desired label and y - v. Z is the predicted label.
In more detail, let A be the adjacency matrix of the input graph, let 17, X, ",,t,," E be the GEN layer output, and let D, X, et E be the scores of our teaching signal. Then, we define the loss LGEN as:
M
guode (us qudee(s,
+ galter (et, + giller (eT (7 + Σ gatte (T,, + Σ podge (ety, aiy);
2:22222 (1.))e) 20,2, 20
(2)
where enodo(v, 0) is defined as [V + 112, for D < -2. as [-v 112 for i > +2 and as [|||
1 otherwise, with [x]+ = max h being the rectified linear unit; where ffiter(e, é) is defined as M [e+ + 113 if S 0 and as M I- $ otherwise; where gater is the squared Euclidean distance for continuous attributes and crossentropy for discrete attributes; and where gedge (e, é, a) is defined 1 and é < - 2, as [-c] if
as |e + 1 if
and 2 2. as [e]3 if a 0 and é S 1. and We can show that this loss is zero if and only if the scripts of the teaching signal and the GEN output are equal (plus a loss for margin violations).
as [-c++ 1]2 if a 0 and ė
Theorem Let A E {0, {0,1)NxN be an adjacency matrix and 17 X, e,,te E as well as 8, X, et, E be two sets of edit scores.
Then, loss 2 is zero if and only is the following conditions hold.
1. For all i: Df > + v is at least 1,
2. for all : i: S }. |Pal is most 4-
3. for all i: i < 1/2 vs is at most 1,
4. for all :: if 2 2'
1
gattr (T, 2,)
5. for all : "f 0, et is least 2.
6. for all i: :f < 0, et is at most 1
2'
7. for all i: 1f > c, is at least
8. for all i: 11f5 6, is most
-
9. for all i,j [ 0, 87 0, فزg > + and aij = 0, ei. is at least 1,
10. for all i.j: > 0, θ, > 0. رب S 1/2 and arj = 0, Et,j is at most 0,
11. for all i.j ef > 0, é > 0, ر 2 1 and at = 1, ei is at least 0, and
12. for all i.j: ef > 0, ē > 0, & < - -/2 and ai = 1, G, is at most -1.
Further, if the loss is zero, the edit scripts resulting from Algorithm for both sets of edits are equal.
Proof. We first re-frame all conditions in terms of the component losses goode gattr, efittor and godge
1. In this case, the node loss is goode (v:, 2.)) = [ vs + 1] Accordingly, the loss is zero iff
- +1 5 + ii 2 1, claimed.
24

---

Published as a conference paper at ICLR 2021
80
Figure 5: An illustration of the loss goode (left) and the loss godge (right) for different teacher and adjacency matrix inputs.
2. In this case, the node loss is guode (24, 14)) = [12/] - = Accordingly, the loss is zero iff
vil S + 1n t. claimed.
3. In this case, the node loss is gaode (vi, (.)) = [vs + 1 Accordingly, the loss is zero iff
1/2 + -15 0 - Vi S 1, claimed.
4. This condition directly refers to the attribute loss and is obvious.
5. In this case, the filter loss is ffilter (eT e,t) = - + 4 Accordingly, the loss is zero
iff c + 0 = c 2 2. as claimed.
6. In this case, the filter loss is gfitter (et ,e,t)
[e] + 2] Accordingly, the loss is zero iff < 2.4 as claimed.
e, + <
7. In this case, the filter loss is gflter (e, 2, = c + 1 Accordingly, the loss is zero
iff - + 2 0 c 2 2,2 as claimed.
8. In this case, the filter loss is fflleer (e, e,,) [ej 1 Accordingly, the loss is zero iff e, 0 - eg < 2. claimed.
9. In this case, the edge loss godge (ci,g: Cr, (s.)), = Ci + 11. Accordingly, the loss is zero iff -Gj +1 = Eij 2 1, as claimed.
10. In this case, the edge loss is gedge (Gi Ciji (i.j) = [cr.s Accordingly, the loss is zero iff
fi S O, as claimed.
11. In this case, the edge loss is gedge((a Ei,j, ai.))
6ig Accordingly, the loss is zero
iff -Ei.j I + Eigj O, as claimed.
12. In this case, the edge loss is godge (ei.j Eijj ai.j)
[ei. + 11 Accordingly, the loss is
zero iff ei +150 + e. S -1, as claimed.
Accordingly, we found that all component losses are zero if and only if the aforementioned margin conditions holds. Since the entire loss is a sum of these component losses and no contribution can be negative in this case, the entire sum is zero if and only if all contributions are zero, which proves the claim. Also refer to Figure 5 for a graphical illustration of the component losses gnode and gedge
This directly yields the second part of Theorem 3 In particular, if condition 3 holds, the same edge deletions are appended in line of Algorithm Due to conditions 5-8, the loops in lines 3-8 iterate over the same elements ji, Further, due to conditions 11-12, Algorithm appends the same edge deletions line 5, and due to conditions 9-10, Algorithm D appends the same edge insertions in line 6. The replacements in line are the same due conditions 2 and 4, well the fact that gattr being zero implies equal inputs by definition. The loop in lines 1 11-14 now iterates over the same elements due to condition 1, and the same node/edge insertions appended in line 12 due
25

---

Published as a conference paper at ICLR 2021
1
20
p(insle) p(dellp)
+1
0.8
15
-1
0.6
p(replu)
1oss
10
=
0.4
0.2
5
0
0
-0.5
0.5
-
0.5
0.5
Figure 6: Left: The node edit probabilities p(ins|e) (bluc), p(dellz) (orange), and p(reply) (red) for B 10 for varying (left). Right: The crossentropy loss (solid) and the GEN loss times /3 (dashed) for varying v and for D = +1 (blue), = -1 (orange), and = 0 (red).
condition 4 and the fact that gattr being zero implies equal inputs by definition. Finally, the same node deletions are generated in line 15 due to condition 3. Thus, the output of Algorithm T is the same for both inputs.
C PROBABILISTIC INTERPRETATION OF THE GEN
Given the node edit scores v4, the edge filter scores ef and e, well as the edge edit scores eap as returned by a GEN layer, we can define the following probabilities over edits. The probability of node insertion node i is the logistic distribution p( v4) Z1/(1 + exp(- (44 })]] the probability of a deletion of node is the logistic distribution p(dell2;) = Z3/ (1/e(1+000) (1+expl- 3-(-v;-))); p(dellp)) In all cases, 3 >> 0
and the probability of replacement is p(rep| p2) = 1 p(ins|u,, aperr-aarmettrr regulating the slope of the distribution with respect to ii and ZB = (1+ (1++)) chosen to ensure that pinns] [ = p(ropl } = p(del - )) = p(rep) 2). Le.
the decision boundary between insertion and replacement and - is the decision boundary between deletion and replacement, just as in Algorithm [ For sufficiently high 3, e.g. 3 > 10, we obtain p(ins(es) s 0 for 14 < 0 and p(dellp:)) A 0 for v4 > 0, such that the distribution becomes equivalent to two binary logistic distributions "glued together'. Also refer to F
straightforward loss based on this probability distribution is the crossentropy between p and the strict teaching distribution ginss];, = if i; > 1. qdcll
(.)) if & < <-1 and g(roplé,) 1 2- otherwise. The loss for varying v and & and 3 = 10 is shown in Figure 6 (right). As we can see, the behavior is qualitatively very similar the GEN loss from Equation 2 shown in dashed lines. The most noteable differences are that the crossentropy behaves linearly for sufficiently extreme whereas the GEN loss behaves quadratic, and that the GEN loss strictly zero when the margin is not violated, whereas the crossentropy still remains strictly larger than zero. This can lead to empiric problems during learning, as we see in the experiments. The quadratic behavior emphasizes large margin violations whereas small margin violations are less emphasized compared to the crossentropy loss, which yields slightly favorable properties in our experiments.
2
To sample edge edits we perform a three-step process. First, for each node we sample whether outgoing edges or incoming edges are edited with the logistic distribution p( p(T]ett) = 1/(1+exp|-2
Then, we only consider edges (i.j) where T has been sampled for both i and and we sample edge insertion with probability p(eins)eaj, (.,)) 1/(1 + exp[-3 , (ei. - })) if a.j 0 and p(eins) eijj, ai.) = 0 if a.j 1, and we sample an egde deletion with probability p(edel/e.,, at.)) 1/(1 + expl- 3 (- 2)) if oi.j 1 and p(cins|ci,j (s.)) = if az.j = 0. Also refer to Figure 7 (left).
() and p(T ) = 1/(1 + expl-B-e;
The crossentropy loss compared to the strict distribution g(cins(és,)) = 1 êf > 1.2 ((ddel)e.,))
if éi,; < 1.4 and q(eins|ér.)) = ((edellé..)) = 0 is shown in Figure 7 (right), Again, we observe that the loss behaves qualitatively very similar to the GEN edge loss, with the striking difference being the square.
26

---

Published as a conference paper at ICLR 2021
0
20
p(einsle, a)
0.8
15
0
0.6
loss
10
0.4
0.2
5
-1
0.5
0
0.5
0.5
0
0.5
Q 1
0
+1
p(edel e, (,))
0.8
15
0
0.6
loss
0.4
0.2
5
0.5
0
0.5
0.5
0
0.5
6
6
The edge insertion probability p(cinsle, a) if the edge is not present. Right top: The crossentropy loss (solid) and the GEN edge loss times 3 (dashed) for ù = +1 (blue) and i = 0 (red) if the edge is not present. Left bottom: The edge deletion probability peedelle, if the edge is present. Right bottom: The crossentropy loss (solid) and the GEN edge loss times B (dashed) for -1 (orange) and (red) if the edge present.
Figure 7: Left top:
27

---

Published as a conference paper at ICLR 2021
Table 2: Summary statistics for all synthetic datasets, in particular the number of unique graphs, the average time series length I (# standard deviation) and the average graph size N (# standard deviation). The number of unique undirected graphs with 8 nodes for degree rules was computed using the nauty-geng function, all averages were obtained via 1000 samples from the dataset.
edit cycles
degree rules
game of life
Boolean
Peano
unique graphs T
12346
2200
10788
34353
3 + 0.82
10.46 + 1.91
10 : 0.00
1.51 + 0.99
11.08 + 11.63
N
3.22 1.03
7.33 1.98
100 + 0.00
4.84 + 2.52
7.82 + 3.89
D3
Ê1,1 =
2
3
4
3
4
22,4
2
D2
V1 = 1
1/4
0/
11,4 =
1
2
2
4
3
2 4
3
1/4
Figure 8: An illustration of the edit cycles dataset, where each graph is shown in black, whereas colored arrows illustrate the system dynamics. Each colored arrow is labelled with the edit scores necessary to move from one graph to the next.
D DATA IN DETAIL
In this section, we discuss the graph dynamical systems of Section 4in more detail and also discuss how graph edit networks can realize solution. The summary statistics are shown in Table
Edit Cycles: The edit cycles dataset is illustrated in Figure g Colored, thick arrows indicate the simulated system dynamics. Each arrow is labelled with the corresponding teaching protocol.
The reference solution to this task is to uniquely identify at each node to which graph it belongs and then decide on the edit. This requires a number of layers equal the graph diameter, in this case two graph neural network layers.
Degree Rules: The degree rules dataset is illustrated for two example graphs in Figure 2 The teaching protocol implements the rules of the dataset as follows. First, for any node with degree larger than 3 we expect 8; 1. i.e. the node should get deleted. Second, for any pair of nodes and j which share at least one neighbor, we expect éi, ε = 1, i.e. an edge should be inserted between the nodes. Third, for any node with degree smaller than 3 we expect ù; > }, i.e. node should get inserted.
To generate the actual dynamics, we limit the process to apply only one rule per connected component. This is because simultaneous application of all rules leads to degeneracies. For example, a 5-clique would be deleted entirely. Instead, we use the following ordering: We first apply rule to the node with highest degree. If rule applies to no node, we apply rule 2 to the node pair with lowest sum of degrees. If rule 2 does not apply, we apply rule 3 to the node with lowest degree. If multiple nodes have the same degree, nodes with lower index take precedence. no rule applies, we perform no edit and the process has converged.
Next, we show that each connected component converges to a 4-clique in this scheme. Note that rule 2 ensures that every connected component becomes fully connected, provided that rule 1 does not interfere. Rule interferes if node degree rises above 3, which will be the case whenever a connected component contains more than 4 nodes. Accordingly, every connected component with
28

---

Published as a conference paper at ICLR 2021
more than 4 nodes must converge to a 4-clique. For smaller connected components, rule 2 first ensures that the component becomes a k-clique for l < 4. Then, rule 2 does not apply anymore but rule 3 applies because all nodes in the component have degree less than 3. Once new node has been added, rule 2 applies again, and so on, until the component is a 4-clique. Finally, note that 4-clique stable because rule applies anymore.
The reference solution for this task is one-layer net with n + neurons. Further, we assign a one-hot coding of the node index attribute. Note that the ordering does not matter, merely that every node has a unique one-hot code. Now, notice that we can compute the degree of node i via the expression Ejev()) 1 Z. This is the case because ž is a one-hot coding of the index and, hence, the expression I I.y is always 1, such that the sum just counts the size of the neighborhood of i, which exactly the degree. Accordingly, we need to apply rule 1 if this expression is higher than 3, and need to apply rule 3 this expression is less than 3. Rule 2 is slightly more complicated. We wish to apply rule 2 whenever nodes and j share least one neighbor, i.c. if (ii) ( o 0. Because the node attributes are one-hot codings of the node index, we can represent the neighborhoods by the sum of the one-hot codings in the neighborhood and the set intersection by their inner product. More precisely, we obtain for any two nodes and j:
Σ
Σ
= - (N())
kEV(()
(EN())
Based on this result, we can identify the need to apply any of the three rules by setting S and fmergee from Equation I as follows.
j (I . 3) (I 5 - 2)
fager = Σ رy and ftherge (Z,9)=
ReLU
JEN
which yields the following representation for all nodes
Ejenia z 1 (W(i)- - 3)
ReLU
((((1)) - 3)
Here, ,3 is defined as == 2- max (3, m). where in the maximum degree in the dataset. Then, we can compute the node edit score as = 3 ( (i) degree is smaller than (rule 3), which is S -1 and only if the degree (rule 1), and which is zero otherwise. Further, we set the edge edit score Ei, o (i) - which is 2 1 if (1() DWOI 2 1 and which is between 0 and 1 otherwise because in that case
o² (1)xxt)). which is 2 1 if and only if the
is larger than
d'(i) (i)
[ReLU([W()] - 3) ReLU((W()) - 3) g2
+ ReLU(3 W(O) ReLU(3 ([OI
(2 max m m3 -
g2
Still, note that this is relatively difficult learn for a neural net because parameters need be to relatively large values (exceeding the maximum degree). Hence the long experimental learning times.
Game of life: Conway's 's game life a 2D cellular automaton with the following rules. Cells can be either alive (xf = 1) or dead (x) = 0) at time t. The state in time t + 1 is given by the equation
if क +2 EjEN(O 2 57
0 otherwise
where (111) is the 8-neighborrood of in the grid. Ishows the development of an example grid.
Our teaching protocol imposes i = x for all nodes and all times t 1, í.e. the node edit score of should correspond to the change in 'aliveness'. Note that our graph connects all neighboring nodes in the grid and that the aliveness of is the only node attribute.
29

---

Published as a conference paper at ICLR 2021
Figure 9: An example 6 x grid evolving over time according to the rules Conway's game of life with alive cells marked blue and dead cells white. Note that even single alive cell close to 'glider' shape breaks the shape and leads to the entire board becoming empty over time.
Our reference solution is one-layer graph neural network with the following setting of faggr and fmergge from Equation
x + 2y
I + 2y 5
Sager (N) =
Σ Tzj JEN
and fmerge (Ir, y) = ReLU
x + 2y 7
I + 2y 8
Now, let y/ == 2; + 2 (eN(s) Tz. Then, we obtain the node representation @ (1) = RRRUU 4, 5, yt 7, 3/ =8,,,)"
With this representation, we obtain the following result for o1 - 02)) + (1).
0 + =0
y < if y1 5
01 - - +0() yi 4 - (y: 55) -5)00+0=
Yi 4 - (y - 5) -(1 - -
- 2
In other words, we obtain (i) - (i) (1(1) + (1)) = =xtt1 Accordingly, we can simply set 1/ (1)
d5(i) o1(1) + (1) (i) and obtain 14 = 2 -² as desired.
Boolean Formulae: We first generate a random Boolean formula using the following stochastic process: Let Σ = {A, V, v, -x, -y. T, L,,,,roo root} be our alphabet of symbols. Then, we initialize a counter ops t 0, a graph G = {{1}. 0, X) with σ1 = root, and stack with 1 as single element. Next, as long the stack is not empty, we pop the top node i from the stack and sample symbol from Σ with probabilities P(^) P(v) = 0.3, P(x) = P(y) = P(-x) = P(-w) = 0.1, node M + 1 the graph with #M+1 being
and P(root)= = P(T) P(L) 0. Then, we add the one-hot-code of the samples symbol, and add the edge (i. M + 1). Further, if we have sampled A adjust the sampling probabilities to P(x)= = P(v) = P(-z) = P(-y)= and P(A) P(V) = P(root)
or V, we push onto the stack two times and increment the ops counter. It reaches
P(T) P(-) =0.
Once the initial graph is sampled, the teaching protocol implements eight simplification rules for Boolean formulae. In particular, we implement the following rules.
1. FAL > I for any formula F. Accordingly, if for two nodes i, we have T, A. 7 =1 and (i.j) E, we impose is
for any node k * with (i, k) E. As minor side note, mention that we consider tree edits according to Zhang & Shasha (1989) for this dataset instead of graph edits, i.c. when we delete node i, the children of automatically get connected to the parent of i. If F is leaf, we also impose ú -1
2. FAT + F for any F. Accordingly, if for two nodes i,j we have H. = A, I. = T and
(1,5) E F., we impose ù; = i; = -1.
3. FVT = T for any F. Accordingly, apply the same scheme in rule 1, just with the condition F; = V and 7 =
4. FVL 1 + for any F. Accordingly, if for nodes i,j we have Z, V, 2, and
(i,j) E F., we impose i; b; = 11
5. x SxA x + I and y A + y. Accordingly, if we find three nodes j, k. such that Z = A, 3, Fh E (z. v). and (i,7), (i, k) E F,, we impose és Ú3 1.
30

---

Published as a conference paper at ICLR 2021
rule 5
rule 8
A
rule 2
x
1/
ins
1/
i/S
11
=-1
x
V3
x²
T3
L3 =
y
y
y
yo
y
Figure 10: An example time series from the Boolean dataset. The initial formula on the left is simplified until no simplification rule applies anymore. Each arrow indicates one simplification step. Superscripts indicate the index of each node in the graph and blue arrow labels indicate the teaching protocol.
6. x Vz = and y y = y. Accordingly, if we find three nodes i, k, such that 3. = V, -, I E {z, v). and (i.j), k) E E, we impose i; = "j
7. x _λ x = 1 and y y = 1. Accordingly, if we find three nodes i, j. k. such that z= A, (i, E E, and h = x as well as He = =x, or क. = y as well as Th = yy
we impose 8j = =b -1 and ÿ; 1.
8. vV 3 T and V y < T. Accordingly, if find three nodes i, k. such that
-= = v.
E E, and ã.- = x as well as Te = -. or T = y as well as Tx =
we impose 8/ D/3 -1 and ÿ T.
The next step in the dynamic is the graph that results from applying all edits imposed by the teaching protocol. The dynamic process ends once no rules apply anymore. An example simplification process shown in Figure TO
The reference solution is a graph neural network with two layers, where the first layer represents whether certain conditions for the eight rules apply and the second layer implements conjunctions between these conditions. For simplicity, we only consider rule 2 here but all other rules can be implemented with a similar scheme. particular, let (xx) be the one-hot coding of the symbol E Σ. Then, we use the following setting of Saager Jtberger J2 and meegg from Equation
((A)* o T(T) T 7 o(T) Ff d(A)T. .Z)
EiENN i.) JEN- Z.z)
Sager ,,+,,
and
Pnerge (I, = ReLU
(b) + 0 -1)
P2 Patg: ,~=,,~ = and
Paerge ( (,,0) = ReLU
0 + 04
Note that distinguish the neighborhood, V of children and ~ of parents. The resulting node representation in layer 2 is as follows. (i) 1 if ह. = A and i has a child j with Σ, = T. Otherwise, (i) = O. Further, og = 1 if E. = T and has a parent j with T. = T. Otherwise. (1) = 0. Accordingly, we can implement rule by setting v; = (i) (i)),, which deletes both the parent and the child if rule 2 applies.
With the same scheme as for the Boolean dataset we first generate a random addition with at most 3 plus operators. However, for the peano dataset we have the alphabet Σ {+, 0, 1,...,9, 9, succ, root) } and the sampling probabilities P(+) = 1/ and P(1) =... ... P(9) 18 which are changed to P(1) =... P(9) = once 3 plus operators are generated.
Peano addition:
1
Once the initial graph is generated, apply Peano's 's addition axiom until the addition is resolved. In more detail, we apply the following rules.
1. F + = F for any formula F. Accordingly, if we find two nodes i.j with H. = + and z 0 such that j is the second child of we impose in ú -1
31

---

Published as a conference paper at ICLR 2021
rule
rule 3
rule
D1 24 = -1
1/1
+1, 33
8/1
+1, P3
rule 4
6²
8/2
83 =6 6
5
13
5
suice
succ?
04
04
53
An example time series from the Peano dataset. The initial formula on the left is evaluated until only a single number- namely the result of the addition is left. Exponents indicate the index of each node in the graph and blue arrow labels indicate the teaching protocol.
Figure 11:
2. F+ 4'+ suc succ(F) - G for any formulac F' and G. Accordingly, if we find two nodes i.j with म = + and 33 = succ such that j is the second child of i, we impose i; = +1, Y: succ, and 8 11. Again, notice that
tree edits (Zhang & Shasha 1989)
instead of graph edits in this case, such that an insertion at node i automatically establishes edge between and the newly inserted node well as between the newly inserted node and the first child of i, while cutting the direct connection between i and its first child, i.e. the new child is inserted between i and its current first child.
3. F+n n F + suce(n 1) for any number n E {1,.... 9}. Accordingly, if we find two nodes i with T. = + and T.y E (1....,9) 9}, such that j is the second child of i, we impose 8/2 +1, D1 succ, and úن
in one-hot coding.
4. succ(n)
for any number in the alphabet. Accordingly, if we find two nodes i.j with I; = succ, Zz E {O....,9) 9}. and (i,j) E E, we impose V4 11 and új
{O.... 9}. If n 9, we define n + 1 0 to remain
1.
The next step in the dynamic is the graph that results from applying all edits imposed by the teaching protocol. The dynamic process ends once no rules apply anymore. An example time series is shown in Figure I1
Note that, for the Peano dataset, the order of children is important. Accordingly, we assume that there is an auxiliary attribute that codes whether the node is a second child (where the attribute has value 1) or not (value 0). Further, let o(x) denote the one-hot coding of symbol x e Σ and let Φ1ι denote the vector that is zero except for one at the auxiliary attribute. Then, we use the following setting of
flgger Smerger Paggr. and fuergge from Equation
(+)T. F ((succ)* - 04 I
fulge falge (N,NN-== =0 and Pasge (N+,N' Erear x o' (E
fuerge (I, ReLU
o111)
ReLU I1 + 3/2 - 1 +
and M
(
Again, we distinguish between the neighborhood. V of children and A of parents. The resulting node representation in layer 2 is as follows. ()) 1 if 74 + and has a second child j with J = succ, otherwise (1) = O. Further, (i = if 7. = succ and has a parent j with T. = +.
Accordingly, we can implement rule by setting ii = df()) (i) and Th = @(succ) if of(1) = 1.
32

---

Published as a conference paper at ICLR 2021
Table 3: The average precision and recall values (+ std.) across five repeats fro all edit types on the max degree dataset.
node insertinn
node deletion
edge insection
zdge deletion
model
recall
precision
recall
precision
recall
peccision
recall
precision
VGAE
1.00 1 0.0
1.00 1 0.0
0.35 1: 0.2
0.51 1: 0.2
1.00 1 0.0
0.83 4 0.1
1.00 2 0.0
0.60 1: 0.3
XE-GEN
1.00
0.0
1.00 0.0
0.49 0.3
1.00 = 0.0
1.00 1.0
1.00 4 0.0
1.00 2 0.0
1.00 1.0::000
GEN
1.00
0.0
1.00
0.90
1.00
1
0.0
1.00
1.00
E MAX DEGREE EXPERIMENT
In addition to the graph dynamical systems presented in the main part of the paper, we also investigated whether our network is able to identify the node with maximum degree in a graph and delete it. In particular, we generated random graphs from the Barabási-Alber model with a random number of nodes sampled uniformly from {4, 5, 6, 7, 8) and 3 new edges per iteration. We then added special node to the graph that is connected to all other nodes to facilitate communication across the graph. In this setup, identifying the node with maximum degree should be possible in three graph neural network layers: The first layer computes the degree for each node, the second layer communicates the degree information to the special node, and the third layer compares the degree of every node to the information stored at the special node, thus identifying the node with maximum degree. Accordingly, we used graph neural networks with 3 layers and 64 neurons in each layer. All other training hyperparameters were chosen as in the other experiments.
The results shown in Table 3 We observe that VGAE does not manage to identify the node with maximum degree, whereas the GEN with hinge loss is. Interestingly, the crossentropy loss GEN is not able identify the node either (as is visible in the 0.49 value for node deletion recall). This may be because the crossentropy loss converges to zero slower and thus nodes that are correctly classified can still influence the gradient, whereas the hinge loss sets the gradient for nodes that are margin of safety away from the decision boundary to zero (refer to Section B
F ADDITIONAL EXPERIMENTS ON SYNTAX TREES
We additionally evaluated graph edit networks on six datasets of Python syntax trees, where students iteratively solve Python programming task, particular implementing the mathematical function f(x) - _ x² + f in Python (fun), plotting the function (plt), implementing its gradient (grad), implementing gradient descent on (desc), and finding optimal starting values (fin), as well as writing sorting program (pysort). While the latter dataset is synthetic, the former five are recordings of fifteen students. In all cases, our task is to predict the next state of the student's 's program, represented by its abstract syntax tree. For all datasets we used graph edit network with four layers, 128 neurons per layer, residual connections, and tanh nonlinearity, which we optimized using Adam with a learning rate of 10 and weight decay of 10-3 3 for 10k epochs. In each epoch we computed the loss for one randomly sampled time series. To obtain statistics we performed a 5-fold crossvalidation on all datasets.
Table 4 shows the average root mean square tree edit distance between the predicted tree and the actual next syntax tree on all datasets. for graph edit networks (GENs, last row), as well as two baselines. namely the constant prediction (const.), i.e. predicting no change, and the Gaussian process scheme (GP) of Paaßen et al.) (2018). We observe that both the synthetic syntax trees as well as the actual student data are hard to predict, as neither GP nor GEN outperforms the constant baseline. Further, we observe that GEN performs slightly better than GP on plt, grad, and desc, clearly better on pysort (by more than four standard deviations) and slightly worse on fun and fin. Overall, we can not observe a clear advantage of GEN on these data in terms of RMSE, which is likely due to the small set of training data (only 15 different time series). Still, in terms of inference time GENs (below 100 ms on all datasets) clearly outperform the expensive kernel-to-tre translation approach of Paaßen et al. (018) (ranging from below 100 ms over 2 minutes per prediction pysort).
33

---

Published as a conference paper at ICLR 2021
Table 4: The mean RMSEs (++ std.) for the constant baseline, Gaussian process regression (GP) of Paaßen et al. 2018). and graph edit networks on all syntax tree datasets.
model
fun
plt
grad
desc
fin
pysort
const.
7.95 = 1.1
3.78 + 1.2
6.85 + 2.3
3.97
0.6 0.6
1.45 + 0.4
13.45 + 1.3
GP
9.69 - 1.4
2.6
8.70 1.7
13.97 - 3.8
1.32 0.5
26.53 + 1.8
GEN
11.68 + 1.4
2.1
2.1
0.10
1.70
18.89 + 1.2
G PROMOTING SHORTER EDIT PATHS GEN'S TRAINING
Denote with C(del), C(is)), C(edel) and C(cins) the edit costs associated with node deletion, node insertion, edge deletion and edge insertion. Define
8) All + A(T ()(()) C(edel) (G)(G) = (1(11-))
+ (IlE @ (1 A) + (711g) C(cins) + - C(del) + ||:/|2 C(ins)
where I, 1 are a n-dimensional vector and n x n matrix of all ones.
Assuming the edge and node scores have been passed through squashing function in (0, 1), then adding term sp to the GEN's 's training loss will penalize costly edit paths, hence promoting shorter ones.
The total cost derived by constructing edits in & is, in fact, given by
Hedely E EE) C(edel) + |eiisss E E C(eins)
= =(((i.) [n]? Gj < - 2 14 > - aG) = 1}} C(edel) + +[((,,) E [n] : > M, > - (G)is = 0}| C(eins).
We can rewrite it in matrix form. Define for convenience
& E- 2' J_ ブー 1
14 ū> 1
__ E-=
where the operators and are applied component wise and return if "true" and if "false". The matrix form becomes
-_) @ All, C(edel) | e o[- --) 2-) @ (1 A) C(eins)
E- where 3 is the element-wist product.
Conversely, the cost associated with vector is
Σ (Hu [n] : a(G) = 13] C(edel) C(del)) + Σ
(C(eins) + C(ins)
< I C(edel) + +TT vT_ C(del) + +1T 84 (C(cins) + C(ins)).
Assuming that both edge and node scores are bounded by 1, adding the following term to the loss will promote shorter edit path
e (G) = [[11 - E) @ All, C(edel) + || o (1-11 -A)ll C(cins)
+ A(G)(( 8)/_ C(edel) + (T 2//l_ C(del) + ||771 (C(eins) + C(ins)).
34


Reviews:
[{"review_id": "qpdzw3znQxz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "Graph Editing is a prominent research area which overlaps a variety of fields in computer science. As a typical example, a series of graphs - each obtained from its predecessor - can naturally represent the evolution of a system over time. From this viewpoint, it would be natural to obtain a means of predicting how such a series of graphs will evolve over time. The authors introduce a simple output layer (called \"GEN\") that can be used in graph neural networks to do precisely that.\n\nOn the theoretical side, the authors show that GENs have several useful properties, such as the ability to provide a constant-factor approximation of the Graph Edit Distance problem (assuming that a suitable teaching signal is provided). On the empirical side, the authors demonstrate the capabilities of GENs via several experimental evaluations, comparing the results to those of existing time series prediction approaches such as variational graph autoencoders. The experimental results are mostly encouraging: unlike existing systems, GENs can predict node insertions, and GENs also achieved higher accuracy for predicting edge operations.\n\nThe paper is well written. While the introduction and definitions are aimed mostly at researchers who have some knowledge on the topic (and hence I could not verify the details of the results), I believe that the paper would be of interest to the ICLR community. From what I have seen and understood, I think the contribution is also sufficient to warrant a presentation at the conference.\n\nQuestions:\n-In Theorem 1, isn't it important to clarify (in the statement) that the translation can be carried out in polynomial time?\n-Is there a specific reason for using the \"Edit Cycles\" and \"Degree Rules\" systems in the experiments? Both seem like rather arbitrary choices. Would it be possible to use GENs for systems where, e.g., we simply delete an edge incident to a highest-degree vertex in the graph? Or the highest-degree vertex?\n-I'm curious whether GENs could be used to develop a neural network capable of learning to solve classical problems such as computing Treewidth... that problem can also be formulated as a graph editing task (via the elimination ordering characterization).\n\nMinor remark:\nPage 6: \"GENs capability...\" should maybe be \"the capability of GENs...\"; also, \"Experiments are reported in three groups cover\" should be \"Experiments are reported in three groups and cover\"\n\nPost-Rebuttal Update:\nI acknowledge having read the author's response and I also glanced over the new experiments. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Sg922s85khx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Summary\n-------\nThis paper proposes a model that, given one graph, predicts a sequence of edits that transforms this graph to the next one in a sequence of evolving graphs. To this end, it proposes the graph edit network (GEN), which is a linear output layer that transforms node embeddings to a set of scores that are then used to deterministically select graph edits. The space of edits predictable by this model covers the full space of graph changes. The paper moreover shows that, given a graph matching and a pair of graphs, we can algorithmically find a near-optimal graph edit sequence for generating training data. Finally, the paper demonstrates the model's capabilities on a set of synthetic benchmarks.\n\nStrong points\n------------------\n\n+ The paper is well written and properly embedded in the literature.\n+ The approach of solving graph transformation by predicting a complete sequence of graph edits (i.e. including deletion) is novel and certainly very interesting.\n\nWeak points\n------------------\n\n- I am not really convinced by the approach. There is no way for the proposed model to know if it is predicting step K+1 of the ongoing edit sequence or step 1 of a new sequence (put differently: the model has no memory/is stateless; unlike to e.g. existing recurrent graph generative models). There is also no signal telling the user that the edit sequence is finished. So it seems to me that neither the model nor the user can know which edit steps are actually predicted graphs and which are just intermediate states. \n- The experiments only use synthetic toy datasets and a single baseline each. There are no comparisons with recently published models using the common, but supposedly inferior method of generating the next graph from scratch.\n- Theorem 1 does not \"prove that graph edit networks can approximate the NP-hard graph edit distance\" or show that \"edits predicted by the GEN can be sharply bounded to be close to optimal\", as (incorrectly) claimed in the introduction/abstract. The theorem merely shows that the space of possible edits is complete and that the edit sequence length of your training data can be bounded if you have an (NP-hard) optimal graph matching. There is no guarantee whatsoever on what the GEN might predict. Also, GEN doesn't use any mapping, so the statement \"provided that an optimal mapping is used\" is rather confusing.\n- Theorem 1 merely transforms the graph edit problem into a graph matching problem. This is stated on page 5, but considering that graph matching is still NP-hard, the importance of Theorem 1 seems to be overstated throughout the rest of the paper. Especially since it is largely just a variant of Proposition 1 by Bougleux et al. 2017 (as cited).\n- The hinge loss with margin is rather common in deep learning, see e.g. [1]. The novelty of the proposed loss function is thus significantly overstated. [Side note: Its description on page 6 also seems overly complicated. I would recommend that you simplify this.]\n- The paper states that the model can achieve linear instead of quadratic runtime if the number of edge edits are limited. While this might be true, there is no measure on how such a constraint would affect model performance. The experiment described in the last paragraph of the experimental section only provides some data on scaling behavior, not on accuracy. Especially considering that this restriction limits the number of edits by the model and thus breaks its universality it can severely affect the outcome. [Side note: The number of non-negative edge filter scores actually does not need to be constant, it merely needs to scale with sqrt(N) instead of N. So you actually have more wiggle room than you allow yourself.]\n\nRecommendation\n--------------\nI recommend rejection, mainly because of significantly lacking experiments and overstated theoretical results. The presented theoretical results are interesting but do not really give deep insights about proposed approach (specifically Theorem 1). The overall theoretical contribution is significantly smaller than the authors make them out to be.\n\nFeedback for the authors\n------------------------\nI really appreciate the novel approach of predicting a complete instead of a limited edit sequence. I would recommend acceptance if you a) significantly extend the experiments to include real (ideally practically relevant) graph sequences and directly compare to multiple relevant methods, which you already mention in the related work, b) solve the stopping problem mentioned above (i.e. distinguishing between another and the first edit step), and c) make your statements more accurate and avoid overstating your results. Since especially points a) and b) are unlikely possible to be solved within 2 weeks I strongly encourage you to build on this work and submit a better version at the next conference.\n\n[1] Junbo Zhao, Michael Mathieu, and Yann LeCun. Energy-based generative adversarial network. ICLR 2017\n\n\n[Update after author responses]: The authors have addressed most of my concerns and I've updated the score accordingly.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q63RDIO1ybm", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "The authors consider Graphical Neural Networks in the time series model: a sequence of \"edits\" (in its general form) describe the difference between two graphs. This approach generalizes over previous works where changes on node attributes or addition and deletion of lone edges were considered.\nThe advantages of this work are more pronounced in applications where the output of the neural network can be encoded as a number of graph edits (this number being much smaller than the size of the whole graph). This is well motivated.\nThe only weakness of this work is its technical novelty. I think all the ingredients of the work were already available. Though I like the combination as well as their theoretical analysis.\nI also think the paper is relevant enough to be cited:\n@inproceedings{li2019graph,\n  title={Graph Matching Networks for Learning the Similarity of Graph Structured Objects},\n  author={Li, Yujia and Gu, Chenjie and Dullien, Thomas and Vinyals, Oriol and Kohli, Pushmeet},\n  booktitle={International Conference on Machine Learning},\n  pages={3835--3845},\n  year={2019}\n}", "extra_scores": {}, "extra_text": {}}, {"review_id": "0-irX0gptc7", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 an algorithm to learn dynamics on graphs: node scores are computed by a GNN and then used to predict the modification of the graph (node/edge insertion/deletion). \n\nThe training of the GNN is unclear to me. In particular, the authors do not describe how they obtain the 'teaching signal'. Theorem 1 is of little help as 'graph mapping' are not defined.\n\nI have a fundamental problem with this paper: it looks like the GNN is trained to mimic the teaching signal but as claimed by the authors on page 5 '...the key theoretical result of our paper yields a simple way to construct teaching signals...'. Hence what is the point of using a GNN if a simple algorithm gives a satisfactory answer?\n\nI do not agree with the authors about the expressive power of GEN: for simplicity, consider a cycle graph, then for a GNN as the one described in (2), the node representation will all be the same. Hence the node scores will be the same for all nodes and the algorithm 1 will have the same output for all nodes and edges. What am I missing?\n\n[After rebuttal]  Thanks for the clarification, the aim of the authors becomes clearer. However I still think the paper requires more work before publication. \nYour definition of graph mapping is still unclear. From your definition, it looks like the only dependence of $\\Psi$ with respect to the graphs $G_t$ and $G_{t+1}$ are through their number of vertices N and M: \" bijective mappingψ:{1,...,M+N} → {1,...,M+N}with  the  additional  restriction  that  for  the  setInsψ:={j≤N|ψ−1(j)> M}we  obtainψ−1(Insψ) ={M+ 1,...,M+|Insψ|}\"\nHow can this mapping be related to the edit distance of $G_t$ and $G_{t+1}$.\nAfter reading the other reviews, I think the authors should clarify if their gaph mapping is related to the standard graph matching pb see https://en.wikipedia.org/wiki/Graph_matching.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally liked the paper but had several concerns. The rebuttal and revision of the paper could mitigate most concerns and the reviewers are now mostly positive towards the paper. Remaining concerns are mostly about the presentation of the paper which indeed has room for improvements but overall is good enough to accept the paper. 

Decision: Accept (Poster)