GNN Overview 및 검색 엔진에 연결해 보기 (Predict Then Propagate: Graph Neural Networks Meet Personalized PageRank)

데이터는 점점 더 방대하고 복잡해지고 있다.
행과 열로 이루어진 세계는 컴퓨터에 친숙한 환경일 뿐이다.
실생활에서 사람들은 관계를 통해 삶을 탐색하고 유추한다.

이 문구는 graph thinking/modeling에 무지했던 저를 일깨워 주었고 모든 문제를 matrix로 embedding한 deep learning으로 풀 수 있을 것만 같던 환상을 합리적으로 깨부쉈습니다. 최근 GNN에 관심을 가지게 된 계기이기도 하고 공부하면서 이 분야는 너무 어렵다! 는 사실도 알게 되는 중입니다. 😂😂 이 글을 통해 막연했던 GNN에 한 발짝 다가서길 바랍니다.

 

---

What is GNN?

GNN은 Graph Neural Network의 약자로, graph라는 자료구조를 이용하여 신경망으로 인공지능을 학습시키는 방법입니다. GNN을 이해하기 위해서는 우선 graph부터 이해해야 합니다.

Graph는 entity와 relationship을 표현할 수 있는 자료구조로, 각 entity는 node (또는 vertex)로써 표현되며 relationship은 edge로써 표현됩니다. 즉 graph는 entity들의 관계나 상호 작용을 기술하고 분석할 수 있는 유일무이한 language라고도 할 수 있습니다. 아래 그림처럼 real-world의 data라고 할 수 있는 social networks, 지하철 노선도, 컴퓨터 네트워크, 단백질 구조 등이 graph로 표현할 수 있는 data의 대표적인 예 라고 할 수 있습니다.

 

Graph Mining Problems

Data에서 어떤 패턴이나 규칙, 이상치를 찾는 data mining task처럼, graph도 이와 같은 graph mining problem들이 존재합니다. 크게 polynomial time solvable problems와 NP-hard problems로 나눌 수 있는데, 많이 연구되는 분야는 다음과 같습니다. 특히 NP-hard problems를 어떻게 효율적으로 빨리 풀 수 있을 것인가가 graph 분야에서 많이 연구되는 주제입니다.

• Polynomial Time Solvable Problems
  ◦ The Shortest Path Problem
  ◦ Connected Component
  ◦ Community Detection
• NP-hard Problems
  ◦ Graph Isomorphism
  ◦ Subgraph Matching
  ◦ Subgraph Query Processing

 

Applications for Tasks of GNNs

그 동안의 deep learning modeling 방식은 CNN, RNN 등과 같이 sequence나 grid 기반으로 디자인 되어 왔습니다. 하지만 최근 들어서는 모든 task가 이런 자료구조를 가지고 있지 않다는 인식과 relationship structure 분석에 더 좋은 방법들에 대한 motivation이 요구되어 왔습니다. 그리하여 이러한 문제점들을 개선해 줄 수 있는 broadly applicable neural network인 GNN이 최근 활발하게 연구되고 있다고 볼 수 있습니다.

GNN에서의 task들은 크게 아래 표와 같이 3가지 level로 나뉩니다. 이러한 task들로부터 적용되는 분야로는 drug discovery, recommender system 등이 있습니다.

Level	Task	Application
Graph-level	Graph embedding, graph generation	Drug discovery
Node-level	Node embedding, node classification	Recommender system, text classification, behavior prediction
Edge-level	Link prediction	Knowledge graph completion

 

Then, Why Are GNNs Difficult?

그렇다면 GNN이 이렇게 활발하게 연구되고 있는데도 불구하고, 왜 이렇게 어렵고 풀기 힘든 문제일까요?

첫 번째, graph 자료구조의 복잡함입니다. Degree (node의 깊이) 나 graph size의 다양함 때문에 GNN을 일반화하여 적용하기가 어렵습니다.

두 번째, grid나 sequence 자료구조처럼 node가 정렬되거나 고정되어 있지 않고 reference point가 없다는 점입니다.

마지막으로는 dynamic graphs에 대한 어려움입니다. 실제 real-world의 data가 그러하듯, graph 내의 data인 node와 edge는 언제든지 삽입/제거될 수 있기 때문에 변수가 많다는 점이 GNN을 어렵게 만듭니다.

 

---

 

최근 저는 검색 엔진에도 관심이 많은데요, 이러한 graph embedding 기법을 검색 엔진 분야에 활용할 수 있겠다는 아이디어가 떠올랐습니다. 물론 당연하게도 비단 저만의 아이디어는 아니었고 관련 논문이 많았습니다. 관련하여 PageRank 알고리즘에 GNN을 적용한 논문을 간단하게 살펴보도록 하겠습니다! 😀😀

 

---

 

Predict Then Propagate: Graph Neural Networks Meet Personalized PageRank

Abstract

일반적인 GNN에서는 node에 대해 오직 몇 번의 propagation만 고려되고 neighbor coverage를 늘리기 쉽지 않다는 단점이 있었습니다. 본 논문에서는 큰 규모이고 adjustable한 node neighborhoods의 classification에 활용 가능하면서 어느 neural network에도 쉽게 결합 가능한 PPNP 모델과, 이에 대한 빠른 근사 버전인 APPNP 모델을 제시합니다.

Methodology

본 논문에서는 GCN과 PageRank의 관계를 이용하여 Personalized PageRank (이하 PPR) 에 기반한 propagation scheme를 구축합니다. 그 결과로 PPNP (Personalized Propagation of Neural Predictions)라는 모델을 제시하며, 또한 최적화를 통해 APPNP (Approximate PPNP) 모델을 제시합니다.

PPNP에서는 node의 feature에 기반하여 predictive value를 생성한 뒤, fully Personalized PageRank scheme를 통해 전파시키는 방식을 사용합니다. 다만 multi-class의 경우, predictive value의 계산이 조합을 통해 중복된 계산을 하게 됩니다. 이를 개선하기 위해 Power Iteration을 통해 근사한 모델이 APPNP 입니다.

Result

본 실험에서는 4가지의 text-classification dataset이 사용되었습니다. (CITESEER, CORA-ML, PUBMED, Microsoft Academic) PPNP와 APPNP는 아래 그래프와 같이 특히 sparse label 환경에서 대조 모델들을 압도하는 모습을 보였습니다.

Conclusion

APPNP는 기존의 aggregation 과정에 대해 또 하나의 유용한 선택지를 제공해주었다고 볼 수 있습니다. 또한 propagation 부분과 predictive value를 생성하는 부분이 분리가 되어있기 때문에 다른 GNN과 결합하기도 용이합니다. 그리고 근사치를 적용하는 알고리즘을 사용하였기 때문에, Power Iteration을 많이 하더라도 parameter 증가, gradient vanishing, over-smoothing problems가 발생할 가능성이 낮기 때문에 많은 장점을 가진 모델이라고 할 수 있습니다.

 

---

 

References

https://arxiv.org/abs/1810.05997

Predict then Propagate: Graph Neural Networks meet Personalized PageRank

 

https://github.com/gasteigerjo/ppnp

GitHub - gasteigerjo/ppnp: PPNP & APPNP models from "Predict then Propagate: Graph Neural Networks meet Personalized PageRank" (

https://greeksharifa.github.io/machine_learning/2021/08/20/APPNP/

Python, Machine & Deep Learning

---

 

모두의 연구소에서 진행하는 "함께 콘텐츠를 제작하는 콘텐츠 크리에이터 모임"
COCRE(코크리) 2기 회원으로 제작한 글입니다. 코크리란? 🐘