Body: <p>I was reading the following paper: <a href="https://arxiv.org/pdf/1609.02907.pdf" rel="nofollow noreferrer">here</a>. In it, it talks about spectral graph convolutions and says:</p>
  <blockquote>
  <p>We consider spectral convolutions on graphs defined as the
  multiplication of a signal <span class="math-container">$x \in R^N$</span> (a scalar for every node)
  with a filter <span class="math-container">$g_{\theta}$</span> <span class="math-container">$=$</span> <span class="math-container">$\text{diag}  (\theta)$</span> parameterized
  by <span class="math-container">$\theta \in R^{N}$</span> in the Fourier domain, i.e.: <span class="math-container">$ g_{\theta} * x = U g_{\theta} U^Tx $</span>. We can understand <span class="math-container">$ g_{\theta}$</span> as a function of the eigenvalues of <span class="math-container">$L$</span>, i.e.  <span class="math-container">$g_{\theta}(\Lambda)$</span></p>
  </blockquote>
  <p>So far, it makes sense. <span class="math-container">$U^T x$</span> is the graph Fourier transform of the signal <span class="math-container">$x$</span>, then we multiply by <span class="math-container">$ g_{\theta}$</span> in the Fourier domain as: <span class="math-container">$FT(f * g) = F(\omega)G(\omega)$</span>. Then we have the multiplication by <span class="math-container">$U$</span> in the front to represent the inverse (graph) Fourier transform.</p>
  <p>Then the paper lists some reasons why using the above convolution equation may not be practical in reality:</p>
  <ul>
  <li>Evaluating the above equation is computationally expensive; multiplying with eigenvector matrix <span class="math-container">$U$</span> is <span class="math-container">$O(N^2)$</span></li>
  <li>Computing eigendecomposition of <span class="math-container">$L$</span> may be too expensive for an arbitrarily large graph</li>
  <li>etc.</li>
  </ul>
  <p>and then the paper says:</p>
  <blockquote>
  <p>To circumvent this problem, it was suggested in Hammond et al. (2011)
  that <span class="math-container">$g_{\theta}(\Lambda)$</span> can be well-approximated by a truncated
  expansion in terms of Chebyshev polynomials <span class="math-container">$T_k (x)$</span> up to
  <span class="math-container">$K^{\text{th}}$</span> order: <span class="math-container">$$ g_{\theta '}(\Lambda) \approx \sum_{k =
  &gt; 0}^{K} \theta_k ' T_k(\tilde{\Lambda}) $$</span></p>
  <p>with a rescaled <span class="math-container">$\tilde{\Lambda} = \frac{2}{\lambda_{\text{max}}}\Lambda − I_N$</span>. <span class="math-container">$\lambda_{\text{max}}$</span>
  denotes the largest eigenvalue of <span class="math-container">$L$</span>. <span class="math-container">$\theta ′ \in R^K$</span> is now a
  vector of Chebyshev coefficients. The Chebyshev polynomials are
  recursively defined as <span class="math-container">$T_k(x) = 2xT_{k−1}(x) − T_{k−2}(x)$</span>, with
  <span class="math-container">$T_0(x) = 1$</span> and <span class="math-container">$T_1(x) = x$</span>. The reader is referred to Hammond et al. (2011) for an in-depth discussion of this approximation. Going
  back to our definition of a convolution of a signal <span class="math-container">$x$</span> with a filter
  <span class="math-container">$g_{\theta '}$</span>, we now have: <span class="math-container">$$ g_{\theta '} * x \approx \sum_{k=0}^{K} \theta_k ′ T_k (\tilde{L}) x$$</span> with <span class="math-container">$\tilde{L} = \frac{2}{\lambda_{\text{max}}}L − I_N$</span> ; as can easily be verified by
  noticing that <span class="math-container">$(U \Lambda U^T)^k = U \Lambda^k U^T $</span></p>
  </blockquote>
  <p><strong>Question:</strong> What happened to the terms <span class="math-container">$U^T$</span> and <span class="math-container">$U$</span> which take the (graph) Fourier transform and invert it respectively?</p>
  <p><strong>Attempt:</strong> Does it have something to do with what is mentioned in the last line about noticing that <span class="math-container">$(U \Lambda U^T)^k = U \Lambda^k U^T $</span>? I might guess that we use that because a k-th order Chebyshev polynomial will have <span class="math-container">$\Lambda ^k$</span> (and lower powers) present in the equation and thus the <span class="math-container">$U^T$</span> and <span class="math-container">$U$</span> mean that we can write the convolution equation in terms of the Laplacian matrix <span class="math-container">$L$</span></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-10T08:02:22.217Z
Comments.Text: I can't understand the equation you pasted from the given paper. Can you please phase this question in your own words and use latex to write equations?
Comments.UserDisplayName: Swakshar Deb
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-10T20:11:33.230Z
Comments.Text: Hi @SwaksharDeb - the equations were written in Latex. Have fixed the few areas where the '>' character made it into the equations (meant for the block quote). The question can be summarized as: how did the Chebyshev function of $\tilde{\Lambda}$  into a function of L
Comments.UserDisplayName: Rocky the Owl
Tags: <papers><geometric-deep-learning><graph-neural-networks><spectral-analysis>
Title: How does Chebyshev approximation of spectral convolution work?
UserDisplayName: Rocky the Owl
ThreadText: # How does Chebyshev approximation of spectral convolution work?
  
  (Asked by: username_0 on 2021-09-09)
  
  I was reading the following paper: [here](https://arxiv.org/pdf/1609.02907.pdf). In it, it talks about spectral graph convolutions and says:
  
  > We consider spectral convolutions on graphs defined as the
  > multiplication of a signal $x \in R^N$ (a scalar for every node)
  > with a filter $g\_{\theta}$ $=$ $\text{diag} (\theta)$ parameterized
  > by $\theta \in R^{N}$ in the Fourier domain, i.e.: $ g\_{\theta} \* x = U g\_{\theta} U^Tx $. We can understand $ g\_{\theta}$ as a function of the eigenvalues of $L$, i.e. $g\_{\theta}(\Lambda)$
  
  So far, it makes sense. $U^T x$ is the graph Fourier transform of the signal $x$, then we multiply by $ g\_{\theta}$ in the Fourier domain as: $FT(f \* g) = F(\omega)G(\omega)$. Then we have the multiplication by $U$ in the front to represent the inverse (graph) Fourier transform.
  
  Then the paper lists some reasons why using the above convolution equation may not be practical in reality:
  
  * Evaluating the above equation is computationally expensive; multiplying with eigenvector matrix $U$ is $O(N^2)$
  * Computing eigendecomposition of $L$ may be too expensive for an arbitrarily large graph
  * etc.
  
  and then the paper says:
  
  > To circumvent this problem, it was suggested in Hammond et al. (2011)
  > that $g\_{\theta}(\Lambda)$ can be well-approximated by a truncated
  > expansion in terms of Chebyshev polynomials $T\_k (x)$ up to
  > $K^{\text{th}}$ order: $$ g\_{\theta '}(\Lambda) \approx \sum\_{k =
  > > 0}^{K} \theta\_k ' T\_k(\tilde{\Lambda}) $$
  >
  > with a rescaled $\tilde{\Lambda} = \frac{2}{\lambda\_{\text{max}}}\Lambda − I\_N$. $\lambda\_{\text{max}}$
  > denotes the largest eigenvalue of $L$. $\theta ′ \in R^K$ is now a
  > vector of Chebyshev coefficients. The Chebyshev polynomials are
  > recursively defined as $T\_k(x) = 2xT\_{k−1}(x) − T\_{k−2}(x)$, with
  > $T\_0(x) = 1$ and $T\_1(x) = x$. The reader is referred to Hammond et al. (2011) for an in-depth discussion of this approximation. Going
  > back to our definition of a convolution of a signal $x$ with a filter
  > $g\_{\theta '}$, we now have: $$ g\_{\theta '} \* x \approx \sum\_{k=0}^{K} \theta\_k ′ T\_k (\tilde{L}) x$$ with $\tilde{L} = \frac{2}{\lambda\_{\text{max}}}L − I\_N$ ; as can easily be verified by
  > noticing that $(U \Lambda U^T)^k = U \Lambda^k U^T $
  
  **Question:** What happened to the terms $U^T$ and $U$ which take the (graph) Fourier transform and invert it respectively?
  
  **Attempt:** Does it have something to do with what is mentioned in the last line about noticing that $(U \Lambda U^T)^k = U \Lambda^k U^T $? I might guess that we use that because a k-th order Chebyshev polynomial will have $\Lambda ^k$ (and lower powers) present in the equation and thus the $U^T$ and $U$ mean that we can write the convolution equation in terms of the Laplacian matrix $L$
  
  **Tags:** papers, geometric-deep-learning, graph-neural-networks, spectral-analysis
  
  > **Comments:**
  > **username_1**: I can't understand the equation you pasted from the given paper. Can you please phase this question in your own words and use latex to write equations?  
  > **username_0**: Hi @username_1 - the equations were written in Latex. Have fixed the few areas where the '>' character made it into the equations (meant for the block quote). The question can be summarized as: how did the Chebyshev function of $\tilde{\Lambda}$  into a function of L  
  
  ---
  
  ## 0 answers
  
  