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

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