Space-Time Graph Neural Networks
Authors: Samar Hadou
Charilaos I Kanatsoulis
Alejandro Ribeiro
Venue: ICLR 2022 Poster (2022)
Keywords: ST-GNNs
GNNs
stability
graph-time perturbations

Abstract: We introduce space-time graph neural network (ST-GNN), a novel GNN architecture, tailored to jointly process the underlying space-time topology of time-varying network data. The cornerstone of our proposed architecture is the composition of time and graph convolutional filters followed by pointwise nonlinear activation functions. We introduce a generic definition of convolution operators that mimic the diffusion process of signals over its underlying support. On top of this definition, we propose space-time graph convolutions that are built upon a composition of time and graph shift operators.  We prove that ST-GNNs with multivariate integral Lipschitz filters are stable to small perturbations in the underlying graphs as well as small perturbations in the time domain caused by time warping. Our analysis shows that small variations in the network topology and time evolution of a system does not significantly affect the performance of ST-GNNs. Numerical experiments with decentralized control systems showcase the effectiveness and stability of the proposed ST-GNNs.

Published as a conference paper at ICLR 2022
SPACE-TIME GRAPH NEURAL NETWORKS
Samar Hadou, Charilaos Kanatsoulis & Alejandro Ribeiro Department of Electrical and Systems Engineering University of Pennsylvania (selaraby, kanac, aribeiro) @seas, upenn edu
ABSTRACT
We introduce space-time graph neural network (ST-GNN), a novel GNN architec- ture, tailored to jointly process the underlying space-time topology of time-varying network data. The cornerstone of our proposed architecture the composition of time and graph convolutional filters followed by pointwise nonlinear activation functions. We introduce generic definition of convolution operators that mimic the diffusion process of signals over its underlying support. On top of this definition, we propose space-time graph convolutions that are built upon a composition time and graph shift operators. We prove that ST-GNNs with multivariate integral Lipschitz filters are stable to small perturbations in the underlying graphs as well small perturbations in the time domain caused by time warping. Our analysis shows that small variations in the network topology and time evolution of a system does not significantly affect the performance of ST-GNNs. Numerical experiments with decentralized control systems showcase the effectiveness and stability of the proposed ST-GNNs.
INTRODUCTION
Graph Neural Networks (GNNs) are powerful convolutional architectures designed for network data. GNNs inherit all the favorable properties convolutional neural networks (CNNs) admit, while they also exploit the graph structure. An important feature of GNNs, germane to their success, is that the number of learnable parameters is independent of the size of the underlying networks. GNNs have manifested remarkable performance in plethora of applications, e.g., recommendation systems (Ying et al. 2018 Wu et al. 2020), drug discovery and biology (Gainza et al., 20200: Strokach et 2020: Wu et 2021 Jiang et al. (02T), resource allocation in autonomous systems (Lima et al. 2020
Cranmer et al. 22021). to name few.
Recently, there has been increased interest in time-varying network data, as they appear in various systems and carry valuable dynamical information. This interest mostly prominent in applications
decentralized controllers (Tolstaya et al.. 2020 Gama et al.
2020b Yang and Matni 2021; Gama
and Sojoudi| (02T), traffic-flow forecasting Yuu ct al. 2018 Li et al.
2018 Fang et al. (022). l), and
skeleton-based action detection (Yan et al. 2018 2 et al. 2020 Pan al. 2021). 1). The state-of-
the-art (SOTA) usually deploys an additional architecture side by side with a GNN so the latter learns patterns from the graph domain while the former works on the time sequences. One choice could be a CNN as in (Li et al. 2020 [sufi and Mazzola 2022 Wang et al.] (021) or a recurrent neural network (RNN) as in (Seo et al. 2018, Nicolicoit
al. 2019; Ruiz et 2020). However, these joint architectures are performed in a centralized manner in the sense that the up-to-date data of all nodes are given any given time. While this well suited for, but not limited to, the case of social networks and recommendation systems, many physical-network applications are decentralized in nature and suffer from time delays in delivering messages.
In this paper, we close the gap by developing a causal space-time convolutional architecture that jointly processes the graph-time underlying structure. That is, the convolutional layers preserve time delays in message passing. Our work is motivated by the following question. Is it possible to transfer learning between signals and datasets defined over different space-time underlying structures? This is well motivated question since in practice we execute these architectures on graphs that are different from the graphs used in training and signals are sampled at different sampling rates between training and execution. The answer to the above question was provided for the case of static graph signals in

---

Published as a conference paper at ICLR 2022
(Gama et al. 2020a), where the stability of traditional GNNs to graph perturbations proved. In this work we give an affirmative answer to the above question in the case when time-varying graph signals are considered and space-time convolutional architectures are employed.
The contribution of this paper is twofold. First we introduce a novel convolutional architecture for time-varying graph signals, and second prove its stability. Specifically, provide a general definition of convolutions for any arbitrary shift operator and define a space-time shift operator (STSO) as the linear composition of the graph shift operator (GSO) and time-shift operator (TSO). We then introduce space-time graph neural networks (ST-GNNss, a cascade of layers that consist of space-time graph filters followed by point wise nonlinear activation functions. The proposed ST-GNN allows processing continuous- time graph signals, which is pivotal in the stability analysis. Furthermore, we study the effect of relative perturbations on ST-GNNS and prove that small variations in the graph and/or irregularities in the sampling process of time-varying graph signals do not essentially affect the performance of the proposed ST-GNN architecture. Our theoretical findings are also supported by thorough experimental analysis based on decentralized control applications.
The rest this paper structured as follows. The related work is summarized in Section 2 Sections 4 present our contributions listed above. Numerical experiments and conclusions are presented in Sections 5 and 6 respectively. The proofs and extended experiments are provided in the appendices.
Notation: Bold small and large symbols, i.c. x and X, denote vectors and matrices, respectively. Calligraphic letters mainly represent time-varying graph signals unless otherwise stated.
2 RELATED WORK
GNNs for Time-varyine Graph Signals. One of the early architectures Yan al. 2018), which introduced a convolutional filter that aggregates information only from 1-hop neighbors. Relying on product graphs. (Isufi and Mazzola 2021) introduced convolutional architecture, where each node has access to the present and past data of the other nodes in the graph. A similar convolutional layer was studied in (Pan et al., [2021 Loukas and Foucard 2016), and while restricted domain that preserves time delays, (Pan et al. 2021) shows that it is not necessarily less expressive. Meanwhile, (Wang et al., 2021) performs GNNs over graph signals at each time instance separately before a temporal convolution is performed at the GNN outputs to capture the evolution of graph embeddings. Graph RNNs are another architecture developed to deal with time-varying graph signals. For example, (Pareja et al. 2020) uses an RNN to evolve the GNN parameters over time. Moreover, (Hajiramezanali cct al. expressive power. However, all these architectures did not take into account the physical restrictions in the form of time delays, associated with decentralized applications.
2019 combined the GRNN with a variational autoencoder (VGAE) to improve the former's
Similar to work, other architectures considered the diffusion equation form message-passineg layers, e.g., (Xhonneux et al.) 2020 Poli et al., 2021] Fang et al., (002). These architectures parame- terize the dynamics of graph signals with GNNs. In simple words, they learn parameterization that helps find the current state variables from the previous ones. The architecture in (Chamberlain et al., 202T) is another example of these architectures, but learns the graph weights instead of limited number of filter coefficients (i.e., it resembles the parameterization of graph attention networks in (Veličković et al. 2018)).
Stability. Deformation stability of CNNs was studied in (Bruna and Mallat 2013 Bietti and Mairal
2019). The notion of stability was then introduced to graph scattering transforms (Gama et al.
2019 Zou and Lerman, 2020). In following work, /ama et al. (2020a) presented study of GNN stability to graph absolute and relative perturbations. Graphon neural networks was also analyzed in terms of its stability in (Ruiz et al.) (021). Moreover, (Pan et al., 202 proves the stability to absolute perturbations of space-time graph scattering transforms.
SPACE-TIME GRAPH NEURAL NETWORKS
In this section, we present the proposed ST-GNN architecture for time-varying graph signals. First, we provide a general definition of convolutions and then we develop the space-time graph filters, which are the cornerstone of the ST-GNN architecture.
2

---

Published as a conference paper at ICLR 2022
Our analysis starts with the homogeneous diffusion equation, which is defined with respect to the Laplacian differential operator
ax(()) -(X((..
Equation (T) describes processes of signals that evolve across the diffusion dimension, The diffused signal, xt),), is modeled as an abstract vector in a vector space V. The vector space is associated with an inner product (.,.)y, and closed under addition and scalar multiplication, e.g., n-dimensional
vector spaces and function spaces. The solution of (T) is (t) e (0) e e-t2 Xg = e e- X (the subscript omitted in what follows), and describes the signal after time t from the initial state.
3.1 CONVOLUTION
With the diffusion equation in our hands, we can now define the convolution operation as the linear combination of the diffusion sequence with a filter h(t).
Definition (Convolution Operator). For a linear shift-invaring filter with coefficients h(t), 2 the convolution between the filter and an input signal X E V, with respect to linear differential operator L - V, is defined as
h h&D X x- h(t)e 1 XXxt,
where *D denotes the convolution operator applied on signals with underlying structure D.
Definition 1 is a valid convolution operator. With abuse of notation, we refer to L as the shift operator but it should be understood that the shift operation is executed using e- Definition establishes a generalized form of convolutions for wide variety of shift operators and signals. Next we discuss two convolution types of practical interest that follow directly from 2 i.e., time convolutions and graph convolutions.
They involve continuous- time signals, denoted by x<T), that are elements of square- -ntterrit function spaces, i.e, x(T) E (R). The underlying structure of z<T) )) is the real line, since the time variable T E R. In order to generate the traditional definition time convolution, the time shift operator (TSO) is chosen as the differential operator, L, 0/8r. One can show that e 19f0- x(T) = x(T f), using the Taylor series,
Time Convolutions:
(-))m 8t
8
e 19/o x<())
Orn a(()))
(())())-
0r =() = =(()).
R=0 n!
n!
with u = T- t. In other words, the TSO performs a translation operation. Then 2
reduces to
x(7) *R h(TT) - h(t)= /.a0 h(t)e 19/or x(rr)t- //" f ((())(T-t))))
(3)
which is indeed the traditional definition of convolutions between time signals. It is also worth noting that ejur, Yu [0, oc) are eigenfunctions of the TSO C, 8/0r with associated eigenvalues jw.
This observation is pivotal in the stability analysis of section
They involve graph signals, x E (TR that are N-dimensional square- summable vectors containing information associated with N different nodes. The underlying structure of x is represented by a graph = (V, W). where is the set nodes with cardinality |V = N, 3 CCM V x V is the set of edges, and W E + R is map assigning weights to the edges (Shuman et al. 2012). The graph shift operator (GSO), S E R. N X is a matrix representation of the graph sparsity, e.g., graph adjacency or Laplacian (Ortega et al. 2018). Applying S to a signal x results in a signal Sx, where [Sx]; represents aggregated data from all nodes j that satisfy that (i,j) e & or (j, E. We focus undirected graphs, and therefore, S is real symmetric and diagonalizable matrix with a set of N eigenvectors [v:) each associated with a real eigenvalue X,-
Graph Convolutions:
The GSO a linear operator S: L (RR + I.2 (IR that deals with discrete signals. Therefore, is more common to discretize the diffusion process over graphs at times KT,, k zt, where T, is the sampling period. The convolution is then defined as
K-1
X kg h
h&c
AS
(4)
k=0
3

---

Published as a conference paper at ICLR 2022
where {he h is the filter coefficients and K is the number of filter taps. The finite number of taps is a direct consequence of
Hamilton theorem, and h is a finite-impulse response (FIR) filter. Equation ( generalizes graph convolutions in the literature, where convolutions are defined as polynomials in the shift operator, i.e., &g h Ek=o S (Sandryhaila and Moura 2013). This definition executes the shift operation using the matrix directly compared in
3.2
SPACE- TIME CONVOLUTION AND GRAPH FILTERS
The generalized definition of convolution in as well as the definitions of time and graph convolutions in (3). 4 respectively, set the ground for the space-time convolution. Space-time convolutions involve signals that are time-varying and are also supported on graph. They are represented by
X [ @ I,2 (TR), where @ is the tensor product [see (Kadison and Ringrose, 1983; Grillet 2007 between the vector spaces of graph signals and continuous-time signals. In the following, calligraphic symbols (except L) refer to timevnryying graph signals unless otherwise is stated.
The space-time shift operator (STSO) is the linear operator that jointly shifts the signals over the space-time underlying support. Therefore, we choose the STSO to be the linear composition of the GSO and TSO, i.e., L = S L,.
The convolution operator in Definition can be specified with respect to the STSO for time-varying graph signals
h * X'
h(t)e (Soc. X't =: H(S, C,)
J
where HSS, 4+) = Io (())e ((t)e-ttoL, tSoL. dt represents the space-time fitte. The frequency response of the filter is then derived [see Appendix A
h(A.jw)
hu(t)e
((())=-(A++j)) ((A+j=) dt.
Remark 1. The space-time graph filters can be implemented distributively. For each node, the operator (e- (e-SoL,) aggregates data from the t-hop neighbors after they are shifted in time. This process can done locally after each node acquires information from their neighbors. The time shift I represents the time required for the data to arrive from the I-hop neighbors.
3.3 SPACE-TIME GRAPH NEURAL NETWORKS
The natural extension of our previous analysis is to define the convolutional layer of ST-GNNs based on the space-time graph filters in (5) However, learning infinite-impulse response (IR)) filters is impractical and thus we employ FIR space-time graph filters, defined as Ha(S Σ2) K-1 hgg-kT,SeC,, The ST-GNN architecture employs cascade of L. layers, each of which consists of bank of space-time graph filters followed by a pointwise nonlinear activation functions, denoted by The input to layer E is the output of the previous layer, X₁_1, and the output of the éth
layer is written as
F1-1 Σ
x/
KT,SoC, X.
for each feature x/ - 1, Fe. The number of features at the output of each layer denoted by Ft, 2 = 1,..., L. A concise representation of the ST-GNN can be written as ( H, S L,), where H. is the set of all learnable parameters { f.g k.k An interesting remark is that the time-varying graph signals processed in (7) are continuous in time, but learning a finite number of parameters. Remark The ST-GNNs are causal architectures, that is, the architecture does not allow the nodes to process data that are still unavailable to them. This is achieved by delaying the data coming from the h-hop neighbors by lo time steps {c.f. (7)). Therefore, each node has access to its own up-to-date data and outdated data from their neighbors.
4 STABILITY TO PERTURBATIONS
In this section, we perform a stability analysis our proposed ST-GNN architecture. particular, we characterize the difference between the filters H(S, and H(S, Σ,), where and Σ, are perturbed versions of the graph and time shift operators, respectively.
4

---

Published as a conference paper at ICLR 2022
4.1 PERTURBATION MODELS
Before we study the effect of graph and time perturbations on the stability of our proposed ST-GNN, we first need introduce a perturbation model in space and time. For graph perturbations, we follow the relative perturbation model proposed in (Gama et al. 2020a):
PTSPP S + SE ES,
where $ is the perturbed GSO, E is the error matrix and Po is a permutation matrix. Taking a closer look in equation ( we observe that the entries of S and Š become more dissimilar as the norm increases. The dissimilarity is measured by the difference [S] [P] SPok, [SE],, + ESS kj where each summand a weighted sum of the edges that are connected to nodes and j. respectively, For nodes and j with high node degrees, the sum includes a high number of non-zero entries from S, which leads to perturbations of high volume. Consequently, the considered graph perturbations are relative to node degrees. It is also worth noticing that equation (8) is invariant to node permutations of the GSO. This due to the use of Po which reconciles for node relabelling of perturbed graphs (see Section 4.2)
E
While there has been plenty of work regarding graph perturbation models, time perturbation in the context of graph neural networks is not well studied. In this paper fill this gap and propose practical model for time perturbations. of sampling continuous-timg time signals, zxr). It is often the case that sampling is imperfect and not exactly equispaced, i.e., the discrete signals are captured at times kT, + xKTT), where E Z, T, E R is the sampling period and R R is differentiable function. To model this phenomenon, we use time-warping operations. In particular, we consider a perturbed timeline i ++++0 2(r), and we observe the signal ar()) <x(T + z(7)) instead of s(r). The diffusion process in ( for continuous-tiin -time signal, over the perturbed timeline, can then be cast as
particular, we study irregularities that appear in the process
a Øt x((, 4) = Of xl(,,))
θ
2 Øt
x(1 +(()) (1 + (T))
Ør att, T 2()))
(9)
Now, let {(T) (T) C, or. and É, 87 Then the perturbed TSO takes the form
(1+ C,
(10)
The effect of time perturbation is controlled by ((T). As the norm [|E(T)]l grows, the dissimilarity between the original and perturbed time shift operators increases. This shows that the considered time perturbation model is relative to the rate of change of 2(T); faster changes in 2(T) produce
more significant perturbations (i.e., longer time shifts), whereas smoother choices of 2(7) yield lower values of [[(()]]2 and lower perturbation levels. The time convolution in (3) with perturbed TSO becomes
z([ + +())) *R h(T)
h(t)e h(())=((+(())) x(T + 2(T))
h(t)e b(t))==(L+ ((r)))))eeeer(r((( x(T)
(11)
since æ<7 a(T x(7)) +(T)) turbations. Moreover, the perturbed TSO e CL)) models time-varying shift of t(1 E(r)) when {(T) is not a constant (which is the case in our analysis).
x(()), which models a signal translation (+()), caused by time per-
4.2 JOINT OPERATOR- DISTTANCE MODULO
In order to proceed with the stability analysis, we need to define the operators used measure the effect of perturbations. We start with the measure of graph perturbations as we utilize the operator distance modulo permutation, [|-||p, introduced in (Gama et al., 2020a). For any two graph operators N) ), the distance between them can be calculated as
A and A (RR - L2((RN)
A
min max PEP xx||=|==1
Ax - p" 1''pp''PPPPP APx|22
(12)
where P is the set of all permutation matrices. This distance measures how close an operator À to being permuted version of A. The distance in permuted versions of each other.
(12) is minimum (i.e., 0) when the two graphs
Next, we define operator distance modulo translation for time operations:
5

---

Published as a conference paper at ICLR 2022
Definition 2 (Operator Distance Modulo Translation). Given the linear time operators B and B: 1.2 (R) T,² define the operator distance modulo translation
B Bl
min SER
max [x((T)
(E- BB)z(T)
(13)
2: 2=1
The expression (33 measures how far or close two time operators are, to being translated versions of each other. In the case where Ê, = (1+)(T)) C, as in (T)), the distance between B e- and B = e -tè- reduces to
|le e the
|T
min max sER x:||=||==1
||((T - 1) - x - 8- -- 16(T 1))12-
(14)
Since we are dealing with time-varying graph signals and joint time and graph perturbations, we com- bine the two previously defined distances and introduce the operator distance modulo permutation- translation.
Definition 3 (Operator Distance Modulo Permutation- -raniiittinaaaaatiinn Given the graph and time op- erators A, (TR + (.R B,B B: (2R >> T.2 (R)),, define the operator distance modulo
permutation-tronslattinn
A B A A
min min max PEP sER x
- -PTAP) sc. o oB)x (15)
4.3 STABILITY PROPERTIES OF SPACE-TIME GRAPH FILTERS
The last step before we present our stability results is to discuss integral Lipschitz filters, which are defined as:
Definition 4 (Multivariate Integral Lipschitz Filters). Let the frequency response of a multivariate filter be h(w): : R + IR. The filter said to integral Lipschitz if there exists a constant such that for all and w2.
W2 W
h(wz) - h(w1)) 2C
(16)
W2 + Will2
The condition in (16) requires the frequency response of the filter to be Lipschitz over line segments defined by arbitrary W| and W2 E IR", with a Lipschitz constant that is inversely proportional to their midpoint. For differentiable filters the above condition reduces to
(ac (((1))
< C willa for
every ( that is component w1. The proposed space-time graph filters admit frequency response which is bivariate with variables À and ju [cf. (6)]. Following Definition 4 space-time graph filter h(A,jw) is integral Lipschitz, if
2 jww I SC JA E {A,jw). O
| + jul
(17)
Note that the vector W1 in this case is given as [Λ, A with || 1111221 = |A A The conditions in (7 indicate that the frequency response of an integral Lipschitz space-time graph filter can vary rapidly at low frequencies close to 0. Therefore, the filter can discriminate between close frefereuencyy spectral components, but is more flat high frequencies, prohibiting discriminabilityy between the spectral features in these bands. Note that when we mention low frequencies in the context of space time graph filters (or ST-GNNs later), we refer to low values of and w, whereas high frequencies correspond to high values of À or
Proposition 1 (Stability to Graph Perturbations). Consider a space-time filter H along with graph shift operators and S, and a time shift operator L,. If it holds that
(Al) the GSOs are related by P SP, = + SE + ES with Po being a permutation matrix. (A2) the error matrix E has a norm [E| < e.. and an eigenvector misalignment ó relative to S, and
(A3) the filter H(S, f.) is an integral Lipschitz filter with a Lipschitz constant C O, then
the difference between the space-time filters H(S, and H(S,C, Lx) is characterized by H(S H(SSL 2Ce, (1 (1+5VN) O
(18)
where 8 [||U V|| + 1)2 1, and N is the number of nodes in S.

---

Published as a conference paper at ICLR 2022
Proposition states that space-time graph filters are stable graph perturbations of order O(c,) with a stability constant 2C + OvN). The constant is uniform for all graphs of the same size and depends on the Lipschitz constant of the filter. The bound is proportional to the eigenvector misalignment between the GSO and the error matrix. The misalignment bounded and does not 8 with U and V being unitary matrices. Now, consider type of perturbations known as graph dilation, where the edge weights stretch by a value 6s, i.e., the GSO becomes $ = (1 + G,)S. In this case, the eigenvalues of the GSO also stretch by 6x. but the eigenvectors are no longer misaligned, i.e., 6 = O. The bound for graph dilation then reduces to 2C's and does not depend on the structure of the underlying graph. Therefore, it is inferred that the bound in [8) is split into (i) term that reflects the difference in eigenvalues between S and S, and (ii) term that arises from the eigenvector misalignment. Note that the stability constant is not affected by any property of the TSO, and consequently has the same form of the one derived by Gama et al. (2200a) for traditional graph filters.
grow with the graph size as 5 < [|| + |V + 1)²
Proposition 2 (Stability to Time Perturbations). Consider spuce-time graph filter H along with time shift operators L, and E,, and graph shift operator S. If it holds that
(Al) the TSOs are related by - (1))(T) L,,
(A2) the error function E(T) is infinitely differentiable with a norm IIE(T)]l2 S. Ke,, and the norm of the mih-order derivative| (| (T) is of order ( where K. is an absolute constant, and
(A3) the filter H(S, Cr) is an integral Lipschitz,ilte filter with a Lipschitz constant C 0, then
the difference between the space-time filters H(S, and H(S, satisfies
(S, - H(S, (T) S CRey + ((2))
(19)
Similarly to Proposition [ the filter difference is bounded by a constant proportional to the size of perturbation, i.e., [1[(T)]l, and the bound is also affected by the Lipschitz constant of the filter.
The perturbed TSO shares the same eigenfunctions with the original TSO since e, jw ((T))e"uT Therefore, the difference between the filters only arises from the difference in eigenvalues. It is worth mentioning that the assumption (A2) of Proposition 2 is rather reasonable. One example of a tirp-ng function z(T) that satisfies this assumption is 2(7) = ve, cos(c,7)e The
error function is then ((T) 2'(r) 2/// (sin E,T + cos (TT)e with a norm of / / The first derivative of the error function is (T() - -er 3/2 cos(e,r)e and its norm is of order Oce)), which increases exponentially with the order of the derivatives.
In Theorem I we consider joint time and graph perturbations, and characterize the difference between the filters under the STSO, S Lr, and its perturbed version $ L..
Theorem 1 (Space- Time Graph Filter Stability). Under the assumptions of Propositions 7 and the distance between the space-time graph filters H(S, f.) and H(S, f.) satisfies
|H(S, - (,($,,)))lP. & 2Cta (1 (1- SVN) + CRe, + O(E),
(20)
where c = max (c,, ).
In order to keep this stability bound small, space-time graph filters should be designed with small Lipschitz constant C. This comes at the cost of filter discriminability at high frequeneies [cf. [[]].
whereas at low frequencies, the integral Lipschitz filters are allowed to vary rapidly. Thus Theorem !
shows that space-time graph filters are stable and discriminative at low frequencies but cannot be both stable and discriminative at higher frequencies.
4.4 STABILITY PROPERTIES OF SPACE- TIME GRAPH NEURAL NETWORKS
Theorem establishes the stability of the proposed ST-GNN architecture.
Theorem 2 (ST-GNNs Stability). Consider an L-layer ST-GNN (::; H. Lx) with single feature per each layer. Consider also the GSOs S and S, and the TSOs L, and É.. If
(Al) the filters at each layer are integral Lipschitz with a Lipschitz constant C > 0 and have unit operator norms, i.e., (S,(S,,,)) = 1, V, 1,..., L, (A2) the nonlinearirties o are hipschitz-continnnnt with a Lipschitz constant of 1, i.e., (1a(x2)
oxx))l )|12 & ||x2 X1 11112.
7

---

Published as a conference paper at ICLR 2022
(A3) the GSOs satisfy (AI) and (A2) of Proposition 7 and the TSOs satisfy (AI) and (A2) of
Proposition 2 then
( H. 1.) S 2CLe, (1+8VN) CLRE, +
$ ( C2)
(21)
where c max
Theorem 2 shows that the stability bound of ST-GNNS depends on the number of layers L, in addition to the factors affecting the stability of space-time graph filters. Compared to space-time graph filters, ST-GNNs can be both stable and discriminative. This is due to the nonlinearities applied at the end of each layer. The effect of the pointwise nonlinearity is that it demodulates (i.e., spills) the energy of the higher-frequency components into lower frequencies [see (Gama et al.] 2020a)]. Once the frequency content gets spread over the whole spectrum by the consecutive application of the nonlinearities, the integral Lipschiz filters in the deeper layers become discriminative. The stability/disrrmmnabbin
property of ST-GNNs is a pivotal reason why they outperform space-time graph filters.
NUMERICAL EXPERIMENTS
We examine two peceettaalizedccomrrollo applications: flocking, and motion planning. Specifically, we are given network of N agents, where agent i has position Pi,. E RR,, velocity Vi," E R22 and acceleration Ui, E IR² at time steps n < T. The agents collaborate to learn controller actions and complete a specific task. For each task, the goal is learn controller U that imitates an optimal centralized controller U Therefore, we parameterize U with ST-GNNs and aim to find H- that satisfies
M
H = arg min HEW
(Xmm H. Lm)
mn
(22)
M
M==
where H is the set of all possible parameterizations, {(.) is the mean- loss function, L. (S a )r is the STSO of the m-th example, and M is the size of the training dataset. The input signal Xm E R contains y state variables of N agents, e.g. the position and velocity, over T time steps. Detailed description of the ST-GNN implementation can be found in Appendix G
A. Network Consensus and Flocking, A swarm of N agents collaborates to learn a reference velocity rn E IK² Vn, according to which the agents move to avoid collisions. Ideally the reference velocity and the agent velocity Vi... should be the same, which is not the case in practice since each agent observes a noisy version of the reference velocity rg.n- Therefore the state variables (inputs) are the estimated velocities {Vi,n the observed velocities (Fi.n Ji,n and the relative masses (q.. (g.n ΣjeN, (Pr.. - Pi.n)i.n where Ns the set of direct neighbors of the i-th agent. We train an ST-GNN to predict agent accelerations Jin according to which the agents will move to a new position with certain velocity. Further details can be found in Appendix G
Experiment 1. First we organize 100 agents in a mesh grid, but the agents are not allowed to move. The reason is that want to test the ST-GNN time. Note that although the agents do not move they still estimate an acceleration and therefore a velocity according which they should move. In simple words the goal is to estimate the optimal accelcration of each agent in the case they would be required to move. Consequently, the training and testing is executed over the same graph but with different state variables and outputs. Fig. [ (Left) illustrates the mean of agent velocities, defined as v, = E Vi.ns along with the reference velocity Tn We observe that the agents succeed to reach consensus and follow the reference velocity. We also exccute the previously trained ST-GNN on a setting with perturbed graph and time shift operators according to
setting where the graph is not changing over
g and (T)), respectively. Specifically, the error matrix E is diagonal with ||E]| < E. 1 (Middle) shows that the relative RMSE of the outputs {u:..
and aT)) = Ve cos(er)e-ss Fig.
defined as | + (X: C-) +b (X; |l X; H. e F. We observe that the relative RMSE linearly proportional to the perturbation size e, following the results of Theorem 2
Experiment 2. We now allow 50 agents to move and form communication network that changes with their movement, i.e., the graph of the agents varies over time. Consequently, the ST-GNN is trained on dynamic graph [see Appendix G Fig. (Right) shows the difference between the agent and reference velocities, Vi.. and rn, averaged over N agents. The small standard deviation in the velocity difference (represented in red) indicates that the agents reached a consensus on their velocities. The figure also shows that the ST-GNN outperforms the decentralized policy, described in Appendix G. This experiment demonstrates the effectiveness of the proposed ST-GNN architecture
8

---

Published as a conference paper at ICLR 2022
1.50
Agtto velueity
1.0
Decatte
veloctt
10
Veladdy ditheene
0.75
0.50
M
0.70
0.25
10
10-1
1014
0:30
Timee stegis
Time
Figure 1: (Left) The mean of the velocity estimates by the agents compared to the reference velocity in test example. (Middle) The relative RMSE in the ST-GNN outputs under perturbations to the underlying space-time topology. (Right) The mean difference between agent and reference velocities.
Relative eroo
0.0
Rolative ctoor
1.00
Goi
L.5
0.75
Aguui
0.0
0.00
19
10
AM
AT,
Figure 2: (Left) Three-second agent trajectories of a test example. (Middle) Relative error caused by using different network densities. (Right) Relative error caused by using different sampling time T..
on dynamic graphs, even though our theoretical analysis is derived for fixed graphs. Further results presented in Appendix G
B. Unlabeled Motion Planning. The goal of this task is to assign N unlabeled agents to N target locations. The agents collaborate find their free-collision trajectories to the assigned targets. We train an ST-GNN to learn the control accelerations (u: J.,, according to (22). The state variables for agent are position {Pi,n Ja. velocity {vi,n)a the position and velocity of agent's M-nearest neighbors, and the position of the M-nearest targets at each time step n. The underlying graph is constructed as (i,j) &, if and only j Nr.,. or E WNj.. where Ni,, is the of the M-nearest neighbors of agent i at time step n. The rest of the training parameters are shown in Appendix G
We executed the learned ST-GNN on test dataset that is designed according the parameter M and sampling time T.. A snapshot of the predicted trajectories are shown in Fig. 2 (Left.. We observe that the agents approach their target goals without collisions. The average distance between the agent's final position and the desired target is, dp., = 0.524 with variance equal to 0.367. We now test the sensitivity of ST-GNNs to the right choice of M and T. in the testing phase. Fig. (Middle) shows dpg.ong) (hgg.ong// h when we change M. The error increases with A because changing the neighborhood size induces a change in the underlying graph. According to our theoretical analysis, the error increases with the size of graph perturbations, which matches the results in Fig. 2 (Middle). The same remark can be observed in Fig, 2 (Right) when we change the sampling time, which induces change in the underlying time structure.
the relative error, which is calculated as (dpp.
CONCLUSIONS
In this paper we developed a novel ST-GNN architecture, tailored for time-varying signals that are also supported on graph. We showed that the proposed architecture is stable under both graph and time perturbations under certain conditions. Our conditions are practical and provide guidelines on how to design space-time graph filters to achieve desirable stability. Our theoretical analysis is supported by strong experimental results. Simulations the tasks of decentralized flocking and unlabeled motion planning corroborated our theoretical results and demonstrated the effectiveness of the proposed ST-GNN architecture.

---

Published as a conference paper at ICLR 2022
REFERENCES
A. Bietti and Mairal. Group invariance, stability to deformations, and complexity of deep convolu- tional representations. Journal of Machine Learning Reseasrch, 20(1):876-924, Jan. 2019.
Bruna and S. Mallat. Invariant scattering convolution networks. IEEE Transactions on Pattern
Analysis and Machine Intelligence, (5(8):1872-188)) Aug. 2013.
B. P. Chamberlain, J. Rowbottom, M. Gorinova, S. Webb, E. Rossi, and M. M. Bronstein. GRAND: Graph neural diffusion. June 2021. URLhttp::/arxttt http:v/aaxivvvvvvvv wwwp:xiwi...ogaaaoooooo abs/ 210. 10934
K. Cheng, Y. Zhang. X. He, W. Chen, J. Cheng, and H. Lu. Skeleton-based action recognition with shift graph convolutional network. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 180-189, 2020.
M. Cranmer, P. Melchior, and B. Nord. Unsupervised resource allocation with graph neural networks. Proceedings of Machine Learning Research, 1:1-13, June 2021. URL http: // http:x.xxvvv..../...
Z. Fang, Q. Long, G. Song, and K. Xie. Spatial-temporal graph ode networks for traffic flow forecasting. page 10, June 2021. URL /RR./tttp::/arxx...orrr httgg//bb//200e 12931.
Gainza, F. Sverrisson, F. Monti, E. Rodolà, D. Boscaini, M. M. Bronstein, and B. E. Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning. Nature Methods, (7(2):184-19) Feb. 2020.
Gama and S. Sojoudi. Distributed lincar-quadratic control with graph neural networks. 2021. URL pettps:/aaxx.r org/ aww./bbs/.... 08417v2)
F. Gama, A. Ribeiro, and J. Bruna. Stability of graph scattering transforms. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Gama, Bruna, and A. Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 68:5680-5695, 2020a.
E. Gama, Q. Li, E. Tolstaya, A. Prorok, and A. Ribeiro. Synthesizing decentralized contrlllerss with graph neural networks and imitation learning. Dec. 2020b. http:::t////aaaaoorrr///// 2012.14906
P. A. Grillet. Abstract Algebra. Peringer-Verlagee New York, 2 edition, 2007.
E. Hajiramezanali, A. Hasanzadeh, N. Duffield, K. R. Narayanan, M. Zhou, and X. Qian. Variational graph recurrent neural networks. In Neural Information Processing Systems (NewrPPS), 2019.
E. Isufi and G. Mazzola. Graph-time convolutional neural networks. In IEEE Data Science and Learning Workshop, June 2021.
D. Jiang, Z. Wu, C. Y. Hsieh, G. Chen, B. Liao, Z. Wang, C. Shen, D. Cao, J. Wu, and T. Hou. Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-baste based and graph-base based models. Journal of Cheminformatics, 13(1):12, dec 2021.
R. V. Kadison and J. R. Ringrose. Fundamentals of the Theory of Operator Algebras, volume I. Academic Press, edition, 1983.
Q. Li, Gama, A. Ribeiro, and A. Prorok. Graph neural networks for decentralized multi-robot path planning. In IEEE International Conference Intelligent Robots and Systems, pages 11785-11792, 2020.
Y. Li, R. Yu, C. Shahabi, and Y. Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In International Conference on Learning Representations (ICLR '18), 2018.
V. Lima, M. Eisen, K. Gatsis, and A. Ribeiro. Resource allocation in large-scale wireless control systems with graph neural networks. In 21th IFAC World Congress, volume 53, pages 2634-2641 Elsevier B. V. Jan. 2020.
10

---

Published as a conference paper at ICLR 2022
A. Loukas and D. Foucard. Frequency analysis of time-varying graph signals. In 2016 IEEE Global Conference on Signal and Information Processing, pages 346-350, Apr. 2016.
A. Nicolicioiu, I. Duta, and M. Leordeanu. Recurrent space-time graph neural networks. Advances in Neural Information Processing Systems, 32, apr 2019.
A. Ortega, P. Frossard, J. Kovacevic, J. M. Moura, and P. Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-88)) 828, May 2018.
C. Pan, S. Chen, and A. Ortega. Spatio-temporal graph scattering transform. International Conference Learning Representations, 2021.
A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. B. Schardl, and C. E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In The Thirty-Fourth AAAI Conference Artificial Intelligence, AAAI, pages 5363- 5370, 2020.
M. Poli, S. Massaroli, C. M. Rabideau. J. Park, A. Yamashita, H. Asama, and J. Park. Continuous- depth neural models for dynamic graph prediction. June 2021. URL
abs 200s/2106... 11811
L. Ruiz, F. Gama, and A. Ribeiro. Gated graph recurrent neural networks. IEEE Transactions Signal Processing, 68:6303-6318 2020.
L. Ruiz, Z. Wang, and A. Ribeiro. Graphon and graph neural network stability. In ICASSP 2021 2021 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 9255-5259) IEEE, June 2021.
A. Sandryhaila and M. Moura. Discrete signal processing on graphs. IEEE Transactions on Signal Processing, 61(7):1644-166 2013.
Y. Sco, M. Defferrard, P. Vandergheynst, and X. Bresson. Structured sequence modeling with graph convolutional recurrent networks. In Advances in Neural Information Processing Systems, pages 362-373, 2018.
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending nigh-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, Oct. 2012.
A. Strokach, D. Becerra, C. Corbi- Verge, A. Perez-Ribe and P. M. Kim. Fast and flexible protein design using deep graph neural networks. Cell Systems, (4)):404-4111) 411.e4, Oct. 2020.
H. G. Tanner, A. Jadbabaie, and G. J. Pappas. Stable flocking of mobile agents part Il: dynamic topology. In Proceedings of the IEEE Conference Decision and Control, volume pages 2016-2021, 2003.
E. Tolstaya, Gama, Paulos, G. Pappas, V. Kumnr, and A. Ribeiro. Learning decentralized controllers for robot swarms with graph neural networks. In Proceedings of the Conference Robot Learning, volume 100, pages 671 672, Oct 2020.
M. Turpin, N. Michael, and V. Kumar. Capt: Concurrent assignment and planning of trajectories for multiple robots. The International Journal of Robotics Research, 33(1):98-11) 112, 2014.
P. Veličković, A. Casanova, P. Liò, G. Cucurull, A. Romero, and Y. Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018 Conference Track Proceedings. International Conference Learning Representations, ICLR, 2018.
Y. Wang, P. Li, C. Bai, and J. Leskovee. Tedic: Neural modeling of behavioral patterns in dynamic social interaction networks. In Proceedings the Web Conference 2021, WWW '21, page 693-705, New York, NY, USA, 2021.
S. Wu, F. Sun, W. Zhang, and B. Cui. Graph neural networks in recommender systems: A survey. Nov. 2020.
Y. Wu, M. Gao, M. Zeng, F. Chen, M. Li, and J. Zhang. BridgeDPI: A novel graph neural network for predicting drug-protein interactions. Jan. 2021.
11

---

Published as a conference paper at ICLR 2022
L.-P. P. A. Xhonneux, M. Qu, and J. Tang. Continuous graph neural networks. In 37th International Conference on Machine Learning, pages 10363-10372, Dec. 2020.
S. Yan, Y. Xiong, and D. Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In 32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pages 1454.. AAAI press, Jan. 2018.
F. Yang and N. Matni. Communication topology co-design in graph recurrent neural network based distributed control. 2021. URL Utthttss: pttts::::///axx //tp///axvvvv//vv///ii//eaaaaiiv org/ abs/ 2104. 13868v1
R. Ying, R. He, K. Chen, P. Eksombatchai, W. L.. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 10:974-983, June 2018.
B. Yu, H. Yin, and Z. Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018.
D. Zou and G. Lerman. Graph convolutional neural networks via scattering. Applied and Computa- tional Harmonic Analysis, 49(3):104-1177,, 2020.
A (PROOF OF) FREQUENCY RESPONSE OF SPACE-TIME GRAPH FILTERS
We start from the abstract representation of signal X' E V, which apply shift operator L : + V. Then we can write the signal X' as
X J. (X,U(())v
(23)
where (u(1), is the set of the orthonormal eigenfunctions of L that spans the space V. The form in (2) is reminiscence of the inverse Fourier transform and the scalar values (x))(()) are the Fourier coefficients. In classical signal processing, the Fourier coefficients represent the spectral components of the signal X.
Now, we consider the example of time-varying graph signals, X' E L' @ LR),,, which are constructed the tensor product of continuous-tims signal and graph signal. Shifting the signal X' is executed using the STSO, S L,, which is the linear composition of the GSO and TSO. The eigenfunctions of the STSO can then be defined as the tensor product V; @ d where v; is an eigenvector of the GSO and eour is an eigenfunction of the TSO. Recall that the eigenfunction is itself vector in the space L (RM) L2((R), ), and thus applying the STSO on V, & eJur means to jointly shift the the graph vector and the continuous-tim time function. In other words, we have SoL. (v; & dس
vv; & e frr = e -A++jw) (v: 8 eduT).
(24)
Thus conclude that every eigenfunction v cdur of the STSO is associated with eigenvalue A + +.j.
Defining the eigenfunctions of the STSO allows to re-write 23 for time-varying graph signals
N
1
X'
X j(),, & ciwr)dw.
(25)
2m
where Í(AA,j is the spectral component of the signal X' the frequency pair (A,,w), and the constant 2= is to normalize the eigenfunctions. It is inferred that the frequency domain of time- varying graph signals bivariate. Considering the space-time graph filter H(S, C+), the filter output can be expressed as
[ M(D) M(D)--SSC -Soc. Xdl
y H(S, C+)x
((Wr / h(t)e h(t)e-1Soo
ISoL (v, ciwT ddd
(26)
2T
N
(
1
f()
/ hitte ((Arttw) dt(v; 8 cdw
2T
12

---

Published as a conference paper at ICLR 2022
where (a) results from expressing &' by its spectral representation [cf. 25 and (b) from recalling
As in (25), the filter output can be also written as E jw),, @ e el
and thus we have jw) = (A,,, ju) (h()) (((()==(A+++ following from (26). From the
convolution theorem, the convolution operator implies a multiplication in the spectral domain.
Therefore. the frequency response of the space-time graph filter is
h(A.jw)= h(t)e b(t)e-uA+ow)ds
(27)
which is the Laplace transform the impulse response htt). It worth noting that the filter response depends on the filter coefficients, which is irrespective of the graph. The spectral coefficients of the filter applied to one specific graph are, however, obtained by instantiating the frequency response jw) on its eigenvalues {A:
B PROOF OF PROPOSITION
First, define the eigenvector misalignment between S and E in the following lemma (Gama et al. 2020a).
Lemma 1. Let S = VAV# and E = UMU with E S
For any eigenvector v, of S, it
holds that
Ev; = m. + E,V,,
(28)
with E, < c8, where = [I)U V| + -
Now we proceed with the proof of Proposition I
Proposition bounds the distance between the space-time graph filters before and after adding graph perturbations. From (12). this distance can be evaluated as
Proof of Proposition 7
H(S, C.) - ((SS
= min
max - P'H((,,,))PXI)
PEP [|
(29)
min PEP
max [|||=
H(P"
where the last step is due H being permutation equivariant, i.c..
P'H(S,,,)P= / h(t)pT 18oL, Pdt (a) [ h(t)e IPTSPoL = C,). (30)
Equality (a) results from the fact that matrix P commutes with the exponential operator and als with the TSO. From the minimum operator (2 there exists matrix Po that satisfies
(, - C.)lp <
(H(S,,,)) max x
H(S. C-) HPP. SPo. 27)
(31)
H(SS C.) H(S + ES + SE, Cr)Il,
where ||-|| is the operator norm, and (b) follows from the assumption (A1).
Define the the filter difference A, H(S + ES + CT) H(S,C,) The next step is to find norm of A,. A, can be expressed [cf. as
h(1)e ((S+ES+SE)) dl / 0o
A
h(())e -(0))-- 180Lr dl
(32)
From Taylor series, e Sooc En 1 ( C2 and the difference is then written as
00
(-t)"
A
h(t))
((S + ES + SE L₂)" (S (+)
(33)
n!!
n=0
13

---

Published as a conference paper at ICLR 2022
By induction, expand the term ((S ES + SE) L+)" to the first order on E, so we have
((S - ES + SE) o ,,
@ (SoL, C, + ES SE 1
(34)
= (s)
Σ (.)
(ES
SE) o L.y -,)
+ +O)E),
r=0
where (2) combines the other higher order terms, and (a) follows from being linear composi- tion. Hence, (33) reduces to
A
8
n
n
(ES ((S (,)
SE) o c. (S --)" dt + OEE, (35)
n!
with OEE) = - analytic function. Thus the norm of OEE) of order ([E))) since
O2(E)dt Note that the frequency response of the filter is an
n!
|O(E)]
lim E 0
<C.
(36)
E
Denote the first term in the right hand side of 35 by A(S). After splitting the summands (ES SE) C, in 335 into ES o L, SE a Ly, get
A(S)
h(()
(o C, --)
(37)
0
72
(tt)
So (. y E(S 6,) dt.
n!
n=0
The first line straightforward and the second follows from commuting the matrix E with the TSO, C,. The required norm becomes ||A,|| < ||(()]|| + [|OE)] from the triangle inequality, with
[[O(E)] being of order (+e2) by the assumption (A2) and (36) Thus the aim of the proof reduces to bound the norm |SS)) by 2C',, + &VN).
The norm
A ASS] is defined as ||((S)| maxx: || We express A(S) as
N
(W) / 1(t) Σ (-t)a n
A(S)
Σ
S ((S
@ jjuT dtdd
=
2n
n!
r=0
1 N
j() 1" h(t) Σ n!
( C.
E(S 2-)" --) (v; @ ddu )dldw,
2m
i=1
R=0
(38)
which follows from expressing A(S) as in 37 and X' as in 25 Then
/ h(1))
A(S)X
(A: (S. @ e ydtdd
n!!
N
{(A..jw)) 1 h(t) Σ
n-1
(Ae +
1 @ edNT ddtd,,
2T
n!
R=0
1=0
(39)
since (S o C, (v; @ ejut) = (A; + 7 & eJuT). The assumption (A2) indicates that matrix
E has eigenvectors that are not aligned with v, Vi. From Lemma I follows that E( v; & edwr)= = Ev, @ ddwr_ = m.v; @ şiur + E, @ elwr The terms (S o L, EE(v; @ ci of (39 can then be simplified as
(S o C, E((, 8 ( m;(S C, (v, @ edur) + (So E. E 8 EWT)
(40)
= =m;(A + (v; @ " ( (So E, @ eduT).
14

---

Published as a conference paper at ICLR 2022
Substituting the first term of (40) in (39) results in
(S) = 2T (WW [ h(t)
N
x-1
2m + +ww)" (v; @ (owT)dtdw.
Td!
a=0
(41)
Doing the same for the second term of 40 leads to
1
/ h(t)
A2
{():.Jw)
(As
& e ddddw
2T
+
(() /
11(1)
Σ
2
n-1
(Ar +
jw) (S) (v & e jdlddw
2m
n!
(42)
where A(S)X = AI(S) + ( The next step is to find the norm of (I and 22(S).
For the term (S) in 41 notice that the inner summation longer depends on and can be written as 2mm, (A: + jw)
& eJuT). Therefore, we get
(-t) (Ax + dt 2m:(A, + jw) Ox
2m;
h(t)
7
h(),
(43)
n!!
7=0
where h(,,, =
Jo h(t)
n== ni!
(-t))((4++ + jw)" dt is the partial derivative of the fre-
quency response of the filter computed d4. Thus 411) written as
A (S)X' = 2T
2m, jw) (As + jw)
jw) (v, @ ydw
(44)
OX
From Pythagoras' theorem we know that the squared norm of sum of orthogonal terms is the sum of the squared norm the individual summands. Then
(S)x = Σ ho 4m (A, 14, + jul?.
h(Ariww)) du S 42,08111813, (45)
aA
since [ma] I E < 6s. the filter is integral Lipschitz [ef. basis vectors orthonormal, i.e., l| So ji)
17)l. and the eigenfunction The norm || is defined as
ew.
F 1.
2
now rewritte (2 in as
A2
1
Σ
EV, @ d ddw,
(46)
2
i=1
with
100
(-))
KC
h(t))
Σ 0=0
(As (S)
($ (47)
n!
r=0
We next find the norm of Kc; in order to find |A]())] Note that KG: (R. 6 (22(RR
2 (IR @ (z) is a linear operator and so is the matrix (2 L (R matrix S
can be expressed using the outer product of its eigenvectors as S EN Avv,v Since the tensor product generalizes the outer product of n-dimensional vectors,
draw parallel and have
N (Ak + jvk @ edw @ (Vx @ H dw...
E/ ( (2T)) k=1
1.
(48)
15

---

Published as a conference paper at ICLR 2022
Caleulating (47 requires evaluating the term (As + "w) first, which can be simplified as
(A: (A) jw)a (S )+)
(A, jaw"" (.)" + (Ae (S (+)
(S Cr)
(S )
(49)
+
(>, + jwj
(A, + jw)
When we substitute in we get
(A: + jww" Cr)" 3" (A: j )
(A: (A++Jw)* jm) _oa ( (dx + jw.) (Ax + jwa) (2T)²
(A=+ (A: + jwj (va 2 du))) (ve & cdurr) dw..
(50)
The inner summation in 47 reduces to the sum of two geometric series, each of which has the form
A + julu
1 (A+ + jw)" (As + ju,)
(51)
A jw
(Λ₃ + jw) A jw (Ax + jw,)
and the reader can confirm with simple algebraic manipulation that the right hand side of (1 follows from the geometric sum E a (1 a") //1) a). It is also straightforward show that
(A:+jw) n
Σ
A + jul
Jus
+
du + jws d +
r+1
A + A + + w.)
(Au
A j
A 2 + 1 - w.)
r=0
(52)
with some algebraic manipulations. We eventually can write K. in
47 as
(-t)a
x + de j(w w.)
KC,
h(t)
(A: jw)" (Ax + jur)"") (53)
(2T)2 n!!
A - da + j(w w.)
(v* 2 ju.T @ (vx @ T). H dw,dt.
Since we have jw) = Joeh ((ll)e-(Arttuall = fo² h(() Σn (-1) + jw) from Taylor series, Nc, reduces
N
(Ar jws + (Ax + jua)
K. (2Tr)
(h(Ai,, jww - h(Ax
(A+ jw) (A+ jww)
(54)
(vx 3 @w. 2 (vx ewet y dww.
Note that (54) has the form (W2 + w1)(h(w))) (2)) h(w1))/ W1 of (6) with w being replaced by its complex form, A + jw. This remark will help bound the norm of K., The norm ||A]]] is defined as =axx:]=x|=== [[ F for all and we have
K.
(a)
Kr
( (v $0 edur
2
b
N
X' jws,
(di + jw) + (Ax + jw.) (Ai + jw) - (A jus)
(h(Ai, - (()n) (vx 8 eduit ydw...
2T
(55)
The RHS in (a) involves the inner products (2 (Vr @ eluit) (vm @ efwr) = (2m) (V& e
iiw.t Vm @ cduT), Vm, k. These inner products are between the orthogonal eigenvectors and are nonzero if and only if m = and à = w.. Therefore, only the terms that have m k and às w. appeared in (b), and the inner products are 1.
16

---

Published as a conference paper at ICLR 2022
From Pythagoras' theorem, the squared norm of K,,'' is then
N
(A, (A+ + jw) + (Ax jww) +w - (Ax jwm)
(h(A,, - h(des. ) du'
||
Σ
4C Vi,
(56)
followed from the assumption (A3) that the filter is Lipschitz filter [ef. Definition Therefore, we get ||]]|| & 2C for unit-norm signal X. Now, it is left to take the norm of (46). which yields
1
(W),, @ oow )dw
2T
(57)
N
- jW):
[|G|| E s 2Ccp
Σ
(X jww
==1
where we have |E,| S co, Vi from Lemma
To bound the summation in 57
can write
N
(a) K
N
7
[&(A
. du
Σ
1 dw
$/2
(W)
8(T)dT
(58)
where (a) follows from Sauchy-Schwarth inequality, and (b) from Parseval's theorem. Note that 8(T) is the Dirac delta function. Eventually, we obtain
|| |1) & 2Cc,ōv \V
(59)
Recall that A(S). = A, + (S) From the triangle inequality, we then obtain
| < A (S)x + ( <
(60)
following from and using 45 and 59 Hence, ||(S]]] = S 2Ce,(1
8v N), which completes the proof.
C PROOF OF PROPOSITION 2
The aim of the proof is bound the distance between the space-time graph filters before and after adding time perturbation. This distance is calculated using the operator distance modulo translation. From Definition 3 it holds that there exists real value s such that
H(S, f.) H(S, 2,)1T
min max *E3
H(S, (,)X - -cc H(,,
2=||=||F=1
max X=
-
(61)
- (1 (11)
where in (a) we let the minimum norm value be lower than or equal to the norm when s = 0, and in (b) we use assumption (A1). The difference between the filters is evaluated as
H(S (.) H(S = | h([)e (G0CC)
1
h(1)e- (SaL. dl.
(62)
Let A, denote H(S Ê.) H(S, LT), which can written as
(-t)" ((S o (Cr + + -(S ((o
A
h(t)
(63)
n!
n=0
17

---

Published as a conference paper at ICLR 2022
following from expanding the exponentials to e 1- Σn= n! series. We also expand (S C, + S {(T) to the first order of {(T):
(-t) -,)" using Taylor
(o + -- -,)"
Σ (S (.)" +0((((T))
(64)
where (z)) a polynomial of the higher powers of E(T). By substituting in 63 we can re-write the latter as
A 0 h(t)) Σ
(-t)
SS
(65)
n!
n=0
where (
Jo h(() - (-)" (2(E(T))dL. The quantity O({(7)) has all the higher power
terms and satisfies
0 lim (O |E(T)]1
0O.
(66)
[|E(+)]l -0
Therefore, the norm [(((T)) is of order (E following from assumption (A2). Remember that if the norm of order e,, it means that [I{())ll2 S Key with being absolute constant, Our goal reduces to bound the nomn of the first term of the right hand side of (65)
Since the TSO and GSO can commute, holds that
(S (())
(S" To
S CTE(T)
(67)
However, C, and E(T) do not commute due to their dependence on т. Recalling that C, differential operator and applying the chain rule, obtain
C (5(T)
Σ ((m) m=0
(m)) m
= [(T) (( Gz(5((T)).
(68)
where (a) is valid by induction, (Tm 8Td ((T)/or"" and the term Gz contains the higher- order derivatives starting from the first derivative. Substituting (67) and 668 (65). we get
h(t)
S"
7=0
(69)
(-))"
m
h(t)
G(
n!
The summands of the inner summation in 66 no longer depend on r leading to the form in (a). We also have G(E'(7) fo h((t) En=o [[)(E(T))llz is of order O(e)) since
Gz( It can now be shown that the norm
[GG('(T))llz [|
0 lim
< <0,
(70)
(T)
and [i is of order et according assumption (A2).
Denote the first term in the right hand side of (69) by (CC,). Since both ||O({())] and [[G(g((T)) of order eg the rest of the proof aims to show that the norm of A is bounded by CRe,- We have
A(C,)X (100
20
(-t)a
)
(
hit)))
Σ
(E() dt
{),,, & e
n!!
2T
n=0
X ()),
/
000
h(t))
(-t)"
(S(T) (v, @ ddtdw.
2T
n!
n=0
(71)
18

---

Published as a conference paper at ICLR 2022
Recalling that (v, @ eluT) is an eigenfunction of (S Lr). re-weite 71
(AL, /.' h(t)
A(C))*
(A: jww) @ e
2
(72)
N
(W))) + jw)
h(A,, jw) (v, @ olw)
2π
Djw
where 8
jw) jw) then be evaluated as
h(di,
So h(1) Ex=o 3 (-1)) jw) - dl. The the squared norm of 72 can
83
|A(C)
) F
(0)
Σ
N
((W)) (E(T) jul
a
h(A,, (()
dwdt
J0
1=1
0
θ @jw
(L, (K(T))(T))
((155 ( [|((T)]lS 1 S C² 22
=| + jwl
h(>.hhh h(>s.jw)
dw
= A4 + + jwl
h jWw 8jw
(73)
In (a), we use the inequality 1 =dke/3 S . |x| In (b), we use assumption (A3), which states that the filter integral Lipschitz with constant C, and assumption (A2), which has the norm lIE(T)]l2 bounded by ke,, Finally, the required norm can be calculated as ||((C)]] maxx: ([T) & CKey, which completes the proof.
D PROOF OF THEOREM
The aim of the proof is to bound the distance between the space-time graph filters before and after adding joint perturbations. From 15 this distance can be evaluated
HHS H(S (,
min min max
H(S,,,) H (PTSP, -
+c. Lir X
PEP X|
(0)
H(S, H(S + SE ES, 2-)x
max
x
= H(S, - + SE ES 2,
(74)
where (a) is true for any specified values of P and s, and we choose Po and as in (31) and (6I).
respectively. Then, we add and subtract H(S + SE + ES, L,) from the filter difference to get
H(S, (-) H(S SE + ES, (.) (S,, C-) H(S + SE ES, L.)
(75)
+ H(S + SE + ES, L,) H(S + SE + ES, Lr).
Using the triangular inequality, the norm of the filter difference bounded by
HHS - H(S + SE + ES, 2+)1 < H(S, C,) H(S + SE (.S
H(S SE + ES, C+) H(S SE ES, L+) | + ||||||
(76)
Note that in Proposition 2 A, defined for the GSO S but the proposition is valid for any GSO. The bounds of ||A,|| and A || are obtained in Propositions/ [ and Therefore, we get
H C.)
H(S - SE ES, 2,) < 2Cc,
CRe, +
(77)
where O(e2) is the highest among (ce)) and (c²)) This completes the proof.
19

---

Published as a conference paper at ICLR 2022
D.1 FINITE-IMPULSE RESPONSE FILTERS
While Theorem handles space-time graph filters with continuous-time impulse response h(t), its results can be extended finite-impulse response filters following the same proofs in Sections B and D In this context, FIR filters can be thought of as a special case of the filter h((), where we have finite number of filter coefficients. We summarize this remark in the following lemma.
C
Lemma 2. Define a space-time graph filter with a finite impulse response as
Ha(S,
Σ hge KT,
(78)
A==
Under the GSOs defined in Proposition [and TSOs in Proposition 2 the distance between the FIR space-time graph filters Ha(S, C,) and H.,(S, satisfies
[HH H. 1p. S 2Cc, (1+0VN) + CKer +
(79)
E PROOF OF THEOREM 2
The goal of the proof is to show the difference between the GNN output before and after adding perturbations. The GNN output is the layer's output, i.e., Nz. From we can write the difference between the two GNNs as o (x,, H.S fx) - ( H. 2+)1 11,2 Rill
(80)
H (S
(H, (.) (.)
where (S, Lr) is the filter in 78 at Layer T., Xe is the output of layer l, and &g is the correspond- ing output after adding the perturbations.
From assumption (A2), we get (|a{())) o (xi 3 ||x22 - X1112. Accordingly, the norm of the
output difference any layer / L is bounded by
|x Rellr -
H. (S. C,)& H, 2.)
(81)
Add and subtract H (S, inside the norm in the right hand side. The norm of (8 can then be wriien
H,(S, C. 1- -S,
) C.),,= +
(8,(,))))6111 -
H. (
H. (+) H. (+) 18--1111 (S 2.)|| X &
(82)
using the triangle inequality in (a) and Cauchy- inccuuarziieeullity in (b). From assumption (A1), the filters have unit operator norm, i.e., [S, f.,ll 1, =I...., L., and hence, || S ||le= = || becomes ||*r -11lF S (2Cte (I (1+8VN) + CKe, + +0(E)) || + | - x1-11
From the stability of graph filters in Theorem (with Lemma D.. the difference
(83)
Substituting (2 in 833 recursively, we obtain
1r &ellF S 2CL (1 (1+8VN) | + C'LNE, +0E2).
(84)
Note that the base case of the recursion is calculated as
- 2 < (S, H L. 2 |126ll
H,, (S, | 22Ce, 8VNN N CKee + +0(2)) |
(85)
Eventually, as in 74 it follows that the joint operator distance modulo of the output of ST-GNNs is
(.; H.S C.)
(:;:; H. $ 2.) S 2CL,, + (1+5VN) + CLae, + O(e3),
(86)
completing the proof.
20

---

Published as a conference paper at ICLR 2022
F STABILITY OF MULTIPLE-INPUT MULTIPLE-OUTPUS ST-GNNS
Theorem 2 only considers the case of sinllefeeauure layers. In this section, we extend the stability analysis to the case of multiple features. We derive a bound for the difference in the output of ST-GNNs in Corollary L where each layer as well as the input signals have multiple features. We let the features at the hidden layers be the same for simplicity.
Corollary (ST-GNNs Stability), Consider the assumptions of Theorem but let Fe = F be the number of features per each layer 1 S. E L 1. Let Fo and Ft be the number of the features of the input and output signals, respectively. Then,
|| | (1; H. L+)
F Fo Σ (2CC((++8VV) + +Cn,,++
(87)
VFL
+ 0(2).
Proof. We aim to find the difference between the output of the Lth layer before and after adding joint perturbations. For a layer and feature J, we can define its output as
F
x
Σ g=1
H (S,
(,)
2,)x,21)
(88)
where H 9 is a single-input signle-output filter as the one used in Theorem From assumption (A2) of Theorem 2 we have the identity [|o a(x1)l2 ||x2 x1 We can then bound the output
difference for all <
<<> Li
22/
8/11 ||F
H (S, 2S,
| - H( | (S. 2+)
-22111
- F (2Ce [1+8VN] + Cke, + 0(2)) | + F L -22-
(89)
The summation (b) has equivalent summands since we assume that all the filters satisfies assumption (A1) in Theorem With applying
where (a) follows from the triangle inequality, (b) from 82 and (c) from Theorem [
| -x recursively, we re-write 89
C-1 (2Ce (1+0VN + CKe,)+
x X/1l= <
pe-1 +
Σ
+ + +0(2)).
(90)
1=1
Note that the base case of the recursion is calculated as
12 Rf
(S.
(91)
$ Fo 220x,
+ (1+5VN) + Cke, + O(22) H
Finally, we can express the difference between the output at layer L. has multiple features, and therefore, the norm of the difference is expressed as
Ft.
Xr Ex
xL.
x/
(92)
2 (2Cle, (1 (1+8VN) + Cke, +
(a) FL
<
F1. Fo +
Σ Fl
where (a) is calculated from 900) for l = L. Taking the square root yields the inequality in 87 which completes the proof.
21

---

Published as a conference paper at ICLR 2022
G EXTENDED NUMERICAL RESULTS
We consider the problem of decentralized controllers, where we are given a team of N agents, each of which has a position P... E IR?, a velocity Vi, E R² and an acceleration U E IR? that are captured at times vT',,' n E Z+. The goal to learn controller actions that allow the agents to move together and complete specific task. Two tasks are considered in this paper: flocking and unlabeled motion planing. Optimal centralized controllers for the two tasks are derived in the literature. However, centralized controllers require access to the information at all the agents, and therefore, the computation complexity scales fast with the number of agents. With the help of ST-GNNs, we can find decentralized controllers that imitate the centralized solutions according to (22). In this section, we aim to provide a detailed description of the experiments in Section 5 along with further experiments.
Communication networks. The underlying graphs represent the communication networks between the agents. Two criteria be used to assemble the graph. First, each agent is connected to its M-nearest neighbors. The graph at a time step n is then represented by a binary graph Gn such that (i.j) E e, if and only if j Nu,,, or i N, where N,,,, the of the M-nearest neighbors of the agent i. The second is to connect each agent to the neighbors within communication range R. The graph in this case is also represented by binary graph such that (i. E E,, if and only |P... P < R. In both cases, when the agents move, the graph G. changes with n.
ST-GNN Implementation. As indicated above, the communication networks (i.e., graphs) change with the movement of the agents (i.e., with time). However, ST-GNNs in (7) are designed for fixed graphs. Moreover, ST-GNNs are designed for continuous-time signals, whereas the signals in our experiments are discrete. To turn around these challenges, we implement the FIR space-time graph filter recursively, where at every time step we use the corresponding underlying graph. The output of the filter at a time step is expressed
K-1 Σ
Yn - Nox,, +
hy
II m==
Sn-m
Xn-k=
(93)
where x,, and S., are the graph signal and the GSO at time step n. The graph diffusion is implemented in (93) with the GSO directly instead of the operator exponential e Sa, The latter can be expressed
as
S - S, + O(S,).
=
(94)
11
where OSS.) contains the higher-order terms. Equation 94 shows that the GSO is first-order approximation of e- e-S,, and the sign difference is absorbed in the learning parameters (hg k=
1K
G.1 APPLICATION I: FLOCKING AND NETWORK CONSENSUS
In this application, the agents collaborate avoid collisions and learn to move according to reference velocity rn RRa The reference velocity is generated randomly as ra+1 = In + T, ArAr,, Vn e Zt,n n < T. The initial value ro is sampled from Gaussian distribution and so is Arn. with zero mean and expected norms E|]rroll and [[[ ro]]] respectively. At each time step n, each agent i observes biased reference velocity Fi.. such that F.,. r, + AF; with Ar, being white Gaussian with independent and identically identically-diisriburee distributed (i.id.) components. The goal is to learn acceleration actions nn Ji, that allow the agents to form swarm moving with the same velocity.
Mobility model. Given acceleration actions (ui, Jim. each agent moves according to the equations of motion:
Vin++ Vi, + Tull, Pin+1 Pi, + Tavi, T2/2 Ui,n-
(95)
The initial velocity is assumed to be V..0 = Hg + Av, for all i, where Av is white Gaussian with i.i.d. components. In our experiments, we aim to learn accelerations {u., hi that make Va, for all i be as close as possible to r, and prevent the position differences Pij.n = Pi.a Pj. from being zero for all o j at any time step n. We solve this problem under the constraints ||u l|2 S p. Vi,n.
22

---

Published as a conference paper at ICLR 2022
Optimal centralized controllers. The problem described above has optimal solution, which, for all i 1,...,,, N and n I T, is given as
-1
1 N
Vin
V
pr.. C(Pi.n Pin).
(96)
2I,
2T.
||u 112 a ps and otherwise u
μ.. The collision avoidance potential C(.) is defined
C(p.. P,) = { 1/ 1 1 log(l 1/7 log(>?),
(2),
|P S 7 otherwise,
(97)
where Pij = P: Pj. and y = (Tanner et al. 2003 Gama et al. 2020b). Note that (96) requires access to data from all the agents, and theretore, this solution is known to be the optimal centralized solution. However, in a decentralized setting, the agents exchange information only within their K K-neighborhood only. Therefore, our goal is to find acceleration controls that imitate the centralized solution in (96).
Decentralized Controllers. We compare results to decentralized controller that only has access to the information shared within the K K--neihborhood of the agents. Unlike the centralized policy where all the information is available the central unit, the agents only have access the data that they receive from their neighbors. More importantly, the data get delayed through the communication network, and the agents have to make their predictions based on outdated data. Therefore, the estimated accelerations in (96) are approximated by
dec -1 2T,
K
u inn
Vi,
Σ
KIN JENt
Σ
2T.
V (Di. - P))(n-)))
(98)
where |-| is the cardinality, and N fs' E 5.(a-1) 1 neighbors.
Nk-1
Ni,1 is the set of the k-hop
G.1.1 EXPERIMENT 1: NETWORK CONSENSUS
In this section, present detailed description of the training process. Remember that the agents in this experiment are not moving and the graphs are fixed mesh grids. The state variables are the estimated and observed velocities, Vi, and Fi,n: Vi, n.
Training. The dataset generated according to the mobility model in (95) and (96). The dataset consists of 500 time-varye varying graph signals [ |,00 that are calculated under optimal centralized 500 policies m ) We split the data into 460 examples for training, 20 for validation and 20 for
testing. We train 2-layer ST-GNN on the training data and optimize the mean squared loss using ADAM algorithm with learning rate 0.01 and decaying factors 31 = 0.9 and B3 = 0.999 T We then keep the model with the lowest cost (across the validation data) among 30 epochs while the cost averaged over the T steps. For single time step, the cost is calculated as
1
c(u,)
2N
Vin
j
2N
[ TTu. 11:
Vn <.
(99)
All the training and simulation parameters shown in Table II
Execution. addition to the 20 test examples generated with the training set, we generate another 20 examples under joint graph and time perturbations for each value of e. The perturbation size of both graph and time topologies is chosen the same. The results shown in Fig. (Middle) suggest that the closer the space-time structures, the closer the outputs of the trained ST-GGN under the cases are. This shows that an ST-GNN, which is trained with signals defined on one particular graph and sampled at certain sampling rate, can be generalized to signals with different underlying topology as long as the two topologies are close.
We used the GNN
library
upenn/
g graph-neura
23

---

Published as a conference paper at ICLR 2022
Table I: Simulation parameters in Experiments # and #2.
parameter
value 1m/s
E Bilrr = Ell Ar, Ar
E
Av
1m/s
Initial agent density, Pu Communication range, R Maximum acceleration value, μ
0.5 agents/m²
m
m//s
Time steps. T Sampling time, T, ST-GNN feature/layer, Fo.2
100
0.1 s
4, 1616, 2 (#1) and 6, 64, 2 (#2)
Filter taps/layer, K1.2 Activation function,
4, 1
tanh
1.8
30
Agan
Agunt
1.6
Agent
25
Agui
1.1
Agei 5
Agri
Agint mon vduciiy
Agents miren welerrs
Redervire veleety
110
314
0.6
0.5
0.1
Time steps
Time siego
115
30
3.
35-
255
30-
P-5
1.5
Agent
Agrit
Agrnta moe udacity
Agents at Us
Teefentre veberty
Agente dfter 9e ST GNN:
n+
20
-0
100
2.
3,11
10000
24
1800
17.5
Time stepss
Figure 3: Flocking experiment. (a) (b) and (c) the estimated velocities of some agents in three different examples from the test dataset, and (d) the positions of the agents in (c) the start of the simulations and after 9s (the red arrows represent the agent velocity).
G.1.2 EXPERIMENT 2: FLOCKING
In this experiment, we have 50 agents that are spread uniformly with initial density Po- The agents allowed to move with their velocities (in. At each time step n, the graph G. represents their communication network based on a communication range R. We train 2-layer ST-GNN that is implemented in (93). and the training procedure is exactly as the previous experiment. The dataset consists of 800 training, 100 validation, and 100 test examples. We execute the trained ST-GNNs on signals defined over graphs constructed with the same initial agent density Po and sampled at the same sampling rate 1/T,, Fig. 3 depicts three paradigms of the learned velocities compared to the reference velocity. We notice that the agents follow the trend in the reference velocity. The mean and variance of the difference between the agent and reference velocities were shown before in Fig. I (Right). Fig. 3d illustrates the positions of the swarm after 9s and shows that the swarm moved together with same velocity in the same direction. Fig, (Right) also shows that the proposed architecture outperforms the decentralized policy in (88.. The difference between the estimated and reference velocities is lower under ST-GNNs than the difference under the decentralized policy.
24

---

Published as a conference paper at ICLR 2022
Ager:
Agrur
Ageal
Agyest
Ageta seadly
Buflemmo velucitty
Reference velooy
Ageir moan veloory
6.0
20
100
60
801
(0
Time steps
Time steps n
2.5
5.0
Agrnt
Agerit
Axyet
2.5
Ageoot
Azeil
Asstall
Agynts non vddciyy
Referenc wduciiy
Refentice veberty
2.0
1.5
20
J0
100
G0
50
.00
'Tmm steps
Time steps
Figure 4: The estimated velocities of some agents in two different examples from the test dataset using ST-GNNs (left) and decentralized controller (right).
Examples of the test dataset are shown in Fig. is clear that ST-GNNs help the agents to mitigate the delays in the received information and learn accelerations that follow the reference velocity.
Graph and time perturbations appear in real applications change in the underlying graph-time topology. the following, we provide extended experiments to show the effect perturbations. In particular, repeat the same experiment either with graphs constructed with different agent densities or under different values of sampling time T..
Experiment 2.1. In this experiment, execute the trained ST-GNN on graphs constructed under different initial agent densities (i.e., a source of graph perturbations). We execute the trained ST- GNNs on 50 signals generated with different initial agent density. We repeat the experiments under densities 2, 1. g+ 32 128 512 agents/m²² respectively, and plot the relative costs after 10s in Figure 5 (Left). The cost represents the mean difference between the agent velocity and the mean of the observed velocities, which is calculated as
cost
ViT
T
(100)
2N
N
The relative cost is then calculated relative deviation from the under density of agents mmm Figure 5 (Left) shows that for the small changes in the density Ap (e.g.. from the original density 2 to 0.5 agents/m²², the relative cost remains small. However, the higher values of Ap result in higher relative costs, i.e., degradation in the performance. Note that using smaller agent densities (i.e., higher Ap) at the same communication range R results in sparser graphs. Therefore, their distances to the graphs generated the original density (2 agents/s s) increases leading to the aforementioned performance degradation.
Experiment 2.11. In this experiment, we execute the trained ST-GNN on signals sampled different sampling rates (i.e., a source time perturbations). For several values of AT,, we replace the sampling time T, with T, + AT, and calculate the relative costs as in Experiment 2. Figure (Right) shows that the smaller the value of AT, the smaller the relative cost is. This matches our theoretical results.
25

---

Published as a conference paper at ICLR 2022
Relatve cost
Reletive cost
0.2
1.5
1.6
1.7
1.8
1.9
2.0
10
10"
Ap
AT,
Figure 5: Relative cost after 10s calculated over test datsets that have encountered either graph perturbations resulted from changing the agent density po (Left), or time perturbations resulted from changing the sampling time T, (Right).
Table 2: Simulation parameters in Section G.2
parameter
value
No. of agents, N Neighborhood size, M Initial minimum distance, d Initial velocity, Vi.0
12
1.5 m
4 m/s
Maximum acceleration value, μ
5 m\/3
Time steps, T Sampling time, T.
30
0.1 34, 64,
ST-GNN feature/layer, Fo:2
Filter taps/layer, K Activation function,
3, 1 tanh
G.2 APPLICATION II: UNLABELED MOTION PLANNING
In this problem, aim assign N unlabeled agents N target goals, {g, E R through planning their free-collision trajectories. The term unlabeled implies that the assignment is not pre-determined and it executed online. At the start of the experiment, the agents minimum inter-agent distance d and so do the goal targets. A centralized solution to this problem was introduced in (Turpin et 2014), which we refer as the CAPT solution. This solution gives the agent trajectories, [Q: E 1= while the agent velocities and accelerations can be calculated as
spread with
Vi,n -P.n)/1
u -
(101)
Note that P.,. is the n-th column of matrix Q.. We use the optimal accelerations in (101) to learn an ST-GNN parameterization that predicts the agent accelerations {u,nhi, according to 22 The input Xmm consists of 6M + 4 state variables for each agent, which are the agent position [P.n n and velocity (Vi.n In the position of the nearest M neighbors (P E IR xx2 Ni,. along with their velocities, and the position of the nearest M target goals. The CAPT accelerations and the corresponding state variables constitutes together one pair in the dataset.
[P [P Pjn Vj
The dataset consists of 55000 training examples and 125 validation examples. We train an ST-GNN on the training data and optimize the mean squared loss using ADAM algorithm with learning rate 0.0005 and decaying factors 31 0.9 and 32 = 0.999. We then keep the model with the lowest mean distance between the agent final position and its desired target among 60 epochs. The other training parameters are shown Table 2 The trained ST-GNN is then executed on a test dataset that consists of 1000 examples. The ST ST-GNN output for each example is the estimated accelerations, and the planned trajectories are then calculated using (95). One example was shown in Fig. 2 (Left), which depicts free-collision trajectories.
26

---

Published as a conference paper at ICLR 2022
Similar to the flocking experiment, we test the trained ST-GNNs with different graph-time topologies, generated with either different neighborhood sizes or different sampling times. Figures 2 (Middle) and (Right) uphold the conviction that the ST-GNN output difference increases with the distance between the underlying topologies.
27


Reviews:
[{"review_id": "zojw_BQbhh_", "reviewer": "Reviewer_u6ex", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-- Strengths:\n\n1. The paper is very well-written and easy to follow. It was a pleasure to read the novel theoretical material presented in this paper.  \n\n2. The paper proposes a new architecture based on their new operators and implementing the finite impulse response (FIR) filter recursively. \n\n3. The theoretical material in the paper is quite thorough and very detailed. In the appendix F, the authors also extend their stability analysis in the main paper to not only consider single-layer features but also extend their analysis to multiple features, which makes the theoretical contributions even stronger.\n\n-- Weaknesses:\n\n1. The experiments in this paper are done on synthetically generated datasets for two applications of flocking and unlabelled motion planning. I would have liked to see experiments done on more real-world mobility datasets to better understand the applicability of the proposed method. It is evident from the in-depth theoretical analysis that the author’s primary focus is to propose a novel architecture that comes with robustness guarantees. But, I feel that some experiments on real-world datasets would further strengthen this paper’s contributions.\n\n2. Can this method also be applied to “standard prediction tasks” on time-varying graphs? If so, could you please elaborate on this and how it would compare to other existing networks for time-varying graphs, e.g. graphon neural networks?\n\n3. If ST-GNN can also be used on standard prediction tasks and do a better job than other GNNs, I was wondering how it would handle the cases where we have heterophilous vs. homophilous time-varying networks? This would also be interesting to investigate. \n", "summary_of_the_paper": "This paper proposes a new deep learning architecture called ST-GNN that learns representations on graphs that evolve over time. Their work focuses on developing an interesting time-varying convolutional architecture, which exploits the graph-time underlying structure of the signals, processing across both the graph and time domains. The authors introduce new graph shift operators (GSO), time shift operators (TSO), followed by a linear combination of those which results in a space-time shift operator termed STSO. The advantage of this paper is that it can handle continuous-time graph signals and the stability of this proposed architecture is studied theoretically (Section 4) with a significant result outlined in Proposition 1 of the paper where the difference between the space-time graph filters of the original graph and the perturbed graph are upper bounded by the order of error introduced.   \n", "summary_of_the_review": "This paper proposes a novel architecture based on graph-shift, time-shift and space-time shift operators (also proposed by the authors in the paper) to handle time-varying graphs. The theoretical analysis of this paper is very thorough and clearly elucidates the stability of their NN architecture. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "yrwc0dOIuN", "reviewer": "Reviewer_G6p1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.\tThe paper is well-written and, despite heavily populated with math formulas and notation, I find it enjoyable and relatively easy to follow it through.\n2.\tThe proposed ST-GNN is principled, natural and neat.\n3.\tI like the analysis of ST-GNN’s stability to perturbations. I find it new and insightful, and especially interesting to read, though I am not an expert in this so I may be biased as well.\n\nWeaknesses:\n1.\tI am not sure if the experiments would be very appealing to the deep learning community because they do not compare with the many latest temporal network SOTAs, and the two tasks seem to mostly target audience from robotics and control. Technically speaking, it mainly uses temporal network dataset whose features have strong continuous-time dynamics, and only for node-level prediction task). To appeal to more audience from the ICLR community, I would suggest that the experiments be significantly extended by referencing and comparing with the following papers in recent years: [1, 2, 3, 4, 5]. Alternatively, the authors could be more explicit in restricting ST-GNN's application domain.\n2.\tDespite being well-principled and neat, the proposed space-time convolution (Equation 7) does not seem quite new to me. It seems essentially just a temporal convolution followed by graph diffusion which is not totally new ([6] for example adopted a very similar idea).\n\n[1] Inductive Representation Learning on Temporal Graphs\n[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks\n[3] EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs\n[4] Variational Graph Recurrent Neural Networks\n[5] JODIE: Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks\n[6] TEDIC: Neural Modeling of Behavioral Patterns in Dynamic Social Interaction Networks\n", "summary_of_the_paper": "This paper introduces a new spatio-temporal Graph Neural Network, ST-GNN, for making predictions on temporal network. Its proposed space-time convolution operator is a composition of temporal convolution and graph diffusion. The paper further proves that under practical conditions their ST-GNN with Integral Lipschitz filters is stale to small perturbation in both time and graph domain. ", "summary_of_the_review": "This is a well-written paper with a neat space-time convolution model and important theoretical contributions in analyzing its stability. However, as significant as its strengths are, its weaknesses are also concerning, which mainly involves two aspects: 1. the architecture of ST-GNN does not seem novel and may suffer from varying graph size; 2. it certain could have empirical studies done on more datasets and have more baselines compared.  Overall, I would be very happy to improve the score if we could see more extensive experiment with more baselines and positive results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kWFkx3XYW4q", "reviewer": "Reviewer_aJtV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1.  Solid theoretical support.\n2.  Jointly process graph and time domains in a single convolution operation.\n3.  Stable to small variations in graphs and sampling rates.\n\nWeakness\n1. Lack of comparison with other methods. \n2. Lack of time complexity analysis.\n3. The setting of hyper-parameters is not specified. \n", "summary_of_the_paper": "This paper introduces a space-time convolution operator that is robust to graph perturbations and small variations of sampling rates.", "summary_of_the_review": "Although this paper theoretically proves the stability of the proposed convolution operator, it does not provide experimental evidence about the superiority of the proposed method against other baseline methods. Given this paper is not the first to study time-varying graph signals, I think baseline comparison is necessary. Based on the above consideration, I think this paper is not ready for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new  time-varying convolutional architecture (ST-GNN) for dynamic graphs. The reviewers were positive about the presentation and detailed theory, especially on the stability analysis. The shared criticism was on experimental validation synthetic datasets that the reviewers did not find appealing. The AC believes that while the lacking validation concerns are legit, there is a lack of sophisticated dynamic graph benchmarks in the community yet, so the authors did their best effort to test their method. We thus recommend to accept the paper.
Decision: Accept (Poster)