Graph Convolution (그래프 컨볼루션)에 대하여


이번 글에서는 Graph Convolution (그래프 컨볼루션)에 대해 알아보자. Graph convolution에 대해 알아보기전에 아래의 글들을 이해하고 오길 바란다.

Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의

Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유

그러면 이제 Graph Convolution에 대해 알아보자.

Graph convolution의 정의

loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $L^{norm}$은 $G$의 normalized Laplacian matrix라 하고 이것의 대각화된 형태를 $L^{norm} = U \Lambda U^T$라고 하자. $k$와 $x$를 길이가 $|V|$짜리 벡터라고 하자. 그러면 $k$와 $x$의 graph convolution $*_{G}$는 아래와 같이 정의한다.

$$ k *_{G} x = U(U^Tk \odot U^Tx)$$

$\odot$은 Hadamard product를 의미한다. 왜 이런 꼴이 나왔을까? $U^Tk$와 $U^Tx$는 각각 $k,x$에 대한 Graph Fourier transform이다. Fourier transform에서 spectral domal에서 곱은 time domain에서 covolution과 대응이 되는데 이것과 마찬가지로 spectral domain 에서 곱인 $U^Tk \odot U^Tx$를 구하고 이것에 대응되는 벡터를 구하기 위하여 $U$를 곱해서 Inverse Fourier Transform을 취해주었다. $K$를 $U^Tk$의 원소를 대각선의 원소로 갖는 대각행렬이라고 하면 아래와 같이 표현할 수 있다.

$$ k *_{G} x = UKU^T x $$

위에서 정의된 covolution에서 만약에 $k$를 고정하고 $x$를 입력으로 하는 어떠한 함수를 만들고 싶다하자. $k$를 설정하고 $U^T k$를 구해서 $U(U^Tk \odot U^Tx)$를 구하는 것 대신 대각행렬 $K$를 설계해서 $UKU^T x$를 만드는 작업을 할 수도 있다. 이럴 때 $K$를 고정하고 입력을 $x$라고 하는 시스템(혹은 필터)를 만들 때 $K$를 kernel이라고 부르는것 같다.

Leave a Comment