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

CC BY-SA 4.0
2021-10-23T08:41:35.973Z
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
Rocky the Owl
CC BY-SA 4.0
2021-10-23T09:18:43.193Z
@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)]$
spiridon_the_sun_rotator
CC BY-SA 4.0
2021-10-22T20:07:32.060Z
2021-10-22T20:07:32.060Z
spiridon_the_sun_rotator
<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>

<geometric-deep-learning><graph-neural-networks><filters>
Graph Convolutional Networks: why are non-parametric filters not localized in space?
Rocky the Owl
# 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)]$  

---

