[Day 24] 정점 표현

DAY24 신기정 교수님 수업과 CS224W 내용 ,  Elior Cohen 의 글을 참고한 학습정리내용입니다. 

 

정점 표현 학습

---

정점 표현 학습은 그래프의 정점들을 n차원의 벡터들로 표현하는 것으로 정점임베딩이라고도 한다. 

우리가 아는 word embedding과 같다. word를 컴퓨터가 이해하기 편한 벡터로 만들어주는 것과 같이 정점을 벡터로 만들어주는 작업을 정점임베딩이라 하는 거다. 

정점이 표현되는 벡터 공간을 임베딩 공간이라고 부른다.

정점 임베딩을 왜 할까?

그래프로 표현되어있으면 그래프에 맞는 특화된 알고리즘을 사용해야한다. 

MLP , K-MEANS 등은 벡터 형태로 된 instance들을 입력으로 받기 때문에 그래프는 사용할 수 없다.

하지만 정점임베딩을 통해 벡터로 만들어주면 기계학습 도구들에도 사용할 수 있게 된다. 

인접행렬에 비해 압축된 표현이기때문에 공간효율도 좋고, 벡터 연산이 더 간단하고 빠르다고 한다.

 

 

정점 임베딩의 목표는 그래프에서의 정점들이 유사할수록 d차원에서의 임베딩들이 근접하도록 만들어 주는 것이다

즉, 그래프에서의 정점 간 유사도를 임베딩 공간에서도 "보존"하는 것이 목표다. 

 

그래프에서의 u,v의 유사도와 임베딩 공간에서의 임베딩 u 와 임베딩 v의 유사도가 근사해야된다. 

임베딩 공간에서의 유사도로는 내적(inner product)를 사용한다.

그러면 그래프에서의 두 정점의 유사도는 어떻게 정의할 수 있을까?

아래에서 그래프에서의 유사도를 구하는 여러가지 방법을 소개하겠다. 

 

정리하면 3단계를 거친다.

1) 그래프에서의 정점 유사도를 정의

2) 임베딩 방식 정의

3) 정의한 유사도를 보존하도록 정점 임베딩 학습

 

우선 그래프에서의 정점 유사도를 정의하는 방식 먼저 알아본다.

 

 

 

인접성/거리/경로/중첩 기반 접근법

---

📌 인접성 기반 접근법 ( Adjacency-based similarity)

 

인접성 기반 접근법은 두 정점 𝑢와 𝑣가 인접하다는 것은 둘을 직접 연결하는 간선 (𝑢, 𝑣)가 있음을 의미한다.

인접행렬(Adjacency Matrix) 𝐀의 𝑢행 𝑣열 원소 𝐀𝑢,𝑣는 𝑢와 𝑣가 인접한 경우 1  아닌 경우 0으로 표현된다.

인접행렬의 원소 𝐀𝑢,𝑣 =두 정점 𝑢와 𝑣의 유사도

우리의 목표는 그래프에서의 노드간 유사성과 임베딩공간에서의 유사성을 근사시키는 것, 즉 둘의 차를 줄이는 것이다.

손실함수를 아래와 같이 쓸 수 있게 된다. 

그럼 이 손실함수를 최소화할 수 있는 dx|V|크기의 embedding matrix를 구해야한다.

SGD를 통해서 손실함수를 최소화하면서 최적의 embedding matrix를 찾게 된다.

 

❗❗ u=v일 때도 계산을 하는지, 아니면 아무리 임베딩을 잘 학습해도 같은 점에 대해서는 차이를 줄이려면 임베딩 값이 0이 되어야하는 거 밖에 없는 거 같은데

 

 

• 단점
  • 모드 정점쌍을 비교하기 때문에 $O(|V|^{2})$으로 시간복잡도가 크다.
  • 벡터 하나가 노드를 의미하므로 공간복잡도는 O(|V|)가 된다.
  • 너무 직접적이고 local한 연결만을 보게 된다. 

 

빨간색 정점과 파란색 정점은 거리가 3이고, 파란색 정점과 초록색 정점은 거리가 2이지만 같은 군집내에 속해있다.

이런 경우 인접성 즉 1촌인지의 여부만 고려하게 되므로 두 경우 모두 유사성이 0이 되어야한다.

파란점을 기준으로 빨간색 정점과는 유사성이 적더라도, 초록색과는 커야하는데 이와 상관없이 직접적 연결이 아니므로 모두 0이 되어버리는 것이다. 

 

 

📌 거리/경로/중첩 기반 접근법

 

• 거리 기반 접근법

거리 기반 접근법은 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주한다. 

두 정점 사이의 거리는 최단 경로를 의미한다.

아래 이미지에서 녹색은 거리1 , 파란색은 거리2, 보라색은 거리3을 의미한다.

"충분히 가깝다"의 기준은 사용자가 하이퍼파라미터로 정해주면 된다.

만약 충분히를 2로 설정했다면 파란색까지는 유사도가 1이고, 보라색부터는 0으로 바라보는 것이다.

 

• 경로 기반 접근법 

경로 기반 접근법에서는 두 정점 사이의 경로가 많을 수록 유사하다고 간주한다.

생각해보면 같은 군집 내에 있다면 경로가 비교적 다양하고, 다른 군집에 있으면 군집끼리의 간선자체가 희소하니 경로가 적을 거다. 그래서 이런 아이디어가 나온 거 같다.

경로가 되는 조건은 저번 시간에 배웠지만 아래 두 조건을 만족해야한다. 

(1) 𝑢에서 시작해서 𝑣에서 끝나야 한다.

(2) 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.

두 정점 𝑢와 𝑣의 사이의 경로 중 거리가 𝑘인 것은 수는 $A_{i,j}^{k}$ 와 같다.

➕ 내가 고민했던 거랑 일치하는 질문과 댓글이 있어서 적어보면 

위 그래프에서 4와 5는 인접해있는데 만약 k=2면 이 둘 사이에 거리가 2인 경로가 없기때문에 0이 된다.

그래서 해당 식대로 유사성을 구하면 k보다 짧은 길이의 경로들에 대한 유사성이 고려되지 않아 문제가 생길 여지가 있다고 한다. 그래서 1~k까지의 합으로 바뀌는 것이 더 합리적이라고한다. 요새는 쓰지 않는 방식이고, 이런 게 있다~를 말해주려고 소개해주신 거라고 한다 

 

• 중첩 기반 접근법

중첩 기반 접근법에서는 두 정점이 많은 이웃을 공유할 수록 유사하다고 간주한다.

아래 그림에서 빨간색 정점은 파란색 정점과 두 명의 이웃을 공유하기 때문에 유사도는 2가 됩니다.

 

공통 이웃 수 대신 자카드 유사도나 adamic adar 점수를 사용할 수 있다. 

- 자카드 유사도 : 두 점의 이웃집합의 교집합의 개수를 합집합의 크기로 나눈 값으로 나눈 값

위 그래프에서 빨간점의 이웃집합 = 3개 , 파란점의 이웃집합 =4개 , 교집합은 2개이므로 유사도는 2/7이 된다.

\begin{align}\frac{\left | N_{u}\cap N_{v} \right |}{\left | N_{u}\cup  N_{v} \right |} \end{align}

 

- Adamic Adar 점수 :  공통 이웃 각각에 가중치를 부여한 가중합을 계산하는 방식이다.

역수인 이유는 이웃들의 연결성이 낮으면 높은 확률로 연결되겠지만, 연결성이 높으면 연결될 확률이 낮아지기때문이다. 위의 공통이웃은 연결성이 3, 아래쪽은 연결성이 2이므로 점수는 5/6이 된다. 

\begin{align}\sum _{w \in N_{u} \cap N_{v}} \frac{1}{d_{w}}\end{align}

 

정점 𝑢의 이웃 집합을 𝑁(𝑢) 그리고 정점 𝑣의 이웃 집합을 𝑁(𝑣)라고 하면 두 정점의 공통 이웃 수 𝑆𝑢,𝑣는 다음과 같이 정의 할 수 있다. 공통 이웃수는 각각의 이웃집합의 교집합의 원소 개수이다.

 

• 단점

요런 방식들은 인접행렬 기반의 유사도를 구하는 과정이 가지고 있는 "1촌만 본다"라는 문제점을 해결하긴 한다. 

하지만 모든 정점들에 대해 쌍으로 진행되기 때문에 $O(|V|^{2})$으로 시간복잡도가 크고 공간복잡도가  $O(|V|)$가 된다. 

 

 

 

임의 보행 기반 접근법 : DeepWalk , Node2vec

---

• DeepWalk

임의보행 기반 접근법에서는 한 정점에서 시작하여 임의보행을 할 때 다른 정점에 도달할 확률을 유사도로 간주한다.

임의보행은 이웃된 노드에게는 1/연결성만큼의 균일한 확률로 이동하는 과정을 반복하는 것이다. 

이럴 경우, 지역적 정보와 그래프 전역 정보를 모두 고려할 수 있다는 장점이 있다. 

 

우선 모든 정점에 대해 임의보행을 반복수행한다. 몇 번 반복할지(max_iter)는 사용자가 정해주게 된다. 

각 정점에서 시작한 임의보행이 거쳐간 정점들을 리스트로 구성한다. 한 정점을 여러번 거쳐간 경우에도 모두 써준다.

정점 u에서 시작한 임의보행 중 거쳐간 정점들의 리스트를 $N_{R}(u)$라고 표현할 수 있다.

이후 손실함수를 최대화하는 임베딩을 학습한다. 

 

손실함수를 풀어보면 모든 정점 u에 대해서 그 정점 u가 지나친 정점 v들 각각에 대해 조건부확률의 네거티브 로그값을 최소화하는 것이다. 결국 임베딩 공간에서 u에서 시작한 임의보행이 v에 도달할 확률을 최대화한다는 것과 같은 얘기다. 

random wali embedding을 최적화한다 = 손실함수를 최소화하는 embedding $z_{u}$를 찾겠다.

 

임베딩 공간에서 정점 u에서 시작한 임의 보행이 정점 v에 도달할 확률은 softmax를 사용하여 아래와 같이 구한다.

당연히 유사도가 높을수록 내적값도 높고 도달확률도 높아진다. 

 

이 방법은 확실히 이전 인접성 기반 접근법과 비교했을 때, 효율적이다.

우선 한번에 local 한 정보와 global한 정보를 얻을 수 있다.

그리고 모든 정점 쌍에 대해 고려하지 않고 지나온 길들만 고려하기 때문이다.

 

하지만 시간 복잡도는 정점의 수의 제곱에 비례하게 된다.

시그마만 총 3번 들어가고 $u \in V$와 $n \in V$가 중첩되기 때문이다. 

 

문제점을 normalization term으로 보고 더 빠르면서도 근사할 수 있는 식으로 대체하게 된다. 

모든 노드에 대해 정규화해주는 것이 아닌 k개의 "negative samples"에 대해서만 정규화 해주는 것이다.

연결성에 비례하는 확률로 negative sample들을 뽑아주고, 이게 많을수록 학습은 안정적이다.  5-20사이로 쓴다고 한다.

 

softmax를 근사하는 식이 sigmoid가 된 이유는 궁금하지만,,,, 조교님 피셜 어떤 기능을 하는지를 이해하는 게 더 중요하다고 하셨기 때문에 ㅎㅎ,,,, 우선 sigmoid를 써서 0과 1사이의 확률로 만들어준다.

 

 

• Node2Vec

DeepWalk와의 가장 큰 차이점은 직전 정점의 거리를 기준으로 경우를 구분해 차등적인 확률을 부여한다는 점이다.

node2vec은 word2vec의 graph 버전이다. word2vec과 비교하면서 공부해보자.

 

word2vec은 "The fat cat sat on the mat"이라는 corpus 내 문장이 주어졌을 때, window_size만큼 자기 주변을 고려해서 input으로 넣어준다. 예를 들어 sat이 기준이면 fat cat sat on the mat이렇게 앞뒤로 2개씩을 고려해주는거다.

그러면 graph에서는 뭐가 문장역할을 하고 어떻게 앞뒤를 세서 인풋으로 넣어줄까?

일단 임의보행 (random walk)를 통해서 "문장역할"을 하는 일종의 sequence를 얻게 된다. 

사용자가 미리 정해준 walk of length는 sequence의 길이가 된다.

여기서의 random walk가 DeepWalk와의 가장 큰 차이점이다.

node2vec의 random walk 방식을 설명하려면 bfs, dfs가 의미하는 것이 무엇인지 알아야한다. 

 

BFS, DFS에 대한 설명은 따로 하지 않겠다. 알고리즘 공부했다면 다 알 거다.

BFS는 너비우선으로 자기 주변부를 우선시하게 되므로 local 적인 걸 보게 된다.

"비슷한 노드는 서로 공통적으로 연결되어 있는 노드가 많다"라는 개념을 기반으로 하는 Network Homophily에 집중하게 된다. 

DFS는 깊이우선으로 계속 멀리 나가게 되면서 global한 정점들을 보게 된다.  

"비슷한 네트워크는 서로 비슷한 구조적 위치에 존재한다"라는 개념의 structural equivalence에 집중하게 된다. 

 

node2vec은 biased 2nd order random walk 방식으로 네트워크의 이웃들을 탐방한다.

여기서의 2nd는 2개의 정점을 고려하겠다는 뜻인데 직전에 지나온 노드와 현재 노드를 고려하겠다는 뜻이다. 

s1을 거쳐 W까지 탐방했다. 이때 다음은 어디로 가야할까?

s1으로 돌아가면 이전 정점으로 돌아가기 때문에 거리가 0이 된다.  즉, 돌아가는 거다.

s2로 가게 되면 s1과의 거리는 그대로 1이 유지된다. 

s3 , s4로 가게 되면 거리는 2로 더 멀어지고 쭉쭉 뻗어나가는 것을 의미한다. 

 

그럼 이걸 위에서 봤던 dfs, bfs관점에서 바라보자.

 s1으로 돌아가는 것은 local한 정보를 탐색하겠다는 뜻이고, p를 통해서 직전꼭짓점으로 돌아올 가능성을 조절한다. 

이는 bfs스럽다고 표현할 수 있고, p는 주변을 얼마나 잘 탐색하는지에 대한 하이퍼파라미터가 된다. 

 s3,s4로 가는 것은 global한 정보를 탐색하겠다는 뜻이고, q를 통해서 직전 꼭짓점으로부터 얼마나 멀어질 지를 조절한다. 이는 dfs 스럽다고 표현할 수 있고, q는 새로운 곳을 얼마나 더 잘 발견하고 탐색하는 지에 대한 파라미터이다. 

 

p와 q를 어떻게 설정하냐에 따라 다른 종류의 임베딩을 얻게 된다. 

❗❗❗ 이 그림 이해가 안간다.

 

이런 식의 biased 2nd random walk를 통해서 사용자가 정해준 길이만큼 반복수행하게 되면 결국 거쳐간 정점들에 대한 시퀀스가 나오게 된다. 시퀀스에 대해서 windowsize만큼을 고려한 게 input으로 들어가고 layer하나를 거쳐 d차원 공간 위의 한 점으로 임베딩 된다. 

목적함수는 deepwalk와 동일하니 생략!

 

 

변환식 임베딩과 귀납식 임베딩

---

Deepwalk , node2vec과 같은 방법들을 우리는 변환식 임베딩이라고 한다. 

스탠포드 강의 자료를 보니 "shallow encoding"이라고 표현한다. 

그냥 embedding-lookup밖에 안된다고 표현하는데,,, 그도 그럴것이 그냥 matrix와 한 번 곱하는 게 다이기 때문이다.

어찌됐든 학습의 결과로 "정점의 임베딩 자체"를 얻는다는 거다.

정점을 임베딩으로 변화시키는 함수 즉 인코더를 얻은 귀납식방법과는 대조된다. 

이게 무슨 차이냐고 하면 어떤 한 문제집을 공부했을 때,  변환식은 답을 , 귀납식은 푸는 방법을 학습한 것이다. 

 

이렇게 되면 

1) 학습이 진행된 이후 추가된 정점에 대해서는 임베딩을 얻을 수 없다

-> 이러려면 embedding matrix의 차원을 중간에 바꿔줘야된다.

2 ) 모든 정점에 대한 임베딩을 미리 계산하여 저장한다.

3)  속성 정보를 가진 경우 활용할 수 없게 된다.