Spatio-Temporal Graph Scattering Transform
Authors: Chao Pan
Siheng Chen
Antonio Ortega
Venue: ICLR 2021 Poster (2021)
Keywords: scattering transform
spatio-temporal graph
graph neural networks
skeleton-based action recognition

Abstract: Although spatio-temporal graph neural networks have achieved great empirical success in handling multiple correlated time series, they may be impractical in some real-world scenarios due to a lack of sufficient high-quality training data. Furthermore, spatio-temporal graph neural networks lack theoretical interpretation. To address these issues, we put forth a novel mathematically designed framework to analyze spatio-temporal data. Our proposed spatio-temporal graph scattering transform (ST-GST) extends traditional scattering transform to the spatio-temporal domain. It performs iterative applications of spatio-temporal graph wavelets and  nonlinear activation functions, which can be viewed as a forward pass of spatio-temporal graph convolutional networks without training. Since all the filter coefficients in ST-GST are mathematically designed, it is promising for the real-world scenarios with limited training data, and also allows for a theoretical analysis, which shows that  the proposed ST-GST is stable to small perturbations of input signals and structures. Finally, our experiments show that i) ST-GST outperforms spatio-temporal graph convolutional networks by an increase of 35% in accuracy for MSR Action3D dataset; ii) it is  better and computationally more efficient to design the transform based on separable  spatio-temporal graphs than the joint ones; and iii) nonlinearity in ST-GST is critical to empirical performance.

Published as a conference paper at ICLR 2021
SPATIO-TEMPORAL GRAPH SCATTERING TRANSFORM
Chao Pan
Siheng Chen
University of Illinois at Urbana-Champaign Champaign, IL, USA chaopan2 @ illinois.edu
Shanghai Jiao Tong University Shanghai, China
sihengc@sjtu. edu. cn
Antonio Ortega
University of Southern California Los Angeles, CA, USA antonio.ortega @ ce.usc.edu
ABSTRACT
Although spatio-temporal graph neural networks have achieved great empirical success in handling multiple correlated time series, they may be impractical in some real-world scenarios due lack of sufficient high-quality training data. Furthermore, spatio-temporal graph neural networks lack theoretical interpreta- tion. To address these issues, we put forth novel mathematically designed frame- work to analyze spatio-temporal data. Our proposed spatio-temporal graph scat- tering transform (ST-GST) extends traditional scattering transforms to the spatio- temporal domain. It performs iterative applications of spatio-temporal graph wavelets and nonlinear activation functions, which can be viewed as a forward pass of spatio peapioteempoal graph convolutional networks without training. Since all the filter coefficients in ST-GST are mathematically designed, it is promising for the real-world scenarios with limited training data, and also allows for theoretical amalysis, which shows that the proposed ST-GST is stable to small perturbations of input signals and structures. Finally, our experiments show that ST-GST out- performs remporll graph convolutional networks by an increase of 35% in accuracy for MSR Action3D dataset; ii) is better and computationally more ef- ficient to design the transform based on separable spatio-temporal graphs than the joint ones; and iii) the nonlinearity in ST-GST is critical to empirical performance.
INTRODUCTION
Processing and learning from spatio-temporal data have received increasing attention recently. Examples include: i) skeseton-based human action recognition based on sequence of human poses (Liu et al. (2019), which critical human behavior understanding (Borges et al.) (2013). and ii) multi-agent trajectory prediction (Hu et al. (2020)), which is critical to robotics and au- tonomous driving "Shalev-Shwand et al.] (2016)). A common pattern across these applications is that data evolves in both spatial and temporal domains. This paper aims to analyze this type of data by developing novel spatio-temporal graph- based data modeling and operations.
Spatio-tempors graph- based data modeling. Graphs are often used to model data where irregu- larly spaced samples are observed over time. Good spatio-temporal graphs can provide informative priors that reflect the internal relationships within data. For example, in skeleton-ber based human tion recognition, we can model a sequence of 3D joint locations as data supported on skeleton graphs across time, which reflects both the human physical constraints and temporal consistency (Yan al. 2018)). Recent studies on modeling spatio-temporal graphs have followed either joint or separable processing frameworks. Joint processing based on constructing single spatio-temporal graph and processing (c.g., filtering) via operations on this graph (Kao et al. 2019); Liu et al. (2020) ) In contrast, a separable processing approach works separately, and possibly with different opera- tors, across the space and time dimension. In this case, independent graphs are used for space and
"This work was mainly done while Chao Pan and Siheng Chen were working at Mitsubishi Electric Research Lahoratories (MERI.).

---

Published as a conference paper at ICLR 2021
However, no previous work thoroughly analyzes and compares these two constructions. In this work, we mathematically study these two types of graphs and justify the benefits of separable processing from both theoretical and empirical aspects.
time Yann al. (2018); Cheng et al. 22200))
Spatio-temporal graph-based operations. Graph operations can be performed once the graph structure is given. Some commonly used graph operations include the graph Fourier transform (Shu-) man et al. (2013), and graph wavelets (Hammond et al. I) It is possible to extend those operations to the spatio-temporal graph domain. For example. Grassi et al. (2017) developed the short time-vertex Fourier transform and spectrum-based time-vertex wavelet transform. However, those mathematically designed, linear operations show some limitations in terms of empirical per- formances. In comparison, many recent deep neural networks adopt trainable graph convolution operations to analyze spatio-temporal data (Yan al. (2018); [iu et al. (2020)). However, most net- works are designed through trial and error. It is thus hard to explain the rationale behind empirical success and further improve the designs (Monga et al. (2019). In this work, fill in the gap between mathematically designed linear transforms and trainable spatio temporal graph neural networks, we propose novel spatio-temporal graph scattering transform (ST-GST), which is a mathematically designed, nonlinear operation.
Specifically, to characterize the spatial and temporal dependencies, we present two types of graphs corresponding to joint and separable designs. We then construct spatio-temporal graph wavelets based on each of these types of graphs. We next propose the framework of ST-GST, which adopts spatio-temporal graph wavelets followed by a nonlinear activation function as single scattering layer. All the filter coefficients in ST-GST are mathematically designed beforehand and no training is required. We further show that i) a design based on separable spatio-temporal graph is more flexible and computationally efficient than a joint design; and ii) ST-GST is stable to small perturbations on both input spatio-temporal graph signals and structures. Finally, our experiments on skeleton- based human action recogmition show that the proposed ST-GST outperforms apatio-tempordl graph convolutional networks by 35% accuracy MSR Action3D dataset.
We summarize the main contributions of this work as follows:
We propose wavelets for both separable and joint spatio-tempol graphs. We show that it is more flexible and computationally efficient to design wavelets based on separable spatio-temporal graphs;
We propose a novel spatio-temporal graph scattering transform (ST-GST), which is a non-trainable counterpart of spatio-temporal graph convolutional networks and nonlinear version of spatio- temporal graph wavelets. We also theoretically show that ST-GST is robust and stable in the presence of small perturbations on both input spatio-temporal graph signals and structures;
For skeleton-based human action recognition, our experiments show that: i) ST-GST can achieve similar or better performances than spatio-temporal graph convolutional networks and other non- deep-learning approaches in small-scale datasets; ii) separable spatio peatio-temporal scattering works sig- nificantly better than joint spatio-temporal scattering; and iii) ST-GST significantly outperforms spatio-temporal graph wavelets because of the nonlinear activation function.
RELATED WORK
Scattering transforms. Convolutional neural networks (CNNs) use nonlinearities coupled with trained filter coefficients and are well known to be hard analyze theoretically (Anthony & Bartlet (009 ). As an alternative, Mallat (2012); Bruna & Mallat 2013) propose scattering transforms, which are non-trainable versions of CNNs. Under admissible conditions, the resulting transform enjoys both great performance in image classification and appealing theoretical properties. These ideas have been extended to the graph domain (Gama al. (2019a); Zou & Lerman (2020): Gao
et al. (2019) Joannidis et al. (2020)). Specifically, the graph scattering transform (GST) proposed in (Gama et al. (2019a) 9ah) iteratively applies predefined graph filter banks and element- wise nonlinear activation function. In this work, extend classical scattering transform to the apatio-temport domain and provide a new mathematically designed transform to handle spatio-temporal data. The key difference between GST and proposed ST-GST lies in the graph filter bank design, where ST-GST needs to handle both spatial and temporal domains.
Spatio-temporal neural networks. Deep neural networks have been adapted to operate on spatio- temporal domain. For example, [Lu et al. (2019) uses LSTM to process time series information, while ST-GCN (Yan et al. (2018) combines graph convolution layer and temporal convolution
2

---

Published as a conference paper at ICLR 2021
layer as unit computational block in the network architecture. However, those networks all require a huge amount of high-quality labeled data, and training them is computationally expensive, which may make them impractical for many real-world scenarios. Furthermore, many architectures de- signed through trial and error, making it hard to justify the design choices and further improve them. In this work, the proposed ST-GST is nonlinear transform with forward procedure similar that of ST-GCN. However, ST-GST does not require any training, which is useful in many applications where only limited training data is available. Furthermore, since all filter coefficients in ST-GST are predefined, it allows us to perform theoretical analysis and the related conclusions potentially shed some light on the design of spatio-tempores networks.
Skeleton- based human action recognition. Conventional skeleton based action recognition mod- els learn semantics based on hand-crafted features (Wang et al.] (2012)). To handle time series models are proposed to capture the temporal de-
information, some ceaurenttneural-netwwoo pendencies between consecutive frames (Kim & Reiter (2017)) Recently, graph-based approaches have gained in popularity while achieving excellent performance Yan et al. 20118 Li et al. 2011)) In this work, our experiments focus on this task and show that ST-GST outper the state-ol-the-ar spatio-tempora graph neural networks, like MS-G3D (Liu et al. 2020), on small-scale datasets.
SPATIO-TEMPORAL GRAPH SCATTERING TRANSFORM
In this section, first define spatio-temporal graph structures and signals. We next design spatio-temporal graph wavelets, Finally, we present ST-GST.
(a) Spatial graph
(b) Temporal graph (c) Kronecker product graph (d) Cartesian product graph
(e) Strong product graph
Figure I: Visualization of spatial graph, temporal graph and three commonly used product graphs.
3.1 SPATIO-TEMPORAL GRAPH STRUCTURES AND SIGNALS
Spatio-temporal data can be represented as matrix X R-NXT where N is the number of the spatial positions and T' is the number time stamps. In this matrix, each row is a time-series for spatial node, and each column is spatial signal at certain time stamp. Note that the index of spatial information can be arbitrary: we will associate each spatial location to a vertex on the spa- tial graph, and the edges will provide information about the relative position of the nodes. We can reshape the matrix to form a vector x of length NT, where the element X(a.t) = X(s-1)T++ is the feature value corresponding to the s-th vertex time I. To construct spatio-temporal graph, create connections based on physical constraints. For example, for skeleton seeleton-based based action recogni- tion, the spatial graph is the human skeleton graph, reflecting bone connections; see Fig. a); and the temporal graph is a line graph connecting consecutive time stamps; see Fig. Fig. [b)).
As starting point, we choose spatial graph G. (V,, A,) with [V, = N, reflecting the graph structure of each column in X and temporal graph G. (Vi, E,, Ae) with |V; T, reflecting the graph structure of each row in X. The separable spatio-tempore design is achieved by processing the columns and rows of X separately based on their respective graphs.
As an alternative, product graph, denoted as G G. G. = (V,E, E, A) can be constructed unify the relations in both the spatial and temporal domains, allowing us to process data jointly across space and time. The product graph G. o G. has | = NT nodes and an appropriately defined NT x NT adjacency matrix A. The operation interweaves two graphs to form unifying graph structure. The edge weight A (ss.t)) == A.T (x. 1)T++, characterizes the relation, such similarity dependency, between the s1-th spatial node at the ti-th time stamp and the sy -t spatial node at the t2 time stamp. There are three commonly used product graphs (Sandryhaila & Moura 2014): i) Kronecker product: G,009, G. with graph adjacency matrix as A A, 00 A, and
3

---

Published as a conference paper at ICLR 2021
represents the Kronecker product of matrices; see Fig e)); ti) Cartesian product: G G 9 with A = A.
IT
In @ A4; see Fig dd) and iii) strong product: g = Ge X g. with A = In @ A,, which can be viewed as combination of Kronecker and Cartesian The joint spatio-temporal design is achieved based on a product graph.
A, A, + A, l
products; see Fig
e)..
In this paper, we consider designs based both separable graphs and product graphs.
3.2 SPAPIO-TEMPORAL GRAPH FILTERING
We now show two graph filter designs, separable and joint filtering, based on the corresponding spatio-temporal graphs we just described. For each design, we first define the spatio-temporal graph shift, which is the most elementary graph filter and defines how information should propagate in a spatio-temporal graph. We then propose spatio-temporal graph filtering in both graph vertex and graph spectral domains.
Separable graph filters. Given the spatial graph G, Es, A.) and the temporal graph G. &,, At). , let the spatial graph shift be S, = A, and the temporal graph shift be S: = A For simplicity, we focus on the symmetric graph shifts. For apatio-temporal graph signal, spatial and temporal graph filtering work as, H(S,)X Σn- SP and XG (S.) x s, where hi are fy are spatial and temporal filter coefficients, respectively. In each modality, the graph filter is a polynomial of the graph shift. The polynomial orders and Q control the length of filters in the spatial and temporal modalities, respectively. Note that these two values can be chosen to be different, which provides additional design flexibility. Then, a separable spatio-temporal graph filtering operation can be defined as
P-1 ENpS p=0
Q-1 Σ q=u
HSS (S,)
=
S
X
Sq
= (H(S.) @ G(S.))
(1)
where the second equality follows from the property: M,XM; = (M, 8 M2)x.
We can also represent the filtering process in the graph spectral domain. Let the eigen-decompositiinn graphs of the spatial and temporal graphs be S, = V.A.V, and S, V,A,V, respectively, where
V. E NNN V. E RTx form the spatial and temporal graph Fourier bases. The elements along the diagonals of Ag, Ar represent the spatial and temporal graph frequencies. We have H(S.) V. Epp
XV, E V, XV,G(A,)VV Letting V = V. V., the spectral representation of the separable pratio-temporal graph filtering is then (V.H(A,)V V. X(VV) = v (H(A.) @ G(A,))VT x.
P-1 hpAgV, TX- V,H(As) V. X. X
Joint graph filters. Given the joint graph structure G GG E, A), let the spatio-temports graph shift be S A. Then, a joint spatio-temporal graph filtering operation can be defined as:
K-1
K Σ K=
HSSx = Σ h+ V A=
h & VT= (HX=VH(A)VTx
where hyp is the filter coefficient. The kernel function h(A) =K= h is applied to each diagonal element of A to obtain (A). Here h(A) is independent of any specific graph structure, and characterizes the filter response in the graph spectral domain. Note that h (ho, ,hx-1), h(A) and (-) are essentially the same thing, and are used interchangeably in this paper.
K-1
It is worth pointing out that these three product graphs share the same form of joint apatio-temponn graph filtering (2) as well as the same graph Fourier bases V = V, & V.. Following from (2). the spectral representation of the joint spatio-temporal graph filtering be formulated
Kronecker product:
H(S) = ((H(A, @ A,))VT,
Cartesian product: H(S) = V(H(A, & I + IN @ T.).VT
Strong product: H(S) VHHA,, & A, A, I + IN A.).VT.
'Some other choices of graph shift include the graph Laplacia matrix, graph transition matrix and their normalized counterparts. Adjacency matrix considered here for notation simplicity.
4

---

Published as a conference paper at ICLR 2021
Comparison between separable and joint graph filters. First of all, stress that both separable and joint spatio-temporal graph filtering share the same Fourier bases, meaning that they share the same frequency space and their difference only comes from the frequency responses.
Second, designing filters based on separable spatio-temporal graphs provides additional flexibility. Although it is conceptually simple to design graph filters directly on product graphs, the eigenvalues along the spatial and temporal domains are tied together, making it difficult to adjust the frequency responses independently for the two modalities. Moreover, two domains are forced to share the same set of filter coefficients and length. Take a filter defined on Kronecker product graph as an example.
By expanding the term HAA, @ At) we can have that (A,, @ A.) = k= h4, @ A.)*
-K-1
Ex h4 (A. & A This shows that the filter coefficients are applied on the product of spatial and temporal eigenvalues, making it hard to decompose and interpret the functionality of the filter in single modality. Such limitations make them less practical for spatio-temporal signals which might have distinct patterns in each of the two modalities. This problem is overcome by separable graph filtering, where different filters are applied to each modality. The ficxibility of separable graph filters means that one design different filters (h and g) with independent filter lengths (P and Q) in the spatial and temporal domains. However, it is worth pointing out that the representation power of these two formulations does not have clear relationship that one is a subset of the other. Consider joint graph filter designed on a strong product graph with length K = 3. The filter kernel is defined as H(A, @ Ar + A. @ LT + IN @ Ar) = Σx= hy (A, @ Ar + A @ +
+ IN 8 A1) Similarly, the kernel of separable graph filter with P = Q 3 can be written as H(A)) @ GA,)) =
(z Ag) @ (o Ag) By expanding the expression and rearranging the coefficients, one can obtain the coefficient matrices for the joint graph filter and the separable graph filter, C1 and C2. respectively; that is,
Tho hi
h1
ht2
hogo
hogh
ho92
[ho]
Ci
h1 +
2h2
2h2
C2
h190
hig1
h192
h1
[g0
91
92]
h2
2h2
hz
h29o
h291
h292.
[22]
where (ith element means the coefficient of term A & A/-1.
On one hand, it is obvious that C2 is always a rank matrix, while Ci could have rank 1, 2, or 3. So C1 is not special case of C2. On the other hand, C1 is always symmetric matrix, but C2 can be either symmetric or non-symmetric, depending on the choices of h and g. So C2 is also not a special case of C1. Therefore, the families spanned by two designs do not have any simple relationship that one is a subset of the other. Similar conclusions hold for the Kronecker and Cartesian products.
Third, designing based on separable spatio-temporal graphs is computationally more efficient. In a separable graph filtering process, we only need to deal with two small matrix multiplications (I), instead of one large matrix-vector multiplication (2) reducing the computational cost from O(N2T2) to O(N((N TT).
In short, the joint and separable graph filters two different design methods for spatio-temporal graphs. Though the representation power of separable graph filters is not necessarily much stronger than joint ones, separable design enjoys the flexibility, computation efficiency and straightforward interpretation. Empirical performances also show that the separable design outperforms the joint one; see Section 5 Note that this separable design coincides with the basic module widely used in spatio-temporal graph convolutional networks Li et al. (2019), which consists of one graph convo- lution layer followed by one temporal convolution layer.
3.3 TEMPORLL GRAPH WAVELETS
In time-series analysis and image processing, wavelets one of the best tools to design filter banks, allowing us to trade-off between the time-frequency resolutions and touching the lower bound of uncertainty principle of the time-frequency representations (Akansu & Haddad 2000). Inspired by this, we propose spatio-temporal graph wavelets, which include a series of mathematically designed graph filters provide multiresolution analysis for spatio-temporal graph signals. The proposed spatio-temporal graph wavelets are later used at each layer in the proposed ST-GST framework. Based on two types of graph structures, we consider two designs: separable and joint wavelets.
Separable graph wavelets. Based on separable spatio-temporal graph filtering
① we are able
to design spatial graph wavelets, (H,, (S.) Epro n J. = and temporal graph wavelets,
5

---

Published as a conference paper at ICLR 2021
S1) j= separately. For each modality, the filter at scale is defined as (S) = S S S S2i-) There also many other off-the-shelf graph wavelets we can choose from. More discussion about wavelets and their properties can be found in Appendix[A] Since two modalities are designed individually, the number of wavelet scales for each modality could be different. This is important in practice because the number of time samples T' is normally larger than the number of spatial nodes N. For each node in spatio-temporal graph, using different wavelet scales in the two domains allows for more flexibility to diffuse the signal with its neighbors. Based on this construction, when we choose J, and Jr scales for spatial and temporal domains, respectively, the overall number of scales for spatio-temporal wavelets is then J = J, x Jt-
(12) (G = ~ Dq
Joint graph wavelets. When the joint filtering (2) is chosen, we can directly apply existing graph wavelet designs, such as the spectral graph wavelet transform (Hammond et al. 2011
3.4 SPATIO-TEMPORAL GRAPH SCATTERING TRANSFORM
The proposed ST-GST is nonlinear version of apatio-tempont graph wavelets, which iteratively uses wavelets followed by a nonlinearity activation function. ST-GST includes three components: (i) spatio-temporal graph wavelets, (ii) a pointwise nonlinearity activation function a-). and (iii) low-pass pooling operator U. These operations are performed sequentially to extract representative features from input spatio-temporal graph signal X. The main difference between ST-GST and spatio-temporal graph wavelets is the application of nonlinear activation at each layer. The nonlinear transformation disperses signals through the graph spectrum, producing more patterns in spectrum.
Separable ST-GST. Let Z E NNXT be
graph signal. At each scattering layer, we sequentially use spatial graph wavelets {H J and temporal wavelets {G {G j2=1 to convolve with Z. Since each graph filter generates a new spatio-temporal graph signal, separable spatio- temporal graph filtering generates J Jg x Jr spatio-temporal graph signals. Then, the nonlinear activation is applied for each spatio-temporat graph signal. For example, the (J1, f2)-th signal is ja (S:)). We can treat each filtered ppatio-temporal graph signal as one tree node. Given Z as the parent node, scattering layer produces J children nodes.
(i)))a) = (H, (S. JZG
To construct ST-GST, we first initialize the input data Zo X be the root of the scattering tree; and then, we recursively apply scattering layers at each node to produce children nodes, growing scattering tree; see Fig. 2 We can index all the nodes in this scattering tree by unique path from the
root to each node. For example, p(t) = (6ff" ) (7()) .22 ()))) is the path from root to one tree node in the ê-th layer, and the signal associated with Z (nt)). Data matrix (g))) is then sum-
marized by an pooling operator U.) to obtain a lower-dimensional vector (( = U (Z (()))) Various pooling methods can lead to different dimensions of scattering features. Common choices for (-) include average in the spatial domain (U = 11INN, Φ = UZ E R²'), average in the tem- poral domain (U + LTxI, & ZU E RR-) and average in both modalities (U NT LNxT, & U o Z E R), where o represent Hadamard product. Finally, all scattering features Pintay are con- L-1
catenated to construct a scattering feature map &(S., S, X)
(pco) Jall pc0 J
Joint ST-GST. Since we deal with a unifying graph, we can use the spatio-temporal product graph directly in combination with the ordinary graph scattering transform (Gama et al. (2019b))
Comparison with ST-GCNs. One distinct difference between ST-GST and ST-GCNs lies in the fact that the trainable graph convolution in each layer of ST-GCN performs the multiplication between a spatial graph shift and the feature matrix, which only extracts low-frequency information over the graph; while ST-GST leverages multiple spatio-temporal graph filters cover multiple frequency bands. Furthermore, predefined filter coefficients conform a frame (3) in each layer of ST-GST, which is crucial for establishing the stability of ST-GST shown in next section.
4 THEORETICAL ANALYSIS
Stability is the key to designing robust and reliable algorithms. However, since the training process of ST-GCNs is data-driven, it might be vulnerable to small perturbations added to training data, which may lead to significant degradation in practice. Trainable parameters make it hard to develop a theoretical analysis for ST-GCNs. In contrast, here we show that the proposed separable ST-GST is stable to perturbations on both spatio-temporal graph signals and structures. All proofs of statements

---

Published as a conference paper at ICLR 2021
Action: high waving
2,
Layer
h2
Spotial layer
Layer
82
g1
82
Temporal layer 1
Zuoan
Zuaan
Ziaan
Spalisl layar 2
Layer 2
Temporal layer
Zianaa Zaanna) Z(aDZa))
Z((2222)
Figure 2: Scattering tree of separable ST-GST with L. 3, 2.
in this section are explained thoroughly in Appendix B Unless specified, |xx|| is the Ee norm for v,ctor while |X|| and ||||| are the Frobenius and spectral norm for matrix X, respectively.
Here we show the results for separable spatio-temporal graph scattering transform. But all the results can be extended the joint version. Before introducing perturbations, we first show that separable spatio-temporal graph wavelets also satisfy certain frame bounds. Thus, with separable construction, we can control bound constants for spatio-temporal wavelet and build tight frames.
Let (H, 1 and (Gjz)/z=1 be the wavelet filter bank for spatial domain and for temporal domain, respectively. Both satisfy frame properties such that for any R2 and y E RT.
Lemma 1.
x
HH, (S.)x S B 1
G, Bayy
.1
Then, for any Z E R NXT and its corresponding reshaped vector NT it holds that
J,.J
J.iJ
AG4
Z
Σ
[H (S.) G (S))2(1
Σ
|
H (S,) I.)
B B
h1===1
J1-j==1
Lemma [ guaranttes that separable design can also lead to valid wavelets. Furthermore, when we choose both spatial (H, 1. 11:=1 and temporal {G 1/ be tight frames with A₁ Bı Ag B2 (Shuman et al. 2015), the resulting separable wavelet also conforms tight frame. In later
context, denote B = B, x B2 as the frame bound constant separable spatio-temporal graph
wavelet, and separable ST-GST is configured with L layers and J = Jg Jr scales each layer.
4.1 STABILITY TO PERTURBATION OF SPATIO-TEMPORI GRAPH SIGNALS
Consider the perturbed spatio-tempory graph signal X - X - A E NXT, where A E R is the perturbation matrix. Such an additive model can represent measurement noise caused by devices or adversarial perturbations added manually. Theorem [ shows that the feature map for perturbed signal will not deviate much from original feature map under small input perturbations.
Theorem 1. Consider the additive noise model for input data X, it then holds that
( S, X) (S. XII
Σ Ei Σ J
L-1
B
|||.
(4)
/TEL-1J
VNT
The difference of output is normalized by the squared root of dimension of the final feature map. Note that we can construct spatio-temporal wavelet easily with B 1 when spatial and tempo- ral wavelets are both tight frames, then the normalized bound presented in 4 indicates that the transform is insensitive perturbations on input signals as the factor is much smaller than 1.

---

Published as a conference paper at ICLR 2021
Method
Accuracy (%)
Method
Accuracy (%)
GFT+TPM
74.0
Deep LSTM
60.7
HDM
81.8
GNNS
PA-LSTM ST-LSTM+TG
62.9
Scattering GNNs
Temporal Conv.
72.1
69.2
ST-GCN (fixed topology)
52.0
Temporal Conv.
74.3
MS-G3D (Jearnble topology)
82.2
ST-GCN (lixed topology)
Separable ST-GST (5, 10, 3)
81.4
Sepurable ST-GST' (5. 20, 2)
68.7
Separable ST-GST (5, 20, 3)
87.0
Scattering
Separable ST-GST (S, 20, 3)
73.1
Joint Kroneeker ST-GST (15, 3)
61.0
Joint Kronecker ST-GST (15,
55.7
Joint Cartesian ST-GST (15, 3)
59.1
Joint Cartesian ST-GST (15,3)
56.2
Joint Strong ST-GST (15, 3)
61.7
Joint Strong ST-GST (15,3)
57.1
Table 1: Classification accuracy (MSR Action3D
Table 2:
Classification accuracy (NTU-RGB+D with 40, 320 training and 16, 560 testing samples).
with 288 training and 269 testing samples).
92
wit roniinaatt without noniinortty
80
Classitcaton acouray
Valhode
60
St-d51 (s,
ST-CS1 (5,
ST-GST (%,
ST-GST (X, 20,
15, S1-GUN (Baed topoloo
Tempprol Comvolution
ST-GGK topoleer
10
15
20
35
30
20000
40000
60000
16 20.31
(5.20, 15 10,
Traming (9)
Computriion cost
Paramotor set U.J..4 BT-05T
(a) Limited training data.
(b) Performance time.
(c) Nonlinear vs. linear.
Figure 3: Performance comparisons with various settings about training ratio, time and nonlinearity.
4.2 STABILITY TO PERTURBATION OF SPATIO-TEMPORAL GRAPH STRUCTURES
Perturbations the underlying graph usually happen when the graph is unknown when the graph changes over time (Segarra et al. 2017). Since such kind of perturbations usually happen in spatial domain, here we simply consider the structure perturbations
the spatial graph only, Specifically, S,E, where E is the perturbation matrix Appendix B
we consider the perturbed spatial graph S. = S. E and temporal graph S; is not changed. Detailed descriptions
E TT.
Theorem 2. Suppose eigenvalues {m,]],] of E NxN are organized in order such that [ma < m22| I ... S |m:]l, satisfying |m,v] S c/2 and |m:/mx- - 1| S 6 for and all i's. Suppose spatial filter bank {H J satisfies max; (A)] S C and temporal filter bank {G
satisfics limited spectral response max; [A) & D. then holds that
[ Sc, X)- S.,
eCD BVNT
X
(5)
TEEL Jr
ΣEJ
where characterizes the perturbation level. Theorem 2isows that ST-GST is stable transform also for structure deformation, as the norm of change of feature map is linear in e. It is worth pointing out that the upper bound in both Theorems [ and 2 only depend on the choice of filter banks and
structure of scattering tree, instead of quantities related with specific graph support S, and S, that
are shown in previous works (Gama et al. 2019b Zou & Lerman 2020
Levie et al. 2019).
EXPERIMENTAL RESULTS
We now evaluate the performance of proposed ST-GST in skeleton- based action recognition task.
Experimental setup. The number of layers, L, the number of spatial wavelet scales, Js, and the number of temporal wavelet scales, Jr, are represented by (Ja, L) for separable ST-GST, and (J, L) for joint ST-GST. Training ratio means the fraction of data used for training in the training set. For the spatial domain, we use the skeleton graph; and for the temporal domain, we use a line graph connecting consecutive time stamps, Fig. (b). Geometric scattering wavelets used
8

---

Published as a conference paper at ICLR 2021
in both domain, and the nonlinear activation af-) is absolute value function which has the property of evergy-preserving Features output by ST-GST are then utilized by random forest classifier with 300 decision trees for classification.
Comparison with state-of-the-art methods. We consider two datasets, MSR Action3D and NTU- RGB+D (cross-subject). For MSR Action3D, the proposed ST-GST is compared with GFT facili- tated by temporal pyramid matching (GFT+TPM) (Kao et al. 2019), Bayesian hierarchical dynamic model (HDM) (Zhao et al. 2019), and few deep learning approaches, including temporal convo- lution neural networks (Kim & Reiter, 2017), ST-GCN Yan et al. 2018), and MS-G3D (Liu et al, 2020 For NTU-RGB+D, Deep LSTM (Liu et al., 2019), part- LSTM (PA-LSTM) (Liu al. 2019) and spatio-tempore LSTM with trust gates (ST-LSTM+TG) (Liu et al. 2016) are included in comparison. Methods labeled "fixed topology" are modified so as not to use adaptive training of the adjacency matrix in order for the comparison with ST-GST to be fair. Tables [ compares the classification accuracies on MSR Action3I and NTU-RGB+D, respectively. We see that even without any training, the performance of ST-GST is better than other non-deep-leariing and LSTM- based methods, and is comparable with state-of-the-ard GCN-based methods in large-scale dataset. Further, ST-GST outperforms all other methods when the size of training set is small. Fig. (a) shows the classification accuracy as a function of the training ratio. When training ratio is less than 20%, ST-GST significantly outperforms ST-GCN. Fig. (3)b shows the accuracy- time plot, reflecting that ST-GST is much faster than ST-GCN with similar classification performance.
ST-GST works well in small-scale-data regime. Table and Fig. Ba show that ST-GST out- performs other deep learning methods in the mhall-scale-date regime, which can be explained as follows. The good performance of spatio-temporal graph neural networks highly relies on the as- sumption that the training data is abundant. When the size of training set is limited, most of them can be easily trapped into bad local optima due to overfitting, resulting in a significant drop of classi- fication accuracy. But in practice, obtaining huge amount of training data with high-quality labels could be extremely expensive. On the other hand, since ST-GST is non-trainable framework, filter coefficients in ST-GST are mathematically designed rather than trained by data, which avoids the problem of overfitting when the training ratio is low. Another advantage of ST-GST compared to ST-GCN is that it requires less computation because no training process is involved in ST-GST.
Separable design better than joint design. Tables 1 and 2 also show that separable spatio- temporal graph wavelets work much better than joint ones, achieving 25% increase in classification accuracy for MSR Action3D dataset. The result consistent with our analysis in Section 3.2 The intuition is that when dealing with spatio-temporal data generated from complex structures like skeleton sequences, the fixed dependencies generated by product graphs highly restrict the way how signals be diffused in spatio-temporal graphs and thus limit the efficiency of feature extraction.
Nonlinearity is beneficial. Fig. ( compares ST-GST with and without nonlinearity and shows that it is critical ST-GST, also reflecting the potential effect of nonlinearity in ST-GCNs.
CONCLUSIONS
In this work we propose a novel spatio-temporal graph scattering transform (ST-GST), which can be viewed as one forward pass spatio-temporal graph convolutional networks (ST-GCNs) without any training. ST-GST is stable to small perturbations on both input signals and structures. Our experiments show that: i) ST-GST can achieve better performance than both non-deep-learning and ST-GCNs based methods when the size of training samples is limited; ii) designing spatial and temporal graph filters separately is more flexible and computationally efficient than designing them jointly; and iii) the nonlinearity is critical to the performance.
7
ACKNOWLEDGEMENT
This work is fully supported by Mitsubishi Electric Research Laboratories (MERL), where Chao Pan was research intern, Siheng Chen was research scientist and Antonio Ortega is a consultant.
REFERENCES
Ali N. Akansu and Richard A. Haddad. Multiresolution signal decomposition: transforms, sub- bands, and wavelets. Academic press, edition, 2000.

---

Published as a conference paper at ICLR 2021
Martin Anthony and Peter L Bartlett. Neural network learning: foundation... cambridge university press, 2009.
Mustafa Bilgic, Lilyana Mihalkova, and Lise Getoor. Active learning for networked data. In Pro- ceedings of the 27th international conference on machine learning, pp. 79-86, 2010.
Paulo Vinicius Koerich Borges, Nicola Conci, and Andrea Cavallaro. Video-based human behavior understanding: A survey. IEEE transactions on circuits and systems for video technology, 23(11): 1993-2008, 2013.
Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE transactions on pattern analysis and machine intelligence, 35(8):1872-1888) 2013.
Ke Cheng, Yifan Zhang, Xiangyu He, Weihan Chen, Jian Cheng, and Hanqing Lu. Skeleton-based action recognition with shift graph convolutional network. In Proceedings of the TEEF/CVF Conference on Computer Vision and Pattern Recognition, pp- 183-192, 2020.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms on graphs. In International Conference on Learning Representations, 2019a.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph scattering transforms. In Advances in Neural Information Processing Systems, pp. 0038-8048, 2019b.
Feng Gao, Guy Wolf, and Matthew Hirn. Geometric scattering for graph data analysis. In Interna- tional Conference on Machine Learning, pp. 2122-2131, 2019.
Francesco Grassi, Andreas Loukas, Nathanaël Perraudin, and Benjamin Ricaud. A time-vertex signal processing framework: Scalable processing and meaningful representations for time-series on graphs. IEEE Transactions on Signal Processing, 66(3):817-82) 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Yue Hu, Siheng Chen, Ya Zhang, and Xiao Gu. Collaborative motion prediction via neural motion message passing. In 2020 IEEE/CVE Conference on Computer Vision and Patern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 2318-6327 IEEE, 2020.
Vassilis N loannidis, Siheng Chen, and Georgios B Giannakis. Pruned graph scattering transforms. In International Conference on Learning Representations, 2020.
Jiun- Yu Kao, Antonio Ortega, Dong Tian, Hassan Mansour, and Anthony Vetro. Graph based skele- ton modeling for human activity analysis. In 2019 IEEE International Conference on Image Processing (ICIP), pp. 2025-2029, IEEE, 2019.
Tae Soo Kim and Austin Reiter. Interpretable 3d human action analysis with temporal convolu- tional networks. 2017 IEEE conference on computer vision and pattern recognition workshops (CVPRW), pp. 1623-1631. IEEE, 2017.
Ron Levie, Elvin Isufi, and Gitta Kutyniok. On the transferability of spectral graph filters. In 2019 13th International conference on Sampling Theory and Applications (SampTA), pp. 1-5. IEEE, 2019.
Maosen Li, Siheng Chen, Xu Chen, Ya Zhang, Yanfeng Wang, and Qi Tian. Actional-struuctuaal graph convolutional networks for skeleton- based action recognition. In IEEE Conference on Com- puter Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp- 3505-3603, Computer Vision Foundation IEEE, 2019.
Wanqing Li, Zhengyou Zhang, and Zicheng Liu. Action recognition based on bag of 3d points. In 2010 IEFE Computer Society Conference on Computer Vision and Pattern Recognition- Workshops, pp. 9-14. IEEE, 2010.
Jun Liu, Amir Shahroudy, Dong Xu, and Gang Wang. Spatio-temporal Istm with trust gates for 3d human action recognition. In European conference on computer vision, pp. 316-833. Springer, 2016.
10

---

Published as a conference paper at ICLR 2021
Jun Liu, Amir Shahroudy, Mauricio Perez, Gang Wang. Ling- Yu Duan, and Alex C. Kot. Ntu rgb+d 120: A large-scale benchmark for 3d human activity understanding. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019. doi: 10.1009TPAMM.20992991900
Ziyu Liu, Hongwen Zhang, Zhenghao Chen, Zhiyong Wang, and Wanli Ouyang. Disentangling and unifying graph convolutions for skeleton-based action recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 143- 2020.
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331-1398, 2012.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. arXiv preprint arXiv:1912. 2019.
Aliaksei Sandryhaila and Jose MF Moura. Big data analysis with signal processing on graphs: Rep- resentation and processing of massive data sets with irregular structure. IEEE Signal Processing Magazine, 31(5):80-90, 2014.
Santiago Segarra, Antonio G Marques, Gonzalo Mateos, and Alejandro Ribeiro. Network topology inference from spectral templates. IEEE Transactions on Signal and Information Processing over Nenworks, 33))-467-483, 2017.
Shai Shalev- SSwwarz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 2016.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high diteemsinnii data analysis to net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-9)) 2013.
David I Shuman, Christoph Wiesmeyr, Nicki Holighaus, and Pierre Vandergheynst. Spectrum- adapted tight graph wavelet and vertex-frequency frames. IEEE Transactions on Signal Process- ing, 63(16):4223 4235, 2015.
Jiang Wang. Zicheng Liu, Ying Wu, and Junsong Yuan. Mining actionlet ensemble for action recog- nition with depth cameras. In 2012 IEEE Conference on Computer Vision and Pattern Recogni- tion, pp. 1290-1297. IEEE, 2012.
Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-based action recognition. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pp. 7444-7452, AAAI Press, 2018
Rui Zhao, Wanru Xu, Hui Su, and Qiang Ji. Bayesian hicrarchical dynamic model for human action recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 7733-7742, 2019.
Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 49(3):1046-1074 2020.
11

---

Published as a conference paper at ICLR 2021
A DIFFERENT DESIGN OF GRAPH WAVELETS
There are many off-the-shelf, well-developed graph wavelets we can choose. They mainly focus on extracting features from multiple frequency bands of input signal spectrum. Some of them are shown as follows.
Monic Cubic wavelets. Monic Cubic wavelets (Hammond al. 2011 define the kernel function ((A) as
for
1;
(AA)
+5+ + 11A 6X2 + 23 for S S 2; A >> 2.
2/A
for
Different scales of filters are implemented by scaling and translation of above kernel function. Itersine wavelets. Itersine wavelets define the kernel function scale j as
h2()) sin (ī cos
(=( cos 5 - 1) 1 IsAS 1
-
Itersine wavelets form tight frames.
Geometric scattering wavelets. Geometric scattering wavelet filter bank (Gao et al. 2019 contains a set filters based on lazy random walk matrix. The filter scale j defined as H2(S)
S S S2 -II S2 - "), where S = (I AD- is the lazy random walk matrix and D the degree matrix.
Note that one is also allowed to customize either spatial temporal graph wavelets, once they conform a frame and satisfy integral Lipschitz constraint shown follows
<
H
< 1
[AV( s const AX,
j=1
where A, are scalar constants and N((+) the gradient of the kernel function.
B PROOFS
B. PROOF OF LEMMA 1
By reshaping the signal from Z to with Z,, I(s-1)T++s we can have that
J.Jy
J.
Σ
IH, (S.) G (S)))21
Σ
H
(S))
f1dt=1
JiJ==1
Since S, and S, do not change over computation process, we just use Hj, and G2, to represent hn
hIN
H (S.) and G,,(S)), respectively. Suppose H,; =
E NxN then we have
hNI
hNN
1111
GINGZ
Apply it vector and can have filtered signal Yji.a (HJ, & Gz E NT The first elements of y can also be written as
the Kronecker product H,, @ G
tini Gj2
hNN
Zun
Za
N
Zae
N
Z
Vi (1 T') Σ
G
hii
:
Zer
Z
12

---

Published as a conference paper at ICLR 2021
Therefore we have
Zi
Zi,1
Zi.
Zi,2
A
his
Σ j2
(1: - B2
Σ h1s
:
ZirT
ZE,T
Thus Eia Iy 11 can be sandwiched as
Zi,1
Zi,1
N
2
2
A3
huii
Jall
B2
Σ
hiss
j2
Zi,T
Zir
By definition of vector &2 norm, we can rewrite the upper and lower bound Eq. (6
as
Z
Z
Z
Zz
A3
Hig
Σ
My i
B3
H
:
jz
N
Z Z
Summing above quantity over fi gives that
Zi.i
Zz,r
Z2
4/431212
A
B
BB
h1.22
ZN.i/
ZN.i/
which completes the proof. Lemma iss very handful result. It shows that we can easily construct new spatio-temporal wavelets just by combining spatio and temporal ones. Moreover, the constants for new frame bound can easily obtained once we know the characteristics of the wavelets each domain. In particular, it also provides us convenient way to build tight frames for spatio-temporal data analysis with = B, because we just need to choose tight frames for spatial and temporal domain separately without considering possible correlations.
B.2 PROOF OF THEOREM !
We are considering pooling operator (-) as average in spatial domain in this proof, so U N 1 lix
and Φ UZ E RT. The proof techniques can be easily generalized to any form of U..). When
reshaping Z e R NXT IR. NT, the new pooling operator can be simply represented as
U' Ir, .I) E TXNT N
Φ = U'z.
Note that ||'|| N Consider scattering tree nodes at the last layer L Suppose they indexed from to J associated with signal
a and their parent nodes are indexed from to JL-2 associated with signal bi.... ... byu-2. When the input data X perturbed, signals scattering tree will change correspondingly. Here we simply denote them as a, b. Then for the change of feature vector located at node with a it holds that
|| Pa. Φa 2| = | (a; - ā 21 < || - ā = (lo(HH, @ Gb, - b.)) (6)
where ji j2 The last inequality holds because we are using absolute value function as nonlinear activation, which is non-expansive. Summing above quantity over ji J2 and by the frame bound proved in Lemma]] we can have that
J
JL-2
B
|a. &a
b
6.112
N
13

---

Published as a conference paper at ICLR 2021
Note that for sum of square norm of change at layer L - is
Σ
Φb. $b. 1
N Σ lb;;
b.ll2.
Compare Eq. have that
7 and 8
The upper bound only differs with factor B Then by induction we can
L-1
1 4-1
I S. X) - (S.., St, XII
1
Σ
B
-
Σ
B
|
N
N
t=
E=
Normalize it with the dimension of final feature map, we have
(S,,, Sr,, X) - (S., X).
1
Σ ビ= B
|
(9)
TE J
NT
Σi
J
B.3 PROOF OF THEOREM
Perturbations the underlying graph usually happen when the graph is unknown when the graph action recognition as an example.
changes over time (Segarra et al. 2017). Take Some joints may misrecognized with others due measurement noise of devices during certain frames, thus the location signals of those joints are interchanged. This leads to different spatial graph structures at those time stamps. Since such kind of perturbations usually happen spatial domain, here we simply consider the structure perturbations on the spatial graph only. But the results can be extended to more general cases.
Consider the original spatio-temporal graph as G with spatial graph shift matrix S, and tempo- ral one St, and the perturbed graph & with S, and St. We first show that ST-GST is invari- ant to node permutations in spatial domain, where the set of permutation matrices is defined as P (P (0, N)NNN P1 = 1,
PP IN ). Note that we considering average in UP.
spatial domain for U(.), so U = lIxN and Φ UZ E IR"",
Lemma 2. Consider the spatial permutation S, = P S, and input data X = P are also permuted in spatial domain correspondingly. Then, it holds that
Φ(S,. S, x) + ( S. X)
(10)
Proof. Note that the permutation holds for all signals computed in scattering tree; that is to say, (ipt = P Zy Suppose for path ( the last two filter are chosen as H(S)) and G(2)), then the feature vector after pooling with respect to new graph support and data can be written
2 si S,, ())) (S. G GS())))
= UPo(P H(S.) (mte) G (S:)) (S,))
The last equation holds due to definition of H(S). Since nonlinear activation is applied element- wise, we can rewrite as
Φ (pteny (S S. 2 ( = Uo (H. (pt)) (S.)))
Uo(H(SS))Z,:))) G (S.))
Qipcoy (S., S. Z ((()))
This conclusion holds independently of specific path p so it holds for all feature vector after pooling scattering tree. Since final feature map is just concatenation of all feature vectors, the proof is complete.
L
Lemma 2 shows that the output of ST-GST is essentially independent of the node ordering in spatial domain, long the permutation is consistent across all time stamps. This result intuitive
14

---

Published as a conference paper at ICLR 2021
because the output of graph convolution should only depend relative neighborhood structure of each node. Since node reordering will not alter neighborhood topology, the output should remain unchanged.
Based on Lemma 2 we use a relative perturbation model for structure modifications (Gama et al, 2019b), which focuses more the change of neighborhood topology compared to absolute per- turbations adopted in Levie et al. (2019). Define the set of permutations that make S, and S the closet as P. == arg millpep S.P Sall2- Consider the set of perturbation matrices S) [ S,P S, + E + S,E, P E Ps, E (RRNN). Then the relative distance to measure structure perturbations can defined
d(S,, S.)=
min SE
EE|2
Note that if S, PSS,P, meaning that the structure perturbation purely permutation, then the relative distance S.) = O, which is consistent with result shown in Lemma 2 Therefore, without loss of generality, we can assume that P = IN and S, = S. + E S. + +S,E E in later context. With this formulation, we are ready prove Lemma B]
Lemma 3. Suppose eigenvalues {m,}i= of E are organized in order such that mmj I [mg] S
< |ma], satisfying |mal Se/2 and [m,/nN - 1| for >> O. For spatial graph filter H(S.) and temporal graph filter G(S,). denote their kernel functions as ((A) and g()), respectively. If for
all X, h(A) is chosen to satisfy integral Lipschitz constraint (A)( I C Cand g(\) has bounded spectral response [a(A] <
D. Then holds that
HHS)) @ G(S,) - H(S.) @ G(S.) <CD+
(1I)
Proof. From Proposition Gama et al. (019b) we can have that when satisfies above condi- tions, [H(S)) - H(,)))l S eC + O So
HHS.)) @ G(S - H(S.) @ G(S)))|2 (HH(S.) H(S.)) 8 G(S.)
[H(S)) H(S)) G(S))
S cCD cCD+0(e).
The second line holds because H(S.) H(S)) symmetric matrix, which can be written as eigen-decomposition FΩF And (FRF (VAV²) (F @ V) @ AF V) holds, which finishes the proof. As for general structural perturbations, where we want to find |[H(S.) @ G(S,) - H(.)) G(S.) can add and subtract term H(S.) @ G(S)), use triangle inequality and further bound those two terms with more assumptions on h(A) and g(A).
The bound shown in Lemma indicates that the difference of output caused by changing spatial graph support from S, S, proportional to c, which is a scalar characterizing the level of the perturbation. Constraints on eigenvalues of E limits the change of graph structure. A more detailed description explaining the necessity of such constraints can found in Gama et al. (2019b). With Lemma 3 in hand, we are ready to show the change of feature vector after pooling at each node in scattering tree when such structure perturbations happen.
Lemma 4, Consider a ST-GST with I. layers and J = J, x Jr scales at each layer. Suppose that the graph filter bank forms frame with upper bound B B, B2, where B,, B2 are frame bounds for spatial and temporal domain, respectively. Suppose for all X, spatial wavelet filter bank (H ; satisfies max; (A)] < C and temporal wavelet filter bank {G 3/ satisfies max; 19: (A)l < D. and other conditions the same as Lemma Then for the change of feature vector 6pto associated with path p(9) it holds that
|1 I1 -
- ( S, x)II
-CDB=-1
(12)
VN
15

---

Published as a conference paper at ICLR 2021
Proof. Expand 1 S, x)= St, as
[ co (S.) G / (S:))) U'(o fo (S.) & G Go (S:)))
[1 (o (S.) X 1 (S (a J1 (S.) @ G f0 (S.)) ,
V
where ||0'|2 I/VN and (o
11 (S.) @ G 500 (S:))) p(t) is shorthand for applying spatio-
temporal filters and nonlinear activation in order to input data l times according to the path p() Add and subtract term (H (H & G 12 (H (S.) & G (g -..)) ....ooHHH go (S.) &
G go (S)))x and apply triangle inequality,
have that
(H cn (S.) @
G 22
- (a cn (S.) @ G (S:)))
< ||oH (S. G to (S.))
(a
(( ((-1))
@ G 5 (St) ((t)))
(o
G m (S) p(t x|
(a(H (S.) G (S.) o [H ,(n (S,) s G Gg (S.))
(a (-- (.) & G u- (S.)) x|
Recursive quantities can be observed above and the bound can be solved explicitly (Gama et al., 2019b). By induction and conclusion from Lemma we can get that
[H (S.) & G Gygn (Si))) (o J1 (S.) & G Gygn (Se))) S (cCDB<+)
Multiplying the coefficient 1/VN caused by pooling gets us the final result.
Note that the upper bound Lemma hholds for all path of length L. Thus the square norm of change in final feature map can be summarized by the sum of square norm of change at each layer, which finishes the proof of Theorem 2
C ADDITIONAL EXPERIMENTS
C.1 DATASET
MSR Action3D dataset (Li et al. 2010) is small dataset capturing indoor human actions. It covers 20 action types and 10 subjects, with each subject repeating each action 2 or times. The dataset contains 567 action clips with maximum number of frames 76; however, 10 of them are discarded because the skeleton information are either missing or too noisy (Wang et al.) 2012). For each clip, locations of 20 joints are recorded, and only one subject is present. Training and testing set is decided by cross- cross-subject split for this dataset, with 288 samples for training and 269 for testing.
NTU-RGB+D (Liu al. 2019) is currently the largest dataset with 3D joints annotations for human action recognition task. It covers 60 action types and 40 subjects. The dataset contains 56,880 action clips with maximum number of frames 300, and there are 25 joints for each subject in one clip. Each clip is guaranteed to have at most 2 subjects. The cross-subject benchmark of NTU-RGE+ includes 40,320 clips for training and 16,560 for testing.
Full table of performance on MSR Action3D dataset. The table contains performance comparison for different algorithms with different set of parameters on MSR Action3D dataset. Note that the triple shown after ST-GST represents the value for (Js. Jr, L). Methods labeled "fixed topology" are modified so as not to use adaptive training of the adjacency matrix in order for the comparison with ST-GST to be fair. Methods labeled "learnable topology" means that we use adaptive training for adjacency matrix to further validate our claim. Other configurations of compared methods are that ST-GST outperforms all other methods even
then set by default. From the table we when the graph topology can be learned by neural networks. The intuition behind this is that deep learning methods need large amount of training data due to the complex structures, and it can easily
16

---

Published as a conference paper at ICLR 2021
Method
Accuracy (%)
GFT+TPM
74.0
HDM
81.8
ST-GCN (fixed topology)
52.0
ST-GCN (learnable topology)
56.0
Temporal Conv. (resnet)
67.3
GNNS
Temporal Conv. (resnet-v3-gap)
69.9
Temporal Conv. (resnet-v4-gap)
72.1
MS-G3D (GCN scales=10, G3D scales=6)
80.3
MS-G3D (GCN scales=5, G3D scales=5)
81.4
MS-G3D (GCN scales=8, G3D scales=5)
82.2
Separable ST-GST (5, 5, 3)
73.6
Separable ST-GST (5, 5,
72.9
Scattering
Separable ST-GST (5, 10, 3)
81.4
Separable ST-GST (5, 15, 3)
85.9
Separable ST-GST (5, 20, 3)
87.0
Joint Kronecker ST-GST (15,3) 3)
61.0
Joint Cartesian ST-GST (15, 3)
59.1
Joint Strong ST-GST (15, 3)
61.7
Table 3: Full comparison of classification accuracy (MSR Action3D with 288 training and 269 testing samples).
Method
Accuracy (%)
Separable ST-GST (5, 5, 3)
73.4
Separable ST-GST (5, 20, 3)
86.7 + 0.4
Joint Kronecker ST-GST (5,
46.3 + 1.2
Joint Cartesian ST-GST (5,3)
42.2 1.1
Joint Strong ST-GST (5.3)
45.0 1.2
Joint Kronecker ST-GST (15, 3)
59.6 0.5
Joint Cartesian ST-GST (15,3)
58.6 + 1.0
Joint Strong ST-GST (15, 3)
60.0 + 1.0
Table Performance for different methods MSR Action3D with standard deviations.
be trapped into bad local optima due to overfitting when the size of training set is limited, which is common in practice. Also the good performance of ST-GST in sparse label regime could potentially inspire active learning for processing spatio-temporal data (Bilgic et al. 2010)).
Performance MSR Action3D dataset with standard deviations. We repeat part of exper- iments 20 times on MSR Action3D dataset, especially for joint approaches, to obtain the standard deviations of classification accuracy. The results are shown in Table Note that since ST-GST is mathematically designed transform, the output features should be the same for different trails, and the randomness comes from classifiers used later (random forest in this case). can be seen that the standard deviations are comparable in all these methods, and therefore the conclusion that separable ST-GST consistently outperforms joint ST-GST still holds.
Comparison between different choices of wavelets. In practice we find that using graph geometric scattering wavelets (Gao et al., 2019) for both spatial and temporal domain can achieve the best performance, which is reported in main text. Classification accuracy using other type of wavelets is shown here. All experiments performed here are separable ST-GST with J, = 5, J = 15, = on MSR Action3D dataset. An interesting observation that there is significant reduction in accuracy when we change temporal wavelet from diffusion based one (Geometric) to spectrum based one (MonicCubic or Itersine). This may caused by the design of different wavelets.
Stability of ST-GST. We also show the classification accuracy under different level of perturba- tions spatio-temporal signals and spatial graph structures in Fig. 4 The experiments
17

---

Published as a conference paper at ICLR 2021
Spatial wavelet
Temporal wavelet
Accuracy (%)
Geometric
Geometric
85.9
Geometric
MonicCubic
76,6
Geometric
Itersine
73.6
MonicCubic
Geometric
82.9
Itersine
Geometric
82.5
MonicCubic
MonicCubic
80.7
MonicCubic
Itersine
78.4
Itersine
MonicCubic
76.2
Itersine
Itersine
80.7
Table 5: Performance for different choices of spatial and temporal wavelets (MSR Action3D) with setting (5, 15, 3).
Classification accuracy (%)
80
Classification accuracy (%)
80
70
70
60
60
ST-GST (5, 20, 3)
ST-GST (5, 20,
ST-GST (5, 20, 2)
ST-GST (5, 20,
ST-CST (5, 3)
ST-CST (5. 10
40
40
20
30
40
50 SNR (dB)
60
70
10
10
10"
(a) Signal perturbations.
(b) Structure perturbations.
Figure 4: Comparisons on performance under different level of perturbations.
ducted on MSR Action3D dataset. For signal perturbation, signal-to-noiss ratio (SNR) is defined as ||| 10 log || For structure perturbation, E be a diagonal matrix, whose diagonal elements satisfy corresponding constraints on e. From both Fig. a) and (b) we can see that ST-GST is stable and will not deviate much from original output when the perturbations small.
18


Reviews:
[{"review_id": "oQr0DQ6LseM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors extend scattering transform to the spatio-temporal domain. The result ST-GST performs well with small size dataset.\n\nPros:\n1.  The authors propose a novel spatio-temporal graph scattering transform.\n2. The authors empirically shows that ST-GST outperform spatio-temporal graph convolutional networks and other non-deep methods in small-scale datasets.\n\n\nQuestions:\n1. We know that scattering-transform cannot do as well as CNN on larger dataset like Imagenet. Does ST-GST also have similar limitations?", "extra_scores": {}, "extra_text": {}}, {"review_id": "kmONksS5qT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose wavelets for both separable and joint spatio-temporal graphs. And then the authors design a spatio-temporal graph scattering transform (ST-GST), which is a non-trainable counterpart of spatio-temporal graph convolutional networks and a nonlinear version of spatiotemporal graph wavelets. Finally, the proposed SF-GST is conducted by experiments, and the results show that it appears to be effective. However, The authors did not give the explanation of the motivation about why did the STG should be scattered by wavelets. Besides, from the results in Table 1,  the joint versions based on the proposed method. i.e., Joint Kronecker, Joint Cartesian and Joint Strong, have not achieved the satisfied performance, though only separable versions performs best.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JyDOKd6n_PA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I will add it tomorrow", "extra_scores": {}, "extra_text": {}}, {"review_id": "IJZg2Qdgm9", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1/ Summary of the paper\n\nThis paper proposes a novel spatio-temporal graph scattering transform (ST-GST) as an intermediate representation of time-varying signals on graphs, which can then be fed into a simple ML model. Building on previously introduced Graph Scattering Transform (GST), the authors investigate the technical question of how to use both the spatial and temporal dimensions, proposing either a joint construction (GST applied on product graph) or a separate one (keeping both dimensions separate conceptually, while mixing). Theoretical results valid in both cases guarantee stability to noise in the input signal or the spatial graph.\nNumerical experiments show that the proposed method outperforms graph convolutional networks in the small data regime, and get a performance close to the state-of-the-art in the large data regime.\n\n2/ Acceptance decision\n\nAccept. This is a very good paper with novel contributions on the algorithmic side, theoretical guarantees and convincing numerical experiments.\n\n3/ Supporting arguments\n\n- In terms of novelty, this paper is the first to tackle the investigate the construction of a fixed representation of spatio-temporal graphs based on priors, using the graph scattering transform approach.\n- In terms of technical contributions, the paper delves into the interesting technical question of how to build such a transform, a proposes convincing arguments to support its final approach, the separable ST-GST. Further, the authors provide theoretical guarantees of the stability of the ST-GST representation with respect to input and spatial graph variations, based on assumptions on the pre-defined filters used in the transform.\n- Experimental results show that in the very low data regime (MSR Action3D dataset with only 288 training samples), the proposed approach improves upon the graph convolutional networks SOTA by ~5% of accuracy (87 vs 82.2). In the large data regime, the proposed method reaches a performance close to SOTA (73.1 vs 75.8% accuracy). The authors also show that the gap between GCN and ST-GST widens as the number of samples decreases.\n- This paper is well motivated and well written. Although it is quite dense and with involved mathematical operations, it is quite easy to follow.\n\n4/ Additional comments\n\n- The authors do a very nice job of putting the joint and separable graph filters under similar notations (Eq. 1 and 2). When it comes to comparing both approaches at the end of Sec 3.2, I am not sure to understand correctly the statement that the separable approach is more « flexible » than the joint one. While I understand that separability brings an easier interpretability of filter responses in the spatial and temporal domain, it seems also that in terms of polynomials with atoms of the form $\\lambda_s^p \\otimes \\Lambda_t^q$ for various $p$, $q$, the family spanned by separable transforms might be smaller than e.g. the strong product (although I’m not sure). Do you have any more insights in this direction?\n- In the numerical results of Table 1, the separable approach gets the better results with much more scales in the temporal dim (20) than in the spatial one (5). In the joint approaches, a single number of scales (15) is used, and it spans both dimensions. Beyond the computational requirements of the joint approach, do you think this forced equality is an issue for the joint approach?\n- In order to compare the significance of results in the low-data regime, standard deviations would have been appreciated, especially to understand the differences between the different joint approaches.\n- Minor details: which graph shift is used in the experiments reported in the last page of the main paper? In Section 3.2, the authors state $S = A$ (for both spatial, temporal and joint cases), but appendix A defines $S$ as a lazy random walk for geometric graph wavelets and Appendix C states that geometric graph wavelets are used in the main paper. Similarly, which non linear activation is used eventually?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies extensions of the Scattering Graph Transform to spatio-temporal domains. By exploring several design choices for spatio-temporal wavelet filters, the authors provide a solid and broad study of such predefined represenatations, including stability analysis as well as extensive empirical evaluations. 
Reviewers were generally favorable, and highlighted the importance of this method as providing a simple yet powerful baseline for spatio-temporal graph prediction tasks that requires no training. Despite some concerns about lack of analysis of the empirical results, the AC believes this work will provide a valuable baseline for future research and therefore recommends acceptance as a poster. 
Decision: Accept (Poster)