\section{Properties of the NACF}
\label{sec: bounds}
The NACF given by \eqref{eq:nacf definition} computes the network autocorrelation for an observed realisation. It considers an underlying network structure and calculates the sample autocorrelation for a possible choice of \mbox{$h$-lag} and \mbox{$r$-stage} adjacency. It bounds the autocovariance in the network structure by noting that the weight matrix $( \bmat{W}_{t} \odot \bmat{S}_r + \bmat{I_d} \big )$ selects the nodes that are considered for neighbourhood regression and assigns coefficients to said linear combinations. These are upper bounded by considering all nodes which correspond to the paths given by $\bmat{W}_t$. To prove Proposition \ref{prop: nacf one} we will use the following proposition.
\begin{proposition} \label{prop: nacf inequality}
    Let $\boldsymbol{Y} \in \mathbb{R}^d$ be a vector where each component corresponds to a mean-zero realisation value for a node in a network time series at time $t$ (i.e., $\boldsymbol{y} = \boldsymbol{X}_t - \boldsymbol{\overline{X}}$). Also, let $\bmat{W}_{t} \in \mathbb{R}^{d \times d}$ be the weights matrix for the given graph $\mathcal{G}$ and $\bmat{S}_r \in \mathbb{R}^{d \times d}$ be the stage adjacency matrices. If we set 
    $$\lambda_t = \underset{j = 1, \dots, d}{\max} \bigg \{ \sum_{i = 1}^d [\bmat{W}_{t} \odot \bmat{W}_t]_{i j} \bigg \}^{1/2}, $$ 
    then we have that 
    \begin{equation*}
        \normx{ \big ( \bmat{W}_{t} \odot \bmat{S}_r + \bmat{I} \big ) \boldsymbol{y} }_2 \leq (1 + \lambda_t) \normx{\boldsymbol{y} }_2 .
    \end{equation*}
\end{proposition}
\begin{proof}
  Let $ [\bmat{W}_{t} \odot \bmat{S}_r]_{\cdot i} $ denote the $i$th column of the matrix $(\bmat{W}_{t} \odot \bmat{S}_r)$, and express the norm as follows
    \begin{align} \label{eq: bounded weight dot product}
        \normx{(\bmat{W}_{t} \odot \bmat{S}_r) \boldsymbol{y} }_2^2 & \overset{(\text{i})}{=} 
         \normx{ \sum_{i = 1}^{d} y_{i} [\bmat{W}_{t} \odot \bmat{S}_r]_{\cdot i} }_2^2 \nonumber \\
        &\overset{(\text{ii})}{\leq} \sum_{i = 1}^{d} | y_{i} |^2 \normx{ [\bmat{W}_{t} \odot \bmat{S}_r]_{\cdot i} }_2^2 \nonumber \\
        &\overset{(\text{iii})}{\leq} \sum_{i = 1}^{d} |y_{i}|^2 \normx{ [\bmat{W}_{t}]_{\cdot i} }_2^2 .
    \end{align}
Above, (i) follows from expressing the matrix product as the sum of the each component $y_i$ and a column in $(\bmat{W}_{t} \odot \bmat{S}_r)$, (ii) follows from the triangle inequality, and (iii) follows by noting that $(\bmat{W}_{t} \odot \bmat{S}_r)$ has more zero entries in every column than $\bmat{W}_{t}$ does.
\par
Now, we know that all weights between nodes satisfy $0 \leq w_{ij} (t) \leq 1$ for all $i, j$ in $\{1, \dots, d\}$ at all times $t$, hence, for each column vector $[\bmat{W}_{t}]_{\cdot i}$ in $\bmat{W}_{t}$ we have that
\begin{equation*}
    \normx{ [\bmat{W}_{t}]_{\cdot i} }_2 = \bigg \{ \sum_{j = 1}^{p} w_{ij}^{2} (t) \bigg \}^{1 / 2} \leq  \bigg \{ \sum_{j = 1}^{p} w_{ij} (t) \bigg \}^{1/2},
\end{equation*}
and we compute
\begin{equation*}
    \lambda_t = \max \left \{ \sum_{j = 1}^{d} w_{j1}^2 (t), \dots, \sum_{j = 1}^{d} w_{jd}^2 (t) \right \}^{1 / 2}. 
\end{equation*}
Thus, for all columns we have that
\begin{equation} \label{eq: bounded weight columns}
    \normx{ [\bmat{W}_{t}]_{\cdot i} }_2 \leq \lambda_t .
\end{equation}
Now we substitute \eqref{eq: bounded weight columns} into \eqref{eq: bounded weight dot product} and we have that
\begin{equation*}
    \normx{(\bmat{W}_{t} \odot \bmat{S}_r) \boldsymbol{y} }_2^2 \leq \lambda_t^2 \sum_{i = 1}^{d} |y_{i}|^2, 
\end{equation*}
hence,
\begin{equation*}
    \normx{(\bmat{W}_{t} \odot \bmat{S}_r) \boldsymbol{y} }_2 \leq \lambda_t \normx{\boldsymbol{y} }_2.
\end{equation*}
Finally, by the triangle inequality we have that 
\begin{equation*}
    \normx{(\bmat{I_d} + \bmat{W}_{t} \odot \bmat{S}_r) \boldsymbol{y} }_2 \leq \normx{\boldsymbol{y}}_2 +  \lambda_t \normx{\boldsymbol{y} }_2 .
\end{equation*}
\end{proof}

Now we are ready to prove Proposition \ref{prop: nacf one} by bounding the NACF between minus one and one as follows.
\begin{proof}
Let $\bmat{M} = \big ( \bmat{W}_{t} \odot \bmat{S}_r + \bmat{I_d} \big )$ $\in \mathbb{R}^{d \times d}$. Then for two vectors $\boldsymbol{y}, \tildesym{y} \in \mathbb{R}^d$ we have that
\begin{align} \label{eq: nacf bounds}
    \myprod{\boldsymbol{y}}{ \bmat{M} \tildesym{y} } &=  \big \langle \boldsymbol{y}, \bmat{M} \tildesym{y}  \big \rangle \nonumber \\
    & \leq \big | \big \langle \boldsymbol{y}, \bmat{M} \tildesym{y}  \big \rangle \big | \nonumber \\
    & \overset{(\text{i})}{\leq} \normx{\boldsymbol{y}}_2 \normx{\bmat{M} \tildesym{y}}_2 \nonumber \\
    & \overset{(\text{ii})}{\leq} \normx{\boldsymbol{y}}_2 ( 1 + \lambda_t ) \normx{\tildesym{y}}_2,
\end{align}
where (i) follows from the Cauchy-Schwarz inequality, and (ii) follows from Proposition \ref{prop: nacf inequality}. Now set $\boldsymbol{y}_{t} = \boldsymbol{X}_{t} - \boldsymbol{\overline{X}}$ and using \eqref{eq: nacf bounds} we have that
\begin{equation} \label{eq: bounded nacf sums}
    \sum_{t = 1}^{N - h} \big \langle \boldsymbol{y}_{t + h}, \bmat{M} \boldsymbol{y}_{t}  \big \rangle \leq \sum_{t = 1}^{N - h} \normx{\boldsymbol{y}_{t + h}}_2 ( 1 + \lambda_t ) \normx{\boldsymbol{y}_{t}}_2 .
\end{equation}
Note that for all the components in the sum in \eqref{eq: bounded nacf sums} we have that 
\begin{equation} \label{eq: bounded sum terms}
    \mathrm{\mathbf{Pr}} \bigg \{  \normx{ \boldsymbol{y}_{t + h}}_2 \normx{\boldsymbol{y}_{t}}_2 
    \leq \max \bigg ( \normx{ \boldsymbol{y}_{t + h}}^2_2, \normx{ \boldsymbol{y}_{t}}^2_2 \bigg  ) \bigg \} = 1.
\end{equation}
Hence, when we add all the available observations, we must include all the $N - h$ summands that dominate the ones in the sum, as well as the remaining $h$ summands that are not considered for the \mbox{$h$-lag} differences, now by combining \eqref{eq: bounded sum terms} and \eqref{eq: bounded nacf sums} we have that
\begin{equation} \label{eq: bounded nacf sum}
    \sum_{t = 1}^{N - h} \big | \big \langle \boldsymbol{y}_{t + h}, \bmat{M} \boldsymbol{y}_{t}  \big \rangle \big | \leq (1 + \lambda_t) \sum_{t = 1}^{N}  \normx{ \boldsymbol{y}_{t}}^2_2 .
\end{equation}
Finally, for $N$ observations and \mbox{$h$-lag} choice we have that
\begin{align} \label{eq: absolute bound}
    \bigg | \sum_{t = 1}^{N - h}  \big \langle \boldsymbol{y}_{t + h}, \bmat{M} \boldsymbol{y}_{t}  \big \rangle \bigg | &\leq \sum_{t = 1}^{N - h} \big | \big \langle \boldsymbol{y}_{t + h}, \bmat{M} \boldsymbol{y}_{t}  \big \rangle \big | \nonumber \\
    &\overset{(\text{ii})}{\leq} (1 + \lambda_t) \sum_{t = 1}^{N} \myprod{\boldsymbol{y}_t}{\boldsymbol{y}_t},
\end{align}
where (ii) follows from \eqref{eq: bounded nacf sum}. Therefore, we have shown that with $\lambda_t$ defined as in Definition \ref{def: nacf definition} we have that 
\begin{equation*}
    -1 \leq \frac{\sum_{t=1}^{N - h} ( \boldsymbol{X}_{t + h} - \boldsymbol{\overline{X}})^{T} \big ( \bmat{W}_t \odot \bmat{S}_r + \bmat{I_d} \big )
    ( \boldsymbol{X}_{t} - \boldsymbol{\overline{X}})}
    {\sum_{t=1}^{N}  ( \boldsymbol{X}_{t} - \boldsymbol{\overline{X}})^{T} \big \{ \big (1 + \lambda_t \big) \bmat{I_d} \big \} ( \boldsymbol{X}_{t} - \boldsymbol{\overline{X}})} \leq 1 .
\end{equation*}
\end{proof}
Note that we might be interested in a particular covariate $c$. Recall that each weight is the sum of the weights between the nodes with respect to the different covariates, i.e., $w_{ij} (t) = \sum_{c = 1}^{C} w_{ijc} (t)$. Hence, we can consider the autocovariance bound for a particular weight matrix with respect to covariate $c$, we substitute $\bmat{W}_{t}$ with $\bmat{W}_{t, c}$ above and get the bound $\lambda_{t, c}$. This allows us to compute the network autocorrelation with respect to a particular covariate $c$ at time $t$. Finally, if the network is static, then we write $\lambda$ and $\bmat{W}$ since these do not depend on $t$ in the static network case.
