spectral representation of a convolutional graph filter

Data

subject:: Data Science Methods for Large Scale Graphs parent:: Graph Signals and Graph Signal Processing theme:: math notes

Spectral representation of a graph convolution

Spectral Representation of a Convolutional Graph Filter

in the spectral/frequency domain, we have $\hat{y}={\sum }_{k=0}^{K-1}{h}_k{\Lambda }^k\hat{x}$ this representation is completely defined by the polynomial $h(\lambda )={\sum }_{k=0}^{K-1}{h}_k{\lambda }^k$

Frequency Response

The spectral representation/frequency response of $H(S)$ is $\widehat{H(S)}={\sum }_{k=0}^{K-1}{h}_k{\Lambda }^k$

Spectrum Representation as Sampling from a Polynomial

Because the spectral representation of a graph filter is independent from the graph and the spectral graph filter operates on a signal pointwise, this tells us

1. The polynomial is fixed once we find the coefficients $h_k$.
2. We can think of $\widehat{H(S)}$ as sampling values ${\lambda }_i$ along the curve $h(\lambda )={\sum }_{k=0}^{K-1}{h}_k{\lambda }^k$.

Thus, changing the shift operator $S$ corresponds to a different set of points sampled from this polynomial.

Spectral Representation of a Graph Signal

The graph fourier transform of the filtered signal is given as

\hat{y} = V^* y &= V^* \sum_{k=0}^{K-1}h_{k}S^{k} x \\ &= V^* \sum_{k=0}^{K-1}h_{k}S^{k} (V \hat{x}) \\ (*) &= \sum_{k=0}^{K-1}h_{k} V^* (V \Lambda V^*)^k V \hat{x} \\ &= \sum_{k=0}^{K-1}h_{k} \Lambda^k \hat{x} \end{aligned}$$ For $(*)$, recall the definition of the [[Concept Wiki/inverse graph fourier transform]].

We can see then that the GFT of the filter and the operator have the same polynomial relationship, but in the spectral domain.

Notes

1. the spectral representation of a graph filter is independent from the graph
2. the spectral graph filter operates on a signal pointwise

Mentions

TABLE
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