[Study]Chapter 1. Introduction to ML for Graphs
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
Standford 대학교에서 진행한 온라인 강의 ‘CS224W: Machine Learning with Graphs : Winter 2021’를 수강하며 정리하고자 포스트를 작성하게 되었습니다.
I. Why Graphs?
Figure 1:many type of graph
현대의 딥러닝 도구들은 sequence(text, speach)와 grid(image)등을 위해 디자인 되어있는데 이에 국한되지 않고 우리는 어떻게 신경망 모델을 더 넓게 활용할 수 있을까?
바로 그래프라는 객체\(_{entity}\)들 간의 관계와 상호작용에 관한 묘사와 분석에 일반적으로 사용되고, 복잡한 도메인은 수 많은 관계를 가지고 있어 이는 relational graph로 표현이 가능하며 이러한 관계를 명시적으로 모델링하면 더 좋은 성과를 거둘 수 있다고 한다. 따라서 PyG(PyTorch Geometric), GraphGym 등의 GNN을 위한 라이브러리들이 toolbox도 존재한다고 한다.
즉, Graph가 바로 신경망 모델 Deep Learning의 새로운 선구자가 될 것이다.
Figure 2 : Hot subfield in ML
그러나 그래프 신경망은 sequence나 grid보다 어렵다고 한다. 그러면 도대체 왜 그래프 신경망이 어려울까? 아래와 같은 이유로 그래프 신경망은 어렵다고 한다.
- 네트워크 자체가 복잡함.
- 임의적인\(_{Arbitrary}\) 크기와 복잡한 위상\(_{topological}\) 구조(grid와 같은 공간의 구역이 없음)를 가짐.
- 고정된 노드 또는 참조할만한 포인트가 없음.
- 다양하거나 동적인 특성을 가짐.
FIgure 3 : Graph Neural Netwroks
그래프에서 신경망을 적용하려면 아래와 같이 모든 노드들은 이웃들을 통해 계산 그래프\(_{Computation graph}\)를 정의해야한다.
Figure 4 : Computation Graph; 노드들은 신경망을 통해 이웃들의 정보를 종합한다. Node는 네트워크에 유사한 노드들과 유사하게 임베딩되도록 d-차원으로 embedding된다.
이러한 계산 그래프의 장점을 통해 지도 학습에서 Feature Enginerring 없이 Graph를 표현 학습\(_{Representation-Learning}\)하여 자동적으로 특징을 학습할 수 있게 한다.
그래프는 목적에 따라 아래와 같이 여러가지 Task로 나뉘게 된다.
Figure 5 : Different types of tasks; 노드 분류(유저 분류, AlphaFOLD 등), 연결 예측(지식 그래프 완성, 추천 시스템 등), 전체 또는 부분 그래프 분류(분자 속성 예측, 교통 예측 등), 군집화(사회망 탐지 등), 그래프 생성(좋은 약과 비슷한 분자 생성 등), 물리 시뮬레이션(날씨 예측 DeepMind 등)그 외 여러가지 등이 존재.
II. What is Graphs?
앞서 그래프가 필요한 이유와 어디에 사용되는 지는 알았다. 그럼 이제는 그래프는 무엇인지 알아보자.
그래프는 node(vertic; \(N\))라는 object와 link(edge; \(E\))라는 상호작용\(_{Interaction}\) 그리고 graph(network; \(G(N,E)\)) 요소들로 이루어져 있으며 이는 주어진 문제에서 적절한 표현을 선택하는 것이 성공을 결정한다.
그래프에서 고유하고 명확한\(_{unambiguous}\) 표현이 있는 것에 반해 의미가 없는 표현도 있습니다. 이처럼 연결을 배정하는 방법이 연구하고있는 질문의 본성을 결정한다고 합니다.
1. Directed vs Undirected
그래프의 Link에 방향의 유무에 따라 무방향 그래프와 방향 그래프로 나뉘며 여기서 간선의 가중치의 유무와 loop의 존재, 다중 그래프(두 노드 사이의 여러개의 간선) 등으로 더 상세하게 나뉘어 집니다.
2. Node Degrees
\(k_i\) : i노드와 인접한\(_{adjacent}\) edge들의 개수(방향 그래프에서는 in-degree와 out-degree로 구분)
3. Bipartite Graph
두 비결합\(_{disjoint}\) 집합 U와 V로 모든 연결이 독립적인 집합인 경우를 이분 그래프 또는 Folded(Projected) Network라 부른다.
4. Adjacency Matrix
그래프를 수식으로 표현하기 위해서 우리는 아래와 같이
\[A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \left \{\begin{array}{ll} A_{ij} = 1 &\text{i에서 j의 노드가 존재} \\ A_{ij} = 0 &\text{그 외.} \end{array} \right.\]인접 행렬\(_{Adjacency-Matrix}\)을 사용합니다.위의 인접 행렬에서의 네트워크는 Sparse Graph이라고 하며 실세계의 대부분의 네트워크는 아래와 같이 가능한 연결이나 노드의 수가 매우 작은 경우 희소\(_{Sparse}\)하다.
\[E << E_{max}(\text{or }k << N-1)\]5. Node and Edge Attributes
- Weight(ex. 통화의 빈도)
- Ranking(ex. 더 중요한 이웃 등)
- Type(ex. 친구, 동료 등)
- Sign(ex. 경쟁, 우호 관계 등)
이러한 속성들은 그래프의 나머지 구조에 의존한다.
6. Connectivity
- 무방향 그래프
Figure 6 : Disconnected Graph; Giant Component = {A,D,C,B}, Isolated node = {H}
끊어진\(_{disconnected}\) graph는 두개 이상의 연결된
컴포넌트\(_{components}\)를 만들어낸다. 여기서 가장 큰 Component를 Giant Component라 부르고 연결이 없는 노드를 Isolated node라고 한다.Figure 7 : 색상 영역을 Block-Diagonal Form이라 하고, zero elements로 둘러쌓인 사각형이 된다.
몇개의 구성 요소를 가진 네트워크의 인접 매트릭스는 Figure 7과 같이 작성될 수 있다.
- 방향 그래프
- 강한 방향 그래프(Strongly connected directed graph)
각 노드로부터 모든 다른 노드들로의 경로가 존재하거나 그 반대\(_{vice-versa}\)의 경로도 존재할 때 ‘강한 방향 그래프’ 라고 부른다. 여기서 강한 연결 성분(SCCs\(_{Strogly-connected-componets}\))을 식별 가능하지만 모든 노드가 그런것은 아니며 작은 성분에 포함되거나 아무데도 속하지 않을 수 있다.
Figure 8 : SCC에 도달하는 노드들을 In-componet, SCC에서 도달 가능한 노드들을 Out-component라고 한다.
- 약한 방향 그래프(Weakly connected directed graph)
노드 간의 연결 방향을 고려하지 않으면\(_{disregard}\) 연결되는 경우를 지칭한다.
—