2025-04-02 lecture 17

[[lecture-data]]

Summary

3. Graphon Signal Processing

Question

Does the GFT converge to the WFT?

Question

And why do we care?

Answer

high variance of small samples might obscure important information in a 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.

convergence of signals in the Fourier domain

Recall

convergent graph signals $(G_{n}, X_{n}) \to (W, X)$ and
eigenvalues of the induced graphon converge pointwise to the eigenvalues of the limit ie $lim_{n \to \infty} \frac{λ_{j} (A_{n})}{n} = λ_{j} (W)$ for all $j$

first approach: using convergence of signal and eigenvalues

Conjecture 1

Given the two above, it is reasonable to conjecture that the GFT $[{\hat{x}}_{n}]_{i}$ converges to the WFT $[\hat{x}]_{i}$ for all $i$ .

Recall that

\begin{aligned} {[{\hat{x}}_{n}]}_{i} & = ⟨ x_{n}, v_{i}^{n} ⟩ \\ {\hat{x}}_{i} & = ⟨ X, φ_{i} ⟩ \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) eigenfunctions||to}

Theorem (Davis-Kahan)

Let $T$ and $T^{'}$ be self-adjoint Hilbert-Schmidt operators with eigenspectra ( $λ_{i,}, φ_{i}$ ) and $(λ_{i}^{'}, φ_{i}^{'})$ respectively ordered by eigenvalue magnitude. Then

| | φ_{i} - φ_{i}^{'} | | \leq \frac{π}{2} \frac{| | T - T^{'} | |}{d (λ_{i}, λ_{i}^{'})}

Where $| | \cdot | |$ is the operator norm and $d (λ_{i}, λ_{i}^{'})$ is defined as

d (λ_{i}, λ_{i}^{'}) \equiv min (min_{j \neq i} (| λ_{i} - λ_{j}^{'} |), min_{j \neq i} (| λ_{j} - λ_{i}^{'} |))

Call the first interior min $d_{1}$ and the second $d_{2}$

Example

$d (λ_{i}, λ_{i}^{'})$ corresponds to the minimum "eigengap" for the closes eigenvalue for eigenvalue $λ_{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 $| | T - T^{'} | |$ to get fast convergence.

see Davis-Kahan Theorem

Let ${G_{n}, X_{n}} \to (W, X)$ . We can use the Davis-Kahan Theorem with $T_{W}$ (the limiting graphon shift operator) and $T_{W_{n}}$ (induced graphon shift operator).

| | φ (T_{W_{n}}) - φ_{i} (T_{W}) | | \leq \frac{π}{2} \frac{| | T_{W} - T_{W_{n}} | |}{d (λ_{i} (T_{W}), λ_{i} (T_{W_{n}}))}

This is good because from lecture 15, we know that if $G_{n}$ converges to $W$ in the cut norm, then $T_{W_{n}}$ 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 $λ_{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 $λ_{i} \neq λ_{j}$ converge to different values (and therefore $d (\cdot) \to ℓ > 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.

Convergence holds in the sense that for all $ϵ > 0$ , there exists $n_{0}$ such that for all $n > n_{0}$ ,

| \frac{λ_{i} (G_{n})}{n} - λ_{i} (W) | < ϵ

However, $n_{0}$ will be different for each $i$ /eigenvalue (non-uniform convergence! we cannot fix a common $n_{0}$ for each $ϵ$ )

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 conjecture 1 is wrong, but in the right direction

approach 2:

bandlimited graphon signal

A graphon signal $(W, X)$ is $c$ -bandlimited if its graphon fourier transform satisfies ${\hat{x}}_{i} = 0$ for all $i \in C = {j such that | λ_{j} | > c}$

see bandlimited graphon signal

Example

"Limiting" the energy to a middle "band" of frequencies about $0$

Conjecture 2 (revision of conjecture 1)

Let $(W, X)$ be $c$ -bandlimited and $(G_{n}, X_{n})$ a sequence converging to $(W, X)$ . Then the GFT $({\hat{x}}_{n})_{i}$ converges to the WFT ${\hat{x}}_{i}$

Theorem

Let $(W, X)$ be $c$ -bandlimited and $(G_{n}, X_{n})$ a sequence converging to $(W, X)$ . Then the GFT $({\hat{x}}_{n})_{i}$ converges to the WFT ${\hat{x}}_{i}$

Proof

Let $C$ be the set of eigenvalues in the $c$ -bandlimited set. Then for all $i \in C$ , we have

\begin{aligned} | ({\hat{x}}_{n})_{i} - {\hat{x}}_{i} | & = | ⟨ X_{n}, φ_{i}^{(n)} ⟩ - ⟨ X, φ_{i} ⟩ | \\ = | ⟨ X_{n}, φ_{i}^{(n)} ⟩ + ⟨ X, φ_{i}^{(n)} ⟩ - ⟨ X, φ_{i}^{n} ⟩ - ⟨ X, φ_{i} ⟩ | \\ \leq | | X - X_{n} | | \cdot | | φ_{i}^{(n)} | | + | | X | | \cdot | | φ_{i}^{(n)} - φ_{i} | | \end{aligned}

By convergence of $X_{n}$ , for all $ϵ > 0$ , there exists some $n_{1}$ such that $| | X_{n} - X | | \leq \frac{ϵ}{2}$ for all $n > n_{1}$ .

And for $| | φ_{i}^{(n)} - φ_{i} | |$ , we have

| | φ_{i}^{(n)} - φ_{i} | | \leq \frac{π}{2} \frac{| | T_{W} - T_{W_{n}} | |}{d (λ_{i}, λ_{i}^{(n)})} \leq \frac{π}{2} \frac{| | T_{W} - T_{W_{n}} | |}{min_{i \in C} d (λ_{i}, λ_{i}^{(n)})}

And from $T_{W_{n}} \to T_{W}$ , for all $ϵ > 0$ , there is some $n_{2}$ such that $| | φ_{i}^{(n)} - φ_{i} | | \leq \frac{ϵ}{2}$ for all $n > n_{2}$

Thus, for any $ϵ$ and each $n > max {n_{1}, n_{2}}$ and for all $i \in C$ , we have

| ({\hat{x}}_{n})_{i} - {\hat{x}}_{i} | \leq | | X_{n} - X | | \cdot {| | φ_{i}^{(n)} | |}^{1} + | | X | | \cdot | | φ_{i}^{(n)} - φ_{i} | | \leq \frac{ϵ}{2} + | | X | | \frac{ϵ}{2 | | X | |} = ϵ

And for $i \notin C$ ,

⟨ φ_{i} (T_{W_{n}}), X_{n} ⟩ \to ⟨ Ψ, X ⟩ = 0

Where $Ψ \in⊥ span {φ_{i} : i \in C}$ (orthogonal complement) $◼$

see bandlimited convergent graph signals converge in the fourier domain

Graphon Convolutions

WFT is the {1||algebraic equivalent} of GFT; graphon filters have the same {1||algebraic structure} of graph filters. These are the same {2||shift-and-sum} operations, but now the {2||shift} is the graphon shift $T_{W}$

Graphon convolution

Given a graphon signal $(W, X)$ , we write the graphon convolution as the map

\begin{aligned} T_{H} & : L_{2} ([0, 1]) \to L_{2} ([0, 1]) \\ T_{H} & : X \mapsto Y \end{aligned}

with

Y = T_{H} X = \sum_{k = 0}^{K - 1} h_{k} T_{W}^{(k)} X

and

T_{W}^{(k)} X = {\begin{cases} \int_{0}^{1} W (u, \cdot) (T_{W}^{(k - 1)} X) (u) d u & k \geq 1 \\ I & k = 0 \end{cases}

see graphon convolution

Like graph convolutions, graphon convolutions also have a spectral representation (see spectral representation of graphon convolutions)

Theorem

Given a graphon convolution with input graphon signal $X$ and output $Y$ , the WFTs $\hat{X}$ of $\hat{Y}$ are related as

\begin{aligned} {\hat{Y}}_{j} & = \sum_{k = 0}^{K - 1} h_{k} λ_{j}^{k} {\hat{X}}_{j} \\ = {\hat{T}}_{H} (λ_{j}) . {\hat{X}}_{j} \\ = h (λ_{j}) {\hat{X}}_{j} \end{aligned}

Where $h (λ_{j}) = \sum_{k = 0}^{K - 1} h_{k} λ_{j}^{k}$ is our polynomial. Here, ${\hat{T}}_{H}$ acts pointwise on the graphon signal $X$

Proof

$\begin{aligned} Y & = \sum_{k = 0}^{K - 1} h_{k} \sum_{j \in Z ∖ {0}} λ_{j}^{k} φ_{j} (v) \underset{{\hat{x}}_{j}}{\underset{⏟}{\int_{0}^{1} φ_{j} (u) X (u) d u}} \\ = \sum_{k = 0}^{K - 1} h_{k} \sum_{j \in Z ∖ {0}} λ_{j}^{k} φ_{j} (v) \hat{X} \\ ⟹ {\hat{Y}}_{i} & = \int_{0}^{1} Y (u) φ_{i} (u) d u \\ = \sum_{k = 0}^{K - 1} h_{k} λ_{i}^{k} {\int φ_{i}^{2} (u) d u}^{1} {\hat{x}}_{i} \\ ⟹ {\hat{Y}}_{i} & = \sum_{k = 0}^{K - 1} h_{k} λ_{i}^{k} {\hat{x}}_{i} \end{aligned}$

This is a simple result following the diagonalization of $T_{W}^{(k)}$ by $φ_{i}$

Note

Some interesting takeaways (analogues of the 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 $Y$ only depends on $λ_{j}$ and ${\hat{X}}_{j}$
- ie ${\hat{Y}}_{j}$ depends only on $λ_{j}$ and ${\hat{X}}_{j}$
The spectral response of $T_{H}$ given by $h (λ) = \sum_{k = 0}^{K - 1} h_{k} λ^{k}$ is independent of the underlying $W$ (like the 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

Important

Given the same (fixed) coefficients $h_{k}$ , define the graph convolution $H (S) x = \sum_{k = 0}^{K - 1} h_{k} S^{k} x$ . The spectral representation of that convolution is $h (λ) = \sum_{k = 0}^{K - 1} h_{k} λ^{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 eigenvalues $λ_{j} (T_{W})$ for graphon signal $T_{H_{j}}$
- For a graph, this is the graph shift operator eigenvalues $λ_{j} (S)$ for the graph signal $H (S)_{j}$

Question

Why do we care?

Given a convergent graph sequence $G_{n} \to W$ , we know that

\frac{λ_{i} (G_{n})}{n} \to λ_{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 (λ) = \sum_{k = 0}^{K - 1} h_{k} λ^{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} (λ_{j} (T_{W_{n}})) \to {\hat{T}}_{H} (λ_{j} (T_{W})) \forall j \in Z ∖ {0}

the graph convolution converges to the graphon convolution (with the same filter coefficients) in the spectral domain.

This says

Convergence of the graph convolution to the graphon convolution in the spectral domain (first line)
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$ .

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)
-?-

The denominator of the bound might vanish because $λ_{i} \to 0$ as $i \to \infty$ (the distances are getting smaller and smaller)
The eigenvalues only accumulate at 0. This means we have non-uniform convergence in the eigenvalues

{1||bandlimited||condition} convergent graph signals converge {2||in the fourier domain.||result}

Created 2025-04-02 Last Modified 2025-06-05