2025-03-10 graphs lecture 13

[[lecture-data]]

• finish cleaning up these notes once PDF is published clean ➕ 2025-03-10 📅 2025-03-12 ✅ 2025-03-12

Summary

Last Time

• lipschitz graph filter Today
• finish stability of GNNs

Notes PDF

1. Graph Signals and Graph Signal Processing

Recall the definition for an integral Lipschitz filter

integral lipschitz filter

Let $h(\lambda )$ be the spectral representation of a convolutional graph filter. $h(\lambda )$ is integral lipschitz on interval $T\subset \mathbb{R}$ means there exists some $c\in \mathbb{R}$ such that \lvert h(\lambda) - h(\lambda') \rvert \leq \frac{C \lvert \lambda'-\lambda \rvert }{\frac{1}{2}\lvert \lambda+\lambda' \rvert }\;\;\;\forall \;\;\lambda, \lambda'$$ ie, h(\lambda)$ is lipschitz with a constant inversely proportional to the interval’s midpoint

Letting ${\lambda }^{\prime }\to \lambda$, we get \lambda h'(\lambda) \leq c \implies h'(x) \leq \frac{c}{\lambda} \to 0,\;\;\;\lambda \to \infty$$ This means that the filter can't change for large \lambda$.

Example

Notice that the filter becomes flat at high frequencies

• At low $\lambda$, they can be arbitrarily thin.
• At medium $\lambda$, these filters are approximately lipschitz filters.
• At high $\lambda$, they become flat and lose discriminability

NOTE

$c$ controls how discerning an integral Lipschitz filter is for frequencies at different ranges.

Stability to different graph perturbations

Recall the types of perturbations on shift operators:

Perturbation Types

We consider 3 perturbation types (first for graph convolutions, then for GNNs)

1. dilations
2. additive perturbations
3. relative perturbations

operator dilation

Let $S$ be a shift operator. We call $S^{\prime }$ an (operator) dilation (or scaling) if S' = (1+\epsilon)S$$ \implies \lvert \lvert S-S’ \rvert \rvert = \epsilon \lvert \lvert S \rvert \rvert $$ We can interpret this as the edges being scaled by $(1+ϵ)$.

[!def] Additive Perturbations

Let $S$ be a matrix. $\tilde{S}$ is an additive perturbation of $S$ if \tilde{S} = S+E, \;\;\;E= \tilde{S} - S,\;\;\; 0 \leq \lvert \lvert E \rvert \rvert \leq \epsilon$$ However, this definition is problematic since it is not [[Concept Wiki/filter permutation invariance\|invariant to permutations]]: \tilde{S} = P^TSP \implies E = P^TSP - S$$

For a graph shift operator, we define an additive perturbation modulo permutations: E(S,\tilde{S}) = \{ D: P^T\tilde{S}P = S+D \}$$ Where P \in \cal{P}$ is a permutation.

Given $\tilde{S}$, the error is the $D$ with the smallest norm: \tilde{E} = \arg\min_{D \in E(S, \tilde{S})} \lvert \lvert D \rvert \rvert_{p} $$ Where \lvert \lvert \cdot \rvert \rvert_{p} = d(\cdot)$isthe[[ConceptWiki/operatordistancemodulopermutations]]and$\lvert \lvert D \rvert \rvert_{p} = d(S, \tilde{S})$

Unlike dilation, absolute perturbations (like the additive perturbations) do not take edge weights into account but can model changes in edge existence. This is fine for unweighted graphs, but for weighted graphs, this renders them unmeaningful. We want something that both

1. takes edge weights into account
2. can model edge additions and deletions ie a perturbation that can combine these two benefits.

Relative Perturbations modulo permutations

$E(S,\tilde{S})=\{D:P^{T}SP=S+DS+SD,P\in \mathcal{P}\}$

given $\tilde{S}$, the error is $E$ with the smallest norm ie $\tilde{E}=\arg {\min }_{D\in E(S,\tilde{S})}||D||$ ie $||\tilde{E}||=d(S,\tilde{S})$

where $d(\cdot )$ is the operator distance modulo permutations.

NOTE

• dilation takes into account edge weights, but cannot model edge additions and deletions
• additive perturbations can model edge additions and deletions, but do not take into account edge weights
• relative perturbations take into account both edge weights and additions/deletions

see relative perturbations

stability for dilations

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$

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.

see integral lipschitz filters are stable to dilations

stability to additive perturbations

Eigenvector misalignment $\delta$

Let $S=V\Lambda V^T$ and $\tilde{E}=UM{U}^T$. Then $\delta (S,\tilde{E})=(||U-V||+1{)}^2=1$

If both $U$ and $V$ are normal (ie $||U||=||V||=1$), then $\delta \le 8$.

see eigenvector misalignment

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

Check Gama et al. 2019.

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.

see Lipschitz filters are stable to additive perturbations

stability to relative perturbations

Let $\tilde{S}=S+DS+SD$ be a relative perturbation on $S$. Locally, we have

\tilde{S}_{ij} &= S_{ij} + (DS)_{ij} + (SD)_{ij} \\ &= S_{ij} + \sum_{k \in N(j)} D_{ik}S_{kj} + \sum_{k \in N(i)} S_{ik}D_{ki} \\ &= S_{ij} + (\propto \text{deg}(j)) + (\propto \text{deg}(i)) \end{aligned}$$ This tells us that the edge changes in the [[Concept Wiki/perturbations on a graph shift operator\|perturbed]] graph is tied to the degrees of the nodes. see [[Concept Wiki/relative perturbation edge changes are tied to node degree]] > [!theorem] > > Suppose $P^TSP = S + \tilde{E}S + S\tilde{E}$ with $\lvert \lvert \tilde{E} \rvert \rvert = \epsilon$. Suppose $h$ is an [[Concept Wiki/integral Lipschitz filter]] with constant $c$. Then > $$\lvert \lvert H(\tilde{S}) = H(S) \rvert \rvert _{p} \leq 2c (1+\delta \sqrt{ n })\epsilon + \cal{O}(\epsilon^2)$$ > Where $\delta$ is the [[Concept Wiki/eigenvector misalignment]] between $S$ and $\tilde{E}$. > > ie, [[Concept Wiki/integral Lipschitz filter\|integral Lipschitz filters]] are [[Concept Wiki/stable graph filter\|stable]] to [[Concept Wiki/relative perturbations]] > [!NOTE] > > This is the *same bound* as the one we got for [[Concept Wiki/lipschitz graph filter\|lipschitz graph filters]] on [[Concept Wiki/Lipschitz filters are stable to additive perturbations#^statement\|additive perturbations]], just with an additional factor of 2. And just like that bound, we see that > - again, this is not bad for small $n$, but *terrible for large graphs* unless $\delta = \cal{O}(n^{r})$ for $r \leq 0$. > - this holds for all graphs of size $n$. ie, this is a property of the [[Concept Wiki/graph convolution\|graph convolution]] and will be true regardless of the actual underlying graph > - Similar to filters that are stable to [[Concept Wiki/operator dilation\|dilation]] and [[Concept Wiki/additive perturbations\|additive perturbation]], the [[Concept Wiki/Lipschitz continuous\|Lipschitz]] constant $c$ can be controlled by design or by penalizing large values. > > The *difference* is that there is *no* [[Concept Wiki/stability-discriminability tradeoff for Lipschitz filters\|tradeoff]] between [[Concept Wiki/stable graph filter\|stability]] and [[Concept Wiki/discriminability of a graph filter\|discriminability]]. > > [!proof] > > check Gama et al. 2019 > [!NOTE] > > For high frequencies $\lambda$, there is *no* tradeoff between [[Concept Wiki/stable graph filter\|stability]] and [[Concept Wiki/discriminability of a graph filter\|discriminability]]. This is because the *filter is always flat* for high values of $\lambda$. Thus, the filter is always non-discriminative for these values. > > ![[Attachments/20250312-graph-1.png]] > > This is a direct result of the behavior of [[Concept Wiki/integral Lipschitz filter\|integral Lipschitz filters]] at high frequencies. > see [[Concept Wiki/integral Lipschitz filters are stable to relative perturbations]] >[!tip] Takeaway > >[[Concept Wiki/additive perturbations]] are not very realistic, and so a [[Concept Wiki/lipschitz graph filter]] is enough to get [[Concept Wiki/stable graph filter\|stability]]. > >If we have a [[Concept Wiki/perturbations on a graph shift operator\|perturbation]] that respects the graph sparsity pattern (models edge weights), we need an [[Concept Wiki/integral Lipschitz filter]] to get [[Concept Wiki/stable graph filter\|stability]]. >- However, there is a *big downside* for large graphs, since the bound depends on $n$. see [[Concept Wiki/stability and size tradeoff for realistic sparsity pattern considerations setting]] ## Generalization to [[Concept Wiki/Graph Neural Networks\|GNNs]] Generally, the stability properties of the convolutions will be inherited by their constituent [[Concept Wiki/graph convolution\|graph filters]]. - [x] finish up this section 📅 2025-03-12 ✅ 2025-03-12 - [x] add gnn stability theorems to concept wiki 📅 2025-03-12 ✅ 2025-03-12 > [!theorem] > > Let $\Phi(S,h)$ be an $L$-layer [[Concept Wiki/Graph Neural Networks\|GNN]]. Let $\tilde{S}$ be a [[Concept Wiki/perturbations on a graph shift operator\|graph perturbation]] modulo permutations. > > (1) if $\tilde{S} = S + \epsilon S$ and all filters are [[Concept Wiki/integral Lipschitz filter\|integral Lipschitz]], then > $$\lvert \lvert \Phi(S,h) - \Phi(\tilde{S}, h)\rvert \rvert_{p} \leq LC \epsilon + {\cal O}(\epsilon^2)$$ > > (stable to [[Concept Wiki/operator dilation\|dilation]]/scaling) > > (2) If $P^T\tilde{S}P = S\tilde{E}$ and all $h$ are [[Concept Wiki/lipschitz graph filter\|lipschitz]], then > $$\lvert \lvert \Phi(S,h) -\Phi(\tilde{S},h)\rvert \rvert _{p} \leq LC(1+\delta \sqrt{ n })\epsilon + {\cal O}(\epsilon^2)$$ > (stable to [[Concept Wiki/additive perturbations]]) > > (3) If $P^T\tilde{S}P = S + \tilde{E}S + S\tilde{E}$ and all $h$ are [[Concept Wiki/integral Lipschitz filter\|integral Lipschitz]], then > $$\lvert \lvert \Phi(S,h) -\Phi(\tilde{S},h)\rvert \rvert _{p} \leq 2LC(1+\delta \sqrt{ n })\epsilon + {\cal O}(\epsilon^2)$$ > (stable to [[Concept Wiki/relative perturbations]]) > > [!proof] > > We begin with some non-restrictive additional assumptions: > 1. $\lvert \lvert x_{\ell} \rvert \rvert \leq 1 \;\;\forall \ell$ - normalized input at all layers (easy to achieve with non-amplifying $h$, ie $\lvert \lvert H \rvert \rvert = 1$) > 2. $\sigma$ activation function/nonlinearity is normalized [[Concept Wiki/Lipschitz continuous\|Lipschitz]], ie has a Lipschitz constant of 1. > > Let $\lvert \lvert \tilde{E} \rvert \rvert = \epsilon$ for any of the three [[Concept Wiki/perturbations on a graph shift operator\|perturbation]] types. Let filters $h$ be stable to $\tilde{E}$ > with > $$\lvert \lvert H(\tilde{S}) = H(S) \rvert \rvert _{p} \leq c_{h} \epsilon$$ > > For each layer $1 \leq \ell \leq L$, we have $\ell$ is a [[Concept Wiki/graph perceptron]] with filter $H_{\ell}$. Then, note that > $$\begin{aligned} > \lvert \lvert \tilde{x}_{\ell} - x_{\ell} \rvert \rvert &= \lvert \lvert \sigma(H_{\ell }(\tilde{S})\tilde{x}_{\ell-1}) - \sigma(H_{\ell}(S) x_{\ell-1}) \rvert \rvert \\ > (\text{since }\sigma=1)\;\;\;\;\;&\leq \lvert \lvert H_{\ell}(\tilde{S}) \tilde{x}_{\ell-1} - H_{\ell}(\tilde{S}) x_{\ell-1}\rvert \rvert \\ > &= \lvert \lvert H_{\ell}(\tilde{S}) \tilde{x}_{\ell-1} - H_\ell(\tilde{S})x_{\ell-1} + H_{\ell}(\tilde{S})x_{\ell-1}- H_{\ell}(S) x_{\ell-1} \rvert \rvert \\ > &= \lvert \lvert H_{\ell}(\tilde{S}) [\tilde{x}_{\ell-1} - x_{\ell-1}] + [H_{\ell(\tilde{S})} - H_{\ell}(S)] x_{\ell-1}\rvert \rvert \\ > (\text{by } \triangle \text{ ineq.}) \;\;\;\;\; &\leq \cancelto{1}{\lvert \lvert H_{\ell}(\tilde{S}) \rvert \rvert} \cdot \lvert \lvert \tilde{x}_{\ell-1} - x_{\ell-1} \rvert \rvert + \cancelto{\leq 1}{\lvert \lvert x_{\ell-1} \rvert \rvert} \cdot \cancelto{\leq c_{h} \epsilon}{\lvert \lvert H_{\ell}(S) - H_{\ell} (\tilde{S})\rvert \rvert } \\ > (*) &\leq \lvert \lvert \tilde{x}_{\ell-1} - x_{\ell-1} \rvert \rvert + c_{h}\epsilon > \end{aligned}$$ > > We can apply the same reasoning to get a similar expression for $\lvert \lvert \tilde{x}_{\ell-1} - x_{\ell-1} \rvert \rvert, \lvert \lvert \tilde{x}_{\ell-2} - x_{\ell-2} \rvert \rvert, \dots$ etc for the final expression with $LC$ > > see [[Concept Wiki/GNNs inherit stability from their layers]] In the node domain, the nonlinearity does not affect the signal much. However, nonlinearities scatter the signal energy across the [[Concept Wiki/spectrum]]. > [!example] > > ![[Attachments/20250312-2025-03-10-graphs.png]] > - we first get a response $\hat{x}$ from the [[Concept Wiki/spectral representation of a convolutional graph filter]] > - after the nonlinearity, some of the energy modes to other areas of the spectrum > > Some of the energy in high frequencies "travels" to low frequencies. Both [[Concept Wiki/lipschitz graph filter\|lipschitz graph filters]] and [[Concept Wiki/integral Lipschitz filter\|integral Lipschitz filters]] can [[Concept Wiki/discriminability of a graph filter\|discriminate]] at these low frequencies. > > If any of our task depends on high-frequency data, then this scattering can help us perform well by moving some of the high-frequency information into the lower frequencies, where we have both [[Concept Wiki/stable graph filter\|stability]] and [[Concept Wiki/discriminability of a graph filter\|discriminability]] >[!tip] Takeaway > > [[Concept Wiki/Graph Neural Networks\|GNNs]] can perform better than their constituent [[Concept Wiki/graph convolution\|graph filters]]. That is, they are more [[Concept Wiki/stable graph filter\|stable]] for the same level of [[Concept Wiki/discriminability of a graph filter\|discriminability]], and more [[Concept Wiki/discriminability of a graph filter\|discriminative]] for the same level of [[Concept Wiki/stable graph filter\|stability]] than a direct composition of the same filters. > > This is because the nonlinear activation function "scatters" the signal across the spectrum, moving some high frequency information to lower frequencies and vice versa. Since both [[Concept Wiki/lipschitz graph filter\|lipschitz graph filters]] and [[Concept Wiki/integral Lipschitz filter\|integral Lipschitz filters]] can [[Concept Wiki/discriminability of a graph filter\|discriminate]] at low frequencies, the mixing from the nonlinearity helps the GNN account for a wider range of the information. see [[Concept Wiki/GNNs perform better than their constituent filters]]