CS224W - 07.Graph Representation Learning

CS224W의 7주차 강의, Graph Representation Learning을 보고 정리한 글입니다.
1. Graph Representation Learning
2. Embedding Nodes
3. Random Walk Approaches to Node Embeddings
4. Translating Enbeddings for Modeling Multi-relational Data
5. Embedding Entire Graphs

Graph Representation Learning

Representation Learning: Graph 도메인에도 적용가능!
앞에서 Node Classification Task를 수행했다면
Link Prediction Task 또한 가능!!

일반적인 ML Lifecycle

Feature Engineering에 상당한 노력을 쏟아부음

Raw data  --->   Structured Data  ---> Learning Algorithm ---> Model  
         Feature                       ------------------------------>           
        Engineering                             Downstream 
                                                   task 

Feature Engineering이라는 Painful한 과정을 생략하고,
자동으로 feature를 학습할 수 있게 하려는 노력들이 있음. (Recent Techniques)
(Automatically learn the features)

그래프에서의 Feature Learning

‘그래프 도메인에서, Efficient 하고, Task-independent 한 Feature Learning을 한 번 해보자!!’
- Efficient: Feature Engineering에 들이는 시간을 줄이고 싶다.
- Task-Independent: Downstream Task가 무엇이든지 간에, automatic feature extraction을 위한 하나의 파이프라인을 만들고 싶다
- 네트워크에서 ‘Embedding’을 왜 하는가?
  - 노드들 사이의 Embedding의 유사성은 곧 그들 네트워크의 유사성을 의미.
  - 네트워크 정보를 Encode해서, node representation을 생성
    (각 Node representation들은 가능한 많은 Network 정보를 Encode하길 원할 것)
  - ㄱ) (앞에서 계속 다뤄오던 Adjacency Matrix형태) 너무 Sparse하고 Large -> Expensive!!!
  - ㄴ) Adjacency Matrix에 비해 매우 compact!
    - 각 Dim들은 노드들의 어떤 aspects들을 capture할 수 있다.
      (ex. 각 노드가 속한 motif, node degree, 등등)
    - 단, 이 ‘Dimension’들은 말그대로 Latent! (Not explicit one)
      (이 말은 곧, Embedding 후 좌표축에 점들을 던져 놓았을 때, 각 축들이 Label되지 않는다는 것을 의미)
  - ㄷ) Embedding을 사용함으로써 해낼 수 있는 Task들
그래프 도메인에서 DL이 어려운 이유
- 단순한 sequence나 grid 세계를 위해 고안된 모델이기 때문
  - ex) CNN: 고정된 사이즈의 이미지나 grid를 대상으로
  - ex) RNN 및 word2vec: 텍스트나 시퀀스를 대상으로
  - 하지만 네트워크는 훨씬 복잡하다!
  - 위상학적으로 상당히 복잡하고, 예를 들어, grid world에서 적용하려고 할 때,
    실제로 그래프에 없는 노드들을 대상으로 Convolution을 쓰는 경우들이 생김. 없는 노드들에 convolution을?)
  - 또 그래프에서는 노드들 간의 순서나, reference point같은 것이 없으며,
  - 종종, 그래프의 형태가 계속 바뀌거나 (dynamic), multimodal feature들을 지닌 경우들도 있음.

Embedding Nodes

어떤 그래프 G가 있다고 해보자.
- V: Vertex set
- A: Adjacency matrix
- Node feature나 extra information 사용x 가정
목표: 네트워크 상의 노드들을 Embedding Space로 Encode 하자.
단, embedding space에서의 similarity가 original network에서의 similarity를 근사할 수 있는 방향으로.
Node Embedding을 학습하는 방법?
- 1. Encoder 정의 (Node를 Embedding으로 어떻게 mapping할 것인가?)
- 1. Node Similarity Function 정의 (Original network에서 노드 간의 Similarity라는 것을 어떤 식으로 측정할 것인가?)
- 1. Encoder의 Parameter 최적화 (아래 Equation에서 최상의 근사를 얻을 수 있도록)
    $similarity(u,v) \approx \mathbf{z}_v^T\mathbf{z}_u$

1. Encoder

각 노드를 Low-dimensional vector로 mapping한다!
- 여기서 d라는 dimension은 모델을 만드는 사람에게 달려있는 파라미터 중 하나!
- 예) “Shallow” Encoding
  - Encoder는 단지 ‘Embedding-lookup’이다! (CS적인 용어로는 Hash Table에 불과하다!)
  - 결과적으로 각 노드는 Unique한 Embedding vector로 할당(assign)된다!
- 이 외에도 다양한 Encoding 방법들이 존재!
  - DeepWalk
  - node2vec
  - TransE
  - 등등

2. Similarity Function

Original network에서의 relationship을 vector space로 어떻게 mapping 할지에 대한 구체화
Similarity function의 선택은, node similarity라는 것을 어떻게 정의하느냐에 달린 것
- 연결되어 있는가?
- Neighbors를 공유하는가?
- 유사한 ‘Structural roles’를 갖고 있는가?
- 등등

3. Parameter Optimization

(이 부분은 뒷 부분의 내용인데 의도적으로 재배치함)
(위의 Node Embedding 학습 step 1, 2에 이어서) 그래프 G=(V,E)가 주어지면 (계속 말하지만) 노드의 d-dimension으로의 mapping을 학습하는 것이 목표!
목적함수
- 노드 u의 vector representation이 주어졌을 때, strategy R을 이용해서 노드 u의 neighbor들을 찾을 조건부 확률을 최대화!
- log로 표현하는 것은, 단순히 확률의 Product로 표현하면, 매우 빠르게 그 값이 줄어들기 때문에, optimization 문제에서 numerical instability를 줄이기 위해 사용되는 방식
- 요컨대
  노드 u가 주어졌을 때, 노드 u의 neighborhood N_R(u) 노드들을 잘 예측할 수 있는 feature representation을 배우고 싶다는 것!

Random Walk Approaches to Node Embeddings

검색 결과 Deepwalk를 설명하고 있는 듯.

특정 그래프, 그 그래프의 시작점이 주어지면, 그 이후로는 neighbor들을 random하게 선택하고 나아가게 되는데, 이 point들의 sequence는 random walk를 따른다고 할 수 있음.

Random-walk Embeddings

$\mathbf{z}_u^T\mathbf{z}_v$
‘네트워크 전반에서 노드 u,v가 random walk 에서 동시에 발생할 확률’로 근사할 수 있음
(probability that u and v co-occur on a random walk over the network)
- 두 embedding이 서로 가깝다면, 해당 값의 결과값은 크기가 클 것.
과정
- 1. 어떤 random walk strategy R을 사용했을 때 node u에서 출발하여 node v에 방문할 확률을 추정한다.
- 2 이 random walk statistics를 encode하기 위해 embedding을 최적화!
Random-walk를 사용하는 이유?
- 1. Expressivity!
    - Local과 Higher-order neighborhood 정보를 함께 고려하는 node similarity의 정의에 대한 Flexible stochastic definition!
- 1. Efficiency!
    - 훈련시 모든 노드 쌍들을 고려할 필요가 없다.
    - Random walk 상에서 함께 일어나는 쌍들만 고려하면 됨
      (해당 성징른 그래프의 크기가 커질수록 힘을 발휘)
      (이 특성은 실세계의 social network에서도 굉장히 확장성 높음!)
- Strategy R로부터 얻게 되는 node u의 ‘Neighbours’!
Optimization in ‘Random-walk’
1. 어떤 strategy R을 사용해서 그래프 상의 각각의 점들로부터 출발하는, 짧고 고정된 길이(short fixed-length random walks)를 지닌 random walk를 실행(run)
2. 각 노드 u에 대해, N_R(u)를 수집한다.
  (N_R(u): The multiset of nodes visited on random walks starting from u)
3. 다음 식에 따라, embedding을 optimize
  $\underset{z}{max}\sum_{u \in V}log P(N_R(u)|z_u)$
- Random Walk에서의 Loss function을 다음과 같이 정의해볼 수도 있음
  (Intuition: Random walk가 동시에 발생(co-occurrrence)할 likelihood를 maximize할 수 있도록 embedding을 최적화)
  $\mathit{L} = \sum_{u \in V}\sum_{v \in N_R(u)}-log(P(v | \mathbf{z}_u))$
  - 여기서 p(v|z_u)는 vector representation이 softmax를 거친 후의 값
- 명시적으로 식을 정리해보면
- 결국 Random-Walk Optimization의 문제는
  = Random Walk embedding을 최적화하라
  = L을 최소화하는 embedding z_u를 찾아라!
- 하지만 이 Loss를 전부다 계산해내는 건 상당히 비효율적인 일 (Too Expensive)
  - 그 원인이 바로 softmax의 분모 (Normalization term) 때문인데, 이 식을 다른 식으로 대체할 수 있다면, 보다 효율적인 방향으로 Loss function을 Approximate할 수 있다!
    -> 그 방법이 바로 Negative Sampling
Negative Sampling
- 기존 Loss function의 log() 파트를 다음과 같이 근사!
  - Idea: 모든 노드들을 고려하여 Normalize 하지말고, k개의 random negative samples n_i에 대해 normalize 해라!
  - 차수에 비례하여 k negative nodes를 샘플링할 것
  - k에 대한 두 가지 조건
    1. k↑ → Robust estimates
    2. k↑ → Negative Events에 대한 higher bias
  - 실제로 k는 5와 20 사이의 수를 택해
방금까지 얘기한 건, Random Walk에서의 Optimization에 대한 이야기
이런 random walk를 사용하기 위해서는 어떤 Strategies를 사용해야 하는가? (뭔가.. 강의 순서가 뒤죽박죽..)
- 고정된 길이의, 각 노드들로부터 출발하는 unbiased random walk를 실행
- 하지만 이 방법의 한계: 두 노드가 유사한 structural role을 지니고 있을 때, 그들이 멀리 있다면, 이 similarity를 caputure하지 못할 것 (길이가 Fixed되어 있기 때문에)

Node2vec Embeddings

목표: 유사한 네트워크 이웃들을 가진 노드들을 Feature Space 상에서 가까이에 Embed하기
- = Downstream prediction task와는 독립적으로, Maximum LIkelihood Optimization 문제
Biased 2nd order random walk R 개발!
Idea
- 네트워크의 local 과 global 한 특성 사이의 균형을 맞출 수 있는 flexible, biased random walk!
- BFS와 DFS는 특정 노드 u의 Neighborhood N_R(u)를 정의할 수 있는 두 가지 고전 strategies
  - BFS: 그래프의 Local(Micro) view 강조
  - DFS: 그래프의 Gloval(Macro) view 강조
BFS와 DFS 간의 Trade-off를 어떻게 Encode할 것인가?
(이 파트에 대한 설명이 너무 불친절하다… 추후에 논문 읽어보고 스스로의 해석으로 업데이트 해야지..)
- 특정 노드 u가 주어지면 neighborhood N_R(u)를 generate하는 Biased fixed-length random walk
- Biased
  - p와 q라는 두 가지 Parameter를 사용!
    - p: Return parameter
      이전의 노드로 돌아온다.
    - q: In-out parameter
      Moving Outwards (DFS) vs. Inwards (BFS)
      즉, BFS vs. DFS의 비율이 바로 q
  - 예

Node2vec 알고리즘

Random walk 확률 계산
각 노드 u에서 출발하여 길이 l짜리 random walk를 r개 simulate!
SGD를 이용하여 node2vec objective를 최적화

이 세 단계는 모두 따로 병렬화가 가능하며, 시간복잡도도 Linear하다.

노드의 embedding z_i를 어떻게 사용할 것인가?

다양한 곳에 사용할 수 있다.
- Clustering / community detection
- Node classification
- Link Prediction 등등
  - 두 노드 pair zi, zj에 aggregation function을 적용해서 f(zi, zj)에 근거하여 edge (i,j)를 예측
요약
- node similarity의 다양한 개념들
  - Adjacency-based
  - Multi-hop similarity definitions
  - Random walk approoach
    등에 근거할 수 있다!
- 이런 방법들 중 silver-bullet은 없으며, 문제에 따라 더 잘 working하는 알고리즘들이 다 다르다.
  ex. node classification에서는 node2vec이, link prediction에서는 multi-hop method가 더 잘 working 한다든지…

Translating Embeddings for Modeling Multi-relational Data

Knowledge graph
- 서로 연관된 entity 들에 대한 facts / statements로 구성되어 있다.
- Knowledge graph에서는 Node는 Entity로, Edge는 Relation으로 명명
- Edge들은 여러 타입으로 구성될 수 있음
- 한편, KG가 불완전(incompleteness)할 경우, 이에 의존하는 시스템의 효율성에 상당한 악영향을 초래할 수 있음.
- 따라서, KG에서의 local & global 연결 패턴으로부터 학습하는 link prediction model을 만들 수 있기를 원함
  - Downstream task: 관심의 대상이 되는 entity와 다른 모든 entity들 사이의 observed된 관계를 generalize하기위해 학습된 패턴을 사용하여 relation prediction을 수행

TransE (Translating Embeddings)

TransE 에서 entity들 사이의 관계는 Triplet 으로 나타남
- h (head entity), l (relation), t (tail entity) → (h,l,t)
  - l(relation) hold시 -> Relation Space에서 Tail entity들이 존재하길 기대
    hold x시 -> Tail entity들이 empty

TransE algorithm

gnn07-22

Triplets의 Batch로 work!
궁극적인 론은, Random Walk가 Embedding generation의 유일한 방법은 아니라는 것

Embedding Entire Graphs

앞 전에는 node 하나하나를 embedding 했다면, 여기서는 그래프 자체를 embedding 해보겠다는 의도
- 이를 통해 해볼 수 있는 태스크
  - Toxic molecules, non-toxic molecules 분류하기
  - anomalous graph 골라내기
이에 대한 3가지 접근
- Approach1: Node Embedding & Sum(or Avg)
  - (sub)graph G에 standard graph embedding 테크닉을 적용
  - (sub)graph G 내에서 node embedding 들을 단순히 더하거나 평균낸다.
    $z_G = \sum_{v \in G}z_v$
- Approach2: (sub)graph를 span하는 super-node를 새로 만들고, 그 노드를 embed
  - (sub)graph를 나타내기 위한 virtual node 를 소개하고, virtual node에 대해 stnadard graph embedding 테크닉 사용
- Approach3: Anonymous Walk Embeddings
  - Anonymous walk 내의 state들은 random walk 내에서 노드를 첫번째로 방문했을 때의 index에 상응한다

(해당 과는.. 뭔가 좀 강의가 정제가 안된 느낌입니다.. 추후에 논문을 읽고 다시 정리해서 업데이트 하도록 하겠습니다.)

References

CS224W: Graph Representation Learning

Graph Representation Learning

그래프에서의 Feature Learning

Embedding Nodes

1. Encoder

2. Similarity Function

3. Parameter Optimization

Random Walk Approaches to Node Embeddings

검색 결과 Deepwalk를 설명하고 있는 듯.

Random-walk Embeddings

Negative Sampling

Node2vec Embeddings

Node2vec 알고리즘

Translating Embeddings for Modeling Multi-relational Data

TransE (Translating Embeddings)

TransE algorithm

Embedding Entire Graphs

References

Share this post