이 글은 GRL book을 번역 및 정리한 글입니다.

Chapter 1 : Introduction

그래프는 ubiquitous data structure이고, 복잡한 시스템을 설명하기 위한 범용적인 언어이다
가장 일반적으로 보자면, 그래프는 단순히 Object(Node)와 Object 간의 상호작용 (Edge)을 모아둔 것이라고 할 수 있다.

ex 1 소셜 네트워크를 그래프로 사용해서 인코딩하기 위해 노드로 개인을 나타내고, 
			엣지를 사용해 두 노드(개인)이 친구임을 나타낼 수 있다.

ex 2 생물학적으로 영역에서 그래프의 노드를 사용해 단백질을 나타낼 수 있고, 
			엣지를 사용해 단백질 간의 kinetic interaction 같은 다양한 생물학적 상호작용 나타낼 수 있다.

graph formalism의 힘은 node간의 관계와 그 일반성에 초점을 맞추는 데 존재한다. graph formalism이란 데이터를 graph의 형태로 수식화한다는 것을 의미한다.(node와 edge의 집합으로 나타내는 것)동일한 graph formalism을 사용해 SNS, 약물과 단백질의 상호작용, 분자 내 원자 간 상호작용 또는 통신 네트워크의 터미널 간 연결을 나타낼 수 있다.

그러나 그래프는 우아한 이론적 틀을 제공하는 것 이상의 역할을 한다.
실제 복잡한 시스템을 분석, 이해 및 학습하기 위해 구축 할 수있는 수학적 기반을 제공한다.

지난 25 년 동안 연구자들이 이용할 수있는 그래프 구조 데이터의 양과 질이 급격히 증가했다. 대규모 소셜 네트워킹 플랫폼, 인터랙션, food webs, 분자 그래프 구조 데이터베이스, 수십억 개의 상호 연결된 웹 지원 장치를 모델링하기위한 대규모 과학 이니셔티브의 출현으로 연구원이 분석 할 의미있는 그래프 데이터가 많이 존재한다. 문제는 이 데이터의 잠재력을 여는 것이다 ! (데이터를 잘 다뤄야한다는 뜻인듯)

이 책 (GRL book)은 ML을 사용하여 위와 같은 문제를 해결하는 방법에 관해 다룬다. 물론 ML이 그래프 데이터를 분석하는 유일한 방법은 아니지만, ML이 그래프 데이터를 모델링, 분석 및 이해하는 능력을 향상시키는데 중요한 역할을 한다는 것은 분명하다

1.1 What is a graph ?

그래프에 대한 ML을 얘기하기 전, "graph data"가 정확히 무엇을 의미하는지에 대해 좀 더 공식적인 설명이 필요하다. 공식적으로 G = (V, E)는 노드 V의 집합과 이들 사이의 엣지 E의 집합으로 정의된다. 노드 u에서 v로 가는 엣지는 E(u,v)라고 표현한다. 대부분 두 노드 사이에 최대 하나의 엣지가 있고, recurrent 엣지나 엣지의 방향성은 없는 단순한 그래프에만 관심이 있다.

그래프를 표현하는 편리한 방법은 인접행렬을 사용하는 것이다.

인접 행렬로 그래프를 표현하기 위해, 모든 노드가 인접 행렬의 특정 행과 열을 인덱싱하도록 그래프에서 노드를 정렬한다. 그런 다음에 행렬을 indexing해서 에지의 존재를 나타낼 수 있다.

E(u, v)가 존재하면 A [u, v] = 1, 그렇지 않으면 A [u, v] = 0

방향성이 없는 그래프(undirect graph)의 인접행렬 A는 대칭 행렬이 되고, 방향성 그래프인 경우 인접행렬A는 반드시 대칭행렬인 것은 아니다. 일부 그래프에는 인접 행렬의 항목에 임의의 weighted edge가 있을 수도 있다.( {0, 1}이 아닌 다른 값으로 ! )

예를 들어, protein-protein interaction graph의 가중치 에지는 두 단백질 간의 연관 강도를 나타낼 수 있다

1.1.1 Multi-relational Graphs

무방향 u그래프, 방향성 그래프, weighted graph 이외에도 다른 유형의 edge를 가진 그래프도 존재한다.

예를 들어, 약물끼리의 상호작용(drug-drug interaction)을 나타내는 그래프에서는 한 쌍의 약물을 동시에 복용할 때 발생할 수 있는 여러 부작용에 대해 서로 다른 edge를 원할 수 있따. 이러한 경우에는 edge 또는 relation type τ 을 포함하도록 edge notation을 확장할 수 있으며(ex. (u,τ,v)) ,edge type 하나당 인접행렬 $A_{\tau}$를 정의할 수 있다. 이러한 그래프를 다중 관계 그래프 (Multi-relational grpah) 라고 부르고, 전체 그래프는 인접 텐서 $A \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{R}| \times |\mathcal{V}| }$ 로 요약할 수 있다. ($\mathcal{R}$은 relation의 집합이다.) multi-relational graph의 두 가지 중요한 subset은 heterogeneous과 multiplex graphs이다.

Heterogeneous graphs

heterogeneous graph에서 node는 type도 포함되어 잇으므로, node set을 disjoint set $\mathcal{V} = \mathcal{V}_1 \cup \mathcal{V}_2 \cup ... \cup \mathcal{V}_k$ 로 분할할 수 있다. $(\mathcal{V}_i \cap \mathcal{V}_j = 0)$ heterogeneous graph의 edge는 일반적으로 node type에 따라 제약조건을 충족는데, 가장 일반적으로 특정 edge가 특정 유형의 node만 연결한다. $(u, \tau_i, v) \in \mathcal{E} \rightarrow u \in \mathcal{V}_k, v \in \mathcal{V}_k.$

heterogeneous biomedical graph

"단백질"을 유형을 나타내는 한 가지 유형의 노드
"약물"을 나타내는 한 가지 유형의 노드 
"질병"을 나타내는 한 가지 유형의 노드

'치료'를 나타내는 Edge는 "약물" 노드와 "질병" 노드 사이에서만 발생할 수 있음

다중 경로 그래프(multipartite graph)는 heterogeneous graph의 특수 케이스로, 서로 다른 타입의 노드사이에만 Edge가 존재할 수 있다. ${(u, \tau_i, v) \in \mathcal{E} \rightarrow u \in \mathcal{V}_k, v \in \mathcal{V}_k} \land {j \ne k}.$

Multiplex graphs

multiplex graph에서는 그래프가 일련의 k layer로 나뉠 수 있다고 가정한다.
모든 노드는 모든 layer에 속한다고 가정되며, 각 layer는 해당 layer의 layer 내 edge type을 나타내는 고유한 relation에 해당한다. 또한 layer간에 동일한 노드를 연결하는 layer간 edge type이 존재할 수 있다고 가정한다.

다중 교통 네트워크에서 각 노드는 도시를 나타낼 수 있고, 각 layer는 서로 다른 교통수단을 나타낼 수 있다.

layer내 edge는 다른 교통 모드로 연결된 도시를 나타내고, 
layer간 edge는 특정 도시 내에서 교통모드를 전환할 수 있는 가능성을 나타낼 수 있다.

1.1.2 Feature Information

마지막으로, 대부분 그래프와 관련된 속성 및 feature info도 존재한다.

대부분의 경우, 위 정보들은 real-value matrix $X \in \mathbb{R}^{|V| \times m}$ 을 사용해서 나타낼 수 있는 node level 속성으로, 여기서 노드의 순서는 인접 행렬의 순서와 일치한다고 가정한다.

Heterogeneous graph에서 일반적으로 서로 다른 유형의 node가 고유한 속성 유형을 가지고 있다고 가정한다.

드문 경우이긴하지만, discrete edge type외에 real-valued edge feature를 가진 그래프로 고려할 것 이며, 어떤 경웨는 real-valued feature를 전체 그래프와 연관시키기도 한다.

1.2 Machine learning on graphs

기계 학습은 본질적으로 problem-driven discipline이다.

우리는 특정 작업을 해결하기 위해 데이터에서 학습할 수있는 모델을 구축하려고한다. 머신 러닝 모델은 해결하려는 작업 유형에 따라 분류되는 경우가 많다. 입력 데이터 포인트가 주어진 목표 출력을 예측하는 것이 목표인 지도학습인지, 데이터에서 점의 군집과 같은 패턴을 추론하는 것이 목표인 비지도학습인지. 그래프를 사용한 기계 학습 또한 다르지 않지만, (비)지도의 일반적인 범주가 반드시 그래프에 유익하거나 유용하게 사용되는 것은 아니다.

이 섹션에서는 그래프 데이터에서 가장 중요하고 잘 연구 된 기계 학습 작업에 대한 간략한 개요를 제공한다. 앞으로 살펴 보 겠지만, "supervised" 문제는 그래프 데이터에서 인기가 있지만 그래프의 기계 학습 문제는 종종 기존 기계 학습 범주 간의 경계를 모호하게 만듭니다.→ 왜 .. ? 라벨이랑 i.i.d 가정때문에 !!

1.2.1 Node classification

수백만 명의 사용자가 포함 된 대규모 소셜 네트워크 dataset이 있다고 가정하자(이러한 사용자 중 상당수가 실제로 봇이라는 것을 알고 있다.) 이러한 봇을 식별하는 것은 여러 가지 이유로 중요 할 수 있다. 회사가 봇에 광고하는 것을 원하지 않거나, 봇이 실제로 소셜 네트워크의 서비스 약관을 위반할 수 있다.

모든 사용자를 수동으로 검사하여 bot인지 확인하는 것은 엄청나게 비효율적이므로, 이상적으로는 수동으로 label 이 지정된 적은 수의 예제만 제공하여 사용자를 봇이나 실제 사람으로 분류 할 수있는 모델을 갖고 싶다고 해보자.

이것은 node classification의 고전적인 예다.

여기서 목표는 모든 노드 $u \in \mathcal{V}$ 와 관련된 label $y_u$ (type or category or attribute)를 예측하는 것이다.

node classification은 특히 최근 몇 년 동안 그래프 데이터에서 가장 인기있는 기계 학습 작업중 하나일 것입니다. 소셜 네트워크를 넘어서는 노드 분류의 예에는 interactome에서 단백질의 기능을 분류하고 [Hamilton et al., 2017b] hyperlink 및 citation을 기반으로 문서의 주제를 분류하는 것이 포함됩된다 [Kipf and Welling, 2016a].

우리는 종종 single graph에서 노드의 매우 작은 하위 집합에 대해서만 label 정보가 있다고 가정한다. (예 : 수동으로 label이 지정된 작은 set의 예제에서 소셜 네트워크의 봇 분류 →semi-supervised learning). 그러나 많은 label이 지정된 노드를 포함하거나 연결이 끊어진 그래프에 대한 일반화가 필요한 노드 분류 인스턴스도 있습니다 (예 : 다른 종의 interactome에서 단백질의 기능 분류).

언뜻보기에 node classification은 standard supervised classification의 간단한 변형으로 보이지만, 중요한 차이가 있다. 가장 중요한 차이점은 그래프의 노드가 독립적이고 동일하게 분포되어 있지 않다는 것입니다 (i.i.d. 를 따르지 않음 !).

일반적으로 지도학습 모델을 구축 할 때, 각 데이터 포인트가 다른 모든 데이터 포인트와 통계적으로 독립적이라고 가정한다. 그렇지 않으면 모든 입력 포인트 간의 종속성을 모델링해야 할 수도 있기 때문이다. 또한 데이터 포인트가 동일한 분포에서 샘플링되었다고 가정한다. 그렇지 않으면 모델이 새로운 데이터 포인트로 일반화 될 것이라고 보장 할 방법이 없기 때문이다.. node classification는 이 i.i.d. 가정을 완전히 깨뜨린다. i.i.d의 set을 모델링하는 대신 대신 상호 연결된 노드 집합을 모델링한다.

실제로 가장 성공적인 노드 분류 접근 방식의 핵심은 노드 간의 연결을 명시적으로 활용하는 것이다.

1. "노드가 그래프에서 이웃과 속성을 공유하는 경향"인 "homophily"를 이용하는 것
		사람들은 "동일한 관심사" 또는 "인구 통계"를 공유하는 다른 사람들과 우정을 형성하는 경향이 있다.
		동질성 개념 (homophily)을 기반으로, 
		유사한 label을 그래프의 인접한 노드(이웃노드)에 할당하는 ML 모델을 구축할 수 있다.

2. 구조적 동등성(structural equivalence)과 같은 개념도 존재한다 -> "heterophily"
		이는 유사한 local neighborhood 구조를 가진 노드가 유사한 label을 가질 것이라는 생각
		다른 label을 가진 노드에 우선적으로 연결될 것이라고 생각하는 것 !

일반적으로 노드 분류 모델을 구축 할 때, 노드를 독립적인 데이터 포인트로 취급하는 대신 이러한 개념을 활용하고 노드 간의 관계를 모델링하고자한다.

Supervised or Semi-supervised ?

노드 분류의 비정형적 성질(atypical nature)로 인해 연구자들은 종종 이를 semi-supervied로 언급한다 [Yang et al., 2016]. 이 용어는 노드 분류 모델을 학습 할 때, 일반적으로 label이 지정되지 않은 모든 (예 : 테스트) 노드도 포함해서 전체 그래프에 액세스 할 수 있기 때문에 사용된다. 우리가 놓친 유일한 것은 테스트 노드의 label이다. 그러나 우리는 여전히 테스트 노드에 대한 정보 (예 : 그래프에서 이웃에 대한 지식)를 사용하여 훈련 중에 모델을 개선 할 수 있다. 이것은 label이 지정되지 않은 데이터 포인트가 훈련 중에 완전히 관찰되지 않는 일반적인 지도학습의 가정과는 다르다.

학습 중 레이블이 지정된 데이터와 레이블이없는 데이터를 결합하는 모델에 사용되는 일반적인 용어는 준지도 학습이므로, 이 용어가 노드 분류 작업과 관련하여 자주 사용된다는 것을 이해할 수 있다. 그러나 준지도 학습의 표준 공식화에는 여전히 i.i.d 가정이 필요하며, 이는 노드 분류적합하지 않다. 그래프의 기계 학습 작업은 표준 범주와는 쉽게 맞지 않는다!

1.2.2 Relation prediction

노드 분류는 그래프에서 다른 노드와의 관계를 기반으로 노드에 대한 정보를 추론하는데 유용하다.

그런데 만약 노드와의 관계에 대한 모든 정보를 알지못하면 어떻게 될까 ? 주어진 세포에 존재하는 단백질간의 상호작용 중 일부만 알고 있고, 우리가 알지 못하는 상호작용에 대해 추측하고 싶으면 어떻게하면 될까 ? ML 사용하면 추측할 수 있을까 ?

해당 작업은 특정 도메인에 다라 link prediction, graph completion, relational inference 같은 많은 이름으로 불린다. 여기서는 간단히 relational inference 라고 부르자. node classification과 함께 그래프 데이터를 사용하는 가장 인기있는 ML task 중 하나이며 실제로 많은 연구사례들이 있다. SNS 에서 사용자에게 콘텐츠를 추천하는 것, 약물에 대한 부작용 예측, 관계형 데이터베이스에서 새로운 사실을 추론하는 작업등이 존재한다.

relational inference를 위한 표준 setting은 node $\mathcal{V}$ 의 집합과 이러한 노드 $\mathcal{E}_{train} \in \mathcal{E}$ 사이의 불완전한 Edge 집합이 제공된다는 것이다. 해당 task의 목표는 주어진 부분 정보를 이용하여, 누락된 Edge (새로운 Edge)를 추론하는 것이다.

해당 task의 complexity는 우리가 조사하는 그래프 데이터의 유형에 따라 크게 달라진다.

"friendship" 관계만 encoding하는 SNS 와 같은 간단한 그래프에는 두 노드가 공유하는 이웃 수를 
기반으로 하는 간단한 휴리스틱만으로도 좋은 성능을 달성할 수 있다.[L¨u and Zhou,2011]

수백 개의 서로 다른 "생물학적 상호작용"을 인코딩하는 biomedical knowledge graphs 같은
보다 복잡한 multi-relational graph dataset에서는 복잡한 추론 전략이 필요하다. [Nickel et al., 2016]

node classification과 마찬가지로, relation predictio은 지도 및 비지도학습이라고 하는 기존 ML 범주의 경계를 모호하게 만들고 graph domain에 specific한 inductive bias을 필요로 한다. 또한, 노드 분류와 마찬가지로 단일 고정 그래프에서 예측이 이루어지거나, 여러 개의 분리된 그래프에서 관계를 예측해야하는 등 많은 변형이 존재한다.

1.2.3 Clustering and community detection

node classification과 relation prediction은 모두 그래프 데이터의 누락된 정보를 추론해야하며, 여러 면에서 이 두 작업은 지도 학습의 graph analogues다. 반면에 Community detection는 unsupervised clustering과 비슷한 그래프작업이다.

Google Scholar의 모든 인용 정보에 액세스 할 수 있고, 두 명의 연구자가 함께 논문을 공동 저술 한 경우 
이를 연결하는 협업 그래프를 만든다고 가정해보자. 이 네트워크를 조사한다면 모든 사람이 다른 모든 사람과 
동등하게 협력 할 가능성이있는 조밀한 "hairball" 을 찾을 수 있을까? 

그래프가 연구 분야, 기관 또는 기타 요인에 따라 함께 그룹화 된 서로 다른 노드 클러스터로 분리 될 
가능성이 더 크다. 

즉, 이 네트워크는 많은 실제 네트워크와 마찬가지로 노드가 동일한 커뮤니티에 속한 
노드와 에지를 형성 할 가능성이 훨씬 더 높은 커뮤니티 구조를 나타낼 것으로 예상된다. 

이것은 커뮤니티 탐지 작업의 기본이되는 일반적인 직관이며, 커뮤니티 탐지의 과제는 입력 그래프 G = (V, E) 만 주어진 잠재적인 커뮤니티 구조를 추론하는 것이다. 커뮤니티 탐지의 많은 실제 응용에는 유전자 상호 작용 네트워크에서 기능 모듈을 발견하고 [Agrawal et al., 2018] 금융 거래 네트워크에서 사기성 사용자 그룹을 발견하는 것이 포함된다 [Pandit et al., 2007].

1.2.4 Graph classification, regression, and clustering

그래프 데이터에 대한 인기있는 머신 러닝 애플리케이션의 마지막 클래스에는 전체 그래프에 대한 classification, regression, clustering problem이 포함된다.

예를 들어 분자의 구조를 나타내는 그래프가 주어지면, 분자의 독성 또는 용해도를 예측할 수있는 regression 모델을 구축 할 수 있다 [Gilmeret al., 2017]. 또는 구문과 데이터 흐름의 그래프 기반 표현을 분석하여 컴퓨터 프로그램이 악성인지 여부를 감지하는 분류 모델을 구축 할 수 있다 [Li et al., 2019].

이러한 그래프 분류 또는 회귀 응용 프로그램에서 우리는 그래프 데이터를 통해 학습하지만, 단일 그래프의 개별 구성 요소 (예 : 노드 또는 엣지)에 대한 예측을하는 대신 여러 다른 그래프와 목표로 구성된 데이터 세트가 제공된다. 각 그래프에 대해 독립적인 예측을 하는 것이다. 그래프 클러스터링과 관련된 작업에서 목표는 그래프 쌍 간의 유사성에 대한 감독되지 않은 측정 값을 학습하는 것입니다.

그래프의 모든 기계 학습 작업 중에서 그래프 회귀 및 분류는 아마도 표준 지도 학습의 가장 직접적인 유사체 일 것이다. 각 그래프는 i.i.d. label과 연결된 데이터 포인트 및 목표는 label이 지정된 훈련 포인트 세트를 사용하여 데이터 포인트 (예 : 그래프)에서 label로의 매핑을 학습하는 것이다. 유사한 방식으로 그래프 클러스터링은 그래프 데이터에 대한 비지도 클러스터링의 간단한 확장이다. 그러나 이러한 그래프 수준 작업의 과제는 각 데이터 포인트 내의 관계형 구조를 고려하는 유용한 기능을 정의하는 방법입니다

Reference

https://www.cs.mcgill.ca/~wlh/grl_book/