그래프 데이터의 방향성은 어디에 있나: Edge vs Node vs 정규화

그래프 데이터 분석에서는 “방향성(directed)”이 하나로 고정되어 있지 않다. 방향성은 (1) 엣지(인접)에 있을 수도 있고, (2) 노드(뷰/피처)에 있을 수도 있으며, (3) 전파(정규화) 연산에서 “비대칭 전파”로 나타날 수도 있다. 해당 포스팅에서는 이 세 가지를 분리해 정의하고, 작은 샘플 데이터로 직접 비교한다.

	대칭(Symmetric)	비대칭(Asymmetric)
무엇을 말하나	관계(상호연결) 관점으로 “균형 있게” 전파한다	전이(transition) 관점으로 “방향(확률 분배)”을 갖고 전파한다
어디에 있나	전파(정규화) 규칙에 존재한다 (그래프가 무방향일 때 해석이 자연스럽다)	전파(정규화) 규칙에 존재한다 (그래프가 무방향이어도 전파는 비대칭일 수 있다)
수식	S = D^-1/2 A D^-1/2 (symmetric normalization)	P = D_out^-1 A (random-walk / row-normalization)
해석	양쪽 노드의 degree를 동시에 보정하여 허브 편향을 완화한다. 관계(연결성) 기반으로 안정적으로 확산하는 표준 형태이다.	각 노드가 이웃으로 “확률적으로 분배”되는 전이행렬로 해석된다. A가 대칭이어도 행 정규화로 인해 전파 연산은 비대칭이 될 수 있다.
간단 예시	친구관계처럼 “서로 연결”만 중요할 때 (커뮤니티/관계 기반)	전달/이동처럼 “퍼져나가는 전이”가 중요할 때 (확산/전이 관점)

1. 용어 정리(Glossary)

Node(노드): 사용자, 지갑, 주소 등 개체이다.
Edge(엣지): 노드 간 관계이다. 거래 그래프라면 “거래 발생”이다.
Adjacency(인접행렬, A): 엣지를 행렬로 표현한 것이다. 일반적으로 A[i, j]는 i에서 j로의 연결(또는 가중치)이다.
Directed adjacency(방향 인접): A[i, j] ≠ A[j, i]가 가능하다. “누가 누구에게 보냈는가(i→j)” 신호가 포함된다.
Undirected adjacency(무방향 인접): A[i, j] = A[j, i]인 대칭 행렬이다. “관계의 존재/강도”만 표현한다.
View(뷰): 노드 속성 행렬 1개이다. 예: X^(1), X^(2) 등이다.
View data(뷰 데이터): 여러 뷰의 집합 {X^(v)}_{v=1..V}이다.
Feature(피처): 각 뷰 행렬의 컬럼(개별 속성)이다. 예: in_degree, out_volume 등이다.
Normalization(정규화): 전파/확산 연산을 만들기 위해 A를 D로 스케일링하는 과정이다.
Propagation/Diffusion(확산/전파): 피처를 그래프를 따라 섞는 연산이다.

2. “방향성”의 3가지 위치

2.1 Edge-level directionality(엣지/인접 기준 방향성)

의미: “누가 누구에게 보냈는가(i→j)”가 인접 구조에 포함된다.
조건: 방향 인접행렬 A_dir이 필요하다.

2.2 Node-level directionality(노드/뷰 기준 방향성)

의미: 거래 상대 방향(i→j) 자체가 아니라, 개인 기준 유입/유출(in/out) 비대칭 신호이다.
예: in_degree, out_degree, in_volume, out_volume, net_flow=out-in 등이다.
조건: 인접이 무방향이어도 가능하다.

2.3 Propagation-level asymmetry(전파/정규화 기준 비대칭성)

의미: 인접이 무방향이어도, 전파 연산을 random-walk(행 정규화)로 만들면 전파가 비대칭적으로 동작할 수 있다.
핵심: “그래프가 directed가 되었다”가 아니라 “전파 연산이 비대칭이 되었다”이다.

3. 샘플 데이터로 한 번에 이해하기

스테이블코인 거래 패턴을 단순화한 4개 노드 예시를 사용한다. 노드는 A, B, C, D이며 방향 거래(가중치=거래횟수 또는 거래량)를 아래처럼 가정한다.

A → B : 3
A → C : 1
B → C : 2
C → A : 1
D → C : 4

3.1 Directed adjacency(거래 관계 방향 포함)

노드 순서가 (A,B,C,D)일 때 방향 인접행렬 A_dir은 다음과 같다.

A_dir =
[ [0, 3, 1, 0],
  [0, 0, 2, 0],
  [1, 0, 0, 0],
  [0, 0, 4, 0] ]

이때 A_dir[i, j]는 “i가 j에게 보낸 강도”이다. 즉 Edge-level directionality가 포함된다.

3.2 Undirected adjacency(관계만 유지)

무방향 인접을 만들기 위해 대표적으로 합 대칭화를 사용한다.

합 대칭화: A_sym = A_dir + A_dir^T
평균 대칭화는 스케일만 달라질 뿐 본질은 동일하다.

A_sym =
[ [0, 3, 2, 0],
  [3, 0, 2, 0],
  [2, 2, 0, 4],
  [0, 0, 4, 0] ]

여기서는 “A—C가 강한가(2)?”처럼 관계 강도만 남고, “A→C vs C→A” 방향 차이는 사라진다.

4. 정규화(전파) 방식: 대칭 vs 랜덤워크(비대칭)

구분	정규화(전파) 방식	수식(대표형)	대칭성	직관적 해석	언제 유용한가
대칭 계열	Symmetric normalization	D^-1/2 A D^-1/2	대칭(무방향 A에서)	양쪽 degree를 균형 보정하며 관계(상호연결성) 관점으로 확산한다	무방향 그래프, 커뮤니티/관계 기반 분석, 허브 편향 완화가 필요할 때
대칭 계열	Self-loop 포함(안정화)	D~^-1/2 (A+I) D~^-1/2	대칭(무방향 A에서)	자기 정보 보존을 강화하며 과도한 혼합(oversmoothing)을 완화한다	깊은 전파/다중 레이어, 노이즈가 많거나 자기 신호 보존이 중요할 때
비대칭 계열	Random-walk(행 정규화)	D_out^-1 A	비대칭 가능	각 노드가 이웃으로 “확률적으로 분배”하며 전이(transition) 관점으로 확산한다	전이/확산 해석이 필요하거나, 노드별 전파 비대칭 효과를 보고 싶을 때
	Reverse random-walk(열 정규화)	A D_in^-1	비대칭 가능	유입(in) 기준으로 스케일을 맞춰 “수신 중심”으로 확산을 해석한다	받는 쪽(유입) 관점의 역할/허브성을 강조하고 싶을 때
	Bi-normalization(이중 정규화)	(행/열을 번갈아 정규화)	비대칭(또는 이중확률화)	스케일 편향을 줄이기 위해 행/열을 모두 정규화(균형화)한다	방향성은 유지하되, 특정 노드로 편향되는 전이를 완화하고 싶을 때
	PPR/Teleport 포함(GDC 스타일)	P_α = αI + (1-α)P	비대칭 가능	전이에 점프(teleport)를 섞어 수렴/안정성을 확보한다	희소/불연결 그래프, 장거리 영향(멀티홉) 반영, 안정적 확산이 필요할 때

그래프 전파(확산)에서 “정규화(normalization)”는 인접행렬 A를 그대로 쓰지 않고, 노드의 연결 규모(degree)에 따라 스케일을 보정하여 전파 행렬을 만드는 과정이다. 정규화 방식에 따라 정보가 이웃으로 퍼지는 양상이 달라지며, 특히 대칭(symmetric)인지 비대칭(asymmetric)인지가 핵심 차이이다.

4.1 Degree 행렬 D의 정의

무방향(대칭) 인접 A_sym에서는 각 노드의 degree를 deg(i)=sum_j A_sym[i, j]로 둔다. 위 샘플의 degree는 다음과 같다.

deg(A)=3+2=5
deg(B)=3+2=5
deg(C)=2+2+4=8
deg(D)=4=4

따라서 D = diag(5, 5, 8, 4)이다.

4.2 Undirected normalization(대칭 정규화) 계열

무방향 그래프에서 가장 표준적인 정규화는 대칭 정규화(symmetric normalization)이다. 대표식은 다음과 같다.

S = D^{-1/2} A D^{-1/2}

특징은 다음과 같다.

양쪽 노드의 degree를 동시에 보정하여, 특정 노드(허브)의 영향이 과도해지는 것을 완화한다.
(A가 대칭이면) 전파 행렬도 “대칭적 성질”을 가져 상호연결성(관계) 관점의 확산에 적합하다.
GCN/Laplacian 기반 모델에서 기본 형태로 널리 사용된다.

Undirected 정규화의 변형(종류)은 보통 아래처럼 분류한다.

Unnormalized: S = A (스케일 보정 없음, 실무에서는 편향이 커 잘 쓰지 않는다)
Random-walk(무방향) 정규화: S = D^{-1}A (무방향에서도 가능하나, 대칭성은 깨질 수 있다)
Symmetric 정규화: S = D^{-1/2}AD^{-1/2} (가장 표준적이며 안정적이다)
Self-loop 포함: A~ = A + I, D~ 기반으로 D~^{-1/2} A~ D~^{-1/2} (자기 정보 보존 목적)

4.3 Directed normalization(비대칭 전파) 계열

방향 그래프(directed adjacency)에서는 degree 정의가 in/out으로 갈라지며, 정규화 선택에 따라 “전이(transition)” 해석이 달라진다. 이 글에서는 비대칭 전파의 대표로 랜덤워크(random-walk) 정규화를 사용한다.

대표식(행 정규화)은 다음과 같다.

P = D_out^{-1} A (row-normalized random walk)

특징은 다음과 같다.

각 행의 합이 1이 되도록 스케일링되어 전이확률(transition matrix)로 해석 가능하다.
전파가 “한 노드에서 이웃으로 분배”되는 형태라, 전파 연산이 비대칭(asymmetric)으로 동작할 수 있다.
A가 대칭이어도(무방향 인접을 쓰더라도) 행 정규화로 인해 P는 비대칭이 될 수 있다. 이는 “엣지 방향이 생긴 것”이 아니라 “전파 연산이 비대칭이 된 것”이다.

Directed 정규화의 변형(종류)은 다음과 같이 정리할 수 있다.

Row-normalized random walk: P = D_out^{-1}A (송신/전파 관점, 가장 흔한 기본형)
Column-normalized: P = A D_in^{-1} (수신/유입 관점, 해석 축이 반대이다)
Bi-normalization(이중 정규화): 행/열을 번갈아 정규화하여 스케일 편향을 줄이는 방식(Sinkhorn류)
Teleport 포함(PPR/GDC 계열): random-walk에 점프를 섞어 수렴성과 안정성을 높이는 방식(예: PageRank 스타일)

4.4 본 글에서 “대칭 vs 비대칭(랜덤워크)”로 비교하는 이유

본 글의 목적은 “방향성”을 Edge(관계 방향), Node(유입/유출 역할), Propagation(전파 비대칭)으로 분리해 이해시키는 데 있다. 이때 정규화 비교는 다음 이유로 대칭 정규화와 랜덤워크(행 정규화)를 대표로 선택한다.

대칭 정규화(D^{-1/2}AD^{-1/2})는 무방향 그래프에서 가장 표준적이며, “관계(상호연결성) 기반 확산”이라는 직관이 명확하다.
랜덤워크 정규화(D_out^{-1}A)는 전이를 “확률적 분배”로 해석할 수 있어, 전파의 비대칭성을 가장 직관적으로 보여준다.
따라서 본 비교는 “그래프가 directed가 되었는가”가 아니라, 전파 연산의 형태(대칭 vs 비대칭)가 표현학습/군집결과에 어떤 차이를 만드는가를 설명하는 데 초점을 둔다.

5. 뷰(View)에서의 방향성: 유입/유출 역할 신호

인접이 무방향이어도, 뷰(노드 피처)에는 개인 기준 방향성 역할 신호가 들어갈 수 있다. 아래는 A_dir을 기준으로 단순히 out/in degree를 만들고 역할 피처를 구성한 예시이다.

5.1 Node-level directional feature 예시

out_degree(A)=2 (B,C), in_degree(A)=1 (C)
out_degree(B)=1 (C), in_degree(B)=1 (A)
out_degree(C)=1 (A), in_degree(C)=3 (A,B,D)
out_degree(D)=1 (C), in_degree(D)=0

역할 신호를 다음처럼 정의할 수 있다.

role = out_degree – in_degree

role(A)=  1
role(B)=  0
role(C)= -2
role(D)=  1

이는 거래 상대 방향(i→j)을 직접 모델링하지 않더라도 “개인 기준 유입/유출 비대칭”을 표현한다.

6. 1-step 전파 비교(직관)

초기 피처 벡터를 h = role이라 두고 1번 전파를 수행한다.

대칭 정규화 전파: h_sym = S h
랜덤워크 전파: h_rw = P h

대칭 정규화는 관계 기반으로 균형 있게 섞이는 경향이 있고, 랜덤워크 전파는 노드별 degree에 따라 “퍼뜨리는 방식”이 달라질 수 있다. 따라서 같은 무방향 A라도 전파 후 표현이 달라져 군집 품질 지표(SIL/CHI 등)가 달라질 수 있다.

7. 요약표 및 실험 설계 체크리스트 (혼동 방지)

구분	방향성 위치	의미	필요한 데이터
Edge-level directionality	인접(엣지)	누가 누구에게 보냈는가(i→j)	Directed adjacency A_dir
Node-level directionality	뷰(노드 피처)	개인 기준 유입/유출(역할) 비대칭	in/out 계열 feature
Propagation-level asymmetry	정규화/전파	전파 연산이 비대칭으로 동작	D^{-1}A 같은 row-normalization

실험 설계 체크리스트
- [ ] Adjacency가 directed인가, undirected인가: directed A를 쓰면 엣지 방향성이 반영된다. undirected A를 쓰면 관계 강도만 반영된다.
- [ ] Normalization이 symmetric인가, random-walk인가: D^{-1/2}AD^{-1/2} vs D^{-1}A를 명시한다.
- [ ] 뷰 피처에 in/out이 있는가: 있다면 node-level 역할 신호를 학습할 수 있다.

8. 결론

인접(Edge) 방향성: i→j 관계 자체의 방향이다.
뷰(Node) 방향성: 개인 기준 유입/유출 역할 신호이다.
정규화(전파) 비대칭: 전파 연산이 비대칭적으로 동작하는 성질이다.

“무방향 그래프에서 directed 모드”라는 표현은, 엄밀히는 “그래프를 directed로 바꾸었다”가 아니라 “전파를 random-walk 정규화로 바꾸어 비대칭 전파를 비교하였다”와 같이 정리해볼 수 있다.

코드 예시

아래는 샘플 데이터의 A_dir, A_sym, D, S, P를 만들고 1-step 전파를 계산하는 최소 예시이다.

import numpy as np

# nodes: A,B,C,D
A_dir = np.array([
    [0,3,1,0],
    [0,0,2,0],
    [1,0,0,0],
    [0,0,4,0],
], dtype=float)

A_sym = A_dir + A_dir.T

deg = A_sym.sum(axis=1)
D = np.diag(deg)

# symmetric normalization: S = D^{-1/2} A D^{-1/2}
D_inv_sqrt = np.diag(1.0 / np.sqrt(np.maximum(deg, 1e-12)))
S = D_inv_sqrt @ A_sym @ D_inv_sqrt

# random-walk normalization: P = D^{-1} A
D_inv = np.diag(1.0 / np.maximum(deg, 1e-12))
P = D_inv @ A_sym

# node-level directional feature example: role = out_degree - in_degree (from A_dir)
out_deg = (A_dir > 0).sum(axis=1)
in_deg  = (A_dir > 0).sum(axis=0)
role = out_deg - in_deg

h = role.astype(float)
h_sym = S @ h
h_rw  = P @ h

print("A_dir=\\n", A_dir)
print("A_sym=\\n", A_sym)
print("deg=", deg)
print("role=", role)
print("h_sym=", h_sym)
print("h_rw =", h_rw)