Answers.Body: <h1>Short answer</h1>
  <p>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</p>
  <h1>Long Answer</h1>
  <h2>Question 1</h2>
  <p>Yes, the filter <span class="math-container">$g_{\theta}$</span> is analogous to CNN's filter. You have a diagonal matrix with <span class="math-container">$\theta_{i}$</span> in its diagonal mainly for matrix-multiplication purposes (otherwise the definition of convolution would not make sense for graph-structured data).</p>
  <h2>Question 2</h2>
  <p>A good introduction to signal processing on graphs is the Paper by Shuman et al. [1]. I will divide the answer in two topics.</p>
  <h3>What is a Fourier Domain</h3>
  <p>I think the authors in [2] used &quot;Fourier Domain&quot; as another name for &quot;Frequency Domain&quot;. As they apply the Fourier transform on graphs, the notion of &quot;frequency&quot; gets lost, and you are left with the operational part of transforming the signal (see next section).</p>
  <p>The fact that the authors in [2] say the filter <span class="math-container">$g_{\theta}$</span> is <em>parametrized in the Fourier domain</em> simply says that <span class="math-container">$g_{\theta}$</span> acts on the Fourier transform of <span class="math-container">$\mathbf{x}$</span>, and not on <span class="math-container">$\mathbf{x}$</span> <em>per se</em>.</p>
  <h3>Fourier Transform on Graph Signals</h3>
  <p>Following [2, sect II.C], recall that the fourier transform of a continuous signal <span class="math-container">$x$</span> is,
  <span class="math-container">\begin{align*}
  X(\xi) = \mathcal{F}(\mathbf{x}) = \int_{\mathbb{R}}x(t)\text{exp}(-2\pi i \xi t)dt,
  \end{align*}</span></p>
  <p>note that this is an inner product on the vector space of continuous functions, that is,
  <span class="math-container">\begin{align*}
  \langle x, u \rangle = \int_{\mathbb{R}}x(t)u(t)dt
  \end{align*}</span></p>
  <p>moreover, if we look at the function <span class="math-container">$u(t)=\text{exp}(-2\pi i \xi t)$</span>, these are the eigenfunctions of the Laplace operator,
  <span class="math-container">\begin{align*}
  -\Delta(u(t)) = -\dfrac{\partial^{2} u}{\partial t^{2}} = (2\pi\xi)^{2}u(t)
  \end{align*}</span></p>
  <p>Now, the Fourier transform on graphs is defined based on two analogies. The first of them, is the <a href="https://en.wikipedia.org/wiki/Laplacian_matrix" rel="nofollow noreferrer">Laplacian operator on Graphs</a>, <span class="math-container">$L$</span>, 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 <span class="math-container">$x(t)$</span> is substituted for <span class="math-container">$\mathbf{x} = [x_{i}]_{i=1}^{n}$</span>, where <span class="math-container">$i$</span> a given graph vertex,</p>
  <p><span class="math-container">\begin{align*}
  \mathcal{F}(\mathbf{x}) = \langle \mathbf{x},\mathbf{u} \rangle = \sum_{i=1}^{n}x_{i}u_{i},
  \end{align*}</span></p>
  <p>where <span class="math-container">$u_{i}$</span> is the i-th eigenvector of <span class="math-container">$L$</span>. Writing <span class="math-container">$U$</span> as the matrix of eigenvectors of <span class="math-container">$L$</span>,
  <span class="math-container">\begin{align*}
  \mathcal{F}(\mathbf{x}) &amp;= \mathbf{U}^{T}\mathbf{x}
  \end{align*}</span></p>
  <p>Finally, following [2, III.A], let <span class="math-container">$g_{\theta}$</span> be the filter parametrized by <span class="math-container">$\theta$</span>, and <span class="math-container">$y$</span> be the filtered signal (whose Fourier Transform is <span class="math-container">$Y$</span>). In the frequency/fourier domain <a href="https://en.wikipedia.org/wiki/Convolution#Convolution_theorem" rel="nofollow noreferrer">convolutions are products</a>, hence,
  <span class="math-container">\begin{align*}
  Y(\xi) = g_{\theta}(\xi)X(\xi).
  \end{align*}</span></p>
  <p>Conversely, for signals on graphs,
  <span class="math-container">\begin{align*}
  \mathbf{U}^{T}\mathbf{y} &amp;= g_{\theta}\mathbf{U}^{T}\mathbf{x},\\
  \mathbf{UU}^{T}\mathbf{y} &amp;= \mathbf{U}g_{\theta}\mathbf{U}^{T}\mathbf{x},\\
  \mathbf{y} &amp;= \mathbf{U}g_{\theta}\mathbf{U}^{T}\mathbf{x},
  \end{align*}</span></p>
  <p>where from the second to third line we used the fact that <span class="math-container">$\mathbf{U}$</span> is an unitary matrix.</p>
  <h1>References</h1>
  <p>[1] Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., &amp; 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.</p>
  <p>[2] Kipf, T. N., &amp; Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-25T15:18:01.097Z
Answers.Text: 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?
Answers.UserDisplayName: JAEMTO
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-25T16:21:02.293Z
Answers.Text: $\mathbf{y}$ is the filtered signal. $\mathbf{U}^{T}\mathbf{y}$ is the (graph) Fourier transform of $\mathbf{y}$.
Answers.UserDisplayName: Eduardo Montesuma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-25T16:25:25.100Z
Answers.Text: 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.
Answers.UserDisplayName: Eduardo Montesuma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-25T10:35:57.090Z
Answers.LastActivityDate: 2021-10-25T16:22:47.867Z
Answers.LastEditDate: 2021-10-25T16:22:47.867Z
Answers.UserDisplayName: Eduardo Montesuma
Body: <p>In Section 2.1 of the research paper titled <a href="https://arxiv.org/abs/1609.02907" rel="nofollow noreferrer">Semi-Supervised Classification with Graph Convolutional Networks</a> by <em>Thomas N. Kipf et al.</em>,</p>
  <p>Spectral convolution on graphs defined as</p>
  <blockquote>
  <p>The multiplication of a signal <span class="math-container">$x ∈ R^N$</span> with a filter <span class="math-container">$g_\theta =$</span> diag<span class="math-container">$(\theta)$</span> parameterized by <span class="math-container">$\theta \in R^N$</span> in the Fourier domain,</p>
  </blockquote>
  <p>i.e.:</p>
  <blockquote>
  <p><span class="math-container">$g_\theta * x $</span>= <span class="math-container">$U g_\theta U^T x$</span></p>
  </blockquote>
  <p>Actually, I don't understand notations here.</p>
  <ol>
  <li><p>What is a filter? Is it like a filter from CNN? Then why it has (or should have) a diagonal form? What is <span class="math-container">$\theta$</span> here?</p>
  </li>
  <li><p>What is a Fourier domain?</p>
  </li>
  </ol>
  <p>I searched on Google and there was no Fourier domain.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-25T14:05:27.680Z
Comments.Text: Please, next time, [**ask only one question per post**](https://meta.stackexchange.com/questions/39223/one-post-with-multiple-questions-or-multiple-posts/39224#39224). 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.
Comments.UserDisplayName: nbro
Tags: <terminology><papers><convolution><graph-neural-networks><notation>
Title: What is a filter in the context of graph convolutional networks?
UserDisplayName: JAEMTO
ThreadText: # What is a filter in the context of graph convolutional networks?
  
  (Asked by: username_0 on 2021-10-25)
  
  In Section 2.1 of the research paper titled [Semi-Supervised Classification with Graph Convolutional Networks](https://arxiv.org/abs/1609.02907) 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.
  
  **Tags:** terminology, papers, convolution, graph-neural-networks, notation
  
  > **Comments:**
  > **username_1**: Please, next time, [**ask only one question per post**](https://meta.stackexchange.com/questions/39223/one-post-with-multiple-questions-or-multiple-posts/39224#39224). 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-10-25. Score: 6 | Accepted answer
  
  # 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](https://en.wikipedia.org/wiki/Laplacian_matrix), $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](https://en.wikipedia.org/wiki/Convolution#Convolution_theorem), 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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_2**: $\mathbf{y}$ is the filtered signal. $\mathbf{U}^{T}\mathbf{y}$ is the (graph) Fourier transform of $\mathbf{y}$.  
  > **username_2**: 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.  
  
  ---
  
  