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

WLOG, we assume that $|h(\lambda )|\le 1\mathrm{\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)}$$

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

$$\{\begin{array}{ll}j\in \mathcal{C}& =\{i\text{ s.t. }|{\lambda }_i|\ge c\}\\ j\notin \mathcal{C}& =\{i\text{ s.t. }|{\lambda }_i|<c\}\end{array}\text{ where }c=\frac{1-|h_0|}{L(2||\mathcal{X}||{ϵ}^{-1}+1)}$$

Where we fix some $ϵ>0$, $h_0=h(0)$, and $L$ is the Lipschitz constant. We can choose $ϵ$ such that $c=k\mathrm{\forall }k\in [-1,1]$. Further, note that this creates a set of bandlimited components ($\mathcal{C}$) and non-bandlimited components (${\mathcal{C}}^c$) of the signal.

Then, by the triangle inequality, we have

$$\begin{array}{rl}||\mathcal{Y}-{\mathcal{Y}}_n||& =\left||\sum _{j\in \mathbb{Z}\setminus \{0\}}h({\lambda }_j){\hat{\mathcal{X}}}_j{\phi }_j-\sum _{j\in \mathbb{Z}\setminus \{0\}}h({\lambda }_j^{(n)})[{\hat{X}}_n{]}_j{\phi }_j^{(n)}|\right|\\ & \le \left||\sum _{j\in \mathcal{C}}h({\lambda }_j{\hat{\mathcal{X}}}_j{\phi }_j)-\sum _{j\in \mathcal{C}}h({\lambda }_j^{(n)})[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|({\star }^1)\\ & +\left||\sum _{j\notin \mathcal{C}}h({\lambda }_j{\hat{\mathcal{X}}}_j{\phi }_j)-\sum _{j\notin \mathcal{C}}h({\lambda }_j^{(n)})[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|({\star }^2)\end{array}$$

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 $\mathcal{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\le h({\lambda }_j)\le h_0+Lc\mathrm{\forall }j\notin \mathcal{C}$$

Then we can write

$$\begin{array}{rl}({\star }^2)& =\left||\sum _{j\notin \mathcal{C}}h({\lambda }_j{\hat{\mathcal{X}}}_j{\phi }_j)-\sum _{j\notin \mathcal{C}}h({\lambda }_j^{(n)})[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|\\ & \le (h_0+Lc)\left||\sum _{j\notin \mathcal{C}}h({\lambda }_j{\hat{\mathcal{X}}}_j{\phi }_j)-\sum _{j\notin \mathcal{C}}h({\lambda }_j^{(n)})[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|\\ & \le \underset{({\star }^3)}{\underbrace{h_0\left||\sum _{j\notin \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j-[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|}}+\underset{(\ast )\le Lc||\mathcal{X}||}{\underbrace{Lc\left|\left|\sum _{j\notin \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j\right|\right|}}+\underset{({\star }^4)}{\underbrace{Lc\left||\sum _{j\notin \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|}}\end{array}$$

We can see $(\ast )$ follows since $\sum _{j\notin \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j$ is a portion of graphon signal $\mathcal{X}=\sum _{j\in \mathbb{Z}\setminus \{0\}}{\hat{\mathcal{X}}}_j{\phi }_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 }^{†})\sum _{j\notin \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}={\mathcal{X}}_n-\sum _{j\in \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}$$

We can do this because the $\phi$ form an orthonormal basis for both the graph and the graphon (see the appropriate spectral theorem).

For $({\star }^3)$, by writing both the induced graphon signal and the limiting graphon signal in terms of the identity $({\star }^{†})$, we can get

$$\begin{array}{rl}\left||\sum _{j\notin \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j-[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|& =\left||(\mathcal{X}-\sum _{j\in \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j)-({\mathcal{X}}_n-\sum _{j\in \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)})|\right|\\ & \le \underset{{\mathcal{X}}_n\to \mathcal{X}}{\underbrace{||\mathcal{X}-{\mathcal{X}}_{\mathcal{n}}||}}+\underset{\text{converges (bandlimited signal)}}{\underbrace{\left||\sum _{j\in \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j-[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|}}\\ & <ϵ\end{array}$$

Where $ϵ$ 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 convergence), we are done for $({\star }^3)$.

Finally, for $({\star }^4)$,

$$\begin{array}{rl}\left||\sum _{j\notin \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|& =\left||{\mathcal{X}}_n-\sum _{j\in \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}+\mathcal{X}-\mathcal{X}|\right|\\ & \le \underset{{\mathcal{X}}_{\mathcal{n}}\to \mathcal{X}}{\underbrace{||{\mathcal{X}}_n-\mathcal{X}||}}+\underset{\text{converges (bandlimited)}}{\underbrace{\left||\sum _{j\in \mathcal{C}}[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}-{\hat{\mathcal{X}}}_j{\phi }_j|\right|}}+\underset{\le ||\mathcal{X}||}{\underbrace{\left|\left|\sum _{j\notin \mathcal{C}}{\hat{\mathcal{X}}}_j{\phi }_j\right|\right|}}\\ & <ϵ+||\mathcal{X}||\end{array}$$

Thus we get that

$$\begin{array}{rl}({\star }^2)& =\left||\sum _{j\notin \mathcal{C}}h({\lambda }_j{\hat{\mathcal{X}}}_j{\phi }_j)-\sum _{j\notin \mathcal{C}}h({\lambda }_j^{(n)})[{\hat{\mathcal{X}}}_n{]}_j{\phi }_j^{(n)}|\right|\\ & \le Lc||\mathcal{X}||+h_0ϵ+Lc(ϵ+||\mathcal{X}||)\\ & <\widetilde{ϵ}\end{array}$$

for all $n>N_{ϵ}$

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$.

• graph convolutions of bandlimited signals converge to the graphon convolution

For the convergence of Lipschitz graph convolutions to Lipschitz graphon convolutions, we define

$$c=\frac{1-|h_0|}{L(2||\mathcal{X}||{ϵ}^{-1}+1)}$$

Where $||\mathcal{X}||$ and $|h_0|$ are fixed.

• If we fix $c$, in order to have $ϵ\to 0$, we need {ah||progressively smaller Lipschitz constant $L$}. ie, we need {ah||flatter and flatter functions}
• If we want $c$ to get smaller (ie, we want {ha||a smaller indiscriminable region}), we need {==ha||a larger $L$ (more variation in the function) ==}