Chapter7. Graph Representation Learning

CS224W 7강 by 신윤종

Graph Representation Learning

Intuition : Graph에는 다양한 Downstram Task가 존재한다.

1. Node Classification

2. Link Prediction

3. Clustering

4. Anomaly Detection

5. ...

이 때, 여느 Machine Learning Lifecycle과 같이 Feature Engineering이 동반되고 우리는 Task Independant한 Automatic Feature Learning을 바라게 된다. 결국 Graph의 한 Node를 어떻게 Feature로써 표현할 수 있을까? 라는 질문에 도달한다.

Idea : Graph를 임베딩 하자

Node Embedding

Network Embedding을 한다는 것은 각 Node를 Low-Dimension Space에 Mapping한다는 것을 뜻한다. Adjacency Matrix 희소행렬이고, 계산량이 많다는 문제점이 있어서 이를 더 낮은 차원의 Latent Matrix로 만들어 효과적 Representation을 수행한다.

Network Embedding

그러나 Network Embedding은 기존 Deep Learning의 것과 차이점이 존재한다. 기존의 Data는 고정된 이미지(Grids)이거나 문자(Sequences)같은 형태의 비정형 데이터를 처리하지만, 네트워크는 좀 더 복잡하다.

• 네트워크는 유클리드 공간에 있지 않다. 쉽게 말해서 좌표계로 표현할 수 없어 CNN같이 Filter를 이동하면서 학습할 수 없다.

• 네트워크는 고정된 형태가 아니기 때문에, 얼마든지 뒤집거나 순서를 섞어도 네트워크에 영향을 주지않는다. 고정되있지 않기 때문에 데이터로 표현하기 어렵다.

Complex topographical structure of network

Embedding Nodes

Idea : Node를 Encode해서 Embedding Space에 Mapping한다.

Embedding Space에서 각 Representation은 Similarity로 관계를 나타낸다. Embedding의 과정은 다음과 같다.

1. Encoder를 정의한다. Node Embedding을 Mapping을 실질적으로 실행한다.

   $ENC(v) = z_v$

2. Similarity Function을 정의한다. 코사인 유사도가 그 예이다.

3. Encoder의 파라미터를 최적화 한다.

Learning Node Embeddings

Shallow Encoding

가장 간단한 Encoding 방식은 Look-up table을 사용하는 것이다. 각 Node는 One-hot Encoding으로 표현 되어 Look-up table의 Representation을 가리키는 Indicator로써 작동한다. (Word2Vec과 매우 흡사하다!)

Look-up Table

이런 방식을 차용하여 다양한 Embedding 방법론들이 연구되었다. (DeepWalk, node2vec, TransE) 어떤 방법론을 선택할지는 어떤 Node Similarity를 사용하느냐에 따라 다르다.

• Edge가 연결되는가?

• 서로 이웃을 공유하는가?

• Structural Role이 비슷한가?

이번 강의에서 다양한 Embedding Methods를 배울 예정이니 기대하시라.

Random-walk Approaches to Node Embeddings

Random-walk

Graph에서 특정 시작 Node($u$) 에서 랜덤으로 이웃($v$)을 선택하여 이동한다. 방향은 자유로우며 설정한 횟수만큼 움직인다. 따라서 같은 Node를 여러번 마주칠 수도 있다.이동하면서 만났던 Node들($z_ v$)은 시작 Node의 이웃으로 간주하고 Representation을 학습한다. 이 때, 이동을 무작위로 할 수도 있고, 별개의 Strategy $R$를 사용할 수도 있는데, 이는 뒤에서 다시 다룬다.

Random-walk Embeddings

Why Random-walks ?

1. Expressivity : 확률 정의에 따른 인접 이웃 정보를 유연하게 표현할 수 있다.

2. Efficiency : Embedding과정에서 모든 Node pair를 고려할 필요가 없으므로 계산량을 효과적으로 줄인다. 간단하면서도 매우 강력한 기능이다.

Random-walk Optimization

1. strategy $R$을 사용하여 고정된 횟수만큼 무작위로 이동한다.

2. 매 Node$u$마다 이웃 Node의 multiset$N_R(u)$를 저장한다.

3. 목적함수에 따라 $u$가 주어졌을 때 $N_R(u)$를 예측하는 Embedding을 학습한다. 즉 Loss $L$ 을 최소화하는$z_u$ 를 학습하는 것이다.

Feature Learning as Optimization

Loss Function

Random-walk Optimization

Negative Sampling

Random-walk를 통한 Graph Embedding에는 계산량이 너무 많다는 단점이 있다. 계산과정을 살펴보자면 2중 반복문으로 Softmax를 구할 때 분모에서는 모든 Node 별 확률 가중합을 진행하게 된다. 따라서 Word2Vec에서 쓰이는 Negative Sampling을 Graph Embedding에 적용한다. 다만, Word2Vec에서는 단어 빈도에 따라 Negative Sampling될 확률에 가중치를 준다.

노드의 샘플링 확률은 Degree에 비례해 준다고 하는데 수식은 강의에 없다.(Deewalk이랑 node2vec에도 없는데?) 다른 Graph Embedding논문을 찾아보니 Word2Vec의 수식과 같아보였다. (Robust Negative Sampling for Network Embedding, 2019,M Armandpour et al.)

파라미터 k가 의미하는 바는 다음과 같다.

1. k가 높을 수록 robust estimates를 제공한다?

2. k가 높을 수록 학습이 negative events에 편향된다. 단순히 negative sample을 많이 가져가는큼 bias를 가진다고 받아들였다.

일반적으로 k의 범위는 5~20 사이로 설정한다고 한다.

Negative Sampling

Q. 왜 직접적인 이웃으로 Embedding 안하고 Random-walk를 하는가?

A. 이유는 2가지로 첫 째는 다들 알다시피 계산량이다. degree가 수 천, 수 백만이면 too expensive하다. 둘 째는 인접 n까지만 보면 Graph Search라는 관점에서 제한적이기 때문이다.

node2vec

Vanila Random-walk : 고정된 길이만큼 무작위로 걍 걷자 -> 먼 거리까지 나갈 확률이 제한적이다.

이 논문에서는 기존 Random-walk의 단점을 커버하기 위하여 biased 2nd order Strategy $R$을 제안한다.

Idea : Graph의 지역적 view와과 전역적 view를 전부 고려할 수 있는 유연한 biased Random-walk를 사용하자

node2vec에서는 지역적 view를 BFS(넓이 우선 탐색)로, 전역적 view를 DFS(깊이 우선 탐색)으로 Random-walk를 시행한다. 이 둘은 Trade-off 관계로, BFS의 경우 가까운 이웃을 잘 찾을 수 있으며 DFS의 경우 Graph의 다른 Structure까지 탐색할 수 있다.

node2vec : Biased Walks

• Two Parameters

  • Return parameter $p$: 바로 이전 Node로 돌아간다.

  • In-out parmater $q$: DFS 또는 BFS를 선택하는 비

Biasd Random-walk

Biased Random-walk parameters

도표 보면 w에서 $S_2$로 가는 평범한 Random-walk의 확률은 1이다. 이와 달리 회귀하는 확률 Return $p$값은 1/p의 확률로 나타낸다. 즉, $p$가 작을 수록 회귀할 확률이 높아진다. 반대로 $q$의 경우 값이 작아질 수록 멀리 나아갈 확률이 높아진다.

Translating Embeddings for Modeling Multi-relational Data

Knowledge Graph

Knowledge Graph

지식 그래프는 Node를 Entity로, Edge를 Relation으로 표현하며, Relation의 타입은 일반적 Graph와 달리 다양할 수 있다. 이러한 KG에 있어 Incompleteness는 System에 부정적 영향을 크게 미친다고 한다. 따라서 Link Prediction Task가 KG에서 중요하다.

Translating Embeddings

TransE는 Entity 3개의 관계를 Triplets로 표현되는 Repesentation이다. 이들은 Entity Space에 이전에 배운 방법론들을 사용하여 Embedding된다. 이렇게 Entity에서 Relation Space로 매핑되는 것을 논문서는 Translation이라고 소개한다.

https://youtu.be/2XFMAdHa8uY?list=PL1OaWjIc3zJ4xhom40qFY5jkZfyO5EDOZ&t=4155

$h (headentity), l (relation), t (tailentity) → (h, l, t)$

TransE

TransE Learning Algorithm

학습 과은 다음과 같다.

1. 하나의 $l$에 대하여 Positive sample과 Negative Sample을 선택한다. Positive Sample은 정상 Triplet이고, Negative Sample은 억지로 만든 틀린 Triplet이다.

2. 목적함수에 따라 Embedding을 업데이트 시킨다. node2vec에서는 Pos Sample의 내적이 커지고 Neg Sample 내적을 작게만들었다면, 여기서는 Pos Sample Translation의 거리를 최소화하고, Neg Sample Translation의 거리를 최대화 한다.

학습 결과가 수렴하는 양상을 띠면 Embedding이 완료되었다고 볼 수 있겠다.

Embedding Entire Graphs

단어 임베딩이 있고, 더 나아가 문서 임베딩이 있듯이 Node Embedding을 넘어선 Graph Embedding도 고려해볼 수 있다.

Graph Embedding

한 가지 간단한 방법은, Graph 전체 Node의 Representation을 Sum때리거나 Mean때리는 것이다. 이 방법이 실제로 유용하게 쓰였다고 한다.

둘 째로 Graph를 대표로 설명하는 Virtual Node를 설정하여 Embedding 시키는 방법이다.

2nd Approach of Graph Embedding

마지막은 Anonymous Walk방법이다.

1. Graph에서 랜덤한 노드부터 시작해서 Random-walk를 시행한다.

2. Random-walk의 모든 경로를 저장한다. (엄밀히 말하면 Unique Node의 Index이다)

3. Index의 리스트가 해당 Graph의 Representation이 된다.

Anonymous-walk

거대한 Graph 전체를 Random-walk로 Embedding하기란 불가능에 가깝다. 어차피 Graph Embedding에서 강조했던 것은 효율성 아닌가? 그래서 이러한 방법을 차용했다.

이제 실제로 Anonymous-walk을 통한 Graph Embedding은 다음과 같다.

1. Anonymous-walk를 t만큼 진행한다. 그리고 예측할 i째 Embedding을 선택한다.

2. Graph의 id값과 나머지 window 만큼의 Anonymous-walk Representation을 Mean때리든지 Concat한다.

3. 똑같은 Graph의 타겟 Anonymous-walk를 예측하여 Loss를 구하고 Back-prop한다.

Training Anonymous-walk

Learn Walk Embeddings