CS224W 2021 Node Embeddings

반응형

이 Lecture는 제가 공부한 부분까지만 정리를 할 것입니다. 제가 한 절반정도 공부했으니 그정도까지만 작성하도록하겠습니다. 제가 pdf파일만 보고 이해한 선에서 작성된 것이므로 틀린 것이 있을 수도 있습니다...

사전에 알아야하는 그래프 용어

V : vertex(꼭짓점) -> 노드

E : Edge(변)

 

이 부분에서는 그래프를 위한 전통적인 머신러닝에 대해서 소개를합니다. 입력 그래프가 주어지면(노드 추출, 링크 및 그래프 수준 기능, 라벨에 기능을 하는 모델 학습을 한다.)

순서

그래프 입력 -> 피처 엔지니어링 -> 피처를 구조화 -> (알고리즘 학습 -> 예측) 

                                                                       다운스트림 예칙 테스크

 

이 부분은 Graph Representation Learning에 대해서 소개를 합니다. 우리는 그래프를 위한 일반 전톡적인 머신 러닝 대신 그래프 표현 학습을 사용하면 매번 피처 엔지니어링을 하는 것을 완화시킬 수 있습니다.

 

이게 그래프 표현 학습이 이루어지는 순서인데 아까전 일반 그래프를 위한 머신러닝이랑 비교를 하면 피쳐 엔지니어링이 없어진다. 왜냐하면 중간에 피쳐 엔지니어링 과정을 따로 안해도 표현학습에서는 자동으로 피쳐를 학습하기 때문이다.

- 노드 간 임베딩의 유사성은 네트워크에서 유사성을 나타내준다.

ex) 엣징에 연결되어 있는 두 노드는 서로 가깝습니다.

- 네트워크 정보를 인코딩을해준다.

- 잠재적으로 많은 다운스트림 예측에 사용됩니다.

 

 

노드 임베딩을 나타내는 사진입니다. 

그래프 G가 있따고 가정해보자.

그리고 V는 노드 집합이다.

A는 이진으로 가정하나 인접행렬이다.

간단성을 우해서 노드 기능 또는 추가 기능을 안 넣었다.

우리의 목표는 임베딩 공간의 유사성이 그래프의 유사성과 유사하도록 노드를 인코딩하는 것입니다.

 

embedding space의 두 노의 similarity는 실제 네트워크에서 similarity와 비슷할 것이다.

그리고  ENC(u) <- 이 표시는 인코더 함수를 나타내는 것 같다.

그래서 위의 두식 similarity와 ENC함수를 정의해야한다.

shallow함수로 ENC를하게 되면 아래와 같은 형식으로 된다. Dimension size를 가지고 각 node마다 하느이 column을 가지게 된다.

가장 간단한 인코딩 방식 : 인코더는 임베딩 조회하는 것이다.

많은 기법들이이 있다.

                          - Deep Walk

                          - node2vec

 

프레임워크 요약

인코더 + 디코더 프레임워크

Shallow encoder : 임베딩 조회하는 역할을 한다.

최적화할 매개변수: Z

디코더 : 노드 유사성을 기반

 

노드 유사성을 정의하는 방법

방법의 주요선택은 노드를 어떻게 유사성있게 정의하는 방법입니다.

 

두 노드가 유사한 임베딩을 가져야하는 경우 : 그들이 링크도리 경우 neighbor를 공유할 경우 유사한 구조적 역할이 있는 경우

 

우리는 이제 random walk를 사용하는 노드 유사성 정의를 배우겠습니다. 그리고 어떻게 이러한 유사성 측정을 위해 임베딩을 최적화하는지 알아낼 것입니다.

random walk란?

꼭짓점 위를 임의로 걸어다니는 것. 한 꼭짓점에서 시작해서 임의의 이웃으로 가고 또 그 꼭짓점의 임의의 이웃으로 정해진 횟수만큼 이동. 이렇게 이동했을 때 방문한 꼭짓점들의 나열한 것을 랜덤워크라고한다.

 

노드 임베딩에 관한 참고 사항

이것은 노드 임베딩 학습하는 비지도학습과 지도학습 방법입니다.

- 우리는 노드 레이블을 사용하지 않습니다.

- 노드 피처를 사용하지 않습니다.

 

이러한 임베딩은 독립적인 작업입니다.

- 특정 테스크에 러닝이 되지 않았지만 모든 작업에 사용이 될 수 있습니다.

 

기법

- vector z를 이용하는 방법이다

- 활성화 함수

- 시그모이드 함수

 

 

그래프와 시작점이 주어지면 우리는 이웃을 랜덤적으로 선택하고 이동한다. 무작위 순서로 포인트를 방문하는 것은 그래프에 random walk하는 방법이다.