2025-03-31 lecture 16

[[lecture-data]]

Announcement

Final project scheduling random sequence generator: to be posted on Cavas later.

3. Graphon Signal Processing

Graphon signal

A graphon signal is defined as a function
$X : [0, 1] \to R$

Note

We focus on signals in $L_{2}$ , or "finite energy signals" $X \in L_{2} ([0, 1])$ :
$\int _{0}^1 \lvert {\cal X}(u) \rvert^2 , du \leq B < \infty $

Induced Graphon Signal

Let $(G_{n}, X_{n})$ be a graph signal. The induced graphon signal is defined as the pair $(W_{n}, X_{n})$ where $W_{n}$ is the induced graphon and
$X_{n} (u) = \sum_{i = 1}^{n} [x_{n}]_{i} 1 (u \in I_{i})$
Where $1$ is the indicator function and
$I_{k} = {\begin{cases} [\frac{k - 1}{n}, \frac{k}{n}) 1 \leq k \leq n - 1 \\ [\frac{n - 1}{n}, 1] k = n \end{cases}$

convergent sequence of graph signals

Let ${G_{n}, x_{n}}$ be a sequence of graph signals and $X$ . If there exists a sequence of permutations ${π_{n}}$ such that for all motifs $F$

\begin{aligned} lim_{n \to \infty} t (F, G_{n}) & \to \tilde{t} (F, W) and \\ lim_{n \to \infty} | | X_{π_{n} (G_{n})} - X | |_{2} & \to 0 \end{aligned}

Where

$t$ and $\tilde{t}$ are the homomorphism density and graphon homomorphism density respectively
$W$ is a graphon
$X$ is a graphon signal

Then ${G_{n}, x_{n}}$ is a sequence of convergent graph signals with limit $(W, X)$ .

see convergent sequence of graph signals

Notes on Permutation

The permutation sequence is independent of the node labels.
If we define a cut distance for graphon signals, then we can define a convergent sequence of graph signals without using the permutations. This is done in Levie 2023.
Since signals we work with are in $L_{2}$ , it is not too bad to use this definition.

The graphon shift operator

Let $W$ be a graphon. The graphon shift operator is the integral linear operator $T_{W} : L^{2} ([0, 1]) \to L^{2} ([0, 1])$ which maps $x \mapsto T_{W} x$

T_{W} x = \int_{0}^{1} W (u, \cdot) x (u) d x

Note

A graphon shift operator is a Hilbert-Schmidt integral operator (continuous and compact) because graphons are bounded

⟹ W \in L^{\infty} ⟹ W \in L^{2}

And has Hilbert-Schmidt norm

| | T_{W} | |_{H S}^{2} = | | W | |_{2}^{2} = \int_{0}^{1} \int_{0}^{1} W^{2} (u, v) d u d v

see graphon shift operator

Graphon Fourier Transform

Theorem

Let $W$ be a graphon and $T_{W}$ its graphon shift operator. Then $T_{W}$ is self-adjoint.

Proof

graphons are symmetric. So

⟨ T_{W} x, y ⟩ = ⟨ x, T_{W} y ⟩

see graphon shift operators are self-adjoint

Theorem

Let $H$ be Hilbert space and $T : H \to H$ a self-adjoint, compact operator. Then there exists an orthonormal basis of $H$ consisting of eigenfunctions of $T$ .

This basis, call it ${φ_{i}}$ , is countably infinite with corresponding real eigenvalues ${λ_{i}}$ satisfying $λ_{i} \to 0$ as $i \to \infty$ .

Note

For graphon signals, $T = T_{W}$ and $H = L_{2} ([0, 1])$

see spectral theorem for self-adjoint compact operators on Hilbert spaces

eigenfunction

Let $A$ be a linear operator on a function space $S$ . An eigenfunction $f : S \to S$ is a function (not zero everywhere) with associated eigenvalue $λ$ such that

A f = λ f

Eigenfunctions are a generalization of eigenvectors to infinite dimensions.

see eigenfunction

The function $φ : [0, 1] \to R$ is an eigenfunction of graphon signal $T_{W}$ with eigenvalue $λ$ if $T_{W} φ = λ φ$ . There are infinitely many $φ, λ$ pairs (possibly with geometric multiplicity larger than 1), but the eigenpairs are countable

{(λ_{i}, φ_{i})}_{i = 1}^{\infty}

Since the $φ_{i}$ form an orthonormal basis, they have unit norm

| | φ_{i} | |^{2} = \int_{0}^{1} \int_{0}^{1} φ_{i}^{2} (u) d u^{2}

Takeaway

We can write the graphon $W$ in the basis ${φ_{i}}$ for its graphon shift operator as

W (u, v) = \sum_{i = 0}^{1} λ_{i} φ_{i} (u) φ_{i} (v)

(compare this to $S = V Λ V^{*}$ for graph shift operator)

see we can write a graphon in the basis of its shift operator

Eigenvalue range

For a graphon $W$ and graphon shift operator $T_{W}$ , the eigenvalues of $T_{W}$ lie in {1|| $[- 1, 1]$ }. This is because

{2|| $0 \leq W \leq 1$ } and
{2|| $| | W | |_{2} \leq 1$ },

(The reasoning is analogous to matrix norms are bounded below by the spectral radius)

And since {2|| $| | T_{W} | |_{H S} \leq 1$ }, the only possible accumulation point for the eigenvalues of $T_{W}$ is {1||0}

(this is a direct result of the second part of {3||the spectral theorem for self-adjoint compact operators on Hilbert spaces})

Thus we can order the eigenvalues as ${λ_{j}}_{j \in Z ∖ {0}}$ so that

λ_{- 1} \leq λ_{- 2} \leq \dots \leq 0 \leq \dots \leq λ_{2} \leq λ_{1}

Example

Eigenvalue accumulation at $0$ (and only at $0$ ) equivalently means that for any $c \neq 0$

| {λ_{i} : | λ_{i} | \geq c} | = n_{c} \leq \infty

see graphon shift operator eigenvalues

Eigenvalue Convergence

Theorem

Let ${G_{n}}$ be a convergent graph sequence with limit graphon $W$ . Then

lim_{n \to \infty} \frac{λ_{j} (A_{n})}{n} = λ_{j} (W) = lim_{n \to \infty} λ_{j} (T_{W_{n}})

ie, the eigenvalues of the induced graphon converge to the eigenvalues of the limit.

Where

$A_{n}$ is the adjacency matrix of $G_{n}$
$W_{n}$ is the graphon induced by $A_{n}$
$T_{W_{n}}$ the graphon shift operator for $W_{n}$

Proof

$W_{n} (u, v) = \sum_{i, j = 1}^{n} [A_{n}]_{i j} 1 (u \in I_{i}) 1 (v \in I_{j})$ $A_{n} = V_{n} Λ_{n} V_{n}^{*}$

Thus

\begin{aligned} T_{W_{n}} φ (v) & = \int_{0}^{1} W_{n} (u, v) φ (u) d u & = λ φ (v) \\ = \int_{0}^{1} \sum_{i, j = 1}^{n} [A_{n}]_{i j} 1 (u \in I_{i}) 1 (v \in I_{j}) φ (u) d u & = λ φ (v) \\ = 1 (v \in I_{j}) \int_{0}^{1} \sum_{i, j = 1}^{n} [A_{n}]_{i j} 1 (u \in I_{i}) φ (u) d u & = λ φ (v) \\ ⟹ & = \sum_{i, j = 1}^{n} [A_{n}]_{i j} \int_{0}^{1} 1 (u \in I_{i}) φ (u) d u & = λ φ (v \in I_{j}) \end{aligned}

LHS is a constant for each $v \in I_{j}$ . This means that $φ$ is a step function $φ (v \in I_{j}) = x_{j}$ . Thus, we can rewrite the last line as

\begin{aligned} λ x_{j} & = \sum_{i = 1}^{n} [A_{n}]_{i j} x_{i} \frac{1}{n} \end{aligned}

since for each $i$ we have $φ (u) = {\begin{cases} x_{i}, x_{i} \in I_{i} \\ 0, otherwise \end{cases}$ . The above is just a matrix multiplication, so we get

\begin{aligned} ⟹ λ x & = \frac{1}{n} A_{n} x \\ ⟹ λ_{j} (T_{W_{n}}) & = \frac{λ_{j} (A_{n})}{n} \forall j \end{aligned}

For convergence, this means that

\begin{aligned} (1) & t (c_{k}, G_{n}) & = \sum_{i = 1}^{n} λ_{i}^{k} \\ (2) & t (c_{k}, G_{n}) & \to \tilde{t} (c_{k}, W) \end{aligned}

where

$c_{k}$ is the $k$ -cycle graph
$t$ is the graph homomorphism density
$\tilde{t}$ is the graphon homomorphism density

(the full proof involves writing out the expressions for (1) and showing (2) by showing the elements in the sum converge pointwise. We do not show this for this class.)

see eigenvalues of the induced graphon converge pointwise to the eigenvalues of the limit

the graphon Fourier transform

Note that $T_{W} X$ can be written as

\begin{aligned} (T_{W} x) (v) & = \int_{0}^{1} W (u, v) X (u) d u \\ = \int_{0}^{1} \sum_{j \in Z ∖ {0}} λ_{j} φ_{j} (u) φ_{j} (v) X (u) d u \\ = \sum_{j \in Z ∖ {0}} λ_{j} φ_{j} (v) \int X (u) φ_{j} (u) d u \end{aligned}

ie we can represent the {1||graphon signal $X$ } in the {2||graphon eigenbasis}. This {2||change of basis} is the {3||graphon fourier transform}.

Graphon Fourier transform

The graphon fourier transform of a graphon signal $(W, X)$ is a functional $\hat{X} = W F T (X)$ defined as

{\hat{X}}_{j} = \hat{X} (λ_{j}) = \int_{0}^{1} X (u) φ_{j} (u) d u

where $λ_{j}$ are the eigenvalues of the graphon $W$ and ${φ_{i}}$ are the eigenfunctions.

Note

Since the $λ_{j}$ are countable, the WFT is always defined.

Inverse graphon Fourier transform

Let $W$ be a graphon and $X$ a graphon signal. The inverse graphon fourier transform (iWFT) is defined as

i W F T (\hat{X}) = \sum_{j \in Z ∖ {0}} \hat{X} (λ_{j}) φ_{j} = X

we recover $X$ since ${φ_{j}}$ are an orthonormal basis. This means that iWFT is an proper inverse of the graphon fourier transform.

see inverse graphon fourier transform

Question

Does the graph fourier transform converge to the graphon fourier transform?

Why do we care? lecture 16 ipynb
Misclassification on noisy SBM, but graphon has no issues. So the induced graphon is helpful if it converges. Spectrum for graphon is much more useful - we can see the number of communities in the spectral content

think about the alignment with this??? This is basically the reasoning for the complexity seen in the last layer for classification? brice
smaller graph = bad (30 nodes) and noisy
50, 100, 300 nodes = good -> better
same for projection

signal and projection

projection noisy for graph

intra- and inter- community probabilities fairly close for this example (close to information theoretic threshold)

Next time: more on this

Created 2025-03-31 Last Modified 2025-05-13