\section{Introduction}
\label{sec:intro}
\vspace{-2mm}
Processing and learning from spatio-temporal data have received increasing attention recently. Examples include: i)  skeleton-based human action recognition based on a sequence of human poses~(\cite{Liu_2019_NTURGBD120}), which is critical to human behavior understanding~(\cite{borges2013video}), and ii) multi-agent trajectory prediction~(\cite{HuCZG:20}), which is critical to robotics and autonomous driving~(\cite{shalev2016safe}). 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 \emph{data modeling} and {\em operations}. 

\mypar{Spatio-temporal graph-based data modeling} 
Graphs are often used to model data where irregularly 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-based human action 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~(\cite{yan2018spatial}). 
Recent studies on modeling spatio-temporal graphs have followed either joint or separable processing frameworks. 
{\em Joint processing} is based on constructing a single spatio-temporal graph 
and processing (e.g., filtering) via operations on this graph~(\cite{kao2019graph, liu2020disentangling}). In contrast, a {\em separable processing} approach works separately, and possibly with different operators, across the space and time dimension. In this case, independent graphs are used for space and time~(\cite{yan2018spatial, cheng2020skeleton}). 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.

\mypar{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~(\cite{shuman2013emerging}), and graph wavelets~(\cite{hammond2011wavelets}). It is possible to extend those operations to the spatio-temporal graph domain. For example,~\cite{grassi2017time} 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 performances. In comparison, many recent deep neural networks adopt trainable graph convolution operations to analyze spatio-temporal data~(\cite{yan2018spatial,liu2020disentangling}). However, most networks are designed through trial and error. It is thus hard to explain the rationale behind empirical success and further improve the designs~(\cite{monga2019algorithm}). In this work, to fill in the gap between mathematically designed linear transforms and trainable spatio temporal graph neural networks, we propose a 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 a 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 recognition show that the proposed ST-GST outperforms spatio-temporal graph convolutional networks by 35\% accuracy in MSR Action3D dataset.


We summarize the main contributions of this work as follows:

$\bullet$ We propose wavelets for both separable and joint spatio-temporal graphs. We show that it is more flexible and computationally efficient to design wavelets based on separable spatio-temporal graphs;
    
$\bullet$ We propose a novel spatio-temporal graph scattering transform (ST-GST), which is a non-trainable counterpart of spatio-temporal graph convolutional networks and a 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;
    
$\bullet$  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-temporal scattering works significantly better than joint spatio-temporal scattering; and iii) ST-GST significantly outperforms spatio-temporal graph wavelets because of the nonlinear activation function.

\vspace{-3mm}
\section{Related Work}
\label{sec:related}
\vspace{-3mm}

\textbf{Scattering transforms.} Convolutional neural networks (CNNs) use nonlinearities coupled with trained filter coefficients and are well known to be hard to analyze theoretically ~(\cite{anthony2009neural}). As an alternative,~\citet{mallat2012group, bruna2013invariant} 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~(\cite{gama2018diffusion, zou2020graph, gao2019geometric, ioannidis2019pruned}). Specifically, the graph scattering transform (GST) proposed in~(\cite{gama2018diffusion}) iteratively applies predefined graph filter banks and element-wise nonlinear activation function. In this work, we extend classical scattering transform to the spatio-temporal domain and provide a new mathematically designed transform to handle spatio-temporal data. The key difference between GST and our proposed ST-GST lies in the graph filter bank design, where ST-GST needs to handle both spatial and temporal domains.

\textbf{Spatio-temporal neural networks.}
Deep neural networks have been adapted to operate on spatio-temporal domain. For example,~\citet{Liu_2019_NTURGBD120} uses LSTM to process time series information, while  ST-GCN~(\cite{yan2018spatial}) combines a graph convolution layer and a temporal convolution layer as a 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 are designed through trial and error, 
making it hard to justify the design choices and further improve them. 
In this work, the proposed ST-GST is a nonlinear transform with a forward procedure similar to 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-temporal networks.

\textbf{Skeleton-based human action recognition.}
Conventional skeleton-based action recognition models learn semantics based on hand-crafted features~(\cite{wang2012mining}). To handle time series information, some recurrent-neural-network-based models are proposed to capture the temporal dependencies between consecutive frames~(\cite{kim2017interpretable}). Recently, graph-based approaches have gained in popularity while achieving excellent 
performance~\citep{yan2018spatial, LiCCZW0:19}. In this work, our experiments focus on this task and show that ST-GST outperforms the state-of-the-art spatio-temporal graph neural networks, like MS-G3D \citep{liu2020disentangling}, on small-scale datasets.


 





\vspace{-2mm}
\section{Spatio-Temporal Graph Scattering Transform}
\label{sec:ST-GST}
\vspace{-2mm}
In this section, we first define spatio-temporal graph structures and signals. We next design our spatio-temporal graph wavelets. Finally, we present ST-GST.

\begin{figure}[h]
\begin{center}
\includegraphics[width=\textwidth]{figs/different_graphs.png}
\end{center}
\vspace{-1mm}
\caption{Visualization of spatial graph, temporal graph and three commonly used product graphs.}
\vspace{-2mm}
\label{fig:product_graph}
\end{figure}
\vspace{-3mm}

\subsection{Spatio-temporal graph structures and signals}
\vspace{-1mm}
Spatio-temporal data can be represented as a matrix $\mathbf{X}\in\mathbb{R}^{N\times T}$, where $N$ is the number of the spatial positions and $T$ is the number of time stamps. In this matrix, each row is a time-series for a spatial node, and each column is a spatial signal at a certain time stamp. Note that the index of spatial information can be arbitrary: we will associate each spatial location to a vertex on the spatial graph, and the edges will provide information about the relative position of the nodes. We can reshape the matrix to form a vector $\mathbf{x}$ of length $NT$, where the element $\mathbf{x}_{(s,t)}  := \mathbf{x}_{(s-1)T+t}$ is the feature value corresponding to the  $s$-th vertex at time $t$. 
To construct a spatio-temporal graph, we create connections based on physical constraints. For example, for skeleton-based action recognition, the spatial graph is the human skeleton graph, reflecting bone connections; see Fig.~\ref{fig:product_graph}(a); and the temporal graph is a line graph connecting consecutive time stamps; see Fig.~\ref{fig:product_graph}(b). 

As a starting point, we choose a spatial graph $\mathcal{G}_s = (\mathcal{V}_s, \mathcal{E}_s, \mathbf{A}_s)$ with $|\mathcal{V}_s|=N$, reflecting the graph structure of each column in $\mathbf{X}$ and a temporal graph  $\mathcal{G}_t = (\mathcal{V}_t, \mathcal{E}_t, \mathbf{A}_t)$ with $|\mathcal{V}_t|=T$, reflecting the graph structure of each row in $\mathbf{X}$. The {\em separable spatio-temporal design} is achieved by processing the columns and rows of $\mathbf{X}$ separately based on their respective graphs. 

As an alternative, a product graph, denoted as $\mathcal{G}=\mathcal{G}_s \diamond \mathcal{G}_t=(\mathcal{V}, \mathcal{E}, \mathbf{A})$ can be constructed to unify the relations in both the spatial and temporal domains, allowing us to process data {\em jointly} across space and time. The product graph $\mathcal{G}_s \diamond \mathcal{G}_t$  has $|\mathcal{V}|=NT$ nodes and an appropriately defined $NT\times NT$ adjacency matrix $\mathbf{A}$. The operation $\diamond$ interweaves two graphs to form a unifying graph structure.  The edge weight $\mathbf{A}_{(s_1,t_1), (s_2,t_2)} := \mathbf{A}_{(s_1-1)T+t_1, (s_2-1)T+t_2}$ characterizes the relation, such as similarity or dependency, between the $s_1$-th spatial node at the $t_1$-th time stamp and the $s_2$-th spatial node at the $t_2$-th time stamp. There are three commonly used product graphs \citep{sandryhaila2014big}: i) Kronecker product: $\mathcal{G} = \mathcal{G}_s\otimes\mathcal{G}_t$ with graph adjacency matrix as $\mathbf{A}=\mathbf{A}_s\otimes \mathbf{A}_t$ and $\otimes$ represents the Kronecker product of matrices; see Fig~\ref{fig:product_graph}(c); ii) Cartesian product: $\mathcal{G} = \mathcal{G}_s\times\mathcal{G}_t$ with  $\mathbf{A}=\mathbf{A}_s \otimes \mathbf{I}_{T}+\mathbf{I}_{N}\otimes \mathbf{A}_t$; see Fig~\ref{fig:product_graph}(d); and iii) strong product: $\mathcal{G} = \mathcal{G}_s\boxtimes\mathcal{G}_t$ with $\mathbf{A}=\mathbf{A}_s\otimes \mathbf{A}_t + \mathbf{A}_s\otimes \mathbf{I}_{T}+\mathbf{I}_{N}\otimes \mathbf{A}_t$, which can be viewed as a combination of Kronecker and Cartesian products; see Fig~\ref{fig:product_graph}(e). The {\em 
joint spatio-temporal design} is achieved based on a product graph. 




In this paper, we consider designs based on both separable graphs and product graphs.


\vspace{-1mm}
\subsection{Spatio-temporal graph filtering}
\vspace{-1mm}
\label{sec:st_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.


\textbf{Separable graph filters.}
Given the spatial graph $\mathcal{G}_s = (\mathcal{V}_s, \mathcal{E}_s, \mathbf{A}_s)$ and the temporal graph $\mathcal{G}_t = (\mathcal{V}_t, \mathcal{E}_t, \mathbf{A}_t)$, let the spatial graph shift be  $\mathbf{S}_s=\mathbf{A}_s$ and the temporal graph shift be  $\mathbf{S}_t=\mathbf{A}_t$~\footnote{Some other choices of a graph shift include the graph Laplacian matrix, graph transition matrix and their normalized counterparts. Adjacency matrix is considered here for notation simplicity.}. For simplicity, we focus on the symmetric graph shifts. For a spatio-temporal graph signal, spatial and temporal graph filtering work as, $\mathbf{H}(\mathbf{S}_s)\mathbf{X} = \sum_{p=0}^{P-1} h_p\mathbf{S}_s^p \mathbf{X}$ and $\mathbf{X} \mathbf{G}^\top(\mathbf{S}_t) = \mathbf{X} (\sum_{q=0}^{Q-1} g_{q}\mathbf{S}_t^{q})^\top$, where $h_p$ are $g_{q}$ are spatial and temporal filter coefficients, respectively. In each modality, the graph filter is a polynomial of the graph shift. 
The polynomial orders $P$ 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
\begin{eqnarray}
\label{eq:separable_filter}
\vspace{-3mm}
  \mathbf{H}(\mathbf{S}_s)\mathbf{X} \mathbf{G}^\top(\mathbf{S}_t)
  :=  \left( \sum_{p=0}^{P-1} h_p\mathbf{S}_s^p \right) \mathbf{X} \left( \sum_{q=0}^{Q-1} g_{q}\mathbf{S}_t^{q} \right)^\top
  = \left( \mathbf{H}(\mathbf{S}_s) \otimes \mathbf{G}(\mathbf{S}_t) \right) \mathbf{x},
\vspace{-3mm}
\end{eqnarray}
where the second equality follows from the property: $\mathbf{M}_1 \mathbf{X} \mathbf{M}_2^T=(\mathbf{M}_1\otimes \mathbf{M}_2)\mathbf{x}$.

We can also represent the filtering process in the graph spectral domain. Let the eigen-decomposition of the spatial and temporal graphs be $\mathbf{S}_s= \mathbf{V}_s \mathbf{\Lambda}_s {\mathbf{V}_s}^\top$ and $\mathbf{S}_t= \mathbf{V}_t \mathbf{\Lambda}_t {\mathbf{V}_t}^\top$, respectively, where $\mathbf{V}_s \in \mathbb{R}^{N\times N}, \mathbf{V}_t \in \mathbb{R}^{T\times T}$ form the spatial and temporal graph Fourier bases. The elements along the diagonals of $\mathbf{\Lambda}_s, \mathbf{\Lambda}_t$ represent the spatial and temporal graph frequencies. We have $\mathbf{H}(\mathbf{S}_s)\mathbf{X} = \mathbf{V}_s \sum_{p=0}^{P-1} h_p \mathbf{\Lambda}_s^p {\mathbf{V}_s}^\top \mathbf{X} = \mathbf{V}_s \mathbf{H}(\mathbf{\Lambda}_s) {\mathbf{V}_s}^\top \mathbf{X}$, $\mathbf{X} \mathbf{G}^\top(\mathbf{S}_t) = \mathbf{X} \mathbf{V}_t \sum_{q=0}^{Q-1} g_q \mathbf{\Lambda}_t^q {\mathbf{V}_t}^\top  = \mathbf{X} \mathbf{V}_t \mathbf{G}(\mathbf{\Lambda}_t) {\mathbf{V}_t}^\top$. Letting $\mathbf{V} = \mathbf{V}_s \otimes \mathbf{V}_t$, the spectral representation of the separable spatio-temporal graph filtering is then
$
 (\mathbf{V}_s  \mathbf{H}(\mathbf{\Lambda}_s)\mathbf{V}_s^\top)\mathbf{X} (\mathbf{V}_t \mathbf{G} (\mathbf{\Lambda}_t)\mathbf{V}_t^\top)^\top  \ = \ \mathbf{V} \left(\mathbf{H}(\mathbf{\Lambda}_s)\otimes\mathbf{G}(\mathbf{\Lambda}_t) \right) \mathbf{V}^\top \mathbf{x}.
$

\textbf{Joint graph filters.}  Given the joint graph structure $\mathcal{G}=\mathcal{G}_s \diamond \mathcal{G}_t=(\mathcal{V}, \mathcal{E}, \mathbf{A})$, let the spatio-temporal graph shift be $\mathbf{S} = \mathbf{A}$. Then, a joint spatio-temporal graph filtering operation can be defined as:
\begin{align}
\label{eq:fre_filter}
  \mathbf{H}(\mathbf{S})\mathbf{x} = \sum_{k=0}^{K-1} h_k\mathbf{S}^k \mathbf{x} = \mathbf{V} \left(\sum_{k=0}^{K-1} h_k\mathbf{\Lambda}^k\right) \mathbf{V}^\top\mathbf{x} = \mathbf{V} \mathbf{H}(\mathbf{\Lambda})\mathbf{V}^\top \mathbf{x},
\end{align}
where $h_{k}$ is the filter coefficient. The kernel function $h(\lambda)=\sum_{k=0}^{K-1}h_k\lambda^k$ is applied to each diagonal element of $\mathbf{\Lambda}$ to obtain $\mathbf{H}(\mathbf{\Lambda})$. Here $h(\lambda)$ is independent of any specific graph structure, and characterizes the filter response in the graph spectral domain. Note that $\mathbf{h}=(h_0,\cdots,h_{K-1})$, $h(\lambda)$ and $\mathbf{H}(\cdot)$ are essentially the same thing, and are used interchangeably in this paper. 

It is worth pointing out that these three product graphs
share the same form of joint spatio-temporal graph filtering~(\ref{eq:fre_filter}) as well as the same graph Fourier bases $\mathbf{V} = \mathbf{V}_s \otimes \mathbf{V}_t$. Following from~(\ref{eq:fre_filter}), the spectral representation of the joint spatio-temporal graph filtering can be formulated as 
\begin{align*}
    \text{Kronecker product:}\quad \mathbf{H}(\mathbf{S}) &=  \mathbf{V}(\mathbf{H}(\mathbf{\Lambda}_s\otimes\mathbf{\Lambda}_t))\mathbf{V}^\top,\\
    \text{Cartesian product:}\quad \mathbf{H}(\mathbf{S}) &= \mathbf{V}(\mathbf{H}(\mathbf{\Lambda}_s\otimes\mathbf{I}_T + \mathbf{I}_N\otimes \mathbf{\Lambda}_t))\mathbf{V}^\top, \\
    \text{Strong product:}\quad \mathbf{H}(\mathbf{S})
    &= \mathbf{V}(\mathbf{H}(\mathbf{\Lambda}_s\otimes\mathbf{\Lambda}_t + \mathbf{\Lambda}_s\otimes\mathbf{I}_T + \mathbf{I}_N\otimes \mathbf{\Lambda}_t))\mathbf{V}^\top.
\end{align*}

\textbf{Comparison between separable and joint graph filters.} First of all, we 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 $\mathbf{H}(\mathbf{\Lambda}_s\otimes\mathbf{\Lambda}_t)$ we can have that
$
    \mathbf{H}(\mathbf{\Lambda}_s\otimes\mathbf{\Lambda}_t) = \sum_{k=0}^{K-1} h_k (\mathbf{\Lambda}_s\otimes\mathbf{\Lambda}_t)^k = \sum_{k=0}^{K-1} h_k (\mathbf{\Lambda}_s^k\otimes\mathbf{\Lambda}_t^k).
$
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 flexibility of separable graph filters means that one can design different filters ($\mathbf{h}$ and $\mathbf{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 a clear relationship that one is a subset of the other. Consider a joint graph filter designed on a strong product graph with length $K=3$. The filter kernel is defined as $\mathbf{H}(\mathbf{\Lambda}_s\otimes \mathbf{\Lambda}_t+\mathbf{\Lambda}_s\otimes \mathbf{I}_T+\mathbf{I}_N\otimes \mathbf{\Lambda}_t)=\sum_{k=0}^2 h_k(\mathbf{\Lambda}_s\otimes \mathbf{\Lambda}_t+\mathbf{\Lambda}_s\otimes \mathbf{I}_T+\mathbf{I}_N\otimes \mathbf{\Lambda}_t)^k$. Similarly, the kernel of a separable graph filter with $P=Q=3$ can be written as $\mathbf{H}(\mathbf{\Lambda}_s)\otimes \mathbf{G}(\mathbf{\Lambda}_t)=(\sum_{p=0}^2 h_p \mathbf{\Lambda}_s^p)\otimes (\sum_{q=0}^2 g_q \mathbf{\Lambda}_t^q)$. By expanding the expression and rearranging the coefficients, one can obtain the coefficient matrices for the joint graph filter and the separable graph filter, $C_1$ and $C_2$, respectively; that is,
\begin{align*}
    C_1=\begin{bmatrix}
        h_0 & h_1 & h_2 \\
        h_1 & h_1+2h_2 & 2h_2 \\
        h_2 & 2h_2 & h_2
    \end{bmatrix},\quad C_2=\begin{bmatrix}
            h_0g_0 & h_0g_1 & h_0g_2 \\
            h_1g_0 & h_1g_1 & h_1g_2 \\
            h_2g_0 & h_2g_1 & h_2g_2
        \end{bmatrix} = \begin{bmatrix}
        h_0 \\
        h_1 \\
        h_2
        \end{bmatrix} \begin{bmatrix}
        g_0 & g_1 & g_2
        \end{bmatrix},
\end{align*}
where $(i,j)$-th element means the coefficient of term $\mathbf{\Lambda}_s^{i-1}\otimes \mathbf{\Lambda}_t^{j-1}$.

On one hand, it is obvious that $C_2$ is always a rank 1 matrix, while $C_1$ could have rank 1, 2, or 3. So $C_1$ is not a special case of $C_2$. On the other hand, $C_1$ is always a symmetric matrix, but $C_2$ can be either symmetric or non-symmetric, depending on the choices of $\mathbf{h}$ and $\mathbf{g}$. So $C_2$ is also not a special case of $C_1$. 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 (\ref{eq:separable_filter}), instead of one large matrix-vector multiplication (\ref{eq:fre_filter}), reducing the computational cost from $O(N^2T^2)$ to $O(NT(N+T))$. 

In short, the joint and separable graph filters are 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~\ref{sec:results}.  Note that this separable design coincides with the basic module widely used in spatio-temporal graph convolutional networks~\cite{LiCCZW0:19}, which consists of one graph convolution layer followed by one temporal convolution layer.  

\vspace{-1mm}
\subsection{Spatio-temporal graph wavelets}
\vspace{-1mm}
In time-series analysis and image processing, wavelets are 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~\citep{akansu2001multiresolution}. Inspired by this, we propose spatio-temporal graph wavelets, which include a series of mathematically designed graph filters to 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.

\textbf{Separable graph wavelets.}
Based on separable spatio-temporal graph filtering (\ref{eq:separable_filter}), we are able to design spatial graph wavelets, $\{\mathbf{H}_{j_1}(\mathbf{S}_s)=\sum_{p=0}^{P-1} h^{(j_1)}_p\mathbf{S}_s^p \}_{j_1=1}^{J_s}$,  and temporal graph wavelets, $\{\mathbf{G}_{j_2}(\mathbf{S}_t)=\sum_{q=0}^{Q-1} g^{(j_2)}_q \mathbf{S}_t^q \}_{j_2=1}^{J_t}$, separately. For each modality, the filter at scale $j$ is defined as $\mathbf{H}_j(\mathbf{S}) = \mathbf{S}^{2^{j-1}} - \mathbf{S}^{2^{j}} = \mathbf{S}^{2^{j-1}}(\mathbf{I} - \mathbf{S}^{2^{j-1}})$. There are also many other off-the-shelf graph wavelets we can choose from. More discussion about wavelets and their properties can be found in Appendix~\ref{app:wavelet_formulation}. 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_s$ and $J_t$ scales for spatial and temporal domains, respectively, the overall number of scales for spatio-temporal wavelets is then $J=J_s\times J_t$.
 
\textbf{Joint graph wavelets.} 
When the joint filtering (\ref{eq:fre_filter}) is chosen, we can directly apply existing graph wavelet designs, such as the spectral graph wavelet transform~\citep{hammond2011wavelets}.


\vspace{-1mm}
\subsection{Spatio-temporal graph scattering transform} 
\vspace{-1mm}
The proposed ST-GST is a nonlinear version of spatio-temporal 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 $\sigma(\cdot)$, and (iii) a low-pass pooling operator $U$. These operations are performed sequentially to extract representative features from input spatio-temporal graph signal $\mathbf{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. 

\textbf{Separable ST-GST.}
Let $\mathbf{Z} \in \mathbb{R}^{N \times T}$ be a spatio-temporal graph signal. At each scattering layer, we sequentially use   spatial graph wavelets $\{\mathbf{H}_{j_1}\}_{j_1=1}^{J_s}$ and temporal wavelets $\{\mathbf{G}_{j_2}\}_{j_2=1}^{J_t}$ to convolve with $\mathbf{Z}$.
Since each graph filter generates a new spatio-temporal graph signal, separable spatio-temporal graph filtering generates $J=J_s\times J_t$ spatio-temporal graph signals. Then, the nonlinear activation is applied for each spatio-temporal graph signal. For example, the $(j_1, j_2)$-th signal is $\mathbf{Z}_{(j_1, j_2)} = \sigma(\mathbf{H}_{j_1}(\mathbf{S}_s)\mathbf{Z} \mathbf{G}^\top_{j_2}(\mathbf{S}_t))$. We can treat each filtered spatio-temporal graph signal as one tree node. Given $\mathbf{Z}$ as the parent node, a scattering layer produces $J$ children nodes.

To construct ST-GST, we first initialize the input data $\mathbf{Z}_0=\mathbf{X}$ be the root of the scattering tree; and then, we recursively apply scattering layers at each node to produce children nodes, growing a scattering tree; see Fig.~\ref{fig:ST-GST-scattering-tree}. We can index all the nodes in this scattering tree by a unique path from the root to each node. For example, $p^{(\ell)}=((j_1^{(1)}, j_2^{(1)}),\dots,(j_1^{(\ell)}, j_2^{(\ell)}))$ is the path from root to one tree node in the $\ell$-th layer, and the signal associated with it is $\mathbf{Z}_{(p^{(\ell)})}$. Data matrix $\mathbf{Z}_{(p^{(\ell)})}$ is then summarized by an pooling operator $U(\cdot)$ to obtain a lower-dimensional vector $\bm{\phi}_{(p^{(\ell)})}=U\left(\mathbf{Z}_{(p^{(\ell)})}\right)$. Various pooling methods can lead to different dimensions of scattering features. Common choices for $U(\cdot)$ include average in the spatial domain ($\mathbf{U} =\frac{1}{N}\mathbf{1}_{1\times N}, \bm{\phi}=\mathbf{U}\mathbf{Z}\in\mathbb{R}^{T}$), average in the temporal domain ($\mathbf{U} =\frac{1}{T}\mathbf{1}_{T\times 1}, \bm{\phi}=\mathbf{Z}\mathbf{U}\in\mathbb{R}^{N}$) and average in both modalities ($\mathbf{U}=\frac{1}{NT}\mathbf{1}_{N\times T}, \bm{\phi}=\mathbf{U}\circ\mathbf{Z}\in\mathbb{R}$), where $\circ$ represent Hadamard product. Finally, all scattering features $\bm{\phi}_{(p^{(\ell)})}$ are concatenated to construct a scattering feature map
$
    \Phi(\mathbf{S}_s, \mathbf{S}_t, \mathbf{X}):=\{\{\bm{\phi}_{\left(p^{(\ell)}\right)}\}_{\text{all }p^{(\ell)}}\}_{\ell=0}^{L-1},
$

\begin{figure}[h]
\begin{center}
\vspace{-3mm}
\includegraphics[width=0.85\textwidth]{figs/ST_GST_tree_with_signal_v4.png}
\end{center}
\caption{Scattering tree of separable ST-GST with $L=3,J_s=J_t=2$.}
\vspace{-3mm}
\label{fig:ST-GST-scattering-tree}
\end{figure}

\textbf{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~(\cite{gama2019stability}). 

\textbf{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 to cover multiple frequency bands. Furthermore, predefined filter coefficients conform a frame (\ref{eq:frame_bound}) in  each layer of ST-GST, 
which is crucial for establishing the stability of ST-GST as shown in next section.






\vspace{-2mm}
\section{Theoretical Analysis}
\label{sec:theory}
\vspace{-2mm}
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 in this section are explained thoroughly in Appendix~\ref{sec:app_proof}. Unless specified, $\|\mathbf{x}\|$ is the $\ell_2$ norm for vector $\mathbf{x}$, while $\|\mathbf{X}\|$ and $\|\mathbf{X}\|_2$ are the Frobenius and spectral norm for matrix $\mathbf{X}$, respectively.

Here we show the results for separable spatio-temporal graph scattering transform. But all the results can be extended to the joint version. Before introducing perturbations, we first show that separable spatio-temporal graph wavelets also satisfy certain frame bounds. Thus, with a separable construction, we can control bound constants for spatio-temporal wavelet and build tight frames.

\begin{myLem}
\label{lemma:sep_wavelet_frame}
Let $\{\mathbf{H}_{j_1}\}_{j_1=1}^{J_s}$  and $\{\mathbf{G}_{j_2}\}_{j_2=1}^{J_t}$ be the wavelet filter bank for spatial domain and for temporal domain, respectively. Both satisfy frame properties such that for any $\mathbf{x}\in\mathbb{R}^N$ and $\mathbf{y}\in\mathbb{R}^T$,
\begin{align}
    A_1^{2}\|\mathbf{x}\|^{2} \leq \sum_{j_1=1}^{J_s}\left\|\mathbf{H}_{j_1}(\mathbf{S}_s)\mathbf{x}\right\|^{2} \leq B_1^{2}\|\mathbf{x}\|^{2}, 
    \quad A_2^{2}\|\mathbf{y}\|^{2} \leq \sum_{j_2=1}^{J_t}\left\|\mathbf{G}_{j_2}(\mathbf{S}_t)\mathbf{y}\right\|^{2} \leq B_2^{2}\|\mathbf{y}\|^{2},
\label{eq:frame_bound}
\end{align}
Then, for any $\mathbf{Z}\in\mathbb{R}^{N\times T}$ and its corresponding reshaped vector $\mathbf{z}\in\mathbb{R}^{NT}$, it holds that
\begin{align*}
    A_1^{2}A_2^2\|\mathbf{Z}\|^{2}
    \leq \sum_{j_1,j_2 =1}^{J_s, J_t}\left\|(\mathbf{H}_{j_1}(\mathbf{S}_s) \otimes \mathbf{G}_{j_2}(\mathbf{S}_t))\mathbf{z}\right\|^{2} = \sum_{j_1,j_2 =1}^{J_s, J_t}\left\|\mathbf{H}_{j_1}(\mathbf{S}_s) \mathbf{Z} \mathbf{G}_{j_2}^\top(\mathbf{S}_t)\right\|^{2}
    \leq B_1^{2}B_2^2\|\mathbf{Z}\|^{2}.
\end{align*}
\end{myLem}
\vspace{-1mm}
Lemma~\ref{lemma:sep_wavelet_frame} guarantees that separable design can also lead to valid wavelets. Furthermore, when we choose both spatial $\{\mathbf{H}_{j_1}\}_{j_1=1}^{J_s}$ and temporal $\{\mathbf{G}_{j_2}\}_{j_2=1}^{J_t}$ to be tight frames with $A_1=B_1=A_2=B_2=1$~\citep{shuman2015spectrum}, the resulting separable wavelet also conforms a tight frame. In later context, denote $B=B_1\times B_2$ as the frame bound constant for separable spatio-temporal graph wavelet, and separable ST-GST is configured with $L$ layers and $J=J_s\times J_t$ scales at each layer.

\vspace{-1mm}
\subsection{Stability to perturbation of spatio-temporal graph signals} 
\vspace{-1mm}
Consider the perturbed spatio-temporal graph signal
$\widetilde{\X} = \mathbf{X} + \bm{\Delta} \in\mathbb{R}^{N\times T}$, 
where $\bm{\Delta}\in\mathbb{R}^{N\times T}$ is the perturbation matrix. Such an additive model can represent measurement noise caused by devices or adversarial perturbations added manually. Theorem~\ref{thm:ST-GST-stability-signal} shows that the feature map for perturbed signal will not deviate much from original feature map under small input perturbations.
\begin{myThm}
\label{thm:ST-GST-stability-signal}
 	Consider the additive noise model for input data $\mathbf{X}$, it then holds that
 	\begin{align}
 	\vspace{-1mm}
 		\frac{\|{\Phi}({\mathbf{S}_s, \mathbf{S}_t, \mathbf{X}})-{\Phi}(\mathbf{S}_s, \mathbf{S}_t, {{\widetilde{\X}}})\|}{\sqrt{T\sum_{\ell=0}^{L-1} J^\ell}} 
 		\leq \frac{1}{\sqrt{NT}}
 		\sqrt{\frac{\sum_{\ell=0}^{L-1}B^{2\ell}}{\sum_{\ell=0}^{L-1} J^{\ell}}}\|{\bm{\Delta}}\|.
 		\label{eq:signal_pert_bound}
 		\vspace{-2mm}
 	\end{align}
\end{myThm}
\vspace{-1mm}
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 temporal wavelets are both tight frames, then the normalized bound presented in~(\ref{eq:signal_pert_bound}) indicates that the transform is insensitive to perturbations on input signals as the factor is much smaller than 1.

\vspace{-1mm}
\subsection{Stability to perturbation of spatio-temporal graph structures}
\vspace{-1mm}
Perturbations on the underlying graph usually happen when the graph is unknown or when the graph changes over time~\citep{segarra2017network}. Since such kind of perturbations usually happen in spatial domain, here we simply consider the structure perturbations on the spatial graph only. Specifically, we consider the perturbed spatial graph $\widehat{\S}_s = \mathbf{S}_s+\mathbb{E}^{\top}\mathbf{S}_s+\mathbf{S}_s\mathbb{E}$, where $\mathbb{E}$ is the perturbation matrix and temporal graph $\mathbf{S}_t$ is not changed. Detailed descriptions see Appendix~\ref{sec:app_proof}. 

\begin{myThm}
\label{thm:ST-GST-structure-stability}
    Suppose eigenvalues $\{m_i\}_{i=1}^N$ of $\mathbb{E}\in\mathbb{R}^{N\times N}$ are organized in order such that $|m_1|\leq|m_2|\leq\cdots \leq|m_N|$, satisfying $|m_N|\leq\epsilon/2$ and $|m_i/m_N-1|\leq \epsilon$ for $\epsilon > 0$ and all $i$'s. Suppose spatial filter bank $\{\mathbf{H}_{j_1}\}_{j_1=1}^{J_s}$ satisfies $\max_i|\lambda h_i'(\lambda)|\leq C$ and temporal filter bank $\{\mathbf{G}_{j_2}\}_{j_2=1}^{J_t}$ satisfies limited spectral response $\max_i|g_i(\lambda)|\leq D$. It then holds that 
     \begin{align}
     \vspace{-3mm}
         \frac{\|\Phi(\mathbf{S}_s, \mathbf{S}_t, \mathbf{X}) - \Phi(\widehat{\S}_s, \mathbf{S}_t, \mathbf{X})\|}{\sqrt{T\sum_{\ell=0}^{L-1}J^\ell}} \leq \frac{\epsilon C D}{B\sqrt{NT}}\sqrt{\frac{\sum_{\ell=0}^{L-1}\ell^2(B^2J)^\ell}{\sum_{\ell=0}^{L-1}J^\ell}}\|\mathbf{X}\|,
     \vspace{-3mm}
     \end{align}
\end{myThm}
\vspace{-1mm}
where $\epsilon$ characterizes the perturbation level. Theorem~\ref{thm:ST-GST-structure-stability} shows that ST-GST is a stable transform also for structure deformation, as the norm of change of feature map is linear in $\epsilon$. It is worth pointing out that the upper bound in both Theorems~\ref{thm:ST-GST-stability-signal} and~\ref{thm:ST-GST-structure-stability} only depend on the choice of filter banks and structure of scattering tree, instead of quantities related with specific graph support $\mathbf{S}_s$ and $\mathbf{S}_t$ that are shown in previous works~\citep{gama2019stability,zou2020graph, levie2019transferability}.

\vspace{-3mm}
\section{Experimental Results}
\label{sec:results}
\vspace{-2mm}


\begin{figure}
\begin{floatrow}
\hspace{-0cm}
\capbtabbox{%
\centering 
\resizebox{0.5\textwidth}{!}{
\small{
\begin{tabular}{ccc}
\hline
& \textbf{Method} & \textbf{Accuracy (\%)} \\ 
\cmidrule{2-3}
\multirow{2}{*}{\rotatebox{90}{}}
&    GFT+TPM & 74.0 \\ 
&    HDM & 81.8 \\ 
\cmidrule{2-3}
\multirow{3}{*}{\rotatebox{90}{GNNs}}
&    Temporal Conv. & 72.1 \\ 
&    ST-GCN (fixed topology) & 52.0 \\
&    MS-G3D (learnable topology) & 82.2 \\
\cmidrule{2-3}
\multirow{5}{*}{\rotatebox{90}{Scattering}}
&    Separable ST-GST (5, 10, 3) & 81.4 \\
&    Separable ST-GST (5, 20, 3) & \textbf{87.0} \\ 
&    Joint Kronecker ST-GST (15, 3)& 61.0 \\
&    Joint Cartesian ST-GST (15, 3)& 59.1 \\
&    Joint Strong ST-GST (15, 3)& 61.7\\ \hline
\end{tabular}
}}
}{%
\caption{Classification accuracy (MSR Action3D with $288$ training and $269$ testing samples).}\label{tab:MSR_results}
}
\capbtabbox{%
\centering 
\resizebox{0.5\textwidth}{!}{
\small{
\begin{tabular}{ccc}
\hline
& \textbf{Method} & \textbf{Accuracy (\%)} \\ 
\cmidrule{2-3}
\multirow{5}{*}{\rotatebox{90}{GNNs}}
&   Deep LSTM & 60.7 \\
&    PA-LSTM & 62.9 \\
&    ST-LSTM+TG & 69.2 \\
&    Temporal Conv. & 74.3 \\ 
 &   ST-GCN (fixed topology) & \textbf{75.8} \\ 
\cmidrule{2-3}
\multirow{5}{*}{\rotatebox{90}{Scattering}} &    Separable ST-GST (5, 20, 2) & 68.7 \\
&    Separable ST-GST (5, 20, 3) & 73.1 \\
&    Joint Kronecker ST-GST (15, 3)& 55.7 \\
&    Joint Cartesian ST-GST (15, 3)& 56.2 \\
&    Joint Strong ST-GST (15, 3)& 57.1\\ \hline
\end{tabular}
}}
}{%
\caption{Classification accuracy (NTU-RGB+D with $40,320$ training and $16,560$ testing samples).}\label{tab:NTU_results}
}
\end{floatrow}
\vspace{-2mm}
\end{figure}
\begin{figure*}[!t]
  \vspace{-3pt}
  \begin{center}
    \begin{tabular}{ccc}
\includegraphics[width=0.28\textwidth]{figs/sparse_labeling.png} 
   & 
\includegraphics[width=0.28\textwidth]{figs/time_vs_acc_v2.png}
   &
\includegraphics[width=0.28\textwidth]{figs/nonlinear.png}
       \\
    {\small (a) Limited training data.}
   &
    {\small (b) Performance vs. time.}
    &
    {\small (c) Nonlinear vs. linear.}
  \end{tabular}
\end{center}
\vspace{-3mm}
\caption{\small Performance comparisons with various settings about training ratio, time and nonlinearity.}
\label{fig:architecture_comparison}
\end{figure*}

We now evaluate the performance of proposed ST-GST in skeleton-based action recognition task. 


\mypar{Experimental setup} 
The number of layers, $L$, the number of spatial wavelet scales, $J_s$, and the number of temporal wavelet scales, $J_t$, are represented by $(J_s, J_t, 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, see Fig.~\ref{fig:product_graph}(a)(b). Geometric scattering wavelets are used in both domain, and the nonlinear activation $\sigma(\cdot)$ is absolute value function which has the property of energy-preserving. Features output by ST-GST are then utilized by random forest classifier with 300 decision trees for classification.

\mypar{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 facilitated by temporal pyramid matching (GFT+TPM)~\citep{kao2019graph}, Bayesian hierarchical dynamic model (HDM)~\citep{zhao2019bayesian}, and a few deep learning approaches, including temporal convolution neural networks~\citep{kim2017interpretable}, ST-GCN~\citep{yan2018spatial}, and MS-G3D~\citep{liu2020disentangling}. For NTU-RGB+D, Deep LSTM~\citep{Liu_2019_NTURGBD120}, part-aware LSTM (PA-LSTM)~\citep{Liu_2019_NTURGBD120} and spatio-temporal LSTM with trust gates (ST-LSTM+TG)~\citep{liu2016spatio} 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~\ref{tab:MSR_results} and~\ref{tab:NTU_results} compares the classification accuracies on MSR Action3D and NTU-RGB+D, respectively. We see that even without any training, the performance of ST-GST is better than other non-deep-learning and LSTM-based methods, and is comparable with state-of-the-art GCN-based methods in large-scale dataset. Further, ST-GST outperforms all other methods when the size of training set is small. Fig.~\ref{fig:architecture_comparison}(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.~\ref{fig:architecture_comparison}(b) shows the accuracy-running time plot, reflecting that ST-GST is much faster than ST-GCN with similar classification performance.

\mypar{ST-GST works well in small-scale-data regime} Table~\ref{tab:MSR_results} and Fig.~\ref{fig:architecture_comparison}(a) show that ST-GST outperforms other deep learning methods in the small-scale-data regime, which can be explained as follows. The good performance of spatio-temporal graph neural networks highly relies on the assumption 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 classification accuracy. But in practice, obtaining a huge amount of training data with high-quality labels could be extremely expensive. On the other hand, since ST-GST is a 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.

\mypar{Separable design is better than joint design} Tables~\ref{tab:MSR_results} and~\ref{tab:NTU_results} 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 is consistent with our analysis in Section~\ref{sec:st_graph_filtering}. 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 can be diffused in spatio-temporal graphs and thus limit the efficiency of feature extraction.

\mypar{Nonlinearity is beneficial} Fig.~\ref{fig:architecture_comparison}(c) compares ST-GST with and without nonlinearity and shows that it is critical to ST-GST, also reflecting the potential effect of nonlinearity in ST-GCNs.

\vspace{-2mm}
\section{Conclusions}
\vspace{-2mm}
In this work we propose a novel spatio-temporal graph scattering transform (ST-GST), which can be viewed as one forward pass of 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. 

\vspace{-2mm}
\section{Acknowledgement}
\vspace{-2mm}
This work is fully supported by 
Mitsubishi Electric Research Laboratories (MERL), where Chao Pan was a research intern, Siheng Chen was a research scientist and Antonio Ortega is a consultant.


