[데이터과학] GraphSAGE
강력한 그래프 임베딩을 활용한 링크 예측 기법
EDITOR'S NOTE
인터넷 네트워크, 도로 네트워크, 인용 네트워크, 유전 정보, 통신망, 전력망과 같이 우리 주변의 많은 것들이 네트워크 형태로 구조화되어있는데요, 네트워크 분석은 물리학, 수학, 컴퓨터과학 등 다양한 분야에서 활용되며 개인과 집단들 간의 관계를 노드와 링크로 모형화하여 구조나 확산 및 진화과정을 계량적으로 분석하는 방법입니다. 개체 자체의 속성에 중점을 둔 기존의 통계적인 연구 방법과는 달리, 개체 간의 상호 관계에 초점을 맞춘 방법인데요.
자세한 내용은 디이프 이상민 소장님께서 설명해드릴게요~!
I. Link Prediction: 그래프 데이터에서의 중요성
실제 세계의 문제들은 대부분 네트워크 데이터로 이루어져 있습니다. 네트워크는 node와 edge로 구성되며, 개체 간의 관계를 표현합니다. 이러한 네트워크 데이터에서 링크 예측(link prediction)은 아직 연결되지 않은 노드 간의 관계를 예측하는 작업을 의미합니다. 이는 현실 세계에서 발생하는 다양한 문제에 매우 중요한 응용 분야입니다.
예를 들면 다음과 같습니다:
1. 소셜 네트워크 확장: 소셜 네트워크에서 새로운 친구 또는 연결 가능한 사람들과의 관계를 예측함으로써 네트워크의 규모를 확장할 수 있습니다. 이는 사회적 활동과 온라인 커뮤니티의 성장과 확장에 도움이 됩니다.
2. 제품 추천: 제품 판매자는 고객들 사이의 관계를 분석하여 특정 고객에게 어떤 제품을 추천해야 하는지 예측할 수 있습니다. 이는 개인화된 제품 추천 시스템의 기반이 됩니다.
3. 화학 분자 상호작용 예측: 화학 분야에서는 분자 간의 상호작용을 예측함으로써 새로운 약물 발견과 약물 효능에 관한 연구에 활용됩니다. 이는 의약 산업에 매우 중요한 역할을 합니다.
소셜 네트워크에서의 새로운 사람 관계 예측이러한 실제 문제들은 네트워크 데이터에서 개체 간의 관계를 예측하는 문제에 집중되어 있습니다. 이러한 문제 해결을 위해 Graph Neural Networks (GNN)과 같은 머신러닝 알고리즘들이 네트워크의 구조와 관계를 효과적으로 모델링하고 예측하는 데 사용됩니다. GNN은 각 노드의 이웃 정보를 활용하여 노드의 임베딩을 업데이트하고, 그래프의 구조적 특징을 반영하여 링크 예측에 유용한 임베딩을 학습합니다. 이를 통해 네트워크 데이터에서의 링크 예측이 실제 문제에 매우 중요한 응용 분야로 자리 잡고 있습니다.
이번 글에서는 링크 예측에 활용되는 다양한 GNN 모델 중 GraphSAGE에 대해 소개해보고자 합니다.
II. GraphSAGE: Link Prediction Models
GraphSAGE는 2017년에 "Inductive Representation Learning on Large Graphs" 논문에 소개된 모델로, 링크 예측을 위해 노드 임베딩을 사용하는 중요한 그래프 신경망 기법입니다. 이전에 소개된 Graph Convolutional Network (GCN)과는 유사한 수학적 원리를 기반으로 하면서도 대규모 그래프 학습에 있어서 기존의 문제점들을 극복한 모델입니다.
GraphSAGE의 주요 특징은 다음과 같습니다:
1. 인덕티브 학습 (Inductive Learning): GraphSAGE는 인덕티브 학습을 통해 새로운 노드를 효과적으로 처리할 수 있습니다. 즉, 보지 못한 노드에 대해도 이를 임베딩하여 링크 예측에 활용할 수 있습니다. 이로 인해 실시간으로 새로운 노드 정보가 생성되는 환경에서도 유용하게 활용할 수 있습니다.
2. 샘플링 기법 (Sampling Techniques): GraphSAGE는 임베딩을 학습하기 위해 노드의 이웃들을 샘플링하여 사용합니다. 이는 대규모 그래프에 효과적인 학습을 가능하게 합니다. 샘플링은 그래프의 규모와 관계없이 더 작은 미니배치를 사용하여 학습을 수행하며, 이는 학습 속도와 메모리 사용을 효율적으로 관리할 수 있게 합니다.
3. 계층적인 방법 (Hierarchical Aggregation): GraphSAGE는 이웃 노드들의 임베딩을 계층적으로 집계하여 각 노드의 표현을 학습합니다. 이웃 노드들의 정보를 적절하게 조합하면서 노드 간의 구조적 관계를 잘 반영하는 임베딩을 생성합니다.
4. 미니 배치 학습 (Mini-batch Training): GraphSAGE는 미니 배치 학습을 통해 효율적으로 학습합니다. 대규모 그래프에서도 빠르게 학습이 가능하며, 이는 네트워크 학습의 성능과 속도를 모두 향상시킵니다.
GraphSAGE의 학습 방식의 특징을 보면 각 노드를 바로 임베딩하는 대신, 이웃 노드로부터 정보를 Aggregate하는 함수를 훈련하는 방식을 취합니다. 구체적으로는, 취합 함수 이용해 관심 있는 노드로부터 얼마나 떨어져 있는 이웃(k)만큼 정보를 취합하는 방법을 학습합니다.
GraphSAGE의 sample과 aggregate 방식논문에서는 GraphSAGE의 성능을 4가지 모델(Random Classifier, Feature Based Logistic Regression, DeepWalk, Concat)과 비교한 결과를 제시하고 있습니다. 해당 결과에서는 4가지 모델보다 상당히 높은 성능을 보였다고 보고하고 있습니다. 물론 해당 내용은 노드 분류에 대한 성능이긴 하지만, GraphSAGE의 프레임워크 자체가 Graph 데이터에 대해 강력한 표현능력을 가지고 있음을 알 수 있습니다.
GraphSAGE는 Graph 데이터 문제를 효과적으로 해결할 수 있는 모델로 입증되고 있습니다. 제품 추천, 소셜 네트워크 확장, 화학 분자 상호작용 등 다양한 실제 문제들에서 그 성능과 활용성이 입증되고 있습니다.
이처럼 GraphSAGE는 네트워크 데이터에서 링크 예측 문제를 다루는 데 매우 유용한 기법으로 자리 잡고 있습니다. 또한 계속해서 연구와 개선이 이루어지고 있으며, 실제 응용 분야에서의 활용 가능성이 더욱 높아질 것으로 기대됩니다.
Reference
Iftikhar Ahmad et al, Missing Link Prediction using Common Neighbor and Centrality based Parameterized Algorithm, Sci Rep, 2020
William L. Hamilton et al, Inductive Representation Learning on Large Graphs, NIPS, 2017
https://jhtobigs.oopy.io/graphsage
