Answers.Body: <p>Your explanation is correct.</p>
  <p>Probably, the term <code>non-parametric</code> 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 <span class="math-container">$\Lambda$</span>.</p>
  <p>Computation of the eigendecomposition of <span class="math-container">$\Lambda$</span> requires knowledge of the graph as a whole.</p>
  <p>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):
  <a href="https://i.sstatic.net/TNRWf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/TNRWf.png" alt="enter image description here" /></a></p>
  <p>The property
  <span class="math-container">$$
  g_\theta (U \Lambda U^T) x = U g_\theta (\Lambda) U^T x
  $$</span>
  doesn't require a lot from <span class="math-container">$g_\theta$</span>, expansion in Taylor series is sufficient, since (<span class="math-container">$U U^T = U^T U = 1$</span>):
  <span class="math-container">$$
  (U \Lambda U^T)^k = U \Lambda^2 U^T (U \Lambda U^T)^{k-2} = ... 
  = U \Lambda^k U^T
  $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-23T08:41:35.973Z
Answers.Text: 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
Answers.UserDisplayName: Rocky the Owl
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-23T09:18:43.193Z
Answers.Text: @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)]$
Answers.UserDisplayName: spiridon_the_sun_rotator
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-22T20:07:32.060Z
Answers.LastActivityDate: 2021-10-22T20:07:32.060Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>I was reading the following paper <a href="https://arxiv.org/pdf/1606.09375.pdf" rel="nofollow noreferrer">here</a> about some of the groundwork in graph deep learning. On page 3, in the bit entitled <strong>Polynomial parameterization for localized filters</strong>, it states that non-parametric filters (i.e. a filter whose parameters are all free) are not localized in space.</p>
  <p><strong>Question:</strong> Why is this the case? It is referring to a filter <span class="math-container">$g_{\theta}$</span> such that:
  <span class="math-container">$$ y = g_{\theta}(L) x = g_{\theta} (U \Lambda U^T) x = U g_{\theta} (\Lambda) U^T x $$</span>
  where <span class="math-container">$L$</span> is the graph laplacian matrix, and <span class="math-container">$U \Lambda U^T$</span> are the eigenvector decomposition matrices.</p>
  <p><strong>Attempted explanation:</strong> Is it because the filter <span class="math-container">$g_{\theta}$</span> 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)?</p>
  
Tags: <geometric-deep-learning><graph-neural-networks><filters>
Title: Graph Convolutional Networks: why are non-parametric filters not localized in space?
UserDisplayName: Rocky the Owl
ThreadText: # Graph Convolutional Networks: why are non-parametric filters not localized in space?
  
  (Asked by: username_0 on 2021-10-22)
  
  I was reading the following paper [here](https://arxiv.org/pdf/1606.09375.pdf) 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)?
  
  **Tags:** geometric-deep-learning, graph-neural-networks, filters
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-10-22. Score: 1 | Accepted answer
  
  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](https://i.sstatic.net/TNRWf.png)](https://i.sstatic.net/TNRWf.png)
  
  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
  $$
  
  > **Comments:**
  > **username_0**: 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  
  > **username_1**: @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)]$  
  
  ---
  
  