Why Graph?
Graphs are a general language for describing and analyzing entities with relations/interactions
: 그래프는 객체의 관계 및 상호작용을 기술하고 분석하기 위한 언어
Many Types of Data are Graph
그래픽 구조로 나타낼 수 있는 다양한 도메인
Types of Networks and Graphs
관계형 구조를 갖는 도메인은 두가지로 표현됨
- NetWork (Natural Graphs)
네트워크 , 자연 그래프- Social network
- Brain connections
- Graph (representation)
- Information / Knowledge
- Software
다양한 네트워크 및 자연그래프는 관계구조를 캡쳐하기 위해 그래프로 모델링됨
How do we take advantage of relational structure for better prediction?
관계형 구조의 이점 : 복잡한 도메인을 관계형 구조로 표현, 이는 모델이 더욱 좋은 성능과 예측을 가능하게 함
일반적인 딥러닝의 데이터구조는 두가지
- 시퀀스 : 텍스트, 음성과 같은 선형구조
- 이미지 : 고정크기의 격자구조
그래프(네트워크 구조)의 특징
1. 임의의 크기와 임의의 복잡한 토폴로지 구조
2. 그리드, 텍스트에서의 공간적 국소성(기준점) 없음
ex) 그리드는 위, 아래 / 텍스트는 왼쪽, 오른쪽
3. 기준점(고정적인 노드의 순서)이 없음
Deep Learning in Graph
그래프를 입력으로 하는 신경망 구조로 예측하기
이러한 신경망 구조를 구축하는 방법
CS224W & Representation Learning
그동안 머신러닝에서는 사람이 feature engineering 단계에 많은 노력을 기울임.
Representation Learning(표현 학습) 은 feature Engineering 단계가 없음
이는 그래프에서 특징을 자동으로 추출하거나 학습하는 것. 그래프가 입력으로 들어오면 알아서 좋은 표현을 학습하여 다음 용도로 사용
-> 다운스트림 머신러닝 알고리즘
Representation Learning 의 방법은 그래프의 노드를 d차원의 벡터로 Embedding 하는 것.
네트워크에서 가깝게 위치한 노드는 임베딩 공간에 가깝게 매핑됨.
목표는 이 매핑함수 F 를 배우는 것.
Course Outline
앞으로 배울것
-
그래프를 나타내는 전통적인 방법 : Graphlets, Graph Kernels
-
노드 임베딩 : DeepWalk, Node2Vec
-
Graph neural Network : GCN, GraphSAGE, GAT, Theory of GNNs
-
Knowledge Graph and reasoning : TransE, BrtaE
-
Deep Generative model 구축 방법
-
생물의학, 과학, 산업에서의 응용
Different Types of Tasks
그래프내의 다양한 level에서 수행할 수 있는 작업
- node level
- subGraph level
- edge level
- Graph level
Node level 예시
- 단백질 접힘
단백질은 매우 복잡한 모양으로 접혀있음
생물학에서 아미노산의 서열을 가지고 기본 단백질의 3D 구조를 예측할 수 있느냐 를 해결
"DeepMind의 AlphaFold"
핵심 아이디어는 단백질의 아미노산 서열을 그래프구조로 나타낸 것.
노드 : 아미노산 서열
링크 : 각 서열의 공간적 근접성
모든 아미노산과 각 근접성을 그래프로 나타내서 단백질 접힘을 시뮬레이션 해보고 분자릐 최종 위치를 찾아냄
Edge level 예시
- 추천 시스템
- 추천 시스템
노드 : 사용자와 아이템
링크 : 사용자와 아이템의 상호작용
그래프 구조로 나타내어 사용자가 미래에 관심을 가질만한 아이템을 추천
핵심 아이디어는 각 노드와 관련된 다른 노드를 관련되지 않은 노드보다 가깝게 Embedding하는 것.
- 약물 조합 부작용
많은 약을 복용하는 환자 -> 약물 간 상호작용 시 부작용을 예측
- 약물 조합 부작용
노드 : 약물(삼각형), 단백질(원)
링크 : 상호작용
C, M을 함께 복용하면 r의 부작용이 일어나는 것이 알려져있을 때의 그래프.
부작용 그래프에서 누락된 edge를 예측할 수 있는지
-> 과거에 알려지지 않은 부작용 예측 가능
subgraph level 예시
Traffic Prediction : 이동시간 예측
노드 : 도로 세그먼트
링크 : 도로 간 연결
출발지와 목적지 사이 각 도로 구간의 교통패턴을 학습
Graph level 예시
- 1.약물 발견 : 새로운 약, 새로운 항생제 발견
노드 : 원자
링크 : 화학 결합
이전에 합성되거나 사용한 적 없는 분자 구조 발견. 분자를 그래프로 생성
- 물리학 기반 시뮬레이션
노드 : 입자들
링크 : 입자 간 상호작용
해당 그래프가 앞으로 어떻게 변형될 지 예측 : 이 재료가 어떻게 변형될 지 예측
- 물리학 기반 시뮬레이션
Component of a NetWork
객체 : 노드 = N
상호작용 : 링크 = E
시스템 : 그래프 = G(N,E)
choosing a proper Representation
노드가 무엇인지, 링크가 무엇인지 선택하는 것은 매우 중요
주어진 문제에 따라 적절한 네트워크를 선택해야 함
객체들 사이에 링크를 할당하는 방식
Direct vs Undirected Graph
-
무방향 그래프
-
방향 그래프
Node Degree
Undirect Graph
-
단순 노드의 차수 : 해당 노드에 연결된 edge의 갯수
-
평균 노드 차수 : 네트워크에 있는 모든 노드의 차수의 평균 == edge의 수의 두배를 노드로 나눈 값 (노드의 차수 계산시 edge가 두번씩 계산되므로)
direct Graph
- in-degree : 해당 노드를 가리키는 (노드로 들어오는) edge의 갯수
- out-degree : 해당 노드에서 나가는 edge의 갯수
Bipartite Graph
이분 그래프 : 두가지 다른 유형의 노드에 대한 그래프
노드는 자신과 다른 유형의 노드와만 상호작용 함
Folded/Projected Graph
이분 그래프를 한쪽으로 투영한 그래프
서로 같은 인접한 노드가 있을 때 두 노드를 이웃으로 만듬
ex ) 1의 인접 노드 : A
2의 인접 노드 : A, B
1과 2의 인접노드중 같은 노드가 있으므로 1과 2를 연결.
Representing Graph : Adjacency Matrix
인접행렬 : 노드 갯수와 같은 크기의 정방행렬을 만들고 = 각 노드가 인접해있으면 1, 아니면 0
무방향 그래프의 특징
- 대각선 원소 모두 0
- 대칭 행렬
- i 노드의 차수 = k(i) = i 행의 합 = i 열의 합
- 전체 차수 : 모든 원소의 합의 1/2
방향 그래프의 특징
- 대각선 원소 모두 0
- 대칭 아님
- i 노드의 out-degree = i 행의 합
- i 노드의 in-degree = i 열의 합
- 전체 차수 : 모든 원소의 합
네트워크는 매우 희박하여 인접행렬 생성시 희소행렬 얻을 수 있음
항상 희소행렬로 표현함.
Representing Graph
-
list of Edge
단점 : 그래프 조작 및 분석 어려움 -
Adjacency list
주어진 노드의 이웃 목록 저장하여 빠르게 탐색 가능
Node and Edge Attributes
그래프 노드, 링크는 속성을 가질 수 있음
More types of Graphs
-
Unweigeted vs Weighted
-
Self-edges , Multigraph
Connectivity of Undirected Graphs
연결성 : 그래프가 연결되어 있는지 , 끊어져 있는지의 여부
edge를 따라 연결되는 노드의 집합이 하나의 component
Connectivity of Directed Graphs
-
strong connect
노드가 양방향으로 모두 연결 된 그래프 -
Weakly connect
방향을 무시하고 단순 연결 그래프 -
노드끼리 사이클을 구성하는 경우에도 강하게 연결되었다고 말함
