lipschitz graph convolutions of graph signals converge to lipschitz graphon filters

[[concept]]

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 [[Concept Wiki/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 [[Concept Wiki/bandlimited graphon signal\|bandlimited]] components* (${\cal C}$) and *non-bandlimited components (${\cal C}^c$)* of the signal. Then, by the [[Concept Wiki/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 [[Concept Wiki/bandlimited graphon signal\|bandlimited]] ${\cal X}$ with bandwith $c$. Thus, $(\star^1)$ vanishes as a direct applications of the previous result ([[Concept Wiki/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 [[Concept Wiki/orthogonal vectors\|orthonormal]] [[Concept Wiki/basis]] for both the graph and the graphon (see the appropriate [[Concept Wiki/spectral theorem for self-adjoint compact operators on Hilbert spaces\|spectral theorem]]). For $(\star^3)$, by writing both the [[Concept Wiki/induced graphon signal]] and the limiting [[Concept Wiki/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 [[Concept Wiki/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}$ ^proof

NOTE

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

see also

• graph convolutions of bandlimited signals converge to the graphon convolution

Review

dsg

{lipschitz graph convolutions} of graph signals converge to {lipschitz graphon filters}

Review

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) ==}

Mentions

Mentions

TABLE file.mday as "Last Modified"
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
SORT file.mday ASC
SORT file.name ASC

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>
}