[GNN] Traditional Methods for Machine Learning in Graphs

본 게시글은 Stanford 대학교 Jure Leskovec 교수님의

Stanford CS224W: Machine Learning with Graphs(2021) 강의를 듣고

학습을 목적으로 재구성한 글입니다

스스로 정리한 내용이라 오류가 있을 수 있습니다

 

https://web.stanford.edu/class/cs224w/

CS224W | Home

https://www.youtube.com/watch?v=6g9vtxUmfwM&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=15

 

---

neural network 구조를 사용하는 deep learning 기술이

지속적으로 발전하면서

다양한 타입의 데이터들을 neural network를 통해 학습시키고 있다

비전같은 경우는 Image 데이터를 neural network에 넣는 것이고

NLP같은 경우는 자연어 데이터를 neural network에 넣는 것이다

 

이러한 흐름에서 graph와 같은 복잡한 타입의 데이터도

neural network에 넣어

graph라는 데이터 타입이 갖고있는 특징을 사용해

무언가를 예측하는 기술이 등장했는데

이것이 바로 Graph Neural Network(GNN)이다

 

그래프 데이터 구조는 생명공학에서의 단백질 구조

혹은 SNS에서의 친구 구조 등에서도 많이 쓰이지만

내가 전공하는 공간정보에서 

공간과 공간과의 관계를 표현할 때도 자주 사용된다

가장 대표적인 예시로는 도로망을 그래프로 나타내는

도로망 네트워크가 있다

 

따라서 공간정보분야에서는 어떠한 공간과 공간 데이터를

그래프의 구조로 표현한 다음

이를 GNN을 사용하여 공간 통계, 예측, 추천 등과 같은 분야에

적용하려는 시도가 늘고있다

이러한 연구주제에 나도 관심이 있기 때문에

Stanford 대학교의 Machine Learning with Graphs 강의를 듣고

정리해보기로 했다

 

해당 강의는 머신러닝, 딥러닝에 대한 사전지식이 필요하며

선형대수학, 확률과통계에 대한 이해가 있어야한다

 

나는 이전에 각 과목들을 따로 공부한 적이 있어 해당 강의를 바로 듣지만

강의를 듣다가 기억이 잘안나거나 모르는 개념이 나올 시에는

기본적인 머신러닝, 딥러닝, 선형대수, 확통 개념을 다시 공부하며

기초를 탄탄히 다져나갈 계획이다

 

... 아무튼 이제부터 시작!

 

---

Traditional Methods for Machine Learning in Graphs

Introduction의 내용은 graph에 대한 기본적인 내용이라 생략했다

 

Graph는 G = (V, E)로 표현되며

V는 node(vertex), E는 edge(link)의 집합이고

방향성이 있는 directed graph

방향성이 없는 undirected graph 등이 존재하고

edge에 weight가 있는 경우도 있다

등과 같은 기본적인 그래프에 대한 내용이었다

 

GNN이 나오기 이전에 전통적으로

머신러닝에서는 그래프를 어떻게 처리했을까?

 

 

그래프에는 3가지 level이 있다

 

1. node-level

2. link-level

3. graph-level

이 있는데

 

노드 레벨은 말 그대로 노드의 관점

링크 레벨도 말 그대로 링크의 관점

그래프 레벨은 노드&링크 전체를 아우르는

전체 그래프의 관점이다

 

 

Node-level Tasks

 

 

우선 node-level부터 살펴보자

node-level에서 할 수 있는 가장 대표적인

머신러닝으로는

node classification이 있다

 

 

 

node classification이란 node의 위치와 구조를

graph 내에서 파악해서 이를 바탕으로 분류하는 것을 말한다

 

node-level의 feature로는

node degree (노드의 차수)

node centralities(노드 중심성)

clustering coefficient (클러스터링 계수)

등이 있다

 

node centralities란 해당 노드가

그래프에서 얼마나 중요한지

"importance"(중요도)를 측정하는 것이다

이런 노드의 중요도를 측정하는 방법은 여러 가지가 있는데

크게 

1. Eigenvector Centrality

2. Betweenneess Centrality

3. Closeness Centrality가 있다

 

 

우선 Eigenvector centrality에 대해서 알아보자

선형대수학에서 나오는 그 eigenvector/eigenvalue(고유 벡터/고유값) 개념이 맞다

 

Eigenvector centrality는 한 마디로 말해서

연결된 이웃들이 얼마나 중요하냐에따라

중심성을 측정하는 방식이다

 

 

노드 v의 중심성 Cv는

노드 v와 이웃한 노드들의 중심성의 합인데

이를 오른쪽과 같이 eigenvector/value를 구하는 식으로 표현할 수 있다

여기서 eigenvalue인 람다는 언제나 양수이고

eigenvector인 C가 centrality를 나타낸다

 

 

다음으로 Betweenness centrality에 대해 알아보자

betweenness centrality는 노드가 중재자 역할을

얼마나 잘 하는지를 수치화한 지표이다

한마디로 "중간다리"역할을 잘하고있다면

해당 노드는 중요하게 생각한다는 의미이다

 

계산식은 위와 같고 social network에서 중요하게 쓰인다고한다

 

 

 

Closeness centrality는

어떤 노드가 그래프 내의 다른 노드와 얼마나 가까운지를

측정하는 지표이다

 

계산식은 위와 같다

 

 

이제 다음으로는 node-level에서의 다른 노드 feature인

Clustering Coefficients에 대해 살펴보자

 

 

clustering coefficient를 쉽게 설명하면

한 노드 주변의 밀집도로

중심성을 측정하는 것이다

 

계산을 하는 공식은 위와 같다

0에서 1사이의 수이고

1일수록 밀집도가 높은 것을 의미한다

 

그래프를 그렸을 때를 생각해보면

clustering coefficient는 그래프 내부에서

삼각형의 개수와 동일하다

 

예를 들자면 A, B, C가 있는데

A, B, C가 모두 연결되어있다면

그래프 내부에는 삼각형 모양으로 연결이 될 것이고

이러한 삼각형 모양일 때 clustering coefficient는 1이 된다

 

clustering coefficient에서 이러한 개념을 이해한채로

다음 graphlets을 살펴보자

위에서 clustering coefficient는 결국

해당 노드 주변(ego-network)에서 삼각형을 세는 것과 같다고 했다

 

 

Graphlets이란 작고 미리 정의된 subgraph pattern을 뜻한다

위의 clustering coefficient는 삼각형 모양만을 고려하지만

실제 복잡한 그래프 구조에서는 삼각형, 별모양, 체인모양 등

다양한 모양이 존재할 수 있다

따라서 graphlets은 이러한 다양한 모양의 subgraph pattern을

세어서 그래프에서의 더욱 풍부한 특징을 추출할 수 있는 것이다

 

따라서 한 그래프에서 이러한 subgraph pattern의

정보를 담은 벡터를

graphlet degree vector(GDV)라고 한다

 

node의 개수가 2개에서 5개까지 존재하는 그래프의

graphlets에 존재하는 subgraph는 총 73개이고

GDV의 차원은 73이 된다

 

 

위는 영상에서 나온 ppt 예시인데

위 Example graph G의 노드 v에서 나오는 lists of graphlets은

a, b, c, d 4가지 종류이고

각 a, b, c, d마다 존재 여부를 확인하면 아래와 같다

 

따라서 그래프 G의 GDV는 a, b, c, d 4차원의 벡터가 되고

GDV는 [2, 1, 0, 2]가 된다

 

 

 

Link-level Tasks

 

link prediction 문제를 설정하는 방법은 크게

1. links missing at random

2. links over time

2가지가 있다

 

links missing at random은

전체 그래프에서 임의의 link 몇 개를 제거한 뒤

제거된 link들이 무엇이었는지 맞추는 방식이다

 

두번째 links over time은

과거 t0시간의 그래프 G의 연결된 링크들을 보여준 다음

t1 시간에는 생기는 새로운 링크들을

예측하는 방식이다

 

link-level features로는

distance-based feature

local neighborhood feature

global neighborhood feature

이렇게 3가지가 있는데

distance-based feature은

두 노드 사이의 shortest-path distance를 말한다

 

그다음 local neighborhood feature은

두 노드 사이에 얼마나 공통된 이웃을 갖고있냐를

측정하는 feature이다

여기에 또 크게 3개의 종류가 있다

 

 

간단하게만 설명을 하고 넘어가자면

common neighbours은 

두 노드 v1, v2에서 공통으로 연결된

노드의 개수를 계산하는 것이고

 

jaccard's coefficient는

전체 v1, v2와 연결된 노드에서

v1, v2와 공통으로 연결된 노드를 계산하는 것이다

 

Adamic-Adar Index는 공통이웃들의 정보량을 반영하는데

희귀한 공통 이웃을 중요하게 본다

 

그러나 이러한 점들의 한계는

공통된 이웃이 없을 시 0이 나온다는 점이 있다

 

다음으로는 global neighborhood에서의

Katz index에 대해서 알아보자

 

Katz index는 두 노드 v1, v2 사이에 존재하는

모든 path를 고려해서

두 노드가 서로 연결될 가능성을 측정하는 지표이다

 

path의 개수는 Adjacency matrix를 이용해서 계산하는데

인접행렬을 제곱해서 구할 수 있다

따라서 전체 path의 총 길이는

인접행렬을 제곱한 것에서 0과 1사이의 discount factor인

베타를 곱해서 다 더한 값으로 구해준다

 

위 식에서 시그마로 총합을 구한 식을

행렬의 등비급수 합공식으로 표현하면 오른쪽처럼 변환할 수 있다

 

 

 

Graph-level Tasks

graph level task를 알아보려면 우선

kernel methods에 대해서 이해해야한다

 

kernel method란

우리가 보통 머신러닝에서는

데이터를 벡터로 표현한다음

이를 어떤 알고리즘에 넣어서 어떤 output을 도출한다

 

하지만 이렇게 데이터를 벡터로 바꾸는 과정이

어렵고 복잡하기 때문에

데이터를 벡터로 변환하지말고 그냥 similarity(유사도)만 측정하자는 것이고

이 유사도를 계산하는 함수를 kernel(커널)이라고 한다

 

 

따라서 수학적으로 kernel을 사용한다는 것은

그래프 G가 있으면

그래프 G의 어디에선가 존재하는 벡터 표현에서

유사도를 계산해서 K(G, G')를 구한다는 의미이다

즉, 커널 함수를 사용한다는 것은 어떤 특정 벡터 공간에서

벡터들을 dot product(내적)한다는 것과 같다

 

여기서 graph kernel이란 개념이 나오는데

이 graph kernel은 bag-of-words(BOW)를

graph에 적용한 것이다

NLP에서 나오는 BOW 개념을 그래프에 적용해서

words 대신에 nodes를 모은 것이다

 

따라서 graph kernel이란 2개의 graph에서 유사도를 계산하는 것인데

여기에는 Graphlet Kernel, Weisfeiler-Lehman Kernel

2가지가 대표적이다

 

첫 번째 graphlet kernel에 대해서 설명하자면

graph-level graphlet feature는

그래프에서 서로 다른 graphlet의 개수를 센 것이다

graph level의 graphlet은 node level의 graphlet과는 다른데

node level의 graphlet은 not need to be connected이며 rooted인데

graph level의 graphlet은 연결되어있어야하며 not rooted이다

 

따라서 각 그래프 G와 G'이 있을 때 

각 그래프에서 graphlet의 출현 횟수를 세어

feature vector로 표현한다

이러한 feature vector를 내적하면

두 그래프 G, G'이 얼마나 유사한지가 나온다

 

하지만 이러한 경우 그래프 크기 차이가 발생하면

문제가 발생할 수도 있다

따라서 이러한 경우 normalize를 시킨다고한다

 

이는 전체 합에서 해당 원소를 나누면서 비율이 구해지기 때문에

전체 그래프 크기와는 상관이 없는 값이 구해지게 된다

따라서 normalize시킨 h를 내적해서 유사도를 구한다고 한다

 

그러나 이런 graphlet kernel은 치명적인 한계점이 있는데

그래프의 graphlet kernel을 세는게 

굉장히 비용이 비싼 작업이기 때문이다

 

size n의 graph에서 size-k grahplet을 세려먼

n의 k제곱의 time complexity가 소요된다

 

따라서 이러한 time complexity가 작은 방법이 바로

Weisfeiler-Lehman Kernel 방법이다

이 방법은 그래프 간 유사도를 측정하기 위해

color refinement algorithm을 사용한다