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.
