I've been reading several papers and reviews about Graph Neural Networks, and I still feel a bit confused about the difference between the two approaches, and also if the spatial approaches have somehow 'overcome' spectral ones. I will add some of my understanding:

Graph Neural Networks take inspiration from the convolution operation between two signals in a Euclidean domain, as a way to combine the features on the nodes as it happens for Convolutional Neural Networks. To do this, a notion of convolution has been required for the graph domain. Given $\bf{x},\bf{y} \in \mathbb{R}^N$ two signals, then

$$\bf{x} \, \, *_G \, \, \bf{y} := U(U^Tx \, \odot \, U^Tx)$$

namely, we perform convolution on the graph domain and then take everything back using the inverse Fourier Transform. If we choose a filter $\bf g_\theta = diag(\theta_1, \dots, \theta_N)$ parametrized by some $\theta \in \mathbb{R}^N$ then the convolution becomes

$$\bf{x} \, *_G \bf{g_\theta} = Ug_\theta U^T$$

The approach above presents several limitations in terms of non-localization of filters (which depend on the entire graph) and scalability issues if presence of perturbations. So the authors of ChebNet proposed the following approximation:

$$\bf{x} \, *_G \bf{g_\theta} = \sum_{i=0}^K \theta_iT_i(\tilde{L})x$$

where $\tilde{L} = 2L/\lambda_{max}-I_n$, $L$ is the Laplacian and $T_i$ are Chebyshev polynomials.

Now the crucial step is that Kipf et Al. (2017) have bridged the gap between spectral and spatial approaches by proposing a first order approximation of the above equation (assuming $\lambda_{max} =2$ and $\theta = \theta_0 = -\theta_1$):

$$\bf{x} \, *_G \bf{g_\theta} = \theta(I_n+ D^{-1/2}AD^{-1/2})$$

Now, from what I've read so far, it seems that from now on several improvements have been made on the spatial approach which defines convolutions on top of node's graph neighbourhood.

The question is, does it still make sense to focus on spectral approaches?


Your Answer

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

Browse other questions tagged or ask your own question.