라플라시안과 그래프 라플라시안(Laplacian and graph Laplacian)

점 아홉 개에 값을 하나씩 매겼습니다. 처음 모양은 이고, 점을 위아래로 끌 수 있습니다. 양 끝 점은 고정되어 있습니다. 안쪽 점마다 청록 막대가 그 점의 값에서 양옆 두 점의 평균까지 뻗어 있습니다. 한 걸음 섞기 처음으로

지금 안쪽 점들의 '이웃 평균 − 나'는 입니다. 이 값이 라플라시안입니다. 양수면 그 점은 이웃보다 낮고, 음수면 높고, 0이면 딱 이웃의 평균입니다. 톱니에서는 모든 막대가 길고, 언덕에서는 짧고, 직선에서는 모두 0입니다. 꺾인 선에서는 꺾인 한 점에서만 0이 아닙니다.

연속인 경우. 간격 $h$로 늘어선 점에서 테일러 전개를 하면 일차 항이 서로 지워져 $\tfrac12\bigl(u(x-h) + u(x+h)\bigr) - u(x) = \tfrac{h^2}{2}\,u''(x) + O(h^4)$입니다($u$가 네 번 미분⁠(differentiation)⁠ 가능할 때). 그래서 이계 도함수⁠(derivative function)⁠는 '휘어진 정도'이면서 동시에 '나는 이웃 평균에서 얼마나 벗어나 있는가'입니다. 평면의 격자에서 위아래 좌우 이웃 넷의 평균을 쓰면 $\tfrac{h^2}{4}(u_{xx} + u_{yy})$, $n$차원에서 이웃 $2n$개를 쓰면 $\tfrac{h^2}{2n}\sum_i u_{x_i x_i}$가 나옵니다. 이 합 $\Delta u = \sum_i \partial^2 u / \partial x_i^2$를 라플라시안⁠(Laplacian)⁠이라 하고 $\nabla^2 u$로도 씁니다. 좌표축을 어떻게 돌려 잡아도 $\Delta u$의 값은 같습니다. 방향에 치우침이 없는 연산입니다.

그래프의 경우. 그래프에서는 변으로 이어진 꼭짓점⁠(vertex)⁠이 이웃입니다. 이웃 수가 꼭짓점마다 달라서 보통 평균 대신 합을 쓰고 부호를 뒤집습니다. 차수(이어진 변의 수)를 대각선에 놓은 행렬 $D$와 인접 행렬⁠(adjacency matrix)⁠ $A$로 $L = D - A$이고, $(Lu)_v = \sum_{w\sim v}(u_v - u_w)$입니다. 부호를 뒤집는 까닭은 이렇게 하면 모든 벡터⁠(vector)⁠ $u$에 대해

$$u^{\mathsf T} L u = \sum_{\text{변 } ab} (u_a - u_b)^2 \;\ge\; 0$$

이 되기 때문입니다. 행렬 $L$은 대칭이라 고유벡터⁠(eigenvector)⁠들로 서로 수직인 좌표축을 잡을 수 있고, 위의 부등식 때문에 고유값⁠(eigenvalue)⁠이 모두 0 이상입니다. 이 부등식 하나에서 여러 사실이 나옵니다.

• 연결 조각 세기. $u^{\mathsf T}Lu = 0$이려면 이어진 꼭짓점끼리 값이 같아야 하므로, 고유값 0이 나오는 횟수가 그래프의 연결 조각의 수입니다. 두 번째로 작은 고유값 $\lambda_2$(피들러의 대수적 연결도⁠(algebraic connectivity)⁠)가 0보다 크면 그래프는 이어져 있고, 그 고유벡터의 부호로 꼭짓점을 가르면 대개 적게 자르는 가르기가 나옵니다(스펙트럴 군집⁠, spectral clustering⁠). 가장 적게 자른다는 보장은 없고, $\lambda_2$가 작을수록 적게 자를 여지가 있다는 부등식(치거 부등식⁠, Cheeger inequality⁠)이 방법을 받쳐 줍니다.
• 나무 세기. 아무 꼭짓점 하나의 행과 열을 지운 행렬식⁠(determinant)⁠은 신장 트리⁠(tree)⁠의 개수입니다(키르히호프의 행렬–트리 정리⁠(matrix-tree theorem)⁠, 1847). $L = BB^{\mathsf T}$($B$는 접속 행렬⁠(incidence matrix)⁠)으로 쓰고 코시–비네 공식⁠(Cauchy–Binet formula)⁠을 적용하면, 트리를 이루는 변 묶음마다 정확히 1이 더해집니다.
• 에너지. $\sum (u_a - u_b)^2$은 1옴 저항 회로가 잃는 전력이고, 연속에서는 디리클레 에너지⁠(Dirichlet energy)⁠ $\iint |\nabla u|^2$입니다. 경계를 고정하고 이것을 가장 작게 하는 $u$는 안쪽 모든 점에서 $Lu = 0$, 곧 조화 함수⁠(harmonic function)⁠입니다.

흔한 오해. "라플라시안은 이계 도함수⁠(second derivative)⁠를 모두 모은 것"이라고 생각하기 쉽지만, 섞인 도함수 $u_{xy}$는 들어 있지 않습니다. 곡면의 휘어짐을 온전히 담는 것은 이계 도함수의 행렬(헤세 행렬⁠, Hessian matrix⁠)이고, 라플라시안은 그 대각합, 곧 모든 방향의 휘어짐의 평균에 비례하는 수 하나입니다. 그래서 말안장 모양 $x^2 - y^2$처럼 한쪽으로는 위로, 다른 쪽으로는 아래로 똑같이 휜 곡면은 휘어 있어도 라플라시안이 0입니다. 또 부호의 관례가 둘이라는 것도 기억해 둘 만합니다. 해석학⁠(mathematical analysis)⁠의 $\Delta$는 '이웃 평균 − 나'의 방향이고, 그래프의 $L$은 '나 − 이웃'의 방향이라 $L$은 $-\Delta$에 해당합니다.

고유 모드⁠(eigenmode)⁠. 라플라시안이 모양은 두고 크기만 바꾸는 함수⁠(function)⁠ $\Delta\varphi = -\lambda\varphi$를 고유 모드라고 합니다. 양 끝을 고정한 길이 $\pi$의 막대에서는 $\sin kx$($\lambda = k^2$)이고, 이것으로 함수를 분해하는 것이 푸리에 급수⁠(Fourier series)⁠입니다. 한 줄로 이은 꼭짓점 $n$개의 그래프에서는 고유벡터가 정확히 이산 코사인 변환⁠(discrete cosine transform)⁠의 코사인⁠(cosine)⁠들입니다.

이어지는 곳. 온도가 '이웃 평균 − 나'에 비례해 변한다는 식이 열방정식⁠(heat equation)⁠ $u_t = \Delta u$이고, 가속도가 그에 비례하면 파동방정식⁠(wave equation)⁠입니다. 고유 모드마다 열에서는 $e^{-\lambda t}$로 사라지고 파동에서는 $\cos\sqrt\lambda\, t$로 떠는데, 모드로 바꿔 보면 연산이 곱셈이 된다는 점에서 대각화⁠(diagonalization)⁠의 가장 유명한 보기입니다. 무작위 행보가 어느 경계에 먼저 닿을 확률⁠(probability)⁠은 라플라시안이 0인 함수여서 도박꾼의 파산⁠(gambler's ruin)⁠과 전기 회로가 같은 문제가 되고, 그래프 위의 확률이 퍼지는 마르코프 연쇄⁠(Markov chain)⁠와 페이지랭크⁠(PageRank)⁠도 같은 뼈대를 씁니다. 사진을 흐리게 하는 것도, 경계를 찾는 것도, 확산 모델⁠(diffusion model)⁠이 잡음을 더하고 되돌리는 것도 이 연산 위에서 일어납니다. 이 모든 곳을 한 줄로 따라가는 긴 글이 「라플라시안, 가장 많이 재사용된 식」입니다.