-
Convolution to GNN Tutorial카테고리 없음 2021. 7. 29. 10:21
목차 :
- GNN 간단 리뷰
- Convolution 연산의 수학적 정의, 머신러닝에서 중요한 이유
- 푸리에 변환
- 라플라시안
- 푸리에 변환과 라플라시안의 관계
- 그래프에 대한 Convolution 연산 적용 및 라플라시안
- 체비셰프 근사를 컨볼루션 필터에의 적용
- 코드
GNN Review
Definition of GNN
- 그래프에서 노드는 그의 특징과 주변 노드들에 의해 정의됩니다.
- 그래프에서 노드들은 서로 연결되어 있기 때문에 데이터들이 dependent 하게 됩니다.
- 따라서 그래프는 상호의존적인 관계가 많은 데이터를 모델링하는데 효과적입니다. 그리고 세상의 많은 지식들은 그래프를 통해 표현됩니다.
- GNN의 목표는 그래프의 state에 대한 임베딩을 배우는 것입니다. 이 임베딩은 각 노드들에 대해 주변 이웃들의 정보를 인코딩합니다. 특정 노드의 임베딩은 아래와 같이 정의됩니다.
local transition function of Vanila GNN
- 순서대로 노드의 피쳐, 엣지들의 피쳐, 노드 v의 이웃들에 대한 은닉상태, 이웃 노드들의 피쳐입니다.
$$h_v = f(\mathbf x_v, \mathbf x_{co[v]}, \mathbf h_{ne[v]}, \mathbf x_{ne[v]})$$
$$o_v = g(\mathbf h_v, \mathbf x_v)$$
global transition function of Vanila GNN
$$H = F(H, X)$$
$$O = G(H ,X_N)$$
- H, O, X의 경우 각각의 local transition function과 feature들을 쌓아서 행렬로 만든 것입니다,
$$H^{t+1} = F(H^t, X)$$
- 상태에 대한 임베딩은 위의 식으로 업데이트가 됩니다.
- 이제 GNN의 프레임워크가 정의되었으니 Loss를 정의해야 합니다.
Loss of GNN
$$loss = \sum_{i=1}^p(\mathbf t_i - \mathbf o_i)$$
- 위 식에서 p는 지도학습될 노드의 수이고, t는 특정 노드의 타겟값에 해당합니다. o의 경우 특정 노드의 예측값입니다.
그래프 문제
- Node Classification Node embedding을 통해 점들을 분류하는 문제다. 일반적으로 그래프의 일부만 레이블 된 상황에서 semi-supervised learning을 한다. 대표적인 응용 영역으로는 인용 네트워크, Reddit 게시물, Youtube 동영상이 있다.
- Link Prediction 그래프의 점들 사이의 관계를 파악하고 두 점 사이에 얼마나 연관성이 있을지 예측하는 문제다. 대표적인 예로 페이스북 친구 추천, 왓챠플레이(유튜브, 넷플릭스) 영상 추천 등이 있다. 물론 저들이 GNN을 실제로 쓰는지는 모르고 우리도 쓰는지 안 쓰는지 비밀이다. 궁금해요? 궁금하면 클릭. 영화와 유저가 점이고 유저가 영화를 봤으면 선으로 연결을 해준 그래프를 생각할 수 있다. 선으로 연결되지 않은 영화, 유저 쌍 중에 연결될 가능성이 높은 쌍을 찾아서 유저가 영화를 감상할 가능성이 높다고 예측할 수 있다.
- Graph Classification 그래프 전체를 여러가지 카테고리로 분류하는 문제이다. 이미지 분류와 비슷하지만 대상이 그래프라고 생각하면 된다. 분자 구조가 그래프의 형태로 제공되어 그걸 분류하는 산업 문제에 광범위하게 적용할 수 있으며 따라서 화학, 생의학, 물리학 연구자들과 활발히 협업을 하고 있다.
Limitations of GNN
- 그래프의 hidden states를 업데이트를 반복적으로 수행해서 수렴하는 점을 찾는 것은 매우 비효율적인 연산입니다.
- Vanila GNN의 경우 모든 반복해서 같은 파라미터를 사용합니다. 하지만 현대 딥러닝의 경우 층마다 다른 파라미터를 사용해서, 계층적인 특징을 추출할 수 있습니다. ex) CNN
- 그래프에서는 몇몇 노드들이 중요한 특징을 가지고 있을 수 있습니다. 그러나 바닐라 GNN으로는 이러한 특징들을 효과적으로 모델링할 수 없습니다. → 어텐션을 도입한 GAT.
- 노드의 은닉상태를 업데이트하는 작업은 순차적인 과정입니다. →RNN 계열의 인공신경망을 도입하는 것이 좋아보입니다.
이러한 바닐라 GNN의 한계점들을 해결하기 위해 Convolution, Recurrent, Attention 등의 Layer를 넣는 그래프 뉴럴네트워크가 등장합니다.
스펙트럼 표현이란 ?
Convolution 연산
합성곱 : 특정 시스템의 입력에 대한 출력을 계산할 때 사용하는 연산. 연산을 통해 새로운 함수를 생성합니다.
신호함수를 반전시키고 이동시켜서, 값을 곱한 후 특정 구간에 대해서 적분합니다.
여기서 x는 입력, y는 출력, h는 신호전달함수합니다.
$$(1) ~~~~~~~ y(t) = x(t) * h(t) = \int_{-\infty} ^\infty x(\tau) h(t-\tau)d\tau$$
$$(2) ~~~~~~~~~~~~y(t) = x[n] * h[n] = \sum_{k=-\infty}^{\infty}x[k]h[n-k]$$
머신러닝에서 Convolution이 중요한 이유
- 가중치 공유를 통한 효율적인 연산
- Local Feature들의 공간적 정보를 보존
Q. 왜 Convolution을 그래프에 적용하려고 할까요?
A : 컨볼루션 연산을 통해 그래프나 특정 노드를 입력으로 받아서 원하는대로 출력하고 싶기 때문입니다. 예를 들어 그래프, 노드의 카테고리 분류나 영향력 계산 등이 있습니다.
단순히 컨볼루션을 적용하기엔 그래프 데이터는 비유클리드 형태의 데이터여서 적용 불가능합니다.
또한 그래프의 크기가 너무 커지면 수작업으로 특징을 추출하기 힘듭니다. 따라서 특징들을
자동으로 추출하기 위해 Convolution Neural Network를 도입하려고 하지만 grid 형태의 데이터가 아니므로 연산을 적용할 수 없었습니다. → 푸리에 변환을 통한 컨볼루션
푸리에 변환
특정 입력 신호를 다양한 주파수를 가지는 주기함수들의 합으로 표현하는 변환입니다.
아래 그림처럼 특정 신호를 sin, cos 함수들의 합로 분해할 수 있습니다.
time domain → frequency domain
$$f(x) = \int_{-\infty} ^\infty F(u)e^{j2\pi ux}du ~~~~~~~(1)$$
$$F(u) = \int_{-\infty} ^\infty f(x)e^{-j2\pi ux}dx ~~~~~~~(2)$$
j는 허수, f(x)는 입력 신호, $e^{j2\pi ux}$는 주파수가 u인 주기함수, F(u)는 주기함수의 계수(해당 주기함수의 강도)
식의 해석 : 입력신호 f(x)는 다양한 주파수를 가지는 주기함수들의 합으로 표현됩니다.
위의 (1) 식을 푸리에 역변환, 아래 식 (2)를 푸리에 변환이라고 합니다.
2. 푸리에 변환의 성질
$$F^{-1}(F(v)) = v ~$$
$$F(v*w) = F(v) \cdot F(w)$$
$$v * w = F^{-1} (F(v*w)) = F^{-1}(F(v) \cdot F(w))$$
Q. 왜 푸리에 변환을 그래프에 적용하려고 할까요?
→ 그래프를 분리가능한 여러 신호들의 합으로 해석해서 푸리에 변환을 적용합니다. 푸리에 변환, 역변환을 통해 컨볼루션 연산을 계산가능합니다.
3. 오일러 공식
복소지수함수를 삼각함수로 변환하게 해주는 공식
$$e^{i\theta} = cos\theta + jsin\theta$$
$$e^{j2\pi ux} = \cos2\pi ux + \sin2\pi ux$$
4. 푸리에 행렬의 정의
선형대수학에서 특정 벡터를 행렬과의 곱을 통해 선형 변환하는 것을 배웠습니다.
즉, 행렬이란 벡터를 입력으로 받고 또 다른 벡터를 출력 해주는 함수로 작동한다고 배운 바 있습니다.
비슷한 맥락으로 오일러의 공식을 이용해서 푸리에 변환을 행렬의 형태로 표현할 수 있습니다.
$$F(u) = \int_{-\infty} ^\infty f(x)e^{-j2\pi ux}dx ~~~~~~~(2)$$
위의 연속 구간에 대한 푸리에 변환 식은 신호가 이산적일 경우 아래와 같이 표현되고, 푸리에 변환을 행렬과 벡터의 곱셈으로써 정의할 수 있게 됩니다.
전체 신호의 길이가 N인 이산신호 x[n]과 길이가 N인 이산 주파수 성분 X[k]에 대하여
$$X[k] = \sum_{n=0}^{N-1}x[n]~exp~({{-j2\pi k \over N}n})$$
$$x[n] = \sum_{k=0}^{N-1}X[k]~exp~({{j2\pi k \over N}n})$$
5. 함수에 대한 라플라시안
그래디언트에 발산을 취한 것. 특정한 점에서의 함수의 오목, 볼록을 나타냄. 이차미분계수와 비슷합니다.
$$\triangle f = \nabla^2f = \nabla \cdot \nabla f$$
6. 그래프에 대한 라플라시안
무방향 그래프에서 정의합니다.
Degree matrix는 특정 노드에 연결된 edge의 수를 나타낸다. 대각 행렬의 제외한 모든 성분이 0
인접행렬은 노드간의 연결여부를 1과 0으로 표현한다. 대각행렬의 모든 성분이 0
라플라시안 행렬은 Degree matrix - adjacency matrix로 정의된다. degree와 adjacency를 모두 포함하게 됩니다.
-라플라시안 행렬을 정규화 안하면 합쳐지면서 gradient 소실이나 폭발이 생길 수 있다고 합니다.
웬만해서는 코드에 정규화를 하는 것 같습니다.
여기서 $U^H$는 에르미트 행렬로 대칭 성분이 켤레 복소수가 되는 행렬입니다.
Q. 특정함수에 대한 라플라시안과 그래프에서 말하는 라플라시안 행렬의 상관관계? (미해결)
A : 푸리에 변환 행렬의 각 열을 이루는 함수들은 라플라시안 행렬의 고유벡터이다.
7. 그래프의 스펙트럼 표현과 푸리에 변환을 통한 컨볼루션
한 줄 요약 : 푸리에 도메인에서 컨볼루션은 그래프의 라플라시안행렬을 고윳값 분해해서 계산할 수 있다!
기존의 Spectral Graph Theory에서는 라플라시안 행렬을 Spectral decomposition(푸리에 기저를 통한 대각화)을 수행하고 얻은 푸리에 행렬을 통해 노드에 대한 푸리에 변환을 하였습니다.
그리고 이를 토대로 그래프에 대한 컨볼루션을 푸리에 변환과 그 역변환을 통해 구할 수 있었습니다.
그러나 이는 노드의 수가 많아질 수록 행렬의 크기가 제곱으로 커지므로 고유값을 구하는 연산이 매우 비효율적임. 실제로 사용하기에 제약이 있습니다.
8. Spectral Network
위에서 컨볼루션연산이 그래프 라플라시안을 고윳값 분해해서 푸리에 영역에서 계산할 수 있었습니다.
Spectral method에서는 그래프에 대한 연산은 다음과 같이 입력 신호 $\mathbf x$와 필터 $g_\theta$의 컨볼루션으로 정의하게 됩니다. 필터 $g_\theta$는 파라미터로 구성된 대각행렬이고 이 파라미터들은 고윳값분해를 통해 계산합니다.
$$g_\theta = diag(\theta)\\ \\ g_\theta * \mathbf x = U g_\theta(\Lambda)U^T \mathbf x$$
여기서 $U$는 정규화된 라플라시안 행렬에서 구한 고유벡터 행렬입니다. $D^{-{1\over2}}AD^{-{1\over2}} = U\Lambda U^T$
D는 Degree Matrix, A는 Adjacency Matrix입니다.
9. ChebNet. Spectral Convolutional Layer
문제점 : 행렬에 대한 스펙트럼 분해는 연산이 전역적이고 매우 계산비용이 많이듭니다.
목표 : 스펙트럼 분해가 아닌 수치근사적 방법을 통해 그래프의 컨볼루션을 계산합니다.
CHEBNET 논문에서는체비셰프 다항식을 전개해서 필터 **$g_\theta$**를 근사하는 방법을 제안합니다.
즉, 아래 식의 좌변의 $g_\theta$와 입력신호 x의 컨볼루션은 우변의 식으로써 근사될 수 있다는 뜻입니다.
$$g_\theta(\Lambda) * \mathbf x ~\approx~ \sum_{k=0}^K\theta_k T_k(\hat{\Lambda})\mathbf x \\ \\ \hat{\Lambda} = {2\over \lambda_{max}}\Lambda - I \cdot \lambda_{max}$$
여기서 $\hat {\Lambda}$ 는 가장큰 고윳값을 통해 정규화된 라플라시안 행렬을 뜻합니다. 위 식은 K-localized 된 컨볼루션 연산을 사용해서 컨볼루션 뉴럴네트워크를 정의합니다. 이를 통해 라플라시안의 고윳벡터를 계산할 필요가 없어졌습니다.
체비셰프 다항식 :
- 체비셰프 다항식은 삼각함수의 배각공식을 표현하는 다항식입니다.
$$T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x), T_0(x) = 1, T_1(x) = x$$
1종 체비셰프 다항식 :
$$T_n(\cos\theta) = \cos n\theta$$
2종 체비셰프 다항식 :
$$U_n(\cos \theta)\sin \theta = \sin (n+1) \theta$$
Q. 왜 체비셰프 다항식을 통해 필터를 근사하는가?
A : 필터 $g_\theta$가 스펙트럼 분해를 통해 구해진 푸리에 변환행렬과 그의 전치행렬의 곱의 형태이기 때문입니다. 푸리에 변환의 각 열들은 오일러 공식의 형태를 띄고 있었고 이에 cos과 sin으로 표현할 수 있기에 체비셰프로 다항식으로 근사합니다.
10. 코드
눈여겨 볼 것 :
- 가중치가 행렬 형태가 아닌 텐서 형태. 즉, 행렬을 K개 쌓아서 (k, in, out) 사이즈의 텐서가 가중치가 된다.
눈여겨 볼 것 (첫 번째 박스) :
- remove_self_loops() 메소드에서 자기 자신에 대한 루프를 제거한다.
- get_laplacition() 메소드에서 Degree Matrix, 인접행렬을 만들고 Laplacian 행렬을 만든다.
눈여겨 볼 것 (두 번째 박스) :
- 라플라시안 행렬 $\hat{\Lambda}$를 정규화하는 코드
torch_geometric의 데이터의 예시 :
edge_index = [[0, 1, 1, 2] 1, 0, 2, 1]
Degree Matrix
$$\def \arraystretch{1.5} \begin{array}{c::} & 0 & 1 & 2 & \\ \hline 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 0 \\ 2 & 0 & 0 & 1 \end{array}$$
인접행렬
$$\def \arraystretch{1.5} \begin{array}{c::} & 0 & 1 & 2 & \\ \hline 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 2 & 0 & 1 & 0 \end{array}$$
$$T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x), T_0(x) = 1, T_1(x) = x$$
$$g_\theta(\Lambda) * \mathbf x ~\approx~ \sum_{k=0}^K\theta_k T_k(\hat{\Lambda})\mathbf x \\ \\ \hat{\Lambda} = {2\over \lambda_{max}}\Lambda - I \cdot \lambda_{max}$$
위 식에서
- $\theta_k$는 k번째 가중치 행렬 self.weight[k] ,
- $T_k$는 self.propagate 함수,
- $\hat{\Lambda}$는 정규화된 라플라시안 코드에서는 norm
- $\mathbf x$는 노드들의 feature
- 반복문은 위 식의 시그마에 해당.
미해결점 :
- ChebConv 논문에 따르면 K의 값은 체비셰프 필터의 사이즈라고 한다. 즉, 뉴럴 네트워크를 쌓는 높이 이다. K의 값을 늘리거나 줄이면 어떤 현상이 일어날까요?
A : K가 너무 적으면 그래프의 특징을 제대로 표현하지 못할 것 같고, K가 너무 많으면 오버피팅 될 것 같습니다.
- forwad 함수에서 edge_index를 왜 넣어야할까요? 보기에는 message passing을 할 때, 아무 역할도 하지 않는 것처럼 보입니다. 즉, 인풋을 그대로 전달하는 것 같습니다.
A : message passing의 경우 엣지에 피쳐가 있는 경우, 즉, 가중치가 있는 경우에 사용하는 방법들입니다. 나중에 Message Passing Neural Network를 배워야 알 것 같습니다.
Message Passing : 노드를 표현하는 벡터를 계속해서 업데이트 해나가는 과정. 컨볼루션 연산을 다른 도메인에서 일반화시킬 때 이를 neighborhood aggregation 또는 message passing이라고 함.
요약하자면 주변 노드들의 피쳐를 통해 현재 노드의 피쳐를 업데이트 하는 것.
[출처]