State Space Models on Temporal Graphs: A First-Principles Study
Authors: Jintang Li
Ruofan Wu
Xinzhou Jin
Boqun Ma
Liang Chen
Zibin Zheng
Venue: NeurIPS 2024 poster (2024)
Keywords: temporal graph learning; state space models; graph neural networks
Primary area: graph_neural_networks
TL;DR: We introduce a conceptualized GHiPPO abstraction on temporal graph and propose GraphSSM as a flexible state space framework for learning discrete graph sequences.

Abstract: Over the past few years, research on deep graph learning has shifted from static graphs to temporal graphs in response to real-world complex systems that exhibit dynamic behaviors. In practice, temporal graphs are formalized as an ordered sequence of static graph snapshots observed at discrete time points. Sequence models such as RNNs or Transformers have long been the predominant backbone networks for modeling such temporal graphs. Yet, despite the promising results, RNNs struggle with long-range dependencies, while transformers are burdened by quadratic computational complexity. Recently, state space models (SSMs), which are framed as discretized representations of an underlying continuous-time linear dynamical system, have garnered substantial attention and achieved breakthrough advancements in independent sequence modeling. In this work, we undertake a principled investigation that extends SSM theory to temporal graphs by integrating structural information into the online approximation objective via the adoption of a Laplacian regularization term. The emergent continuous-time system introduces novel algorithmic challenges, thereby necessitating our development of GraphSSM, a graph state space model for modeling the dynamics of temporal graphs. Extensive experimental results demonstrate the effectiveness of our GraphSSM framework across various temporal graph benchmarks.

State Space Models on Temporal Graphs: A First-Principles Study
Jintang Li Ruofan Wu Xinzhou Jin', Boqun Ma², Liang Chen ; Zibin Zheng' Sun Yat-sen University, *Coupang, "Shanghai Jiao Tong University
{lijt55, j 1inxzi5mmmaaiiiii sysu, edu. en, (wwruofan1989 {chenliang6, zhzibin) baaiiiainmmmm.l.mmmmmm "omail.syse sysu. edu. cn}
Abstract
Over the past few years, research on deep graph learning has shifted from static graphs temporal graphs response to real-world complex systems that exhibit dynamic behaviors. In practice, temporal graphs are formalized as an ordered sequence static graph snapshots observed at discrete time points. Sequence models such as RNNs Transformers have long been the predominant backbone networks for modeling such temporal graphs. Yet, despite the promising results, RNNs struggle with long-range dependencies, while transformers burdened by quadratic computational complexity. Recently, state space models (SSMs), which are framed as discretized representations of underlying continuous time linear dynamical system, have garnered substantial attention and achieved breakthrough advancements in independent sequence modeling. In this work, undertake principled investigation that extends SSM theory to temporal graphs by integrating structural information into the online approximation objective via the adoption of a Laplacian regularization term. The emergent continuous-time system intro- duces novel algorithmic challenges, thereby necessitating our development of GRAPISSM,, a graph state space model for modeling the dynamics of tempo- ral graphs. Extensive experimental results demonstrate the effectiveness of our GRAPHSSM framework across various temporal graph benchmarks.
1 Introduction
As a class of neural networks designed to operate directly on graph traph--stuctured data, graph neural networks (GNNs) [21, 43, 24] have achieved remarkable success and have established new state-of- the-art performance across a broad spectrum of graph-based learning tasks [19]. While significant progress has been made in researching static graphs, many real-world networks, such social, traffic, and financial networks may exhibit temporal behaviors that carry valuable time information [20, 23]. This gives rise temporal (dynamic) graphs, wherein the nodes and edges of the graph may undergo constant or periodic changes over time. In applications where temporal graphs arise, modeling and exploiting the dynamic nature of the continuously evolving graph is crucial in representing the underlying data and achieving high predictive performance [22, 44, 41].
Learning over temporal graphs is typically approached sequence modeling problem in which graph snapshots form a sequence [34]. This often involves challenges related to long graph sequences and scalability issues [25]. Recurrent neural networks (RNNs) [46, 18] have historically dominated sequence modeling over the last years. However, they have long been plagued by poor capability in modeling long sequences due to rapid forgetting. This hampers their performance in temporal
'Equal contribution. CCorresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

graphs that require broader context or longer time window to capture relevant dependencies and patterns. Recently, the advancement of Transformers [42] has led shift in this paradigm, given their superior performance. Yet, Transformers also struggle with long sequence learning because the computational and memory complexity of self-attention is quadratically dependent on the sequence length. The overwhelming computation and memory requirements/costs associated with Transformers makes them less applicable in practical applications handling long-term sequences [51].
Recently, state space models (SSMs) have emerged as a powerful tool for sequence modeling [11, 13, 29, 40, 6, 10]. The salient characteristic that distinguishes state space models as particularly compelling is their conceptualization of sequential imputs as discrete observations from an underlying process evolving in continuous time, which naturally arises in scenarios such as speech processing [40] and time series analysis [49]. SSMs sustain a latent state throughout an input sequence and formulate state update equations through the discretization of an underlying linear dynamical system (L.DS). Owing to their invariant state size, SSMs exhibit an efficient inferential time complexity, akin to that of RNNs. Simultaneously, they overcome the long-range modeling deficiencies inherent to RNNs through meticulous initializations of state matrices which are theoretically shown to achieve an optimal compression of history [11].
Temporal graphs often manifest as discrete snapshots capturing the evolution of an underlying graph that inherently dynamic and continuous in nature [20]. In this context, the SSM methodology could be appropriated as foundational primitive for temporal graph modeling. However, SSMs are predominantly architected towards independent sequence modeling. Hence, the task of systematically incorporating time-varying structural information into the SSM framework poses significant chal- lenges. Specifically, remains unexplored as whether the foundational methodology of discretized LDS is readily applicable to the domain of temporal graphs.
In this work, we advance the SSM methodology to encompass temporal graphs from the first principles. Rather than presupposing the evolution of the underlying temporal graph, we dive into the fundamental problem of online function approximation that underpins the theoretical development of SSMs for sequence modeling [11]. By solving a novel Laplacian regularized online approximation objective, we derive a piecewise dynamical system that compresses historical information of temporal graphs. The piecewise nature of the obtained continuous time system poses new challenges toward discretization into linear recurrences, thereby motivating our design of GRAPHSSM, a state space framework for temporal graphs. The main contributions of this work are summarized as follows:
We introduce the GHiPPO abstraction, a novel construct predicated on the objective of Laplacian regularized online function approximation. This abstraction can alternatively be conceptualized as a memory compression primitive that simultancously compresses both the feature dynamics and the evolving topological structure of the underlying temporal graph. The solution to GHIPPO is characterized by a dynamical system that is piecewise linear in node feature inputs.
We introduce GRAPHSSM, flexible state space framework designed for temporal graphs, which effectively addresses the key algorithmic challenge of unobserved graph mutations that impedes the straightforward discretization of the GHIPPO solution into (linear) recurrences through employing a novel mixed discretization strategy.
Experimental results on six temporal graphs have validated the effectiveness of GRAPHSSM. In particular, GRAPUSSM has the advantages in scaling efficiency compared to existing state-of-the- arts, which can generalize to temporal graphs with long-range snapshots.
2
Related work
2.1 Temporal graph learning
major branch of temporal graph learning methods consists of snapshot-based methods, which handle discrete-time time temporal graphs by learning the temporal dependencies across a sequence of time-stamped graphs. Early works mainly focus on learning node representations by simulating temporal random walks [39] or modeling the triadic closure process [50] on multiple graph snapshots. These methods typically generate piecewise constant representations and may suffer from the staleness problem [20]. In recent years, the most established solution has been switched to combine sequence models (e.g., RNNs [46] and SNNs [38, 8)) with statie GNNs to capture temporal dependencies and correlations between snapshots [47, 34, 39, 25J. To better translate the success achieved on static

---

graphs in both their design and training strategies, recent frameworks such as ROLAND [48] and its variants [53, 17] have been proposed repurpose static GNNs to temporal graphs. There is another important line of research that focuses on continuous-timg temporal graphs, we kindly refer readers to [27] and [20] for comprehensive surveys on this research topie.
2.2 State space models
State space models (SSMs) have historically served as pivotal tool in fields such as signal process- ing [30] and time series analysis [3]. recent advancements, they have also seen active adoption as a layer within neural sequence modeling frameworks [11, 13, 29, 40, 10]. The linear nature of SSMs confers several significant advantages. Key among these is the conter-controlled stability that enables effective long-range modeling through careful initializations of state space layer parameters [11, 31 ]1], with the most representative method being HiPPO [11], a theory-driven framework notable for its optimal memory compression on continuous sequence inputs. Moreover, the computational efficacy of SSMs notably enhanced through the use of techniques such as convolutions [13, 6] or parallel scans [40]. The promising properties of SSMs also attracts further explorations graphs [2].
Comparison. The usual paradigms for designing sequence models over graphs involve recurrence (e.g. RNNs [46]), integrate-and-fire (e.g. SNNs [38, 8)). or attention (e.g. Transformers [42]), which each come with tradeoff's [14]. For example, RNNs are a natural recurrence model for sequential modeling that require only constant computation/storage per time step, but are slow to train and suffer from the rapid forgetting issue. This empirically limits their ability to handle long sequences. SNNs share a similar recurrent architecture with RNNs while using 1-bit spikes to transmit temporal information, which would sacrifice expressivity and potentially suffer from optimization difficulties (e.g., the "vanishing gradient problem") [26]. Transformers encode local context via attention mechanism and enjoy fast, parallelizable training, but are not sequential, resulting in more expensive inference and an inherent limitation on the context length. Compared to the aforementioned architectures, SSMs particularly the promising Mamba (S6) model [10], offer advantages such as fast training and inference, along with fewer parameters and comparable performance. These characteristics make SSMs particularly well-suited for sequence modeling, even (or especially) on extremely long sequences. Comparisons among these architectures illustrated in table 1
Table Comparisons of different neural network architectures for sequence modeling.
RNNs [46, 4, 18]
SNNs [38, 8]
Transformers [42]
SSMs (S6 [10)
Training Inference
Slow Fast Medium
Slow
Fast
Fast
Fast
Slow
Fast
Para. Size
Extremely small
Large si d
Small
Performance
d
Limitations
Forgetting
Vanishing gradients
Mem. Time: O(n")
?
The GRAPHSSM framework
The primary motivation our framework is the fact that discrete-time temporal graphs sequential observations of an underlying temporal graph that evolves continuously. Adopting this functional viewpoint, we will first develop piecewise recurrent memory update scheme in section 3.1 that optimally approximates the underlying continuous- time temporal graph, utilizing novel extension of the HIPPO abstraction to graph-typed inputs [1]]. The pro- posed framework retains many nice properties of HIPPO while posing the new challenge of unobserved graph mu- tation when handling discretely-observe which we analyze section 3.2 and propose a mixing mechanism to improve the recurrent approximation. Fi- nally, we present GR GRAPHSSM framework section 3.3. An overview of GRAPHSSM is shown in figure 1.
Feature Mixing
K
Graph
x X
Graph Conmiition
(OON, GAT. SADE,
Lineor
observations,
Convelator
SGM
54
Output
Figure 1: GRAPHSSM framework.
3

---

3.1 GHIPPO: HIPPO on temporal graphs
Setup. We fix a time interval [0, T). temporal graph on [0, T) is characterized by two processes G and X: For each t E [0, T) the process G maps t to graph object G(t)) = (t) Et)). We assume the node process (t) to be fixed over time, i.c. (t) = V,t E [0, with Ny = V and discuss
the case for varying node processes in appendix B.2. The edge process (i()) is piecewise-constant process with a finite number M of mutations over [0, 7] that are described via a sequence of events:
8 {E,, . E with each E. (um, Um tmm am)) 1 m M.
(1)
Each event Em constitutes an interaction between node pair (um, Um) at time fm with action am. the action could be either insertion or deletion. The evolution process is thus depicted as the following:
((O) S G(4) E G(12) -
G((M-1) EMs, G((M) G(T)-
(2)
The process X maps to a node feature matrix (()) E RNvxd with feature dimension d. Throughout this paper, it is often helpful to view G and X as graph-valued and matrix- functions. In typical discrete-time temporal graph learning problems, the underlying graph is observed at timestamps Ti...., TL with time gaps A 7 7- 2 S / L. The observations thus form a sequence of snapshots (G(n), (((m))(()))))) ((r)hsis which are abbreviated as [GI.L, X1 Notably, the observation times are usually interleaved with the mutation times, resulting in the majority of mutation times re- main unobserved. This situation presents significant challenges in effectively modeling the dynamics of graph evolution, topic that will be further explored subsequently.
The HiPPO abstraction. Algorithmically, the goal of continuous-time dynamic modeling is to design memory module that optimally compresses all the historical information [11]. Under the context of univariate sequence modeling, the HIPPO framework [11] formalizes the memory com- pression problem into online approximation problem in some function space and derives HIPPO operators under specific types of basis functions, among which the HIPPO-LEGS configuration has become the state-of-theeart in state-space sequence modeling paradigms [13, 40J. However, naively extending HIPPO abstraction to graph learning scenarios (via treating node features as inputs) could be deemed inadequate since HIPPO handles distinct inputs independently, without the capability to incorporate the interconmectivity information among various inputs which could potentially enhance the efficiency of memory compression. For illustrative purposes, in instances where input observa- tions are noisy, the exploitation of neighborhood information has the potential to facilitate a denoising step, as evidenced in image processing applications [33] and semi-supervised learning primitives [52, 45]. To systematically utilize the connectivity information, we propose new approximation paradigm, the aaaplacian-regularizzn frameworks. Formally, we start with the simple setup with d = 1, i.c., each node possesses a scalar feature, and we propose an approximation scheme that simultaneously approximates the history of all the Nv inputs up until time t, i.e., {X(s), E [0. t|} using their corresponding memories at time t, E R Ny according to the following objective time t:
online approximation that extends HIPPO to graph modeling
i... Z(t) (2)(e))
C, = J. [x(ss - Z(s) 1 dur(s) + a S. Z($) L(s)
(3)
Here a >> O is a balancing constant, ir is time-dependent measure that is supported on the interval [0, f] which controls the importance of various parts of the input domain' and L(t) is normalized Laplacian at time t, which allows definition such as the symmetric normalized Laplacian Lsym(s) I D(s))111 A// D(s) 1/2 where D(s) is a diagonal matrix whose diagonals are node degrees, or random walk normalized Laplacian L I D(s) Ass). The objective (3) is understood as the ordinary HiPPO approximation objective augmented with a regularization component that encourages the smoothness of memory compression with respect adjacent nodes." The imposition of smoothness constraints commonly emerges as a beneficial relational inductive bias in the context of graph learning [1]. By leveraging the data from adjacent nodes, can potentially achieve more effective denoising effect during the process of node memory compression. To specify
TTechnicall,, we require Z and X to reside within some appropriately defined Hilbert space. A comprehensive treatment will be provided in appendix C.
"To be more precise, at any time s E [0,t], the integrand 2ss) (ss) attains its minimum when (s) satisfies certain smoothness criterion which is determined via the choice of graph Laplacian. A more detailed explanation is deferred appendix B.I.
L(s)2(s) inside the second term of (3)

---

Unobserved
Unobserved G(4)
((0)
((t.) ((t))
G(tt)
((4)
f f2
fs
G(0)
((t))
6g ((t))
Figure 2: Illustrative example of the unobserved graph mutation issue. In this example, the underlying graph is observed at time points TI, T2, 73 with two unobserved mutations between (TI,72) and one between [T2, Ts). These unobserved mutations result in temporal dynamics that inconsistent across the observed intervals, thereby complicating direct applications of ODE discretization methods such the Euler method or the zero-order hold (ZOH) method.
a suitable approximation subspace for memories Z, we adopt the approach of HiPPO that uses some N-dimensional subspace of polynomials which we denote as Pv- Now we define a graph memory projection operator GPROJ; that maps the temporal graph up until time t to a collection of Ny polynomials with each one lies in PN, i.c.
GPROJ, (G,
arg min L, C,), ZPN YOEV
We further define a coefficient operator COEF; that maps each polynomial in the collection in (4) the coefficients of the basis of orthogonal polynomials defined with respect to μ4, the following definition formalizes our extension of HIPPO to continuous- temporal graphs which we term GHIPPO:
Definition (GHIPPO). Given continuous -iemm temporal graph (G, X), time varying measure family μr, an N N-dimensional subspace of polynomials Px, the GHIPPO operator at time I is the composition GPROI, and COEF, that maps the temporal graph and node features a collection of projection coefficients (L) E Ny xN or GHIPPO (G, X) COFF, (GPROJ, (G,X)) X))-
The most favorable property of the HIPPO framework on independent inputs is that the outputs of HıPPO operators are characterized via a concise ordinary differential equation (ODE) that takes the form of linear imme-inarrant state space model (LTI-SSM). The following theorem states that most of the desirable properties of HиPPO are retained by GHIPPO except for the LTI property:
Theorem Let G evolve according to (2). Taking μr to be the scaled Legendre measure (LegS) with
14 1 (o where T(o,a) stands for the indicator function of the interval [0, t), the evolution of the outputs of GHIPPO operator is characterized by M ODES according to mutation times as follows:
dU U()AA + (T al(())
15 S M, E (m))
(5)
dt
where A E NXN and B E Nx1 takes the same form as in the H1PPO formulation [11]:
(2n 1)(2k +1)
if k, ifn k, in < k,
Ank
n+1
and B, = v2 21 (6)
According to theorem 1, the solution (5) is LTI over each interval [Im (m41) during which the graph structure remains fixed. This property further extends to piecewise LTI perspective over the interval [0,2], Moreover, we may view the solution (5) as a two-stage procedure that could be intuitively described as ceffuse--heenupaee an initial diffusion operation is applied to the features of the input nodes, succeeded by an update to the memory of these nodes.
Specifically, this procedure entails a sequential execution, wherein
3.2 Unobserved graph mutations and mixed discretization
Theorem establishes an analogue of HiPPO theory on temporal graphs. It is straightforward to verify that most of the subsequent refinements of HiPPO apply to GHiPPO as well. Among
5

---

these we will utilize the popular technique of diagonal state spaces [15, 12] that simply sets A as diagonal matrix with negative diagonal elements". To apply the GHiPPO framework to discrete-time temporal graphs, a critical step is to develop discretized version of (5). However, unlike ordinary H1PPO where we can use standard discretization techniques of ODEs to discretize L.TI equations, the GH1PPO ODE contains discontinuities that correspond to mutation times of the underlying temporal graph, which are often not observed given only access to a list of snapshots. This issue of unobserved dynamics complicates the development of a viable discretization scheme for GHIPPO, as is pictorially illustrated in figure 2. To devise a solution to this challenge, we start by analyzing a hypothetical oracle scenario in which all mutations observable.
An oracle discretization. We consider a time range [7-1. Ti) between the 1 1th and the Ith snapshot, and assume there are altogether M, mutation events (Etihhsss M, happened during this period. Let GL.0 = Gi-1 the graph snapshot at 77-1, the following process describes the structural evolution inside the interval 7:):
G G1,0 3 G1,1 LL3 G12 -1
E1,M4 GL.M; = Gt
(7)
Next, we derive discretization formula under the strategy of zeroth-order-holl (ZOH). We assume that all intermediate mutations are observed, with the node features staying fixed between mutations, i.e., (1) X & E [|,,5-1, The following theorem characterizes the resulting state evolution: Theorem (Oracle discretization of (5)). Assume A is a diagonal matrix with negative diagonals, for any 1 < 1 < L. Let Lt,s be some Laplacian of Gt. we have the following oracle update rule:
Mi
Ul Ui= + XX -
A- X
2I++
",,,A,"
(8)
where Uj E N. XN denotes the discretized state at step with U, = O. For each 1 S <I$L, M, Ar NxN non-negative diagonal matrices with values depending only the mutation times, which satisfy E A; I.
Mixed discretization. According to (8). given all the (unobserved) mutation information, the state update rule is equivalent to applying ZOH to X₁ which is an element-wise convex combination of all the diffused node features. In practice, among all the components of X, we only have access to Xi-1, X1, GI-1, Gi with the rest left unobserved. Therefore, propose mixed discretization as an approach to approximate X₁. Specifically, we introduce the following mechanisms:
X10) GNNa (Xi, Gi),
(ordinary ZOH)
X GNNo (MIX (X Xi),
(feature mixing)
X = MIX; (GNN, (X1-1, G1-1), GNN, (X1, Gi)),
(representation mixing)
which are compositions of inter-node mixing (a consequence of diffusion) and intra-node mixing (mixing node features of consecutive snapshots). For the process of inter-node mixing, we opt to approximate the diffusion operation with learnable shallow graph neural network (typically 1-layer GNN) parameterized by 0 to alleviate the computation burden and improve flexibility detailed discussion considering the relation between certain GNN formulations and the choice of Laplacian is presented in appendix B.I. In the context of intra-node mixing, we introduce a MIX module parameterized by e to merge either consecutive node features (as illustrated in (feature mixing)) or consecutive node representations produced by the GNN model (as illustrated in (representation mixing)). In this paper, we assess two simple MIx instantiations: Convolution with kernel size of 2 (CONv ID) and gating mechanism that interpolates between the two inputs (INTERP). We postpone a comprehensive description of the mixing methods to appendix D. The resulting discretized system is presented the following matrix-valued state space model:
U1 = U1-1eAA + (, BT
with XP {
E
((0)
: X1
S(F)
.SSISL. ]
((R)
(9)
U.C..
'More concretely, diagonal SSMs are defined by diagonal A matrices whose diagonal elements lie on the complex plane with negative real parts [12]. yet recent developments have found that complex state matrices often not necessary [10]. For ease of representation, we only explore real state matrices this paper. "We let the balancing constant be absorbed into the learnable parameters. Indeed, for GNNs that employ asymmetric aggregation [16], it is plausible conceptualize the GNN engaging form of auto-balancing

---

When exact timestamps for snapshots are unavailable, we use the adaptive time step strategy as in [11, 10] that models A a 1-dimensional affine projection of the inputs followed by a non-negative activation like softplus. Finally, we utilize the approximation A- (cSA - -1) AT for diagonal As, and equip the system with output Y with state projection matrix C E R
3.3 The GRAPHSSM framework
Having established the SSM equation (9), we are ready to introduce our main framework GRAPHSSM. In alignment with conventional design paradigms in the SSM literature, we define a depth- GRAPHSSM model through the sequential composition K GRAPHSSM blocks, with each block characterized as follows:
H 1 =a (SSMLAYER (H(L"",,..L)) LINEAR (H . .15ksk, (10)
Gr.z))
where we use Hi- to denote the concatenation of the hidden representation depth & of all the snapshots along the sequence dimension and H are the node features XI.L. The GRAPHISM blocks, as outlined (10), incorporate an SSM layer that operates on graph snapshot inputs. This followed by the application of nonlinear activation and the integration of residual connection which we denote as the addition a linear projection of inputs with Linear denotes a linear projection layer that ensures dimension compatibility.
GRAPHSSM-S4. The architectural formulation of the SSM layer essentially involves the expansion of the one-dimensional recurrence, as specified in (9), to accommodate general dimensions, i.e., > 1. This expansion is achieved a straightforward manner by utilizing an individual SSM for each dimension. Consequently, the emergent SSM layer adopts a Single-Input, Single-Output (SISO) configuration. Such design is intuitively understood as the graph learning analogue of S4 [13], which we term GRAPHSSM-S4
GRAPHSSM-S5 and GRAPHSSM-S6. In addition the SISO implementation, we further introduce two variants within the GRAPHSSM framework. The first alternative represents a Multiple-In Input, Multiple-Outppe (MIMO) extension of (9), wherein a single SSM system applied across all dimensions. This variant serves as graph-informed analogue to the S5 model [40]. The second variant extends the S4 model by facilitating input-controlled time intervals and state matrices (A, B, and C). This innovation yields a selective state space model, drawing parallels to the latest SSM architectures such as S6 [10].
detailed exposition of the GRAPHSSM-S4 (resp. GRAPHSSM-55, GRAPHSSM-S6) layer is provided in algorithm 1 (resp. algorithm 2, algorithm 3) appendix D.2. The overall end-to-end architecture is briefly illustrated in figure 1, where we use feature mixing as the mixing mechanism for illustration.
Remark 1 (Choice of mixing mechanisms). In the GRAPHSSM architecture, each SSM layer incorporates a mixing mechanism. Based on our empirical investigations, we have observed that employing sophisticated mixing strategies such (feature mixing) and (representation mixing), yields benefits predominantly when these are applied exclusively to the lowermost layer. Specifically, this entails utilizing either X or X(R) configurations in the initial layer, while defaulting to X;(0: for the layers that follow. An intuitive rationale behind this strategic layer-specific choice will be elucidated in appendix B.3.
4 Experiments
This section presents our key experimental findings on the temporal node classification task. Also, ablation studies of the key design choices presented. Due to space limitation, the detailed experimental settings are deferred to appendix F.
4.1 Experimental results
Node classification performance. The node classification performance of all methods is presented in table 2. It has been observed that graph embedding methods, especially static ones, tend to underperform in most cases. This is expected since these methods are typically trained in an
7

---

Table 2:
Node classification performance (%) on four small scale temporal graphs. The best and the second best results are highlighted as red and blue, respectively.
DBLP33
Brain
Reddit
DBL.P-10
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
WeepWalk [36]
40.5
4
51,45
51,03
26 26.82200
26.75
66.38
67.12
Vode2Vec [9]
48.79
48.4220.4
53.51
$2.95
25.47
25.44
67.31
66,93
HTNE [54]
48. 28.
48.74.0.3
22.12 20.3
26.9620.
26 26.8
38.79
68.36
MDNE [28]
49.12+0.5
48.87+0.4
23.79
23.54
25.79 25.79
25.61
69.71
69.75
Dynamic Triad |50]
48.78
48.633006
21.71
21 21.94.0.7
28. 28.76.0.5
28.51 20.5
66.95
66.42
MPNN [32]
81.78
81.46g1.2
90.97
91.01
40.85
40.64
67.7440.
65.05_0.a
STAR [47]
84.74
84.20
92.08-1.5
92.23
43.42.23
43.43.2.4
72.98
72.03-1.2
INodeEmbed [39]
84,51
83,57+1.1
92.35
92.30
42.11=18
42.06
74.19
74,23
EvolveGICN [34]
84.01 21.5
83.12
92.20=1.3
92.00;100
41.24g1.3
41.11
71.32+0.5
71.20
SpikeNet [25]
83.92
83.04.1.1
92.00=12
91,97
40.42-20
40.20
74.8620.5
74.65
ROLAND [48]
84.21
84.06
92.1421.2
91.85
44.22
44.25
75.01
74.98
GRAPESSM
85.26.0.9
85,00
93,52.1.0
93,54
49.21
49.05
76.80
76.00
unsupervised manner, solely focusing on exploiting the graph structure. We note that continuous-time methods HTNE and M'DNE exhibit poor performance in DBLP-3, Brain, and Reddit even when compared to static methods. This indicates that continuous-time methods are not well-suited for handling discrete-ting graphs, particularly in the absence of temporal continuity. As can also be observed from table 2, most temporal graph neural networks demonstrate good performance on DBLP- 3 and Brain datasets, where the node labels are largely dominated by node attribute information [47]. However, for datasets like Reddit and DBLP-10, where graph topology information plays a more significant role in classification, the performance has notably degraded. This indicates that the baseline methods struggle to effectively capture the underlying evolving graph structure and exploit for accurate classification. In contrast, our most performant architecture, GRAPHSSM-S4 exhibits an average improvement of 14% and 2% in Micro-F1 and Macro-Fl scores, respectively, compared to state-of-the-art baselines on the Reddit and DBLP-10 datasets. In addition, GRAPHSSM S4 is more preferable choice for long graph sequences, achieving new ofate-of-the-art performance on the DBLP-10 dataset.
Scalability to large temporal graphs. To explore the effectiveness of GRAPHSSM on large-scale and long-range temporal graphs, we conduct comparison experiments on arXiv and Tmall and present the result in table Since both datasets exhibit relatively high level of temporal continuity in the observed graph sequence, several advanced baselines have achieved good performance. However, the graph scale and long sequence still pose significant challenges for learning over both datasets, where most methods are insufficient to effectively and efficiently capture the long-range graph dynam- ics. In contrast, by leveraging the linear effi- ciency and long-range modeling capability of SSMs, GRAPHISM outperforms strong base- lines on both datasets.
Table 3: Node classification performance (%) on large scale temporal graphs. OOM: out-of- memory.
arXiv
Tmail
Micro-F1
Macr-FF1
Micro-F1
Macro-F1
DeepWalk [36]
66.5420.3
43.01=0s
57.88
Node2Nee [9]
67.71
43.69 .0.
60.66
$1.58
HINE
65.48
42 42.25-0s
62.64
54.93
MÉDNE [28]
26.91
43.52-06
DynamicTriad Triad [50]
61.10
38 38.25
60.72
51.16
MPNN [32]
64.68
41.22
58.07 100
50.27 1o.
STAR
00M
00M
GOM
OOM
(NodeEmbed [39]
0OM
00M
COM
OOM
ProlveGiN [34]
68.17
43.0121
61.77a0
55.7840.6
SpikeNat [25]
66.6 66.69
43.96-10
66.10..0
62.40.006
[48]
68.27
48.01
21.5
0OM
OOM
GRAPHSSM
70.67
49.97
.0.
66.29 .0
62.57 L0.3
Table 4: Node classification performance (%) with different SSM architectures.
DBLP33
Brain
Reddit
DBLP-10
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
GRAPHSSM-S GRAPHSSM-S5
85.26
85.00
93.52-1.0
93.5440.9
49.21
49.05
76.80 20.a
76.00
84.32
83.57+19
92.20
92.05
44.75
44.7940.
73.19
72.95
GRAPHSSM -6
85.74.0.s
85.2310.
93.80_2..
94.47.0.6
42.52
41.73
75.26
74.81
8

---

SSM architectures. As GRAPHSSM is general framework that generalizes SSMs to temporal graphs, we conduct experiments on extending GRAPHSSM with different ad-hoc SSMs, including $5 [40] and $6 [10]. The node classification results on four datasets are shown in table 4. By comparing different variants of GRAPHSSM, we can find that S4 the best architecture for learning over temporal graph sequences. $5, being simplified version of S4 with fewer parameters, achieves poor performance on all datasets. Notably, while S6 shows impressive performance in other modalities such as language or images [10, 51J, it is observed that they underperform when applied to graph sequences. This indicates the selective mechanism may not be good fit for graph data.
Table 5: Ablation results (%) of GRAPHSSM-S4 with different mixing configurations.
DBLP-3
Brain
Reddit
DBLP-10
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
8 8:00
84.51 10.9
84.28
91.5611.1
91.99.0.7
48.05.28
47.99
75.62.0.5
74.65
8 + X
85.12
84.82
92.36
92.54
49.06.1.9
49.06.1.8
76.67
75.95
8 + -
84.9811.1
84.7911.0
93,52
93,54
49.21
49.05 10.7
77.7610.
77.54
8 X
85.26
85.00
91.84
91.88
47.88
47.94
75.4
74.89
Mixing mechanism. We assess the effectiveness of various mixing mechanisms introduced in section 3.2 through a series of experiments conducted using the S4 variant of GRAPHSSM. The analysis spans four distinct configurations: no intra-node mixing (A1 + 2200), feature mixing at the first layer (811) x and representation mixing at either the first (X-18) ( second (x10) + ) layers. The findings, presented in table 5, indicate that the integration of the Mix module at the first layer generally leads to enhanced model performance. An intuitive explanation for this observed phenomenon is elaborated in appendix B.3.
Initialization strategy. Recent advancements have highlighted the crucial role of initialization SSMs [12], prompting our inves- tigation into the effects of various initialization strategies for the matrix. Specifically, we explore "hippo", "constant", and "ran- dom" initializations, with their comprehensive definitions provided in appendix D.2. The result, as shown in figure exhibits distinct performance variations across different initialization strategies, with HiPPO being typically the dominant one which corroborates our theoretical motivations.
MotroFF (9s)
80-
50
46-
DBLP-10
Figure 3: Comparison of GRAPHSSM with different initialization strategies.
5
Conclusion
In this work, we introduce conceptualized GHIPPO abstraction temporal graphs. Building upon GHIPPO, we propose GR APHSSM, a theoretically motivated state space framework for modeling temporal graphs derived from novel memory compression scheme. The proposed framework is computationally efficient and versatile in its design, which is further corroborated by strong empirical performance across various benchmark datasets. We also point out the unobserved graph mutation issue in temporal graphs and propose different mixing mechanisms to ensure temporal continuity across consecutive graph snapshots. Despite the promising results, the applicability of GRAPHSSM is presently confined to discrete- discrete-time temporal graphs. A discussion of our framework's 's current limitations and the scope for future extensions is presented in appendix E.
Acknowledgement
The research is supported by the National Key R&D Program of China under grant No. 2022YFF0902500. the Guangdong Basic and Applied Basic Research Foundation, China (No. 2023A151500 1050), Shenzhen Science and Technology Program (KZID2023100339990000011 and
Tencent AI Lab RBFR2024004, Liang Chen is the corresponding author.

---

References
[1] W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzale V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 180.00166,, 2018.
[2] A. Behrouz and F. Hashemi. Graph mamba: Towards learning on graphs with state space models. CoRR, abs/2402.08678,, 2024.
[3] P. J. Brockwell and R. A. Davis. Time series: theory and methods. Springer science & business media, 1991.
[4] K. Cho, B. van Merrienboer, Ç. Gülgehre, D. Bahdanau, F. Bougares, H. Schwenk, and Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In EMNLP, pages 1724-1734. ACI., 2014.
[5] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometrie. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[6] D. Y. Fu, T. Dao, K. K. Saab, A. W. Thomas, A. Rudra, and C. Ré. Hungry hungry hippos: Towards language modeling with state space models. In ICLR. OpenReview.net, 2023.
[7] D. Y. Fu, H. Kumbong, E. Nguyen, and C. Ré. Flashfficony: Efficient convolutions for long sequences with tensor cores. arXiv preprint 2xXi:2311.05500 2023.
[8] W. Gerstner, W. M. Kistler, R. Naud, and L. Paninski. Neuronal dynamics: From single neurons
to networks and models of cognition. Cambridge University Press, 2014.
[9] A. Grover and Leskovee. node2vec: Scalable feature learning for networks. KDD, pages 855-864. ACM, 2016.
[10] A. Gu and T. Dao. Mamba: Linear-time sequence modeling with selective state spaces. CoRR, 12.00722, 2023.
[11] A. Gu, T. Dao. S. Ermon, A. Rudra, and C. Ré. Hippo: Recurrent memory with optimal polynomial projections. In NeurlPS, 2020.
[12] A. Gu, K. Goel, A. Gupta, and C. Ré. On the parameterization and initialization of diagonal state space models. Advances in Neural Information Processing Systems, 35:35971-35988 2022.
[13] A. Gu, K. Goel, and C. Ré. Efficiently modeling long sequences with structured state spaces. In ICLR. OpenReview.net, 2022.
[14] A. Gu, I. Johnson, K. Goel, K. Saab, T. Dao, A. Rudra, and C. Ré. Combining recurrent, convolutional, and continuous models with linear state space layers. In NeurlPS, pages 572-585. 2021.
[15] A. Gupta, A. Gu, and J. Berant. Diagonal state spaces effective as structured state spaces. Advances in Neural Information Processing Systems, 35:22982-22994, 2022.
[16] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[17] Hashemi, A. Behrouz, and M. R. Hajidehi. CS-TGN: community search via temporal graph neural networks. In WWW (Companion Volume), pages 1196-1203. ACM, 2023.
[18] S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Comput., 18): 1997.
[19] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning graphs. In NeurIPS, 2020.
[20] S. M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, Forsyth, and P. Poupart. Representation learning for dynamic graphs: A survey. J. Mach. Learn. Res., 21(1), jan 2020.
[21] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks.
In ICLR (Poster). OpenReview.net, 2017.
[22] S. Kumar, X. Zhang, and J. Leskovee. Predicting dynamic embedding trajectory temporal
interaction networks. In KDD, pages 1269-1278. ACM, 2019.
10

---

[23] J. Li, S. Tian, R. Wu, L. Zhu, W. Zhao, C. Meng, L. Chen, Z. Zheng, and H. Yin. Less can be more: Unsupervised graph pruning for large-scale dynamic graphs. CoRR, abs/2305.10673, 2023.
[24] J. Li, R. Wu, W. Sun, I. Chen, S. Tian, L. Zhu, C. Meng, 7. Zheng, and W. Wang. What's behind the mask: Understanding masked graph modeling for graph autoencoders. In KDD,
pages 1268 1078-127.....m ACM, 2023.
[25] J. Li. Z. Yu, Z. Zhu, L. Chen, Q. Yu, Z. Zheng, S. Tian, R. Wu, and C. Meng. Scaling up dynamic graph representation learning via spiking neural networks. In AAAI, pages 8588-8596. AAAI Press, 2023.
[26] J. Li, H. Zhang, R. Wu, Z. Zhu, B. Wang, C. Meng, Z. Zheng, and L. Chen. A graph is worth 1-bit spikes: When graph contrastive learning meets spiking neural networks. In ICLR, 2024.
[27] A. Longa, V. Lachi, G. Santin, M. Bianchini, B. Lepri, P. Liò, F. Scarselli, and A. Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. CoRR, abs/2302.01018, 2023.
[28] Y. Lu, X. Wang, C. Shi, P. S. Yu, and Y. Ye. Temporal network embedding with micro- and macro-dynamics. In CIKM, pages 469-478. ACM, 2019.
[29] E. Nguyen, K. Goel, A. Gu, G. W. Downs. P. Shah, T. Dao, S. Baccus, and C. Ré. S4ND: modeling images and videos as multidimensional signals with state spaces. In NeurlPS, 2022.
[30] A. V. Oppenheim, J. Buck, M. Daniel, A. S. Willsky, S. H. Nawab, and A. Singer. Signals & systems. Pearson Education, 1997.
[31] A. Orvieto, S. L. Smith, A. Gu, A. Fernando, C. Gulcchre, R. Pascanu, and S. De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, pages 26670-26699 PMLR, 2023.
[32] G. Panagopoulos, G. Nikolentzos, and M. Vazirgiannis. Transfer graph neural networks for pandemic forecasting. In AAAI, pages 4838 4845. AAAI Press, 2021.
[33] J. Pang and G. Cheung. Graph laplacian regularization for image denoising: Analysis in the continuous domain. IEEE Transactions on Image Processing, 26(4): 1770-1785, 2017.
[34] A. Pareja, G. Domeniconi, J. Chen, Ma, T. Suzumura, H. Kanezashi, Kaler, T. B. Schardl, and C. E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In AAAI, pages 5363-5370. AAAI Press, 2020.
[35] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Z. Yang, Z. De M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-pun gegh-performance deep learning library. In NeurlPS, pages
2019.
[36] B. Perozzi, R. AI-Rfou, and S. Skiena. Deepwalk: online learning of social representations, In KDDD, pages 701-710. ACM, 2014.
[37] A. Rogozhnikov. Einops: Clear and reliable tensor manipulations with einstein-like notation. In International Conference on Learning Representations, 2022.
[38] E. Salinas and Sejnowski. Integrate-and-fir neurons driven by correlated stochastic input. Neural computation, 14(9):211-22155 2002.
[39] U. Singer, I. Guy, and K. Radinsky. Node embedding over temporal graphs. In IJCAI, pages 4605-4612. ijcai.org, 2019.
[40] H. Smith, A. Warrington, and S. W. Linderman. Simplified state space layers for sequence modeling. In /CLR. OpenReview.net, 2023.
[41] S. Tian, J. Dong, J. Li, W. Zhao, X. Xu, B. Wang, B. Song, C. Meng, T. Zhang, and L. Chen. Sad: supervise anomaly detection on dynamic graphs. In IJCAI, pages IJCAI, 8 2023.
[42] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and Polosukhin. Attention all you need. NIPS, pages 5998-6008, 2017.
[43] Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lið, and Y. Bengio. Graph attention networks. In ICLR (Poster). OpenReview.net. 2018.

---

[44] Y. Wang, Y. Chang, Y. Liu, J. Leskovec, and P. Li. Inductive representation learning in temporal networks via causal anonymous walks. In ICLR. OpenReview.net, 2021.
[45] C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622, 2020.
[46] R. J. Williams and D. Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Comput., 1(2):270-28) 280. 1989.
[47] D. Xu, W. Cheng, D. Luo, X. Liu, and X. Zhang. Spatio tentioa attentive RNN for node classification in temporal attributed graphs. IJCAI, pages 3947-3953, ijcai.org, 2019.
[48] You, T. Du, and Leskovec. ROLAND: graph learning framework for dynamic graphs. In KDD, pages 2358-2366 ACM, 2022.
[49] M. Zhang. K. K. Saab, M. Poli, T. Dao, K. Goel, and C. Ré. Effectively modeling time series with simple discrete state spaces. arXiv preprint arXiv:2303.09453 2023.
[50] L. Zhou, Y. Yang, X. Ren, F. Wu, and Y. Zhuang. Dynamic network embedding by modeling triadic closure process. AAAI, pages 571-578. AAAI Press, 2018.
[51] L. Zhu, B. Liao, Q. Zhang, X. Wang, W. Liu, and X. Wang. Vision mamba: Efficient visual representation learning with bidirectional state space model. CoRR, abs/2401 109417, 2024.
[52] X. Zhu, Z. Ghahramani, and J. D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pages 912-919, 2003.
[53] Y. Zhu, Cong. D. Zhang, W. Gong, Q. Lin, Feng, Y. Dong, and J. Tang. Wingnn: Dynamic graph neural networks with random gradient aggregation window. In KDD, pages 3650-3662. ACM, 2023.
[54] Zuo, Liu, H. Lin, J. Guo, X. Hu, and J. Wu. Embedding temporal network via neighborhood formation. In KDD, pages 2857-2866. ACM, 2018.
12

---

Appendix
Table of Contents
A Broader impact
13
B Notes
13
B.1 Laplacian regularization, diffusion and GNN approximation
13
An extension to varying node sets
B.3 Heuristic justifications for layer-specific choice of mixing mechanisms
15
C Proof of theorems
15
C.1 Proof of theorem 1.
15
C.2 Proof of theorem
16
Algorithm descriptions
17
The designs of mixing mechanism MIx
D.2 Details of GRAPHSSM
................................
18
D.3 Complexity and implementations
19
E Discussions and limitations
20
E.1 Extension to continuous-tine temporal graphs
20
E.2 Going beyond piecewise dynamics
21
F Experimental setup
21
A
Broader impact
Our extension of state space models for temporal graph modeling may have broader impacts, particu- larly if applied to social, traffic, and financial networks which could affect individuals and society. While our work is fundamental and not tied to specific applications, the potential for misuse in surveillance, exacerbation be dismissed. For example, more accurate temporal graph models might inadvertently facilitate more intrusive tracking of individuals or groups, or could be employed in creating diseriminatory financial models. It is the responsibility of those employing such technologies to consider these ethical implications and implement measures such as algorithmic fairness checks, privacy-preserving methodologies, and security protocols that prevent exploitation of the technology. As with any pow- erful tool, the utmost caution should be exercised to avoid the irresponsible use of our advancements in modeling dynamic systems.
biases in algorithmic decision-making or violation of privacy cannot
B
Notes
B.1
Laplacian regularization, diffusion and GNN approximation
In this section, discuss in detail the smoothness regularization of different types of Laplacians, and their approximations related to popular GNN architectures.
Inductive bias and compression capability of different Laplacians. As mentioned in section 3.1, two typical (normalized) graph Laplacians are
Liym (s) D(s)
D(3))
(11)
(.w(s) = A(s))
(12)
13

---

with corresponding penalties written
' Z(s) T Lsym (s)
2u(s)
20(8)
dd((s)
(13)
Vd((s)
vdo(s)
(u,))E((s)
I. ((s) Lim (s)
(zu(s) - =z(s))² duc(s).
(14)
du
(u.))E
The above display reveals the inductive bias of Laplacian regularizations as a promoting closeness in weighted l2 metric regarding adjacent nodes' memory compressions, with distinct choices of Laplacians utilizing different weighting schemes. In particular, let a - oc in objective then when the Laplacian is chosen
Laym, the solution Zvm(s)
(s) must satisfy
sym
5ym V(, E E(3),088S
(15)
V (8)
(s)
then follows that Z compresses all the historical degree profiles over connected components of G. Analogously, when Iew is chosen, it follows that the solution 7d (s) must satisfy
2, (s) Zu (s). Vu, v) E E(s).0
(16)
which compresses the composition of connected components of G.
Diffusion and GNN approximation. We consider approximations of the following diffused node features with respect to some type of Laplacian:
= (ho aT+
T Σ 111 XBT
(17)
The right- side of the preceding display equivalent to performing infinite rounds of message passing. If we drop most of the higher-order terms, we arrive at models similar to graph neural networks. particular, we keep only the first order terms, i.e., k = 1, then for the two Laplacians listed above, for each V. we have the resulting approximations:
h (1 Ba) + Σ
Bfa
(GCN-Like)
Vd
(EN(v)
N 2 (1 11-0- Br +
Σ
a
Bfu-
(SAGE(MEAN)-Like)
d
uEN(w)
The above display exhibits a similar pattern to the design of graph neural networks with a aggregate- then-combine procedure, with the corresponding aggregation steps mirroring two typical GNN architectures GCN [21] and SAGE with mean pooling [16]. Furthermore, note that the effect of the balancing constant would be absorbed into the learnable parameters of the GNN.
B.2
An extension varying node sets
The methodology described in section 3.1 applies to temporal graphs with a fixed node set. To extend our approach to accommodate graphs featuring varying node sets, we initially focus on the continuous-time context, subsequently delving into discussions on discretization strategies. Suppose on the time interval = [0, T], the node set evolves as depicted in the following sequence:
V(0) - V(h)
V(12) - - V(ln-1 - V(In) = V
(18)
That is, throughout the interval T, the node undergoes alterations on R distinct occasions, with associated changes occurring at times t respectively. We denote these evolving node sets as Vo, ....., VR. To systematically analyze this temporal evolution, we partition the entire interval into R + segments:
T, = [t, 1,,1), 5
r R with = 0 and f T.
(19)
14

---

According to the formulations in section 3.1, on each Tr, we have well defined GHIPPO operator and the solutions are characterized by theorem 1. With an approximation order of N, we let the resulting projection coefficients be
(1) VIIN RIITT
(20)
To address the issue of shape incoherence arising from variations in node sets, we employ a mem- ory alignment procedure. This technique facilitates the mapping from (1+++))) to ensuring that the memory associated with each node aligned according to the following scheme:
[uu.r(b411)
if E VV++ if E VV+
(tr+1)
(21)
Minit
The memory alignment procedure (21) retains the continuity of states for nodes that persist over time. For nodes that emerge anew within the graph, it assigns default initial state, which could either be an zel-zero state or an estimation derived a priori from the states of neighboring nodes.
Discretizations. Within the established context, Theorem 2 remains applicable on each segment Tr Consequently, our primary concern becomes the treatment of nodes that emerge between consecutive snapshots. Adhering to the ZOH discretization rule, newly emerged nodes lack historical states and therefore do not undergo the MIX strategy, and use their initial state during their first appearance in the recurrent update. This initial state can be set zero or determined through aggregation from neighboring nodes.
B.3 Heuristic justifications for layer-specific choice of mixing mechanisms
The various mixing mechanisms introduced in this paper are designed to facilitate an estimation of a weighted average of unobserved graph representations that occur amidst successive observational time points. Starting with the output generated by the initial SSM block, these outputs inherently encapsulate the information pertaining the current snapshot, well that of its antecedent. Thus, the incorporation of mixing mechanisms at a second-layer may inadvertently result in the assimilation of superfluous information, extending beyond the target scope of back-to-back snapshots. Therefore, confining the deployment of mixing solely to the first SSM layer ensures the strict conservation of temporal locality. We have empirically verified that such an approach yields enhanced performances.
C Proof of theorems
In this section we present the proof of theorem I and theorem 2. We first present some necessary technical preparations: For any i E [0, 7), let 14, be some finite measure and let Hy, denote the Hilbert space induced by the inner product
(. : -[ f(s)g())dm((s))
(22)
Let (t) be the space of polynomials constructed via the restriction of each element in Pn to |0, t].
We assume the measure family be chosen such that (t) C Hppe Vt E [0, T]. For each v E V, we assume that the restriction of xe (viewing function [0, T)) to [O, t is element of Hy, Note that these assumptions are trivially satisfied for the scaled Legendre measure (LegS) μr _ [o,t)-
C.1 Proof of theorem
Proof of theorem 1. Hereafter we omit the dependence on μ4 and write the inner product simply as (.,-) without misunderstandings. Let Po.... .., PN-11 be a set of orthogonal polynomials in Px with
(P., = 0 for i # j and the degree of P, is for each 0 < n I N 1. Then for any f E Hyw the optimal approximation in (14) distance in Px is given by
N-1
P
Ilf) =
Pf. R
(23)
|
2
15

---

where we define II to be the projection operator. Now we turn to G, viewing 2e as
function [0. for any U, we have:
/'' Σ
- ((())) + L. 2(s) L(s)((s)ss))
G,
(24)
NEV
Σ (20(8)) [T)
(25)
NEV
+
(I) 20)) + (()))((4))))))
(26)
DEV
Σ (z,(s) II(z,)(s)) + (Z, VEV
(27)
The preceding display suggest that the minimizer of (2 G, X, is the same as the minimizer of (Z; (.G.,)) thus suffices to analyze Z, G, X. μJ) which easier to work with since l1zz,) PN, Vu E V and the solution is a direct application of Laplacian regularization with respect to the integrand at any s E [0, f). yielding:
GPROJ, (G, (s) (1 (1+ +
(28)
Now let the coefficient matrix Q E X be defined as Qu,n = (xe, Pa), Vo E V,n E [N]. we obtain the GHIPPO operator
GHIPPO (G, (s) = U(s)= = aL Q(s)
(29)
Next we take derivatives to the coefficients. Note that T.(t) discontinuous and we can only apply derivative intervals where L(t) remains same. First note that if we choose μa to be the scaled Legendre measure (LegS) with μl = tlo.... and Pn as basic Legengre polynomials [11, Appendix B.I.I], then we have the HIPPO property:
dQ(t) dt Q()A +
(30)
where E NxN BERNII with
(2n + 1)(2++1) if > k if n k,, if k. Fix some 1 < m I M and for t E [1- tm) we have:
Ank
n +1
Bn /2n +
(31)
dU((t)
((1+ dQ(t) dt
(32)
dt
(1+aa(t)) (Q())) + = U(IAA + +(1 -(()) X(IBBB
(33)
(34)
which finishes the proof.
C.2
Proof of theorem 2
Proof of theorem 2. For ease of presentation, operate the node level instead of graph level. Recall the unobserved dynamics:
G Gio Eig Gi
&L3 G1,2 - GL.M-11 EgMy GI.M. G
(35)
Following the assumptions, intuitively write the update process follows:
GI..XK.
G1a.X12
NI.M, UL.
U U.o
U2 -
U1,
(36)
16

---

For each 0 S S M, let D : (I+,),,) - Let de,s be the v-th row of D, and up be the v-th row of U1.-- We first write the ZOH update corresponding each step (36) for every v E V:
Uv A-1 ( 1) du:i for - i S Mi
Up
(37)
Un!!
for i = 0
Next we do the recursion from the rightmost to the leftmost according to (8):
We = e ( uu,
un,as +
A (c( (c(n--s44)4 - -1) do,.s.
= e )A ( -MM un, M + A-1 das, - uu (u,Mi-1)
-toy -1
+ 1 (7 ( - 10
(38)
Wo + T
where we define
Mi
T= A- (elt-tmmm))
-1) Uv Mr
Σ e A-1
( (clt-teidd 1) Uv
(39)
in the above display we define 7--1 Note that A-1 and e are simultaneouly diagonalizable for any 8, therefore the matrix multiplication commutes and we further write
Mi
Y = A- (c -1) Ue,M. +
Σ 1=1
A
(cln-ti e(T-((dd)) 1o
(40)
With some abuse of notation let A E RV denote the diagonal vector of the matrix. We provide the following construction:
( -
i= Mi
e (T- ni 1)1 - (h- (7-41)
A
(41)
0 Osis Mr
-(7-- -
Here note that A R.V, is straightffrward verify that:
Mi Σ
T= A- (6
A O Up
(42)
M. where {AiJosisM, non-negative N-dimensional vectors satisfying Em X; 1x. with 1s denoting the all-one vector dimension N. As the values of As are independent v, the proof finishes by combining (38), (42) and write the above conclusion in matrix form via setting A, diag(A.). < i Mi
Algorithm descriptions
D.I The designs of mixing mechanism MIX
We consider two types of mixing mechanisms: convolution (CONv1D) and Scaled interpolation (INTERP) which we describe below:
CoNvID. This the usual convolution operation along the sequence dimension using shared parameters. We use kernel size of 2 so that only consecutive representations mixed.
17

---

INTERP. This is an input-dependent weighted average strategy followed by an input seputddeeendent scaling, implemented as
MIx (21, p 22) (5(21, Z₁ + (1 (1, @ Z2),
(43)
where Z1, Z2 E IR xd are node representation matrices corresponding to consecutive snapshots. and are scale and weight functions that map two inputs into positive real numbers of identical shape with 1 or Zz, defined by
(Z 72) = softplus (W [Z [2] + bp), 5(Z,, Z2) = sigmoid
+ bg)
(44)
where Wpp Wg Rdddd and bp. bg E R are learnable parameters therein.
D.2 Details of GRAPHSSM
In this section, we elucidate on the methodology of GRAPHSSM through three specific instantiations. For clarity in our explanation, we employ certain notational conventions that might be somewhat different from the main text: the term V refers to the number of vertices in each graph snapshot G₁ within a sequence of L. graph snapshots [Gihsig which we further denote as GI.L. and D represents the dimensionality of node features. The symbol LINEAR is used represent linear projection layer including a bias term, where the dimensions for input and output are typically clear from the context to ensure compatibility. The notation XI.7. denotes the concatenation of tensors of the same dimensions along their second axis. For operations on tensors of order higher than two, we use the einsum notation, as defined by the einops framework [37]. We present the algorithmic description of our design of SSM layers, namely GRAPHSSM-SI (resp. GRAPHSSM-SS GRAPHSSM-SG algorithm (resp. algorithm 2, algorithm 3). Subsequently, we adopt the
Algorithm 1 GRAPHSSM-SS S4 layer
Input: A sequence of graph (snapshots) G1.Z, with each of size V.
Node (hidden) feature inputs X1.1. E RVVLxD
A graph neural network GNN, parameterized by 0.
A mixing mechanism MIX& parameterized by é.
State-space parameters A E DDN, B E DxN C RDx,
A linear layer for adaptive time gaps LINEAR,.
Output: Y1. E RVV xVxLx
1: # Approximate diffusion via GNN
2: for = 1 to L do
3: Zi GNN, (XI, Gi);
4: H, = Z₁ if else MIx(ZI, Zi-1):
5: end for
6: Initialize state Un = 0; # SISO state of shape VXDxN
7: for t = 1 to L do
8:
A = softplus (LINEAR, (Hi));
9:
A exp (einsum A A, DV + VDD"));
10:
B einsum B, "V, DN + VDN");
11:
U1 = U:-1 @ A + einsum (B, Hi, DV,,, VD + VDN");
12:
Yi einsum(Uj, C, DV DN + VD");
13:
end for:
14:
return YT.L;
following neural architecture composed of K blocks, with each block composed of one SSM layer followed by nonlinear activation and a residual connection:
(k) = (SSMLAYER (H ,.I..)) - LINEAR (Hi Is
(45)
where !! are the node features XIAL The SSMLAYER in (45) may be chosen any of (GRAPISSM-SA GRAPUSSM-S5, GRAPUSSM-SS). In our implementation of GRAPUSSM- S6, we add an additional layer normalization the last operation of each block.
"I these algorithmic descriptions, we illustrate using the representation mixing mechanism. The case for feature mixing is similarly defined.
18

---

Algorithm 2 GRAPHSSM-S5 layer
Input: A sequence of graph (snapshots) G1.L with each of size V. Node (hidden) feature inputs XI.L E RVxLDD
A graph neural network GNN, parameterized by 9.
A mixing mechanism MIX, parameterized by é.
State-space parameters
RNx1, B PxN, C. RNDD. A linear layer for adaptive time gaps LINEAR,.
Output: Y1.z E RVXLD
1: # Approximate diffusion via GNN
2: for 1 to L do
3: Z = (X,, Gi);
4: H, Z4 if else MIX 7-1)):
5: end for
6: Initialize state Un 0; # MIMO state of shape N
7: for t 1 to L do
8:
Â softplus LINEAR,(UH)))
9:
A exp (A,AT);
10:
B einsum ( B, "V, DN 4 VDN");
11:
U U--1 @ A + einsum (B, Hi, "VDN, - VN");
Yi U,C:
13: end for:
return VI.L:
Initialization strategy. Recent developments in state space modeling have underscored the signifi- cance of initializing the state matrices A, B, and C, with the initialization of A frequently emerging as the most critical factor for the performance of the SSM [12]. Building upon the progress made in $4 [13] and S4D [29, 15], we evaluate three disparate initialization strategies for the matrix A. Note that since is diagonal, we instead represent as a N-dimensional vector:
VISSS:: S4D -nn + 1),
A S4D. Const
A random
(46)
2
S4D-Real (HIPPO) This is the diagonal part of the original HIPPO matrices (6).
S4D-Const (Constant) This the real part of the eigenvalues corresponding to the S4N matrix as defined in [13], which equals -
Random This initialization is generated via negative transform of random number X, which generated using the Glorot initialization method.
Additionally. we initialize the B matrices using a constant of all-1 vector, and we initialize C randomly using Glorot.
D.3 Complexity and implementations
As detailed in section 3.1 and the algorithmic outlines provided, the implementations of GRAPHSSM across all three variants can be stratified into two primary phases: a diffuseeand--mise -ni-iixin--ii step, and linear recurrence step. The diffuse-and-mixinn stage facilitates straightforward parallelization through the employment of methods such as graph batching. The inherent linear characteristic of the recurrence operation permits the utilization of efficient computation strategies. notably the selective scan technique as introduced in [10]. This approach yields FLOP complexity of ((VDDN per SSM layer with work-efficient parallelization, concurrently achieving efficiency, Furthermore, note that if we replace the adaptive time gap mechanism into a constant, i.e., we use A, = +, < < L line 8 of algorithm and algorithm 2, the resulting linear system time-invariant and we can use other computational accelerations like convolution [13, 7] and parallel scan [40].
19

---

Algorithm 3 GRAPHSSS-SG layer
Input:
A sequence of graph (snapshots) G1.Z with each of size V. Node (hidden) feature inputs XI.L E RVXLDD
A graph neural network GNN, parameterized by 9.
Three graph neural networks for selective state spaces GNN GNN GNN A mixing mechanism M parameterized by Φb
State-space parameters A RDxN
Output: YI.L E RVXLLD
Approximate diffusion via GNN
2: for t = 1 to L do
3:
Z = GNN, X1, Gi):
4: Hi Z if / else MIX (Z,, Z(11):
5: end for
6: Initialize state Un 0; # SISO state of shape x N
7: for = 1 to L do
8:
A softplus (GNN A (X1, GI) +b;;
9:
Ā exp (einsum A,, A, "VD, DN - >VDN"))
10:
B einsum(A, (,,, GNN, (Xi, Gr), "VD, VN - VDN");
11:
U1 U--1 @ A + einsum (B, Hi, "VDN, VD VDN");
12:
C GNN (X,, Gi);
13: Yi einsum(Ui, C, "VDN, DN + VD");
end for:
15: return Y1...
E Discussions and limitations
In this section, we discuss the limitations of the GRAPHSSM framework and propose few future research directions that might be of interest.
E.1
Extension to continuous-timg temporal graphs
In this study, focus modeling discrete-time temporal graphs (DTTGs) through the lens of discretizing continuously evolving systems. The continuous-time viewpoint holds promise for encapsulating the modeling of continuous-time temporal graphs (CTTGs), domain of growing importance in graph learning literature. However, the current GHiPPO framework has its limitations when extending to continuous-time setups. We provide brief discussion as follows:
DTDG, CTDG and GHiPPO Recall that in our formulation of the underlying graph process (2), the node features evolve contimuously and the topological relations among nodes allow finite (countable) mutations. In DTTG representations, observe the entire graph at certain time spots resulting in serious of snapshots. In this spirit, DTTGs have complete latitudinal information, but are lossy regarding longitudinal information. In CTTG representations, we have complete observations of events, but upon each event information, we do not observe the features the rest of the nodes (that do not participate in those specific events). Therefore, CTTGs have complete longitudinal information, but are lossy regarding latitudinal information. In this regard, we may view DTDG and CTDG as two different lossy observation schemes of the underlying graph process in the GHiPPO abstraction.
do not directly observe the events, but
Handing CTTGs using SSM discretizations is challenging In section 3.2 of our paper (especially theorem 2), we established the discretization scheme upon an ideal, discrete observation (We observe the graph snapshot at each mutation events). We believe that this result might reasonably hints the gap between possible empirical approximations in either DTTG or CTTG scenarios: DTTGs, we believe approximations using available snapshots are possible since from hindsight, the ideal representation is convex combination of the snapshot representations at the mutation times. The approximation bias mostly comes from fewer snapshots, and we use mixing strategies mitigate
20

---

the biases. However, in CTTG scenarios, we miss the majority of information in each snapshot. Besides, constureting snapshots from CTDGs is itself a very impractical method. Hence, we regard the modeling of CTDG to be beyond the scope of GraphSSM.
E.2 Going beyond piecewise dynamics
The distinguishing algorithmic feature of GHIPPO compared the conventional HiPPO framework lies in the piecewise nature of the dynamical system it generates. This characteristic leads to the challenge of dealing with unobserved dynamics, factor that motivated the development of our MIx module. However, it's important to acknowledge that the mixing module serves as an approximation of the actual underlying dynamics, thus representing limitation within the framework. This acknowl- edgment raises an intriguing question: might there exist alternative problem formulations capable of yielding a smoother dynamical system that mitigates the issue of discontinuities? One potential pathway could involve adopting smoother versions of the Laplacian or revising the approximation objective specified in (3) towards one that fosters a smooth solution. Such solution would promote consistency in the dynamics across the complete temporal interval. Implementing these innovations would, however, necessitate the incorporation more sophisticated technical assumptions and theoretical tools which we left for future explorations.
F Experimental setup
Table 6:
Dataset Statistics.
DBLP-3
Brain
Reddit
DBLP-10
arXiv
Tmall
Nooes
4,257
5,000
8,291
28,085
169,343
577,314
#Edges
23,540
1,955,488
264,050
236,894
2,315,598
4,807,545
#Features
100
20
20
128
128
128
#Classes
3
10
4
10
40
5
#Time Steps
10
12
10
27
35
186
Category
Citation
Biology
Saciety
Citation
Citation 0.580
E-commerce
TC structure
0.139
0.024
0.030 0.556
0.823
0.811
TCRestue
0.468
0.070
0.823
1.000
0.712
Temporal continuity. As illustrated in figure 2, work has highlighted the problem of unobserved graph mutations in learning from discrete-timg temporal graphs. The issue of unobserved graph mutations greatly hampers the temporal continuity of such graphs, presenting significant challenge for learning if not properly addressed. To quantitatively measure the temporal continuity of a temporal graph, we calculate the average proximity between consecutive graph snapshots in the graph sequence. Specifically, we utilize Jaceard distance and Cosine similarity to measure the temporal continuity in terms of graph structure and node features, respectively:
L-1
E1+
TCstructure
L
& E E
L-1
TC
Σ
Sim(Xi X1, X(+1),
(47)
L --1
1
(a F141.e)
where Sim(Xi, X1-1)
Nv
DEV | |2411ell|
Datasets. We focus on the node classification task in discrete-time temporal graphs, which is straightforward extension of static graphs. The experiments are conducted on six temporal graph benchmarks with different scales and time snapshots, including DBLP-3 [47], Brain [47]. Reddit [47], DBLP-10 [25], arXiv [19], and Tmall [25]. Dataset statistics are summarized in table including the corresponding temporal continuity. The graph datasets are collected from cal-world networks belonging different domains. should be noted that in the arXiv dataset, the time information associated with the nodes rather than the edges. As result, we split the snapshots of arxiv based on
21

---

the occurrence of nodes. Each snapshot graph in the dataset shares the same attribute information but not the topology. Therefore, Teatuue 1.000 for arXiv in our experiments.
Baselines. We compare GRAPHSSM with the following baselines: (i) static graph embedding
methods: DeepWalk [36], Vede2Vec [9]: (ii) temporal graph embedding methods: HTNE, MD and Dynamic'Trian [50]; (iii) discrete-ting time temporal graph neural networks: MPNN [32]. STAR [47], tNodeEmbed [39], EvolveGCN [34], SpikeNet [25], and ROLAND [48]. For baselines that are originally designed for static graphs, we accumulate historical information (edges) in the graph snapshot sequence and represent the static graph structure at the last time point. All baselines are carefully tuned to achieve their best results based on the code officially provided by the authors.
Implementation details. GRAPUSSM is built on the success of SSMs, where in this work we have derived variants of GRAPIISM-SS4, GRAPUSSS-S5, and GRAPUSSM-S6, under different SSM settings. Our experiments are mainly conducted on the S4 architecture. we employ feature mixing for DBLP-10 and representation mixing for other datasets. The graph convolution networks used to learn the graph structure are SAGE [16] for all datasets, except for arXiv, where GCN [21] is used. We implement our models as well as baselines with PyTorch [35] and PyTorch Geometric [5], which are open-source software released under BSD-style and MIT license, respectively. All datasets used throughout experiments are publicly available. All experiments conducted an NVIDIA RTX 3090 Ti GPU with 24 GB memory. Code will be made available at https:
//gi thub.
Evaluation protocol. We adopt the conventional transductive learning setting, where the graph structure of all snapshots is visible during both training and inference stages. This is analogous to the standard node classification task, but with the additional incorporation of time information facilitate the learning. For the DBLP-3, Brain, and Reddit datasets, we adopt the 31%/9%/19% train/validan validation/// splits as suggested in [47]. For the DBLP-10 10 and Tmall datasets, we follow the experimental settings of previous works [25], where 80% of the nodes are randomly selected as the training set, and the remaining nodes are used as the test set. Note that stratified sampling is employed to ensure that the class distribution remains consistent across splits. For the arviv dataset, we use the fixed public splits. We use Micro-Fl and Macro-F1 to evaluate the node classification performance. We report the average performance with standard deviation across 5 runs for each method.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction has accurately reflected the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitation of this work in appendix E.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. The proof of theorems are presented in appendix C.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide a comprehensive description of the experimental settings in appendix F. The algorithm framework of GRAPHSSM with different SSM architectures is presented in appendix D.2. All the code for reproducing the experiments is made available in the supplementary material accompanying the submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All the data used in experiments publicly available online and the code to reproduce the experiments is available in the supplementary material accompanying the submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines fattps://nips.cm cc/ httple/ggiides/ooeeeSueaee
wrriiissssiiiiyysi for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /niis..co.
guwggeudd///eee /CodeSummi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided a comprehensive description of the experimental settings in appendix F. Exploration experiments different SSM architectures and components of our proposed method are also conducted in section 4.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experiments were conducted over 5 runs, and we present the averaged results along with the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Implementation details including software and hardware infrastructures listed in appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:
Answer: [Yes]
Justification: The attached code has undergone thorough scrutiny to guarantee anonymity and adherence the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
26

---

The discussion on both potential positive societal impacts and negative societal impacts of the work provided in appendix A.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the original paper that produced the code package or dataset and have explicitly stated the license used for the open-source frameworks.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
27

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi whrode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
28

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "moTZCmFz28", "reviewer": "Reviewer_o7Uk", "summary": "This paper investigates SSM theory to temporal graphs by integrating structural information into the online approximation with laplacian regularization term.", "questions": "1. Since one advantage of the SSM based methods is its small parameter size, then what's the size of the model compared with other baseline methods?\n\n2. The transformer based methods have better performance as shown in Table 1, do you include any transformer-based methods for the experimental comparison?\n\n3. What is the time complexity of the GraphSSM?", "limitations": "The authors provide the limitation in appendix E.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method has the theoretical support to show the effectiveness of the proposed method.\n2. The experimental results show that the proposed method outperform most of the baseline methds.\n3. This paper is well-motivated.", "weaknesses": "1. Since one advantage of the SSM based methods is its small parameter size, then what's the size of the model compared with other baseline methods? It's better to list the number of parameters to show the efficiency of the proposed method.\n\n2. The transformer based methods have better performance as shown in Table 1, do you include any transformer-based methods for the experimental comparison?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive reviews. Your concerns are addressed as follows:\n\n**W1 & Q1: Parameter size of GraphSSM and baseline models**\n\nThank you for your insightful suggestion. Per your suggestion, we have now included the comparison of parameter sizes between GraphSSM models and baselines on a large dataset arXiv.\n\n|       | STAR | tNodeEmbed | EvolveGCN | SpikeNet | ROLAND | GraphSSM-S4 | GraphSSM-S5 | GraphSSM-S6 |\n| ----- | ---- | ---------- | --------- | -------- | ------ | ----------- | ----------- | ----------- |\n| arxiv | OOM  | OOM        | 2.5M      | 780K     | 1.2M   | 294K        | 93k         | 229K        |\n\nAs observed from the table, GraphSSM, particularly GraphSSM-S5, shows superior parameter efficiency compared to other methods. This is attributed to the advantages offered by SSM models.\n\n**W2 & Q2: Comparison of transformer-based methods.**\n\nIn this work, we focus on **discrete-time temporal graphs**, which typically have long sequence lengths and are not suitable scenarios for transformers. Current works on transformer-based temporal graph learning mainly focus on **continuous-time temporal graphs**, leaving a significant gap for discrete-time temporal graphs. In this regard, we did not and cannot include transformer-based baselines in our experiments. And it is unfair to directly apply continuous-time methods to our specific settings for comparison. Therefore, we conduct an ablation study on GraphSSM by substituting the SSM architecture with Transformer and present the results below.\n\n|                      |  **DBLP-3**   |               |   **Brain**   |               |  **Reddit**   |               |  **DBLP-10**  |               |\n| -------------------- | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |\n|                      | **Micro-F1**  | **Macro-F1**  | **Micro-F1**  | **Macro-F1**  | **Micro-F1**  | **Macro-F1**  | **Micro-F1**  | **Macro-F1**  |\n| GraphSSM-Transformer |   85.02±1.1   |   84.98±0.8   |   93.47±1.5   |   93.11±1.1   |   43.48±0.7   |   43.11±0.5   |   75.65±0.8   |   74.32±0.6   |\n| GraphSSM-S4          |   85.26±0.9   |   85.00±1.3   |   93.52±1.0   |   93.54±0.9   | **49.21±0.5** | **49.05±0.7** | **76.80±0.3** | **76.00±0.4** |\n| GraphSSM-S5          | **86.29±1.0** | **85.78±0.9** |   93.00±0.4   |   93.01±0.4   |   44.75±0.4   |   44.79±0.4   |   75.19±0.6   |   73.95±0.4   |\n| GraphSSM-S6          |   86.10±0.5   |   85.70±0.6   | **93.80±0.3** | **94.47±0.6** |   43.11±0.9   |   42.85±1.1   |   74.09±0.3   |   73.16±0.2   |\n\nAs observed, GraphSSM-Transformer does not exhibit significantly superior performance in learning from discrete graph sequences compared to SSM-based architectures, despite introducing more memory and computation overheads.\n\n**Q3: Time complexity of the GraphSSM**\n\nGraphSSM is a discrete-time sequence model that performs a message passing step for each graph snapshot, followed by an SSM model for sequence learning. Assuming we have $L$ GNN layers and the sequence length is $T$, the full-batch training and inference time complexity for each graph snapshot with $L$ layers can be bounded by $\\mathcal{O}(L|\\mathcal{E}|d)$, which represents the total cost of sparse-dense matrix multiplication or message passing. We assume a hidden dimension of $d$ across all layers for simplicity.\n\n|                         |                                  |\n| ----------------------- | -------------------------------- |\n| Graph message passing   | $\\mathcal{O} (TL\\| \\mathcal{E}\\| d)$ |\n| Graph sequence learning | $\\mathcal{O}(T)$                 |\n\nThe main bottleneck of GraphSSM is the graph message passing step, which can be further optimized using techniques such as graph sampling[1] or graph condensation[2].\n\n[1] GraphSAINT: Graph Sampling Based Inductive Learning Method. ICLR 2020.\n\n[2] Graph Condensation for Graph Neural Networks. ICLR 2022.\n\n---\n\nWe would be grateful if you tell us whether the response answers your questipns of GraphSSM, if not, what we are lacking, so we can provide better clarification. Thank you for your time.", "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": "zs8bnmhBvT", "reviewer": "Reviewer_PUCW", "summary": "The paper introduces GRAPHSSM, a novel state space model framework for temporal graphs. GRAPHSSM extends state space models (SSMs) by incorporating structural information through Laplacian regularization to handle the dynamic behaviors of temporal graphs. The framework aims to overcome limitations of recurrent neural networks (RNNs) and Transformers in modeling long-range dependencies and managing computational complexity. The authors propose the GHIPPO abstraction for memory compression and various mixing mechanisms to handle unobserved graph mutations. Extensive experiments on multiple temporal graph benchmarks demonstrate the effectiveness and efficiency of GRAPHSSM.", "questions": "- Q1: I fail to understand the second part of Eq.(3).  Why does minimizing the second term of Eq.(3) amounts to increasing smoothness?  In addition, I don't think the interpretation/remark given in line 179-180 are correct. If $\\alpha$ goes to infinity, the whole objective, Eq.(3), is dominated by the second term. There is a degenerate solution $Z(s) = \\mathbf{0}$ (zero vector) that would minimize the objective. Which part of the objective/model prevent this degenerate solution?\n\n- Q2: Theorem 1 is saying that GHIPPO is \"nice\" because its parameter update can be described by the given ODEs. Can you further explain why this property is nice? does the benefit comes from better efficiency or inference performance? and how?\n\n- Q3: the discretization in the HIPPO paper was for computation purposes. In the case of temporal graph, where event and snapshot are inherently discrete. What is the (optimization) objective for discretization? i.e., what should be considered as a \"good discretization\" in this case?", "limitations": "N.A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and I enjoy reading the paper. The derivation of the method and the extension from SSM is technically sound\n\n- The the overall research direction is well-motivated and interesting. SSM is indeed a good potential candidate for modelling temporal graph.", "weaknesses": "- There already exists an important family of temporal graph neural networks (TGNNs) that use memory mechanism (see [1] and [2] for examples) and resemble a state transition model. The paper seems to neglect/be unaware of this line of related work.\n\n- There are parts of the method/extension that are not clear (see questions below for more details)\n\n- There are a couple of serious limitations regarding the empirical study: \n1) the baselines for the paper are rather outdated. The paper did not compare with the more recent TGNN models (e.g. above-mentioned memory-based temporal graph neural network, which is the SOTA for TGNN) \n2) the performance improvement from the proposed baselines is still marginal\n3) the conical task for temporal graph neural should be link prediction which is missing from the current study\n\n[1] Rossi, Emanuele, et al. \"Temporal graph networks for deep learning on dynamic graphs.\" arXiv preprint arXiv:2006.10637 (2020).\n\n[2] Zhang, Yao, et al. \"Tiger: Temporal interaction graph embedding with restarts.\" Proceedings of the ACM Web Conference 2023. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: Missing comparison of related works [1,2] and advanced methods**\n\nThank you for your suggestions. We have throughly reviewed the literature in temporal graph learning and have awared of several advanced works such as [3] and [4]. However, to our best knowledge, they are focusing on the **continuous-time tempora graph leanring** research and it is unfair to consider them as baselines for comparison under the discrete-time settings. We have explicitly clarified the situation in Related Work, and we will add a brief discussion with GraphSSM and continus-time methods in the next revision.\n\n\n**W2: Performance improvement is marginal**\n\nFirst of all, we respectively disagree with that the performance improvement is marginal. GraphSSM consistently achieves state-of-the-art performance and outperforms the runner-up baselines by significant margins, especially on the Reddit dataset. Secondly, scientific research is not a race; it is essential to place strong emphasis on other aspects of a method besides a single performance metric. GraphSSM shows superior performance while also exhibiting lower memory and computational overheads compared to other methods. This is also an important contribution of our work.\n\n**W3: Link prediction results**\n\nThank you for your suggestion. The results for the link prediction task are presented below. We follow the experimental settings of ROLAND, where the model leverages information accumulated up to time t to predict edges in snapshot t + 1.\n\n||DBLP-3||Brain||Reddit||DBLP-10||\n|-----------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|\n||AUC|AP|AUC|AP|AUC|AP|AUC|AP|\n|STAR|94.21±0.43|91.80±0.51|56.10±0.48|55.24±0.71|98.21±0.59|98.32±0.32|86.81±0.23|85.3±0.31|\n|tNodeEmbed|93.19±0.37|90.22±0.42|55.21±0.29|56.32±0.36|98.39±0.41|98.10±0.23|87.32±0.41|86.54±0.25|\n|EvolveGCN|94.01±0.62|91.05±0.39|56.33±0.41|56.91±0.55|98.77±0.39|98.80±0.13|88.32±0.24|87.19±0.50|\n|SpikeNet|92.53±0.57|90.11±0.51|54.95±0.58|55.88±0.64|97.97±0.12|97.06±0.24|86.88±0.17|85.40±0.18|\n|ROLAND|95.01±0.55|91.25±0.38|56.87±0.41|56.02±0.23|98.76±0.11|98.99±0.14|89.42±0.30|88.91±0.23|\n|GraphSSM-S4|95.47±0.23|91.58±0.24|57.74±0.45|56.92±0.21|99.59±0.32|99.24±0.20|90.62±0.45|90.12±0.37|\n|GraphSSM-S5|**96.45±0.15**|92.41±0.17|**58.49±0.33**|**57.40±0.31**|99.66±0.21|99.35±0.12|90.99±0.29|90.80±0.56|\n|GraphSSM-S6|95.88±0.31|**92.52±0.28**|56.77±0.41|57.16±0.25|**99.70±0.13**|**99.42±0.14**|**91.16±0.32**|**91.19±0.24**|\n\n\n**Q1: On remark 1 and degenerate solutions**\n\nThank you for pointing out the degenerate solution and we shall restate the remark in future revisions of our paper. Technically, the minimizers of Laplacian quadratic forms shall satisfy a smoothness condition over connected components of the underlying graph (please refer to our discussion in appendix B.1). It is correct that zero is a trivial solution that satisfies the smoothness requirement yet contains no useful information. Therefore the optimal solution is only non-trivial when the objective is a combination of $\\ell_2$ approximation and Laplacian regularization. Under such scenarios, the node features might be noisy themselves, and the Laplacian regularizer serves as a way to use neighborhood features as a (dynamic) denoiser.\n\n\n**Q2: What are nice properties of GHiPPO solutions?**\nThe GHiPPO solutions are desirable in the following aspects:\n\n- It allows a linear dynmaical system (LDS) representation under specific choice of approximation configurations, which is a nice property of HiPPO framework that is inherited by GHiPPO. Without a reasonable ODE representation, the approximation framework would have been only technically of interest but impractical.\n- ODE representations allow a constant memory update rule via utilizing a suitably defined discretization procedure. This ensures that the inference time memory and computational complexity is well-controlled.\n- GHiPPO also inherits the versatility of HiPPO in that the LegS configuration is not the only one that allows ODE parameterization. Indeed we may use alternative approximation schemes such as fourier approximation and the resulting framework is still efficiently computable and practical.\n\n**Q3: The semantics of discretization**\n\nThis is a very good question, and we think this is an important algorithmic challenge raised by the GHiPPO abstraction. In our framework, we view the underlying temporal graph as a collection of node feature processes together with a dynamically-changing topological relation among them. Under this framework, we regard graph snapshots as discrete observations of this underlying graph process. The objective of discretization is thus to develop a node state update rule that respects the graph dynamics, which is the central topic we discussed in section 3.2 of our paper. In particular, the existence of dynamic topological relations brings significant challenges to the discretization scheme (note that without topological relations, we can directly apply the ZOH discretization rule in a node-wise fashion) due to unobserved mutations of the underlying temporal graph which is conceptually depicted in equation (7) and figure 2 in our paper. Therefore, to study what should be a good discretization in this case, we first establish a dicretization rule in hindsight (the oracle discretization in theorem 2) and propose approximations to the oracle discretization thereafter. \n\n[3] DyGFormer: Towards Better Dynamic Graph Learning: New Architecture and Unified Library, NeurIPS 2023\n\n[4] SimpleDyG: On the Feasibility of Simple Transformer for Dynamic Graph Modeling, WWW 2024\n\n---\nThank you again for taking the time to review our paper. We hope our responses could clarify your concerns, and hope you will consider increasing your score. If we have left any notable points of concern unaddressed, please do share and we will attend to these points.", "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": "AekGunbkqM", "reviewer": "Reviewer_ZL4u", "summary": "The paper proposes an approach for processing discrete-time temporal graphs via an extension of state-space models (SSMs). In this direction, the main contribution of the paper is a generalization of the HIPPO framework for graph structured data (named GHIPPO), which defines how the state of different nodes should be updated through time to compress the evolution of nodes features (a solution capable of dealing with multiple changes that might happen between two snapshots is additionally introduced in the paper). In experimental evaluation, an SSM-based solution implemented with the proposed GHIPPO framework (named GraphSSM) outperforms a variety of approaches on both the moderately sized DBLP-3, Brain, Reddit and DBLP-10 datasets, and the large-scale arXiv and Tmall datasets.", "questions": "One thing that I think would be helpful to improve the strength of the paper is to run some experiments where the proposed SSM module is swapped with a RNN or transformer architecture. As we can see from the ablation study of table 5, it appears that the mixing strategy one might decide to use is relevant to outperform prior art. As a result of this, I wonder what would be the performance that a comparable solution would have with the very same architecture used by the authors but without using any SSM approach. This will clearly provide an indication on whether using SSMs is beneficial for achieving the desired performance (which is the main claim of the paper) or whether the results we see in Table 2 and 3 are only due to the mixing strategy.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "While I’m personally not an expert in SSM models, I generally found the paper to be an interesting read (to the best of my knowledge there is not much work on applications of SSMs to graph-structured data, and as such the work highlights a research direction possibly worthy of further exploration). The presentation of the paper is generally understandable (albeit not always clear in some spots, see weaknesses), and allows a reader unfamiliar with the SSM literature to grasp the overall idea of the paper. The experimental evaluation of the paper appears well done (with the proposed approach outperforming prior art on a variety of different datasets), although there might be room for improvement.", "weaknesses": "Generally I do not have many weaknesses to highlight in the paper. From a technical perspective, I would want to highlight that: \n\n1) the proposed approach might face some issues with heterophilic graphs (as the smoothness in the node state imposed in equation (3) is not necessarily a good regularizer in that setting - see point 5 below) \n\n2) the proposed methodology is limited to discrete-time temporal graphs, and further work would need to be done to extend the model to a continuous-time setting (this is also highlighted by the authors themselves in the paper). \n\nFrom a different perspective, a weakness of the paper is probably its exposition, which in some parts is a little confusing and could be improved. In this direction:\n\n1) lines 67, I believe there is a typo and the authors should replace “features the dynamics” with “the features dynamics”\n2) line 74 to 77 are quite unclear and should probably be refactored\n3) line 105, “recurrence model” should probably be replaced with “recurrent model”\n4) Table 1, while it is true that classic transformers have a quadratic space and time complexity, there are also efficient transformers (e.g. Performs) that show linear space and time complexity. I believe these are not mentioned in the paper and probably they should, in order to provide to the reader a complete picture of where we stand with transformer architectures.\n5) I believe the smoothness in node state imposed in equation 3 with the dirichlet energy regularizer makes sense only on homophilic graphs, and might not be a meaningful prior to use when dealing with heterophily. This is not pointed out in the paper and probably it should be highlighted as a possible limitation.\n6) Lines 180-181, the authors mention that what minimizes equation 3 is a piecewise vector. I believe what they mean is that the solution is piecewise over time, I think this should probably be clarified in the paper as it might be a source of confusion\n7) line 184-185, how the nodes' memories are parameterized as polynomials is very unclear here. How are those polynomials defined? What is the input to such polynomials? It might be that a reader familiar with the HIPPO framework would be aware of such details, but the lack of an explanation in the text makes it hard to draw a complete picture here.\n8) lines 335-336, GraphSSM with S5 doesn’t always achieve poor performance (it is indeed the best performing model on DBLP-3 in table 4). This should be clarified in the text.\n9) line 339, I believe there is a typo and the “and” at the beginning of the sentence should be fixed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable and insightful comments, and we provide our responses below.\n\n**W1: heterophilic graphs issues**\n\nThank you for your question. We agree with you that equation (3) reflects a prior belief that the node representation generated by GHiPPO should be homophilic under the representation level [3] at any time point. While being empirically effective, it poses significant challenge when the underlying temporal graph has more complex characteristics, and we will discuss it in revisions of our paper. Indeed, we do think that defining a proper homophily metric when the underlying graph is treated as a process is itself a valuable future research question.\n\n**W2: Typos or misunderstandings  in Line 67, Lines 74-77, Line 105, Lines 180-181, and Line 339**\n\nWe appreciate the reviewer for pointing out the careless errors. In the revision, we will make thorough proofreading to enhance readability by correcting any typos and improving the writing.\n\n**W3: Table 1 may not be entirely accurate**\n\nThank you for bringing this to our attention. We agree that Table 1 may not be entirely accurate in all cases. In this context, \"Transformers\" refers to traditional \"softmax Transformers.\" We will include a note to clarify this and prevent any potential misunderstandings. We will also provide a comprehensive discussion on this matter, as outlined below:\n\nIndeed, there are close relationships between transformers with finite kernel feature maps (which are essentially what efficient transformers rely on), RNNs and SSMs [1, 2]. All of the three allow a recurrent parameterization and constant-memory-linear-compute inference. The primary difference is the update rule during recurrence: Linear transformers essentially use a unitary state matrix that is not learnable, while standard RNNs use learnable but not well-controlled state matrix. SSMs use an improved and learnable state matrix by adopting more careful initializations.\n\n**W4: On semantics of node memory**\n\nWe will add a more accessible and detailed introduction to the background on HiPPO abstraction in revisions of our paper. Specifically, by an $N$-dimensional node memory at time $t$ we mean the coefficients of some order-$N$ polynomial (under the orthogonal polynomial basis) that optimally approximate the node features (viewed as a function over time) up until time $t$. The rationale of this representation is that a finite dimensional function space spaned by polynomials are characterized by their coefficients, thereby allowing us to **embed functions into finite dimensional vectors**. Now we answer your question: The inputs to the approximation polynomial is time $t$. The coefficients $u(t)$ of the polynomial is determined by an optimal approximation criteria, and constitues the node memory at time $t$.\n\n**W5: Performance of GraphSSM-S5**\n\nThank you for your suggestion. We will address it and provide clarification in the revisions.\n\n**W6: Ablation study on swapping SSMs with RNN and Transformer**\n\nThak you for your insightful suggestion. We replaced the SSM architecture with RNN and Transformer and present the results below. As observed, SSMs prove to be a superior choice compared to RNNs and Transformers. While Transformers excel in NLP tasks, they are not well-suited for discrete graph sequences.\n\n||**DBLP-3**||**Brain**||**Reddit**||**DBLP-10**||\n|--------------------|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|:-----------:|\n||**Micro-F1**|**Macro-F1**|**Micro-F1**|**Macro-F1**|**Micro-F1**|**Macro-F1**|**Micro-F1**|**Macro-F1**|\n|GraphSSM-RNN|84.24±1.3|83.10±1.4|92.28±1.5|92.43±1.0|43.11±1.7|43.15±1.7|73.46±1.5|72.93±1.5|\n|GraphSSM-Transformer|85.02±1.1|84.98±0.8|93.47±1.5|93.11±1.1|43.48±0.7|43.11±0.5|75.65±0.8|74.32±0.6|\n|GraphSSM-S4|85.26±0.9|85.00±1.3|93.52±1.0|93.54±0.9|**49.21±0.5**|**49.05±0.7**|**76.80±0.3**|**76.00±0.4**|\n|GraphSSM-S5|**86.29±1.0**|**85.78±0.9**|93.00±0.4|93.01±0.4|44.75±0.4|44.79±0.4|75.19±0.6|73.95±0.4|\n|GraphSSM-S6|86.10±0.5|85.70±0.6|**93.80±0.3**|**94.47±0.6**|43.11±0.9|42.85±1.1|74.09±0.3|73.16±0.2|\n\n**Q1: Link prediction results**\n\nThank you for your suggestion. The results for the link prediction task are presented below. We follow the experimental settings of ROLAND, where the model leverages information accumulated up to time t to predict edges in snapshot t + 1.\n\n||DBLP-3||Brain||Reddit||DBLP-10||\n|-----------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|\n||AUC|AP|AUC|AP|AUC|AP|AUC|AP|\n|STAR|94.21±0.43|91.80±0.51|56.10±0.48|55.24±0.71|98.21±0.59|98.32±0.32|86.81±0.23|85.3±0.31|\n|tNodeEmbed|93.19±0.37|90.22±0.42|55.21±0.29|56.32±0.36|98.39±0.41|98.10±0.23|87.32±0.41|86.54±0.25|\n|EvolveGCN|94.01±0.62|91.05±0.39|56.33±0.41|56.91±0.55|98.77±0.39|98.80±0.13|88.32±0.24|87.19±0.50|\n|SpikeNet|92.53±0.57|90.11±0.51|54.95±0.58|55.88±0.64|97.97±0.12|97.06±0.24|86.88±0.17|85.40±0.18|\n|ROLAND|95.01±0.55|91.25±0.38|56.87±0.41|56.02±0.23|98.76±0.11|98.99±0.14|89.42±0.30|88.91±0.23|\n|GraphSSM-S4|95.47±0.23|91.58±0.24|57.74±0.45|56.92±0.21|99.59±0.32|99.24±0.20|90.62±0.45|90.12±0.37|\n|GraphSSM-S5|**96.45±0.15**|92.41±0.17|**58.49±0.33**|**57.40±0.31**|99.66±0.21|99.35±0.12|90.99±0.29|90.80±0.56|\n|GraphSSM-S6|95.88±0.31|**92.52±0.28**|56.77±0.41|57.16±0.25|**99.70±0.13**|**99.42±0.14**|**91.16±0.32**|**91.19±0.24**|\n\n\n[1] Transformers are rnns: Fast autoregressive transformers with linear attention. ICML, 2020.  \n[2] Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. arXiv 2024.  \n[3] Luan, Sitao, et al. \"Is heterophily a real nightmare for graph neural networks to do node classification?.\" arXiv preprint arXiv:2109.05641 (2021).\n\n---\n\nWe hope our responses were helpful in adequately addressing your earlier concerns. In case you have any further questions or comments, please let us know, and we will gladly respond.", "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:

Meta-review: This paper presents a well-motivated and technically sound approach to applying state space models (SSMs) to temporal graph neural networks (TGNNs), supported by strong theoretical foundations and promising experimental results. However, it has some limitations, such as the lack of comparison with recent memory-based TGNNs, which are state-of-the-art, and the omission of key tasks like link prediction in the empirical evaluation. Additionally, the model's applicability is limited to discrete-time graphs, and potential issues with heterophilic graphs warrant further exploration. Despite these drawbacks, the paper offers a valuable and interesting research direction.
Decision: Accept (poster)