integral lipschitz filters are stable to dilations

[[concept]]

Theorem

Let $S^{\prime }=(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^{\prime })||\le cϵ+\mathcal{O}({ϵ}^2)$

ie, integral Lipschitz filters are stable to dilations/scalings

Proof

H(S') - H(S) &= \sum_{k=0}^\infty S'^{k} - \sum_{k=0}^\infty S^k \\ S' = (1+\epsilon)S \implies H(S') - H(S) &=\sum_{k=0}^\infty h_{k} ((1+\epsilon^k)S^k - S^k) \end{aligned}

Via binomial expansion, we have

(1+\epsilon)^k &= \sum_{i=0}^\infty {{k}\choose{i}} \epsilon^k \\ &= 1+k\epsilon + \cal{o}_{k}(\epsilon) \\ \end{aligned}

Recall that $o_k(ϵ)$ means $0\le {\lim }_{ϵ\to 0}\frac{||o_k(ϵ)||}{{ϵ}^2}<\infty )$. Since the filter is analytic, $o_k(ϵ)$ is of order $\mathcal{O}({ϵ}^2)$ and is thus negligible. We can then write

\implies H(S) - H(S') &= \sum_{k=0}^\infty h_{k}((1+k\epsilon)S^k - S^k) + \cal{O}(\epsilon^2) \\ &= \sum_{k=0}^\infty h_{k} k \epsilon S^k + \cal{O}(\epsilon^2) \end{aligned}$$ Right multiplying each side by $x=\sum_{i=1}^\infty \hat{x}_{i} v_{i}$ (using the [[Concept Wiki/inverse graph fourier transform]]) we have $$\begin{aligned} \implies [H(S) - H(S')]x &= \sum_{k=0}^\infty h_{k} k \epsilon S^k \left( \sum_{i=1}^n \hat{x}_{i} v_{i} \right) \\ (*) &= \epsilon \sum_{k=0}^\infty h_{k} k \sum_{i=1}^n \lambda_{i}^k v_{i} \hat{x}_{i} \\ &= \epsilon \sum_{i=0}^n \sum_{k=0}^\infty (h_{k} k \lambda_{i}^{k}) \hat{x}_{i} v_{i} \\ &= \epsilon \sum_{i=0}^n \sum_{k=0}^\infty (h_{k} k \lambda_{i}^{k-1}) \lambda_{i} \hat{x}_{i} v_{i}\\ (**) &= \epsilon \sum_{i=0}^n [\lambda_{i} h'(\lambda_{i})] \hat{x}_{i} v_{i} \\ \lvert \lambda_{i h'(\lambda_{i})} \rvert \leq c \implies &\leq \epsilon c\sum_{i=1}^n \hat{x}_{i} v_{i} \end{aligned}$$ Where - the second line $(*)$ equality holds since the $v_{i}$ are [[Concept Wiki/eigenvalue\|eigenvectors]] of $S$ and - $(**)$ holds from the definition of [[Concept Wiki/integral Lipschitz filter]] when letting $\lambda' \to \lambda$. Thus $$\lvert \lvert (H(S) - H(S'))x \rvert \rvert \leq \epsilon c \lvert \lvert x \rvert \rvert \implies \lvert \lvert H(S) - H(S') \rvert \rvert \leq \epsilon c$$ ie, the [[Concept Wiki/integral Lipschitz filter]] is [[Concept Wiki/stable graph filter\|stable]] to [[Concept Wiki/operator dilation\|dilation]] $\blacksquare$ ^proof

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

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