Graph Convolutional Networks: why are non-parametric filters not localized in space?

Question

I was reading the following paper here about some of the groundwork in graph deep learning. On page 3, in the bit entitled Polynomial parameterization for localized filters, it states that non-parametric filters (i.e. a filter whose parameters are all free) are not localized in space.

Question: Why is this the case? It is referring to a filter $g_{\theta}$ such that: $$ y = g_{\theta}(L) x = g_{\theta} (U \Lambda U^T) x = U g_{\theta} (\Lambda) U^T x $$ where $L$ is the graph laplacian matrix, and $U \Lambda U^T$ are the eigenvector decomposition matrices.

Attempted explanation: Is it because the filter $g_{\theta}$ is defined in the spectral domain and thus its spatial domain (i.e. its inverse graph Fourier transform) may be defined over the whole graph (and thus not localized)?

Answer 1

Your explanation is correct.

Probably, the term non-parametric is not very appropriate. But the meaning of it here, as far as I understand, is the parametrization where all parameters are all independent. And in order to work with independent parameters, one makes the transition to the diagonal basis of the graph Laplacian $\Lambda$.

Computation of the eigendecomposition of $\Lambda$ requires knowledge of the graph as a whole.

The drawback of the spectral methods is that they work only on a given graph and do not generalize to other graphs. Even more, a small perturbation in the graph structure can lead to big changes in the spectrum as the following example shows (it is a mesh, actually, a particular case of graph):

The property $$ g_\theta (U \Lambda U^T) x = U g_\theta (\Lambda) U^T x $$ doesn't require a lot from $g_\theta$, expansion in Taylor series is sufficient, since ($U U^T = U^T U = 1$): $$ (U \Lambda U^T)^k = U \Lambda^2 U^T (U \Lambda U^T)^{k-2} = ... = U \Lambda^k U^T $$