Network representation learning is a task aimed at embedding network typology into low-dimensional vector space. One advantage is that tedious feature engineering work is avoided as the network representation learning model runs in an unsupervised manner, the learned latent vectors are general enough to be applied in a wide variety of network tasks. Another benefit is that the network representation learning model better captures the homophily characteristic and encodes it into latent vectors, which provide the performance improvement in the multi-label vertex classification task.
Various network representation learning models have been proposed[1, 2, 3]. Although these models are empirically effective, we find that they suffer from the "stop words" issue and the "short-sighted" problem. The "stop words" issue indicates that meaningless vertices are involved in the computation procedure, causing the model to be inefficient. The "short-sighted" problem is that the models fail in capturing the information of long-distance proximities between vertices, resulting in inadequate vertex representation are learned.
In this thesis, we present a novel network representation learning model named MHRWalk to learn latent vectors for a network. It mitigates the "stop words" issue and resolves the "short-sighted" problem by introducing the Metropolis-Hastings random walk sampler to this task. Moreover, we also show how latent representations of individual vertices learned using MHRWalk can be extent to sub-networks.
Experiments on real-world network datasets demonstrate the effectiveness and efficiency of the proposed model compared the state-of-the-art vertex representation models. We also demonstrate that the learned latent sub-network representation outperforms all baseline approaches in the sequence matching task. Beyond this, we visualize several sub-networks in a two-dimensional plane with the help of MHRWalk, which projects the sub-network topology into a low-dimensional and continuous-valued vector.
네트워크 표상 학습은 네트워크 위상을 저차원 벡터 공간으로 투사(embedding)하는 것을 목표로 하는 작업이다. 이 방법은 네트워크 표상 학습 모델이 비지도 방법으로 수행되어 번거로운 피쳐 엔지니어링 과정을 거칠 필요가 없는 동시에, 학습된 잠재 벡터들이 다양한 네트워크 작업에 적용될 수 있을 정도로 충분히 범용적이라는 장점을 갖는다. 네트워크 표상 학습의 또 다른 장점은 동류성(homophily characteristic)을 포착하여 잠재 벡터로 표현하는 부분이 더 뛰어나기 때문에 다중 레이블 정점 분류 작업에서 개선된 성능을 보인다는 것이다.
그 동안 다양한 네트워크 표상 학습 모델이 제안되어왔다. 이러한 모델들은 실증적인 효과를 보였으나 본 연구에서 이들이 "불용어(stop words)" 문제와 "근시안적(short-sighted)" 문제를 겪고 있음이 발견되었다. "불용어" 문제는 의미 없는 정점들이 계산 과정에 포함되어 모델을 비효율적으로 만드는 것을 말한다. "근시안적" 문제는 모델이 멀리 위치해있는 정점 간의 거리 정보를 포착하는 데 실패하여 부적절한 정점 표상을 학습하는 것을 의미한다.
본 논문에서는 네트워크상의 잠재 벡터를 학습하기 위해 MHRWalk 라는 이름의 새로운 네트워크 표상 학습 모델을 제안한다. 이는 메트로폴리스-헤이스팅 무작위 행보(Metropolis-Hasting Random Walk) 샘플러를 도입하여 "불용어" 문제와 "근시안적" 문제를 완화시킨다. MHRWalk로 학습된 각 정점의 잠재 표상이 서브 네트워크까지 확장될 수 있다는 점도 기술되었다.
현실 네트워크 데이터셋에 대한 실험에서 최신 정점 표상 모델들과의 비교를 통해 제안된 모델의 성능과 효율을 보인다. 또한 학습된 잠재 서브 네트워크 표상이 시퀀스 매칭 작업에서 모든 베이스라인 접근법들보다 뛰어난 성능을 보이는 것을 입증한다. 그 외에도 2차원 평면에서 서브 네트워크 위상을 저차원 연속값 벡터로 투사하는 MHRWalk를 통해 여러 서브 네트워크를 시각화하였다.
