GNNs inherit stability from their layers

[[concept]]

Theorem

Let $\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 $||\Phi (S,h)-\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 $||\Phi (S,h)-\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 $||\Phi (S,h)-\Phi (\tilde{S},h)|{|}_p\le 2LC(1+\delta \sqrt{n})ϵ+\mathcal{O}({ϵ}^2)$ (stable to relative perturbations)

And GNNs perform better than their constituent filters.

Proof

We begin with some non-restrictive additional assumptions:

1. $||x_{\ell }||\le 1\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

\lvert \lvert \tilde{x}_{\ell} - x_{\ell} \rvert \rvert &= \lvert \lvert \sigma(H_{\ell }(\tilde{S})\tilde{x}_{\ell-1}) - \sigma(H_{\ell}(S) x_{\ell-1}) \rvert \rvert \\ (\text{since }\sigma=1)\;\;\;\;\;&\leq \lvert \lvert H_{\ell}(\tilde{S}) \tilde{x}_{\ell-1} - H_{\ell}(\tilde{S}) x_{\ell-1}\rvert \rvert \\ &= \lvert \lvert 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} \rvert \rvert \\ &= \lvert \lvert H_{\ell}(\tilde{S}) [\tilde{x}_{\ell-1} - x_{\ell-1}] + [H_{\ell(\tilde{S})} - H_{\ell}(S)] x_{\ell-1}\rvert \rvert \\ (\text{by } \triangle \text{ ineq.}) \;\;\;\;\; &\leq \cancelto{1}{\lvert \lvert H_{\ell}(\tilde{S}) \rvert \rvert} \cdot \lvert \lvert \tilde{x}_{\ell-1} - x_{\ell-1} \rvert \rvert + \cancelto{\leq 1}{\lvert \lvert x_{\ell-1} \rvert \rvert} \cdot \cancelto{\leq c_{h} \epsilon}{\lvert \lvert H_{\ell}(S) - H_{\ell} (\tilde{S})\rvert \rvert } \\ (*) &\leq \lvert \lvert \tilde{x}_{\ell-1} - x_{\ell-1} \rvert \rvert + c_{h}\epsilon \end{aligned}$$ We can apply the same reasoning to get a similar expression for $\lvert \lvert \tilde{x}_{\ell-1} - x_{\ell-1} \rvert \rvert, \lvert \lvert \tilde{x}_{\ell-2} - x_{\ell-2} \rvert \rvert, \dots$ etc for the final expression with $LC$ ^proof

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source