When Graph Neural Networks Meet Dynamic Mode Decomposition
Authors: Dai Shi
Lequan Lin
Andi Han
Zhiyong Wang
Yi Guo
Junbin Gao
Venue: ICLR 2025 Poster (2025)
Keywords: Dynamic Mode Decomposition
Graph Neural Networks
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) have emerged as fundamental tools for a wide range of prediction tasks on graph-structured data. Recent studies have drawn analogies between GNN feature propagation and diffusion processes, which can be interpreted as dynamical systems. In this paper, we delve deeper into this perspective by connecting the dynamics in GNNs to modern Koopman theory and its numerical method, Dynamic Mode Decomposition (DMD). We illustrate how DMD can estimate a low-rank, finite-dimensional linear operator based on multiple states of the system, effectively approximating potential nonlinear interactions between nodes in the graph. This approach allows us to capture complex dynamics within the graph accurately and efficiently. We theoretically establish a connection between the DMD-estimated operator and the original dynamic operator between system states. Building upon this foundation, we introduce a family of DMD-GNN models that effectively leverage the low-rank eigenfunctions provided by the DMD algorithm. We further discuss the potential of enhancing our approach by incorporating domain-specific constraints such as symmetry into the DMD computation, allowing the corresponding GNN models to respect known physical properties of the underlying system. Our work paves the path for applying advanced dynamical system analysis tools via GNNs. We validate our approach through extensive experiments on various learning tasks, including directed graphs, large-scale graphs, long-range interactions, and spatial-temporal graphs. We also empirically verify that our proposed models can serve as powerful encoders for link prediction tasks. The results demonstrate that our DMD-enhanced GNNs achieve state-of-the-art performance, highlighting the effectiveness of integrating DMD into GNN frameworks.

Published as a conference paper at ICLR 2025
WHEN GRAPH NEURAL NETWORKS MEET DYNAMIC MODE DECOMPOSITION
Dai Shi
Lequan Lin"
Andi Han
University of Sydney
University of Sydney
Riken AIP
Zhiyong Wang
Yi Guo
Junbin Gao
University of Sydney
Western Sydney University
University of Sydney
ABSTRACT
Graph Neural Networks (GNNs) have emerged fundamental tools for wide range of prediction tasks on analogies between GNN feature propagation and diffusion processes, which can be interpreted as dynamical systems. In this paper, we delve deeper into this perspective by connecting the dynamics in GNNs to modern Koopman theory and its numerical method, Dynamic Mode Decomposition (DMD). We illustrate how DMD can estimate a low-rank, finite-dimensional linear operator based on multiple states of the system, effectively approximating potential nonlinear interactions between nodes in the graph. This approach allows us to capture complex dynamics within the graph accurately and efficiently. We theoretically establish connection between the DMD-estimated operator and the original dynamic operator between system states. Building upon this foundation, GNN models that effectively leverage the low-rank eigenfunctions provided by the DMD algorithm. We further discuss the potential of enhancing our approach by incorporating domain-specific constraints such as symmetry into the DMD computation, allowing the corresponding GNN models to respect known physi- cal properties of the underlying system. Our work paves the path for applying advanced dynamical system analysis tools via GNNs. We validate our approach through extensive experiments on various learning tasks, including directed graphs, large-scale graphs. long-range interactions, and empirically verify that our proposed models can serve powerful encoders for link prediction tasks. The results demonstrate that our DMDDenhanced GNNs achieve state-of- titthheart art performance, highlighting the effectiveness of integrating DMD into GNN frameworks.
data. Recent studies have drawn
introduce family of DMD-
graphs. We also
INTRODUCTION
Graph Neural Networks (GNNs) (Kipf & Welling 2017) have become fundamental tools for pro- cessing graph-structured data across a wide range of learning tasks. Recently, numerous studies (Thorpe al. 2022]] Chamberlain
2021e| Wang al., 2023 Choi et al. 2023) have established
a strong connection between GNN feature propagation and diffusion processes. Building upon this connection, many of these works have integrated complex physical processes into graph diffusion to mitigate inherent computational issues in GNNs, such as over-smoothing (Rusch et al.) (023) and over-squashing (Shi et al.) 2023b). While these approaches have yielded significant theoretical and empirical results from the feature propagation perspective, there remains gap in analyzing these dynamics through the lens of physics, particularly from a dynamical systems viewpoint.
From the dynamical systems perspective, carefully analyzed and refined dynamic can potentially enhance GNN performance by providing deeper insights into feature propagation over graphs.
"Equal contribution. Dai Shi is the corresponding author. dai shi@ eeddeyyddey...m edu. au. In memory of MeiMei H. whose love and companionship will always be remembered.

---

Published as a conference paper at ICLR 2025
However, to tackle more challenging tasks, recent GNNs often adopt advanced physical dynamics
(Han et al. 2024). increasing complexity and hindering interpretability. Thus, a well-established tool i8 needed to analyze these dynamies and provide deeper insights. Motivated by this, delve deeper into the GNN dynamics by employing Dynamic Mode Decomposition (DMD) (Tu 2013), fundamental tool from fluid dynamics theory for approximating the Koopman operator [Koopman 1931), which is essentially designed to approximate the non-linear dynamic using an (ininitt-dimmeniionaa) linear operator. Specifically, DMD approximates the Koopman operator with Unite-dimensional representations only via the states (i.e., snapshots) of the system, regardless of its complexity. In addition, DMD produces the so-called RMD-modes, which are collection of refined eigenbases 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 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 proposed DMD-GNIT 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 (Dwivedi) et al. 2022 in which the original model of DMD-GNNs usually delivers weak performance.
Contribution In this paper, we establish a novel link between feature dynamics in graph neural networks and the Koopman operator learning theory through DMD. We begin by formulating the dynamic system, Koopman operator, and DMD in Section 3 and show the link between GNN and dynamic system in Section + In Section we introduce our newly designed data-driven graph DMD approach, demonstrating how it captures the principal components that drive the underlying complex physics on the graph. Accordingly, a family of DMD-GNNS can be smoothly derived from DMD with flexible choice of initial dynamics. In Section 6 we analyze the properties of graph DMD from a dynamical systems perspective, showing that the manifold containing DMD outputs is locally topologically conjugate to specific spectral submanifold tangent to the system origin. This reveals the underlying geometry between our graph DMD and the actual characteristics of the data. We further investigate how different choices of initial dynamics affect the range of the DMD output spectrum, which is essential for DMD-G.N GNN in fitting both homophily and heterophily graphs. In Section 7 we evaluate the performance of MDD- on various learning tasks, including node classification on citation networks. long-range datasets, and node regression
spatial-temporal graphs (STGs), along with tests of parameter sensitivities. We also show that DMD-GNNs can be powerful encoders for the link prediction tasks. Finally, in Section [ we explore the potential of incorporating additional constraints on DMD and deploying physics-informed DMD for directed graphs, showing the model's ' potential of imitating complex physical dynamics, which leads to range of future research directions at the intersection of DMD and GNNs.
2 RELATED WORKS
Graph Neural Diffusion Models Many recent works have explored the link between the feature propagation in GNNs to the so-called physical diffusion process, leading to a variety of diffusion- based or physics- informee models (Chamberlain et al. [02 Choi et al., 2023) (hi et al. (024a). By integrating complex physical dynamic systems into the graph domain, these methods often achieve superior performance across different learning tasks. However, the analysis of whether the benefits from incorporated dynamies are sufficiently leveraged in GNN is rarely conducted and can only be observed in the recent works (Wang et al.) 2023). Furthermore, although they are data-driven, iatention-baase GNNs (e.g., Velikooio et al.] (018)) and waasformer-basee diffusion models (e.g., Difformen Wu et al.) 2023at) compute nede- 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. In this work, we analyze some commonly implemented GNNs and their dynamics through DMD, showing that a low-rank estimate of the system original operator from multiple system states is sufficient to induce identical or even better learning performances. Our theoretical results establish a bridge between DMD and the operators of the underlying dynamics.
Koopman Operator and Dynamic Mode Decomposition The Koopman operator theory (Koop man 193I) has become one of the most widely applied tools for analyzing modern dynamical systems (Brunton et al. 202T). Fundamentally, Koopman theory posits that any finite-dimensional nonlinear
2

---

Published as a conference paper at ICLR 2025
dynamic can be studied an mnfinite-dimensinn linear operator, denoted AC. To identify finite- dimensional representations of K. numerous numerical methods have been developed. with DMD emerging as of the most popular. DMD has become a leading tool in acrodynamics and fluid physics (Azencot et al. [0200] Fivazi et al. 2021). From a machine learning perspective, Koopman autoencoders (Nayak et al. 2024) have been developed to learn both the system's 's measurement functions and the operator simultancously. Furthermore, the spectral characteristics (i.c., eigenvalues and eigenvectors) of the estimated Koopman operator have been leveraged in recent advancements in time series analysis (Berman et al. 2023 Liu et al. 2024 Lange et al. (021). Theoretically, the work by [addoo et al. (2023) extends the DMD algorithm to incorporate more information about the underlying physics (e-g., symmetry, low-rank structures) into its outputs, resulting in a suite of physics-informeet DMD methods. Additionally, (Haller & Kaszás 2024) proved that the estimates computed from DMD belong to the slow decay submanifold that is tangent to the slow-spectral subspaces, leading to a deeper understanding of the DMD outputs and the underlying physics.
DYNAMIC SYSTEMS, KOOPMAN OPERATOR AND DMD
We consider an autonomous dynamic system which can be defined as:
x fxx),
X RR.
f (RR",
(1)
in which = x(t) is d-dimensional vector serving as the state of the system at 6. An evolution or trajectory of the system (x(t)) can induce a so-called flow mapping F, : R + Rd that takes the state x(0) at time 0 to the state x(t) at time t > 0.
In 1931, Bernard O. Koopman demonstrated that is possible to represent a nonlinear dynamical system in equation ① by using an infnnte-dimmnsionall linear operator that acts Hilbert space of measurement functions of the state x (Koopman 1931). Specifically let us consider the smooth functions: o(x) (I I."), where & and ((x) are often named as the measurement function and observations, respectively, (or interchangeably named as observables in some works (Schmid) )022)) The Koopman operator Kr, is an infinite-dimensionall linear operator that maps a measurement function & into new function Kg such that its function values at a state x (imagining it is at time 0) is given by Ø's function value the state given by the flow map , after time t, i.e.,
(K+ = & (xF,,)), VX E R.d.
(2)
This can be written as KiΦ Φ F,. is easy to prove that, for any measurement functions Φi and (aΦ1 + bep2) = ax + bC& where a, b E R. When considering all the possible advancing time along the flow maps, one can prove that (Kr)TRR, forms semi-group which has an infinitesimal generator K. In literature, this generator is called the Koopman operator of the underlying dynamical system, which satisfies the Koopman dynamical system: 4 Φ K.Φ.
For our purpose, we are more interested in the discrete nonlinear system defined by
X
F(xx).
The discrete system equation (3) itself defines a discrete path X' = {xx} }- In the same merit of equation (2), the Koopman operator IC for the nonlinear discrete system can be defined as
KΦ((x)) = (FF(x))) = ((x++1).
(4)
That is the value of the mapped function K& at the state in step k is given by the value of measurement function o at the state in the next along the path X. As IC is an dimete-dimessioall linear operator in the measurement function space, this paves the way such that analyze the underlying discrete nonlinear dynamical system in measurement space.
With given set of finite number of observed data & (X())) {)(xx)), the Dynamic Mode Decomposition (DMD), as one of the most popular numerical methods for approximating the Koopman operator, originally seeks for finiteddmenssonn linear operator K, such that
(X 1)) (X()))
where @ + 1)) is the dataset of one step shift version of dataset $ (X))).. DMD and its variants have been widely deployed via various fields such fluid dynamics (Arbabi & Mezic 2017 Mezić 2013), time series forecasting (Liu et al. 2024). environmental engineering (Li et al. 2023). and solving partial differential equations (Kutz et al. 2016b)
3

---

Published as a conference paper at ICLR 2025
4 How GNNS RESONATE WITH DYNAMIC SYSTEMS
Throughout this paper, we denote E) as graphs that can be weighted and directed, where V and & are the set of nodes and edges. Consider multilayer GNN on the graph G(V, E), and let H(E) E xxxx be the node feature matrix at layer f, and A and L E gN be the adjacency and Laplacian matrices of the graph, respectively. In general, most GNNs propagate the node signals through either spatial aggregation or spectral filtering (Wu et al. 2020), denoted as:
(6) where one can have H()) = X. the original feature matrix or H(O) = XW. and the generic function F maps node features from one layer to another. When F(H) - AH or its variants,
H(L+ 1)= F(H(
e.g., A is reweighed based the attention mechanism or rewired according to the graph topology.
equation (6) represents those spatial GNNs (Kipf & Welling 2017: Veličković et al. 2018). On
the other hand, if F(H) Udiag U H or its variants, e.g., F(H) Udian O 11 H
Ucos (diag(())) UU H. then equation 6 becomes those spectral or multi-scale GNNs (Han et al.
2022). In addition, it well-studied that many GNN dynamics in equation (6) are equivalent to the discretized version of some continuous diffusion processes (Han et al. (0024). Specifically, let h RRd be the signal over node i, the graph diffusion process can be denoted as:
(h1(1)
Σ (h, hy (t) ht))))
where the function S (t),,,,, (t)(). x (0) + R defines the diffusivity coef- ficient controlling the diffusion strength pariwisely for any given t. In the simplest case, when St,j (h,, hy. t) 1, (i) E E the diffusion process can be written as 2h, = ddivVHH), = - -LH),, in which we denote div and V the divergence and gradient operator the graph. The solution of the diffusion equation is given by the so-called heat kernel, i.e., X()) = (esp(--L))HQQ suggesting an exponential decay of the feature dissimilarities known as over-smoothing (OSM) (Rusch et al.) 2023). Accordingly, GNNs are required to find the balance between the diffusion and reaction pro- cesses, with the former homogenizes (smoothing) and later differentiates (sharpening) node features. One way to achieve this goal is to assign a certain source term to the diffusion process in equation 77) yielding the following: (t) Ot
a Σ
h2) 3 (t),
(8)
J.(.j)E
where we let R Rd x +00) Rd be a reaction function that acts only on the node features and a, 33 E R, are hyperparameters to balance two terms. One can verify that when the system is dominated by the diffusion term, e.g., large a and small 3, the corresponding GNNs will have more smoothing effects on the node features, whereas when the reaction term is dominated, node features tend to
be dissimilar to each other, see (Han et al. 2022 Giovanni et al., 2023 Choi et al., 2023) for more
detailed analysis. Furthermore, let 3 1. when (t, t) h, о h, (t) h, (f)).
h, ()), reach the
Fisher information of the node features (Fisher 1937), , and if R(h,
then have the source term presented Allen-Cahn term (Wang et al. 2023 We refer equation
(10) in (Choi et al.) 2023) and Appendix [B] for more examples. In practice, equation (8) can be implemented by the so-called MLP,, and MLP out paradigm as:
H(0)- MLP in (X), H(T) = H(() + [' P(H())dL Y = MLP ou HH (T)).
(9)
in which we let P(H()) = - (I + ()) Fixing a 3 3-1, then its Euler discretiza- AH( (HH()), E). yielding generalized (H(() where R is any matrix, then the diffusion and reaction terms can be combined as (A + H(),, resulting a linear F. i.e., F(ah; + thy)
tion yields H({+1) H(e) LH(() + (R(((()).....
version of equation 6 Finally, (H()))))
aF, + (h;)). Otherwise, in the case, e.g., (HH()), H()) @ (I H()) @ H(Q), where the diffusion and reaction terms can not be combined, resulting as non-linear feature propagation.
Clearly, equation (6) can be seen as a special case of discrete dynamical system equation 3 Similarly, the diffusion processes such as equation 7 and equation (8) are described as the continuous dynamical system equation ( These analogies show the potential of linking the Koopman operator induced under the settings of equation (3) equation { to the GNN dynamics. In the next section, we will show how the Koopman operator theory and its numerical approximation method (i.c., DMD) can facilitate analyzing GNN dynamics.
4

---

Published as a conference paper at ICLR 2025
5 DYNAMIC MODE DECOMPOSITION IN GNNS
5.1 THE DATA-DRIVEN DMD ALGORITHM
Our primary goal to leverage DMD to estimate best-fitted finite-dimensional matrix K to approximate the infinit-dimensional Koopman operator K. In the meantime, we also expect the process of estimating K can capture sufficient graph information by considering multiple rather than individual states of the system. Let's assume H (XX), i.e., the graph features are the actual observation induced from h, and denote the operator F such that H(C + 1) (E),,, thus we have
F= H(e + H())+))((()
(10)
where we let H() be the pseudo-inverse of H(E). To show how DMD approximate F, we start with the singular value decomposition (SVD) of H()): H(2) = MEV*, where we denote the upper case as the conjugate transpose or Hermitian, and the matrix M, Σ and V are with the size of N x N, N x d and d x d, respectively. We note that given N is larger than d in most of cases (e.g.. X in Cora a is with the size 2708 1433), the rank of H() is at most d. Accordingly, we have
F H(e + IIV
(11)
Furthermore, multiplying M and M on the left and right side of F yields
K = M =
(12)
suggesting a projection of F onto the column space of M Let the actual rank of H()) then equation (2) directly suggests that in practice, to estimate the unknown F from system states, i.e., H(f) and H + 1), one only need to focus the K which is with reduced dimensionality of r x which is obtained by min(N, dd).
Denoting the eigendecompositiin of KUKK)= U(K)A(K since the rank of H(() is therefore the rank of K is also r. Accordingly, one can check that the first r eigenvalues of K are equal to the original F, whereas the rest N eigenvalue of K is zero The corresponding (projected) DMD modes caan be denoted as the columns of v = MU(K) =
E & One can verify that if the columns of H(E 1) spanned by those of (t), then the DMD modes and eigenvalues obtained from the cigendecomposition of K are the eigenvectors and cigenvalues of the operator F defined in equation (IO) Accordingly, DMD provides a data-driven low-dimensional estimation of the operator F, with both eigenvalues and eigenvectors based on H()) and H( + 1).
5.2 DMD-GNNS AND FLEXIBLE CHOICE OF UNDERLYING PHYSICS
The illustration of DMD from the previous section suggests that to deploy DMD, one needs to assign an initial feature dynamic the graph so that the snapshots (i.e., H({) and H({+1)) can be collected. Through this paradigm. DMD can produce as a low-rank estimation for approximating the original non-linear dynamics. That is
H(E + 1) FH(() & KH(
(13)
in which we note that the dimension of K is N X however both N - eigenvectors and eigenvalues of K are all zeros based on equation T2. One can also leverage DMD via different feature dynamies such as oscillation (Rusch et al.] 2022). wave equation (Eliasof et al. 202T) and quantum processing (Verdon et al., 2019) to unleash the underlying physics. More importantly, DMD provides the estimated dynamic modes and eigenvalues based on the data matrices from the initial dynamics, therefore, the feature propagation via the corresponding DMD-GNNs can expressed as a spectral filtering process by leveraging the estimated V, that is
H(E+ + 1) Vddiag H())(())
(14)
where we denote W()) as the learnable matrix for channel-mixing, In practice, such spectral filtering process can be further approximated via polynomial approximation, e.g., via the first r eigenvalues
and verify that if (() and H(E + 1) shares the same column space, then the projected DMD modes will be equal to the exact DMD modes. Accordingly, in this work, we use the term DMD modes for simplicity reasons.
'One can also denote the so- calcalled exact DMD modes by v = H(E + 11)+v=--'UP
5

---

Published as a conference paper at ICLR 2025
Latent Feature Space
DMD UMD-GRN Graph Convolation
Meden Pank
Modes Transpote
Marrs
Measurement
+(+)
+
((-))
DMD
120%
* dddag (0)
Observable
Figure 1: Illustration on how DMD-GNNS are designed.
(Defferrard al. 2016). We further note that DMD also provides flexible truncation rate (Ichinaga et al. ).24). Specifically, rate [0, 1 is assigned to control the rate of truncation via the SVD process in DMD, e.g., < 0.85 means DMD will select the singular values (from the largest) that needed to reach 85% of the total spectral energy (i.e., E, A. Accordingly, higher value of indicates more eigenvalues are considered in K, suggesting a wider range, including both higher and lower frequency components for spectral filtering equation (14). On the other hand, in the case when & is smaller, only those lower frequency components are preserved. Nevertheless, we found that practically setting [0.7, 0.9) is flexible enough for letting DMD--NNN fit most of the graph benchmarks, see Section and 7.4 for more theoretical and empirical justifications.
Summary of the Model Procedure We visualize the steps how DMD-GNNG designed in Figure 1. Initially, the underlying graph features x inside the top left blue circles are measured by the measurement function db, leading to the observed features h (in the left bottom orange cycles), which is further propagated by the initial GNNs to supply the inputs (smppshots) to DMD. DMD then takes these snapshots, e.g.. h(f) and h(4 + 1). produce the low-rank estimation of the GNN dynamics, namely DMD modes. After customized truncation, the DMD modes (c.g., V IR are leveraged via DMD-GNNS to propagate node features via spectral filtering.
5.3 TOWARDS LEVERAGING MULTIPLE STATES VIA TEMTOOAL GRAPHS (STG)
Recall that the DMD algorithm produces a low-rank estimate of the system operator via multiple snapshots of the system, causing its wide application in time series forecasting (Kutz et al.) 2016a). In terms of graph-based forecasting tasks, this can correspond the node-level regression task via STGs. Specifically, the task can be interpreted as predicting the future time series window Hy (hr++1 2 ... h given the past context window H. ( (ho,-e+1: fefl--+1,hh.-coe
h,, where ff and с are the length of future and past windows, by considering GNNs as solver for the approximating the transaction between them (Bui et al. 2022 Lin et al. 2024). that is (heo+1, 2 h } R GNN((h,
htg hto-ct2, he, in which the graph structure, usu- ally as prior knowledge STGs, is leveraged consistently via the GNN dynamics. However, is preferable to have the graph structure reweighed (Wu et al.) 2023a) or rewired (Ali et al., (022)
especially when the prediction task is highly time-dependent, e.g., the traffic flow (speed) varies between rush hours and other time intervals. In this case, DMD shares similar motivation by offering a data-driven estimated cigenspace for spectral filtering based on the selected initial dynamics and
snapshots, resulting in dynamic STG forecasting paradigm (Ivanovic & Pavone 2019)
6 DMD RECOVERS THE UNDERLYING GEOMETRY
Recall that in Section 5.1 we briefly showed the relationship between the DMD modes and eigenvalues in K and those in the generie F. In this section, we provide further analysis to show that
DMD captures the principal slow decay spectral subspace that is spanned by the d basis vectors of the underlying dynamic system defined in equation 7
Our analysis adopts the settings in (Haller & Kaszás 2024). First. without loss of generality, assume that the underlying dynamic system contains a fixed point at the origin, i.c., f(0) 0. We
will also assume that the measurement function & id e.g., ((X) X. Accordingly, can

---

Published as a conference paper at ICLR 2025
rewrite the dynamic in equation ① as
x Ax + f(x), A= Df(O),
f(xx) o(xx)),
x IR.
(15)
where denote o(xx) to show that Limx-o
[(x)] 0, indicating that [f(x)] goes faster to [
0 than |x| near the origin. We also let Df(O) be the Jacobian matrix of the function f(x) when x = O. In addition, we assume that A is symmetric and the spectrum of A can be partitioned at a specific index (set d for simplicity). That is Av S -... S Yy S .... A1 < O, suggesting the existence of d-dimensional, normally attracting slow-spectral subspace S = span(e1. .cd) where denote e be the basis vector. Similarly, one can denote the corresponding fast-decay subspace denoted as F = span(e "..,,,,,,,,,, eN We further let U(A) = (U(A)s. r[ be the corresponding eigenvectors in A, with U(A)s E Rxddd U(A) E (RNx((Nd)) Then we have the following conclusion.
Lemma 1 (Informal). With mild conditions, further assume that rank(H) (U(A) F 1) lying dynamics the subspace outside S can quickly shrink out. Then DMD can capture the principal component that drives the underlying dynamic. Specifically, let the output of DMD be denoted as 'D (e.g., K D), then D is with the form
d and ( for some T E (0, 1], suggesting in the under-
D =
([(A)seAAAALAA
+ (((U(()ssX())))
(16)
and D is locally topologically conjugated with order x(( error to the linearized dynamic on a dd-dimensional, slow attracting spectral submanifold MS)) C tangent to S.
Proof and list of conditions for inducing Lemmal) I in Appendix A.II equation (T6) directly shows that
DMD captures the principal component (i.c., A.) that drives the dynamic system from its spectral subspace. We further remark that the results of Lemma cann be smoothly applied to the discretized dynamic by assuming the spectrum range of A to be AN < ... & |A S |aal S ... ... < 1, similarly, we show more detailed clarification in Appendix A.1
Guidance for GNN Dynamic, Parameter Initialization and Heterophily Adaptation The conclu- sion in Lemma I provides guidance to select the initial dynamic and DMD-GNN filtering parameter initialization. For example, let's consider two different initial dynamics H(E + 1) = (H) and H(E + 1) = ((). where we let Ä E R N be the normalized adjacency matrix. From the spectral graph theory, we have the eigenvalues of Å (denoted as A A(A) ranging from -1 to 1. The solutions of the corresponding continuous dynamics of them are
Htt) e (1-AA(A) (()) and H(t) = e (1- A2 H()).
(17)
and it is well-known that the eigenvalues of normalized Laplacian L is with the range of [0, However, one can verify that the range the eigenvalues in A A² ) is [0, 1] Therefore, with a fixed dimension of the slow decay subspace (i.e., fixed truncation rate), the second dynamic provides a smaller range of the eigenvalues and this is particularly useful for the graphs that require feature smoothing rather than sharpening dynamic in GNN, e.g., homophily graphs. Similarly, one can always bring the variation back by adding the source terms. For example, let the initial dynamic as H(E 1) = ÁH(!) + H(2) = (À + I)H( and the solution of the continuous system is H(t) - as AĀ) E [-1, hence corresponding slow decay subspace is back to the wider range, suggesting a potential mixed dynamic i.e., negative eigenvalues for sharpening and positive eigenvalues for smoothing, which benefits DMD-GNNs for fitting heterophily graphs.
EXPERIMENTS
We apply the proposed DMD GNNs to various learning tasks: 1) Node classification on both homophilic and heterophilic graphs; 2) Node classification on long-range graphs (Dwivedi et al.
2022); 3) spatial-temporal dynamic predictions; 4) As efficient encoder for link prediction tasks. We conduct the parameter sensitivity analysis to test the model's 's sensitivity on the truncation rate g. We include detailed experiment setting information, and some further interpretation of our results via e.g., epidemiology and physics in Appendix C All experiments are conducted in Python 3. on one NVIDIA RTX 4090 GPU with 16384 CUDA cores and 24GB memory size.
7

---

Published as a conference paper at ICLR 2025
Table
Node classification results in homophilic and heterophilic graphs, with the best highlighted
in bold
Methods
Cora
Citeseer
Pubmed
Texas
Wisconsin
Cornell
OGB-arXiv
MI.P
1..1+1.3
39.1+0.5
71.4+0.4
92.3-0.7
91.8+3.1
91.3+0.7
55.0+0.3
GCN
01.5
70.9:0.5
79.010.3
75.7=110
6.
66,5113388
7..
GAT
83.0+0.7
12.0=0.7
78.540.3
78.8=0.9
71.044.6
76.0=110
72.0=0.5
GIN
78.6+11.2
714+1.1
76.9+0.6
79.6-0.8
72.9+2.5
784+14
67.5=2.5
GPRGNN
83.8.10.9
75.9-122
79,840.8
75.9-622
89,913.0
85.0-5.2
70.4-1.5
APPNP
83,5+0.77
75.9-0.6
79.0+0.3
83.9-0.7
90.1
89.8-0.6
70.3=2.5
H2GCN
83.4+0.5
73.1-004
79.2+0.3
85.9-4.6
87.9+4.2
85.1-6.4
728--24
SAGE
7..5+0.8
67.2+1.0
76.8+0066
79.3=1.2
64.8+552
714+12
70.6
GRAND++
12
70.8=1111
19.2+1.5
81.4-3.5
88.6+2.11
75.6-3.2
74.1=2.3
ACMP
1.
71.4+0.5
79.1+2.3
892-5..
88.1+4.22
85.6+4.55
72.1+0.4
ChebNet
81.2.10.7
6.58
74,410.3
83.5-2.6
86.113.5
80.
70.8
Framelets
83.3.0.5
71.020.6
79.410.4
82.3-2.5
88.943.2
72.6-0.3
71.9=022
DMD-GCN
82.610.7
71412.
79.310099
84.2-2.6
85.242.11
83.613.11
73.9-28
DMD-SGC
84.1104
72.6-0.8
79.411.4
81.2-2.5
83.0+1.8
80.0=119
74.1=0.9
DMD++
3..3:10.3
73.2104
79.910.7
3.4
91.9
91.4-1.7
744:115
DMD-ACMP
82.9:0.9
73.0
81.211..5
89.4=3.8
89.412.2
88.1-2.4
75.5-0.8
7.1 NODE CLASSIFICATION ON HOMO AND HETEROPHILIC GRAPHS
We report the performances of DMD-GNNs via both homophilic and heterophilic graphs for later the connected nodes are often with distinguished labels. The baseline models include: two-layer MLP. GCN, GAT, GIN (Xu al. 2019b). GPRGNN (Chien et al. 202T). APPNP (Gasteiger et al., 2019), H2GCN (Zhu et al. (022)) GraphSage (Hamilton et al. (017). ACMP, GRAND++, ChebNet (Defferrard et al. 2016) and Graph Framelets <Zheng et al. 2021). For datasets, we include the homophilic datasets Cora, Citeseer and Pulomed, and heterophilic graphs Texas, Wi wionsinn and Cornell 1...101....... addition, to illustrate DMD-GNNs scalability, we test our models via CGB- -aB-arXXiv
(Hu et al. 2020
For DMD-GNNS, we include DMD-GCN for which the initial feature dynamic is conducted via one layer of GCN without learnable weight matrices, i.e., H({+ (H))). Followed by the 88. in terms of the initial non-linear dynamics. we selected the ACMP dynamic H(E + 1) (A- (() H(4) @ (I H(E) @ H())), leading to the DMD-ACMP A²H()), where stands
generic form in equation
model. We also define DMD-SGC with the initial dynamic H(E for a certain power of the adjacency and we fix s = 2 followed by the settings SGC (Wu et al. 2019). Moreover, to let the initial dynamic appropriately capture the graph characteristies, we define the DMD++ as H(f + 1) = H + (1 a ((), suggesting feature dynamic with two-hops of neighboring information (i.e., SGC) and source term. Additionally, we fixed the truncation rate f 0.85 for homophilic graphs (as well as for Ogbn-a aanon-arxiii v) and { 0.7 for heterophilic graphs.
The results are presented in Table I and one can check that DMD-GNNN demonstrate comparable performance to baseline models, with modest improvements on some datasets. addition, DMD- SGC shows higher/lower accuracy compared to DMD-GCN via homophilic/hetrrpphilc graphs, suggesting that stronger smoothing/ssarppeningg effect, i.e., ÅH compared to Å H is preferred in homophilichheterophilii graphs. Moreover, DMD-GNNs that are induced from the original dynamics that contain diffusion-reaactin process (e.g., ACMP) show better performances than those DMD- GNNs induced from relatively simple dynamics (e.g., GCN), this implies that DMD-GNNs can inherit the advantages of their original models. Finally, one observe that DMD-GNNs also outperform spectral GNNs such as ChebNet, suggesting that the produced from data-driven DMD (i.e., in equation (14) effectively enhances GNN dynamics by offering refined spectral domain.
7.2 PERFORMANCE ON LONG RANGE GRAPH BENCHMARKS
As DMD estimates the lower-rank graph adjacency matrix via a data-driven manner, thus, the resulting matrix K from equation (12) is, in general, denser than the original graph adjacency, leading the DMD-GNNA to own the natural advantage in terms of long-range graph learning tasks for which traditional GNNs tend to lose their accuracy due to reduced sensitivity between node features caused by the relatively long hops or distances between them, also known as the wver-squashing issue (Shi al. 2023b Topping et al. 2021). In this experiment, we test the performance of DMD via two long-
8

---

Published as a conference paper at ICLR 2025
Table 2: Results on long-range graph datasets, accuracies are reported via Macro-F1 scores. Best performances are highlighted in bold.
Table 3: Results on the link prediction tasks by treating DMD-GNN as an graph feature encoder. The best performances are highlighted in bold.
Methods
COCO-SP
PascalVOC-SP
Methods
Cora
Citeseer
Chamelcon
Squirrel
MLP
0.031=0.016
0.114=0.023
MLP
75.0+:111
7.
76.9+0444
73.24-0.2
GCN
0.079:0.025
0.238=0.016
GCN
76.94:0.8
77.9=0.9
78.74005
74.74:011
GPRGNN
0.044:0.015
0:12-=0.024
SAGE
75.140.5
76.3=1.2
82.140.4
75.34:03
SGC
0.056:20.011
0.216=0.039
APPNP
76.0::09
75.91.1
78.94088
73.64:0.2
DMD-GCN DMD-SGC
0.081=0.015
0.243-0.014
DMD-GCN
75.7+00.
78.7=0.6
76.1+:44
788++0.44
0.083440.122
0.217-0.036
DMD-SGC
77.4-0022
77.240.7
78.34-0.7
74.3+-122
DMD++
0.091:1.0099
0.241
DMD++
75.3:10.6
76.6:10.6
77.510.3
78.1
Table 4: Results (MSE) on spatial-temporal predicctiooooiiiii datasets, with the best highlighted in bold.
MLP
GAT-KNN
GUN-NNN
Chebhet
Grand++
Fromelet
DMDDGUN
DMINSGU
DMD-ACMP
DMD+
Chickenpox
(:0.001)
0.92
(:0000)
(:0.00)
0.944
(+0.004)
0.926
(:0.04)
0.926
(10.014)
0.915
(40.009)
[40.05)
0.925
(-0.093)
(:0014)
0935
(10,001)
0.924
(:0,02)
0.910
Covid
(:0.034)
0.56
(=00029)
0.556
(s0.061)
1,022
(40.045)
0.851
(=00028)
1,73
(200075)
0.911
(40/073)
1,271
(20.081)
0,938
(200025)
0,760
(=00667)
0,855
(20.013)
0,809
(=0.013)
0.784
WilMMath
(:0.042)
(:0
(20.073)
(20.058)
(=0.028)
(600001)
(=0.042)
range graph datasets, namely PascalVoc-Sy SP and COCO-SP SP (details in Appendix C.3 We did not include DMD-ACMP in this experiment due to the potential high variation of its hyperparameters. We evaluate the model performance via Macro-Fl scores and the final results are averaged from 10 runs. The learning outcomes are presented in Table. 2 One can see DMD-GNNs show superior performances by surpassing baseline models via COCO SP, whereas limited improvements can be observed via Pasca SP. We noticed that this might be due to the fact that in both datasets, the initial feature dimension is less than the number of classes, and DMD-GNNs are conducted via the spectral filtering paradigm. Henee, limited free parameters be adjusted. In Appendix CC..44] C..3. we show how we slightly changed our model's architecture to better handle this phenomenon.
7.3 TEMPPORA DYNAMICS PREDICTION FOR INFECTIOUS DISEASE EPIDEMIOLLOGY
We test DMD-GNNS in three spatial-temport datasets. These datasets are a series of graph- graph-structured data with each of them containing an integer observation, e.g., the Chickenpox and COVID prevalence. The task is to predict the future, e-g., disease occurrence based on the historical records (snapshots). For example, in the Chi ckenpox dataset, the initial graph is with the nodes countries and edges as direct neighborhood relationships. Followed by the settings from (Wu et al. 2023a), the node features are lagged weekly counts of the chickenpox cases (e.g., 4-lags). For we also deploy GCN and GAT via KNN graphs. However, we do not use the K- K-Nearest- Neiihbboss (KNN) graph for DMD-GNNS. Table 4 shows the prediction accuracy of DMD-GNNS compared to different competitors. Other than GCN and GAT models, we also include ChebNet, Grand++, Graph Framelets DMD-GNNs show remarkable performances among all included datasets, indicating the potential of deploying DMD and related approaches to identifying the principal spreading pattern in terms of infectious disease epidemiology, see Appendix C.4.2 for more details.
appropriate comparison,
7.4 SENSITIVITY ANALYSIS
In this experiment, we test DMD-GNN's sensitivities the parameter& & [0.2, 0.8), which controls the rate of truncation in DMD. The results are shown in Figure a One can observe that in homophilic graphs, the best results for DMD-GNNs using a wider spectrum) compared to heterophilic graphs in which learning accuracy dropped after best performances with lesser & achieved. This aligns with our previous claim in Section [6] That is, the graph structural information, as well as its spectrum, is with higher/lower importance via homophilichheterophilii graphs.
achieved in relatively large value of (i.e.,
7.5 DMD-GNNS FOR LINK PREDICTION
In this section, we demonstrate that DMD GNDs can powerful encoder for link prediction tasks by effectively capturing complex relational structures in graphs. Based on the work in (Kipf & Welling 2016), design model in which during the encoding process, negative links randomly

---

Published as a conference paper at ICLR 2025
(4) Cora
UI Cornel
IM-
100-02 05
000000
PEMG-GC1
56.25
56.55
4.
060-CC
15.06
DND4
DNC GCN
DMD+
R04011
07.01
02
33
44
03
06
37
36
acuioo (10
Figure 2: (a): hyperparameter sensitivity. (b): comparison between DMD-GNNs and PIDMD-GNNS
in directed and undirected graphs.
added to the original graph to enhance the model's discriminative capabilities. The model is then tasked with a binary classification problem. distinguishing between positive links from the original edges and negative links from the artificially added edges. Using node embeddings generated by the DMD-GNN encoder, the decoder predicts link existence across all edges including the negative links by computing the dot product between pairs of node embeddings for each edge. This operation aggregates the values across the embedding dimensions to produce single scalar that represents the probability of edge existence for each edge. We select Cora, Citeseer, Chame leon and Squir wrel (Rozemberczki et al., 2021a) for the testing datasets and fixed the quantity of & same as the ones used in node classification. The results presented in Table. We note that use accuracy as the metric instead of AUC-ROC because we adopt quallpproportio sampling for positive and negative edges. One interesting observation here is the DMD-GNNS included from relatively less complex initial dynamic (e.g., GCN) show better link prediction accuracy compared to others, and MLP shows comparable learning outcomes compared to all GNN models.
MODEL EXTENSIONS AND FURTHER DIRECTIONS
DMD with Additional Constraints One can check that DMD approach defined in Section 5.1 can
also be viewed as (Schmid 2010 Tu 2013) arg min |[ + - (H(()]FF. However, when information about the underlying ying dynamic is known, e.g., K should be symmetric or shift equivariant, one may prefer to align these constraints to the above optimization problem, yielding the so-called physics-informed DMD (Baddoo et al. 2023) as arg milkeE || + 1) - (f) F where we let .M be the generic notion of the potential manifold that contains K. The manifold constraint on K leads to variations in terms of the estimated eigenvectors, i.c., v, indicating a family of physics-ifformed DMD- in different learning tasks. In addition, one can let K satisfy the so-called coupling conditions (Shi) al. 2021b, such that K1 - μe, K problem between features, and these features may not need to be sourced from the same graph, e.g., transportation between two knowledge graphs. In this case, K serves as a graph-structured transportation plan between two distributions.
(PIDMD- GNNs), that can potentially show better performances
v, then the problem can be treated as an optimal transport
On Directed Graphs and Reconstruct Complex Physical Systems The DMD algorithm described in Section is is not necessarily produce a symmetric K. This suggests DMD algorithm may be naturally suitable for direct graphs. To verify this idea and motivate future research directions, we briefly test the performances of DMD-GNNs and PIDMD-GNNs (with symmetric constraints) via two directed graphs: Computer and Photo in which, unlike the node classification experiment where the graph is programmed to be undirected, results presented in Figure. 2b) show that PIDMD-GNNs underperformmoutpeffon DMD-GNNs via directed/undirected graphs. In Appendix C.6 we also show that PIDMD own the potential to reconstruct complex physical dynamics such as Schrödinger's ss equation.
preserve the directions of the links. The
CONCLUSION
In this work, we introduced a novel integration of DMD with GNNs, demonstrating its efficacy in enhancing GNN performance across various graph learning tasks. By leveraging DMD to approximate the underlying dynamics of graph data, we are able to capture key dynamical patterns through a low-rank representation, which in turn enables more effective feature propagation in GNNs. Our proposed DMD-GN GNN models demonstrate superior performance across various tasks, underscoring the benefits of incorporating the advanced dynamic system analysis tool into graph learning.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels compared to state-of-the-arr superpixel methods. IEEE transactions on pattern analysis and machine intelligence, 34(1 34(11):2274-2882 2012.
Ahmad Ali, Yanmin Zhu, and Muhammad Zakarya. Exploiting dynamic spatio-temporal graph convolutional neural networks for citywide traffic flows prediction. Neural networks, 145:233-247, 2022.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications In International Conference on Learning Representations, 2021. URL httpss://ppeereeiie.e
net / Eorum? ii= 80CPhOCVHZ
Hassan Arbabi and Igor Mezic. Ergodic theory, dynamic mode decomposition, and computation of spectral properties of the koopman operator. SIAM Journal Applied Dynamical Systems, 16(4): 2096-20 2126, 2017.
Omri Azencot, N Benjamin Erichson, Vanessa Lin, and Michael Mahoney. Forecasting sequential data using consistent koopman autoencoders. International Conference on Machine Learning, pp. 475-485 PMLR, 2020.
Waiss Azizian and mare lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference Learning Representations, 2021. URL http:s:s//ppeeeeeeeeeeeeeeee net forum?? id= xHqXYN4bw>
Peter J Baddoo, Benjamin Herrmann, Beverley J McKeon, J Nathan Kutz, and Steven Brunton. Physics-informed dynamic mode decomposition. Proceedings of the Royal Society A, 479(2271): 20220576, 2023.
Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Over- squashing GNNs through the lens of information contraction and graph expansion. In The 58th Annual Allerton Conference on Communication, Control, and Computing, pp. 1-8. IEEE, 2022.
Nimrod Berman, Ilan Naiman, and Omri Azencot. Multifactor sequential disentanglement via structured koopman autoencoders. In The Eleventh International Conference on Learning Repre- sentations, 2023. URL http:/ttts//ppeereeeeeee net.iieeweeeeeeeeeeeee wwt.:nntneeeeeeeeeeeee
forum? 1dw.enmIeedfdeeeeeee
Mitchell Black, Zhengehao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in GNNs through the lens of effective resistance. In International Conference on Machine Learning, pp. 2528 2547. PMLR, 2023.
Steven L. Brunton, Marko BudiKić, Eurika Kaiser, and Nathan Kutz. Modern koopman theory for dynamical systems. arXiv preprint arXiv:2 /2086, 2021.
Khac-Hoai Nam Bui, Jiho Cho, and Hongsuk Yi. Spatial-temporal graph neural network for traffic forecasting: An overview and open research issues. Applied Intelligence, 52(3):2763-2774 2022.
Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pp. 1407-1418. PMLR, 2021a.
Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusion on graphs. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 1594-1609. Curran Associates, Inc., 2021b. URL http::t://tcceeeeeaaaaaae flle/Ooaedccc2205511eettttrtrrfe
neurips cc/ files/paper/22
pdf
Benjamin Paul Chamberlain, James Rowbottom, Maria Goronova, Stefan Webb, Emanuele Rossi, and Michael M Bronstein. Grand: Graph neural diffusion. Proceedings of the 38th International Conference Machine Learning, (ICMI) 2021, 18-24 July 2021, Virtual Event, 2021c
11

---

Published as a conference paper at ICLR 2025
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In Proceedings of International Conference on Learning Representations, 2021.
Jeongwhan Choi, Seoyoung Hong. Noseong Park, and Sung-Bar Bae Cho. Gread: Graph neural reaction- diffusion networks. In International Conference Machine Learning, pp. 5722-574445 PMLR, 2023.
Andreea Deac, Mare Lackenby, and Petar Veličković. Expander graph propagation. In Learning on Graphs Conference, pp. 38-1. PMLR, 2022.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, 29, 2016.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 2-22236--2244,, 2022.
Hamidreza Eivazi, Luca Guastoni, Philipp Schlatter, Hossein Azizpour, and Ricardo Vinuesa. Re- current neural networks and koopman- based frameworks for temporal predictions in a low-order model of turbulence. International Journal of Heat and Fluid Flow, 90:108816, 2021.
Lars Eldén and Haesun Park. A procrustes problem on the stiefel manifold. Numerische Mathematik, 82(4):599-619, 1999.
Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. Advances in neural information processing systems, 34:3836-3843 3849, 2021.
Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using augmentations of forman-ricci curvature. In Learning on Graphs Conference, pp. 19-1. PMLR, 2023.
Ronald Aylmer Fisher. The wave of advance of advantageous genes. Annals of eugenics, 7(4): 355-369, 1937.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of International Conference on Learning Representations, 2019.
Francesco Di Giovanni, James Rowbottom, Benjamin Paul Chamberlain, Thomas Markovich, and Understanding convolution on graphs via energies. Transactions on foruum?1d=xxex3FFPTg
Michael M. Bronstein.
Machine Learning Research, 2023. ISSN 2835-8856. URL /
Jhony H Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D Malliaros. On the trade- off between over-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM international conference information and knowledge management, pp. 566-576. 2023.
George Haller and Bálint Kaszás. Data-driven linearization of dynamical systems. Nonlinear Dynamics, pp. 1-25, 2024.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Andi Han, Dai Shi, Zhiqi Shao, and Junbin Gao. Generalized energy and gradient flow via graph framelets. arXiv:2210.04/22 2022.
Andi Han, Dai Shi, Lequan Lin, and Junbin Gao. From continuous dynamics to graph neural networks: Neural diffusion and beyond. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL hhtttps:///ppeteee itt.reeeeeeeo.ooomioooooooooooo
Survey Certification.
12

---

Published as a conference paper at ICLR 2025
Philip Hartman. On local homeomorphisms of euclidean spaces. Bol. Soc. Mat. Mexicana, 5(2):
220-241, 1960.
Nicholas Higham. The symmetric procrustes problem. BIT Numerical Mathematics, 28:133-143, 1988.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33:221 2-21333, 2020.
Sara M Ichinaga, Francesco Andreuzzi, Nicola Demo, Marco Tezzele. Karl Lapo, Gianluigi Rozza, Steven Brunton, and J Nathan Kutz. Pydmd: A python package for robust dynamic mode decomposition. arXiv preprint arXiv:2402.07463. 2024.
Boris Ivanovic and Marco Pavone. The trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 2375-2384, 2019.
Kedar Karhadkar, Pradeep Kr Banerjee, and Guido Montúfar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. arXiv:2210.1 /190, 2022.
Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph comvolutional networks. In International Conference on Learning Representations, 2017. URL httpptss//ppeeeeeiiie met/forumm3 (tt.:uummd=ssJJAAp00 YJJ44aa
Bernard O Koopman. Hamiltonian systems and transformation in hilbert space. Proceedings the
National Academy of Sciences, 17(5):315-31 -188 1931.
J Nathan Kutz, Steven L Brunton, Bingni W Brunton, and Joshua L Proctor. Dynamic mode decomposition: data-driven modeling of complex systems. SIAM, 2016a.
J Nathan Kutz, Joshua L Proctor, and Steven L Brunton. Koopman theory for partial differential cquations. arXiv preprint vrXiv:1607.00077 2016b.
Henning Lange, Steven Brunton, and Nathan Kutz. From fourier to koopman: Spectral methods for long-tenn teng-termmtn time series prediction. Journal of Machine Learning Research, 22(41):1-38. 2021.
Andrei Leman and Boris Weisfeiler. A reduction of graph to canonical form and algebra arising during this reduction. Nauchno- Mauchhn--ecchnicheskkaaa Informatsiya, 2(9): 1968.
Cruz Y Li, Zengshun Chen, Xuelin Zhang, KT Tim, and Chongjia Lin. Koopman analysis by the dynamic mode decomposition in wind engineering. Journal of Wind Engineering and Industrial Aerodynamics, 232:105295, 2023.
Woosang Lim, Minhwan Kim, Haesun Park, and Kyomin Jung. Double nyström method: An efficient and accurate nyström scheme for large-scale data sets. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pp. 1367-1375, 2015.
Lequan Lin and Junbin Gao, A magnetic framelet-based convolutional neural network for directed graphs. In ICASSP 2023-2023 IEEE International Conference Acousties, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Lequan Lin, Zhengkun Li, Ruikun Li, Xuliang Li, and Junbin Gao. Diffusson models for time-series applications: survey. Frontiers of Information Technology & Electronic Engineering, 25(1): 19 19-41, 2024.
Yong Liu, Chenyu Li, Jianmin Wang, and Mingsheng Long. Koopa: Learning non-stationary time series dynamics with koopman predictors. Advances in Neural Information Processing Systems, 36, 2024.
Igor Mezić. Analysis fluid flows via spectral propertics of the koopman operator. Annual review of fluid mechanics, 45(1):357-378, 2013.
13

---

Published as a conference paper at ICLR 2025
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1-59, 2023. URL http:/ http:///mmrr.oo org/
papers/v24/22 0240. html
Indranil Nayak, Debdipta Goswami, Mrinal Kumar, and Fernando Teixeira. Temporally-coosiiseett koopman autoencoders for forecasting dynamical systems. arXiv preprint arXiv:2403. 1ttt:24433.2335,, 2024.
George Panagopoulos, Giannis Nikolentzos, and Michalis Vazirgiannis. Transfer graph neural net- works for pandemic forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pp. 4838-4844 4845,48455222 2021.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9()xcnab014, 2021a.
Benedek Rozemberczki, Paul Scherer, Yixuan He, George Panagopoulos, Alexander Riedel, Maria Astefanoaei, Oliver Kiss, Ferenc Beres, Guzman Lopez, Nicolas Collignon, et al. Pytorch geometric temporal: Spatiotemporal signal processing with neural machine learning models. In Proceedings of the 30th ACM international conference on information & knowledge management, pp. 4564- 4573, 2021b.
Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. In International Conference on Machine Learning, pp. 18888- 18909. PMLR, 2022.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv:2333.10992 2023.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural networks. In International conference on machine learning, pp. 9323-9332. PMLR, 2021.
Peter Schmid. Dynamic mode decomposition of numerical and experimental data. Journal of fluid mechanics, 656:5-25 2010.
Peter Schmid. Dynamic mode decomposition and its variants. Annual Review of Fluid Mechanics, 54(1):225-255 2022.
Peter H Schönemann. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31(1):1-10, 1966.
Zhiqi Shao, Dai Shi, Andi Han, Yi Guo, Qibin Zhao, and Junbin Gao. Unifying wer-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond. arXiv:2309.02769, 2023.
Dai Shi, Junbin Gao, Xia Hong, ST Boris Choy, and Zhiyong Wang. Coupling matrix manifolds assisted optimization for optimal transport problems. Machine Learning. 110533-555 2021.
Dai Shi, Yi Guo, Zhiqi Shao, and Junbin Gao. How curvature enhance the adaptation power of framelet GCNs. 2rXiv:2307.09768 2023a.
Dai Shi, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao. Exposition over-squashing problem GNNs: Current methods, benchmarks and challenges. arXiv:2311.07073, 2023b.
Dai Shi, Zhiqi Shao, Yi Guo, Qibin Zhao, and Junbin Gao. Revisiting generalized p-laplacian regularized framelet gens: Convergence, energy dynamic and as non-linear diffusion. Tronsactions on Machine Learning Research, 2023c.
Dai Shi, Andi Han, Lequan Lin, Yi Guo, Zhiyong Wang, and Junbin Gao. Design your own universe: A physics-informed agnostic method for enhancing graph neural networks. International Journal of Machine Learning and Cybernetics, 2024a.
Dai Shi, Zhiqi Shao, Junbin Gao, Zhiyong Wang, and Yi Guo. Frameless graph knowledge distillation. IEEE Transactions Neural Networks and Learning Systems, 2024b.
14

---

Published as a conference paper at ICLR 2025
Matthew Thorpe, Tan Minh Nguyen, Hedi Xia, Thomas Strohmer, Andrea Bertozzi, Stanley Osher, and Bao Wang. GRAND++: Graph neural diffusion with a source term. In International Confer- Learning Representations, 2022. URL http:: https://ppenreviewt net. http://wwwwwteetruutrtea formm/formmmic UMxuudzvJK.
Mathieu Blondel Tianlin Liu, Joan Puigcerver. Sparsity-constraineed optimal transport. In Proceedings of the Kleventh International Conference on Learning Representations (ICLR), 2023. URL htttps://openreet
net forumriccoooooo for 9NoQJ5RF
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference Learning Representations, 2021.
Jonathan H Tu. Dynamic mode decomposition: Theory and applications. PhD thesis, Princeton University, 2013.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, Vikash Singh, Stefan Leichenauer, and Jack Hidary. Quantum graph neural networks. arXiv preprint arXiv:1909 12264, 2019.
Yuelin Wang, Kai Yi, Xinliang Liu, Yu Guang Wang, and Shi Jin. ACMP: Allen-cahn message passing with attractive and repulsive forces for graph neural networks. In The Eleventh International Conference Learning Representations, 2023. URL TtRLhttss:// http::///pppeeeeeeeeeeeem wtwp:rreiwwwe.neeforrreeeeee id-4ffcc7P0 79Lrqs
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp. 1661-6871, PMLR, 2019.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. International Conference Learning Representations (ICLR), 2023a.
Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b. URL
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. comprehensive survey graph neural networks. IEEE transactions Neural Networks and Learning Systems, 32(1))4-24, 2020.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. arXiv preprint XrXiv:1904.07758 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference on Learning Representations, 2019b. https:
Minkai Xu, Jiaqi Han, Aaron Lou, Jean Kossaifi, Arvind Ramanathan, Kamyar Azizzadenesheli, Jure Leskovec, Stefano Ermon, and Anima Anandkumar. Equivariant graph neural operator for modeling 3d dynamics. arXiv preprint arXiv:2401. 1037, 2024.
Mengxi Yang, Shi Dai, Xuebin Zheng, Jie Yin, and Junbin Gao. Quasi-framelett Another improve- ment to graph neural networks. International Journal of Machine Learning and Cybernetics, 2024.
Kaisheng Zeng, Chengjiang Li, Lei Hou, Juanzi Li, and Ling Feng. A comprehensive survey of entity alignment for knowledge graphs. Al Open, 2:1-13, 2021.
15

---

Published as a conference paper at ICLR 2025
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: survey, arXiv preprint arXiv:2308.08235, 2023.
Xuebin Zheng, Bingxin Zhou, Junbin Gao, Yuguang Wang, Pietro Lió, Ming Li, and Guido Montufar. How framelets enhance graph neural networks. In International Conference on Machine Learning, pp. 12761-12771. PMLR, 2021.
Xuebin Zheng, Bingxin Zhou, Yu Guang Wang, and Xiaosheng Zhuang. Decimated framelet system on graphs and fast g-framelet transforms. Journal of Machine Learning Research, 23:18-1, 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
16

---

APPENDICES CONTENTS
THEORETICAL JUSTIFICATIONS OF DMDS THFORETICAL PROOFS
18
18
GNNS WITH DIFFERENT TYPES SOURCE TERMS
18
B.1 Linear and Non-linear GNN Dynamics
20
EXPERIMENT DETAILS
20
Pscudocode of DMD-GNN
20
NODE CLASSIFICATION ON BOTH TYPES OF GRAPHS
21
C.2.1
BASELINES AND DMD GO-NN IMPLEMENTATION DETAILS
22
C.3
PERFORMANCE ON LONG RANGE GRAPH BENCHMARKS (LRGB)
23
C.3.1
OVER-SQUASHING IN GNNS
23
C.3.2
DATASETS AND DATA PRE-PROCESSING
23
C.3.3
TRAINING DETAILS
24
C33.4
DMD-GNN IMPLEMENTATION AND HYPERPARAMETERS
24
C33.5
Further Discussion
25
4
DYNAMIC PREDICTIONS
25
C.4.J
DATASETS AND DATA PRE-PROCESSING
CHICKENPOX
25
COVID
25
WIKIMATH
25
C.4.2
INFLUENCE ON INFECTIOUS DISEASE EPIDEMIOLOGY
25
C.5
LINK PREDICTION DETAILS
26
C.5.1
TASK INFORMATION AND DATA PRE-PROCESSING
26
C,5.2
DMD-GNN IMPLEM IMPLEMENTATION AND HYPERPARAMETIR
27
C.6
DIRECT GRAPH AND PHYSICS INFORMED DMD
27
C.6.1
PHYSICS INFORMED DMD AND PIDMD GNN SCIENCE
27
C.6.2
ILLUSTRATIVE EXAMPLE: SCHRODINGER EQUATION
27
C.6.3
OPTIMIZATION
PIDMD
28
D FINAL REMARKS AND FUTURE RESEARCH DIRECTIONS
28
Insufficient Feature Dimension
28
Information Integrity
29
Graph Classification and Expressive Power
29
Adopting DMD More Complex Dynamics
29
17

---

Published as a conference paper at ICLR 2025
A THEORETICAL JUSTIFICATIONS OF DMDS
A.1 THEORETICAL PROOFS
Lemma (Formal Version of Lemma []. Assuming that the system defined in equation (15) has stable hyperbolic fixed point at origin x = 0, & C² in a neighborhood of the origin. Assuming the measurable function & id, i.e., (X) X. for some (generic) integer d, rank [DX
suggesting no rank degeneracy in the slow decayed subspace S. Further assume that rank(H) = d and x (UA))
+1) S (U()))X(()) (+) for some T (0, 11, suggesting in the underlying dynamics the subspuce outside S can quickly shrink out. Then the estimation of DMD, denoted as DD (e.g., K C D) with the form
D U(A)ge
+ x((U(A))x(())))
(18)
and D is locally topologically conjugated with order (( error to the linearized dynamic on a d-dimensional, slow attracting spectral submanifold M(S) E C tangent to S at
x 0.
Our proof follows directly from the one used in proving Theorem I in the work (Haller & Kaszás 2024 with the case that A is symmetric. We briefly show our proof of self-completeness.
Proof. By the assumption of stable hyperbolic fixed point and the C2 linearization theorem (Hart-
man 1960), any trajectory in a neighborhood of the origin in the nonlinear system equation (15)
converges an exponential rate cA4+11 to d-dimensional attracting spectral submanifold (S)).
tangent to a d-dimensional attracting slow spectral subspace S of the linearized system at the origin.
Based on Theorem 1 in (Haller & Kaszás 2024). we have the form of the estimations of DMD as the submanifold defined as
D (=
(O))))
(19)
where let T(A)s and P(A)s E Nxd be the right and left eigenvectors of A restricted by S. respectively. Given we assumed the A is symmetric, we have T(A)s = P(A)s = U(A)s. Therefore the above equation can be further simplified
D = se) As (D*()) ((IU(A)sx(001))
(20)
Further, because the assumption that D id, hence the derivative D D& (X)()) w.r. X(e) Is therefore we have
D =
(21)
and this completes the proof.
B GNNS WITH DIFFERENT TYPES OF SOURCE TERMS
In this section, we provide more examples regarding GNNs with source terms, which serve generic notion to those GNNs that contain two terms with one term homogenizing the node feature and another term bringing the variation back to the system to preserve the dissimilarities between features. In terms of the spatial GNNs, this paradigm typically refers to the diffusion-reactionn paradigm mentioned in the paper. Based the summary provided in Choi al. (023) and Han et al. (2024), we include some of recently developed GNNs for self-completeness. On the other hand, in terms of spectral GNNs, this GNN structure may refer multi-scale GNNs like Wavelet GNNs (Xu et al. 2019a) or Framelet GNNs (Shi et al., 2023a Zheng et al.] | (Sha et al. 2023 Shi et al. 2023c). Given there are many GNNs in this field, in this work, we only include the formulation of the models that we included in our experiments. for more details, please refer to the recent reports (Han et al. 2024). In terms of the notations, for all formulated GNNs, we denote them
via normalized adjacency/Lapllcian matrices, i.e., A and L, respectively, although notation could be bit different within their original publications. We further note that omit to introduce those basic yet state-of-te oftt--of-the-an art GNNs such as MLP, GCN, GAT and GPRGNN. Finally, we start by showing the formulation of the APPNP model which has the feature propagation as:
APPNP: H(E + 1) a) AH( oH()), H(out) H(L)W, W.
(22)
18

---

Published as a conference paper at ICLR 2025
where we let L be the number of layers. The core idea of APPNP is to balance the diffusion and
reaction terms by a and 1 - a, and this approach has been adopted by many successive models, such
as ACMP (Wang et al. 2023):
H( -
+ H(t) о (I (I-H(() O H())
(23)
in which, a matrix B is involved with adjacency matrix A for adjusting the attractive and repulsive forces between nodes, and the so-called Allen-Cahn term H(E) @ (I- ([)) @ H(E)) is leveraged as
the source term. Similar to APPNP, the graph sample and aggregate (SAGE) (Hamilton et al. 2017)
is with the propagation rule as:
SAGE:
= H()W + 2H())
(24)
where the source term is generated from the (embedded) feature matrix in addition to the original GCN propagation. We then formulate the GRAND++, which serves as the initial work on bringing 8H the source term to the diffusion process of the graph ot discretized version as:
= div(A(H). VH) + S which owns
GRAND++: H(L+1)= ĀH( SS
(25)
in which the S is the source term with each row of the is defined as S, = Σ EjEz 8i5 (H(0), - (()
with I S V selected node subset used as the source term and H(0) = [2] EjEz H(O) is the
average signal. dig denotes the initial transition probability from node j to i. Finally, we include H2GCN as
H2GCN -
(4) E = = Σ
H(dd jA and
2/2 2/2
1/2
(26)
(EN
H final = Combine (0). H,), HL),
(27)
where we let h be the neighboring order (hops) that H2GCN uses to aggregate, and the representation is formed as combination of all intermediate representations. Lastly, another embedding of H ffinal is leveraged to make the final prediction of the labels.
In terms of spectral GNNs, we only include ChebNet (Defferrard et al.) 2016) and graph framelets. Both two models propagate the node features via spectral filtering approach. For example, we have
ChebyNet: H(e +
Udiag(0) H()),
(28)
in which we let diag(O) be the filtered graph spectrum. We note that the process of the ChebyNet can be empirically approximated by the corresponding polynomials and one usually applies feature embedding. e.g., (H) prior to the spectral filtering process for computational convenience. Similarly, framelet GNN attempts to balance the feature smoothing and sharpening effects induced from the spectral filtering on both low and high pass domains, that is
Framelet
H({+1)= = Σ
WT, W...diag diag(O,,)) W.,
(29)
(NJ)EP
where we let W be the framelet decomposition matrices such that E(rseEz W.T
Py Wr, = I for P (v:5) : r = 1, ...., L.j..,,.j 0,1, J} U [),. For example, one denote the framelet
Haar type filter as
H(L + 1) = Ucos (diag(O)) H()))(()) + Usin (diag(OO) ((())
(30)
and let 0: > O. one can check that compared to the low pass filtering process cos(diag(O))U) (E),, one treat the high pass filtering process to bring the variation back to the model. Finally, along with the development of the GNNs for the node-level classification task, number of GNNs are proposed motivated by maximizing their expressive power (Xu et al. 2019b Azizian & marc lelarge 2021 Morris et al. 2023) targeting on the graph-level classification tasks (i.e., graph pooling). In general, a powerful GNN shall be equivalent to the so-called Weisfeiler and Leman (WI.) test (Leman & Weisfeiler 1968) to distinguish any two non-isomorphic graphs. Accordingly, in our experiment, we also include one of the fundamental GNNs with the maximal expressive power, graph isomorphism networks (GIN), in which, before the final pooling layer, the propagation of the node features can be denoted as
reaction process
H(L+ + 1)= = MLP(() ((1 + <(()) H(e) + AH(!). where we let be the scaling parameter added self-loops after diagonalization.
(31)
19

---

Published as a conference paper at ICLR 2025
B.1 LINEAR AND NON-LINEAR GNN DYNAMICS
In addition to our statement in Section 4 here we provide more discussion on the linear/oonllnnerity of the GNN dynamics. The main motivation for designing non-linear GNNs is enhance GNN dynamics to fit more complex graph datasets and downstream tasks. For example, it is common to observe that in spectral GNNs, the spectral filtering functions are learned via non- non-linear domains. and higher-order polynomials are usually leveraged to approximate them (Defferrard et al.) 2016 Zheng al. 202T p. On the other hand, non-linearity dynamics are widely utilized in spatial GNNs as well in order to let models propagate richer feature information from wider receptive fields (e.g.. SGC). Compared to linear GNNs, those non-linear GNNs usually have higher computational complexity and lesser interpretability to exchange the model accuracy. Driven by the snapshots induced by these complex dynamics, DMD offers us the potential to analyze and approximate these dynamics in a simple linear way, and proposed DMD-GNNN can also achieve similar or even better empirical results compared to their non-linear GNN counterparts.
C EXPERIMENT DETAILS
In this section, we first present the pseudocode of our DMD-GNNs, followed by the details of our experiments, and in the next section, we present some extra tests in addition to our current results. Our code is available at htttp:://gitube htwpa/uww..c.//t..aaaaa//aeeeaee
C.1 PSEUDOCODE OF DMD-GNN
In addition to the flow chart in Figure. below we show the pseudocode of DMD algorithm and training of DMD-GNN.
Algorithm Training Algorithm for DMD-GNN (Classification)
Input: Input Graph adjacency A, initial GNN model and ground truth Y.
Output: DMD-GNI prediction Accuracy
1: Apply the initial GNN model (e.g., GCN) to obtain system snapshots (i.e., H(E+ + 1), H())) through H(L + 1) AH(AH ().
2: Apply DMD in Algorithm to obtain DMD modes V
3: while Not converged do
4: Spectral filtering via the domain defined by V H({+ Vdiag(0) (())()
5: Compute the model output Y Softmax (( (H(
1)),
6: Take the gradient step on W
Ve w CrossEntropy (Y).
7: end while
Algorithm 2 Dynamic Mode Decomposition (DMD) Algorithm
Input: Snapshots of the system: H()) and H(E + 1), truncation rate &.
Output: DMD modes L, Optional: Reconstructed operator K.
1: Perform singular value decomposition (SVD) of H()). H(4) = MΣV*
2: Truncate the SVD results based on the truncation rate rank r: E., M., Vy.
3: Compute the reduced operator: K = M. 1)V,E--!
4: Compute eigendecomposition of K: KU(K) = (KK)..K)
5: Compute the DMD modes: v
-U()).
We note that Σ,, M, and V, are with reduced dimension (e.g., r) due to the truncation.
DMD-GNN has three major components in terms of computation: GNN, DMD and spectral filtering. Apparently, DMD-GNI scales with the chosen GNN, DMD is one time computation and essentially an SVD where efficient method such as (Lim al. 2015) can be applied. The spectral filtering in
20

---

Published as a conference paper at ICLR 2025
Table 5: Summary statistics of datasets, the column H(G) the homophily index.
Datasets
#Classes #Features
#nodes
#Edges
H(C)
Ranks
Cora
7
1433
2708
5429
0.825
421
Citeseer
6
3703
3327
4372
0.717
819
Pubmed
500
19717
44338
0.792
CS
15
6805
18333
100227
0.832
1750
Photo
745
7487
126530
0.849
Ogbn-arxiv
47
100
169343
1166243
0.681
128
Wisconsin
5
251
499
1703
0.150
21
Texas
1703
183
279
0.097
Cornell
5
1703
183
277
0.386
16
Runtime Comparison: DMD-GNN GCN
27.8s
DMD DMD-GGN
24.8s
Runtime (5)
15
10.40
12.64
12.25
11.55
11.15
9.1s
6.76
7:36
Cala
Creeser
Pubmed
Photo
#isconei
Cornel
Datasets
Figure 3: Comparison between GCN (two-layers) and DMD-GCN of the total times for citation datasets.
Line 4 in Algorithm 1 has similar scalability spectral GNN, although R" and < (nin(N, d) thanks to the low rank in DMD. Therefore, the scalability of DMD-GNN is mainly determined by the GNN used and a spectral GNN.
C.2 NODE CLASSIHICATON ON BOTH TYPES OF GRAPHS
Table. shows the summary statistics of the included static graphs, in which we let H(G) be their homophily index which indicates the uniformity of labels in neighborhoods. For example, higher homophily index suggests that the connected nodes within the graph are more likely with the same label. note that also show the summary statistics of CS and Photo as they have been utilized via Section
g for testing the performance difference between DMD-GNNs and PIDMD-GNNs Finally, as we have shown the main page, we fixed SVD Rank within the SVD of H(E) as 0.85 for the homophilic graphs (as well as for we also show the number of actual ranks that are used for DMD-GNNS and these ranks directly determine the number of parameters for the spectral filtering within DMD-GNNs, e.g., equation (14). Figure. visualizes the actual number the ranks (highlighted in orange) via six included datasets. From both table and figure, one can see that DMD significantly reduced the number of singular values. Especially in the heterophilic graphs, spectral filtering. This directly verified our claim in Section5.22 That is, for homophilic graphs, in which more graph structural information is needed for GNNs, one may need higher value of g for the truncation compared to the heterophilic graphs
and 0.7 for heterophilic graphs. In Table. 5
only require less than 40 learnable parameters for
21

---

Published as a conference paper at ICLR 2025
Singuar V3 Loc
singuaa Vakke
Singuar
You hupala
Mostheggaaa 1271 CART silar
Test legicca Nakes
32-
Figure Number of feature dimensions and the actual number of ranks selected from the DMD. From the first row (E = 0.85): Cora, Citeseer, Pubmed; second row (5 = 0.7): Wi Wisconsin, Texas and Cornell.
C.2.1 BASELINES AND AMD-GNNG IMPLEMENTATION DETAILS
All included baselines are implemented using torch. geometric, except graph framelets with we adapt from the work in (Zheng et al. 2022 Yang et al., 2024). As there are many ways of implementing graph framelets, in this work, we only consider the easiest case, i.e., Haar filter, which leads to the propagation denoted in equation (30). We set the number of layers of all included baselines as 2. and the baseline outcomes are collected from the pre-published results. In terms of DMD-GMM
all of our proposed models adopt a spectral filtering paradigm, as illustrated in equation 14). Hence, in most of our conducted experiments, we let all DMD-GNNs with one single layer. More specifically, for all tested datasets, we do normalization on both feature and graph adjacency to adjust the potential scaling issues. terms of the ACMP dynamic, we fixed B,j 0.0001 and 0.5 for homophilic and heterophilic graphs, respectively based on the conclusion in (Wang et al. 2023)
For all included datasets, we followed the standard data split scheme. In terms of the model training and testing, we leverage the ADAM as the optimizer. We also found that in this experiment, our proposed DMD-GNN models are not sensitive to hyperparameters such as hidden dimension, learning rate, weight decay, dropout, etc, suggesting the effectiveness of incorporating DMD to refine the initial dynamics the graph. Finally, the maximum number of epochs set as 200 for all included datasets except 500 for Ogbn-arXiv The average test accuracy and its standard deviation came from 10 runs In Figure. 3 we show the total training time for DMD-GCN and GCN (two layers) via both homophilic and heterophilic graph datasets. We highlight that as our DMD-GNNS propagate node features via spectral filtering, hence we implemented DMD-GNN usually with one layer, which aligns with the settings in Defferrard et al. (2016). In terms of the comparison between the number of parameters, here we take Cora dataset, with feature and label dimensions 1433 and 7, respectively, as an example, and we compare the parameters within GCN (two-layers), ChebNet (one-layer), DMD-GCN (one-layer). Let the number of hidden dimensions be 16. One can check two-layer GCN with the total parameters as 1433 x 1 16 7 16 + 7 = 23063 (with bias), and for ChebNet with polynomial order of 2 is x 1433 x 16 +2 x 16 x 17+1777 = 46103. In terms of DMD-GNNs, as adopt spectral filtering paradigm, the number of parameters is 1433 16 + 421 23349, which is very similar to GCN two layers but far less than ChebNet. This directly suggests the effectiveness of incorporating DMD the GNN dynamics.
22

---

Published as a conference paper at ICLR 2025
Table 6: Summary statistics of the selected LRGBs
Dwivedi al. 2022
Dataset
Total Graphs
Total Nodes
Average Nodes
Total Edges
PusculVOC-SP
11355
5443545
479.40
30777444
COCO-SP
123286
58793216
476.8
332091902
15
25
Grach
10
16
Oraah
Gusph44
28
Grap"
Figure 5: Illustration of the block-wise adjacency matrix used in LRGB experiment. The first edge of the second graph is with the index right after the first graph.
C.3 PERFORMANCE ON LONG RANGE GRAPH BENCHMARKS (LRGB)
C.3.1 OVER-SQUASIINGG IN GNNS
In this section, we demonstrate the motivation for testing DMD-GNNs on long-range graph datasets. The over-squashing (OSQ) problem was initially identified in (Alon & Yahav 202T) as phenomenon, termed the bottleneck, that arises during message aggregation by graph nodes along long paths. The presence of this bottleneck leads to exponentially increasing information being compressed into fixed-size vectors as the number of layers in Message Passing Neural Network (MPNN) increases that is, as the network becomes "deeper" (Topping et al. (02T). Consequently, graph-based MPNNs are unable to effectively transmit messages from distant nodes, resulting in poor performance when the prediction task depends on long-range interactions. Although the OSQ problem was initially identified empirically in (Alon & Yahav| 202T), subsequent work by Topping et al. (2021) first attempted to quantify the phenomenon by analyzing the sensitivity of each node representation h, (C)
dx, with respect to the input x,. denoted by (f) We refer to the work done by Shi et al. (023b) for
more detailed discussion on the over-squashing issue.
In general, there are two major ways of mitigating the over-squashing issue, namely spatial or spectral
rewiring. Specifically, spatial methods conduct rewiring via the graph topological indicators such
as curvatures (Topping et al. 2021: Black et al. 2023: Giraldo et al. 2023 Fesser & Weber 2023)
whereas spectral methods mainly target optimizing the graph Laplacian spectrum (Deac et al. 2022
Banerjee al.) (022). We highlight there a few methods that alleviate the over-squashing issue in an implicit manner (Shi et al. 2024b) Chamberlain et al. 2021a]b). however, we omit to discuss these methods in detail this is out of the scope of our work. Nevertheless, long-range graph benchmarks,
provided in (Dwivedi et al. (022)) have been leveraged in many subsequent works for testing the model's performance and mitigation power on the over-squashing issue.
C.3.2 DATASETS AND DATA PRE-PRSCSS
Regarding the datasets, in this work, we select two datasets in LRGB from Syytorch-geomet ric, namely COCO-SP SP and Pascalvoc-$3 both original designed for the computer vision tasks (Dwivedi al.] (022). Specifically, given the input image, the image segmentation techniques (e.g., SLIC (Achanta et al. 2012)) are initially applied to split the image by the so-called superpixels (SP). These superpixels contain rich information such coordinates and RGB components as
23

---

Published as a conference paper at ICLR 2025
the representations of different areas of the image. Then based the similarities between SPs, graph generation methods such as KNN are leveraged to build up the graph in the image. Each SP corresponds to region of the image belonging particular class. We show the summary statistics of COCO-SP SP and Pascal 1 VOC-SP in Table. 6
Given the large number of nodes and edges in both datasets, in our presented experiment, we only select 10% of total graphs for training our model. In addition, we found that there are 21 and 81 classes in Pasca 1VOC-SP and COCO respectively, and the variability of the label class in each graph is very limited. For example, in general, it is not possible to have 21 or 81 different classes via a single graph within P PascalVOC-SS and COCO-SP, respectively. To have sufficient training of the GNNs, the graph adjacency matrices are allocated into one big adjacency matrix in a block-wise manner (Figure. 5). Through this manner, the train, validation, and test split can be conducted.
C.3.3 TRAINING DETAILS
To address the inherent class imbalance, we use weighted cross-entropy (WCE) loss function, denoted
as
N WCE - Wy. log(py.),
(32)
in which we let yi be the true class label for the node i, Py, is the predicted probability for the true class and Wy; is the weight assigned to the true class. WCE adjusts the penalty applied to misclassified examples based on their class frequency. Specifically, the class weights are computed inversely to their frequency in the dataset, ensuring that minority classes, which are underrepresented, receive higher penalties during training. This mechanism forces the model to focus not only on the dominant classes but also on those that are less frequent, leading to more balanced learning process.
For evaluation, we employ the macro Fi-score, which calculates the Fi-score for each class indi- vidually and averages them to give equal weight to each class, regardless of its frequency. This is particularly relevant for imbalanced datasets, where accuracy alone may obscure poor performance in minority classes. By using the macro F1-score, we ensure that the model's 's ability to correctly classify underrepresented classes is fairly assessed. The evaluation phase begins by feeding the input data into the model, after which the predicted labels are obtained by selecting the class with the highest predicted logit. These predictions are compared to the ground truth, and the macro F1-score is computed to assess the model's 's overall classification performance, ensuring balanced evaluation across all classes. Finally, we assign channel-wise normalization to all input data.
C.3.4 DMD-GNN IMPLEMENTATION AND HYPERPARAMETERS
Recall that the architecture of our proposed DMD-GNNs follow the so-called MLP in and MLP out paradigm, in which the spectral filtering process of our model takes place via lower dimensional feature space induced from the initial embedding from MLP_in. However, this architecture can be slightly modified for LRGBs. This is because the feature dimension of LRGBs is far below the number of nodes in each graph. In this case, the feature dimension, or the actual nonzero number in the learnable filtering diagonal matrix (i.e., diag(0) in equation (14) will be even less than d. For handling this case, we set the truncation rate of DMD-GNNs as -T to provide sufficient number of free parameters to diag( (). In addition, we also slightly swap the feature propagation steps in DMD-GNN MDD- by doing spectral filtering first, followed by two MLP layers, that is
H(e+ 1) = (O)i (C), and H(out) MLPP (H(E + 1)),
(33)
where the functionality of MLP, and MLP, is to gradually increase the dimension of H( + +) to the label dimension. This architecture is essentially equivalent to our original model structure, with the only difference as stacking two MLPs after the convolution. This change shows better results compared to the original one, we note that this may be due to that compared to classic node classification tasks, tasks on LRGBs require a more fluent information transaction over graphs, and MLP gives additional feature propagation over the self-loops of the nodes, that is HW = diag HW)... Furthermore, instead of reducing the feature dimension, two subsequent MLPs provide higher free learnable parameters for the model. In terms of model training, due to the relatively large scale of LRGBs, for all DMD GNNs, we fixed the learning rate 0.0005, weight decay as 5e
24

---

Published as a conference paper at ICLR 2025
dropout 0.1, and the hidden dimension as 256, also fixed the batch size as 128 for training set, 500 for both validation and test set. In addition, all models have 10 layers to ensure that the receptive field of the initial node can cover the Long-range nodes.
C.3.5 FURTHER DISCUSSION
Although DMD-GNNS show good results via both COCO-SP SP and Pasca 1VOC-SP datasets, the performances are still relatively underscore compared to those methods (Topping et al., [02T]] Karhadkar et al. 2022) that are specifically designed for handling LRGBs. In addition, as mentioned, our proposed DMD-GNNs are not specifically designed to accomplish LRGBs, but rather generic methods to enhance GNNs in various tasks. Moreover, we mentioned in the data pre-pro rre-processing section, due to the large (total) number of nodes and edges, we only selected 10% of the dataset for training model, and this will further limit model's 's performance.
C.4 SPATIAL-TEMPORAL DYNAMIC PREDICTIONS
C.4.1 DATASETS AND DATA PRE- PROCESSCGSI
We select three spatial-temporal graph datasets from berezki et al. 2021b). Below we describe their basic information from torch geometric temporal.
(Rozem
CHICKENPOX Chi ckenpox is dataset of county-level chickenpox cases in Hungary between 2004 and 2014. We made it public during the development of Py Torch Geometric Temporal. The underlying graph is static vertices are counties and edges are neighborhoods. Vertex features are lagged weekly counts of the chickenpox cases (we included 4 lags). The target is the weekly number of cases for the upcoming week (signed integers). Our dataset consists of more than 500 snapshots (weeks).
COVID Covid d (Panagopoulos al. 2021 is dataset of mobility and history of reported cases of COVID-19 in England NUTS3 regions, from 3 March to 12 of May. The dataset is segmented in days and the graph is directed and weighted. The graph indicates how many people moved from one region to the other each day, based on Facebook Data For Good disease prevention maps. The node features correspond the number of COVID-19 cases in the region in the past window days. The task is to predict the number of cases in each node after day. For details see this paper
WIKIMATH Wikimath dataset of vital mathematics articles from Wikipedia. We made public during the development of PyTorch Geometric Temporal. The underlying graph is static vertices are Wikipedia pages and edges are links between them. The graph is directed and weighted. Weights represent the number of links found at the source Wikipedia page linking to the target Wikipedia page. The target is the daily user visits to the Wikipedia pages between March 16th 2019 and March 15th 2021 which results in 731 periods.
In terms of the data pre-processing, different from other experiments, we did not conduct feature and adjacency normalization, based on the default setting of the dataloader. In addition, for more appropriate comparison to show the DMD's advantages of the graph structure estimation, we also involved KNN graphs for some baselines, resulting in GCN-KNN and GAT-KNN. We generate the KNN graph following the setting in (Wu et al. (023a). Similar to the settings in the LRGBs experiment, we adapt the model architecture expressed in equation (33), and set -1 same as the one used in the initial node classification experiment. For all experiments in STGs, we let learning rate be 0.0005 and weight decay be 0.0001 with dropout as 0.8, and hidden dimension as 64. The
shows the difference in terms of graph adjacencies from the original graph (Chi chicko)p and DMD estimates.
C.4.2 INFLUENCE ON INFECTIOUS DISEASE EPIDEMIOLOGY
The estimated data-driven graph adjacency matrix from DMD plays important role in terms of infectious disease modeling. Specifically, the SIR model, which divides a population into three compartments: Susceptible (S())), Infected (T()),, and Recovered (R(()). The basic form of the SIR
25

---

Published as a conference paper at ICLR 2025
Adjacency
Adjacency Matrix
0.0
0.0
2.5
2.5
5.0
12.5
15.0
15.0
17.5
17.5
2.5
5.0
17.5
0.0
2.5
37.5
Medias
Figure 6: Heat plots of the original graph adjacency matrix (chickenpox) and DMD reconstructed adjacency matrix. One can check that although with the same number of eigenvectors (i.e., & = -- 1), compared to the original graph adjacency, DMD is able to deliver dense adjacency data-driven manner, e.g., historical records.
model as follows:
ds
dR di = -S(()(( di = - -
dI
~I(1,
(34)
di
where:
3 is the transmission rate, representing the rate at which susceptible individuals become infected through contact with infected individuals;
y is the recovery rate, representing the rate at which infected individuals recover and move into the recovered category.
We note that the SIR model we instanced here requires the dynamic of the disease spread in closed population, analogy to the diffusion process, which we assume the physics shall be operated with limited space. In addition, we will also assume that all individuals have the same probability to contracting with each other with any addition constraints. The transmission dynamics between nodes can be further described using adjacency matrix A, where Aij represents the transmission potential between nodes (individuals) and j. Accordingly, a spatial relationship based SIR model with the form dt
dS;
dI.
dR; dt
BS; Σ A.gh,
3S, A. 74, dt
744
(35)
static adjacency matrix A purely relies on geographic adjacency or predefined connections is often insufficient to capture the true dynamics of disease spread. As we have illustrated in Section 5.3 DMD) allows us to estimate a data-driven, time-evolving adjacency matrix from historical epidemiological data, reflecting changes in transmission dynamics.
C.5
LINK PREDICTION DETAILS
C.5.1 TASK INFORMATION AND DATA PRE-PROCESSING
Link prediction is binary classification task aimed at identifying whether connection exists between two nodes (Kipf Welling 2016). A pair of nodes with an existing edge is considered "positive link." categorized as class In contrast, node pairs without connecting edge are labeled as "negative links." corresponding to class O. Typically, the prediction process involves two phases: (1) an encoder is used to learn node embeddings based on the positive links; (2) decoder then predicts the presence of a link by calculating the inner product of the embeddings of node pairs. The dataset split at the edge level for training, validation, and testing. Specifically, 5% of the edges are randomly chosen as validation data, while 10% are used as test data. The remaining edges form the training set. These selected edges represent the positive links, and the negative links randomly sampled from pairs of unconnected nodes. The number of negative edges balanced with the positive ones, allowing accuracy to be used as the evaluation metric.
26

---

Published as a conference paper at ICLR 2025
Funcior Evelution
025
600
-0.0
-100
Figure 7: Iluustatioon on the power of PIDMD-GCN to capture the evolution of the quantum wave function. One that the estimated (blue) evolution generated from the PIDMD-GCN success- fully captured the original evolution of the wave function.
C.5.2 DMD-GNN IMPLEMENTATION AND HYPERPARAMETERS
In terms of the hyperparameters, since DMD-GNNs serve as the graph encoders in the link prediction task, we fixed most of the hyperparameters the same (including baselines) as the previous node classification tasks, except we let weight decay as 0.005, dropout as 0.7, and number of hidden dimensions as 16. We note that didn't 't use the ROC-AUC the evaluation metric as leveraged in Kipf& & Welling (0166), instead, we adopted the average accuracy.
C.6 DIRECT GRAPH AND PHYSICS INFORMED DMD
We deploy two types of DMD GNN models via directed and undirected graph Photo and CS, respectively (Lin & Gao 2023 Kipf & Welling 2017). The hyperparameters of both models are exactly the same as the node classification experiment.
C.6.1 PIYSICS INFORMED DMD AND PIDMD-GNN FOR SCIENCE
The attempt to develop PIDMD can traced back to the work Baddoo al. (0023). which if some characteristics of the operator in the original dynamic known (e.g., equation (15) ). it shall be
applied as a constraint to the DMD estimate. These constraints align the model with the fundamental laws (such symmetry, conservation laws, and self-adjoint properties) governing the system, leading to more reliable and noise-resilient predictions. PIDMD's s key advantage lies in its ability to enforce physical consistency, which improves generalization and robustness, especially when applied to well-defined physical systems.
PIDMD-GNNs may own the potential as tool for solving complex dynamic systems.
We provide simple example in the following section.
C.6.2 ILLUSTRATIVE EXAMPLE: SCHRÓDINGER EQUATION
In this example, we briefly discuss the power of PIDMD-GNN in terms of solving the time-dependent Schrödinger equation for a one-dimensional free particle, which can written as:
122 0²
ih D1
2m dx (I,
(36)
where we let (1 t) the wave function of the particle at the specific position at time f, and further denote f as the Planck constant, and m represents the particle's 's mass. To make a proper simulation of the equation,
let the number of nodes (particles) as 100, 2g = 2 the initial position of the particle. The real part of the wave function is set as Gaussian at Zo modulated by the cosine function the momentum. The imaginary part of the wave function is also Gaussian by sine
27

---

Published as a conference paper at ICLR 2025
function, which represents the phase of the quantum system. The real and imaginary parts of the wave function evolve according to the system's 's symmetric Hamiltonian operator, which can be analyzed as the graph adjacency matrix, ensuring that probability is conserved over time.
In terms of the graph construction, as our example is of a ID grid, each node is typically connected to its nearest neighborhoods. We leave the construction of the graph adjaceney for high dimensional physical system as a future work. In addition, in this illustration, we did not assign edge weights to the adjacency. Finally, the node features are the real and imaginary parts of the wave function. From Figure. 7 one can clearly see that PIDMD-GCN successfully captured the evolution of the more
wave function of the system (real part). However, whether PIDMD GCN remains powerful complex and long- snn-term evolved system is out of the scope of this work, we leave it as future works.
C.6.3 OPTIMIZATION WITHIN PIDMD
In this section, we briefly review the optimization process involved in both original DMD and PIDMD, review adapts the work in (Baddoo et al.) 2023). We recall that the DMD) algorithm is equivalent to finding the solution of the following optimization problem
arg min Sd
|| + 1) (H
(37)
However, when the information of the underlying physics is known, one may adopt the following
arg min
[H({e + 1) KL
(38)
KEM
where we denote M the generic condition for the potential compact manifold that contains the solution of all K. In this case, the problem in equation (38) serves as Procrustes problem, which seeks to find the optimal transformation between two matrices subject to certain constraints the class of
admissible transformations (Schönemann) 1966). The solution to equation (38) can be obtained by adopting the method developed in (Schönemann 1966) for orthogonality constraint, (Higham 1988) for symmetric constraint, and (Eldén & Park| 1999) for Stiefel manifold. In addition, one can also control the sparsity of K by incorporating the regularization of its norm, that is
arg min |[((e + 1) - (H(l) + |||2, KEM
(39)
and this aligns with the recent idea of controlling the sparsity of the transportation plan via optimal transport problem (Tianlin Liu 2023). Lastly, as we have mentioned in Section g we are also
interested in assigning the so-called coupling condition to K, yielding
arg min
[H(e+ + - KH(O)rr
(40)
K1=,,K 1=
and since H(L ([e++) 1) and (e) are graph observables, this indicates that the classic OT problem might GNN convolution via a dense graph (i.e., K). This assumption is reasonable due to the fact that OT finds the optimal solution between distributions, the transportation from the source to the target can be sparse as one-to-one or dense as me-too-many In more general, under the OT scope, one can even drop the square condition of K, since the number of elements of the source can be different compared the elements in targets. This could own the potential of defining a new branch of DMDs with system states via different dimensions. Lastly, if H(E + 1) and (&) are sourced from the different graph, then the above equation means that there shall be a convolution (using K), under the scope of OT, to transport one feature matrix to another. This might be of interest in terms of knowledge graph alignment (Zeng et al. 202T). We leave these exciting topics to the future works.
be able be interpreted
D FINAL REMARKS AND FUTURE RESEARCH DIRECTIONS
Insufficient Feature Dimension In some cases of our initial tests, we found that DMD showed limited performance when the feature dimension of the graph was low. That is, the feature information is not rich enough, and this leads to a limitation of our model and good standing point for developing more complete DMD variants for dealing with this situation. Fortunately, in most of our included experiments, DMD-GNN performed fairly well compared to the baselines, even with lesser filtering
28

---

Published as a conference paper at ICLR 2025
parameters. This could be due to its data-driven nature to refine the eigenspace (i.e., v) from the system snapshots.
From Figure 4 although the ranks leveraged in different graphs different, from our empirical observations, graphs with similar characteristics are more likely to share similar truncation rates. For example, for homophily graphs, we observed that Ç = 0.85 often achieves the best learning accuracy, whereas for heterophilic graphs, Ç = 0.7 is the selected rate for all graphs. This unified quantity of g in different types of graphs may be due to the nature of their homogeneity (citation graphs). However, to sufficiently determine the suitable truncation rate for any given dataset is a challenging problem not only for DMD-GNN but also for other SVD-related tasks. We kindly leave it to the future works.
Information Integrity Similar to the above discussion, one can also observe that in tasks where DMD-GNNs serve as an intermediate module for the downstream task, e.g., link prediction, the OMD-GNN-based models sometimes underperform their original model, e.g., GCN vs. DMD-GCN. This phenomenon leads us to explore the truncation process in DMD in the future, or in other words, what information shall be preserved/ignore.. We suppose this may heavily depend on the type of downstream tasks, e.g., whether the encoded feature generated from DMD-GNNs is still distinguishable from each other via the classification tasks. Furthermore, the construction of the node feature differs between datasets, making it even more difficult to sufficiently quantify and analyze the above challenge. We suppose the analysis could merely conducted on the synthetic datasets (e.g.. from the Contextual Stochastic Block Model (CSBM)) where features are sampled from pre-defined distributions, and the results shall be cedistica--relatte (Wu al. 2023b).
Graph Classification and Expressive Power Although our experiment did not run into the graph classification tasks, one can still check that our model outperformed the GIN model with is proved to have maximal expressive power (Xu et al. 2019b) via the node classification task (e.g., Table I In addition, another reason for the absence of the graph classification is due to the fact that similar to the settings in link prediction, in graph classification, one also consider DMD-GI GNNs as an encoder prior to those so-called readout layers such as maximal and average pooling (Zhang et al. 2023). Similar to discussion on the information integrity paragraph, we shall be focusing on the interactions between DMD-GNN outputs and the downstream calculations. Although DMD-GNNs can inherit many advantages from the original GNN dynamics, fully quantifying its impact on various downstream tasks requires an ideal control of the settings of each module of the model and various data inputs. We aim to provide new insights into this direction. Such investigations will likely lead to novel designs that further enhance DMD-GNN capabilities for a broader range of graph-based learning tasks.
Adopting DMD to More Complex Dynamics Another interesting field in which DMD-GNNS can be applied is the learning tasks on physical and chemical dynamics, e.g., molecular dynamics (Xu) eet al. 2024) and quantum (or standard) many-body problems (Satorras et al. (202T) in which the main task is to simulate and predict the particles' position and feature changes through the evaluation of the system. Many recently developed methods tend to construct the graph (e.g.. for the molecules)
via a combination of KNN and its original topology, and such graph connectivity remains unchanged through the rest of the simulatioo/preeditionn Although many physical/chemistry inductive biases have been introduced, a data-driven approach that generates suitable graph structure that fits the propagation defined in the relevant models remains insufficiently explored, A deeper reason for this could refer to the changes in the compound structure due to the changes in its energy (c.g., Gibbs free energy). This alignment may lead to a deeper insight into the relationship between numerical data-driven methods in machine learning and actual chemical/physical laws. We also expect to conduct our research in this field in our future research.
29


Reviews:
[{"review_id": "mbvJPy6fTG", "reviewer": "Reviewer_RmcR", "summary": "It presents an approach that integrates Dynamic Mode Decomposition (DMD) with Graph Neural Networks (GNNs), resulting in DMD-GNN models. These models are designed to capture the principal components driving the underlying complex physics on graphs, thereby enhancing feature propagation and reducing computational costs. The paper also explores the potential of incorporating additional constraints on DMD and deploying physics-informed DMD for directed graphs, indicating a range of future research directions at the intersection of DMD and GNNs.", "questions": "Eq(12) and Line 237, which is correct? K = ?\n\nWhat is the W(l) in Eq(14)?\n\nLine 280: Could you please elaborate on the usage of the rate? \n\nYou explained what o() is in Eq (15), but what is Df(0)?\n\nIn Lemma 1, what is X? should be X(l)?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "By integrating DMD with GNNs, the paper provides a new perspective for capturing dynamic patterns in graph data, which could be important for understanding dynamic behaviors in complex network structures.", "weaknesses": "The main proof is very similar to the proof in \"Data-Driven Linearization of Dynamical Systems.\" \n\nAlthough the paper proposes the DMD-GNN model, it does not explicitly elaborate on the relationship between the Koopman operator and graph neural networks in the first chapters, which may affect the reader's understanding of the theoretical foundation and the perceived innovativeness of the model.\n\nAlthough the paper points out the DMD-GNN's application in multiple learning tasks, it does not discuss the model's potential and challenges in specific fields (such as bioinformatics, social network analysis, etc.). \n\nThe experimental results are not convincing; for example, in Table 1, some of the best results are close to simple MLP's performance. Besides, it only solves some very traditional classification problems in the experiments.\n\nThe analysis of the new approach on graph subclasses (e.g., sparse, dense, small-world, etc.) is insufficient. \n\nSummary of the Model Procedure: From Line 291 to Line 293 is unclear.", "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": "", "extra_scores": {}}, {"review_id": "xhCHr0TJ7j", "reviewer": "Reviewer_3qZf", "summary": "The paper explores the relationship between Graph Neural Networks (GNNs) and Dynamic Mode Decomposition (DMD), proposing DMD-GNN models that enhance GNNs' ability to capture complex interactions in graph data through low-rank approximations of dynamic operators. The authors establish a theoretical connection between GNNs and the Koopman operator via DMD, reducing the number of learnable parameters and computational complexity. Experimental results demonstrate that DMD-GNNs achieve superior performance on various tasks, including node classification and link prediction. This work highlights the potential of integrating DMD techniques into GNN frameworks to improve their performance and applicability.", "questions": "I’m confused about the implementation details of the model, as the paper provides limited description in this part. Standard DMD requires explicit eigendecomposition, and I would like to know how $\\Psi$ and $\\theta$ are determined in Equation 14.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written and easy to follow, providing a thorough introduction to the backgrounds of GNNs and DMD. This clarity enhances the reader's understanding of the foundational concepts necessary for grasping the main contributions of the work.\n2. Connecting DMD with GNNs is an interesting perspective.\n3. The authors support their claims with extensive experiments demonstrating the effectiveness of the DMD-GNN models, including evaluations on directed graphs, large-scale graphs, long-range interactions, and spatial-temporal graphs.", "weaknesses": "1. My main question regarding the paper concerns the 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?\n2. 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.\n3. 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.", "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": "", "extra_scores": {}}, {"review_id": "MSzqZuCDmF", "reviewer": "Reviewer_33PK", "summary": "This work draws a connection between the feature dynamics in GNNs to DMD (a numerical method for Koopman theory). They use this connection to build a novel GNN architecture, which can be used across tasks --- node classification, node regression, link prediction --- and data settings. They validate this architecture with extensive numerical experiments.", "questions": "**The unique benefit of DMD-GNN**\n\nI am really looking for setting which can show the *unique* benefit of DMD-GNN. The authors have gone through extensive derivations and work to derive DMD-GNN. What can it do that a generic, off-the-shelf, large GNN simply cannot do? What tasks does it make significantly easier (perhaps beyond just the final metric going up a bit). Can the authors think of any applications, and ideally datasets, for this purpose? Perhaps data generated from systems closer to how DMD/Koopman theory is typically used would be a nice direction.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is generally well written. I particularly like the high level layout; the section titles lead the reader along nicely; 'How GNNs Resonates with Dynamic Systems' is a particularly nice one :)\n\nI like that it brings the solidity of DMD and merges it with a learning architecture; which I believe to be mostly original (although out of my expertise). I think it could be useful in real physical systems. I understand the authors use publicly available and widely known datasets out of necessity in proceedings like this, but I would think the work would present even stronger if there were physical systems datasets to validate on. See more on this in 'Questions'.", "weaknesses": "**Clarity of Derivation for Non-Experts**\nI did have a bit of trouble following the derivations in Section 4 and 5; I am not a super GNN expert, nor a dynamics systems expert, so this could be on me. I believe this work will be at a disadvantage in an ICLR-like review process bc it truly lies at the intersection of two fields which are typically distinct. I attempt not to punish this work for this valiant effort/approach, but 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 section 4. Figure 1 covers some, but not all, of this.\n\n&nbsp;\n\n**Scalablity**\nAdditionally, 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.\n\n&nbsp;\n\n**Runtime**\nI 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?", "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": "", "extra_scores": {}}, {"review_id": "yNZArLsS7d", "reviewer": "Reviewer_WY5R", "summary": "This paper provided a novel connection between dynamical mode decomposition and graph neural network. Starting from considering the feature propagation as a dynamical system, authors took advantages of Koopman theorem and DMD in practice to refine this process. They also provided theoretical analysis to state the properties of the model. The results showed consistent improvement of combining the existing models and the DMD module.", "questions": "1. In Koopman theorem, it states that \"a linear process can be found in the infinite-dimensional space\", while for the proposed model, the authors used DMD method to imitate this, so only a finite dimensional space is constructed. It means that some information will be ignored. Will this method affect the performance of a more complex dataset? In your experiments, are the ranks different in different datasets? How do you decide the number of filters?\n\n2. In the result table 3, when you compare the results of GCN and DMD-GCN, one can observe that the performance is not improved in all columns. Can you have some additional explanations on what features benefit or \"destroy\" the model? As I pointed out in the weakness, the model's motivation should be explained by the results.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provided enough details and derivation to explain the proposed model.\nThe results proved that with refined features, GNN performance can be improved. Therefore, physics-informed or biological-plausible systems can be further developed based on this structure.", "weaknesses": "1. 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.\n2. The motivation of this paper should be expanded. As 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 it benefits the performance.\n3. It would be much clearer if authors could highlight the algorithm of the model.", "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": "", "extra_scores": {}}, {"review_id": "VvslK34LTA", "reviewer": "Reviewer_EfEy", "summary": "The authors investigate GNNs from the perspective of Koopman theory. They use dynamic mode decomposition (DMD) to approximate the Koopman operator with a finite dimensional matrix. Based on this they propose Graph Neural Network (GNN) models using the low-rank eigenfunctions given by DMD. They compare their model to state of the art GNNs in extensive experiments on several learning tasks, in which the DMD GNNs achieve competitive results.", "questions": "a) How many hidden nodes were used in the baseline models for node classification? Can you include a comparison of the number of model parameters?\n\nb) The link prediction VGAE framework is not state-of-the-art, why did you use it and not SEAL?\n\nc). For link prediction you used average accuracy instead of ROC-AUC. Why?\n\nd). Why was ChebNet only used for spatial-temporal dynamics experiments?\n\ne) Why did you use the parameter \\xi = 0.85 for homophilic graphs but the sensitivity analysis was perfomed only up to \\xi = 0.8?\n\nf). Could it be interesting to use other discretization methods than Euler?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The background of Koopman theory and DMD is well explained in  section 3 and 4.\n2) The authors made extensive experiments and effort to validate their models.\n3) To the best of my knowledge the idea presented is novel.", "weaknesses": "Major:\n\n1) 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.\n2) The proposed model is not compared to GIN, although it is maximally expressive.\n3) 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.\n\nAmbiguities:\n\n4) The sentence on attention-based GNNs (l. 90-93) is a little bit confusing\n5) in line 411, you are listing ACMP as a baseline model but it is not occurring in the tables.\n6) APPNP is not cited anywhere and explained what the abbreviation means\n\nMinor:\n\n7) The related work section is very general, the differentiation to previous work is unclear.\n8) The equation in line 133 is probably wrong, because it would lead to K = 1. Should probably be the linearity of K_t?\n9) Line 237: K = M*F would mean that M = 1? Probably a mistake?\n10) Please briefly mention the results of App. C.2.4 in 7.2\n11) KNN abbreviation in line 466 was not defined\n12) Line 234: The pseudo-inverse of H(l) has already been defined in line 227, and it is not even occurring in Eq. (11)\n13) Please divide Figure 2 in a and b\n14) Fig. 2 is much too small\n15) First sentence in 7.1 is confusing.\n\nSpelling/Grammar:\n\n16) line 146: underlying\n17) Headline 4: How GNNs Resonate with Dynamic Systems\n18) Table 1: Caption should state that the results are from node classification experiments. Point is missing at the end of the caption.\n19) line  523-524, grammatic error", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)