[[lecture-data]]Summary
3. Graphon Signal Processing
Question
Does the GFT converge to the WFT?
Question
And why do we care?
signal's GFT, like the correlation with respect to the graph structure. Since the limiting graphon has no noise, it can reveal the "real"/intrinsic structure of the signal.
high variance of small samples might obscure important information in a
convergence of signals in the Fourier domain
Recall
- convergent graph signals and
- eigenvalues of the induced graphon converge pointwise to the eigenvalues of the limit ie for all
first approach: using convergence of signal and eigenvalues
Conjecture 1
Recall that
\left[\hat{x}_{n}\right]_{i} &= \langle x_{n}, v_{i}^n \rangle \\ \hat{x}_{i} &= \langle {\cal X}, \varphi_{i} \rangle \end{aligned}$$ In order to have convergence of the [[graph fourier transform]] to the [[graphon fourier transform]], we need {==1||convergence of the graph (filter) eigenvectors||convergence==} to the {==1||graphon (filter) [[eigenfunction|eigenfunctions]]||to==} <!--SR:!2026-03-09,53,130--> > [!theorem] Theorem (Davis-Kahan) > > Let $T$ and $T'$ be [[self-adjoint]] [[Hilbert-Schmidt integral operator|Hilbert-Schmidt]] operators with eigenspectra ($\lambda_{i, }, \varphi_{i}$) and $(\lambda_{i}', \varphi_{i}')$ respectively ordered by [[eigenvalue]] magnitude. Then > $$\lvert \lvert \varphi_{i} - \varphi_{i}' \rvert \rvert \leq \frac{\pi}{2} \frac{\lvert \lvert T-T' \rvert \rvert}{d(\lambda_{i}, \lambda_{i}')} $$ > Where $\lvert \lvert \cdot \rvert \rvert$ is the [[operator norm]] and $d(\lambda_{i}, \lambda_{i}')$ is defined as > $$d(\lambda_{i}, \lambda_{i}') \equiv \min (\min_{j \neq i}(\lvert \lambda_{i}-\lambda_{j}' \rvert ), \min_{j \neq i}(\lvert \lambda_{j}-\lambda_{i}' \rvert ))$$ > Call the first interior min $d_{1}$ and the second $d_{2}$ > [!example] > > ![[Attachments/20250402-graph.png]] > $d(\lambda_{i}, \lambda_{i}')$ corresponds to the minimum "eigengap" for the closes eigenvalue for eigenvalue $\lambda_{i}$ in its own spectrum. Smallest > [!NOTE] > > If $d(\cdot,\cdot)$ is large, then this is OK for fast convergence. But if this is small, then we also need small $\lvert \lvert T-T' \rvert \rvert$ to get fast convergence. see [[Davis-Kahan Theorem]] Let $\{ G_{n}, X_{n} \} \to (W,{\cal X})$. We can use the [[Davis-Kahan Theorem]] with $T_{W}$ (the limiting [[graphon shift operator]]) and $T_{W_{n}}$ ([[induced graphon]] shift operator). $$\lvert \lvert \varphi(T_{W_{n}}) - \varphi_{i}(T_{W}) \rvert \rvert \leq \frac{\pi}{2} \frac{\lvert \lvert T_{W} - T_{W_{n}} \rvert \rvert }{d(\lambda_{i}(T_{W}), \lambda_{i}(T_{W_{n}}))} $$ This is good because from [[2025-03-26 lecture 15|lecture 15]], we know that if $G_{n}$ [[convergent graph sequence|converges]] to $W$ in the [[cut norm]], then $T_{W_{n}}$ [[convergent sequence of graph signals|converges]] to $T_{W}$ in $L_{2}$ (cut norm [[Convergence in the cut norm implies convergence in L2]]). Thus we have convergence in the numerator! Does this mean everything is OK? - **No**! The denominator might vanish as $i \to \infty$ since we have $\lambda_{i} \to 0$ from the second part of the [[spectral theorem for self-adjoint compact operators on Hilbert spaces]] - even though we look at $\min(d_{1}, d_{2})$ and $\lambda_{i} \neq \lambda_{j}$ converge to different values (and therefore $d(\cdot) \to \ell>0$ ), it still might not work. - Even if we have eigenvalue convergence, this convergence is not necessarily uniform. (recall the difference between convergence and [[uniform convergence]]) because the graphon eigenvalues accumulate at 0. ![[Attachments/20250402-graph-1.png]] Convergence holds in the sense that for all $\epsilon >0$, there exists $n_{0}$ such that for all $n > n_{0}$, $$\left\lvert \frac{\lambda_{i}(G_{n})}{n} - \lambda_{i}(W) \right\rvert < \epsilon $$ However, $n_{0}$ will be different for each $i$/eigenvalue (non-uniform convergence! we cannot fix a common $n_0$ for each $\epsilon$) > [!NOTE] > > - this is a limitation of graphons > - for dense graphs this is useful > - bounded spectrum > - sparser graphs do not have convergence of spectra, so they are harder to deal with as well > Though the eigenvalues converge, they do not converge uniformly since their accumulation is at 0. So [[2025-04-02 lecture 17#^conj-1|conjecture 1]] is wrong, but in the right direction ### approach 2: > [!def] bandlimited graphon signal > > A [[graphon signal]] $(W, {\cal X})$ is $c$-**bandlimited** if its [[graphon fourier transform]] satisfies $\hat{x}_{i} = 0$ for all $i \in {\cal C} = \{ j\text{ such that }\lvert \lambda_{j} \rvert > c \}$ see [[bandlimited graphon signal]] > [!example] > > "Limiting" the energy to a middle "band" of frequencies about $0$ > ![[Attachments/20250402-graph-2.png]] > ![[Attachments/20250402-graph-3.png]] > [!NOTE] Conjecture 2 (revision of [[#^conj-1|conjecture 1]]) > > Let $(W, {\cal X})$ be $c$-[[bandlimited graphon signal|bandlimited]] and $(G_{n}, X_{n})$ a sequence [[convergent sequence of graph signals|converging]] to $(W, {\cal X})$. Then the [[graph fourier transform|GFT]] $(\hat{x}_{n})_{i}$ converges to the [[graphon fourier transform|WFT]] $\hat{x}_{i}$ > [!theorem] > > Let $(W, {\cal X})$ be $c$-[[bandlimited graphon signal|bandlimited]] and $(G_{n}, X_{n})$ a sequence [[convergent sequence of graph signals|converging]] to $(W, {\cal X})$. Then the [[graph fourier transform|GFT]] $(\hat{x}_{n})_{i}$ converges to the [[graphon fourier transform|WFT]] $\hat{x}_{i}$ > [!proof] > > Let ${\cal C}$ be the set of eigenvalues in the $c$-bandlimited set. Then for all $i \in {\cal C}$, we have > $$\begin{aligned} > \lvert (\hat{x}_{n})_{i} - \hat{x}_{i} \rvert &= \lvert \langle X_{n}, \varphi_{i}^{(n)} \rangle - \langle {\cal X}, \varphi_{i}\rangle \rvert \\ > &= \lvert \langle X_{n}, \varphi_{i}^{(n)} \rangle + \langle {\cal X}, \varphi_{i}^{(n)}\rangle - \langle {\cal X}, \varphi_{i}^n\rangle - \langle {\cal X}, \varphi_{i}\rangle \rvert \\ > &\leq \lvert \lvert {\cal X} - X_{n} \rvert \rvert \cdot \lvert \lvert \varphi_{i}^{(n)} \rvert \rvert + \lvert \lvert {\cal X} \rvert \rvert \cdot \lvert \lvert \varphi_{i}^{(n)} - \varphi_{i} \rvert \rvert > \end{aligned}$$ > > By convergence of $X_{n}$, for all $\epsilon>0$, there exists some $n_{1}$ such that $\lvert \lvert X_{n} - {\cal X} \rvert \rvert \leq \frac{\epsilon}{2}$ for all $n > n_{1}$. > > And for $\lvert \lvert \varphi_{i}^{(n)} -\varphi_{i}\rvert \rvert$, we have > $$\lvert \lvert \varphi_{i}^{(n)} -\varphi_{i}\rvert \rvert \leq \frac{\pi}{2} \frac{\lvert \lvert T_{W}-T_{W_{n}} \rvert \rvert }{d(\lambda_{i}, \lambda_{i}^{(n)})} \leq \frac{\pi}{2} \frac{\lvert \lvert T_{W} -T_{W_{n}} \rvert \rvert }{\min_{i \in {\cal C}} d(\lambda_{i}, \lambda_{i}^{(n)})}$$ > And from $T_{W_{n}} \to T_{W}$, for all $\epsilon>0$, there is some $n_{2}$ such that $\lvert \lvert \varphi_{i}^{(n)} -\varphi_{i}\rvert \rvert \leq \frac{\epsilon}{2}$ for all $n>n_{2}$ > > Thus, for any $\epsilon$ and each $n > \max \{ n_{1}, n_{2} \}$ and for all $i \in {\cal C}$, we have > $$\lvert (\hat{x}_{n})_{i} - \hat{x}_{i} \rvert \leq \lvert \lvert X_{n} - {\cal X} \rvert \rvert\cdot \cancelto{1}{\lvert \lvert \varphi_{i}^{(n)} \rvert \rvert} + \lvert \lvert {\cal X} \rvert \rvert \cdot \lvert \lvert \varphi_{i}^{(n)} - \varphi_{i} \rvert \rvert \leq \frac{\epsilon}{2} + \lvert \cancel{\lvert{\cal X} \rvert \rvert} \frac{\epsilon}{2 \cancel{\lvert \lvert {\cal X} \rvert \rvert} } = \epsilon $$ > And for $i \not\in {\cal C}$, > $$\langle \varphi_{i}(T_{W_{n}}), X_{n} \rangle \to \langle \Psi, {\cal X} \rangle = 0$$ > Where $\Psi \in \perp \text{span}\{ \varphi_{i}: i \in {\cal C} \}$ (orthogonal complement) $\blacksquare$ see [[bandlimited convergent graph signals converge in the fourier domain]] ## Graphon Convolutions [[graphon fourier transform|WFT]] is the {==1||algebraic equivalent==} of [[graph fourier transform|GFT]]; graphon filters have the same {==1||algebraic structure==} of [[graph convolution|graph filters]]. These are the same {==2||shift-and-sum==} operations, but now the {==2||shift==} is the [[graphon shift operator|graphon shift]] $T_{W}$ <!--SR:!2026-08-02,288,250!2026-12-06,363,250--> > [!def] Graphon convolution > > Given a [[graphon signal]] $(W, {\cal X})$, we write the **graphon convolution** as the map > $$\begin{align} > T_{H}&: L_{2}([0,1]) \to L_{2}([0,1]) \\ > T_{H}&: {\cal X} \mapsto {\cal Y} > \end{align}$$ > with > $${\cal Y} = T_{H}{\cal X} = \sum_{k=0}^{K-1} h_{k} T_{W}^{(k)} {\cal X}$$ > and > $$T_{W}^{(k)} {\cal X} = \begin{cases} > \int _{0}^1 W(u, \cdot) (T_{W}^{(k-1)} {\cal X})(u) \, du &k ≥1 \\ > I &k=0 > \end{cases}$$ see [[graphon convolution]] Like [[graph convolution|graph convolutions]], [[graphon convolution|graphon convolutions]] also have a spectral representation (see [[spectral representation of graphon convolutions]]) > [!theorem] > > Given a [[graphon convolution]] with input [[graphon signal]] ${\cal X}$ and output ${\cal Y}$, the [[graphon fourier transform|WFTs]] ${\cal \hat{X}}$ of ${\cal \hat{Y}}$ are related as > $$\begin{align} > {\cal \hat{Y}}_{j} &= \sum_{k=0}^{K-1} h_{k} \lambda_{j}^k {\cal \hat{X}}_{j} \\ > &=\hat{T}_{H}(\lambda_{j}) . {\cal \hat{X}}_{j} \\ > &= h(\lambda_{j}) {\cal \hat{X}}_{j} > \end{align}$$ > Where $h(\lambda_{j})=\sum_{k=0}^{K-1} h_{k} \lambda_{j}^k$ is our polynomial. Here, $\hat{T}_{H}$ acts pointwise on the graphon signal ${\cal X}$ > [!proof] > > $$\begin{align} > {\cal Y} &= \sum_{k=0}^{K-1} h_{k} \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} \lambda_{j}^k \varphi_{j}(v) \underbrace{ \int _{0}^1 \varphi_{j}(u) {\cal X}(u) \, du }_{ \hat{x}_{j} } \\ > &= \sum_{k=0}^{K-1} h_{k} \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} \lambda_{j}^k \varphi_{j}(v) {\cal \hat{X}} \\ > \implies \hat{{\cal Y}}_{i} &= \int _{0}^1 {\cal Y}(u) \varphi_{i}(u) \, du \\ > &= \sum_{k=0}^{K-1} h_{k}\lambda_{i}^k \cancelto{1}{ \int \varphi_{i}^2(u)\, du } \hat{x}_{i} \\ > \implies \hat{{\cal Y}}_{i} &= \sum_{k=0}^{K-1}h_{k}\lambda_{i}^k \hat{x}_{i} > \end{align}$$ > > This is a simple result following the [[diagonalizable|diagonalization]] of $T_{W}^{(k)}$ by $\varphi_{i}$ > [!note] > > Some interesting takeaways (analogues of the [[graph convolution|graph convolution]]) > - Like the WFT, the spectral response of a [[graphon convolution]] is discrete > - the spectral response of the graphon convolution is also pointwise in that the $j$th spectral component of the output ${\cal Y}$ only depends on $\lambda_{j}$ and ${\cal \hat{X}}_{j}$ > - ie ${\cal \hat{Y}}_{j}$ depends only on $\lambda_{j}$ and $\hat{\cal X}_{j}$ > - The spectral response of $T_{H}$ given by $h(\lambda) = \sum_{k=0}^{K-1} h_{k}\lambda^k$ is independent of the underlying $W$ (like the [[spectral representation of graphon convolutions|spectral response]] of $H(S)$ was independent of the graph) > - ie, the spectral response can be written as a polynomial function. The eigenvalues of the graphon determine where we evaluate this function. (samples of function that is eigenvalues/spectrum) > [!example] > > ![[Attachments/20250402-graph-4.png]] > > [!important] > > Given the same (fixed) coefficients $h_{k}$, define the [[graph convolution|graph convolution]] $H(S)x = \sum_{k=0}^{K-1} h_{k} S^k x$. The [[spectral representation of a convolutional graph filter|spectral representation]] of that convolution is $h(\lambda) =\sum_{k=0}^{K-1} h_{k}\lambda^k$ > - this is the **same** as the [[spectral representation of graphon convolutions]]/function for the same coefficients. > - The only difference is where the function is evaluated. > - For a [[graphon]], we evaluate it at the [[graphon shift operator]] [[eigenvalue|eigenvalues]] $\lambda_{j}(T_{W})$ for [[graphon signal]] $T_{H_{j}}$ > - For a [[graph]], this is the [[graph shift operator]] eigenvalues $\lambda_{j}(S)$ for the [[graph signals|graph signal]] $H(S)_j$ >[!question] > > Why do we care? Given a [[convergent graph sequence]] $G_{n}\to W$, we know that $$\frac{\lambda_{i}(G_{n})}{n} \to \lambda_{i}(W)\,\,\,\forall i$$ And if we fix coefficients $h_{k}$, the [[graph convolution]] $H(S)$ and the [[graphon convolution]] $T_H$ have the same spectral response (from above) $$h(\lambda) = \sum_{k=0}^{K-1} h_{k}\lambda^k$$ > [!theorem] > > Given $G_{n} \to W$ and $H(G_{N}) = \sum_{k=0}^{K-1} h_{k} (\frac{A_{n}}{n})^k$ and $T_{H} = \sum_{k=0}^{K-1} h_{k}T_{W}^{(k)}$, we have > $$\hat{H}\to \hat{T}_{H}$$ > in the sense that > $$\hat{T}_{H}(\lambda_{j}(T_{W_{n}})) \to \hat{T}_{H}(\lambda_{j}(T_{W})) \,\,\,\forall\,j \in \mathbb{Z} \setminus \{ 0 \}$$ > the graph convolution converges to the graphon convolution (with the same filter coefficients) in the spectral domain. This says 1. Convergence of the graph convolution to the graphon convolution in the spectral domain (first line) 2. Convergence of the spectral response of the graphon convolution on the induced graphon converges pointwise to the spectral response of the limiting graphon convolution (second line) see [[the graph convolution converges to the graphon convolution in the spectral domain for a convergent sequence of graph signals]] And this holds for all eigenvalue indices $j$. > [!Caution] Problem though > > Spectral convergence is not enough to do what we want. Graph convolutions operate in the node domain. # Review #flashcards/math/dsg We'd like to use the **Davis-Kahan Theorem** to bound the distance between the eigenfunctions of the *induced graphon shift operator* and the *limiting graphon shift operator* to show **convergence in the Fourier domain**. Why does this fail? (2 reasons) -?- 1. The denominator of the bound might vanish because $\lambda_{i} \to 0$ as $i \to \infty$ (the distances are getting smaller and smaller) 2. The eigenvalues only accumulate at 0. This means we may have *non-uniform* convergence in the eigenvalues <!--SR:!2026-02-18,16,130--> {==1||bandlimited||condition==} convergent graph signals converge {==2||in the fourier domain.||result (how/where)==} <!--SR:!2026-11-07,343,250!2026-06-27,145,170--> ```datacorejsx 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> } ```