그래프 머신러닝: (2-3) 그래프 라플라시안과 스펙트럴 방법

(GRL) Background and Traditional Approaches: Graph Laplacians and Spectral Methods

graph
network
machine learning
spectral
Author

Cheonghyo Cho

Hamilton,W.L. Graph Representation Learning. 2020

그래프 라플라시안과 스펙트럼 방법

Graph Laplacians and Spectral Methods

그래프 데이터로 노드 분류 작업에 유용한 피쳐와 관계예측을 위한 방법을 이전의 두 포스트 (1) (2)에서 확인했다.

이제 그래프에서 노드들을 클러스터하는 법에 대해 다루어보자. 또한 노드의 저차원 임베딩에 대해 다룬다.

Graph Laplacians

인접 행렬의 다양한 변형으로 나타내며 유용한 수학적 속성들을 가진다.

Unnormalized Laplacian

가장 기본적인 라플라시안(Laplacian) 행렬

\[L=D-A\]

  • \(A\)는 인접 행렬, \(D\)는 degree 행렬
  • 라플라시안 행렬의 속성
    • symmetric, positive semi-definite
    • \(\forall \mathbf{x} \in \mathbb{R}^{|\mathcal{V}|}\) , \(\mathbf{x}^{\top}L\mathbf{x} = \sum_{(u,v)\in \mathcal{E}}(\mathbf{x}[u]-\mathbf{x}[v])^2\)
    • \(L\)은 \(|V|\)개의 비음수 eigenvalue를 가짐

Normalized Laplacian

대칭 라플라시안:

\[L_{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\]

랜덤워크 라플라시안:

\[L_{RW}=D^{-1}L\]

Graph Cuts and Clustering

fully connected 그래프에서 라플라시안이 노드의 최적 클러스터링을 하는데 사용되는 방법을 알아보자.

graph cuts

\(\mathcal{A} \subset \mathcal{V}\)은 그래프의 노드의 부분집합을 나타내고 \(\bar{\mathcal{A}}\)은 이 집합의 여집합이라고 하자.

그래프를 \(K\)개 중복되지 않는 부분집합으로 나누면(파티셔닝) ’cut value’를 다음과 같이 정의할 수 있다:

\[\text{cut}(\mathcal{A}_1, \dots, \mathcal{A}_K) = \frac{1}{2}\sum^{K}_{k=1}|(u,v) \in \mathcal{E} : u \in \mathcal{A}_k, v \in \bar{\mathcal{A}}_k|\]

  • cut은 노드 파티션 사이 경계에 엣지의 개수를 나타낸다.
  • 노드를 \(K\)개 클러스터로 나누는 최적 방법은 이 cut value를 최소화하는 파티션을 결정하는 것이다.
  • 하지만 이 경우 하나의 노드로 구성된 클러스터를 만드는 경향이 있다.

대신 파티션의 크기를 적당히 크게 하면서 cut을 최소화하는 방법을 사용한다:

\[\text{RatioCut}(\mathcal{A}_1, \dots, \mathcal{A}_K) = \frac{1}{2} \frac{\sum^{K}_{k=1}|(u,v) \in \mathcal{E} : u \in \mathcal{A}_k, v \in \bar{\mathcal{A}}_k|}{{|\mathcal{A}}_k|}\],

\[\text{NormalizedCut}(\mathcal{A}_1, \dots, \mathcal{A}_K) = \frac{1}{2} \frac{\sum^{K}_{k=1}|(u,v) \in \mathcal{E} : u \in \mathcal{A}_k, v \in \bar{\mathcal{A}}_k|}{\text{vol}(\mathcal{A}_k)}\] where \(\text{vol}(\mathcal{A}_k) = \sum_{u \in \mathcal{A}} d_u\)

Approximating the RatioCut with the Laplacian Spectrum

라플라시안 스펙트럼(Laplacian spectrum)을 사용하여 RatioCut을 최소화시키는 방법을 도출해보자. \(K=2\)인 경우를 보자.

\[\min_{\mathcal{A} \in \mathcal{V}}\text{RatioCut}(\mathcal{A}, \bar{\mathcal{A}}) \]

벡터 \(\mathbf{a}\in \mathbb{R}^{|\mathcal{V}|}\)를 다음과 같이 정의한다.

\[\mathbf{a}[u] = \begin{cases} \sqrt{\frac{|\bar{\mathcal{A}}|}{|\mathcal{A}|}} \quad \text{if} \ u \in \mathcal{A}\\ - \sqrt{\frac{|\mathcal{A}|}{|\bar{\mathcal{A}}|}} \quad \text{if} \ u \in \bar{\mathcal{A}} \end{cases}\]

그래프 라플라시안의 속성을 이용하면,

\[\mathbf{a}^{\top}L\mathbf{a}=\sum_{(u,v) \in \mathcal{E}}(\mathbf{a}[u]-\mathbf{a}[v])^2\\ =\cdots^{\text{*}} \\ =|\mathcal{V}|\text{RatioCut}(\mathcal{A},\bar{\mathcal{A}})\]

  • *(중간 단계는 생략)

또한 \(\mathbf{a}\)의 속성인 \(\mathbf{a} \perp \mathbf{1}\) 그리고 \({\parallel\mathbf{a}\parallel}^2 = |\mathcal{V}|\)을 고려,

\[\min_{\mathbf{a} \in \mathbb{R}^{|\mathcal{V}|}}\mathbf{a}^{\top}L\mathbf{a} \quad s.t. \quad \mathbf{a} \perp \mathbf{1},\ {\parallel\mathbf{a}\parallel}^2 = |\mathcal{V}|\]

벡터 a를 라플라시안 행렬의 두번째로 작은 eigenvector로 설정하여 RatioCut 최소화를 근사할 수 있다. 다음 \(\mathbf{a}[u]\)의 부호로 클러스터링을 할 수 있다.

즉, 라플라시안의 두번째로 작은 eigenvector는 최적 클러스터를 (RatioCut에 대해) 수행하는 이산(discrete) 벡터에 연속적 근사치이다.

Generalized Spectral Clustering

위에서 라플라시안의 스펙트럼을 이용하여 그래프를 두 클러스터로 나누는 방법에 대해 알 수 있었다.이제 일반화시켜 \(K\)개 클러스터링을 해보자.

  1. \(K\)개의 최소 \(L\) eigenvector들을 찾는다(단, 가장 작은 eigenvector 제외): \(\mathbf{e}_{|\mathcal{V}|-1},\mathbf{e}_{|\mathcal{V}|-2},\cdots,\mathbf{e}_{|\mathcal{V}|-K}\)

  2. 이 eigenvetor를 행으로 하여 행렬 \(U \in \mathbb{R}^{|\mathcal{V}| \times (K-1)}\)를 형성한다.

  3. \(U\)에 있는 각 노드를 대응하는 열로 표현한다: \(\mathbf{z}_u = U[u] \quad \forall u \in \mathcal{V}\)

  4. 임베딩(embedding) \(\mathbf{z}_u\)에 K-means 클러스터링을 돌린다.

스펙트럼 클러스터링의 일반적인 원리는 강력하다. 그래프 라플라시안의 스펙트럼을 사용하여 노드를 그래프로 표현할 수 있으며, 이 표현은 최적의 그래프 클러스터링에 대한 원칙적 근사로 볼 수 있다.

참고자료

[1] Hamilton, W. L. (2020). Graph Representation Learning. Morgan & Claypool Publishers.