푸른 하늘

Preliminaries

NeighborLoader 포스팅

지난번 포스팅에서 PyG의 mini-batch training을 위한 방법 중 하나인 NeighborLoader를 간략하게 살펴보았다.

이번엔 NeighborLoader와 간단한 dataset을 활용하여

이 neighbor sampling (또는 node-wise sampling)의 특징(?)을 알기 위해 간단하게 진행했던 실험에 대해 정리하고자 한다.

작성 편의상 sampling을 수행하는 기준 node, 즉 sampling을 수행하였을 때 최 상단에 위치하게 되는(기준이 되는) node를 anchor node로 작성하였다.

Cora dataset & EDA

여러 초장기 GNN paper에 자주 등장한 dataset이다.

PyG에선 torch_geometric.datasets.Planetoid 에 함께 포함되어 있다.(공식 doc 링크)

여러 GNN paper에 기재된 듯이, 비교적 작은 규모의 citation network 이다.

(전체 node의 수는 2708, edge 수는 5429, feature vector의 차원이 1433.)

그럼 그래프가 어떻게 생겼을까?

살펴보면 다음과 같다. (이미지 출처는 이미지에 포함)

직접 plotting해본 것도 있지만... 아무래도 이렇게 이쁘게 그려주신 분이 있다면 :)

추가적인 EDA를 위해 필요한 라이브러리를 import 한다.

import torch

import networkx as nx
import matplotlib.cm as cm
import matplotlib.pyplot as plt
import pandas as pd

from torch_geometric.datasets import Planetoid
from torch_geometric.loader import NeighborLoader
from torch_geometric.seed import seed_everything
from torch_geometric.utils import to_networkx, unbatch_edge_index

seed_everything(62)

dataset = Planetoid(root='dataset', name='cora')

data = dataset[0]
del dataset

data.n_id = torch.arange(data.num_nodes)

각 node마다의 degree 정도/분포도를 확인.

graph = to_networkx(data)
degree_list = list(graph.degree)
df = pd.DataFrame(degree_list, columns=['n_id', 'degree'])
print(df['degree'].describe())

이미지로 봤던 graph에서 처럼, degree 분포가 상당히 극단적이다.

(근데 사실 대부분의 graph dataset들은 이런 식의 long-tail distribution인 경우가 많다.)

추가적으로 train mask, val mask, test mask 라는 것이 존재한다.

이는 각 train/val/test 마다 masking을 한 것으로, T/F로 이뤄진 값이며,

node를 unseen node처럼 간주하기 위해 사용하는 셈 이다.

print(sum(data.train_mask))    # 140
print(sum(data.val_mask))    # 500
print(sum(data.test_mask))    # 1000

train에는 140개의 mask가, val에는 500개의 mask가, test에는 1000개의 mask가 있다.

이게 도대체 무슨 의미가 있고, 왜 있는 걸까?

앞서 언급하였듯, Cora dataset은 데이터의 규모가 상당히 작은 편이다.

2708 node에 대해, mask를 적용하면 그 값이 False인 node를 train에서 제외하는 셈이다.

즉 해당 갯수(True인 갯수)의 노드만을 가지고 train/val/test를 실시한다는 의미로 볼 수 있다.

(적은 양의 data로 model의 충분한 generalizaion을 돕기 위해서 사용하는 셈 이라고도 볼 수 있을 듯.)

Mini-batch testing

GraphSAGE의 sampler가 어떻게 mini-batch를 생성하는지 직접 코드를 통해 확인해보자.

NUM_NEIGHBORS = [2,4]    # 2-hop sampling
# NUM_NEIGHBORS = [-1]    # 1-hop sampling
BATCH_SIZE = 16
INDEX_NUM = 0

loader = NeighborLoader(
    data = data,
    num_neighbors = NUM_NEIGHBORS,
    batch_size = BATCH_SIZE,
    input_nodes = data.train_mask, # "len(sum(data.train_mask)):140 / batch_size" 갯수 만큼의 batch가 만들어진다.
    # directed=False, # RuntimeError: Undirected subgraphs not yet supported
    disjoint=True # each seed node will create its own disjoint subgraph : 각 anchor node마다 disjoint한 sub-graph를 생성. 
)

subgraph_list = []
nodes_in_subgraph = []
edges_in_subgraph = []
for batch in loader:
    subgraph_list.append(batch)
    # 해당 배치에서 anchor node 를 제외하고 새로 sampling된 node
    nodes_in_subgraph.append(len(batch.n_id.tolist()) - BATCH_SIZE)
    # 새로 sampling된 노드들과 anchor node들 간의 connectivity
    edges_in_subgraph.append(batch.edge_index.numpy()[1].shape[0])

print('Total # of batches : ', len(subgraph_list))    # 9

loader에 대한 loop을 실행할 때 실질적인 sampling이 수행된다.

여기서, disjoint=True 를 하면 서로 연결된 anchor node끼리는 computation graph에 포함시키지 않는다.

즉, anchor node끼리 겹치지 않으며 anchor node 1개당 고유한 computation graph를 생성하게 되고,

약간의 작업을 통해 batch안에 있는 computation graph들을 각각 분할시킬 수 있다.

(당시 공식 repo discussion 탭에서 질문했던 내용: https://github.com/pyg-team/pytorch_geometric/discussions/6325)

그럼 batch 안에 들어가는 실제 computation graph는 어떻게 생성되는지 확인해보자.

sample_batch = subgraph_list[INDEX_NUM]
# edge_batch = sample_graph[sample_graph.edge_index[0]]
# print(sample_graph.edge_index[0]) # source->target 에서 target에 해당하는 index만을 챙기기.
### batch vector에서 실제로 어떤 node가 어떤 sub-graph에 할당되어 있는지 확인. 
### 즉, 기존 edge_index랑 이 값이랑 비교하면 어떤 앵커가 몇개를 샘플링했는지 확인가능.
# print(sample_batch.edge_index.numpy())
# print(sample_batch.batch[sample_batch.edge_index[0]].tolist())

# batch안에 있는 개별 anchor node마다의 computation graph를 추출할 수 있음.
sample_graph_edge_index = sample_batch.batch[sample_batch.edge_index[0]]
for i in range(BATCH_SIZE):
    edge_index_for_i = sample_batch.edge_index[:, sample_graph_edge_index == i]
    print(edge_index_for_i.numpy())

print된 결과물(첫번째 batch에 포함된 computation graph들)을 보면 다음과 같다.

모든 node마다 2-hop sampling을 수행하였고, 1-hop에서는 2개의 node를, 2-hop에서는 4개의 node를 sampling 했다.

앞서 수행했던 data.n_id = ~~ 부분을 통해 edge_index에 있는 값 (0~15)과 실제 graph에서의 id값인 n_id의 매칭을 통해 각 배치마다 어떤 node가 computation graph를 어떻게 형성하는지 확인 가능하다.

앞서 지정한 BATCH_SIZE 개수 만큼의 computation graph가 생성된 것을 확인할 수 있는데,

눈여겨 볼 점은 각 computation graph마다의 크기가 다른 점이다.

상단 Cora dataset의 graph plot을 봐도 알 수 있듯, 각 node의 degree가 long-tail distribution의 형태를 따르고 있기에

sampling을 수행할 때 고립된(isolated) node가 있다면 서로간의 sampling만을 수행하고 종료되는 것을 짐작할 수 있다.

그렇다면 무엇이 문제일까?

비교분석을 위해 간단한 코드를 작성해서 chart로 확인을 해보자.

# ## x축은 각 batch id, y축은 그 길이 값 -> bar chart
graph_info_tuples = list(zip(nodes_in_subgraph, edges_in_subgraph))
df = pd.DataFrame(graph_info_tuples, columns=['node_num', 'edge_num'])

ax = df.plot(kind='bar', rot=0, xlabel='batch_id', ylabel='value', title=f'batch_size={BATCH_SIZE} \n num_neighbors={NUM_NEIGHBORS}', figsize=(12, 8))#, cmap=cmap)
df.plot(kind='line', xlabel='batch_id', ylabel='value', ax=ax)#, cmap=cmap)
for c in ax.containers:
    ax.bar_label(c, fmt='%.0f', label_type='edge')
ax.margins(y=0.1)
ax.legend(title='columns', bbox_to_anchor=(1, 1.02), loc='upper left')
plt.show()

먼저 batch_size를 다르게 (batch마다 들어가는 anchor node 수를 다르게) 한 경우를 살펴보면 다음과 같다.

batch마다 들어가는 anchor node 수를 다르게 한 경우, 한 개 batch마다의 전체 computation graph들의 크기가 증가하는 경향을 볼 수 있다.

즉, batch_size를 크게 잡으면(한 batch에 넣을 anchor node수를 늘리면) 1개 batch당 computation graph 수 증가하게 되고, batch당 계산량의 차이가 더 심해질 수 있다.

다음은 num_neighbors를 다르게 (고려하는 hop을 다르게, 고려하는 이웃 수를 다르게) 한 경우는 다음과 같다.

고려하는 hop 수를 늘리거나, 고려하는 이웃의 수를 늘리는 경우 (앞서 살펴본 경우와 비슷하게) 한 개 batch마다의 전체 computation graph의 깊이/크기 차가 심하게 증가하는 경향을 확인할 수 있다.

즉 batch당 computation graph의 깊이(depth)/크기가 증가하는 것을 확인할 수 있고, 그 차이의 폭(gap)이 더욱 커지는 것을 바로 확인할 수 있다.

특히 위 사진의 3사분면과 4사분면에서 그 차이가 가장 크게 두드러지는 것을 확인할 수 있는데,

고려하는 이웃의 수가 많으며 고려하는 hop 수가 늘어남에 따라 computation graph의 깊이/크기가 지수적으로 폭발하는 현상을 neighborhood explosion이라고 한다.

(여러 paper에서 언급되는 용어 이기도 하고, PyG 공식 docs에서도 간략하게 소개하고 있다.)

Consideration

neighborhood sampling은 random sampling을 통해 정말 간단하면서도 상당히 안정적인 mini-batch training을 가능하게 한다.

하지만 앞서 진행한 간단한 mini-batch test를 통해 확인한 것 처럼, 무턱대고 sampling을 수행하게 되면 batch마다의 computation graph 크기가 달라지게 되고, neighborhood explosion 문제가 발생할 수 있다.

그렇다면 이게 왜 문제가 될까?

실제 산업현장이 아닌 이상, 대부분 single GPU로 시간을 들여서 이런 문제는 충분히 커버할 수 있는 수준일 것이다.

(위처럼 Cora 같은 dataset이나, Reddit 같은 dataset이라면...)

하지만 실제 산업현장(실세계, real world)에서 등장하는 대부분의 데이터들은 규모가 정말 방대한 경우가 많고,

single GPU로는 턱 없이 부족한 경우가 많다.

(당장 Jure 교수님 산하의 stanford 팀에서 개발/운영중인 OGB(Open Graph Benchmark)를 봐도 large-scale challenge가 있고, 제공중인 dataset에도 상당히 큰 규모의 dataset이 있다.)

결국 Multi-GPU를 통한 distributed training이 필요한데, 보다시피 graph data의 특성 상 이게 상당히 힘들다.

(즉 large graph로부터 mini-batch를 어떻게 잘 만들 것 인지가 문제.)

GPU마다의 load balance를 맞추기 위해선 각 GPU마다 담당하는 양, 계산량이 비슷해야 synchronize가 잘 되어서 이상적인 distributed training이 될 것인데...

앞서 보았듯, mini-batch 마다 그 안에 들어있는 graph data의 크기가 제각각이니 synchronization도 잘 이뤄지지 않게 되고, GPU마다 계산량이 달라지게 되며 결국 놀게되는 GPU가 생겨날 수 밖에 없다.

(이렇게 놀게되는 GPU가 생겨서 작업 시간이 비효율적?이게 되는 문제를 straggler problem이라고도 한다.)

결국 mini-batch를 어떻게 잘 만들어 볼 것이냐 가 관건일 것인데, 단순히 GraphSAGE에서 제안한 random sampling 만으로는 mini-batch를 어떻게 적절하게 잘 만들기가 상당히 골치아프다는 점을 짚고 넘어갈 수 있다.

Conclusion

물론 다양한 paper들이 large-scale graph를 어떻게 효율적으로 distributed training 할 수 있는지 그 방법을 제안하기도 했고, Tiktok의 개발사?로도 알려진 ByteDance에서도 관련된 paper를 내기도 했다.

(당시 review했던 paper들은 기회가 된다면 천천히 posting 하는 것으로...)

글을 작성하며 예전 notion에 정리했던 내용들을 천천히 다시 둘러보니... 참 여러 생각이 든다.

돈 한푼 없이 정말 말 그대로 재미?로 시작해서, 다른 연구실 분과 협업도 해보고, 실험을 하면서 이런 현상이/문제가 정말로 있구나 하는걸 직접 확인하고, (비록 국내 학술대회 였지만) 첫 논문도 작성해보고...

단지 프로젝트가 상당히 길어질 것 같아 3학기를 마친 후 방학때 물러나게 되었지만, 기회가 된다면 다시 한번 진득하게 보고 싶은 field 이기도 하다.

지금은 뭐... 연구실의 다른 후배 분이 이어서 해주시고 있는지, 프로젝트가 그냥 무산났을지도 모르겠다.

당시에도 연구실에서 이 프로젝트를 하던 인원이 나 밖에 없었고, 4학기때 새로 들어온 후배 분에게 간략?한 인수인계를 해드리긴 했는데... 어떻게 진행중인지는 ^^;;

이전 PyG 포스팅 이후 딱 하반기 시즌이 열리는 바람에 하반기에 참 치이고 데이고,

정신없이 지내다가 한숨 돌리고 다시 기록해둬야지 하고 보니 어느새 거진 반년이 지나버리긴 했지만..

마음 속 응어리가 조금이나마 줄어든 기분은 든다. :)

다음 번 이쪽(Programming) 포스팅이 아...마 있을지는 잘 모르겠지만, 포스팅을 하게 된다면 당시 비교실험 등 을 진행했던 코드를 작성하며 review 해보고자 한다.

(집의 환경이 multi-GPU가 아니기에, 아마 single-GPU 코드를 작성하게 될 것 같긴 하다.)

E.O.D.

Preliminaries

PyG의 NeighborLoader 공식 docs

참고가 될 만한 포스팅 (중국어로 작성되어있어, 영어로 번역하여 보는 것을 추천)

지난번 포스팅을 통해 널리 알려진 GNN 라이브러리 중 하나인 PyTorch Geometric (이하 PyG)에 대해 간략하게나마 정리하였다. (링크)

본 포스팅에서는 PyG 활용 시 mini-batch training을 위한 대표적인 method 중 하나인 NeighborLoader에 대해 정리하고자 한다.

작성 편의상 sampling을 수행하는 기준 node, 즉 sampling을 수행하였을 때 최 상단에 위치하게 되는(기준이 되는) node를 anchor node로 작성하였다.

NeighborLoader의 인자

torch_geometric.loader를 확인해보면 NeighborLoader외에 다양한 loader class가 존재한다.

torch_geometric.loader.NeighborLoader는 GraphSAGE에서 제안한 neighbor sampling을 수행하는 DataLoader로, full-batch training이 힘든 (single) large graph에 대해 mini-batch training을 수행할 수 있도록 하는 역할을 수행한다.

(GraphSAGE paper review 링크)

class의 인자를 보면 여러개가 있는데, (거의) 주로 사용하는 인자를 살펴보면 다음과 같다.

• data: 현재 sampling을 수행할 대상이 될 graph.
• num_neighbors: sampling을 수행 할 이웃 node의 수.
  • num_neighbors = [a, b]과 같이 지정하는 경우, 총 2-hop 거리 만큼 까지 sampling을 수행할 것을 의미하며, 첫 번째 hop에선 a개의 이웃 node를, 두 번째 hop에선 b개의 이웃 node를 sampling 하게 된다.
  • 즉, len(num_neighbors)가 sampling에 고려할 hop 수를 의미한다.
  • GCN, GraphSAGE paper에서도 언급하였듯, GNN layer의 개수가 연산 수행 시 고려할 hop 수를 의미하므로, len(num_neighbors) == number of layers == number of hop 이 된다.
• batch_size: 하나의 batch마다 포함될 anchor node의 개수.
  • batch_size = B로 설정하는 경우, 하나의 batch마다 B개의 anchor node가 포함되며, 각 anchor node마다 num_neighbors만큼의 node를 sampling하여 computation graph를 생성하게 된다.
• input_nodes: 이를 설정할 경우, batch마다 len(input_nodes)의 수 만큼을 anchor node로 설정해 computation graph를 생성.
  • 즉 각 batch 마다 최대 B개의 anchor node를 설정하고, 이 anchor node를 input_nodes에서 선택하게 된다.
  • 만약 input_nodes가 지정되지 않았다면 graph에 있는 모든 node에서 ordering 된 순서대로 anchor node를 설정하게 된다.
• disjoint: True로 설정하는 경우, batch안의 구성되는 anchor node마다 서로 겹치지 않는(disjoint) node들을 sampling하여 disjoint한 computation graph를 생성한다. (기본은 False)
  • default인 False일 때, 만일 한 batch에서 anchor node로 node 1, node 2가 함께 있고, 둘이 서로 연결된 node라면 computation graph를 생성할 때 계산의 중복이 발생할 수 있다.
  • 즉 node 1을 기준으로 한 computation graph에 node 2가 포함되고, node 2를 기준으로 한 computation graph에서 node 1이 포함될 수 있다. (각 computation graph에서 representation의 계산에 중복이 발생할 수 있다)

인자 중 batch_size와 input_nodes는 서로 상호보완(?)적이기도 하다.

1. input_nodes를 지정하지 않는 경우 (input_nodes=None): 생성되는 batch의 갯수는 total_nodes / batch_size가 되고, 각 batch마다 설정되는 anchor node의 수는 batch_size가 된다.
   • 특정 node들을 anchor node로 설정하라는 명시가 없으므로, 전체 graph에 있는 모든 node들을 대상으로 node의 id ordering 순서대로 anchor node를 설정한다.
   • 즉 이러한 경우, 전체 batch의 갯수는 total_nodes / batch_size가 되며, 각 batch마다 batch_size만큼의 anchor node의 수가 설정된다.
2. input_nodes를 지정하는 경우 (input_nodes=[~~]): batch_size를 지정하지 않을 시 batch 갯수는 len(input_nodes) (== batch_size=1)가 되고, batch_size 지정 시 batch 갯수는 len(input_nodes) / batch_size 가 된다.
   • batch_size는 (위에서도 동일하게) 한 batch 안에서 고려할 총 anchor node의 개수이다.
   • input_nodes를 지정했는데 batch_size를 지정하지 않는다면: batch_size = 1이 되며, 각 batch마다 1개의 anchor node를 설정하게 되고, 이 anchor node는 input_nodes에 있는 node들 만을 가지고 batch를 생성하게 된다.
   • input_nodes를 지정하고 batch_size도 지정하게 된다면: 각 batch마다 batch_size만큼의 anchor node가 설정되고, 이 anchor node는 input_nodes에 있는 node들만을 가지고 batch를 생성하게 된다.

만일 10개의 node가 있을 때, input_nodes = 2, batch_size = 2와 같이 설정하게 된다면
batch_size만큼 input_nodes에서 anchor node를 선택해 batch 생성하게 되며, 이때는 batch_size==len(input_nodes)이므로 batch 1개에 2개의 anchor node가 선택되어 batch가 1개만 생성된다.

Example

백문이 불여일RUN, 간단한 예제를 통해 직접 확인해보자.

10 node, 15 edge로 구성된 임의의 그래프를 생성하였다.

import torch

import networkx as nx
import matplotlib.pyplot as plt

from torch_geometric.loader import NeighborLoader
from torch_geometric.utils import from_networkx, to_networkx
from torch_geometric.seed import seed_everything

seed_everything(62)

## Custom Graph (10 node) make
G = nx.Graph()
G.add_nodes_from([0,1,2,3,4,5,6,7,8,9])
G.add_edges_from([(0,1), (0,3), (1,2), (1,6), (2,3), (2,7), (3,5), (4,2), (4,6), (5,7), (6,9), (8, 9), (8,3), (9, 3), (0,9)])

## Color map for nodes
color_map = ['red', 'red', 'green', 'cyan', 'pink', 'pink', 'red', 'pink', 'pink', 'green']

# ## Made graph check by plotting
# plt.figure(figsize=(12, 8))
# nx.draw(G, pos=nx.kamada_kawai_layout(G), node_size=500, alpha=1.0, with_labels=True, node_color=color_map)
# plt.show()

graph가 준비되었다면, 앞서 기술한 인자들을 토대로 batch를 생성해보자.

## PyG transform 
data = from_networkx(G)
data.n_id = torch.arange(data.num_nodes) # original node 접근을 위해, n_id attribute 추가.

NUM_NEIGHBORS = [2,3]
BATCH_SIZE = 2

## Loader 생성
loader = NeighborLoader(
    data = data,
    num_neighbors = NUM_NEIGHBORS,
    batch_size = BATCH_SIZE,
)

## sampling 수행
subgraph_list = []
for batch in loader:
    subgraph_list.append(batch)

간단하다. 정말...

이제 생성된 computation graph들을 plot해보자.

def batch_wise_graph_plot(subgraph_index_num):
    # 해당 위치의 subgraph를 가져오기
    graph_in_batch = to_networkx(subgraph_list[subgraph_index_num])

    # 변환작업
    # 각 batch로 들어갈때, global node id는 사라지고 batch마다 고유한 id를 가지게 되므로
    # 이를 original node와 mapping.
    transformed_nodes = graph_in_batch.nodes()
    original_nodes = subgraph_list[subgraph_index_num].n_id.tolist()
    node_dict = dict(zip(transformed_nodes, original_nodes))

    # batch로 가면서 변환된 node id를 original node id와 mapping한 node_dict을 통해 subgraph를 re-label.
    transformed_graph = nx.relabel_nodes(graph_in_batch, node_dict)

    # original graph에서의 node color를 그대로 get.
    colormap_sample = []
    for position in transformed_graph.nodes():
        colormap_sample.append(color_map[position])

    return transformed_graph, colormap_sample


# Plot
plt.figure(figsize=(20,16))
plt.subplot(231).set_title("Original Graph")
nx.draw(G, pos=nx.kamada_kawai_layout(G), node_size=400, alpha=1.0, with_labels=True, node_color=color_map)
for i in range(len(subgraph_list)):
    subgraph, colors = batch_wise_graph_plot(i)

    plt.subplot(int(f'{23}{i+2}')).set_title(f"Anchor Node : {subgraph_list[i].n_id[:BATCH_SIZE].tolist()} \n # of neighbors = {NUM_NEIGHBORS}")
    nx.draw(subgraph, pos=nx.spring_layout(subgraph, k=0.9, iterations=40), node_size=400, alpha=1.0, with_labels=True, node_color=colors)
    # nx.draw(subgraph, pos=nx.kamada_kawai_layout(subgraph), node_size=400, alpha=1.0, with_labels=True, node_color=colors)
    # nx.draw(nx.balanced_tree(3, 3), pos=graphviz_layout(subgraph, prog='dot'), node_size=400, alpha=1.0, with_labels=True, node_color=colors)

plt.tight_layout()
plt.show()

각 subgraph마다 anchor node가 batch_size = 2개씩 선정되었고, 각 anchor node에서 len(num_neighbors) = 2-hop 거리의 이웃까지 sampling하게 된다.

위 plot에서 edge가 양 방향인 경우는 선택된 이웃 node에서 1개의 이웃 node를 선택했는데, 그 이웃이 anchor node인 경우이다.
(disjoint 인자를 따로 명시하지 않았으므로 default인 disjoint = False 가 되었기 때문)

Example (extreme case)

sampling이 어떻게 수행되어서 각 batch마다 어떤 computation graph가 생성되는지는 앞선 예제를 통해 알아보았다.

그렇다면, graph가 조금 많이 극단적인 형태라면 sampling이 어떻게 수행될까?

역시 백문이 불여일RUN, 예제를 작성하여 확인해보자.

10 node, 9 edge로 구성된 임의의 그래프를 생성하였다.

import torch

import networkx as nx
import matplotlib.pyplot as plt

from torch_geometric.loader import NeighborLoader
from torch_geometric.utils import from_networkx, to_networkx
from torch_geometric.seed import seed_everything

seed_everything(62)

G = nx.Graph()

G.add_nodes_from([0,1,2,3,4,5,6,7,8,9])
G.add_edges_from([(0,2), (1,2), (1,6), (2,3), (2,7), (3,5), (4,0), (8,3), (9,3)])

color_map = ['red', 'red', 'green', 'cyan', 'pink', 'pink', 'red', 'pink', 'pink', 'green']

# print(G)
# plt.figure(figsize=(12, 8))
# nx.draw(G, pos=nx.kamada_kawai_layout(G), node_size=500, alpha=1.0, with_labels=True, node_color=color_map)
# plt.show()

data = from_networkx(G)
data.n_id = torch.arange(data.num_nodes)

NUM_NEIGHBORS = [2,3]
BATCH_SIZE = 2

loader = NeighborLoader(
    data = data,
    num_neighbors = NUM_NEIGHBORS,
    batch_size = BATCH_SIZE,
)

# sampling 수행
subgraph_list = []
for batch in loader:
    subgraph_list.append(batch)

(그나마) 앞선 예제보다 좀 많이 극단적인 형태이긴 하다.

이제 batch 마다 생성된 computation graph를 확인해보자.

def batch_wise_graph_plot(subgraph_index_num):
    # 해당 위치의 subgraph를 가져오기
    graph_in_batch = to_networkx(subgraph_list[subgraph_index_num])

    # 변환작업
    # 각 batch로 들어갈때, global node id는 사라지고 batch마다 고유한 id를 가지게 되므로
    # 이를 original node와 mapping.
    transformed_nodes = graph_in_batch.nodes()
    original_nodes = subgraph_list[subgraph_index_num].n_id.tolist()
    node_dict = dict(zip(transformed_nodes, original_nodes))

    # batch로 가면서 변환된 node id를 original node id와 mapping한 node_dict을 통해 subgraph를 re-label.
    transformed_graph = nx.relabel_nodes(graph_in_batch, node_dict)

    # original graph에서의 node color를 그대로 get.
    colormap_sample = []
    for position in transformed_graph.nodes():
        colormap_sample.append(color_map[position])

    return transformed_graph, colormap_sample

plt.figure(figsize=(20,16))
plt.subplot(231).set_title(f"Original Graph \n node : {G.order()}, edge : {len(G.edges())}")
nx.draw(G, pos=nx.spring_layout(G), node_size=400, alpha=1.0, with_labels=True, node_color=color_map)
for i in range(len(subgraph_list)):
    subgraph, colors = batch_wise_graph_plot(i)

    plt.subplot(int(f'{23}{i+2}')).set_title(f"Anchor Node : {subgraph_list[i].n_id[:BATCH_SIZE].tolist()} \n # of neighbors = {NUM_NEIGHBORS} \n node : {subgraph.order()}, edge : {len(subgraph.edges)}" )
    nx.draw(subgraph, pos=nx.spring_layout(subgraph, k=0.9, iterations=40), node_size=400, alpha=1.0, with_labels=True, node_color=colors)

plt.tight_layout()
plt.show()

함수를 만들어두면 역시 재활용하기가 편해서 좋다 :)

anchor node가 1개와만 연결된 경우(anchor node = 4,5 case), 1-hop 거리에서 현재 이웃이 1개밖에 존재하지 않으므로, 해당 이웃만을 선택하게 된다.
(node 4는 node 0을 선택, node 5는 node 3을 선택)

또한 선택된 node에서 1-hop 거리 (anchor node에서 2-hop 거리)에서 이웃들을 최대 3개까지 선택하게 된다.
(node 3의 이웃 2, 5, 8, 9 에서 2, 5, 9를 선택 // node 0의 이웃은 2, 4 밖에 없으므로 2, 4를 선택)

여기서 확인할 수 있는 점은 이웃의 수가 선택하게 되는 수 보다 작으면 전체 이웃을 선택하게 되고, 이웃 수가 선택할 수 보다 많으면 정해진 수 만큼을 선택한다는 것이다.(어떻게 보면 당연한 이치이다)

즉 num_neighbors를 지정하여도 graph의 특성 상 각 batch마다 생성되는 computation graph의 크기가 달라질 수 있다는 점을 확인할 수 있으며, 이것이 GraphSAGE에서 제안한 neighborhood sampling의 특징이다.

(말 그대로 정해진 개수 만큼의 node를 무작위로 sampling)

Conclusion

이전 포스팅처럼 작성하다 보니 글이 조금 길어진 듯 하다.

PyG가 역시 Python/PyTorch style을 잘 따르고 있어 실제로 sampling하여 mini-batch를 구성하는 code가 단 몇 줄 만으로 완성되며 상당히 직관적으로 되어있다.

예제를 작성하기 위해 22년, 23년에 작성하였던 testing code를 다시 열어서 확인하니 그 당시의 기억이 새록새록 떠오르는 듯 하다.

이뻐보이는 grpah를 그려보기 위해 node간의 연결성을 여러 가지로 조합도 해 보고, 각 node마다 색깔도 입혀보고...

현재 포스팅은 온전히 NeighborLoader를 통해 mini-batch가 어떻게 형성되는지를 기술하였는데, 실제 GNN code를 작성하여 mini-batch train을 수행하는 과정은 기존 PyTorch code와 동일하다:

다음 포스팅은 GNN field에서의 MNIST라고 불리는 Cora 데이터 셋과 NeighborLoader를 이용해 간단한 실험을 진행했던 내용을 기술하고자 한다.

E.O.D.

Preliminaries

PyTorch Geometric official docs

PyTorch Geometric official github repo

Stanford PyTorch Geometric tutorial (YouTube)

몇몇 GNN paper를 차츰 읽어보고, 관련 라이브러리가 있는지 찾아보던 중 알게된 PyTorch Geometric, 일명 PyG.

이때가 아마 22년 9월~10월 경인데, 기억상 PyG가 정식으로 공개된지 얼마 되지 않기도 하였고 한창 개발중이던 때라 왠지 더 눈길이 갔던 것 같다.

그리고 무엇보다 마음에 들었던 점은 기존 PyTorch의 code style과 거의 비슷하여서 익숙해지는데 큰 어려움이 없었던 점이다.

더욱 마음에 들었던 점은 바로 공식 docs에 예제 code와 video tutorial를 제공해주어서, GNN의 기본부터 block building, downstream task, advanced topics까지 필요한 부분을 학습할 수 있는 것이 정말 좋았다.

본 포스팅에서는 PyG를 처음 접했을 때 기본 code block의 구성이 어떻게 되는지, code flow가 어떻게 진행되는지를 간략하게 정리하고자 한다.

Basic Data Handling

PyTorch Geometric official docs에서 제공하는 문서를 보면 PyG에서 데이터를 어떻게 다룰 수 있는지 설명하고 있는데, 간략하게 정리해보면 다음과 같다:

• data.x : 각 node마다 가지고 있는 feature를 matrix 형태로 표현. shape는 $(number \ of \ nodes, \ feature \ dim)$가 된다.
• data.edge_index : 각 node간의 연결 정보를 담고 있는 adj matrix 같은 것으로, 효율성을 위해 COO format으로 표현.
• data.edge_attr : 각 edge마다 가지고 있는 feature를 마찬가지로 matrix 형태로 표현. shape는 $(number \ of \ edges, \ feature \ dim)$가 된다.
• data.y : training을 위한 label 정보. shape는 $(number \ of \ nodes, \ *)$ 또는 (graph-level task)에선 $(1, \ *)$가 된다.

단순하다.

실제로 PyG에서 제공하는 Dataset을 받아서 code를 작성하다 보면 대부분 위에 기술한 4가지 인자를 주로 사용하게 된다.

기존 adjacency matrix로는 표현 및 code 활용의 한계가 있어 위와 같은 이중 list 형태의 COO format을 사용하는데, 이게 상당히 직관적이다.

(단순히 첫 번째 row와 두 번째 row 간의 요소들이 서로 연결되어 있다를 의미한다.)

Message Passing

PyG official docs에서도 설명하는 GNN의 핵심인 message passing의 기본적인 골격은 다음과 같다.

$$\mathbf{x}_i^{(k)} = \gamma^{(k)} \left( \mathbf{x}_i^{(k-1)}, \bigoplus_{j \in \mathcal{N}(i)} \, \phi^{(k)}\left(\mathbf{x}_i^{(k-1)}, \mathbf{x}_j^{(k-1)},\mathbf{e}_{j,i}\right) \right)$$

$\mathbf{x}^{(k-1)}_i \in \mathbb{R}^F$가 node $i$의 feature를 의미하며, $\mathbf{e}_{j,i} \in \mathbb{R}^D$는 node $j$와 $i$간 연결된 edge의 feature를 의미한다.

$\bigoplus$가 바로 각 node와 edge들의 feature를 aggregate하는 함수로, 미분 가능하고 순서 불변(permutation invariant)한 특징을 가진다.

(GraphSAGE paper에서도 언급하였듯이, 주로 활용할 수 있는 함수(연산)는 sum, mean, max 가 있다.)

($\phi$와 $\gamma$도 마찬가지로 MLP와 같은 미분 가능한 함수이다.)

PyG에서 제공하는 torch_geometric.nn의 여러 layer module들은 기본적으로 basic class인 torch_geometric.nn.MessagePassing module을 상속 받으며, MessagePassing은 torch.nn.Module을 상속 받는다.

이 MessagePassing은 기본적으로 4가지의 basic block을 구현해야 하는데, 그 구성은 다음과 같다:

• __init__(aggr='mean', 'max', 'add'): feature aggregation의 연산에 있어 어떤 연산을 수행할지를 지정한다.
• propagate(): edge_index와 각 노드들에 전달할 데이터(e.g. feature)를 입력받아 message passing을 위한 초기 단계를 준비한다.
• message(): target node에 전파할 message를 생성하며, propagate()에 의해 호출된다.
• update(): 계산된 message를 이용해 embedding을 갱신한다.

즉, __init__(aggr='mean', 'max', 'add')를 통해 $\bigoplus$를 지정하고, propagate(), message()를 통해 $\phi^{(k)}\left(\mathbf{x}_i^{(k-1)}, \mathbf{x}_j^{(k-1)},\mathbf{e}_{j,i}\right) $의 연산을 수행하며 최종적으로 update()를 통해 $\gamma^{(k)}\left( \cdot \right)$의 연산을 수행하는 셈이다.

실제로 PyG github repo에 공개되어 있는 GNN layer들의 구현들을 살펴보면 MessagePassing을 상속받아 상단의 함수들을 구현하여 layer를 구현한다.

Example Code

Stanford PyTorch Geometric tutorial (YouTube)에서 활용한 colab notebook의 code의 일부를 이용해 기본적인 flow를 살펴보고자 한다.

우선 필요한 library를 import 한 후, MessagePassing을 상속받는 CustomConv class를 작성한다.

import torch
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim

import torch_geometric.nn as pyg_nn
import torch_geometric.utils as pyg_utils
import torch_geometric.transforms as T

from torch_geometric.data import DataLoader
from torch_geometric.data import Planetoid

class CustomConv(pyg_nn.MessagePassing):
    def __init__(self, in_channels, out_channels):
        # add, mean, max 중 add aggregation으로 지정.
        super(CustomConv, self).__init__(aggr='add')
        self.lin = nn.Linear(in_channels, out_channels)
        self.lin_self = nn.Linear(in_channels, out_channels)

    def forward(self, x, edge_index):
        # x의 shape은 [N, in_channels]
        # edge_index의 shape은 [2, E]

        # Add self-loops to the adjacency matrix.
        edge_index, _ = pyg_utils.add_self_loops(edge_index)

        # Node feature matrix 선형 변환
        self_x = self.lin_self(x)

        # propagate()을 통해 message passing의 초기 단계 준비
        return self_x + self.propagate(edge_index, size=(x.size(0), x.size(0)), x=self.lin(x))

    def message(self, x_i, x_j, edge_index, size):
        # Message 계산
        # x_j의 shape은 [E, out_channels]

        # GCN-like message passing
        row, col = edge_index
        deg = pyg_utils.degree(row, size[0], dtype=x_j.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]

        return x_j

    def update(self, aggr_out):
        # aggr_out의 shape은 [N, out_channels]
        return aggr_out

__init__(aggr='add')를 통해 feature aggregation의 연산 방법을 지정하였다.

기존 PyTorch class들과 마찬가지로 forward()를 통해 주 연산을 수행하고, propagate()를 통해 message()와 update()를 호출하여 node embedding을 계산한다.

PyTorch만으로 작성하는 기본적인 여느 model/layer와 큰 차이가 없고, 단지 사용하는 데이터가 image, word가 아닌 graph가 사용됨에 따라 추가적인 연산(feature aggregation 및 message passing)이 추가된 셈이다.

작성된 CustomConv layer를 활용해 기본적인 model을 작성해보면 다음과 같다:

class GNNStack(nn.Module):
    def __init__(self, input_dim, hidden_dim, output_dim, task='node'):
        super(GNNStack, self).__init__()
        self.task = task
        self.convs = nn.ModuleList()
        self.convs.append(self.build_conv_model(input_dim, hidden_dim))
        self.lns = nn.ModuleList()
        self.lns.append(nn.LayerNorm(hidden_dim))
        self.lns.append(nn.LayerNorm(hidden_dim))
        for l in range(2):
            self.convs.append(self.build_conv_model(hidden_dim, hidden_dim))

        # post-message-passing
        self.post_mp = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim), nn.Dropout(0.25), 
            nn.Linear(hidden_dim, output_dim))
        if not (self.task == 'node' or self.task == 'graph'):
            raise RuntimeError('Unknown task.')

        self.dropout = 0.25
        self.num_layers = 3

    def build_conv_model(self, input_dim, hidden_dim):
        # refer to pytorch geometric nn module for different implementation of GNNs.
        if self.task == 'node':
            # 예제 code는 torch_geometric.nn.GCNConv를 사용.
            # return pyg_nn.GCNConv(input_dim, hidden_dim)
            return CustomConv(input_dim, hidden_dim)
        else:
            return pyg_nn.GINConv(nn.Sequential(nn.Linear(input_dim, hidden_dim),
                                  nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)))

    def forward(self, data):
        x, edge_index, batch = data.x, data.edge_index, data.batch
        if data.num_node_features == 0:
          x = torch.ones(data.num_nodes, 1)

        for i in range(self.num_layers):
            x = self.convs[i](x, edge_index)
            emb = x
            x = F.relu(x)
            x = F.dropout(x, p=self.dropout, training=self.training)
            if not i == self.num_layers - 1:
                x = self.lns[i](x)

        # graph-level task는 graph-level embedding을 활용하므로,
        # global pooling 연산을 이용해 graph-level embedding을 생성한다.
        if self.task == 'graph':
            x = pyg_nn.global_mean_pool(x, batch)

        x = self.post_mp(x)

        return emb, F.log_softmax(x, dim=1)

    def loss(self, pred, label):
        return F.nll_loss(pred, label)

제공된 colab code는 node-level task(node classification, Planetoid dataset)와 graph-level task(graph classification, TU dataset)을 수행하는 예시를 보여준다.

(추후 posting 할 예정이지만) graph-level task는 node-level task와는 다르게 말 그대로 graph 하나 하나를 가지고 downstream task를 수행하는 것으로, node embedding이 아닌 graph embedding이 필요하다.

이에 따라 상기 code에서는 global_mean_pool(x, batch)를 통해 각 graph마다 계산된 node embedding에 대해 global pooling 연산을 수행하여 하나의 embedding, 즉 graph embedding을 생성하였다.

PyTorch로 작성된 여느 model과 마찬가지로 forward()를 통해 주 연산을 수행한다.

앞서 언급하였듯이 단지 사용되는 데이터가 graph이기에 node feature와 연결 정보를 담은 edge_index를 이용해 주 연산을 수행한다.

train 및 test를 수행하는 code도 기존 PyTorch의 code style과 거의 동일하다:

def train(dataset, task):
    if task == 'graph':
        data_size = len(dataset)
        loader = DataLoader(dataset[:int(data_size * 0.8)], batch_size=64, shuffle=True)
        test_loader = DataLoader(dataset[int(data_size * 0.8):], batch_size=64, shuffle=True)
    else:
        test_loader = loader = DataLoader(dataset, batch_size=64, shuffle=True)

    # model 선언
    model = GNNStack(max(dataset.num_node_features, 1), 32, dataset.num_classes, task=task)
    opt = optim.Adam(model.parameters(), lr=0.01)
    
    # train
    for epoch in range(200):
        total_loss = 0
        model.train()
        for batch in loader:
      	    print(batch.train_mask, '----')
            opt.zero_grad()
            embedding, pred = model(batch)
            label = batch.y
            if task == 'node':
                pred = pred[batch.train_mask]
                label = label[batch.train_mask]
            loss = model.loss(pred, label)
            loss.backward()
            opt.step()
            total_loss += loss.item() * batch.num_graphs
        total_loss /= len(loader.dataset)

        if epoch % 10 == 0:
            test_acc = test(test_loader, model)
            print("Epoch {}. Loss: {:.4f}. Test accuracy: {:.4f}".format(
                epoch, total_loss, test_acc))

    return model
    
def test(loader, model, is_validation=False):
    model.eval()

    correct = 0
    for data in loader:
        with torch.no_grad():
            emb, pred = model(data)
            pred = pred.argmax(dim=1)
            label = data.y

        if model.task == 'node':
            mask = data.val_mask if is_validation else data.test_mask
            # node classification: only evaluate on nodes in test set
            pred = pred[mask]
            label = data.y[mask]
            
        correct += pred.eq(label).sum().item()
    
    if model.task == 'graph':
        total = len(loader.dataset) 
    else:
        total = 0
        for data in loader.dataset:
            total += torch.sum(data.test_mask).item()
    return correct / total
    
    # model train with Cora dataset
    dataset = Planetoid(root='/tmp/cora', name='cora')
    task = 'node'
    
    model = train(dataset, task)

여느 PyTorch script와 마찬가지로 loader를 통해 dataset을 불러오고, model을 선언하고, optimizer를 선언하고, train 및 test를 진행한다.

학습이 완료된 model을 통해 Cora dataset (citation network)에서의 node classification 결과를 확인해보면 다음과 같은 결과를 얻을 수 있다:

학습된 GNN model을 통해 Cora dataset에서 각 paper(node)가 어느 주제(class)에 속하는지를 분류하였다.

Conclusion

작성하다보니 포스팅이 조금 길어진 듯 하다.

앞선 예시 code를 살펴봐도 알 수 있듯이, PyG는 기존 PyTorch와 거의 완벽하게 호환이 될 정도로 code style이 간편한것이 정말 큰 장점인 듯 하다.

(물론 내부적으로 더 나은 연산을 위해 torch-sparse, torch-scatter와 같은 라이브러리를 별도로 사용하기도 한다.)

전체적인 code style은 기존 PyTorch와 거의 유사하지만, 사용하는 데이터가 graph 데이터 이기에 전 처리 과정 및 model/layer에서 연산 수행을 위한 code style이 조금 다를 뿐이다.

22년, 23년 당시 GNN paper와 공개된 github repo를 잠시 찾아본 적이 있는데, 실제로 새로운 model을 구현한 work 중 PyG를 통해 구현한 경우 위 처럼 MessagePassing을 상속받아 제안한 model/layer를 직접 설계한 모습을 볼 수 있었다.

물론 이렇게 직접 구현할 수 있지만, 라이브러리는 괜히 라이브러리가 아닌 지라 PyG team 에서도 적극적으로 outstanding한 work들의 layer를 직접 구현하여 모듈로 제공하고 있다.

(well-build 된 것이 있다면 역시 그것을 사용하는게...)

그리고 Jure Leskovec 교수님이 강의에서 직접 PyG를 사용하도록 권장(?)하고 있기도 하고, PyG를 개발한 Matthias Fey를 포함한 PyG team들과 함께 kumo라는 벤쳐 기업을 설립하여 그런지,

실제 비즈니스 적 측면에서 PyG를 어떻게 더 효율적으로 최적화하는지에 대한 연구도 함께 진행되고 있다는 점을 23년 Webinar에서 직접 듣기도 한 만큼 DGL과 더불어 유망한 라이브러리로 거듭나고 있는 느낌이 많이 들었다.

만일 GNN을 입문하고자 하는 지인/후배가 있다고 한다면,

나는 물론 실제로 coding이 간편하기도 하고, 무엇보다 양질의 tutorial & video가 정말 잘 제공되는 PyG를 추천할 생각이다.

(그렇다고 DGL은 별로다 라는 것은 아니다 😅 분산 학습과 같이 system 적인 측면에서는 DGL이 아직은 PyG보다 더욱 well-build 되어 있다고 생각하기에...)

E.O.D.

Graph Machine Learning

Graph ML, random walk approach에 관한 글은 이전 포스팅에 기술되어 있다.

Graph Neural Network

random walk를 이용한 접근 방식에도 당연히 문제점이 존재했다.

• embedding 계산을 위해 graph에 존재하는 전체 node 수 만큼의 복잡도를 가진다.
• node마다 가지고 있는 정보(feature, attribute)를 온전히 활용하지 못한다.
• Transductive한 방법이기에 학습하는 과정에서 unseen node에 대한 embedding 계산을 하지 못한다.

따라서 encoding을 수행하는 mapping function $f$를 신경망을 통해 진행하자는 연구가 진행되었고, GNN(Graph Neural Network)의 연구가 진행되었다.

널리 활용되던 CNN/RNN을 graph 데이터에 적용하기가 힘들었는데, 이전 포스팅에서 언급한 바와 같이 graph는 이미지나 텍스트와 같이 grid, sequence 형태로 표현하기가 힘드며, graph를 구성하는 node가 고정된 순서/기준이 존재하지 않아 관점에 따라 다른 모양이 될 수도 있다는 것이 특징이다.

(이러한 특징으로 인해 주어진 두 그래프가 동형인지를 확인하는 Weisfeiler-Leman(WL) test가 있다.)

graph 데이터에 신경망을 활용하기 위한 Naïve한 방법으로 다음과 같은 설계를 해볼 수 있을 것이다.

이전처럼 traditional하게, graph의 구조적인 정보를 담고 있는 인접 행렬(adjacency matrix)과 각 node마다 가지고 있는 특징 정보(feature vector)를 CONCAT한 후, 이를 신경망의 입력으로 전달하는 방법이다.

어찌 보면 graph의 구조적인 정보도 학습할 수 있고, 각 node가 가지고 있는 feature 정보 또한 학습할 수 있을 것이다.

하지만, 당연히 이는 아래와 같은 문제점이 존재한다.

• graph에 존재하는 모든 node를 처리하기 위해 신경망의 입력, 즉 parameter 수가 많아지게 된다.
• graph의 크기가 달라지거나 다른 형태의 graph가 주어진다면 동일한 model을 활용할 수 없게 된다.
• node의 순서가 변경되는 경우에 sensitive해지게 된다.
  (graph의 구조가 변경되거나, 전처리 과정에서 순서가 변경되거나, 일반적인 mini-batch training을 하는 경우 node의 순서가 변경될 수 있다.)

그렇다면 어떻게 graph의 구조에 sensitive하지 않으면서 신경망의 parameter 수를 적절히 handle할 수 있을까?

CNN의 경우를 생각해보자.

이미지가 입력으로 주어졌을 때, CNN은 filter를 이동시키는 일명 sliding window라는 기법을 이용해 이미지 전체에 대한 feature를 학습하게 된다.

주어진 graph가 이미지라고 생각해본다면, CNN에서 사용한 sliding window와 같은 기법을 이용해 graph의 지역적인 구조에 대한 학습을 차근차근 진행할 수 있을 것이다.

하지만 graph는 지역성(locality)에 대한 개념이 애매모호하며, sliding window 기법을 바로 적용하기 힘든 문제가 있다.

위 예시처럼 graph는 그 구조가 아주 다양하며, sliding window를 적용한다 하더라도 매번 달라지는 node의 순서와 그 갯수로 인해 적용이 상당히 어려울 것이다.

Graph Convolutional Network(GCN)

(GCN paper review 포스팅)

기존의 CNN은 filter라는 개념을 이용해 이를 sliding하면서 feature extraction 및 학습을 진행하였다.

즉, 여러 개의 grid로부터 feature를 추출 및 결합하여 한층 더 압축된 feature를 생성하였고, 이를 반복하였다.

이에 intuition을 받아 다음과 같은 접근이 제안되었다.

하나의 node를 기준으로, 인접한 node로부터 정보를 모으는 방식이다. (neighborhood aggregation)

즉, 각 node마다 연결된 이웃 node들의 feature(message)를 추출 및 결합하여 학습을 진행하는 것이다.

이 과정을 그림으로 표현하면 다음과 같이 표현할 수 있다:

신경망을 이용하여, 각 node마다 연결된 모든 이웃 node의 feature를 결합하고 변형을 진행한다.

위 그림에선 node A를 기준으로 연결된 node인 node B, C, D의 feature를 결합 및 변형하고, 각 node B, C, D는 마찬가지로 연결된 node들로부터 feature를 결합 및 변형한다.

즉, 하단 그림처럼 각 node마다 연결된 node들을 이용해 일종의 계산 그래프(computation graph)를 형성하여 node마다 feature를 추출 및 결합하여 학습을 진행하는 방법이다.

(CS224W가 정말 양질의 자료...)

GCN paper review 포스팅에서도 언급했듯이, (어떻게 보면) 이게 전부다.

feature aggregation을 위해 layer(Graph Convolution layer)를 $n$개 적재하여 기준 node로 부터 $n$-hop 이웃 node 까지의 computation graph를 생성 $\rightarrow$ feature aggregation(neighborhood aggregation, message passing) 진행 $\rightarrow$ 기준 node의 feature update, 학습 진행

전체적인 이 과정을 수식으로 표현하면 다음과 같다:

이전 layer, 즉 현재 target node를 기준으로 연결된 모든 이웃 node의 representation/feature를 결합한 후, layer의 weight를 적용한 후 non-linear activation을 취하여 현재 layer(계산/갱신 될 현재 target node)의 representation/feature를 update한다.

정말 이게 전부다 🙂

다시 한번 정리해보면 다음과 같이 정리해볼 수 있을 것이다.

1. 현재 target node를 기준으로 연결된 모든 이웃 node를 탐색
2. 이웃 node들의 representation을 aggregate
3. aggregate 된 이웃 node들의 representation과 target node의 이전 representation을 결합하여 target node의 representation을 update

GCN paper에서는 위 수식과 같은 vector representation이 아닌 matrix representation으로 설명하고 있는데, matrix를 분해하여 계산보면 결국 위 수식과 같은 summation(average)의 연산을 수행하는 것을 알 수 있다.

이전 DeepWalk, node2vec과 같은 random walk 기반의 방법과는 다르게 별도의 전처리 과정 수고가 줄어들게 되었고, 기존의 CNN/RNN과 같은 신경망 처럼 layer를 적재하고 parameter tuing을 수행하여 graph에 대한 representation을 보다 간편하고 쉽게 구할 수 있게 되었다.

(GCN paper review 포스팅 을 보면 기존의 random walk 기반의 방법들에 비해 downstream task의 성능이 훨씬 더 잘 나오는 것을 확인할 수 있다.)

GraphSAGE

(GraphSAGE paper review 포스팅)

GCN은 획기적이면서도 빠르고 간편한 representation을 생성할 수 있는 방법을 제안했다.

하지만 마찬가지로 GCN에도 치명적인 문제가 있었는데, 한 target node를 기준으로 연결된 모든 이웃 node의 feature aggregation을 진행하는 것이다.

어찌 보면 feature aggregation을 위해서라면 당연히 필요한 과정이지만, 이는 large graph에서 scalable하지 못하기가 쉽다.

(계산 복잡도가 지수적으로 증가하는 문제)

그러하여 GraphSAGE는 GCN을 변형하여 large graph에서도 동작할 수 있는 방법을 제시하였고, (결과적으로 보면) GCN에 비해 좋은 성능을 달성할 수 있음을 보여주었다.

GraphSAGE의 연산 과정을 수식으로 보면 다음과 같다:

GCN과 차이점이 뭘까?

선택된(sampling 된) 이웃 node들의 representation을 aggregate 한 후에($\mathrm{AGG}$), target node의 representation과 CONCAT하여 non-linear activation을 거쳐 현재 layer(계산/갱신 될 현재 target node)의 representation/feature를 update한다.

$\mathrm{AGG}(\cdot)$으로는 GCN과 같은 MEAN을 사용할 수도 있고, paper에선 permutation invariant한 pooling 또는 LSTM을 사용할 수 있음을 소개하였다.

또 다른 핵심은 앞서 언급한 "선택된(sampling 된) 이웃 node들" 인데, 단순히 target node와 연결된 모든 이웃 node가 아닌 그 중 일부분만을 random하게 sample하여 aggregation에 활용한다는 것이다.(neighborhood sampling/node-wise sampling)

(sampling 관련 부분은 GraphSAGE paper review 포스팅에 좀 더 상세하게 기재되어 있다.)

Graph Attention Network (GAT)

GCN의 한계점을 해결하기 위해 GraphSAGE가 등장하였었다.

하지만 GCN, GraphSAGE에도 문제점이 있다.

바로 "각 node의 중요도"를 충분히 고려하지 않았다는 점이다.

앞서 기술한 수식들만 봐도 단순히 이웃 node들의 representation을 모아 평균(mean)을 취하고 있는데, GAT에서는 이 문제점을 지적한 것이다.

(실제 SNS만 보아도 각 사용자의 영향력, 즉 node마다 가지고 있는 고유한 중요도가 다를 수 있다.)

따라서 GAT에서는 (당시 화제가 되었던) attention mechanism을 이용해 각 node마다의 중요도를 다르게 계산하여, feature aggregation을 수행할 때 그 중요도를 각기 다르게 부여해 representation을 보다 더 정교하게 다듬을 수 있는 방법을 제안하였다.

(attention mechanism에 대한 설명은 정말 잘 정리되어 있는 문서가 있기에 그것으로 대체하고자 한다.)

수식을 보면 다음과 같다.

단순히 각 node마다의 중요도를 다르게 두기 위한 attention weight가 추가되었는데, 이 attention weight를 보면 다음과 같다.

attention mechanism에서 계산하는 attention weight의 계산과 거의 동일하다.

말 그대로 node 간의 중요도를 계산하여 그 중요도에 따라 representation 계산에 차등을 주어야 한다 라는 접근이다.

기존의 attention 처럼 multi-head attention을 수행할 수 도 있는데, 이는 위의 attention 연산을 head의 수 만큼을 진행하여 각기 다른 attention weight를 계산하여 각 head에서의 reprsentation을 계산한 후, 이를 CONCAT하여 최종 representation을 계산하는 것이다.

GAT paper를 보면 실제로 기존 방법들에 비해 우수한 성능을 보여준 것을 알 수 있다.

하지만 attention 연산이 들어간 시점에서, (attention 연산을 수행하는 거의 모든 architecture와 마찬가지로) 연산에 있어 상당한 complexity가 있다는 점을 짐작할 수 있다.

(이는 추후 포스팅 할 paper에서도 자주 언급되는 문제이다.)

Conclusion

Graph representation learning을 알기에 앞서 기존의 representation learning이 무엇인지, 어떻게 발전되었는지 간략하게 짚어보았고, graph domain에서 representation learning이 어떻게 이루어지는지를 간략하게 정리하였다.

기존엔 random walk 기반의 representation learning이 주 를 이루었지만 그 한계점이 존재하였고, 이를 해결하기 위해 신경망(GNN)을 활용하는 방법이 제안되고 발전됨에 따라 graph domain에서의 representation learning은 (아마도 거의) GNN을 통해 이루어진다고도 볼 수 있다.

실제로 graph domain의 대표격이라 볼 수 있는 생물/화학 분야(molecule, PPI 등)에서 GNN/GT(Graph Transformer)와 같은 신경망 기반(deep-learning based)의 방법이 주를 이루고 있음을 알 수 있다.

다시 한번 일반적인 GNN의 연산 과정을 살펴보면 다음과 같이 정리할 수 있을 것이다:

• 인접 행렬(adjacency matrix)을 이용해 target node에서 (sampling 된 or 모든) 연결된 이웃 node를 탐색
• 이웃 node의 representation을 집계 (neighborhood aggredation/message passing)
• 현재 target node의 representation과 집계된 이웃 node의 representation을 결합
• layer의 weight와 non-linear activation을 거쳐 target node의 새로운 representation을 계산

추가적으로, GNN을 공부하던 시절 도움이 되었던 자료를 함께 첨부하였다:

Stanford CS224W: Machine Learning with Graphs (개인적으로 강추하는 자료)

PyTorch Geometric(PyG) Tutorial (DGL보다는 조금 늦게 개발되었지만 기존 PyTorch와 거의 동일하게 간편한 PyG 라이브러리에서 제공하는 튜토리얼 영상/자료)

Graph Representation Learning textbook (GraphSAGE 저자가 발간한 pdf)

CS224W 정리본 (wandb에서 작성)

꼭 한번 다시 정리해야지 하는 내용을 간략하게나마(?) 정리하였다.

(이전 포스팅과 마찬가지로 어디까지나 개인적으로 아카이빙, 정리 용으로 작성한 글 이기에 다소 오류/문제점이 있을 수 있습니다. 언제든지 지적해주시면 감사하겠습니다.)

GNN을 처음 접하고 공부하던 시절엔 인터넷에 자료가 그렇기 많지 않았고, PyG 또한 개발이 막 시작되던 때라 자료를 검색하면 십중팔구 외국 자료가 많이 나왔었기에 당시에 많은 도움을 받았던 자료들을 함께 첨부했다.

포스팅을 작성하고 있는 지금 다시 검색해보면 한글로 된 여러 자료가 많이 나오는데, 그 몇 년 사이에 국내에서도 GNN에 조금이나마(?) 붐이 오긴 왔었던 듯 하다.

시간이 지나면서 조금 흥미로웠던 점은 학계에서는 PyG를 많이 선호하는 듯 하고, 산업에서는 DGL을 많이 선호하는 듯 하다는 것이다.

(아무래도 Jure 교수님이 거의 대놓고 PyG를 support하기도 하고, Amazon에서 DGL을 support하기도 하고...)

예전 GNN 관련 프로젝트를 진행하기에 앞서 프로젝트에 참가하는 분들에게 간략하게 소개하였던 자료도 함께 첨부하였다.

E.O.D.

Preliminaries

머신 러닝, 딥 러닝에 발을 담궈보면 언제나 나오는 representation learning.

학부 시절 수업을 들었을 때나, 유튜브에 공개된 외국 강의 자료들을 봐도 항상 등장한다.

단어 뜻만 보면 "표현 학습" 인데, 공부를 막 시작하다 보면 이게 도대체 무슨 의미인가 하고 쉬이 넘어가기가 쉬웠다.

머신 러닝, 딥 러닝 관련 자료를 보면 위와 같은 그림이 자주 등장한다.

CNN의 hidden layer가 주어진 이미지의 feature를 위 그림처럼 학습해서 최종적으로 분류와 같은 downstream task를 수행할 수 있다는 설명을 하는데, 그런가보다~ 하고 넘어가기가 쉽다.

도대체 자주 언급되고 등장하는 feature, representation이 뭘까?

Representation Learning

wikipedia를 보면 다음과 같이 소개하고 있다.

특징 학습(feature learning) 또는 표현 학습(representation learning)은 특징을 자동으로 추출할 수 있도록 학습하는 과정이다.

그래서 이 특징, 표현이 뭘까?

이를 설명하기 위해 많이들 드는 예시로 강아지, 고양이 등 동물의 분류가 있다.

우리(사람)는 동물을 보면 "아 이건 무슨 동물이다" 라는 걸 (어느 정도) 알 수 있다.

위 예시에서 고양이는 "뾰족한 귀", "입과 코 주변의 수염", "털 위의 무늬", "큰 눈동자" 등 으로 유추해볼 수 있고, 강아지는 "접혀진 귀", "상대적으로 작은 눈동자", "커다란 코" 등 으로 유추해볼 수 있으며, 햄스터는 "동그란 외형", "작은 눈동자", "작은 코", "작은 입", "몸에 비해 짧은 팔과 다리", "동그랗게 세워져 있는 귀" 등 으로 유추해볼 수 있을 것이다.

이처럼 우리는 어린 시절 부터 보고 접해온 동물들의 여러 특징들을 종합하여 "이 동물은 강아지/고양이/햄스터 구나" 라는 결론을 내릴 수 있다.

하지만 사람에게도 한계는 존재한다.

100억 장의 동물 사진들을 가지고 이 동물들을 완벽하게 분류해보라 하면 시간도 상당히 오래 걸리고, 에너지가 부족하면 실수가 잦아지기 마련이다.

그래서 컴퓨터를 이용해 이러한 단순하면서도 반복적으로 수행할 수 있는 작업을 해결하고자 하는 시도가 많았다.

(대표적인 예시로 사람의 손 글씨를 분류하고자 하는 연구가 있다: Gradient-based learning applied to document recognition, Y. Lecun et al., 1998)

하지만 사람과는 다르게 컴퓨터는 눈이 있는 것도 아니고, 단순히 전기 신호인 0, 1의 이진수를 통해 작업을 수행한다.

숫자를 통한 단순 계산은 사람을 능가하는 수준의 정확도와 속도를 보여주지만, 실제 세계에서 우리가 접하는 여러가지 물체/개체들은 복잡한 특징을 가지고 있어 숫자로 표현하는 것이 힘들기 마련이다.

컴퓨터가 사람처럼 특정 물체/개체를 어떻게 인식하게 할 수 있을까? 에서 시작된 것이 바로 representation learning의 기원이라고 생각한다.

즉 "데이터를 잘 설명할 수 있는 특징(feature, representation)을 생성하고, 컴퓨터가 이 특징을 학습하여 주어진 데이터들에 대한 여러 작업을 처리할 수 있게 하자!" 정도 로 생각할 수 있을 것이다.

representation learning이 무엇인가에 대한 내용을 계속 기술하자니 서두가 너무 길어지는 것 같아, 잘 정리되어 있는 medium 포스팅으로 대신하고자 한다:

https://medium.com/@hugmanskj/%ED%91%9C%ED%98%84%ED%95%99%EC%8A%B5-representation-learning-%EA%B0%9C%EC%9A%94-ea8d6252ea83

(어떻게 보면 사람도 방대한 양의 데이터를 통해 여러 물체/개체의 representation을 학습한 것으로도 볼 수 있지 않을까?)

Embedding

앞서 언급한 듯이, 사람과는 다르게 컴퓨터는 숫자를 통해 작업을 수행한다.

즉, 컴퓨터를 통한 연산을 수행하기 위해선 우리가 알고 있는 물체/개체와 같은 데이터를 숫자로 표현해야 하는 작업이 필요하다.

이미지는 RGB 값, 오디오는 주파수 값 과 같은 수치들을 이용해 숫자로 표현할 수 있지만, 현재 작성하고 있는 이러한 글자(텍스트) 들은 어떻게 숫자로 표현할 수 있을까?

단순하게 생각해보면 하나의 단어, 하나의 글자 마다 고유한 숫자를 대입하여 해당하는 단어/글자를 표현할 수 있는 특징, 즉 feature vector를 구성할 수 있을 것이다. (Integer Encoding)

하지만 단어/글자는 동일한 외형이지만 그 뜻이 다른 경우도 빈번하며, "다섯"처럼 그 자체에 숫자/순서의 개념을 내포하고 있는 경우가 있어 자칫하다간 의도한 것 과는 다른 결과를 초래할 수도 있다.

이러한 문제를 다루고자 아예 컴퓨터가 이해할 수 있는 0과 1만을 이용해 단어/글자를 표현하는 방법이 있다.

예를 들어 "강아지" 라는 글자를 $(0, 1)$, "고양이" 라는 글자를 $(1, 0)$과 같은 vector표현할 수 있을 것이다. (One-hot Encoding)

하지만 이런 표현 방법도 제한점이 존재한다.

"햄스터" 라는 글자를 $(1, 1)$, "원숭이"라는 글자를 $(0, 0)$으로 표현했다고 생각해보자.

그렇다면 "돌고래", "개구리"와 같은 글자는 어떻게 표현할 수 있을까?

앞서 표현한 $(0, 1)$과 같은 차원이 2인 vector로 표현하기엔 부족하며, 결국 표현하고자 하는 숫자를 더 늘려(vector의 차원을 확장) "돌고래"라는 글자는 $(1, 0, 0)$, "개구리"라는 글자는 $(1, 0, 1)$ 로 표현할 수 밖에 없을 것이다.

이처럼 0과 1만을 이용한 표현법은 다루어야 하는 글자의 수가 많아짐에 따라 0과 1의 수를 늘려서 표현해야 하는 문제가 발생한다.

즉, 글자의 수가 많아짐에 따라 vector의 차원도 늘어나는 것도 문제이지만, 데이터를 표현하는 숫자가 0과 1로만 이루어져 있게 되어 불필요한 저장 공간 낭비가 될 수 있다.

극단적으로 보면 100,000차원 vector가 99,999개의 0, 1개의 1로 구성되어 있는 상태가 될 수 있다. (Sparse vector)

이렇게 되면 컴퓨터 저장 공간의 낭비가 심해질 뿐 더러, 글자 그 자체의 특징을 표현해주기엔 역부족해질 수 있는 문제가 존재한다.

(그리고 vector의 차원이 늘어나고 sparse해짐에 따라 두 vector 간의 similarity를 계산하는 작업이 상당히 비효율적이게 되기 쉽다)

그래서 아예 "0과 1뿐만이 아닌, 모든 숫자와 소수점을 이용하여 정해진 크기의 vector로 표현하자"라는 접근이 나타난다.

이것이 Embedding 이다.

앞서 언급한 예시로 보면 "강아지"를 $(0, 1)$이 아닌 $(0.23, 0.98)$, "고양이"를 $(0.96, 0.38)$와 같이 고정된 크기를 가진 실수 vector로 표현하는 것이다. (Embedding vector)

Embedding을 생성하는 방법엔 여러 방법이 존재하는데, 그 중 2013년 Google에서 발표한 Word2Vec 기법이 가장 유명하고 대중적이다.

Word2Vec에 대한 설명은 학부 시절 개별적으로 공부를 할 때 참고한 아주 양질의 자료가 있기에, 대체하고자 한다: 링크

(사실 word2vec 말고도 머신 러닝, 딥 러닝에 대한 전반적인 개요가 정말 깔끔하고 친절하게 잘 기술되어 있다 🙂)

간단하게 설명하자면 신경망을 이용해 주어진 단어를 실수 vector로 표현하여 주어진 단어의 representation vector/feature vector/embedding vector를 생성하는 기법이며, 생성된 vector를 이용해 downstream task를 수행할 수 있는 것이다.

Graph Machine Learning

이처럼 실 세계의 데이터를 이용한 복잡한 문제를 해결하고자 컴퓨터를 활용하기 시작하였고, 해당 데이터들을 컴퓨터가 연산에 활용할 수 있도록 적절한 형식(vector)으로 변환하여 컴퓨터에 전달해주었다.

(이미지는 RGB, 오디오는 주파수, 텍스트는 word embedding, ...)

앞서 언급했던 이미지/텍스트 를 위한 머신 러닝, 딥 러닝 작업을 위해선 흔히 아래와 같은 lifecycle을 따른다고 볼 수 있다.

실제 데이터(Raw Data)를 적절히 가공하여 컴퓨터가 활용할 수 있도록 적절한 vector로 변환(Feature Engineering)한 후, 컴퓨터를 이용해 작업을 수행한다(Learning Algorithm, Model, ...).

실 세계에는 이미지, 오디오, 텍스트와 같은 데이터 이외에도 사람 간의 복잡한 관계, 분자 구조를 구성하는 원소 간의 관계, 회사나 기관의 조직도와 같이 graph 형태로 표현되는 데이터 또한 존재한다.

그렇다면 이러한 graph 형태의 데이터로부터 feature/representation을 어떻게 추출 할까?

graph 형태의 데이터는 앞서 언급하였던 데이터들과는 성격이 상당히 다른 것이 특징이다.

graph를 구성하는 요소인 node라는 것이 있고, 각 node 끼리 edge를 통해 연결되어 있고, edge마다 그 종류가 다르고 특성이 다를 수 있으며, 심지어 edge에 방향성이 존재하기도 한다.

이처럼 graph 그 자체는 구조적인 특징을 가지고 있으며, 심지어는 구성 요소 간의 관계정보 까지 포함하고 있는 복잡한 형태의 데이터이다.

이렇게 복잡한 데이터를 비교적 잘 표현할 수 있는 representation을 생성하는 것은 많은 시간이 필요할 것이고, 많은 연산이 필요로 할 것이다.

따라서 앞서 언급했던 embedding 기법(접근법)이 graph 데이터에도 적용되기 시작하였다.

단순히 보면 별도의 번거로운 feature engineering 과정을 거치지 않고 graph에 존재하는 node(또는 edge)들의 특징을 잘 간직하는 정해진 크기의 vector로 바로 변환하자는 접근이다.

(latent space(정해진 크기의 차원/vector)로 node/edge를 project/mapping하여 해당 node/edge에 대한 representation vector를 얻어보자는 접근)

이게 무슨 소리일까?

주어진 graph의 node $u$ 대해, 이를 $\mathbb{R}^d$ 차원으로 project/mapping하는 함수 $f$ ($f: u \rightarrow \mathbb{R}^d$)를 이용해 representation vector를 생성하자는 의미로 생각할 수 있다.

즉 graph representation learning의 기본 아이디어는 저 차원의 vector 공간(latent space)으로 graph를 project/mapping하여 representation을 생성하는 것이고, 이 representation이 잘 생성될 수 있도록(graph의 구조적인 정보를 온전히 내포할 수 있도록) 저 차원 vector 공간으로 project/mapping하는 함수 $f: u \rightarrow \mathbb{R}^d$를 적절하게 조절/학습한다는 것으로 볼 수 있다.

(node/edge를 적절하게 encoding 하여, embedding spacce에 적절히 project/mapping)

(다시 봐도 CS224W 강의가 진짜 양질의 강의인 듯 하다)

graph representation learning의 목표는 위와  같이 node $u$, $v$의 embedding으로 표현된 vector $\mathbf{z}_u$, $ \mathbf{z} _v$의 유사도가 실제 node 간의 유사도에 근접해지도록 하는 것이다.

즉, 실제 graph에서 유사도가 높은 두 node라면 latent space에서도 유사도가 높을 것이다 라는 점을 전제 하에 두고 mapping function $f$를 최적화 하는 것으로 볼 수 있다.

Random Walk Approach

graph representation learning에서 embedding을 생성하기 위한 대표적인 접근법이다.

random walk는 node들에 대한 sequence 데이터로, 하나의 기준점 node에서 시작해 정해진 길이 만큼 walk를 진행하여 sequence를 생성한 것이다. (한 node에서 시작해 정해진 길이 만큼 갔을 때 생성되는 발자국 으로 생각할 수도 있다)

두 node간의 유사도를 random walk sequence에서 동시에 발생할 확률로 정의하는데, 즉 node들이 graph의 짧은 random walk에서 동시에 존재하는 경향이 보인다면, 해당 node들이 비슷한 embedding을 갖도록 encoding하는 것이다.

대표적인 random walk 기반의 방법으로 DeepWalk, node2vec 이라는 방법이 있다.

간단히 보면 DeepWalk는 random walk를 생성하여 Word2Vec의 방법을 활용하는 방법이고, node2vec은 random walk를 어떻게 진행할 것인지를 다르게 설정하여 graph의 local/global 적인 representation을 잘 표현할 수 있는 방법이다.

두 방법을 작성하기엔 글이 너무 길어질 듯 하기도 하고, CS224W를 들으며 공부하던 시절 참고했던 블로그 포스팅/자료로 대체하고자 한다: 블로그 포스팅, GraphSAGE 저자가 작성한 book(Chapter 3.3)

(양질의 자료가 있다면 적극 활용하는 것이 옳다고 생각하기에...😅)

다짜고짜 graph domain으로 넘어가기 보단, 그래도 역시 representation learning이 무엇인가 라는 걸 먼저 다시 한번 짚고 가야한다는 생각을 했기에 representation learning에 대한 내용도 기술하게 되었다.

representation learning을 어떻게 풀어서 기술할 수 있을까 천천히 생각하며 작성하다 보니 해당 부분의 내용이 좀 길어진 듯 하다.

(어디까지나 개인적으로 아카이빙, 정리 용으로 작성한 글 이기에 다소 오류/문제점이 있을 수 있습니다.)

그래서 Graph Neural Network에 대한 부분은 아예 다음 포스팅에서 기술하고자 한다.

E.O.D.

GCN 논문을 review하고 난 후 이어서 바로 deep-dive를 했던 논문.

소개된 모델의 이름에 SAGE(현자)가 들어가있어서 좀 신기하기도 하고 피식했던 기억이 난다.

GCN과 마찬가지로 원본 코드가 tensorflow v1으로 작성되었던 터라 코드 분석과 실행에 다소 애를 먹었지만, 그래도 개인적으론 (appendix 부분을 제외하고) GCN에 비해 수학적 background가 많이 요구되었던 것 같지는 않았다.

논문에서 계속 GCN을 언급하면서 GCN을 확장했다, GCN보다 성능이 잘 나온다 라는 말이 나오는데, GCN paper review는 이전 포스팅에서 확인할 수 있다.

Published in NIPS(NeurIPS)2017

• paper
• official source code repo (tensorflow v1)
• commented source code repo (tensorflow v1)

Transductive한 방법으로 접근한 이전 연구들과는 다르게 Inductive한 방법으로 접근하는 방법을 소개.
지역적인 이웃(local neighborhood)들의 feature를 적절하게 sample & aggregate하여 node embedding을 생성하는 함수를 학습하는 방법을 소개.

random neighborhood sampling을 활용한 mini-batch training 방법을 소개.

Introduction

node2vec, DeepWalk, LINE과 같은 이전 representation learning 방법들은 large graph의 node를 low-dimensional embedding vector로 변환하여 여러 downstream task를 위한 입력을 준비하는데 사용되었다.

여기서의 핵심인 node embedding은 기본적으로 차원 축소(dimensionality reduction technique), 즉 high-dimensional인 node의 이웃 정보를 low-dimensional인 dense embedding vector로 압축하는 것.이를 통해 여러 downstream task(node classification, clustering, link prediction)을 수행할 수 있다.

(거의 모든 representation learning이 그렇듯이, 고 차원으로 표현된 데이터를 저 차원으로 변환/압축하여 downstream task를 위한 준비를 할 수 있다.)

이러한 작업은 고정된 graph에서 embedding을 생성하는 것에 초점을 맞추고 있지만, 실 세계 application들은 관측되지 않은(unseen) node에 대해 embedding을 빠르게 계산하는 작업이 필요하다.

즉, 이런 inductive한 능력은 변화(진화/성장)하는 graph에서 동작하거나 지속적으로 unseen node를 마주치게 되는 ML system에선 필수적이며, node embedding을 생성하는 inductive한 접근법은 graph 간의 generalization이 보다 간편해질 수 있다.

즉, 단백질-단백질 상호작용(protein-protein interaction, PPI) graph에 대한 embedding generator를 train한 후, trained model을 활용하여 새로운 PPI graph에 대한 node embedding을 손쉽게 생성할 수 있다.

(Inductive method가 왜 필요한지에 대한 설명. model을 먼저 train 한 뒤, 다른 data에 대해 빠르게 embedding을 생성할 수 있다.)

그렇다면 왜 Inductive method가 transductive method보다 어려울까?

관측되지 않은(unseen) node를 일반화(generalize)하는데 있어, 설계한 알고리즘이 이미 최적화가 진행된 node embedding에 sub-graph를 할당하기 때문이다.

즉, node의 local role과 global position을 모두 나타내는 structural property를 인식하는 방법을 학습해야 한다.

(node embedding을 생성함에 있어 해당 node가 global한 관점에서 어떤 역할을 담당하는지, local한 관점에서 어떤 역할을 담당하는지를 고려해 적절한 embedding을 생성하는 것이 필요. node2vec에서 return parameter에 따라 local에 초점을 맞춰 embedding을 생성할지, global에 초점을 맞춰 embedding을 생성할지를 결정하는게 필요하다는 점에서 기인한 듯 하다.)

node embedding을 생성하는 작업은 선천적으로 transductive한 작업인데, 이는 matrix factorization 기반의 목적 함수를 사용해 각 node마다 embedding을 직접적으로 최적화 한다.

하지만 이 방법은 single/fixed graph의 node에 대해 prediction을 수행하므로 unseen data의 일반화를 잘 하지 못하는 문제가 있다.

DeepWalk에서 소개한 방법 처럼 inductive한 작업으로 변환할 수 있지만, 새로운 예측을 수행하기 전 추가적인 gradient descent 단계가 필요하기에 이는 굉장히 computationally expensive한 작업이 된다.

GCN처럼 convolution 연산을 이용해 graph의 구조를 학습하는 접근 법도 있지만, GCN은 fixed graph를 사용하는 transductive method에서만 사용되고 있다.

따라서 본 논문에서는 GCN을 inductive unsupervised learning으로 확장하고, GCN의 접근 방식을 일반화하여 trainable한 aggregate function을 사용하는 framework를 제안한다.

Present work

Inductive node embedding을 위한 general framework인 GraphSAGE(SAmple and aggreGatE)를 소개한다.

unseen node를 일반화하기 위한 embedding function을 학습하기 위해 node feature를 활용하며, 학습 알고리즘에 node feature를 활용함으로써 각 node마다 이웃의 topological structure 뿐만이 아닌 이웃 node에 존재하는 node feature의 분포 또한 학습이 가능하다.

또한 각 node마다 구별되는 embedding vector를 학습하는 대신, node의 local 이웃에서 feature 정보를 집계하는 aggregator function을 학습하며, 이 함수는 주어진 node로부터 몇 hop(depth)까지의 정보를 집계한다.

(aggregator function을 통해 한 node로 부터 $k$ 거리 만큼 떨어진 node의 정보를 활용. $k$ 거리 == $k$-hop)

test(inference)시엔 학습된 aggregator function을 활용해 unseen node 전체에 대한 embedding을 생성할 수 있다.

(즉 aggregator function이 정해진 hop 수 만큼까지의 node 정보를 집계하여 model train을 하고, trained model(aggregator function)을 이용해 unseen data에 대한 embedding을 간단하게 생성할 수 있다는 의미이다.)

Citation network, Reddit, PPI 총 3개의 dataset을 이용했을 때 기존 GCN의 단순한 aggregate 방식 보단 본 논문에서 제안한 여러 종류의 aggregator function이 embedding 생성에 있어 월등한 성능을 보여준다.

Related Work

(언제나 보는 선행연구 소개 & 우리 paper가 이래서 더 좋다~ 하는 내용들)

Factorization-based embedding approaches

random walk approach와 matrix-factorization 기반의 목적 함수를 이용해 low-dimensional embedding을 학습하는 연구가 존재한다.

이 방법들은 전통적인 spectral clustering, multi-dimensional scaling, PageRank와 유사하며, 각 node마다 직접적으로 node embedding을 학습하기에 기본적으로 transductive한 방법이고, 새로운 node에 대한 예측을 생성하기 위해 추가적인 training이 필요하다.

또한 이 방법들은 목적 함수가 embedding의 orthogonal transformation(직교 변환)에 대해 불변(invariant)한데, 이는 즉 embedding space가 graph마다의 embedding space를 자연스럽게 일반화하지 못함을 의미하며 re-train 동안 embedding space가 변경될 수 있다.

(train 마다 embedding space가 변할 수 있음을 이야기하는 듯 하다.)

Planetoid-I 알고리즘은 inductive & semi-supervised learning의 embedding 기반 접근법이지만, inference를 하는 동안 graph의 구조적인 정보(structural information)을 활용하지 않는다.

앞서 언급한 접근 방식들과는 다르게, 본 논문에서는 unseen node에 대한 embedding을 생성할 수 있도록 model train에 있어 feature information을 사용한다.

Supervised-learning over graphs

graph data의 supervised learning에 대한 여러 연구가 존재하며, 대표적으로 kernel-based 접근이 포함된다.

(graph의 feature vector가 다양한 graph kernel에서 부터 생성된다는 의미.)

WL graph kernel에 관한 내용은 다른 블로그 포스팅을 참고하면 좋을 듯 하다:

블로그 포스팅

블로그 포스팅

이 외에도 neural network를 활용한 접근 방안(최초의 GNN(2009), Recurrent-GNN 등)도 있었고, 본 연구는 해당 몇몇 알고리즘들에 영감을 받았다.

하지만 선행된 연구들은 graph(또는 sub-graph) classification에 초점을 두었고, 본 연구는 node 개별마다의 representation을 생성하는 것에 초점을 둔다.

Graph convolutional networks

CNN 구조를 사용하는 이 방법들은 large graph로 확장되지 않거나, graph classification (또는 둘 다)를 위해 설계되었다.

본 연구는 기본적으로 GCN에 기반하지만, GCN은 train 동안 full graph Laplacian을 알고 있어야 하는 문제가 있다.

(각 node마다 연결된 모든 node의 feature를 aggregate할 때 어느 node가 어느 node와 연결되었는지에 대한 연결 정보를 알고 있어야하므로.)

따라서 본 연구가 GCN을 inductive한 방법으로 확장한 것으로도 생각할 수 있다.

Proposed method: GraphSAGE

Embedding Generation (i.e. forward propagation) algorithm

입력: 전체 graph $\mathcal{G}$, 모든 node의 feature vector인 $\mathrm{x}_v$, 미분 가능한 집계 함수
$\mathrm{AGGREGATE_k}$, 이웃 함수 $\mathcal{N}$
출력: 모든 node에 대한 vector representation $\mathrm{z_v}$

line 1: 초기 representation 초기화
line 2~8: 탐색 깊이 $k$ ($k$-hop) 만큼 loop
 line 3~6: 모든 node마다 loop
  line 4: 현재 layer의 이웃 node들의 정보는 이전 layer에서 존재했던 이웃 node들의 정보를 집계 (이웃 representation 집계)
  line 5: 현재 layer의 자기 자신 node의 정보는 이전 layer에서 존재했던 자신의 정보 & 현재 layer에서 앞서 계산한 이웃 node들의 정보를 집계 (이전 layer에서 계산된 자신의 representation & 현재 layer에서 계산된 이웃의 representation을 이용해 현재 layer에서의 자기 자신의 representation을 계산)
 line 7: L2 normalization

model이 이미 train 되었다 가정하고, model의 parameter는 고정된 상태임을 가정한다.

$K$개의 집계 함수($\mathrm{AGGREGATE}$)는 이웃 node들로부터 정보를 집계하며, 가중치 행렬인 $\mathbf{W}$는 다른 layer(또는 다른 search depth)간 정보를 전파하는 역할을 수행한다.

각 iteration(각기 다른 search depth, hop) 마다 이웃 node의 정보를 집계, 이 과정을 반복, 반복하며 점점 더 많은 이웃 node들의 정보를 집계한다.

핵심을 살펴보면...

line 4: 각 node $v$는 근처 이웃 node의 representation을 단일 vector $\mathrm{h}^{k-1}_{\mathcal{N}_(v)}$로 집계한다.

이 과정은 이전 loop에서 생성된 representation에 의해 생성되며, $k=0$은 입력으로 전달된 초기 node feature를 의미한다.

line 5: 현재 자기 자신의 representation인 $\mathrm{h}^{k-1}_{v}$와 집계된 이웃 node들의 representation인  $\mathrm{h}^{k-1}_{\mathcal{N}_(v)}$을 CONCAT한다.

CONCAT한 vector를 non-linear activation function $\sigma$를 가진 fully-connected layer(FFN)로 전달한 후, 전달된 정보는 다음 step에서 사용될 representation이 된다.

놀랍게도 이게 전부다.

정해진 hop 수 $k$까지 각 node마다 이웃 node의 representation을 aggregate $\rightarrow$ 이전에 계산된 자신의 representation과 aggregate한 이웃 node의 representation을 CONCAT $\rightarrow$ 현재 자신의 representation을 계산

Relation to the Weisfeiler-Lehman Isomorphism Test

GraphSAGE는 기본적으로 graph 동형 테스트에 사용되는 classical한 알고리즘인 WL-test에 영감을 받았다.

위 Algorithm 1에서 다음의 가정을 한다면, 해당 알고리즘은 전형적인 WL-test의 예시가 된다.

1. $K = |\mathcal{V}|$: 탐색 깊이를 node 수와 동일하게 설정.
2. $\mathbf{W} = \mathbf{I}$: 가중치 행렬을 항등(Identity) 행렬로 설정.
3. non-linearity를 가지지 않은 적절한 hash function을 aggregator로 설정.

(WL kernel/WL-test는 상단 Supervised-learning over graphs 문단에서 hyperlink로 설정한 블로그 포스팅 참고)

서로 다른 2개의 sub-graph에서 생성된 representation set $\mathrm{z}_v$가 동일하다면, WL-test에 따라 이 2개의 sub-graph는 isomorphic하다.

(즉 2개의 sub-graph에서 생성된 representation이 동일하다면 2개의 sub-graph는 동형사상.)

GraphSAGE는 WL-test의 continuous approximation으로, hash function을 trainable한 neural network aggregator로 대체한 셈이다.

Neighborhood definition

고정된 크기의 batch에서 계산 공간(computational footprint)을 유지하기 위해, 전체 이웃이 아닌 고정된 크기의 이웃 집합을 uniform하게 sample 한다.

$\mathcal{N}_(v)$는 고정된 크기의 집합인 {$u \in \mathcal{V} : (u, v) \in \mathcal{E}$} 로 부터 uniform하게 생성된 집합이며, Algorithm 1에서 각 $k$번째 iteration마다 서로 다른 sample을 수집한다.

실험적으로 보았을 때, $K=2$, $S_1 \cdot S_2 \leq 500$일때 최상의 성능을 보여주었다.

(즉 2-hop에 걸쳐 representation 계산을 위해 aggregate하는 이웃 node의 수가 총 500개 이하일 때 성능이 좋았다 라는 의미. (e.g. 1-hop에서 50개의 node를 sample($S_1 = 50$), 2-hop에서 10개의 node를 sample ($S_2 = 10$)))

논문 Appendix 부분에 sampling을 활용한 mimibatch training의 pseudocode가 같이 기술되어 있다.

Appendices A: Minibatch pseudocode (일부)

더보기

 

line 2~7: sampling 수행

line 9~15: forward propagation

 

앞서 소개되었던 Algorithm 1 부분에 sampling을 수행하는 과정이 추가되었다.

 

단순히 주어진 graph에서 node마다 정해진 hop 수 $k$만큼 까지 연결된 이웃 node들을 random하게 sampling 해서 batch를 생성한다. (forward propagation은 기존과 동일)

 

 

구현된 코드를 보면 random_shuffle 하여 num_samples 만큼 slice하며, graphsage/models.py에서 SampleAndAggregate class 내부의 sample 함수 부분을 보면 위 sampler를 활용한 sampling이 수행됨을 확인할 수 있다.

 

Learning the parameters of GraphSAGE

output representation $\mathrm{z}_u$에 대해 graph-based loss function을 사용하며, SGD를 이용해 가중치 행렬 $\mathbf{W}$와 aggregator function의 parameter tuning을 진행한다:

식1과 같은 CE-like loss function은 인접한 node는 유사한 representation을 갖도록 하고, 이질적인 node (feature가 극히 다른 node)의 representation은 최대한 구별되도록 하는 역할을 수행한다.

즉 $\log (\sigma(\mathrm{z}^{\top}_{u} \mathrm{z}_{v}))$ 부분이 1에 가까워지도록(비슷한 node는 비슷한 representation을 갖도록), $\log (\sigma(- \mathrm{z}^{\top}_{u} \mathrm{z}_{v}))$ 부분이 0에 가까워지도록(이질적인 node는 representation이 최대한 달라지도록) 목적 함수를 설정한다.

Aggregator Architectures

기존 N-D lattices(e.g. 이미지, 문장 등...)들을 이용해 train하는 ML과는 달리 node의 이웃들은 자연적인 순서가 없으므로, 따라서 aggregator function은 순서가 없는 모든 vector 집합에 대해 동작해야 한다.

즉, 이상적인 aggregator function은 trainable하고, 높은 representational capacity를 유지하면서 symmetric(입력의 순서가 바뀌어도 결과가 불변, invariant to permutation of its inputs)이어야 한다.

Mean Aggregator

단순히 $\mathrm{h}^{k-1}_{\mathcal{N}_(u)}, \forall u \in \mathcal{N}_(v)$에 있는 모든 vector들에 대해 element-wise mean을 계산하는 방법으로, 기존 transductive GCN의 convolutional propagation rule과 동일하다.

위의 식2를 Algorithm1의 line 4,5에 대입함으로써 inductive한 GCN 연산을 구현할 수 있다.

(기존의 GCN은 Algorithm1의 line 5에 해당하는 CONCAT 연산이 없음)

LSTM Aggregator

LSTM 구조에 기반한 aggregator로서, mean aggregator에 비해 더욱 큰 표현력(larger expressive capability)를 가질 수 있다.

하지만 기본적으로 LSTM은 입력을 순차적으로 처리하기 때문에 not symmetric (not permutation invariant)한데, 본 연구에서는 LSTM을 이웃 node들의 random permutation에 적용하여 unordered set에서 동작할 수 있도록 적용했다.

(해당 부분에 대한 commented source code)

Pool Aggregator

이는 symmetric하고 trainable하며, 각 이웃 vector는 독립적으로 fully connected neural network의 입력으로 전달되어 이웃 집합의 정보 집계를 위해 element-wise pooling 연산을 적용한다.

(이 방법은 일반적인 point set을 neural network에 적용한 PointNet[C. R. Qi, et al., CVPR2017]에서 영감을 받음)

MLP를 이웃 집합의 각 node representation에 대한 feature를 계산하는 여러 개의 함수 집합(set)으로 간주할 수 있으며, 계산된 feature에 pooling operator를 적용함으로써 model은 효과적으로 이웃 집합의 각기 다른 측면(aspect)을 포착할 수 있다.

Experiments

3가지의 benchmark task.

• citation dataset에 대한 classification
• reddit dataset에 대한 classification
• PPI dataset에 대한 classification.

(PPI의 경우 작은 크기의 graph가 다수 포함되어 있으므로, 해당 dataset에선 unseen graph에 대한 test를 수행)

Experimental setup

4개의 baseline.

• random classifier
• feature 기반의 logistic regression
• DeepWalk
• raw feature와 DeepWalk에서 생성된 embedding을 결합한 classifier

GraphSAGE가 GCN의 inductive한 방법이기에, GCN을 GraphSAGE-GCN으로 명명하여 비교 실험에 기재.

또한 aggregator function을 각기 달리 변형하여 사용하였고, $K=2$, $S_1=25$, $S_2=10$으로 설정.

(1-hop에서는 25개의 이웃 node를 sample, 2-hop에서는 10개의 이웃 node를 sample)

Inductive learning on evolving graphs: Citation and Reddit data &
Generalizing across graphs: Protein-protein interactions

citation dataset에선 node degree를 feature로 사용하였고, abstract를 300-dimensional word vector로 변환하여 활용.

reddit dataset에서 node label은 subreddit(community)를 의미하며, 사전에 생성된 300-dimensional word vector를 feature로 활용.

PPI dataset에선 유전자의 위치 정보, 유전자의 생김새, 면역학적 특징(immunological signature)를 feature로 활용.

결과 table에서 볼 수 있듯이 inductive method인 GraphSAGE가 다른 baseline들에 비해 월등히 뛰어난 분류 성능을 보여줌을 알 수 있고, transductive method인 GCN(GraphSAGE-GCN)과 비교해도 대체적으로 좋은 분류 성능을 보여주는 것을 알 수 있다.

Runtime and parameter sensitivity

Deepwalk는 unseen node의 embedding을 계산하기 위해 SGD round를 새롭게 시작해야 하므로 속도가 많이 뒤쳐진다.

(Figure 2-A의 DW)

$K=1$로 설정한 경우에 비해 $K=2$로 설정한 경우가 10~15%의 성능 항상을 보이지만, $K=2$보다 크게 설정하는 경우 미미한 성능 차이(0~5%)를 보여준다.

(sample되는 이웃 node의 수 & hop 수를 적절하게 설정하는 경우 보편적으로 좋은 성능을 보인다.)

Summary comparison between the different aggregator architectures

LSTM, pool aggregator의 성능이 가장 좋게 나왔으며, 기존 GCN의 방법에 비해 대체적으로 논문에서 제안한 LSTM, pool, mean의 성능이 좋았다.

특이하게도 서로 다른 aggregator들을 사용한 결과에 대해 비모수 검정 기법인 Wilcoxon Signed-Rank Test를 진행하였고, T-통계량과 p-value가 applicable하였음을 확인하였다.

(또한 GCN 접근법에 비해 통계적으로 유의미한 gain을 얻었음을 한번 더 강조하였다.)

LSTM과 pool 간의 큰 성능 차이는 없었지만, 특성상 LSTM의 속도가 pool보다 (약 2배) 느렸음을 언급하였다.

Theoretical analysis &
Conclusion

GraphSAGE가 feature에 기반함에도 불구하고 graph의 구조를 학습할 수 있음을 소개하였고, 이웃 node의 sampling을 통해 runtime과 성능을 효율적으로 trade-off 할 수 있음을 보여주었다.

(Theoretical analysis와 Appendix 부분에 본 연구가 이론적으로 어떤 특징/강점이 있는지를 설명해주는데, 수학적인 background가 부족하여 별도로 기술하진 않았다😥)

개인적으로 GNN 연구를 할 때 GCN에 비해 여러 insight를 많이 가져다 준 논문이다.

neighborhood sampling을 소개하여 GNN의 mini-batch training이 가능함을 알려주기도 하였고, 이것이 발전하여 추후 layer-wise sampling, sub-graph sampling 등등 여러 sampler가 등장할 수 있게 하는 계기를 마련해주기도 했다는 생각이 든다.

실제로 PyG, DGL에서도 간단하게 sampler를 호출하여 random sampling을 수행할 수 있기도 하다.

하지만 이렇게 단순하면서도 편리하고 어떻게 보면 획기적인 neighborhood sampling의 (어떻게 보면 고질적인) 문제점이 있는데, 이는 추후 포스팅 할 글들에서 다시 언급하고자 한다.

22년 당시 review 후에 작성하였던 슬라이드도 함께 첨부하였다.

E.O.D.

석사과정을 시작하던 시절, 본격적으로 논문들을 review하던 중 deep-dive를 했던 논문 중 하나.

당시엔 notion의 존재를 모르기도 했고, (현재까지) 태블릿이 없기도 해서 프린트로 출력 후 논문에 직접 써가며 review를 했었던 기억이 난다.

(notion의 존재를 좀 더 빨리 알았더라면 re-posting도 수월했을텐데..)

tensorflow v1으로 작성된 코드를 논문과 비교하면서 해석해보고, 어찌저찌 실행도 해보고, 원 저자의 pytorch 구현을 참고해서 pytorch로 다시 작성해보고...

여러모로 추억이 많은 논문인 듯 하다.

Published in ICLR2017

• paper: https://arxiv.org/abs/1609.02907
• official source code repo (tensorflow v1): https://github.com/tkipf/gcn
• commented source code repo (tensorflow v1)
• re-built source code repo (pytorch)

graph의 edge 수에 따라 선형적으로 확장 가능한 semi-supervised learning 방법(GCN)을 소개.
hidden layer는 node의 feature와 그래프의 지역적인(local) 구조를 encode하여 그에 해당하는 representation을 학습하는 것이 가능.

Introduction

graph-based semi-supervised learning을 언급한다.

graph-based semi-supervised learning이 무엇일까?

graph의 모든 node마다 label 정보가 포함되어 있지 않고 일부의 node만이 label 정보를 가지고 있어, 해당 node들을 통해 node representation을 학습하여 label이 없는 node들에 대한 generalization(일반화)을 하는 것이 주 목적이라고 생각할 수 있을 것이다.

이를 하게 되면 뭐가 좋을까?

대표적으로 학습된 representation들을 통해 주어진 node가 어떤 label에 속하는 지를 판단하는 node classification task를 수행할 수가 있고, 논문의 첫 문장에서도 "classifying nodes (such as documents) in a graph (such as a citation network)." 를 언급하여 node classification task를 고려하기로 한다.

물론 과거에도 node classificaiton task를 해결하기 위한 여러 시도들이 있었고, 해당 연구들은 주로 graph Laplacian regularization term을 loss function에 추가하여 학습을 진행했다.

$\mathcal{L_{reg}}$의 몇몇 부분을 보자.

$f(\cdot)$ 이 미분 가능한 함수(e.g. neural network), $\lambda$는 단순 factor, $X$는 node feature vector 로 구성된 feature matrix, 그리고 $\Delta$는 $\Delta = D - A$로 이뤄지는 unnormalized graph Laplacian이다.

여기서 $D$는 각 node들의 차수(degree)를 나타내는 차수 행렬(degree matrix) 이고, $A$는 각 node들 간의 연결 정보를 binary하게 표현한 인접 행렬(adjacency matrix) 이다.

unnormalized graph Laplacian 이 무엇일까?

식을 보면 말 그대로 인접 행렬과 차수 행렬을 이용하여, graph의 구조적인 정보를 조금이나마 더 담아낸 행렬로 생각할 수 있다.

여기서 문제점이 발생한다.

식1은 연결된 node끼리는 같은 label을 공유한다 라는 가정을 전제 하에 두고 있다는 점이다.

이는 graph의 edge가 node 간의 유사성을 직접적으로 encode하지는 않지만, node간의 유사성은 추가적인 정보를 포함할 수 있기에 modeling capacity를 제한할 수 있다.

이게 무슨 의미 일까?

label은 동일하지만, 거리가 멀리 떨어진 두 node간의 유사성 정보를 반영하지 못할 수 있다.

즉 이러한 가정을 갖고 modeling을 수행할 경우, 복잡한 graph 또는 다양한 label을 가진 graph에서 모델의 학습 성능이 저하될 수 있다는 의미일 것이다.

따라서 본 논문에서는 graph의 구조를 곧바로 encode할 수 있는 방법과 더불어 크게 2개의 contribution을 소개한다.

1. graph에 바로 적용될 수 있는 neural network를 위한 간단한 layer-wise propagation rule을 소개.
2. 제안한 graph-based neural network 모델이 semi-supervised node classification task를 빠르고 scalable하게 수행 가능하다는 점을 소개.

Fast Approximate Convolutions on Graphs

논문에서 소개하는 GCN(Graph Convolutional Network)을 간단하게 소개하고, 관련된 이전 연구와 spectral convolution에 대한 background를 언급한다.

논문에서 소개하는 핵심인 layer-wise propagation rule은 다음과 같다.

$\tilde{A}$는 $A + I_N$으로 표현되는 undirected graph의 수정된 인접 행렬.

이때 $I_N$은 항등 행렬(identity matrix)이고 각 node가 자기 자신의 정보를 활용하기 위해 self-connection을 추가 한 형태라고 볼 수 있다.

$\tilde{D_{ij}}$는 $\tilde{A}$의 차수 행렬이고, $W^{(l)}$은 layer-specific weight matrix이다.

$H^{(l)}$은 $l$번째 layer의 activation matrix, 즉 $H^{(0)} = X$ (node feature matrix)가 된다.

논문에서는 식2의 propagation rule이 선행 연구인 [Hammond et al., 2011]과 [Defferrard et al., 2016](ChebNet)과 같이 localized 된 spectral filter의 1차 근사(first order approximation)를 통해 이뤄질 수 있음을 이야기 하고 있다.

선행되었던 두 연구 뿐만이 아니라 Chebyshev polynomials, spectral convolution 등등 알아햐 할 내용이 좀 많은 듯 한데, 이후로는 최대한 내가 이해했던 대로 기술하고자 한다.

review를 하던 당시 내용이 이해가 가질 않아 (조금이나마 이해하는데 도움이 되었 던) 자료를 다시 봐도 좋을 듯 하다:

블로그 포스팅

UCLA 자료

Spectral Graph Convolutions

Fourier domain에서 정의되며 filter $g_{\theta} = diag(\theta)$를 통한 spectral convolution은 다음과 같이 정의가 가능:

이때 $U$는 대각 성분이 자기 자신의 eigenvalue인 $\Lambda$로 구성된 normalized graph Laplacian $L = I_N - D^{-\frac{1}{2}}A D^{-\frac{1}{2}} = U{\Lambda}U^T$의 eigenvector로 이뤄진 행렬이고, $U^{T}x$는 $x$의 graph Fourier transform이다.

(벌써 어지럽다)

여하튼, 논문에서는 식3의 문제점을 지적하고 있다.

1. 이 식을 바로 계산하는 것은 computationally expensive.
   ($\because$ $D$는 sparse한 eigen matrix)
2. large graph의 Laplacian $L$을 eigen decomposition하는 것은 expensive.

이처럼 sparse matrix의 직접적인 이용이 힘들었기에, [Hammond et al., 2011]가 다음과 같이 $g_{\theta}(\Lambda)$에 대해 Chebyshev polynomials $T_k(x)$를 $K^{th}$차 까지 확장한다면 적절하게 근사(approximate)할 수 있음을 제안했다.

Chebyshev polynomials는 $T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$와 같이 recursive한 형태로 정의된다.

(자세한 내용은 [Hammond et al., 2011]의 논문을 참고하라고도 저자가 이야기 하고 있다.)

위의 식4을 이용해 식3을 다시 표현한다면 다음과 같이 근사(approximate)할 수 있다:

이때 $\tilde{L} = \frac{2}{\lambda_{max}}L - I_N$.

이 표현 식은 Laplacian에서 $K$차수 polynomial이기 때문에 $K$-localized된 식 이며, 즉 graph의 한 중심 node에서부터 최대 $K$ step만큼 떨어진 node에만 집중할 수 있으며, 계산 복잡도는 edge 수에 linear한 $\mathcal{O}(|\delta|)$가 된다.

역시 어렵다.

깊게 생각하기 보단, 단순히 기존 spectral convolution on graph의 식3 을 위와 같이 Chebyshev polynomials를 이용해 식5와 같이 approximate 하게 된다면 복잡도를 linear하게 줄일 수 있다는 점을 짚고 가면 될 듯 하다.

[Defferrard et al., 2016](ChebNet)가 선행적으로 이 식을 사용해 graph에 대해 convolutional neural network를 적용하는 방법을 정의하기도 하였다.

Layer-wise Linear Model

식5 형태의 convolutional layer를 여러 층 쌓아 graph convolution에 기반한 neural network model을 설계할 수 있고, 이때 $K=1$로 제한하게 된다면 식5는 선형함수가 된다.

$K=1$이어도 식5의 layer를 여러 층 쌓아서 convolutional filter를 여전히 근사할 수 있지만, Chebyshev polynomials로부터 주어진 명시적 파라미터화(explicit parameterization)의 제약을 받지 않게 된다.

이런 $K=1$인 모델은 wide node degree distribution을 가진 graph(e.g. social network, citation network, 실 세계 graph data 등...)에서 지역적인 이웃 구조(local neighborhood structure)에 overfit하는 문제를 완화할 수 있으며, layer-wise한 선형 연산으로 인해 neural network의 층을 더욱 깊게(deep) 할 수 있다.

neural network의 파라미터가 train하는 동안 적응 및 변화할 것으로 기대하기에 $\lambda_{max} \approx 2$로 근사하게 되면, 식5는 2개의 free parameter $\theta'_0$, $\theta'_1$ 를 이용해 다음과 같이 전개될 수 있다:

filter parameter는 전체 graph에서 공유 가능하며, 이 형태의 filter를 연속적으로($k$번) 적용하게 되면 한 node로 부터 $k$ 거리 만큼 떨어진 이웃까지 잘 convolve할 수 있다.

Chebyshev polynomials
$T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$를 이용해 $K=1$인 경우를 전개를 해 보면 다음처럼 간단히 전개할 수 있다:

$T_0(\tilde{L}) = 1$
$T_1(\tilde{L}) = \tilde{L}$

그리고 $\tilde{L} = \frac{2}{\lambda_{max}}(L - I_N)$로 정의되었고,
이때 $\lambda_{max} \approx 2$를 적용하면,
$\tilde{L} = L - I_N$ 이므로
$L = I_N - D^{-\frac{1}{2}}A D^{-\frac{1}{2}}$가 된다.

이 결과들을 식5에 적용($K=1$)하면 식6의 형태를 구할 수 있다.

여기서 연산량을 줄이거나 overfitting을 방지하기 위해서 filter parameter를 $\theta$ $=$ $\theta'_0$ $=$ $- \theta'_1$와 같이 간소화 한다면 식6은 다음과 같이 표현될 수 있다:

(단순히 $\theta$를 풀어서 전개하면 이 형태가 나온다.)

하지만 deep neural network에서 이 연산을 반복적으로 수행하는 경우, 수치적으로 불안정할 수 있으며 exploding/vanishing gradient 문제가 발생할 수 있다.

따라서 이를 방지하기 위해 다음과 같은 renormalization trick을 사용한다:

$$I_N + D^{-\frac{1}{2}}A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$$

$$where \ \tilde{A} = A + I_N, \ \tilde{D}_{ij} = \sum_{j} \tilde{A}_{ij}$$

이 trick을 이용해 $C$ input channel을 가진 signal $X \in \mathbb{R}^{N \times C}$ (graph의 각 node마다 $C$ 차원의 feature vector를 가지고 있는 경우)에 일반화를 하면 다음과 같은 형태의 수식을 구할 수 있다:

$\Theta \in \mathbb{R}^{C \times F}$는 filter parameter로 구성된 행렬, $Z \in \mathbb{R}^{N \times F}$는 convolution이 진행 된 signal의 행렬이다.

(즉 $\Theta$가 learnable weight, $Z$가 1번의 layer propagation을 거치고 non-linear activation을 적용하기 이전의 representation이 된다.)

이 filtering operation은 $\mathcal{O}(|\delta|FC)$의 복잡도를 가지며, 인접 행렬(adjacency matrix)과 특징 행렬(feature matrix)의 곱 연산($AX$)은 sparse matrix dense matrix multiplication (SpMM)과 같은 연산을 통해 효율적인 계산이 가능하다.

(몇몇 자료들을 보면 $\sum$ 기호를 이용해 node-level에서 representation을 계산하는 식을 소개하는데(vector-level), 

결국 이 vector들을 stack하여 식8과 같이 matrix로 표현한 것일 뿐이다.)

Semi-Supervised Node Classfication

앞서 소개한 내용을 바탕으로 이제 본 논문에서 target으로 잡았던 node classification을 어떻게 handle할 것인지를 소개한다.

논문에서는 graph의 구조적인 정보를 담은 $A$와 주어진 데이터인 $X$에 기반하여 식8 기반의 모델 $f(X, A)$를 conditioning하여 graph-based semi-supervised learning이 가능함을 이야기하고 있다.

semi-supervised learning을 위한 multi-layer GCN의 구조를 그림으로 보면 다음과 같다:

Example

2-layer GCN을 생각해보자.

먼저, 주어진 인접 행렬 $A$를 이용해 $\hat{A} = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$와 같은 전 처리(pre-process) 과정을 거친 후, 다음의 forward pass를 거치면 된다:

($\tilde{A} = A + I_N, \ \tilde{D}_{ij} = \sum_{j} \tilde{A}_{ij}$)

여기서 $W^{(0)} \in \mathbb{R}^{C \times H}$는 input-hidden 간의 가중치 행렬(weight matrix)이고, $W^{(1)} \in \mathbb{R}^{H \times F}$는 hidden-output 간의 가중치 행렬이다.

그리고 $\mathrm{softmax}$는 $\mathrm{softmax}(x_i) = \frac{1}{\sum_i exp(x_i)}exp(x_i)$인 row-wise로 적용되는 활성화 함수(activation function)이다.

학습을 위한 손실 함수(loss function)는 classification task에서 자주 사용되는 cross-entropy error를 사용하며, label이 포함된 모든 데이터에 대해 계산을 한다면 다음과 같다:

실험에 있어 모든 training iteration마다 full-batch gradient descent를 수행하였고, dropout을 사용하였으며, $A$는 sparse representation을 이용했기에 edge 수 만큼의 공간 복잡도를 가지게 된다.

어떻게 보면 단순하다.

2-layer를 가진다는 의미는 node representation을 계산 할 때 하나의 node로 부터 거리 2(2-hop)만큼 떨어진 노드의 representation을 활용한다는 의미일 것이다.

graph theory에 따르면 인접 행렬 $A$를 여러 번($n$번) 곱한다는 의미가 곱한 수 만큼의 거리($n$)까지를 고려한다(?)는 의미로 알고있는데, 자세한 내용은 graph theory를 자세히 공부한 적이 없어서 아직은 잘 모르겠다😥

Implementation

상단 repo link 참고

tf-v1이라 코드 해석 및 실행이 많이 힘들었던 기억이 새록새록 난다.

Related Work

Graph-based Semi-Supervised Learning

크게 2가지 접근법이 존재.

• 명시적으로 graph Laplacian regularization 형태를 사용하는 방법
  : label propagation [Zhu et al., 2003], manifold regularization [Belkin et al., 2006], deep semi-supervised embedding [Weston et al., 2012]
• graph embedding에 기반한 방법
  : DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], node2vec [Grover & Leskovec, 2016], Planetoid [Yang et al., 2016]

graph embedding 방법 중 DeepWalk, LINE, node2vec은 모두 random walk를 생성한 후 semi-supervised learning을 진행하는 2-step pipeline이 필요하여 두 step이 분리되어 최적화가 되어야 하지만, Planetoid는 embedding 학습 중 label 정보가 주입되어 그런 별도의 작업이 필요하지 않다.

Neural Networks on Graphs

Gori et al. (2005)에 의해 graph에 동작하는 neural network가 처음 소개되었고, Scarselli et al. (2009)에 의해 RNN을 이용한 방법이 소개되었다. 

RNN을 이용한 방법엔 여러 제약점이 존재했고, 이를 해결하기 위해 Li et al. (2016)에 의해 개선된 연구를 소개되었고, Duvenaud et al. (2015)에 의해 graph-level classification task에 convolution-like propagation rule이 소개되었다.

하지만 이 방법들은 node degree에 특정된 weight matrix가 필요했고, 이는 large graph에는 적용되기 힘든 문제가 있었다.

앞선 연구들과는 다르게 본 논문에서는 layer 당 1개의 weight matrix를 가지며, $A$를 적절하게 정규화하여 여러 node마다 다른 degree를 다룰 수 있도록 하였다.

spectral graph convolutional neural network는 Bruna et al. (2014)에 의해 소개가 되었고, Defferrad et al. (2016)가 fast localized convolution을 이용해 앞선 연구를 개선하였다.

본 연구에서는 조금 더 큰 규모의 network(graph)에서 node classification을 하는 방법을 고안하였고, 기존 framewortk에 몇가지 단순화(simplification)를 진행하여 large scale network(graph)에서 더 나은 scability와 classification performance를 달성할 수 있었다.

(단순히 related work 소개 + 우리 paper가 이래서 더 좋다~ 하는 내용들.)

Experiments

Datasets

Planetoid [Yang et al., 2016]에서 사용한 Citeseer, Cora, Pubmed, NELL을 사용.

Citation, Cora, Pubmed와 같은 Citation network에 대해선 citation link를 undirected edge로 판단하여 binary, symmetric adjacency matrix $A$를 생성하였다.

Knowledge graph인 NELL에 대해선 $(e_1, r, e_2)$와 같은 entity relation을 $(e_1, r_1), \ (e_2, r_2)$와 같이 분리하였고, 모든 relation node마다 one-hot representaion을 할당하였으며, Citation network와 마찬가지로 binary, symmetric adjacency matrix $A$를 생성하였다. (두 node 사이에 1개 이상의 edge가 연결되어 있다면 1, 아니라면 0)

Experimental Setup

• 2-layer GCN
• Planetoid [Yang et al., 2016]과 동일한 dataset split 진행
• 200 epoch
• Adam with learning rate 0.01
• early stopping with window size 10
• Glorot & Bengio weight initialization (Xavier initialization)
• input feature에 대해 row normalize 진행
• hidden layer size 32

Baselines

Planetoid [Yang et al., 2016]과 동일한 baseline 사용, 추가적으로 Planetoid와 비교 실험 진행.

Results

table에서 볼 수 있듯이, 기존 method들에 비해 significant한 성능 향상을 달성했다.

Planetoid와 제안한 GCN에 대해 wall-clock training time(실제 train에 소요된 시간)을 측정하였는데, 대부분의 경우 Planetoid에 비해 시간이 단축된 점을 확인할 수 있다.

특이하다고 느꼈던 점은 기존의 propagation 방법들에 대한 비교 실험도 진행한 것인데, 논문에서 제안했던 renormalization trick을 적용한 경우의 perfomance가 가장 좋은 결과를 보여주고 있다.

앞서 언급했었던 기존 방법(수식)들의 한계점을 결과로서 직접 보여주고자 했던 것이지 않았을까 라는 생각이 들었었다.

Discussion & Conclusion

graph Laplacian regularization에 기반한 방법은 edge가 단순히 node의 유사성(similarity)을 encode한다고 가정하기에 제한점이 많을 수 있다.

Skip-gram(embedding) based method에 기반한 방법은 최적화하기가 어려운 multi-step pipeline에 기반한다는 점에서 한계점이 존재한다.

본 논문에서 제안한 방법은 두 가지의 한계점을 모두 극복할 수 있으며, 각 layer에서 이웃 node들의 feature information의 propagation을 통해 classification performance를 높일 수 있다.

하지만 본 논문에서는 edge feature를 고려하지 않았고, undirected graph만을 고려하였다.

또한 암묵적으로 locality ($K$개의 layer를 가진 GCN에서 $K^{th}$ 차수의 이웃에 의존적)를 가정하였고, 몇몇 데이터 셋에 있어서는 self-connection과 이웃 node와의 edge에 대한 가중치를 조절할 수 있는 파라미터 $\lambda$를 이용해 $\tilde{A} = A + \lambda I_N$와 같이 이용하는 것이 바람직할 수 도 있다.

결과적으로 graph 데이터에 대해 semi-supervised classification을 수행하는 novel approach를 소개하였고, 소개하였던 first order approximation of spectral convolution에 기반한 layer-wise propagation rule이 효과적임을 보여주었다.

실제로 GCN code를 실행해보면 상당히 빠르게 동작하는 것을 볼 수 있다.

Graph Neural Network 연구를 시작할 때 Jure Leskovec 교수님의 강의 CS224W, pytorch geometric 공식 tutorial, DeepFindr 채널 등 인터넷에 공개된 좋은 자료들의 도움을 정말 많이 받았었다.

22년 당시 review 후에 작성하였던 슬라이드도 함께 첨부하였다.

E.O.D.