GNN의 배경
기존 머신러닝은 유클리드에 잘 적용된다. 그 이유는 선형회귀와 같은 머신러닝 모델들이 대부분 가정하는 것이 특징이 서로 독립적이기 때문이다.
유클리드 데이터가 아닌 것들은 그래프 또는 트리 구조를 가진 데이터를 말한다. 그래프틑 연결된 edge들이 방향성이 있거나 없거나, 순환되는 구조가 있다. 트리는 방향성이 있는, 즉 유향 비순환 그래프의 한 종류로 생각하면 된다. 단 tree는 root node 가 하나로 고정되어 있다. 이렇게 유클리드 데이터가 아니면 특징 간에 관계가 있기 때문에 기존 머신러닝 방법으로는 접근이 어렵다. 이 문제를 해결하기 위해 다양한 Neural Network 가 제안되었다.
GNN의 종류
- Recurrent GNN
- Recurrent를 기반으로 iteration을 통해 node를 학습하는 방법
- Convolutional GNN
- CNN을 기반으로 각 node 또는 edge의 정보를 계산하는 방법
- Graph AutoEncoders
- 그래프를 embedding하거나 새로운 그래프를 생성하는 방법
- Spatial-Temporal GNN
- 그래프의 spatial과 temporal을 함께 고려한 방법
Convolutional GNN(spectral model)
단점
spectral 모델은 학습한 데이터의 푸리에 변환을 기반으로 하기 때문에 새로운 데이터를 적용했을 때, eigenbasis가 변해서 일반화가 떨어진다는 단점이 있다. 또한 undirected graph에 제한되어 있기 때문에 다른 graph에는 사용할 수 없다는 단점이 있다.
spectrum의 의미
spectrum은 양자역학에서 관찰가능량에 대응하는 에르미트 연산자의 eigenvalues로 측정한 양자들의 집합을 말하기도 한다. 이와 같이 다양한 분야에서 spectrum이라는 말이 사용되고 있다. 현재는 이미지나 음성 데이터에서 spectrum representation을 얻기 위해 푸리에 분석을 활용한다.
Spectral GCN의 핵심
-
signal processing에서 사용하는 푸리에 변환을 활용하여 Convolution theory와 연결하여 사용한다.
-
푸리에 변환을 위해 사용하는 것이 라플라시안 operator다.
-
라플라시안 operator는 두 노드 간의 거리를 나타내는 방법이다.
-
라플라시안 매트릭스에 eigen decomposition을 사용하여 eigenvalue와 eigenvector를 활용한다.
-
Convolution은 푸리에 변환의 곱과 같으므로 Convolution 연산을 푸리에 변환을 활용하여 계산할수 있다.
라플라시안 operator
벡터장이 균일하지 않은 정도를 파악할수 있는 방법이다. 예를 들어 이미지에서 라플라시안 필터를 사용하게 되면 이미지 내에서 어떤 물체의 경계선 같은 곳이 있을 때, 필터의 결과값이 균일하지 않은 곳은 라플라시안 값이 크게 나온다. 라플라시안 필터를 싀운 이미지는 물체의 edge가 나오게 된다.
푸리에 변환
앞에서 많이 설명했기 때문에 생략
예제
스펙토그램을 분석하기 위해 GNN을 사용하여 노드와 에지가 있는 그래프로 나타낼 수 있다. 그 방법 중 하나는 스펙토그램의 각 픽셀을 그래프의 개별 노드로 취급하는 것이다. 여기서 픽셀 값은 특징 벡터를 나타낸다.
계산비용을 줄이기 위해 슬라이딩 윈도우 방식을 사용하여 스펙토그램에서 로컬 패턴 또는 기능을 추출하고 유사성 또는 상관관계를 기반으로 인접한 윈도우 간의 에지를 정의할 수 있다.
유사성 또는 상관 관계를 기반으로 인접한 창 사이의 에지를 정의할 수 있다. 예를 들어 인접한 특징 벡터 쌍 사이의 코사인 유사성 또는 Pearson 상관 관계를 계산하고 유사성 또는 상관 관계가 특정 임계값을 초과하는 경우 두 창 사이의 에지를 정의할 수 있다. 그 결과 각 노드가 스펙트로그램의 로컬 기능에 해당하고 각 에지가 인접한 기능 간의 관계에 해당하는 그래프가 생성된다.
