When Graph Neural Networks Meet Dynamic Mode Decomposition

Dear authors,

thank you for thoroughly revising your paper, I believe your changes have been very beneficial. You have addressed all my minor concerns and most of my major concerns, especially the pseudocode helped a lot.

Regarding major point 2, I think you have misunderstood my comments. I did not mean to ask why you did not use GIN in your model, but why you did not compare against it, because it is proven to be maximally expressive and might solve the learning tasks in your experiments better. You are right, that GIN is often used in graph classification, but it would still be an interesting baseline. However I will not insist on the comparison, since the strength of you manuscript is a new theoretical framework, not performance of an algorithm.

Regarding major point 3, In my mind 'notable improvements over baseline models' says the exact same thing as before.

Comment: While sections 3 and 4 are good to understand, I am not sure, if I understood sections 5 and 6 about the model itself completely. A pseudocode and a more detailed description of Figure 1 could help.

Reply: Thank you very much for your suggestion. Based on your suggestion, in our revised submission, we have included the pseudocode for our model via Appendix C.1.

Comment: The proposed model is not compared to GIN, although it is maximally expressive

Reply: Thank you very much for your insightful suggestion. Based on the best of our knowledge, GIN is designed for the purpose of graph-level classification tasks due to its maximal expressive power to the WL tests. Although we can also deploy the DMD algorithm to the snapshots provided by GIN, resulting in the DMD-GIN model, the functionality of DMD-GIN will be challenging to explore compared to those tasks (e.g., node classification) using DMD-GNN output directly for prediction, since one need to at least apply some pooling strategies to the DMD-GNN outputs to accomplish the graph classification. In this case, DMD-GNN is similar to its functionality via link prediction, where its output only serves as one intermediate step of the whole model.

Nevertheless, based on your suggestion, we include some discussion in Appendix D, via the paragraph: Graph Classification and Expressive Power, in which we highlight challenging aspects and potential direction for the future study that is undergoing by us.

Comment: In line 425,426 you state that DMD-GNNs “outperform the baseline models across the majority of datasets”, which is formulated too strong, because in most cases the performance increases are only minor and/or not significant.

Reply: Thank you very much for pointing this out. In our revised submission, we have moderated our description below:

One can check that DMD-GNNs consistently achieve notable improvements over baseline models across the majority of datasets.

We also checked the description to ensure our claim is accurate. We hope our changes can meet your expectations on these comments.

Comment: The sentence on attention-based GNNs (l. 90-93) is a little bit confusing

Reply: Thank you very much for spotting this out. In our revised submission, we have clarified this content below:

In addition, attention-based GNNs (e.g., GAT) and transformer-based diffusion models (e.g., Difformer) compute node-level attention scores based on feature similarities within each layer (i.e., the current system state) but rarely consider cross-layer feature interactions, which could better capture relationships between multiple system states

Comment: In line 411, you are listing ACMP as a baseline model but it is not occurring in the tables.

Reply: We sincerely apologize for this careless mistake! We have added ACMP back to our revised submission.**

Comment: APPNP is not cited anywhere and explains what the abbreviation means.

Reply: Thank you for posting this out. In our revised submission, we have cited APPNP on our main page. Also, the propagation of APPNP was originally included in Appendix B via equation (22).

Comment (Minor): The related work section is very general, the differentiation to previous work is unclear.

Reply: Thank you very much for your suggestion. Based on your comments, we have tried our best to revise the related work section, especially on the related work of the graph neural diffusion models. Please take a look at our revised submission for further details. In addition, we wish to highlight that although we have maximized our effort to link the DMD algorithm to the current machine learning approaches via some recent works, the area of incorporating DMD to GNNs seems still in its infancy, causing limited comparison between the current machine learning works via the scope of DMD in the second paragraph of related work. In the future study, we also wish to deploy this powerful tool to other machine-learning areas.

Comment (Minor): The equation in line 133 is probably wrong because it would lead to K = 1. Should it probably be the linearity of $K_t$?

Reply: Thank you very much again for spotting this. You are definitely right. To illustrate the linearity of the operator $\mathcal K_t$, the expression shall be $\mathcal{K}_t(a\boldsymbol{\phi}_1 +b \boldsymbol{\phi}_2) = a \mathcal K_t\boldsymbol{\phi}_1+b \mathcal K_t\boldsymbol{\phi}_2$

We have included the changes in our revised submission.

Comment (Minor): Line 237: K = M*F would mean that M = 1? Probably a mistake

Reply: That is definitely a mistake. We are sorry for this. The expression of $\mathbf K$ shall refer to equation (12). In case of any confusion in the future, we have deleted that equation in our revised submission. Thanks for this careful check.

Dear authors, thank you very much for the additional changes, I have increased my final rating accordingly.

Comment (from Strength): physics-informed or biological-plausible systems can be further developed based on this structure.

Reply: We thank the reviewer for this positive feedback. In fact, this was one of our initial plans to incorporate DMD into the biological or physical fields, such as molecular dynamics, ligand binding, quantum systems, etc. We did not delve into it as the models designed for these areas usually come with some extra conditions, such as equivariant [1], and one may require some additional inductive bias in physics and chemistry via the model developing process. Most importantly, existing models incorporate the message-passing paradigm using both positional and feature information, and this information interacts with each other via propagation. Please refer to the model formulation in [1] for more details. If this is the case, it might be possible to define a generalized DMD algorithm that acts on two interacted domains, i.e., positional and feature. Such DMD has the potential to analyze the complex EGNN [1] and its variants, and the corresponding new models (if available) could show better prediction accuracy via different aspects. We will dive into these exciting fields in our future research.

Finally, we have added the relevant content in one newly included section, Appendix D, for further discussion. Please kindly visit our revised submission for more details, and let us know if you need more information. Thanks again.

[1]: E(n) Equivariant Graph Neural Networks.

Comment: Figure 1 is actually confusing as an illustration of the model. The same arrow feels like an input to the next function, and it doesn't really show where DMD module is applied.

Reply: Thank you very much for pointing this out. In our revised submission, we have revised Figure 1 to explicitly show that DMD takes two system states (snapshots) to produce DMD modes. Thank you very much for helping us to make our paper clearer.

Comment: The motivation of this paper should be expanded. As the authors stated at the beginning, "a carefully analyzed and refined dynamic can potentially enhance GNN performance by providing deeper insights into feature propagation over graphs." it would be great to see how the features are refined and why they benefit the performance.

Reply: Thank you very much for this great suggestion. As a following-up, we have made the following changes in our revised submission.

From the dynamical systems perspective, a carefully analyzed and refined dynamic can potentially enhance GNN performance by providing deeper insights into feature propagation over graphs. However, to tackle more challenging tasks, recent GNNs often adopt advanced physical dynamics [1], increasing complexity and hindering interpretability. Thus, a well-established tool is needed to analyze these dynamics and provide deeper insights.

In addition to these changes, we also tried our best to make the rest of this paragraph more explicit in illustrating the impact of applying the DMD algorithm to analyze the GNN dynamic. For your convenience, we also include them below:

Specifically, DMD approximates the Koopman operator with finite-dimensional representations only via the states (i.e., snapshots) of the system, regardless of its complexity. In addition, DMD produces the so-called DMD-modes, which are a collection of refined eigenbasis of the system's original operator (e.g., graph adjacency matrix) with potentially lower-dimensional. These modes capture the principal components driving the underlying GNN dynamics and offer a data-driven adjusted domain for spectral filtering. Building on these advantageous properties of DMD, in this work, we propose DMD-enhanced GNNs (DMD-GNNs). We show that our proposed DMD-GNNs not only can capture the characteristics of the original dynamics in a linear manner but also have the potential to adopt more complex tasks (e.g., long-range graphs [2]) in which the original model of DMD-GNNs usually delivers weak performance.

[1] From continuous dynamics to graph neural networks: Neural diffusion and beyond.

[2] Long range graph benchmark.

Comment: It would be wise of the authors to attempt to preempt this confusion with generous use of intuitive figures. Perhaps an additional figure outlining arguments in section 4. Figure 1 covers some, but not all, of this.

Reply: Thank you very much for your kind suggestion. We agree that figures are important in helping to explain GNN dynamics and Koopman theory or DMD. Therefore, in our revised submission, we have enriched the last paragraph of Section 4 to make the relevant contents more explicit. Moreover, we refined the last paragraph in Section 5.3, Summary of the Model Procedure to provide a more detailed illustration of how our model is constructed. Lastly, in Appendix C.1, we show the pseudocode of both the DMD algorithm and our DMD-GNNs.

Comment: Additionally, the authors claim scalability by showing an experiment on 'OGB-arXiv', but I would like a cleaner argument for scalability. It seems a power (s=2) of the adjacency is used in some experiments. This can present issues for memory and runtime.

Reply: Thank you very much for pointing this out. The scalability of our method is ultimately determined by the DMD update in (14). To make this clearer, we added the pseudocode in Algorithms 1 and 2 in Appendix C. DMD-GNN has three major components in terms of computation: GNN, DMD, and spectral filtering. Apparently, DMD-GNN scales with the chosen GNN. DMD is a one-time computation and essentially an SVD where efficient methods such as [1] can be applied. The spectral filtering in (14) has similar scalability as a spectral GNN, although $\boldsymbol{\theta}\in\mathbb R^r$ and $r<\min(N,d)$ thanks to the low rank in DMD. To summarize, the scalability of DMD-GNN is mainly determined by the GNN used and a spectral GNN. To make it clear, we have made corresponding contextual changes on P8 and P19 in the revision.

In regards to $s$, we fix $s =2$ followed by the settings in the SGC original paper [2]. The computation of $\widehat{\mathbf A}^s$ is one time and hence can be precomputed to save time.

Finally we point out that one may need to apply training strategies such as [3] and [4] that are designed specifically for fitting large-scale graph datasets. Adopting this may lead to a potential for applying DMD-GNN to analyze those dynamics with large-scale graph. However, this is out of the scope of this paper since our focus is to demonstrate the effectiveness of DMD to enhance a GNN.

[1]: Double Nyström Method: An Efficient and Accurate Nyström Scheme for Large-Scale Data Sets

[2]: Simplifying Graph Convolutional Networks.

[3]: Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.

[4]: Training Graph Neural Networks with 1000 Layers

Comment: I would also like to see some actual runtime plots/figures/numbers. Don't feel the need to re-run everything to record the times. Just enough to give the reader a sense of scale; what will it cost me (time, memory, etc) to actually run this?

Reply: Thank you very much for your suggestion. In Appendix C.2, we include the experiment runtime (DMD-GCN vs GCN(two layers)) of the node classification in citation networks (Figure 3); in addition, we also include the information on the actual ranks used in DMD-GNNs via different datasets (Table 5). Due to the time limit, it was quite challenging for us to include more figures and tables regarding the experiment statistics. We are happy to include them at any further stage.

We sincerely hope that the revisions we have made address your comments and enhance the clarity and depth of the paper. In light of these efforts and the updates made, we kindly ask you to consider increasing our score. Your constructive feedback has been invaluable in strengthening our work, and we remain committed to improving the paper based on your guidance. Thank you again for your thoughtful review.

Comment: My main question regarding the paper concerns motivation: to what extent do the dynamics of GNNs actually influence their performance? Approaching this from the perspective of DMD is interesting, but what specific insights does it offer in understanding GNN performance?

Reply: We thank the reviewer for your valuable suggestion. In terms of the insights that DMD can offer to analyze the GNN dynamics, although we have highlighted the role of DMD in analyzing GNN dynamics in our original Introduction section, we agree that an enriched, more explicit statement shall be included. Therefore, in our revised submission, we maximized our effort to revise the second paragraph in the Introduction section to ensure a better illustration of our motivation and functionality of the Koopman operator, DMD, and their impacts on GNN dynamics. Please refer to our revised submission for the details.

In addition to the above revision, we included one extra subsection in Appendix (B.1) to provide additional discussion on the main motivation for developing different GNN dynamics and their functionalities. We also discuss the role of DMD in analyzing these dynamics in a simple, linear way, and our proposed DMD-GNNs can generate similar or better learning accuracy than their original counterparts. We hope our effort can meet your expectations and strengthen this weakness. Please let us know what else we can do to make our paper better. Thanks again.

Comment: On long-range graph datasets, DMD-GNNs appear to outperform traditional GNNs, but some of the baselines used in the paper seem relatively weak. As far as I know, there is a class of GNNs derived from optimization or energy function approaches that perform reasonably well on such datasets. It would be helpful if the authors could include a few examples of these models for comparison.

Reply: Thank you very much for your insightful observation. We highlight that our proposed DMD-based GNNs are not specifically designed to accomplish long-range graph datasets but rather are a generic way of enhancing GNNs in various tasks. Nevertheless, we still observe that DMD-GNNs show comparable or even better results than our included baselines. To resolve your concern, we have included one more discussion section in our revised submission in Appendix C.3.5. by stating the difference between our proposed model and models that specifically target on long-range graph datasets such as [1,2].

[1]: FOSR: First-order Spectral Rewiring for Addressing Oversquashing in GNNs.

[2]: Understanding Oversquashing and Bottlenecks on Graphs via Curvature.

Comment: It could benefit from a more thorough comparison with frequency-based analysis methods. Since the modes identified by DMD correspond to specific patterns in dynamical systems—similar to how frequency-based methods assume learned graph signals contain both high-frequency and low-frequency components—exploring the relationship between these approaches could yield unique insights. Although the authors provide some explanations in Section 6, illustrating this comparison with specific datasets would strengthen their argument.

Reply: Thanks for this great suggestion. In our original submission, we only compared our model with graph framelets [3], which is a multi-scale spectral GNN that learns the filtering functions on both low and high frequency domains. Based on your comments, in our revision, we further compared our model with one of the fundamental spectral GNNs, namely ChebNet [4]. In addition, we also include the discussion between the results of ChebNet and DMD-GNNs in the experiment result paragraph via our revised submission as follows:

Finally, one can observe that DMD-GNNs also outperform spectral GNNs such as ChebNet, suggesting that the produced from data-driven DMD (i.e., $\boldsymbol{\Psi}$ in equation (14) ) effectively enhances original GNN dynamics by offering a refined spectral domain.

We hope our revision meets your expectations; thanks again.

[3]: How framelets enhance graph neural networks

[4]: Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

I would like to know (theoretically, and not necessarily in a very rigorous sense) under what graph properties the new method performs well. One motivation for this question is that, even from experiments alone, it is evident that the new method is not always the best; when it is not the best, the gap to optimality can be significant. Moreover, even when it is the best, the difference compared to suboptimal methods is not substantial. Do certain properties of the graphs determine these outcomes? It would be great if we could determine whether to use the new method based on whether the graph satisfies certain properties (naturally forming a subclass).

Comment: Summary of the Model Procedure: From Line 291 to Line 293 is unclear.

Reply: Thank you very much for pointing this out. To address your concern. We have refined the paragraph Summary of the Model Procedure below:

We visualize the steps on how our DMD-GNNs are designed in Figure 1. Initially, the underlying graph features $\mathbf x$ inside the top left blue circles are measured by the measurement function $\boldsymbol{\Phi}$, leading to the observed features $\mathbf h$ (in the left bottom orange cycles), which is further propagated by the initial GNNs to supply the inputs (snapshots) to DMD. DMD then takes these snapshots, e.g., $\mathbf h(\ell)$ and $\mathbf h(\ell +1)$, to produce the low-rank estimation of the GNN dynamics, namely DMD modes. After a customized truncation, the DMD modes (e.g., $\boldsymbol{\Psi} \in \mathbb R^{N\times r}$) are leveraged via DMD-GNNs to propagate node features via spectral filtering.

In addition, in our revised submission, we also include the pseudocode of our methods in Appendix C.1 as further clarification.

Question: Eq(12) and Line 237, which is correct? K = ?

Reply: We thank the reviewer for pointing this out. We apologize that we missed one $\mathbf M$ at line 237; the correct expression shall be the one in equation (12). In our revised submission, we have removed the expression of $\mathbf K$ at line 237 to prevent any further confusion.

Question: What is the $W(\ell)$ in Eq(14)?

Reply: We apologize for missing the statement for $\mathbf W(\ell)$ in equation (14). We have revised our submission by denoting $\mathbf W(\ell)$ as a learnable matrix for channel-mixing.

Question: Line 280: Could you please elaborate on the usage of the rate?

Reply: Thanks for the suggestion. The usage of $\xi$ is to adjust the degree of truncation via the SVD in DMD. We suppose that your confusion is due to a lack of clarification. Accordingly, we have refined our statement in our revised submission.

Specifically, a rate $\xi \in [0,1]$ is assigned to control the rate of truncation via the SVD process in DMD, e.g., $\xi = 0.85$ means DMD will select the singular values (from the largest) that are needed to reach 85% of the total spectral energy.

Followed by some additional clarification. Please visit our revised submission for more details. In addition, in Appendix C, we have visualized (Figure 4) the utilization of $\xi$ in terms of the truncation rate adjustment and the actual ranks (Table 5) that are used in DMD-GNNs via different graphs. We hope our efforts can resolve your concern. Thanks again.

You explained what o() is in Eq (15), but what is Df(0)?

Reply: Thank you very much for pointing this out. In our revised submission, we have added the following clarification:

We also let $D\mathbf f(\boldsymbol{0})$ be the Jacobian matrix of the function $\mathbf f(\mathbf x)$ when $\mathbf x = \boldsymbol{0}$.

Question: In Lemma 1, what is X? should be X(l)?

Reply: We sincerely thank the reviewer for pointing this out. You are definitely correct, and we dropped $\ell$ in our original submission to avoid cluttered notations. In our revised paper, we have adequately refined the notation in both the informal and formal versions of Lemma 1 on the main page and Appendix.

Dear Reviewer,

Thank you for taking the time to provide your thoughtful and constructive feedback on our paper. We deeply appreciate your efforts and have carefully considered your comments and suggestions.

While some of your suggestions, such as identifying a specific graph type most suitable for our method or extending the methodology to biological domains, are beyond the immediate scope of this work, we have included a discussion on these directions as potential future studies over here and our revised submission (e.g., Appendix D). We hope this provides clarity on how these ideas might be explored further in future research.

We have also worked to address your other concerns to the best of our ability, as we believe they are important for strengthening the clarity and contribution of our work, especially in establishing a connection between modern Koopman learning theory (via dynamic mode decomposition) and graph neural networks, which we hope you find compelling.

If you have any additional comments or further suggestions, we would be grateful to hear them and will be happy to address them promptly. Thank you again for your time and thoughtful engagement with our work.

Sincerely, The Authors

Thank you for your response; it has clarified many of my concerns. I understand that some aspects will need to be addressed in the future. However, the two main points I’m still worried about seem unavoidable: 1. The theoretical contribution is too similar to existing work technologically; 2. The experimental results are not particularly impressive.

I’m willing to increase your scores for your efforts, but the points mentioned indicate a limit to how high I can go. I look forward to your future work and wish you all the best!