GNN의 기초

그래프란?

데이터 유형에는 시계열, 이미지, 텍스트, 공간적 데이터가 있다.  -> 모두 “연속적”이라는 공통점

그래프는 연속성보다는 상관관계, 위상적 연결을 통해 데이터에 접근하며, 시간에 따른 관계의 변화를 고려한다. 

Graph = G(V, E) V:Nodes(개체), E:Egde(관계)

활용 분야 : 소셜미디어, 화학식, 생물학, 교통, 프로그램 분석

 

그래프를 수학적으로 표현하는 방법

기초적으로 인접행렬[두 노드가 연결되면 1, 연결되지 않으면 0 -> (#node, #node) shape, A or W] 로 표현된다.

그래프의 방향이 ‘없는’ 경우는 인접행렬이 symmetric하다.

하지만 방향이 있는 경우는 정보의 흐름까지 표현하기 위해 대칭성이 깨지게 된다.

또한, 만약 자기 자신의 정보도 중요한 경우에는 Self-loop를 고려하게 되어 (A+I)의 형태처럼 된다. 이를 N(i)합집합{i}로 표현하기도 한다. (i의 Neighbor과 I 자기자신을 합함)

 

Feature Aggregation *정보를 취합하는 것

나의 이웃들에게 정보/신호를 받아 나의 새로운 상태를 계산하는 것

그런데 그래프 위의 노드 신호/정보 값인 feature값을 h라 한다면, Ah가 각 노드가 이웃의 값을 합친 것이 된다.

이는 그래프 위에서의 conv 연산이라고 볼 수 있고, 이때 A는 그래프의 커널 역할을 하게 된다.

 

Aggregation의 두 관점

1. Spectral Convolution

• 그래프 위에서 conv를 어떻게 정의해서 filtering할 것이냐?
• 유클리디안 공간 상의 시간 영역에서 conv란, 퓨리에 공간에서의 곱셈으로 표현된다.
• 주파수 영역(퓨리에 공간)을 정의해서 곱하면 conv를 정의할 수 있을 것이다.
• 그런데 여기서 주파수란 신호의 변화 속도를 표현하는 값인데, 함수에서 라플라시안과 유사하다고 한다.
• Laplacian L = D-A, Eigen Decomposition: L = U*eigenvalues*U_t
• 최종 conv 정의 : h*g = U*g(eigenvalues)*U_t*h, 여기서 g(eigenvalues)는 주파수별 가중치로, 어떤 주파수 성분을 얼마나 통과시킬지 결정하는, CNN에서의 kernel에 해당하는 부분이다.-Spectral Filter)
• 하지만 이때 Decomposition을 계산하는 비용이 O(n^3)이고, 학습 파라미터 수(n)가 너무 많다는 단점이 있다.
• 따라서 계산 비용을 줄이기 위해, 우리가 학습시켜야 하는 Spectral Filter를 Chebyshev polynomial 근사 방법론을 제시한다. 일단 Decomposition이 없어지기에 계산량이 대폭 감소한다. 이걸 ChebNet이라고 하는데, 여기서 K=1로 한 것이 GCN이다.

 

2. Message Passing

• Spectral conv에 비해 훨씬 직관적이다. 노드 간의 직접 통신으로 업데이트 된다. 내가 만약 u라면 u의 주변 정보를 일단 다 모으고, 나의 정보인 h_u를 추가해서 이를 update function에 집어넣는다. 이 함수들(update, aggregate)은 자율적으로 정의하게 된다. 이때 aggregate 함수는 permutation invariance, 즉 노드의 순서는 신경쓰지 않아야 한다.

 

3. GCN(new!)

Spectral conv를 간소화한 것이 GCN인데, 이를 어찌저찌 조정하면 Message Passing 방식으로 식을 정리할 수 있다.

 

4. 한계

aggregation을 할 때 평균을 내면 계속 oversmoothing이 된다.

 

그래프 머신러닝 모델의 종류

1. GCN

• GNN 계보의 출발
• 이웃 정보를 평균화/스무딩한다.
• CNN은 기초적으로 위치 정보를 어쩔 수 없이 이용하지만, GCN은 이 feature들이 떨어져있어도 한 kernel로 볼 수도 있다. receptive field에서 여기저기 떨어져있는 node 중, 내가 의미있다고 생각하는 node들을 찍고, 이를 GCN에 넣는 것이다.
• CNN과 GCN가 근본적으로 다름을 파악하면 좋다.
• 예를 들어, 뇌 사진을 분석한다고 할 때, CNN은 kernel이 평행이동하며 분석을 진행하게 되지만, 어차피 뇌를 감싸는 두개골 위치는 같은 역할을 하기에, 그 같은 역할을 하는 위치의 node들을 한 데 모아 kernel을 적용시킬 수 있다는 것이다.

 

2. GraphSAGE

• Sampling의 도입
• GCN은 그래프가 변화할 때 적응이 불가한 Transductive한 성질을 가지고 있지만, GraphSAGE는 새로운 그래프에서도 재사용이 가능한 inductive learning 한 성격을 가지고 있다.
• GCN에 비해 계산량을 줄일 수 있어 대규모 그래프를 처리할 수 있다.

 

3. GAT

• 중요한 이웃과 중요하지 않은 이웃을 구분하겠다는 목적을 가진다.
• 각 이웃의 중요도를 '학습 가능한 가중치'로 부여할 수 있다.
• 정보의 흐름이 구조적으로 결정되는 GCN과 달리, feature간 관계로 정보의 흐름이 결정된다.
• 정적인 그래프 구조에 한정되는 GCN과 달리, feature 기반 가변적인 표현이 가능하다. 목적함수에 따라 가중치의 업데이트가 결정되는 task-driven한 형태이다. 

 

4. GIN

• 만약 3-cycle graph이고, 모든 노드의 값이 1이면, 노드 값이 update될 수 없다. 또한 한 줄로 이어진 3-path graph의 모든 노드의 값이 1이면, 노드 값이 update될 수 없다. Isomorphism!
• 이렇게 계속 두 그래프의 feature가 계속 동일하게 업데이트 되기에 서로 다른 그래프를 구별할 수 없다고 볼 수 있다 
• 따라서 GIN은 injective한 표현을 찾기 위해 노력한다. injective란, input이 다르면 output도 다르다는 것이다. 

 

5. Graph Transformer

• GNN은 근처 이웃으로부터 정보를 받기에, 멀리 있는 정보는 반영되지 않거나 희석된다는 문제점이 있다. 이를 단순히 해결하기 위해 layer를 깊게(3개 layer 이상) 쌓는다면 oversmoothing, oversquashing, gradient vanishing이 발생한다. "세상 사람들은 두 다리를 건너면 모두 알 수 있다" 라는 말이 있듯, layer를 2~3개만 쌓아도 거의 모든 node를 고려하게 되기 때문이다.
• Self-attention을 사용하며, 그래프의 구조 정보를 반영하기 위해 edge 정보를 bias나 encoding 형태로 주입하게 된다. 

 

6. 한계점

• Oversmoothing
• Locality
• Expressivity
• Data load