보강 3. 그래프 라플라시안과 스펙트럴 클러스터링

L12는 회로 이야기로 끝났다. 그리고 마지막 절에서 행렬 하나를 만들었다.

(1)의 $L$ 을 그래프 라플라시안이라 부른다고 하고 L12는 거기서 멈췄다. 그때는 회로를 푸는 도구였을 뿐이다.

그런데 이 행렬은 대칭이고 준정부호다. 그러니 L25의 스펙트럼 정리가 무조건 통하고, L27의 에너지 이야기도 통한다. 후반부에서 만든 도구가 전부 들어맞는다는 뜻이다.

그러면 그 도구로 무엇을 할 수 있는가. 놀랍게도 그래프를 자르는 선을 알려준다.

1. L12가 한 줄을 남겨 두었다¶

L12의 마지막 논증을 다시 보자. $L\vv{x} = \vv{0}$ 인 $\vv{x}$ 를 찾을 때 이렇게 썼다.

(2)의 오른쪽을 성분으로 풀어 쓰기만 하면 이 글 전체가 나온다. L12는 그것을 하지 않고 넘어갔다.

성분으로 풀어 쓴다¶

$A$ 의 $k$ 번째 행은 간선 $k$ 에 해당한다. 그 간선이 노드 $i$ 에서 노드 $j$ 로 간다면 그 행은 이렇게 생겼다(L12).

(3)의 행에는 0이 아닌 성분이 딱 둘뿐이다. 그러니 $\vv{x}$ 와 곱할 때 살아남는 항도 둘뿐이다.

이다. (4)의 값이 L12에서 "간선 양 끝의 전위차"라고 부른 것이다. 이제 (2)의 제곱합에 넣는다.

여기서 두 가지가 공짜로 나온다¶

첫째, $L$ 은 준정부호다. (5)의 오른쪽이 제곱의 합이니 음수가 될 수 없다. L27의 다섯 조건 중 "에너지"로 판정한 것이고, $L = A^{\mathsf T}A$ 라는 꼴에서 곧바로 나오는 것이기도 하다.

둘째, 상수벡터가 영공간에 있다. $\vv{1} = (1,1,\dots,1)$ 을 넣으면 모든 간선에서 $x_i - x_j = 0$ 이므로 (5)의 값이 0이다. 준정부호에서 에너지가 0이면 영공간에 있는 것이므로

이다. (1)의 정의로 보면 더 뻔하다. $i$ 번째 행을 다 더해 보자.

(8)의 계산은 "대각에 차수가 있고 나머지에 -1 이 차수만큼 있다"를 그대로 적은 것이다. 행의 합이 0이라는 것이 곧 $L\vv{1} = \vv{0}$ 이다.

대각합도 세어 두자. L21에서 대각합이 고윳값의 합이었다.

(9)의 마지막 등식은 간선 하나가 양 끝에서 한 번씩 세어지기 때문이다. 고윳값을 다 더하면 간선 수의 두 배다.

2. 영공간의 차원이 조각의 개수다¶

L12에서는 연결된 그래프만 다뤘고, 그때 영공간이 상수벡터 하나뿐이라고 했다. 연결이 끊기면 어떻게 되는가.

에너지가 0이라는 것의 뜻¶

$\vv{x}^{\mathsf T}L\vv{x} = 0$ 이라고 하자. (5)의 오른쪽은 제곱의 합이므로 모든 항이 각각 0이어야 한다.

(10)의 오른쪽은 "이어진 두 노드는 값이 같다"는 뜻이다. 그런데 한 연결 성분 안에서는 어떤 두 노드도 간선을 따라 이어져 있으므로, 그 길을 따라가며 값이 계속 같아야 한다. 한 성분 안에서는 값이 상수다.

성분끼리는 이어져 있지 않으니 서로 다른 값을 가져도 된다.

확인해 보자. 성분 $S$ 의 지시벡터를 $\vv{1}_S$ 라 하면, 어떤 간선 $(i,j)$ 든 양 끝이 같은 성분에 있다. 성분을 넘나드는 간선은 정의상 없기 때문이다. 그러니 두 값이 항상 같다.

(12)에서 에너지가 0이고 $L$ 이 준정부호이므로 $L\vv{1}_S = \vv{0}$ 이다. 그리고 성분이 다르면 겹치는 자리가 없으므로 $\vv{1}_S^{\mathsf T}\vv{1}_{S'} = 0$, 곧 서로 직교라 독립이다. 성분이 $c$ 개면 독립인 벡터가 $c$ 개 나온다.

3. 두 번째 고윳값이 진짜 이야기다¶

$\lambda_1 = 0$ 은 아무것도 말해 주지 않는다. 어떤 그래프에서든 그렇기 때문이다. $\lambda_2$ 부터가 정보다.

• $\lambda_2 = 0$ 이면 Theorem 1에 의해 연결이 끊겨 있다.

• $\lambda_2$ 가 아주 작으면 끊어질 뻔했다. 다리 몇 개로 겨우 붙어 있다는 뜻이다.

• $\lambda_2$ 가 크면 단단히 얽혀 있다.

그래서 $\lambda_2$ 를 대수적 연결도(algebraic connectivity)라 부르고, 그 고유벡터를 피들러 벡터라 부른다. 미로슬라프 피들러가 1973년에 이 성질을 알아낸 데서 왔다.

왜 최소화 문제인가¶

$\lambda_2$ 가 무엇을 최소로 하는 것인지 적어 두자. L25의 스펙트럼 정리로 $L = Q\Lambda Q^{\mathsf T}$ 라 쓰고, $\vv{x}$ 를 고유기저로 펼치면 $\vv{x} = \sum_i c_i\vv{q}_i$ 이고

가 된다. (14)의 오른쪽은 $\lambda_i$ 들의 가중평균이므로 가장 작은 것 이상이다. 보강 1에서 쓴 레일리 몫 바로 그것이다.

아무 조건도 없으면 최솟값은 $\lambda_1 = 0$ 이고, 그것을 주는 $\vv{x}$ 는 상수벡터다. 시시한 답이다. 그래서 그 방향을 막는다.

막는다는 것이 고유좌표에서 무슨 뜻인지 보자. $\vv{q}_1 = \vv{1}/\sqrt{n}$ 이므로

이고, (15)의 조건을 (14)의 식에 넣으면 첫 항이 통째로 사라진다.

(16)의 부등식에서 등호는 $c_2$ 만 남을 때, 곧 $\vv{x} = \vv{q}_2$ 일 때 성립한다. 한 방향을 막았더니 최솟값이 그다음 고윳값으로 올라간 것이다.

(17)의 오른쪽을 말로 옮기면 이렇다. 성분의 합이 0이라는 조건 아래에서, 이웃끼리 가장 덜 어긋나게 값을 적는 방법.

합이 0이라는 조건은 "양수도 있고 음수도 있어야 한다"는 뜻이다. 곧 모두를 같은 편에 둘 수는 없다. 그러면서 이웃끼리는 되도록 같은 편에 두라는 것이니, 답이 자연스럽게 두 덩어리로 갈린다.

앵커¶

삼각형 두 개를 다리 하나로 이은 그래프를 보자.

(18)의 대각선이 차수 $(2,2,3,3,2,2)$ 이고 행의 합이 전부 0이다.

이 그래프는 좌우가 대칭이다(노드 $0\leftrightarrow5$, $1\leftrightarrow4$, $2\leftrightarrow3$ 을 맞바꾸면 그대로다). 그러니 $\vv{1}$ 에 수직인 고유벡터는 반대칭일 것이라 짐작하고 $\vv{x} = (a, a, b, -b, -a, -a)$ 로 놓아 보자. 첫 행과 셋째 행을 쓰면

이다. (19)의 왼쪽에서 $b = (1-\lambda)a$ 를 얻어 오른쪽에 넣으면

가 되고, (20)의 근이 답이다.

(21)의 값이 수치 계산과 소수점 아홉 자리까지 일치한다. 그리고 피들러 벡터는 $(-0.465, -0.465, -0.261, +0.261, +0.465, +0.465)$ 다.

4. 그래서 그래프를 자른다¶

이제 알고리즘이 나온다. 놀랍도록 짧다.

Definition 1의 절차는 그래프의 구조를 아무에게도 알려주지 않았다. 고윳값 하나를 구했을 뿐인데 덩어리가 갈린다.

왜 이것이 좋은 절단인가¶

절단의 크기, 곧 두 편을 잇는 간선의 개수를 세어 보자. $\vv{x}$ 를 한쪽은 +1, 다른 쪽은 -1 인 벡터로 두면 (5)에서

항마다 두 경우뿐이다.

(22)의 값을 다 더하면 4가 건너는 간선의 개수만큼 나온다.

(23)의 등식이 다리를 놓아 준다. 절단을 작게 하는 것과 $\vv{x}^{\mathsf T}L\vv{x}$ 를 작게 하는 것이 같은 일이다.

그리고 $\pm1$ 성분의 합이 0이라는 조건은 양쪽을 반반으로 나누라는 뜻이다. 그러면 우리가 풀고 싶은 문제는 이렇게 적힌다.

(24)의 문제는 NP-어렵다. 후보의 개수를 세어 보면 왜 그런지 짐작이 간다.

(25)의 값은 1초에 10억 개씩 세어도 2년이 걸린다. 노드가 60개인 작은 그래프에서 그렇다.

그런데 여기서 조건 하나를 놓아 준다. $x_i \in \{-1,+1\}$ 이라는 조건을 빼고 실수를 허용하면, 남는 것이 정확히 (17)의 문제이고 답이 $\lambda_2$ 와 피들러 벡터다.

실제로 잘라 보면¶

노드 60개를 두 덩어리로 만들고 덩어리 안은 촘촘히, 사이는 성기게 이었다. 간선이 320개이고 그중 두 덩어리를 잇는 것이 15개다.

피들러 벡터의 부호로 자르면 30 대 30으로 정확히 갈리고 15개를 자른다. 무작위로 반반 나눈 것 5000개와 견주면 최선이 125개다.

언제 안 되는가¶

$\lambda_2$ 는 "얼마나 붙어 있는가"를 재는 수다. 그러니 덩어리가 애초에 없으면 알려줄 것도 없다. 두 덩어리 사이의 다리를 늘려 가며 재 보면 그것이 보인다.

다리가 없으면 $\lambda_2 = 0$ 이고 갈래가 뚜렷하다. 다리를 몇 개 놓아도 $\lambda_2$ 가 작게 남아 여전히 잘 갈린다. 그런데 다리를 충분히 많이 놓으면 두 덩어리라는 것이 더 이상 사실이 아니고, 그때는 알고리즘이 틀린 것이 아니라 찾을 것이 없는 것이다.

5. 어디까지 가는가¶

두 조각으로 가르는 것이 전부가 아니다.

$k$ 조각으로 나누려면 고유벡터를 $\vv{q}_2, \dots, \vv{q}_k$ 까지 $k-1$ 개 쓴다. 노드 $i$ 에 좌표를 하나씩 붙이는 셈이다.

(26)의 좌표는 그래프에서 가까운 노드를 $\R^{k-1}$ 에서도 가깝게 놓는다. 그 위에서 보통의 군집화를 돌리면 된다. 이것이 스펙트럴 클러스터링이다. $k = 2$ 이면 좌표가 하나뿐이고, 그 부호로 자르는 것이 4절이었다.

이미지 분할도 같은 틀이다. 픽셀을 노드로 두고 이웃 픽셀을 간선으로 이은 뒤, 색이 비슷할수록 큰 가중치를 준다. 그러면 라플라시안이 $L = A^{\mathsf T}CA$ 가 되는데, L12에서 회로의 전도도로 만든 바로 그 행렬이다. 피들러 벡터가 그 그래프를 자르면 그것이 곧 물체의 경계다.

반반이 아니어도 될 때가 실무에서는 더 흔하다. 4절에서는 $\pm1$ 성분의 합이 0이라는 조건을 걸었고, 그것은 정확히 반반으로 나누라는 뜻이었다. 그럴 이유가 없다.

크기가 $a$ 와 $b$ 인 두 덩어리 $A, B$ 로 나누고 싶다면 값을 이렇게 잡으면 된다.

(27)의 벡터는 두 조건을 자동으로 만족한다. 합을 세어 보면

이다. 이제 (5)에 넣는다. 건너는 간선에서만 값이 생기고, 그때 차이는 $\sqrt{b/a} + \sqrt{a/b}$ 이므로

가 된다. (28)의 노름이 $n$ 이었으니 레일리 몫은 $n$ 이 약분되어

(30)의 오른쪽이 정체를 밝혀 준다. $\lambda_2$ 를 구하는 것은 RatioCut 을 완화해 푸는 것이다. 절단이 작으면서 양쪽 마디 수가 고를수록 값이 작아진다.

그런데 마디 수로 균형을 잡는 것이 늘 옳지는 않다. 차수가 제각각이면 간선 수로 재는 편이 낫다. $\vol A = \sum_{i \in A}\deg(i)$ 라 두고 분모를 바꾼 것이 Ncut 이다.

(31)의 목적함수를 완화해 푸는 것이 정규화 라플라시안이다.

(32)의 행렬도 대칭이고 준정부호이므로 지금까지의 이야기가 그대로 통한다. $\vv{y} = D^{1/2}\vv{x}$ 로 바꿔 놓으면 무엇이 달라졌는지 보인다.

(33)에서 차수가 큰 노드는 분모가 커서 덜 어긋난 것으로 세어진다. 그래서 허브 하나가 절단을 좌우하지 못한다.

6. 자주 하는 오해¶

① 라플라시안은 인접행렬이다. 아니다. L11의 인접행렬은 이어져 있으면 1, 아니면 0인 $n \times n$ 행렬이다. 라플라시안은 $L = D - W$ 로, 대각에 차수가 들어가고 비대각의 부호가 음수다. 그 차이 때문에 행의 합이 0이 되고, 그래서 $\lambda_1 = 0$ 이 나온다.

② $\lambda_2$ 가 작으면 좋은 그래프다. 좋고 나쁨의 문제가 아니다. $\lambda_2$ 가 작다는 것은 끊어지기 쉽다는 뜻이다. 통신망이라면 나쁜 소식이고, 군집을 찾고 싶다면 좋은 소식이다.

③ 부호로 자르는 것이 최적 절단이다. 아니다. (24)의 문제는 NP-어렵고, 피들러 절단은 그것을 완화해 푼 것이다. 대개 아주 좋지만 최적이라는 보장은 없다. 실제로 이 강의의 큰 예제에서는 참 분할을 정확히 찾았지만, 그것이 늘 그렇다는 뜻은 아니다.

④ 0을 기준으로 잘라야 한다. 그럴 필요 없다. 피들러 벡터의 성분을 정렬해 놓고 어디를 잘라도 후보 분할이 된다. $n-1$ 개의 후보를 전부 재 보고 가장 좋은 것을 고르는 방법을 흔히 쓴다. 0으로 자르는 것은 가장 단순한 규약일 뿐이다.

⑤ 고유벡터의 부호가 정해져 있다. 아니다. $\vv{f}$ 가 고유벡터면 $-\vv{f}$ 도 고유벡터다(L21). 그래서 어느 쪽이 "1번 덩어리"인지는 소프트웨어 마음이다. 분할은 같고 이름만 바뀐다.

⑥ 라플라시안은 대칭이니 언제나 대각화된다 — 그러니 조건이 좋다. 대각화는 되지만 조건이 좋다는 것은 다른 이야기다. $\lambda_2$ 와 $\lambda_3$ 이 가까우면 피들러 벡터 자체가 불안정해진다. 두 고유벡터가 만드는 평면은 잘 정해져도 그 안에서 어느 방향인지는 흔들린다. 보강 2의 고윳값 조건수 이야기가 여기서도 산다.

마치며...¶

이번 글에서는 L12에서 만들어 놓고 이름만 붙였던 행렬을 끝까지 따라갔다.

• $\vv{x}^{\mathsf T}L\vv{x} = \sum_{(i,j)\in E}(x_i-x_j)^2$ 이다. L12는 이 한 줄 앞에서 멈췄다. 이 식 하나가 라플라시안의 모든 성질을 준다.

• 그래서 $L$ 은 준정부호이고(L27), 대칭이라 스펙트럼 정리가 통하며(L25), 상수벡터가 언제나 영공간에 있다.

• 영공간의 차원이 연결 성분의 개수다. 다리를 끊으면 0이 하나 는다.

• $\lambda_2$ 는 "얼마나 붙어 있는가"를 재고, 그 고유벡터의 부호가 그래프를 가른다.

• 그 절단이 왜 좋은가 하면, $\pm1$ 벡터에서 $\vv{x}^{\mathsf T}L\vv{x}$ 가 절단 크기의 4배이기 때문이다. 어려운 이산 문제를 연속 문제로 완화한 것이다.

고윳값이 시간의 흐름을 예측하고(L23), 확률의 정착점을 알려주고(L24), 이제는 그래프를 자르는 선까지 알려준다.

그리고 여기서 끝난다¶

서른네 편의 본편과 세 편의 보강편이 지났다.

$A\vv{x} = \vv{b}$ 라는 방정식 하나에서 시작했다. 푸는 법을 배웠고, 해가 사는 공간의 모양을 배웠고, 해가 없을 때 가장 가까운 답을 찾는 법을 배웠다. 그다음 방향을 돌려 행렬 자체를 들여다보았다. 변하지 않는 방향을 찾았고, 시간의 흐름을 예측했고, 조건 없이 쪼갤 수 있는 도구에 닿았다. 마지막에는 그 도구를 들고 밖으로 나가 자료를 줄이고, 계산이 무너지는 자리를 재고, 그래프를 잘랐다.

돌아보면 같은 문장이 계속 나왔다.

좋은 기저를 고르면 어려운 문제가 쉬워진다. 대각화가 그랬고, 푸리에가 그랬고, DCT가 그랬고, SVD가 그랬고, 방금 본 피들러 벡터가 그랬다.

존재하는 것과 손에 쥘 수 있는 것은 다르다. 크래머 공식도, 여인수 전개도, 조르당 형도, 정규방정식도, 공분산행렬도 종이 위에서는 옳았다.

조건이 없는 도구가 가장 강하다. 그래서 이 책의 후반부는 조건을 하나씩 버리는 이야기였고, 마지막에 아무 조건도 없는 분해에 닿았다.

이제 길이 여러 갈래로 갈라진다. 최적화로, 함수해석으로, 확률과 통계로, 미분기하로. 어느 길로 가든 손에 쥔 다섯 개의 분해와 네 부분공간의 그림은 계속 쓰이게 될 것이다.

긴 여정에 함께해 주어 고맙습니다.

이번 글의 내용을 파이썬으로 확인해 보려면 보강 3 실습 노트북으로 넘어가면 된다. 이차형식이 정말 차이 제곱의 합인지 재 보고, 다리를 끊어 가며 0인 고윳값이 늘어나는 것을 보고, 60개짜리 그래프를 피들러 벡터로 잘라 무작위 5000개와 겨뤄 볼 수 있다.