integral lipschitz filters are stable to dilations

[[concept]]

Theorem

Let $S^{'} = (1 + ϵ) S$ be a dilation, and consider graph convolution $H (S)$ . If $H (S)$ is a integral Lipschitz filter with constant $c$ , then

| | H (S) - H (S^{'}) | | \leq c ϵ + O (ϵ^{2})

ie, integral Lipschitz filters are stable to dilations/scalings

Proof

$\begin{aligned} H (S^{'}) - H (S) & = \sum_{k = 0}^{\infty} S^{' k} - \sum_{k = 0}^{\infty} S^{k} \\ S^{'} = (1 + ϵ) S ⟹ H (S^{'}) - H (S) & = \sum_{k = 0}^{\infty} h_{k} ((1 + ϵ^{k}) S^{k} - S^{k}) \end{aligned}$

Via binomial expansion, we have

\begin{aligned} (1 + ϵ)^{k} & = \sum_{i = 0}^{\infty} (\binom{k}{i}) ϵ^{k} \\ = 1 + k ϵ + o_{k} (ϵ) \end{aligned}

Recall that $o_{k} (ϵ)$ means $0 \leq lim_{ϵ \to 0} \frac{| | o_{k} (ϵ) | |}{ϵ^{2}} < \infty)$ . Since the filter is analytic, $o_{k} (ϵ)$ is of order $O (ϵ^{2})$ and is thus negligible. We can then write

\begin{aligned} ⟹ H (S) - H (S^{'}) & = \sum_{k = 0}^{\infty} h_{k} ((1 + k ϵ) S^{k} - S^{k}) + O (ϵ^{2}) \\ = \sum_{k = 0}^{\infty} h_{k} k ϵ S^{k} + O (ϵ^{2}) \end{aligned}

Right multiplying each side by $x = \sum_{i = 1}^{\infty} {\hat{x}}_{i} v_{i}$ (using the inverse graph fourier transform) we have

\begin{aligned} ⟹ [H (S) - H (S^{'})] x & = \sum_{k = 0}^{\infty} h_{k} k ϵ S^{k} (\sum_{i = 1}^{n} {\hat{x}}_{i} v_{i}) \\ (*) & = ϵ \sum_{k = 0}^{\infty} h_{k} k \sum_{i = 1}^{n} λ_{i}^{k} v_{i} {\hat{x}}_{i} \\ = ϵ \sum_{i = 0}^{n} \sum_{k = 0}^{\infty} (h_{k} k λ_{i}^{k}) {\hat{x}}_{i} v_{i} \\ = ϵ \sum_{i = 0}^{n} \sum_{k = 0}^{\infty} (h_{k} k λ_{i}^{k - 1}) λ_{i} {\hat{x}}_{i} v_{i} \\ (* *) & = ϵ \sum_{i = 0}^{n} [λ_{i} h^{'} (λ_{i})] {\hat{x}}_{i} v_{i} \\ | λ_{i h^{'} (λ_{i})} | \leq c ⟹ & \leq ϵ c \sum_{i = 1}^{n} {\hat{x}}_{i} v_{i} \end{aligned}

Where

the second line $(*)$ equality holds since the $v_{i}$ are eigenvectors of $S$ and
$(* *)$ holds from the definition of integral Lipschitz filter when letting $λ^{'} \to λ$ .

Thus

| | (H (S) - H (S^{'})) x | | \leq ϵ c | | x | | ⟹ | | H (S) - H (S^{'}) | | \leq ϵ c

ie, the integral Lipschitz filter is stable to dilation $◼$

Note

This is universal for graphs of any size, ie any number of nodes.

This property of graph convolution is independent of the underlying graph.

Takeaway

This means that if we can control the Lipschitz constant $c$ , then we can design stable filters (with low $c$ ) - or learn stable filters by penalizing large $c$ .

The filter is still non-discriminative at high frequencies. This is the tradeoff for having stability in graph convolution.

Mentions

File
2025-03-10 graphs lecture 13