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

✅ 정점 표현 학습¶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

✅ 인접성 기반 접근법¶

1️⃣ 인접성 기반 접근법¶

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

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

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

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

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

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

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

군집 관점에서 보면

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

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

1️⃣ 거리 기반 접근법¶

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

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

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

2️⃣ 경로 기반 접근법¶

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

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

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

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

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

3️⃣ 중첩 기반 접근법¶

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

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

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

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

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

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

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

✅ 임의보행 기반 접근법¶

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

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

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

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

각 정점에서 시작하여 임의보행을 반복 수행한다.

각 정점에서 시작한 임의보행 중 도달한 정점들의 리스트를 구성한다. 이때, 정점$u$에서 시작한 임의 보행 중 도달한 정점들의 리스트를 $N_{R}(u)$라고 하면 한 정점을 여러 번 도달한 경우, 해당 정점은 $N_{R}(u)$에 여러 번 포함될 수 있다.

다음 손실함수를 최소화하는 임베딩을 학습한다.

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

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

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

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

2️⃣ DeepWalk와 Node2Vec¶

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

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

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

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

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

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

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

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

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

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

3️⃣ 손실 함수 근사¶

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

중첩된 합 때문에

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

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

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

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

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

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

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

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

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

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

📌Node2Vec¶

# 없을시 다운
import networkx as nx
from node2vec import Node2Vec
from matplotlib import pyplot as plt

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

##### 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 수행¶

Node2Vec?

node2vec.fit?

Object `node2vec.fit` not found.

# 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의 출력으로 얻은 정점들의 임베딩 확인¶

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]

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

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

#### Most Similar Nodes to Node 2

[('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)]

📌 군집 분석¶

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

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

# 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)

시각화¶

#### 그래프 시각화 - 각 클러스터별로 다른 색깔을 갖도록 함 ####
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()

📌 정점 분류¶

라이브러리 로드¶

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

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

# 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 수행¶

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

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

#### 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)

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

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)

성능 평가¶

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

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

Image classification I (0)	2021.03.08
그래프 신경망이란 무엇일까? (심화) (0)	2021.02.26
그래프 신경망이란 무엇일까? (기본) (1)	2021.02.26
그래프를 추천시스템에 어떠게 활용할까? (심화) (0)	2021.02.25
그래프를 추천시스템에 어떻게 활용할까?(기본) (0)	2021.02.24
그래프의 구조를 어떻게 분석할까? (0)	2021.02.24
그래프를 바이럴 마케팅에 어떻게 활용할까? (0)	2021.02.23
검색 엔진에서는 그래프를 어떻게 활용할까? (0)	2021.02.23

개발자CuCu