logo

그래프 라플라시안 📂그래프이론

그래프 라플라시안

정의

그래프 GG의 차수행렬를 DD, 인접행렬를 AA라고 하자. 이때, GG의 그래프 라플라시안graph Laplacian LL은 다음과 같이 정의된다.

L:=D−A L := D - A

설명

유클리드 공간 위의 함수에 대해서 정의되는 라플라시안 Δ=∑i∂2∂xi2\Delta = \sum\limits_{i} \frac{\partial^{2}}{\partial x_{i}^{2}}와는 다르게, 주어지는 그래프에 의존한다.

그래프 G=(V,E)G = (V, E)에 대해서 f:V→Rf : V \to \mathbb{R}을 노드 시그널이라 하고 f=[f(v1)⋯f(vn)]T\mathbf{f} = \begin{bmatrix} f(v_{1}) & \cdots & f(v_{n}) \end{bmatrix}^{\mathsf{T}}와 같이 표기하자. 그러면 LfL\mathbf{f}의 각 성분은 각 정점vertex에서의 값이 인접한 정점에서의 값과 얼마나 차이나는지를 나타낸다.

유도

다변수 함수 g:Rn→Rg : \mathbb{R}^{n} \to \mathbb{R}에 대해서 라플라시안은 다음과 같이 정의된다.

∇2g=Δg=∂2g∂x12+⋯+∂2g∂xn2 \nabla^{2} g = \Delta g = \dfrac{\partial^{2} g}{\partial x_{1}^{2}} + \cdots + \dfrac{\partial^{2} g}{\partial x_{n}^{2}}

실수 공간위에서 정의된 함수 f:R→Rf : \mathbb{R} \to \mathbb{R}의 미분 계수는 다음과 같이 수치적으로 근사할 수 있다.

f′(x)=f(x+h)−f(x)h f^{\prime}(x) = \dfrac{f(x+h) - f(x)}{h}

f′′(x)=f(x+h)−2f(x)+f(x−h)h2(1) f^{\prime \prime}(x) = \dfrac{f(x+h) - 2f(x) + f(x-h)}{h^{2}} \tag{1}

위 식을 그래프에 대해서 생각해보자. xx를 정점이라 보면, x+hx+h와 x−hx-h는 각각 xx와 연결된 정점이라 볼 수 있을 것이다. f(x)f(x) 앞의 22는 xx와 인접한 점이 두 개 라는 것을 의미한다. 따라서 (1)(1)을 그래프의 관점에서 보면 인접한 정점에 대한 값에서 기준이 되는 정점의 값을 차수만큼 빼준 것이다. 이를 수식으로 표현하면 A−DA - D이 될텐데, 부호를 반대로 하면 양의 정부호 행렬이 되므로 다음과 같이 정의한다.

L:=D−A L := D - A

■

성질

  1. 그래프 라플라시안 LL은 양의 정부호 행렬이다.

증명

1.

D=[Dij]D = [D_{ij}]와 A=[Aij]A = [A_{ij}]를 n×nn \times n 차수행렬과 인접행렬이라고 하자. x∈Rn\mathbf{x} \in \mathbb{R}^{n}이라고 하자.

xTLx=xT(D−A)x=xTDx−xTAx=∑i=1nDiixi2−∑i,j=1nAijxixj=∑i=1n(∑j=1nAij)xi2−∑i,j=1nAijxixj \begin{align*} \mathbf{x}^{\mathsf{T}} L \mathbf{x} &= \mathbf{x}^{\mathsf{T}} (D - A) \mathbf{x} \\ &= \mathbf{x}^{\mathsf{T}} D \mathbf{x} - \mathbf{x}^{\mathsf{T}} A \mathbf{x} \\ &= \sum\limits_{i=1}^{n} D_{ii} x_{i}^{2} - \sum\limits_{i,j = 1}^{n} A_{ij} x_{i} x_{j} \\ &= \sum\limits_{i=1}^{n} \left( \sum\limits_{j=1}^{n} A_{ij} \right) x_{i}^{2} - \sum\limits_{i,j = 1}^{n} A_{ij} x_{i} x_{j} \\ \end{align*}

이때 i,ji, j는 더미 인덱스이고 AA는 대칭행렬이므로, ∑i,jAijxi=∑i,jAijxj\sum_{i,j}A_{ij}x_{i} = \sum_{i,j}A_{ij}x_{j}가 성립한다. 따라서 다음을 얻는다.

xTLx=∑i,j=1nAij(xi2−xixj)=12∑i,j=1nAij(2xi2−2xixj)=12∑i,j=1nAij(xi2+xj2−2xixj)=12∑i,j=1nAij(xi−xj)2 \begin{align*} \mathbf{x}^{\mathsf{T}} L \mathbf{x} &= \sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i}^{2} - x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( 2x_{i}^{2} - 2x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i}^{2} + x_{j}^{2} - 2x_{i} x_{j} \right)\\ &= \dfrac{1}{2}\sum\limits_{i,j = 1}^{n} A_{ij} \left( x_{i} - x_{j} \right)^{2} \end{align*}

Aij≥0A_{ij} \ge 0이므로 LL은 양의 정부호 행렬이다.

■