Chapter5. Spectral Clustering
투빅스 12기 박진혁
PreviousChapter4. Community Structure in NetworksNextChapter6. Message Passing and Node Classification
Last updated
투빅스 12기 박진혁
Last updated
1)Pre-processing
2)Decomposition(분해)
3)Grouping
Bi-Partitioning : 말 그대로 그래프를 두 개로 쪼개는 것! 그렇다면 우리는 어떻게 그래프를 쪼개야 그래프를 잘 쪼갰다고 할 수 있고 또 그렇게 쪼개기 위해서는 어떻게 해야할까?
좋은 partitioning : 그룹 내에 connection은 많지만, 그릅 끼리의 connection은 최소화 되는 것
먼저 Cut이라는 개념을 알아보자
Cut : 어떤 Group에서 다른 Group으로 가는 Edge (정의는 endo point라는 개념을 쓰기는 하지만 실제 식을 보면, A와 B 모든 그룹에 속한 Edge의 weight의 합으로 정의된다)
그렇다면 Cut은 어떤 것을 기준으로 하면 될까?
Minimum Cut : 그냥 weight가 가장 작은 것을 기준으로 그룹을 쪼갠다 . 딱봐도 좋지 못한 방법이다
Conductance : A와 B의 Volume 중 더 작은 볼륨(특정 그룹내에 있는 모든 weighted degree의 합)을 나눠줌으로써, Minimum Cut의 문제를 방지할 수 있음
그렇다면 Partitioning은 어떻게 해야할까? 스포일러를 하자면 Eigen Decomposition을 이용한다. 여기까지 가기는 과정이 많으므로 일단 우리는 Partitioning의 방법을 찾고있다는 아이디어만 가지고 넘어가자.
어떤 그래프에 대한 인접행렬 A가 있다고 가정하자. 그리고 n개의 성분을 가진 x라는 벡터가 있다고 가정하자. 그렇다면 A*x는 무슨 의미를 가질까?
딱 직관적으로 생각을 해보면, X1 X2 X3 등을 어떤 노드의 어떤 값이라고 하자. 그러면 Yn은 n번째 노드와 연결된 Edge의 X값의 합 이라고 생각할 수 있다.
다음 그림1 을 보
이걸 만족 시키는 것은 무엇일까? 정의적으로 봤을 때 여기서 X벡터는 인접 행렬의 Eigen Vector라고 할 수 있다.
예시) 우리는 모든 node가 d의 degree를 가지고 있다고 가정하자. 이 때 벡터 X를 (1,1,1,1,1,1,1...)이라고 하면 A * x = (d,d,d,d,d,d,d,d,...) 와 같은 형태를 띄게 될 것이다. 왜냐하면 A의 각 행은 인접한 node와 연결된 edge의 개수이고 각 행의 합은 d가 될 것이기 때문이다. 즉, 우리는 x = (1,1,1,1,1,....)이 eigenvector, d가 eigenvalue라고 생각할 수 있다.
이 때
1) eigenvalue d는 이 행렬의 eigen vector중 가장 큰 값이다.
2) eigen value d에 대응하는 eigen-vector는 오직 하나로 결정된다. (증명은 생략)
예시를 하나 더 들어주셨는데.. 어떤 두 가지 완전히 분리된 Component가 있으면 여기서 두 번째로 큰 eigen value에 대응되는 eigen vector가 양수인 node와 음수인 node에 따라서 두 component를 구분할 수 있다고 합니다. 저는 이게 별로 clear하게 느껴지지는 않네요 ㅠㅠ
우리는 여기서 Laplacian Matrix라는 것을 정의합니다.
L = D - A라고 정의를 하는데 D는 Degree Matrix, A는 Adjacency matrix를 나타냅니다. 이 matrix는
1) symmetric 하고
2)n개(node의 개수)의 eigen values를 가지고 있으며
3)모든 eigenvetor가 real하고 Orthogonal합니다(근데 eigen vector는 무조건 orthogonal아닌가요..?)
증명은 슬라이드에 나와있습니다. 그리고 여기서 제가 추가로 하나 더 말씀 드리고 싶은것은 모든 행의 합이 0이라는 겁니다
자 이 때, 어떤 symmetric한 matrix가 있다고 하면, 이 것의 labmda2를 찾는데 더 집중하고 거기서 많은 property를 찾을 수 있을 것이다!!
Lambda2 Problem
우리는 lambda2를 찾는 문제를 다음과 같이 변형할 수 있다. 이건 eigen value 정의에 의해서 생기는 것! (M은 symmetric matrix라고 하면)
w1(lambda1에 대응되는 eigenvector)와 수직이여야 하면서 x^T*M*x/M^T*x 의 값을 최소화 하는 vector X는 eigen vecotr이고 이 때 x^T*M*x/M^T*x 값을 lambda2라고 할 수 있습니다.
-> 그냥 이건 '대칭행렬의 성질'이라고 생각을 해 둡시다. 궁금하면 Spectral Decomposition을 검색해보세요!
그런데, X^T*L*X를 하고 이 때 L을 Laplacian Matrix로 둔다면 이 계산 결과는
과 같게 됩니다. (증명은 간단합니다. 그냥 전개만 하면 돼요)
우리는 X를 unit vector로 두겠습니다. (eigen vector는 상수배해도 성질이 그대로 남아있기 때문에 unit vector로 둬도 괜찮습니다) 이 두개를 결합하면 위 식은 다음과 같이 변하게 됩니다.
그런데 X는 unit vector이므로, 분모는 1이 되겠죠? 여기까지만 일단 알고 넘어갑시다
그런데.. 우리 원래 목표가 A랑 B를 나누는 가장 좋은 방법을 찾고 있었죠? 우리는 어떤 Vector yi를 다음과 같이 정의합시다. A에 있는 node를 +1, B에있는 node를 -1 이라고 둡시다
그러면 좋은 Cut을 찾는 문제는 다음과 같이 바뀌게 됩니다. 왜냐! A끼리 있는 edge는 어차피 1 -1 = 0 B끼리 있는 edge도 0, 그러니까 A와 B를 cross하는 Edge를 찾는 것과 같습니다.
결국 이것을 정리한 레일리 이론에 따르면 저 위에 나와있는 (yi-yj)^2를 최소화시키는 y는 laplacian matrix L에대해 lambda2는 저 f(y)의 최소값이 되고, 저것을 최소화 하는 벡터y는 그에 해당하는 eigen vector가 됩니다. 그리고 이러한 lambda2와 이에 해당하는 eigen vector에 해당하는 값을 이용한 클러스터링은 conductance를 최소화하는 것도 입증한다고 합니다.
그렇다면 이것을 가지고 어떻게 Partitioning을 할까?
저렇게 찾은 lambda2에 해당하는 eigen vector의 각 값들을 나열했을 때, median값 (보통0일거에요)을 기준으로 잘라서 node를 나누면 됩니다. 즉 (-0.1,0.2,-0.3,0.4...)와 같은 형태가 있다면 -0.1, -0.3에 해당하는 1,3번 node는 그룹 A 0.2, 0.4에 해당하는 2,4번 node는 그룹 B에 배치하면 되는 것입니다. 여러개가 나와도 마찬가지에요 값을 기준으로 자르면됩니다.
그런데 lambda1, lambda3는 어떤 의미 일까요? 아까 lambda1은 하나의 연결된 Component라면 다 똑같은 값(1,1,1,1,1,1,1,1,1,1..)등등이라고 했죠? 그리고 떨어져있다면? (1,1,1,1,1,0,0,0,0)이런 의미이구요. 그러니까 이것도 어떻게 보면 하나의 가장 큰 Clustering이라고 볼 수 있습니다. X3는 X2에서 급변하는 점을 기준으로 음양이 새로 나뉘는 걸로 봐서는 이것도 하나의 Cluster의 기준으로 쓸 수 있겠네요!
그리고 eigen value는 다음과 같은 의미도 가지고 있습니다.
이 그림을 다시 떠올려보면, k개의 connected component의 경우는 저 x'과 x''같은 것들이 k개 존재햐아한다는 것을 알 수 있습니다.
루스코벡 강의에서는 Eigen Gap으로 클러스터링 하는 경우만 나왔지만 실제로는 다양한 partitioning방법이 존재합니다.
출처 : https://users.ics.aalto.fi/gionis/biss2016-lec5.pdf
Motif-Based Spectral Clustering
Motif 들을 이용해 클러스를 형성하게 됩니다.
우리는 Motif를 Base로 클러스터링을 할 때 위에서 정의했던 Volume과 Cut의 정의를 바꿀 수 있습니다. 여기서 헷갈리지 말아야 할 것은 Vol은 Motif의 갯수가 아니라, Motif의 End Point의 개수라는 점입니다.
사실 여기서는 전처리만 다시 해주면 같습니다.
바로 해당 edge가 주어진 motif를 형성하는데 몇 개가 관여되는지를 쓰면 되기 때문입니다. 즉 각 edge간 weight를 참여하고 있는 Motif의 수로 정하고 똑같은 방식으로 Decomposition을 해주면 됩니다. 그 이후, eigen vector에 대응되는 값으로부터 작은 것을 순서대로 자르면서 Conductance를 계산해서 이상적인 Cut을 정해주면 됩니다.
또 이렇게 찾은 Set의 Conductance는
Optimal에 대해 다음과 같음을 보장합니다. 꽤나 효율적인 것을 알 수 있죠.
그렇다면 이런 Motif Clustering 어떤 Application이 있을까요? 해양 생물의 포식구조가 다음과 같이 돼있다고 가정합시다. 그러면 M6의 경우 공통된 하나의 생물을 잡아먹고, 그 잡아먹는 아이들끼리도 서로를 잡아먹는 구조라고 생각할 수 있습니다.
각각의 모티프를 가지고 아까와 같은 알고리즘을 돌리면
와 같은 결과가 나오고 이 때 이상적인 Conductance를 가진 M6를 이용해서 Clustering을 하면 가장 이상적인 바다속 구조를 얻을 수 있게 됩니다.
