Node2Vec은 그래프에서 노드 간의 관계를 임베딩 벡터로 학습하기 위한 알고리즘입니다.
DeepWalk의 확장된 버전으로, 랜덤 워크(Random Walk)의 유연성을 추가하여 그래프의 구조적 특성과 노드 간 유사성을 효과적으로 학습합니다.
Node2Vec 은 전용 파이썬 라이브러리인 node2vec을 사용할 수 있습니다.
Node2Vec의 핵심 아이디어
- 랜덤 워크의 개선:
- Node2Vec은 단순 랜덤 워크가 아닌, 편향된 랜덤 워크(Biased Random Walk)를 사용합니다.
- 두 가지 파라미터 p와 q를 통해 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 균형 있게 조절합니다.
- Word2Vec 활용:
- Node2Vec은 생성된 랜덤 워크 시퀀스를 Word2Vec의 입력으로 사용하여 노드 임베딩을 학습합니다.
- Skip-gram 또는 CBOW 모델을 활용해 노드 간의 유사성을 학습.
그래프 탐색
그래프 탐색 알고리즘은 하나의 시작점 노드에서 연결된 노드들은 모두 찾는 알고리즘입니다.
그래프 탐색 알고리즘ㅇㄴ 각 노드들을 어떤 순서로 탐색하는지에 따라 크게 두가지 종류로 나눕니다.
너비 우선 탐색(Breadth-First Search, BFS), 깊이 우선 탐색(Depth-First Search, DFS)
1) BFS(Breadth First Search)
Breath는 영어로 너비를 뜻하는 말로, BFS는 너비 우선 탐색입니다.
A의 인접한 노드들로 부터, 즉 시작점으로 부터 가까운 노드들을 탐색하여 인접 노드를 탐색하는 방식, 깊이 보다 너비를 우선으로 탐색하여 너비 우선 탐색이라고 합니다.
BFS 알고리즘 순서
1. 시작노드를 방문 표시 후, Queue에 넣음
2. while Queue.isEmpty():
Queue의 가장 앞 노드를 꺼낸다.
꺼낸 노드의 인접한 노드를 모두 찾는다:
if 꺼낸 노드가 처음 방문:
방문 표시
큐에 넣는다.
BFS 시간 복잡도 : O(V+E)
2) 깊이 우선 탐색(Depth-First Search, DFS)
하나의 노드에서 시작해서 최대한 깊이 멀리 탐색하는 방법입니다.
깊이 우선 탐색은 큐 대신 스택을 사용합니다.
A B D G J
E H
C F I
DFS 알고리즘
(처음에 모든 노드를 방문하지 않았다고 표시)
시작점 노드를 옅은 회색 표시 후, 스택에 넣는다
스택에 아무 노드도 없을 때까지:
스택에서 가장 위 노드를 꺼냅니다
(방문 처리) 표시
이 노드에 인접해 있는 노드들을 돌면서:
처음방문 노드면:
방문 표시
스택에 넣는다
DFS 시간 복잡도 : O(V+E)
3) 구조적 동등성(Structural equlvalence), 동질성(homophily)
DFS와 BFS를 설명한 이유는 구조적 동등성과 동질성 때문입니다.
구조적 동등성은 노드들이 많은 수의 동일 이웃을 공유할 경우 구조적으로 동등하다는 의미입니다.
동질성은 비슷한 노드들이 더 연결될 가능성이 높다는 것을 의미합니다.
BFS와 DFS 가 구조적 동등성과 동질성을 향상시킨다고 하는데, 상반된 의견이 있습니다.
DFS가 동질성을 강조하고, BFS가 구조적 동등성과 관련있다는 의견이 있고 반대 논문들도 많습니다.
BFS가 주변 노드만 관찰하여 구조적 동등성을 향상시키고, DFS는 동질성의 반대를 강조한다는 의견이 있습니다.
| 정의 | 두 노드가 동일한 이웃을 가질 때, 즉 동일한 노드들과 연결되어 있을 때 구조적 동등성을 가진다고 합니다. | 연결된 노드들이 유사한 특성이나 속성을 공유하는 경향을 동질성이라고 합니다. 이는 "유유상종"의 원리로도 알려져 있습니다. |
| 초점 | 노드 간의 연결 패턴에 중점을 둡니다. | 노드의 내부 속성이나 특성의 유사성에 중점을 둡니다. |
| 예시 | 조직 내에서 동일한 상사에게 보고하는 직원들. 이들은 동일한 상사(이웃 노드)와 연결되어 있어 구조적 동등성을 가집니다. | 소셜 네트워크에서 같은 취미를 가진 사람들이 서로 친구가 되는 경우. 이들은 유사한 특성을 공유하여 동질성을 나타냅니다. |
| 탐색 방법과의 관계 | - DFS (Depth-First Search): 그래프의 깊은 부분까지 탐색하여 전역적인 구조를 파악하므로, 구조적 동등성을 발견하는 데 유리합니다. - BFS (Breadth-First Search): 인접한 노드들을 우선 탐색하므로, 지역적인 연결 패턴을 파악하는 데 유리하지만, 구조적 동등성을 발견하는 데는 제한적일 수 있습니다. |
- BFS (Breadth-First Search): 인접한 노드들을 우선 탐색하므로, 근접한 노드들의 속성 유사성을 파악하는 데 유리하여 동질성을 발견하는 데 효과적입니다. - DFS (Depth-First Search): 전역적인 구조를 탐색하므로, 동질성을 발견하는 데는 제한적 |
4) DFS와 BFS개념이 필요한 이유
Node2Vec는 랜덤워크에서 DFS와 BFS를 결합하여 구래프의 구조적 동등성과 동질성을 모두 학습할 수 있습니다.
DFS와 BFS는 그래프를 탐색하는 두가지 상반된 방식으로 p(반환 확률 Return Probability)와 q(탐색확률, In out probability)로 DFS와 BFS를 제어 합니다.
DFS로 전역 구조를 학습하고, BFS로 유사성을 학습합니다.
p와 q를 적절히 조정하면, 특정 그래프 특성에 최적화된 임베딩을 생성할 수 있습니다.
Node2Vec에서 p = 1, q = 1로 설정하면 DeepWalk와 동일하게 동작합니다.
Node2Vec의 주요 파라미터
- p: 반환 확률 (Return Probability)
- 이전 노드로 돌아가는 확률을 조정.
- 높은 p: 이전 노드로 돌아가는 것을 더 어렵게 만들어 깊이 우선 탐색(DFS)을 유도.
- q: 탐색 확률 (In-out Probability)
- 현재 노드 주변의 이웃 탐색을 조정.
- q<1: 가까운 이웃을 더 자주 탐색 → 너비 우선 탐색(BFS).
- q>1: 먼 이웃을 더 자주 탐색 → 깊이 우선 탐색(DFS).
- 워크 길이 및 개수:
- 랜덤 워크 길이: 각 랜덤 워크의 길이를 설정.
- 랜덤 워크 수: 각 노드에서 생성할 랜덤 워크의 개수를 설정.
Node2Vec의 동작 과정
- 제어된 랜덤 워크 생성:
- 그래프의 각 노드에서 p와 q로 조정된 랜덤 워크를 생성.
- 랜덤 워크 시퀀스는 Word2Vec에서 문장에 해당.
- Word2Vec 학습:
- 생성된 랜덤 워크 시퀀스를 Word2Vec에 입력하여 노드 임베딩 벡터를 학습.
- 임베딩 생성:
- 학습된 Word2Vec 모델에서 노드의 고차원 벡터를 추출.
- 이 벡터는 그래프 분석(노드 분류, 클러스터링 등)에 사용.
Node2Vec vs DeepWalk
| 특징 | DeepWalk | Node2Vec |
| 랜덤 워크 방식 | 단순 랜덤 워크 | 편향된 랜덤 워크 (p,로 조정 가능) |
| 탐색 전략 | DFS/BFS 균형 없음 | DFS와 BFS를 유연하게 조합 가능 |
| 유연성 | 고정된 탐색 | 다양한 그래프 구조 학습 가능 |
| 응용 가능성 | 동질성 기반 네트워크 | 동질성 및 구조적 유사성 모두 학습 가능 |
Node2Vec의 강점- 유연성: DFS/BFS를 조합해 그래프의 다양한 구조를 학습 가능.
- 효율성: 랜덤 워크와 Word2Vec의 조합으로 대규모 그래프에서도 효율적으로 동작.
- 적용 범위: 동질성 기반 네트워크와 구조적 패턴이 중요한 네트워크 모두에서 활용 가능.
Node2Vec RandomWalk 구현
Node2Vec에서 DeepWalk와의 주요 차이점은 랜덤 워크(random_walk)에서 DFS와 BFS의 편향을 조절할 수 있는 p와 q 파라미터를 도입했다는 점입니다.
random.choice로 이웃을 무작위 추출 시 아래 코드와 같이 p와 q로 이전 노드로 돌아갈지(BFS), 새로은 노드로 이동할 지(DFS)의 확률로 이웃을 추출하는 방법을 제어합니다.
이를 통해 특정 탐색 경향(전역 구조를 강조하거나 지역적 유사성을 강조)을 조절할 수 있습니다.
확률 합계를 정규화한 후, random.choices를 사용해 이웃을 선택합니다.
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import random
random.seed(42)
np.random.seed(42)
# 10개의 노드와 엣지 존재 확률 0.3으로 무작위 그래프를 생성
g = nx.erdos_renyi_graph(n=10, p=0.3, seed=42, directed=False)
# 랜덤 워크 함수 정의
def random_walk(graph, start_node, length, p, q):
"""
Perform a biased random walk on a graph.
Parameters:
graph (nx.Graph): The input graph.
start_node (int): The starting node for the random walk.
length (int): The length of the random walk.
p (float): Return probability.
q (float): In-out probability.
Returns:
list: The sequence of nodes visited during the random walk.
"""
walk = [start_node]
for _ in range(length - 1):
current = walk[-1]
neighbors = list(graph.neighbors(current))
if not neighbors:
break
if len(walk) > 1:
prev = walk[-2]
else:
prev = None
probs = []
for neighbor in neighbors:
if neighbor == prev:
probs.append(1 / p) # 이전 노드로 돌아가는 확률
elif graph.has_edge(neighbor, prev): # 이웃이 이전노드 인 경우
probs.append(1)
else:
probs.append(1 / q) # 새로운 노드로 이동하는 확률
total = sum(probs)
probs = [prob / total for prob in probs]# 확률을 정규화
# Random Choice함수에 확률
next_node = random.choices(neighbors, weights=probs, k=1)[0]
walk.append(next_node)
return walk
# 랜덤 워크 실행
start_node = 0
length = 10
# 그래프 시각화
plt.figure(figsize=(6, 6))
nx.draw_networkx(g, node_size=600, font_color='white', cmap='coolwarm')
plt.title("Random Graph")
plt.show()
# 기본 랜덤 워크 (DeepWalk 방식).
walk = random_walk(g, start_node=start_node, length=length, p=1, q=1)
print("Random Walk p = 1, q=1 :", walk)
# DFS에 편향된 랜덤 워크
walk = random_walk(g, start_node=start_node, length=length, p=1, q=10)
print("Random Walk p = 1, q=10:", walk)
# BFS에 편향된 랜덤 워크.
walk = random_walk(g, start_node=start_node, length=length, p=10, q=1)
print("Random Walk p = 10, q=1 :", walk)
Node2Vec 라이브러리
Node2Vec 알고리즘을 간단하게 구현하고, 그래프 데이터에서 노드 임베딩을 생성하는 데 사용됩니다.
이 라이브러리는 그래프 탐색(랜덤 워크 생성)과 Word2Vec 학습 과정을 자동화하여, 사용자가 복잡한 로직 없이 그래프 임베딩을 생성할 수 있도록 설계되었습니다.
Node2Vec 하이퍼 파라미터
| 파라미터 | 기본값 | 설명 |
| dimensions | 128 | 임베딩 벡터의 차원. 임베딩 벡터 차원을 증가시켜 더 많은 정보를 표현 가능 (단, 과적합 주의). |
| walk_length | 80 | 랜덤 워크의 최대 길이. 더 긴 랜덤 워크로 전역적 정보를 더 많이 학습 가능 |
| num_walks | 10 | 각 노드에서 생성할 랜덤 워크 수. 각 노드에서 더 많은 랜덤 워크를 생성, 학습 데이터 증가 |
| p | 1 | 반환 확률. DFS/BFS 균형 조정. p > 1 : 이전 노드로 돌아가는 확률이 낮아져 더 깊은 탐색 (DFS) p < 1 : 이전 노드로 쉽게 돌아가므로 지역적 탐색 (BFS). |
| q | 1 | 탐색 확률. 지역적/전역적 탐색 조정. q > 1 : 더 멀리 떨어진 노드를 탐색 (DFS). q < 1 : 가까운 이웃을 집중적으로 탐색 (BFS). |
| weight_key | None | 엣지의 가중치를 나타내는 그래프 속성. 지정하지 않으면 동일 가중치로 처리. |
| workers | 1 | 병렬 처리에 사용할 CPU 코어 수. |
| use_rejection_sampling | True | 효율적인 랜덤 워크 생성을 위한 샘플링 옵션. |
fit() 메서드
| 파라미터 | 설명 |
| window | 중심 노드와 학습할 주변 노드의 범위. Word2Vec에서 주변 노드의 범위가 넓어져 전역적 정보 학습 가능. |
| min_count | 최소 등장 빈도. |
| batch_words | 한 번에 처리할 단어 수. |
사용예제
import networkx as nx
from node2vec import Node2Vec
# 1. 그래프 생성
G = nx.karate_club_graph()
# 2. Node2Vec 모델 생성
node2vec = Node2Vec(
graph=G,
dimensions=64,
walk_length=30,
num_walks=200,
p=1, # DFS/BFS 균형 조정
q=0.5, # 지역 탐색 강조
workers=4 # 병렬 처리
)
# 3. Word2Vec 학습
model = node2vec.fit(window=10, min_count=1, batch_words=4)
# 4. 노드 임베딩 추출
node_embeddings = {node: model.wv[str(node)] for node in G.nodes()}
print(node_embeddings[1]) # 노드 '1'의 임베딩 벡터
Node2Vect로 이전 작성했던 코드를 수정하면 훨씬 간편해집니다.
import networkx as nx
from node2vec import Node2Vec
import pandas as pd
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# 1. 그래프 생성: Karate Club 그래프
G = nx.karate_club_graph()
# 2. Node2Vec 객체 생성
node2vec = Node2Vec(
G,
dimensions=64, # 임베딩 벡터 차원
walk_length=10, # 랜덤 워크 길이
num_walks=80, # 각 노드에서 생성할 워크 수
workers=4, # 병렬 처리에 사용할 CPU 코어 수
p=1, # Return probability
q=10 # In-Out probability
)
# 3. Word2Vec 학습 (Node2Vec 내부적으로 Word2Vec 사용)
model = node2vec.fit(window=5, min_count=1, sg=1)
# 4. 임베딩 벡터 추출
node_embeddings = {node: model.wv[str(node)] for node in G.nodes()} # 문자열 변환
embedding_df = pd.DataFrame(node_embeddings).T
embedding_df.columns = [f"dim_{i}" for i in range(embedding_df.shape[1])]
# 5. 종속변수 생성: 'club' 속성 기반
labels = {node: 1 if G.nodes[node]['club'] == 'Officer' else 0 for node in G.nodes()}
labels_df = pd.DataFrame.from_dict(labels, orient='index', columns=['label'])
# 6. 데이터 준비
X = embedding_df.values # 노드 임베딩
y = labels_df['label'].values # 종속변수
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# 7. Logistic Regression 모델 학습 및 평가
clf = LogisticRegression(random_state=42)
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
# 8. 정확도 평가
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.4f}")
0.9'GNN' 카테고리의 다른 글
| GNN(Graph Neural Network) - 6. GAT(Graph Attention Network) (0) | 2025.01.09 |
|---|---|
| GNN(Graph Neural Network) - 5. GCN(Graph Convolution Network) (3) | 2025.01.06 |
| GNN(Graph Neural Network) - 3. 딥워크(DeepWalk) (1) | 2025.01.05 |
| GNN(Graph Neural Network) - 2. 그래프와 행렬 (0) | 2025.01.04 |
| GNN(Graph Neural Network) - 1. 그래프 개념 (1) | 2025.01.04 |