[그래프 ML] 행렬 분해(Matrix Factorization) - 비음수 행렬 분해(NMF), 특이값 분해(SVD), 주성분 분석(PCA)

목차

• 1. 행렬 분해(Matrix Factorization)란
  • 1.1. 개념
  • 1.2. 활용
• 2. 행렬 분해의 수학적 배경
  • 2.1. 원천 행렬(Source Matrix)와 기여도 행렬(Abundance Matrix)
• 3. 대표적인 행렬 분해 기법
  • 3.1. 비음수 행렬 분해(NMF; Non-negative Matrix Factorization)
  • 3.2. 특이값 분해(SVD; Singular Value Decomposition)
  • 3.3. 주성분 분석(PCA; Principal Component Analysis)
• 4. 행렬 분해의 활용 사례
  • 4.1. 링크 예측(Link Prediction)
  • 4.2. 노드 임베딩(Node Embedding)
  • 4.3. 그래프 신호 처리(Graph Signal Processing)
  • 4.4. 그래프 클러스터링(Graph Clustering)

 

※ 출처 : 그래프 머신러닝 (클라우디오 스타밀레 외, 김기성·장기식 옮김)

 

1. 행렬 분해(Matrix Factorization)란

1.1. 개념

$$X \approx S \times A$$

    대규모 행렬 데이터를 두 개 이상의 작은 행렬들의 곱으로 나타내는 것을 말합니다. 일반적으로 원본 행렬 $X$를 원천 행렬(source matrix) $S$와 기여도 행렬(abundance matrix) $A$의 곱으로 근사합니다. 여기서 $S$는 데이터를 구성하는 기본 요소들을, $A$는 각 요소가 원본 데이터에 기여하는 정도를 의미합니다.

 

1.2. 활용

    고차원 데이터의 잠재적인 패턴과 구조를 발견하고, 저차원 표현으로 압축하며, 노이즈를 제거하는 등의 목적으로 사용됩니다.

* 대표적인 활용 분야
  - 추천 시스템의 협업 필터링
  - 신호 처리
  - 텍스트 마이닝과 토픽 모델링
  - 생체 정보 분석
  - 예시
    . 영화 평점 데이터에서 사용자-영화 행렬을 분해하면 사용자 취향과 영화 장르 정보를 추출 가능

 

2. 행렬 분해의 수학적 배경

    행렬 분해는 주어진 $m \times n$ 차원의 행렬 $X$를 원천 행렬 $S \in \mathbb{R}^{m \times d}$와 기여도 행렬 $A \in \mathbb{R}^{d \times n}$의 곱으로 나타내는 것입니다. 여기서 $d$는 잠재 차원의 개수를 가리킵니다. 목표는 $X$와 $S \times A$의 차이를 최소화하는 행렬 $S$, $A$를 찾는 것입니다. 이를 수식으로 표현하면:

$$\min \lVert X - S \times A \rVert^{2}_{F}$$

* $\lVert \rVert_F$ : 프로브니우스 노름(Frobenius norm)

※ 프로브니우스 노름(Frobenius Norm)
* 행렬의 노름(norm) 중 하나로, 행렬의 모든 원소 값에 대한 제곱 합의 제곱근
  - 유클리드 노름이 벡터의 크기를 나타내듯, 프로브니우스 노름은 행렬의 크기를 나타내는 스칼라 값임
* $m \times n$ 행렬 $A = (a_{ij})$에 대해,
$$\lVert A \rVert_{F} = \sqrt{\sum_{i, j} a_{ij}^2}$$
* 연산이 간단하고 미분이 용이하여 최적화 문제에 적합

 

2.1. 원천 행렬(Source Matrix)와 기여도 행렬(Abundance Matrix)

* 원천 행렬(Source Matrix) $S$
  - 데이터 $X$를 구성하는 기본 요소나 패턴
  - 각 열 벡터는 하나의 기본 패턴을 의미

* 기여도 행렬(Abundance Matrix) $A$
  - 각 기본 패턴이 원본 데이터 $X$에 기여하는 정도
  - 원소 $A_{ij}$ : $j$번째 패턴이 $i$번째 데이터 포인트에 기여하는 정도

* 예시
  - 텍스트 데이터 $X$가 문서-단어 행렬일 때,
    . $S$ : 단어 $m$, 토픽 $d$ 행렬
    . $A$ : 토픽 $d$, 문서 $n$ 행렬로, 각 문서가 토픽을 포함하는 정도

 

3. 대표적인 행렬 분해 기법

3.1. 비음수 행렬 분해(NMF; Non-negative Matrix Factorization)

$$X \approx W \times H$$

* 행렬 $X \in \mathbb{R}^{m \times n}$를 두 개의 비음수 행렬 기저 행렬 $W \in \mathbb{R}^{m \times d} \ge 0$, 계수 행렬 $H \in \mathbb{R}^{d \times n} \ge 0$의 곱으로 분해
* 비음수 제약 조건으로 인해 부분적으로 가산적인 구조를 가지므로 해석이 용이
* 텍스트 마이닝, 음성 처리, 이미지 처리에 활용

※ 비음수 제약 조건
* 분해된 행렬 $W$, $H$의 모든 원소가 0 이상의 값을 갖는 조건
  - 이 제약 조건으로 인해 데이터 $X$가 $W$와 $H$의 곱으로 표현될 때, 부분적으로 합쳐지는 구조를 가짐

 

* 파이썬 예제
  ① 예제 그래프 생성

import networkx as nx

G = nx.karate_club_graph()  # 예제 그래프
nx.draw(G)  # 그래프 시각화

예제 그래프 생성

 

  ② 그래프 인접 행렬 추출

A = nx.to_numpy_array(G)  # 그래프 인접 행렬
print("인접 행렬 크기:", A.shape)
print("인접 행렬:\n", A)

인접 행렬 크기: (34, 34)
인접 행렬:
[[0. 4. 5. ... 2. 0. 0.]
 [4. 0. 6. ... 0. 0. 0.]
 [5. 6. 0. ... 0. 2. 0.]
...
 [2. 0. 0. ... 0. 4. 4.]
 [0. 0. 2. ... 4. 0. 5.]
 [0. 0. 0. ... 4. 5. 0.]]

 

  ③ NMF 모델 학습 및 실행

from sklearn.decomposition import NMF

# NMF 모델 학습
nmf = NMF(n_components=5,  # 분해할 성분 개수
          init="nndsvd",  # 초기화 방법
          max_iter=200)  # 최대 반복 횟수
W = nmf.fit_transform(A)  # 기저 행렬(W)
H = nmf.components_  # 계수 행렬(H)
print("기저 행렬(W) 크기:", W.shape)
print("계수 행렬(H) 크기:", H.shape)

기저 행렬(W) 크기: (34, 5)
계수 행렬(H) 크기: (5, 34)

 

  ④ NMF 결과 시각화

import matplotlib.pyplot as plt

fig, subs = plt.subplots(ncols=2, figsize=(10, 5))
# 기저 행렬(W) 시각화
subs[0].imshow(W, cmap="Reds")
subs[0].set_title("W")
# 계수 행렬(H) 시각화
subs[1].imshow(H, cmap="Reds")
subs[1].set_title("H")

plt.show()

NMF 결과. (왼쪽) 기저 행렬, (오른쪽) 계수 행렬

 

3.2. 특이값 분해(SVD; Singular Value Decomposition)

$$X = U \Sigma V^T$$

* 행렬 $X$를 직교 행렬 $U$, $V^T$와 대각 행렬 $\Sigma$ 세 개의 행렬 곱으로 분해
* 데이터의 랭크와 고유값, 고유벡터를 계산할 수 있음

* 활용
  - 차원 축소 및 데이터 압축
    . $\Sigma$의 큰 특이값에 대응하는 $U$, $V$의 열 벡터만 선택하여 압축
    . 데이터 차원을 축소하고 노이즈를 제거
  - 노드 임베딩 및 시각화
    . $U$, $V$의 열 벡터를 노드 임베딩 벡터로 활용
    . 상위 k개의 열 벡터를 선택하여 k차원 공간에 노드를 임베딩하고 시각화
  - 그래프 클러스터링
    . $U$, $V^T$의 열 벡터를 기반으로 노드 클러스터링 수행
  - 신호 분석 및 주파수 영역 변환
    . $\Sigma$의 특이값은 그래프 신호의 주파수 성분을 나타냄
    . 주파수 영역에서 분석하거나 필터링을 수행할 수 있음

* 파이썬 예제
  ① SVD 실행

import numpy as np

U, Sigma, Vt = np.linalg.svd(A, full_matrices=False)  # SVD
Sigma_matrix = np.diag(Sigma)

print("U 크기:", U.shape)
print("Sigma 크기:", Sigma_matrix.shape)
print("Vt 크기:", Vt.shape)

U 크기: (34, 34)
Sigma 크기: (34, 34)
Vt 크기: (34, 34)

 

  ② SVD 결과 시각화

fig, subs = plt.subplots(ncols=3, figsize=(15, 5))
# U 시각화
subs[0].imshow(U, cmap="Reds")
subs[0].set_title("U")
# Sigma 시각화
subs[1].imshow(Sigma_matrix, cmap="Reds")
subs[1].set_title("Sigma")
# V 시각화
subs[2].imshow(Vt, cmap="Reds")
subs[2].set_title("Vt")

plt.show()

SVD 결과. (왼쪽) U, (중앙) Sigma, (오른쪽) Vt

 

3.3. 주성분 분석(PCA; Principal Component Analysis)

$$X \approx u + \sum z_i p_i$$

* 데이터 $X$를 평균 벡터 $u$와 주성분 벡터 $p_i$, 주성분 벡터에 투영된 X의 값인 $z_i$의 선형조합으로 나타냄
* 고차원 데이터의 차원을 낮추면서 가능한 많은 변동성을 보존하는 기법
* 차원 축소, 데이터 시각화, 노이즈 제거에 활용

* 파이썬 예제
  ① PCA 실행

from sklearn.decomposition import PCA

pca = PCA(n_components=5)  # PCA 모델 생성
zi = pca.fit_transform(A)  # PCA 모델 학습 및 변환
u = pca.mean_  # 평균 벡터(u)
pi = pca.components_  # 주성분 벡터(pi)

print("투영 벡터(zi) 크기:", zi.shape)
print("평균 벡터(u) 크기:", u.shape)
print("주성분 벡터(pi) 크기:", pi.shape)

투영 벡터(zi) 크기: (34, 5)
평균 벡터(u) 크기: (34,)
주성분 벡터(pi) 크기: (5, 34)

 

  ② PCA 결과 시각화

fig, subs = plt.subplots(ncols=2, figsize=(10, 5))
# 투영 벡터(zi) 시각화
subs[0].imshow(zi, cmap="Reds")
subs[0].set_title("zi")
# 계수 행렬(H) 시각화
subs[1].imshow(pi, cmap="Reds")
subs[1].set_title("pi")

plt.show()

PCA 결과. (왼쪽) 투영 벡터, (오른쪽) 주성분 벡터

 

4. 행렬 분해의 활용 사례

4.1. 링크 예측(Link Prediction)

* 그래프 데이터에서 노드 간 링크 존재 여부를 예측하는 문제
  - (소셜 네트워크) 친구 관계 예측
  - (생물학 네트워크) 단백질 간 상호작용 예측

 

4.2. 노드 임베딩(Node Embedding)

* 그래프 데이터의 노드를 낮은 차원의 밀집 벡터로 변환하는 작업
  - DeepWalk, Node2Vec 기법

 

4.3. 그래프 신호 처리(Graph Signal Processing)

* 그래프 신호(Graph Signal)
  - 그래프 구조의 각 노드에 스칼라 값이 할당된 형태
  - 예시
    . (교통 네트워크) 각 도로 구간의 혼잡도
    . (센서 네트워크) 각 센서의 측정값
    . (소셜 네트워크) 각 사용자의 특성값
    . (분자 구조) 각 원자의 전하량

* 그래프 신호의 필터링, 압축, 보간에 이용
  - 그래프 신호를 푸리에 기저(Fourier basis)로 분해

※ 그래프 푸리에 기저(Graph Fourier Basis)
* 그래프 라플라시안 행렬(Graph Laplacian Matrix)의 고유벡터(eigenvectors)로 구성되며, 이 고유벡터들은 그래프 구조를 반영하는 기저 함수 역할을 함
  - 그래프 신호를 그래프 라플라시안의 고유벡터들의 선형 조합으로 표현할 수 있음
$$f = \sum \alpha_i \phi_i$$
  - $f$ : 그래프 신호, $\phi_i$ : 그래프 푸리에 기저(고유벡터), $\alpha_i$ : 계수

※ 그래프 라플라시안 행렬(Graph Laplacian Matrix)
* 그래프의 구조적 특성을 포착하는 행렬
$$L = D - A$$
  - $D$ : 차수 행렬(Degree matrix)
    . 대각 행렬로 $D(i, i)$는 $i$번째 노드의 차수
  - $A$ : 인접 행렬(Adjacency matrix)
* 주요 특성
  - 대칭 행렬
  - 고유값은 0 이상
  - 고유벡터들은 그래프 푸리에 기저를 형성

 

4.4. 그래프 클러스터링(Graph Clustering)

* 그래프의 구조적 유사성을 포착
  - 커뮤니티 탐지