Lipschitz filters are stable to additive perturbations

[[concept]]

Theorem

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 $||H(S)-H(\tilde{S})|{|}_p\le c(1+\delta \sqrt{n})ϵ+\mathcal{O}({ϵ}^2)$ 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.

Proof

Exercise

Left as an exercise

NOTE

The statement becomes $||H(S)-H(\tilde{S})|{|}_p\le c(1+8\sqrt{n})ϵ+\mathcal{O}({ϵ}^2)$ 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}(n^r)$ 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.

Example

• 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.

Example

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.

• finish example 1 with images from pdf edit clean 📅 2025-03-13 ✅ 2025-03-12

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