2020-01 Intro

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

Graph의 정의

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

Network와 Graph의 종류

Networks (=Natural Graphs)

• Social Networks
• Communication and transactions
• Biomedicine
• Brain Connections

Graphs

• Information/knowledge
• Software
• Similarity Networks
• Relational Structures

Graphs: Machine Learning

Complex domains have a rich relational structure, which can be represented as a relational graph(복잡한 도메인은 관계형 그래프로 표현할 수있는 풍부한 관계형 구조를 가지고 있음)

이미지/텍스트와 달리 네트워크 분석이 어려움

---

Applications of Graph

Classic Graph ML Tasks

• Node classification: node가 어느 class에 속할지 예측
• Link Prediction: node사이에 link가 있을지 없을지 예측
• Graph Classification: graph들이 어느 class에 속할지 예측
• Clustering

Graph의 다양한 Task

Examples of ML Tasks

Node Level

Protein Folding

AlphaFold: Solving Protein Folding

Edge Level

Recommender System

• nodes: users and items
• edges: user-item interactions
• Goal: recommend items users might like

PinSage

• recommend related pins to users

Subgraph Level

Traffic Prediction

• Nodes: Road Segments
• Edge: Connectivity between road segments

Graph Level

Drug Discovery

• Nodes: Atoms
• Edges: Chemical Bonds

Choice of Graph Representations

Directed vs Undirected Graphs

Undirected Graphs

• symmetrical, reciprocal links
• examples
  • collaborations
  • friendship on facebook

Directed Graphs

• directed
• examples
  • phone calls
  • following on Twitter

Node Degrees

• node i에 인접합 edge의 개수
• directed graph에서는 in-degree(들어오는 방향)와 out-degree(나가는 방향)를 정의한다.

Bipartite Graph

• 두 집합간에만 edge가 있는 그래프
•  examples
  • Authors-to-papers
  • Actors-to-Movies
  • Users-to-Movies
  • Recipes-to-Ingredients

Adjacency Matrix(인접행렬)

연결되어 있는 edge를 행렬로 나타냄

Unweighted and Weighted Graphs

Self-edge and Multigraph