In the simple case of univariate discrete data over a finite domain t ∈ {0, .., N − 1} (i.e., restricting to finite impulse response filters) we can simplify these operations to a discrete circular convolution.

Discrete Circular Convolution

Fourier coefficient corresponding to the sequence (f(x0), f(x1), ..., f(xN−1)) is sk ∈ {s0..., sN−1}. In the equation shown below, we use the notation *N to emphasize that this is a circular convolution defined over the finite domain
{0, ..., N − 1}, but we will often omit this subscript for notational simplicity.

 Discrete Fourier Transform (DFT)

This property means that translating a signal and then convolving it by a filter
is equivalent to convolving the signal and then translating the result. 

The Translation Equivariant Property of Convolutions

One critical aspect of the convolution operation is that it can be computed by
an element-wise product of the Fourier transforms of the two functions:

Hamilton College

In order to generalize the notion of a convolution to graphs, we first must define
what we wish to generalize and provide some brief background details. We can define the general continuous convolution operation * shown below, let f and h be two functions.


 The General Continuous Convolution Operation

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Fourier Transform of the Convolution Operation

We can represent a convolution by a filter $h$ as matrix multiplication on the vector **f**:

$(f \star h)(t) = \sum_{\tau=0}^{N-1} f(\tau)h(\tau - t)$

= $Q_hf$

where $Q_h \in \mathbb{R}^{N*N}$  is a matrix representation of the convolution operator by a filter function $h$ and **f** = $\mathbf{[f(t_0),f(t_2),...,f(t_{N-1}]}^\top$ is a vector representation of the function $f$

Learn Before

Related

Learn After