text:
\section{Floats}

\input{sections/abstract}

\maketitle

\input{sections/introduction}
\input{sections/related_works}
\input{sections/preliminaries}
\input{sections/equivalences}
\input{sections/approximation}
\input{sections/conclusion}
\input{sections/acknowledgements}
\bibliographystyle{elsarticle-num}

\section*{Acknowledgments}
This work was partially supported by the Ministry of Education and Research Germany (BMBF, grant number 01IS20047A) and partially by INdAM GNCS group.
We want to acknowledge Monica Bianchini and Maria Lucia Sampoli for their proofreading contribution and fruitful discussions.

\section{Appendix}\label{section_appendix}

\subsection{Proof of Prop.~\ref{f_unfold}}\label{apx:prop_functions_of_attr_unf_trees}
A function $f$ belongs to $\mathcal{F}(\mathcal{G})$ if and only if there exists a function $\kappa$ defined on trees such that for any graph $\bm{G}\in\mathcal{G}$ it holds $f(\mathbf{G},v)= \kappa(\mathbf{T}_v)$, for any node $v \in \bm{G}$.
\begin{proof} We proof by showing both equivalence directions:
\begin{compactenum}
    \item[$\Leftarrow$] If there exists a function $\kappa$ on attributed unfolding trees such that $f(\bm{G},v) =\kappa (\bm{T}_v)$ for all $v\in G$, then $u\sim_{AUT}v$ for $u,v\in G$ implies

        $f(\bm{G},u) =\kappa (\bm{T}_u) = \kappa (\bm{T}_v) = f(\bm{G},v)$.

    \item[$\Rightarrow$] If $f$ preserves the attributed unfolding equivalence, then a function $\kappa$ on the attributed unfolding tree of an arbitrary node $v$ can be defined as $\kappa(\bm{T}_v):= f(\bm{G}, v)$. Then, if $\bm{T}_u$ and $\bm{T}_v$ are two attributed unfolding trees, $\bm{T}_u=\bm{T}_v$ implies $f(\bm{G},u) = f(\bm{G},v)$ and $\kappa$ is uniquely defined.
\end{compactenum}
\end{proof}

\subsection{Proof of Lem.~\ref{ue=equal_trees}}\label{apx_proof_of_ue=equal_trees}
Let $G_1,G_2$ belong to the domain of bounded SAUHGs. Then
\begin{equation*}
    {\forall\, u\in \mathcal{V}_1, \forall\, v \in \mathcal{V}_2 : u \sim_{AUT} v \Longleftrightarrow \bm{T}^{r+1}_u = \bm{T}^{r+1}_v},
\end{equation*}
with $r = \max(\text{diam}(G_1), {diam}(G_2))$.
\begin{proof}
The proof is completely analogous to the original proof in \cite{d2021unifying}:
\begin{compactenum}
    \item[$\Rightarrow$:] By definition, $u \sim_{AUT} v \Longleftrightarrow \bm{T}_v = \bm{T}_u$, which implies
    $\bm{T}^k_u = \bm{T}^k_v$ for all $k$ and, in particular, also for $k = r + 1$.
    \item[$\Leftarrow$:] We prove by reductio ad absurdum that

    $\bm{T}^k_v = \bm{T}^k_u \Rightarrow \bm{T}^{k+1}_v = \bm{T}^{k+1}_u \quad \forall\, k \geq r + 1.$

    In fact, let us assume that $\exists \; k \geq r + 1$ such that $\bm{T}^k_v = \bm{T}^k_u$ but
$\bm{T}^{k+1}_v \neq \bm{T}^{k+1}_u$. This means that there would be a node $\mu \in \bm{T}^{k+1}_v$
and a node $\nu \in \bm{T}^{k+1}_u$ such that $\mu = \nu$ and $\bm{T}^1_{\mu} \neq \bm{T}^1_{\nu}$, which is
impossible, because in $\bm{T}^k_v$ and $\bm{T}^k_u$ all nodes have already been explored
(since $k \geq r + 1$). Moreover, some $i$, with $i \leq r$, exists such that, at
depth $i$, an equality holds between subtrees of depth 1 so as $\bm{T}^1_{\mu} = \bm{T}^1_{\nu}$.
Therefore, $\nexists \; k \geq r+ 1$ such that $\bm{T}^k_v = \bm{T}^k_u$ but $\bm{T}^{k+1}_v \neq \bm{T}^{k+1}_u$ , which
proves the theorem.
\end{compactenum}
\end{proof}

\subsection{Proof of Lem.~\ref{equal_trees=WL_coloring}}\label{proof_of_equal_trees=WL_coloring}

Consider ${G' = (\mathcal{V}', \mathcal{E}' , \alpha', \omega')}$ as the SAUHG resulting from a transformation of an arbitrary static graph $G = (\mathcal{V}, \mathcal{E} , \alpha, \omega)$ with nodes $u, v \in \mathcal{V}$ and corresponding attributes $\alpha_u, \alpha_v$. Then it holds
\begin{align}\label{eq4}
    \forall \; d \in \mathbb{N} : \bm{T}^{d}_u = \bm{T}^{d}_v \Longleftrightarrow c_u^{(d)} = c_v^{(d)}
\end{align}

\begin{proof}
The proof is carried out by induction on $d$, which represents both the
depth of the unfolding trees and the iteration step in the WL colouring.
\begin{compactenum}
    \item[$(d = 0)$:] It holds
    \begin{equation*}
         \quad \bm{T}^0_u = Tree(\alpha_u) = Tree(\alpha_v) = \bm{T}^0_v \;
    \end{equation*}
    \begin{equation*}
        \Longleftrightarrow \; \alpha_u = \alpha_v \text{ and } c^{(0)}_u = \text{HASH}(\alpha_u) = \text{HASH}(\alpha_v) = c^{(0)}_v.
    \end{equation*}
    \item[$(d > 0)$:] Suppose that Eq.~\eqref{eq4} holds for $d-1$, and prove that it holds also for $d$.
\begin{compactenum}
    \item[-] By definition,  $\bm{T}^d_u = \bm{T}^d_v$ is equivalent to
        \begin{equation}
            \begin{cases}
            \bm{T}^{d-1}_u = \bm{T}^{d-1}_v \quad
               \text{and} \\
           {\small\text{Tree}\bigl(\alpha_u, \Omega_{ ne_u}, \bm{T}^{d-1}_{ne_u}\bigr)  = \text{Tree}\bigl(\alpha_v, \Omega_{ ne_v}, \bm{T}^{d-1}_{ne_v}\bigr)}.
           \end{cases}
           \end{equation}\label{eq6}
    \item[-] Applying the induction hypothesis, it holds that
        \begin{equation}\label{eq7}
            \bm{T}^{d-1}_u = \bm{T}^{d-1}_v \Longleftrightarrow c^{(d-1)}_u = c^{(d-1)}_v.
        \end{equation}
    \item[-] Eq.~\eqref{eq6} is equivalent to the following:
        \begin{equation*}
            \alpha_u = \alpha_v, \quad \Omega_{ ne_u} = \Omega_{ ne_v}  \quad \textbf{and} \quad \bm{T}^{d-1}_{ne_u} = \bm{T}^{d-1}_{ne_v}.
        \end{equation*}
        Which is equivalent to the existence of an ordering on $ne_u$ and $ne_v$ s.t.
        \begin{equation}
        \begin{cases}
             \omega_{\{u, ne_{u_{i}}\}} = \omega_{\{v, ne_{v_{i}}\}} \; \forall \; i = 1,...,|ne_u|\; \text{ and } \\ \bm{T}^{d-1}_{ne_{u_{i}}} = \bm{T}^{d-1}_{ne_{v_{i}}} \; \forall \; i = 1,...,|ne_{u}|. \label{eq89}
             \end{cases}
        \end{equation}
    \item[-] Hence, Eq.~\eqref{eq89} hold iff an ordering on $ne_u$ and $ne_v$ exists s.t.
        \begin{equation*}
            c^{d-1}_{ne_{u_{i}}} = c^{d-1}_{ne_{v_{i}}} \quad  \forall \; i = 1,...,|ne_u|
            \end{equation*}
            \begin{equation*}\text{, \; i.e.,} \quad
            \sms{c^{(d-1)}_m \mid m \in ne_u} = \sms{c^{(d-1)}_n \mid n \in ne_v}.
        \end{equation*}
    \item[-] Putting together Eq.~\eqref{eq7}, \eqref{eq89}, and the fact that the HASH function is bijective, we obtain:
        \begin{equation*}
            \quad  \text{HASH}\Bigl(\bigl(c^{(d-1)}_u, \Omega_{ ne_u}, \sms{c^{(d-1)}_m \mid m \in ne_u}\bigr)\Bigr) =
            \end{equation*}
            \begin{equation*}
            =\text{HASH}\Bigl(\bigl(c^{(d-1)}_v, \Omega_{ ne_v}, \sms{c^{(d-1)}_n \mid n \in ne_v}\bigr)\Bigr)
        \end{equation*}
        which, by definition, is equivalent to $c^{(d)}_u = c^{(d)}_v$.
\end{compactenum}
\end{compactenum}
\end{proof}

\subsection{Proof of Prop.~\ref{f_unfold_dyn}}\label{proof_of_f_unfold}
A dynamic system \straight{dyn} belongs to $\mathcal{F}(\mathcal{D^\prime})$ if and only if there exists a function $\kappa$ defined on trees such that for all $(t,G,v)\in \mathcal{D'}$ it holds
$\text{\straight{dyn}}(t,G,v)= \kappa\Bigl(\bigl(\bm{T}_{v}(i)\bigr)_{i\in [t]}\Bigr)$.

\begin{proof} We show the proposition by proving both directions of the equivalence relation:
\begin{compactenum}
    \item[$\Rightarrow$:] If there exists $\kappa$ such that $\text{\straight{dyn}}(t,G,v) = \kappa\Bigl(\bigl(\bm{T}_{v}(i)\bigr)_{i\in [t]}\Bigr)$ for all triplets $(t,G,v)\in \mathcal{D'}$ then $u \in G', v \in G''$ with $u \sim_{DUT} v$ implies
    {\small\begin{equation*}
        \text{\straight{dyn}}(t,G',u) = \kappa\Bigl(\bigl(\bm{T}_{u}(i)\bigr)_{i\in [t]}\Bigr) = \kappa\Bigl(\bigl(\bm{T}_{v}(i)\bigr)_{i\in [t]}\Bigr) = \text{\straight{dyn}}(t,G'',v).
    \end{equation*}}
    \item[$\Leftarrow$:] On the other hand, if \text{\straight{dyn}} preserves the unfolding equivalence, then we can define $\kappa$ as
    \begin{equation*}
        \kappa\Bigl(\bigl(\bm{T}_{v}(i)\bigr)_{i\in [t]}\Bigr) = \text{\straight{dyn}}(t,G,v).
    \end{equation*}
    Note that the above equality is a correct specification for a function. In fact, if
    \begin{equation*}
        \kappa\Bigl(\bigl(\bm{T}_{v}(i)\bigr)_{i\in [t]}\Bigr) = \kappa\Bigl(\bigl(\bm{T}_{u}(i)\bigr)_{i\in [t]}\Bigr)
    \end{equation*}
    implies $\text{\straight{dyn}}(t,G,u) = \text{\straight{dyn}}(t,G,v)$, then $\kappa$ is uniquely defined.
\end{compactenum}
\end{proof}

\subsection{Proof of Thm.~\ref{thm_bijection_of_uf_trees}}\label{apx:proof_thm_bijection_of_uf_trees}
Let $G = (G_t)_{t\in I}$ be a dynamic graph and $${\textsc{makeStatic}(G) =: G' = (\mathcal{V'}, \mathcal{E'}, \alpha', \omega')}$$ the static graph after the transformation. Furthermore, let $\mathcal{V}:= \bigcup_{t\in I}\mathcal{V}_t$ be the set of all nodes appearing in the graph sequence of $G$ and $\tilde{\alpha}:\mathcal{V}\times I \rightarrow \mathcal{A}\,\! \perp$ with $\tilde{\alpha}_v(t):= (\alpha_v(t), \rho)$ be the extended attribute function for all nodes including a flag $\rho\in \{0, 1\}$ for the existence of a node at time $t$. Then for all $u,v \in \mathcal{V}$ and $d\in \mathbb{N}$ it holds
\begin{equation*}
    (\bm{T}_{u}^d(t))_{t\in I} = \left(\bm{T}_{v}^d(t)\right)_{t\in I}  \Longleftrightarrow \bm{T}_{{u}}^d = \bm{T}_{{v}}^d.
\end{equation*}
\begin{proof} We prove the statement via induction over $d$.
\begin{compactenum}
    \item[$d=0$:]
    \begin{equation*}
    \begin{array}{cc}
        & (\bm{T}_{u}^d(t))_{t\in I} = (\bm{T}_{v}^d(t))_{t\in I}   \\
          \overset{\text{Def.~\ref{def_unfolding_tree_dynamic}}}{\Longleftrightarrow} & \left(Tree(\tilde{\alpha}_{u}(t))\right)_{t\in I} = \left(Tree(\tilde{\alpha}_{v}(t))\right)_{t\in I}\\
         \overset{\text{\textsc{makeStatic} bij.}}{\Longleftrightarrow} & Tree(\alpha'_{u}) = Tree(\alpha'_{v}) \\
        \Longleftrightarrow &   \bm{T}_{{u}}^d = \bm{T}_{{v}}^d
            \end{array}
   \end{equation*}
    \item[$d>0$:]
    Assuming the induction hypothesis (IH) holds for $d-1$, show the hypothesis holds also for $d$.

\begin{equation*}
\begin{array}{cc}
    &  (\bm{T}_{u}^d(t))_{t\in I} = (\bm{T}_{v}^d(t))_{t\in I}  \\
    \overset{\text{Def.~\ref{def_unfolding_tree_dynamic}}}{\Longleftrightarrow} &
            \left(Tree\left(\tilde{\alpha}_{u}(t), \Omega_{ ne_u(t)} , \bm{T}^{d-1}_{ne_u(t)}\right)\right)_{t\in I}  = \\ &
            \left(Tree\left(\tilde{\alpha}_{v}(t), \Omega_{ ne_v(t)} , \bm{T}^{d-1}_{ne_v(t)}\right)\right)_{t\in I}  \\
    \Longleftrightarrow
    &  \tilde{\alpha}_{u}(t) = \tilde{\alpha}_{v}(t) \wedge \Omega_{ ne_u(t)} = \Omega_{ ne_v(t)} \wedge \\ & \wedge \; \bm{T}^{d-1}_{ne_u(t)} = \bm{T}^{d-1}_{ne_v(t)}  \forall \; t\in I\\
     \overset{\text{IH}}{\Longleftrightarrow} &  \alpha'_{u} = \alpha'_{v} \wedge \Omega_{ ne_u} = \Omega_{ ne_v} \wedge \bm{T}^{d-1}_{ne_u} = \bm{T}^{d-1}_{ne_v}\\
    \overset{\text{Def.~\ref{def_unfolding_tree_attributed}}}{\Longleftrightarrow} &
            Tree\bigl(\alpha'_{u}, \Omega_{ ne_u} , \bm{T}^{d-1}_{ne_u}\bigr)   =
            Tree\bigl(\alpha'_{v}, \Omega_{ ne_v} , \bm{T}^{d-1}_{ne_v}\bigr) \\
    \overset{\text{Def.~\ref{def_unfolding_tree_attributed}}}{\Longleftrightarrow} & \bm{T}_{{u}}^d = \bm{T}_{{v}}^d
\end{array}
\end{equation*}
\end{compactenum}
\end{proof}

\subsection{Proof of Thm.~\ref{thm_bijection_of_wl_tests}}\label{apx:proof_thm_bijection_of_wl_tests}
Let $G = (G_t)_{t\in I}$ be a dynamic graph and $${\textsc{makeStatic}(G) =: G' = (\mathcal{V'}, \mathcal{E'}, \alpha', \omega')}$$ the SAUHG resulting from a bijective graph type transformation.
Furthermore, let $\mathcal{V}:= \bigcup_{t\in I}\mathcal{V}_t$ be the set of all nodes appearing in the graph sequence of $G$ and $\tilde{\alpha}:\mathcal{V}\times I \rightarrow \mathcal{A}\,\times\! \perp$ with $\tilde{\alpha}_v(t):= (\alpha_v(t), \rho)$ be the extended attribute function for all nodes including a flag $\rho\in \{0, 1\}$ for the existence of a node at time $t$. Then for an iteration $i$ and $u,v\in\mathcal{V}$ it holds
\begin{equation*}
    \left(c_{u}^{(i)}(t)\right)_{t\in I} = \left(c_{v}^{(i)}(t)\right)_{t\in I} \Longleftrightarrow c_{{u}}^{(i)} = c_{{v}}^{(i)}.
\end{equation*}
\begin{proof} We prove the statement by induction over the iteration $i$.
\begin{compactenum}
    \item[$i = 0$:]
\begin{equation*}
    \begin{array}{cc}
    & \quad \left(c_{u}^{(0)}(t)\right)_{t\in I} = \left(c_{v}^{(0)}(t)\right)_{t\in I} \\
    \overset{\text{Def.~\ref{def_WL_test_dynamic}}}{\Longleftrightarrow}
    & \quad \bigl(\text{HASH}\left(\tilde{\alpha}_{u}(t)\right)\bigr)_{t\in I} = \bigl(\text{HASH}\left(\tilde{\alpha}_{v}(t)\right)\bigr)_{t\in I} \\
    \Longleftrightarrow
    & \quad \tilde{\alpha}_{u}(t) = \tilde{\alpha}_{v}(t) \quad \forall\;  t\in I \\
    \overset{\text{by constr.}}{\Longleftrightarrow}
    & \quad \alpha'_u = \alpha'_v\\
    \Longleftrightarrow
    & \quad \text{HASH}\left(\alpha'_u\right) = \text{HASH}\left(\alpha'_v\right) \\
    \Longleftrightarrow
    & \quad c_u^{(0)} = c_v^{(0)}
    \end{array}
\end{equation*}
    \item[$i > 0$:] Assume the induction hypothesis (IH) is true for $i-1$ and show the assumption is also true for $i$.
\begin{equation*}
    \begin{array}{cc}
    &  \left(c_{u}^{(i)}(t)\right)_{t\in I} = \left(c_{v}^{(i)}(t)\right)_{t\in I} \\
    \overset{\text{Def.~\ref{def_WL_test_dynamic}}}{\Longleftrightarrow}
    & \Bigl(\text{HASH}\left( c_{u}^{(i-1)}(t), \Omega_{ne_u(t)} ,c_{ne_u(t)}^{(i-1)}\right)\Bigr)_{t\in I} = \\& \Bigl(\text{HASH}\left( c_{v}^{(i-1)}(t), \Omega_{ne_v(t)} ,c_{ne_v(t)}^{(i-1)}\right)\Bigr)_{t\in I} \\
    \overset{\text{Bij. of HASH}}{\Longleftrightarrow}
    &   c_{u}^{(i-1)}(t) = c_{v}^{(i-1)}(t) \; \wedge \\ & \wedge \; \Omega_{ne_u(t)} = \Omega_{ne_v(t)} \wedge c_{ne_u(t)}^{(i-1)} = c_{ne_v(t)}^{(i-1)}\quad \forall \; t\in I \\
    \overset{\text{IH}}{\Longleftrightarrow}
    &    c_{u}^{(i-1)} = c_{v}^{(i-1)} \wedge \Omega_{ne_u} = \Omega_{ne_v} \wedge c_{ne_u}^{(i-1)} = c_{ne_v}^{(i-1)} \\
    \overset{\text{Bij. of HASH}}{\Longleftrightarrow}
    &  \text{HASH}\Bigl( \bigl( c_u^{(i-1)}, \Omega_{ ne_u}, c_{ne_u}^{(i-1)}\bigr)\Bigr) \\ & = \text{HASH}\Bigl( \bigl( c_v^{(i-1)}, \Omega_{ ne_v}, c_{ne_v}^{(i-1)}\bigr)\Bigr)\\
   \overset{\text{Def.~\ref{def_WL_test_attributed}}}{\Longleftrightarrow}
   & c_{{u}}^{(i)} = c_{{v}}^{(i)}
   \end{array}
\end{equation*}
\end{compactenum}
\end{proof}

\subsection{Sketch of the proof of Thm.~\ref{theorem_universal_approx_sauhg}}\label{apx:proof_apx_thm_attributed}
Since the proof is quite identical to the one in \cite{d2021unifying}, we will only sketch the proof idea below and refer to the original paper for further details. First, we need a preliminary lemma which is an extension of \cite[Lem.~1]{scarselli2008computational} to the domain of SAUHGs. Intuitively, this lemma suggests that a domain of SAUGH graphs $\mathcal{G}$ with continuous features can be partitioned into
small subsets so that the features of the graphs are almost constant in each partition. Moreover, a finite number of partitions is sufficient, in probability, to cover a large part of the domain.

\begin{Lem}
\label{hypercubes_att}

For any probability measure $P$ on $\mathcal{D}$, and any reals $\lambda$, $\delta$, where $0 < \lambda \leq 1$, $\delta \geq 0$, there exist a real $\Bar{b} >0$, which is independent of $\delta$, a set $\Bar{\mathcal{D}} \subseteq \mathcal{D}$, and a finite number of partitions $\Bar{\mathcal{D}_1}, \dots , \Bar{\mathcal{D}_l}$ of $\Bar{\mathcal{D}}$, where $\Bar{\mathcal{D}} = \mathcal{G}_i \times \{ v_i \}$, with $\mathcal{G}_i \subseteq \mathcal{G}$ and $v_i \in \mathcal{G}_i$, such that:
\begin{compactenum}
    \item $P(\Bar{\mathcal{D}}) \geq 1- \lambda $ holds;
    \item for each $i$, all the graphs in $\mathcal{G}_i$ have the same structure, i.e., they differ only for the values of their labels;
    \item for each set $\Bar{\mathcal{D}_i}$, there exists a hypercube $\mathcal{H}_i \in \mathbb{R}^a$ such that $\ell_{\mathbf{G}} \in \mathcal{H}_i$ holds for any graph $\mathbf{G} \in \mathcal{G}_i$, where $\ell_{\mathbf{G}}$ denotes the vector obtained by stacking all the feature vectors of both nodes and edges of $\mathbf{G}$, namely $\ell_{\mathbf{G}} = \ell^n_{\mathbf{G}} | \ell^e_{\mathbf{G}}$ where $\ell^n_{\mathbf{G}}$ is the stacking of all the feature vectors of nodes and $\ell^e_{\mathbf{G}}$ is the stacking of all the feature vectors of edges ;
    \item for any two different sets $\mathcal{G}_i$, $\mathcal{G}_j$, $i \neq j$, their graphs have different structures or their hypercubes $\mathcal{H}_i$, $\mathcal{H}_j$ have a null intersection, i.e. $\mathcal{H}_i \bigcap \mathcal{H}_j = \emptyset$;
    \item for each $i$ and each pair of graphs $\mathbf{G}_1$, $\mathbf{G}_2 \in \mathcal{G}_i$, the inequality $\| \ell_{\mathbf{G}_1} - \ell_{\mathbf{G}_2} \|_{\infty} \leq \delta$ holds;
    \item for each graph $\mathbf{G} \in \Bar{\mathcal{D}}$, the inequality $\| \ell_{\mathbf{G}}\|_{\infty} \leq \Bar{b}$ holds.
\end{compactenum}
\end{Lem}

\begin{proof}
The proof is quite identical to the one contained in \cite{scarselli2008computational}. The only remark needed here is that we can consider the whole stacking of all features from both nodes and edges without loss of generality; indeed, if we were considering separately the node features and the edge features, we would need conditions on the hypercubes s.t.:
\begin{equation*}
\begin{split}
   & \quad  \| \ell^n_{\mathbf{G}_1} - \ell^n_{\mathbf{G}_2} \|_{\infty} \leq \delta^n, \; \delta^n>0, \\ \text{ and }  &\quad
     \| \ell^e_{\mathbf{G}_1} - \ell^e_{\mathbf{G}_2} \|_{\infty} \leq \delta^e, \; \delta^e>0
\end{split}
\end{equation*}
then we can stack those feature vectors, as in the statement, s.t. :
\begin{equation*}
\begin{split}
    \| \ell_{\mathbf{G}_1} - \ell_{\mathbf{G}_2} \|_{\infty} &= \| [\ell^n_{\mathbf{G_1}} | 0 ] + [ 0 | \ell^e_{\mathbf{G_1}}] - \bigl[[\ell^n_{\mathbf{G_2}} | 0 ] + [ 0 | \ell^e_{\mathbf{G_2}}] ] \|_{\infty}
    \\
    & \leq \| \ell^n_{\mathbf{G_1}} - \ell^n_{\mathbf{G_2}} \|_{\infty} + \| \ell^e_{\mathbf{G_1}} -  \ell^e_{\mathbf{G_2}} \|_{\infty} \\ & \leq \delta^n + \delta^e := \delta
\end{split}
\end{equation*}
which allow us to exploit the same proof contained in \cite{scarselli2008computational}.
\end{proof}

By adopting an argument similar to that in \cite{scarselli2008computational}, it is proved that Thm.~\ref{theorem_universal_approx_sauhg} is equivalent to the following, where the domain contains a finite number of graphs and the features are integers.

\begin{Thm} \label{attributed reduct}
For any finite set of patterns $\{ ( \mathbf{G}_i , v_i) |\  \mathbf{G}_i \in \mathcal{G}, v_i \in \mathit{N}, 1 \leq i \leq n \}$, with $ r= \max\limits_{\mathbf{G}_i} \text{diam}(\mathbf{G}_i)$ and with graphs having integer nodes features,
for any function which preserves the attributed unfolding equivalence, and for any real $\varepsilon >0$, there exist continuously differentiable functions  $\text{AGGREGATE}^{(k)}$, $\text{COMBINE}^{(k)}$, $\forall \; k \leq r+1$, s.t.
{\scriptsize\begin{equation*}
    \bm{h}_v^k = \text{COMBINE}^{(k)}\left( \bm{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)}\left(\{ h_u^{k-1}\}_{ u \in ne_v}, \{\omega_{\{u,v\}}\}_{ u \in ne_v}  \right)\right)
\end{equation*}}

and a function
$\text{READOUT}$, with feature dimension $m=1$, i.e, $\mathbf{h}_v^k\in\mathbb{R}$, so that the function
$ \varphi$  (realized by the SGNN), computed after $r+1$ steps,
satisfies the condition
\begin{equation}
|\tau (\mathbf{G}_i, v_i) - \varphi(\mathbf{G}_i, v_i)| \leq \varepsilon \quad \text{ for any } i, 1 \leq i \leq n.
\end{equation}
\end{Thm}

\begin{proof}[Sketch of the proof]
The idea of the proof is that of designing a GNN that is able to approximate any function $\tau$ that preserves the attributed unfolding equivalence. According to Thm.~\ref{f_unfold} there exists a function $\kappa$ s.t. $\tau(\mathbf{G},v) = \kappa (T_v)$.
Therefore, the GNN has to encode the attributed unfolding tree into the node features, i.e., for each node $v$, we want to have $\mathbf{h}_v = \triangledown (\mathbf{T}_v)$, where $\triangledown$ is an encoding function that maps attributed unfolding trees into real numbers. The existence and injectiveness of $\triangledown$ are ensured by construction. More precisely, the encodings are constructed recursively by the $\text{AGGREGATE}^{(k)}$ and the $\text{COMBINE}^{(k)}$
functions using the neighbourhood information, i.e., nodes' features and edges' attributes.
Therefore, the theorem can be proved provided that there exist
appropriate functions $\triangledown$, $\text{AGGREGATE}^{(k)}$, $\text{COMBINE}^{(k)}$ and READOUT.

The functions  $\text{AGGREGATE}^{(k)}$ and $\text{COMBINE}^{(k)}$ must satisfy
\begin{equation*}
\begin{array}{lc}
\triangledown(\mathbf{T}_v^k)= \bm{h}_v^k = & \\
= {\scriptsize\text{COMBINE}^{(k)}\left( \bm{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)}\left(\{ h_u^{k-1}\}_{ u \in ne_v}, \{\omega_{\{u,v\}}\}_{ u \in ne_v}  \right)\right) } & \\
= {\scriptsize \text{COMBINE}^{(k)} \left(\triangledown(\mathbf{T}_v^{k-1}), \text{AGGREGATE}^{(k)}(\{\triangledown(\mathbf{T}^{k-1}_{u}), \; \}_{u \in ne_v})\right)} & \\
\end{array}
\end{equation*}
$\forall \; k \leq diam(\mathbf{G})$. In a simple solution, $\text{AGGREGATE}^{(k)}$ decodes the attributed trees of the neighbours $u$ of $v$, $\mathbf{T}^{t-1}_{u}$, and stores them into a data structure
to be accessed by $\text{COMBINE}^{(k)}$.
\end{proof}

\subsection{Proof of Thm.~\ref{dyn_thm_approximation}}\label{proof_approx}
In order to prove Thm.~\ref{dyn_thm_approximation} we need some preliminary results.
Using the same argument used for attributed static graph, we  need as a preliminary lemma, the extension of \cite[Lem.~1]{scarselli2008computational} to the domain of dynamic graphs.

\begin{Lem} \label{hypercubes}
For any probability measure $P$ on $\mathcal{D'}$, and any reals $\lambda$, $\delta$, where $0 < \lambda \leq 1$, $\delta \geq 0$, there exist a real $\Bar{b} >0$, which is independent of $\delta$, a set $\Bar{\mathcal{D'}} \subseteq \mathcal{D'}$, and a finite number of partitions $\Bar{\mathcal{D'}_1}, \dots , \Bar{\mathcal{D'}_l}$ of $\Bar{\mathcal{D'}}$, where $\Bar{\mathcal{D'}} = \mathcal{G}_i \times \{ v_i \}$, with $\mathcal{G}_i \subseteq \mathcal{G}$ and $v_i \in \mathcal{G}_i$, such that:
\begin{compactenum}
    \item $P(\Bar{\mathcal{D'}}) \geq 1- \lambda $ holds;
    \item for each $i$, all the graphs in $\mathcal{G}_i$ have the same structure, i.e., they differ only for the values of their labels;
    \item for each set $\Bar{\mathcal{D'}_i}$, there exists a hypercube $\mathcal{H}_i \in \mathbb{R}^a$ such that $\ell_{\mathbf{G}} \in \mathcal{H}_i$ holds for any dynamic graph $\mathbf{G} \in \mathcal{G}_i$, where $\ell_{\mathbf{G}}$ denotes the vector obtained by stacking all the feature vectors of $\mathbf{G}$ for each timestamp;
    \item for any two different sets $\mathcal{G}_i$, $\mathcal{G}_j$, $i \neq j$, their graphs have different structures or their hypercubes $\mathcal{H}_i$, $\mathcal{H}_j$ have a null intersection, i.e. $\mathcal{H}_i \bigcap \mathcal{H}_j = \emptyset$;
    \item for each $i$ and each pair of graphs $\mathbf{G}_1$, $\mathbf{G}_2 \in \mathcal{G}_i$, the inequality $\| \ell_{\mathbf{G}_1} - \ell_{\mathbf{G}_2} \|_{\infty} \leq \delta$ holds;
    \item for each graph $\mathbf{G} \in \Bar{\mathcal{D'}}$, the inequality $\| \ell_{\mathbf{G}}\|_{\infty} \leq \Bar{b}$ holds.
\end{compactenum}
\end{Lem}
\begin{proof}
Indeed, taking in account the argument in \cite{thomas2021graph} one can establish a bijection between the domain of dynamic graphs and the domain of SAUHGs; on the latter we can directly apply \ref{hypercubes_att}.
\end{proof}

Thm.~\ref{dyn_thm_approximation} is equivalent to the following, where the domain contains a finite number of elements in $\mathcal{D'}$ and the features are integers.

\begin{Thm}\label{reduct}
For any finite set of patterns $$\{ (t, G^{(i)} , v) |\ (t, G^{(i)} , v) \in \mathcal{D'}, 1\leq i\leq n \}$$ with $ r_t= \max\limits_{G_t^{(i)}} \text{diam}(G_t^{(i)})$ and with graphs having integer features, for any measurable dynamical system preserving the unfolding equivalence,  $\| \cdot \|$ be a norm  on $\mathbb{R}$, $P$ be any probability measure
on $\mathcal{D'}$ and $\epsilon$ be any real number where $\epsilon >0$. Then, there exists a Message-passing-DGNN such that the function
$ \varphi$  (realized by this model) computed after $r_t+1$ steps satisfies the condition

\begin{equation}\label{mainIntEq}
||dyn (t, G^{(i)}, v) - \varphi(t, G^{(i)}, v)||_m \leq \varepsilon \quad
\end{equation}
$\forall \; i, 1 \leq i \leq n \; \text{ and } \; \forall \; t\in I.$
\end{Thm}

The equivalence is formally proved by the following lemma.
\begin{Lem}\label{reducLemma}
Thm.~\ref{dyn_thm_approximation} holds if and only if Thm.~\ref{reduct} holds.
\end{Lem}
\begin{proof}

Thm.~\ref{dyn_thm_approximation} is more general than Thm.~\ref{reduct}, which makes this implication straightforward. Suppose instead that Thm.~\ref{reduct} holds and show that this implies Thm.~\ref{dyn_thm_approximation}.
Let us apply Lem.~\ref{hypercubes} with values for $P$ and $\lambda$ equal to the corresponding values of Thm.~\ref{dyn_thm_approximation}, being $\delta$ any positive real number. It follows that there is a real $\Bar{b}$ and a subset $\Bar{\mathcal{D'}}$ of $\mathcal{D'}$ s.t. $P(\Bar{\mathcal{D'}}) > 1-\lambda$.
Let $\mathcal{M}$ be the subset of $\mathcal{D'}$ that contains only the dynamic graphs $\mathbf{G}$ satisfying $\| \ell_{\mathbf{G}} \|_{\infty} \leq \Bar{b}$. Note that, since $\Bar{b}$ is independent of $\delta$, then $\Bar{\mathcal{D'}} \subset \mathcal{M}$ for any $\delta$.
Since $\tau$ is integrable, there exists a continuous function which approximates $\tau$, in probability, up to any degree of precision. Thus, without loss of generality, we can assume that $\tau$ is equi--continuous on $\mathcal{M}$. By definition of equi--continuity, a real $\Bar{\delta} > 0 $ exists such that
\begin{equation}\label{cont_1}
    | \tau(\mathbf{G}_1,v) - \tau(\mathbf{G}_2,v) | \leq \frac{\varepsilon}{2}
\end{equation}
holds for any node $v$ and for any pair of dynamic graphs $\mathbf{G}_1, \mathbf{G}_2$ having the same structure and satisfying
$${\| \ell_{\mathbf{G}_1} - \ell_{\mathbf{G}_2} \|_{\infty} \leq \Bar{\delta}}$$
Let us apply Lem.~\ref{hypercubes} again, where, now, the $\delta$ of the hypothesis is set to $\Bar{\delta}$, i.e. $\delta= \Bar{\delta}$. From then on, $\Bar{\mathcal{D'}} = \mathcal{G}_i \times \{ v_i \}$, $1 \leq i \leq n$, represents the set obtained by the new application of Lem.~\ref{hypercubes} and  $I_i^{\Bar{b}, \Bar{\eta}}$ , $1 \leq i \leq 2d$, denotes the corresponding intervals defined in the proof of the same lemma.
Let $\theta: \mathbb{R} \rightarrow \mathbb{Z}$ be a function that encodes reals into integers as follows: for any $i$ and any $z \in I_{i}^{\Bar{b}, \Bar{\eta}}$, $\theta(z) = i$. Thus, $\theta$ assigns to all the values of an interval $I_{i}^{\Bar{b}, \Bar{\eta}}$ the index $i$ of the interval itself. Since the intervals do not overlap and are not contiguous, $\theta$ can be continuously extended to the entire $ \mathbb{R}$. Moreover, $\theta$ can be extended also to vectors, being $\theta(\mathbf{Z})$ the vector of integers obtained by encoding all the components of $\mathbf{Z}$. Finally, let $\Theta: \mathcal{G}\rightarrow \mathcal{G}$ represent the function that transforms each graph by replacing all the feature labels with their coding, i.e. $\mathbf{L}_{\Theta(\mathbf{G})} = \theta(\mathbf{L}_{\mathbf{G}})$. Let $\Bar{\mathbf{G}_1}, \dots, \Bar{\mathbf{G}_v} $ be graphs, each one extracted from a different set $\mathcal{G}_i$. Note that, according to points 3, 4, 5 of Lem.~\ref{hypercubes}, $\Theta$ produces an encoding of the sets $\mathcal{G}_i$. More precisely, for any two graphs $\mathbf{G}_1$ and $\mathbf{G}_2$ of $\Bar{\mathcal{D}}$, we have $\Theta(\mathbf{G}_1) = \Theta(\mathbf{G}_2)$ if the graphs belong to the same set, i.e., $\mathbf{G}_1, \mathbf{G}_2 \in \mathcal{G}_i$, while $\Theta(\mathbf{G}_1) \neq \Theta(\mathbf{G}_2)$ otherwise. Thus, we can define a decoding function $\Gamma$ s.t. $\Gamma(\Theta(\Bar{\mathbf{G}_i}), v_i)=(\Bar{\mathbf{\mathbf{G}_i}}, v_i)$, $1 \leq i \leq n$.

Consider, now, the problem of approximating $\tau \circ \Gamma$ on the set $(\Theta(\Bar{\mathbf{G}_1}),v_1), \dots , ( \Theta(\Bar{\mathbf{G}_n}),v_n)$. Thm.~\ref{reduct} can be applied to such a set, because it contains a finite number of graphs with integer labels. Therefore, there exists a Dyn-GNN that implements a function $\Bar{\varphi}$ s.t., for each $i$,
\begin{equation}\label{cont_2}
|\tau(\Gamma(\Theta(\Bar{\mathbf{G}_i}), v_i))- \Bar{\varphi}(\Theta(\Bar{\mathbf{G}_i}), v_i)| \leq \frac{\varepsilon}{2}
\end{equation}
However, this means that there is also another GNN that produces the same result operating on the original
graphs $\mathbf{G}_i$, namely a GNN for which
\begin{equation}\label{cont_3}
\varphi(\mathbf{G}_i, v_i) = \Bar{\varphi}( \Theta( \Bar{\mathbf{G}_i}), v_i)\,
\end{equation}
holds. Actually, the graphs ${\mathbf{G}_i}$ and $\Bar{\mathbf{G}_i}$ are equal except that the former
 have the coding of the feature labels attached to the nodes, while the latter contain the whole feature labels.
Thus, the GNN that operates on $\Bar{\mathbf{G}_i}$ is that suggested by Thm.~\ref{reduct}, except that
 $\overline{\text{AGGREGATE}}_t^{(0)}$ creates a coding of $\theta(\ell_v)$ before the rest of the tasks.

Putting together the above equality with Eq.
(\ref{cont_1}) and (\ref{cont_2}), it immediately follows that, for any $(\mathbf{G},v) \in \bar{\mathcal{D'}_i}$,
\begin{equation*}
\begin{split}
    |\tau(\mathbf{G}, v) - \varphi (\mathbf{G},v)| &=  |\tau(\mathbf{G},v) - \tau (\Bar{\mathbf{G}_i},v) + \tau (\Bar{\mathbf{G}_i},v) - \varphi (\mathbf{G},v)| \\
    & \leq | \tau(\Bar{\mathbf{G}_i},v)- \varphi(\mathbf{G},v)| +\frac{\varepsilon}{2} \\
    & = |\tau(\Gamma(\Theta(\Bar{\mathbf{G}_i}),v))- \Bar{\varphi}(\Theta(\Bar{\mathbf{G}_i}),v)| + \frac{\varepsilon}{2} \leq \varepsilon
\end{split}
\end{equation*}

Thus, the GNN described by Eq. (\ref{cont_3}) satisfies $|\tau(\mathbf{G},v) - \varphi (\mathbf{G},v) | \leq \varepsilon$ in the restricted domain $\bar{\mathcal{D'}}$.
Since ${P(\bar{\mathcal{D'}}) \geq 1- \lambda}$, we have:
$P( \| \tau(\mathbf{G},v)- \varphi( \mathbf{G},v) \| \leq \varepsilon) \geq 1- \lambda$
which proves the lemma.
\end{proof}

\noindent
Now, we can  proceed to prove Thm.~\ref{reduct}.

\begin{proof}[Proof of Thm. \ref{reduct}]
For the sake of simplicity, the theorem will be proved assuming $m
=1$, i.e. $dyn(t,G,v) \in \mathbb{R}$. However, the result can be easily extended to the general case when $dyn(t,G,v) \in \mathbb{R}^m$, with $m>1$.
According to Thm.~\ref{f_unfold_dyn}, there exists a function $\kappa$ s.t. $dyn(t,G,v) = \kappa ((T_v(i))_{i\in [t]})$. As a remark, each $T_v(i)$ is an attributed unfolding tree. For any timestamp $t$, Thm.~\ref{ue=equal_trees} (with $G_1=G_2$) suggests that an attributed unfolding tree of depth $r+1$, where $r:=  \max\limits_{i\in[t]}  \text{diam}(\mathbf{G}_i)$ is enough to store the dynamic graph information, so that $\kappa$ can be designed to satisfy
$dyn(t,G,v) = \kappa ((T_v(i))_{i \in [t]})= \kappa ((T_v^{r+1}(i))_{i\in [t]})$.
Thus, the main idea of the proof consists of designing a Message-passing-DGNN that is able, at each timestamp t, to encode the sequence of attributed unfolding trees $((T_v(i))_{i\in [t]}$ into the node features, i.e., for each
node $v$, we want to have $q_v(t) = \#_t ((T_v(i))_{i\in [t]}) $, where $\#_t$ is a coding function that maps sequences of $t+1$ attributed trees into real numbers.
In order to build a proper encoding which could fit the definition of the Message-passing-DGNN, we need two coding functions: the $\nabla$ function which encodes the attributed unfolding trees, and the family of coding functions $\#_t$. In particular, we want the nodes' features to be defined as composition of coding functions as follows:
\begin{equation}
    \begin{split}
        q_v(0) & = f_0\left(h_v(0)\right)=\#_0\left(\nabla ^{-1} (h_v(0))\right) \\
        q_v(t) & = \#_t \left(\text{APPEND}_t\left(\#_{t-1}^{-1}(q_v(t-1)), \nabla ^{-1}(h_v(t))\right)\right)
    \end{split}
\end{equation}

where $f_0$ is defined as in \ref{dynsis}, the ausiliar function $\text{APPEND}_t$ and the $\nabla$, $\#_t$ coding functions are defined in the following.
\paragraph{The $\text{APPEND}_t$ Function}
\begin{Def} Let $\mathcal{T}_{v}^{d}$ be the domain of the attributed unfolding trees with root $v$, up to a certain depth $d$.
The function $\text{APPEND}_t : \{(T_{v}^d(i))_{i\in[t-1]}\}\cup \emptyset \times \mathcal{T}_{v}^{d}   \rightarrow \{(T_{v}^d(i))_{i\in[t]}\}$ is defined as follows:
\begin{equation*}
        \text{APPEND}_0\bigl(\emptyset, \bm{T}_{v}^d(0)\bigr) := \bm{T}_{v}^d(0)
\end{equation*}
\begin{equation*}
        \text{APPEND}_t\bigl( \bigl({\bm{T}_{v}^d(0), \ldots, \bm{T}_{v}^d(t-1)}\bigr),\bm{T}_{v}^d(t)\bigr)  :=
\end{equation*}
\begin{equation*}
        \bigl(\bm{T}_{v}^d(0), \ldots,\bm{T}_{v}^d(t-1), \bm{T}_{v}^d(t)\bigr)
\end{equation*}

\noindent Intuitively, this function appends the unfolding tree snapshot of the node $v$ at time $t$ to the sequence of the unfolding trees of that node at the previous $t-1$ timestamps.
\end{Def}

In the following the coding functions are defined; their existence and injectiveness are provided by construction.

\paragraph{The $\nabla$ Coding Function}
Let  $\nabla$ be a composition of any two  injective functions $\alpha_{\nabla}$ and $\beta_{\nabla}$, $\alpha_{\nabla} \circ \beta_{\nabla}$, with the properties described in the following.
\begin{compactenum}
\item[-] $\alpha_{\nabla}$ is an injective function from the domain of static unfolding trees, calculated
on the nodes in the graph $G_t$,  to the Cartesian product $\mathbb{N} \times \mathbb{N}^P \times \mathbb{Z}^{\ell_{\mathbf{V}}}= \mathbb{N}^{P+1} \times \mathbb{Z}^{\ell_{\mathbf{V}}} $,  where
$r_t= \max\limits_{G_t}  \text{diam}(G_t)$ and $P$ is the maximum number of nodes a tree could have.

Intuitively, in the Cartesian product, $\mathbb{N}$ represents the tree structure, $\mathbb{N}^P$ denotes the node numbering, while, for each node, an integer vector $\in \mathbb{Z}^{\ell_{\mathbf{V}}}$ is used to encode the node features. Notice that  $\alpha_{\nabla}$ exists and is injective, since the maximal information contained in an unfolding tree
is given by the union of all its node features and all its structural information, which just equals the dimension of the codomain of $\alpha_{\nabla}$.
\item[-] $\beta_{\nabla}$ is an injective function from $\mathbb{N}^{P+1} \times \mathbb{Z}^{\ell_{\mathbf{V}}}$ to $\mathbb{R}$, whose existence is guaranteed by  the cardinality theory, since the two sets have the same cardinality.
\end{compactenum}
Since $\alpha_{\nabla_t}$ and $\beta_{\nabla_t}$ are injective, also the existence and the injectiveness of
 $\nabla_t$ are ensured.

\paragraph{The $\#_t$ Coding Family } \label{hash_def}
Similarly as $\nabla$, the $\#_t$ functions are composed by two functions $\alpha_{\#_t}$ and $\beta_{\#_t}$, $\alpha_{\#_t} \circ \beta_{\#_t}$, with the properties described in the following.
\begin{compactenum}
\item[-] $\alpha_{\#_t}$ is an injective function from the domain of the dynamic unfolding trees $ \mathcal{U}_t := \{({T}^{d}_{v}(i))_{i\in [t]}\}$
 to the Cartesian product $\mathbb{N}^{t} \times \mathbb{N}^{tP_t} \times \mathbb{Z}^{t\ell_{\mathbf{V}}}= \mathbb{N}^{t(P_t+1)} \times \mathbb{Z}^{t \ell_{\mathbf{V}}} $,  where
$r_t= \max\limits_{\mathbf{G}_t}  \text{diam}(\mathbf{G}_t)$ and $P_t$ is the maximum number of nodes a tree could have (at time t?).
\item[-] $\beta_{\#_t}$ is an injective function from $\mathbb{N}^{t(P+1)} \times \mathbb{Z}^{t \ell_{\mathbf{V}}}$ to $\mathbb{R}$, whose existence is guaranteed by  the cardinality theory, since the two sets have the same cardinality.
\end{compactenum}
Since $\alpha_{\#_t}$ and $\beta_{\#_t}$ are injective, also the existence and the injectiveness of
 $\#_t$ are ensured.

\paragraph{The recursive function $\text{f}$ and the functions $\text{AGGREGATE}_t^{(k)}$ and $\text{COMBINE}_t^{(k)}$ }
The functions $f$ must satisfy
\begin{equation*}
\#_t\bigl((T_v(i))_{i\in[t]}\bigr)= \mathbf{q}_v(t) = f\bigl(\mathbf{q}_v(t-1), \mathbf{h}_v(t)\bigr)
\end{equation*}
where the $\mathbf{h}_v(t)$ is the feature of node $v$ at time $t$ extracted from the $t-th$ SGNN, i.e. $\mathbf{h}_v(t) =$ $\text{SGNN}$ $(G_t,v)$. In particular, at each iteration $k$, we have
{\footnotesize
\begin{equation*}
    \mathbf{h}^k_v(t)=\text{COMBINE}_t^{(k)} \left(\mathbf{h}_v^{k-1}(t), \text{AGGREGATE}^{(k)}\left(\{ h_u^{k-1}(t)\}_{ u \in ne_v(t)}, \{\omega_{\{u,v\}}(t)\}_{ u \in ne_v(t)}  \right)\right)
\end{equation*}}
The functions $\text{AGGREGATE}_t^{(k)}$ and $\text{COMBINE}_t^{(k)}$ -- following the proof in \cite{d2021unifying} -- must satisfy
\begin{equation*}
\begin{array}{lc}
\triangledown(\mathbf{T}_v^k(t))= \mathbf{h}_v^k(t)= & \\{\tiny\text{COMBINE}_t^{(k)} \left(\mathbf{h}_v^{k-1}(t), \text{AGGREGATE}_t^{(k)}\left(\{{h}^{k-1}_{u}(t) \; \}_{u \in ne_v(t)}, \{\omega_{\{u,v\}}(t)\}_{ u \in ne_v(t)}  \right)\right)}&  \\
= {\scriptsize \text{COMBINE}_t^{(k)} \left(\triangledown(\mathbf{T}_v^{k-1}(t)), \text{AGGREGATE}_t^{(k)}(\{\triangledown(\mathbf{T}^{k-1}_{u}(t)) \; \}_{u \in ne_v(t)})\right)} &
\end{array}
\end{equation*}
$\forall \; k \leq r_t:=diam(G_t)$ and $\forall \; t\in I$.

For example, the trees can be collected into the coding of a new  tree, i.e.,
{\small\begin{equation*}
    \text{AGGREGATE}_t^{(k)}({\triangledown}(\mathbf{T}^{k-1}_{u}(t) ), {u \in ne_v(t)})= {\triangledown}(\cup_{u \in ne_v(t)} {\triangledown}^{-1}(\triangledown(\mathbf{T}^{k-1}_{u}(t)))),
\end{equation*}}
where  $\cup_{u \in ne_v(t)} $ denotes an operator that  constructs a tree with a  root having void features from a set of sub--trees (see Fig.~\ref{fig:union}). Then, $\text{COMBINE}_t^{(k)}$ assigns the correct features to the root by extracting them from  $\mathbf{T}^{k-1}_{v}(t) $, i.e.,
{\small\begin{equation*}
    \text{COMBINE}_t^{(k)}({\triangledown}(\mathbf{T}^{k-1}_{v}(t)),b)= {\triangledown}( \text{ATTACH}({\triangledown}^{-1}({\triangledown}(\mathbf{T}^{k-1}_{v}(t))) ,{\triangledown}^{-1}(b))),
\end{equation*}}
where ATTACH is an operator that  returns a tree constructed by replacing the features of the root in the latter tree with those of the former tree and $b$ is the result of the $\text{AGGREGATE}_t^{(k)}$ function.
\begin{figure}[ht]
\centering
 \includegraphics[width=\linewidth]{figures/attach_trees.pdf}
\caption{The ATTACH operator on trees.}
\label{fig:union}
\end{figure}
\\Now, notice that, with this definition, $\text{AGGREGATE}_t^{(k)}$, $\text{COMBINE}_t^{(k)}$, and $\text{READOUT}$ may not be differentiable. Nevertheless, Eq.~(\ref{mainIntEq}) has to be satisfied only for a finite number of graphs,
namely $\mathbf{G}_i$.
Thus, we can specify other functions $\overline{\text{AGGREGATE}_t}^{(k)}$, $\overline{\text{COMBINE}_t}^{(k)}$, and $\overline{\text{READOUT}}$, which  produce exactly the same computations when they are applied on the graphs
$\mathbf{G}_i$, but that can be extended to the rest of their domain, so that they are continuously differentiable. Obviously, such an extension exists since those  functions are only constrained to interpolate a finite number of points\footnote{Notice
that a similar extension can  also be applied to the coding function $\triangledown$ and to the
decoding function $\triangledown^{-1}$. In this case, the coding function is not injective on the whole domain, but only
on the graphs mentioned in the theorem.}.\\

\end{proof}

\subsection{Proof of Thm.~\ref{dyn_mainNN}}\label{proof_dyn-mainNN}

Assume that the hypotheses of Thm.~\ref{dyn_thm_approximation} are fulfilled and
	$\cal{Q}$ is a class of  GNNs with universal components.
	Then, there exists a parameter set $w$ and the functions
	$\text{SGNN}(t)_w$, $f_{0,w}$, $f_w$,  implemented by neural networks in $\cal{Q}$, such that the thesis of	Thm.~\ref{dyn_thm_approximation} holds.

\begin{proof}
The idea of the proof follows from the same reasoning adopted in \cite[Cor.~2]{scarselli2008computational}.
Intuitively,  since the discrete DGNN of Thm.~\ref{dyn_thm_approximation} is implemented by continuously differentiable functions, its output depends continuously on the possible changes in the DGNN implementation:
small changes in the function implementation cause small changes in the DGNN outputs.
Therefore, the functions of the DGNN of Thm.~\ref{dyn_thm_approximation}  can be replaced by neural networks, provided that those networks are \textit{good} approximators.

As in the proof of the dynamic version of the approximation theorem, cf.~Thm.~\ref{dyn_thm_approximation}, without loss of generality, we will assume that the feature dimension is $n=1$.
First of all, note that Thm.~\ref{dyn_thm_approximation} ensures that we can find $\overline{\text{SGNN}(t)}$ (composed by $\overline{\text{COMBINE}^{(k)}(t)}$, $\overline{\text{AGGREGATE}^{(k)}(t)}$ $\forall \;k \leq r_t$ and $\overline{\text{READOUT}(t)}$ ) and $\bar{f_0}$, $\bar{f}$ so that, for the corresponding function $\bar{\varphi}$ implemented by the DGNN:

\begin{equation}\label{prob_partial}
P( \| \text{\straight{dyn}}(t,G,v)- \bar{\varphi}(t, G,v) \| \leq \frac{\varepsilon}{2}) \geq 1- \lambda \quad \quad \quad \forall \; t \in I
\end{equation}

Considering that the theorem has to hold only in probability, we can also assume that the domain is bounded, so $\bar{f}(q,h)$ is bounded and has a bounded Jacobian. Let $B$ be a bound on the Jacobian of $\bar{f}(q,h)$ $\forall \; t \in I$ and $\forall \; q$.

Moreover, let  $\text{SGNN}_w(t)$, $f_{0,w}$,  $f_w$ be functions implemented by universal neural networks that approximate $\overline{\text{SGNN}(t)}$ and $\bar{f_0}$, $\bar{f}$ respectively; let us assume that
\begin{equation*}
\| \bar{h}(t) - h_w(t) \| =
\left\|\overline{\text{SGNN}}(\mathbf{G_t}) - \text{SGNN}_w(\mathbf{G_t}) \right\|_\infty\leq \epsilon_1,
\end{equation*}
\begin{equation*}
\left\| \overline{f_0}( \mathbf{q}, \mathbf{h})-f_{0,w}( \mathbf{q},\mathbf{h})\right\|_\infty\leq \epsilon_2,
\end{equation*}
\begin{equation*}
\text{ and } \left\| \overline{f}( \mathbf{q}, \mathbf{h})-f_w( \mathbf{q},\mathbf{h})\right\|_\infty\leq \epsilon_3
\end{equation*}
hold $\forall \; t \in I$ and $\epsilon_1, \epsilon_2, \epsilon_3>0$.

Let $\bar{F}$, $F_w$ be the recursive functions of the DGNNs that are obtained by stacking all the $\bar{f}$ and $f_w$ for all the nodes of the input graph ; let $\Bar{F}_0$, $F_{0,w}$ be the recursive functions of the DGNNs that are obtained by stacking all the $\bar{f}_0$ and $f_{0,w}$ for all the nodes of the input graph  analogously, let $\bar{H}(t)$ and $H_w(t)$ the features produced by $\overline{\text{SGNN}}$, $\text{SGNN}_w$ stacked over all the nodes of the input graph. Therefore, we have:
\begin{equation*}
\| \bar{H}(t) - H_w(t) \|_{\infty} \leq N\epsilon_1 \; \forall \; t \in I,
\end{equation*}
where $ = |G|$ is the number of nodes of the graph input in the SGNN.
Additionally, we have that:
\begin{equation*}
\begin{array}{l}
    \| \bar{Q}(0) - Q_w(0) \|_{\infty} = \| \bar{f}_0(\bar{H}(0)) - f_{0,w}(H_w(0)) \|_{\infty} \\
    = \| \bar{f}_0(\bar{H}(0)) - \bar{f}_0(H_w(0)) + \bar{f}_0(H_w(0)) -  f_{0,w}(H_w(0)) \|_{\infty} \\
     \leq  \| \bar{f}_0(\bar{H}(0)) - \bar{f}_0(H_w(0)) \|_{\infty} + \| \bar{f}_0(H_w(0)) -  f_{0,w}(H_w(0)) \|_{\infty}  \\
     \leq N\epsilon_1 (NB) + N\epsilon_2 \\
     := \lambda_0(\epsilon_1, \epsilon_2, \epsilon_3).
\end{array}
\end{equation*}
With a similar argument,
\begin{equation*}
\begin{array}{l}
    \| \bar{Q}(1) - Q_w(1) \|_{\infty} =  \|  \bar{f}(\bar{Q}(0),\bar{H}(1)) - f_w(Q_w(0),H_w(1)) \|_{\infty}  \\
    = \|  \bar{f}(\bar{Q}(0),\bar{H}(1)) - \bar{f}(Q_w(0),\bar{H}(1))   + \\
      \quad  +\bar{f}(Q_w(0),\bar{H}(1)) - \bar{f}(Q_w(0),H_w(1)) + \\
     \quad  + \bar{f}(Q_w(0),H_w(1)) - f_w(Q_w(0),H_w(1)) \|_{\infty} \\
     \leq \|  \bar{f}(\bar{Q}(0),\bar{H}(1)) - \bar{f}(Q_w(0),\bar{H}(1)) \|_{\infty}  +
     \\ \quad + \| \bar{f}(Q_w(0),\bar{H}(1)) - \bar{f}(Q_w(0),H_w(1)) \|_{\infty} +\\
     \quad  + \| \bar{f}(Q_w(0),H_w(1)) - f_w(Q_w(0),H_w(1)) \|_{\infty} \\
      \leq \lambda_0 (NB) + N \epsilon_2 + N \epsilon_3 \\
     := \lambda_1(\epsilon_1, \epsilon_2, \epsilon_3).
\end{array}
\end{equation*}

The above reasoning can then be applied recursively to prove that
\begin{equation*}
    \| \bar{\varphi}(t,G,v) - \varphi_w(t,G,v) \|_{\infty} = \| \bar{Q}(t) - Q_w(t) \|_{\infty} = \lambda_t(\epsilon_1, \epsilon_2, \epsilon_3),
\end{equation*}
where $\lambda_t(\epsilon_1, \epsilon_2, \epsilon_3)$ could be found as little as possible, according to $\epsilon_1, \epsilon_2, \epsilon_3$. We choose $\epsilon_1, \epsilon_2, \epsilon_3$ s.t. $\lambda_t \leq \frac{\varepsilon}{2}$. Therefore,
\begin{equation*}
P( \| \bar{\varphi}(t, G,v) - \varphi_w(t, G,v) \| \leq \frac{\varepsilon}{2}) \geq 1- \lambda \quad \quad \quad \forall \; t \in I,
\end{equation*}
which, along with Eq.~\eqref{prob_partial}, proves the result.
\end{proof}
\section{Approximation Capability of GNN's}\label{section_approximation}

This section brings all the results from Sec.~\ref{section_equivalence_SAUHG}
and Sec.~\ref{section_equivalence_dyn_graphs} together and formulates a universal approximation theorem for GNNs working on SAUHGs and dynamic graphs and the set of functions that preserve the attributed or dynamic unfolding equivalence, respectively.

\subsection{GNN's for Attributed Static Graphs}
Since all the different graph types are lossless transformable into each other \cite{thomas2021graph}, it suffices to introduce the GNN architecture of a general model that can handle a SAUHG, as defined in Def.~\ref{def_sauhg}. For this purpose, the GNN architecture introduced in Def.~\ref{def_GNN} has to be extended to take also edge attributes into account. This can be done including the edge attributes as the edge representation in the first iteration analogously to the processing of the node information in the general GNN framework as follows.

\begin{Def}[SGNN]\label{def:SGNN}
For a SAUHG $G=(\mathcal{V}, \mathcal{E}, \alpha, \omega)$ let $u,v \in \mathcal{V}$ and $e = \{u, v\}$.
The SGNN propagation scheme for one iteration $k\in [l]$ is defined as
{\footnotesize\begin{equation*}
    \bm{h}_v^k = \text{COMBINE}^{(k)}\left( \bm{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)}\left(\{ h_u^{k-1}\}_{ u \in ne_v}, \{\omega_{\{u,v\}}\}_{ u \in ne_v}  \right)\right)
\end{equation*}}

The output for a node specific learning problem after the last iteration $l$ respectively is given by
\begin{equation*}
    \bm{z}_v = \text{READOUT}\left( \bm{h}_v^l\right)
\end{equation*}
using a selected AGGREGATION scheme and a suitable READOUT function and the output for a graph specific learning problem is determined by
\begin{align*}
    \bm{z} = \text{READOUT}\left( \{\bm{h}_v^l \mid v \in \set{V}\}\right).
\end{align*}
\end{Def}

Considering the previously defined concepts and statements for SAUHGs in Sec.~\ref{section_equivalence_SAUHG}, finally the following theorem states the universal approximation capability of the SGNNs on bounded SAUHGs.

\begin{Thm}[Universal Approximation Theorem by SGNN]\label{theorem_universal_approx_sauhg}
Let $\mathcal{G}$ be the domain of bounded SAUHGs with ${r= \max\limits_{G \in \mathcal{G}} \text{diam}(\mathbf{G})}$.  For any measurable function $f \in \mathcal{F}(\mathcal{G})$ preserving
the attributed unfolding equivalence (cf.~Def.~\ref{def_preserve_attr_unf_eq}), any norm $\| \cdot \|$ on $\mathbb{R}$, any probability measure $P$
on $\mathcal{G}$, for any reals $\epsilon, \lambda$ where $\epsilon >0$, $0 < \lambda < 1$, there exists a SGNN defined by the continuously differentiable functions $\text{COMBINE}^{(k)}$, $\text{AGGREGATE}^{(k)}$, $\forall k \leq r+1$, and by the function
$\text{READOUT}$, with feature dimension $m=1$, i.e,  $h_v^k\in\mathbb{R}$, such that the function
$ \varphi$  (realized by the GNN) computed after $r+1$ steps for all $\bm{G}\in\mathcal{G}$
satisfies the condition
\begin{equation*}
P( \| f(\mathbf{G},v)- \varphi( \mathbf{G},v) \| \leq \varepsilon) \geq 1- \lambda.
\end{equation*}
\end{Thm}

The corresponding proof can be found in \ref{apx:proof_apx_thm_attributed}

\subsection{GNN's for Dynamic Graphs}

Consistently with the given definition of unfolding trees and WL test for dynamic graphs from Sec.~\ref{section_equivalence_dyn_graphs}, the definition of the discrete dynamic graph neural networks (DGNN) provided in \cite{skardinga2021foundations} can be adopted which uses a GNN to encode each graph snapshot. Here, the model is modified by using the previously defined SGNN \ref{def:SGNN} to encode the structural information of each graph snapshot in Def.~\ref{DGNN} and further extended by restricting the function for modeling the temporal behaviour to continuously differentiable recursive functions in Def.~\ref{def:MPDGNN}.

\begin{Def}[Discrete DGNN]\label{DGNN}
Given a discrete dynamic graph $G = (G_t)_{t\in I}$, a \textbf{discrete DGNN} using a function $f$ for temporal modelling can be expressed as:
\begin{equation}\label{eq_dgnn}
    \begin{split}
        h_1(t), \dots, h_n(t) & = \text{SGNN}(G_{t}) \\
        q_j(t) & =  f(q_j(t-1), h_j(t)) \; \text{for} \; j \in [1,n]
    \end{split}
\end{equation}
where $f:\mathbb{R}^{k} \times \mathbb{R}^{m}\rightarrow \mathbb{R}^k$ is a neural architecture for temporal modelling (in the methods surveyed in \cite{skardinga2021foundations}, $f$ is almost always a RNN or a LSTM) and $h_j^{t} \in \mathbb{R}^m$ is the vector representation of node $j$ at time $t$. Furthermore, $q_j^{t}\in\mathbb{R}^k$ is a hidden representation of node $j$ produced by $f$. The stacked version of the discrete DGNN is:
\begin{equation}\label{stack_eq}
    \begin{split}
        H(t) & = \text{SGNN}(G_{t}) \\
        Q(t) & = F(Q(t-1),H(t))
    \end{split}
\end{equation}
\end{Def}
where $H(t)\in \mathbb{R}^{n\times m}$, $Q(t)\in \mathbb{R}^{n\times k}$, $F:\mathbb{R}^{n\times k} \times \mathbb{R}^{n\times m}\rightarrow \mathbb{R}^{n \times k}$, being $n$ the number of nodes, $m$ and $k$ the dimensions of the hidden representation of a node produced respectively by the $\text{SGNN}$ and by the $f$. Applying $F$ corresponds to component-wise applying $f$ for each node.

\begin{Def}[Message-passing-DGNN]\label{def:MPDGNN}
The \textbf{Message-passing-DGNN} is a particular kind of discrete DGNN where the $f$ and the SGNN of Eq.~\eqref{eq_dgnn} are respectively any continuously differentiable recursive function and a SGNN that uses the following general updating scheme for the $k-th$ iteration with $k\in [l]$ and for any $t \in I$:
{\small\begin{equation*}
    \begin{split}
        {h}_v^{k}(t) & = \text{COMBINE}_t^{(k)}\left( {h}_v^{k-1}(t), \text{AGGREGATE}_t^{(k)}\{ h_u^{k-1}(t) \}_{ u \in ne_v(t)}  \right)
    \end{split}
\end{equation*}}

Then $h_v(t):= h_v^l(t)$ is used as input, together with the previous $q_v(t-1)$, to the recursive function $f$ Eq.~\eqref{eq_dgnn}.

\noindent
\end{Def}

Finally, the universal approximation of the Message-Passing GNN for dynamic graphs is determined as follows.

\begin{Thm}[Approximation by Message-passing-DGNN]\label{dyn_thm_approximation}
Let  $G = (G_t)_{t\in I}$ be a discrete dynamic graph in the graph domain $\mathcal{D'}$. For each timestamp $t\in I$ we define ${r_t = \max \limits _{\mathbf{G_t} \in \mathcal{G}} (diam(G_t))}$. Let $\text{\straight{dyn}}(t,G,v) \in \mathcal{F}(\mathcal{D'})$ be any measurable dynamical system preserving
the unfolding equivalence,  $\| \cdot \|$ be a norm  on $\mathbb{R}$, $P$ be any probability measure
on $\mathcal{D'}$ and $\epsilon, \lambda$ be any real numbers where $\epsilon >0$, $0 < \lambda < 1$. Then, there exists a Message-passing-DGNN such that the function
$ \varphi$  (realized by this model) computed after $r_t+1$ steps
satisfies the condition
\begin{equation*}
P( \| \text{\straight{dyn}}(t,G,v)- \varphi(t, G,v) \| \leq \varepsilon) \geq 1- \lambda \quad \quad \quad \forall t \in I
\end{equation*}
\end{Thm}

The proof can be found in Apx.~\ref{proof_approx}.

Theorem~\ref{dyn_thm_approximation} intuitively states that, given a dynamical system $\text{dyn}$, there is a Message Passing DGNN that approximates it.
The functions which the Message-Passing DGNN is a composition of (such as the dynamical function $f$, $\text{COMBINE}^{(k)}$, $\text{AGGREGATE}^{(k)}$ etc) are supposed to be continuously differentiable but still generic, while  can be generic and completely unconstrained. This situation does not correspond to practical cases, where the Message Passing DGNN adopts particular architectures and those functions are neural networks or, more generally, parametric models --- for example made of layers of sum, max, average, etc.
Thus, it is of fundamental interest to clarify whether the theorem still holds when the components of the Message-Passing DGNN are parametric models.

\begin{Def} \label{def:universal}
A class $\cal{Q}$  of discrete DGNN models is said to have \textit{universal components} if, for any $\epsilon_1, \epsilon_2, \epsilon_3>0$
and any continuously differentiable target functions $\overline{\text{SGNN}(t)}$, $\overline{f_0}$,  $\overline{\text{f}}$,
 there is a discrete DGNN in  the class $\cal{Q}$, with functions $\text{SGNN}_w(t)$, $f_{0,w}$,  $f_w$,  and parameters $w$  such that, for any input values  $\mathbf{G_t}$,
 $\mathbf{q},\mathbf{h}$, it holds

\begin{equation*}
\begin{split}
\left\|\overline{\text{SGNN}}(\mathbf{G_t}) - \text{SGNN}_w(\mathbf{G_t}) \right\|_\infty &\leq \epsilon_1, \\
\left\| \overline{f_0}( \mathbf{q}, \mathbf{h})-f_{0,w}( \mathbf{q},\mathbf{h})\right\|_\infty &\leq \epsilon_2 \; \text{ and } \\
\left\| \overline{f}( \mathbf{q}, \mathbf{h})-f_w( \mathbf{q},\mathbf{h})\right\|_\infty &\leq \epsilon_3, \;
\end{split}
\end{equation*}
where $\|\cdot\|_\infty$ is the infinity norm.
\end{Def}

\begin{Rem}
In Def.~\ref{def:universal} the definition of $\text{SGNN}_w(t)$ is well-posed, as we know from \cite[Thm.~IV.6]{scarselli2008computational} that a static parametric $\text{SGNN}(t)_w$ exists s.t. $$\left\|\overline{\text{SGNN}(t)}(\mathbf{G_t}) - \text{SGNN}(t)_w(\mathbf{G_t}) \right\|_\infty\leq \epsilon_1 $$
\end{Rem}

\vspace{0.5cm}
The following result shows that Theorem~\ref{dyn_thm_approximation} still holds even for discrete DGNNs with universal components.

\begin{Thm}[Approximation by neural networks]\label{dyn_mainNN}
	Assume that the hypotheses of Thm.~\ref{dyn_thm_approximation} are fulfilled and
	$\cal{Q}$ is a class of  GNNs with universal components.
	Then, there exists a parameter set $w$ and the functions
	$\text{SGNN}(t)_w$, $f_{0,w}$, $f_w$,  implemented by neural networks in $\cal{Q}$, such that the thesis of	Thm.~\ref{dyn_thm_approximation} holds.
\end{Thm}

The proof can be found in Apx.~\ref{proof_dyn-mainNN}

\subsection{Discussion}

The following remarks may further help to understand the results proved in the previous paragraphs:
\begin{itemize}
    \item Theorem \ref{theorem_universal_approx_sauhg} shows that each message passing GNN considering edge attributes in the aggregation step and whose COMBINE and AGGREGATE functions satisfy specific properties can be a universal approximator for functions on a variety of different domains. Examples are hypergraph domains, multigraph domains, directed graph domains, etc. This result provides an alternative way to design individual GNNs for a specific graph domain. First, each graph in the domain can be transformed into a SAUHG and then a standard message passing GNN (such as OGNN \cite{jour_scarselli_2009}, GIN \cite{xu2018powerful} or a GNN characterized by sufficiently "expressive" AGGREGATE and COMBINE functions) can be used.

    as we take into account a discrete recurrent model
working on graph snapshots (also known as Stacked
DGNN); nevertheless, in [ 15 ] several DGNNs of this
kind are listed, such as GCRN-M1 [ 37], RgCNN [ 38],
PATCHY-SAN [ 39 ], DyGGNN [40], and others. Still,
the approximation capability depends both on the functions
AGGREGATE and COMBINE designed for each GNN
working on the single snapshot and the implemented
recurrent neural network. As an example, the most
general model, the original Recurrent Neural Network
has been proved to be a universal approximator [41]

    \item Theorem \ref{dyn_thm_approximation} doesn't hold for any Dynamic GNN, as we take into account a discrete recurrent model working on graph snapshots (also known as Stacked DGNN); nevertheless, in\cite{kazemi_survey_dyn_gnn} several DGNN of this kind are listed, such as  GCRN-M1 \cite{seo2018structured}, RgCNN \cite{narayan2018learning}, PATCHY-SAN \cite{niepert2016learning}, DyGGNN \cite{taheri2019learning}, and others.
     Still, the approximation capability depends both on the functions AGGREGATE and COMBINE designed for each GNN working on the single snapshot and the implemented Recurrent Neural Network. As an example, the most general model, the original RNN, has been proved to be a universal approximator \cite{hammer2000approximation}.

\end{itemize}

\section{Conclusion}\label{section_conclusion}

This paper provides two extensions of the 1-WL isomorphism test and the definition of unfolding trees of nodes and graphs. First, we introduced WL test notions to attributed and dynamic graphs, and second, we introduced extended notions for unfolding trees on attributed and dynamic graphs.
Further, we proved the existence of a bijection between the dynamic 1-WL equivalence of dynamic graphs and the attributed 1-WL equivalence of their corresponding static versions that are bijective regarding their encoded information. The same result we proved w.r.t. the unfolding tree equivalence.
Moreover, we extended the strong connection between unfolding trees and the (dynamic/attributed) 1–WL tests — proving that they give rise to the same equivalence between nodes for the attributed and the dynamic case, respectively. Note that the graph neural networks working on static graphs usually have another architecture than those working on dynamic graphs. Therefore, we have proved that both the different GNN types can approximate any function that preserves the (attributed/dynamic) unfolding equivalence (i.e., the (attributed/dynamic) 1-WL equivalence).

Note that, in this paper, we consider extensions of the usual 1-WL test and the commonly known unfolding trees. One could further investigate extensions, for example, the n-dim attributed/dynamic WL test or other versions of unfolding trees, covering GNN models not considered by the frameworks used in this paper.
These extensions might result in a more exemplary classification of the expressive power of different GNN architectures.
Moreover, the proposed results mainly focus on the expressive power of GNNs. However, GNNs with the same expressive power may differ for other fundamental properties, e.g., the computational and memory complexity and the generalization capability. Understanding how the architecture of AGGREGATE(k), COMBINE(k), and READOUT impact those properties is of fundamental importance for practical applications of GNNs.

\section{Equivalence of Unfolding Tree Equivalence and WL Equivalence}\label{section_equivalences}

From \cite{d2021unifying} it is known, that for static undirected and unattributed graphs, both the unfolding tree and Weisfeiler-Lehman approach for testing the isomorphism of two graphs are equivalent. This result, combined with the set of functions that preserve the unfolding tree equivalence (cf.~Def.~\ref{def_function_preserves_uf_equivalence}), leads to the universal approximation theorem for GNNs as defined in Def.~\ref{def_GNN}. This paper extends the universal approximation theorem to GNNs working on SAUHGs (cf.~Def.~\ref{def_sauhg}) and dynamic graphs (cf.~Def.~\ref{def_discrete_dynamic_graph}) for the set of functions that preserve the attributed unfolding tree equivalence (cf.~Def.~\ref{def_preserve_attr_unf_eq}) and the dynamic unfolding tree equivalence (cf.~Def.~\ref{def:sys_unfold}), respectively. In this context, this section first proposes the extended versions of the unfolding trees (UT) and the Weisfeiler-Lehman (WL) test to the additional consideration of edge attributes (cf.~Def.~\ref{def_unfolding_tree_attributed} and \ref{def_WL_test_attributed}). Having these two notions, it is possible to show the equivalence between the extended versions of UT-equivalence and the WL-equivalence for SAUHGs (cf.~Def.~\ref{def_sauhg}).
Given that any graph type is reducible to a SAUHG by a composition of the transformations, the result holds for any arbitrary graph type. However, GNNs that work on static graphs differ in their architecture when handling dynamic graphs. Thus, it is necessary to emphasize the extensions for dynamic graphs.

\subsection{Equivalence for Attributed Static Graphs}\label{section_equivalence_SAUHG}

To extend the result that the WL equivalence and the unfolding tree equivalence between two graphs are equivalent (\cite{d2021unifying}) to any arbitrary graph an extension of the theorem to SAUHGs suffices. The extended result on SAUHGs is formalized and proven in Thm.~\ref{ue=wl}.
The original WL test and unfolding tree notion covers all graph properties except for the node and edge attributes. Thus, first the notion of unfolding trees (cf.~Def.~\ref{def_unfolding_Tree}) and the Weisfeiler-Lehman test (cf.~Def.~\ref{def_1_WL_test}) have to be extended to an attributed version.

\begin{Def}[Attributed Unfolding Tree]\label{def_unfolding_tree_attributed}
The \textbf{attributed unfolding tree} $\bm{T}_{v}^d$ in graph $G = (\mathcal{V}, \mathcal{E}, \alpha, \omega)$ of node $v \in \mathcal{V}$ \textbf{up to depth} $d \in \mathbb{N}$ is defined as
\begin{align*}
    \bm{T}_{v}^d =
    \begin{cases}
        Tree(\alpha_{v}), \quad \text{if } d = 0 \\
        Tree\bigl(\alpha_{v}, \Omega_{ ne_v} , \bm{T}^{d-1}_{ne_v}\bigr) \quad \text{if } d > 0\,,
    \end{cases}
\end{align*}
where ${Tree(\alpha_{v})}$ is a tree constituted of node $v$ with attribute $\alpha_v$,  and $Tree\bigl(\alpha_{v}, \Omega_{ ne_v} , \bm{T}^{d-1}_{ne_v}\bigr)$ is the tree with root node $v$ and subtrees $\bm{T}^{d-1}_{ne_v} = (\bm{T}_{u_1}^{d-1}, \ldots, \bm{T}_{u_{|ne_v|}}^{d-1})$ with corresponding edge attributes $\Omega_{ne_v} = (\omega_{\{v, x_1\}}, \ldots,  \omega_{\{v, x_{|ne_v|}\}})$ and roots in the neighbors of $v$ of depth $d-1$.

Moreover, the \textbf{attributed unfolding tree} of $v$ determined by $\bm{T}_v = \lim_{d \rightarrow \infty} \bm{T}_v^d$ is obtained by merging all unfolding trees $\bm{T}^d_v$ of any depth $d$.
\end{Def}

Note that the subtrees in the aforementioned definition of the attributed unfolding trees, unlike the unattributed unfolding trees (cf.~Def.~\ref{def_unfolding_Tree}) are sorted. In Rem.~\ref{rem_multiset_vs_sorted_multiset} we already mentioned that there are situations where it is necessary to consider ordered multisets. Here, the order of the subtrees is important for the proof of Lem.~\ref{equal_trees=WL_coloring}. More precisely, the assumption is used for the steps in Eq.~\eqref{eq89} where the subtrees in the unfolding trees have to be linked to the attributes of the edges between the parent node and the root of the subtree.

Based on the definition of the attributed unfolding tree of nodes, it is possible to extend the concept of unfolding equivalence of nodes and graphs (cf.~Def.~\ref{def_unfolding_tree_equivalence}) to the unfolding equivalence respecting the node and edge attributes.

\begin{Def}[Attributed Unfolding Equivalence]\label{def_attributed_unfolding_tree_equivalence}

Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, \alpha_1, \omega_1)$ and $G_2 = (\mathcal{V}_2, \mathcal{E}_2, \alpha_2, \omega_2)$ be two SAUHGs. Then $G_1$ and $G_2$ are \textbf{attributed unfolding tree equivalent}, noted by $G_1 \sim_{AUT} G_2$, if and only if ${\multiset{\bm{T}_u \mid u \in \mathcal{V}_1} = \multiset{\bm{T}_v \mid v \in \mathcal{V}_2}}$.
Analogously, two nodes $u\in {V}_1, v\in \set{V}_2$ are unfolding tree equivalent, noted by $u \sim_{AUT} v$ if and only if $\bm{T}_u = \bm{T}_v$.
\end{Def}

Since it is the goal to show the attributed extension of the universal approximation theorem (Thm.~\ref{theorem_universal_approx_sauhg}), it is necessary to define the corresponding family of attributed unfolding equivalence preserving functions. A function preserves the attributed unfolding equivalence if the output of the function is equal when two nodes are attributed unfolding equivalent.

\begin{Def}\label{def_preserve_attr_unf_eq}Let $\mathcal{G}$ be the domain of bounded SAUHGs, $\bm{G}=(\mathcal{V}, \mathcal{E}, \alpha, \omega)\in\mathcal{G}$ a SAUHG and $u,v\in \mathcal{V}$ two nodes. Then a function $f: \mathcal{G} \rightarrow \mathbb{R}^m$ is said to \textbf{preserve the attributed unfolding equivalence} on $\mathcal{G}$ if
\begin{equation*}
v \sim_{AUT} u \Rightarrow f(\mathbf{G},v)=f(\mathbf{G}, u).
\end{equation*}
All functions that preserve the attributed unfolding equivalence are  collected in the set $\mathcal{F}(\mathcal{G})$.
\end{Def}

Analogous to the argumentation in \cite{scarselli2008computational}, there exists a relation between the unfolding equivalence preserving functions and the unfolding trees for attributed graphs, as follows.

\begin{Prop}[Functions of attributed unfolding trees] \label{f_unfold}
A function $f$ belongs to $\mathcal{F}(\mathcal{G})$ if and only if there exists a function $\kappa$ defined on trees such that for any graph $\bm{G}\in\mathcal{G}$ it holds $f(\mathbf{G},v)= \kappa(\mathbf{T}_v)$, for any node $v \in \bm{G}$.
\end{Prop}

The proof works analogous to the proof of the unattributed version presented in \cite{scarselli2008computational} and can be found in Apx.~\ref{apx:prop_functions_of_attr_unf_trees}.

Using the definition of the attributed unfolding equivalence on graphs, the 1-Weisfeiler Lehman (1-WL) test provided in \cite{d2021unifying} is extended to attributed graphs. This allows for the definition of the attributed 1-WL equivalence on graphs and the subsequent lemmata Lem.~\ref{ue=equal_trees}, Lem.~\ref{equal_trees=WL_coloring} and the resulting theorem Thm.~\ref{ue=wl} that pose the relation between the attributed unfolding equivalence and the attributed 1-WL test.

\begin{Def}[Attributed 1-WL test]\label{def_WL_test_attributed}
Let HASH be a bijective function that codes every possible node feature with a color and $G = (\mathcal{V}, \mathcal{E}, \alpha, \omega)$.
The \textbf{attributed 1-WL (1-AWL) test} is defined recursively through the following.
\begin{itemize}
    \item At iteration $i=0$ the color is set to the hashed node feature:
    \begin{align*}
        c_v^{(0)} = \text{HASH}(\alpha_v)
    \end{align*}
    \item At iteration $i>0$ the HASH function is extended to the edge weights:
    \begin{align*}
        c_v^{(i)} = \text{HASH}\Bigl( \bigl( c_v^{(i-1)}, \Omega_{ ne_v}, c_{ne_v}^{(i-1)}\bigr)\Bigr)
    \end{align*}
\end{itemize}
\end{Def}

In the following the 1-WL equivalence of graphs and nodes, as defined in Def.~\ref{def_wl_equivalence} is extended by using the attributed version of the 1-WL test (cf.~Def.~\ref{def_WL_test_attributed}).

\begin{Def}[Attributed 1-WL equivalence]\label{def_attributed_wl_equivalence}
Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, \alpha_1, \omega_1)$ and $G_2 = (\mathcal{V}_2, \mathcal{E}_2, \alpha_2, \omega_2)$ be two SAUHGs. Then $G_1$ and $G_2$ are \textbf{attributed WL-equivalent}, noted by $G_1 \sim_{AWL} G_2$, if and only if for all nodes $v_1 \in \mathcal{V}_1$ there exists a corresponding node $v_2 \in \mathcal{V}_2$ with $c_{v_1} = c_{v_2}$.
Analogously, two nodes $u\in {V}_1, v\in \set{V}_2$ are attributed WL-equivalent, noted by $u \sim_{AWL} v$ if and only if $c_u = c_v$.
\end{Def}

Finally, to complete the derivation of the equivalence between the  attributed unfolding equivalence (cf.~Def.~\ref{def_attributed_unfolding_tree_equivalence}) and the attributed WL-equivalence (cf.~Def.~\ref{def_attributed_wl_equivalence}), the following helping lemmata Lem.~\ref{ue=equal_trees} and Lem.~\ref{equal_trees=WL_coloring} are given which directly lead to Thm.~\ref{ue=wl}.
The first lemma states the equivalence between the attributed unfolding tree equivalence of nodes and the equality of their attributed unfolding trees up to a specific depth. In \cite{d2021unifying} it has been shown, that the unfolding trees of infinite depth are not necessary to consider for this equivalence. Instead, the larger diameter
of both graphs under consideration is sufficient for the depth of the unfolding trees, which is finite due to the fact that the graphs are bounded.
Here, this statement is also used for the attributed case.
\begin{Lem}\label{ue=equal_trees}
Let $G_1,G_2$ belong to the domain of bounded SAUHGs. Then
\begin{align*}
    {\forall\, u\in \mathcal{V}_1, \forall\, v \in \mathcal{V}_2 : u \sim_{AUT} v \Longleftrightarrow \bm{T}^{r+1}_u = \bm{T}^{r+1}_v},
\end{align*}
with $r = \max(\text{diam}(G_1), {diam}(G_2))$.
\end{Lem}
The proof can be found in Apx.~\ref{apx_proof_of_ue=equal_trees}.\\
Furthermore, the second helping lemma determines the equivalence between the attributed unfolding trees of two nodes and their colors resulting from the attributed 1-WL test. Additionally, the iteration of the attributed 1-WL test corresponds to the depth of the attributed unfolding trees.

\begin{Lem}\label{equal_trees=WL_coloring}
Consider $G' = (\mathcal{V}', \mathcal{E}' , \alpha', \omega')$ as the SAUHG resulting from a transformation of an arbitrary static graph $G = (\mathcal{V}, \mathcal{E} , \alpha, \omega)$ with nodes $u, v \in \mathcal{V}$ and corresponding attributes $\alpha_u, \alpha_v$. Then it holds
\begin{align*}
    \forall \; d \in \mathbb{N} : \bm{T}^{d}_u = \bm{T}^{d}_v \Longleftrightarrow c_u^{(d)} = c_v^{(d)}
\end{align*}
\end{Lem}

The proof can be found in Apx.~\ref{proof_of_equal_trees=WL_coloring}

Combining lemmata Lem.~\ref{ue=equal_trees} and Lem.~\ref{equal_trees=WL_coloring}, finally the equivalence of the attributed unfolding tree equivalence and the attributed 1-WL equivalence of two nodes belonging to the same graph can be formalized.

\begin{Thm}\label{ue=wl}
Consider $G'$ as in Lem.~\ref{equal_trees=WL_coloring}.
Then it holds
\begin{align*}
    \forall \; u, v \in V : u \sim_{AUT} v \Longleftrightarrow u \sim_{AWL} v.
\end{align*}
\end{Thm}

\begin{proof}
The proof follows from a ring closure of the proofs of Lem.~\ref{ue=equal_trees} and Lem.~\ref{equal_trees=WL_coloring}.
\end{proof}

Note that Lem.\ref{equal_trees=WL_coloring} and, therefore, Thm.~\ref{ue=wl} also hold in case $G'$ is the SAUHG (cf.~Def.~\ref{def_sauhg}) resulting from a transformation of a dynamic graph $G = (G_t)_{t\in I}$.
However, another main result of this paper depicts the universal approximation capability for a graph neural network (GNN) for dynamic graphs (cf.~Thm.~\ref{dyn_thm_approximation}), whose architecture significantly differs from the GNN applied to attributed graphs. Therefore, the following section includes the derivation of the different equivalences on dynamic graphs separately.

\subsection{Equivalence for Dynamic Graphs} \label{section_equivalence_dyn_graphs}
In this section, the previous introduced concepts of unfolding tree and Weißfeiler-Lehman equivalences are expanded to the dynamic case.
First, dynamic unfolding trees are introduced including a sequence of unfolding trees for each graph snapshot respectively. Afterwards, the equivalence of two dynamic graphs regarding their dynamic unfolding trees is presented. Furthermore, the correspondence between the dynamic unfolding tree and the attributed unfolding tree of a dynamic graph and its corresponding static version is verified by the construction of a appropriate bijection in (cf.~Thm.~\ref{thm_bijection_of_uf_trees} and Thm.~\ref{thm_bijection_of_wl_tests}).
Fig.~\ref{fig_commutative_diagram_dynamic} illustrates the connection between the definitions of dynamic graphs and SAUGHs, their unfolding trees and WL tests and which theorems and definitions characterize these.

\begin{figure*}[!ht]
    \centering
    \includegraphics[width=\textwidth]{figures/commutative_diagram.pdf}
    \caption{The commutative diagram illustrates the relations between a dynamic and a static attributed graph and their corresponding dynamic and attributed unfolding trees and WL tests.\label{fig_commutative_diagram_dynamic}}
\end{figure*}

\begin{Def}[Dynamic Unfolding Tree] \label{def_unfolding_tree_dynamic} Let $G = (G_t)_{t\in I}$ with $G_t = (\mathcal{V}_t, \mathcal{E}_t, \alpha_t, \omega_t)$ be a dynamic graph.
The \textbf{dynamic unfolding tree} $\bm{T}_{v}^d(t)$ at time $t\in I$ of node $v$ up to depth $d \in \mathbb{N}$ is defined as
\begin{align*}
    \bm{T}_{v}^d (t)=
    \begin{cases}
         Tree(\alpha_{v}(t)), \quad \text{if } d = 0
        \\
        Tree\bigl(\alpha_{v}(t), \Omega_{ ne_{v}(t)} , \bm{T}^{d-1}_{ne_{v}(t)}(t)\bigr) \quad \text{if } d > 0,
    \end{cases}
    \end{align*}

where ${Tree(\alpha_{v}(t))}$ is a tree constituted of node $v$ with attribute $\alpha_{v}(t)$ if $\alpha_v\neq \,\perp$ or empty otherwise. Furthermore, $Tree\bigl(\alpha_{v}(t), \Omega_{ ne_{v}(t)} , \bm{T}^{d-1}_{ne_{v}(t)}(t)\bigr)$ is the tree with root node $v$ with attribute $\alpha_{v}(t)$ if $\alpha_v(t)\neq \,\perp$ or empty otherwise. Additionally, $\bm{T}^{d-1}_{ne_{v}(t)}(t) = \bigl({\;\bm{T}_{u_1}^{d-1}(t), \ldots, \bm{T}_{u_{|ne_{v}(t)|}}^{d-1}(t)\;}\bigr)$ are corresponding subtrees with edge attributes $\Omega_{ ne_{v}(t)}$ .

Moreover, the \textbf{dynamic unfolding tree of $v$} at time $t$,  ${\bm{T}_{v}(t) = \lim \limits_{d \rightarrow \infty} \bm{T}_{v}^d(t)}$ is obtained  by merging all the unfolding trees $\bm{T}_{{v}}^d(t)$ for any $d$.
\end{Def}

\begin{Def}\label{def:unf_eq}
Two nodes $u,\ v$ are said to be \textbf{dynamic unfolding equivalent} $u\sim_{DUT} v$ if $(\bm{T}_{u}(t))_{t\in I} = (\bm{T}_{v}(t))_{t\in I}$.  Analogously,
two dynamic graphs $G'_1 = (G'_{1,t})_{t\in I}, G'_2 = (G'_{2,t})_{t\in I}$ are said to be \textbf{dynamic unfolding equivalent} $G'_1 \sim_{DUT} G'_2$, if there exists a bijection between the nodes of the graphs that respects the partition induced by the unfolding equivalence on the nodes\footnote{For the sake of simplicity and with notation overloading, we adopt the same symbol $\sim_{DUT}$ both for the equivalence between graphs and the equivalence between nodes.}.
\end{Def}

\begin{Rem}\label{remark_domain_graph_andsoon}
Note that the investigation on equivalences of dynamic graphs requires determining the handling of dynamic graphs that are equal in their structure but differ in their temporal occurrence.
I.e., dependent on the commitment of the WL equivalence or the unfolding tree equivalence it is required to decide whether the concepts need to be \textbf{time-invariant}. For time-invariant equivalence, the following concepts hold as they are. In case two graphs with the same structure should be distinguished when they appear at different times, the node and edge attributes can be extended by an additional dimension carrying the exact timestamp. Thereby, the unfolding trees of two (structural) equal nodes would be different, having different timestamps in their attributes. Then, all dynamic graphs $G^{(n)} \in \mathcal{G}'$ are defined over the same time interval $I$. Without loss of generality, this assumption can be made since the set of timestamps of $G^{(n)}$ noted by $I_{G^{(n)}}$ can be padded by including missing timestamps $t_q$ and $G^{(n)}$ can be padded by empty graphs ${G^{(n)}_{q} = (\mathcal{V}^{(n)}_q = \emptyset, \mathcal{E}^{(n)}_q = \emptyset, \alpha_q(\emptyset) = \emptyset, \omega_q(\emptyset) = \emptyset}$.
For the sake of simplicity, in this paper we go with time-invariant graph equivalences and assume that all graphs $G^{(n)} \in \mathcal{G}'$ are defined over the same time indices $I$. As a result, two dynamic graphs over different time intervals are never considered as equivalent in any sense.
\end{Rem}

Assuming that all dynamic graphs under consideration have the same timestamps, suitable functions that preserve the unfolding equivalence on dynamic graphs are dynamic systems. Before this statement is formalized and proven in Prop.~\ref{f_unfold_dyn}, dynamic systems and their property to preserve the dynamic unfolding equivalence are defined in the following.

\begin{Def}[Dynamic System]\label{def:dyn_sys}
Let $\mathcal{G}'$ and $I$ be as stated in Rem.~\ref{remark_domain_graph_andsoon} and further let $\mathcal{V}' = \; \cup_{G^{(n)} \in \mathcal{G'}, t \in I} \mathcal{V}^{(n)}_t$ be the set of all appearing nodes in $G'$. A
\textbf{dynamic system} is defined as a function ${\text{\straight{dyn}}: \mathcal{D^\prime}:= I \times \mathcal{G'} \times  \mathcal{V}' \rightarrow \mathbb{R}^m}$ formalized by
\begin{equation}\label{dynsis}
    \text{\straight{dyn}}(t,G,v): =g(x_G(t),v),
\end{equation}
for $G = (\mathcal{V}, \mathcal{E}, \alpha, \omega) \in \mathcal{G}', v \in \mathcal{V}$ with
\begin{equation*}
    x_G(t)\; = \;
    \begin{cases}
      f_0(G_0)  &  \text{if}\; t=0 \\
      f(x_G(t-1), G_{t})  & \text{if} \; t>0,\\
    \end{cases}
\end{equation*}
where $f_0$ is a given initialization function applied to the first graph snapshot $G_0$ of the graph sequence in $G \in \mathcal{G}$ and $f: \mathbb{R}^k \times \mathcal{G} \rightarrow \mathbb{R}^k$ is a recursive function.
\end{Def}

\begin{Def}\label{def:sys_unfold}
A dynamic system $\text{\straight{dyn}}(\cdot,\cdot,\cdot)$ \textbf{preserves the dynamic unfolding tree equivalence} on $\mathcal{D^\prime}$ if and only if for any input graph sequences $G',G''\in \mathcal{G'}$, node set $\mathcal{V'}$ and two nodes $u, v\in\mathcal{V'}$ it holds
\begin{align*}
    v \sim_{DUT} u  \Longrightarrow \text{\straight{dyn}}(t,G^\prime,v)=\text{\straight{dyn}}(t,G^{\prime\prime},u).
\end{align*}
\end{Def}

The class of dynamic systems that preserve the unfolding equivalence on $\mathcal{D^\prime}$ will be denoted with $\mathcal{F}(\mathcal{D^\prime})$. A characterization of $\mathcal{F}(\mathcal{D^\prime})$ is given by the following result (following the work in \cite{scarselli2008computational}).

\begin{Prop}[Functions of dynamic unfolding trees] \label{f_unfold_dyn}
A dynamic system \straight{dyn} belongs to $\mathcal{F}(\mathcal{D^\prime})$ if and only if there exists a function $\kappa$ defined on trees such that for all $(t,G,v)\in \mathcal{D'}$ it holds
\begin{align*}
\text{\straight{dyn}}(t,G,v)= \kappa\Bigl(\bigl(\bm{T}_{v}(i)\bigr)_{i\in [t]}\Bigr).
\end{align*}
\end{Prop}

The proof can be found in Apx.~\ref{proof_of_f_unfold}.

For the dynamic WL test an extended version of the attributed 1-WL test is used and defined in Def.~\ref{def_WL_test_attributed} in $r$-dimensions. Note, that it is not equal to an attributed extension of the $r$-dimensional WL-test defined in \cite{morris_2019_WL_go_neural} since here a special subset of $r$ nodes is used. Based on the modified WL test, the corresponding dynamic WL equivalence is defined respectively.

\medskip
\begin{Def}[Dynamic 1-WL test]\label{def_WL_test_dynamic}Let $G = (G_t)_{t\in I}$ with $G_t = (\mathcal{V}_t, \mathcal{E}_t, \alpha_t, \omega_t)$ a dynamic graph.
Let $\text{HASH}_t$ be bijective function that codes every possible node feature of $G_t$ with a color. Note that, for each timestamp t, the color set could change.
The dynamic 1-WL test generates a vector of color sets one for each timestamp $t\in I$ by:
\begin{itemize}
    \item At iteration $i=0$ the color is set to the hashed node attribute:
    \begin{align*}
        c_{v}^{(0)}(t) &= \text{HASH}_t\left(\alpha_{v}(t)\right)

    \end{align*}
    \item At iteration $i>0$ the $\text{HASH}_t$ function is extended to the edge weights:
    \begin{align*}
        c_{v}^{(i)}(t) &= \text{HASH}_t\Bigl( \bigl( c_{v}^{(i-1)}(t), \Omega_{ne_v(t)} , c_{ne_v(t)}^{(i-1)}(t)\bigr)\Bigr)

    \end{align*}
\end{itemize}
\end{Def}

\begin{Def}[Dynamic 1-WL equivalence]\label{def_dynamic_wl_equivalence}
Let $G_1 = (G^{(1)}_t)_{t\in I}$ and $G_2 = (G^{(2)}_t)_{t\in I}$ be dynamic graphs. Then $G_1$ and $G_2$ are \textbf{dynamic WL equivalent}, noted by $G_1 \sim_{DWL} G_2$, if and only if for all nodes $v_1 \in \mathcal{V}^{(1)}(t)$ there exists a corresponding node $v_2 \in \mathcal{V}^{(2)}(t)$ with $c_{v_1}(t) = c_{v_2}(t)$ for all $t\in I$.
Analogously, two nodes are said to be \textbf{dynamic WL equivalent} if their colors resulting from the WL test are equal for all timestamps.
\end{Def}

Consider a dynamic graph $G = (G_t)_{t\in I}$ and its transformed static version ${\textsc{makeStatic}(G) =: G' = (\mathcal{V'}, \mathcal{E'}, \alpha', \omega')}$. In the following theorem (Thm.~\ref{thm_bijection_of_uf_trees}) it is shown that two nodes $u, v \in \mathcal{V}= \bigcup_{t\in I}\mathcal{V}_t$ of $G$ are dynamic unfolding tree equivalent $u \sim_{DUT} v$ if and only if the affiliated nodes $u' := \textsc{makeStatic}(u), v' := \textsc{makeStatic}(v) \in \mathcal{V}'$ are unfolding equivalent $u' \sim_{AUT} v'$.
By definition, the dynamic unfolding trees of $u$ and  $v$ must be equal if and only if the unfolding trees of $u'$ and $v'$ are equal. Fig.~\ref{fig_dyn_unfolding_trees_equal_attrib_unforlding_trees} illustrates this theorem.

\begin{figure}[!ht]
    \centering
    \includegraphics[width=\linewidth]{figures/dynamic_unfolding_eq.pdf}
    \caption{Illustration of Thm.~\ref{thm_bijection_of_uf_trees}. In the bottom parts, the dynamic unfolding trees for two dynamic unfolding equivalent nodes are displayed from the dynamic and statified graph shown in the upper parts.\label{fig_dyn_unfolding_trees_equal_attrib_unforlding_trees}}
\end{figure}

\begin{Thm}\label{thm_bijection_of_uf_trees}
Let $G = (G_t)_{t\in I}$ be a dynamic graph and ${\textsc{makeStatic}(G) =: G' = (\mathcal{V'}, \mathcal{E'}, \alpha', \omega')}$ the static graph after the transformation. Furthermore, let $\mathcal{V}:= \bigcup_{t\in I}\mathcal{V}_t$ be the set of all nodes appearing in the graph sequence and $\tilde{\alpha}_v(t):= (\alpha_v(t), \rho)$ be the extended attribute function including a flag $\rho\in \{0, 1\}$ for the existence of a node at time $t$. Then for all $u,v \in \mathcal{V}$ and $d\in \mathbb{N}$ it holds
\begin{align*}
    (\bm{T}_{u}^d(t))_{t\in I} = \left(\bm{T}_{v}^d(t)\right)_{t\in I}  \Longleftrightarrow \bm{T}_{{u}}^d = \bm{T}_{{v}}^d.
\end{align*}
\end{Thm}
The proof can be found in Apx.~\ref{apx:proof_thm_bijection_of_uf_trees}.

Furthermore, analogously to Thm.~\ref{thm_bijection_of_uf_trees}, the bijection between a dynamic graph and its static version leads to the equivalence between the colorings resulting from the dynamic 1-WL test on the dynamic graph and the attributed 1-WL test on the static version of the graph. More precisely, two nodes in a dynamic graph have the same color for all the timestamps if and only if the colors of the affiliated nodes in the static graph after the \textsc{makeStatic} transformation are the same.

\begin{Thm}\label{thm_bijection_of_wl_tests}
Let $G = (G_t)_{t\in I}$ be a dynamic graph and ${\textsc{makeStatic}(G) =: G' = (\mathcal{V'}, \mathcal{E'}, \alpha', \omega')}$ the SAUHG resulting from a bijective graph type transformation.
Furthermore, let $\mathcal{V}:= \bigcup_{t\in I}\mathcal{V}_t$ be the set of all nodes appearing in the graph sequence of $G$ and $\tilde{\alpha}:\mathcal{V}\times I \rightarrow \mathcal{A}\,\times\! \perp$ with $\tilde{\alpha}_v(t):= (\alpha_v(t), \rho)$ be the extended attribute function for all nodes including a flag $\rho\in \{0, 1\}$ for the existence of a node at time $t$. Then for an iteration $i$ and $u,v\in\mathcal{V}$ it holds
\begin{align*}
    \left(c_{u}^{(i)}(t)\right)_{t\in I} = \left(c_{v}^{(i)}(t)\right)_{t\in I} \Longleftrightarrow c_{{u}}^{(i)} = c_{{v}}^{(i)}.
\end{align*}
\end{Thm}

The proof can be found in Apx.~\ref{apx:proof_thm_bijection_of_wl_tests} and is illustrated in Fig.~\ref{fig_dyn_wl_coloring}.

\begin{figure}[!ht]
    \centering
    \includegraphics[width=\linewidth]{figures/wl_coloring.pdf}
    \caption{(colored) Illustration of Thm.~\eqref{thm_bijection_of_wl_tests}. In the bottom parts, the dynamic 1-WL test is applied for the dynamic nodes of the dynamic graph $G$ (left side) and the attributed 1-WL test on the static nodes of the statified graph ${G' := \textbf{MakeStatic}(G)}$ (right side). One can see that two dynamic nodes are dynamic 1-WL equivalent if and only if the corresponding static nodes of the statification are attributed 1-WL equivalent. In this example, nodes a and c are dynamic WL equivalent due to the fact that they have the same color in each iteration and at each timestamp on the dynamic graph, as well as in each iteration in the statified graph (emphasized by the gray box).
    \label{fig_dyn_wl_coloring}}
\end{figure}

The next statement Cor.~\ref{cor:equivalence_DWL_DUT} follows directly from the equivalence between the unfolding trees of the dynamic graphs and their static versions determined in Thm.~\ref{thm_bijection_of_uf_trees}
and the equivalence between the WL coloring for the same graphs given in Thm.~\ref{thm_bijection_of_wl_tests}, as well as the equivalence of the attributed WL equivalence and the attributed unfolding tree equivalence formalized in Thm.~\ref{ue=wl}.

\begin{Cor}[Equivalence of Dynamic WL Equivalence and Dynamic UT Equivalence]\label{cor:equivalence_DWL_DUT}
Let $G_1 = (G^{(1)}_t)_{t\in I}$ and $G_2 = (G^{(2)}_t)_{t\in I}$ be dynamic graphs. Then $G_1$ and $G_2$ are dynamic WL equivalent if and only if they are dynamic unfolding tree equivalent, i.e.,
\begin{equation*}
    G_1 \sim_{DWL} G_2 \Longleftrightarrow G_1 \sim_{DUT} G_2.
\end{equation*}
\end{Cor}

\section{Introduction}
Graph data is becoming pervasive in many application domains, such as biology, physics, and social network analysis. Graphs are handy for complex data since they allow us to naturally encode information about entities, their links, and their attributes.
In modern applications, several different types of graphs are commonly used, and possibly combined: graphs can be homogeneous or heterogeneous, directed or undirected, have attributes on nodes and/or on edges, be static or dynamic, hyper- or multigraphs.
Interestingly, it has recently been shown that Static Attributed Undirected Homogenous Graphs (SAUHGs) with both attributes on nodes and edges  can act as a standard form for graph representation,
namely that all the common graph types can be transformed into SAUHGs without losing their encoded information~\cite{thomas2021graph}.

\medskip
Graph Neural Networks (GNNs) are a large class of relational models that can directly process graphs. Most of these models adopt a computational scheme based on a local aggregation mechanism.
The information relevant to a node is stored in a feature vector,
which is recursively updated by aggregating the feature vectors of neighboring nodes.
After $k$ iterations, the feature vector of a given node $v$ captures the structural information and the local information included within the $v$'s $k$--hop neighborhood. At the end of the iterative process, the node feature vectors can be used to classify/cluster the patterns represented by the nodes or the whole graphs.
The study of machine learning for graphs based on neural networks and local aggregation mechanisms started in the 90s with the proposal of some seminal models mainly designed for graph focused applications, including labelling RAAMs \cite{sperduti1993}, recursive neural networks \cite{jour_sperduti_1997,goller1996}, recursive cascade correlation networks \cite{micheli2002} and SOM for structure data \cite{hagenbuchner2003}.
In this paper, the Graph Neural Network model~\cite{jour_scarselli_2009} is the ancestor of the GNN class and is called Original GNN (OGNN). It is the first GNN designed to face both node/edge and graph-focused tasks.
Recently the interest in GNNs has rapidly grown, and a large number of new applications and models have been proposed, including neural networks for graphs \cite{micheli2009neural}, Gated Sequence Graph Neural Networks~\cite{ li2015gated}, Spectral Networks~\cite{bruna2013},
Graph Convolutional Neural Networks~\cite{kipf2016}, GraphSAGE~\cite{hamilton2017inductive}, Graph attention networks~\cite{GAT}, and Graph Networks~\cite{Battaglia2018}.
Another interesting extension of GNNs consisted in the proposal of several new models capable of dealing with dynamic graphs~\cite{kazemi_survey_dyn_gnn}, which, for instance, can be used to classify the following graph or the nodes of a sequence of graphs or to predict the insurgence of an edge in a graph.

\medskip
A great effort has been dedicated to studying the theoretical properties of GNNs and, in particular, their expressive power~\cite{Sato2020ASO}.
A goal of such a study is to define which graphs can be distinguished by a GNN, namely for which input graphs the GNN produces different encodings. In~\cite{xu2018powerful}, GNNs are proven to be as powerful as the Weisfeiler--Lehman graph isomorphism test (1--WL)~\cite{leman1968,wltest2011}.
Such an algorithm allows us to test whether two graphs are not isomorphi
\footnote{It is worth noting that the 1--WL test is not conclusive since there exist pairs of graphs that the test recognizes as isomorphic even if they are not.}. The 1--WL  algorithm is based on a graph signature that is obtained by assigning a color to each node. The graph coloring is achieved by iterating a local aggregation function.
More generally, a hierarchy of algorithms exists, called  1--WL, 2--WL, 3--WL, $\ldots$, whose elements recognize larger and larger classes of graphs.
It has been proven that a standard GNN model can simulate the 1--WL test, but it cannot implement higher tests; namely, 3--WL,  4--WL, and so on ~\cite{morris_2019_WL_go_neural}. Therefore, the  1--WL test exactly
defines the classes of graphs that GNNs can recognize.

\medskip
Another goal of the research on the expressive power of GNNs is to study GNN approximation capability.
Formally, in node-focused applications, a GNN implements a function $\varphi(\mathbf{G},v)\rightarrow \mathbb{R}^m$ that takes as input a graph $\mathbf{G}$ and returns an output at each node. Similarly, in graph-focused tasks, a GNN implements a function $\varphi(\mathbf{G})\rightarrow \mathbb{R}^m$.
In both cases, the study's objective is to define which classes of functions can be approximated by a GNN model.

Intuitively, existing results suggest, provided that a sufficiently general aggregation function is used, GNNs are universal approximators on graphs except for the following constraint: a GNN must produce the same
output  $\varphi(\mathbf{G},v)$ on a pair of nodes $v=v_1, v_2$ that can be distinguished neither for their features nor for their neighborhoods.
Such a concept can be formally captured in two ways. In most of the recent results, it has been observed that if  1-WL gives the same colors to  $v_1, v_2$ then a GNN produces the same outputs on them: this fact
can be defined by affirming that $v_1, v_2$ are equivalent according to  1-WL. On the other hand, in~\cite{scarselli2008computational}, which is dedicated to studying the expressive power of the OGNN, the concepts of unfolding trees and unfolding equivalence were adopted.
The unfolding tree $\mathbf{T}_v$, with root node $v$, is constructed by unrolling the graph starting from that node\footnote{Currently, the concept underlying unfolding trees is widely used to study the GNN expressiveness, even if they are mostly called {\em computation graphs}~\cite{garg2020generalization}.}.
Intuitively, $\mathbf{T}_v$ exactly describes the information used by the GNN at node $v$.
The unfolding equivalence is, in turn, an equivalence relationship defined between nodes having the same unfolding tree: obviously, a GNN cannot distinguish $v_1, v_2$  if they are unfolding equivalent.
Interestingly, it has been proven recently \cite{d2021unifying} that
1-WL and the unfolding equivalences are equal; namely they induce the same relationship between nodes. Thus, 1-WL and the unfolding equivalences can be used interchangeably.

\medskip
Formally, in~\cite{scarselli2008computational}, it has been proven that OGNNs can approximate in probability, up to any degree of precision, any measurable function $\tau(\mathbf{G},v)\rightarrow \mathbb{R}^m$  that respects the unfolding equivalence. Such a result has been recently extended to a large class of GNNs~\cite{d2021unifying} called message passing GNNs, which includes most of the contemporary architectures.
Similar results show that the functions implemented by message passing GNNs~\cite{xu2018powerful,azizian2020expressive},  Linear Graph Neural Networks~\cite{azizian2020expressive,maron2018invariant} and Folklore Graph Neural Networks~\cite{maron2019provably} are dense in continuous functions
on graphs modulo 1-WL.
Interestingly, the most recent results differ for the technique adopted in the proof, which can be based on a partitioning of the input space~\cite{d2021unifying} or Stone-Weierstrass theorem~\cite{xu2018powerful,azizian2020expressive,maron2018invariant,d2021unifying}. Such techniques have advantages and disadvantages.
Stone-Weierstrass provides a more elegant proof that holds for continuous target functions.
Space partitioning provides a constructive proof, allowing us to deduce information about the GNN  architectures that can achieve the desired approximation. Moreover, with the latter technique, the proof holds in probability so that it can also be applied to discontinuous target functions.

\medskip
Despite the availability of the mentioned results on the expressive power of GNNs, their application is still limited to undirected static graphs with attributes on nodes. This is particularly restrictive since modern applications usually involve much more complex data structures, such as heterogeneous, directed, dynamic graphs and multigraphs.
Even if, intuitively, one may expect that GNNs can be universal approximators over those extended domains, it is not apparent which GNN architectures can achieve such a universality. So the question is how the definition of the 1-WL test has to be modified to cope with such novel data structures and whether the universal results fail for some particular graph type.

\medskip
In this paper,  we propose a study on the expressive power of GNNs for two exciting domains, namely dynamic graphs and SAUHGs with node and edge attributes. Dynamic graphs are interesting from a practical and a theoretical point of view. They are used in several application domains.
 Moreover, dynamic GNN models are structurally different from common GNNs, and the results and the methodology required to analyze their expressive power cannot directly be deduced from existing literature.
On the other hand, SAUHGs with node and edge attributes are interesting because, as mentioned above,  they act as a standard form for several other types of graphs that all can be transformed to SAUGHs~\cite{thomas2021graph}.

\medskip
To construct the fundamental theory for both types of domains, appropriate versions of the 1--WL test and the unfolding equivalence are introduced, and we discuss how they are related.
Then, we consider generic GNN models that can operate on such domains, and we prove that they are universal approximators modulo the aforementioned 1--WL/unfolding equivalences. More precisely, the main contributions of this paper are as follows.

\begin{itemize}
    \item We present new versions of the 1--WL test and of the unfolding equivalence that are appropriate for dynamic graphs and SAUHGs with node and edge attributes, and we show that they induce the same equivalences on nodes. Such a result makes it possible to use them interchangeably to study the expressiveness of GNNs.
    \item
    We show that generic GNN models for dynamic graphs and SAUHGs with node and edge attributes are capable of approximating, in probability and up to any precision, any measurable function on graphs that respects the 1-WL/unfolding equivalence.
    The work extends the state-of-the-art results available on approximation capability of GNNs to the two domains, maintaining the best generality and providing information about the architecture achieving the approximation. The result on approximation capability holds for graphs with unconstrained features of reals and measurable target functions.
Thus,  most of the domains used in practical applications are included. Moreover, the proof is based on space partitioning, which is constructive in nature and allows us to deduce information about the GNN architecture that can achieve the desired approximation.
For example, it is shown that, provided that the GNN is endowed with sufficiently general aggregation and combination functions, the approximation is achieved in $r+1$ iterations and that a hidden feature of dimension $1$ is sufficient.
\end{itemize}

The rest of the paper is organized as follows. Section~\ref{related_work}  illustrates the related literature. In section~\ref{section_preliminaries}, the notation used throughout the paper is described and the main definitions are introduced. In section~\ref{section_equivalences}, we introduce the 1--WL test and unfolding equivalences suitable for dynamic graphs and SAUHGs with node and edge attributes and prove that those equivalences are equal. In section~\ref{section_approximation}, the approximation theorems for GNNs on both graph types are presented. Finally, section~\ref{section_conclusion} includes our conclusions and future matter of research. For the sake of simplicity, all of the proofs are collected in the appendix \ref{section_appendix}.
\section{Weisfeiler-Lehmann Hierarchy}\label{section_WL_hierarchy}

In this section we aim to position the attributed WL tests into the Weisfeiler Lehmann Hierarchy.

\begin{Thm}\label{thm_1WL_vs_attrib_1WL}
1-WL test $\subsetneq$ attributed 1-WL test
\end{Thm}

\begin{proof} First we show that 1-WL test is a subset of the attributed 1-WL test and then we give a counter example for them being equal.
\begin{itemize}
    \item[$\subset$] Due to Thm.~\ref{ue=wl} the WL test is equivalent to the unfolding tree equivalence. Therefore, the equality of the attributed trees leads to an equality in those trees underlying tree structure,  i.e., if two graphs are attributed-wise unfolding equivalent they are unfolding equivalent. Hence, if two graphs are attributed-wise WL equivalent, they are 1-WL equivalent.
    \item[$\neq$] In Fig.~\ref{fig_limitations_dynamic_WL} one can see that the attributed WL test can distinguish the first and last graph (graphs a and c), while the 1-WL test fails.
\end{itemize}
\end{proof}

\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{figures/limitation_dyn_WL.pdf}
    \caption{The graphs a) and b) are falsely recognized as 1-WL and attributed 1-WL isomorphic; same holds for the 3-WL and 3-AWL. The graphs b) and c) are falsely recognized isomprohic just by the 1-WL/3-WL test while the 1-AWL/3-AWL test correctly recognizes both graphs as non isomorphic. The same result holds for the graphs b) and c) for 1-WL and 1-AWL while 3-WL and 3-AWL can distinguish both. The 1-WL and 3-WL equivalences on the graphs from a) and b) and a) and c) without attributes are taken from \cite[§3.1]{Sato2020ASO}}.
    \label{fig_limitations_dynamic_WL}
\end{figure}

\begin{Cor}
2-WL test $\subsetneq$ attributed 1-WL test
\end{Cor}
\begin{proof}
As stated in \cite[§3.5, Cor.~3.5.8]{grohe2017descriptive}, 1-WL test and 2-WL test are equivalent.
\end{proof}

\begin{Cor}
k-WL test $\subsetneq$ attributed k-WL test.
\end{Cor}
\begin{proof}
Follows analogously from the proof of Thm.~\ref{thm_1WL_vs_attrib_1WL}.
\end{proof}
\textcolor{orange}{Here, we have the same problem of the previous theorem. The inequality is obvious, but can we prove for non isomorphic graphs? }

\begin{Cor}
The dynamic k-WL test $\subseteq$ dynamic (k+1)-WL test.
\end{Cor}
\begin{proof}
Follows immediately from the static Weisfeiler-Lehmann Hierarchy.
\end{proof}
\textcolor{orange}{}
\begin{Thm}
The 3-WL test and the attributed 1-WL test cannot be compared regarding to the Weisfeiler Lehmann Hierarchy.
\end{Thm}

\begin{Thm}
Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, \alpha_1)$ and $G_2 = (\mathcal{V}_2, \mathcal{E}_2, \alpha_2)$ be to graphs with $G_1 \nsim_{WL} G_2$. Then there exists at least one $\omega_1, \omega_2$ such that $G_1 \nsim_{AWL} G_2$.
\end{Thm}

\begin{proof}
THATS SO TRIVIAL, because I can just set $\omega_i(\mathcal{E}) \mapsto x$ for a fix but arbitrary $x \in B$ , or not?
\end{proof}

\begin{proof}
In Fig.~\ref{fig_limitations_dynamic_WL} one can see that the 3-WL test can distinguish the graphs a) and b) but the attributed 1-WL test cannot. However, the 3-WL test cannot distinguish the graphs b) and c) while the attributed 1-WL test can.
\end{proof}

\begin{paragraph}{Remark.} Another comparison we haven't talked about yet is between the dynamic 1-WL test and the attributed 1-WL test. In fact, these two tests refer to mathematically different objects. The dynamic 1-WL test is defined only on dynamic nodes of dynamic graphs, while the attributed 1-WL test is defined on static nodes of static graphs.
Therefore, they cannot be related with respect to the Weisfeiler-Lehmann hierarchy. In other words, this hierarchy is only a partial order and not a total order when all possible WL tests and extensions are considered.
\end{paragraph}

\section{Notation and Preliminaries}\label{section_preliminaries}
Before extending the work about the expressive power of GNNs to dynamic and edge attributed graph domains,
the mathematical notation and preliminary definitions are given in this chapter. In this paper, only finite graphs are under consideration.
\medskip

\tablehead{\hline\textbf{Notation table} & \\}\label{tab_notation}
\begin{supertabular}{|l|l|}
	\hline
	$\mathbb{N}$ & natural numbers\\
	$\mathbb{N}_0$ & natural numbers starting at $0$\\
	$\mathbb{R}$ & real numbers\\
	$\mathbb{R}^k$ & $\mathbb{R}$ vector space of dimension $k$\\
	\hline
	$|a|$ & absolute value of a real $a$ \\
	$\|\cdot \|$ & norm on $\mathbb{R}$ \\
	$|M|$ & number of elements of a set $M$\\
	$[n], \,n\in \mathbb{N}$ & sequence $1,2,\ldots, n$ \\
	$[n]_{0}, \,n\in \mathbb{N}_{0}$ & sequence $0,1,\ldots, n$ \\
	\hline
	$\emptyset$ & empty set\\
	$\{\cdot\}$ & set \\

	$\{\!\vert\cdot\vert\!\}$ & multiset, i.e. set allowing \\
	& multiple appearances of entries\\
	$\sms{\cdot}$ & sorted multiset\\
	$(x_i)_{i \in I}$ & vector of elements $x_i$ \\
	& for indices in set $I$\\

	\hline
	$\wedge$ & conjunction \\
	$\cup$ & union of two (multi)sets\\

	$\subseteq$ & sub(multi)set \\
	$\subsetneq$ & proper sub(multi)set \\
	$\times $ & factor set of two sets\\
	\hline

\end{supertabular}

\vspace{0.2cm}

\noindent
In \cite{thomas2021graph} it has been proven that several types of graphs can be transformed to SAUGHs with node and edge attributes.
Therefore, SAUHGs will be used as a standard form for all the types of graphs defined in the following.

\begin{NDef}[Different Graph Types]\label{def_different_graph_types}
The elementary graphs are defined in \cite{thomas2021graph} as follows.
\begin{compactenum}

		\item A \textbf{directed graph (digraph)} is a tuple $G=(\set{V}, \set{E})$ containing a set of nodes $\set{V}\subset\mathbb{N}$ and a set of directed edges given as tuples $\set{E}\subseteq\set{V}\times\set{V}$.
		As the set of nodes $\mathcal{V} \subset \mathbb{N}$, each node is provided with an \textbf{identifier}, which is simply the natural number with which is represented; the identifier could be used to create an ordering of the nodes.
		\item A \textbf{(generalized) directed hypergraph} is a tuple $G=(\set{V},\set{E})$ with nodes $\set{V}\subset\mathbb{N}$ and hyperedges\\ $	\set{E}\subseteq \{(\hypset{x},f_i)_i\mid \hypset{x}\subseteq\set{V},\, f_i\mathbin{:}\hypset{x}\rightarrow\mathbb{N}_0\}$
		 that include a numbering map $f_i$ for the $i$-th edge $(\hypset{x},f)_i$ which indicates the order of the nodes in the (generalized) directed hyperedge.
	\end{compactenum}

An elementary graph $G = (\set{V}, \set{E})$ is called
	\begin{compactenum}
		\item \textbf{undirected} if the directions of the edges are irrelevant, i.e.,
		\begin{itemize}

	\item for directed graphs: if $(u,v) \in \set{E}$ whenever $(v,u)\in\set{E}$ for $u,v\in\set{V}$. Then an abbreviation can be the set data type instead of tuples, namely $
		\set{E}\subseteq\{\{u,v\}\,|\,u,v\in\set{V}, u\neq v\}\cup\{\{u\}\mid u\in\set{V}\}\footnote{the second set contains the set of self-loops},$

			\item for directed hypergraphs: if $f_i\mathbin{:}\hypset{x}\rightarrow 0$ for all $(\hypset{x},f_i)_i\in\set{E}$\footnote{$f_i(\hypset{x})=0$ encodes that $\hypset{x}$ is an undirected hyperedge}. Abbreviated by $\set{E}\subseteq\{ \hypset{x}\mid \hypset{x}\subseteq\set{V}\}$.
		\end{itemize}
		\item \textbf{multigraph} if it is a multi-edge graph, i.e., the edges $\set{E}$ are defined as a multiset, a multi-node graph, i.e., the node set $\set{V}$ is a multiset, or both.
			\item \textbf{heterogeneous} if the nodes or edges can have different types. Mathematically, the type is appended to the nodes and edges. I.e., the node set is determined by $
		\set{V}\subseteq\mathbb{N}\times \set{S}$ with a node type set $\set{S}$ and thus, a node $(v,s)\in\set{V}$ is given by the node $v$ itself and its type $s$. The edges can be extended by a set $\set{R}$ that describes their types, to $(e,r)\ \forall\, e\in\set{E}\text{ of edge type }r\in\set{R}$.
		\item \textbf{attributed} if the nodes $\set{V}$ or edges $\set{E}$ are equipped with node or edge attributes\footnote{In some literature attributes are also called features.}. These attributes are formally given by a node and edge attribute function, respectively, i.e. $\alpha:\set{V}\rightarrow\set{A}$ and $\omega:\set{E}\rightarrow \set{W}$,
		where $\set{A}$ and $\set{W}$ are arbitrary attribute sets.
	\end{compactenum}
\end{NDef}

Recall that, for any graph type, a graph $G=(\mathcal{V}, \mathcal{E})$ is called \textbf{bounded} if $\exists K \in \mathbb{N}$ s.t. $\max\limits _{G \in \mathcal{G}} |G| \leq K$, where $|G|$ is the cardinality of the set $\mathcal{V}$ of nodes.\\

\noindent Since all the graph types introduced in Def.~\ref{def_different_graph_types} are static, but temporal changes (dynamics) play an essential role in learning on graphs representing real-world applications, the dynamic graphs are defined in the following.
In particular, the dynamic graph definition here consists of a discrete-time representation.

\begin{NDef}[Dynamic Graph]\label{def_discrete_dynamic_graph}
Let $T= \{t_i\}_{i\in I}\subsetneq\mathbb{R}$ with $I=[0, \ldots, l]\subsetneq  \mathbb{N}$ be a set of timestamps. Each timestamp $t_i$ can be bijectively identified by its index $i$. Without loss of generality, from now on we refer to the set of timestamps as $I$.
Then a \textbf{(discrete) dynamic graph} can be considered as a vector of static graph snapshots, i.e., $G = (G_t)_{t\in I}$, where $G_{t} = (\mathcal{V}_t, \mathcal{E}_t) \; \forall t \in I$.
Furthermore,
\begin{align*}
    \alpha_{v}(t) :=
    \begin{cases}
             \alpha(v,t), &\quad v \in \mathcal{V}_t \\
             \perp, &\quad \text{otherwise}
    \end{cases}
    \quad \text{and} \quad
\end{align*}
\begin{align*}
    \omega_{\{u,v\}}(t) :=
    \begin{cases}
             \omega(\{u,v\},t), &\quad \{u,v\} \in \mathcal{E}_t \\
             \perp, &\quad \text{otherwise}
    \end{cases}
\end{align*}

where $\alpha : \mathcal{V} \times I  \rightarrow \mathcal{A}\; \cup \perp$ and $\omega : \mathcal{E} \times I \rightarrow \mathcal{B} \; \cup \perp$ define the vector of \textbf{dynamic node/edge attributes}.

In particular, $\alpha_v(t)=\perp$ means that at the timestamp $t$ the node $v$ doesn't exist. In the same way, $\omega_{\{u,v\}}(t)=\perp$ encodes the absence of the edge at that time.
Moreover, let
\begin{align*}
    \Omega_{ne_v}(t) &= \left({\;{\omega_{\{v, x_1\}}(t), \ldots,  \omega_{\{v, x_{|ne_v(t)|}\}}(t)\; }  \;}\right)_{t\in I}

\end{align*}
be the sequence of \textbf{dynamic edge attributes of the neighborhood}  corresponding node at each timestamp.

\end{NDef}

The following definition introduces a static, nodes/edges attributed, undirected and homogeneous graph, called SAUHG. The reason for defining and using it comes from \cite{thomas2021graph}. Here, it is shown, that every graph type is transformable into each other. Thus, it suffices to consider only one graph type in which all graph types are easily transformable to extend the universal approximation theorem to all graph types defined in Def.~\ref{def_different_graph_types} and Def.~\ref{def_discrete_dynamic_graph}.

\begin{NDef}[Static Attributed Undirected Homogeneous Graphs]\label{def_sauhg}
$G'$ is called \textbf{static, nodes/edges attributed, undirected, homogeneous graph (SAUHG)} if $G'=(\mathcal{V}, \mathcal{E}, \alpha, \omega)$, with $\mathcal{V} \subset \mathbb{N}$ is a finite set of nodes, $\mathcal{E} \subset \{\{u,v\} \mid \forall\, u,v \in \mathcal{V} \}$ is a finite set of edges, and node and edge attributes determined by the mappings ${\alpha\, :\, \mathcal{V} \rightarrow \mathbb{R}^k,\ \omega\, :\, E \rightarrow \mathbb{R}^k}$ that map w.l.o.g. into the same $k$-dimensional attribute space.
The domain of SAUGHs will be denoted as $\mathcal{G}$.
\end{NDef}

There exists a bijective transformation from any arbitrary graph type defined in Def.~\ref{def_different_graph_types} to the SAUHG. They result from concatenating graph type transformations for single graph properties from \cite{thomas2021graph}. In particular, a dynamic graph can be transformed into a static one through the ${\textsc{makeStatic}}$ transformation, which encodes the dynamical behaviour of the graph into a time series of node and edge attributes accordingly.

Next, the definition of a GNN that can handle static node-attributed undirected homogeneous graphs is given from \cite{xu2018powerful}. Here, the node attributes $\alpha_v$ of a node $v \in \mathcal{V}$ are used as the initial representation and input to the GNN. The update is executed by an AGGREGATION over the representations of the neighbouring nodes. In the $i$-th layer of the GNN, the nodes hidden representation is encoded in an embedding vector $\bm{h}_v$ containing both the local structural information and the node information within the $i$-hop neighborhood. Dependent on the learning problem under consideration, a READOUT function is used to obtain a suitable output $\bm{z}_v$. The entire GNN propagation scheme is defined as follows.

\begin{NDef}[Graph Neural Networks]\label{def_GNN}
The GNN propagation scheme in one iteration $i\in J$ for the representation of a node $v$ is defined as

{\small\begin{equation*}
    \bm{h}_v^i = \text{COMBINE}^{(i)}\left( \bm{h}_v^{(i-1)}, \text{AGGREGATE}^{(i)}\left(\{ \bm{h}_u^{(i-1)}\mid u\in ne_v\} \right)\right)
\end{equation*}}

The output for a node specific learning problem after the last iteration $l$ is given by
\begin{align*}
    \bm{z}_v = \text{READOUT}\left( \bm{h}_v^l\right)
\end{align*}
using a selected AGGREGATION scheme and a suitable READOUT function and the output for a graph specific learning problem is determined by
\begin{align*}
    \bm{z} = \text{READOUT}\left( \{\bm{h}_v^l\mid v \in \set{V}\}\right).
\end{align*}
\end{NDef}

The GNNs expressivity is studied in terms of their capability of distinguishing two non isomorphic graph.

\begin{NDef}[Graph Isomorphism]\label{def_graph_iso}
Let $G_1$ and $G_2$ be two static graphs, then $G_1=(\set{V}_1, \set{E}_1)$ and $G_2=(\set{V}_2, \set{E}_2)$ are \textbf{isomorphic} to each other $G_1 \approx G_2$, if and only if there exists a bijective function $\phi: \mathcal{V}_1 \rightarrow \mathcal{V}_2$, with
 \begin{compactenum}
     \item $v_1 \in \mathcal{V}_1 \; \Longleftrightarrow \; \phi(v_1) \in \mathcal{V}_2\ \quad \forall \; v_1 \in \mathcal{V}_1$,
     \item $\{v_1, v_2\} \in \mathcal{E}_1 \; \Longleftrightarrow \; \{\phi(v_1), \phi(v_2)\} \in \mathcal{E}_2 \quad \forall \; \{v_1, v_2\} \in \mathcal{E}_1$
 \end{compactenum}

In case the two graphs are attributed, i.e.~ $G_1=(\set{V}_1, \set{E}_1, \alpha_1, \omega_1)$ and $G_2=(\set{V}_2, \set{E}_2, \alpha_2, \omega_2)$, then $G_1 \approx G_2$ if and only if additionally there exist bijective functions $\varphi_{\alpha} : A_1 \rightarrow A_2$ and $\varphi_{\omega} : B_1 \rightarrow B_2$ with $A_i := \text{im}(\alpha_i)$ and $B_i := \text{im}(\omega_i)$, $i = 1, 2$.
\begin{compactenum}
\item $\varphi_{\alpha}(v_1) = \alpha_2(\phi(v_1)) \quad \forall \; v_1 \in \mathcal{V}_1$,
\item $\varphi_{\omega}(\{u_1, v_1\}) = \omega_2(\phi(u_1), \phi(v_1)) \quad \forall \; \{u_1, v_1\} \in \mathcal{E}_1$.
\end{compactenum}
\end{NDef}

Graph isomorphism (GI) gained prominence in the theory community when it emerged as
one of the few natural problems in the complexity class NP that could neither be classified as being hard (NP-complete) nor shown to be solvable with an efficient algorithm (that is, a polynomial-time algorithm) \cite{grohe2020graph}. Indeed it lies in the class NP-Intermidiate.
However, in practice, the so-called Weisfeiler-Lehman (WL) test is used to at least recognize non-isomorphic graphs. If the WL test outputs two graphs as isomorphic, the isomorphism is likely but not given for sure. \\
There are many different extensions of the WL test, e.g., n-dim.~WL test, n-dim folklore WL test or set n-dim.~WL test \cite{Sato2020ASO}. However, introducing all of them is out of the scope of this paper, so in the following we only introduce the 1-WL test, on which all other WL tests are based.

In general, the 1-WL test is based on a graph coloring algorithm. The coloring is applied in parallel on the nodes of the two input graphs and at the end the number of color used per each graph are counted. Then, two graphs are detected as non-isomorphic if these numbers do not coincide, whereas when the numbers are equal, the graphs are possibly isomorphic.

\begin{NDef}[1-WL test]\label{def_1_WL_test}
Let HASH be a bijective function that codes every possible node attribute with a color and $G = (\mathcal{V}, \mathcal{E}, \alpha)$. Then, the \textbf{1-WL} test is recursively defined on the graph nodes by
\begin{itemize}
    \item At iteration $i=0$ the color is set to the hashed node attribute:
    \begin{align*}
        o_v^{(0)} = \text{HASH}(\alpha_v)
    \end{align*}
    \item For any other iteration $i>0$ it holds
    \begin{align*}
        o_v^{(i)} = \text{HASH}\Bigl( \bigl( o_v^{(i-1)}, o_{ne_v}^{(i-1)}\bigr)\Bigr)
    \end{align*}
\end{itemize}
The algorithm terminates if the number of colors between two iterations does not change, i.e., if
\begin{align*}
    |\{o_v^{i} \mid v \in \mathcal{V}\}| = |\{o_v^{i+1} \mid v \in \mathcal{V}\}|.
\end{align*}
\end{NDef}

It is reasonable to define two graphs as equivalent if their node colors result in the same stable position. Formally, this concept leads to the following expression of WL-equivalence.

\begin{NDef}[WL-equivalence]\label{def_wl_equivalence}
Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, \alpha_1)$ and $G_2 = (\mathcal{V}_2, \mathcal{E}_2, \alpha_2)$ be two graphs. Then $G_1$ and $G_2$ are  \textbf{WL-equivalent}, noted by $G_1 \sim_{WL} G_2$, if and only if for all nodes $v_1 \in \mathcal{V}_1$ there exists a corresponding node $v_2 \in \mathcal{V}_2$ with $o_{v_1} = o_{v_2}$.
\end{NDef}

Note, that in terms of the GNN expressive power, the GNN is as powerful as the WL test if the hidden embedding representation of two graphs is different in case the input graphs are not equal regarding the WL test.
However, another way to check the graph isomorphism of two graphs and therefore compare the GNN expressivity is to considers the so-called unfolding trees of all their nodes. An unfolding tree consists of a tree constructed by a breadth-first visit of the graph, starting from a given node.
Two graphs are possibly isomorphic if all their unfolding trees are equal.
For this purpose, the following two definitions introduce the notion of an unfolding tree and the concept of unfolding tree equivalence.

\begin{NDef}[Unfolding Trees]\label{def_unfolding_Tree}
The \textbf{unfolding tree} $\bm{F}_{v}^d$ in graph $G = (\mathcal{V}, \mathcal{E}, \alpha)$ of node $v \in \mathcal{V}$ \textbf{up to depth} $d \in \mathbb{N}$ is defined as
\begin{align*}
    \bm{F}_{v}^d =
    \begin{cases}
        Tree(\alpha_{v}), \quad \text{if } d = 0 \\
        Tree\bigl(\alpha_{v}, \bm{F}^{d-1}_{ne_v}\bigr) \quad \text{if } d > 0\,,
    \end{cases}
\end{align*}
where ${Tree(\alpha_{v})}$ is a tree constituted of node $v$ with attribute $\alpha_v$. Furthermore, $Tree\bigl(\alpha_{v}, \bm{F}^{d-1}_{ne_v}\bigr)$ is the tree with root node $v$ and subtrees $\bm{F}^{d-1}_{ne_v} = \multiset{\bm{F}_{u_1}^{d-1}, \ldots, \bm{F}_{u_{|ne_v|}}^{d-1}}$ with roots in the neighbors of $v$ of depth $d-1$ if $\alpha_v\neq \, \perp$ or empty otherwise.

Moreover, the \textbf{unfolding tree} of $v$ determined by $\bm{F}_v = \lim_{d \rightarrow \infty} \bm{F}_v^d$ is obtained by merging all unfolding trees $\bm{F}^d_v$ of any depth $d$.
\end{NDef}

\begin{NRem}\label{rem_multiset_vs_sorted_multiset}
Note that in the aforementioned definition the subtrees are given by a multiset. Indeed this is essential since there might be nodes within a graph which induce equal unfolding trees. However, for some applications or graph types, e.g.~positional graphs where the neighbourhood of each node is sorted by some given order, it could be necessary to use a sorted multiset.
\end{NRem}

Analogous to the WL equivalence between two graphs with the new approach of computing the unfolding trees of the nodes of each graph leads to the notion of unfolding equivalence between two graphs which is defined as follows.

\begin{NDef}[Unfolding Tree Equivalence]\label{def_unfolding_tree_equivalence}
Two nodes $u$, $v$ are said to be \textit{unfolding equivalent} $u \backsim_{ue} v$, if $\mathbf{F}_u = \mathbf{F}_v$. Moreover,let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, \alpha_1)$ and $G_2 = (\mathcal{V}_2, \mathcal{E}_2, \alpha_2)$ be two graphs. Then $G_1$ and $G_2$ are \textbf{unfolding tree equivalent}, or short \textbf{unfolding equivalent}, noted by $G_1 \sim_{UT} G_2$, if and only if $\multiset{\bm{F}_u \mid u \in \mathcal{V}_1} = \multiset{\bm{F}_v \mid v \in \mathcal{V}_2}$.
\end{NDef}

Interestingly enough, in \cite{d2021unifying}, it has been shown that the 1–WL test induces an equivalence
relationship on the graph nodes that exactly equals the
unfolding equivalence.

\medskip
Returning to the expressive power of GNNs, the study of their approximation capability, is an interesting topic.
It generally analyzes the capacity of different GNNs models to approximate arbitrary functions \cite{bronstein_geometric_DL}.
Different universal approximation theorems can be defined depending on the model, the considered input data and the sets of functions. This paper will focus on the set of functions that preserve the unfolding tree equivalence which is defined as follows.

\begin{NDef}\label{def_function_preserves_uf_equivalence}
Let $\mathcal{D}$ be the domain of bounded graphs, $\bm{G}=(\mathcal{V}, \mathcal{E})\in\mathcal{G}$ a graph and $u,v\in \mathcal{V}$ two nodes. Then a function $f: \mathcal{G} \rightarrow \mathbb{R}^m$ is said to \textbf{preserve the unfolding equivalence} on $\mathcal{G}$ if
\begin{equation*}
v \sim_{UT} u \Rightarrow f(\mathbf{G},v)=f(\mathbf{G}, u).
\end{equation*}
All functions that preserve the unfolding equivalence are  collected in the set $\mathcal{F}(\mathcal{D})$.
\end{NDef}

To conclude this section, finally the universal approximation theorem for unattributed undirected graphs and a message-passing GNN defined in Def.~\ref{def_GNN} is given to show that this model can approximate any function that preserves the unfolding equivalence (Def.~\ref{def_function_preserves_uf_equivalence}) in probability and up to any precision.

\begin{NThm}[Universal Approximation Theorem \cite{d2021unifying}]\label{theorem_universal_approx_thm}
Let $\mathcal{D}$ be a domain that contains graphs, with ${r= \max\limits_{G \in \mathcal{D}} \text{diam}(\mathbf{G})}$.  For any measurable function
$\tau \in \mathcal{F}(\mathcal{D})$ preserving
the unfolding equivalence, any norm $\| \cdot \|$ on $\mathbb{R}$, any probability measure $P$
on $\mathcal{D}$, for any reals $\epsilon, \lambda$ where $\epsilon >0$, $0 < \lambda < 1$, there exists a GNN defined by the continuously differentiable functions $\text{COMBINE}^{(k)}$, $\text{AGGREGATE}^{(k)}$, $\forall k \leq r+1$, and by the function
$\text{READOUT}$, with feature dimension $m=1$, i.e,  $h_v^k\in\mathbb{R}$, such that the function
$ \varphi$  (realized by the GNN) computed after $r+1$ steps
satisfies the condition
\begin{equation*}
P( \| \tau(\mathbf{G},v)- \varphi( \mathbf{G},v) \| \geq \varepsilon) \leq 1- \lambda.
\end{equation*}
\end{NThm}

Since the results in this section hold for undirected and unattributed graphs, we aim to extend the universal approximation theorem to GNNs working on SAUHGs (cf.~Def.~\ref{def_sauhg}) and dynamic graphs (cf.~Def.~\ref{def_discrete_dynamic_graph}). For this purpose, in the next sections we introduce a static attributed and a dynamic version of both the WL test and the unfolding trees to show that the graph equivalences regarding the attributed/dynamic WL test and attributed/dynamic unfolding trees are equivalent. With these notions, we define the set of functions that are attributed/dynamic unfolding tree preserving and reformulate the universal approximation theorem to the attributed and dynamic cases (cf.~Thm.~\ref{theorem_universal_approx_sauhg} and Thm.~\ref{dyn_thm_approximation}).
\section{Related Work}\label{related_work}
The Weisfeiler-Lehman test and its variants have been exploited in a wide variety of GNN models since \cite{xu2018powerful} showed that message passing GNNs are as powerful as the 1--WL test. To overcome the limit of 1--WL, a new GNN model is introduced in \cite{you2021identity}, where node identities are directly injected into the Weisfeiler-Lehman aggregate functions.
In \cite{morris_2019_WL_go_neural}, the k-WL test has been taken into account to develop a more powerful GNN model, given its greater capability to distinguish non-isomorphic graphs.
In \cite{bodnar2021weisfeiler}, a simplicial-wise Weisfeiler-Lehman test is introduced, and it is proven to be strictly more powerful than the 1-WL test and not less powerful than the 3-WL test; a similar test (called cellular WL test) proposed by \cite{bodnar2021weisfeiler_c} is proven to be actually more powerful than the simplicial version.
Nevertheless, all this proposed tests do not deal with edge-attributed graphs, certainly not with dynamic graphs.

Moreover, the WL test mechanism applied to GNNs has been also studied within the paradigm of \textit{unfolding trees} (\cite{Sato2020ASO}, ~\cite{zhang2021nested}). However, only recently it has been established an equivalence between the two concepts by \cite{d2021unifying}, and still, it is limited to static graphs without edge attributes.

By a theoretical point of view, several approaches have been carried out to study the approximation and generalization properties of graph neural networks. In \cite{scarselli2008computational}, the authors proved  the universal approximation properties of the original graph neural network model, \textit{modulo} the unfolding equivalence. Universal approximation is shown for GNNs with random node initialization in \cite{abboud2020} while, in~\cite{xu2018powerful}, GNNs are shown to be able to encode any graph with countable input features. Moreover, the authors of \cite{dasoulas2019coloring} proved that GNNs, provided with a colored local iterative procedure (CLIP), can be universal approximators for functions on graphs with node attributes.
The approximation property has been extended also to Folklore Graph Neural Networks in~\cite{maron2019provably} and to Linear Graph Neural Networks and general GNNs in \cite{azizian2020expressive,maron2018invariant}, both in the invariant and equivariant case. Recently, the universal approximation theorem has been proved for modern message passing graph neural networks by \cite{d2021unifying}.
Despite the availability of universal approximation theorems for static graphs with node attributes, the theory lacks results about approximation capability of other types of graphs such as dynamic graphs and graphs with attributes on both nodes and edges. \\
The aim of this paper, is that of extending the results on the expressive power
of GNNs for dynamic graphs
and SAUHGs with node and edge attributes.

redpajama_set_name: RedPajamaArXiv