그래프와 인접 행렬, 라플라시안 행렬(Adjacent matrix, Laplacian matrix)

 머신러닝을 처음 공부하면, 대개 테이블로 구성된, 이미 예쁘게 정돈된, Pandas로 읽어내려 사용만 하면 되는 그런 데이터들을 접하게 됩니다. 이런 데이터를 몇 번 다루다, 이후에는 이미지 또는 자연어를 접해요. 이미지는 사실 그 자체로는 여태 보던 테이블과는 달라서, 이걸 여러 색상 포맷에 맞게끔 조작해서, 최종적으로는 행렬로 만들어 다루게 되요. 자연어도 똑같이, 어떤 문장 데이터가 있으면, 이걸 자기가 다루기 편하게 행렬로 예쁘장하게 변환하구요. 이렇게 내 용도에 맞게 약간의 조작을 거쳐야하는 데이터 타입 중 하나가 그래프인 것 같아요.

 위 그림과 같은 데이터가 그래프 데이터의 예시입니다. 단순하게, 그냥 노드(Node, Vertex)와 엣지(Edge)를 가지기만 하면되요. 여기에 추가로 Node weight, Edge weight, Directionality 등을 가질 수도 있겠죠. 위 그림의 노드와 엣지가 각각 무엇을 의미하는지는, 저도 모르겠습니다만, 저런 형태를 띄는 데이터가 어떤게 있을 수 있을지 생각해보면, 뭐 어떤 지역의 도로 연결 상황? 벤젠 같은 물질의 화학식을 시각화한 것? 인터넷 네트워크 연결 상황? 어떤 사람들끼리의 인맥 정보? 이런 식으로 여러 실용적인 상황을 잘 표현할 수 있겠습니다. 다만 문제는, 앞서 말한 것 처럼, 그래프는 결국 노드와 엣지로 저장되는데, 그 파일을 열어보면 노드 = (Node1, Node2, Node3, Node4, ...), 엣지 = ((Node1, Node2), (Node1, Node3), (Node2, Node3), ...) 이런 식인데 이게 영 알아보기가 힘들어요. 

 게다가 저희는 앞에서 맨날 행렬하나 딱 만들어놓고 그걸 지지고 볶고 했는데, 노드 따로, 엣지 따로, Weight 혹은 Directionality 정보도 붙어있으면 이것도 처리해줘야하는데, 영 익숙하지도 않고, 계산도 어렵고 한거지요. 그래서 이걸 하나의 행렬로 뙇 정리할 방법이 필요한건데, 그게 바로 인접 행렬(Adjacent matrix)입니다. 라플라시안 행렬(Laplacian matrix)도 무서워보이는 이름과는 달리 인접 행렬에 특정 정보를 더 담으려 조금 꼼지락 거린 것 밖에 되지 않습니다.

 그래서 인접 행렬이 뭐냐? 총 노드의 개수를 N이라고 하면, 일단 N x N 인접 행렬 A을 만들어 줄거에요. 이 때, A의 (i,j) 성분이 의미하는 바는, Node_i, Node_j가 연결이 되어 있니~ 마니~ 하는 정보입니다. 방향성도 있고, 가중치도 있는 그래프라면 그에 맞게끔 조오금 수정하면되겠지요. 이렇게 구성한 인접 행렬의 i-th row는 Node_i에 대한 정보를 담게 되는 셈입니다. 아래 그림은 위키피디아에서 가져온 그림인데, 저걸 이해하시면 충분합니다.

 위 그림을 보면 못보던 행렬이 하나 더 껴있습니다.  Degree matrix란 놈인데, 이 친구는 각 대각 행렬을 제외하고는 다 0을 가집니다. 진짜 어떤 노드의 차수(Degree) 정보만을 표현하는 행렬인 셈이에요. 예를 들어, (1,1) 성분은 Node_1의 Degree가 입력되어 있습니다. 1의 이웃이 2와 5니까 맞는 말이네요.

 차수 행렬과 인접 행렬을 이해했으면, 라플라시안 행렬은 끝입니다. 그냥 차수 행렬 - 인접 행렬을 계산하면, 그게 라플라시안 행렬이에요. 차수 행렬의 정보와 인접 행렬의 정보 모두를 어찌 저찌 포함하고 있네요. 결과적으로는 아래 그림과 같은 방식으로 표현됩니다.

 여기서 조금만 더 들어가면, 조금더 실전에서 많이쓰이는 놈을 접할 수 있는데, Symmetric normalized laplacian matrix란 놈입니다. 아래와 같은 수식으로써 표현되는데, 의미는 사실 간단해요. Normalized라는 이름처럼, 라플라시안 행렬을 정규화한 것인데, 차수 정보가 모두 1로 통일되고, 인접 행렬로 표현되어 있던, 노드에 대한 이웃정보가 차수로 나누어져 있는 형상입니다.

 위 그림과 같은 간단한 그래프를 대상으로 직접 D^(-0.5)에 대한 연산을 해보시면 금방 느낄 수 있을텐데, D matrix가 차수 행렬이라 저렇게 앞에 곱하고 뒤에 곱하고 하면, 각각 행벡터에 대한 실수배, 열벡터에 대한 실수배를 진행하는 셈이라 저렇게 정규화가 진행됩니다. 말로하면 어려운데, 그냥 해보면 당연해요.

 쨋든, 이렇게 그래프 정보롤 눌러 담은 행렬을 만들고, 이제 어떤 연산을 시작할텐데, 이런 인접 행렬 기반의 표현 방식은 큰 단점이 하나 있습니다. 전체 노드의 크기를 N으로 두면, 인접 행렬의 크기는 N x N인데, 이게, 너무 커요. 근본 자체가 크다보니, 이걸 지지고 볶고 계산을 해대려니까, 뭐 하나 진행할 때마다 큰 부담이란 말이에요. 그래서 이걸 조금 더 작은 차원에 임베딩해서 정보를 압축하고, 그 임베딩 행렬을 지지고 볶자- 하는게 최근의 흐름, 인 것 같습니다. 정확히 어떤 임베딩 방법론이 사용되는지는, 다음에 볼 수 있도록 하겠습니다.

이상입니다.

이미지 출처