Graph
1) 개요
node와 edge로 이루어진 구조를 그래프라고 한다. 이를 활용하여 데이터 간의 관계성이 크고 중요한 데이터를 효과적으로 나타낼 수 있다. 페이스북의 친구관계, 분자구조, 바이러스 감염자 간의 관계 등이 대표적인 예이다. edge는 단순히 연결하는 것에 그치지 않고 방향성(directed, undirected)과 가중치(weighted, unweighted)를 활용하여 추가적인 정보를 가지기도 한다.
2) 그래프 데이터의 구조
그래프 데이터는 vertex (node) set와 edge set로 구성되며 다음의 총 4가지 요소들로 나타낼 수 있다.
- node-feature matrix (n x f) : 각 노드에 해당되는 feature 정보를 가지고 있는 matrix로 feature의 개수에 따라 차원의 수가 정의된다.
- adjacency matrix (n x n) : 노드가 연결되어 있는지 유무에 따라 0과 1의 수로 나타내는 matrix이다. (인접행렬)
$$D_{ii} = \sum_{i~j}A_{ij}$$
- degree matrix (n x n) : 차수 행렬로 각 노드에 연결된 엣지 정보를 나타낸다. (대각행렬)
$$L = D - A$$
- laplacian matrix (n x n)
3) Laplacian matrix (Graph Laplacian)
그래프 이론에서 laplacian matrix는 그래프의 유용한 특성을 찾는데 많이 사용된다. 두번째로 작은 eigenvalue를 통해 graph cut을 하는데 사용하기도 하고 spectral-based GCN에서도 사용된다. 위에서 나온 L = D - A의 유도 과정은 다음과 같다. laplace operation f(x)에서 continuous한 line을 discretize 시킨다.
$$\nabla^{2}f(x) = \lim_{h\rightarrow0}\frac{f(x+h)-2f(x)+f(x-h)}{h^{2}} = \lim_{n\rightarrow\infty}\frac{f(x+\frac{1}{2^{n}})-2f(x) + f(x-\frac{1}{2^{n}})}{(\frac{1}{2^{n}})^{2}}$$
위의 식은 아웃의 노드에 대한 차이를 구한 것으로 볼 수 있다. 이를 수식화 하면 아래와 같은 식이 나온다. 이 수식은 D - A의 값과 같다.
$$\nabla^{2}f(v_{i}) = \sum_{v_{j}~v_{i}} [f(v_{i} - f(v_{j})], \;\; f:V \Rightarrow \mathbb{R}^{n}$$
Graph Convolutional Network
1) 개요
Convolution layer의 경우 filter가 이미지를 sliding하며 feature를 추출한다. FC-layer를 사용한 것보다 각 픽셀 간의 상관관계를 잘표현할 수 있어서 이미지, 비디오와 같은 시각적 정보를 다루는데 많이 사용되고 있다. GCN에서도 이런 특성을 활용하여 graph 데이터에도 적용하려는 시도가 각광 받아왔으며 가장 큰 특징으로는 filter parameter가 모든 노드와 엣지에 공유된다는 것이다.
2) 구조 및 연산
$$H^{(l+1)} = \sigma(AH^{(l)}W^{(l)} + b^{(l)})$$
graph convolution layer와 fc layer로 구성되어 있으며 특징적으로 fc layer에 들어가기 전 readout이 위치한다. A는 adjacency matrix로 edge가 있는 연결된 노드만을 업데이트할 수 있도록 하는 matrix이다. 그리고 readout은 gc layer의 값을 graph 전체를 표현하는 하나의 벡터로 변환하는 함수이다.
$$Readout = \tau(\sum_{i \in G} MLP(H_{i}^{(L)}))$$
- readout : node의 순서가 바뀌더라도 해당 그래프의 속성은 변하지 않는다. 하지만 컴퓨터가 연산을 수행할 경우 이를 동일한 것으로 인식하기 못하기 때문에 readout layer를 통해 동일한 결과를 만들 수 있다. MLP (multi-layer perceptron)을 hidden state에 적용하여 모든 노드가 연결되며 하나의 벡터가 구성된다.
- 구현 1) pytorch-geometric.readthedocs.io/en/latest/ 2) www.dgl.ai
graph classification/regression에서는 readout이 필수지만 node classification, link prediction에서는 사용하지 않는다.
3) Tasks
- graph-level : graph classification
- edge-level : edge classification and link prediction
- node-level : node regression and classification
Semi-supervised classification with GCN
해당 논문은 spectral graph-based neural network를 발전시킨 모델을 제시하였다. ChebyNet을 간소화시키고 self-loop을 추가한 Renormalization trick을 제안하였다. 여기서 말하는 spectral-based는 spatial-based의 이웃노드에 대한 정보만 반영하는 것과 다르게 더 많은 정보를 반영한다.
1) Semi-supervised
node classification을 수행하는데 있어서 매우 적은 노드에 대해서 label 값이 있는 경우에서도 학습을 할 수 있는 방법이다. 방대한 양의 데이터에 대해 labeling을 모두 하는 것이 데이터를 정제하는데도 많은 시간이 소요되고 오류가 발생할 수도 있다. 그래서 몇몇 데이터에 대한 label 값으로 준지도 학습을 수행하는 것이다.
2) introduction
기존에 사용되던 graph-based regularization 중 예시로 graph laplacian regularization term을 loss function에 적용한 것을 들고 있다.
위의 loss function에서 L_0는 label이 된 node에 대한 loss값이고 뒷부분은 regularization을 의미한다. 해당 식은 그래프 내에서 연결된 node는 동일한 label 값을 가지고 있다고 가정한다. 하지만 이런 가정은 modeling capacity를 제한하고 edge가 node similarity를 의미하지 않는 경우에 제약이 있다. 따라서 이를 해결하기 위해 논문의 저자는 graph structure를 직접 NN모델에 입력하여 loss function에서 explicit graph-based regularization를 피하기 위한 방법을 제시했다.
3) Semi-supervised node classification
$$Z = f(X, A) = softmax(\hat{A}ReLU(\hat{A}XW^{0})W^{1})$$
$$\hat{A} = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}, \;\; \tilde{A} = A + I_{N}$$
multi-layer GCN을 고려하여 위와 같이 layer-wise propagation rule을 제시했다. A(인접행렬)에 identity matrix를 더하여 node 자체의 정보를 사용할 수 있게 됐다. 이를 적용하지 않으면 자신의 특성을 고려하지 않고 연산을 수행하는 것과 같은 의미이다. convolution layer에서 sparse connection를 위해 이를 적용했다고 보면 된다. 연결이 많이 된 node일수록 연산 이후 큰 값을 가지게 되고 적게 연결 될수록 작은 값을 가진다. 따라서 degree matrix를 이용하여 normalization을 수행하는데 이는 exploding/vanishing gradient 현상을 방지하기 위해 사용한다.
4) experiments
ref.
medium.com/bioai/graph-convolutional-networks-cf5d0f7b28d2
'AI > Deep Learning' 카테고리의 다른 글
| RNN, LSTM, GRU (0) | 2021.04.02 |
|---|---|
| CNN(Convolutional Neural Network); 합성곱 신경망 (0) | 2021.03.15 |
| Softmax Classifier (0) | 2021.03.09 |
| Batch Normalization (0) | 2021.03.05 |
| Dropout (0) | 2021.03.04 |
