요즘 그래프 임베딩(DeepWalk/node2vec)을 제대로 이해해보려고 CS224W 슬라이드를 따라가고 있다.
웃긴게 처음에는 모델 구조는 “word2vec이랑 비슷하다” 한 줄로 끝나는데, 수식이 한 번 등장하면 그때부터 뇌정지가 온다.
특히 내가 막혔던 건 이거였다.
NR(u가 뭔지 감이 안 잡힘
첫 번째 objective가 왜 갑자기 두 번째 loss로 바뀌는지 이해 안 됨
softmax 분모가 왜 문제인지, negative sampling이 뭘 “근사”하는지 모르겠음
GD/SGD가 왜 나오는지 알겠는데 "납득"이 안 됨
node2vec의 p, q가 그냥 파라미터인지(하이퍼파라미터인지) 감이 없었음
오늘은 이걸 내가 이해한 흐름대로 처음부터 끝까지 정리한다.
1. 일단 목표가 뭐냐: “노드를 벡터로” 만들고 싶다
그래프에서 노드마다 zuz_uzu라는 벡터(embedding)를 하나씩 만들고, 이 벡터가 “그래프 구조에서의 유사성”을 반영하게 하고 싶다.
직관은 간단하다:
그래프에서 자주 “같은 문맥”에 등장하는 노드들은
embedding 공간에서도 가깝게 만들자.
이 “문맥(context)”을 만들기 위해 랜덤워크(random walk)를 돌린다.
2. NR(u)이게 도대체 뭐야? v랑 무슨 관계야?
슬라이드에 이런 식이 나온다:
여기서 핵심은 N_R(u)
u: 기준 노드(center node)
R: 랜덤워크 전략(random walk strategy)
NR(u): 전략 R로 랜덤워크를 돌렸을 때, u 주변 “문맥”으로 관측된 이웃 노드들의 집합(혹은 멀티셋)
즉,
v∈NR(u)
의 의미는 엄청 단순하다:
“랜덤워크로 만든 u의 문맥 안에 v가 등장했다.”
중요: 여기서 이웃은 1-hop 이웃이 아니라, walk + window에서 나온 “공동출현(co-occurrence)” 이웃이다.
Word2Vec 비유로 말하면:
문장 속 단어가 있고
window 안에 같이 등장하는 단어들이 context인데
그래프에서는 “랜덤워크가 문장 역할”을 한다고 보면 된다.
3. 첫 번째 식 → 두 번째 loss로 왜 바뀌냐 (내가 제일 막혔던 부분)
슬라이드에서 갑자기 다음으로 넘어간다:
이게 마법처럼 바뀌는 게 아니라, 중간에 3가지 발상이 들어간다.
(1) 이웃 전체 확률을 “이웃 원소별 확률”의 곱으로 단순화
보통 다음 가정을 한다:
뜻: “u의 embedding이 주어지면, 이웃 노드들은 독립적으로 생성된다” 같은 단순 모델.
(2) 로그를 씌우면 곱이 합으로 바뀜
(3) 최대화 문제를 loss 최소화로 바꿈
최대화 → 최소화로 바꾸려고 마이너스 붙임:
이제 해석이 완전 쉬워진다.
“u가 주어졌을 때, 실제로 문맥에 등장한 v들을 높은 확률로 예측하게 만들어라.”
4. P(v∣zu)P(v\mid z_u)P(v∣zu)를 softmax로 두는 이유
이 확률은 보통 이렇게 둔다:
내적 zu⊤zvz_u^\top z_vzu⊤zv가 클수록 v가 u 문맥에 등장할 확률이 커짐
분모로 전체 노드에 대해 정규화(softmax)
여기까지는 이론적으로 완벽한데…
5. 진짜 문제: softmax 분모가 너무 비싸다
∑n∈V 이게 문제다.
노드가 100,000개면,
확률 하나 계산할 때 exp를 100,000번…
SGD 한 스텝마다 이걸 하면 그냥 끝이다.
그래서 등장하는 게 Negative Sampling.
6. Negative Sampling을 내 머리로 이해한 한 줄
softmax 다중분류를 못 하니까, 이진분류 여러 번으로 바꾼다.
원래 하고 싶었던 것(softmax)
“전체 노드 중 정답 v를 맞춰라”
현실적으로 하는 것(negative sampling)
“(u,v)가 진짜 이웃이면 1(positive)”
“(u,n)이 랜덤으로 뽑힌 가짜면 0(negative)”
이걸 k개 negative에 대해 반복
대표 목적함수는 이런 느낌:
직관:
positive pair(u,v): 내적 크게 → sigmoid가 1에 가깝게
negative pair(u,n): 내적 작게 → sigmoid가 0에 가깝게
핵심 이득: 전체 노드 대신 정답 1개 + 오답 k개만 보면 되니까 계산량이 O(|V|)에서 O(k)로 내려간다.
내가 느낀 비유:
시험을 볼 때 “전교생 10만 명 중 1등을 맞춰라”는 문제 대신 “얘가 정답 후보냐? 아니냐?”를 정답 1명 + 랜덤 오답 몇 명만 두고 판단하는 느낌.
7. GD vs SGD가 왜 나오냐 (슬라이드에서 갑자기 SGD가 등장한 이유)
loss는 모든 (u, v∈N_R(u))에 대해 합쳐져 있다. 즉 데이터가 엄청 많다.
GD: 모든 (u,v) 다 보고 한 번 업데이트 → 너무 느림
SGD: (u,v) 한 쌍(또는 미니배치)만 뽑아 업데이트 → 현실적
그래서 실전 조합은 거의 고정이다:
SGD + Negative Sampling
8. DeepWalk: “가장 단순한 랜덤워크 문장 생성기”
DeepWalk는 random walk를 그냥 돌린다.
각 노드에서 시작
이웃 중 하나를 균등하게 선택하면서 이동
길이 L짜리 walk 여러 개 만들고
그 walk를 “문장”으로 보고 skip-gram 학습
근데 이 방식은 탐색이 너무 단순해서 “나는 로컬 구조를 더 보고 싶다 / 글로벌 구조를 더 보고 싶다” 같은 조절이 어렵다.
여기서 node2vec가 나온다.
9. node2vec 핵심: BFS 느낌 vs DFS 느낌을 섞어서 학습하기
node2vec는 “편향 랜덤워크(biased random walk)”를 쓴다.
그리고 중요한 건:
다음 스텝에서 어디로 갈지는 “현재 노드”만 보지 않고 “직전 노드”도 기억한다. (2nd-order random walk)
p, q는 사용자가 정하는 하이퍼파라미터 맞아?
맞다. p와 q는 하이퍼파라미터다. 사용자가 정하고, 데이터/목표에 맞게 튜닝한다.
p (return parameter): 바로 직전 노드로 돌아갈 확률 성향
p가 작으면 “되돌아가기”가 쉬워짐(가중치가 커지는 방향으로 해석)
p가 크면 되돌아가기가 어려움(앞으로 진행)
q (in-out parameter): 안쪽(BFS) vs 바깥쪽(DFS) 이동 성향
q가 크면 멀리 나가는 걸 억제 → BFS-like(로컬)
q가 작으면 멀리 나가는 걸 장려 → DFS-like(글로벌)
슬라이드 그림 해석을 내 방식으로 요약하면:
“지금 w에 왔을 때, 다음 후보 노드 t들이 직전 노드 s1과의 거리(0,1,2)에 따라 가중치가 달라지고 그 가중치를 p,q가 조절한다.”
10. node2vec 알고리즘이 왜 3단계인지
슬라이드에 “node2vec algorithm”이 3줄로 요약된다:
Compute random walk probabilities
Simulate r random walks of length l from each node
Optimize objective using SGD
내 해석은 이렇다:
1단계는 “탐색 규칙(p,q)”를 확정
2단계는 “문장(워크 코퍼스)”를 생성
3단계는 “word2vec처럼 학습(SGD + negative sampling)”
장점:
계산이 선형 시간에 가깝고
노드별로 walk 생성/학습을 병렬화하기 쉽다
11. (확장) 그래프 전체 임베딩: 노드가 아니라 그래프를 벡터로
마지막 강의 파트는 “노드 임베딩 말고 그래프 자체를 임베딩하자”였다.
정리하면 3개.
Approach 1) 노드 임베딩 합/평균
그래프 임베딩 = 그래프 안 노드 임베딩의 sum/avg 심플한데 의외로 잘 됨(분자 그래프 분류 같은 데서 성공 사례 많음)
Approach 2) 슈퍼노드(virtual node)
그래프(또는 subgraph)를 대표하는 빨간 노드를 만들고 모든 노드와 연결한 다음 그 노드 embedding을 그래프 embedding으로 사용
Approach 3) Anonymous Walk Embeddings
여기가 재미있었음.
랜덤워크를 “노드 ID”로 표현하지 않고
“처음 방문한 순서(인덱스)”로 표현함 → 노드 이름이 달라도 구조가 비슷하면 같은 표현이 나옴
그리고 그래프를
anonymous walk들의 빈도 분포 벡터로 나타내거나,
더 나아가 anonymous walk 자체도 임베딩하고, 그래프 임베딩 ZGZ_GZG도 같이 학습할 수 있다.
12. 오늘 공부를 한 문장으로 요약하면
그래프 임베딩은 “랜덤워크로 만든 문장”에서 공동출현 노드들을 맞추는 문제로 바꾼 뒤, softmax가 비싸서 negative sampling + SGD로 빠르게 학습한다. node2vec는 여기서 랜덤워크를 p,q로 편향시켜 로컬(BFS)과 글로벌(DFS) 정보를 조절한다.
(내가 다음에 다시 볼 체크리스트)
NR(u)N_R(u)NR(u) = 랜덤워크 문맥에서 얻은 u의 이웃(= co-occurrence)
