HNE (Heterogeneous Network Embedding)

HNE (Heterogeneous Network Embedding) - 소개

2021. 8. 31. 21:39

Intro

안녕하세요, 오늘은 머신 러닝 알고리즘의 한 종류인 HNE(Heterogeneous Network Embedding) 에 대해서 정리해보겠습니다.

네트워크, 그래프라고 알려져 있는 자료구조는 여러 객체 사이의 관계를 표현하는데 매우 효과적입니다.

어떤 객체와 직접/ 간접적으로 연결되어있는 객체들을 분석하면 우리는 이 객체와 유사한 객체들을 찾을 수 있습니다.

하지만 문제가 있습니다. 직접/ 간접적인 연결이 너무 많다는 겁니다. 이는 우리가 일일이 다 고려할 수 없는 수준이죠.

어떤 객체는 10개의 다른 객체와 연결되어 있는 반면, 어떤 객체는 10,000개의 다른 객체와 연결되어있기도 합니다. 간접적인 연결까지 다 고려하면 이루 말할 수 없는 다양한 연결 관계가 존재합니다.

따라서 그래프 (또는 네트워크)는 그동안 다루기 어려운 자료구조로 여겨져 왔습니다. 이 복잡한 관계를 분석하려면 많은 연산이 필요하니까요!

하지만 머신 러닝 기술이 발전하고 하드웨어 스펙이 좋아지면서, 이 까다로운 자료구조를 다룰 수 있는 기술이 등장합니다.

바로 그래프 임베딩 (Graph Embedding) 입니다.

저는 그래프 임베딩 중에서도, 그래프를 구성하는 node와 edge의 종류가 여러 개인 Heterogeneous network (graph) embedding 에 대해서 공부해서 정리하려고 합니다.

heterogeneous network representation learning a unified framework with survey and benchmark 라는 논문의 내용을 정리할 거고, 내용이 많아서 여러 개에 나눠서 하려고 합니다.

한글표현과 영어표현이 섞여서 사용될 수 있습니다. 아래 단어 사전을 참고하세요.

그래프, 네트워크: graph, network (두 단어는 구분없이 사용됩니다.)

객체: node

연결: edge

Graph Embedding

그래프 임베딩은 그래프를 구성하는 객체들을 낮은 차원의 벡터로 표현하는 기술입니다.

$N$개의 객체 (node)로 이루어진 그래프를 있는 그대로 표현하려면, 적어도 $N \times N$크기의 인접 매트릭스가 필요합니다. 그래서 어느 두 객체가 연결되어 있으면 (edge가 존재하면) 해당 부분은 1, 아니면 0으로 채워지게 되는 것이죠. 물론 edge에 가중치 (weight)가 있거나, edge에 방향이 있는지 (directed), 없는지 (undirected)에 따라서 달라집니다.

그리고 이 인접 매트릭스는 매우 sparse하기 때문에 (대부분이 0이기 때문에), 낭비되는 메모리도 크고, 많은 연산량을 필요로 합니다. 그리고 직접적인 연결 정보만을 알 수 있죠. 이 인접 매트릭스만으로는 그래프의 직접/ 간접적인 풍부한 연결정보를 모두 파악하기 어렵습니다.

하지만 그래프 임베딩 기술을 적용한다면, $N \times d,, (d << N)$인 매트릭스의 각 값에, 다른 객체들 사이의 직접/ 간접적인 연결 정보를 고려한 값을 채울 수 있습니다. 각 객체는 $d$차원의 벡터로 표현이 되는데, 이때 그래프 상에서의 구조적 정보 (topological information)을 보존하는 형태로 표현이 됩니다. 그래프 상에서 가까우면, 비슷한 벡터로 표현이 된다는 뜻 입니다.

이렇게 그래프를 구성하는 각 node가 표현된 $d$차원 벡터를 latent vector, 또는 node의 representation이라고 합니다. 그래프 임베딩은 이 latent vector를 어떻게 구하느냐에 따라 여러 방법이 존재합니다.

수식으로 표현하면 $${\Phi}: V \rightarrow \mathcal{R}^{|V|\times d}$$

그래프 임베딩의 가장 시초격인 방법은 DeepWalk입니다. 그래프 임베딩에 관심이 있으신 분이라면 꼭 논문을 읽어보시길 추천드립니다.