Graph Representation Learning Book의 Chapter5을 번역, 요약, 정리했습니다.

5.2 Generalized Neighborhood Aggregation

이번 장에서는 AGGREGATE 함수를 일반화하고 개선하는 방법을 다룹니다.

5.2.1 Neighborhood Normalization

앞서 Basic에서 단순이 이웃 노드들의 임베딩을 더해주는 방법을 사용했습니다. 이때 더해주는 것은 노드의 degree에 영향을 많이 받게되고 값이 급격히 커지는 문제가 생길 수 있습니다. 단순한 방법으로 노드의 degree로 값을 나눠서 정규화해서 해결합니다. 이때 Target 노드 뿐만아니라 각 이웃 노드의 degree까지 함께 나눠주는 symmetric normalization 방식을 적용하는 것이 효과적이라고 합니다.

\[m_{N(u)} = \sum_{v \in N(u)} \frac{h_v}{\sqrt{| N(u) | | N(v) |}}\]

Graph convolutional networks (GCNs)

가장 대표적인 GNN 방식 중 GCN는 self-loop 방식에 symmetric normalization 을 함께 적용합니다.

\[h_u^{(k)} = \sigma ( W^{(k)} \sum_{v \in N(u) \cup \{u\}} \frac{h_v}{\sqrt{| N(u) | | N(v) |}} )\]

GCN 구현

위 과정을 pytorch-geometric을 이용해 GCN Layer를 구현해보고 pytorch-geometric에 내장된 GCNConv와 비교해보겠습니다.

pytorch-geometric 설치

각자 환경에 맞춰서 라이브러리를 설치합니다. https://pytorch-geometric.readthedocs.io/en/latest/notes/installation.html

데이터 정의

torch_geometric.data 형식에 맞춰 데이터를 정의합니다. 여기서 데이터 1개는 그래프 1개를 의미합니다.

0번 노드와 1번 노드, 1번 노드와 2번 노드가 연결된 그래프입니다.

import torch
from torch_geometric.data import Data

x = torch.tensor([[-1], [0], [1]], dtype=torch.float)

edge_index = torch.tensor([[0, 1],
                        [1, 0],
                        [1, 2],
                        [2, 1]], dtype=torch.long)

data = Data(x=x, edge_index=edge_index.t().contiguous())

데이터의 x는 각 노드를 의미합니다. 여기서 shape은 (노드 수, Feature 차원 수)으로 이루어 집니다.

n_nodes, n_features = data.x.shape

n_nodes  # 3
n_features  # 1

GCNConv 결과

pytorch-geometric에 내장된 GCNConv를 선언하겠습니다. GCNConv(in_channels, out_channels)로 Layer를 정의합니다. 노그의 Feature 차원이 1이고, Hidden Feature는 3으로 설정합니다.

from torch_geometric.nn import GCNConv

conv = GCNConv(1, 3)

conv Layer에 데이터를 Forward 시켜 k=1의 결과를 얻을 수 있습니다.

conv1(data.x, data.edge_index)

# tensor([[ 0.1714,  0.0919, -0.1091],
#         [ 0.0000,  0.0000,  0.0000],
#         [-0.1714, -0.0919,  0.1091]], grad_fn=<AddBackward0>)

GCNConv 구현

위의 GCNConv 결과가 나오는 과저을 살펴보겠습니다.

  1. 먼저 Self-loop를 설정합니다. edge_index에 Self Edge가 추가되었습니다.
from torch_geometric.utils import add_self_loops

x = data.x
edge_index = data.edge_index

edge_index, _ = add_self_loops(edge_index, num_nodes=x.size(0))
edge_index
# tensor([[0, 1, 1, 2, 0, 1, 2],
#         [1, 0, 2, 1, 0, 1, 2]])
  1. 각 노드의 Degree를 계산합니다. Undirected 그래프로 엣지의 Out 또는 In 노드를 이용해 계산할 수 있습니다.
from torch_geometric.utils import degree 

out_node, in_node = edge_index

deg = degree(in_node, x.size(0), dtype=x.dtype)
deg
# tensor([2., 3., 2.])
  1. Symmetric Normalization 상수를 계산합니다. In 노드와 Out 노드의 -0.5승 degree를 이용해 각 엣지의 정규화 값을 계산합니다.
deg_inv_sqrt = deg.pow(-0.5)
norm = deg_inv_sqrt[out_node] * deg_inv_sqrt[in_node]
  1. 각 노드의 Message 값을 계산합니다. (동일한 결과를 얻기위해 conv의 Linear 임베딩을 공유해서 사용합니다.)
message = conv1.lin(x[in_node])
  1. Message 값에 정규화 값을 곱해줍니다.
message = message * norm.view(-1, 1)
  1. 각 노드의 이웃 노드들의 message를 AGGREGATE(sum)해 Update 합니다.
node_0 = message[out_node == 0].sum(0)
node_0
# tensor([ 0.1714,  0.0919, -0.1091], grad_fn=<SumBackward1>)

node_1 = message[out_node == 1].sum(0)
node_1
# tensor([0., 0., 0.], grad_fn=<SumBackward1>)

node_2 = message[out_node == 2].sum(0)
node_2
#tensor([-0.1714, -0.0919,  0.1091], grad_fn=<SumBackward1>)

6번에서 계산한 값와 GCNConv 결과 값이 동일함을 알 수 있습니다.