Chapter 4-2. Convolutional Layers, Spectral methods

( 참고 : https://www.youtube.com/watch?v=JtDgmmQ60x8&list=PLGMXrbDNfqTzqxB1IGgimuhtfAhGd8lHF )

(1) Cheb Convolution

( pytorch geometric 링크 : https://pytorch-geometric.readthedocs.io/en/latest/modules/nn.html#torch_geometric.nn.conv.ChebConv )

다음의 순서로, Cheb Convolution에 대해 알아볼 것이다.

  1. 목표
  2. Chebyshev 근사
  3. Chebyshev 근사를 filter에 적용

  4. 기타


1) 목표

\(v * w = U^H ((U w) \odot (U v))= U^H g_w U w\) 를 계산하자!

  • 여기서 \(g_w = g_w(\Lambda)\) 이다


2) Chebyshev 근사

Chebyshev polynomials \(T_k\) :

  • \(T_{k}(x) = 2 x T_{k-1}(x) - T_{k-2}(x), \;\; T_0(x) = 1, T_1(x) = x\).


위의 \(U^H g_w U w\) 안의 \(g_w = g_w(\Lambda)\)를 계산하는데에 있어서, Chebyshev approximationd을 사용한다.

  • \(K\) 개의 필터를 사용한다.
  • \(g_w(\Lambda) = \sum_{k=0}^K \theta_k T_k(\tilde \Lambda),\;\;\;\;\tilde \Lambda = \frac{2}{\lambda_\max} \Lambda - I\).


Laplacian matrix의 spectral decompositon과, 이를 Chebyshev 근사해보자.

  • \(L = U \Lambda U^T\).
  • \(T_k(L) = U T_k(\Lambda) U^T\).


3) Fast Approximated Convolution

위의 근사를 사용하여, 아래와 같이 식을 정리할 수 있다.

\(\begin{align*} v * w &= U g_w U^T x = U \left(\sum_{k=0}^K \theta_k T_k(\tilde \Lambda) \right)U^T x =\sum_{k=0}^K \theta_k U T_k(\tilde \Lambda) U^T x\\ &=\sum_{k=0}^K \theta_k T_k(\tilde L) x \end{align*}\).

where \(\tilde L = \frac{2}{\lambda_\max} L - I\)


이를 통해 알 수 있듯, 우리는 \(U\) 와 \(\Sigma\) 전체를 구할 필요 없이, 오직 \(L\) 과 \(\lambda_{\text{max}}\)에만 의존한다.

또한, \(K\)-powers 까지만 사용하므로써, 각 노드에 대해 \(K\) 번째 이웃만을 고려한다.

Categories:

Updated: