2025-04-07 lecture 18

[[lecture-data]]

Summary

Last Time

• We saw that bandlimited convergent graph signals converge in the fourier domain.
• We also saw the graph convolution converges to the graphon convolution in the spectral domain for a convergent sequence of graph signals
  • However, convergence in the spectral domain is not enough because graph convolutions and graphon convolutions operate in the node domain.
• We want to convert this convergence back into the node domain (iWFT) and see if convergence holds

3. Graphon Signal Processing

Recall that

1. graph convolutions converge in the spectral domain
2. given $(G_n,X_n)\to (W,\mathcal{X})$ where $(W,\mathcal{X})$ is bandlimited, GFT of ${\hat{x}}_n$ converges to WFT $\hat{\mathcal{X}}$ (bandlimited convergent graph signals converge in the fourier domain)

For bandlimited graphon signals, we should be able to show convergence in the node domain!

Convergence of bandlimited signals in the node domain

Theorem

Let $(G_n,X_n)\to (W,\mathcal{X})$ with $c-$bandlimited $(W,\mathcal{X})$. Let $H(G_n)={\sum }_{k=0}^{K-1}{h}_k(\frac{A_n}{n}{)}^k$ be a sequence of graph convolution that share coefficients with graphon convolution $T_H={\sum }_{k=0}^{K-1}{h}_k{T}_W^{(k)}$. Then

$(G_n,Y_n)\to (W,\mathcal{Y})$ Where $Y_n$ and $\mathcal{Y}$ are the graph and graphon convolution outputs respectively.

Recall that our definition of a convergent sequence of graph signals compares the induced graphon signal and the limiting graphon signal to see if they converse in an $L_2$ way.

theorem basically says

• if we have a sequence that converges in this way and we have these graphon and graph convolutions, the outputs of those convolutions also converge in $L_2$

Proof

${\hat{Y}}_n\to \mathcal{Y}$ follows ${\hat{X}}_n\to \hat{\mathcal{X}}$ conbined with $\hat{H}(G_n)\to {\hat{T}}_H(W)$. Since $\mathcal{X}$ is bandlimited, so is $\mathcal{Y}$ because both graph convolutions and graphon convolutions act pointwise in the spectral domain. Therefore, the iGFT converges to the iWFT. $■$

See graph convolutions of bandlimited signals converge to the graphon convolution

Our first result for convergence for graphon signals is restrictive though, since we require that {==as||the signal is bandlimited||restriction} and {ha||graphons have infinite-dimensional spectra||why restrictive==}.

Can we get a better result? Can we generalize to arbitrary convergent graph signals?

set-up for solution

To show convergence of filters for general signals (not only bandlimited), we instead restrict {as||the filters||what restrict} to {==ha||be Lipschitz||restriction==}.

Recall the definition for lipschitz graph filters.

lipschitz filter

Let $H$ be a convolutional graph filter and $h(\lambda )$ its spectral representation. $H$ is a lipschitz filter if $h(\lambda )$ is Lipschitz on some interval $T\subset \mathbb{R}$. ie, that there exists some $c\in \mathbb{R}$ such that \lvert h(\lambda) - h(\lambda') \rvert \leq c\lvert \lambda - \lambda' \rvert \;\;\;\forall \;\lambda, \lambda' \in T$$ This uses the idea that once the filter is fixed, we can think of the representation as [[spectral representation of a convolutional graph filter#^spectral-as-poly|sampling along a "spectrum polynomial"]]. Typically, T = [\lambda_{\text{min}}, \lambda_{\text{max}}]$

We define our analogue for graphon filters in the same way:

Lipschitz graphon filters

Let $T_H$ be a graphon filter. $T_H$ is a Lipschitz graphon filter if it has Lipschitz spectral response. ie, it $|h({\lambda }_1)-h({\lambda }_2)|\le L|{\lambda }_1-{\lambda }_2|\forall {\lambda }_1,{\lambda }_2\in [-1,1]$ This upper bounds the magnitude of the first derivative on the interval $[-1,1]$

NOTE

In this statement, our $h$ are arbitrary analytic functions. However, in practice, these will be polynomials

• On the real line, polynomials are not Lipschitz. However, in a bounded interval, we can always find a Lipschitz constant.

We consider general analytic filters $h(\lambda )$ with Lipschitz constant $L$ (both for generality and to avoid dependence on the polynomial degree $k$ which gives us better/tighter bounds)

see Lipschitz graphon filter

Improved/more general version

Aside: this is a LONG proof (longest in the class probably). The theorem is basically the same as the one above, but without the bandlimited assumption.

Theorem

Let $(G_n,X_n)\to (W,\mathcal{X})$.

Let $H(G_n)={\sum }_{k=0}^{K-1}{h}_k(\frac{A_n}{n}{)}^k$ be a sequence of graph convolution that share coefficients with graphon convolution $T_H={\sum }_{k=0}^{K-1}{h}_k{T}_W^{(k)}$ where $h(\lambda )$ is a Lipschitz graphon filter. Then

$(G_n,Y_n)\to (W,\mathcal{Y})$ Where $Y_n$ and $\mathcal{Y}$ are the graph and graphon convolution outputs respectively.

Proof

graph convolutions converge in the "induced graphon signal" sense to the outputs of the graphon convolution

We want to show the outputs on the

• ie, want to show $||{\mathcal{Y}}_n-\mathcal{Y}|{|}_2\to 0$ where ${\mathcal{Y}}_n$ is the induced graphon signal for $Y_n$.

WLOG, we assume that $|h(\lambda )|\le 1\forall \lambda \in [-1,1]$. We have

$\mathcal{Y}={\sum }_{j\in \mathbb{Z}\setminus \{0\}}h({\lambda }_j){\hat{\mathcal{X}}}_j{\phi }_j\text{ and }{\mathcal{Y}}_n={\sum }_{j\in \mathbb{Z}\setminus \{0\}}h({\lambda }_j^{(n)})[{\hat{X}}_n{]}_j{\phi }_j^{(n)}$

note on notation ${\lambda }_j,{\mathcal{X}}_j,{\phi }_j$ are the eigenvalues, graphon signal, and eigenfunctions of the graphon respectively. ${\lambda }_j^{(n)},[{\hat{X}}_n{]}_j,{\phi }_j^{(n)}$ are the eigenvalues, graph signals, and eigenvectors of the graphs in the sequence of convergent graphs and convergent graph signals.

Define an partitioning index set $\mathcal{C}$ such that

j \in {\cal C} &= \{ i \text{ s.t. } \lvert \lambda_{i} \rvert \geq c \} \\ j \not\in {\cal C} &= \{ i \text{ s.t. } \lvert \lambda_{i} \rvert < c \} \end{cases} \qquad \text{ where }\quad c=\frac{1-\lvert h_{0} \rvert }{L(2\lvert \lvert {\cal X} \rvert \rvert \epsilon^{-1} + 1 )}$$ Where we fix some $\epsilon>0$, $h_{0} = h(0)$, and $L$ is the [[Lipschitz graphon filter|Lipschitz]] constant. We can choose $\epsilon$ such that $c=k\,\,\forall k \in [-1,1]$. Further, note that *this creates a set of [[bandlimited graphon signal|bandlimited]] components* (${\cal C}$) and *non-bandlimited components (${\cal C}^c$)* of the signal. Then, by the [[triangle inequality]], we have $$\begin{align} \lvert \lvert {\cal Y} - {\cal Y}_{n} \rvert \rvert &= \left\lvert \left\lvert \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} h(\lambda_{j}) \hat{{\cal X}}_{j} \varphi_{j} - \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} h(\lambda_{j}^{(n)}) [\hat{X}_{n}]_{j} \varphi_{j}^{(n)}\right\rvert \right\rvert \\ &\leq \left\lvert \left\lvert \sum_{j \in {\cal C}} h(\lambda_{j} \hat{{\cal X}}_{j} \varphi_{j}) - \sum_{j \in {\cal C}} h(\lambda_{j}^{(n)}) [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert \quad(\star^1) \\ &\quad+ \left\lvert \left\lvert \sum_{j \not\in {\cal C}} h(\lambda_{j} \hat{{\cal X}}_{j} \varphi_{j}) - \sum_{j \not\in {\cal C}} h(\lambda_{j}^{(n)}) [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert \quad(\star^2) \end{align}$$ And we can bound $(\star^1)$ and $(\star^2)$ individually. It is very easy to bound $(\star^1)$, since this is equivalent to filter applications to a [[bandlimited graphon signal|bandlimited]] ${\cal X}$ with bandwith $c$. Thus, $(\star^1)$ vanishes as a direct applications of the previous result ([[bandlimited convergent graph signals converge in the fourier domain]]) to this expression. For $(\star^2)$, we note that $$h_{0} - Lc \leq h(\lambda_{j})\leq h_{0}+Lc\quad \forall \, j \not\in {\cal C}$$ > [!example]- Illustration > ![[Attachments/20250407-graph.png]] > > We don't care about the spectral intervals $(-\infty, -c]$ and $[c, \infty)$ since they are covered by $(\star^1)$. Since $h(\lambda)$ is $L$-lipschitz, the maximum value the function can change between $0$ and $c$ is $Lc$. Then we can write $$\begin{align} (\star^2)&=\left\lvert \left\lvert \sum_{j \not\in {\cal C}} h(\lambda_{j} \hat{{\cal X}}_{j} \varphi_{j}) - \sum_{j \not\in {\cal C}} h(\lambda_{j}^{(n)}) [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert \\ &\leq (h_{0}+Lc) \left\lvert \left\lvert \sum_{j \not\in {\cal C}} h(\lambda_{j} \hat{{\cal X}}_{j} \varphi_{j}) - \sum_{j \not\in {\cal C}} h(\lambda_{j}^{(n)}) [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert \\ &\leq \underbrace{ h_{0} \left\lvert \left\lvert \sum_{j \not\in{\cal C}} \hat{\cal X}_{j} \varphi_{j} - [\hat{\cal X}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert }_{ (\star^3) } + \underbrace{ Lc \left\lvert \left\lvert \sum_{j \not\in{\cal C}} \hat{{\cal X}}_{j} \varphi_{j} \right\rvert \right\rvert }_{ (*)\leq Lc \lvert \lvert {\cal X} \rvert \rvert } + \underbrace{ Lc \left\lvert \left\lvert \sum_{j \not\in{\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert }_{ (\star^4) } \end{align}$$ We can see $(*)$ follows since $\sum_{j \not\in{\cal C}} \hat{{\cal X}}_{j} \varphi_{j}$ is a portion of graphon signal ${\cal X} = \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} \hat{{\cal X}}_{j} \varphi_{j}$. And so, we can upper bound the norm of the portion of the signal by the norm of the entire signal. Now, we need to bound $(\star^3)$ and $(\star^4)$. Note that we can write $$(\star^{\dagger})\quad \sum_{j \not\in {\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} = {\cal X}_{n} - \sum_{j \in {\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)}$$ We can do this because the $\varphi$ form an [[orthogonal vectors|orthonormal]] [[basis]] for both the graph and the graphon (see the appropriate [[spectral theorem for self-adjoint compact operators on Hilbert spaces|spectral theorem]]). For $(\star^3)$, by writing both the [[induced graphon signal]] and the limiting [[graphon signal]] in terms of the identity $(\star ^{\dagger})$, we can get $$\begin{align} \left\lvert \left\lvert \sum_{j \not\in{\cal C}} \hat{\cal X}_{j} \varphi_{j} - [\hat{\cal X}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert &= \left\lvert \left\lvert \left( {\cal X} - \sum_{j \in {\cal C}} \hat{{\cal X}}_{j} \varphi_{j} \right) - \left( {\cal X}_{n} - \sum_{j \in {\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right) \right\rvert \right\rvert \\ &\leq \underbrace{ \lvert \lvert {\cal X} - {\cal X_{n}} \rvert \rvert }_{ {\cal X}_{n} \to {\cal X} } + \underbrace{ \left\lvert \left\lvert \sum_{j \in {\cal C}} \hat{{\cal X}}_{j} \varphi_{j}-[\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert }_{ \text{converges (bandlimited signal)} } \\ &< \epsilon \end{align}$$ Where $\epsilon$ is the same one we fixed above. Since both RHS terms converge (the first is from our initial conditions, the second one is again a direct application of [[bandlimited convergent graph signals converge in the fourier domain|bandlimited convergence]]), we are done for $(\star^3)$. Finally, for $(\star^4)$, $$\begin{align} \left\lvert \left\lvert \sum_{j \not\in{\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert &= \left\lvert \left\lvert {\cal X}_{n} - \sum_{j \in {\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} + {\cal X} - {\cal X}\right\rvert \right\rvert \\ &\leq \underbrace{ \lvert \lvert {\cal X}_{n} - {\cal X} \rvert \rvert }_{ {\cal X_{n}} \to {\cal X} } + \underbrace{ \left\lvert \left\lvert \sum_{j \in {\cal C}} [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} - \hat{{\cal X}}_{j} \varphi_{j} \right\rvert \right\rvert }_{ \text{converges (bandlimited)} } + \underbrace{ \left\lvert \left\lvert \sum_{j \not\in {\cal C}} \hat{{\cal X}}_{j} \varphi_{j} \right\rvert \right\rvert }_{ \leq \lvert \lvert {\cal X} \rvert \rvert } \\ &< \epsilon + \lvert \lvert {\cal X} \rvert \rvert \end{align}$$ Thus we get that $$\begin{align} (\star^2) &= \left\lvert \left\lvert \sum_{j \not\in {\cal C}} h(\lambda_{j} \hat{{\cal X}}_{j} \varphi_{j}) - \sum_{j \not\in {\cal C}} h(\lambda_{j}^{(n)}) [\hat{{\cal X}}_{n}]_{j} \varphi_{j}^{(n)} \right\rvert \right\rvert \\ &\leq Lc\lvert \lvert {\cal X} \rvert \rvert + h_{0}\epsilon +Lc(\epsilon+\lvert \lvert {\cal X} \rvert \rvert) \\ &< \tilde{\epsilon} \end{align}$$ for all $n>N_{\epsilon}$

see lipschitz graph convolutions of graph signals converge to lipschitz graphon filters

Summary

For node-domain convergence, we first saw that graph convolutions of bandlimited signals converge to the graphon convolution. But since graphons have infinite-dimensional spectra, this can be quite strict and therefore not super useful. Instead, we replaced the bandlimited assumption with a Lipschitz continuity requirement.

It was difficult to show convergence for the GFT for spectral components associated with eigenvalues close to $0$ (see conjecture 1 from Lecture 17). This is why we showed instead that bandlimited convergent graph signals converge in the fourier domain.

Here, the same thing happens because graphon shift operator eigenvalues accumulate at 0. The Lipschitz continuity addresses this by ensuring all spectral components near 0 are amplified in an increasingly “similar” way. We can see this by looking at how we defined $c$ in the proof: $c=\frac{1-|h_0|}{L(2||\mathcal{X}||{ϵ}^{-1}+1)}$

• If we fix $c$, in order to have $ϵ\to 0$, we need progressively smaller Lipschitz constant $L$. ie, we need flatter and flatter functions
• If we want $c$ to get smaller (ie, we want the region where the spectral components cannot be discriminated to get smaller), we need a larger $L$.

convergence-discriminability tradeoff

In HW3:

• Train a GNN on a subsample of the graph and as we increase the size, the convergence gets better and better
• explanation: convolution converges asymptotically

Transferability: If we want to make an error of at most $ϵ$ …

• how do we pick the size of the subgraph to train on? Can we see a relationship between the size of the graph $n$ and the Lipschitz constant $L$?

Transferability of Graph Convolutions and GNNs

The asymptotic convergence of the lipschitz graph filters reveals an important tradeoff between convergence/transferability and discriminability. We can compare this to the stability-discriminability tradeoff for Lipschitz filters.

$c$-band cardinality

$c$-band cardinality of a graphon $W$ are the number of graphon eigenvalues with magnitude greater than $c$ $n_c(W)=|\{{\lambda }_i:|{\lambda }_i|>c\}|$ Note that this quantity is finite since the graphon shift operator eigenvalues accumulate only at 0.

see c band cardinality

$c$-eigenvalue margin

The $c$-eigenvalue margin of graphons $W$ and $W^{\prime }$ is the minimum difference between and eigenvalue of $W^{\prime }$ outside of the $c$ band and an eigenvalue of $W$: ${\delta }_c(W,W^{\prime })={\min }_{i\ne j}\{|{\lambda }_i(T_{W^{\prime }})-{\lambda }_j(T_W)|:|{\lambda }_i(T_{W^{\prime }})|\ge c\}$

see c eigenvalue margin

Non-asymptotic convergence of graph convolutions

Theorem

Let $(G_n,X_n)\sim (W,\mathcal{X})$ and let graph and graphon convolutions be such that $H(G_n)={\sum }_{k=0}^{\infty }{h}_k{\left(\frac{A_n}{n}\right)}^k\text{ and }{T}_H={\sum }_{k=0}^{\infty }{h}_k{T}_W^k$ Further, assume

1. $||\mathcal{X}||\le 1$ (WLOG)
2. $|h(\lambda )|<1$ and $h(\lambda )$ is $L-$Lipschitz in $[-1,-c]\cup [c,1]$ and $\ell -$Lipschitz in $(-c,c)$

Then we have $||{\mathcal{Y}}_n-\mathcal{Y}||\le \left(L+\frac{\pi n_c}{{\delta }_c}\right)||T_W-T_{W_n}||+(Lc+2)||\mathcal{X}-{\mathcal{X}}_n||+2\ell 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 $||\mathcal{X}-{\mathcal{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 $\mathcal{O}\left(\frac{1}{n}\right)$ by introducing more restrictive requirements.

• Convergence $(G_n,X_n)\to (W,\mathcal{X})$ with appropriate node labelling means approximation improves with $n$ as expected
• The bound grows with $\left(L+\frac{\pi n_c}{{\delta }_c}\right)$
  • 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 ${\delta }_c$
    • a higher $\frac{\pi n_c}{{\delta }_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\ell 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 $\ell =0$, there is always leftover “nontransferable energy” corresponding to the spectral components with $|{\lambda }_i|<c$ which do not converge

see convergence bound for graph convolutions

Review

dsg

Even though graph convolutions converge in the spectral domain, this is not enough for our purposes. Why is that? -?- graph convolutions and graphon convolutions operate in the node domain (not the spectral domain)

What does the lipschitz condition achieve in lipschitz graph convolutions of graph signals converge to lipschitz graphon filters? -?- it ensures all spectral components near 0 are amplified in an increasingly “similar” way.

Summary

For node-domain convergence, we first saw that {==ass||graph convolutions of bandlimited signals converge to the graphon convolution==}. But since graphons have {has||infinite-dimensional spectra}, this can be quite strict and therefore not super useful. Instead, we replaced the {==ass||bandlimited assumption} with {hha||a Lipschitz continuity requirement==}.

• link clean ⏳ 2025-04-22 ✅ 2025-04-22
• add review clean ⏳ 2025-04-22 ✅ 2025-04-22

const { dateTime } = await cJS()
 
return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}