spectral representation of graphon convolutions

[[concept]]

Theorem

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

{\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}$

NOTE

• graphon convolutions act pointwise in the spectral domain

Proof

{\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 [[Concept Wiki/diagonalizable\|diagonalization]] of $T_{W}^{(k)}$ by $\varphi_{i}$

Note

Some interesting takeaways (analogues of the graph convolution)

• Like the WFT, the spectral response of a graphon convolution is discrete
• the $j$th spectral component of the output $\mathcal{Y}$ only depends on ${\lambda }_j$ and spectral graphon signal ${\hat{\mathcal{X}}}_j$
  • ie ${\hat{\mathcal{Y}}}_j$ depends only on ${\lambda }_j$ and ${\hat{\mathcal{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 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

Sampling eigenvalues from the spectrum polynomial

fixed coefficients yield the same spectral response for both graphon and graph convolutions

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(\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 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 signal $H(S{)}_j$

Review

dsg

In the spectral domain, the graphon shift operator ${\hat{T}}_H$ {acts pointwise||special behavior} on the graphon signal $\mathcal{X}$

Like the GFT, the spectral response of a graphon convolution is {discrete||property}

The $j$th spectral component of the output $\mathcal{Y}$ only depends on eigenvalue ${\lambda }_j$ and the spectral graph signal ${\hat{\mathcal{X}}}_j$

The spectral response of graphon convolution $T_H$ given by $h(\lambda )={\sum }_{k=0}^{K-1}{h}_k{\lambda }^k$ is {==independent of the underlying graphon $W$||relation to object==}

the spectral response can be written as {1||a polynomial||function}. The eigenvalues of the {2||graphon shift operator} determine {3||where we evaluate} this function.

Mentions

Mentions

TABLE file.mday as "Last Modified"
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source
SORT file.mday ASC
SORT file.name ASC

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