그래프 라플라스 연산자

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$

또한, 그 고윳값들은 모두 음이 아닌 실수이다.^[31] 그래프 라플라스 연산자의 고윳값들을 (중복수를 고려하여)

:$\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)$

이다.

그래프 라플라스 연산자의 작용소 노름은 다음과 같은 상계를 갖는다.^[31]

:$\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$의 고유분해를 고려하면 다음과 같다.

• 정규화된 대칭 라플라시안의 모든 고유값은 0 = μ₀ ≤ … ≤ μ_n−1 ≤ 2를 만족한다. 이러한 고유값(정규화된 라플라시안의 스펙트럼으로 알려짐)은 일반 그래프의 다른 그래프 불변량과 잘 관련되어 있다.^[1]

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

• 1, & \text{if } v = v_j\\

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

3. 1. 부분 그래프

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

3. 2. 생성나무

• $\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$의 생성나무의 수와 같다.^[30]
• $\backslash textstyle\backslash det\backslash Delta\_\backslash Gamma[v]\; =\; |\backslash operatorname\; V(\backslash Gamma)|^\{-1\}\backslash sum\_\{i=1\}^$
  \lambda_i(\Delta_\Gamma)이다.^[30]

  3. 3. 표현

  유클리드 공간$\backslash mathbb\; R^n$이 주어졌다고 하자. 유한 그래프 $\backslash Gamma$의 '''균형 직교 표현'''(balanced orthogonal representation^영어)은 다음 조건을 만족시키는 함수
  
  :$\backslash rho\backslash colon\backslash operatorname\; V(\backslash Gamma)\backslash to\backslash mathbb\; R^n$
  
  이다.

  
  
  • (균형성) $\backslash textstyle\backslash sum\_\{v\backslash in\backslash operatorname\; V(\backslash Gamma)\}\backslash rho(v)=0$
  • (직교성) $\backslash textstyle\; \backslash sum\_\{v\backslash in\backslash operatorname\; V(\backslash Gamma)\}\backslash rho\_i(v)\backslash rho\_j(v)\; =\; \backslash delta\_\{ij\}\backslash qquad\backslash forall\; i,j\backslash in\backslash \{1,\backslash dotsc,n\backslash \}$

  
  이 두 조건에 의하여, 균형 직교 표현이 존재하려면 $n\backslash ge\; 1+\backslash operatorname\; V(\backslash Gamma)$이어야 한다.
  
  유한 그래프 $\backslash Gamma$의 $\backslash mathbb\; R^n$ 속의 균형 직교 표현 $\backslash rho$가 주어졌으며, 또한
  
  :$\backslash lambda\_1(\backslash Delta\_\backslash Gamma)>0$
  
  라고 하자. 그렇다면, 다음이 성립한다.^[30]
  
  :$\backslash sum\_\{uv\backslash in\backslash operatorname\; E(\backslash Gamma)\}\backslash |\backslash rho(u)-\backslash rho(v)\backslash |$
  
  \ge \lambda_1(\Delta_\Gamma)+\lambda_2(\Delta_\Gamma)+\dotsb+\lambda_n(\Delta_\Gamma)
  
  $|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''의 전치 행렬이다.
  
  

  무방향 그래프	접속 행렬	라플라시안 행렬
  	$\backslash left(\backslash begin\{array\}\{rrrr\}$	$\backslash left(\backslash begin\{array\}\{rrrr\}$

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

4. 일반화 및 확장

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

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

• 부호 없는 라플라시안: 단순 그래프에서 부호 없는 라플라스 연산자 $Q$는 다음과 같이 정의된다.^[6]

• 유향 멀티그래프: 방향 그래프의 경우, 응용 분야에 따라 내차수 또는 외차수를 사용한다. 유향 멀티그래프에 대한 라플라스 행렬은 외차수 행렬과 인접 행렬의 차이로 정의된다.^[7][26]

4. 1. 일반화 라플라시안

4. 2. 자기 라플라시안

4. 3. 변형 라플라시안

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

4. 4. 부호 없는 라플라시안

4. 5. 유향 멀티그래프

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

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

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

:$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 \\

6. 응용

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

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

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

• 1&1

• 무변 그래프이다.
• 그래프 라플라스 연산자가 0이다.

참조

_[1] 서적 Spectral Graph Theory http://www.math.ucsd[...] American Mathematical Society
_[2] 간행물 Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24–27, 2003, Proceedings Springer
_[3] 서적 Algebraic Graph Theory, Graduate Texts in Mathematics Springer-Verlag 2001
_[4] 학회 Graph Signal Processing for Directed Graphs based on the Hermitian Laplacian https://ecmlpkdd2019[...]
_[5] 저널 The Deformed Consensus Protocol http://hal.archives-[...]
_[6] 저널 Towards a Spectral Theory of Graphs Based on the Signless Laplacian, III 2010
_[7] 저널 Matrix Tree Theorems
_[8] 웹사이트 SciPy https://github.com/s[...] 2023-10-04
_[9] 웹사이트 NetworkX https://github.com/n[...] 2023-10-04
_[10] 웹사이트 Julia https://github.com/J[...] 2023-10-04
_[11] 웹사이트 2.3. Clustering https://scikit-learn[...]
_[12] 웹사이트 PyGSP: Graph Signal Processing in Python https://github.com/e[...] 2022-03-23
_[13] 웹사이트 Megaman: Manifold Learning for Millions of Points https://github.com/m[...] 2022-03-14
_[14] 웹사이트 SmoothG https://github.com/L[...] 2020-09-17
_[15] 웹사이트 Announcing Our Paper at KDD 2020 https://complexdatal[...]
_[16] 웹사이트 Harshangrjn/LaplacianOpt.jl https://github.com/h[...] 2022-02-02
_[17] 웹사이트 LigMG (Large Irregular Graph MultiGrid)-- A distributed memory graph Laplacian solver for large irregular graphs https://github.com/l[...] 2022-01-05
_[18] 웹사이트 Laplacians.jl https://github.com/d[...] 2022-03-11
_[19] 문서 Laplacian Matrix
_[20] 서적 Algebraic Graph Theory, Graduate Texts in Mathematics Springer-Verlag 2001
_[21] 저널 The Deformed Consensus Protocol
_[22] 서적 Spectral graph theory American Math. Soc.
_[23] 서적 Spectral Graph Theory http://www.math.ucsd[...] American Mathematical Society
_[24] 서적 Networks: An Introduction Oxford University Press
_[25] 간행물 Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24–27, 2003, Proceedings Springer
_[26] 저널 Matrix Tree Theorems http://www.sciencedi[...]
_[27] 저널 A survey of graph Laplacians 1995
_[28] 저널 Laplacian matrices of graphs: a survey 1994-01
_[29] 서적 The Laplacian spectrum of graphs https://www.seas.upe[...] 매니토바 대학교 2000-07-01
_[30] 서적 Algebraic graph theory https://www.math.uwa[...] Springer Verlag
_[31] 저널 Eigenvalues of the Laplacian of a graph 1985