Spectral Methods

여기서 convolution operation인 합성곱을 ($g_\theta$ ★ x) 와 같은 식으로 나타낸다.

5.1.1 Spectral Network

• convolution operation는 Fourier domain에서 정의된다.
  • by computing the eigendecomposition of the graph Laplacian.
  • a signal $x \in \mathbb{R}^N$( a scalar for each node)와 filter $g\theta = diga(\theta)$의 곱에 의해 나타낸다. $$g_\theta ★ x = Ug\theta(\Lambda)U^T x$$
  • U: the matrix of eigenvectors of the normalized graph Laplacian $L=I_N - D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = U\Lambda U^T$. 
    • $L = I - A$의 식에서 변형된 꼴인데, $D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$은 정규화를 위하여 계산이 된다.
• 한계: Laplacian Matrix의 eigen vectors의 의존성 Backpropagation을 위한 시간($O(n^2)$) + eigen decomposition 위한 시간 $O(n^3)$

5.1.2 Chebnet

• $g\theta (\Lambda)$이 truncated expansion in terms of Chebyshev polynomials인 $T_k (x)$에 의해서 근사될 수 있다는 특징을 이용 $$g_\theta ★ x \approx \sum_{k=0}^{K} \theta_k T_k (\tilde{L})x$$

5.1.3 GCN

• limit the layer-wise convolution operation to K=1 to alleviate the problem of overfitting on local neighborhood structures for graphs with very wide node degree distributions $$g_{\theta^{\prime}} ★ x \approx \theta_{0}^{\prime} x + \theta_{1}^{\prime} (L-I_N)x =  \theta_{0}^{\prime} x - \theta_{1}^{\prime}D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$$
• $\theta = \theta_0^\prime = -\theta_1^\prime$에 의하여 다음과 같은 식으로 나타낼 수 있다. $$g_{\theta^{\prime}} ★ x \approx \theta(I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x$$
•