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에 대해 알아볼 것이다.
- 목표
- Chebyshev 근사
-
Chebyshev 근사를 filter에 적용
- 기타
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\) 번째 이웃만을 고려한다.