ㅎㅅㅎ
로그인
ㅎㅅㅎ
로그인
[1][GNN][GCN] Laplacian matrix
홍성환
·
2022년 1월 27일
팔로우
3
3
1. Intro
주어진 그래프를 spectral 도메인으로 해석하는데 laplacian matrix를 사용한다.
laplacian matrix가 무엇이길래, graph를 표현하는데 쓰이는걸까?
laplacian matrix의 의미에 대해 알아보자.
2. laplacian matrix란?
2-1 Adjacaemcy matrix
Adjacaemcy matrix는 그래프의 연결관계를 표현한 행렬이다.
위에서 처럼 두 노드(i,j)가 연결되어 있으면
A
i
j
=
1
A_{ij}=1
A
i
j
=
1
로 아니면
A
i
j
=
0
A_{ij}=0
A
i
j
=
0
이 되는 행렬이다.
2-2 Degree matrix
Degree matrix는 한 노드에 연결된 엣지의 개수이다.
2-3 laplacian matrix
laplacian matrix는 Degree matrix - Adjacaemcy matrix로 정의된다.
L
=
D
−
A
L = D-A
L
=
D
−
A
L
L
L
:
Laplacian matrix
D
D
D
:
Degree matrix
A
A
A
:
Adjacaemcy matrix
3. Smoothness
laplacian matrix는 graph의 smoothness를 측정할 수 있다.
이게 무슨말일까?
laplacian matrix(
L
L
L
)가 아래 처럼 주어졌다고 생각해보자.
이때 각 노드의 값을 (v1, v2, v3, v4) =
x
x
x
로 표현해보자.
그러면
L
x
Lx
L
x
는 다음과 같이 된다.
위와 같은 과정으로 인해
L
x
Lx
L
x
는 각
노드가 이웃노드와 얼마나 차이가 나는지
측정하게 된다.
x
T
L
x
x^TLx
x
T
L
x
는 여기서 아래와 같이 된다.
즉
x
T
L
x
x^TLx
x
T
L
x
는 각 노드와 이웃노드 사이의 차이 제곱의 합이 된다.
만약 이웃노드끼리 값이 비슷하다면
x
T
L
x
x^TLx
x
T
L
x
는 값이 작을 것이다.
만약 이웃노드이지만 값이 크게 다르다면
x
T
L
x
x^TLx
x
T
L
x
는 값이 클 것이다.
이러한 성질로인해
laplacian matrix는 smoothness를 측정할 수 있다.
4. eigenvalue decomposition
Lapalacian matrix는 대각성분으로 기준으로 좌우가 대칭이여서 Positive semi-definite matrix이고 성질로 인해 모든 고유값이 실수이다.
(eigenvalue decomposition이 뭔지 잘 모른다면 10시간정도는 들여서 따로 공부하는 것이 좋을 것 같다.)
따라서 다음과 같은 고유값 분해가 가능하다.
L
=
U
Λ
U
T
L = U\Lambda U^T
L
=
U
Λ
U
T
라플라시안 matrix의 eigenvalue가 작을수록 그래프에 대한 의미를 많이 가지고 있을 수 있다.
이어지는 다음글에서 laplacian matrix의 eigenvalue의 의미와 eigenvector를 활용한 graph의 spectral representation에 대해서 알아보자..
홍성환
Machine Learning Engineer: recsys, mlops
팔로우
이전 포스트
관측데이터로 인과 관계 파악이 가능할까? [Confounder, Collider]
다음 포스트
[Inverse Sampling] 컴퓨터는 정규분포를 어떻게 만들어낼까?
1개의 댓글
댓글 작성
김채란
2024년 4월 16일
글 잘 읽었습니다!
이어지는 다음 글은 어디서 확인할 수 있나요?
답글 달기
글 잘 읽었습니다!
이어지는 다음 글은 어디서 확인할 수 있나요?