AI/이론

그래프의 정점을 어떻게 벡터로 표현할까?

N-analyst 2021. 2. 25. 23:11
그래프의 정점을 어떻게 벡터로 표현할까

그래프의 정점을 어떻게 벡터로 표현할까?

✅ 정점 표현 학습

1️⃣ 정점 표현 학습이란?

📌 정점 표현 학습이란 그래프의 정점들을 벡터의 형태로 표현하는 것이다.

  • 정점 표현 학습은 간단히 정점 임베딩(Node Embedding)이라고도 부른다.
  • 정점 임베딩은 벡터 형태의 표현 그 자체를 의미하기도 한다.
  • 정점이 표현되는 벡터 공간을 임베딩 공간이라고 부른다.

image.png



  • 정점 표현 학습의 입력은 그래프이다.
  • 주어진 그래프의 각 정점 $u$에 대한 임베딩, 즉 벡터 표현 $z_{u}$가 정점 임베딩의 출력이다.

image.png


2️⃣ 정점 표현 학습의 이유

📌 정점 임베딩의 결과로, 벡터 형태의 데이터를 위한 도구들을 그래프에도 적용할 수 있기때문이다.

기계학습 도구들이 한가지 예시이다.

  • 분류기(로지스틱 회귀분석, 다층 퍼셉트론 등)
  • 군집 분석 알고리즘(K-Means, DBSCAN 등)

위 예시는 벡터 형태로 표현된 사례들을 입력으로 받고 있다.

그래프의 정점들을 벡터 형태로 표현할 수 있다면, 위의 예시와 같은 대표적인 도구들 뿐 아니라, 최신의 기계 학습도구들을 정점 분류(Node Classification), 군집 분석(Community Detection)등에 활용할 수 있다.


3️⃣ 정점 표현의 학습의 목표

📌 어떤 기준으로 정점을 벡터로 변환해야할까?

  • 그래프에서의 정점간 유사도를 임베딩 공간에서도 "보존"하는 것을 목표로 한다.
  • 그래프에서 유사한 정점들은 임베딩 공간에서도 근처에 존재하게 해야한다.

image.png


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

임베딩 공간에서의 $u$와 $v$의 유사도는 두 임베딩의 내적 $z_{v}^{T}z_{u} = \parallel z_{u}\parallel\cdot\parallel z_{v} \parallel\cdot\cos (\theta)$ 이다. 내적은 두 벡터가 클 수록, 그리고 같은 방향을 향할 수록 큰 값을 갖는다.

image.png


📌 그렇다면 그래프에서의 두 정점간 유사도는 어떻게 정의할까?

이 질문에 여러가지 답이 있을 수 있다.
아래 대표적인 몇가지 답을 설명한다.

따라서 정점 임베딩은 다음 두 단계로 이루어진다.

  1. 그래프에서의 정점 유사도를 정의하는 단계
  2. 정의한 유사도를 보존하도록 정점 임베딩을 학습하는 단계



✅ 인접성 기반 접근법

1️⃣ 인접성 기반 접근법

📌 인접성(adjacency) 기반 접근법에서는 두 정점이 인접할 때 유사하다고 간주한다.

  • 두 정점 $u$와 $u$인접하다는 것은 둘을 직접 연결하는 간선$(u,v)$가 있음을 의미한다.
  • 인접행렬(Adjacency Matrix)A의 $u$행 $v$열 원소 $A_{u,v}$는 $u$와 $v$가 인접한 경우 1아닌 경우 0이다.
  • 인접행령의 원소 $A_{u,v}$를 두 정점 $u$와 $v$의 유사도로 가정한다.

image.png


📌 인접성 기반 접근법의 손실 함수(Loss Function)는 아래와 같다.

  • 즉, 이 손실 함수가 최소가 되는 정점 임베딩을 찾는것을 목표로 한다.
  • 손실 함수 최소화를 위해서는 (확률적) 경사하강법 등이 사용된다.

image.png



2️⃣ 인접성 기반 접근법의 한계

📌 인접성만으로 유사도를 판단하는 것은 한계가 있다.

  • 빨간색 정점과 파란색 정점은 거리가 3인 반면
  • 초록색 정점과 파란색 정점은 거리가 2이다.
  • 인접성만 고려할 경우 이러한 사실에 대한 고려 없이, 두 경우의 유사도는 0으로 같다.

image.png

군집 관점에서 보면

  • 빨간색 정점과 파란색 정점은 다른 군집에 속하는 반면
  • 초록색 정점과 파란색 정점은 같은 군집에 속합니다.
  • 인접성만을 고려할 경우 이러한 사실에 대한 고려 없이, 두 경우의 유사도는 0이다.



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

1️⃣ 거리 기반 접근법

📌 거리 기반 접근법에서는 두 정점 사이의 거리가 충분히 가까운 경우 유사하다고 간주

예를 들어, "충분히"의 기준을 2로 가정

  • 빨간색 정점은 초록색 그리고 파란색 정점들과 유사합니다. 즉 유사도가 1이다.
  • 반면, 빨간색 정점은 보라색 정점과는 유사하지 않습니다. 즉 유사도가 0이다.

image.png


2️⃣ 경로 기반 접근법

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

정점 $u$와 $v$의 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequnce)이다.

  1. $u$에서 시작해서 $v$에서 끝나야 한다.
  2. 순열에서 연속된 정점은 간선으로 연결되어 있어야 한다.

image.png


두 정점 $u$와 $v$ 사이의 경로 중 거리가 $k$인 것의 수는 $A_{u,v}^{k}$와 같다. 즉 인접 행렬 A의 $k$ 제곱의 $u$행 $v$열 원소와 같다.

경로 기반 접근법의 손실 함수는 아래와 같다

image.png


3️⃣ 중첩 기반 접근법

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

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

image.png


정점 $u$의 이웃 집합을 $N(u)$그리고 정점 $v$의 이웃 집합을 $N(v)$라고 하면 두 정점의 공통 이웃 수 $S_{u,v}$는 다음과 같이 정의 된다.

image.png



중첩 기반 접근법의 손실 함수는 다음과 같다.

image.png


📌 공통 이웃 수 대신 자카드 유사도 혹은 Adamic Adar 점수를 사용할 수도 있다.

  1. 자카드 유사도(Jaccard Similarity)는 공통 이웃의 수 대신 비율을 계산하는 방식

image.png


  1. Adamic Adar 점수는 공통 이웃 각각에 가중치를 부여하여 가중합을 계산하는 방식
    • 여기서 $d_{w}$는 $w$의 연결성을 의미한다.

image.png



✅ 임의보행 기반 접근법

1️⃣ 임의보행 기반 접근법

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

  • 임의보행이란 현재 정점의 이웃 중 하나를 균일한 확률로 선택하여 이동하는 과정을 반복하는 것을 의미한다.
  • 임의보행을 사용할 경우 시작 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있다.

image.png


📌 임의보행 기반 접근법은 3단계를 거친다.

  1. 각 정점에서 시작하여 임의보행을 반복 수행한다.
  1. 각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성한다. 이때, 정점$u$에서 시작한 임의 보행 중 도달한 정점들의 리스트를 $N_{R}(u)$라고 하면 한 정점을 여러 번 도달한 경우, 해당 정점은 $N_{R}(u)$에 여러 번 포함될 수 있다.
  1. 다음 손실함수를 최소화하는 임베딩을 학습한다.

image.png


📌 어떻게 임베딩으로부터 도달 확률을 추정할까?

정점 $u$에서 시작한 임의보행이 정점$v$에 도달할 확률 $P(v|z_{u})$을 다음과 같이 추정한다.

image.png

  • 여기서 $V$는 모든 정점을 의미한다.
  • 모든 정점에 대해서 정규화를 진행.
  • 즉 유사도 $z_{v}^{T}z_{u}$가 높을 수록 도달 확률이 높다.

추정한 도달 확률을 사용하여 손실함수를 완성하고 이를 최소화하는 임베딩을 학습한다.

image.png


2️⃣ DeepWalk와 Node2Vec

📌 임의보행의 방법에 따라 DeepWalk와 Node2Vec이 구분된다.

  • DeepWalk는 앞서 설명한 기본적인 임의보행을 사용한다.
  • 즉, 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동 과정을 반복한다.


📌 Node2Vec은 2차 치우친 임의보행(Second-order Biased Random Walk)를 사용한다.

  • 현재 정점(예시에서 $v$)과 직전에 머물렀던 정점(예시에서 $u$)을 모두 고려하여 다음 정점을 선택한다.
  • 직전 정점의 거리를 기준으로 경우를 구분하여 차등적인 확률을 부여한다.

image.png


📌 Node2Vec에서는 부여하는 확률에 따라서 다른 종류의 임베딩을 얻는다.

  • 차등적인 확률은 사용자가 지정해 줄 수 있다.
  • 아래 그림은 Node2Vec으로 임베딩을 수행한 뒤, K-means 군집 분석을 수행한 결과이다.

image.png



멀어지는 방향에 높은 확률을 부여한 경우,

  • 정점의 역할(다리 역할, 변두리 정점 등)이 같은 경우 임베딩이 유사하다.

image.png



가까워지는 방향에 높은 확률을 부여한 경우,

  • 같은 군집(Community)에 속한 경우 임베딩이 유사하다.

image.png


3️⃣ 손실 함수 근사

📌 임의보행 기법의 손실함수는 계산에 정점의 수의 제곱에 비례하는 시간이 소요된다.

  • 중첩된 합 때문에

image.png


📌 따라서 근사식을 사용하게 된다.

  • 모든 정점에 대해서 정규화하는 대신 몇 개의 정점을 뽑아서 비교하는 형태이다.
  • 이 때 뽑힌 정점들을 네거티브 샘플이라고 부른다.

image.png

  • 연결성에 비례하는 확률로 네거티브 샘플을 뽑으며, 네거티브 샘플이 많을 수록 학습이 더욱 안정적이다.



✅ 변환식 정점 표현 학습의 한계

1️⃣ 변환식 정점 표현 학습과 귀납식 정점 표현 학습

📌 지금까지 본 정점 임베딩 방법들은 변환식(Transductive)방법이다.

  • 변환식 방법은 학습의 결과로 정점의 임베딩 자체를 얻는다는 특성이 있다.
  • 정점을 임베딩으로 변화시키는 함수, 즉 인코더를 얻는 귀납식(Inductive)방법과 대조된다.

image.png


📌 변환식 임베딩 방법은 여러 한계를 갖는다.

  1. 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없다.
  2. 모든 정점에 대한 임베딩을 미리 계산하여 저장해 두어야 한다.
  3. 정점이 속성(Attribute)정보를 가진 경우에 이를 활용할 수 없다.

✅ Node2Vec을 사용한 군집 분석 및 정점 분류

📌Node2Vec

In [1]:
# 없을시 다운
import networkx as nx
from node2vec import Node2Vec
from matplotlib import pyplot as plt

소설 등장인물 간의 공동 등장 그래프

In [2]:
##### Weighted Graph Generation #####
weighted_edgelist=[]
with open('../실습코드/data/lab/lab7/lesmis.mtx', 'r') as f:
    for line in f:
        l = line.strip().split()
        if l[0].isdigit() == False:
            continue
        weighted_edgelist.append((str(int(l[0])-1), str(int(l[1])-1), float(l[2])))


G = nx.Graph()
G.add_weighted_edges_from(weighted_edgelist)

Node2Vec 수행

In [3]:
Node2Vec?
In [4]:
node2vec.fit?

Object `node2vec.fit` not found.
In [5]:
# edge 별 확률 계산(p, q에 따른 edge별 확률 계산) & random walk 생성 
node2vec = Node2Vec(G, dimensions=16, walk_length=4, num_walks=200, workers=4)  # p = 1, q = 1 as default
# node embedding 구하기
model = node2vec.fit(window=2, min_count=1, batch_words=4)





















Node2Vec의 인자를 살펴보자


    

  • graph: 입력으로 들어갈 그래프를 넣어준다.
    • 

  • dimension: 임베딩 차원
    • 

  • walk_length: random walk의 길이를 제한
    • 

  • num_walks: 시작지점별 샘플링하는 random walk의 수를 지정
    • 

  • workers: 사용하는 스레드 갯수 지정

    • 



model.fit의 인자


    

  • window: 임의보행 상에서 얼마나 가까이에 위치한 정점들을 유사한 것으로 보는지와 관련된 인자
    • 
















Node2Vec의 출력으로 얻은 정점들의 임베딩 확인












In [6]:



    


print("#### Embedding Vector of Node 2 ####")
print(model.wv['2'])



    















    






#### Embedding Vector of Node 2 ####
[-0.29162323 -0.75107276 -0.08837654  0.20485903 -0.63520414 -0.35433483
  0.9141787   1.0550616   0.9444821   0.9800188  -0.34103894 -0.69588065
 -0.80140376 -0.60213053  1.0149325   0.09205327]



















In [7]:



    


##### Node 2와 가장 유사한 10개의 node를 출력 #####

print("#### Most Similar Nodes to Node 2")
model.wv.most_similar('2')  



    















    






#### Most Similar Nodes to Node 2










    
Out[7]:








[('3', 0.99619460105896),
 ('6', 0.9952034950256348),
 ('5', 0.9936782121658325),
 ('7', 0.9926062226295471),
 ('1', 0.9918403029441833),
 ('8', 0.9911578893661499),
 ('4', 0.9894993305206299),
 ('9', 0.9883965253829956),
 ('0', 0.9793883562088013),
 ('14', 0.6393628120422363)]
























📌 군집 분석












In [8]:



    


from sklearn.cluster import KMeans
import numpy as np
from matplotlib import pyplot as plt



    















정점 임베딩을 입력으로 K-Means를 수행하여 정점의 군집을 찾는다.












In [9]:



    


# sklearn.cluster의 KMeans 알고리즘을 실행시키기 위해 node별 embedding 값을 array로 변환해준다 
# 노드 번호에 해당하는 index에 embedding 값을 저장
vectors_array = np.zeros((len(G.nodes), 16))
for node in G.nodes:
    vectors_array[int(node)] = model.wv[node]

# kmeans clustering 알고리즘 실행
kmeans = KMeans(n_clusters=5, random_state=0).fit(vectors_array)



    















시각화












In [10]:



    


#### 그래프 시각화 - 각 클러스터별로 다른 색깔을 갖도록 함 ####
pos = nx.spring_layout(G)
node_color=[]
node_degree = []
for node in G.nodes:
    node_degree.append(G.degree[node]*10)
    i = int(node)
    if kmeans.labels_[i] == 0:
        node_color.append('red')
    elif kmeans.labels_[i] == 1:
        node_color.append('yellow')
    elif kmeans.labels_[i] == 2:
        node_color.append('blue')
    elif kmeans.labels_[i] == 3:
        node_color.append('green')
    else:
        node_color.append('orange')

img = nx.draw_networkx_nodes(G, pos, node_color = node_color, node_size=node_degree)
nx.draw_networkx_edges(G, pos)
plt.show()



    















    































📌 정점 분류














라이브러리 로드












In [11]:



    


from sklearn.model_selection import train_test_split
from sklearn.neural_network import MLPClassifier
from sklearn.metrics import mean_squared_error, accuracy_score



    















논문 간의 인용 네트워크, 논문의 주제가 정점의 유형으로 주어진다.












In [12]:



    


# Directed Graph Generation 
# 메모리 활용을 위해 node class는 숫자로 re-labelling하여 사용
node_class = dict()
edgelist = list()
class_num = 1
class_name_to_num = dict()
with open('../실습코드/data/lab/lab7/cora.content', 'r') as f, open('../실습코드/data/lab/lab7/cora.cites','r') as f2:
    for line in f:
        l = line.strip().split()
        class_name = l[-1]
        if class_name not in class_name_to_num:
            class_name_to_num[class_name] = class_num
            class_num += 1
        node_class[l[0]] = class_name_to_num[class_name]

    for line in f2:
        l = line.strip().split()
        edgelist.append((l[1],l[0]))


G = nx.DiGraph()
G.add_edges_from(edgelist)



    















Node2Vec 수행












In [13]:



    


import time

s= time.time()
##### Node Embedding #####
node2vec = Node2Vec(G, dimensions=32, walk_length=50, num_walks=200, workers=4)  
model = node2vec.fit(window=10, min_count=1, batch_words=4) 
print("runtime: ", time.time() - s)



    















    






 
 















    






runtime:  492.96851205825806





















정점 임베딩을 학습 데이터와 평가 데이터로 분리












In [14]:



    


#### X : embedding of a node, y : class label of a node ####

X = list()
y = list()
node_name_to_idx = dict()
for i, (v, class_) in enumerate(node_class.items()):
    node_name_to_idx[v] = i
    X.append(model.wv[v])
    y.append(class_)
X = np.array(X)
y = np.array(y)

X_train, X_test, y_train, y_test = train_test_split(X, y, shuffle= True)



    















학습 데이터를 사용하여 분류기인 다층퍼셉트론을 학습












In [15]:



    


clf = MLPClassifier(max_iter=500).fit(X_train, y_train)
y_predict = clf.predict(X_test)



    















    






C:\Users\won\anaconda3\envs\pydatavenv\lib\site-packages\sklearn\neural_network\_multilayer_perceptron.py:585: ConvergenceWarning: Stochastic Optimizer: Maximum iterations (500) reached and the optimization hasn't converged yet.
  % self.max_iter, ConvergenceWarning)





















성능 평가












In [16]:



    


print("###### Result of prediction #####")
print("Accuracy : {0:05.2f}% ".format(accuracy_score(y_test, y_predict)*100))



    















    






###### Result of prediction #####
Accuracy : 76.51%