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)?


1 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): enter image description here

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 $$

  • $\begingroup$ Many thanks for the reply! One follow up I have, to make sure I understand, is about the line: ". in order to work with independent parameters, one makes the transition to the diagonal basis of the graph Laplacian $\Lambda$ ". Is this the case because we want to have a filter which can element-wise multiply the GFT coefficients ($U^T x$). Thus, to implement this Hadamard product, we can change the filter 'vector' into a diagonal matrix. Is this the reason you were speaking of? Thanks $\endgroup$ Oct 23, 2021 at 8:41
  • 1
    $\begingroup$ @RockytheOwl yes, exactly. Purpose of switching to the Fourier basis is to simplify the convolution operation - as a particular case of general rule : $x \star y = F^{-1}[F(x) \cdot F(y)]$ $\endgroup$ Oct 23, 2021 at 9:18
  • $\begingroup$ Perfect! Thank you very much $\endgroup$ Oct 23, 2021 at 11:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .