Ordinary differential equations on graph networks
Authors: Juntang Zhuang
Nicha Dvornek
Xiaoxiao Li
James S. Duncan
Venue:  (2020)
Keywords: Graph Networks
Ordinary differential equation

Abstract: Recently various neural networks have been proposed for irregularly structured data such as graphs and manifolds. To our knowledge, all existing graph networks have discrete depth. Inspired by neural ordinary differential equation (NODE) for data in the Euclidean domain, we extend the idea of continuous-depth models to graph data, and propose graph ordinary differential equation (GODE). The derivative of hidden node states are parameterized with a graph neural network, and the output states are the solution to this ordinary differential equation. We demonstrate two end-to-end methods for efficient training of GODE: (1) indirect back-propagation with the adjoint method; (2) direct back-propagation through the ODE solver, which accurately computes the gradient. We demonstrate that direct backprop outperforms the adjoint method in experiments. We then introduce a family of bijective blocks, which enables $\mathcal{O}(1)$ memory consumption. We demonstrate that GODE can be easily adapted to different existing graph neural networks and improve accuracy. We validate the performance of GODE in both semi-supervised node classification tasks and graph classification tasks. Our GODE model achieves a continuous model in time, memory efficiency, accurate gradient estimation, and generalizability with different graph networks.

Under review as a conference paper at ICLR 2020
ORDINARY DIFFERENTIAL EQUATIONS ON GRAPH NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Recently various neural networks have been proposed for irregularly structured data such as graphs and manifolds. To our knowledge, all existing graph networks have discrete depth. Inspired by neural ordinary differential equation (NODE) for data in the Euclidean domain, we extend the idea of continuous-des depth models to graphs, and propose graph ordinary differential equation (GODE). The deriva- tive of hidden node states are parameterized with a graph neural network, and the output states are the solution to this ordinary differential equation. Noticing that NODEs are typically trained with the adjoint method, with the advantages of adaptive evaluation and free-form continuous invertible model; however, their performance on benchmark image classification tasks is significantly inferior discrete-layer models. We show the reason is adjoint method generates inaccu- rate gradient due numerical error in reverse-mode integration. We then propose a memory-efficient framework for free-form ODEs with accurate gradient esti- mation, which is fundamental deep-learning models. Furthermore, when ap- plied to invertible blocks, our method achieves constant memory cost with GODE (NODE). We show our method for free-form ODEs generalizes various model structures and achieves high accuracy for both NODE and GODE in benchmark tasks.
INTRODUCTION
Convolutional neural networks (CNN) have achieved great success in various tasks, such as image classification (He et al. 2016) and segmentation (Long al. 2013), video processing (Deng al.) 2014) and machine translation (Sutskever et al.) 2014). However, CNNs are limited to data that can be represented by a grid in the Euclidean domain, such as images (2D grid) and text (ID grid), which hinders their application in irregularly structured datasets.
A graph data structure represents objects as nodes and relations between objects as edges. Graphs widely used to model irregularly structured data, such social networks (Kipf & Welling 20166
protein interaction networks (Fout er al., 20,7), citation and knowledge graphs (Hamaguchi et al. 2017). Early works traditional methods such random walk (Lovász et al. 1993), independent component analysis (ICA) (Hyvärinen & Oja, 2000) and graph embedding Yan et al. 2006) to model graphs, however their performance is inferior due to the low expressive capacity.
Recently a new class of models called graph neural networks (GNN) (Scarselli et al. 2008 were proposed, Inspired by the success of CNNs, researchers generalize convolution operations to graphs to capture the local information. There are mainly two types of methods to perform convolution on graph: spectral methods and non-spectral methods. Spectral methods typically first compute the graph Laplacian, then perform filtering in the spectral domain (Bruna et al. (013). Other methods aim approximate the filters without computing the graph Laplacian for faster speed (Defferrard
al. 2016). For non-spectral methods, the convolution operation is directly performed in the graph domain, aggregating information only from the neighbors of a node (Duvenaud al.) 2015 Atwood
& Towsley 2016). The recently proposed GraphSAGE (Hamilton al. 2017) learns convolution kernel in an inductive manner.
To our knowledge, all existing GNN models mentioned above have structure of discrete layers.
The discrete structure makes it hard for the GNN to model continuous diffusion processes (Freidlin & Wentzell 1993. Kondor & Lafferty 2002) in graphs. The recently proposed neural ordinary

---

Under review as a conference paper at ICLR 2020
differential equation (NODE) (Chen et al. 2018) views neural network an ordinary differential equation (ODE), whose derivative is parameterized by the network, and the output is the solution to this ODE. We extend NODE from the Euclidean domain graphs and propose graph ordinary differential equations (GODE), where the message propagation on a graph is modeled as an ODE,
NODEs are typically trained with adjoint method. NODEs have the advantages of adaptive evalu- ation, accuracy-speed control by changing error tolerance, and are free-form continuous invertible models (Chen al. 2018 Grathwohl al. 2018). However, to our knowledge, in benchmark im- age classification tasks, NODES are significantly inferior to state-of-the-ar discrete-layer models (error rate: 19% for NODE vs 7% for ResNet18 on CIFARIO) (Dupont al. 2019 Gholami al., 2019). In this work, we show this is caused by error in gradient estimation during training of NODE, and propose a memory-efficient framework for accurate gradient estimation. We demonstrate our framework for free-form ODEs generalizes to various model structures, and achieves high accuracy for both NODE and GODE in benchmark tasks. Our contribution can be summarized as follows:
1. We propose framework for free-form NODES to accurately estimate the gradient, which is fun- damental to deep-learning models. Our method significantly improves the performance on bench- mark classification (reduces test error from 19% to 5% on CIFAR10).
2. Our framework is memory-efficient for free-form ODEs. When applied to restricted ferritted-fommmm invert- ible blocks, the model achieves constant memory usage.
3. We generalize ODE to graph data and propose GODE models.
4. We demonstrate improved performance on different graph models and various datasets.
2 RELATED WORKS
2.1 NEURAL NETWORKS AND DIFFERENTIAL EQUATIONS
There have been efforts to view neural networks as differential equations. Lu (2017) viewed resid- ual network as a discretization of a differential equation and proposed several new architectures based numerical methods in ODE solver. Haber & Ruthotto (017)) proposed a stable architec- ture based on analysis of the ODE. Chen et al. (2018) proposed neural ordinary differential equation (NODE), which treats the neural network as continuous ODE. NODE was later used in a continu- ous normalizing flow for generative models (Grathwohl et al. 2018).
There have been many studies on the training of NODE. The adjoint method has long been widely used in optimal control (Stapor et al. 2018) and geophysical problems (Plessix (0066. and recently applied ODE (Chen et al.) 2018). Dupont et al. (2019) proposed augmented neural ODEs to improve the expressive capacity of NODEs. However, to our knowledge, none of the methods above discusses the inaccurate gradient estimation issue; empirical performances of NODE in benchmark classification tasks are significantly inferior to state-of-the-an discrete-layer models.
2.2 GRAPH NEURAL NETWORKS
GNNs can be divided into two categories: spectral methods and non-spectral methods. Spectral GNNs perform filtering in the Fourier domain of graph, thus need information of the whole graph determine the graph Laplacian. In contrast, non-spectral GNNs only consider message aggrega- tion around neighbor nodes, therefore are localized and generally require less computation (Zhou ct al. 2018).
We first briefly introduce several spectral methods. Bruna et al. 2013) first introduced graph con- volution in the Fourier domain based on the graph Laplacian. however the computation burden is heavy because of non-localized filters. Henaff et al.] (2055) incorporated graph estimation pro- cedure in spectral networks and parameterized spectral filters into a localized version with smooth coefficients. Defferrard et al. (2016) used Chebyshev expansion to approximate the filters without the need to compute the graph Laplacian and its eigenvectors, therefore significantly accelerated the running speed. Kipf & Welling (2016) proposed to localized first-order approximation of graph convolution on graph data and achieved superior performance in semi-supervised tasks for node classification. Defferrard al. (2166) proposed fast localized spectral filtering on graphs.
Non-spectral methods typically define convolution operations on a graph, only considering neigh- bors of certain node. MoNet (Monti 2017) uses mixture of CNNs generalize convolution to
2

---

Under review as a conference paper at ICLR 2020
graphs. GraphSAGE (Hamilton al. 2017) samples fixed size of neighbors for each node for
fast localized inference. Graph attention networks (Veličković et al., (017)) learn different weights for different neighbors of node. The graph isomorphism network (GIN) (Xu et al. 2018 has
structure as expressive as the Weisfeiler-Lehman graph isomorphism test.
2.3 INVERTIBLE BLOCKS
Invertible blocks are family of neural network blocks whose forward function bijective map- ping. Therefore, the input to a bijective block can be accurately reconstructed from its outputs. Invertible blocks have been used in normalizing flow (Rezende & Mohamed 2015 Dinh 2016
Kingma& & Dhariwal 2018 Dinh et al.) 2014; Kingma et al. 2016), where the model is required to be invertible order to calculate the len-iensity of data distribution. Later on, Jacobsen et (2018) used bijective blocks to build invertible networks. [oomez et al. (2017) proposed to use invertible blocks to perform back propagation without storing activation, which achieves memory- network structure. They were able to discard activation of middle layers, because each layer's s acti- vation can be reconstructed from next layer with invertible blocks.
ACCURATE GRADIENT ESTIMATION FOR TRAINING OF NODE
3.1
FROM DISCRETE MODELS TO CONTINUOUS MODELS
We first consider discrete-layer models with residual connection (He et al. 2016), which can be represented as:
Ik+1 + fx((
(1)
where F& is the states in the leth layer; (-) is any differentiable function whose output has the same shape as its input.
When add more layers with shared weights, and let the stepsize in Eq. go infinitesimal, the difference equation turns into a neural ordinary differential equation (NODE) (Chen et al. 2018):
dz(() (==()), dt
We use zt)) in the continuous case and Jg in the discrete case to represent hidden states. f(-) the derivative parameterized by a network. Note that key difference between Eq. [ and 2 of f: in the discrete case, different layers (different & values) have their own function fk: while in the continuous case, f is shared across all time
is the form
The forward pass of model with discrete layers can be written as:
Fo inpul, 21 = .o + fo(2o), ... TK = FK +
(3)
where K is the total number of layers. Then an output layer (e.g. fully-comnected layer for classifi- cation) is applied on dk.
The forward pass of NODE is:
dz(t) input + J- (()(),))
2 (7) = x0)
(4)
di
where 20) input and T is the integration time, corresponding number of layers K in the discrete case. The transformation of states is modeled the solution to the NODE. Then an output layer is applied on z(T). Integration the forward pass can performed with any ODE solver, such as the Euler Method, Runge-Kutta Method, VODE solver and Dopris Solver (Milne & Milne 1953
Brown al.) 1989 Ascher et al. 1997).
3.2
BACK-PROP WITH ADIOINT METHOD IS SENSITIVE TO NUMERICAL. ERROR
The adjoint method is widely used in optimal process control and functional analysis (Stapor al. 2018 Pontryagin 2018). We follow the method by (Chen et al. 2018). Denote model parameters 6, which is independent of time. Define the adjoint as:
ØL
a(t) = dz(l)
(5)
3

---

Under review as a conference paper at ICLR 2020
Forward-time
Reverse-lime
Reverse-time
=(t)
k(t))
zlt)- k(t))
To
Tux
Th
time
time
Faxz
time
(a) forward pass
(b) back-prop with adjoint method
(c) direct back-prop through solver
Comparison of two methods for pack-propagation on NODE. As in figure (a), the ODE solver is discretized at points (fa, ft,..,,y (w] during forward pass. Black dashed curve shows hidden state solved in forward-time, denoted as z(t.. Figure (b) shows the adjoint method, red solid line shows the hidden state solved in reverse- tieese-time, denoted as lt().. Ideally 2()) = l(t) and dashed curve overlaps with solid curve; however, the reverse-time solution could be numerically unstable. and causes z(t) * h(tt,, thus causes error in gradient. Figure (c) shows the direct pack-propagation
Figure 1:
through ODE solver. In direct propaaaopa, we save evaluation time points {fo, f1y-..tx } during forward pass; during backward pass, we re-build the computation graph by directly ovaluating at the same time points. this way, x(t,) = h(t,). Since the hidden state can be accurately reconstructed, the gradient can be accurately evaluated.
where I. is the loss function. Then have da(t) -a(t) (f(=(t),t,)) xt)
a(t) - a dt
dL
do - -
(6)
dt
00
with detailed proof from optimization perspective in appendix F. Then can perform gradient descent to optimize to minimize L. Eq. 6 is reverse-time integration, which can be solved with
any ODE solver (Chen et al. 2018 R. To evaluate (f(x())1.0)) we need to determine z(t) by solving Eq. reverse-time (Directly storing =(t) during forward pass requires a large memory consumption, because the continuous model is equivalent to an infinite- model). To summarize, in the forward pass we solve Eq. 2 forward in time; in the backward pass, we solve Eq. 2 and reverse time, with initial condition determined from Eq, at time T.
80
We give an intuition why the reverse-time ODE solver causes inaccurate gradient in adjoint meth- ods. The backward pass (Eq. 6) requires determining f(x(t), t, 0) and @f(a(t))..)) which requires determining =(t) by solving Eq. reverse-time. As shown Fig. [ (a.b), the hidden state solved forward herward-time (z(tz)) and the hidden state solved reverse-time (h(t;)) may not be equal; this could be caused by the instability of reverse-time ODE, and is represented by the mismatch between 2t)) (dashed curve) and f(t) (solid curve). Error h(t) 2tt) will cause error in gradient dL de
Proposition 1 For an ODE the form di = [=((), 1), denote the Jacobian of as Jy. If this ODE is stable both in forward-time and reverse-time, then Re(A:(Js)) ith eigenvalue of Jy, and Re(X) the real part of X.
d=(t)
Vi, where Xc(Jg) is the
Detailed proof is in appendix C. Proposition iindicates that if the Jacobian of the original system Eq. has eigenvalues whose real-part are
then either the reverse-time is unstable. When Re(A)] is large, either forward-tims or reverse-ting time ODE is sensitive to numer- ical errors. This phenomenon is also addressed in Chang et al. (2018). This instability affects the accuracy of solution to Eq. 2 and 6. thus affects the accuracy of the computed gradient.
forward-time ODE
3.3 MEMORY-EFFICIENT DIRECT
THROUGH ODE SOLVER
The adjoint method might be sensitive to numerical errors when solving the ODE in reverse-time. To resolve this, we propose to directly back mack-propagate through the ODE solver.
As in Fig. [a), the ODE solver uses discretization for numerical integration, evaluated at time points {fo, N. Fig. [c) demonstrates the direct proppproongttton with accurate hidden states h(t)), which can be achieved with two methods: (1) the activation x(4;) can be saved in cache for back- back-prop. prop. but requires huge memory; or (2) we can accurately reconstruct att,) by re- re-building the computation graph directly at evaluated time points )t ). Since the model is evaluated at the same time points t; in forward-time it's guaranteed that 2(t)) = h(tt). Therefore direct back prop is accurate, regardless of the stability of Eq.
4

---

Under review as a conference paper at ICLR 2020
Similar to the continuous case, define the adjoint with discrete time. Then we have:
0L a (z((,) 0++1 a, Oz(t,)
@z(li+1)
dL
dz(4:)
d0
00
where is the adjoint for the ith step in discrete forward- ODE solution. Eq. Eq. be viewed as a numerical discretization of Eq. We show Eq. be derived from an optimization perspective. Detailed derivations of Eq. are in appendix E and F.
Algorithm 1: Algorithm for accurate gradient estimation in ODE solver for free-form functions
Define model dz(()
f(z(t), t). where f is free-form function. Denote integration time T.
Forward (f, T, Zu. tolerance):
t= 0, 2 = 20
stateg = f.state (), aache.save(state))
Select initial step size h = ho (adaptively with adaptive step-size solver).
Sime-points = empty.list)
While < T:
state = ffstate.dict(), accept_step- = False
While Not accept sepeept__ppp.._eeee
flload state, state slale.ddcl(statlee (scl(state)
with grad disabled:
z z_ee,, error prrroressimalee = sl
If error esstmmte tolerance:
accept. step = True
z z neww t = h, time time.points.co ppints.appendly.
else:
reduce stepsize according to error eestimate
delete z_new, error eesimmate and related local computation graph
cache. cache.save waaveeeime.pointte return 2, cache
Backward T, zg. tolerance, cache):
fta,
(x) = cache.time points
For 4 in (lo, 1,,,,,,
a(1,+1) = step(J,= step
step 4411 4.)
For & in t1,
Determine att,) HL
and dz(t.)
3z(t,
80
dL M
d=(t,) -== a4 98
return de
Details of our method are summarized in Algorithm] I
We discuss its properties below:
Summary of the algorithm (1) During forward pass, the solver performs a numerical integration, with the stepsize adaptively varying with error estimation. (2) During forward pass, the solver outputs the integrated value, and the evaluation time points {tz}- All middle activations are deleted save memory. (3) During backward pass, the solver re-builds the computation graph, by directly evaluating at saved time points, without adaptive searching. (4) During backward pass, the solver performs numerical version (Bq. of reverse-time integration (Eq.)6).
Support for free-form continuous dynamics There's no constraint on the form of f. Therefore, our algorithm is generic method.
Memory consumption analysis (1) Suppose has N/ layers, the number of forward evaluation step is N, on average, and the evaluations to adaptively search for an optimal stepsize is K. naive solver will take O(N, N, K), while method consumes O(N, x N.) because all middle
5

---

Under review as a conference paper at ICLR 2020
activations deleted during forward pass, and we don't need to search for optimal stepsize in backward pass. (2) If we perform step-wise checkpoint method, where we only store =(t,) for all fy, and compute the gradient dz(f++1] for one i; at a time, then the memory consumption can be reduced to O (3) Since the solver can handle free-form functions, it can also handle restricted form
dz(t.)
invertible block (see below). In this case, we don't 't need to store 2f4,,, and the memory consumption can reduce to (N))).
More memory-efficient solver with invertible blocks Restricting the form of f to invertible blocks (Gomez et al., 2017) allows for O(Ny) memory consumption. For invertible blocks, input is split into two parts (21, of the same size (e.g. x has shape N x C, where N is batch size, C The forward and inverse of a
is channel number; we can split x into #i and D2 with shape N x f) bijective block can be denoted as:
{
1/2 = vb x2, F(I1)) 5/1 ve Fı, G(y2)
V1. G(y2) I1 = 1- 15-1(1 13-
(8)
422 = 3/ 1 y/: F F(x1)
where the output of a bijective block is denoted as (y1, 12) with the same size 22). F and G are any differentiable neural networks, whose output has the same shape as the input. (a, B) is a differentiable bijective function w.r.t when / is given; ( 3) is the inverse funetion of sb.
Theorem If ()(,,)) 9) is bijective function w.r.l a when B is given, then the block defined by Eq. is a bijective mapping.
Proof of Theorem is given in appendix D. Based this, can apply different & functions for different tasks, Since can be accurately reconstructed from y, there's 's no need to store activations, hence is memory-efficient, Details for back-prop without storing activation are in appendix B.
4 NEURAL ORDINARY DIFFERENTIAL EQUATION ON GRAPH NETWORKS
We first introduce graph neural networks with discrete layers, then extend the continuous and introduce graph ordinary differential equations (GODE).
4.1 MESSAGE PASSING IN GNN
As shown in Fig. 2 graph is represented with nodes (marked with circles) and edges (solid lines). We assign unique color to each node for ease of visualization. Current GNNs can generally be represented in message passing scheme (Fey & Lenssen 2019):
message(u.u) (x)) (x 1- eu,v)
(9)
aggregation, (oEN(()) (messogEe
(10)
x = (k) aggregation))))
(11)
where æb represents states of the uth node in the graph at kth layer and e,,, represents the edge between nodes u and v. N(u) represents the set of neighbor nodes for node u. ( represents a differentiable, permutation invariant operation such as mean, max or sum. g(k)) and ((()) are differentiable functions parameterized by neural networks.
For a specific node u, a GNN can be viewed as a 3-stage model, corresponding to Eq. (1) Message passing, where neighbor nodes E (w(u) send information to node u, denoted by message(r.a). The message is generated from function e(-), parameterized by neural network. (2) Message aggregation, where a node u aggregates all messages from its neighbors (u)), denoted aggregation... The aggregation function Ç is typically permutation invariant operations such as mean and sum, because graphs are invariant to permutation.
(3) Update, where the states of node updated according its original states = and aggregation of messages aggregation... denoted as 7.-)

---

Under review as a conference paper at ICLR 2020
4.2 CONTINUOUS- TIME MODELS ON GRAPHS
We can convert a discrete-time GNN to continuous-time GNN by replacing f in Eq. 2 with the message passing process defined in Eq. 9 to I1 which we call graph ordinary differential equation (GODE). A diagram of GODE is shown in Fig. Because GODE is an ODE in nature, it can capture highly non non-linear functions, thus has the potential outperform its discrete-layer counterparts.
We demonstrate that the asymptotic stability of GODE could be related to the over-smoothing phe- special case of Laplacian smoothing (Li et al., 2018), which can be written Y (I ----D-m - LD 1/2)x where X and Y are the input and output of a graph-conv layer respectively, Å + where the adjacency matrix, and D the corresponding degree matrix of A, and y a positive scaling constant.
nomena (Li et al., 2018). It's demonstrated that graph convolution
When modified from a discrete model to continuous model, the continuous smoothing process is:
dX dt = - x/2x
(12)
Since all eigenvalues of the symmetrically normalized Laplacian are real and non-negative, then all eigenvalues of the above ODE are real and non-positive. Suppose all eigenvalues of the normalized Laplacian are non-zero. In this case, the ODE has only negative eigenvalues, hence the ODE above asymptotically stable (Lyapunov 1992). Hence as time grows sufficiently large, all trajectories are close enough. In the experiments, this suggests if integration time 7 is large enough, all nodes (from different classes) will have very similar features, thus the classification accuracy will drop.
Node Edge
Node Edge
Dynamics of a npdo
steo
step
step
Number Steps
Continuous time (b) Cortinuous-time model graphs
(a) Discrete-time model on graphs
Figure 2: Diecrete- and continuous-time models on graph. Nodes are represented with circles, and each node is represented with unique color. Edges represented with solid lines. For discrete-time models in (a), the hidden states of nodes are updated with discrete steps. For continuous-timg models in (b), hidden states of each node evolves continuously with time. The dynamics of nodes represented with dashed lines, with the same color as corresponding nodes.
5 EXPERIMENTS
5.1 DATASETS
To evaluate our method on general NODE, we conducted experiments with a CNN-NODE on two benchmark image classification tasks (CIFAR10 and CIFAR100) (Krizhevsky et al. 2009
We also evaluated our method on benchmark graph datasets, including bioinformatic graph classi- fication datasets (MUTAG and PROTEINS), social network graph classification datasets (IMDB- BINRAY, REDDIT-BINARY) (Yanardag & Vishwanathan 2015). and citation networks (Cora, CiteSeer and PubMed). For graph classification tasks, different from the experiment settings in Xu et al. (2018), we input the raw dataset into our models without pre-pree rre-processing. For node classifica- tion tasks, we performed transductive inference and strictly followed the train validation-d-niteeeeee -est split by Kipf & Welling (2016), where less than 6% nodes are used as training examples. Details of datasets summarized in appendix A.
5.2
MODEL STRUCTURES
For image classification tasks, we directly modify a ResNet18 into its corresponding NODE model. For each block, the function is dz(t) f(((t)) where is sequence of conv bn relu conv - bn relu layers. f is the same as residual branch ResNet, and can be replaced with any free-form functions.
7

---

Under review as a conference paper at ICLR 2020
Ours
Literature
Adaptive Stepsize Solvers
Fixed stepsize solvers
Heun-Euler RK23
RK45
Euler
RK2
RK4
adjoint-ODE
ResNet18
ResNet50
ResNet101
CIFARIO
4.85
4.92
5.29
5.52
5.27
5.24
19.2
6,98
6.38
6.25
CI
22.66
24.13
23.56
24.44
24.44
24.43
37.6
27.08
25.73
24.84
Table 1: Error rate on test set. "Ours" represent NODE models directly modified from ResNet18, trained with Heun-Fuler solver, but tested with different solvers. "Adjoint" the result when trained and tested with adjoint method, reported by (Gholami et al. 2019). We also report results from standard ResNet.
MUTAG
PROTEINS
IMDB
REDDIT
Table 2: Accuracy of adjoint method and direct back-prop, for GODE model with GCN the derivative function.
adjoinl ours
4.6
67.013.7
12.1
69.513.9
80.8+8.3
73.93.1
5..6=5.1
92.4221
For tasks on graph datasets, GODE can be applied to any graph neural network by simply replac- ing in Eq. with corresponding structures (free-form functions), or replacing G, in Eq. with other structures (invertible blocks). To demonstrate that GODE easily generalized to existing structures, used several different GNN architectures, including the graph convolutional network (GCN) (Kipf & Welling 2016), graph attention network (GAT) (Veličković et al. (017)), graph network approximated with Chebyshev expansion (ChebNet) (Defferrard et al. 2016), and graph isomorphism network (GIN) (Xu et al. 2018). For a fair comparison, we trained GNNs with dif- ferent depths of layers (1-3 middle layers, besides an initial layer to transform data into specified channels, and final layer to generate prediction), and reported the best results among all depths for each model structure.
On the same task, different models use the same channel number. For graph classification tasks, we the channel number of hidden layers 32 for all models; for ChebNet, we set the number of hops as 16. For node classification tasks, we set the channel number 16 for GCN and ChebNet, and set number hops as 3 for ChebNet; for GAT, we used heads, and set each head as 8 channels.
on model structures, such as
For every GNN structure, we experimented with different number of hidden layers (1,2,3), and calculated the mean and variance of accuracy of 10 runs.
5.3 COMPARISON OF BACK- BACK- PROPAGATION METHODS
We compared the adjoint method and direct back-propagation on the same network, and demon- strated direct back-prop generates higher accuracy. For CNN-NODE classification tasks, directly modify 18 into NODE18, and report resuls in Table. [ for graph networks, we train a GODE model with GCN parameterize the derivative, and report results Table. 2
Empirical performance Direct proppaaopagttion consistently outperformed the adjoint method for both tasks. This result validates our analysis on the instability of the adjoint method, which is in- tuitively caused by the instability of the reverse-time ODE. On image classification tasks, compared to adjoint method, our training method reduces on CIFARIO (CIFAR100), Furthermore, NODE18 has the same number of parameters as ResNet18, but outperforms deeper networks such ResNet101 on both datasets. Our method also consistently outperforms the adjoint method on several benchmark graph datasets, as shown in Table. 2
rate of NODE18 from 19% (37%) to 5%(33%)
Robustness to ODE solvers We implemented adaptive ODE solvers of different orders, as shown in Table [ HeunEuler, RK23, RK45 are of order 2, 4 respectively, i.e.. for each step forward in time f is evaluated 1, 2, 4 times respectively. During inference, using different solvers is equivalent to changing model depth (without re-training the network): for discrete-layer models, generally causes huge error; for continuous models, we observe only around I % increase in error rate. This suggests our method is robust to different orders of ODE solvers.
Support for free-form functions Our method supports NODE and GODE models with free-form functions; for example, f in NODE18 in Table. Tis free-form function.
8

---

Under review as a conference paper at ICLR 2020
Model
Cora
CheeScor
PolMed
Model
MUTAG
PROTEINS
18008
REDOOT
DISC
$1.6=0.55
71.6220.3
79.2:0.1
733132
114.11
142-36
GCN
add
$1.7=0.77
72.4200.**
80.0=00.20
ODE
1,8g
N1.8-0.1
12.4
73.1
166439
733
DISC
8.3
71.7+0.8
78.9-0.3
DISC
34,0664
706439
7198338
91,0=1.5
GAT
ODE
1ig
83.1=0.4
72.120.3**
22.1
79.0-0.3
ODE
36.116.3
7277377
72.5177
720-300
100
91:2-133
DESC
33.0104
73.023.1
23.3
29:2-25
Cheb
ODE
adk
1,8g
8.4-0.5
82.2 0.4
7033-0066
718
GIN
ODE
INV
87,7152
75.19337
24.13.5
754 3,99
90.5 13
Table 3: Results node classification tasks. We compared various discrete-layer structures (marked with DISC) and their corresponding GODE models (marked with ODE). We tested GODE model with dif- ferent eb functions ("Isii" represents linear sigmoid). each model, we use (#4) mark GODE models that outperform corresponding discrete-layer baselines at a 5% (1 (6) significance level under paired t-test.
Table 4: Results on craph-clasiffictiion tasks. For each base model structure, discerete-layer model marked with DISC; for corresponding GODE, we tested both free-form functions ("free"), and their in- vertible block form ("INV"". For each model, we (**) to mark GODE models that outperform corre- sponding discrete-layer baselines at 5% (1%) signif- icance level under paired t-test.
Integration time
0.5
1.0
155
2.0
5.0
10.0
20.0
100.0
Table 5:
Accuracy of a free-form GCN- ODE on Cora and NODEI8 on CIFARIO, varying with integration time.
Cora CIFARIO 10
80.5
81.6
80.1
80.1
79.3
77.6
68.9
35.1
91.3
95.2
94.2
88.4
10.0
10.0
5.4 GENERAL BUECTIVE BLOCKS
We demonstrate that bijective blocks defined as Eq. [ can be easily generalized: F and G are general neural networks, which can be adapted to different tasks; va 5) can be any differentiable bijective mapping w.r.t. a when 3 is given. We demonstrate two examples of th: (1) additive, forward 1 (a, 3) a + 3, inverse a = in B) n 83 (2) linear_sigmoid, forward is v(a, 3) a x (3gm inverse is a = x (n. 3) // (3).
Results for different ub are reported Table Note that we experimented with different depths and reported the best accuracy for each model, and performed a paired t-test on results from GODE and their discrete-layer counterparts. Most GODE models outperformed their corresponding discrete- layer models significantly, validating the effecctiveness of GODE; different & functions behaved similarly on our node classification tasks, indicating the continuous- time model is more important than coupling function th We also validate the lower memory cost, with details in appendix B.
5.5 RESULTS ON GRAPH CLASSIFICATION TASK
Results for different models on graph classification tasks are summarized in Table 4 We exper- imented with different structures, including GCN, ChebNet and GIN; for corresponding GODE models (marked with ODE), we tested both free-form (marked with "free") and invertible block (marked with "INV"). We performed paired t-test comparing GODE and its discrete-layer coun- terparts. For most experiments, GODE models performed significantly better. This indicates the continuous process model might be important for graph models.
5.6 IMPACT OF INTEGRATION TIME
For NODE and GODE model, during inference, we test the influence of integration time. Results are summarized in Table. 5 When integration time is short, the network does not gather sufficient information from neighbors; when integration time too long, the model sensitive to over-smooth We observe accuracy drop in both cases.
issue, as discussed in Sec. 4.2
6 CONCLUSIONS
We propose GODE, which enables us to model continuous diffusion process on graphs. We propose a memory-efficien direct prok-propngttion method to accurately determine the gradient for general free-form NODEs, and validate its superior performance on both image classification tasks and graph data. Furthermore, we related the over-smoothing of GNN to asymptotic stability of ODE. Our paper tackles the fundamental problem of gradient estimation for NODE; to our knowledge, it's the first paper to improve accuracy on benchmark tasks to comparable with state-of-the-ar discrete layer models. It's an important step to apply NODE from theory to practice.
9

---

Under review as a conference paper at ICLR 2020
REFERENCES
Uri M Ascher, Steven J Ruuth, and Raymond J Spiteri. Implicit-explicit runge-kutta methods for time-dependent partial differential equations. Applied Numerical Mathematics, 25(2-3):511-677, 1997.
James Atwood and Don Towsley. Diffussion-convolutionnal neural networks. In NIPS, 2016.
Peter N Brown, George D Byrne, and Alan C Hindmarsh. Vode: A variable-coefficient ode solver. SIAM, 1989.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6200 2013.
Bo Chang, Lili Meng, Eldad Haber, Lars Ruthotto, David Begert, and Elliot Holtham. Reversible architectures for arbitrarily deep residual neural networks. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differ- ential equations. In Advances in neural information processing systems, pp. 6571-6583, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 2016.
pp.
Li Deng, Dong Yu, et al. Deep learning: methods and applications. Foundations and Trends in Signal Processing, 7(3-4):197-3877 2014.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components esti- mation. arXiv preprint arXiv:1410.8516. 2014.
Laurent Dinh. Density estimation using real nvp. arXiv, 2016.
Emilien Dupont, Amaud Doucet, and Yee Whye Teh. Augmented neural odes. arXiv preprint arXiv:1904.0160 681,,, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Eapuru-Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2224-2232, 2015.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02428 2019.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks, In Advances in Neural Information Processing Systems, pp. 6530-6539, 2017.
Mark Freidlin and Alexander D Wentzell, Diffusion processes on graphs and the averaging princi- ple. The Annals of probability, 1993.
Amir Gholami, Kurt Keutzer, and George Biros. Anode: Unconditionally accurate memory-efficient gradients for neural odes. arXiv preprint arXiv::902. 10298, 2019.
Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger Grosse. The reversible residual net- work: Backpropagation without storing activations. In Advances in neural information processing systems, pp. 2214-2224, 2017.
Will Grathwohl, Ricky TQ Chen, Jesse Betterncourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv:1810.013667 2018.
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. Inverse Problems, 2017.
10

---

Under review as a conference paper at ICLR 2020
Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge trans- fer for out-of-kmowe wwwooo-ooolwde-eeeeeoeeoooee entities: graph neural network approach. arXiv preprint (oXx::7706.05674. 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.0516; 2015.
Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neural networks, (3(45))411-433 2000.
Körn-Henrik Jacobsen, Amoll Smeulders, and Edouard Oyallon. i-revnet: Deep invertible networks. 2018.
arXiv preprint
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible Ixl convolutions, In NIPS. 2018.
Durk P Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Ilya Sutskever, and Max Welling. Im- proved variational inference with inverse autoregressive flow. In Advances in neural information processing systems, pp. 4743-4751, 2016.
Thomas N Kipf and Max Welling. Semi-super classification with graph convolutional net- works. arXiv preprint arXiv: (0..66699.0900 2016.
Risi Imre Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures. In ICML, 2002.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-3440, 2015.
László Lovász et al. Random walks on graphs: survey. Combinatorics, Paul erdos is eighty, 2(1): 1-46, 1993.
Yiping al Lu. Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations. arXiv, 2017.
Aleksandr Mikhailovich Lyapunov. The general problem of the stability of motion. International journal of control, 55(3):531-534, 1992.
William Edmund Milne and WE Milne. Numerical solution of differential equations. 1953.
Federico et al Monti. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, 2017.
R-E Plessix. A review of the adjoint-state method for computing the gradient of a functional with geophysical applications. Geophysical Journal International, 167(2):495550) 503, 2006.
Lev Semenovich Pontryagin. Mathematical theory of optimal processes. Routledge, 2018.
Danilo Jimenez Rezende and Shakir Mohamed. Variational inference with normalizing flows. arXiv, 2015.

---

Under review as a conference paper at ICLR 2020
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Paul Stapor, Fabian Froehlich, and Jan Hasenauer. Optimization and uncertainty analysis of ode models using second order adjoint sensitivity analysis. BioRriv, pp. 272005, 2018.
llya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104-3112, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: arXiv:1710.10003 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008226 2018.
Shuicheng Yan, Dong Xu, Benyu Zhang, Hong-Jiang Zhang, Qiang Yang, and Stephen Lin. Graph embedding and extensions: A general framework for dimensionality reduction. IEEE transactions on pattern analysis and machine intelligence, 29(1):40-51, 2006.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In ACM KDD, 2015.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv: /8/2:v////2000 18/2.0844, 2018.
12

---

Under review as a conference paper at ICLR 2020
A DATASETS
We perform experiments on various datasets, including citation networks (Cora, CiteSeer, PubMed), social networks (COLLAB, IMDB-BINAKE REDDIT-BINARY, and bioinformatics datasets (MUTAG, PROTEINS). Details of each dataset are summarized Table
Table 1: Statistics of datasets
Dataset
Graphs
Nodes
Edges
Features
Classes
Label rate
Cora
2,708
5,278
1,433
0,052
CiteSeer
3,327
4,552
3,703
0.036
PubMEd
1
19,717
44,324
500
3
0,003
MUTAG
188
17.93
19.79
0.8
PROTEINS
1,113
39.06
72.82
0.8
1,000
19.77
96.53
0.8
REDDIT BINARY
200
429.63
497.76
0.8
B DETAILS ABOUT INVERTIBLE BLOCKS
X1
y1
X1
y1
X2
Y2
X2
Y2
Two neural network blocks
Forward Inverse of a bijective function
Figure 1: Structure of hijective blacks. and G can he any differentiahle neural network whose output has the same shape as its input. Blue dot (Orange diamond) represents the forward (inverse) of a bijective function, corresponding to vi (w ( Eq. 8 of the main paper. Left (right) figure represents the forward (inverse) as in Eq.8
We explain the structure and conduct experiments for the invertible block here.
Structure of invertible blocks Structure of invertible blocks are shown in Fig. We follow the work of Gomez et al. (2017) with two important modifications: (1) We generalize to family of bijective blocks with different in Eq. g in the main paper, while Gomez et al. (2017) restrict the form of s to be sum. (2) We propose parameter state checkpoint method, which enables bijective blocks to called more than once, while still generating accurate inversion.
The algorithm is summarized in Algo. We write the pseudo code for forward and backward func- tion as in Torch. Note that we use "inversion" to represent reconstructing input from the output, and use "backward" to denote calculation of the gradient. To reduce memory consumption, in the forward function, we only keep the outputs y/, 3/ and delete all other variables and computation graphs. In the backward function, first "inverse" the block to calculate 11, from V1, V2. then perform local forward and calculate the gradient Ølvi.va]
Experiments In this section we demonstrate that our bijective block is memory efficient. We trained GODE model with bijective blocks, and compared the memory consumption using our memory-efficient function as in Algo. 2 and a memory-ine mmmoor-iinffficient inefficient method as in conventional back- propagation. Results were measured with batchsize of 100 on MUTAG dataset.
Depth
Memory-efficient
Conventional
Table 2: Memory consumption of bijective blocks. "Conventional" represents storing activation of all layers in cache, "memory-efficienn" represents method Algo
10
2.2G
5.3G
20
2.6G
10.5G
13

---

Under review as a conference paper at ICLR 2020
Results summarized in Table. We measured the memory consumption with different depths, which the number of ODE blocks. When depth increases from 10 to 20, the memory by con- ventional methods increases from 5.3G 10.5G, while our memory-efficient version only increases from 2.2G to 2.6G. In theory, our bijective block takes (1) memory. because we only need to store the outputs in cache, while deleting activations of middle layers. For memory-effiiint network, the slightly increased memory consumption is because states of F; G need to be cached; but this step takes up minimal memory compared input data.
Algorithm 2: Function for memory-efficient bijective blocks
Forward (cache, T1, 32, P. G, v)) cache.save( F states, G states])
Backward(cache, U2. F, G, v 89i
Reset F and G states cache
forward in 8
Inverse from y1 y/ to 21, 22
7/1 (()) J. y2 = (122,7))) 7/2 G [2), yn = ((21.7))
G(yz), 21
(y), 112)
f F(21), Ø2
(22.77)
delete 77, f22 T1,
Local forward pass and gradient
delete computation graphs generated by F and G return cache, 81, y/2
X1 X2 = 31 J1.detach (2 #2-dttcc
calculate Y1. Y22 from X1, X2 as Eq.
determine 0(Yi. Y/li,.a]/B [e] X2. OF, 0g
8L
P6 .0..
3.01.0l 3 Y.
21.
3 Kc
delete Y1, 12
X1, X2
return 0T,
11,0011,000
a0..0a//00.0 0nl
C PROOF FOR PROPOSITION
dz(t) Proposition 1 For an ODE the form di (=((),)) denote the Jacobian of f as Jy. If this ODE is stable both in forward-time and reverse-time, then Re(Ax(J)) = 0 Vi, where Xc(Jg) is the ith eigenvalue of Jy. and Re(X) the real part of X.
Proof Denote 5 - 1, where is the end time. Notice that the reverse-time in is equivalent to forward-ting in s. Therefore, we have forward-time ODE:
dz(t) = ((((1),
(I)
dl
and reverse-time ODE:
dz(s) =))(s) g(2()),8)
(2)
ds
Therefore, we have X(Jr) = - -(,g). For both forward-time and reverse-time ODE to be stable, the eigenvalues of need have non-positive real part. Therefore
ReA: SO, Red:(Ja) = -ReA: 50, Vi
(3)
The only solution is
Re):(J,) -ReN(J)) =0 Vi
D PROOF FOR THEOREM
Theorem For bijective block whose forward and reverse mappings are defined as
y2 + 22, F(x1))
I 1 3/1 G(yz) I2 - U2 F
Forward(ai, x2)
Reverse(yn,
1/1 + (21 G(yz)
(T, 9) is a bijective function word A. when is given, then the block is bijective mapping.
14

---

Under review as a conference paper at ICLR 2020
To prove the forward mapping is bijective, it is equivalent to prove the mapping is both injective and surjective.
Proof
Injective
We need to prove, if Forward(21, x2) = Forward(13- F4), then 1₁ = 23. 22 = F.A-
The assumption above is equivalent to
Fo) = F 2A)
V2 ( F(a1)) (F,,, F(rz))
(5)
(II, G(uz)) - (13,, G(v2))
(6)
Since (b 33) is bijective w.r.& a when ,3 is given, from (6), we have 21 = T3. Similarly, condition on æ1 23 and Eq.(5), using bijective property of vh, we have 22 24.
Therefore, the mapping is injective.
Surjective
We need to prove [21, [12) s.l. Forward(a1, #2) = [y1.3/2.
Given V1, U/. we construct
w ((v))) -
(2, 1 F(a1))
Then for the forward function, given bijective property of v., apply Forward and Reverse defined in the proposition statement,
22 (122, F(11)) v/ (100 ( (12. F(x1)) F(z1) y22
(8)
21 (21. G(vz)) eb (0 G(yz)) G(yz) t/1
(9)
Therefore we construct 21, s.t. Forward(z1; x22) [v1 v24 Therefore the mapping is surjective. Therefore is bijective.
E DERIVATION OF GRADIENT IN DISCRETE CASE
We use a figure to demonstrate the computation graph, and derive the gradient from the computation graph.
z(to)
z(t:)
z(ti)
z(tr-1)
z(tx)
The loss is L, forward pass is denoted with black arrows, gradient pookppropggttion is shown with arrows. We use p to denote each path from 0 to L., corresponding to all paths in red that goes from I to O.
dT.
TT,
aL
0z(1.)
dz(1,)
Σ
Σ a,
(10)
d0
30
Jz(4)
00
15

---

Under review as a conference paper at ICLR 2020
0L ÔL Oz(t++1) az(li+1) 0; 0z(4,)
dz((++)) 0z(4,)
di+1 0z(1,)
(11)
F DERIVATION OF PARAMETER GRADIENTS IN CONTINUOUS CASE
In this section we derive the gradient of parameters in an neural-ODE model from optimization perspective. Then we extend from continuous cases to discrete cases.
Notations With the same notations in the main paper, we use =(1) to denote hidden states at time L. Denote parameters as 0, and input as v, target as y, and predicted output as y. Denote the loss Jú y). Denote the integration time as 0) to T.
Problem setup The continuous model is defined follow an ODE:
dz(t) = (=((), 0), s.t. =(0) =
(12)
dt
We assume f is differentiable, since f is represented by neural network our case. The forward pass is defined as:
9 = =T) /'¹ f(x(t),t,0)dt
(13)
The loss function defined as:
J(..)) = J(=(T),))
(14)
We formulate the training process as optimization problem:
1
N
Jür. vi) s.t. dz(t) = f(e(t),t, 2,( = dt
argming
(15)
N
1=1
For simplicity, Eq. 15 only considers one ODE block. In the case multiple blocks, 2(T) is the input to the next ODE block. As long as we can derive dLoss and dLoss when dLoss given, the d=(0)
de same analysis here can be applied to the case with chain of ODE blocks.
da(T)
Lagrangian Multiplier Method We the Lagrangian Multiplier Method to solve the problem defined in Eq. 15 For simplicity, only consider one example (can be easily extended to multiple examples cases), the Lagrangian is
{ dz(l) dt
I. J=(T()
X(01
((2(1),,
(16)
Karush-Kuhn Kuhh-Tucker (KKT) conditions are necessary conditions for an solution to be optimal. In the following sections start from the KKT condition and derive our results.
Derivative w.r.t. At optimal point, we have the derivative from calculus of variation.
8L 5λ
0. Note that À is a function of I, we derive
Consider a cotninuous and differentiable perturbation A(t) on X(t), and scalar L now becomes function e. E.
((c) [(=(0) S. ((=(1),,,0))u) [ (A(t) e((i)) dz(()
dt f(=(t),t,0)ddr
(17)
It's easy to check the conditions for Leibniz integral rule, and we can switch integral and differenti- ation, thus:
dL
/ de Jo
X(1 dz(l) 1(=(1),4.))l
(18)
dt
dl At optimal A(t), de |e=0 = 0 for all continuous differenniablee X(t).
Therefore,
dz(t)
dt - f(x(t),t,)) = o, E (0,T)
(19)
16

---

Under review as a conference paper at ICLR 2020
Derivative w.rf
Consider perturbation z(t) 2(t), with scale With similar analysis:
[ x(t) dz(() + cz(l)
- J
f(=(t)++ + (
(20)
di
Take derivative w.n. it's easy to check conditions for Leibniz integral rule are satisfied, when and ztt) are Lipschitz continuous differentiable functions:
(1) f(x(t),t, (, Lebesgue-integrrable function for each 2(t) E R since we use a neural network to represent f, which is continuous and differentiable almost everywhere.
(2) for almost 0, (f(x(t)..00) exists for almost x Rd dz(()
(3)
0f(a)),1.)) is bounded by g(0) for all z(t) for almost all 0. (z(t)
Then we calculate dLie) note that we can switch integral and derivative:
dL
0J (T) de
L' X(tl dz(t) cz(t)
de -=
-f(((t) + t,
(21)
(2(
dt
0J 2T) [/ T X(t) dz(l) af(=(1), 1, 0)
z(t))dt
(22)
0z(TT)
dt
0z(t)
aJ =TT) + /'' (2(1)
p d=(l) d2(1) dA(1) =(t) 2(1) 02(t)
05(=(1),,,0
+ dt =(1) dt
(())dt
(z(
dt
(23)
AJ =(T) + x()=((0)
T =(1) dt
dx(1)
(S(=())
+ ((1)
del
(24)
0z(T))
Oz(t)
0J
T
2(t)( dx(t)
X(t) 0f(z(t),t,
2(T) X(T)2(T) x(0)=(0)
dt (25)
(x(TT)
dz(t)
0J
x(t] dx(t) di
(f(z(t).t,
- = (az(T)
+ x(t)
dt
(26)
Oz(l)
Since the initial condition =00) is given, perturbation z(0) at is 0, then we have:
de l- = ( (xx(T) + ((T))²(T) / 2(t)| dx(t) de
dL
0J
af(z(1), L, dt =
dt + A(t)
(27)
0z(t)
for any 2(t) s.t. z(0) 0 and 2t) differentiable.
The solution is:
aJ
+ A(T) =0
(28)
dz(T)
dX(t)
0f(=(1), =0 Vt E (0, dt + A(t) dz(t)
(29)
Derivative w.r. 0 From Eq. 16,
dI.
= ['' T 0f(=(1),t,0) 1, 00
d0 = A(t)
dt
(30)
To up, first solve the ODE forward-in time with Eq. 19, then determine the boundary condition by Eq. 28, then solve the ODE backward with Eq. 29, and finally calculate the gradient with Eq. 30. In fact corresponds to the negative adjoint.
17

---

Under review as a conference paper at ICLR 2020
From continuous to discrete case To derive corresponding results in discrete cases, we need to replace all integration with finite sum.
In discrete cases, the ODE condition turns into:
2i+1 = f(i,,ti;
(31)
t+ t,
from Eq. 31, we can get:
öL
aL
0z++1 ÖL
Of(zi, ti t1,
(1 +
(li+1 - 1:))
(32)
0z:
0z++1
Oz,
0zit1
Ozi
Re-arranging terms we have:
0L
0L
0L
0f af(z,t
|//trr1 - t.]
(33)
0z++1
Ozi
0z++1
which is the discrete version of Eq. 29. Which also corresponds to our analysis in Eq. 10 and 11.
18


Reviews:
[{"review_id": "ryxO66ok5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposed a deep model called graph-ODE (GODE), which extends the continuous deep model, neural ODE [1], to graph structured data. Two methods of computing the gradient are proposed, one is the adjoint method proposed in [1] which is memory-efficient but not perfectly accurate, and the other method is to discretize the ODE and compute an accurate gradient, which is also memory-efficient but relies on an invertible architecture.\n\nIn general, this paper contains many interesting thoughts, but to me, it seems these ideas are not new and have been proposed before[1,2,3,4]. I could not find a strong contribution of this paper. \n\n- - - about the ODE stability issue\n\nAmong invertible deep models, the advantage of ODE-based continuous models [1] is: there is *no restriction* on the form of f. The drawback is the computed gradient has an error, depending on discretization step size and stability. This paper pointed out the stability problem (which is also discussed in [2,3]), but do not provide a solution in the domain of continuous deep models. \n\nInstead, the solution they provided is to use a discretized version and compute the gradient accurately. Then it becomes a standard invertible DL model with discrete layers, where the invertible building blocks have a specific *restricted form*. The 'adjoint method with discrete-time' in Eq (10) is the same as the chain rule, which has also be pointed out in [4]. To this point, I think GODE is in the class of discrete invertible DL models trained by gradient descent. I think it less related to continuous models, except the step size can be adaptive in the forward pass.\n\n- - - about the invertible building block\n\nThe proposed invertible building block replaces 'sum' in [5] by a function \\psi. This is not novel enough to serve as a contribution.\n\n- - - comparison to graph neural network\n\nI think it is interesting to apply ODE techniques or other invertible architectures to graph-structured data, for which I didn't see similar works before and could be a contribution of this paper. However, for the experimental results shown in table 3 and 4, the improvement is really small. A stronger result is needed to demonstrate the advantages.\n\n[1] Chen, Tian Qi, et al. \"Neural ordinary differential equations.\" Advances in neural information processing systems. 2018.\n[2] Chang, Bo, et al. \"Reversible architectures for arbitrarily deep residual neural networks.\" Thirty-Second AAAI Conference on Artificial Intelligence. 2018.\n[3] Behrmann, Jens, et al. \"Invertible Residual Networks.\" International Conference on Machine Learning. 2019.\n[4] Li, Qianxiao, et al. \"Maximum principle based algorithms for deep learning.\" The Journal of Machine Learning Research 18.1 (2017): 5998-6026.\n[5] Gomez, Aidan N., et al. \"The reversible residual network: Backpropagation without storing activations.\" Advances in neural information processing systems. 2017.\n\n\n\n-------------after reading the response\n\nI'd like to thank the authors for their explanations.\nHowever, the authors' explanation of the benefit of transforming the invertible building block into an ODE model is still not convincing to me.\n\nThe authors explained that ODE solutions can represent highly nonlinear functions. However, discrete NN also represents highly nonlinear functions (e.g. with Relu activation, they are *piecewise* linear, but they are highly nonlinear)! From my point of view, their difference is that ODE model is more smooth. However, the benefit of using a smoother model is still unclear. For the example that the authors provided, $\\sin x$, why being able to represent that kind of function is an advantage for the graph classification problem? Why is this a good model bias? I think the authors' responses are still not convincing enough, so I choose to retain the score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Syg40shatr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThe authors discussed that most graph NNs to date considered discrete layers and hence are difficult to model diffusion processes on graphs. This paper proposed the Neural ODE on a graph, termed with a graph ODE, to tackle this problem. The authors gave a sufficient condition under which the adjoint method gets instable and pointed out potential issues of training Neural ODEs using it. To overcome the instability issue, the author proposed to backpropagate errors directly at discretized points. Since the naive implementation of the direct method is memory-consuming, the authors used invertible blocks as building blocks of graph ODEs, which do not store the intermediate activations for backward propagation. Finally, the authors conducted empirical studies to see the effectiveness of the proposed method.\n\n\nDecision\n\nI recommend rejecting the paper weakly because I think the extension of Neural ODEs to graphs is straightforward and that the empirical study is not strong enough to compensate for the weakness of the novelty.\nTheoretical justification of numerical instability of Neural ODEs (Proposition 1) and its empirical verification (Section 5.4) give new insights for understanding Neural ODEs. However, if I understand correctly, the formulation of graph ODEs do not use the internal structures of graph NNs, even the fact that the underlying neural network is a graph NN. Therefore, I think the extension from Neural ODEs to graphs is a bit too straightforward. The authors proposed a method which improves the stability and memory-efficiency of training. We can apply this method to general Neural ODEs, too. In addition, we can attribute the idea of using invertible blocks to existing works (Gomez et al., 2017). Finally, regarding the empirical performance of graph ODEs, the performance improvement from existing GNNs is within the standard deviations. Therefore, I think the empirical result is not sufficiently strong to justify the novelty of applying Neural ODEs to graphs. Taking these things into account, although the authors gave a new result on Neural ODEs, I think the contribution is limited from the viewpoint of the study of graph NNs.\n\n\nSuggestion\n\n- As I wrote in the Decision section, the theoretical results are not restricted to graph ODEs but valid for general neural ODEs. Therefore, I think the authors do not have to restrict the application areas to graph ODEs. The possible direction of the paper is to further analysis of training neural ODEs (e.g., instability). On the other hand, if the authors are interested in the extension of neural ODEs to graphs, I expect a more detailed relationship between the neural ODEs framework and underlying GNNs. For example, I am curious how the topological information of graphs affects the graph ODEs via spectral-type graph convolution operations and what is the relationship to the oversmoothing phenomena (Li et al., 2018).\n- Since Theorem 1 is applicable not only graph ODEs but also Neural ODEs, it implies that ordinal Neural ODEs are also vulnerable to the instability. The experiments in Dupont (2019), which this paper referenced, pointed out the instability of Neural ODEs. I am wondering the proposed method can enhance the training of neural ODEs, too.\n\n[Li et al., 2018] Li, Qimai, Zhichao Han, and Xiao-Ming Wu. \"Deeper insights into graph convolutional networks for semi-supervised learning.\" Thirty-Second AAAI Conference on Artificial Intelligence. 2018.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJe4NPehKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:  This work extends Neural ODE to graph networks and compares the continuous adjoint method with propagation through the ODE solver.\n\nThe paper addresses an interesting and important problem and it is well-written in general.\nTo determine the significance of this work, I have two questions:\n\nQuestion: \n1. What is the major difference between the original Neural ODE and the Graph Neural ODE? \nFor example, In graph networks, each node’s representation may depend on its neighbor nodes. Will this impact the way you formulate the adjoints or compute the derivative?\n\n2. It seems in Mechanical engineering, various adjoint methods such as Discrete adjoint (e.g. [1])  has been studied.\nHow does the direct propagation through solver related to the these Discrete adjoint methods?\n\nSome minor comments for experiments:\nThe authors have 10 runs and take the best one. How about the average? which maybe a better indicator for stability.\nHow is the runtime comparing normal NN, adjoint, and direct propagation. Runtime has been a major disadvantage for Neural ODE.\n\nDecision:\nOverall, the novelty seems somewhat incremental, but I still feel the work is concrete and meaningful. I vote for weak accept.\nLooking forward to the code.\n\n[1] A Discrete Adjoint-Based Approach for Optimization Problems on Three-Dimensional Unstructured Meshes. Dimitri J. Mavriplis", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a few ideas to potentially improve the performance of neural ODEs on graph networks.  However, the reviewers disagreed about the motivations for the proposed modifications.  Specifically, it's not clear that neural ODEs provide a more advantageous parameterization in this setting than standard discrete networks.

It's also not clear at all why the authors are discussion graph neural networks in particular, as all of their proposed changes would apply to all types of network.

Another major problem I had with this paper was the assertion that the running the original system backwards leads to large numerical error.  This is a plausible claim, but it was never verified.  It's extremely easy to check (e.g. by comparing the reconstructed initial state at t0 with the true original state at t0, or by comparing gradients computed by different methods).  It's also not clear if the authors enforced the constraints on their dynamics function needed to ensure that a unique solution exists in the first place.
Decision: Reject