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 ${\cal X}: [0,1] \to \mathbb{R}$$

[!NOTE]

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

[!def] Induced Graphon Signal

Let $(G_n,X_n)$ be a graph signal. The induced graphon signal is defined as the pair $(W_n,{\mathcal{X}}_n)$ where $W_n$ is the induced graphon and {\cal X}_{n}(u) = \sum_{i=1}^n [x_{n}]_{i} \mathbb{1}(u \in I_{i})$$ Where \mathbb{1}$istheindicatorfunctionand$I_{k} = \begin{cases} [ \frac{k-1}{n}, \frac{k}{n} );;;1 \leq k \leq n-1 \ \left[ \frac{n-1}{n}, 1 \right] ;;; k=n \end{cases}$$

convergent sequence of graph signals

Let $\{G_n,x_n\}$ be a sequence of graph signals and $\mathcal{X}$ . If there exists a sequence of permutations $\{{\pi }_n\}$ such that for all motifs $F$

\lim_{ n \to \infty } t(F, G_{n}) &\to \tilde{t}(F,W) \,\,\,\text{and} \\ \lim_{ n \to \infty } \lvert \lvert {\cal X}_{\pi_{n}(G_{n})} - {\cal X} \rvert \rvert_{2} &\to 0 \end{align}$$ Where - $t$ and $\tilde{t}$ are the [[homomorphism density]] and [[graphon homomorphism density]] respectively - $W$ is a [[graphon]] - ${\cal X}$ is a [[graphon signal]] Then $\{ G_{n}, x_{n} \}$ is a **sequence of convergent graph signals** with limit $(W, {\cal 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)dx$

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|{|}_{HS}^2=||W|{|}_2^2={\int }_0^1{\int }_0^1{W}^2(u,v)dudv$

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 $\{{\phi }_i\}$, is countably infinite with corresponding real eigenvalues $\{{\lambda }_i\}$ satisfying ${\lambda }_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 $\lambda$ such that $Af=\lambda f$ Eigenfunctions are a generalization of eigenvectors to infinite dimensions.

see eigenfunction

The function $\phi :[0,1]\to \mathbb{R}$ is an eigenfunction of graphon signal $T_W$ with eigenvalue $\lambda$ if $T_W\phi =\lambda \phi$. There are infinitely many $\phi ,\lambda$ pairs (possibly with geometric multiplicity larger than 1), but the eigenpairs are countable $\{({\lambda }_i,{\phi }_i){\}}_{i=1}^{\infty }$ Since the ${\phi }_i$ form an orthonormal basis, they have unit norm $||{\phi }_i|{|}^2={\int }_0^1{\int }_0^1{\phi }_i^2(u)d{u}^2$

Takeaway

We can write the graphon $W$ in the basis $\{{\phi }_i\}$ for its graphon shift operator as $W(u,v)={\sum }_{i=0}^1{\lambda }_i{\phi }_i(u){\phi }_i(v)$ (compare this to $S=V\Lambda V^{\ast }$ 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\le W\le 1$==} and
• {==2||$||W|{|}_2\le 1$==},

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

And since {==2||$||T_W|{|}_{HS}\le 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 $\{{\lambda }_j{\}}_{j\in \mathbb{Z}\setminus \{0\}}$ so that ${\lambda }_{-1}\le {\lambda }_{-2}\le \cdots \le 0\le \cdots \le {\lambda }_2\le {\lambda }_1$

Example

Eigenvalue accumulation at $0$ (and only at $0$) equivalently means that for any $c\ne 0$ $\left|\{{\lambda }_i:|{\lambda }_i|\ge c\}\right|=n_c\le \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{{\lambda }_j(A_n)}{n}={\lambda }_j(W)={\lim }_{n\to \infty }{\lambda }_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{]}_{ij}1(u\in I_i)1(v\in I_j)$ $A_n=V_n{\Lambda }_n{V}_n^{\ast }$ Thus

T_{W_{n}} \varphi(v) &= \int _{0}^1 W_{n}(u,v) \varphi(u)\, du &= \lambda \varphi(v) \\ &= \int _{0}^1 \sum_{i,j=1}^n [A_{n}]_{ij} \mathbb{1}(u \in I_{i}) \mathbb{1}(v \in I_{j}) \varphi(u)\, du &= \lambda \varphi(v) \\ &= \mathbb{1}(v \in I_{j}) \int _{0}^1 \sum_{i,j=1}^n [A_{n}]_{ij} \mathbb{1}(u \in I_{i}) \varphi(u) \, du &= \lambda \varphi(v) \\ \implies &= \sum_{i,j=1}^n [A_{n}]_{ij} \int _{0}^1 \mathbb{1}(u \in I_{i}) \varphi(u) \, du &=\lambda \varphi(v \in I_{j}) \end{aligned} $$ LHS is a constant for each $v \in I_{j}$. This means that $\varphi$ is a step function $\varphi(v \in I_{j}) = x_{j}$. Thus, we can rewrite the last line as $$\begin{aligned} \lambda x_{j} &= \sum_{i=1}^n [A_{n}]_{ij} x_{i} \frac{1}{n} \end{aligned}$$ since for each $i$ we have $\varphi(u) = \begin{cases} x_{i},\,\,x_{i} \in I_{i}\\0, \,\,\,\text{otherwise}\end{cases}$ . The above is just a matrix multiplication, so we get $$\begin{align} \implies \lambda x &= \frac{1}{n} A_{n}x \\ \implies \lambda_{j} (T_{W_{n}}) &= \frac{\lambda_{j}(A_{n})}{n} \;\;\;\forall j \end{align}$$ For convergence, this means that $$\begin{align} (\text{1}) & &\, t(c_{k}, G_{n}) &= \sum_{i=1}^n \lambda_{i}^k \\ (2) & &\, t(c_{k}, G_{n}) &\to \tilde{t}(c_{k}, W) \end{align}$$ 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\mathcal{X}$ can be written as

(T_{W}x)(v) &= \int _{0}^1 W(u,v) {\cal X}(u) \, du \\ &=\int _{0}^1 \sum_{j \in \mathbb{Z}\setminus \{ 0 \}} \lambda_{j} \varphi_{j}(u) \varphi_{j}(v)\,{\cal X}(u) du \\ &= \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} \lambda_{j} \varphi_{j}(v) \int {\cal X}(u) \varphi_{j}(u) \, du \\ \end{align}$$ ie we can represent the {==1||[[graphon signal]] ${\cal X}$==} in the {==2||[[graphon]] eigenbasis==}. This {==2||change of basis==} is the {==3||[[graphon fourier transform]]==}. > [!def] Graphon Fourier transform > > The **graphon fourier transform** of a [[graphon signal]] $(W,{\cal X})$ is a functional ${\cal \hat{X}} = WFT({\cal X})$ defined as > $${\cal \hat{X}}_{j} = {\cal \hat{X}}(\lambda_{j}) = \int _{0}^1 {\cal X}(u) \varphi_{j}(u)\, du $$ > where $\lambda_{j}$ are the [[eigenvalue|eigenvalues]] of the [[graphon]] $W$ and $\{ \varphi_{i} \}$ are the [[eigenfunction|eigenfunctions]]. > [!NOTE] > > Since the $\lambda_{j}$ are countable, the WFT is always defined. > [!def] Inverse graphon Fourier transform > > Let $W$ be a [[graphon]] and ${\cal X}$ a [[graphon signal]]. The **inverse graphon fourier transform** (iWFT) is defined as > $$iWFT({\cal \hat{X}}) = \sum_{j \in \mathbb{Z} \setminus \{ 0 \}} {\cal \hat{X}}(\lambda_{j}) \varphi_{j} = {\cal X}$$ > we recover ${\cal X}$ since $\{ \varphi_{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 ```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> } ```