교재 및 참고문헌
▪ Willian L. Hamilton, Graph Representation Learning • https://www.cs.mcgill.ca/~wlh/grl_book/
▪ Yao Ma and Jiliang Tang, Deep Learning on Graphs • https://cse.msu.edu/~mayao4/dlg_book/
그래프 모델링
- 복잡계(복잡한 시스템)을 데이터로 수치화, 정형화 된 형태로 가져올 때 그래프를 도구로 씀
- 복잡계의 객체를 노드로, 객체들 사이의 상호 작용을 링크로 연결
- 노드들의 집합과 링크들의 집합
- 소셜 네트워크 → 각 개인: 노드, 친구 관계: 링크
- 단백질 네트워크 → 단백질: 노드, 단백질 사이 상호작용: 링크
시각화, 탐험적 데이터 분석 가능, 군집화 (커뮤니티 발견)
ex) 웹 그래프: page rank
그래프의 중요성
- 그래프로 표현 가능한 데이터의 양과 질이 증가
- 대규모 그래프 데이터 접근 가능
- 기계학습 기술의 발전 → 기계학습이 그래프 데이터 모델링, 분석 및 이해력 향상에 도움
⇒ Graph Machine Learning
1.1 그래프란?
그래프 (Graph)
- **𝐺= (𝑉,𝐸)**로 표현
- 노드의 집합 𝑉 = {v1, v2, …, v3}
- 링크의 집합 𝐸 = {(𝑢, 𝑣) | 𝑢 ∈ 𝑉,𝑣 ∈ 𝑉}
- 보통 n개의 노드, m개의 링크
단순 그래프 (Simple Graph)
- 중복된 링크와 loop가 없는 그래프
- 두 노드 사이의 링크는 최대 1개
- 모든 링크는 방향성이 없음 (undirected), 즉 (𝑢, 𝑣) ∈ 𝐸 ↔ (𝑣, 𝑢) ∈ 𝐸
인접 행렬 (Adjacency Matrix)
▪ $𝑨∈ℝ ^{𝑉×𝑉}$로 표현 ▪ 모든 노드를 행(row)과 열(row)에 대응하여 링크 표현 ▪ 그래프가 방향성이 없는(undirected) 링크만 포함→𝑨는 대칭 행렬(symmetric matrix) ▪ 그래프가 가중치가 있는(weighted) 링크를 포함→𝑨의 성분(element)은 {0,1} 대신 실수 값
다중-관계 그래프 (Multi-relational Graph)
▪ 링크에 유형을 추가하여 표현: (𝑢, 𝜏, 𝑣) ∈ 𝐸 ▪ 각 관계 유형 별 인접행렬 정의: 𝑨𝜏
$𝜏_1 → 𝑨𝜏_1$
$𝜏_2 → 𝑨𝜏_2$
▪ 관계의 집합: 𝑅 = {${𝜏_1,𝜏_2, ...}$} ▪ 전체 그래프를 요약하는 인접텐서(adjacency tensor) 정의: $𝑨 ∈ ℝ^{|V|×|R|×|V|}$ 3차원 array
예제: Multi-relational Graph ▪ 이종 그래프(heterogeneous graph) ▪ 다중 그래프(multiplex graph)
이종 그래프 (Heterogeneous Graph)
▪ 노드에도 유형(type)이 있는 경우 ▪ 노드 집합의 분할: $𝑉=𝑉1∪𝑉2∪⋯∪𝑉𝑘$ where $𝑉𝑖 ∩𝑉𝑗 =∅, ∀𝑖 ≠𝑗$ ▪ 특정 링크는 특정 유형의 노드들 사이에서만 연결, 즉 $(𝑢, 𝜏_𝑖, 𝑣) ∈ 𝐸 → 𝑢 ∈𝑉_𝑗, 𝑣 ∈ 𝑉_k$
= i 번째 type은 j번째 type과 k번째 type의 노드들을 연결해주는 relation type이다.
예제: Biomedical Graph ▪ 단백질, 약물, 질병을 나타내는 노드 유형이 가능 ▪ “치료” 링크: 약물 노드와 질병 노드 사이의 연결 $(v_{질병}, 𝜏_1, 𝑣_{약물})$ ▪ “부작용” 링크: 두 약물 노드 사이의 연결 $(v_{약물}, 𝜏_2, 𝑣_{약물})$
예제: 다분 그래프 (Multipartite Graph) ▪ 서로 다른 유형의 노드끼리만 연결이 가능한 그래프 ▪ 즉, $(𝑢, 𝜏_𝑖, 𝑣) ∈ 𝐸 → 𝑢 ∈𝑉_𝑗, 𝑣 ∈ 𝑉𝑘 ∧𝑗 ≠ 𝑘$ ▪ 이분 그래프(bipartite graph): 노드 유형이 2개인 다분 그래프
⭐ 다중 그래프 (Multiplex Graph)
▪ 그래프가 𝑘개의 레이어로 분해가 가능한 경우 ▪ 각 노드는 모든 레이어에 속함 ▪ 각 레이어는 하나의 관계와 연관, 해당 유형의 링크를 포함 ▪ 서로 다른 레이어를 연결하는 링크가 존재한다고 가정할 수 있음
예제: Transportation Network ▪ 각 노드는 도시, 각 레이어는 서로 다른 교통 수단을 표현 ▪ Intra-layer 링크는 교통 수단으로 연결된 도시들을 표현 (하나의 레이어 안의 링크) ▪ Inter-layer 링크는 도시 내에서 교통 수단을 바꾸는 가능성 (레이어 간의 링크)
ex. 각 노드는 서울, 대구, 대전 … 레이어 0=버스, 레이어 1=KTX, 레이어2=SRT
특징 정보
속성(Attribute)
▪ 속성 또는 특징(feature): 그래프와 관련된 정보 ▪ 노드-레벨 속성: $𝑋∈ℝ^{|𝑉|×𝑚}$ ▪ 이종 그래프: 각 노드 유형이고 유의 속성을 가진다고 가정할 수 있음 ▪ 경우에 따라 링크-레벨 속성을 고려하기도 함
정형화된 데이터(속성)를 비정형 데이터(그래프)와 같이 결합해서 분석하고자 할 때
→ Attributed graph, Multi-attribute graph
속성만 가지고도 분석할 수 있고, 그래프만 가지고도 분석할 수 있는데 이를 같이 분석할 수 있는 방법들이 개발되고 있음
1.2 그래프 기계학습
기계학습
▪ 특정 문제를 해결하기 위해 데이터를 학습하는 모델 설계 ▪ 풀고자 하는 문제의 유형에 따라 기계학습 모델 분류 ▪ 지도학습 및 비지도학습을 포함
그래프 기계학습
▪ 노드 분류(nodeclassification) ▪ 관계 예측(relation prediction) ▪ 군집화와 커뮤니티 검출(clustering and community detection) ▪ 그래프 분류, 회귀, 군집화(graph classification, regression, and clustering)
노드 분류
예제: Node Classification ▪ 소셜 네트워크 사용자 중 봇(bot)이 존재하는 경우 ▪ 모든 사용자를 수동으로 검사하는 것은 많은 비용을 필요로 함 ▪ 수동으로 레이블링(labeling)된 소수의 예제로 나머지를 분류 가능할까?
노드 분류 ▪ 목표: 훈련 데이터 $𝑉_{train} ⊂ 𝑉$가 주어졌을 때,모든 노드 𝑢∈𝑉의 레이블(label) $𝑦_𝑢$를 예측하는 것 ▪ 최근 그래프 기계학습 분야의 가장 인기 있는 문제 ▪ 많은 레이블링 된 노드를 포함하거나 연결성이 끊어진 그래프에 걸쳐 일반화를 요구하기도 함
(connected component가 여러 개 있는 disjoint graph 같은 경우)
예제: Node Classification ▪ 단백질 상호작용 그래프를 통한 단백질 기능 분류 (노드=단백질, 링크=상호작용) ▪ 하이퍼링크 또는 인용 그래프를 통한 문서 주제 분류
노드 분류 vs 지도 학습 ▪ 노드 분류는 지도학습의 단순 변형이 아님 (topological information, 구조 정보를 갖고 있음) ▪ 노드 분류는 독립적이지 않은 (종속성을 지닌) 분포를 따른다는 차이점 (연결이 있다=종속성O) ▪ 노드 분류 접근법 • 동질성(homophily): 인접 노드와 유사한 레이블을 가지는 경향 • 구조적 동등성(structural equivalence): 비슷한 로컬 구조를 가진 노드와 유사한 레이블을 가지는 경향
관계 예측
목표: 불완전한 링크 집합 $𝐸_{train} ⊂𝐸$가 주어졌을 때, $𝐸$ \ $𝐸_{train}$에 속하는 링크를 추론하는 것 ▪ 링크 예측(link prediction), 행렬 채우기(matrix completion) 문제와 연관 ▪ 연결성이 끊어진 그래프에 걸쳐 일반화를 요구하기도 함
예제: Relation Prediction ▪ 소셜 플랫폼의 컨텐츠 추천 ▪ 약물 부작용 예측 ▪ 관계형 데이터베이스 지식 추론
군집화와 커뮤니티 검출
▪ 목표: 그래프𝐺 =(𝑉,𝐸)가 주어졌을 때, 잠재 커뮤니티를 추론하는 것 ▪ 노드 분류, 관계 예측과 달리 완전한 비지도 학습의 그래프 버전
예제: Community Detection ▪ 인용 및 공저자 네트워크에서 밀집 연결 그룹 발견 ▪ 유전자 상호작용 네트워크에서 기능 모듈 발견 ▪ 금융거래 네트워크에서 부정 사용자 그룹 발견
그래프 분류, 회귀, 군집화
▪ 목표: 전체 그래프를 활용하는 분류, 회귀, 군집화 ▪ 그래프 내의 개별 노드, 링크 대신 각 그래프에 대한 독립적인 예측 분석 수행
예제: Graph Classification, Regression and Clustering ▪ 컴퓨터 프로그램의 구문과 데이터 흐름에 대한 그래프에서 악성 프로그램 감지하는 분류 모델 ▪ 분자 구조 그래프에서 분자의 독성 또는 용해도 예측하는 회귀 모델 ▪ 단일 그래프의 노드, 링크에 대한 예측 대신 전체 그래프에 대한 분류, 회귀, 군집화 가능