cs224w_3
Node Embeddings
Graph Representation learning은 매번 feature engineering하는 것을 더 쉽게 해준다.
목표 : 그래프를 사용한 머신러닝에 효율적인 피쳐 학습
태스크 : 노드를 임베딩 공간으로 매핑하는 것
- 노드간의 임베딩이 비슷하다는 것은 네트워크 내에서 그들이 유사하다는 것을 의미(예, 두 노드가 엣지로 연결되어 있으면 두 노드가 서로 가깝다는 것을 의미)
- 네트워크 정보를 인코딩
- 잠재적으로 다양한 다운스트림 태스크에 사용
Node Embeddings : Encoder and Decoder
임베딩 공간에서의 유사도로 그래프 내에서의 유사도를 추정하기 위해 노드를 인코딩한다.
Learning Node Embeddings
- 인코더는 노드로부터 임베딩을 매핑한다.
- 노드 유사도 함수를 정의한다.
- 디코더는 임베딩으로부터 유사도 점수를 매핑한다.
- 다음과 같이 인코더 파라미터 최적화
두가지 주요 구성물
- 인코더 : 각 노드를 낮은 차원의 벡터로 매핑
-
유사도 함수 : 벡터 공간에서의 관계가 원래 네트워크에서의 관계에 어떻게 매핑되는지 명시
- “Shallow” 인코딩 가장 간단한 인코딩 접근법 인코딩은 하나의 임베딩 색인 각 노드는 유니크한 벡터로 할당
요약
- 인코더 + 디코더 프레임워크 – Shallow encoder : 임베딩 색인 – 최적화 할 파라미터 : 모든 노드 임베딩 $z_u$를 포함하는 Z – Lec 6 GNNs에서 확인
- 디코더 : 노드 유사도에 기반
- 목적함수 : 유사한 노드(u,v)에 대해서 $z_v^T$$z_u$ 쌍을 최대수
어떻게 노드 유사도를 정의할 수 있는가?
고려해볼 사항
- 연결되어 있는가?
- 이웃을 공유하는가?
- 비슷한 구조적 역할을 수행하는가?
이제 random walk를 사용하여 노드 유사도를 구하는 방법과 어떻게 유사도를 측정해서 임베딩을 최적화 하는지 배운다. 이것은 노드 임베딩을 학습하는 비지도/ 자기 지도 방법이다.
- 노드 레이블을 활용하지 않는다.
- 노드 피쳐를 활용하지 않는다.
- 목표는 네트워크 구조의 어떤 측면을 보존하기 위해 한 노드의 좌표를 직접 측정하는 것
- 이러한 임베딩은 태스크 독립적이다. 특정 태스크에 대해서 훈련되는 것이 아니고, 어느 태스크에서나 사용될 수 있다.
Random Walk Approaches for Node Embeddings
- Vector $z_u$ : 노드 u의 임베딩 (우리가 찾고자 하는 것)
-
Probability $P(v z_u)$ : 노드 u에서 출발하여 random walk로 노드 v를 방문할 가능성
가능성을 예측하기 위해서 비선형 함수가 쓰인다.
- Softmax Function
- Sigmoid Function
Random Walk
하나의 그래프와 하나의 출발점이 주어졌을 때, 이웃 중 무작위로 선정하여 이동하는 것을 반복하는 방식
$z_u^Tz_v$ : 노드 u,v가 동시에 random walk에서 발생할 확률
-
$P_R(v u)$ : 노드u에서 출발하여 random walk strategy R을 사용하여 노드v를 방문할 확률을 추정하는 것 - random walk 통계를 인코딩 하도록 임베딩 최적화
Why Random Walks?
- 표현성 : 지역 및 고차 이웃의 정보를 통합하는 노드 유사도의 유연한 확률적 정의 – 아이디어 : 노드 u에서 시작해서 무작위 보행으로 노드 v에 도착할 확률이 높으면, u와 v는 유사한 것이다.
- 효율성 : 학습 과정에서 모든 노드 쌍을 고려하지 않아도 된다. 오직 무작위 보행 중 동시에 발생한 쌍만 고려하면 된다.
Unsupervised Feature Learning
– Intuition : 유사도를 보전하는 d차원 공간의 노드 임베딩을 찾자 – Idea : 네트워크 내 인접한 노드가 서로 가깝게 학습하도록 노드 임베딩 – 주어진 노드 u에 대해서 어떻게 인접한 노드를 정의할 것인가? 무작위 보행 전략 R에 의해 얻은 u의 이웃 : $N_R$(u)
Feature Learning as Optimization
노드u가 주어졌을 때 우리는 $N_R(u)$의 노드들에 대한 예측의 Feature representation을 원한다.
- 노드 u에서 시작한 무작위 보행 전략R을 사용하는 고정된 짧은 거리의 무작위 보행
- 각 노드 u에서 $N_R(u)$를 수집한다. u에서 시작한 무작위 보행 노드의 다중 셋
- u가 주어지면 그것의 이웃 $N_R(u)$를 예측할 수 있도록 임베딩 최적화 – Intuition : 동시에 발생한 무작위 보행에 대한 likelihood가 최대화 되도록 임베딩 $z_u$를 최적화 – softmax를 사용하여 $P(v|z_u)$ 파라미터화: – 연산이 너무 많이 들어간다.
Negative Sampling
모든 노드에 대해서 적용하는 대신에 k개의 random “negative samples” $n_i$를 사용
- 샘플 k negative nodes는 각각의 degree에 비례하는 확률을 따른다.
- k의 수를 정하기 위한 고려사항
- k가 클수록 더 강건한 측정을 한다.
- k가 클수록 네거티브 event에 대한 더 큰 편향을 나타낸다.
실제로는 k는 5~20으로 사용
확률적 경사 하강법
스킵
Random Walks : 요약
- 그래프에서 각 노드로부터 출발하는 짧은 길이의 무작위 보행 실행
- 각 노드 u에서 출발하여 무작위 보행으로 방문한 노드로 구성된 멀티셋을 $N_R(u)$를 모은다.
- 확률적 경사하강법을 사용하여 임베딩을 최적화 한다.
How should we randomly walk?
어떤 무작위 보행 전략을 사용할 수 있을까?
- 가장 간단한 아이디어 : 각 노드에서 시작해서 편향되지 않은 무작위 보행으로 고정된 길이만큼만 간다. – 이러한 유사도는 너무 제약적이라는 문제가 존재
- 어떻게 일반화 할 수 있을까?
Overview of node2vec
Goal : 비슷한 네트워크 이웃들을 미래 공간에 가깝게 임베딩한다. 이 목표를 다운스트림 태스크와 무관하게, 최대우도법 최적화 문제로 규정한다.
Key observation : 노드 u의 이웃 $N_R(u)$의 유연한 표기가 노드 임베딩을 더 풍부하게 할 것이다. n의 네트워크 이웃 $N_R(u)$를 생성하기 위해 편향된 두번째 순서의 무작위 보행R 을 발전시킨다.
node2vec : Biased Walks
Idea : 네트워크의 지역적 전역적 관점 사이를 절충할 수 있는 유연하고 편향된 무작위 보행 전략 사용 노드 u의 이웃 $N_R(u)$를 정의하기 위한 두가지 전통적인 방법 두개의 파라미터
- Return parameter p : 전의 노드로 복귀
- In-out parameter q : 바깥방향(DFS) vs. 안방향(BFS)로의 이동, q는 BFS대 DFS의 비율
- random walk가 간선($s_1$, w)를 횡단했고 지금은 w에 있다.(어디서 왔는지 기억)
- $N_R(u)$는 편향된 보행간에 방문한 노드들
node2vec algorithm
- random walk 확률을 계산한다.
- 각 노드u로부터 출발하여 길이 l만큼의 random walk를 시뮬레이션 한다.
- 확률적 경사하강법을 사용하여 node2vec의 목적함수를 최적화 한다.
- 선형 시간 복잡도
- 3가지 스텝이 모두 개별적으로 병렬화 가능하다.
Other Random Walk Ideas
요약
Core idea : 임베딩 공간의 거리가 원래 네트워크의 노드 유사도를 반영하도록 노드를 임베딩한다. 노드 유사도의 개념들
- 두 노드가 연결되어 있음.
- 이웃을 공유함
- 무작위 보행 접근법
각각의 방법들이 쓰임이 있다.
랜덤워크 접근법이 일반적으로 더 효율적이다.
Embedding Entire Graphs
Gaol : 그래프 임베딩 $z_G$로 전체 그래프 G 또는 부분 그래프를 임베딩
Approach 1
Simple idea 1:
- 일반 그래프 임베딩 기술을 (부분)그래프 G에 적용
- 이후에 그래프 G에 속하는 노드 임베딩을 sum(or average)
Approach 2
Idea 2:
- (부분)그래프를 표현하고 표준 그래프 임베딩 기술을 수행하기 위해 가상의 노드를 제시한다.
Approach 3 : Anonymous Walk Embeddings
anonymous walk 중의 상태는 처음 특정 노드를 방문했을 때의 index와 대응된다. 방문한 노드의 ID와 관계 없다.(그래서 익명)
- Number of Walks Grows Anonymous walks의 길이가 증가함에 따라 anonymous walk의 수는 지수적으로 증가한다.
l스텝의 anonymous walk를 시뮬레이션하고 그들의 수를 기록한다. 그래프를 이러한 walks의 확률 분포로 나타낸다.
예) l = 3 5-dim 벡터를 표현할 수 있다. $Z_G[i]$ = 그래프 G에서 anonymous walk $w_i$의 확률
Sampling Anonymous Walks
m개의 Random walks 세트를 독립적으로 생성 그래프를 이 walks의 확률 분포를 통해 표현
- Random walk의 수 m은 어느정도가 적당한가?
New idea : Learn Walk Embeddings
발생 횟수로 나눠 각 walk에 대해 간단히 표현하는 것보다, anonymous walk $w_i$의 임베딩 $z_i$를 배우는 것이 낫다. – 모든 anonymous walk embedding $z_i$와 함께 그래프 임베딩 $Z_G$를 학습한다. – 어떻게 walks를 임베딩하는가? idea : 다음 walk를 예측하는 것을 목적으로 walk를 임베딩
$z_G$ : 입력 그래프의 벡터 매개변수 (배우게 될 전체 그래프의 임베딩) anonymous random walks 샘플(노드 1에서 시작) $\Delta$-size의 window에서 동시에 발생할 Walk를 예측하는 것을 학습($\Delta$=1 일 때, $w_1$,$w_3$이 주어졌을 때 $w_2$를 예측) – 목적함수 (그래프 내 모든 node의 objective 합)
u에서 출발한 길이 l의 서로 다른 random walk T개:
anonymous walk $w_i$의 임베딩 $z_i$를 추정 $\eta$를 가능한 Walk임베딩의 수로 한다.
최적화 이후에 그래프 임베딩 $z_G$(학습 가능한 파라미터)를 얻게 된다. $z_G$를 예측에 사용한다.(그래프 분류) – 옵션1 : 커널 내적 $z_{G_1}^T z_{G_2}$ – 옵션2 : 분류를 위한 입력으로 $z_G$ 사용
요약
접근1 : 노드를 임베딩하고 그것들을 합/평균 접근2 : (서브)그래프에 걸쳐있는 수퍼노드를 만들고 그 노드를 임베딩 접근3 : Anonymous Walk Embeddings – idea1 : anon. walks를 샘플링하고 시간 단위의 각 anon walk가 발생하는 것으로 그래프를 표현 – idea2 : anon. walks를 임베딩하고 그것들을 연결하여 그래프 임베딩을 얻음