스펙트럴 클러스터링(Spectral Clustering): 라플라시안 행렬(Laplacian Matrix)과 고유값(Eigenvalue) 분석을 통한 그래프 구조의 수학적 표현

요약: 고윳값과 고유벡터는 그래프 안에서 '비슷하게 연결된 노드'를 숫자 공간에 가까이 위치시키며, K-Means 같은 단순한 알고리즘으로도 복잡한 연결 구조를 깔끔하게 분리할 수 있게 됨

• 그래프 이론의 행렬: 각 노드의 연결 관계를 수학적으로 표현하는 핵심 도구
• 차수 행렬(Degree matrix), 인접 행렬(Adjacency matrix), 라플라시안 행렬(Laplacian matrix): 그래프의 구조 정보를 담고 있음
• 라플라시안 행렬은 $L := D - A$로 정의되며, 고윳값(Eigenvalue)과 고유벡터(Eigenvector)를 통해 그래프의 특성을 요약
• $L$의 고윳값은 항상 $0$ 이상의 값을 가지며, 그 구조적 의미는 스펙트럴 분석(Spectral Analysis)에서 활용됨
• 정규화 라플라시안(Normalized Laplacian matrix)은 차수를 보정하여 다양한 그래프에 더 안정적으로 적용됨
• 스펙트럴 클러스터링(Spectral Clustering)
  - 라플라시안 행렬의 고유벡터를 기반으로 그래프 노드를 k-means와 같은 방법으로 클러스터링
  - 고차원 데이터에서도 이 기법은 구조적으로 비슷한 노드를 잘 분리해줌

 

 

 

꼭짓점(vertex) $n$개인 그래프(graph) $G$의

차수 행렬(degree matrix) $D$, 인접 행렬(adjacency matrix) $A$가 있을 때

라플라시안 행렬(Laplacian matrix) $L$은 아래와 같다.

$ L := D - A $

 

정의에서

• 대각성분 $ L_{i,i} = d_i - 0 = d_i $
• 비대각성분 $ L_{i,j} = 0 - A_{ij} = - A_{ij} $ 

이다.

무향(undirected) 그래프 가정 시 라플라시안 행렬의 성질은 아래와 같다.

1. Positive semi-definiteness
   [증명]
   임의의 벡터 $ \mathbf{x} \in \mathbb{R}^n $ 에 대해,
   변(edge) $(i, j) \in E $를 생각하면
   $ \mathbf{x} ^T D \mathbf{x} = \sum_{i=1}^{n} d_i x_i^2 = \sum_{(i, j) \subset E} (x_i^2 + x_j^2) $
   $ \mathbf{x} ^T A \mathbf{x} = \sum_{i=1}^{n} {\sum_{j=1}^{n} A_{ij} x_i x_j} = 2 \sum_{(i, j) \subset E} (x_i  x_j) $
   이므로 
   $ \mathbf{x} ^T L \mathbf{x} = \mathbf{x} ^T (D - A) \mathbf{x} = \sum_{(i, j) \subset E} (x_i  - x_j)^2  \geq 0 $ 
   
   
2. 고윳값의 최솟값은 항상 0이다.
   [증명]
   인접행렬 $A$의 각각의 행(또는 열)을 모두 더하면 차수가 되므로, $L$의 각각의 행(또는 열)의 합은 0이다.
   즉, $ L \mathbf{1} = 0 \cdot \mathbf{1} $이다.
   그런데, 위 성질 1에 의해 $L$은 Positive semi-definite이고, 따라서 모든 고윳값(eigenvalue) $ \lambda_i ≥ 0 $이다.

위 성질 2.를 고려하여 일반적으로 $L$의 고윳값을

$ 0 = \lambda_0 \leq \lambda_1 \leq ... \leq \lambda_{n-1} $와 같이 표기한다.

 

라플라시안 행렬의 스펙트럼(고유값, 고유벡터)은 그래프 내의 노드 간 연결 구조를 수학적으로 압축해서 보여준다.

(비슷한 노드끼리 묶을 수 있음)

 

고유벡터 공간에서는 노드 간 유사성이 잘 표현되며, 고유벡터들은 구조적으로 비슷한 노드를 비슷한 방향에 배치한다.

 

 

 

정규화 라플라시안 행렬(normalized Laplacian matrix) $L^{norm}$은 노드의 차수를 고려하여 스케일을 보정하며, 정의는 아래와 같다.

 

$ L^{norm} := D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2} $

 

대각성분 $ L_{i,i}^{norm} $은 $ L_{i,i} = d_i $ 에서

• $d_i >0$이면 $ {d_i}^{-1/2} \cdot d_i \cdot {d_i}^{-1/2} = 1$
• 아니면 0

이며,

비대각성분 $ L_{i,j}^{norm} (i \neq j) $는 $ L_{i,j} = - A_{ij} $ 에서

• $v_i$, $v_j$가 인접한 경우는 $ - {d_i}^{-1/2} \cdot 1 \cdot {d_j}^{-1/2} = - {d_i}^{-1/2} {d_j}^{-1/2} $
• 아니면 0

이다.

 

정규화 라플라시안 행렬의 성질:

고윳값은 0 이상 2 이하이며 최솟값은 항상 0이다.

 

[증명]

 

임의의 벡터 $ \mathbf{x} \in \mathbb{R}^n $ 에 대해

$ \mathbf{x}^T L_{norm} \mathbf{x} = (D^{-1/2} \mathbf{x})^T L (D^{-1/2} \mathbf{x}) $이므로

$ L $의 성질에서 $ L^{norm} $의 고윳값은 항상 0 이상이며,

최솟값은 항상 0이다.

 

한편 레일리 몫(Rayleigh quotient)

$ R( \mathbf{x} ) = \frac{  \mathbf{x}^T L_{norm} \mathbf{x}  }{  \mathbf{x}^T \mathbf{x} } $ 를 생각하면

 

$ R( \mathbf{x} ) = 1 - \frac{  \mathbf{x}^T D^{-1/2}AD^{-1/2} \mathbf{x}  }{  \mathbf{x}^T \mathbf{x} } $ 에서

$ I + D^{-1/2} A D^{-1/2} $ 가 positive semi-definite임을 보이면 $ R( \mathbf{x} ) \leq 2 $이므로 증명이 끝난다.

 

그런데 위의 라플라시안 행렬 증명과 유사하게

(표기법 수정하지 않고 복붙),

$ \mathbf{x} ^T (D + A) \mathbf{x} = \sum_{(i, j) \subset E} (x_i  + x_j)^2  \geq 0 $ 이므로

$ I + D^{-1/2} A D^{-1/2} $는 positive semi-definite이다.

 

 

 

스펙트럴 클러스터링(Spectral Clustering) = Embedding + Clustering:

• 서로 강하게 연결된 노드는 비슷한 좌표에 위치시킴
• 고유벡터는 이 노드 간 관계를 반영하여, 비슷한 노드끼리는 비슷한 수치값을 갖게 됨
• 이를 2차원 또는 3차원에 임베딩하고 K-Means를 적용하면 클러스터가 만들어짐

1. 라플라시안 계산(구조 정보 추출) 및 고유값 분해(그래프 구조를 반영한 축 생성)

2. (고윳값이 작은) 상위 k개의 고유벡터를 선택

3. 노드들을 $\mathbb{R}^k$ 공간에 임베딩 (i.e. k개 고유벡터 공간의 좌표(coordinate))

4. K-means와 같은 Clustering 기법 적용

 

 

 

예시 코드: 사이클 + 두 클러스터로 나뉜 그래프

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from sklearn.cluster import KMeans
from scipy.sparse.csgraph import laplacian
from sklearn.preprocessing import normalize

# 1. 그래프 생성 (두 그룹으로 나뉜 연결 구조)
G = nx.planted_partition_graph(l=2, k=10, p_in=0.9, p_out=0.05, seed=42)

# 2. 라플라시안 행렬 계산
A = nx.to_numpy_array(G)
L = laplacian(A, normed=True)  # 정규화 라플라시안

# 3. 고유벡터 계산
eigenvalues, eigenvectors = np.linalg.eigh(L)  # 작은 고윳값 순 정렬됨

# 4. 상위 2개 고유벡터로 임베딩
embedding = eigenvectors[:, 1:3]  # 첫 번째는 항상 0이므로 2번째부터

# 5. KMeans로 클러스터링
kmeans = KMeans(n_clusters=2, random_state=42).fit(embedding)
labels = kmeans.labels_

# 6. 시각화
plt.figure(figsize=(8, 4))

plt.subplot(1, 2, 1)
nx.draw_spring(G, node_color='lightgray', with_labels=True, edge_color='gray')
plt.title("Original Graph")

plt.subplot(1, 2, 2)
plt.scatter(embedding[:, 0], embedding[:, 1], c=labels, cmap='coolwarm', s=100, edgecolors='k')
plt.title("Spectral Embedding + KMeans")
plt.xlabel("2nd Eigenvector")
plt.ylabel("3rd Eigenvector")
plt.grid(True)

plt.tight_layout()
plt.show()