D028

Eigenvalues of the Laplacian Matrix

이전 d-regular 예시와 같이
고유벡터는 해당 노드의 라벨(그룹) 속성을 나타냅니다.
이번 포스팅에서는 라플라시안 행렬의 고유값과 고유벡터가
어떤 특성을 나타내고, 이를 어떻게 사용할 수 있는지에 대해 다루겠습니다.

라플라시안 행렬의 가장 작은 고유값은 0 입니다. 이에 해당하는 고유벡터는 (1,1,…,1) 입니다.
L 을 n 개의 노드가 있는 그래프의 라플라시안 행렬이라 합시다.
1 은 n 길이고 모든 성분이 1인 칼럼 벡터입니다. $(1,1,\dots,1)^T$
L과 1의 곱, L1 은 모든 성분이 0인 칼럼 벡터가 됩니다.

L의 i 번째 행에서, i번째 열(대각 성분)은 노드 i 의 차수 d 입니다.
i 행은 d 개의 -1 성분이있고, 나머지는 성분은 0 입니다.
그래서 1과의 곱해서 합은 0이됩니다. (d + d(-1))

L1 = 01 이고,
여기서 0 이 고유값, 1 이 고유벡터가 됩니다.
그리고 이는 행렬의 가장 작은 고유값입니다.(라플라시안은 non-negative 고유값을 가진다.)

라플레시안과 같은 symmetric 행렬에서는
두번째로 작은 고유값을 구하는 방법이 있습니다.

x가 n 개의 요소를 가진 벡터일 때, $[x_1,x_2,\dots,x_n]$
두번째로 작은 고유값은 $x^TLx$ 의 최소값입니다.(증명은 추후 추가예정)
그리고 이 최소값은 다음과 같은 제약조건이 있습니다.

1. 벡터 x의 길이는 1 입니다. $\sum_{i=1}^n x_i^2 = 1$
2. 벡터 x는 가장 작은 고유값의 고유벡터와 직교합니다.(1벡터와 직교)

이 조건을 만족하는 가장 작은 값이
라플라시안 행렬의 두번째로 가장 작은 고유값이 됩니다.

2번 조건에서 말하는 고유벡터는 1 입니다.
x 는 1과 직교해야하므로,
2번 조건은 다음과 같이 표현할 수 있습니다.

\[x^T1 = \sum_{i=1}^n x_i = 0\]

라플라시안 행렬은 L = D-A 이므로
식 $x^TLx$ 다음과 같이 표현할 수 있습니다.
$x^TLx = x^TDx -x^TAx$

$x^TDx$ 에서 $Dx$ 는
행 벡터$ [d_1x_1,d_2x_2,\dots,d_nx_n]$ 입니다. ($d_i$ 는 i 노드의 차수입니다.)
그러므로 $x^TDx = \sum_{i=1}^nd_ix_i^2$ 이 됩니다.

$x^TAx$ 에서
칼럼벡터 $Ax$의 i번째 요소는 엣지 (i,j) 로 연결된 $x_j$ 인 것들의 합입니다.(i와 연결된 노드에 해당하는 x 들의 합)
그래서 $-x^TAx$ 는 $-2x_ix_j$ 의 합이 됩니다. (i,j 사이 엣지가 있는 경우)
+엣지 {i,j} 는 2번 나타나므로 2를 곱합니다. ($-x_ix_j, -x_jx_i$)

우리는 $x^TLx$
$x^TDx$ 로 부터 $d_ix_i^2$ 를 얻었고, $-x^TAx$ 로 부터 $-2x_ix_j$ 를 얻었습니다.
여기서 $d_i$ 는 i 노드와 연결된 다른 노드입니다.
그 결과, 노드 i 와 j 사이 엣지를 갖는 각 쌍 {i,j}는
$x_i^2 -2x_ix_j +x_j^2$ 과 연결할 수 있습니다.
그리고 이 식은 $(x_i-y_j)^2$ 과 같습니다.

결과적으로 $x^TLx$ 는 그래프의 전체 엣지(i,j) 중 $(x_i-x_j)^2$ 의 합 과 동일합니다.

직관적으로 생각해보면,
$x_i,x_j$ 의 값을 가깝게 만들면서, $(x_i-x_j)^2$ 을 최소화 합니다.

$\sum_{i=1}^n x_i^2 = 1$ 제약이 있으므로
$x_i = 1/ \sqrt{n}$ 을 선택해서 0 으로 만드는 것을 생각해 볼 수 있습니다.
이는 조건 $\sum_{i=1}^n x_i = 0$ 으로 인해 성립하지 않습니다.

$x_i$ 를 모두 0 으로 두는 경우에는
$\sum_{i=1}^n x_i^2 = 1$ 을 성립하지 않습니다.
그래서 결과적으로 x는 일부는 양수, 일부는 음수인 성분을 갖어야 합니다.

이제 그래프를 두개로 분할 할 수 있습니다.
$x_i$ 가 양수인 노드 i 로 구성된 집합과, $x_i$ 가 음수로 구성된 집합으로 나눌 수 있습니다.

부호로 분할하는 것은 집합을 동일한 크기로 분할한다는 것을 보장하지는 않습니다.
그러나 일반적으로 비슷한 크기를 갖게 됩니다.
$x_i,x_k$ 둘이 다른 부호일 때 보다 동일한 부호일 때 $(x_i-x_j)^2$ 가 더 작아지고,
$\sum_{i=1}^n x_i = 0$ 이므로 음수, 양수의 성분의 수가 비슷해집니다.

위와 같은 맥락으로 $(x_i-x_j)^2$ 의 합을 최소화 한다는 것은 cut 을 적게 만드는 의미도 포함합니다.
$x_i,x_j$ 가 다른 부호를 갖게 되면(cut), $(x_i-x_j)^2$ 이 커지게 되므로
최소화하는 것이 cut의 엣지도 줄어들게 만듭니다.

이 분할을 예시를 통해 확인해 봅시다.

다음과 같은 그래프가 주어졌고

이 그래프에 대한 라플라시안 행렬은 다음과 같습니다.

그리고 이 행렬의 고유값, 고유 벡터는 다음과 같습니다.

여기서 2번째로 가장 작은 고유값은 1 입니다.
두번째 고유벡터는 3개의 양수와 3개의 음수 성분을 갖습니다.
이 결과는 {1,2,3},{4,5,6} 으로 나누도록 합니다.

Alternative Partitioning Methods

앞선 내용에서 그래프를 작은 컷으로 2개의 조각으로 나누는 방법을 제시하였습니다.
고유벡터의 부호에 따라서 그래프를 나눴습니다.
하지만 꼭 부호를 사용해야하는 것은 아닙니다.
이전 예시에서는 임계값을 0 으로 사용했을 뿐, 다른 임의의 값을 사용해서 분할 할 수 있습니다.

위의 예시에서 임계값을 0이 아닌 -1.5 로 설정한다면, 4,6 노드는 1,2,3 그룹에 들어가게 됩니다.
5번 노드와 나머지 노드의 집합으로 분할되는 것입니다.
이 분할에서도 컷의 크기는 2입니다.(이전과 같습니다.)
대신, 두개의 집합의 크기에서 차이가 더 많이 생깁니다.
그래서 예시에서는 0으로 설정한 것입니다.

위 방법은 2개로 분할하는 방법에 대해서만 다뤘습니다.
이 방법을 기반으로 세 그룹 이상으로 나누는 기법은 2가지 방식이 있습니다.

Recursive bi-partitioning

이 방식은 2개로 나눠진 분할에서 계층적으로 각각 다시 분할을 하는 방식입니다.(recusive)
매 분할마다 새로운 고유벡터를 계산해야하므로 비효율적입니다.

Cluster multiple eigenvectors

이 방식은 2번째로 고유벡터 뿐 아니라 다른 고유벡터를 사용하여 분할하는 방식입니다.
만약 m 개의 고유값을 사용하고 각각 임계값을 설정하면,
$2^m$ 개의 그룹으로 분할 할 수 있습니다.
고유벡터 x 들이 이전 모든 벡터들과 직교한다는 제약으로 인해
뒤로 갈수록 성능이 약화되는 단점이 있지만
한번만 계산하면 되므로 주로 사용되는 기법입니다.