Permutation Equivariant Neural Controlled Differential Equations for Dynamic Graph Representation Learning

We sincerely thank the reviewer for their detailed and constructive feedback. We begin by responding to the specific questions and will then address your remaining concerns.

[Q1]: Statistical significance tests

Whenever possible, we reported means along with 95% confidence intervals. This applies to all synthetic experiments and the PyTorch Geometric Temporal datasets reported in Tables 1 and 2 of the main paper. For the Temporal Graph Benchmark datasets, baseline results were only available as mean NDGC scores with standard deviations, so we adopted the same format for consistency.

To address statistical significance testing, we employ critical difference diagrams, based on a two-stage procedure:

1. A global Friedman test was used to determine whether any model differences were statistically significant.

2. If the null hypothesis was rejected, we performed pairwise comparisons using the aligned Friedman post-hoc test.

We present the results in Tables 1-6 below and will include the full CD diagrams in the camera-ready version of the manuscript.

Table 1: Critical difference diagram for heat diffusion synthetic experiment.

Table 2: Critical difference diagram for gene regulation synthetic experiment.

Table 3: Critical difference diagram for opinion dynamics synthetic experiment.

Table 4: Critical difference diagram for wealth formation synthetic experiment.

Table 5: Critical difference diagram for PGT experiments.

Table 6: Critical difference diagram for TGB experiments.

We can see that in all synthetic experiments (Tables 1-4), our PENG-CDE consistently ranks within the top non-significant clique which demonstrates its strong and stable performance. For the PyTorch Geometric Temporal datasets (twitter-tennis, england-covid; Table 5), the global Friedman test was inconclusive, meaning the test did not reject the null hypothesis that no model (even the baselines) is statistically different from the others. On the Temporal Graph Benchmark, the critical difference analysis (see Table 6) shows that PENG-CDE performs significantly better than both GN-CDE and STG-NCDE.

[Q2]: Evaluation on larger graphs

The main scope of our paper is the derivation of a new mathematical formalism for dynamic graph representation learning. Our method belongs to a family of models that are unique in their approach to tackling graph dynamics. Most other approaches are permutation equivariant due to handling the graph structure using an existing graph neural network structure.

Our implementation relies on JAX and, in particular, the Diffrax library. As both currently lack full support for sparse matrix operations, PENG-CDE, like the original GN-CDE, exhibits quadratic memory complexity in the number of nodes. This constrains scalability beyond moderately sized graphs, as discussed in the Limitations section. We view this as an exciting direction for future work. As sparse support in JAX matures beyond its experimental stage, we expect to overcome this scalability bottleneck. Importantly, as shown in Table 1 in our response to Reviewer GJRF, once memory constraints are addressed, PENG-CDE exhibits significantly better runtime scaling than GN-CDE, highlighting its potential for efficient execution even at larger scales.

[Q3]: More diverse synthetic experiments

We are happy to provide the results of testing our PENG-CDE, the baselines included in the original submission, as well as the additional baselines suggested by Reviewer Dvhd, in the two tables below.

As suggested by the reviewer, we have added two more dynamical systems to our synthetic experiments: an economic network model and a social interaction network model.

1. Capital Gains Wealth Dynamics

   $\frac{dx_i}{dt} = \delta x_i + s_i x_i^k + \sum_{j} A_{ij} (x_j - x_i)$

2. Nonlinear Opinion Dynamics

   $\frac{dx_i}{dt} = -x_i + \sigma\left( \sum_{j} A_{ij} \cdot x_j \right)$
   where $\sigma$ is a thresholding function.

For the results see Tables 7 and 8. We can see that PENG-CDE outperforms the original GN-CDE by 35–90%, and achieves the overall lowest mean MSE in 6 out of 8 dataset configurations.

Table 7: Comparison of GN-CDE variants and extended baselines on the wealth dynammics tasks. Mean MSEs with $95\%$ confidence intervals are reported, with the best mean highlighted in bold.

Table 8: Comparison of GN-CDE variants and extended baselines on the opinion dynammics tasks. Mean MSEs with $95\%$ confidence intervals are reported, with the best mean highlighted in bold.

[Q4]: Non-linear graph dynamics in Theorem 3.1

The reviewer is correct to point out that Theorem 3.1 is stated under the assumption of a linear vector field, i.e. the absence of non-linearities. The purpose of this result is to theoretically motivate the architectural modifications we introduced when transitioning from GN-CDEs to PENG-CDEs. Specifically, it formalises the idea that “PENG-CDE is the closest equivariant version of GN-CDE we can construct in the linear setting.”

In practice, however, we train all CDE-based models with non-linearities in the vector field. This enhances their expressive power and enables them to learn the non-linear dynamical systems in Section 4.1 and Tables 7 and 8 above.

[Q5]: More information on architectures and hyperparameters in main text

We agree with the reviewer the paper would benefit from more details in the main manuscript and will include this with the camera-ready version.

[W1]: Lack of novelty

See our reply to [W1] of reviewer G4dS.

[W2]: Hyperparams of baselines

To ensure a fair comparison, we followed the hyperparameter settings from the original papers as closely as possible for all baselines, in particular DCRNN and GraphMixer.

[W3]: Ablation in Table 9 is descriptive, not mechanistic

We thank the reviewer for pointing this out. We will include additional explanations in the final version. For example, summing over rows or columns of the adjacency matrix corresponds to computing node degrees, indicating that our model can utilise global information such as degree normalisation.

[W4]: No evaluation of link prediction or clustering

To ensure a fair comparison with the main baseline GN-CDE, we focused on the setup evaluated in the original paper, which included both graph-level and node-level tasks. This is a promising avenue for future work.

---

[1] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks?, 2023.

[2] Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabuseau, and Reihaneh Rabbany. Temporal graph benchmark for machine learning on temporal graphs, 2023

[I5] We are happy to expand on subsection "FINDING IV: PENG-CDE is robust to oversampling and irregular sampling" in Section 4.1, providing a mechanistic interpretation for the robustness of PENG-CDEs in these scenarios: "CDE-based models such as PENG-CDE decouple the computational complexity of their forward passes from the number of input observations: the number of vector field evaluations is determined by the ODE solver, not by the sampling rate of the data. This property makes them inherently robust to oversampling. As shown in Figure 2, increasing the sampling frequency negatively impacts both the performance and runtime of the recurrent baseline (DCRNN), while our model remains largely unaffected. Although STIDGCN also maintains performance under oversampling, its computational cost increases with the number of observations, in contrast to the constant runtime of our approach. Likewise, PENG-CDE sustains high performance across all levels of sampling irregularity, while the other models exhibit degraded performance."

Regarding the MLP, we will add the following to Section F.5 after Equation 29: "We selected the following hyperparameters: an embedding dimension of $n = 512$; an Euclidean MLP with input dimension $1 + n + n$, width $8$, two hidden layers, ReLU activation functions, and output dimension $1$."

---

[1] Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 2023

[2] Le Yu, Leilei Sun, Bowen Du, Weifeng Lv. Towards Better Dynamic Graph Learning: New Architecture and Unified Library. Advances in Neural Information Processing Systems, 2023

We appreciate the reviewer’s concerns and thank them for their thoughtful feedback. We will address the points raised one by one.

[W1] Limited real-world performance

First, we would like to highlight that across all tested real-world datasets - twitter-tennis, england-covid, tgbn-trade, and tgbn-genre - PENG-CDE achieves the best mean performance among all baselines in terms of mean losses and NDCG@10, respectively. On tgbn-genre, a widely used benchmark, our method sets a new state-of-the-art result.

Regarding the reviewer's concern about marginal performance differences: in our response to [Q1] of Reviewer FW39, we perform a statistical significance analysis using Friedman tests followed by critical difference diagrams. We kindly refer the reviewer to Tables 1–6 in our reply, which show that while none of the models (including the baselines) on twitter-tennis and england-covid are statistically distinguishable by this test, PENG-CDE's superior performance over both GN-CDE and STG-NCDE on the Temporal Graph Benchmark (TGB) and our dynamical systems datasets are statistically significant.

Secondly, beyond strong empirical results, PENG-CDE offers substantial practical advantages over the original GN-CDE:

• PENG-CDE uses only ~2% more parameters than GN-CDE, yet reduces the average MSE by 0.7% and 5.4% on twitter-tennis and england-covid datasets, respectively, and improves NDCG@10 by 2.5% and 13.7% on the TGB datasets.
• Compared to the Pre-Mult GN-CDE variant, PENG-CDE reduces its parameter count by over 99%, while still reducing the mean MSE by a factor of 8.56× to 27.65× on the synthetic datasets.

[W2] Missing baselines in synthetic experiments

We thank the reviewer for suggesting the inclusion of additional baselines in the synthetic experiments. Please refer to Tables 1 and 2 below for updated results incorporating the requested baselines. As shown, our method consistently outperforms these baselines, often by an order of magnitude. For further synthetic experiments on wealth formation and opinion dynamics including these baselines, we kindly refer to our response to Reviewer FW39.

Table 1: Comparison of GN-CDE variants and extended baselines on the heat diffusion tasks. Mean MSEs with 95% confidence intervals are reported, with the best mean highlighted in bold.

Table 2: Comparison of GN-CDE variants and extended baselines on the gene regulation tasks. Mean MSEs with $95\%$ confidence intervals are reported, with the best mean highlighted in bold.

[W3] Minor grammatical error

Thank you for highlighting this. We have adjusted the paper accordingly.

Dear Reviewer Dvhd,

Thank you for your thoughtful consideration of our rebuttal and for adjusting your score. We are pleased that our response has addressed the points you raised. Should any concerns remain, we would be glad to provide further clarification.

We thank the reviewer for their time invested in reading the paper and for their constructive and helpful review.

[Q1] Computational complexity compared with original Graph Neural CDEs

We appreciate you highlighting this aspect of our model, since it was one of the key motivations for introducing PENG-CDEs.

Parameters: The number of parameters in the PENG-CDE is independent of the number of nodes $n$ or edges $e$, whereas in the original GN-CDE, the parameter count scales quadratically with $n$. This makes the original formulation unsuitable for large-scale graph problems and negatively impacts runtime complexity.

As shown in Table 1 below, even for a modest graph size of 2048 nodes, our model trains 6.1× faster per epoch on the experiments in section 4.1 compared to the original GN-CDE. We have now clarified these differences in Section 3.2.

Table1: Runtime per training epoch (s) for the GN-CDE and our PENG-CDE, for experiments in Section 4.1 for different graph sizes.

[Q2] Theoretical guarantees for approximation power of equivariant projection

In terms of the statement of Theorem 3.1, we know that projecting an element in a vector space onto a subspace will give us the closest element in that subspace (see Appendix A for a more formal treatment of this). We use this notion to argue in Theorem 3.1 that (assuming the absence of non-linearities) PENG-CDEs are the best possible permutation equivariant approximation to the GN-CDE. Furthermore, [1] show that GN-CDEs are universal.

[Q3] Handling of rapidly evolving and sparse graph structures

Before training and inference, the provided graph snapshots are interpolated into a continuous driving path (which depends on the number of observations in the sequence). Once this preprocessing has been done, both the complexity of the forward and backward passes are decoupled from the number of input observations. Indeed, the number of vector field evaluations depends on the ODE solver rather than the sampling rate. This makes our model inherently robust to oversampled input data. For more details and experiments on this, we kindly refer the reviewer to Section 4.1 and Figure 2.

When the graph structure itself evolves rapidly, any time series model will require a large number of observations to perform well. However, since the PENG-CDE is formulated as a controlled differential equation, it offers a distinct advantage over conventional time series models: it allows us to tap into the differential equations literature to understand how rapidly changing data will impact our model, by analysing the bounded variation norm of the input path.

Regarding sparsity, we acknowledge that in its current implementation, just like the original GN-CDE, PENG-CDEs have quadratic memory complexity in the number of nodes due to the need to store dense adjacency matrices. This limitation, which we outline in the Limitations section, restricts scalability to problems with a large number of nodes. This constraint arises primarily from JAX’s limited support for sparse matrix operations. With future versions of JAX moving its sparse support beyond the experimental stage, we will be able to address this scalability bottleneck is an important direction for future work. As shown in Table 1, once memory allocation constraints are met, PENG-CDE scales much more favorably in runtime compared to GN-CDE - demonstrating its potential for efficient execution, even at larger scales.

We emphasise that for a fixed number of nodes, the memory footprint of PENG-CDEs is independent of the number of edges. This enables us to scale (within the same order of magnitude) to the largest dataset in the Temporal Graph Benchmark [2] in terms of the number of edges. For an overview of the edge counts in these datasets, we refer the reader to Figure 1 in [2].

[Q4] Extension to discrete-time graph sequences or hybrid continuous-discrete dynamics

By construction, CDEs - and by extension, PENG-CDEs - are well-suited to handle all these scenarios. While Sections 2 and 3 present the framework assuming continuous observations, discrete-time graph sequences can be naturally incorporated by interpolating the observations, for example using cubic splines. If the evaluations of the control path are ought to remain in a discrete domain, one can employ rectilinear interpolation, as discussed in [3]. We note that all real-world experiments in Section 4.2 operate on discrete-time graph dynamics, which we handle precisely in this way, as described in Section 2.2. Hybrid continuous-discrete settings can also be accommodated straightforwardly: discrete-time regimes or features can be interpolated, while continuous ones are used directly. We agree that this point could be emphasised more clearly in the main paper and will add further details in Section 4.

---

We hope to have addressed the reviewer’s questions and concerns, and we would be happy to engage in further discussion or respond to any follow-up questions.

---

[1] Tiexin Qin, Benjamin Walker, Terry Lyons, Hong Yan, and Haoliang Li. Learning dynamic graph embeddings with neural controlled differential equations, 2023.

[2] Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. Temporal graph benchmark for machine learning on temporal graphs. Advances in Neural Information Processing Systems, 2023

[3] James Morrill, Patrick Kidger, Lingyi Yang, and Terry Lyons. On the choice of interpolation scheme for neural CDEs. Transactions of Machine Learning Research, 2022.

We thank the reviewer for their constructive and helpful review.

[W1]: Limited Significance

Although the permutation-equivariant linear map we employ is well-known, we do not believe our contribution is limited to a routine application. Theorem 3.1 proves that projecting the GN-CDE vector field onto the equivariant subspace is the optimal choice, establishing new theory for dynamic-graph CDEs. Empirically, this projection delivers large practical gains: on our synthetic benchmarks, PENG-CDE uses only 2% more parameters than GN-CDE (see Table 1 below) yet reduces average MSE by between 30.44% and 73.84%. Compared to the Pre-Mult GN-CDE variant, PENG-CDE reduces the parameter count by over 99%, while still achieving 8.56× to 27.65× lower average MSE. Finally, our method belongs to a family of models that are unique in their approach to tackling graph dynamics. Most other approaches are permutation equivariant due to handling the graph structure using an existing graph neural network structure. Therefore, introducing the first permutation equivariant graph neural CDE represents an important step for this class of models. We believe this represents a meaningful advancement in the design of continuous-time models for dynamic graphs.

Table 1: Comparison of number of parameters for GN-CDE, its Pre Mult version and PENG-CDE on our synthetic experiments

[Q1]: Change in Graph Structure during Validation

In all synthetic experiments in Section 4.1, the underlying graph topology changes at 12 uniformly random snapshots out of the total 120 time steps. This implies that the expected number of topology changes in the validation window (20 snapshots for interpolation validation, 20 for extrapolation) is 40 / 120 × 12 = 4. As shown in Figure 1, where vertical gray dashed lines indicate the timing of topology changes, 3 changes occur within the extrapolation regime of the validation set in this setting. We consider this number sufficient to assess the model’s ability to generalise to evolving graph structures. For testing, we generate entirely new time series realisations, each containing 12 randomly sampled topology changes. This ensures that the test set evaluates generalisation to unseen sequences and topological dynamics. We have modified Section 4 to make this clearer.

[Q2]: Importance of time-warp equivariance Time-warp equivariance is important in time series modeling when the task depends on the sequential structure of the signal rather than the absolute timing of events. For example, in classifying whether a trajectory draws the digit “6”, it is irrelevant how fast or slowly it is traced, as long as the shape is preserved. Similarly, if you consider classifying the nodes of a social media network as to whether they are friends with a specific node or friends-of-a-friend with that node. The important characteristic is the order in which the edges appeared (you can't connect with a friend-of-a-friend without first connecting with the friend) and not the time in-between those connections appearing. We will emphasise the motivation for this type of equivariance more clearly in the camera-ready version, as well as detailing how you can avoid it by simply including time as a channel in the driving path when you believe that your problem is not time-warp equivariant.