2
$\begingroup$

In Section 2.1 of the research paper titled Semi-Supervised Classification with Graph Convolutional Networks by Thomas N. Kipf et al.,

Spectral convolution on graphs defined as

The multiplication of a signal $x ∈ R^N$ with a filter $g_\theta =$ diag$(\theta)$ parameterized by $\theta \in R^N$ in the Fourier domain,

i.e.:

$g_\theta * x $= $U g_\theta U^T x$

Actually, I don't understand notations here.

  1. What is a filter? Is it like a filter from CNN? Then why it has (or should have) a diagonal form? What is $\theta$ here?

  2. What is a Fourier domain?

I searched on Google and there was no Fourier domain.

$\endgroup$
1
  • $\begingroup$ Please, next time, ask only one question per post. Your second question is quite distinct from the first one. If you have multiple questions (even though they are related), ask each of the questions in its own separate post by providing the necessary context in each post to understand the corresponding question. $\endgroup$
    – nbro
    Oct 25 at 14:05
6
$\begingroup$

Short answer

Check out the paper of Shuman et al. [1], it provides some background on Graph Signal Processing, including answers to your questions in sections II.C and III.A

Long Answer

Question 1

Yes, the filter $g_{\theta}$ is analogous to CNN's filter. You have a diagonal matrix with $\theta_{i}$ in its diagonal mainly for matrix-multiplication purposes (otherwise the definition of convolution would not make sense for graph-structured data).

Question 2

A good introduction to signal processing on graphs is the Paper by Shuman et al. [1]. I will divide the answer in two topics.

What is a Fourier Domain

I think the authors in [2] used "Fourier Domain" as another name for "Frequency Domain". As they apply the Fourier transform on graphs, the notion of "frequency" gets lost, and you are left with the operational part of transforming the signal (see next section).

The fact that the authors in [2] say the filter $g_{\theta}$ is parametrized in the Fourier domain simply says that $g_{\theta}$ acts on the Fourier transform of $\mathbf{x}$, and not on $\mathbf{x}$ per se.

Fourier Transform on Graph Signals

Following [2, sect II.C], recall that the fourier transform of a continuous signal $x$ is, \begin{align*} X(\xi) = \mathcal{F}(\mathbf{x}) = \int_{\mathbb{R}}x(t)\text{exp}(-2\pi i \xi t)dt, \end{align*}

note that this is an inner product on the vector space of continuous functions, that is, \begin{align*} \langle x, u \rangle = \int_{\mathbb{R}}x(t)u(t)dt \end{align*}

moreover, if we look at the function $u(t)=\text{exp}(-2\pi i \xi t)$, these are the eigenfunctions of the Laplace operator, \begin{align*} -\Delta(u(t)) = -\dfrac{\partial^{2} u}{\partial t^{2}} = (2\pi\xi)^{2}u(t) \end{align*}

Now, the Fourier transform on graphs is defined based on two analogies. The first of them, is the Laplacian operator on Graphs, $L$, that substitutes the Laplacian operator of functions. In [2], the authors further used the normalized Laplacian. The second analogy is the inner product. As the signal $x(t)$ is substituted for $\mathbf{x} = [x_{i}]_{i=1}^{n}$, where $i$ a given graph vertex,

\begin{align*} \mathcal{F}(\mathbf{x}) = \langle \mathbf{x},\mathbf{u} \rangle = \sum_{i=1}^{n}x_{i}u_{i}, \end{align*}

where $u_{i}$ is the i-th eigenvector of $L$. Writing $U$ as the matrix of eigenvectors of $L$, \begin{align*} \mathcal{F}(\mathbf{x}) &= \mathbf{U}^{T}\mathbf{x} \end{align*}

Finally, following [2, III.A], let $g_{\theta}$ be the filter parametrized by $\theta$, and $y$ be the filtered signal (whose Fourier Transform is $Y$). In the frequency/fourier domain convolutions are products, hence, \begin{align*} Y(\xi) = g_{\theta}(\xi)X(\xi). \end{align*}

Conversely, for signals on graphs, \begin{align*} \mathbf{U}^{T}\mathbf{y} &= g_{\theta}\mathbf{U}^{T}\mathbf{x},\\ \mathbf{UU}^{T}\mathbf{y} &= \mathbf{U}g_{\theta}\mathbf{U}^{T}\mathbf{x},\\ \mathbf{y} &= \mathbf{U}g_{\theta}\mathbf{U}^{T}\mathbf{x}, \end{align*}

where from the second to third line we used the fact that $\mathbf{U}$ is an unitary matrix.

References

[1] Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3), 83-98.

[2] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.

$\endgroup$
3
  • $\begingroup$ What \begin{align*} \mathbf{U}^{T}\mathbf{y} &= g_{\theta}\mathbf{U}^{T}\mathbf{x},\\ \end{align*} means? I mean, what is $\mathbf{y}$ here? $\endgroup$
    – JAEMTO
    Oct 25 at 15:18
  • $\begingroup$ $\mathbf{y}$ is the filtered signal. $\mathbf{U}^{T}\mathbf{y}$ is the (graph) Fourier transform of $\mathbf{y}$. $\endgroup$ Oct 25 at 16:21
  • $\begingroup$ I rephrased some equations in my answer for better clarity. I previously used y for the Fourier transform of x, and for the filtered signal. Now it reads as $X(\xi) = \mathcal{F}(x(t))$, the Fourier transform of $x(t)$, and $Y(\xi) = \mathcal{F}(y(t))$. I hope it's clearer now. $\endgroup$ Oct 25 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.