GNNs inherit stability from their layers

Let $\mathrm{\Phi }(S,h)$ be an $L$-layer GNN. Let $\tilde{S}$ be a graph perturbation modulo permutations.

(1) if $\tilde{S}=S+ϵS$ and all filters are integral Lipschitz, then

$$||\mathrm{\Phi }(S,h)-\mathrm{\Phi }(\tilde{S},h)|{|}_p\le LCϵ+\mathcal{O}({ϵ}^2)$$

(stable to dilation/scaling)

(2) If $P^T\tilde{S}P=S\tilde{E}$ and all $h$ are lipschitz, then

$$||\mathrm{\Phi }(S,h)-\mathrm{\Phi }(\tilde{S},h)|{|}_p\le LC(1+\delta \sqrt{n})ϵ+\mathcal{O}({ϵ}^2)$$

(stable to additive perturbations)

(3) If $P^T\tilde{S}P=S+\tilde{E}S+S\tilde{E}$ and all $h$ are integral Lipschitz, then

$$||\mathrm{\Phi }(S,h)-\mathrm{\Phi }(\tilde{S},h)|{|}_p\le 2LC(1+\delta \sqrt{n})ϵ+\mathcal{O}({ϵ}^2)$$

(stable to relative perturbations)

We begin with some non-restrictive additional assumptions:

1. $||x_{\ell }||\le 1\mathrm{\forall }\ell$ - normalized input at all layers (easy to achieve with non-amplifying $h$, ie $||H||=1$)
2. $\sigma$ activation function/nonlinearity is normalized Lipschitz, ie has a Lipschitz constant of 1.

Let $||\tilde{E}||=ϵ$ for any of the three perturbation types. Let filters $h$ be stable to $\tilde{E}$
with

$$||H(\tilde{S})=H(S)|{|}_p\le c_hϵ$$

For each layer $1\le \ell \le L$, we have $\ell$ is a graph perceptron with filter $H_{\ell }$. Then, note that

$$\begin{array}{rl}||{\tilde{x}}_{\ell }-x_{\ell }||& =||\sigma (H_{\ell }(\tilde{S}){\tilde{x}}_{\ell -1})-\sigma (H_{\ell }(S)x_{\ell -1})||\\ (\text{since }\sigma =1)& \le ||H_{\ell }(\tilde{S}){\tilde{x}}_{\ell -1}-H_{\ell }(\tilde{S})x_{\ell -1}||\\ & =||H_{\ell }(\tilde{S}){\tilde{x}}_{\ell -1}-H_{\ell }(\tilde{S})x_{\ell -1}+H_{\ell }(\tilde{S})x_{\ell -1}-H_{\ell }(S)x_{\ell -1}||\\ & =||H_{\ell }(\tilde{S})[{\tilde{x}}_{\ell -1}-x_{\ell -1}]+[H_{\ell (\tilde{S})}-H_{\ell }(S)]x_{\ell -1}||\\ (\text{by }\mathrm{△}\text{ ineq.})& \le {\cancel{||H_{\ell }(\tilde{S})||}}^1\cdot ||{\tilde{x}}_{\ell -1}-x_{\ell -1}||+{\cancel{||x_{\ell -1}||}}^{\le 1}\cdot {\cancel{||H_{\ell }(S)-H_{\ell }(\tilde{S})||}}^{\le c_hϵ}\\ (\ast )& \le ||{\tilde{x}}_{\ell -1}-x_{\ell -1}||+c_hϵ\end{array}$$

We can apply the same reasoning to get a similar expression for $||{\tilde{x}}_{\ell -1}-x_{\ell -1}||,||{\tilde{x}}_{\ell -2}-x_{\ell -2}||,\dots$ etc for the final expression with $LC$