CSG-ODE: ControlSynth Graph ODE For Modeling Complex Evolution of Dynamic Graphs

Thank you for your valuable comments. We have responded to each concern as follows:

A1(Response to Claims And Evidence):

Suggestion(1): To verify the correctness of the theoretical derivations, we perform additional extrapolation experiments on CSG-ODE and SCSG-ODE on walk motion data. Each model was run for 5 rounds and its mean and standard deviation were calculated $(MSE \times{10^{-2}})$. The results show that the standard deviation of SCSG-ODE is always about half of that of CSG-ODE under all sampling ratios, which indicates that it has higher stability, thus confirming the correctness of the theoretical derivation. The experimental results are shown in the following table:

ratio 40% 60% 80%

CSG-ODE $0.1883\pm0.0092$ $0.1676\pm0.0109$ $0.1524\pm0.0097$

SCSG-ODE $0.2304\pm0.0056$ $0.1978\pm0.0050$ $0.1787\pm0.0043$

Question(2): We believe that it depends on the demand for the task, and in experiments where stability is important, a tiny fraction of the model performance can be sacrificed in favor of SCSG-ODE.

A2(Response to Methods And Evaluation Criteria):

See A1.

A3(Response to Theoretical Claims):

Definition of antisymmetric matrix: The matrix $A$ satisfies ${A^T} = - A$, i.e., $a_{ij}=-a_{ji}\forall i,j$. For any matrix $A$, it can be converted to an antisymmetric matrix by $A-A^T$ (given in Remark 3.1 in the text). In our experiments, we learn a matrix $A$ and ensure its antisymmetry with the help of methods in Remark 3.1. Antisymmetric matrices have important mathematical properties and physical significance in linear algebra, and their purely imaginary eigenvalue property ensures the stability of ODE systems.

A4(Response to Experimental Designs Or Analyses):

Question(1): We model the node state evolution using a dynamical system control framework (Eqn.(18)), where ${A_0}z_i^t$ describes the linear dynamics, and $c_i^t$ (the neighborhood interaction information computed by the GNN) is transformed into control inputs (functionally analogous to the control matrix $B$ in the classical control) by the neural network $g(\cdot)$. Different from the classical control theory, we introduce subnetworks with nonlinear activation functions to portray the nonlinear evolution of the node states, so that the node states are driven by a combination of linear evolution, nonlinear evolution and external control.

Question(2): We performed a more detailed error analysis of the model for each dataset. For real datasets, numerical errors in ODE solving are inevitable. In addition, real-world data are often affected by complex factors, such as environmental changes, that were not included in our consideration and may further exacerbate error accumulation.

A5(Response to Supplementary Material):

We have added the training algorithm:

\STATE {\bfseries Input:}Observation data

\STATE {\bfseries Output:}The parameters in the model

\STATE Initialize model parameters

\WHILE {not convergence}

\FOR {each training sequence}

\STATE Construct the temporal graph with Eqn. 5

\STATE Generate a representation of each node by Eqn. 8 to 11

\STATE Generate an approximate posterior distribution of potential states for each node using Eqn.16

\STATE Sample the initial latent state $z_i^0$ of each node

\STATE Solve our ODE in Eqn. 18

\STATE Output the trajectories using the decoder

\STATE Compute the final objective, Eqn. 21

\STATE Update parameters in our CSG-ODE using gradient descent

\ENDFOR

\ENDWHILE

A6(Response to Relation To Broader Scientific Literature):

We add the following discussion: Yıldız et al. (2022) accurately decompose the independent dynamics of individual objects from their interactions and infer the independent dynamics and its interaction with reliable uncertainty estimates using ordinary differential equations for underlying Gaussian processes.

A7(Response to Relation To Other Strengths And Weaknesses):

See A1.

A8(Response to Other Comments Or Suggestions):

Suggestion(1):We put the results on the SCSG-ODE into the main text, removing the description of the GNN in the appendix, while simplifying the description of the dataset and the baseline methodology.

Suggestion(2): We have changed the abstract to read that for scenarios with stability requirements or prediction tasks...

A9(Response to Questions For Authors):

Question(1): See A5.

Question(2): $\beta$ denotes the step size of the finite difference approximation, and we use the empirical Eqn.$\beta = \frac{2}{N} \times {10^{ - 4}}$ proposed by Noschese(2024) for $\beta$ selection, which is based on an error analysis of finite-difference approximation and balances the truncation and rounding errors to ensure that the total error is minimized. For $\alpha$, we performed a sensitivity analysis (see Section 4.6). We finally chose to conduct most of the experiments with $\alpha=0.5$ because in the extrapolation experiments, the results around $\alpha=0.5$ tend to be stable and locally optimal.

Thank you for your valuable comments. We have responded to each concern as follows:

A1(Response to Claims And Evidence):

${L_f}(G_o^T,e{e^T})$ is the Frechet derivative with regard to $G_o^T$ and $e{e^T}$, which denotes the total transmission rate, and is used to measure the contribution of each edge in the graph to the information transfer. $||\cdot|{|_F}$ is the Frobenius norm,$||{L_f}(G_o^T,e{e^T})|{|_F}$ denoting the total transmissibility of the graph. ${L_f}(G_o^T,e{e^T})$ is computed by finite difference approximation, where $\beta$ denotes the step size, and the shorter the step the more accurate it is. We use the empirical equation $\beta = \frac{2}{N} \times {10^{-4}}$ proposed by Noschese(2024) for $\beta$ selection, which is based on the error analysis of the finite-difference approximation, and is able to balance the truncation and rounding errors to ensure that the total error is minimized.

A2(Response to Methods And Evaluation Criteria):

We remove the well-known graph convolution Eqn (7) in our modification. We define more explicitly the mathematical symbol for Information Propagation based Inter-node Importance Weight, as described in A1.

A3(Response to Theoretical Claims):

A diagonal matrix $P$ is invertible if none of its diagonal elements are zero, and by the nonnegativity of the activation function we can obtain that none of the diagonal elements of the matrix $P$ is zero, and therefore the matrix $P$ is invertible. We add this in the text.

A4(Response to Experimental Designs Or Analyses):

$\alpha$ is a key parameter for adjusting the effect of the sampling density mechanism, and we performed sensitivity experiments and analyzed it (see Section 4.6).

A5(Response to Supplementary Material):

Given a vector-valued function $f:\mathbb{R}^n\to\mathbb{R}^m$, its Jacobian matrix ${J_f}(x)$ is a $m \times n$ matrix, with each element denoting the partial derivative of $f$ with respect to the input variable: $J_f(x)=\begin{bmatrix}\frac{\partial f_1}{\partial x_1}& \frac{\partial f_1}{\partial x_2}& \cdots &\frac{\partial f_1}{\partial x_n}\\\ \frac{\partial f_2}{\partial x_1}&\frac{\partial f_2}{\partial x_2}&\cdots&\frac{\partial f_2}{\partial x_n}\\\ \vdots&\vdots&\ddots&\vdots\\\ \frac{\partial f_m}{\partial x_1}&\frac{\partial f_m}{\partial x_2}&\cdots&\frac{\partial f_m}{\partial x_n}\end{bmatrix}$. We have added this intermediate step in the text. Also deleted the reference to GCN in Appendix C.

A6(Response to Relation To Broader Scientific Literature):

The graph neural ODE converts message propagation into differential equations, which can adaptively adjust the computational depth to avoid the over-smoothing problem of too deep GNN. Based on ODE solving, it can deal with arbitrary time intervals without predefined time step limitations, which is suitable for irregularly sampled data. Therefore, the graph neural ODE is inherently equipped with the advantages of mitigating the oversmoothing problem and dealing with irregular sampling.

A7(Response to Relation To Other Strengths And Weaknesses):

Weaknesses(1): To verify the correctness of the theoretical derivations, we perform additional extrapolation experiments on CSG-ODE and SCSG-ODE on walk motion data. Each model was run for 5 rounds and its mean and standard deviation were calculated $(MSE \times{10^{-2}})$. The results show that the standard deviation of SCSG-ODE is always about half of that of CSG-ODE under all sampling ratios, which indicates that it has higher stability, thus confirming the correctness of the theoretical derivation. The experimental results are shown in the following table:

ratio 40% 60% 80%

CSG-ODE $0.1883\pm0.0092$ $0.1676\pm0.0109$ $0.1524\pm0.0097$

SCSG-ODE $0.2304\pm0.0056$ $0.1978\pm0.0050$ $0.1787\pm0.0043$

Weaknesses(2):We provide a brief description of the Jacobian derivation $J(t)$, as described in A5. The contents of Appendix C have also been deleted.

A8(Response to Other Comments Or Suggestions):

Suggestion(1):We have added the following to the text for the answer in A1

Suggestion(2):We have added the following to the text: Theorem: For the computation of the node importance weight matrix $D\in\mathbb{R}^{N\times N}$, the time complexity is $O({N^3})$. Note: where $\exp_0(G_o)$ is needed to compute the matrix indices by power series expansion, which usually requires $O({N^3})$ operations due to the matrix multiplication operations involved. The Frobenius norm and the linear operations that follow produce an additional $O({N^2})$ computation, but this is covered by the dominant term, $O({N^3})$.

A9(Response to Questions For Authors):

Question(1):See A1.

Question(2):See A3.

Thank you for your valuable comments. We have responded to each concern as follows:

A1(Response to Claims And Evidence):

Suggestion(1): Information Propagation based Inter-node Importance Weight can better capture the time-varying relationship in the following aspects:

• Make up for the lack of local information: by measuring the contribution of each edge to the total information propagation in the graph, we make the weight not only contain the original topological information, but also portray the influence of edges on the overall information flow, thus enhancing the model's ability to utilize the global information.
• Explanation of real-world application: in a transportation network, the efficiency of information flow will be improved if the accessibility between nodes $i$ and $j$ is enhanced (e.g., by widening the lanes). Our approach enables the model to more accurately simulate dynamic interactions in complex networks by measuring the role of edges in overall information propagation.
• Experimental Validation: In the ablation experiment, we remove the module. The results show that the model performance decreases significantly after removing the module, which further proves the key role of the mechanism in improving the effectiveness of the model.

Suggestion(2): To verify the correctness of the theoretical derivations, we perform additional extrapolation experiments on CSG-ODE and SCSG-ODE on walk motion data. Each model was run for 5 rounds and its mean and standard deviation were calculated $(MSE \times{10^{-2}})$. The results show that the standard deviation of SCSG-ODE is always about half of that of CSG-ODE under all sampling ratios, which indicates that it has higher stability, thus confirming the correctness of the theoretical derivation. The experimental results are shown in the following table:

ratio 40% 60% 80%

CSG-ODE $0.1883\pm0.0092$ $0.1676\pm0.0109$ $0.1524\pm0.0097$

SCSG-ODE $0.2304\pm0.0056$ $0.1978\pm0.0050$ $0.1787\pm0.0043$

A2(Response to Questions For Authors):

The $c_i^t$ denotes the node interaction information computed by the GNN, which we consider as the external control information of the node, and is updated as shown in Eqn(18). The equation contains two ODE equations, where the second ODE equation describes the continuous evolution of interactions between nodes and other nodes. Similarly to the classical discrete GNN, we perform a continuum treatment that allows $c_i^t$ to be modeled as an ODE. Specifically, in this model, the control information $c_i^t$ is computed by the GNN, which acts as a graph information aggregator that influences the dynamic evolution of the node's own state by aggregating information from neighboring nodes and transforming it into continuous control signals.

Thank you for your valuable comments. We have responded to each concern as follows:

A1(Response to Methods And Evaluation Criteria):

The mechanism improves model performance in the following ways:

• Make up for the lack of local information: by measuring the contribution of each edge to the total information propagation in the graph, we make the weight not only contain the original topological information, but also portray the influence of edges on the overall information flow, thus enhancing the model's ability to utilize the global information.
• Explanation of real-world application: in a transportation network, the efficiency of information flow will be improved if the accessibility between nodes $i$ and $j$ is enhanced (e.g., by widening the lanes). Our approach enables the model to more accurately simulate dynamic interactions in complex networks by measuring the role of edges in overall information propagation.
• Experimental Validation: The results of the ablation experiments show a significant decrease in model performance after the remove of this module, further demonstrating the key role of this mechanism in improving the effectiveness of the model.

A2(Response to Experimental Designs Or Analyses):

We performed Friedman's test (significance level $\alpha_s = 0.05$):

Task ratio Friedman statistic

Interpolation 40% 28.54

~ 60% 28.97

~ 80% 28.03

Extrapolation 40% 25.80

~ 60% 26.40

~ 80% 27.77

The critical value of the Friedman test is 2.508 when $k_s = 7,\alpha_s = 0.05$, and $N_s = 5$, where $k_s$ denotes the number of models compared and $N_s$ denotes the number of data sets. Since the calculated Friedman statistic is much larger than the critical value, there is a significant difference in the predictive performance among the seven models. In addition, the larger the Friedman statistic, the more significant the difference in prediction results.

A3(Response to Supplementary Material):

To verify the correctness of the theoretical derivations, we perform additional extrapolation experiments on CSG-ODE and SCSG-ODE on walk motion data. Each model was run for 5 rounds and its mean and standard deviation were calculated $(MSE \times{10^{-2}})$. The results show that the standard deviation of SCSG-ODE is always about half of that of CSG-ODE under all sampling ratios, which indicates that it has higher stability, thus confirming the correctness of the theoretical derivation. The experimental results are shown in the following table:

ratio 40% 60% 80%

CSG-ODE $0.1883\pm0.0092$ $0.1676\pm0.0109$ $0.1524\pm0.0097$

SCSG-ODE $0.2304\pm0.0056$ $0.1978\pm0.0050$ $0.1787\pm0.0043$

A4(Response to Relation To Other Strengths And Weaknesses):

Weaknesses(1): See A3.

Weaknesses(2): We performed a more detailed error analysis for each dataset. For real datasets, numerical errors in ODE solving are unavoidable. In addition, real-world data are affected by complex factors such as environmental changes that are not taken into account and may exacerbate the accumulation of errors. In the ablation experiments, we further analyze the effects of each component. Among them, the Ours-no EI performance is significantly reduced because the weights not only encode the topology of the original graph, but also reflect the role of edges in the global information propagation, which improves the model's ability to portray time-varying relationships among nodes.

A5(Response to Other Comments Or Suggestions):

Suggestion(1):${L_f}(G_o^T,e{e^T})$ is the Frechet derivative with regard to $G_o^T$ and $e{e^T}$, which denotes the total transmission rate, and is used to measure the contribution of each edge in the graph to the information transfer. $|| \cdot |{|_F}$ is the Frobenius norm,$||{L_f}(G_o^T,e{e^T})|{|_F}$ denoting the total transmissibility of the graph. ${L_f}(G_o^T,e{e^T})$ is computed by finite difference approximation, where $\beta$ denotes the step size.

Suggestion(2): We use the empirical Eqn.$\beta = \frac{2}{N} \times {10^{ - 4}}$ proposed by Noschese(2024) for $\beta$ selection, which is based on an error analysis of finite-difference approximation and balances the truncation and rounding errors to ensure that the total error is minimized. For $\alpha$, we performed a sensitivity analysis (see Section 4.6). We finally chose to conduct most of the experiments with $\alpha=0.5$ because in the extrapolation experiments, the results around $\alpha=0.5$ tend to be stable and locally optimal.

A6(Response to Questions For Authors):

In large dynamic graphs, it may be difficult to adequately capture the complex interaction patterns between nodes by relying only on GNN as graph information aggregators. Therefore, we plan to construct modeling methods that are more in line with real information propagation in order to model dynamic interaction processes more effectively. In addition, we plan to incorporate external environmental variables to enhance the generalization ability of the model.