[Stanford/CS224W] 2. tradition-ml(3) : 전통적인 그래프 레벨 피쳐와 그래프 커널

스탠포드 강의를 듣고 정리한 내용입니다. 

 

지난 포스팅에서는 링크 레벨의 작업과 피쳐에 대해서 알아봤습니다. 

이번 포스팅에서는 그래프 레벨의 피쳐와 그래프 커널에 대해 알아보겠습니다. 

 

Graph-level feature

graph-level feature의 목적은 전체 그래프의 구조를 특징짓는 하나의 feature를 만드는 것입니다. 

예를 들어 graph-level feature는 위의 A~H노드와 그 간선들을 표현할 수 있는 하나의 feature로 만드는 것이죠.

 

위의 작업을 하기 위해서는 kernel이라는 것을 이용합니다. 

kernel은 쌍으로 이루어진 그래프들의 유사도를 비교하기 위해 전통적인 ML에서 널리 쓰이는 방법입니다. 

요약을 하자면 다음과 같습니다. 

• 두 그래프의 커널이란 서로 다른 데이터 포인트 간의 유사성을 측정하는 상수이다. (내적)

• 커널 행렬은 항상 양의 값을 가지면서 대칭인 행렬이다. 

• feature를 나타내는 표현인 Ø가 있다. 그래프 G와 G'의 커널이란 Ø(G)^T와 Ø(G')의 내적과 같다.

• 커널은 한번 정의되면 SVM과 같은 모델에서 계속 사용 가능하다. 

 

이제 graph kernel의 방법론들을 살펴보도록 하겠습니다. 

• Graphlet Kernel
• Weisfeiler-Lehman Kernel

더 다양한 방법들이 있지만, 크게 이 두 커널에 대해서 살펴보도록 하겠습니다. 

 

두 개념에 들어가기 전 먼저 알아야 할 아이디어들을 소개하고, 바로 위의 두 방법을 소개하도록 하겠습니다. 

 

이 방법들의 특징은 Bag-of-Words(BoW)의 개념을 그래프에 적용한다는 것인데요. 들어보셨을 수도 있지만, BoW은 자연어 처리에서 주로 등장하는 개념이죠. 

 

※ Bag-of-Words(BoW)가  뭔가요?

BoW는 단어들의 순서는 전혀 고려하지 않고, 출현 빈도에만 집중하는 텍스트 데이터의 수치화 표현 방법입니다.

BoW를 구하기 위해서는 아래의 두 단계를 거쳐야 합니다. 

1. 문장 내에 각 단어들을 인덱싱 해준다. 

2. 각 단어가 몇 번 나왔는지 세준다.

 

예를 들어 "나는 그래프를 공부한다. 그래프 공부는 너무 재밌다."라는 문장이 있을 때, 이 문장을 최소 단위로 잘라주고, 각 단어들을 인덱싱 해줍니다. 

{"나" : 0, "는" : 1, "그래프" : 2, "를" : 3, "공부" : 4, "한다" : 5, "너무" : 6, "재밌다" : 7 }

 

이후 각 단어들이 몇 번 등장했는지 세준 뒤, 각 인덱스에 값으로 채워넣어줍니다. 

[1, 2, 2, 1, 2, 1, 1, 1]

 

그렇다면 BoW를 어떻게 그래프에 적용할까요?

 

BoW의 '단어'를 그래프의 '노드'로 생각하시면 됩니다. 즉 같은 노드가 등장하면 같은 그래프라고 표현하게 됩니다. 

위와 같이 노드 수는 같지만 링크는 다릅니다. 하지만 같은 노드가 등장하기 때문에 위 두 그래프는 같은 그래프가 됩니다. 

 

방법을 조금 보완해서  BoW의 단어를 node degree로 표현해 보겠습니다. 

각 노드의 degree에 따라 다르게 센 뒤 하나의 행렬로 표현한다면, 위의 두 그래프가 다르다는 것을 알 수 있게 됩니다. 

 

하지만 우리가 배울 Graphelt kernel, weisfeiler-lehman kernel은 위에서 나온 그래프의 BoW 표현보다 훨씬 정교하게 표현이 가능합니다. 

 

Graphlet Kernel

graphlet kernel은 여기에 graphlet 개념을 적용합니다. 여기서는 기존의 graphlet과 두 가지 다른 특징을 가집니다. 

• 모든 노드가 연결되어 있지 않아도 된다.
• root 노드가 없다. 

예를 들어 노드 개수가 3개, 4개인 graphlet은 아래와 같이 나타낼 수 있습니다.

기존 graphlet에서 k = 3인 노드들의 graphlet은 아래와 같이 나타낼 수 있습니다. 현재의 graphlet과 차이가 느껴지시나요?

위의 그래플랫을 이용하여 아래 수식처럼 graphlet count vector를 만들어 줄 수 있습니다.

 

그래프를 G라고 표현할 때, 그래프의 k에 대한 graphlet list는 𝒢_k = (g₁, g₂, g₃, ..., g_(nk))로 표현할 수 있고, graphlet count vector는 최종적으로 f_G ∈ R^nk 로 표현이 가능합니다.

 

조금 더 자세히 풀어 써보자면 

으로 표현할 수 있습니다. 즉 노드 k개로 만들 수 있는 graphlet의 개수 i개가 원본 그래프 G에 몇개 들어있는지 하나의 벡터로 표현하는 것 입니다. 

 

이렇게 수식으로 보면 이해가 안될 수 있으니 바로 예를 들어보도록 하겠습니다. 

k=3으로 설정했을 경우 나올 수 있는 graphlet은 위와 같이 4개 입니다. 위의 graphlet을 인덱스로 0~3으로 설정하고, 그래프에 있는 개수를 보면 0번째는 1, 1번째는 3, 2번째는 6, 4번째는 0입니다.

 

따라서 이를 graphlet count vector로 나타내면 f_G=(1,3,6,0)입니다.

 

아까 제가 kernel은 '두 그래프의 차이를 구하는 것이다'라고 말씀드렸었죠? 

G, G' 두 그래프가 있을 때, 각각을 위와 같이 graphlet count vector로 표현한 뒤, 각 행렬을 내적해주시면 됩니다. 

위의 수식을 해석해 보자면 "G, G'의 커널은 두 그래프의 graphlet count vector의 내적이다." 라고 할 수 있습니다. 여기서 T는 transpose를 뜻하고(단순히 곱을 위해 행과 열을 바꿔줌), 내적을 하는 이유는 내적이 두 벡터가 얼마나 닮아있는지를 측정할 수 있기 때문입니다. 왜 그런지에 대해서는 관련 포스팅을 참고해주세요.

 

그런데 여기서 문제점은 G, G'가 다른 사이즈일 수 있다는 것이죠. 

 

따라서 아래와 같이 정규화 과정을 거친 뒤에 두 벡터의 내적을 구해줍니다.

※ 사이즈가 다른데 정규화요? 무슨소리죠?

여기서 '사이즈가 다르다'라는 것은 벡터의 길이가 다른 것이 아닌 공간이 다르다고 볼 수 있는데요.

예를 들어 G는 노드가 4개인 작은 그래프, G'는 노드가 100개인 큰 그래프이기 때문에 f_G = [1,2,1,4]

, f_G'= [20,10,30,15]처럼 나올 수 있습니다. 따라서 두 벡터 사이의 수 차이가 너무 크기 때문에, 이를 정규화 시켜주고 비교해줍니다. 

 

이 방법은 겉 보기에는 편해보이고 좋아보일 수 있습니다. 하지만 계산 비용이 아주 크다는 단점이 있습니다. 시간 복잡도를 구해보면 n 사이즈를 가진 그래프는 n^k입니다. 

 

Weisfeiler-Lehman Kernel

Weidfeiler-Lehman Kernal은 좀 더 효율적으로 계산 할 수 있는 방법입니다. 

바로 이웃 노드들의 구조를 반복적으로 이용하여 조금더 풍부한 표현을 만들고자 했는데요. 

 

즉, BoW의 vocab을 풍부하게 만드는 것과 같습니다. 이게 무슨 소리지? 하실 수 있는데 "노드를 다양하게 표현하는구나" 생각하시면 됩니다. 여기서는 이 아이디어를 color refinement라고 부릅니다. 

수식은 위와 같이 표현할 수 있는데요. k+1번째 반복하는 노드 v는, k번째 반복하는 노드 v와 그 이웃 노드들의 합으로 표현할 수 있고, 이 표현은 Hash를 통해 다른 값으로 맵핑된다고 보시면 됩니다. 

 

이번에도 예를 통해서 쉽게 이해해 봅시다. 

위와 같이 서로 다른 그래프 G(좌), G'(우)가 있다고 가정해 봅시다. 각 노드의 값은 1으로 초기화 됩니다. 

 

이제 첫 번째 루프를 돌아볼까요?

위에 보시는 것 처럼 현재 자기 자신의 값을 먼저 적고, 주변 노드에 어떤 색이 있었는지 뒤에 이어붙여줍니다.



이 값은 먼저 정의해둔 Hash table에 의해 또 다른 수치로 변경됩니다. 

 

그럼 두 번째 루프를 돌아볼까요?

첫 번째와 달리 해싱된 값들이 사용되었기 때문에, 굉장히 다양한 숫자들이 붙어있는 것을 확인할 수 있습니다. 

이번에도 해싱 함수를 통해 바꿔주면 다음과 같은 값을 얻을 수 있습니다. 

 

두 번째 루프까지 돌고 각 벡터를 표현해 보면, 아래와 같습니다.

각 벡터들은 k번 반복할 때까지, 각각의 숫자(해싱 값)들이 몇 번 나왔는지 카운트합니다. 따라서 위와 같이 각 벡터들을 표현할 수 있습니다. 

최종적으로 커널은 위의 두 벡터를 내적해 주시면 됩니다. 

 

위의 방법은 앞서 나온 graphlet kernel과는 다르게 시간복잡도가 linear하여 매우 효율적인 방법입니다. 즉 엣지에 따라 선형인 시간복잡도를 가집니다.