[CS224W] 7. Graph Representation Learning

7강은 신민정님께서 리뷰하셨습니다. Graph에 Machine Learning을 이용하기 위한 개념과 방법론이 쏟아져나오는 강의이기 때문에 정신을 바짝 차리고 들어야했습니다. 복습도 굉장히 오랜시간이 걸립니다.

목차

0. Intro
1. Embedding Nodes
2. Random Walk Approaches to Node Embedding
- Basic
- Node2Vec
3. Translating Embeddings for Modeling Multi-relation Data
4. Embedding Entire Graphs

0. Intro

Representation Learning

representation learning이란 어떤 task를 수행하기에 적절하게 데이터의 representation을 변형하는 과정을 학습하는 것입니다. (컴퓨터는 사람이 아니라는 것을 항상 기억하세요)

Machine Learning Lifecycle 은 다음과 같습니다. 이 때 Raw data 에서 Feature Engineering을 거치지 않고 pipiline을 구축 가능하도록 하는 것이 딥러닝의 핵심입니다.

Feature Learning in Graphs

Feature Engineering 과정을 Automatically learn the features로 수행하기 위해서 Graph의 구조를 vector로 바꾸는 Embedding (feature represention) 과정을 거치게 됩니다. 그림으로 이해하는 것이 더 쉬울 것 같습니다.

우리는 왼쪽의 그래프를 가지고 있기 때문에 이 그래프를 모델에 input으로 넣어주기 위해서 mapping 함수 f를 사용해서 d-dimension의 vertor로 바꿔줄 것입니다.

많은 방법이 있고, 인접행렬(adjacency matrix)를 사용하는 것도 하나의 방법이겠지만, 인접행렬은 노드 갯수만큼의 차원을 가진 고차원의 행렬이기 때문에 사용에 어려움이 있습니다. 따라서 각 노드를 low-dimensional space에 mapping하는 방법에 대해서 알아보겠습니다.

process

이 때 그래프는 이미지 데이터처럼 일정한 grid 형식도 아니고, text나 음성처럼 sequence 데이터도 아니기 때문에 Embedding 하는 방법이 어렵습니다.

• Complex topographical structure
• No fixed node ordering or reference point (i.e., no spatial locality like grids) -> 고정 노드 순서를 정할 수 없음
• Often dynamic and have multimodal features.

---

1. Embedding Nodes

Goal : 원래 네트워크에 있는 similarity(유사성)에 근사하게 embedding space에 인코딩(embedding)하는 것!

ex. 원래 네트워크에서 a노드와 b노드가 유사하다면 embedding space에 mapping했을 때도 a,b노드는 서로 유사해야합니다

• graph G
• vertex(node) set V
• adjacency matrix A (assume binary)
• node feature나 그 외의 추가 정보는 고려하지 않음

노드의 유사성(similarity)에 대한 정의는 dot product로 측정합니다. -> ENC(u), ENC(v)

Learning Node Embedings

1. Define an encoder (a mapping from nodes to embeddings) -> encoder 정의
2. Define a node similarity function (a measure of similarity in the original network) -> 노드 유사성을 구하는 함수 정의
3. Optimize the parameters of the encoder so that : similarity(u,v) -> encoder의 파라미터 최적화

Encoder

각 node를 low-dimensional vector로 mapping해준다.

가장 쉬운 encoding 방법은 shallow encoding

• v : node in the input graph
• z_v : d-dimensional embedding (d차원은 empirical proof 이용)

Shallow Encoding

가장 쉬운 encoding 접근법으로 encoder는 그냥 embedding-lookup 이다. (참조하는 해시테이블에 불과, 이해가 안된다면 lookup table 개념을 찾아보면 됩니다.)

각 노드당 한 column의 unique vector로 임베딩합니다.

이외의 방법으로는 DeepWalk, node2vec, TransE 등이 있습니다.

Similarity function

: specifies how the relationships in vector space map to the relationships in the original network

어떻게 node similarity를 정의할지가 핵심인데 이 때 많은 고려사항들이 있습니다.

• 두 노드가 연결되어있는지?
• 두 노드가 이웃을 공유하는지?
• 두 노드의 구조적 역할이 비슷한지?

---

2. Random Walk Approaches to Node Embedding

위에서는 가장 간단한 임베딩 방법론 shallow embedding에 대해서만 다뤘다면, 이번에는 Random Walk를 사용한 방법론에 대해서 보겠습니다.

위에서 언급한 DeepWalk, node2vec이 관련있습니다.

• DeepWalk: Online Learning of Social Representations arxiv.org/pdf/1403.6652.pdf
• .node2vec: Scalable Feature Learning for Networks cs.stanford.edu/~jure/pubs/node2vec-kdd16.pdf. KDD.

2-1. DeepWalk

Random Walk

Random Walk란 말 그대로 node위를 random하게 선택해서 이동하는 것을 말합니다. 시작노드(starting point)를 정하고 random하게 neighbor를 선택해서 거쳐가는 point를 sequence로 이용합니다.

ex. random walk 4걸음 -> [4,3,2,8,5]

z_.T z_v = probability that u and v co-occur on random walk over the network
-> similarity(u,v) 는 network에서 u와 v가 동일한 random walk 의 경로에 있는 확률로 근사합니다. (함께 발생)

Random Walk Embedding Process

1. node u에서 시작한 random walk에서 node v를 방문할 확률을 random walk strategy R을 사용해서 계산합니다. (조건부확률로 추정)

2. 이 확률 P(v|u)를 encoding하기 위해 embedding을 최적화 시킵니다. (유사도계산 -> cos(θ) 사용)

Random Walk Optimization

Graph에서 Unsupervised Feature Learning에 대해서 상기하고 objective function을 정의한 후에 optimize 과정을 살펴보겠습니다.

Unsupervised Feature Learning

• intuition : similarity를 보존하면서 d-dimension인 node Embedding 값을 찾아보자
• Idea : 네트워크에서 node끼리 가깝다면 node embedding 도 이를 학습해야한다
• 이웃 노드의 정의 : node u 가 주어졌을 때, 근처 노드를 어떻게 정의할 것인가?
  • N_R(u) : strategy R로 얻을 수 있는 node u 의 이웃 노드

Objective Function

node u가 주어질때, 우리는 근처 이웃노드 N_R(u)를 예측할 수 있는 feature representation을 학습하기 원합니다. 이때 objective function은 Log-likelihood objective를 사용해서 다음과 같이 나타냅니다. node를 임베딩 시킬 수 있는 mapping(z)을 배우는 것입니다.

Random Walk Optimization

1. graph 위의 각 node에서 strategy R을 이용해서 short fixed-length random walks(짧은 거리의 이동)를 시작합니다.
2. 각 node u에서 random walk로 방문한 node들을 모아서 N_R(u), 이웃노드 집합을 가지게 됩니다.
3. node u 가 주어질 때, 그 노드의 이웃노드 N_R(u)를 예측하도록 Optimize embedding을 수행합니다. (objective function은 위에서 살펴본 것과 동일)

Loss function은 random walk co-occurrences(random walk의 동시 발생 수)의 최대우도를 최적화하는 것입니다.

(Optimize embeddings to maximize likelihood of random walk co-occurences)

이 때 파라미터 P(v|z_u) 는 어떤 노드가 가장 비슷한지 확률처럼 사용하기 위해 softmax를 사용합니다.

따라서 모두 대입한 공식은 오른쪽과 같습니다.

Optimizing random walk embeddings = Findeing embeddings z_u that minimize L

-> random walk embeddings 을 최적화하는 것이 loss function L을 최소화시키는 embedding 값 z_u를 찾는 것과 동일합니다.

-> 그런데 여기서 이 Optimization 방식을 naive하게 가져가는 것이 computation 측면에서 expensive해서 Negative Sampling을 한번 이용해줍니다. (직관적으로 네트워크에 있는 모든 노드 u에 대해서 loss function을 모두 계산 해줄때, softmax 를 사용한 부분이 많은 연산량을 필요로하기 때문에 당연한 선택인 것 같습니다. 근사적으로 해결하는 방법을 사용합시다.)

연산량이 많은 곳(log 안 연산)을 근사함으로써 해결했습니다. random으로 Negative sample(n_i)들만을 Sampling해서 이용합니다. (표본을 샘플링해서 만든 분포가 전체 분포라고 가정~하고 사용하는 방식)

negative node, sample k는 차수에 비례하는데 k를 정할 때 두 가지 고려사항은 다음과 같습니다.

• Higher k gives more robust estimates (많이 쓸 수록 전체를 사용한거니..)
• Higher k corresponds to higher bias on negative events in practice k = 5~20 (k가 높다는 것은 negative events에 대한 bias가 크다는 것입니다. 보통 경험적으로 5~20으로 설정해서 사용합니다.)

Random walk advantages

random walk의 장점으로는 크게 표현력이 뛰어나다는 것과 효율성이 좋다는 것이 있습니다.

• Expressivity : local 정보와 고차원의 이웃정보를 모두 포함하는 node similarity를 확률적으로 유연하게 설명합니다.
• Efficiency : training시에 모든 node pair들을 고려하지 않습니다 (쌍대비교 x). random walk에서 동시에 발생한 pair들만 고려하기 때문에 매우 큰 그래프에서의 사용이 가능합니다. 따라서 수십억개의 노드가 있는 real world에 적합합니다.

Random walk strategy

지금까지 random strategy에대해서 R이라고 표기하고 구체적인 방법은 설명하지 않았습니다. 이 strategy에는 다양한 방법이 있는데 가장 간단한 것이 위에서 잠깐 봤던 'run fixed-length, unbiased random walks starting from each node' 이며 다양한 방법이 있을 수 있습니다.

random walk의 길이를 고정 해놓는 방식은 노드 주변을 멀리 볼 수 없기 때문에 멀리 있는 노드끼리 유사성을 가진 경우 임베딩이 불가능하고, random으로 인해서 graph의 전체 structure을 고려하지 못한다는 단점이 있습니다.

따라서 다양한 방법론(좀 더 일반화된 방법론)으로 node2vec에 대해서 알아보겠습니다.

---

2-2. node2vec

node2vec

큰 목표는 네트워크 안에 비슷한 이웃 노드끼리 가까운 feature space에 mapping 되도록 Embed nodes를 구하는 것으로 node Embedding의 목표와 동일합니다. 여기에 추가적으로 다양한 task에 적용이 가능하도록 downstream prediction task에 독립적으로 만드는 것이 목적입니다.

핵심은 네트워크에서 node u의 이웃의 개념이 각 node embedding에 유연하게 이어지는 것입니다. (대충 유연하게 이웃개념을 잘 임베딩할 수 있다는 말)

Idea : use flexible, biased random walks that can trade off between local and global views of the network

• 유연하게 biased random walk를 사용해서 네트워크의 local과 global의 trade off를 찾습니다.
• 주어진 node u의 이웃 노드 N_R(u)를 찾는 전략으로 BFS와 DFS를 사용합니다. BFS는 local view를, DFS는 global view를 봅니다. (그림이 이해가 쉽습니다.)

parameter : biased fixed-length random walk R 에서는 두 가지 파라미터 p,q를 다음과 같이 정의해서 사용합니다.

• p : 이전 노드로 돌아가는 가능성을 계산 -> p가 낮을수록 좁은 지역 고려
• q : DFS와 BFS의 비율, random walk가 얼마나 새로운 곳을 잘 탐색하는지 -> q가 낮을 수록 넓은 지역 고려

Example : walk가 어디에서 어디로 진행되는지 주목해서 다음 예시를 보겠습니다.

(s1,w) 경로로 이동해서 지금 w노드에 있는 상태입니다.

node w 의 neighborhood는 s1,s2,s3이고 s2와 s1은 공통 이웃 노드로 w를 가지고 있습니다.

s3 방향으로 간다면 s1,s2와는 반대방향으로 멀어지게 됩니다.

위에서 배운 p와 q의 개념을 바탕으로 각 확률 1/p, 1/q를 계산합니다.

(s1,w) 경로로 이동해서 지금 w노드에 있는 상태에서 다음은 어디로 가면 될까요? 지금까지의 과정이 node2vec의 random walk probability를 계산하는 것 까지의 과정이고 이 후, random walk를 진행 후 node2vec을 SGD로 최적화 합니다. 3단계가 독립적으로 병렬처리가 가능해서 Linear-time complexity를 가집니다.

node2vec algorithm

1. Compute random walk probabilities
2. Simulate r random walks of length l starting from each node u
3. Optimize the node2vec objective using Stochastic Gradient Descent

지금까지가 Node Embedding 중 Random walk를 이용한 방법론들 DeepWalk, node2vec이었습니다.

---

3. Translating Embeddings for Modeling Multi-relational Data (TransE)

Knowledge Graph(KG)의 node들을 embedding할 수 있는 TransE에 대해서 알아보겠습니다.

Knowledge Graph

Knowledge graph는 entity간의 상호관계에 대한 사실/상태로 이뤄진 그래프입니다. (데이터베이스에서 배우는 관계형 데이터 베이스(ERD)를 생각하면 편할 것 같습니다. entity와 relationship 개념이 존재합니다. Node = entity, edge = relation)

knowledge graph에 대해서는 Link Prediction에 대한 연구가 활발합니다. entity(node)간의 관계인 relation(edge)에 대해서 놓치고 있는것이 있다면 이로 인해 많은 정보가 누락되기 때문입니다.

intuition : 따라서 KG의 local&global connectivity를 잘 학습해서 link prediction을 하는 model을 만드는 것이 목적입니다.

downstream task : 관심있는 노드와 이 외의 모든 Entity간의 관계를 학습된 패턴을 사용해서 일반화 시킵니다. 일반화함으로써 relation prediction을 할 수 있습니다.(relation predictions are performed by using the learned patterns to generalize observed relationships between an entity of interest and all the other entities.)

Translating Embeddings (TransE)

1. TransE는 entity들의 관계를 triplets으로 표현합니다. -> (h,l,t)

• h : head entity
• l : relation
• t : tail entity

2. Entity들이 먼저 entity space R^k에 embedding 됩니다. (이전 방법들이랑 비슷하게)

3. Relation들이 translations으로 표현됩니다.

• h + l ≈ t, if the given fact is true ⁡
• else, h + l ≠ t

강의에서는 이 과정을 각각 애니메이션으로 벡터가 변화하는 과정을 보여줍니다. 다른 알고리즘의 문제를 해결하거나 더 좋다보기보다는 지식기반그래프 KG에서 사용하는 점이 핵심인 알고리즘 같습니다.

전체 알고리즘은 다음과 같습니다.

---

4. Embedding Entire Graphs

지금까지는 node embedding에 대해서 배웠습니다. 그래프의 노드를 어떻게 embedding space의 vector로 더 잘 표현할 것인가, 어떻게 노드가 가진 이웃과의 관계 정보(유사성)을 포함시켜서 표현할 것인가를 중점적으로 봤습니다.

이번에는 Graph G를 통채로 embedding 하는 방법, 전체뿐만 아니라 sub-graph를 한 point로 임베딩하는 방법을 보겠습니다.

전체 그래프 G를 임베딩하는 것이 목표이기 때문에, 이 결과는 toxic vs non-toxic molecules 의 분류, 비정상적인 그래프 식별 등의 task에 이용할 수 있습니다.

Graph embedding에 대한 3가지 접근을 보겠습니다.

Approach 1. 가장 간단한 방법

(sub)graph G의 각 node를 embedding하고(ex.Deep Walk, node2vec...) 그 embedding값을 모두 더하거나 평균을 내어 graph embedding을 할 수 있습니다.

즉 각 node embedding 결과를 단순 집계하여 사용합니다.

Approach 2. graph -> node

(sub)graph를 대표하는virtual node(super-node)를 만들고, 그 node를 embedding값을 (sub)graph의 embedding으로 사용할 수 있습니다.

즉 network를 sub graph로 묶어서 super node를 만듦으로써 간소화 시켜서 node embedding 합니다.

Approach 3. Anonymous Walks Embedding

Anonymous Walk는 random walk를 하는데 어느 node를 지나왔느냐가 아닌, 지나온 순서를 고려하는 random walk입니다. random walk를 진행하고 그 발자취의 순서(index)를 Anonymous Walk라고 합니다.
Anonymous Walk의 결과로 embedding하는 것을 Anonymous Walks Embeddings이라고 합니다.

-> 이 방법은 length에 따라 walk수가 폭발적으로 늘어납니다.

-> 3번째 접근법에 대해서도 3가지 다른 idea가 있는데 생략합니다. (아래에 간단히 적혀있습니다.)

3가지 방법 정리

Reference

Stanford CS224W 2019
스터디 7강 리뷰 자료 velog.io/@tobigs-gnn1213/7.-Graph-Representation-Learning#4-embedding-entire-graphs

7. Graph Representation Learning