[CS224W] 2-3. Traditional Feature-based Methods: Graph

1. Graph-Level Features

Goal: We want features that characterize the structure of an entire graph

Background: Kernel Methods

Kernel methods란 graph-level prediction을 위한 전통적인 ML에서 보편적으로 쓰이는 방법론이다. 이 방법론의 아이디어는 이름처럼, feature vector 대신 'kernel'을 디자인하자는 것이다.

• Kernel K(G, G') $\in$ $\mathbb{R}$은 두 그래프(G) 사이의 유사도를 측정한다.
• Kernel matrix K는 항상 positive semi-definite이며(이는 해당 matrix가 항상 양의 eigenvalue를 가짐을 의미), 대칭행렬 이어야 한다.
• feature representation(vector representation) $\phi(.)$가 존재한다. kernel은 이 vector representation의 dot product로 나타낼 수 있다.
• kernel을 SVM(support vector machine) 등에 붙여서 사용할 수 있다.

앞으로 Graphlet kernel, Weisfeiler-Lehman kernel을 비롯한 실제 kernel에 대해 구체적으로 살펴볼 예정이다. 방금 언급한 것들 외에도 Random-walk kernel, Shortest-path graph kernel 등 여러 방법론이 존재하지만 이 강의의 범위를 벗어나는 것이라 구체적으로 다루지는 않는다.

2. Graph Kernel

Goal: Design graph feature vector $\phi(G)$

Key idea: Bag-of-Words(BoW) for a graph

1) Naive extension

이때, BoW란 NLP에서 모든 단어가 몇 번 나타나는지 세는 방법을 말하는데, 이를 graph에 적용할 수 있는 가장 naive한 방법은, node를 단어라고 생각하고 BoW를 적용하는 것이다. 다만 이렇게 했을 때 문제점은, 그래프의 구조가 매우 다르더라도 같은 수의 node를 가지고 있다면 같은 feature vector를 얻을 수 있다는 점이다. 일례로, 아래 두 가지 그래프는 다른 구조를 가지고 있지만 node의 개수가 4로 같기 때문에 이와 같은 naive한 접근법에서는 서로 같은 결과가 나올 수 있다.

2) Node Degrees

위와 같은 naive extension에서의 문제점을 보완하고자 등장한 것이 바로 node degrees를 word로 취급하자는 아이디어이다. 아래 그림에서, 위쪽 그래프는 degree 1인 node가 1개, 2인 node가 3개, 3인 node가 0개인 반면, 아래쪽 그래프는 degree 1인 node가 0개, 2, 3인 node가 각각 2개로, node의 개수는 같지만 이처럼 node degrees를 기반으로 나타내었더니 서로 다른 그래프라는 것이 잘 구분됨을 알 수 있다.

앞으로 살펴볼 Graphlet kernel과 Weisfeiler-Lehman kernel에도 이러한 Bag-of-something representation이 활용되는데, 이때 something에는 node degree보다 더욱 정교한 지표가 사용된다.

3. Graphlet Features

Key idea: Count the number of different graphlets in a graph

Graphlet이 무엇인지에 대해서는 이미 2-1. Traditional Feature-based Methods: Node에서 살펴본 바 있다. 그런데 이 강의에서 이야기하는 graphlet의 정의는 node-level features에서의 graphlet의 정의와 살짝 다르다. 그 차이점은 아래와 같다.

• Isolated node 또한 graphlet의 일부로 허용한다.
• Root Node가 없다.

graph G가 주어지고, graphlet list $G_k$가 주어졌을 때, Graphlet count vector $f_G$는 graph에서 나타나는 각 graphlet의 instance의 수로 정해진다. 자세한 사항은 아래와 같다.

4. Graphlet Kernel

1) Graphlet Kernel

2개의 그래프 G, G'이 주어지면, graphlet kernel은 다음과 같이 각각의 graph count vector의 내적으로 표현될 수 있다.

• Problem: G와 G'의 size가 다르면, 값이 크게 왜곡(skew)될 수 있다.
• Solution: $f_G$ 대신 전체 sum으로 나눠서 normalize한 $h_G$를 사용한다.

그러나 graphlet kernel에는 한계점이 존재하는데, graphlet을 계산하는 것이 매우 비싸다는 점이다. k-size의 graphlet을 n개의 node를 가진 graph에 대해서 계산하려면, $n^k$만큼의 연산이 필요하다.

• This is unavoidable in the worst-case since subgraph isomorphism test(judging whether a graph is a subgraph of another graph) is NP-hard(다항 시간에 맞았는지 확인할 수 있는 문제를 NP 문제라 하는데, 그보다 어려운 문제다... 라고 간단하게 이해하고 넘어가면 될 것 같다. 이때 '어렵다'는 난이도의 개념은 다항 시간 변환을 통해 비교가 가능한데, 이를 통해 어떤 문제가 이미 잘 알려진 NP-hard 문제보다 어렵다는 등의 증명이 가능하다).
• If a graph's node degree is bounded by d, an $O(nd^{k-1})$ algorithm exists to count all the graphlets of size k.

여기에서 대두되는 문제는, 보다 효율적인 graph kernel을 디자인할 수는 없는 것인가? 인데, 이에 대한 대답으로 등장하는 것이 다음에서 살펴볼 Weisfeiler-Lehman Kernel이다.

2) Weisfeiler-Lehman Kernel

Goal: Design an efficient graph feature descriptor $\phi(G)$

Idea: neighborhood structure를 이용하여 반복적으로 node vocabulary를 풍부하게 만드는 것

이는 one-hop neighborhood인 node degree 방식을 일반화한 버전이라고 보면 된다. 해당 kernel은 'color refinement'라는 알고리즘에 의해 이루어질 수 있는데, 이것이 무엇인지는 아래에서 자세히 보도록 하자.

3) Color Refinement

graph G와 set of nodes V가 주어졌다고 해보자.

1. Initial color $c^{(0)}(v)$를 각각의 node v에 할당한다.
2. 아래와 같은 연산을 통해 반복적으로 node의 color를 정제해 나간다(이때 HASH는 서로 다른 input이 들어왔을 때 서로 다른 색으로 매핑하는 연산이다).
3. K step의 color refinement가 끝나고 나면, $c^{(k)}(v)$는 K-hop neighborhood 구조의 summary가 된다.

구체적인 예시는 아래에서 확인할 수 있다. 비슷하지만 조금 다른 형태의 그래프 G, G'이 들어왔을 때 color refinement 연산을 적용하는 예이다.

1단계. Assign initial colors(동일한 initial color를 모든 nodes에 할당)

2단계. Aggregate neighboring colors(직접 이웃하고 있는 node의 개수만큼 aggreagting이 잘 된 것을 볼 수 있다)

3단계. Hash aggregated colors(Hash table을 통해 새로운 color로 변환)

4단계. 다시금 이웃하는 색상에 대해서 aggreagte

5단계. 다시금 aggregate된 결과에 대하여 Hash 연산 적용

6단계. k번의 iteration을 거쳐 color refinement가 끝나면, WL kernel이 각 color가 등장한 횟수를 세서 summary(우리의 예시에서는 총 13개의 color가 등장하여, 첫 번째 그래프의 경우 1번 color는 6번, 2번 color는 2번... 이런 식으로 feature descriptor를 구성한다)

7단계. 이전 단계에서 구한 feature descriptor(color count vector) 사이의 내적으로 WL kernel의 결과값을 구한다.

WL kernel은 매우 popular할 뿐 아니라 매우 strong하며, computationally efficient하기까지 하다. color refinement의 각 step에서의 시간 복잡도는 number of edges(size of the graph)에 linear하기 때문이다. 모든 node가 해야할 일은 이웃한 node들로부터 color를 수집하고, 간단한 hash function을 적용하기만 하면 되기에, 많은 시간 복잡도가 요구되지 않는다. 또한 color의 개수는 node의 전체 개수를 넘어가지 않기 때문에, 시간 복잡도가 지나치게 상승하는 것을 막을 수 있다.