여기서 말하는 그래프는 컴퓨터 공학 혹은 컴퓨터 과학 혹은 이산 수학에서 이야기하는 그래프다.
기본 개념
그래프 Graph 는 $G$는 정점 (Vertex) 혹은 노드 (Node)라고 불리는 집합 $V$와
간선, 연결선 (edge)의 집합인 $E$의 ordered pairs 순서쌍 $G$ = ($V, E$)으로 정의 된다.
이때 ordered pair는 $(x, y) \neq (y, x)$라는 뜻이다.
엣지의 집합 $E \subseteq \{ (x, y) | x, y \in V^2 \, \text{and} \, x \neq y \}$로 정의 된다.
노드 $v$와 연결된 모든 노드의 집합을 neighbor(hood)라고 부르며 $N(v) = \{ u \in V | (u, v) \in E \}$로 정의한다.
이때 연결된 두 노드는 서로 인접 (adjacent)한다고 한다.
차수 Degree는 하나의 노드에 연결된 간선의 합이다.
그래프에는 방향이 존재하는데
directed graph 방향 그래프라면, 노드 1 → 노드 2라고 하더라도 노드 2 → 노드 1가 아니다.
반면에 undirected graph 무방향 그래프라면 노드 1 → 노드 2이면 무조건 노드 2 → 노드 1도 성립한다.
그래프 표현
1. Adjacent Matrix 인접 행렬
Node 1과 2, 3은 연결되어 있지만 2와 3은 서로 연결되어 있지 않음을 표현한다.
| 1 | 2 | 3 | |
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 |
2. Adjacent List 인접 리스트
1 -> [2, 3]
2 -> [1]
3 -> [1]
엣지의 수가 노드 보다 많으면 인접 행렬을, 엣지의 수가 노드 보다 적다면 인접 리스트를 쓰는게 좋다고 한다.
이는 공간 복잡도가 인접 행렬이 O($|V|^2$)이고 인접 리스트는 O($|V| + |E|$)이기 때문이다.
Laplacian Matrix 라플라시안 행렬
그래프 구조와 관련된 ML이나 DL 논문을 보다보면 자주 보이는 개념이라 여기서도 다룬다.
Laplacian matrix L은 방향 그래프냐 무방향 그래프냐에 따라서 다르게 정의된다.
무방향 그래프의 경우 Degree matrix인 D와 Adjacent matrix인 A로 도출된다.
L = D - A다.
방향 그래프인 경우 In-Degree matrix D1과 Out-Degree matrix D2에 대해서 각각 아래처럼 정의된다.
L1 = D1 - A
L2 = D2 - A
보통 symmetrically normalized Laplacian matrix를 많이 보게 된다.
이는 directed graph의 경우 근본적으로 adjacent matrix이 asymmetirc이기 때문에 이를 대칭화하는 작업을 함과
동시에 차수인 D의 역수를 곱하는 개념과 비슷한 느낌으로 스케일링을 통한 normalized해주며 diagonal term은 1으로 만들게 된다.
변환 결과 symmetrically normalized Laplacian matrix L은 여러 성질들 중에서 다음의 두 성질을 지닌다.
- symmetric
- positive semi-definite
위 두 성질을 만족하면 eigen decomposition을 비롯해서 좋은 장점이 많았던거 같은데 선형대수의 배움이 짧아서 나중에 추가하기로 한다.
여담
예전에 추천 공부할 때 GraphSAGE나 PinSAGE 등을 공부할 때 알았던 내용인데 복기할 겸 블로그에 간단하게 정리해보았다.
또 요즘 GraphRAG라는 방법도 있길래 공부하기 전에 복습이 필요했다.
References:
https://en.wikipedia.org/wiki/Graph_theory
https://en.wikipedia.org/wiki/Neighbourhood_(graph_theory)
https://ratsgo.github.io/data%20structure&algorithm/2017/11/18/graph/
https://junklee.tistory.com/112
https://en.wikipedia.org/wiki/Laplacian_matrix