Spectral Graph Convolution Network

Contents

 

Graph Convolution Network는 Spectral Convolution Network와 Spatial Convolution Network로 분류할 수 있다. Spatial Convolution은 CNN의 연산과 매우 흡사하며, 이웃 노드의 feature information을 바탕으로 message passing을 통해 특정 노드의 hidden state를 계산한다. 반면에 Spectral Convolution Network는 한 노드 내에 혼재된 signal들을 여러 signal의 요소로 나누어서 노드의 특징을 더 잘 추출할 수 있도록 하는 방법이다. 

Spectral-based graph filter

Spectral-based graph filter는 filtering을 하기 위해 기본적으로 Spectral graph theory을 적용한다. Spectral graph theory는 Adjacency matrix과 Degree matrix를 가지고 계산되는 Laplacian matrix를 eigen-decomposition 한다. 그렇다면 Laplacian이 무엇인지 부터 알아보자. 

 

Laplacian (Laplace Operator)

Laplacian 또는 Laplace Operator는 2차 미분 연산자의 일종으로, 기울기의 발산을 의미한다. 

\[ \Delta f = \nabla \cdot \nabla f = \nabla^2 f \]

Graph 노드의 signal 영역에서의 Laplace operator를 적용하는 것은 한 노드에서 signal의 방향성 혹은 흐르는 정도를 확인할 수 있다. 특정 노드에서 signal이 들어왔을 때 그 signal이 특정 노드와 연결된 노드들로 각각 얼마만큼 빨리 흩어지는지 알 수 있으며 이것이 바로 노드의 특징이다. 

 

Graph Laplacian

Graph에서 Laplacian Matrix는 위에서의 Laplacian을 통해 변화와 관련된 행렬임을 알 수 있다. 위에서 다룬 Laplace Operator가 Graph에 적용되면 노드 $x$의 signal $f(x)$와 노드 $x$와 $h$만큼 떨어진 이웃 노드 signal $f(x+h)$, $f(x-h)$ 와의 변화량을 통해 노드 $x$의 signal feature를 구하는 것이다. 

 

\[ \text{L} = \text{D} - \text{A} \]

\[ \text{L} = \begin{cases} \text{deg}(v_i) & \text{if}\ i = j \\ -1 & \text{if}\ i \neq j\ and \ v_i \text{ is adjacent to } v_j \\ 0 & \text{otherwise} \end{cases} \]

 

Graph에서의 Laplacian matrix는 Adjacency matrix와 Degree matrix를 가지고 계산하기에 주변 노드 간의 연결된 구조를 바탕으로 Graph signal을 구할 수 있을 것이다. 이때 Graph Fourier Transform을 사용하여 Graph signal을 분해해 어떠한 특징을 가지고 있는지 도출한다.

 

푸리에 함수(Fourier tranform)

Spectral graph theory는 Laplacian matrix과 관련된 행렬의 특성 다항식, 고유값, 고유 벡터와 관련된 그래프 속성에 대한 연구라고 언급하였다. Graph signal에서의 푸리에 변환은 Graph의 Laplacian matrix를 eigen-decomposition하는 것이며,  Laplacian matrix를 분해하기 위해서는 푸리에 함수를 사용하고 수식은 다음과 같다.

\[ \underset{n \times n}{\Delta} = \Phi^T \Lambda \Phi \]

이는 SVD와 동일한 수식으로 나타낼 수 있다. $\Phi^T$와 $\Phi$는 각각 Laplacian matrix에 대해서 고유 벡터인 열벡터를 가진다. $\Lambda$는 Diagonal matrix로 Laplacian matrix의 고유값을 가지고 있다. 

푸리에 함수는 하나의 함수를 주기를 가지는 여러가지 함수로 분해하는 함수라고 보면 된다. 다시 역푸리에 변환을 통해 되돌려서 사용하기도 한다. 

\[ \hat{f} (\xi) = \int_{R^d} f(x) e^{2\pi i x \xi } \text{d}x \]

\[ f(x) = \int_{R^d} \hat{f} (\xi) e^{-2 \pi i x \xi} \text{d} \xi \]

첫 번째 수식은 $f$의 푸리에 변환이고, 두 번째 수식은 푸리에 역변환이다. 푸리에 변환을 바라보는 관점은 여러가지 존재하지만 본 글에서 언급하는 것은 '내적'이다. 

\[ \forall \text{signal} \ f(x), \hat{f}(\xi) = f(x) \cdot e^{-2 \pi i x \xi} \]

내적은 둘 간의 유사도를 의미하며, $f(x)$와 $e^{-2 \pi i x \xi}$의 유사도가 $\hat{f}(\xi)$가 되는 것이다. 그렇다면 여기에서 $e^{-2 \pi i x \xi}$는 무엇인가? 이를 이해하기 위해서는 오일러 공식이 필요하며 오일러 공식은 다음과 같다. 

\[ e^{ix} = \cos (x) + i \sin (x) \]

\[ e^{2 \pi i x \xi} = \cos (2 \pi x \xi) + i \sin (2 \pi x \xi) \]

 

 

이와 같은 Spectral-based filter는 전체 그래프를 입력으로 사용하기에 실제 필드에서 사용할 때는 엄청난 양의 파라미터가 요구된다. 이러한 문제를 해결하기 위해 2016년에 Polynomial filter가 제안 되었다. Polynomial filter는 해당 노드 주변의 K 번째 neighbor만 연산하여 signal을 식별하고 중요한 signal을 모델이 학습하는 방법이다. 이처럼 그래프에 하위 노드 집합을 생성하게 되면 기존에 모든 그래프의 노드를 고려하는 것 보다 상당한 수의 파라미터를 줄일 수 있다. 

 

Polynomial filter는 orthogonal based가 아닌 Polynomial based로 학습이 진행된다. Polynomial based로 모델을 학습하는 경우 어떤 노드를 선택하냐에 따라 다른 계수들이 변경될 수 있다는 문제가 존재한다. 이는 학습 과정에서 불안정성을 유발할 수 있는 것으로 해결해야되는 이슈 중 하나다. 이러한 문제를 해결하기 위해 Chebyshev polynomial과 Cheby-filter와 같은 다양한 방법론이 제안되었다. Chebyshev polynomial과 Cheby-filter는 Polynomial base가 아닌 orthogonal based로 모델을 학습하였다. 

 

Spectral GCN는 최근에도 많이 사용되고 있는 기법 중 하나이다. Spectral GCN는 Cheby-filter가 제안된 후, Cheby-filter의 복잡한 구조를 단순화한 기법이다. Cheby-filter는 neighbor의 수를 1부터 k개로 다양하게 설정이 가능하지만, Spectral GCN는 k를 1로 제한하여 단순화 하였다. 

\[ H^{(l+1)} = \sigma ( \hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}) \]

$H$는 state embedding을 의미하고 $D$는 대각 행렬, $A$는 인접 행렬을 의미한다.