Graph와 Machine learning 설명 (Node classification, relation prediction, clustering, graph regression)

  Graph 형태로 표현된 데이터는 복잡한 데이터를 한 눈에 쉽게 파악할 수 있게 해주고, 데이터 간의 관계를 한 눈에 알 수 있게 해준다는 장점을 가진다. 그래프에 머신러닝을 적용하는 것이 기존의 머신러닝과 비교했을 때 가지는 가장 큰 차이점은 그래프 내부의 노드나 엣지들이 서로 독립적인 것이 아닌, 관계를 가지고 있기 때문에 이들이 가지는 관계성을 머신러닝 시에 고려해야 한다는 점이다. 이를 고려한 그래프에의 머신러닝 활용 방법에는 크게 네 가지가 있다. 이번 포스팅에서는 그래프의 머신러닝 활용 방법에는 어떤 것이 있는지에 대해 알아보겠다. 

Node classification

 Node classification은 그래프 내의 노드의 label을 classification하는 것을 말한다. 이 노드의 label은 노드의 타입이 될 수 도 있고, 노드의 특성이 될 수도 있다. 그래프의 node classification이 다른 머신러닝의 classification과 다른 점은 그래프의 노드들은 서로 독립적이지 않다는 것이다. 그래프 내의 노드들이 서로 연결되어 있고, 관계를 가지고 있기 때문에 기존의 머신러닝에서의 iid를 가정하는 classification 방법이 아닌, 데이터의 dependency를 고려하는 다른 방법을 적용해야 한다. 

 이를 위해서는 노드 사이의 관계에 대해 다양한 가정을 하기도 한다. 대표적인 예시가 homophily이다. 즉, 이웃한 노드들은 비슷한 특성을 가지고 있다는 것이다. 이외에도 비슷한 local 이웃을 가지고 있는 노드들은 비슷한 label을 가진다는 structural equivalence, 다른 label을 가지는 노드들은 연결된다는 heterophily 등의 다양한 가정이 존재한다.

예시

 SNS 상의 사람들의 관계를 나타낸 그래프가 있다고 하자. 노드는 각 SNS 계정, 엣지는 각 SNS 계정 간의 관계를 표현한다. 이 때, 어떤 계정들은 진짜 사람들의 계정일 것이고, 어떤 계정들은 가계정일 것이다. 각 노드가 진짜 사람들의 계정인지 가계정인지를 classify하는 것이 node classification의 예시이다.

Relation prediction

 Relation prediction은 노드와 노드 사이에 엣지가 존재하는지 여부를 예측하는 것이다. 이는 link prediction, graph completion, relational inference 등으로도 불린다. 그래프 내에 존재하는 엣지들을 training하여, 이외에 엣지가 존재하지 않는 노드 간에 어디에 엣지가 생길 수 있는지를 예측하는 것을 말한다. 

예시

 사람과 영화를 노드로, 어떤 사람이 어떤 영화를 시청했다면 이를 엣지로 표현하는 그래프가 있다고 하자. 이 때, 영화와 사람 간의 관계를 나타내는 엣지를 training하여 그 사람이 어떤 새로운 영화를 볼 것인지를 예측하는 relation prediction을 통해 그 사람에게 영화를 추천할 수 있을 것이다.

Clustering (Community detection)

 Clustering은 그래프 안의 노드들끼리 연관성이 높은 노드들을 묶어주는 것을 말한다. 앞에서 살펴본 node classificaiton과 relation prediction은 supervised learning의 형태에 가까웠다면, clustering은 unsupervised learning 형태에 가깝다. 

예시

 논문들 간의 인용을 나타낸 그래프가 있다고 하자. 노드는 논문, 엣지는 논문 간의 인용을 나타낸다. 이 때, 주제가 비슷한 논문들끼리 community를 찾아내는 것이 clustering의 예시이다.

Graph classification, regression, clustering

 Graph classification, regression, clustering은 앞서 본 세 가지 유형과는 달리, 그래프 하나하나를 통째로 분류하거나, 그래프의 특성을 예측하거나, 클러스터링하는 것을 말한다. 즉, 여러 다른 그래프들로 구성된 dataset을 가지고, 특정 그래프가 어떤 특성을 가지고 있는지를 예측하거나, 그래프들을 묶어주는 것이다. 

예시

 하나의 그래프가 단백질의 구조를 나타낸다고 하자. 각 그래프들에 대해 해당 단백질이 독성을 가지고 있는지 아닌지를 classify하는 것을 graph classficiation이라고 할 수 있다.

 

 이번 포스팅에서는 그래프 형태의 데이터에 머신 러닝이 어떻게 적용될 수 있는지를 예시와 함께 알아보았다. 다음 포스팅에서는 그래프 머신러닝을 위해 어떤 feature들이 사용될 수 있는지에 대해 알아보겠다. 

References

1. Hamilton. William L., Graph Representation Learning.