Anti-Symmetric DGN: a stable architecture for Deep Graph Networks
Authors: Alessio Gravina
Davide Bacciu
Claudio Gallicchio
Venue: ICLR 2023 poster (2023)

Abstract: Deep Graph Networks (DGNs) currently dominate the research landscape of learning from graphs, due to their efficiency and ability to implement an adaptive message-passing scheme between the nodes. However, DGNs are typically limited in their ability to propagate and preserve long-term dependencies between nodes, i.e., they suffer from the over-squashing phenomena. As a result, 
we can expect them to under-perform, since different problems require to capture interactions at different (and possibly large) radii in order to be effectively solved. In this work, we present Anti-Symmetric Deep Graph Networks (A-DGNs), a framework for stable and non-dissipative DGN design, conceived through the lens of ordinary differential equations. We give theoretical proof that our method is stable and non-dissipative, leading to two key results: long-range information between nodes is preserved, and no gradient vanishing or explosion occurs in training. We empirically validate the proposed approach on several graph benchmarks, showing that A-DGN yields to improved performance and enables to learn effectively even when dozens of layers are used.

Published as a conference paper at ICLR 2023
ANTI-SYMMENT DGN: A STABLE ARCHITECTURE FOR DEEP GRAPH NETWORKS
Alessio Gravina
Davide Bacciu University of Pisa
University of Pisa
alessio. www.siii.....iiaad.....o unipi it
davide weeeeeaacccuuiggpeee it
Claudio Gallicchio
University of Pisa
claudio. www.iichhoouniipi.ccooo it
ABSTRACT
Deep Graph Networks (DGNs) currently dominate the research landscape of learning from graphs, due to their efficiency and ability to implement an adap- live message-passing scheme between the nodes. However, DGNs are typically limited in their ability to propagate and preserve long-term dependencies between nodes, i.e., they suffer from the over-squashin phenomena. This reduces their effectiveness, since predictive problems may require to capture interactions at dif- ferent, and possibly large, radii in order to be effectively solved. In this work, we present Anti-Symmetric Deep Graph Networks (A-DGNs), framework for stable and non-dissipative DGN design, conceived through the lens ordinary differential equations. We give theoretical proof that our method is stable and non-dissipative, leading to two key results: long-range information between nodes is preserved, and gradient vanishing explosion occurs in training. We em- pirically validate the proposed approach on several graph benchmarks, showing that A-DGN leads improved performance and enables to learn effectively even when dozens of layers are used.
INTRODUCTION
Representation learning for graphs has become one of the most prominent fields in machine learn- ing. Such popularity derives from the ubiquitousness of graphs. Indeed, graphs are an extremely powerful tool to represent systems of relations and interactions and are extensively employed in many domains (Battaglia et al.) 2016 Gilmer et al., 2017 Zitnik et al.) 2018, Monti et al. 2019 Derrow-Pinion et al.) 2021). For example, they can model social networks, molecular structures, protein-proteie interaction networks, recommender systems, and traffic networks.
The primary challenge in this field is how capture and encode structural information in the learning model. Common methods used in representation learning for graphs usually employ Deep Graph Networks (DGNs) (Baceiu et al.) 2020 Wu et al. 2021). DGNs are family of learning models that learn a mapping function that compresses the complex relational information encoded in graph into an information-rich feature vector that reflects both the topological and the label information in the original graph. As widely popular with neural networks, also DGNs consists of multiple layers. Each of them updates the node representations by aggregating previous node states and their neighbors, following a message passing paradigm. However, in some problems, the exploitation of local interactions between nodes is not enough to learn representative embeddings. In this scenario, it is often the case that the DGN needs to capture information concerning interactions between nodes that are far away in the graph, i.e., by stacking multiple layers. A specific predictive problem typically needs to consider a specific range of node interactions in order to be effectively solved, hence requiring a specific number (possibly large) of DGN layers.
"Corresponding author.

---

Published as a conference paper at ICLR 2023
Despite the progress made in recent years in the field, many of the proposed methods suffer from the over-squashing problem (Alon & Yahav] (021) when the number of layers increases. Specifi- cally, when increasing the number of layers cater for longer-range interactions, one observes an excessive amplification or an annihilation of the information being routed to the node by the mes- sage passing process update its fixed length encoding. As such, over-squashing prevents DGNs to learn long-range information.
In this work, we present Anti-Symmetric Deep Graph Network (A-DGN), framework for effective long-term propagation of information in DGN architectures designed through the lens of ordinary differential equations (ODEs). Leveraging the connections between ODEs and deep neural archi- tectures. we provide theoretical conditions for realizing a stable and dissipatee ODE system on graphs through the use of anti-symmetrie weight matrices. The formulation of the A-DGN layer then results from the forward Fuler discretization of the achieved graph ODE. Thanks to the prop- erties enforced on the ODE, our framework preserves the long-term dependencies between nodes as well as prevents from gradient explosion vanishing. Interestingly, our analysis also paves the way for rethinking the formulation of standard DGNs as discrete versions of non-dissipative and stable ODEs graphs.
The key contributions of this work can be summarized as follows:
We introduce A- A-DGN, a novel design scheme for deep graph networks stemming from an ODE formulation. Stability and non-dissipation are the main properties that characterize our method, allowing the preservation of long-term dependencies in the information flow.
We theoretically prove that the employed ODE on graphs has stable and non-dissipative behavior. Such result leads to the absence of exploding and vanishing gradient problems during training, typical of unstable and lossy systems.
We conduct extensive experiments demonstrate the benefits of our method. A-DGN can outperform classical DGNs over several datasets even when dozens of layers are used.
The rest of this paper is organized as follows. We introduce the A-DGN framework in Section by theoretically proving its properties. In Section 3, we give an overview of the related work in the field of representation learning for graphs and continuous dynamic models. Afterwards, we provide the experimental assessment of our method in Section 4. Finally, Section 5 concludes the paper.
2 SYMI-SYMMETRIC DEEP GRAPH NETWORK
Recent advancements in the field of representation learning propose to treat neural network archi- tectures as an ensemble of continuous (rather than discrete) layers, thereby drawing connections be- tween deep neural networks and ordinary differential equations (ODEs) (Haber & Ruthotto [017]] Chen et al.) 2018). This connection can be pushed up to neural processing of graphs as introduced graph structure.
in (Poli et al. 2019), by making a suitable ODE define the computation
We focus on static graphs, i.e., on structures described by G = (V, E), with V and & respectively denoting the fixed sets of nodes and edges. For each node u E V we consider state x., (t) Rd. which provides a representation of the node u at time t. We can then define a Cauchy problem on graphs in terms of the following node-wise defined ODE:
(x,, (t),, Öt
(1)
for time t [0, 7]. and subject to the initial condition (0) xΩ E Rd. The dynamies of node's ' representations is described by the function fg : Rd - Rdd while the initial condition x,,(), (0) can be interpreted as the initial configuration of the node's 's information, hence as the input for our computational model. As consequence, the ODE defined in Equation be seen as a continuous information processing system over the graph, which starting from the input configuration x,, x., computes the final node's representation (i.e., embedding) x., (T). Notice that this process shares similarities with standard DGNs, in what it computes nodes' states that can be used as an embedded representation of the graph and then used to feed readout layer in downstream task on graphs. The top of Figure [ visually summarizes this concept, showing how nodes evolve following a specific graph ODE in the time span between 0 and terminal time T > 0.
2

---

Published as a conference paper at ICLR 2023
dl
t= time
initial conditiion (kmput)
final embeddinn
ODB
Io(xa(0)
(x)
(2) layers
DGN
x
W W
1
%
A-DGN
Figure 1: A high level overview of our proposed framework, summarizing the involved concepts of ODE a graph, its discretization as layers of DGN, and the resulting node update of Anti- symmetric DGN. At the top, span between and T > 0, Cauchy problem on graphs. The node-wise ODE fo determines the evolution of the states x., (t), while the initial conditions (0) play the role of input information. In the middle, the discretized solution of the graph ODE is interpreted as a succession of DGN layers in neural network architecture. The node state x,, computed at layer & is updated iteratively by leveraging its neighborhood and self representations at the previous layer sketches the computation performed by a layer in an Anti-Symmetric DGN (in Equation resulting from the forward Euler discretization stable and non-dissipative ODE on graphs. The more layers, the more long-range dependencies included in the final nodes' representations.
illustrated the continuous processing of nodes' states the time
The bottom part
Since for most ODEs it is impractical to compute analytical solution, a common approach relies on finding an approximate one through numerical discretization procedure (such as the forward Euler method). In this way, the time variable is discretized and the ODE solution is computed by the successive application of an iterated map that operates on the discrete set of points between 0 and T' with step size O. Crucially, as already observed for feed-forward and recurrent neural models (Haber & Ruthotto 2017, Chang et al. (219),, each step of the ODE discretization process can be equated one layer of a DGN network. The whole neural architecture contains as many layers as the integration steps in the numerical method (i.e., L T/c), and each layer & { 1, ..., L computes nodes' states x which approximates (, E). This process summarized visually in the middle of Figure
Leveraging the concept of graph neural ODEs (Poli et al., 2019). in this paper we perform a further step by reformulating DGN as solution to stable and non-dissipative Cauchy problem over a graph. The main goal of our work is therefore achieving preservation of long-range information between nodes, while laying down the conditions that prevent gradient vanishing explosion. In- spired by the works on stable deep architectures that discretize ODE solutions (Haber & Ruthotto 2017 Chang al. 2019), do by first deriving conditions under which the graph ODE is constrained to the desired stable and non-dissipative behavior.
Since are dealing with static graphs, instantiate Equation f for node follows:
ix,(() = Øt a (Wxx,(t) 4(X(t), + b,),
(2)
where is monotonically non-decreasing activation function, W, ddxd and b, E Rd are, respectively, a weight matrix and a bias vector that contain the trainable parameters the system. We denote by & (((()). the aggregation function for the states of the nodes in the neighborhood of We refer to X(t) RDixd as the node feature matrix of the whole graph, with d the number of available features. For simplicity, in the following we keep W, and b, constant over time, hence dropping the subscript in the notation.
3

---

the initial conditions Published as a conference paper at ICLR 2023
Well pelledossssess and stability essential concepts when designing DGNs as solutions to Cauchy problems, both relying on the continuous dependence of the solution from initial conditions. An ill- ill-posed unstable system, even if potentially yielding low training error, is likely to lead to a poor generalization error on perturbed data. On the other hand, the solution of a Cauchy problem is stable if the long-term behavior of the system does not depend significantly (Ascher et al.) 1995). In our case, where the ODE defines a message passing diffusion over a graph, our intuition is that stable encoding system will be robust perturbations in the input nodes information. Hence, the state representations will change smoothly with the input, resulting in non-exploding forward propagation and better generalization. This intuition is formalized by the Definition (see Appendix A). whose idea is that a small perturbation of size 5 of the initial state (i.e., the node input features) results in a perturbation on the subsequent states that at most w. As known from the stability theory of autonomous systems (Ascher et al. 1995), this condition is met when the maximum real part of the Jacobian's eigenvalues of fg is smaller or equal than 0, i.c., max Re(A, (J(())) I 0, vt O. Re(
Although stability is a necessary condition for successful learning, alone not suffi- cient capture long-term dependencies. As it is discussed in |Haber & Ruthotto (2017), if max;=1....d { < 0 the result is a lossy system subject to catastrophic forgetting dur- ing propagation. Thus, in the graph domain, this means that only local neighborhood information is preserved by the system, while long-range dependencies among nodes are forgotten. If no long- range information preserved. then likely that the DGN will underperform, since it will not be able to reach the minimum radius of inter-nodes interactions needed to effectively solve the task.
Therefore, we can design an ODE for graphs which is stable and non-dissipative (see Definition in Appendix (A] that leads to well-posed learning, when the criterion that guarantees stability is met and the Jacobian's 's eigenvalues of fg are nearly zero. Under this condition, the forward propagation produces at most moderate amplification or shrinking of the input, which enables to preserve long- term dependencies the node states. During training, the backward propagation needed to compute the gradient of the loss / (xx,.)) (1) will have the same properties of the forward propagation. As such, no gradient vanish nor explosion is expected to occur. More formally:
time, the forward and back- ward propagations of the ODE in Equation D are stable and non non-dissipative if
Proposition 1. Assuming that (t) does not change significantly
(e())(J(t)) = O, = 1,....d
(3)
see the proof in Appendix B
A simple way to impose the condition in Equation 3 is to use anti-symmetric weight matrix in Equation 2 Under this assumption, we can rewrite Equation 2 as follows:
(x,,()) ((W - ((W-W))x.(1)) + $ (X()).N.) + b)
(4)
Öt
where (W- -WT) Rdxd is the anti-symmetric weight matrix. The next Proposition] ensures that
when the aggregation function & (X((),,Na)) is independent of (1) (see for example Equation o the Jacobian of the resulting ODE has imaginary eigenvalues, hence it is stable and non-dissipative according to Proposition 1 As discussed in Appendix D. whenever ((((),,N,, includes x,, (t) in its definition (see for example Equation]] ()) the eigenvalues of the resulting Jacobian are still bounded in small neighborhood around the imaginary axis.
Proposition 2. Provided that (X(t), ) is independent of xu (t), the Jacobian matrix of the ODE in Equation 4 has purely imaginary eigenvalues, i.e.
Rc()x(((t)) -0, 1,
Therefore the ODE in Equation 4 is stable and non-dissipative.
See proof in Appendix
We now proceed to discretize the ODE in Equation 4 by means of the forward Euler's method. To preserve stability of the discretized system we add a diffusion term to Equation 4 yielding the
A matrix A E Rxdd anti-symmetric (i.c., skww-symmerrii) if AT - The interested reader is referred to (Ascher & Petzold 1998) for an in-depth analysis the stability of the forward Fuler method.
4

---

Published as a conference paper at ICLR 2023
following node state update equation:
x ca (WW-W) -I)x D(x ,Na) +b)
(5)
where I is the identity matrix, ? is hyper-parameter that regulates the strength of the diffusion, and e is the discretization step. By building on the relationship between the discretization and the DGN layers, we have introduced x as the state of node layer i.e. the discretization of state at time t =
Now, both ODE and its Euler discretization are stable and non-dissipative. We refer to the frame- work defined by Equation Anti-symmelric Deep Graph Network (A-DGN), whose state update process is schematically illustrated in the bottom of Figure [I Notice that having assumed the pa- rameters of the ODE constant in time, A-DGN can also be interpreted recursive DGN with weight sharing between layers.
We recall that (x can be any function that aggregates nodes (and edges) information. Therefore, the general formulation of ((X'-1,,, .Na) in A-DGN allows casting all standard DGNs through in their non-dissipative, stable and well-posed version. As result, A-DGN can be im- plemented leveraging the aggregation function that is more adequate for the specific task, while allowing to preserve long-range relationships in the graph. As demonstration of this, in Section we explore two neighborhood aggregation functions, that are
D (Nw = Σ Vx
(6)
JEN
(which is also employed in Morris al. (2019) and the classical GCN aggregation
((X 1-1 (N.)) V
Σ
Vddd. xf-1,
JEN..fu)
where V is the weight matrix, d, and dy are, respectively, the degrees of nodes and Finally, although we designed A-DGN with weight sharing in mind (for ease of presentation). a more general version of the framework, with layer-dependent weights W -(W?)", is possible
RELATED WORK
Deep Graph Network Nowadays, most of the DGNs typically relies on the concepts introduced by the Message Passing Neural Network (MPNN) (Gilmer et al. (017), which is general frame- work based on the message passing paradigm. The MPNN updates the representation for a node at layer as
X = ox
Σ O ,x, f-1 e.v))
(8)
JEN.
where du and dM are respectively the update and message functions. Hence, the role of the message function is to compute the message for each node, and then dispatch it among the neighbors. On the other hand, the update function has the role collecting the incoming messages and update the node state. A typical implementation of the MPNN model is x Wx EjeN, MLP(Ce.) -x/->+b, where euv E Idde is the edge feature vector between node and v. Thus, by relaxing the concepts of stability and non-dissipation from our framework, MPNN becomes specific discretization instance of A-DGN.
Depending the definition of the update and message functions, it is possible to derive variety of DGNs that mainly differ on the neighbor aggregation scheme (Kipf & Welling 2017
Veličkovic
et. 2018 Hamilton et al. 2017 Xu et al.] 2019 Defferrard et al. 2016 all these methods focus on presenting new and effective functions without questioning the stability and non-dissipative behavior of the final network. As result, most of these DGNs are usually not
al. 2020 However,
'The dynamical properties discussed in this section are in fact still true even in the case of time varying W in Equation 2 provided that max.=.....d Re(A,( (J(()) 5 0 and ((t) changes sufficiently slow over time (see
Ascher 1995 Haber & Ruthotto 2017))
5

---

Published as a conference paper at ICLR 2023
able to capture long-term interactions. Indeed, only few layers can be employed without falling into the werrsqqushing phenomenon, as it is discussed by Alon & Yahav (202I).
Since the previous methods are all specific cases of MPNN, they are all instances of the discretized and unconstrained version of A-DGN. Moreover, a proper design of d (x - .Nw) in A-DGN allows rethinking the discussed DGNs through the lens of non-dissipative and stable ODEs. Ming Chen et al. (200)). Zhou et al. (202T) Ellasof et al. (2022) proposed three methods to alleviate over- smoothing, which is phenomenon where all node features become almost indistinguishable after few embedding updates. Similarly to the forward Euler discretization, the first method employs identity mapping. also exploits initial residual connections to ensure that the final representation of each node retains at least fraction of input. The second method proposes DGN that constrains the Dirichlet energy at each layer and leverages initial residual connections, while the latter tackles over-smoothing by aggregating random paths over the graph nodes. Thus, the novelty of our method still preserved since A-DGN defines a map between DGNs and stable and non-dissipative graph ODEs to preserve long-range dependencies between nodes.
Continuous Dynamic Models Chen et al. 2018) introduce NeuralODE, a new family of neu- ral network models that parametrizes the continuous dynamics of recurrent neural networks using ordinary differential equations. Similarly. Chang et al. (2019) and Gallicchio (2022) draw a connec- tion between ODEs and, respectively, RNNs and Reservoir Computing architectures. Both methods focus on the stability of the solution and the employed numerical method.
Inspired by the NeuralODE approach, Poli et al. (2019) develops a DGN defined as a continuum of layers. In such a work, the authors focus on building the connection between ODEs and DGNs. We extend their work to include stability and non-dissipation. which are fundamental properties to preserve long-term dependencies between nodes and prevent gradient explosion or vanishing during training. Thus, by relaxing these two properties from our framework, the work by Poli] eet al. (2019) becomes specific instance of A-DGN. [Chmmberlain et al. (2021) propose GRAND an architecture to learn graph diffusion as a partial derivative equation (PDE). Differently from GRAND, our framework designs an architecture that is theoretically non-dissipative and free from gradient vanishing or explosion. DGC (Wang et al.) (021) and SGC (Wu et
al.] (019) propose linear models that propagate node information as the discretization of the graph heat equation, (x(()
- (I), without learning. Specifically, DGC mainly focus on exploring the influence of the step size in the Fuler discretization method. [llisoof al. (202T) and |usch al. (2022) present two methods to preserve the energy of the system, i.c., they mitigate over-smoothing, instead of preserving long-range information between nodes. Differently from our method, which employs first-order ODE, the former leverages the conservative mapping defined by hyperbolic PDEs, while the latter defined as second-order ODEs that preserve the Dirichlet energy. In general, this testifies that non-dissipation in graph ODEs is an important property to pursue, not only when preserving long-range dependencies. However, to the best of our knowledge, we are the first to propose a non-dissipative graph ODE to effectively propagate the information on the graph structure.
4 EXPERIMENTS
In this section, we discuss the empirical assessment of our method. Specifically, we show the ef- ficacy of preserving long-range information between nodes and mitigating the over-squashing by evaluating framework on graph property prediction tasks where we predict single source shortest path, node eccentricity, and graph diameter (see Section 4.1). With the same purpose, we report the experiments on the TreeNeeighbuurMMach problem (Alon & Yahav) (02I) in Appendix H.2 More- over, we assess the performance of the proposed A-DGN approach on classical graph homophilic (see Section 4.2) and heterophilic (see Appendix [.TI) benchmarks. The performance of A-DGN is assessed against DGN variants from the literature. We carried the experiments on Dell server with 4 Nvidia GPUs A100. We release openly the code implementing our methodology and reproducing our empirical analysis at https:: /ttp:/gitttuuu com
tttoo//ravae gravi innvvinn//nnn Ant SeiinntiSyymmmme Symmet r cDGN
4.1 GRAPH PROPERTY PREDICTION
Setup For the graph property prediction task, we considered three datasets extracted from the work of Corso et al. (2020). The analysis consists of classical graph theory tasks on undirected

---

Published as a conference paper at ICLR 2023
unweighted randomly generated graphs sampled from wide variety of distributions. Specifically, we considered two node level tasks and one graph level task, which are single source shortest path (SSSP), node eccentricity, and graph diameter. Such tasks require capturing long-term dependencies in order to be solved, thus mitigating the over-squashing phenomenon. Indeed, in the SSSP task, we computing the shortest paths between given node and all other nodes in the graph. Thus, it is fundamental to propagate not only the information of the direct neighborhood of u, but also the information of nodes which are extremely far from it. Similarly, for diameter and eccentricity.
We employed the same seed and generator as Corso et al. 2020 to generate the datasets, but we considered graphs with 25 to 35 nodes, instead of 15-25 nodes in the original work, to increase the task complexity and lengthen long-range dependencies required to solve the task. As in the original work, we used 5120 graphs as training set, 640 as validation set, and 1280 as test set.
We explored the performance of two versions of A-DGN, i.e., weight sharing and layer dependent weights. Moreover, we employed two instances of our method leveraging the two aggregation func- tions in Equation [ and 7
We will refer to the former as simple aggregation and to the latter as GCN-based aggregation. We compared our method with GCNII, two neuralODE-
models, i.e., GRAND and DGC, and the four most popular DGNs, i.e., GCN, GAT, GraphS and GIN.
We designed each model as a combination of three main components. The first is the encoder which maps the node input features into a latent hidden space; the second is the graph convolution (i.e., A-DGN or the DGN baseline); and the third is a readout that maps the output of the convolution into the output space. The encoder and the readout Multi-Layer Perceptrons that share the same architecture among all models in the experiments.
We performed appem-earaeeter tuning via grid search, optimizing the Mean Square Error (MSE). We trained the models using Adam optimizer for a maximum of 1500 epochs and early stopping with patience of 100 epochs on the validation error. For each model configuration, we performed training runs with different weight initialization and report the average of the results.
We report in Appendix the grid of hyper- pareamearaeterss exploited for this experiment. We observe that even if we do not directly explore in the hyper-parameter space the terminal time T in which the node evolution produces the best embeddings, that done indirectly by fixing the values of the step size e and the maximum number of layers L, since T = Le.
Results We present the results on the graph property prediction in Table T Specifically, we report (og))(MSE) as the evaluation metric. We observe that our method, A-DGN, outperforms all the DGNs employed in this experiment. Indeed, by employing GCN-based aggregation, we achieve an error score that is average 0.80 points better than the selected baselines. Notably, if we leverage the simple aggregation scheme, A-DGN increases the performance gap from the baselines. A-DGN with simple aggregation shows a decisive improvement with respect to baselines. Specifically, it achieves a performance that is 200% to 300% better than the best baseline in each task. Moreover, it is on average 3.6x faster that the baselines (see Table 7 in Appendix G).
We observe that the main challenge when predicting diameter, eccentricity, or SSSP is to leverage not only local information but also global graph information. Such knowledge can only be learned by exploring long-range dependencies. Indeed, the three tasks are extremely correlated. All of them require compute shortest paths in the graph. Thus, as for standard algorithmic solutions (e.g., Bell- man- Ford (Bellman) 1958). Dijkstra's algorithm (Dijkstral 1959)), more messages between nodes need to be exchanged in order to achieve accurate solutions. This suggests that A-DGN can better capture and exploit such information. Moreover, this indicates also that the simple aggregator is more effective than the GCN-based because the tasks are mainly based on counting distances. Thus, exploiting the information derived from the Laplacian operator is not helpful for solving this kind of algorithmic tasks.
4.2 GRAPH BENCHMARKS
Setup In the graph benchmark setting we consider five well-known graph datasets for node clas- sification, i..., PubMed (Namata et al. 2012);; coauthor graphs CS and Physics; and the Amazon co-purchasing graphs Computer and Photo from SShhur et al. (2018). Also for this class of ex- periments, we considered the same baselines and architectural choices for the graph property
7

---

Published as a conference paper at ICLR 2023
Table 1: Mean test set (og1)(MSF.) and std averaged over random weight initializations for each configuration. The lower the better. For each dataset we present the best performing variant of A- DGN, please refer to Apprendix for the complete results.
Diameter
SSSP
Eccentricity
GCN
0.7424:00.0466
0.949919. 10
0.8468==0.0028
GAT
0.8221::00052
0.6951=0.1499
0.7909=:0.0222
GraphSAGE
0.8645+-000401
0.2863-0..18
0.7863+0.0007
GIN
0,61311:0,0900
-054408=0.4193
0.95041100007
GCNII
0.5287
-1.1329-10.0335
0.7640-10.0355
DGC
0.6028 0050
-0,1483=0.0231
0.8261#0.0032
GRAND
0.6715=000490
-0.0942=0.3897
0.6602=0.1393
Our
-0.5455
-3.4020-0.1372
0,3046::0.1881 0.7177:+0.0345
Our(GCN)
0.2271+:00800
-L82888=00000
prediction task. However, in this experiment study only the version of A-DGN with weight sharing, since it achieve good performances with low training costs.
Within the aim accurately assess the generalization performance of the models, we randomly split the datasets into multiple train/validation/eess sets. Similarly to [Shchur et al. (2018), we use 20 labeled nodes per class as the training set, 30 nodes per class as the validation set, and the rest as the test set. We generate 5 random splits per dataset and 5 random weight initialization for each configuration in each split.
tuning via grid search, optimizing the accuracy score. We train for a maximum 10000 epochs to minimize the Cross-Entropy loss. We use an early stopping cri- terion that stops the training if the validation score does not improve for 50 epochs. We report in Appendix F the grid of hhpperpparametee explored for this experiment.
We perform
Results We present the results the graph benchmark in Table 2 Specifically, report the curacy as the evaluation metric. Even in this scenario, A-DGN outperforms the selected baselines, except in PubMed and Amazon Computers where GCNII slightly better than our method. benchmark, results that the GCN-based aggregation produces higher scores with respect to the sim- ple aggregation. Thus, additional local neighborhood features extracted from the graph Laplacian seem to strengthen the final predictions. It appears also that there is less benefit from including global information with respect to the graph property prediction scenario. As result, exploiting ex- tremely long-range dependencies do not strongly improve the performance the number of layers increases.
this
To demonstrate that approach performs well with many layers, show in Figure 2 how the number layers affects the accuracy score. Our model maintains or improves the performance as the number of layers increases. On the other hand, all the baselines obtain good scores only with one to two layers and most of them exhibit a strong performance degradation as the number of layers increases. Indeed, in the Coauthor CS dataset obtain that GraphSAGE, GAT, GCN and GIN lose 24.5% to 78.2% of accuracy. We observe that DGC does not degrade its performance since the convolution do not contain parameters.
Although extreme long-range dependencies do not produce the same boost as in the graph property prediction scenario. including more than 5-hop neighborhoods is fundamental to improve state- of-the-art performances. As clear from Figure [ this is not practical when standard DGNs are employed. On the other hand, A-DGN demonstrates that can capture and exploit such information without any performance drop.
5 CONCLUSION
In this paper, we have presented Anti-Symmetric Deep Graph Network (A-DGN), new framework for DGNs achieved from the study of ordinary differential equation (ODE) representing a continu- process of information diffusion on graphs. Unlike previous approaches, by imposing stability and conservative constraints to the ODE through the use of anti-symmetric weight matrices, the proposed framework is able learn and preserve long-range dependencies between nodes. The A-
8

---

Published as a conference paper at ICLR 2023
Table 2: Mean test accuracy and std in percent averaged 5 random trainn/allidaiion/esst splits
and 5 random weight initializations for each configuration in each split. The higher the better.
Coauthor
Coauthor
Amazon
Amazon
PubMed
CS
Physics
Computers
Photo
GCN
76.75+1.29 .229
90.34+0.31
92.80+00444
81.63+0.93
89.14=0.559
GAT
75.64.11.27
81.57.11002
89.2511..2
76.36.10.899
85.58:10.91
GraphSAGE
74,96+:1.69
89.93+0.799
92.47=0094
79.37
88 88.04+0.85
GIN
16.24+1.86
89.26-1.31
91.40+0.70
79.6410.72
87.69=1.16
GCNII
77.39-+1.36
91.16++0.28
92.97+00.00
82.72-+0.98
09.96-
DGC
66.71+2.55
85.84+00.0
82.95+1.20
66.44+0.63
76.13+00.01
GRAND
16.1811.56
89.20110.22
90.72:10.7
81.0910.70
89.05
Our
16,57=1100
91.35++.88
92.45++0.33
01783+0.75
88 1.18
Our(GCN)
76.82.10.86
91.71.10.43
93.27.10.62
82.35.10.89
90.52.10.40
PubMeed
Cosuther CS
Conithor Phydics
0.8
0.7
Accurary
0.6
0.6
Accracy
0.5
0.4
0.4
0.2
0.2
Amaza Compulers
Amazen Photo
0.8
Accuray
0.6
0.6
OEM GAT
CAuphSACE
0.2
DEC
GRAND
Figure 2:
The test accuracy with respect the number of layers all the graph benchmark datasets. From the top left to the bottom, we show: PubMed, Coauthor CS, Coauthor Physics, Amazon Computers, and Amazon Photo. The accuracy is averaged over random train/vliidttion/eest splits and 5 random weight initialization of the best configuration per split.
DGN layer formulation is the result of the forward Euler discretization of the corresponding Cauchy problem graphs. We theoretically prove that the differential equation corresponding to A-DGN is stable as well as non-dissipative. Consequently, typical problems of systems with unstable and lossy dynamics, e.g., no gradient explosion vanishing, do occur. Thanks its formulation, A-DGN can be used to reinterpret and extend any classical DGN as non non-dissipative and stable ODEs.
Our experimental analysis, on the one hand, shows that when capturing long-range dependencies is important for the task, our framework largely outperform standard DGNs, On the other hand, it indi- cates the general competitiveness of A-DGN on several graph benchmarks. Overall, A-DGN shows the ability to effectively explore long-range dependencies and leverage dozens of layers without any noticeable drop performance. For such reasons, we believe it can be step towards the mitigation of the over-squashing problem in DGNs.
The results of our experimental analysis and the comparison with state-of-the-ar methods suggest that the presented approach can be a starting point to mitigate also over-smoothing. Thus, we plan to accurately explore the consequences of our approach on over-smoothing as a future research direction. Looking ahead to other future developments, we plan to extend the analysis presented in this paper to study DGN architectures resulting from alternative discretization methods of the underlying graph ODE, e.g., using adaptive multi-step schemes (Ascher & Petzold 1998). Other future lines of investigation include extending the framework to dynamical graph structures, and evaluating its impact in the area of Reservoir Computing (Tanaka al. 2019).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research was partially supported by EMERGE, a project funded by EU Horizon research and innovation programme under GA No 101070918.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical im- plications. In International Conference on Learning Representations, 2021. URL https:
//openzeview. wtwp::/ww..e//.rmmmmaa--ooooo-..
U.M. Ascher, R.M.M. Mattheij, and R.D. Russell. Numerical solution of boundary value prob- lems for ordinary differential equations. Classics in applied mathematics. Society for Industrial and Applied Mathematics (SIAM), United States, unabridged, corr. republication. edition, 1995.
ISBN 1889871-35444
Uri M. Ascher and Linda R. Petzold. Computer Methods for Ordinary Differential Equations and Differential-Algeree Equations. Society for Industrial and Applied Mathematics, USA, 1st edition, 1998. ISBN 089871411 14125.
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 129:203 221, 2020. ISSN 0893-6080. doi:
https://doi.org/10..r htw.:/0000o.eeeeetee2...oooo 006. URLhtttss www. wwi. encedi rect. com/ sci cciiane//arrccee/11//33330303322
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
Friedrich L Bauer and Charles Fike. Norms and exclusion theorems. Numerische Mathematik, (1):137-141, 1960.
Richard Bellman. On routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learn ing. pp. 1407-1418. PMLR, 2021.
Bo Chang. Lili Meng, Eldad Haber, Lars Ruthotto, David Begert, Elliot Holtham. Reversible architectures for arbitrarily deep residual neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Bo Chang, Minmin Chen, Eldad Haber, and Ed Chi. AntisymmetricRNN:: A dynamical system view recurrent neural networks. In International Conference Learning Representations, 2019.
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud, Neural ordinary dif- ferential equations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL httppppp::ppppcpeissss.s.tto
neurip.....e..isp.. cttppppccc//aee//1////1ee pdd
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances Neural Information Processing Sys- tems, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. NIPS" 16, pp. 3844-3852, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838811
10

---

Published as a conference paper at ICLR 2023
Austin Derrow-Pinion Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, Peter W. Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez, Yujia Li, and Petar Velickovic. Eta prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, CIKM 221, pp. 3767-3776, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450384469, doi: 10.1145/3459377. 3481916. URL https:t/dti....ooo http://oo..rgg../o
3481916
Edsger. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
Moshe Eliasof, Eldad Haber, and Eran Treister. PDE-GCN: Novel architectures for graph neural networks motivated by partial differential equations. In A. Beygelzimer, Y. Dauphin, P. Liang, a.d Wortman Vaughan (eds.), Advances Neural Information Processing Systems, 2021. URL https://openreviie net
Moshe Eliasof, Eldad Haber, and Eran Treister. pathGCN: Learning general graph spatial operators from paths. In ICML, 2022.
Claudio Gallicchio. Euler state networks: Non-dissipative reservoir computing. arXiv preprint arXiv:2203.09388, 2022.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML'I7, pp. 1263-1272. JMLR.org. 2017.
Paul Glendinning. Stability, Instability and Chaos: An Introduction to the Theory of Nonlinear Differential Equations. Cambridge Texts in Applied Mathematics. Cambridge University Press, 1994. doi: 10.1017/CB0997001112222 1662299...
Eldad Haber and Lars Ruthotto. Stable architectures for deep neural networks. abs/1705.03341, 2017. URL httphtt:://artt //tppvv////xvv...//. http:/awwwww......aaaoooo http://b///1..0. 03341 03341
CoRR,
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Confer- ence on Learning Representations, 2020. URL https::t////ttt httpss://openreviee... wwwp:eevwwwweeeefffroeeeee nwt./orunffrf HJIWWJSFDH
A. R. Humphries and A. M. Stuart. Runge-kutta methods for dissipative and gradient dynamical systems. SIAM J. Numer Anal., 3155)11452-1485, oct 1994. ISSN 0036-1429, doi: 10.1137/ 0731075. URL
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Zhewei Wei Ming Chen, Bolin Ding Zengfeng Huang, and Yaliang Li. Simple and deep graph convolutional networks. 2020.
Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M. Bronstein. Fake news detection on social media using geometric deep learning. CoRR, abs/1902.06673, 2019.
URL Btlthttp///axxiv org/ abs/ 1902. 06673
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gau- rav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference Artificial Intelligence and Thirty-Fit First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Sym- posium Educational Advances in Artificial Intelligence, 19A1A1 19/EAAI'19, 1 AAAI
Press. 2019. ISBN 978 777757773599111 doi: 10.1609/aaai, 133001..3010144444303 URL https:
7/doi. .lw..org1100 1099/16009000 wtt.aaaa.......... 00331111.30166000 33014602
331111

---

Published as a conference paper at ICLR 2023
Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query-driver active sur- veying for collective classification. In Workshop on Mining and Learning with Graphs 2012. URL http://lings.. cs umd. www.basiliccccccca/a/aa/a. http:/ablication////a/... namata: : :m gl
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference Learning Representations, 2020.
URL httpps:///ppereeeiieet wet.:wiwwweeeeeeeee.ee......eeee sese:/oormmmdddiie /
Michael Poli, Stefano Massaroli, Junyoung Park, Atsushi Yamashita, Hajime Asama, and Jinkyoo
Park. Graph neural ordinary differential equations. arXiv preprint arXiv: 2019.
Konstantin Rusch, Benjamin P Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael M Bronstein. Graph-coupled oscillator networks. arXiv preprint arXiv:2202.02296, 2022.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, abs/181 1000868,, 2018. URL httpp://rxivz exq/abs/1ee 1abb/1811..0 05868
Gouhei Tanaka, Toshiyuki Yamane, Jean Benoit Héroux, Ryosho Nakane, Naoki Kanazawa, Seiji Takeda, Hidetoshi Numata, Daiju Nakano, and Akira Hirose. Recent advances in physical reser- voir computing:
A review. Neural Networks, 115:100-123, 2019.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- tional Conference on Learning Representations, 2022. URL
Forum? ddmm:11--UmmnR-2--1-
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
wwweeerrwwwweeeeeeeeeeeeeeeeeeee fortt//frum?? JXM iCCZ accepted as poster.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. CoRR, abs/2102.10739, 2021. URL https://arxt:
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Sim- plifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 09-15 Jun 2019. URL htttps://proceedings www..prees//vil wu/ wttps///////119.hmmmmll
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-22 24, 2021. doi: TT000//NNN.S..20..299777
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Or- leans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL Eorum? 2 -ineeddddryyyylnoe 6155km
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li,, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in neural information processing systems, 2021.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharnacy side effects with graph convolutional networks. Bioinformatics, 34(13)1457--466 06 2018. ISSN 1367-4803. doi: 10. 1001099/hooifoomaatic//yyy2 URL O0R
bty294
12

---

Published as a conference paper at ICLR 2023
A STABILITY AND DISSIPATIVITY DEFINITIONS
In the following, we define the condition in which the solution of the Cauchy problem in Equation is stable.
Definition 1. solution x. (t) of the ODE in Equation 2 with initial condition x, (O), is stable for
any w > O, there exists 6 > O such that any other solution x, of the ODE with initial condition
x, (0) satisfying (0) (0) S also satisfies (t) & (1) S w. for all t 2 O.
We now provide a definition of a dissipative system based on the one provided in Humphries & Stuari 1994).
Definition 2. Let define E S Id bounded set that contains any initial condition x. (0) the ODE in Equation 2 The system defined by the ODE in Equation is dissipative there is bounded set B where, for any E, exists 1* 2 0 such that { (x)(() (O) E E} C B for L 1*.
B PROOF OF PROPOSITION
Let us consider the ODE defined in Equation and analyze the sensitivity its solution the initial conditions. Following (Chang et al. 2019). we differentiate both sides of Equation 2 with respect to x, (0), obtaining:
d (xxx(1) ( J(t) (x, (0)
dt (xx
Assuming the Jacobian does not change significantly over time, we can apply results from au- tonomous differential equations (Glendinning 1994) and solve Equation 9 analytically as follows:
(t), (0)
(tA)*
e TT T(
(10)
where A is the diagonal matrix whose non-zero entries contain the eigenvalues of J, and T has the eigenvectors of J as columns. The qualitative behavior of āx,, (0), (0) is then determined by the real parts of the eigenvalues of J. When maxi=l....d (e():( > 0, small perturbation of the initial condition (i.e., a perturbation on the input graph) would cause an exponentially exploding difference in the nodes representations, and the system would be unstable. On the contrary, for max Re (R, (J())) < O, the term 0x,, (1) (1)/0x.(00) (0) would vanish exponentially fast over time, thereby making the nodes' representation insensitive to differences in the input graph. Accordingly, the system states x,,() (t) would asymptotically approach the same embeddings for all the possible initial conditions x,, (0), and the system would be dissipative. Notice that the effects of explosion and dissipation are progressively more evident for larger absolute values of max;=1,.... (t))). for 1.., then the magnitude of (xxtt)/x(0)) is constant over time, and the input graph information is effectively propagated through the successive transformations into the final nodes' representations. In this last case, the system hence both stable and non-dissipative.
If Re(A, (J()))
Let us now consider loss function C. and observe that its sensitivity to the initial condition (i.e., the input graph) 0C/Ox,, (0) is proportional to 0x,, (t) (O)) Hence, in light of the previous considerations, if Re (J())) the longest gradient chain that we can obtain during back-propagation. stays constant over time. The backward propagation is then stable and non-dissipative, and no gradient vanishing or explosion can occur during training.
0 for i 1,... d, then the magnitude of OC/Ox,, (0), which is
C PROOF OF PROPOSITION 2
Under the assumption that the aggregation function ((X(t), does not include term that de- pends on (t) itself (see Equation 6 for an example), the Jacobian matrix of Equation 4 is given by:
(11) Following (Chang et al. 2019 2018), we can see the right-hand side of Equation II as the result of a matrix multiplication between an invertible diagonal matrix and an anti-symmetric matrix. Specif- ically, defining A diag ao' ((W W + (x(())...)) -b] and w W we
J(t) diag o ((W W xx, + ((..). + b)] (w- -WT)
have J()= = AB.
13

---

Published as a conference paper at ICLR 2023
Let us now consider eigenpair of AB, where the eigenvector is denoted by and the eigenvalue
by A. Then:
ABv Av,
Bv AA AA-v,
v'Bv A(v'AvAA' 'vv
(12)
where * represents the conjugate transpose. On the right-hand side of Equation 12 we can notice that the (v" Av*A-lv term a real number. Recalling that B* B B for a real anti-symmetric matrix, can notice that (v" (v"Bv)"= v'B'v -v -v'.v. Hence, the v Bv term the left-hand side of Equation [2 an imaginary number. Thereby, needs to be purely imaginary, and, as a result, all eigenvalues of (() are purely imaginary.
D BOUNDED EIGENVALUES OF J(t)
Let us consider here the case in which (((()..)) is defined such that it depends on (.()) (see for example Equation 7 In this case, the Jacobian matrix of Equation 4 can be written (in more general form than Equation| IT), as follows:
(() diag (o' ((W -
(WW-"")x.dd (x,),(()) + ((((),, + b)] ((W w²) + CC, (13)
where the term C represents the derivative of ((X()), with respect x ((). For example, for the aggregation function in Equation we have C = v/d, (instead, under the assumption of Proposition 2 C is zero matrix).
Similarly to Appendix we can see the right-hand side of Equation 13 as J()) A(B+
AB + AC. Thereby, can bound the cigenvalues of J(t) around those of AB by applying the results of the Bauer-Fike's theorem (Bauer & Fike 1960). Recalling that the eigenvalues of AB are all imaginary (as proved in Appendix[C. in a neighborhood of the imaginary axis with radius r = AC|| S ||||| For example, using the definition of the aggregation function (x)(t), Nw)) given in Equation 7 we have r S |
can conclude that the eigenvalues of J(t) are contained
Although this result does not guarantee that the eigenvalues of the Jacobian are imaginary, in practice it crucially limits their position around the imaginary axis, limiting the dynamics of the system on the graph show at most moderate amplification or loss of signals over the structure.
E DATASETS DESCRIPTION AND STATISTICS
In the graph property prediction (GPP) experiments, we employed the same generation procedure as Corso al. (2020). Graphs are randomly sampled from several graph distributions, such as Erdös Erdös-Rényi. Barabasi-Alln Alberr, and grid. Each node have random identifiers as input features. Target values represent single source shortest path, node eccentricity, and graph diameter.
PubMed is a citation network where each node represents paper and each edge indicates that one paper cites another one. Each publication the dataset is described by a 0/1-valued word vector indicating the absence/presence of the corresponding word from the dictionary. The class labels represent the papers categories.
Amazon Computers and Amazon Photo are portions of the Amazon co-purchase graph, where nodes represent goods and edges indicate that two goods are frequently bought together. Node features are bag-of-words encoded product reviews, and class labels are given by the product category.
Coauthor CS and Coauthor Physics are co-authorship graphs extracted from the Microsoft Academic Grapt where nodes are authors, that are connected by edge if they co-authored paper. Node features represent paper keywords for each author's papers, and class labels indicate most active fields of study for each author.
Table 3 contains the statistics of the employed datasets, sorted by graph density. The density of graph computed the ratio between the number of edges and the number of possible edges, i.e..
1]
14

---

Published as a conference paper at ICLR 2023
Table 3: Datasets statistics ordered by graph density.
Nodes
Edges
Features
Classes
Density
GPP
25 35
22 553
0.0275 0.5
Amazon Computers
13,752
491,722
767
10
2.6c
Amazon Photo
7,650
238,162
745
8
4.1e
PubMed
19,717
88,648
500
3
2.3e 4
Coauthor Physics
34,493
495,924
8,415
5
4.2e
Coauthor CS
18,333
163,788
6,805
15
4.9c
F EXPLORED HYPER-PARAMETER SPACE
In Table and Table 5 method. We recall that the hyper-parameter. and y refer only to our method.
we report the grids of hyper-ppaee paremetrrssstrsss employed in experiments by each
Table 4: The grid of hyper-parameters employed during model selection for the graph property prediction task.
Configs
optimizer learning rate
Adam
0.003
weight decay
10-6
n. layers
1, 10, 20
embedding dim tanh
10, 20, 30
a
10-1. 10-2 10 10-1 10-2 2 10-3
y
Table 5; The grid of hyper-parameters employed during model selection in the graph benchmark.
Configs
optimizer learning rate
AdamW
10-2, 10-3,
weight decay
0.1
layers
1, 5,00 20, 30
embedding dim
32, 64, 128
tanh
e
10-1 10 10-2, 2, 10-3 10 1, 10-1, 10-2 10-3 10-4
?
G COMPLETE RESULTS
In Table 6 we report the complete results for the graph property prediction benchmark, including all the versions and cofiguration of our A-DGN. We reported the average time per epoch (measured in seconds) for each model in the graph property prediction task in Table 7 Each model in the evaluation has 20 layers and embedding dimesion equal to 30.
15

---

Published as a conference paper at ICLR 2023
Table Mean test set (ogI)(MSE) and std averaged over random weight initializations for each configuration. The subscript stands for weight sharing, while ldw for layer dependent weights.
The lower the better.
Diameter
SSSP
Eccentricity 0.8468:1000028
GCN
0.742420.0466
0.949919918
GAT
0.8221#0.0752
0.6951:0.1499
0.7909:10.0222
GraphSAGE
0.8445+000001
0.2863=0.1843
0.7863=00.007
GIN
0.0990
-0.5408=0:4193
0.9504110.007
GCNII
0.5287
-1.1329=0.0135
0.764010.0355
DGC
0.0020
00.0433=0.0231
0.8261:1000322
GRAND
0.0095+0.0490
-0.0942=0.8897
0,6602=0.1193
Ourws
-0.1188=0.1812
-3.2417=00051
0.4296=10.103
Our
0..5455=000288
-3,4020
0.3046=10.111
Our (GCN)
0.2646+0.0402
-1.3659=0.0722
0.7177=000345
Our (GCN)
0.2071
-1.8288=0.0007
0.7235+:0.021
Table 7: Average time per epoch (measured seconds) and std, averaged over 4 random weight initializations. Each time is obtained by employing 20 layers and embedding dimension equal to 30. The subscript wy stands for weight sharing, Idw for layer dependent weights.
Diameter
SSSP
Eccentricity
GCN
3.54
37.44
11.78:1:2.43
GAT
20.2015.18
26.41118334
17.28
GraphSAGE
13.12+2.99
13.12+-2.99
8.20++0.75
GIN
6.63
21.16:12.33
14.22:43.17
GCNII
13.13+66.85
14.96+t7.17
15.70+33.92
DGC
8.97
12.5411.62
7.21
GRAND
133.84++42.57
109.15+22..49
202.46+88.001
Our
8.42+22.7
7.86+2.11
13.18:99.07
Our
14.59
10.47
14.04
13.08
28.74+10.92
16.26=t4.58
Our (GCN)
16.40
26.72+17.99
24.43+19.10
H ADDITIONAL EXPERIMENTS
H.1 GRAPH HETEROPHILIC BENCHMARKS
In the graph heterophilic benchmark we consider six well-known graph datasets for node classifi- cation, i.e., Chameleon, Squirrel, Actor, Cornell, Texas, and Wisconsin. We employed the same experimental setting as Pei et al. (020). As in the graph benchmark in Section 4.2 we study only the version of A-DGN with weight sharing. We perform hyper-parameter tuning via grid search, optimizing the accuracy score. We report in Table g the grid of hyper-parameters explored for this experiment.
We present the results on the graph heterophilic benchmarks in Table 9 reporting the achieved accuracy. We observe that our method obtains comparable results to state-of-the-art methods on four out of six datasets (i.e., Actor, Cornell Texas, Wisconsin). As stated in the work of Yan et al. 2021), the main cause of performance degradation in heterophilic benchmarks strongly related over-smoothing. Therefore, since A-DGN is not designed to tackle the over-smoothing problem, the achieved level of accuracy on these datasets is a remarkable performance. fact, our method outperforms most of the DGNs specifically designed to mitigate this phenomenon, ranking
16

---

Published as a conference paper at ICLR 2023
Table 8: The grid of hyper-parameters employed during model selection in the graph heterophilic
benchmarks.
Configs
optimizer
Adam learning rate
10-1, 1 10-4 10-2
weight decay
layers
16, 32, 64
embedding dim
128, 256, 512, 1024
tanh, relu
10-1,00-2 10-2 10-1 10-2
?
dropout
0, 0.2, 0.4, 0.6
third and fourth among all the models when considering the average rank of each model across all benchmarks.
Similarly to the graph benchmarks in Section our approach maintains or improves the perfor- mance as the number of layers increases, as Figure 3 shows. Moreover, this experiment, we show that A-DGN has outstanding performance even with 64 layers. Thus, A-DGN is able to effectively propagate the long-range information between nodes even in the scenario of graphs with high het- erophilic levels. Such result suggests that the presented approach can be starting point to mitigate the over-smoothing problem as well.
Table Mean test set accuracy and std percent averaged over different train/validation/tess splits. The higher the better. The "*" results are obtained from Yan et al. (202T), while the "o" results are obtained from Topping al. (2022). We also report the average ranking of each model across all benchmarks, showing that the proposed method ranks third and fourth (in the GCN variant) among all models considered.
Chameleon
Squirrel
Actor
Cornell
Texas
Wisconsin
avg rank
GGCN
71.14++1.84
55.17 1.58
37.54 1.56
85.68
84.86 4.55
86.86++3.29
1.33
GPRGNN
16.5
31.61
34.6
80.2748.11
78.38
82.94
8.50
H2GCN
60.11+22.15
1..48+1.86
35.70+1.000
82.70+:5.28
84.86+7.223
87.65
4.67
GCNII
63.86:1:.04
38.47
3..4
37.86:13.79
77.57+13.83
80.39+:3.40
5.83
Geom-GCN"
60.00+-2.81
38.15=0.92
31.59+1.15
6..54++3.67
66.76+22.72
64.51+3.66
9.17
PairNorm"
62.7441-2.2
20.44+1.04
2..40
58.92++3.15
60.27+:4.34
48.43-16.14
11.00
GraphSAGE
58.73+1.68
41.6110.74
34.23+0.99
75.95+5.01
82.43+6.14
81.18:5..56
6.67
GCN
64.82+2.24
53.43+2.00
27.32+1.10
60.54+5.30
55.144..116
51.76+3.06
9.83
GAT"
60.26:12.50
1..72.1.55
27.44
61.89
52.16:16.63
49.41
11.00
MI.P*
46.21+-2.99
18.77+1.56
36.53+0.70
81.89+6.40
80.81+4.75
85.29
7.67
FA
42.33110.17
0..3
28.6810.16
58.2910049
64.82:1.29
55.48
11.33
DIGL
42.02-+0.13
0..2
24.77+0032
58.26+
62.03+0043
49.53+0.27
15.33
DIGL Undirected
42.28
3..4
25.45+10.30
59.54-0.64
63.5410.38
52.23
14.00
SDRF*
42.73++0.15
37.05+0.17
28.42+0075
54.60+00.99
64.46+0..8
55.51+0.27
12.67
SDRF + Undirected
44.46:10.17
37.67
28.35
57.54
70.35
61.55
11.67
Our
49.6912.59
38.7011.26
35.3441.011
78.3842.70
82.97+2.72
86.6743.70
5.83
Our(GCN)
48.7143.07
36.36+1.08
36.1120.83
76.49
83.2446.02
87.25+3.64
6.50
H.2 TRER-NEIGHHORSMMATHH
In the Tree-NeighborsMatch task we consider the same experimental setting as Alon & Yahav
2021). For simplicity, focus the version of A-DGN with weight sharing and simple ag-
17

---

Published as a conference paper at ICLR 2023
Chameleon
Squimel
0.45
0.55
Accuracy
0.50
-0.40
Accurary
0.35
0.35
0.45
0.30
0.30
0.40
0.25
16
32
64
16
32
64
8
16
32
64
Layers
N. Layers
Layers
Cornell
Wisconsin
0.90
Accuracy
0.80
Accuracy
0.80
0.70
0.70
0.75
16
32
64
0
26
32 Layers
54
16
32
64
N. Layers
N. Layers
OurlGCN)
Figure 3: The test accuracy of A-DGN with respect to the number of layers all the graph het- erophilic datasets. From the top left to the bottom, we show: Chameleon, Squirre, Actor, Cornell, Texas, and Wisconsin. The accuracy is averaged over 10 train/validaaionntess splits.
gregation scheme (Equation 6). We report in Table the grid of hyper-parameters explored for this experiment.
Table 10: The grid of hyper-parameters employed during model selection in the Tree- NeighborMatch task.
Configs
embedding dim
32, 86, 128
tanh, relu
6
0.1
7
0.1
We present the results on the Neie-eeeibooosttchh benchmark in Table 11 having overly unbalanced setup in terms of the number of trainable parameters, have increased the number of hidden unit in our method (we use weight sharing, while baselines present up to trainable layers). Moreover, we have normalized the achieved accuracy, reporting the ratio between the accuracy score in percentage points and the employed total number of trainable hidden units, i.c., acc 100/Nzot- As it can seen, A-DGN generally outperforms the baselines (with the only exception of radius 5). Moreover, even considering the un-normalized (i.c., original) accuracy, we observe that, even with fewer trainable parameters, A-DGN achieves on par or better performance compared to GAT, GCN, and GIN.
this case, to avoid
18

---

Published as a conference paper at ICLR 2023
Table 11: Normalized train accuracy across problem radius (tree depth) in the Tree-NeighboosMatch task. The subscript in each cell contains the un-normalized (i.c., original) train accuracy. The higher the better. "N/A" denotes non-reported results. The "s" results are obtained from Alon & Yahav
2021
Problem radius
2
3
GGNN
1.56
1.04 1.0
0.78
0.38 0.60
0.20
0.09 0.21
0.06 0.16
GAT"
1.56
1.04 1.0
0.78 1.0
0.26 0.41
0.10 0.20
0.07 0.15
0.04 0.10
GCN
1.56
1.04 1.0
0.55 0.70
0.12 0.19
0.07 0.14
0.04 0.09
0.03 0.08
GIN
1.56
1.04 1.0
0.60 0.77
0.18 0.29
0.10 0.20
N/A
N/A
Our
3.13 1.0
3.13 1.0
1.16 1.0
0.32 0.41
0.27 0.23
0.13 0.16
0.12 0.10
19


Reviews:
[{"review_id": "dyfQhsb4l_O", "reviewer": "Reviewer_fEsH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This paper proposed an anti-symmetric deep graph neural network (A-DGN) to solve the over-squashing problem of GNNs. First, this paper gave a sufficient condition that an ODE corresponding to a given GNN is stable and non-dissipative (Proposition 1). Then, to satisfy the sufficient condition, they proposed to make the GNN weights anti-symmetric (Proposition 2), deriving A-DGN. Finally, numerical experiments about the graph property prediction problems and the graph classification problems were conducted to verify the usefulness of the proposed method.", "summary_of_the_review": "This paper provides theoretically grounded solutions to the problem of accuracy degradation due to the deepening of GNNs from the standpoint of ODE stability. The method is simple and applicable to a wide range of GNNs. On the other hand, the numerical experiments have not been compared with recent GNN models, and comparing the proposed method with them is desirable.", "strength_and_weaknesses": "Strengths\n- The proposed method provides a new approach to the over-squashing problem by associating a GNN with the properties (stability, non-dissipative) of corresponding ODEs.\n- The proposed method is easy to implement and can be applied to many GNNs.\n- The proposed method can effectively mitigate the accuracy degradation caused by deepening GNNs (Figure 2).\n\nWeaknesses\n- The mathematical statement is somewhat informal.\n- Comparison with baseline methods that addressed the over-squash problem or performance degradation of deep is preferable.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XfB8wdoIDk-", "reviewer": "Reviewer_Cm1J", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Deep graph networks (DGNs), especially those following the message passing paradigm, cannot effectively capture long-range dependencies in graph datasets and usually suffer from exploding and vanishing gradients.\n\nThis paper takes an ordinary differential equations (ODE)-perspective and proves that using anti-symmetric parameter matrices can be effective in mitigating the aformentioned issues.\n\nThe effectiveness of the resulting model, termed Anti-symmetric-DGN (A-DGN), is demonstrated on benchmark graph property prediction and node classification datasets.\n___", "summary_of_the_review": "While the proposed method is interesting, more empirical evaluation in support of the claims and positioning with relevant prior work are needed to strengthen the contributions.\n___", "strength_and_weaknesses": "\\\n**Strengths**\n\n\\+ The paper is well-organised and Figure 1 clearly explains the key ideas of the proposed method.\n\n\\+ The use of anti-symmetric weights for node's own features (Equations 4 and 5) to effectively deepen DGNs is theoretically grounded and interesting.\n\n\n\\\n**Weaknesses**  \n\n\\- There are no experiments to support the claim that A-DGN can specifically alleviate/mitigate oversquashing.\n\n\\- There are no experiments to support the claim that A-DGN can effectively handle long-range dependencies specifically on graph data requiring long-range reasoning.\n\n\\- The poor long-range modelling ability of DGNs is attributed to oversquashing and vanishing/exploding gradients but the poor performance could also be due to oversmoothing, another phenomenon observed in the context of very deep graph networks [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning, In AAAI'18].\n___", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "3DkAlt9py1q", "reviewer": "Reviewer_29BN", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper introduces a new formulation of GNNs based on ODEs. The main goal of the method is to ensure stability and non-dissipation properties, thus allowing the model to preserve long-range dependencies with deep architectures that also avoid vanishing gradient problems. The paper provides theoretical arguments about the properties of the proposed A-DGN model. Moreover, experiments on several tasks support the benefit of the A-DGN over several baseline models.", "summary_of_the_review": "Overall, I believe it’s an interesting approach that further increases our understanding of the relationship between GNN models and ODEs. Some aspects related to the experimental evaluation and the choice of baseline models should be addressed.", "strength_and_weaknesses": "Strengths:\n* The paper provides an elegant formulation of GNNs based on ODES. More importantly, several message aggregation schemes can be incorporated into the model.\n\n*  Providing theoretical arguments about the properties of A-DGN is a key part of the paper. Even if some properties can be derived from previous studies (including works in control theory), they still contribute to the understanding of the model.\n\n* Good experimental pipeline, considering different important tasks.  \n\nWeaknesses:\n* The main limitation of the paper is the choice of baseline models. While the paper focuses on addressing the over-squashing effect, none of the baselines has specifically been designed to do so. Therefore, to this extend, the part of the evaluation does not favor traditional GNNs. \n\n  Moreover, while training deep traditional models (e.g., GCN, GAT), the problem of over-smoothing occurs. From the discussion, this has not been taken into account in the evaluation. For instance, methodologies like PairNorm could be used to prevent over-smoothing.\n\n  At the same time, no prior work on neural ODEs is considered. I would expect that some of these models (e.g., DGC, GRAND) should have been part of the evaluation\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2MRZS7MWd88", "reviewer": "Reviewer_Hf3x", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors propose an anti-symmetric GNN to tackle the oversmoothing phenomenon in GNNs. \nThe authors suggest an ODE based approach and analyze their model A-DGN and show that it is non-dissipative, i.e., feature/energy preserving and therefore suggest that it can alleviate the oversmoothing phenomenon. Several experiments with a variable number of layers is offered showing slight improvement over the considered methods.", "summary_of_the_review": "The paper proposed an interesting extension of existing ODE based GNNs but lacks a discussion of them, and the experimental evaluation is lacking. ", "strength_and_weaknesses": "Positive points:\n- The work continues the research in the field of neural networks as ODEs that enables to interpret neural networks as dynamical systems.\n- The authors provide nice theoretical understanding of their method.\n- The paper is well organized.\n\nNegative points:\n\n- The concept of non-dissipative systems in GNNs is not novel and was previously proposed in the following papers:\n\n\"PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations\"\n\n\"Graph-Coupled Oscillator Networks\"\n\n- It is not clear to me why the authors chose to use a layer shared W matrix and not to learn it per layer, given their claim that the theoretical analysis is also correct with such a formulation. Does it yield worse results? In any case it needs to be examined and reported.\n\n-What is the difference between the proposed aggregation in equation (6) and the one in GraphConv (Morris et al, 2019). It seems to be the same to me.\n\n-It is not explained in section 4.1 why did the authors choose to change the experimental settings from the original ones (number of nodes) in Corso et al.\n\n- In the context of alleviating oversmoothing , a discussion of existing method is lacking. For example, a comparison with GCNII (Chen et al), EGNN (Zhou et al), pathGCN (Eliasof et al).\n\n-The experimental evaluation is lacking proper comparison with recent GNN methods, for example with GraphCON (Rusch et al), GCNII (Chen et al), GRAND (Chamberlain et al).\n\n- The authors run their experiments for up to10,000 epochs, which is a large number of epochs compared to typical methods in GNNs. Can the authors explain why? What is the effective number of epochs required to get the best results? What is the accuracy when using a smaller number of maximal epochs, like 500 or 1000 epochs?\n\n- The scope of experiments is quite narrow. Ideally the authors should report their results on more benchmarks such as Cora/Citeseer/Pubmed and heterophilic datasets as proposed in Geom-GCN (Pei et al).\n\n- In the context of oversmoothing evaluation the authors report the accuracy with only up to 30 layers. I think that showing the accuracy (and also possibly the energy of the node features) with more layers (e.g. 64 layers) will be more convincing. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster