[CS224W] 1강 Machine Learning With Graphs

 

 

 

1️⃣  Why Graphs 

---

 

🔹 Graph 

 

•  Graphs are a general language for describing and analyzing entities with relations/interactions

 

 

•  엔티티의 관계와 상호작용을 분석하고 묘사할 수 있는 언어 

 

 

🔹 Many Types of Data are Graphs 

 

 

 

•  많은 데이터가 네트워크 형태로 이루어져 있음 

 

 

 

🔹 네트워크 vs 그래프 

 

•  네트워크 ( = Natural Graph) 

 

• social network : 사회 연결망 
• communication and transaction : 전자기기, 휴대폰, 금융거래 
• Biomedicine : 유전자, 단백질 상호작용을 통한 생명 조절 
• Brain connection : 수십억 뉴런들 사이의 연결성 

 

•  Graph ( as a representation ) 

 

• Information/knowledge : 정보와 지식이 구성되고 연결됨 
• software : 소프트웨어 구조 역시 그래프로 표현 가능 
• similarity networks : 비슷한 데이터 포인트들을 연결
• relational structures : 분자구조, Scene graph (장면의 객체와 관계) , 3D graphs, 물리적 시뮬레이션 기반의 입자

 

→ 네트워크는 system 을 칭하고 graph 는 네트워크의 수학적 표현을 의미하는데, 보통 네트워크와 그래프를 구분두지 않고 용어를 섞어서 사용한다. 

 

 

prediction 을 더 잘 하기 위해 relational structure 를 어떻게 이용할까 → 복잡한 도메인은 rich relational structure 를 가지므로 명확하게 모델링을 하는 것이 중요하다

 

 

 

🔹 Modern ML Toolbox 

 

 

•  현재의 딥러닝 학습 방법 → 간단한 sequence 나 grid 를 학습하도록 설계되어 있음 

 

※ sequence : 텍스트나 음성 데이터 , grid : 이미지 데이터 (격자 형태) 

 

•  네트워크는 복잡한 구조를 가지고 있기 때문에 현재 딥러닝 학습 방법에 적용시키기가 어렵다. 

 

 

 

 

✨ 네트워크의 특징 

① 임의의 크기 (arbitrary size) 와 복잡한 위상적 구조 (grid 처럼 공간적인 기준점이 없음)

② 고정적인 노드 순서나, 참고점이 없음 

③ dynamic 한 구조를 가지며, mutimodal (이미지, 텍스트, 음성 등 여러 형태의 데이터) feature 를 가짐 

 

 

 

 

🗨  CS224W 강의는 그래프를 학습시킬 수 있는 딥러닝에 대해 배우는 과목!

 

 

 

 

🔹 Representation learning 

 

•  표현학습 : feature 를 자동으로 추출하고 학습하는 것 

 

 

 

•  노드를 d 차원의 임베딩으로 맵핑 시키는 것 → 네트워크 내에서 비슷한 노드들은 임베딩 된 공간에서 가깝게 위치하도록 하는 것 

 

목표 : 함수 f 를 학습하는 것

 

 

🔹 강의 개요 

 

•  그래프 구조의 데이터에서 Machine learning 과 Representation learning 을 다룰 예정 

 

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️⃣  Applications of Graph ML 

---

 

🔹 Task 유형 

 

 

• Node 수준 , Edge 수준, Subgraph 수준, Graph 수준 

• Node classification : 주어진 노드 종류 분류 

• Link prediction : 노드 간의 연결 여부 예측 

• Community detection : 군집 감지 

• Network similarity : 유사도 측정 

 

 

🔹 Node level task 

 

 

 

🔹 Edge level task 

 

 

🔹 Subgraph level 

 

http://www.aitimes.com/news/articleView.html?idxno=131974  딥마인드, GNN 기술로 구글지도 도착시간 정확도 개선

 

 

🔹 Graph level 

 

 

 

 

 

 

3️⃣  Choice of Graph Representation 

---

 

🔹 그래프 표현 기법 

 

 

 

• 그래프는 일반적인 상황들을 표현할 수 있는 수단이다. 

 

 

🔹 Edge 의 방향에 따른 구분 : Directed graph VS Undirected graph 

 

 

 

🔹 Node Degrees : 노드가 가지고 있는 edge 의 개수 

 

 

 

 

🔹 Bipartite Graph : 서로 다른 종류의 독립된 노드들로 구성된 그래프 

 

 

 

 

🔹 그래프 표현 방법 

 

① Adjacency matrix 

 

 

 

그래프의 연결 유무를 1과 0으로 나누어 행렬로 표현한 것으로, Undirected 그래프의 경우에는 행렬이 대칭적으로 나타나는데, Undirected 는 단방향인 경우도 존재하므로 대칭 행렬이 아닐 수도 있다. 인접 행렬 표현 방식은 노드가 많아질수록, 즉 행렬의 차원이 커질수록 행렬이 Sparse 해진다는 단점이 있다. 

 

② Edge list 

 

 

edge 를 연결된 노드의 쌍 pair 로 표현한 방식이다. 

 

 

③ Adjacency list 

 

 

출발 방향의 노드를 key 값으로 도착 노드를 value 값으로 가지는 사전 Dictionary 형태로 저장하는 방식이다. 단방향 그래프이거나 거대한 그래프에서 효율이 좋다. 

 

 

 

🔹 Node and Edge Attributes 

 

 

 

• Weight : 엣지에 가중치 값을 부여할 수 있다. 

• Rank : 연결관계에 순위를 부여할 수 있다. 

• Type : 연결 관계에 유형을 부여할 수 있다. 

• Sign : 친구 vs 적, 진실 vs 거짓 처럼 상반된 관계성을 부여할 수 있다. 

 

 

 

🔹 그래프 유형 

 

 

• Self edges : 자기 자신으로 돌아오는 방향을 가진 그래프 (ex. 단백질, 하이퍼링크) 

• Multigraph : 두 노드 사이에 2개 이상의 edge 를 가진 그래프 (ex. 커뮤니케이션, 콜라보레이션) 

 

 

🔹 Connectivity - 양방향 그래프 

 

 

 

🔹 Connectivity - 단방향 그래프 

 

 

위의 빨간색 노드 그래프를 예로들면 E 노드에서 G 노드로 방향을 무시한다면 갈 수 있고, 방향을 지킨다면 갈 수 없는 Weakly connected directed graph 라고 할 수 있다. 

 

SCCs 는 그래프에서 부분적으로 나타나는 connected subgraph 로 In component 는 SCC 를 포함, Out component 는 SCC 를 미포함 하는 것을 의미한다.