라플라시안 메트릭스 / Laplacian Matrix

   Graph 기반의 Collaborative Filtering의 논문을 읽다가, Graph Laplacian norm을 접하게 되었다. 무엇인지에 대해서 하나씩 찾아보다가, 라플라시안 메트릭스부터 차근차근히 정리하기로 했다. 

   먼저, 그래프에 있는 노드들을 비슷한 것끼리 클러스터링할 때 혹은 그래프를 나눌 때, 라플라시안 메트릭스가 활용된다. 그래프로 표현된 N개의 점들 사이의 유사성이 주어졌다면, 유사성 매트릭스를 통해서 클러스터링 하면 된다. 하지만, N개의 점들만 주어졌을 때에는 점들의 유사성을 따로 구해 유사 그래프를 생성해야 한다. 유사 그래프를 생성시에, 인접 행렬(Adjacency matrix)과 라플라시안(Laplacian matrix)이 활용된다. 인접 행렬 매트릭스는 노드로 표현될 수 있는 각 점들 사이에 존재하는 엣지를 나타내는 행렬이다. 

   라플라시안 메트릭스(Unnormalized Laplacian matrix)는 각각의 노드가 주변 이웃을 얼마만큼 가지고 있는지에 대한 정보값을 가지고 있는 D 대각차수행렬(degree matrix)에서 W 인접행렬 메트릭스(Adjacency matrix)를 뺀 값과 같다. L = D - W

출처; https://en.wikipedia.org/wiki/Laplacian_matrix

   라플라시안 메트릭스의 특징은 다음과 같다. 1) 대각 성분을 중심으로 양 값이 대칭적이며(Symmetric) 2) 대각요소 성분을 제외하고 음의 값을 가지고 있으며 (Non-positive off-diagonals) 3) 주 대각성분의 값이 행의 다른 값보다 크거나 같다 - 대각지배행렬(Diagonally dominant)이다. 

   Graph Laplacian Norm의 경우, 정규화된 라플라시안 메트릭스의 값이다. 정규화된 라플라시안 메트릭스(normalized Laplacian matrix)는 다음과 같은 식으로 구해질 수 있다. 

출처; https://en.wikipedia.org/wiki/Laplacian_matrix

 

   많은 논문에서 아래의 표현이 Graph Laplacian Norm으로 사용되고 있다. 아래의 표현 식으로 유저와 아이템을 그래프 상의 노드로 표현하는데 있어서 유저의 선호도를 학습할 때 한 번의 엣지 연결로 연결된 주변 유저 혹은 아이템 노드들의 입베딩 취합의 결과를 정규화하게 된다(graph Laplacian norm to normalize the embeddings aggregated from previous layer, where Nu and Ni respectively denote's u's and i's neighborhood). 정규화된 라플라시안 메트릭스로부터의 norm임을 인지하고도, Nu와 Ni의 norm값을 곱하여 루트씌운 값이라는 게 이해가 안 갔는데, 논문을 반복해서 읽은 결과, Graph에 CF matrix표현 시, 유저와 아이템을 붙여 하나의 메트릭스로 동일한 공간에서 학습시키기 때문으로 이해했다. 

    한편, 라플라시안 메트릭스를 통해서, 원래의 d차원의 점들이 라플라시안 메트릭스의 각각의 가장 작은 고유값들에(사용자가 임의로 자를 수 있는) 대응되는 고유벡터로 나타내질 수 있다. 한편, x의 성분이 모두 1인 아이젠 벡터의 값에 대해서 아이젠벨류의 모든 값은 0으로 같다. 

출처 ; www.slideshare.net/JeonghunYoon/08-spectal-clustering, https://www.youtube.com/watch?v=Nv3EaRL60ww

08. spectal clustering