GNN

[GNN] Lecture 1 : 그래프 소개

Ojungii 2024. 9. 29. 00:05

 

그래프 모델링

  • 복잡한 시스템을 표현할 수 있는 범용적인 자료구조
  • 시스템을 분석하고 이해할 수 있는 수학적 기초 제공
  • 노드(node): 객체의 집합
  • 링크(link): 객체들 간의 상호 작용

그래프 (Graph)

  • 𝐺 = (𝑉, 𝐸) 로 표현
  • 노드의 집합 𝑉
  • 링크의 집합 𝐸 = {(𝑢, 𝑣) |𝑢 ∈ 𝑉, 𝑣 ∈ 𝑉}

단순 그래프 (Simple Graph)

  • 두 노드 사이의 링크는 최대 1개
  • 같은 노드를 연결하는 링크는 없음
  • 모든 링크는 방향성이 없음(undirected), 즉 (𝑢, 𝑣 )∈ 𝐸 ↔( 𝑣, 𝑢) ∈ 𝐸

인접 행렬 (Adjacency Matrix)

  • 그래프를 표현하는 편리한 방법
  • $𝑨 ∈ ℝ^{ |𝑉| × |𝑉|}$ 로 표현
  • 모든 노드를 행(row)과 열(row)에 대응하여 링크 표현
  • 𝑨[ 𝑢, 𝑣 ]= 1 if (𝑢, 𝑣) ∈ 𝐸 and 𝑨[ 𝑢, 𝑣] = 0 otherwise
  • 방향성이 없으면 A는 대칭행렬
  • 가중치가 있으면 A의 성분은 {0,1} 대신 실수값

 

다중-관계 그래프 (Multi-relational Graph)

  • 그래프 내에서 다양한 관계 유형(relational type)의 링크를 고려하는 경우
  • 링크에 유형을 추가하여 표현: (𝑢, 𝜏, 𝑣) ∈ 𝐸
  • 각 관계 유형 별 인접행렬 정의: $𝑨_𝜏$
  • 관계의 집합: 𝑅
  • 전체 그래프를 요약하는 인접텐서(adjacency tensor) 정의: $𝑨 ∈ ℝ^{ |𝑉|×| 𝑅| × |𝑉|}$
  • 종류 : 이종 그래프(heterogeneous graph), 다중 그래프(multiplex graph)

 

이종 그래프 (Heterogeneous Graph)

  • 노드에도 유형(type)이 있는 경우
  • 특정 링크는 특정 유형의 노드들 사이에서만 연결
  • 예제: Biomedical Graph
    • 단백질, 약물, 질병을 나타내는 노드 유형이 가능
    • “치료” 링크: 약물 노드와 질병 노드 사이의 연결
    • “부작용” 링크: 두 약물 노드 사이의 연결

예제: Multipartite Graph

  • 다분 그래프: 서로 다른 유형의 노드끼리만 연결이 가능한 그래프
  • 이분 그래프(bipartite graph): 노드 유형이 2개인 다분 그래프

 

다중 그래프 (Multiplex Graph)

  • 그래프가 𝑘개의 레이어로 분해가 가능한 경우
  • 각 노드는 모든 레이어에 속함
  • 각 레이어는 하나의 관계와 연관, 해당 유형의 링크를 포함
  • 서로 다른 레이어를 연결하는 링크가 존재한다고 가정할 수 있음
  • 예제: Transportation Network
    • 각 노드는 도시, 각 레이어는 서로 다른 교통 수단을 표현
    • Intra-layer 링크는 교동 수단으로 연결된 도시들을 표현
    • Inter-layer 링크는 도시 내에서 교통 수단을 바꾸는 가능성

속성 (Attribute)

  • 속성 또는 특징(feature): 그래프와 관련된 정보
  • 이종 그래프: 각 노드 유형이 고유의 속성을 가진다고 가정할 수 있음
  • 경우에 따라 링크-레벨 속성을 고려하기도 함

 

그래프 기계학습

  • 노드 분류(node classification)
  • 관계 예측(relation prediction)
  • 군집화와 커뮤니티 검출(clustering and community detection)
  • 그래프 분류, 회귀, 군집화(graph classification, regression, and clustering)

노드 분류 vs 지도학습

  • 노드 분류는 지도학습의 단순 변형이 아님
    • 구조에 대한 정보를 가지고 있기 때문에 접근법이 달라짐.
  • 노드 분류는 독립적이지 않은 (종속성을 지닌) 분포를 따른다는 차이점
    • 지도학습은 기본적으로 독립적으로 생각하고, 노드 분류는 시작부터 구조적 종속을 가지고 있음.
  • 노드 분류 접근법
    • 동질성(homophily): 인접 노드와 유사한 레이블을 가지는 경향
    • 구조적 동등성(structural equivalence): 비슷한 로컬 구조를 가진 노드와 유사한 레이블을 가지는 경향

 

관계예측

  • 목표: 불완전한 링크 집합에서 속하는 링크를 추론하는 것
  • 링크 예측(link prediction), 행렬 채우기(matrix completion) 문제와 연관
  • 연결성이 끊어진 그래프에 걸쳐 일반화를 요구하기도 함
  • 예제: Relation Prediction
    • 소셜 플랫폼의 컨텐츠 추천
    • 약물 부작용 예측
    • 관계형 데이터베이스 지식 추론

 

군집화와 커뮤니티 검출

  • 커뮤니티 검출
    • 목표: 그래프가 주어졌을 때, 잠재 커뮤니티를 추론하는 것
    • 노드 분류, 관계 예측과 달리 완전한 비지도 학습의 그래프 버전
  • 예제: Community Detection
    • 인용 및 공저자 네트워크에서 밀집 연결 그룹 발견
    • 유전자 상호작용 네트워크에서 기능 모듈 발견
    • 금융 거래 네트워크에서 부정 사용자 그룹 발견

 

그래프 분류, 회귀, 군집화

  • 목표: 전체 그래프를 활용하는 분류, 회귀, 군집화
  • 그래프 내의 개별 노드, 링크 대신 각 그래프에 대한 독립적인 예측 분석 수행
  • 예제: Graph Classification, Regression and Clustering
    • 컴퓨터 프로그램의 구문과 데이터 흐름에 대한 그래프에서 악성 프로그램 감지하는 분류 모델
    • 분자 구조 그래프에서 분자의 독성 또는 용해도 예측하는 회귀 모델
    • 단일 그래프의 노드, 링크에 대한 예측 대신

 

 

 

 

 

출처 :

- William L. Hamilton. (2020). Graph Representation Learning.

- 충남대학교 임성수 교수님 그래프 기계학습 강의

 

저작자표시 비영리 변경금지