Lipschitz filters are stable to additive perturbations

Let $\tilde{S}$ be an additive perturbation of graph shift operator $S$, ie, $P^T\tilde{S}P=S+\tilde{E}$ with $||\tilde{E}||=ϵ$.

Suppose $h$ is a lipschitz graph filter with constant $c$. Then

Where $\delta$ is the eigenvector misalignment between $S$ and $\tilde{E}$. Since both $S$ and $\tilde{E}$ are normal, we can see $\delta \le 8$.

ie, graph convolutions are stable to additive perturbations, provided they have Lipschitz spectral response.

Check Gama et al. 2019.

The statement becomes

This means we have lipschitz stability to additive perturbations when $c(1+\delta \sqrt{n})\le c(1+8\sqrt{n})$.

• this is not bad for small $n$, but terrible for large graphs unless $\delta =\mathcal{O}\mathcal{(}{\mathcal{n}}^{\mathcal{r}}\mathcal{)}$ for $r\le 0$.
• this holds for all graphs of size $n$. ie, this is a property of the graph convolution and will be true regardless of the actual underlying graph
• Similar to filters that are stable to dilation, $c$ can be controlled by design or by penalizing large values.

• there is a tradeoff between stability to the additive perturbations and discriminability
• The higher the $c$, the higher the spectral discriminability. The lower the $c$, the better the stability of the filter.

For community detection, penalizing for large Lipschitz constants would make a GNN more stable to adding noise to the graph (increasing the edge deletion probability). But, this might make it worse at detecting the communities.