graph convolutions are stable to perturbations in the data and coefficients

[[concept]]

Takeaway

graph convolutions are Lipschitz stable to perturbations in $x$ and $h_{k}$ .

This is because the convolutional graph filter $y = \sum_{k = 0}^{K - 1} h_{k} S^{k} x$ is linear in both $h_{k}$ and $x$ , and continuous linear functions are lipschitz continuous.

The convolutional graph filter $y = \sum_{k = 0}^{K - 1} h_{k} S^{k} x$ is linear in both $h_{k}$ and $x$ .

(1) if $x^{'} = x + ϵ$ , then $| | y - y^{'} | | \leq (K . max_{k} h_{k} λ_{i}^{+ +})$
(2) if $h_{k}^{'} = h_{k} + ϵ$ , then $| | y - y^{'} | | \leq (λ_{1}^{k} \cdot | | x | |) ϵ$

File
2025-03-05 graphs lecture 12