[CS224W] 1-2. Applications of Graph ML

1. Different Types of Tasks

지난 글, 1-1. Why Graphs에서도 잠깐 언급한 바 있지만, 그래프에 대한 딥러닝 모델링에서 output인 prediction은 여러 수준에서 이루어질 수 있다. 개별 node level일 수도 있고, edge(pairs of nodes) level일 수도 있고, community(subgraph) level일 수도, graph 혹은 graph generation level일 수도 있다. 아래에서 각각 level에서의 task가 무엇이 있는지, 그 응용 사례에는 어떤 것이 있는지 소개하겠다.

1. Node Classification: predict a property of a node(ex. categorize online users/items)
2. Link Prediction: predict whether there are missing links between two nodes(ex. knowledge graph completion)
3. Graph Classification: categorize different graphs(ex. molecule property prediction, drug design에 응용 가능)
4. Clustering: detect if nodes form a community(social circle detection)
5. Others: Graph Generation(ex. drug discovery), Graph Evolution(ex. physical simulation)

위와 같은 Graph ML task들은 high-impact applications로 이어질 수 있다! 아래에서 보다 구체적인 예시를 소개하겠다.

1) Example of Node-level ML Tasks

(1) Protein Folding

많은 약들이 우리 인체의 protein(단백질)과 결합하거나 그들의 특성을 변화시킴으로써, 결과적으로 인체 내 biological processes를 변화시키는 방식으로 작동한다. 단백질은 아미노산으로 구성되어 있다. 달리 말해, 단백질은 아미노산의 sequence인 것이다. 그런데, magnetic 혹은 다른 종류의 힘에 의해서 단백질은 쫙 펴진 아미노산 chain 형태로 존재하는 것이 아니라, 매우 복잡한 형태로 접혀 있게 된다. 이러한 단백질의 3D 구조를 예측하는 것은 생물학계의 오랜 난제였다. "아미노산 sequence가 주어졌을 때, 3D 구조를 예측할 수 있을 것인가?"

DeepMind사가 개발한 인공지능 AlphaFold는 이 문제에 대해 큰 성능 향상을 이루었다. AlphaFold의 핵심 아이디어는 바로 "spatial graph"였다. 이때 node는 protein sequence의 아미노산이 되고, edge는 아미노산 사이의 proximity(근접성)가 된다. 이는 모든 아미노산의 위치와 그 사이의 proximities가 주어진다면, 아미노산의 새로운 위치를 예측할 수 있는 Graph Neural Networks를 구축할 수 있음을 의미한다. 이를 이용하면 protein folding을 시뮬레이션할 수 있을 뿐 아니라, 분자들의 최종적인 위치를 예측할 수 있다.

2) Example of Edge-level ML Tasks

(2) Recommender Systems

유저는 아이템과 상호작용한다. 이때 아이템은 상품이 될 수도 있고, 영화나 음악이 될 수도 있다. 유저와 아이템 각각을 node로 표현하고, 유저-아이템 상호작용을 edge로 표현하면 이를 그래프로 구축할 수 있다(유저-아이템 상호작용은 유저가 어떤 상품을 사고, 리뷰를 남기거나, 영화를 보거나, 음악을 듣는 등의 행위를 가리킨다). 이렇게 그래프를 구축함으로써, 우리는 어떤 유저가 관심 있어할 만한 다른 아이템을 추천하거나 예측할 수 있다.

Graph Neural Network를 이용한 Recommender system에서의 key insight는, nodes를 어떻게 embed 혹은 represent하냐는 것이다. 서로 연관이 있는 노드는, 관계가 없는 노드에 비해 더 가까이 embedding 되어야 한다. 핀터레스트의 예시를 들면, query pin으로 케이크 이미지가 주어졌을 때, 비슷한 케이크 이미지는 가까이 embedding, 관련이 없는 스웨터 이미지는 멀리 embedding 되도록 함으로써 성공적인 recommendation이 이루어질 수 있도록 만든다. 이는 이미지 그 자체보다는, 이미지와 그래프 구조를 함께 고려하는 것이 보다 나은 추천을 가능케 할 수 있음을 시사한다.

(3) Drug Side Effects

많은 환자들이 complex하거나 함께 발병한 질병들을 치료할 목적으로 동시에 여러 종류의 약물을 사용하곤 한다. 그런데, 이처럼 둘 이상의 약물을 동시에 사용하는 행위는 예상치 못한 부작용을 불러일으킬 수 있다. 그렇다고 그 많은 종류의 약물 조합을 하나하나 실제로 테스트해볼 수도 없는 노릇. 해당 task에서의 과제는 임의의 약물 조합이 어떻게 상호작용하며, 어떠한 부정적인 부작용을 불러올 수 있는지를 알아내는 것이다.

이 또한 그래프로 접근할 수 있다. 이때 node는 약물과 단백질이 되며, edge는 그들 사이의 상호작용이 될 것이다. 우리가 알아내야할 부분은 drug와 drug 사이의 상호작용으로 인한 부작용이므로, drug-drug 사이의 missing connection을 알아내는 것이 목표라 할 수 있다. 이것이 해당 task가 edge-level ML task에 속하는 이유이다.

3) Example of Subgraph-level ML Tasks

(4) Traffic Prediction

지도를 켜서 고려대학교에서 연세대학교까지 어떻게 가는지를 찍어보면, 경로와 함께 예상 소요 시간도 알려준다. 이 또한 그래프 네트워크의 결과물이다. 이때 nodes는 road segment, edge는 road segment간의 connectivity가 된다. Graph Neural Network는 각 road segment의 condition 및 traffic patterns, 출발점으로부터 도착점까지의 경에 기반하여 travel time을 예측하도록 훈련된다. 실제로 구글맵에서는 도착 시간 예상, travel time 예측에 이러한 방식을 사용하고 있다.

4) Example of Graph-level ML Tasks

(5) Drug Discovery

Antibiotics(항생제)는 atoms(원자)를 node로 하고, chemical bonds(화학 결합)을 edge로 하는 small molecular graph이다. 우리가 관심 있는 부분은 그래프로 표현되어지는 각각의 분자가 치료 효과를 가지는지다. 실제로 MIT에서 Graph Neural Network를 이용해서 엄청난 양의 candidate pool에서 치료 효과를 가지는 분자를 빠르게 선별해 내는 antibiotic discovery를 수행한 연구 사례가 있다.

우리는 또한, 더 나아가서 graph generation에 대해서도 생각해볼 수 있다. 이는 지금껏 합성되거나 고려되지 않은 새로운 분자를 발견하는 데 활용될 수 있다. non-toxic하거나 high solubility 혹은 high drug likeness를 가지는 새로운 분자를 생성해내는 등 우리가 원하는 특성을 가지는 새로운 분자, 새로운 구조를 연구하는 데 응용 가능하다. 또한, 기존에 존재하던 분자가 desirable한 특성을 가질 수 있도록 optimization하는 데도 사용될 수 있다.

(6) Physics Simulation

우리는 물질을 set of particles라고 나타낼 수 있고, 이는 그래프 구조로 표현 가능하다. node는 particles 각각이 되며, edge는 그 particle들 사이의 interaction이 된다. Physics Simulation에 Graph Neural Network가 응용되는 과정은 다음과 같다.

1. proximity에 기반해 particle 간의 interaction을 표현하여 proximity graph를 만든다.
2. 현재의 특성(particle의 위치, 속도)을 반영하여 graph neural network를 구축하고, 이러한 정보에 기반했을 때 미래의 particle의 위치나 속도가 어떻게 변화할지를 예측한다.
3. 위에서의 예측에 기반하여 그래프를 업데이트하고, 1번으로 돌아가서 위 과정을 반복한다.

위와 같은 과정은 매우 빠르고 정확한 physics simulation을 가능케 한다.