convergence bound for graph convolutions

[[concept]]

Theorem

Let $(G_{n}, X_{n}) \sim (W, X)$ and let graph and graphon convolutions be such that

H (G_{n}) = \sum_{k = 0}^{\infty} h_{k} {(\frac{A_{n}}{n})}^{k} and T_{H} = \sum_{k = 0}^{\infty} h_{k} T_{W}^{k}

Further, assume

$| | X | | \leq 1$ (WLOG)
$| h (λ) | < 1$ and $h (λ)$ is $L -$ Lipschitz in $[- 1, - c] \cup [c, 1]$ and $ℓ -$ Lipschitz in $(- c, c)$

Then we have

| | Y_{n} - Y | | \leq (L + \frac{π n_{c}}{δ_{c}}) | | T_{W} - T_{W_{n}} | | + (L c + 2) | | X - X_{n} | | + 2 ℓ c

Note

note that this bound depends on

the norm difference between the graphon and the induced graphon $| | T_{W} - T_{W_{n}} | |$
the the norm difference between the graphon signal and the induced graphon signal $| | X - X_{n} | |$

We already know that these two things converge (we've already discussed the (slow) convergence rate for $W_{n}$ in induced graph sequence converges if and only if the induced graphon sequence converges). We can bring the rates for both quantities to $O (\frac{1}{n})$ by introducing more restrictive requirements.

Convergence $(G_{n}, X_{n}) \to (W, X)$ with appropriate node labelling means approximation improves with $n$ as expected
The bound grows with $(L + \frac{π n_{c}}{δ_{c}})$
- if we want better discriminability, then we need a lower $c$ . A lower $c$ means
  - a higher c band cardinality $n_{c}$
  - a lower c eigenvalue margin $δ_{c}$
  - a higher $\frac{π n_{c}}{δ_{c}}$ , and thus a worse convergence bound
- ie, the bound is large when the filter is most discriminative

Here, the convergence-discriminability tradeoff is explicit. We can see that larger $L$ and smaller $c$ (more discriminative filters) lead to a higher error bound.

The last term $2 ℓ c$ does not vanish. We can think of this as the "approximation error" that comes from the fact that the eigenvalues of the graphs converge non-uniformly (recall this conjecture).

In the finite sample regime, unless $ℓ = 0$ , there is always leftover "nontransferable energy" corresponding to the spectral components with $| λ_{i} | < c$ which do not converge

Review

#flashcards/math/dsg

What 3(or 4) conditions do we need for a convergence bound on the graph convolution $H (G_{n}) = \sum_{k = 0}^{\infty} h_{k} {(\frac{A_{n}}{n})}^{k}$ to the limiting graphon convolution $T_{H} = \sum_{k = 0}^{\infty} h_{k} T_{W}^{k}$ of a signal $X \to X$ ?
-?-

The graphon signal $| | X | | \leq 1$
the functions $| h (λ) | < 1$ and
$h (λ)$ is $L -$ Lipschitz in $[- 1, - c] \cup [c, 1]$
- and $ℓ -$ Lipschitz in $(- c, c)$

Mentions

File	Last Modified
2025-04-07 lecture 18	2025-05-30

Created 2025-04-22 Last Modified 2025-05-30