Post

CS224W - (1) Introduction; Machine Learning for Graphs

Posted Updated
network

network

By Jay Han
views 19 min read




Introduction

왜 그래프를 사용할까요?

그래프는 관계나 상호작용이 있는 엔티티를 설명하고 분석하기 위한 일반적인 언어입니다. 그래프로 나타낼 수 있는 데이터는 많습니다. 컴퓨터 네트워크, 질병 경로, 지하철 노선도, 소셜 네트워크, 인터넷 등 수없이 많습니다. 그러면 우리는 이런 관계형 구조를 활용해서 더 나은 예측을 생성할 수 있을까요? 보통 복잡한 도메인은 관계형 그래프 (relational graph) 로 표현할 수 있는 풍부한 관계 구조로 되어 있습니다. 관계를 명시적으로 모델링함으로써 더 나은 성능을 얻을 수 있게 되죠.

최근 뉴럴 네트워크를 사용한 성공적인 결과는 대부분 순서가 있는 데이터나 격자형 데이터였습니다. 하지만 모든 데이터를 순서나 격자 형태로 나타낼 수 없기 때문에 지금의 뉴럴 네트워크를 넘어서는 무언가가 필요한 상황이었죠. 그 무언가가 바로 그래프입니다. 최근 ML 분야에서도 매우 뜨거운 반응을 일으키고 있습니다.

왜 그래프를 사용한 딥러닝은 어려울까요?

보통 네트워크는 복잡한 형태를 보이고 있습니다. 네트워크는 임의의 크기와 복잡한 위상 구조를 갖죠. 격자형 데이터가 공간 지역성(spatial locality)을 갖는 것과는 사뭇 다릅니다. 또한 고정된 노드 순서나 기준점을 갖고 있지 않습니다. 종종 변화무쌍하고 멀티 모달 피처(multi-modal feature)를 갖습니다.

그래프 뉴럴 네트워크(Graph Neural Network, GNN)와 같은 그래프를 사용한 ML 모델은 입력값으로 네트워크를 갖습니다. 예측값으로는 노드의 레이블이나 새로운 링크, 또는 생성된 그래프나 서브그래프를 갖습니다.

GNN에서 각각의 노드는 연산 그래프(computation graph) 를 정의합니다. 그래프에서 각각의 엣지(edge)는 변환 함수(transformation function)나 집계 함수(aggregation function)입니다. 노드는 뉴럴 네트워크를 이용해 자신의 이웃 노드의 정보를 집계합니다. 네트워크에서 이웃은 연산 그래프를 정의합니다. 아까 각 노드를 연산 그래프를 정의한다고 했는데, 바로 그 노드의 이웃을 기반에 두고 계산 그래프를 정의합니다.

보통 지도 학습을 사용하는 ML 사이클에서 가장 중요한 요소는 피처입니다. 하지만 그래프를 이용한 ML은 표현 학습(representation learning) 을 통해 피처를 자동으로 학습합니다. 위 그림처럼 노드를 $d$ 차원 임베딩에 매핑하여 네트워크 안에서 유사한 노드가 서로 가깝게 위치하도록 합니다.

Application of Graph ML

전통적인 그래프 ML 태스크

그래프 ML을 이용한 태스크는 크게 네 개의 레벨로 나눌 수 있습니다.

  • 노드 레벨
  • 커뮤니티 (서브그래프) 레벨
  • 엣지 레벨
  • 그래프 레벨 / 그래프 생성

전통적인 그래프 ML 태스크를 나열하자면 다음과 같습니다.

  • 노드 분류 (Node classification) : 노드의 특성 예측
    • 예) 온라인 사용자 / 아이템의 카테고리를 예측
  • 링크 예측 (Link prediction) : 두 노드 사이에 누락된 링크가 있는지 예측
    • 예) 지식 그래프 완성
  • 그래프 분류 (Graph classification) : 서로 다른 그래프를 카테고리화
    • 예) 분자 특성 예측
  • 클러스터링 (Clustering) : 노드들이 커뮤니티를 형성하는지 탐색
    • 예) 소셜 서클 감지
  • 기타 태스크
    • 그래프 생성 (Graph generation) : 신약 발굴
    • 그래프 진화 (Graph evolution) : 물리 시뮬레이션

그래프 ML 태스크 예시

노드 레벨 태스크

노드 레벨의 ML 태스크로는 단백질 접힘 (protein folding) 사례가 있습니다. 아미노산 서열을 기반으로 단백질의 3D 구조를 예측합니다. 한때 화제가 되었던 AlphaFold가 바로 단백질 접힘 구조를 예측하는 모델입니다. AlphaFold에서는 노드는 단백질 서열의 아미노산을, 엣지는 아미노산 사이의 근접성을 나타냅니다.

엣지 레벨 태스크

엣지 레벨의 ML 태스크의 가장 대표적인 예시는 추천 시스템입니다. 이 경우 사용자와 아이템을 노드로 갖고 사용자와 아이템 사이의 상호작용을 엣지로 갖게 됩니다. 그래프를 모델링하여 사용자가 좋아할 만한 아이템을 추천해주게 되죠. 이때 노드를 임베딩하여 활용할 수도 있습니다.

다른 예시는 약의 부작용 예측입니다. 한 쌍의 약물이 주어졌을 때 발생할 수 있는 부작용을 예측하는 경우입니다. 약과 단백질을 노드로 하고 그 상호작용을 엣지로 가지는데, 서로 다른 두 약물 사이에 누락된 링크가 어떤 특성을 갖는지 예측하게 됩니다.

서브그래프 레벨 태스크

서브그래프 레벨의 ML 태스크로는 교통량 예측이 있습니다. 도로 네트워크를 그래프로 보는 건데요. 이때 도로 구간을 노드로 하고 도로 구간 사이의 연결을 엣지로 간주합니다. 마지막으로 도착 시간 (ETA) 을 예측하는 것이 목표입니다. 우리가 자주 사용하는 구글 맵에서도 이 방법을 활용하고 있습니다.

그래프 레벨 태스크

마지막으로 그래프 레벨의 ML 태스크 예시로는 신약 발굴이 있습니다. 항생제는 매우 작은 분자 그래프입니다. 그래프로 나타냈을 때 원자가 노드가 되고 화학 결합이 엣지가 됩니다. 신약 발굴의 경우 그래프 분류 문제와 그래프 생성 문제로 나눌 수 있는데, 우선 그래프 분류 문제는 후보 물질 목록에서 가장 가능성 높은 분자를 예측하게 됩니다.

반면 그래프 생성 문제로 생각한다면 새로운 분자 구조를 생성하게 되죠.

물리 시뮬레이션 문제도 그래프를 통해 해결할 수 있습니다. 각각의 입자를 노드로, 입자 사이의 상호작용을 엣지로 둘 때, 그 그래프가 앞으로 어떻게 진화하는지 예측하는 문제로 치환할 수 있습니다. 일종의 그래프 진화 문제로 푸는 거죠.

Choice of Graph Representation

보통 네트워크는 세 가지 요소를 가지고 있습니다. 바로 노드, 엣지, 그래프입니다. 각각을 다른 용어로 쓰는 경우도 있지만 세 가지 요소라는 점은 변함이 없습니다. 실세계의 환경을 그래프로 나타낸다면 어떤 객체는 노드가 됩니다. 그리고 객체 사이의 상호작용은 엣지가 되죠. 객체와 객체 사이의 상호작용을 통틀어서 하나의 시스템이 이루어지고, 그 시스템은 그래프가 됩니다. 노드를 $N$, 엣지를 $E$로 나타낸다면 그래프는 보통 $G(N, E)$로 나타냅니다.

어떤 도메인에서 문제를 맞닥뜨렸을 때 가장 중요한 것은 그 도메인과 문제를 적합한 네트워크로 표현하는 것입니다. 어떻게 표현하느냐에 따라 이후 모델을 생성했을 때 성능이 크게 달라집니다. 이번 섹션에서는 그래프를 표현할 때 어떻게 해야 하는지 알아보겠습니다.

Directed vs Undirected

그래프를 표현할 때 방향 여부는 매우 중요합니다. 방향이 없는 그래프를 무방향 그래프 (undirected graph), 방향이 있는 그래프를 방향 그래프 (directed graph) 라고 합니다. 무방향 그래프는 엣지에 방향이 없고 대칭적인 상호관계를 나타냅니다. 페이스북에서 친구 관계를 예로 들 수 있습니다. 반대로 방향 그래프는 모든 엣지에 방향이 있습니다. 트위터의 팔로잉을 그래프로 나타내면 방향 그래프가 됩니다.

Heterogeneous Graphs

수많은 그래프 중에서 대부분을 차지하는 이종 그래프 (Heterogeneous graph) 는 서로 다른 종류의 노드와 엣지를 갖는 그래프입니다. 이종 그래프는 다음과 같이 정의합니다. \(G = (V, E, R, T)\)

  • 여러 노드 종류를 포함하는 노드 $v_i \in V$
  • 여러 관계 종류를 포함하는 엣지 $(v_i, r, v_j) \in E$
  • 노드 종류 $T(v_i)$
  • 관계 종류 $r \in R$

Node Degrees

Node degree는 노드에 인접한 엣지 수를 의미합니다. 어떤 노드 $i$의 node degree를 $k_i$라고 나타낼 때 모든 노드의 평균 node degree는 다음과 같습니다.

\[\bar{k} = \left<k\right> = \frac{1}{N} \sum^N_{i=1} k_i = \frac{2E}{N}.\]

방향 그래프는 모든 노드에 대해서 in-degree와 out-degree를 정의할 수 있습니다. 어떤 노드로 향하는 엣지의 수가 in-degree, 어떤 노드에서 나가는 엣지의 수가 out-degree입니다. 어떤 노드의 총 degree는 in-degree와 out-degree의 합과 같습니다. 따라서 다음 성질을 항상 만족합니다.

  • $\bar{k}^\text{in} = \bar{k}^\text{out}$
  • $\bar{k} = \frac{E}{N}$

Bipartite Graph

이분 그래프 (Bipartite graph) 는 노드를 독립적인 두 개의 노드 집합 $U$, $V$로 나눌 수 있고 $U$에 있는 노드가 $V$에 있는 노드에 연결된 그래프를 의미합니다.

Adjacency Matrix

인접 행렬 (Adjacency matrix) 은 그래프를 나타내는 편리한 방법입니다. 행과 열이 노드의 개수인 행렬을 만들어서 두 노드가 연결되어 있는 경우 1, 연결되지 않은 경우 0으로 구성합니다.

\[A \in \mathbb{R}^{|V| \times |V|} \text{ such that } A[u, v] = 1 \text{ if } (u, v) \in E \text{ and } A[u, v]= 0 \text{ otherwise.}\]

대부분 경우에서 인접 행렬은 매우 희소(sparse)합니다.

\[E << E_\text{max} \quad \text{or} \quad \bar{k} << N-1.\]

More Types of Graphs

위에서 다룬 그래프를 제외하고 다른 그래프들에 대해서도 알아보겠습니다.

우선 가중치가 없는 일반적인 그래프입니다. 연결되어 있는 모든 엣지의 가중치가 동일하고 자기 자신을 향하는 엣지가 없는 그래프로 가중치가 없는 일반적인 그래프는 다음의 성질을 갖고 있습니다.

  • $A_{ii} = 0$ for all $i$
  • $A_{ij} = A_{ji}$
  • $E = \frac{1}{2} \sum^N_{i, j=1} A_{ij}$
  • $\bar{k} = \frac{2E}{N}$

가중치가 있는 그래프, 즉 가중 그래프는 자기 자신을 향하는 엣지가 없고 엣지마다 고유의 가중치를 갖고 있습니다.

  • $A_{ii} = 0$ for all $i$
  • $A_{ij} = A_{ji}$
  • $E = \frac{1}{2} \sum^N_{i, j=1} nonzero(A_{ij})$
  • $\bar{k} = \frac{2E}{N}$

어떤 노드의 엣지가 자기 자신을 향하기도 하는 self-edges (self-loops) 그래프는 다음의 성질을 갖습니다.

  • $A_{ii} \ne 0$ for some $i$
  • $A_{ij} = A_{ji}$
  • $E = \frac{1}{2} \sum^N_{i, j=1, i \neq j} A_{ij} + \sum^N_{i=1} A_{ii}$

마지막으로 어떤 노드에서 다른 노드로 여러 개의 엣지가 연결되어 있기도 한 멀티 그래프도 있습니다.

  • $A_{ii} = 0$ for all $i$
  • $A_{ij} = A_{ji}$
  • $E = \frac{1}{2} \sum^N_{i, j=1} nonzero(A_{ij})$
  • $\bar{k} = \frac{2E}{N}$

Connectivity

노드 사이의 연결 여부를 이용해서 그래프를 나타낼 수 있습니다. 우선 방향이 없는 그래프로 가정하고 해당 그래프에 있는 모든 노드가 서로 연결되어 있는 그래프를 연결 그래프 (connected graph) 라고 합니다.

당연하게도 반대 경우도 있습니다. 비연결 그래프 (disconnected graph)는 두 개 이상의 연결된 컴포넌트로 구성됩니다. 컴포넌트 가운데 가장 큰 컴포넌트를 거대 컴포넌트 (giant component) 라고 합니다. 그리고 어떤 노드와도 연결되어 있지 않은 노드를 고립 노드 (isolated node) 라고 합니다.

방향 그래프는 연결의 강약을 이용해서 그래프를 표현할 수 있습니다. 강한 연결 그래프 (strongly connected directed graph) 는 모든 노드가 연결되어 있고 양방향으로 연결되어 있는 그래프를 말합니다. 만약 노드 A로부터 노드 B가 연결되어 있다면, 반대로 노드 B로부터 노드 A도 연결되어 있습니다. 방향 그래프에서 일반적인 연결 그래프는 약한 연결 그래프 (weakly connected directed graph) 라고 합니다.

비방향 그래프에서 비연결 그래프를 이야기할 때 컴포넌트를 다루듯 방향 그래프에서도 비슷한 개념을 다룰 수 있습니다. 강한 연결 컴포넌트 (Strongly connected components, SCCs) 는 양방향 연결되어 있는 노드로 구성된 컴포넌트를 의미합니다.

CS224W
cs224w


This post is licensed under CC BY 4.0 by the author.