[CS224W] 5. Spectral Clustering

5강은 정민준님께서 리뷰하셨습니다. 4강에서는 네트워크에서 커뮤니티를 찾는 방법에 대해서 배웠습니다. 5강은 더 나아가서  네트워크 클러스터링에 대한 것입니다. 이를 위해서 선형대수(linear Algebra)개념을 사용해서 그래프를 처리해봅니다. 그리고 네트워크 모티프를 기반으로 클러스터링을 해봅니다.

목차

1. Spectral Clustering Algorithm
    - Spectral Clustering Algoritm
    - Spectral Partitioning Algoritm
2. Motif-Based Spectral Clustering

 

1. Spectral Clustering Algorithm

Spectral Clustering Algorithm은 3가지 단계로 이루어져 있습니다.

• 1) Pre-processing(전처리)
  • 그래프를 표현하는 matrix 생성
• 2) Decomposition(분해)
  • matrix의 eigenvalue와 eigenvector를 계산
  • eigenvalue와 eigenvector를 기반으로 저차원의 표현으로 mapping(low-dimensional representation)
• 3) Grouping
  • 새로운 representation을 기반으로 2개 이상의 cluster를 만들고 point들을 cluster에 할당

 

이 3가지 단계를 설명하기 위한 각 개념에 대해서 먼저 살펴보겠습니다. 

Graph Partitioning

왼쪽과 같이 Graph가 주어졌을 때, partition에 대한 다음과 같은 의문이 생깁니다. 

• 어떻게 graph G를 좋은 partition으로 나눌 것인가?
• 어떻게 효율적으로 partition을 정의할 것인가?

이 때 좋은 partition에 대한 정의는 그룹내 노드간의 연결을 최대화하면서 그룹간 연결을 최소화시키는 것입니다. 

 

Graph Cuts

 

 

 

 

 

얼마나 잘 분리시키는지(Edge Cut) 알기 위해서 'Cut' 이라는 목적함수를 정의합니다.

 

• Cut : 각 그룹에서 end point가 있는 edge들의 집합 (그림이 이해가 쉽습니다.)
  • 두 네트워크를 연결하고 있는 edge의 수, 1+1 = 2 입니다. 
• Criterion : Minimum-Cut
  • 그룹들 간의 연결성 weight를 최소화 시킴
  • cluster 바깥의 연결에만 주목하고, 내부적인 것은 고려하지 않는 문제점이 있음 -> Conductance로 해결
• Criterion : Conductance
  • 군집 내부의 연결성도 고려, 군집의 밀도를 반영
  • 두 그룹간의 밀도는 상대적이기 때문에(큰 그룹이 있고, 작은 그룹이 있을 수 있음) cut을 volum으로 나눠서 구함
  • edge cut이 작고 min(vol(A), vol(B))의 값이 커진다면, 작은 Conductance 얻을 수 있음
  • 더 균형을 갖춘 partition들을 만들 수 있음
  • best Conductance를 찾을 때, NP-Hard 문제가 있음 <- 쌍대비교를 해야하기 때문에

따라서 NP-hard 해결을 위해 고유값과 고유벡터를 얻어서 Conductance를 최소화 시키는 방법에 대해서 알아보겠습니다.

 

Spectral Graph Partitioning

그래프 G 에는 인접행렬 A가 있습니다. 이 때 x는 n차원 공간의 component로 이루어진 벡터 입니다.

• A : adjacency matrix of undirected G
  • A_ij = 1 or 0 (연결되어 있으면 1)
• x is a vector in R^n with components (x_1, ...,x_n)
  • 각 노드을의 label이나 value 값

 

결국 A · X 의 뜻은 뭘까요? ->  A · X 의 선형변환은 노드 i의 이웃인 x_j의 label의 합 입니다.

• y_i => i의 neighbors 인 x_j의 label 합
• A·X 의 j 번째 요소는 j의 이웃의 x-value 합이며, node j 에 대해 새로운 x-value 값을 만들었습니다. 
• Spectral Graph Theory는 이처럼 matrix representing G 의 Spectrum 을 분석하는 방법입니다.
  • Spectrum : 그래프의 eigenvectors x(i)는 eigenvalues lambda(i)의 크기 순으로 정렬됩니다. (오름차 순)

 

Example: d-Regular Graph를 예시로 보겠습니다. 

 

• d-regular graph : 모든 노드가 동일하게 차수 d를 가지는 그래프 G
• What are some eigenvalues / vectors of G?
  • A · x = lambda · x 에서 lambda 와 x 는 무엇일까?
  • x = (1,1,...,1) 일 때를 보면, A · x = (d,d,...,d) = lambda · x 이다.
  • 따라서 lambda = d 이다
• A의 가장 큰 eigenvalue는 d 이며, A = n x n 행렬일때 n개의 eigenpairs가 나오게 됩니다.

 

Eigenvector와 Eigenvalue에 대한 기본 개념이 헷갈리신다면, 블로그의 다른 포스팅인 linear algebra 관련 글을 참고 부탁드립니다.

2021/02/12 - [[ Today I Learned ]/Linear algebra] - [선형대수] 고유값과 고유벡터 (eigenvector & eigenvalue)

[선형대수] 고유값과 고유벡터 (eigenvector & eigenvalue)

 

그래프 G가 위와 같이 C vs B 로 나뉘는 경우를 가정한다면, 다음과 같은 특징들이 있다고 합니다. (eigenvector의 orthogonal함 이용, 증명 생략)

-> 0을 기준으로 양수이면 C그룹이고, 음수이면 B그룹으로 볼 수 있음

 

 

 

 

 

 

 

 

Matrix Representations

이제 matrix representation 방법들에 대해서 보겠습니다. 여기서는 크게 3가지가 있습니다.

• Adjacency matrix (A)
• Degree matrix (D)
• Laplacian matrix (L)

이 때 Laplacian matrix 는 L = D - A로 표현할 수 있습니다.

• Ax = lambda x 에서 x=(1,,,1)인 경우는 Lx = 0이 되고 lambda=0인 trivial 해 같게 됨.
• Eigenvalue 는 음이 아닌 실수
• Eigenvector는 실수이며 항상 orthogonal 함

 

---

 

Laplacian Matrix -> lambda2 -> finding optimal cut

 

 

lambda2 에 대한 정의는 M이 대칭행렬이라고 할 때, 왼쪽과 같이 표현됩니다. 

그렇다면 그래프 G에서 x.T Lx 의 의미는 뭘까요? laplacial의 성질을 이용해서 식을 변환하면 x_i와 x_j의 차이를 제곱한 값의 합이 됩니다. 

(lambda2 공식에 대한 증명은 생략합니다.)

 

 

이제 lambda 에 대한 공식은 왼쪽과 같이 나타낼 수 있습니다. 

 

 

 

우리는 궁극적으로 균형있게 Partitioning하기 위해서 lambda2의 값을 찾아 왔던 것입니다. 최적의 cut을 찾는 문제는 두 노드간의 차이를 최소화하는 y를 찾는 문제로 바뀌는데, 이는 정확하게 해를 찾기는 어렵고 레일리 정리를 통해서 도출합니다. 

결국 레일리 이론에 따르면

노드간의 차 (y_i - y_j)^2 을 최소화 시켜야 최적의 cut을 찾을 수 있는데 laplacian matrix L의 lambda2가 저 f(y)의 최소값이 되고, 최소화하는 벡터 y는 eigenvector(x)가 됩니다.

lambda2와 eigenvector를 이용한 클러스터링이 conductance(cut criterion)을 최소화하는 것을 입증한다고 합니다.  

---

정리

Spectral Partitioning Algorithm을 한줄요약 해보면 다음과 같습니다. 

- 어떻게 그래프의 good partition을 정의할 수 있을까? 
->  주어진 그래프의 cut criterion을 최소화해서

- 어떻게 partition의 효율적인 구분이 가능할까?
-> 그래프의 eigenvalue와 eigenvector를 구해서 근사된 정보를 사용한다. 

- Spectral Clustering

 

다시 Spectral Partitioning Algorithm을 그림으로 보면 다음과 같습니다.

다음과 같이 고차원의 인접행렬을 고유벡터와 고유값으로 저차원의 행렬로 매핑시켜버린 후에, 양수와 음수를 나눠서 clustering 해버렸습니다.

 

네트워크에 대한 예시들을 봅시다.

네트워크들은 오른쪽과 같이 plot 한 그래프로 나타낼 수 있으며, component에 따라서 잘 구분될 수도 있고, 아닐 수도 있습니다. (제일 마지막 비교 참고)

-> 따라서 k개의 클러스터를 찾는 것에 대해서는 다양한 접근이 있고, 최적의 k를 찾는 것은 eigengap 의 최대화 하는 지점으로 찾습니다. (클러스터링에서 최적의 k를 찾는 것과 동일)

 

---

2. Motif-Based Spectral Clustering

이전 시간에 배운 motif를 기준으로 clustering 할 수는 없을까? 에 대해서 알아봅시다.

based motif를 어떻게 정하는지에 따라서 클러스터링도 달라짐 -> 모티프를 기반으로 네트워크를 클러스터링 할 수 있는가?

 

이전에는 edge를 기준으로 cut과 기준을 설정했다면, 이번에는 motif를 기준으로 cut을 설정합니다. 주의할 점은 vol(S)가 S에서 모티프의 end point 갯수라는 점입니다.) 오른쪽의 그림을 보면 쉽게 ⏀(S)를 이해할 수 있습니다. 

따라서 motif의 cluster를 찾기 위해서 motif conductance(⏀)를 최소화하는 nodes S 집합을 찾으면 되는데, S를 찾는 것 또한 NP-hard 문제가 있습니다. -> 하지만 일반화할 수가 있습니다. 이전에 배운 Spectral Clustering Algorithm을 사용해봅시다. 

 

동일하게 Spectral Clustering을 진행하면 되는데,

input으로 그래프 G와 모티프 M을 넣고 -> G를 이용해서 새로운 weighed graph W를 만들어서 사용합니다. -> W에 Spectral clustering을 진행해서 -> output으로 cluster가 나옵니다. 

이 cluster 결과가 거의 최적의 motif conductance를 포함한다고 합니다. 

 

Motif Spectral Clustering

1. 주어진 그래프G 에서 motif M이 나타나는 edge의 수로 wighted graph W를 만듭니다.

 

 

2. Spectral clustering을 적용합니다. W에 대해서 Laplacian을 구해서 eigenvector와 eigenvalue(정확히는 Lambda2 값)을 찾습니다. 

 

 

3. x 값을 sort 해서 plot한다. x축을 각 S 집합으로 두고 y축을 motif conductance로 둬서 conductance를 최소화하는 값을 찾는다. 멈출 위치를 정하려면 결국 휴리스틱한 접근을 해야한다. (위의 예시가 아주 잘 나온 경우라고 한다.)

 

 

4. 결과는 아래의 공식을 따릅니다. 알고리즘으로 찾은 motif conductance가 거의 최적의 값입니다. (near optimal)

 

정리

- Community detection 을 higher-order structure로 일반화 가능하다. (Generalization of community detection to higher-order structures)

- Motif-conductance는 motif Cheeger 불평등을 인정한다. (Motif-conductance objective admits a motif Cheeger inequality) -> cheeger constant에 부합하다. -> 기존의 graph theory에 부합한다.
https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)

Cheeger constant (graph theory)

 

 

Example 

예시로 다음과 같은 먹이 그물 네트워크를 들 수 있다. 각 노드들은 환경시스템의 종이고, edge는 누구를 잡아 먹는가(carbon exchange)이다. 다른 모양의 motif들이 있다고 가정한다. (M5, M6m M8) 

어떤 motif 가 먹이 그물을 잘 설명하는지 보면 다음과 같다. 

 

 

각 모티브들과 motif-conductance는 다음과 같이 나타난다. M6 이 cunductance를 가장 최소로 만드는 지점을 가지며, goot cut을 가지고 있다.

-> 따라서 motif M6을 기준으로 cut을 설정해서 community를 잘 구분할 수 있다. 

 

 

 

 

Reference

Stanford CS224W 2019
스터디 5강 리뷰 자료 velog.io/@tobigs-gnn1213/5.-Spectral-Clustering

5. Spectral Clustering