그래프 라플라스 연산자

1. 개요

그래프 라플라스 연산자는 그래프 이론에서 사용되는 선형 연산자로, 그래프의 구조를 행렬 형태로 표현한다. 그래프 라플라스 연산자는 유계 작용소이며, 라플라스 행렬, 접속 행렬, 가중 그래프, 정규화 라플라스 행렬 등 다양한 형태로 정의될 수 있다. 이 연산자는 그래프의 연결성, 스펙트럼 특성, 생성 나무의 개수 등을 분석하는 데 활용되며, 이산 라플라스 연산자와의 관계를 통해 열 방정식과 같은 물리적 현상을 모델링하는 데에도 사용된다. 그래프 라플라스 연산자는 다양한 분야에서 응용되며, 그래프 이론 연구와 데이터 분석, 인공지능 기술 개발 등 다양한 분야에서 활용된다.

2. 정의

그래프 라플라스 연산자는 그래프의 꼭짓점과 변을 기반으로 정의되는 선형 연산자이다. 이 연산자는 다양한 방식으로 정의될 수 있지만, 가장 일반적인 정의는 차수 행렬과 인접 행렬의 차이를 이용하는 것이다.

체 $\backslash mathbb\; K$가 실수체($\backslash mathbb\; R$) 또는 복소수체($\backslash mathbb\; C$)이고, 그래프 $\backslash Gamma$의 모든 꼭짓점의 차수가 유한한 상한을 갖는다고 가정하자. 즉,
:이다.

이때, $\backslash operatorname\; V(\backslash Gamma)$로 생성되는 $\backslash mathbb\; K$-힐베르트 공간
:$V=\backslash operatorname\; L^2(\backslash operatorname\; V(\backslash Gamma);\backslash mathbb\; K)$
를 생각할 수 있다.

그래프 라플라스 연산자
:$\backslash Delta\_\backslash Gamma\backslash colon\; V\backslash to\; V$
는 유계 작용소이며, 다음과 같이 두 가지로 정의될 수 있으나, 이 두 정의는 서로 같다.

만약 $\backslash Gamma$가 유한 그래프라면, $\backslash operatorname\; V(\backslash Gamma)$ 위에 임의의 전순서를 부여하여 그래프 라플라스 연산자를 정수 성분 대칭 행렬로 표현할 수 있다. 이를 $\backslash Gamma$의 라플라스 행렬이라고 한다.

$V$의 원소는 함수
:$f\backslash colon\backslash operatorname\; V(\backslash Gamma)\backslash to\backslash mathbb\; K$
:
로 생각할 수 있다.

이제, 다음과 같은 $\backslash mathbb\; K$-선형 변환을 정의할 수 있다.
:$\backslash Delta\_\backslash Gamma\backslash colon\; V\backslash to\; V$
:$\backslash Delta\_\backslash Gamma\; f\backslash colon\; v\backslash mapsto\; \backslash sum\_\{uv\backslash in\backslash operatorname\; E(\backslash Gamma)\}\backslash left(f(v)-f(u)\backslash right)$
즉, 임의의 두 꼭짓점 $u,v\backslash in\backslash operatorname\; V(\backslash Gamma)$에 대하여 다음과 같다.
:$\backslash langle\; u|\backslash Delta\_\backslash Gamma|v\backslash rangle\; =\; \backslash begin\{cases\}$
-1&uv\in\operatorname E(\Gamma)\\
\deg v&u=v\\
0&u\ne v,\;uv\not\in\operatorname E(\Gamma)
\end{cases}

다른 방법으로는, 그래프 $\backslash Gamma$의 (방향이 없는) 변들로 생성되는 $\backslash mathbb\; K$-힐베르트 공간을 정의할 수 있다.
:$W=\backslash operatorname\; L^2(\backslash operatorname\; E(\backslash Gamma);\backslash mathbb\; K)$

$\backslash Gamma$ 위에 임의의 유향 그래프 구조를 주고, 그 유향 변들의 집합을
:$\backslash operatorname\{E\_\{or\}\}(\backslash Gamma)\backslash subseteq\backslash operatorname\; V(\backslash Gamma)^2$
라고 하면, 다음과 같은 연산자를 정의할 수 있다.
:$E\backslash colon\; W\backslash to\; V$
:$E|u,v\backslash rangle\; =\; |u\backslash rangle\; -\; |v\backslash rangle\; \backslash qquad\backslash left((u,v)\backslash in\backslash operatorname\{E\_\{or\}\}(\backslash Gamma)\backslash right)$

이는 유계 작용소를 정의하며, 따라서 그 에르미트 수반
:$E^\backslash dagger\backslash colon\; V\backslash to\; W$
를 정의할 수 있다. 이들을 합성하여 유계 작용소
:$\backslash Delta\_\backslash Gamma=EE^\backslash dagger$
:$\backslash Delta\_\backslash Gamma\backslash colon\; V\backslash to\; V$
를 정의할 수 있다. 이것은 $\backslash Gamma$의 유향 그래프 구조에 의존하지 않는다. (반면, $E^\backslash dagger\; E\backslash colon\; W\backslash to\; W$는 일반적으로 유향 그래프 구조에 의존한다.)

2.1. 라플라스 행렬

단순 그래프 $G$의 라플라스 행렬 $L$은 다음과 같이 정의된다.

:$L\_\{i,j\}\; :=\; \backslash begin\{cases\}$
\deg(v_i) & \mbox{if}\ i = j \\
-1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise},
\end{cases}

또는 행렬 표기를 사용하여 다음과 같이 나타낼 수 있다.

:$L\; =\; D\; -\; A,$

여기서 D는 차수 행렬이고 A는 그래프의 인접 행렬이다. $G$가 단순 그래프이므로, $A$는 1 또는 0만 포함하며 대각선 요소는 모두 0이다.

다음은 레이블이 지정된 무방향 그래프와 해당 라플라스 행렬의 예시이다.

무방향 그래프의 경우, 인접 행렬과 라플라스 행렬 모두 대칭이며 라플라스 행렬의 행과 열의 합이 모두 0임을 알 수 있다(이는 라플라스 행렬이 특이 행렬임을 직접적으로 의미한다).

방향 그래프의 경우, 응용 분야에 따라 내차수 또는 외차수를 사용할 수 있다.

👆

좌우로 밀어서 보기

📌 열 고정 해제

레이블이 지정된 그래프	인접 행렬	외차수 행렬	외차수 라플라스 행렬	내차수 행렬	내차수 라플라스 행렬
	$\backslash left(\backslash begin\{array\}\{rrr\}$	$\backslash left(\backslash begin\{array\}\{rrr\}$	$\backslash left(\backslash begin\{array\}\{rrr\}$	$\backslash left(\backslash begin\{array\}\{rrr\}$	$\backslash left(\backslash begin\{array\}\{rrr\}$

방향 그래프에서 인접 행렬과 라플라스 행렬은 모두 비대칭이다. 라플라스 행렬에서 내차수 또는 외차수 중 무엇을 사용했는지에 따라 열의 합 또는 행의 합이 0이 된다.

2.2. 접속 행렬을 통한 정의

그래프의 접속 행렬을 이용하여 라플라스 행렬을 정의할 수도 있다.

$|v|\; \backslash times\; |e|$ 크기의 방향성을 가진 접속 행렬 B는 정점 v와 간선 e (정점 $v\_i$와 $v\_j$를 연결하며, i ≠ j)에 대한 원소 $B\_\{ve\}$를 다음과 같이 정의한다.

:$B\_\{ve\}\; =\; \backslash left\backslash \{\backslash begin\{array\}\{rl\}$
1, & \text{if } v = v_i\\
-1, & \text{if } v = v_j\\
0, & \text{otherwise}.
\end{array}\right.

이 정의에서 간선은 기술적으로 방향성을 가지지만, 그 방향은 임의로 설정될 수 있으며, 이는 여전히 다음과 같이 정의되는 동일한 대칭 라플라시안 $|v|\; \backslash times\; |v|$ 행렬 L을 생성한다.

:$L\; =\; B\; B^\backslash textsf\{T\}$

여기서 $B^\backslash textsf\{T\}$는 B의 전치 행렬이다.

가중 엣지를 갖는 그래프의 경우, 가중치 인접 행렬 B를 정의하고 이를 사용하여 해당 대칭 라플라시안을 $L\; =\; B\; B^\backslash textsf\{T\}$로 구성할 수 있다. 여기서 설명하는 더 깨끗한 대안적 접근 방식은 가중치를 연결성으로부터 분리하는 것이다. 즉, 일반 그래프와 마찬가지로 인접 행렬을 계속 사용하고 가중치 값만 보유하는 행렬을 도입하는 것이다.

따라서 가중치가 없는 $|v|\; \backslash times\; |e|$ 인접 행렬 B의 정의를 재사용하며, 정점 v와 엣지 e (정점 $v\_i$와 $v\_j$를 연결하며, i > j)에 대한 요소 $B\_\{ve\}$를 다음과 같이 정의한다.

:$B\_\{ve\}\; =\; \backslash left\backslash \{\backslash begin\{array\}\{rl\}$
1, & \text{if } v = v_i\\
-1, & \text{if } v = v_j\\
0, & \text{otherwise}.
\end{array}\right.

이제 엣지 가중치를 포함하는 대각선 $|e|\; \backslash times\; |e|$ 행렬 W도 정의한다. 기술적으로 B의 정의에서 엣지는 방향성을 갖지만, 그 방향은 임의일 수 있으며, 여전히 다음과 같이 정의되는 동일한 대칭 라플라시안 $|v|\; \backslash times\; |v|$ 행렬 L을 생성한다.

:$L\; =\; B\; W\; B^\backslash textsf\{T\}$

여기서 $B^\backslash textsf\{T\}$는 B의 전치 행렬이다.

다음 예는 각 엣지 $e\_i$에 가중치 값 i를 할당하는 방식을 보여준다. $i=1,\; 2,\; 3,\; 4.$

2.3. 가중 그래프의 라플라스 행렬

가중 그래프의 경우, 인접 행렬의 각 원소는 해당 변의 가중치를 나타낸다. 라플라스 행렬은 단순 그래프와 마찬가지로 차수 행렬과 인접 행렬의 차이로 정의된다.
: $L\; =\; D\; -\; A,$
여기서 D는 차수 행렬이고 A는 그래프의 인접 행렬이다.

유향 그래프의 경우, 응용 분야에 따라 내차수 또는 외차수를 사용할 수 있다. 예를 들어 다음과 같다.

접속 행렬을 이용한 정의도 확장될 수 있는데, 이 경우 가중치를 나타내는 행렬 W를 도입하여 다음과 같이 정의한다.

가중치가 없는 $|v|\; \backslash times\; |e|$ 인접 행렬 B는 다음과 같이 정의한다. 정점 v와 엣지 e (정점 $v\_i$와 $v\_j$를 연결하며, i > j)에 대한 요소 B_ve는 다음과 같다.
:$B\_\{ve\}\; =\; \backslash left\backslash \{\backslash begin\{array\}\{rl\}$
1, & \text{if } v = v_i\\
-1, & \text{if } v = v_j\\
0, & \text{otherwise}.
\end{array}\right.

이제 엣지 가중치를 포함하는 대각선 $|e|\; \backslash times\; |e|$ 행렬 W도 정의한다. B의 정의에서 엣지는 방향성을 갖지만, 그 방향은 임의일 수 있으며, 여전히 다음과 같이 정의되는 동일한 대칭 라플라시안 $|v|\; \backslash times\; |v|$ 행렬 L을 생성한다.
:$L\; =\; B\; W\; B^\backslash textsf\{T\}$
여기서 $B^\backslash textsf\{T\}$는 B의 전치 행렬이다.

다음 예는 각 엣지 $e\_i$에 가중치 값 i를 할당하는 방식을 보여준다. $i=1,\; 2,\; 3,\; 4.$

2.4. 정규화 라플라스 행렬

라플라스 행렬의 정규화는 차수가 큰 꼭짓점의 영향을 줄이고, 그래프의 스펙트럼 특성을 더 잘 드러내기 위해 사용된다. 정규화에는 주로 대칭 정규화와 랜덤 워크 정규화 두 가지 방식이 사용된다.

대칭 정규화 라플라스 행렬:

대칭 정규화 라플라스 행렬은 다음과 같이 정의된다.

:$L^\backslash text\{sym\}\; :=\; (D^+)^\{1/2\}\; L\; (D^+)^\{1/2\}\; =\; I\; -\; (D^+)^\{1/2\}\; A\; (D^+)^\{1/2\}$

여기서,
* `L`은 비정규화 라플라스 행렬이다.
* `A`는 그래프의 인접 행렬이다.
* `D`는 차수 행렬이다.
* $D^+$는 무어-펜로즈 역행렬이다.

$L^\backslash text\{sym\}$의 각 요소는 다음과 같이 계산된다.

:$L^\backslash text\{sym\}\_\{i,j\}\; :=\; \backslash begin\{cases\}$
1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
-\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise}.
\end{cases}

* `i = j` 이고, 꼭짓점 `v_i`의 차수가 0이 아니면, 1이다.
* `i ≠ j` 이고, 꼭짓점 `v_i`와 `v_j`가 인접해 있으면, $-\backslash frac\{1\}\{\backslash sqrt\{\backslash deg(v\_i)\backslash deg(v\_j)\}\}$이다.
* 그 외의 경우에는 0이다.

인접 행렬이 대칭인 경우에만 대칭 정규화 라플라스 행렬도 대칭이 된다.

랜덤 워크 정규화 라플라스 행렬:

랜덤 워크 정규화 라플라스 행렬은 다음과 같이 정의된다.

:$L^\backslash text\{rw\}\; :=\; D^+L\; =\; I\; -\; D^+A$

여기서 $D^+$는 무어-펜로즈 역행렬이다.

$L^\backslash text\{rw\}$의 각 요소는 다음과 같이 계산된다.

:$L^\backslash text\{rw\}\_\{i,j\}\; :=\; \backslash begin\{cases\}$
1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\
-\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\
0 & \mbox{otherwise}.
\end{cases}

* `i = j` 이고, 꼭짓점 `v_i`의 차수가 0이 아니면, 1이다.
* `i ≠ j` 이고, 꼭짓점 `v_i`와 `v_j`가 인접해 있으면, $-\backslash frac\{1\}\{\backslash deg(v\_i)\}$이다.
* 그 외의 경우에는 0이다.

인접 행렬이 대칭인 경우에도, 왼쪽 또는 오른쪽 정규화된 라플라시안 행렬은 일반적으로 대칭이 아니다. (고립된 정점이 없는 경우).

$L^\backslash text\{rw\}$는 랜덤 워크 정규화 라플라시안이라고도 불리는데, 이는 $L^\backslash text\{rw\}\; =\; I\; -\; P$이고, $P\; =\; D^+A$가 그래프에서 랜덤 워크의 전이 행렬이기 때문이다.

3. 성질

그래프 라플라스 연산자는 다음과 같은 중요한 성질들을 갖는다.

그래프 라플라스 연산자는 유계 작용소이자 자기 수반 작용소이며, 그 성분들은 꼭짓점에 대한 표준 정규 직교 기저에서 모두 정수이다. 즉, 모든 꼭짓점의 차수가 유한한 임의의 그래프 $\backslash Gamma$ 및 $u,v\backslash in\backslash operatorname\; V(\backslash Gamma)$에 대하여 다음과 같다.
:$\backslash langle\; u|\backslash Delta\_\backslash Gamma|v\backslash rangle\; =\; \backslash langle\; v|\backslash Delta\_\backslash Gamma|u\backslash rangle\; \backslash in\backslash mathbb\; Z$
또한, 그 고윳값들은 모두 음이 아닌 실수이다. 그래프 라플라스 연산자의 고윳값들을 (중복수를 고려하여)
:$\backslash lambda\_0(\backslash Delta\_\backslash Gamma)\backslash le\; \backslash lambda\_1(\backslash Delta\_\backslash Gamma)\; \backslash le\; \backslash lambda\_2(\backslash Delta\_\backslash Gamma)\backslash le\backslash dotsb$
로 표기하면,
:$0\backslash le\backslash lambda\_0(\backslash Delta\_\backslash Gamma)$
이다.

그래프 라플라스 연산자의 작용소 노름은 다음과 같은 상계를 갖는다.
:$\backslash |\backslash Delta\_\backslash Gamma\backslash |\backslash le2\backslash max\_\{v\backslash in\backslash operatorname\; V(\backslash Gamma)\}\backslash deg\; v$

(무향) 그래프 G와 그 라플라스 행렬 L에 대한 고윳값 $\backslash lambda\_0\; \backslash le\; \backslash lambda\_1\; \backslash le\; \backslash cdots\; \backslash le\; \backslash lambda\_\{n-1\}$은 다음과 같은 성질을 갖는다.

* L은 대칭 행렬이다.
* L은 양의 정부호 행렬이다(즉, 모든 $i$에 대해 $\backslash lambda\_i\; \backslash ge\; 0$이다). 이는 라플라스 행렬이 대칭이고 대각 우세라는 사실에서 알 수 있다.
* L은 M-행렬이다(비대각선 요소는 음수이지만, 고윳값의 실수 부분은 0 이상이다).
* L의 모든 행 합과 열 합은 0이다. 실제로 합에서, 정점의 차수는 각 이웃에 대해 "−1"과 함께 합산된다.
* 결과적으로 $\backslash lambda\_0\; =\; 0$이며, 이는 벡터 $\backslash mathbf\{v\}\_0\; =\; (1,\; 1,\; \backslash dots,\; 1)$이 $L\; \backslash mathbf\{v\}\_0\; =\; \backslash mathbf\{0\}$을 만족하기 때문이다. 이는 또한 라플라스 행렬이 특이 행렬임을 의미한다.
* 그래프의 연결 요소 수는 라플라시안의 영공간의 차원과 0 고유값의 대수적 중복도이다.
* L의 가장 작은 0이 아닌 고유값은 스펙트럼 갭이라고 한다.
* L의 두 번째로 작은 고유값(0일 수 있음)은 그래프 G의 대수적 연결도 (또는 피들러 값)이며 그래프의 가장 희소한 컷을 근사한다.
* 라플라시안은 $f\; :\; V\; \backslash to\; \backslash mathbb\{R\}$ 형태의 n차원 함수 공간에 대한 연산자이며, 여기서 $V$는 G의 정점 집합이고, $n\; =\; |V|$이다.
* G가 k-정규일 때, 정규화된 라플라시안은 다음과 같다: $\backslash mathcal\{L\}\; =\; \backslash tfrac\{1\}\{k\}\; L\; =\; I\; -\; \backslash tfrac\{1\}\{k\}\; A$, 여기서 A는 인접 행렬이고 I는 항등 행렬이다.
* 여러 개의 연결 요소가 있는 그래프의 경우, L은 블록 대각 행렬이며, 각 블록은 각 구성 요소에 대한 해당 라플라스 행렬이다(정점의 재정렬 후일 수 있음, 즉 L은 블록 대각 행렬과 순열 유사하다).
* 라플라스 행렬 L의 대각합은 $2m$과 같으며, 여기서 $m$은 고려된 그래프의 간선 수이다.
* 단위 노름 고유벡터 $\backslash mathbf\{v\}\_i$와 해당 고유값 $\backslash lambda\_i$를 사용하여 $L$의 고유분해를 고려하면 다음과 같다.
:$\backslash begin\{align\}$
\lambda_i & = \mathbf{v}_i^\textsf{T} L \mathbf{v}_i \\
& = \mathbf{v}_i^\textsf{T} M^\textsf{T} M \mathbf{v}_i \\
& = \left(M \mathbf{v}_i\right)^\textsf{T} \left(M \mathbf{v}_i\right). \\
\end{align}

$\backslash lambda\_i$는 벡터 $M\; \backslash mathbf\{v\}\_i$와 자기 자신의 내적으로 표현될 수 있으므로, 이는 $\backslash lambda\_i\; \backslash ge\; 0$임을 보여주며, 따라서 $L$의 고유값은 모두 음수가 아니다.
* 정규화된 대칭 라플라시안의 모든 고유값은 0 = μ₀ ≤ … ≤ μ_n−1 ≤ 2를 만족한다. 이러한 고유값(정규화된 라플라시안의 스펙트럼으로 알려짐)은 일반 그래프의 다른 그래프 불변량과 잘 관련되어 있다.

* $L^\backslash text\{rw\}\; =\; I-D^\{-\backslash frac\{1\}\{2\}\}\backslash left(I\; -\; L^\backslash text\{sym\}\backslash right)\; D^\backslash frac\{1\}\{2\}$가 성립한다.

즉, $L^\backslash text\{rw\}$는 정규화된 라플라시안 $L^\backslash text\{sym\}$과 유사하다. 이러한 이유로, $L^\backslash text\{rw\}$가 일반적으로 대칭이 아니더라도 실수 고유값을 가지며, 이는 정규화된 대칭 라플라시안 $L^\backslash text\{sym\}$의 고유값과 정확히 동일하다.

$|v|\; \backslash times\; |e|$ 크기의 방향성을 가진 접속 행렬 B는 정점 v와 간선 e (정점 $v\_i$와 $v\_j$를 연결하며, i ≠ j)에 대한 원소 B_ve를 다음과 같이 정의한다.
:$B\_\{ve\}\; =\; \backslash left\backslash \{\backslash begin\{array\}\{rl\}$
1, & \text{if } v = v_i\\
-1, & \text{if } v = v_j\\
0, & \text{otherwise}.
\end{array}\right.
이 정의에서 간선은 기술적으로 방향성을 가지지만, 그 방향은 임의로 설정될 수 있으며, 이는 여전히 다음과 같이 정의되는 동일한 대칭 라플라시안 $|v|\; \backslash times\; |v|$ 행렬 L을 생성한다.
:$L\; =\; B\; B^\backslash textsf\{T\}$
여기서 $B^\backslash textsf\{T\}$는 B의 전치 행렬이다.

다른 곱인 $B^\backslash textsf\{T\}B$는 원래 일반적으로 사용되는 정점 기반 라플라시안 행렬 L과 대조적으로, 소위 $|e|\; \backslash times\; |e|$ 크기의 간선 기반 라플라시안을 정의한다.

3.1. 부분 그래프

다음이 주어졌다고 하자.

* 유한 그래프 $\backslash Gamma$
* 꼭짓점 집합 $S\backslash subseteq\backslash operatorname\; V(\backslash Gamma)$

그렇다면, 다음이 성립한다.

:$\backslash lambda\_1(\backslash Gamma)\backslash le\; \backslash lambda\_1(\backslash Gamma\backslash setminus\; S)+|S|$

3.2. 생성나무

유한 그래프 $\backslash Gamma$의 라플라스 행렬을 이용하여 그래프의 생성나무의 개수를 계산할 수 있다.

임의의 꼭짓점 $v\backslash in\backslash operatorname\; V(\backslash Gamma)$에 대해, $\backslash Delta\_\backslash Gamma$에서 $v$에 대응하는 행과 열을 생략한 $(|\backslash operatorname\; V(\backslash Gamma)|-1)\backslash times(|\backslash operatorname\; V(\backslash Gamma)|-1)$ 행렬을 $\backslash Delta\_\backslash Gamma[v]$로 표기하면, 다음이 성립한다.

* $\backslash det\backslash Delta\_\backslash Gamma[v]\backslash in\backslash mathbb\; Z$는 항상 자연수이다.
* $\backslash det\backslash Delta\_\backslash Gamma[v]$는 $v\backslash in\backslash operatorname\; V(\backslash Gamma)$의 선택에 의존하지 않는다.
* $\backslash det\backslash Delta\_\backslash Gamma[v]$는 $\backslash Gamma$의 생성나무의 수와 같다.
* $\backslash textstyle\backslash det\backslash Delta\_\backslash Gamma[v]\; =\; |\backslash operatorname\; V(\backslash Gamma)|^\{-1\}\backslash sum\_\{i=1\}^$

다른 곱인 $B^\backslash textsf\{T\}B$는 원래 일반적으로 사용되는 정점 기반 라플라시안 행렬 L과 대조적으로, 소위 $|e|\; \backslash times\; |e|$ 크기의 간선 기반 라플라시안을 정의한다.

4. 일반화 및 확장

그래프 라플라스 연산자는 다양한 방식으로 일반화되거나 확장될 수 있다.

* 일반화 라플라시안: 단순 그래프의 라플라스 행렬을 일반화한 것이다. 비대각선 원소의 부호에 제약이 완화된 행렬이다. 인접한 꼭짓점에 대응하는 비대각선 원소는 0보다 작아야 하지만, 인접하지 않은 꼭짓점에 대응하는 비대각선 원소는 0이어야 한다. 대각선 원소는 어떤 숫자든 될 수 있다.
* 자기 라플라시안: 그래프의 변에 복소수 가중치를 부여해 정의한다. 양자 물리학에서 자기장 하의 전하 입자 현상을 설명하는 데 사용된다. 실수 가중치를 갖는 방향성 그래프에 대한 자기 라플라스 연산자는 대칭화된 라플라스 연산자와 복소수 항목을 갖는 에르미트 위상 행렬의 하대마르 곱으로 구성된다. 양자 물리학에서 자기 라플라스 연산자는 그래프에서 자기장의 작용을 받는 자유 전하 입자의 현상을 설명하는 연산자로 해석될 수 있으며, 매개변수는 전하라고 불린다.
* 변형 라플라시안: 다음과 같이 정의된다.

:$\backslash Delta(s)\; =\; I\; -\; sA\; +\; s^2(D\; -\; I)$

여기서 I는 단위 행렬, A는 인접 행렬, D는 차수 행렬, s는 (복소) 수이다. 표준 라플라시안은 $\backslash Delta(1)$이다.
* 부호 없는 라플라시안: 단순 그래프에서 부호 없는 라플라스 연산자 $Q$는 다음과 같이 정의된다.

:$Q\; =\; D\; +\; A$

여기서 $D$는 차수 행렬이고, $A$는 인접 행렬이다. 부호 있는 라플라시안과 마찬가지로, 부호 없는 라플라시안 역시 양의 반정부호 행렬이며, 인수분해할 수 있다.
* 유향 멀티그래프: 방향 그래프의 경우, 응용 분야에 따라 내차수 또는 외차수를 사용한다. 유향 멀티그래프에 대한 라플라스 행렬은 외차수 행렬과 인접 행렬의 차이로 정의된다.

:$L\; =\; D\; -\; A$

여기서 D는 대각 행렬로, D_i,i는 정점 i의 밖차수와 같으며, A는 A_i,j가 i에서 j로 가는 간선의 수(루프 포함)와 같은 행렬이다.

4.1. 일반화 라플라시안

단순 그래프에서 라플라스 행렬을 일반화한 형태가 일반화 라플라시안이다. 일반화 라플라시안은 비대각선 원소의 부호에 대한 제약이 완화된 행렬이다. 즉, 인접한 꼭짓점에 대응하는 비대각선 원소는 0보다 작아야 하지만, 인접하지 않은 꼭짓점에 대응하는 비대각선 원소는 0이어야 한다. 대각선 원소는 어떤 숫자든 될 수 있다.

일반화 라플라시안 $Q$는 다음과 같이 정의된다.
:$\backslash begin\{cases\}$
Q_{i,j} < 0 & \mbox{만약 } i \neq j \mbox{ 이고 } v_i \mbox{가 } v_j \mbox{에 인접하면}\\
Q_{i,j} = 0 & \mbox{만약 } i \neq j \mbox{ 이고 } v_i \mbox{가 } v_j \mbox{에 인접하지 않으면} \\
\mbox{어떤 숫자} & \mbox{그렇지 않으면}.
\end{cases}

4.2. 자기 라플라시안

자기 라플라시안은 그래프의 변에 복소수 가중치를 부여하여 정의되는 연산자이다. 이는 양자 물리학에서 자기장 하의 전하 입자 현상을 설명하는 데 사용된다.

실수 가중치 $w\_\{ij\}$를 갖는 방향성 그래프에 대한 자기 라플라스 연산자는 대칭화된 라플라스 연산자와 복소수 항목을 갖는 에르미트 위상 행렬의 하대마르 곱으로 구성된다.

:$\backslash gamma\_q(i,\; j)\; =\; e^\{i2\; \backslash pi\; q(w\_\{ij\}-w\_\{ji\})\}$

이는 복소 평면에서 위상으로 에지 방향을 인코딩한다.

양자 물리학의 맥락에서 자기 라플라스 연산자는 그래프에서 자기장의 작용을 받는 자유 전하 입자의 현상을 설명하는 연산자로 해석될 수 있으며, 매개변수 $q$는 전하라고 불린다.

다음은 $q=1/4$인 경우의 예시이다.

4.3. 변형 라플라시안

변형 라플라시안은 일반적으로 다음과 같이 정의된다.

:$\backslash Delta(s)\; =\; I\; -\; sA\; +\; s^2(D\; -\; I)$

위 식에서,

* I는 단위 행렬
* A는 인접 행렬
* D는 차수 행렬
* s는 (복소) 수

이다.

표준 라플라시안은 $\backslash Delta(1)$이다.

4.4. 부호 없는 라플라시안

단순 그래프 $G$가 $n$개의 꼭짓점을 가질 때, 부호 없는 라플라스 연산자 $Q$는 다음과 같이 정의된다.

:$Q\; =\; D\; +\; A$

여기서 $D$는 차수 행렬이고, $A$는 인접 행렬이다. 부호 있는 라플라시안 $L$과 마찬가지로, 부호 없는 라플라시안 $Q$ 역시 양의 반정부호 행렬이며, 다음과 같이 인수분해할 수 있다.

:$Q\; =\; RR^\backslash textsf\{T\}$

여기서 $R$은 사건 행렬이다. $Q$는 이분 연결 요소(고립된 정점은 이분 연결 요소임)를 가질 경우에만 0-고유벡터를 갖는다. 이것은 다음과 같이 나타낼 수 있다.

:$\backslash mathbf\{x\}^\backslash textsf\{T\}\; Q\; \backslash mathbf\{x\}\; =\; \backslash mathbf\{x\}^\backslash textsf\{T\}\; R\; R^\backslash textsf\{T\}\; \backslash mathbf\{x\}\; \backslash implies\; R^\backslash textsf\{T\}\; \backslash mathbf\{x\}\; =\; \backslash mathbf\{0\}.$

이는 그래프가 이분 연결 요소를 가질 경우에만 $\backslash mathbf\{x\}\; \backslash neq\; \backslash mathbf\{0\}$인 해를 갖는다.

4.5. 유향 멀티그래프

방향 그래프의 경우, 적용 분야에 따라 내차수 또는 외차수를 사용할 수 있다. 유향 멀티그래프에 대한 라플라스 행렬은 외차수 행렬과 인접 행렬의 차이로 정의된다.

:$L\; =\; D\; -\; A$

여기서 D는 대각 행렬로, D_i,i는 정점 i의 밖차수와 같으며, A는 A_i,j가 i에서 j로 가는 간선의 수(루프 포함)와 같은 행렬이다.

5. 이산 라플라스 연산자와의 관계

그래프 라플라스 행렬은 유한 차분법을 통해 얻어지는 음의 연속 라플라스 연산자를 근사하는 그래프 상의 음의 이산 라플라스 연산자의 행렬 형태로 볼 수 있다. (이산 푸아송 방정식 참조) 이 해석에서, 모든 그래프 정점은 격자점으로 취급된다. 정점의 국소 연결성은 이 격자점에서 유한 차분 근사 스텐실을 결정하고, 격자 크기는 모든 에지에 대해 항상 1이며, 균질 노이만 경계 조건, 즉 자유 경계의 경우에 해당하여 어떠한 격자점에도 제약이 없다.

n개의 꼭짓점을 가진 단순 그래프(루프나 다중 변을 갖지 않는 무향 그래프)를 생각할 때, 그 라플라시안 행렬 $L\_\{n\; \backslash times\; n\}$는 다음과 같이 정의된다.

:$L\; =\; D\; -\; A$

여기서 D는 그래프의 차수 행렬, A는 인접 행렬이다. $G$는 단순 그래프이므로, $A$의 성분은 1 또는 0뿐이며, 그 대각 요소는 모두 0이다.

Directed graph^영어의 경우, 입차수 또는 출차수 중 하나가 용도에 따라 사용될 것이다.

$L$의 요소는 다음과 같이 주어진다.

:$L\_\{i,j\}\; :=\; \backslash begin\{cases\}$
\deg(v_i) &\mbox{if}\ i = j \\
-1 &\mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\
0 &\mbox{otherwise}
\end{cases}

여기서 $\backslash operatorname\{deg\}(v\_i)$는 꼭짓점 $i$의 차수이다.

$\backslash phi$가 그래프에 걸쳐 열 분포를 설명한다고 가정하면($\backslash phi\_i$는 정점 $i$에서의 열), 뉴턴의 냉각 법칙에 따르면, 노드 $i$와 노드 $j$ 사이를 이동하는 열은, 노드 $i$와 노드 $j$가 연결되어 있다면, $\backslash phi\_i\; -\; \backslash phi\_j$에 비례한다(노드가 연결되어 있지 않다면 열은 이동하지 않는다).

그러면, 열 용량 $k$에 대해,

:$\backslash begin\{align\}$
\frac{d \phi_i}{d t}
&= -k \sum_j A_{ij} \left( \phi_i - \phi_j \right) \\
&= -k \left( \phi_i \sum_j A_{ij} - \sum_j A_{ij} \phi_j \right) \\
&= -k \left( \phi_i \ \deg(v_i) - \sum_j A_{ij} \phi_j \right) \\
&= -k \sum_j \left( \delta_{ij} \ \deg(v_i) - A_{ij} \right) \phi_j \\
&= -k \sum_j \left( \ell_{ij} \right) \phi_j.
\end{align}

행렬-벡터 표기법으로 나타내면,

:$\backslash begin\{align\}$
\frac{d\phi}{dt} &= -k(D - A)\phi \\
&= -kL \phi
\end{align}

이를 통해,

:$\backslash frac\{d\; \backslash phi\}\{d\; t\}\; +\; kL\backslash phi\; =\; 0$

을 얻을 수 있다.

이 방정식은 행렬 −L이 라플라스 연산자 $\backslash nabla^2$를 대체하고 있는 열 방정식^한국어과 같은 형식이다. 따라서, L은 "그래프 라플라시안"이라고 불린다.

이 미분 방정식의 해를 찾기 위해, 1차 Matrix differential equation^영어을 풀기 위한 표준적인 기법을 적용한다. 즉, L의 고유 벡터 $\backslash mathbf\{v\}\_i$($L\backslash mathbf\{v\}\_i\; =\; \backslash lambda\_i\; \backslash mathbf\{v\}\_i$)의 선형 결합으로 $\backslash phi$를 쓴다. 시간에 의존하는 $\backslash phi\; =\; \backslash sum\_i\; c\_i\; \backslash mathbf\{v\}\_i$를 대입한다.

원래 식에 대입하면(L이 대칭 행렬이기 때문에 그 단위 노름 고유 벡터 $\backslash mathbf\{v\}\_i$는 직교한다는 사실을 이용):

:$\backslash begin\{align\}$
\frac{d\left(\sum_i c_i \mathbf{v}_i\right)}{dt} + kL\left(\sum_i c_i \mathbf{v}_i\right) &= 0 \\
\sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i L \mathbf{v}_i\right] &= \\
\sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i \lambda_i \mathbf{v}_i\right] &= \\
\frac{dc_i}{dt} + k \lambda_i c_i &= 0\\
\end{align}

이 해는

:$c\_i(t)\; =\; c\_i(0)\; e^\{-k\; \backslash lambda\_i\; t\}$

이다.

L의 고유값 $\backslash lambda\_i$는 음이 아니며, 이는 미분 방정식의 해가 평형에 접근한다는 것을 나타낸다. 즉, $\backslash lambda\_i$와 초기 조건 $c\_i(0)$이 주어지면, 어떤 시점에서의 해라도 찾을 수 있다. 전체 초기 조건 $\backslash phi(0)$의 관점에서 각각의 $i$에 대한 $c\_i(0)$를 찾기 위해서는, $\backslash phi(0)$을 단위 노름 고유 벡터 $\backslash mathbf\{v\}\_i$로 투영한다.

:$c\_i(0)\; =\; \backslash left\backslash langle\; \backslash phi(0),\; \backslash mathbf\{v\}\_i\; \backslash right\backslash rangle$

무향 그래프의 경우, $L$이 대칭 행렬이므로 이는 잘 동작하며, 스펙트럼 정리에 의해, 그 고유 벡터는 모두 직교한다.

6. 응용

그래프 라플라스 연산자는 다양한 분야에서 응용된다.

* 스칼라런 스펙트럼 군집화
* PyGSP: 파이썬에서의 그래프 신호 처리
* megaman: 수백만 개의 점에 대한 매니폴드 학습
* smoothG
* 동적 그래프를 위한 라플라시안 변곡점 감지 (KDD 2020)
* LaplacianOpt (가중 그래프의 라플라시안의 두 번째 고유값을 최대화하기 위한 줄리아 패키지)
* LigMG (대규모 불규칙 그래프 멀티그리드)
* Laplacians.jl

7. 예

유한 완전 그래프 $K\_n$의 라플라스 행렬은 다음과 같이 표현된다.

:$\backslash langle\; u|\backslash Delta\_\{K\_n\}|v\backslash rangle=n\backslash langle\; u|v\backslash rangle-1=$
\begin{cases}
n-1 & u=v\\
-1 & u\ne v
\end{cases}

이는 다시 다음과 같이 표현할 수 있다.

:$\backslash Delta\_\{K\_n\}=n\; -\; \backslash mathsf\; J$

여기서 $\backslash mathsf\; J$는 모든 성분이 1인 행렬(아다마르 곱의 항등원)이다. $K\_n$ 속의 생성 나무의 수는 다음과 같다.

:$\backslash det\; \backslash Delta\_\{K\_n\}[u]\; =\; \backslash det(n\; -\; \backslash mathsf\; J\_\{(n-1)\backslash times(n-1)\})\; =\; n^\{n-2\}$

특히, $K\_2$의 라플라스 행렬은 다음과 같다.

:$\backslash Delta\_\{K\_2\}\; =\; \backslash begin\{pmatrix\}$
1&-1\\
-1&1
\end{pmatrix}

이 행렬의 고윳값은 다음과 같다.

:$\backslash lambda\_0(\backslash Delta\_\{K\_2\})=0$
:$\backslash lambda\_1(\backslash Delta\_\{K\_2\})=2$

꼭짓점 차수가 상한을 갖는 (유한 또는 무한) 그래프에 대하여, 다음 두 조건은 서로 동치이다.
* 무변 그래프이다.
* 그래프 라플라스 연산자가 0이다.

다음은 레이블이 지정된 무방향 그래프와 해당 라플라시안 행렬의 예시이다.