라플라시안으로 정의되는 GFT: 인접행렬 A부터 주파수까지

라플라시안이란? “이웃과 얼마나 다르게 튀는지”를 수치화하는 연산자

그래프에서는 시간축처럼 “앞/뒤”가 고정되어 있지 않다. 대신 엣지(연결)가 “누가 이웃인지”를 결정한다. 그래서 GFT는 아래와 같이 정의한다.

  • 이웃과 비슷하게 변하는 패턴 = 저주파(부드러움)
  • 이웃과 크게 달라지는 패턴 = 고주파(거침/경계)

이 “부드러움/거침”을 수식으로 잡아주는 게 라플라시안 (L)이다.

시작점: 두 개의 데이터프레임

(1) 노드 신호: signal_df (노드에 붙은 값)
nodex
010
112
213
39
48
  • 여기서 \(x_i\) 는 “노드 i의 값(신호)”이다.
(2) 그래프 구조: edge_df (연결 + 가중치)
srcdstw
010.9
020.2
120.7
230.8
340.6
  • \(w_{ij}\) 는 “i와 j가 얼마나 강하게 연결되어 있는가(가중치)”다.
  • (보통 GFT 기본 설명은 무방향 그래프를 가정 → 이 경우 \(w_{ij}=w_{ji}\))
    • 무방향 그래프: 방향이 없는 그래프(‘주는/받는’이 아니라, 두 노드 사이의 관계 강도만 표현)

인접행렬 A: “연결 지도”

edge_df를 행렬로 바꾸면 인접행렬 (A) 이다.

정의:

$$
A_{ij} =
\begin{cases}
w_{ij} & \text{(i와 j가 연결되어 있으면)}\\
0 & \text{(연결 없으면)}
\end{cases}
$$

예시(노드 0~4): 아래는 “함수처럼” 가중치를 정의한 뒤, 무방향이면 반대 방향도 동일하게 적용한다.

  • \(w(0,1)=0.9\), \(w(0,2)=0.2\), \(w(1,2)=0.7\), \(w(2,3)=0.8\), \(w(3,4)=0.6\)
  • 무방향이면 \(w(i,j)=w(j,i)\) 이므로 \(w(1,0)=0.9\), \(w(2,0)=0.2\), \(w(2,1)=0.7\), \(w(3,2)=0.8\), \(w(4,3)=0.6\) 도 동일하게 성립한다.
  • 그리고 인접행렬 값은 “엣지가 있으면” \(A_{ij}=w(i,j)\), 없으면 \(A_{ij}=0\) 으로 채운다.

차수행렬 D: “각 노드가 가진 연결 강도의 합”

노드 i의 가중 차수(degree):

$$
d_i = \sum_j A_{ij}
$$

그리고 이를 대각행렬로 만든 게 차수행렬 (D):

$$
D_{ii}=d_i,\quad D_{ij}=0\ (i\neq j)
$$

예시 (무방향 가정):

  • \(d_0 = 0.9+0.2 = 1.1\)
  • \(d_1 = 0.9+0.7 = 1.6\)
  • \(d_2 = 0.2+0.7+0.8 = 1.7\)
  • \(d_3 = 0.8+0.6 = 1.4\)
  • \(d_4 = 0.6 = 0.6\)

라플라시안 L: 그래프에서의 “변화량 측정기”

5-1) 비정규화 라플라시안 (가장 기본)

$$
L = D – A
$$

이 한 줄이 GFT의 핵심이다.

5-2) 라플라시안이 “거칠기”를 만든다는 직관

$$
x^\top L x = \frac{1}{2}\sum_{i}\sum_{j} A_{ij}(x_i-x_j)^2
$$

의미:

  • 연결된 두 노드 \((i,j)\)가 값이 비슷하면 \((x_i-x_j)^2\)가 작아서 전체가 작아짐 → 부드러움(저주파)
  • 값이 크게 다르면 전체가 커짐 → 거침(고주파)

즉 \(x^\top L x\)는 “이 그래프에서 신호 x가 얼마나 이웃 대비 튀는지”를 재는 점수다.

한 번 더 직관: \((Lx)_i\)는 “이웃과의 차이의 가중합”

$$
(Lx)_i = d_i x_i – \sum_j A_{ij}x_j
= \sum_j A_{ij}(x_i – x_j)
$$

  • 노드 i에서 볼 때, 연결된 이웃들과의 차이를 가중치로 합친 값이다.
  • 값이 이웃과 비슷하면 \((Lx)_i\)가 작고,
  • 경계처럼 혼자 튀면 크게 나온다.

라플라시안으로 “그래프 주파수 축” 만들기: 고유값/고유벡터

GFT는 DFT처럼 사인/코사인 기저를 쓰지 않는다. 대신 라플라시안의 고유분해를 쓴다.

$$
L = U\Lambda U^\top
$$

  • \(U\): 고유벡터들을 모아둔 행렬(= 그래프의 “기준 파형들”)
  • \(\Lambda\): 고유값 대각행렬(= 그래프 “주파수 크기”)

해석:

  • \(\lambda\)가 작을수록 이웃끼리 비슷한 변화(부드러운 모드) → 저 그래프-주파수
  • \(\lambda\)가 클수록 이웃 대비 급격한 변화(거친 모드) → 고 그래프-주파수

GFT 정의: “라플라시안 고유벡터 축으로 좌표변환”

그래프 신호 \(x\)를 고유벡터 기저로 투영하면 GFT다.

$$
\hat{x} = U^\top x
$$

  • \(\hat{x}\)는 “그래프 주파수 성분”
  • \(\hat{x}_m\)은 m번째 모드(주파수)에 얼마나 실려 있는지

역변환:

$$
x = U\hat{x}
$$

정규화 라플라시안: 노드 차수 편차를 줄이고 싶을 때

노드마다 연결 수(차수)가 크게 다르면, 비정규화 \(L\)이 특정 노드에 치우칠 수 있다. 그때 정규화 버전을 쓴다.

대칭 정규화 라플라시안

$$
L_{\text{sym}} = I – D^{-1/2}AD^{-1/2}
$$

9-2) 랜덤워크 라플라시안

$$
L_{\text{rw}} = I – D^{-1}A
$$

실무에서 한 줄 가이드:

  • 그래프가 비교적 균일하면 \(L=D-A\)도 충분
  • 차수 편차가 크면 \(L_{\text{sym}}\)부터 고려

DF로 “라플라시안 만들기” 흐름 요약

입력 DF:

  • edge_df(src,dst,w) → \(A\)
  • signal_df(node,x) → \(x\)

만드는 것:

  1. \(A\) 만들기(없으면 0, 연결이면 w)
  2. \(d_i = \sum_j A_{ij}\)
  3. \(D\) 만들기(\(D_{ii}=d_i\))
  4. \(L=D-A\) (또는 \(L_{\text{sym}}\))
  5. \(L = U\Lambda U^\top\)
  6. \(\hat{x}=U^\top x\) 가 GFT

라플라시안은 “이웃과의 차이”를 수식으로 고정해 주고, 그 고유벡터가 GFT의 기저(푸리에 축)를 만든다.
그래서 GFT에서 라플라시안은 “반영”이 아니라, 정의 그 자체라고 할 수 있다.

import numpy as np
import pandas as pd

# 예시 DF
signal_df = pd.DataFrame({"node":[0,1,2,3,4], "x":[10,12,13,9,8]})
edge_df   = pd.DataFrame({
    "src":[0,0,1,2,3],
    "dst":[1,2,2,3,4],
    "w":[0.9,0.2,0.7,0.8,0.6]
})

n = signal_df["node"].max() + 1

# 1) A 만들기 (무방향)
A = np.zeros((n,n), dtype=float)
for s,d,w in edge_df.itertuples(index=False):
    A[s,d] = w
    A[d,s] = w

# 2) D, L
deg = A.sum(axis=1)
D = np.diag(deg)
L = D - A

# 3) 고유분해 (대칭행렬이므로 eigh)
lam, U = np.linalg.eigh(L)

# 4) GFT: xhat = U^T x
x = signal_df.sort_values("node")["x"].to_numpy()
xhat = U.T @ x

print("eigenvalues (lambda):", lam.round(4))
print("xhat:", xhat.round(4))
태그