General Notation

denote	meaning	note
$\cal{G} = (\cal{V, E})$	formal definition of graph	calligraphic font used
$\cal{V}$	a set of nodes	node = vertex
$\cal{E}$	a set of edges, edges between nodes	$\therefore$ edge needs coordinate-likely information to denote each one
$u \in \cal{V}$	a node of node set $\cal{V}$	normally node denoted by $\cal{u}$ or $\cal{v}$
$(u, v) \in \cal{E}$	when u, v in $\cal{V}$, it means an edge from u to v vice versa	check it is direct graph or not

1. Introduction

그래프는 어디에나 있는 데이터 구조이며 복잡한 시스템을 묘사하는 일반적인 언어이다. 대부분의 일반적인 관점에서 그래프는 정점(node)들과 그 상호작용 집합인 간선(edge)와 같은 단순한 객체들의 집합이었다. 예를 들어 사회 관계망을 그래프로 부호화(encode) 하는 경우 우리는 아마 개인을 표현하기 위해 정점을, 개인이 친구임을 표현하기 위해서는 간선를 사용할 것이다. 생물학 도메인에서는 그래프의 정점을 단백질을 표현하는데 사용할 수 있으며 간선은 다양한 생물학적 연관관계; 예를들어 단백질 사이의 운동관계를 표현하는데 사용할 수 있다.


Zachary Karate Club Network

위는 유명한 자카리 가라테 클럽 네트워크로 가라테 클럽 멤버 사이의 친밀도를 나타내는 사회 관계망 그래프이며 웨인 W 자카리가 190-1972 사이에 연구한 결과다. 간선은 두 개인이 클럽 바깥에서 아는 사이이면 연결된다. 연구동안 클럽은 0번과 33번 정점을 중심으로 양분되었는데 연구자는 어떤 정점(회원)이 어디로 나뉠지 그래프 구조를 기반으로 정확하게 예측한 바 있다.

그래프 형식의 강점은 관계와 (개별 지점 대신에) 각 지점 ’사이’에 초점을 맞추는데 있으며 그 일반화 능력을 빠트릴 수 없다. 같은 그래프 형태는 사회 관계망, 약물과 단백질 사이의 상호작용, 원자와 분자간 상호작용 등… 을 표현할 수 있다. 다시말해, 정점을 정의하는것이 무엇이냐에 따라 같은 그래프도 다르게 사용될 수 있다.

1.1 What is a graph

그래프에서의 머신러닝을 논하기 이전에 ’그래프 데이터’가 정확히 무엇을 의미하는지 나타내는 공적인 표현에 대해 조금 알아둘 필요가 있다. 공식적으로, 그래프 $\cal{G} = (\cal{V, E})$ 는 정점의 집합인 $\cal{V}$ 와 정점 사이의 간선의 집합인 $\cal{E}$ 로 정의된다. 정점 $u \in \cal{V}$ 와 $v \in \cal{V}$ 로 이루어진 간선은 다음과 같이 정의한다: $(u, v) \in \cal{E}$. 많은 경우에 (우리는) 단순 그래프 (simple graph) 만을 고려하는데, 단순 그래프는 대부분 하나의 간선이 각 정점의 쌍 사이에 존재하는 집합으로 어떤 간선도 정점 하나에 존재하지는 않는 그래프이다.

그래프를 편리하게 표현하는 방법은 adjacency matrix (인접행렬) $A \in \mathbb{R}^{|\cal{V}|*|\cal{V}|}$ 를 사용하는 방법이다. ¹ $A$ 로 그래프를 표현하기 위해서는 그래프의 정점을 순서대로 배열함으로써 모든 정점의 색인들(indexes)이 인접행렬 $A$의 각각의 행과 열이 되게 해야 한다. 그렇게 하면 다음 조건의 행렬에서의 모든 간선의 존재를 표현할 수 있다: $A[u, v] = 1$ if $(u,v) \in \cal(E)$ and $A[u, v] = 0$ otherwise ² ³ 만약 그래프가 방향이 없는 간선 (undirected edge)으로만 구성된 경우 인접행렬 $A$는 대칭행렬이 된다. 하지만 간선들이 방향성이 있다면 (edge direction matters) $A$는 대칭이지 않아도 된다. 몇몇 그래프들은 가중치를 가질 수도 있는데 (weighted edges) 그 경우 그래프에 기재되는 값이 {0, 1}이 아닌 임의의 실수가 된다. 예를 들어 가중 그래프 중 단백질간 상호작용 그래프는 두 단백질 사이의 연관된 힘을 나타내는 그래프로 쓰일 수 있다.

1.1.1 Multi-relational Graph

multi-relational graph는 방향이 있는 간선, 없는 간선, 가중치가 있는 간선을 넘어 다양한 종류의 간선이 있는 그래프를 고려한다. 예를 들어, 약물과 약물의 상호작용 그래프에서 각 간선이 두 약물을 동시에 복용할 때 발생할 수 있는 부작용에 대하여 서로 두가지의 간선이 필요할 수 있다. 이 예에서 간선 표기법을 확장하여 다음을 표현할 수 있다:

간선 또는 관계 유형 $\tau$, ($u$, $\tau$, $v$) $\in$ $\cal{E}$, 그리고 하나의 인접행렬 $A_{\tau}$ 를 간선 종류마다 정의할 수 있다. 이러한 그래프를 multi-relational 하다고 말하며 전체의 그래프는 인접 텐서 $\cal{A} \in \mathbb{R}^{\cal{|V| * |R| * |V|}}$ 로 정의된다. ⁴ multi-relational graph의 두가지 중요한 부분집합은 1. heterogenous, 2. multiplex 그래프로 나뉜다. tau ($\tau$)는 간선의 타입을 의미하며, 간선의 종류에는 위에 기술한 바와 같이 방향이 있는 것, 없는 것, 가중치가 있는 것 등이 포함된다. 이렇게 간선의 종류가 달라지면 Adjacency Matrix $A$도 따로 정의해야 한다.

Heterogeneous graph

Heterogeneous graph에서, 정점들은 type에 물들어있다. 다시 말해, 정점 집합의 일부는 다음과 같이 해체될 수 있다: $\cal{V = V_1} \cup \cal{V_2} \cup \dots \cup \cal{V_k}$ where $\cal{V_i} \cap \cal{V_j} = \emptyset, \forall_i \neq j$. heterogeneous graph의 간선은 일반적으로 제한이 걸려있는데 이는 집합 $\cal{V}$가 서로 겹치지 않는 부분집합 $\cal{V_1}$ 부터 $\cal{V_k}$ ⁵ 의 합집합이다.

Footnotes

$\mathbb{R}$ : Real number set ( $\mathbb{R}$ in TeX)↩︎
$A[u, v] = 1$: $u$와 $v$ 사이에 간선이 존재할 때 ($A[u, v] = 0$: 존재하지 않을 때)↩︎
$(u, v)$ 가 그래프 안에 있고 간선 집합 $\cal{E}$ 안에 존재할 때 $A$의 위치 $(u, v)$에 올 수 있는 값은 간선이 존재하거나 (1) 존재하지 않는 (0) 두 가지 경우의 수 뿐이다. ↩︎
행렬 A가 실수 집합 V, R의 계량수(cardinality, cardinal number)로 결정되는 차원으로 구성된다.↩︎
$\forall$ : forall↩︎

--- title-block-banner: true title: Graph 101 (작성중) subtitle: Graph Representation Learning (2020, William L. Hamilton) description: 읽으며 도움이 될만한 내용 기록 toc: false sidebar: false categories: - graph reference-location: document date: 2023/03/08 --- ## General Notation | denote | meaning | note | | :--: | :------ | :------- | | $\cal{G} = (\cal{V, E})$ | formal definition of graph | calligraphic font used | | $\cal{V}$ | a set of nodes | node = vertex | | $\cal{E}$ | a set of edges, edges between nodes | $\therefore$ edge needs coordinate-likely information to denote each one | | $u \in \cal{V}$ | a node of node set $\cal{V}$ | normally node denoted by $\cal{u}$ or $\cal{v}$ | | $(u, v) \in \cal{E}$ | when u, v in $\cal{V}$, it means an edge from u to v vice versa | check it is direct graph or not | # 1. Introduction 그래프는 어디에나 있는 데이터 구조이며 복잡한 시스템을 묘사하는 일반적인 언어이다. 대부분의 일반적인 관점에서 그래프는 정점(`node`)들과 그 상호작용 집합인 간선(`edge`)와 같은 단순한 객체들의 집합이었다. 예를 들어 사회 관계망을 그래프로 부호화(encode) 하는 경우 우리는 아마 개인을 표현하기 위해 정점을, 개인이 친구임을 표현하기 위해서는 간선를 사용할 것이다. 생물학 도메인에서는 그래프의 정점을 단백질을 표현하는데 사용할 수 있으며 간선은 다양한 생물학적 연관관계; 예를들어 단백질 사이의 운동관계를 표현하는데 사용할 수 있다. |<img a="Zachary Karate Club Network" src="https://github.com/dotpyo/archive/assets/60145951/344c9b97-9d0d-46c6-89fa-c3cbb19b3ba2" width="100%" > |:-:| |Zachary Karate Club Network| 위는 유명한 자카리 가라테 클럽 네트워크로 가라테 클럽 멤버 사이의 친밀도를 나타내는 사회 관계망 그래프이며 웨인 W 자카리가 190-1972 사이에 연구한 결과다. 간선은 두 개인이 클럽 바깥에서 아는 사이이면 연결된다. 연구동안 클럽은 0번과 33번 정점을 중심으로 양분되었는데 연구자는 어떤 정점(회원)이 어디로 나뉠지 그래프 구조를 기반으로 정확하게 예측한 바 있다. 그래프 형식의 강점은 관계와 (개별 지점 대신에) 각 지점 '사이'에 초점을 맞추는데 있으며 그 일반화 능력을 빠트릴 수 없다. 같은 그래프 형태는 사회 관계망, 약물과 단백질 사이의 상호작용, 원자와 분자간 상호작용 등... 을 표현할 수 있다. 다시말해, 정점을 정의하는것이 무엇이냐에 따라 같은 그래프도 다르게 사용될 수 있다. ## 1.1 What is a graph 그래프에서의 머신러닝을 논하기 이전에 '그래프 데이터'가 정확히 무엇을 의미하는지 나타내는 공적인 표현에 대해 조금 알아둘 필요가 있다. 공식적으로, 그래프 $\cal{G} = (\cal{V, E})$ 는 정점의 집합인 $\cal{V}$ 와 정점 사이의 간선의 집합인 $\cal{E}$ 로 정의된다. 정점 $u \in \cal{V}$ 와 $v \in \cal{V}$ 로 이루어진 간선은 다음과 같이 정의한다: $(u, v) \in \cal{E}$. 많은 경우에 (우리는) 단순 그래프 (*simple graph*) 만을 고려하는데, 단순 그래프는 대부분 하나의 간선이 각 정점의 쌍 사이에 존재하는 집합으로 어떤 간선도 정점 하나에 존재하지는 않는 그래프이다. 그래프를 편리하게 표현하는 방법은 ***adjacency matrix (인접행렬)*** $A \in \mathbb{R}^{|\cal{V}|*|\cal{V}|}$ 를 사용하는 방법이다. ^[$\mathbb{R}$ : Real number set (`$\mathbb{R}$` in TeX)] $A$ 로 그래프를 표현하기 위해서는 그래프의 정점을 순서대로 배열함으로써 모든 정점의 색인들(indexes)이 인접행렬 $A$의 각각의 행과 열이 되게 해야 한다. 그렇게 하면 다음 조건의 행렬에서의 모든 간선의 존재를 표현할 수 있다: $A[u, v] = 1$ if $(u,v) \in \cal(E)$ and $A[u, v] = 0$ otherwise ^[$A[u, v] = 1$: $u$와 $v$ 사이에 간선이 존재할 때 ($A[u, v] = 0$: 존재하지 않을 때)] ^[$(u, v)$ 가 그래프 안에 있고 간선 집합 $\cal{E}$ 안에 존재할 때 $A$의 위치 $(u, v)$에 올 수 있는 값은 간선이 존재하거나 (1) 존재하지 않는 (0) 두 가지 경우의 수 뿐이다. ] 만약 그래프가 방향이 없는 간선 (undirected edge)으로만 구성된 경우 인접행렬 $A$는 대칭행렬이 된다. 하지만 간선들이 방향성이 있다면 (edge direction matters) $A$는 대칭이지 않아도 된다. 몇몇 그래프들은 가중치를 가질 수도 있는데 (weighted edges) 그 경우 그래프에 기재되는 값이 {0, 1}이 아닌 임의의 실수가 된다. 예를 들어 가중 그래프 중 단백질간 상호작용 그래프는 두 단백질 사이의 연관된 힘을 나타내는 그래프로 쓰일 수 있다. ### 1.1.1 Multi-relational Graph *multi-relational graph*는 방향이 있는 간선, 없는 간선, 가중치가 있는 간선을 넘어 다양한 종류의 간선이 있는 그래프를 고려한다. 예를 들어, 약물과 약물의 상호작용 그래프에서 각 간선이 두 약물을 동시에 복용할 때 발생할 수 있는 부작용에 대하여 서로 두가지의 간선이 필요할 수 있다. 이 예에서 간선 표기법을 확장하여 다음을 표현할 수 있다: 간선 또는 관계 유형 $\tau$, ($u$, $\tau$, $v$) $\in$ $\cal{E}$, 그리고 하나의 인접행렬 $A_{\tau}$ 를 간선 종류마다 정의할 수 있다. 이러한 그래프를 *multi-relational* 하다고 말하며 전체의 그래프는 인접 텐서 $\cal{A} \in \mathbb{R}^{\cal{|V| * |R| * |V|}}$ 로 정의된다. ^[행렬 A가 실수 집합 V, R의 계량수(cardinality, cardinal number)로 결정되는 차원으로 구성된다.] *multi-relational graph*의 두가지 중요한 부분집합은 1. `heterogenous`, 2. `multiplex` 그래프로 나뉜다. *tau* ($\tau$)는 간선의 타입을 의미하며, 간선의 종류에는 위에 기술한 바와 같이 방향이 있는 것, 없는 것, 가중치가 있는 것 등이 포함된다. 이렇게 간선의 종류가 달라지면 Adjacency Matrix $A$도 따로 정의해야 한다. #### Heterogeneous graph Heterogeneous graph에서, 정점들은 *type*에 물들어있다. 다시 말해, 정점 집합의 일부는 다음과 같이 해체될 수 있다: $\cal{V = V_1} \cup \cal{V_2} \cup \dots \cup \cal{V_k}$ where $\cal{V_i} \cap \cal{V_j} = \emptyset, \forall_i \neq j$. heterogeneous graph의 간선은 일반적으로 제한이 걸려있는데 이는 집합 $\cal{V}$가 서로 겹치지 않는 부분집합 $\cal{V_1}$ 부터 $\cal{V_k}$ ^[$\forall$ : forall] 의 합집합이다.