[CS224W: Machine Learning with Graphs 강의 내용 요약 - 1]

 

 

http://web.stanford.edu/class/cs224w/

CS224W | Home

본 포스팅은 CSS224W 강의를 들으며 필요한 내용을 요약한 것이다. 필자 주관적으로 필요한 부분만 요약되어 있으니, 참고하길 바람.

 

 

---

1. Introduction; Machine Learning for Graphs

 

 

1) Objective

그래프 데이터구조에 대한 정의 및 종류에 대한 내용. 생략.

DNN 구조로 그래프 표현을 하면 fixed size 데이터를 간편하게 처리할 수 있기 때문에 이점이 많다. 이를테면 이미지 데이터나 음성 데이터를 예로 들 수 있다. 그러나 그래프 구조는 더 복잡하기 때문에 처리하기에 쉽지 않다. 

 

좌우당간에 이 수업의 목표는 Graph 자료구조로 DNN 네트워크에 임베딩을 시키고, 그 벡터로 무언가 prediction 하는 task를 디자인할 수 있도록 학습하는 것이다.

 

 

이를 통해, 과거의 ML task 에서 Feature Engineering 이라는 부분의 노고가 없어질 것이고, 이는 DNN 알고리즘의 잘 알려진 장점 중 하나이다.

 

 

그리고 클래스에서 다루게 될 Graph 관련 토픽들은 아래와 같다.

 

- Traditional methods : Graphlets, Graph Kernels
- Methods for node embeddings : DeepWalk, Node2Vec
- Graph Neural Networks : GCN, GraphSAGE, GAT, Theory of GNNS
- Knowledge graphs and reasoning : TransE, BetaE
- Deep generative models for graphs
- Applications to Biomedicine, Science, Industry

 

 

---

 

2) GNN ML Tasks

 

GNN을 디자인함으로써 수행 가능한 ML Task들은 다음과 같다.

 

- Node Classification
- Link prediction
- Graph classification
- Clustering
- Other tasks

그중에서도 Edge Level ML Task를 살펴보면, 가장 대표적인 예시는 Recommender System이다. 유저와 아이템이라는 두 개 타입의 노드로 그래프를 생성할 수 있고, Interaction 이라는 Edge가 존재하기 때문이다. 그리고 이를 이용해 Edge predict를 하면, "You might also like"의 의미가 될 수 있기 때문이다.

 

 

다른 예시들은 강의 내용을 참고하자.

 

---

 

3) Representations of Graph

Graph Network의 기본 구성은 다음의 그림과 같이 정의할 수 있다.

 

 

그리고 이에 더해 degree 라는 개념을 소개하는데, degree는 말 그대로 하나의 노드에 몇 개의 연결이 딸려있는가이다. 이를 잘 활용하면 그래프 전체에서의 평균 degree를 구할 수도 있다.

 

 

그리고 Graph 자료구조를 다루다 보면 가장 많이 등장하는 용어는 Bipartite Graph, 그리고 Adjacency Matrix이다. 당연하게도, 실제 데이터에서 대부분의 Adjacency Matrix는 매우 Sparse하다. 만약 User-Item 그래프라고 생각해본다면, 100만개의 아이템을 다 주문해본 유저는 없을 것이기 때문이다. 

 

 

그리고 이러한 행렬의 성질을 잘 활용하면 아래의 그림과 같이 row, column 단위의 degree를 쉽게 구할 수 있다.

 

 

만약 Edge에 특정한 의미가 있는 경우, 즉 Weighted Edge를 갖게 된다면 어떨까, 이는 아래와 같이 생각할 수 있다.

 

 

그리고 그래프 종류에 따라 아래와 같은 것도 생각해볼 수 있다. self-loops와 Multigraph이다.

 

 

지금까지 Graph 구조를 표현할 수 있는 방법들에 대해 알아보았다. 다시 한 번 정리하면 그래프는 Directed, Undirected 그래프로 나눌 수 있으며, 표현 방법으로는 bipartite, weighted, adjacency matrix 등의 자료 구조 표현 방법을 사용할 수 있다.