[CS224W] 1-1. Why Graphs

※ Machine Learning with Graphs 카테고리의 글 시리즈는 Stanford University의 동명의 강의(CS224W) 내용을 정리한 것입니다. 혹시 오류를 발견하신다면 언제든지 댓글로 알려주시면 감사하겠습니다!

강의 영상: https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn 

Stanford CS224W: Machine Learning with Graphs

1. What is Graph?

Graph(그래프)는 entity(개체)간의 관계, 상호작용을 설명하고 분석하기 위해 사용되는 일반적인 언어이다. 이는 이 세상이나 주어진 도메인을 독립된 데이터 포인트들의 집합으로 보기보다는, entity 사이의 네트워크와 관계의 관점에서 보는 것이다. entity들은 그래프의 구조에 따라 서로 연결되어 있다.

태생적으로 그래프의 형태로 표현되는 데이터 종류들이 굉장히 많고, 이러한 도메인의 데이터들을 그래프 구조로 표현하는 것은 보다 믿을만하고, 정확한 방법이다. 그래프로 표현되는 도메인의 대표적인 예시는 아래와 같다.

• Event Graphs
• Computer Networks
• Disease Pathways
• Food Webs
• Particle Networks
• Underground Networks
• Social Networks
• Economic Networks
• Communication Networks
• Citation Networks
• Internet
• Networks of Neurons
• Knowledge Graphs
• Regulatory Networks
• Scene Graphs
• Code Graphs
• Molecules
• 3D shapes

2. Types of Networks and Graphs

그래프로 나타낼 수 있는 데이터는 근본적으로 크게 두 개 파트로 나눌 수 있다. 하나는 natural graphs 혹은 networks라 부르는 것으로, 기저에 있는 도메인이 태생적으로 graph로 표현되게 된다. 이에 속하는 도메인의 종류는 아래와 같다.

1) Networks(also known as Natural Graphs):

• Social networks: Society is a collection of 7+ billion individuals
• Communication and transactions: Electronic devices, phone calls, financial transactions
• Biomedicine: Interactions between genes/proteins regulate life
• Brain connections: Our thoughts are hidden in the connections between billions of neurons

다른 하나의 파트는, 태생적으로 그래프 형태를 갖는 것은 아니지만 relational structure를 가지고 있어서 그래프로 표현될 수 있는 도메인이다. 그 예시는 아래와 같다.

2) Graphs(as a representation):

• Information/knowledge: are organized and linked
• Software: can be represented as a graph
• Similarity networks: Connect similar data points
• Relational Structures: Molecules, Scene graphs, 3D shapes, Particle-based physics simulations

이 강의에서 다룰 메인 주제는 "relational structure(그래프)를 활용하여 어떻게 더 나은 prediction을 할 수 있는가?"이다. 복잡해 보이는 도메인은, 그래프로 표현될 수 있는 풍부한 relational structure의 집합이라고 볼 수 있다. 이러한 관계를 명시적으로 모델링한다면 우리는 보다 좋은 performance를 발휘할 수 있고, 보다 정확한 모델을 구축하여 정확한 예측을 하도록 만들 수 있다.

3. Why is Graph Deep Learning Hard?

현재 딥러닝의 toolbox는 단순한 시퀀스, 그리드같은 데이터에 특화되어 있다. 선형적인 구조로 표현될 수 있는 text나 speech, fixed size의 그리드로 표현될 수 있는 이미지 등이 그 예시다. 현대의 딥러닝 모델들은 이러한 유형의 데이터들을 처리하는데 매우 뛰어난 성능을 보이고 있다.

하지만 그래프는 앞서의 text, speech, 이미지 데이터에 비해 더욱 복잡한 구조를 가지고 있기 때문에 다루기가 까다롭다. 구체적인 이유는 다음과 같다.

1. 임의의 크기와 복잡한 topology(위상)를 가지고 있다.
2. 그리드나 text에서와 같은 spatial locality가 없다. 그리드의 경우 상하좌우, 텍스트의 경우 좌우의 spatial locality를 가지는데, 그래프의 경우 고정된 기준점이나 순서가 없기 때문에 이를 따질 수 없다.
3. 네트워크 자체가 dynamic하고, multi-modal한 특징까지 가진다.

이 강의에서는 그래프와 같은 복잡한 데이터 유형에 대해 딥러닝 모델링을 하는 방법에 대해서 다룬다. 이때 모델의 input은 그래프가 되고, output은 prediction이 된다. prediction은 개별 노드 수준에서 이루어질 수도 있고, 노드 쌍이나 노드 간의 링크 수준에서 이루어질 수도 있고, 아예 새로운 그래프를 생성해내거나 그래프로 나타나지는 주어진 molecule의 특성을 예측하는 것처럼 더욱 복잡한 수준일 수도 있다. 그래프에 대한 모델링은 실제로 아직 활발히 개척 중인 분야이다.

이 강의에서 하고자 하는 것은, "representation learning"이다. feature engineering 과정 없이, 자동적으로 그래프에 대한 좋은 representation을 학습하게 만들고자 한다. 이를 위해 representation learning 과정에서는 우리의 그래프의 노드들을 d차원으로 임베딩하여 d차원의 벡터를 만든다(이렇게 만들어진 벡터는 'representation', 'feature representation', 'embedding' 등 여러 이름으로 불린다). 유사한 노드끼리 embedding space에서 가까이 위치하도록 만드는 것이다. 임베딩이 잘 되면 downstream task에도 쉽게 적용이 가능하므로, 결국 우리의 목표는 그래프를 잘 임베딩하는 것이라고 표현할 수도 있겠다.