연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.
유튜브 강의 링크는 다음과 같다.
https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn
Stanford CS224W: Machine Learning with Graphs
This course covers important research on the structure and analysis of such large social and information networks and on models and algorithms that abstract ...
www.youtube.com
목차
Graph를 사용한 머신러닝 과정을 요약하면 다음과 같다.
- Input Graph
- Structured Features
- Learning Algorithm
- Prediction
이때, 1번 과정에서 2번 과정으로 넘어갈 때를 주목하자. 이렇게 graph를 node-level, edge-level, graph-level 중 하나의 feature로 바꾸는 과정을 Feature engineering이라 한다.
그런데 전통적인 ML에서는 이 feature engineering을 학습할 때마다 rule-based, hand-crafted 방식으로 해주어야 했다. 이 과정이 복잡하고, 시간도 많이 소요되는 문제점이 있었다.
따라서 최근에는 representation learning을 통해 학습할 모델이 자동으로 feature를 학습할 수 있도록(변수를 뽑아낼 수 있도록) 한다.
이를 위해서는 그래프나 노드를 일반적으로 학습 가능한 형태로 만들어 주어야 하는데, 그 방법에 대해 자세히 알아보자.
Graph Representation Learning
Representation learning의 목적은 task와 독립적으로 효과적인 feature learning을 하는 것이다.
그래프에서 representation을 학습한다는 것은 입력을 임의의 vector로 변환하는 것이다.
그래프의 요소인 node, link, graph 등이 입력이 되고, 어떤 모델(함수)은 그 입력을 특정 embedding space로 맵핑한다.
위 그림과 같이 vector 형태로 나타난 맵핑의 결과물을 feature representation, 혹은 embedding이라 한다.
맵핑 과정은 network의 정보를 인코딩(encoding)하는 과정으로 볼 수 있다. 즉, 네트워크에서 비슷한(유사한) 노드들은 임베딩 공간에서도 서로 가까이 위치하게 된다.
이러한 embedding은 node classification, link prediction, graph classification, anomalous node detection, clustering 등 다양한 task에 사용된다.
예를 들어, 아래와 같이 입력 graph를 2차원 임베딩 공간에 맵핑할 수 있다.
같은 색의 노드는 2차원 공간에서 비슷한 위치에 있음을 알 수 있다.
Node Embeddings: Encoder and Decoder
vertex 집합 \(V\), (binary) adjacency matrix \(A\)를 갖는 graph \(G\)가 있다고 하자.
Node embedding의 목적은 embedding space에서의 두 vector의 유사도(예를 들어, dot product 사용)가 graph에서의 유사도를 근사하도록 인코딩하는 것이다.
수식으로 나타내면 다음과 같다.
\( \text{similarity}(u, v) \approx \mathbf{z_v^\top} \mathbf{z_u} \)
좌변은 네트워크에서의 유사도, 우변은 embedding의 유사도이다. 위 식을 만족시키는 \(\text{ENC}(u), \text{ENC}(v)\)를 정의하는 것이 바로 node embedding이다.
Node embedding을 학습하는 과정을 정리해보면 다음과 같다.
- Encoder를 정의한다. Encoder(\(\text{ENC}\))는 node로부터 embedding으로 맵핑하는 함수를 말한다.
- Network에서의 node similarity function을 정의한다.
- Decoder를 정의한다. Decoder\(\text{DEC}\))는 embedding으로부터 similarity score로 맵핑하는 함수이다.
- Encoder의 parameter를 다음 식을 만족시키도록 optimize한다.
- \(\text{ENC}(u, v) \approx \text{DEC}(\mathbf{z_v^\top z_u})\)
여기서 두 가지 주요 개념이 있다.
먼저 encoder는 다음 식으로 나타난다.
\( \text{ENC}(v) = \mathbf{z}_v \)
즉, 입력 graph의 특정 노드 \(v\)를 \(d\)차원의 임베딩으로 맵핑한다.
그리고, decoder(similarity function)는 다음과 같다.
\( \text{similarity}(u,v) \approx \mathbf{z}_v^\top \mathbf{z}_u \)
벡터공간에서의 관계를 네트워크에서의 관계로 맵핑한다.
Shallow Encoding
가장 단순한 encoder는 embedding-lookup 방식이다.
\( \text{ENC}(v) = \mathbf{z}_v = \mathbf{Z} \dot v \)
여기서 \(\mathbf{Z} \in \mathbb{R}^{d \mul \lvert \mathcal{V} \rvert}\)는 각 column이 학습할(optimize할) node embedding인 matrix이고, \(v \in \mathbb{I}^{\lvert \mathcal{V} \rvert}\)는 indicator vector로, node \(v\)를 나타내는 요소만 1이고 나머지는 모두 0인 벡터이다.
위 식은 look-up table에서 입력으로 주어진 index의 열만 출력하는 것이다.
각 노드마다 embedding vector가 생기므로 각 노드의 embedding을 직접적으로 optimize할 수 있지만, 노드의 수가 많아지면 look-up table의 size가 너무 커진다는 단점이 있다.
정리하자면,
Shallow encoder는 embedding lookup 방식으로 구성하고, 최적화할 parameter는 모든 노드(\(u \in V\))의 embedding \(\mathbf{z}_u\)로 이루어진 \(\mathbf{Z}\) 행렬이다.
Deep encoder에 대해서는 GNN을 다루면서 알아보도록 하자.
Node Similarity
Decoder는 node similarity를 기반으로 하며, 서로 비슷한 노드 쌍 \((u,v)\)에 대해 \(\mathbf{z}_v^top \mathbf{z}_u\)를 최대화하는 것이 목적이다.
여기서 중요한 점은, node의 유사도를 어떻게 정의할지이다.
두 노드가 유사할 조건으로는 연결되어있는지, 이웃 노드를 공유하는지, 비슷한 구조를 갖는지 등을 생각해볼 수 있는데, 여기서는 'random walks'라는 개념과 이 방법으로 측정한 유사도에 대해 어떻게 embedding을 optimize할지를 알아볼 것이다.
Node Embeddings의 특징
Node embedding의 학습은 unsupervised, 혹은 self-supervised learning이다. 노드의 label이나 feature를 사용하지 않으므로, 사람의 노동이 필요가 없다.
이러한 embedding들은 task에 독립적이다. 즉, 특정 task에 맞추어 학습되는 것이 아니라, 어떤 task에서든 사용이 가능하다.
Random Walk Approaches for Node Embeddings
노드 \(u\)의 임베딩 벡터를 \(\mathbf{z}_u\)라 하자. 모델은 노드 \(u\)로부터 시작해서 random walk를 진행하여 노드 \(v\)를 방문할 확률 \(P(v \vert \mathbf{z}_u)\)를 예측하게 된다.
Random Walk
앞서 언급했듯, random walk는 node similarity를 표현하는 방법이다.
Random walk 과정을 알아보자.
어떤 그래프가 주어졌을 때, 특정 노드에서 시작하여 이웃 노드로 랜덤하게 움직이며 방문한 노드들의 순서를 random walk라 한다.
옮기는 횟수(step 개수), 어떻게 옮겨갈지는 전략 \(R\)에 따라 달라진다. 여기서 단순히 이웃 노드를 랜덤으로(uniformly random) 고르고, 옮겨가는 과정을 반복하는 random walk 전략을 deepwalk라 한다.
또한, 그래프 \(G = (V, E)\)에서 노드 개수가 \(V\)개 이므로, 그래프 \(G\)에는 총 \(V\)개의 random walk가 있다.
만약 임의의 노드 \(u, v\)가 random walk 내에서 같이 등장할 확률이 높다면, 그 두 노드는 가까이 있다는 것을 의미한다. 두 노드 간에 엣지가 많거나, 경로가 짧기 때문에 자주 등장할 것이기 때문이다.
Random Walk Embeddings
이제 주어진 네트워크(그래프)에서 두 노드 \(u, v\)간의 유사도를 측정할 수 있다.
그래프에서 노드 쌍 \((u, v)\)의 유사도는 random walk를 통해 산출한 확률(random walk에서 같이 등장한 확률)로 계산할 수 있다.
그리고, 노드를 인코딩하여 근사하고자 하므로 다음과 같은 식으로 정리할 수 있다.
\( \mathbf{z}_u^\top \mathbf{z}_v \approx \text{Probability that } u \text{ and } v \text{ co-occur on a random walk} \)
정리하자면, 그래프(노드)의 유사도와 임베딩의 유사도에 따른 random walk embedding 과정을 다음과 같이 정리할 수 있다.
- Graph(Node) similarity : 노드 \(u\)에서 시작하여 random walk strategy \(R\)에 따라 노드 \(v\)를 방문할 확률을 추정한다.
- \(P(v \vert u)\)
- Embedding similarity : 이러한 random walk statistics를 인코딩한 임베딩을 최적화(optimize)한다.
- \(\mathbf{z}_u^\top \mathbf{z}_v \)
예를 들어, 아래 그림과 같이 embedding space에서 dot product(cosine)를 사용하여 random walk의 유사도를 인코딩한다.
최종적으로 모델은 두 유사도를 서로 근사시키는 방식으로 학습한다.
Random walk의 장점은 아래와 같다.
- Expressivity : node similarity를 확률적으로 정의하기 때문에 두 노드의 경로가 짧은 경우와 긴 경우 모두 이웃 노드에 대한 정보를 담을 수 있다.
- Efficiency : Training 과정에서 모든 노드를 고려할 필요 없이, random walk에서 동시에 등장하는 노드 쌍만 고려하면 된다.
Unsupervised Feature Learning
Feature learning이란, 노드의 유사도 정보를 포함하는 \(d\)차원 벡터(임베딩)를 찾는 것이다.
이를 위해서는, 네트워크에서 가까운 노드들은 임베딩 공간에서도 가깝도록 임베딩을 학습해야 한다.
그래프 \(G = (V,E)\)가 주어져 있다. 이때 목표는 mapping \(f:u \rightarrow \mathbb{R}^d\), 즉 함수 \(f(u) = \mathbf{z}_u\)를 학습하는 것이다.
이때 log-likelihood는 다음과 같다.
\( \underset{f}{\max} \sum\limits_{u \in V} \log{P(N_R(u) \vert \mathbf{z}_u)} \)
이때 \(N_R(u)\)는 random walk strategy \(R\)에 의해 얻은 이웃노드들이다. 쉽게 말해, random walk 중에 방문한 노드들이다.
식을 설명하자면, 노드 \(u\)가 주어졌을 때, \(N_R(u)\)인 노드들을 예측하는 feature representation을 학습하려 하는 것이다.
이제 optimization 과정을 살펴보자.
- 그래프에서 각 노드 \(u\)로 시작하여 strategy \(R\)을 갖는 random walk를 사용한다. (short fixed-length random walks)
- 각 node \(u\)에 대해 random walks에서 방문한 노드의 multiset \(N_R(u)\)를 구한다.
- 여기서 multiset이란, 같은 요소를 반복해서 가질 수 있는 set을 말한다. 한 node를 여러 번 반복해서 방문할 수 있기 때문에 이를 사용한다.
- Maximum-likelihood를 사용하여 Loss를 구한다.
- Stochastic gradient descent를 사용하여 loss를 최소화한다. (=embedding을 최적화한다.)
Maximum-likelihood
위의 log-likelihood에 maximum-likelihood 방법을 적용한 loss function은 다음과 같다.
\( \mathcal{L} = \sum\limits_{u \in V} \sum\limits_{v \in N_R(u)} - \log{(P(v \vert \mathbf{z}_u))} \)
노드 \(u\)가 random walk에서 방문한 노드 중 \(v\)와 동시에 발생할 likelihood를 최대화하도록 embedding \(\mathbf{z}_u\)를 최적화하는 개념이다.
여기서 \(P(v \vert \mathbf{z}_u)\)는 softmax 함수를 사용하여 다음과 같이 나타낸다.
\(P(v \vert \mathbf{z}_u) = \cfrac{\text{exp}(\mathbf{z}_u^\top \mathbf{z}_v)}{\sum\limits_{n \in V} \text{exp}(\mathbf{z}_u^\top \mathbf{z}_n)}\)
가능한 모든 노드 중에서 노드 \(v\)의 임베딩과 \(u\)의 임베딩이 가장 유사할 확률 개념이라고 볼 수 있다.
이를 위의 loss function에 대입하여 최적화를 한다면 \(N_R(u)\) 내의 노드는 내적값이 커지고, 아닌 노드는 내적값이 작아질 것이다. 즉, \(N_R(u)\)에 속하는 노드가 등장할 확률이 높아지도록 임베딩 벡터가 최적화될 것이다.
따라서 최종적으로 다음 loss function을 얻는다.
\( \mathcal{L} = \sum\limits_{u \in V} \sum\limits_{v \in N_R(u)} - \log{\left( \cfrac{\text{exp}(\mathbf{z}_u^\top \mathbf{z}_v)}{\sum\limits_{n \in V} \text{exp}(\mathbf{z}_u^\top \mathbf{z}_n)} \right)} \)
다시 한 번 식을 분석해보면, random walk에서 \(u\)와 \(v\)가 동시에 발생할 확률에 -log를 취하여 가능한 \(v\)와 가능한 \(u\)에 대해 모두 더하여 loss를 구한다.
Random walk embedding을 최적화한다는 것은 곧 \(\mathcal{L}\)을 최소화하는 embedding \(\mathbf{z}_u\)를 찾는다는 것이다.
하지만, 위 식과 같이 이중으로 summation(softmax에서 한 번, 최종 summation에서 한 번)을 하게 되면 알고리즘의 복잡도가 \(O(\lvert V \rvert^2)\)로, 계산이 매우 비효율적일 것이다.
따라서 log(softmax) 형태를 근사화하는 negative sampling 기법을 사용한다.
Negative sampling은 sigmoid function을 활용하여 softmax의 분모, 즉 normalization을 모든 노드에 대해 하는 대신, 랜덤으로 \(k\)개의 negative sample \(n_i\)를 뽑아 normalize한다. (정확한 증명은 여기서 다루지 않겠다.)
'실제로 \(u\)와 관련성이 적은 노드가 대부분일 텐데, 관련성 적은 노드 중 일부를 뽑아서 normalize하자'라는 아이디어를 사용한다.
\( \log{\left( \cfrac{\text{exp}(\mathbf{z}_u^\top \mathbf{z}_v)}{\sum\limits_{n \in V} \text{exp}(\mathbf{z}_u^\top \mathbf{z}_n)} \right)} \approx \log{\left( \sigma(\mathbf{z}_u^\top \mathbf{z}_v) \right)} - \sum\limits_{i=1}^k \log{\left( \sigma(\mathbf{z}_u^\top \mathbf{z}_{n_i}) \right)}, \quad n_i \sim P_V \)
k개 노드들은 random distribution \(P_V\)에 따라 샘플링하는데, negative node일수록(\(u\)와 상관 없는 노드일수록) 뽑힐 확률이 높아진다.
\(\sigma\)는 sigmoid function으로, 0과 1 사이의 값(확률 개념)을 갖도록 해준다.
따라서 앞의 sigmoid term은 \(u\)와 관련성이 큰 노드가 이웃 노드일 확률의 개념(최적화 시 높아짐)이고, 뒤의 sigmoid term은 \(u\)와 관련성이 적은 노드가 이웃노드일 확률의 개념(최적화 시 낮아짐)이다.
k는 보통 5~20개로 선택한다. 실제 데이터는 그래프의 노드 개수가 100만개가 넘어가는 경우도 많은데, 이에 비하면 이는 훨씬 적은 숫자이다. 이를 통해 계산을 효율적으로 할 수 있게 된다.
Stochastic Gradient Descent
Stochastic gradient descent는 gradient를 계산할 때 모든 example 대신, 이들을 mini batch로 나누어 loss 합을 최소화하는 과정을 반복한다.
Node2Vec
앞선 방법에서는 계속해서 단순한 strategy를 사용하는 random walk인 deepwalk에 대해 알아보았다.
하지만, node2vec은 random walk에서 좀 더 업그레이드된 전략을 사용한다.
Biased Walk
Node2vec은 유연하고 bias된 random walk를 사용하여 그래프의 local view와 global view 둘 다 적절히 살핀다.
위와 같은 예시에서 시작 노드 \(u\)에 대해 사이즈가 3인 \(N_R(u)\)를 구하는 과정을 알아보자.
만약 Breadth First Serach (BFS) 알고리즘을 사용한다면 \(N_{\text{BFS}}(u) = \{ s_1, s_2, s_3 \}\)일 것이고, 이는 그래프의 local view (microscopic view)를 얻는 역할을 한다.
반대로, Depth First Search (DFS) 알고리즘을 사용한다면 \(N_{\text{DFS}}(u) = \{s_4, s_5, s_6\}\)일 것이고, 이는 그래프의 global view (macroscopic view)를 얻을 것이다.
(BFS, DFS 알고리즘에 대한 자세한 설명은 링크를 참조하자.)
이렇게 \(N_R(u)\)를 얻는 과정에서 두 가지 parameter가 존재한다.
- Return parameter \(p\) : 이전 노드로 돌아갈 확률을 나타내는 parameter
- In-out parameter \(q\) : 밖으로 움직이거나(DFS), 안에서 움직이는(BFS) 경우를 나타내는 parameter, 즉 이전 노드에서 먼 노드로 갈 확률을 나타내는 parameter
- 직관적으로, \(q\)는 BFS와 DFS의 비율을 나타낸다.
위 그림에서, 현재 walk는 \(s_1\) 노드에서 \(w\) 노드로 이동한 상태라고 하자.
움직이는 경우를 예시의 색깔에 따라 세 경우로 나눠볼 수 있다.
- 파란색 : \(s_1\) 노드로 돌아갈 경우이다.
- 빨간색 : \(s_2\) 노드로 갈 경우, 이때 직전 노드(\(s_1\))간 거리가 현재 노드와 같다.
- 갈색 : \(s_3\) 혹은 \(s_4\) 노드로 갈 경우, 두 노드는 현재 노드보다 직전 노드와의 거리가 더 멀어진다.
각 노드로 이동할 확률분포는 그림과 같이 \(p\)와 \(q\)로 정해진다. BFS 형태의 walk는 \(p\)가 낮을수록 일어날 확률이 높아지고, DFS 형태의 walk는 \(q\)가 낮을수록 일어날 확률이 높아진다.
이떄 \(1, 1/p, 1/q\)는 정규화되지 않은 확률로, 겨우에 따라 여러 노드가 해당될 수 있기 때문에 분류 후에 정규화 과정을 진행한다.
과정을 요약하면, '\(w\)에서 각 노드까지의 거리 계산 → 거리마다 세 방향 중 어떤 방향인지 분류 → \(p, q\)에 대한 확률 정규화 → 확률에 따라 이동'의 과정을 거쳐 random walk를 진행한다. Random walk이긴 하지만, 확률 분포가 uniform이 아니라 \(p, q\)에 따라 bias되기 때문에 biased random walk라 부른다.
전체 알고리즘의 과정은 deepwalk에서와 비슷하다.
- Random walk 확률을 계산한다.
- 길이가 \(l\)인 random walk를 \(r\)번 진행한다.
- Stochastic Gradient Descent를 사용하여 node2vec objective를 최적화한다.
이는 시간복잡도가 linear하며, 세 단계 각각을 병렬적으로 진행할 수 있어 아주 빠르게 학습을 진행할 수 있다. 하지만 그래프가 커질수록 embedding 차원이 커진다는 단점이 있다.
지금까지 다룬 내용을 요약해보자.
핵심으로는 embedding space에서의 거리가 그래프에서 노드 간 유사도를 반영하도록 노드를 embedding하는 아이디어를 살펴보았다.
노드의 유사도를 나타내는 개념으로는 단순히 두 노드가 연결이 되었는가, 이웃 노드가 서로 겹치는가를 살펴보는 방법도 있지만, 이번에는 random walk를 사용한 방법을 알아보았다.
사실 세 가지 중 어떤 것이 가장 효율적인 방법인지는 task에 따라 다르다. 단, 일반적으로 random walk approach가 더 효과적이긴 하다. 어떤 task에, 어떤 application에 사용할지에 따라 적절한 방법을 선택해야 할 것이다.
Embedding Entire Graphs
다음으로, 노드가 아니라 graph 전체(혹은 subgraph)를 embedding하는 방법을 살펴보자.
Graph embedding의 목표는 전체 graph \(G\) 혹은 subgraph를 embedding space 상의 graph embedding \(\mathbf{z}_G\)로 맵핑하는 것이다.
Simple Ideas
가장 간단한 방법은 전체 graph 혹은 subgraph에 포함된 모든 노드에 대한 embedding을 구해 더하는(평균 내는) 것이다.
Embedding space에서 벡터의 위치는 상대적이므로, 모든 node embedding \(\mathbf{z}_v\)를 더하거나 평균내는 방법이다.
\( \mathbf{z}_G = \sum\limits_{v \in G} \mathbf{z}_v \)
또는 아래 사진과 같이 특정 subgraph를 하나의 가상 노드(virtual node)로 표현하여 임베딩하는 방법도 있다.
Anonymous Walk Embeddings
위의 간단한 방법들보다 발전된 방식으로, anonymous walk를 사용한다.
Anonymous walk란, 노드의 index를 지운 '익명'노드에 대한 random walk이다. Random walk를 진행한 순서에 따라 index를 매기게 되며, 중복으로 등장한 노드는 처음 등장했을 때의 index를 부여한다.
다음 예시를 보면 쉽게 이해할 수 있을 것이다.
위 예시에서 random walk 1과 random walk 2는 서로 다른 노드를 지났지만, index를 지우고 순서만 따져보면 같은 anonymous walk임을 알 수 있다.
이를 통해 각 노드의 정보는 사라지지만, 그래프의 구조는 파악이 가능하기 때문에 그래프를 embedding하는 데 유의미하다.
그리고 아래 표와 같이 anonymous walking embedding은 walk의 길이(length)에 따라 anonymous walk 개수가 지수적으로 증가한다.
| Length | Num of Walks | \(w_i\) |
| 2 | 2 | \(w_1 = 11, w_2 = 12\) |
| 3 | 5 | \(w_1 = 111, w_2 = 112, w_3 = 121, w_4 = 122, w_5 = 123\) |
| 4 | 15 | ... |
| 5 | 52 | ... |
| 6 | 203 | ... |
| 7 | 877 | ... |
Embedding vector를 생성하는 과정은 다음과 같다.
- \(l\) step에 대해 anonymous walks \(w_i\)를 실행하고, 해당 walks의 빈도를 센다.
- Embedding vector \(\mathbf{Z}_G\)의 \(i\)번째 element를 walk \(w_i\)가 나온 확률로 할당한다.
예를 들어, \(l = 3\)이면, graph를 5차원의 벡터로 나타낼 수 있다.
그래프를 walk \(w_i\)에 대한 확률분포로 표현하기 위해서는 여러 번의 anonymous walk를 독립적으로 수행해야 한다.
샘플링 횟수를 \(m\)이라 할때, 적절한 실행 횟수를 구하는 식은 다음과 같다.
\( m = \left \lceil \cfrac{2}{\epsilon^2} \left( \log{(2^\eta - 2)} - \log{(\delta)} \right) \right \rceil \)
식의 잘린(?) 대괄호같이 생긴 것은 ceil(올림)이다. 참고로 floor(내림)는 \(\left \lfloor \cfrac{a}{b} \right \rfloor\)로 표현한다.
\(\epsilon\)은 오차 하한, \(\delta\)는 오차 상한, \(\eta\)는 길이가 \(l\)일 때의 총 anonymous walk 개수이다.
(The distribution has error of more than \(\epsilon\) with probability less than \(\delta\).)
Learning Walk Embeddings
Walk embedding을 학습한다는 것은, 위에서는 단순히 walk의 빈도를 통해 embedding vector를 구했는데, 각 walk도 embedding하여 사용하는 방법이다.
즉, 모든 anonymous walk embedding \(\mathbf{z}_i\)를 모아 graph embedding \(\mathbf{Z}_G\)를 학습한다.
\(\mathbf{Z} = \{ \mathbf{z}_i : i = 1, \dots, \eta \}\)
여기서 \(\eta\)는 샘플링된 anonymous walk의 개수이다.
Walk를 임베딩하는 핵심 아이디어는 '\(w_{t - \Delta}\)부터 \(w_{t + \Delta}\)까지의 walk로 \(w_t\)를 예측'하는 것이다. (여기서 \(\Delta\)는 window size이다.)
예시와 함께 자세히 살펴보자.
예를 들어, 위 사진과 같은 input graph의 vector parameter를 \(\mathbf{z}_G\)라 하자.
보라색 노드를 node 1로 두고, node 1로부터 anonymous sample walk를 샘플링한다. 예를 들어, 다음과 같이 샘플링했다고 하자.
다음으로, \(\Delta\) 사이즈의 window 내에서의 walk를 예측하도록 학습시킨다. 예를 들어, \(\Delta = 1\)이면, \(w_2\)를 예측하기 위해 \(w_1, w_3\)를 사용한다.
따라서 objective는 다음 식으로 나타낼 수 있다.
\( \max \sum\limits_{t=\Delta}^{T - \Delta} \log{P(w_t \vert w_{t-\Delta}, \dots, w_{t+\Delta}, \mathbf{z}_G)} \)
Learning Process
전체 학습 과정은 다음과 같다.
1. 시작 노드가 \(u\)이고, length가 \(l\)인 \(T\)번의 서로 다른 random walk를 수행한다.
이때의 \(N_R(u)\)는 이제까지의 이웃 노드 집합 개념이 아니라, 노드 \(u\)에서 시작한 random walk의 집합이다.
\( N_R(u) = \{ w_1^u, w_2^u, \dots, w_T^u \} \)
2. \(\Delta\) 사이즈의 window 내에서 walk를 예측하도록 학습한다.
Anonymous walk \(w_i\)의 embedding \(\mathbf{z}_i\)를 추정한다. 여기서 \(\eta\)는 모든 가능한 walk embedding의 수이다.
이때 목적함수는 다음과 같다.
\( \underset{\mathbf{Z}, d}{\max} \cfrac{1}{T} \sum\limits_{t=\Delta}^{T - \Delta} \log{P(w_t \vert \{ w_{t - \Delta}, \dots, w_{t + \Delta}, \mathbf{z}_G \} )} \)
이전과 같은 방법으로 softmax 함수를 이용하여 모든 가능한 walk에 대한 t번째 walk의 확률을 구할 수 있다. (이후 negative sampling을 사용하고, optimization 하는 과정은 똑같다.)
\( P(w_t \vert \{ w_{t-\Delta}, \dots, w_{t + \Delta}, \mathbf{z}_G \} ) = \cfrac{\text{exp}(y(w_t))}{\sum_{i=1}^\eta \text{exp}(y(w_i))} \)
이러한 walk embedding의 학습과정은 다음 수식으로 나타낼 수 있다.
\( y(w_t) = b + U \cdot \left( \operatorname{cat} \left( \cfrac{1}{2 \Delta} \sum_{i=-\Delta}^{\Delta} \mathbf{z}_i, \mathbf{z}_G \right) \right) \)
즉, random walk 벡터들을 평균을 낸 후에 graph 벡터와 concat되어 입력값으로 들어가고, 이를 통해 \(w_t\)를 추정하는 것이다. 또한 \(b \in \mathbb{R}, U \in \mathbb{R}^D \)는 학습할 parameter이다. (위 수식은 linear layer임을 알 수 있다.)
이 개념을 제안한 Anonymous Walk Embeddings라는 논문에서는 단어 벡터를 이용해 문단 벡터를 생성하는 NLP 분야의 논문 'Distributed Representations of Sentences and Documents'를 차용하여 이 학습 방법을 고안했다.
NLP 논문에서는 다음 그림처럼 동일한 문단에서 나온 단어와 해당 문단의 벡터를 concat 및 average하여 중심 단어를 예측한다.
위에서의 '단어-문단'의 관계와 같이, 'random walks - graph'의 관계를 통해 \(t\)에서의 random walk를 예측하는 것으로 보면 된다.
3. 2에서 optimization을 거치면 그래프 전반적인 정보를 인코딩한 graph embedding \(\mathbf{z}_G\)을 얻는다. 이를 학습할 parameter로 하여 graph classification 등의 예측 task에 사용한다.
Task에 사용하기 위한 방법은 두 가지가 있다.
먼저, 앞선 포스팅에서 다루었던 traditional ML의 경우에는 두 그래프에 대한 inner product kernel \( \mathbf{z}_{G_1}^\top \mathbf{z}_{G_2} \)을 사용한다.
또한, \(\mathbf{z}_G\)를 nerual network의 입력으로 사용하는 방법도 있다. 이는 차후에 GNN을 배우면서 알아볼 것이다.
How to Use Embeddings
Node embedding \(\mathbf{z}_i\)는 다음과 같은 task에서 사용할 수 있다.
- Clustering, Comunity Detection : Cluster point로 \(\mathbf{z}_i\) 사용한다.
- Node Classification : \(\mathbf{z}_i\)를 기반으로 node \(i\)의 label을 예측한다.
- Link Prediction : \(\mathbf{z}_i, \mathbf{z}_j\)를 기반으로 edge \((i, j)\)를 예측한다.
- 이때 두 embedding에 대한 concat, Hadamard, sum, avg, product, difference, distance 등을 사용할 수 있다.
Node embedding을 합(평균)하거나, anonymous random walk를 사용하여 얻은 graph embedding \(\mathbf{z}_G\)는 다음과 같은 task에 사용한다.
- Graph Classification : Graph embedding \(\mathbf{z}_G\)를 기반으로 graph의 label을 예측한다.
최근댓글