3. 노드 임베딩 (Node2Vec으로 간단한 추천시스템 구현)

Contents
1. 노드 표현
1.1 DeepWalk
1.2 Word2Vec

2. Node2Vec
2.1 Biased randomwalk
2.2 간단한 추천 시스템 구현

 

Node representation은 그래프에서 각 노드를 벡터 형태로 나타내는 방법입니다. 노드 표현은 그래프 기반 분석 및 다양한 그래프 기계 학습 작업에서 노드의 특성을 나타낼 때 사용합니다. 이번 포스팅에서는 두 가지 주요한 노드 표현 방법인 Word2Vec과 DeepWalk에 대해 알아보겠습니다. 이후 이 두가지 표현 방법에서 발전하여 노드에 대한 임베딩을 수행하는 Node2Vec 기법을 알아보고 간단한 추천 시스템을 구현해보겠습니다. 본 포스팅부터 본격적으로 그래프 뉴럴 네트워크에 대한 deep walk를 시작하겠습니다.

 

1. 노드 표현(Node Representaion)

이 장에서는 DeepWalk와 Word2Vec과 Random Walk 대해 알아보겠다. DeepWalk은 머신 러닝(ML) 기법을 그래프에 적용하기 위한 성공적인 방법 중 하나이다. 이는 GNN의 핵심인 임베딩과 같은 중요한 개념이다. Word2Vec은 자연어 처리에서 단어의 임베딩을 학습할때 사용하는 알고리즘으로, 이를 노드에 대한 표현으로 적용해본다. 여기서는 skip-gram, CBOW와 같은 자연어 처리의 기본 개념을 숙지한 것을 가정으로 진행하겠다. 만약 이 부분이 궁금하다면 아래 링크를 참조하기를 추천한다. (https://wikidocs.net/book/2155)

 

1.1 DeepWalk

Perozzi et al. (2014)에 의해 제안된 DeepWalk는 NLP에서 사용하는 방법과 같이 인접 노드에 대한 정보를 바탕으로, 현재 노드의 상태를 학습한다. DeepWalk는 Word2Vec 기법의 아이디어를 통해, 풍부한 노드 표현을 얻는 것을 목표로 한다. Random walks은 각 스텝에서 무작위로 이웃 노드를 선택하여 생성되는 노드의 시퀀스이다. 따라서 노드는 동일한 시퀀스에서 여러 번 나타날 수 있다.

 

각 토큰을 다음과 같이 나타내고, 토큰의 시퀀스를 문장으로 표현한다.

 

이는 각 토큰을 노드로 하는 그래프로 표현할 수 있다.

표현된 그래프에서 인접 노드를 랜덤 하게 탐색하는 Random walk 알고리즘을 적용하여, 새로운 시퀀스를 만들 수 있다. 이 시퀀스는 NLP에서 새로운 문장으로 이해할 수 있다.

 

 

노드가 무작위로 선택되더라도, 동일한 시퀀스에서 자주 함께 나타나는 것은 그들이 서로 가까이에 있다는 것을 의미한다. 이는 network homophily 이론을 기반으로 한다. 따라서 서로 가까이 연결된 노드는 성질이 유사하다는 것을 의미한다. 이 아이디어는 DeepWalk 알고리즘의 핵심이다. 노드가 서로 가까울 때 높은 유사도를 가지며 노드가 멀리 떨어져 있을 때는 낮은 점수를 갖는다. 다음은 랜덤 워크를 구현하는 코드이다.

import networkx as nx
import matplotlib.pyplot as plt

# Create a graph
# 노드의 개수는 10으로 고정
# 두 노드 간의 엣지를 만드는 확률은 0.3으로 설정함
G = nx.erdos_renyi_graph(10, 0.3, seed=1, directed=False)

# Plot graph
plt.figure()
plt.axis('off')
nx.draw_networkx(G,
                 pos=nx.spring_layout(G, seed=0),
                 node_size=600,
                 cmap='coolwarm',
                 font_size=14,
                 font_color='white'
                 )

 

• 랜덤 워크 함수는 시작 노드와, 원하는 시퀀스의 길이, 두 가지 파라미터를 받는다.
• 매 스텝마다 랜덤하게 이웃 노드를 선택한다. (np.random.choice)를 사용한다.
• 시퀀스의 길이만큼 반복문을 진행한다.

import random
random.seed(0)

def random_walk(start, length):
    walk = [str(start)]  # starting node

    for i in range(length):
        neighbors = [node for node in G.neighbors(start)]
        next_node = np.random.choice(neighbors, 1)[0]
        walk.append(str(next_node))
        start = next_node

    return walk

# Create a list of random walks
print(random_walk(0, 10))

### result ###

['0', '1', '9', '1', '0', '4', '6', '7', '6', '5', '6']

 

1.2 Word2Vec

랜덤 워크를 통해 얻은 시퀀스를 바탕으로, 노드의 representation을 학습하기 위해 word2vec을 사용한다. 그래프로 사용할 데이터는 Zachary`s Karate Club 데이터로, 그래프 이론에서 유명한 소셜 데이터이다. 데이터는 두 그룹으로 나눠진다.

 

# Load dataset
G = nx.karate_club_graph()

# Process labels (Mr. Hi = 0, Officer = 1)
labels = []
for node in G.nodes:
    label = G.nodes[node]['club']
    labels.append(1 if label == 'Officer' else 0)
    
# Plot graph
plt.figure(figsize=(12,12))
plt.axis('off')
nx.draw_networkx(G,
                 pos=nx.spring_layout(G, seed=0),
                 node_color=labels,
                 node_size=800,
                 cmap='coolwarm',
                 font_size=14,
                 font_color='white'
                 )

이후 길이가 10인 랜덤워크를 생성한다. 이때 학습을 충분하게 진행하기 위해, 각 노드별로 80번의 랜덤 한 시퀀스를 생성하였다.

# Create a list of random walks
walks = []
for node in G.nodes:
    for _ in range(80):
        walks.append(random_walk(node, 10))

# Print the first random walk
print(walks[0])

### result ###

['0', '10', '0', '17', '0', '2', '13', '0', '2', '9', '33']

 

하나의 시퀀스는 NLP에서 길이가 10인 sentence들로 볼 수가 있다. 따라서 각 노드의 임베딩을 얻기 위해 word2vec을 사용한 코드이다.

# Create Word2Vec
model = Word2Vec(walks,
                 hs=1,   # Hierarchical softmax
                 sg=1,   # Skip-gram
                 vector_size=100,
                 window=10,
                 workers=1,
                 seed=1)

print(f'Shape of embedding matrix: {model.wv.vectors.shape}')

# Build vocabulary
model.build_vocab(walks)

# Train model
model.train(walks, total_examples=model.corpus_count, epochs=30, report_delay=1)

# Most similar nodes
print('Nodes that are the most similar to node 0:')
for similarity in model.wv.most_similar(positive=['0']):
    print(f'   {similarity}')

# Similarity between two nodes
print(f"\nSimilarity between node 0 and 4: {model.wv.similarity('0', '4')}")

### result ###

Nodes that are the most similar to node 0:
   ('7', 0.6418899893760681)
   ('11', 0.6362671256065369)
   ('10', 0.6353005766868591)
   ('4', 0.6283879280090332)
   ('1', 0.6240326762199402)
   ('17', 0.6081677675247192)
   ('6', 0.5763440132141113)
   ('5', 0.5598748326301575)
   ('21', 0.5572237372398376)
   ('16', 0.550387442111969)

Similarity between node 0 and 4: 0.6283879280090332

 

2. Node2Vec

Node2Vec은 Leskovec 교수님에 의해 2016년에 소개되었다. Node2Vec과 DeepWalk의 차이점은 균일한 분포로 노드의 시퀀스를 얻는 대신, Node2Vec에서는 무작위성이 편향된다는 것이다. 이후 이러한 biased random walk가 더 나은 성능을 보여주는 것을 구현할 것이다. 먼저 이해를 위한 두 가지 개념을 소개하겠다.

• Structural equivalence: 그래프에서 노드 간의 관계가 유사한 경우를 나타낸다. 예를 들어, 두 노드가 비슷한 이웃을 가지고 있거나 서로 비슷한 다른 노드와 연결되어 있다면 구조적으로 동등하다고 볼 수 있다. 구조적 동등성은 네트워크에서 특정한 패턴이나 구조를 공유하는 노드들을 식별하는 작업에 사용된다.
• Homophily: 그래프에서 유사한 특성을 가진 노드들이 연결되는 경향을 나타낸다. 이는 네트워크 상에서 비슷한 속성이나 관심사를 가진 노드들이 서로 연결되는 현상을 의미한다. 동질성은 소셜 네트워크에서 특히 중요하다. 이는 친구나 가족과 연결되어 있는 사람들이 유사한 특성을 가지고 있을 가능성이 높기 때문이다.

 

Node2Vec에서는 두 성질을 활용하여 노드의 이웃을 정의한다. 특히 앞선 포스팅에서 살펴본, BFS와 DFS 방식이 이웃 탐색을 위한 방법으로 사용된다.

• BFS 방식은 노드에서 시작하여 한 단계씩 이웃 노드를 탐색하고, 그다음 단계의 이웃을 계속 탐색한다. 노드와 동일한 거리에 있는 이웃을 우선적으로 탐색하며, structural equivalence에 기반하여 이웃을 선택합니다.
• DFS 방식은 한 노드에서 시작하여 가능한 한 깊이 들어가서 이웃을 탐색한다. 노드의 근접 이웃들과 연결된 더 멀리 있는 이웃들을 우선적으로 탐색하며, Homophily 기반하여 이웃을 선택한다.

 

2.1 Biased Node2Vec

Node2Vec은 그래프 임베딩 방법 중 하나로, DeepWalk의 개선된 버전이다. Node2Vec은 그래프 내에서 노드 간의 구조를 보다 잘 반영하기 위해 두 가지 유형의 무작위 보행을 사용한다. Biased randomwalk는 그래프에서 특정 유형의 경로를 더 자주 탐색하도록 편향을 주는 방식이다. 이를 통해 노드 간의 군집성과 구조적 유사성을 잘 반영한 임베딩을 얻을 수 있다. 

 

이때, Node2Vec에서 편향을 추가하기 위해 사용되는 원리는 아래 그림과 같다.

각각의 파라미터는 다음과 같은 역할을 한다.

• p값: 이전 노드로 돌아가는 확률이다. p값은 현재 노드의 이전 노드로 돌아가는 것을 선호하는 정도를 나타낸다. 즉, p값이 높을수록 이전 노드로 돌아가는 확률이 낮아진다. p값이 클수록 특정 새로운 노드를 탐색하는 경향이 크다. 이는 구조적 동등성을 고려하여 노드 간의 구조적 유사성을 강조하는 역할을 한다.
• q값: q 값이 높을수록 이전 노드에 가까운 노드에 집중하며 BFS와 유사한 형태를 나타낸다. 이는 이전 노드와 가까운 이웃 노드에 더 많은 가중치를 두어 탐색하는 특성을 나타낸다. q값이 클수록 동질성을 고려하여 비슷한 특성을 가진 노드를 방문하는 경향이 있다.

 

이때 DeepWalk는 p와 q가 모두 1인 Node2Vec의 특별한 케이스로 이해할 수 있다.

 

2.2 간단한 추천 시스템 구현

본 장에서는 이러한 biased randomwalk를 사용하여 노드의 임베딩을 나타내는 Node2Vec 기법을 적용하여 간단한 추천 시스템을 구현하겠다. 추천 시스템을 구현하기 위해서 유저 - 아이템의 이분 그래프를 생성해야 한다. 이 섹션에서는 간단하고 직관적인 접근 방식을 구현하였다. movielens 데이터를 사용하여 동일한 사용자가 좋아하는 영화들을 연결하였다. 이러한 정보를 그래프로 표현하여 Node2Vec을 통해 아이템인 영화 임베딩을 학습하였다.

 

from io import BytesIO
from urllib.request import urlopen
from zipfile import ZipFile

url = 'https://files.grouplens.org/datasets/movielens/ml-100k.zip'
with urlopen(url) as zurl:
    with ZipFile(BytesIO(zurl.read())) as zfile:
        zfile.extractall('.')
        
import pandas as pd

ratings = pd.read_csv('ml-100k/u.data', sep='\t', names=['user_id', 'movie_id', 'rating', 'unix_timestamp'])

movies = pd.read_csv('ml-100k/u.item', sep='|', usecols=range(2), names=['movie_id', 'title'], encoding='latin-1')

# 4점 이상 평점을 준 레이팅 정보만 사용한다.
ratings = ratings[ratings.rating >= 4]
ratings

 

- 그래프 만들기

from collections import defaultdict

# defaultdict을 통해 자동적으로 결측 값을 무시하는 딕셔너리를 생성함.
# 링크가 존재하는 영화를 저장하기 위해 사용함
pairs = defaultdict(int)

# Loop through the entire list of users
for group in ratings.groupby("user_id"):
    # List of IDs of movies rated by the current user
    user_movies = list(group[1]["movie_id"])

    # Count every time two movies are seen together
    for i in range(len(user_movies)):
        for j in range(i+1, len(user_movies)):
            pairs[(user_movies[i], user_movies[j])] += 1
            
pairs

### result ###

defaultdict(int,
            {(61, 33): 4,
             (61, 160): 6,
             (61, 20): 4,
             (61, 202): 4,
             (61, 171): 6,
             (61, 265): 8,
             ...

- 두 영화 페어가 20번 이상 같은 유저에 의해 시청된, 페어만을 필터링하여 그래프를 그린다.

- 이때 두 영화가 얼마나 가까운지를 나타내는 edge의 weight는 두 영화가 함께 시청된 횟수를 지정하였다.

# Create a networkx graph
G = nx.Graph()

# Try to create an edge between movies that are liked together
for pair in pairs:
    movie1, movie2 = pair
    score = pairs[pair]

    # The edge is only created when the score is high enough
    if score >= 20:
        G.add_edge(movie1, movie2, weight=score)

print("Total number of graph nodes:", G.number_of_nodes())
print("Total number of graph edges:", G.number_of_edges())

### result ###

Total number of graph nodes: 410
Total number of graph edges: 14936

- 마지막으로 Node2Vec을 적용하여 생성된 그래프에 대해 노드 임베딩을 학습한다.

- 각 노드를 표현하는 dimension은 64, 노드 시퀀스의 길이는 20, 시퀀스의 개수는 200, p값과 q값은 각각 2, 1이다.

- 이후 recommend 함수에 인자를 입력하여, 가장 유사도가 높은 노드, 즉 영화 5개를 추천해 준다.

from node2vec import Node2Vec

node2vec = Node2Vec(G, dimensions=64, walk_length=20, num_walks=200, p=2, q=1, workers=1)

model = node2vec.fit(window=10, min_count=1, batch_words=4)

def recommend(movie):
    movie_id = str(movies[movies.title == movie].movie_id.values[0])
    for id in model.wv.most_similar(movie_id)[:5]:
        title = movies[movies.movie_id == int(id[0])].title.values[0]
        print(f'{title}: {id[1]:.2f}')

recommend('Star Wars (1977)')

### result ###

Return of the Jedi (1983): 0.61
Raiders of the Lost Ark (1981): 0.55
Godfather, The (1972): 0.49
Indiana Jones and the Last Crusade (1989): 0.46
White Squall (1996): 0.44

 

Reference 

Hands-On Graph Neural Networks Using Python, published by Packt.