GNN Overview

Graph Convolution Neural Network 는 # 왜 두가지로 나뉘는 것일까? # 두개의 차이점은 무엇인가? # 각각 사용되는 어플리케이션의 차이가 있는가?

  • Spectral based GCN

  • Spatial based GCN

Spectral Based GCN

Spectrum 은 그래프를 표현하는 방식 중 하나이다. 그래프 G 의 n∗nn*n 의 Adjacency Matrix (A) 가 있을 때, nn 개의 고유벡터들을 스펙트럼이라고 한다. 이 때 주의할 것은 고유벡터들의 나열은 고유벡터의 대응되는 고유값이 오름차순으로 정렬된 상태이어야 한다. 이러한 스펙트럼을 분석하는 연구를 Spectral Graph Theory 라고 한다.

그래프를 Adjacency Matrix 로 표현한 후, 노드의 피처를 내적하면, 그 결과는 한 ROW 를 노드라 생각하였을 때, 노드의 이웃노드 피처들의 합과 같다. 즉, GCN 에서는 각 노드를 이웃한 노드 피처의 합으로 표현한다.

AxAx

하지만 여기에는 문제가 있다. 자신을 나타내는 피처에서 자신의 피처는 정작 포함하지 않는다. 따라서, 이를 해결하기 위하여, Self Loop 를 추가한다. 즉, Adjacency Matrix 에다 I 를 더하는 것이다.

고유 분해를 알아보기 위해 먼저 d-regular Graph 에서 고유값 분해를 알아보자.

그래프가 연결되어 있을 때만 보았는데, 분리가 되어있을 때에도 고유값은 d 인것을 알 수 있다. 즉, 연결이 되지 않았을 때, 제일 큰 고유값과 두번째로 큰 고유값이 같다는 것이다. 즉 가장 큰 고유값이 2라면 이 그래프는 2개로 그루핑을 할 수 있다. 만약에 첫번째로 큰 고유값과 두번째로 큰 고유값이 같지는 않지만 거의 비슷하다면, 이또한 두 개의 그룹을 연결하는 간선이 적다는 것이다.

두번째 고유값은 그루핑을 하는데 중요한 역할을 한다.

왜냐하면, 고유벡터들을 서로 직교하는 성질을 가진다. 즉, 첫번째로 큰 고유값에 대응되는 고유벡터 xnx_n 과 두번째로 큰 고유값에 대응하는 고유벡터 xn−1x_{n-1} 을 내적하였을 때, 0이라는 것이다. xn=(1,1,1,..)x_n = ({1,1,1,..}) 이면 xn−1x_{n-1} 의 총합은 0이어야 하며, 몇개는 0보다 작은 값, 몇개는 0보다 큰값이다. 즉, 두번째로 큰 고유값을 가지고 집합군을 분리할 수 있다.

라플라시안 행렬이란?

라플라시안 행렬의 형태를 보면 간선이 있는 곳은 -1 이고, 대각선은 각 노드의 차수이다.

  • x=(1,1,1,...)Tx = (1,1,1,...)^T 일 때, 라플라시안 행렬의 고유값은 0 이고, 고유벡터는 xx 이다.

  • 고유값은 양의 실수이다.

  • 고유벡터는 실수이며, 항상 직교한다.

우리의 목적은 두번째로 큰 고유값 λ2\lambda_2 을 찾는 것인데, λ2\lambda_2 에 대응하는 고유벡터 xx 를 이용해서 찾는다. 즉 첫번째 고유벡터 xT∗w1x^T * w_1 와의 내적이 0 인 minxTMxxTxmin \frac{x^TMx}{x^Tx} 을 최소화 하는 값을 찾는 것이다.

xTLxx^TLx 를 정리해보면, 즉 간선이 있는 두 고유벡터의 위치의 원소들 차의 제곱의 합을 최소화하는 것과 같다.

즉, 위 말은 다음 두가지 사실을 고려해보자 . 우리가 구하려는 xx 는

  • xx 는 유닛 벡터이다.

  • 또한, 첫번째 고유벡터와 직교한다.

이 두 사실을 고려하면 양수와, 음수 사이의 간선이 적어야 함을 의미한다.

수학의 라플라시안 연산자와 다르다. 라플라시안 행렬은 그래프를 표현하는 행렬의 형태중 하나이다.

라플라시안 고유 분해

spatial domain 을 frequency domain 의 합으로 표현한다. 푸리에 변환 행렬을 사용하는 대신의 라플라시안 행렬의 고유 벡터를 사용한다.

라플라시안은 다음과 같이 표현할 수 있다.

한계점은 라플라시안 고유벡터의 의존한다는 것이다. 시간 복잡성이 크다.

Spatial Based Graph Convolution

이미지를 Regular Grid Graph 로 표현할 수 있다. 여기서 2D 컨볼루션이란, 3*3 필터가 주어졌을 때, 3*3 행렬을 하나의 스칼라 값으로 만드는 DOT 연산을 말한다. 즉, convolution 은 aggregator 연산자이다. 그리고, 이 dot 연산은 permutation invariant 하지 않다. w1x1+w2x2≠w1x2+w2x1w_1x_1 + w_2x_2 \neq w_1x_2 + w_2x_1

하지만, 이를 그래프에 적용하자면 node 는 set 이기 때문에 순서에 상관이 없다. 따라서 적용할 수 있는 aggregator는 두가지 유명한 연산자를 사용하는데 평균과 합계이다. (x1+x2)w1≡(x2+x1)w1(x_1+x_2)w_1 \equiv (x_2+x_1)w_1 이러한, 평균, 혹은 합계를 컨볼루션이라 하는데, 그 이유는 매 노드마다 연산을 하면서 슬라이드를 하기 때문이다.

푸리에 변환

Laplacian Matrix

한 노드가 가지고 있는 간선의 수를 대각형으로 놓은 다음 인접행렬을 뺀다.

  • 대각행렬의 원소일 경우, 두 노드간의 간선을 제외한 나머지 간선의 수

  • 대각행렬의 원소가 아닌 경우, 두 노드 사이 간선이 있을 경우 -1 또는, 간선이 없을 경우 0이 된다.

http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/16_spectral_methods1.pdf

참고 :

PreviousPresentationNextCRF

Last updated