[Study]Chapter 14. Traditional Generative Models for Graphs

Posted Nov 21, 2023 Updated Apr 28, 2024

By Eastk1te

12 min read

해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.

해당 챕터에서는 GNN의 생성 모델들로 그래프 생성 문제를 다루게 됩니다. 그래프 생성 문제는 그래프의 상호작용을 이해하여 예측과 시뮬레이션 그리고 이상 탐지등의 활용이 가능합니다.

Figure 20 : 그래프 생성모델을 통해 만들어진 그래프를 실제 그래프와 유사하게 만드는 것

I. Properties of Real-world Graphs

P(k); 차수 분포
\[P(k) = N_k / N\]
C; 군집계수
\[\begin{array}{ll} k_i = \text{노드 i의 degree} \\ e_i = \text{노드 i 이웃들 사이의 edge의 수} \\ C_i = \frac{2e_i}{k_i(k_i-1)} \\ C = \frac{1}{N}\sum_i^NC_i \end{array}\]
s; 연결 요소
Giant component = Largest component
즉, 가장 큰 연결 요소의 크기 = 두 노드의 연결되는 통로의 집합이 가장 큰 요소
h; path length
- Diameter : 그래프에서 노드들의 쌍의 최대(최단) 거리
- Average path length
\[\bar{h}=\frac{1}{2E_{max}}\sum_{i,j\neg i}h_{ij}, \text{h_{ij}는 노드 i와 j사이의 거리, E_{max}는 edge의 최대 수.}\]

1. Case Study : MSN Graph

Figure 1 : MSN Graph 한달에 억단위의 user data를 가진 MSN Messenger, MSN의 각 그래프 속성을 시각화하였다.

위와 같은 값들이 기대된 값들에 비해 흥미로운 결과인지 무엇을 알려주는지에 대한 답을 하기위해 Model이 필요합니다.

II. Erdös-Renyi Random Graphs

두 가지 변형으로 아래와 같다.

$G_{np}$ : n개의 노드를 가진 무방향 그래프와 각 edge는 i.i.d 확률 p를 가짐.
$G_{nm}$ : n 개의 노드의 무방향 그래프와 m개의 edge들이 무작위적으로 균일하게 선택됨

여기서 $G_{np}$는 무작위 절차의 결과로 수 많은 다른 그래프를 만들어 냅니다.

P(k)
Figure 2 : 각 노드의 degree 분포는 binomial 분포이다.
Clustering coeffient
\[\begin{array}{ll} E[e_i] &= p\frac{k_i(k_i-1)}{2} \\ E[C_i] &= \frac{p\cdot k_i(k_i-1)}{k_i(k_i-1)}\\ &=p =\frac{\bar{k}}{n-1} \approx \frac{\bar{k}}{n} \end{array}\]
Connected Components
Figure 3 : p 변화에 따른 $G_{np}$의 그래프 구조
Figure 4 : Simulation Excperiment
shortest path of $G_{np}$
Figure 7 : shortest path of $G_{np}$, Erdös-Renyi 무작위 그래프에서 최단 경로크기에 비례한 노드들의 수로 최단 경로는 증가하지만 몇 개의 hop만 떨어져 있을 것입니다.

1. Expansion α

G(V,E)에서 모든 부분집합 S가 V의 부분집합이면, S의 edge들의 수는 $\geq α \cdot min(|S|, |V \backslash S |)$ 이다. 이는 S 노드의 개수와 V 노드 집합에서 S를 뺀 노드의 개수 중 작은 값에 α를 곱한 값보다 S에 속하는 간선의 개수가 크거나 같다는 것을 의미합니다.

\[α = \min\limits_{S\subseteq V}\frac{\# \text{edges leaving }S}{min(|S|,|V \backslash S|)}\]

set notation($\backslash$): A \ B, x $\in$ A; x $\notin$ B

이러한 α는 l개의 노드가 끊어졌을때 해당 노드와 연결된 edge들을 잘라내는 비율 상수로 아래와 같이 나타냅니다.

\[\text{# 끊어진 l개의 노드}\geq α \cdot \text{# 끊어진 l개의 edge}\]

Figure 5 : 차례대로 α의 비율이 작은것과 큰것에 대한 이미지

2. 무작위 그래프의 확장.

Figure 6 : α를 활용한 그래프의 확장

확장 α를 가진 무작위 그래프
O((logn)/α)의 경로 길이를 가지게 됩니다. 즉, 그래프의 확장 α가 클수록, 노드 간의 경로가 더 짧아지며 네트워크의 효율성이 향상됩니다.
log n > np > c, diam($G_{np}$) = O(log n / log (np))
$G_{np}$의 지름은 log(n)의 함수로 나타나고, n이 충분히 크다면 $G_{np}$는 지름이 로그에 비례하는 크기를 갖습니다.
무작위 그래프의 Robust성
무작위 그래프는 임의의 확장에 robust하며 BFS를 사용해 효율적으로 모든 노드에 방문할 수 있습니다.

3. MSN vs $G_{np}$

실세계 네트워크와 랜덤 네트워크를 비교했을때, Giant connected component와 평균 경로 길이는 동일하지만 군집 계수와 차수 분포는 동일하지 않습니다.

Figure 8 : 무작위 네트워크 모델의 문제로는 차수 분포가 실세계 그래프와 다르고, 실세계의 giant component는 phase transition을 통해 출현하지 않으며 지역 구조(군집 계수가 너무 낮음)가 없다는 문제가 존재합니다.

따라서, 실세계 네트워크는 무작위하지 않다는 것을 의미합니다.

III. The Small-World Model

그러면 이러한 무작위 네트워크의 단점을 해결하기위해 차수 분포와 거대 연결 요소에 영향을 미치는 최단 경로를 가지면서 군집 계수를 높일 수 있을까?

Figure 10 : 랜덤 네트워크에서는 O(logn)의 최단 경로를 가지지만 클러스터링이 낮고, 실제 그래프는 Triadic closure 매커니즘으로인해 “지역”구조를 가지지만 네트워크의 지름이 높아 최단 길이가 높습니다.

실세계 그래프와 랜덤 그래프 사이를 채워$_{interpolate}$ 두 가지를 모두 가지게 만듭니다.

어떻게 이 사이를 메울 수 있을까?

Figure 11 : rewiring은 interpolate를 가능하게 한다.

small-world 모델¹은 아래와 같이 두개의 요소가 있습니다.

저차원의 정칙 라티스$_{regular-lattice}$
저차원의 정칙 라티스에서 시작해 높은 군집 계수를 가지며, 각 노드의 이웃들이 서로 연결되어 있는 상태를 나타냅니다.
rewire
일정 확률 p로 리와이어링을 발생시켜 무작위한 연결(shorcuts)이 생기게 합니다.

Figure 12 : 초록색의 가로 영역은 높은 클러스터링을 가지만 낮은 path length를 가지는 영역이다. 이를 small-world라 부른다. 네트워크는 무겁게 클러스터링 되지만 short path를 여전히 지니고 있따.

따라서 높은 클러스터링의 네트워크는 small world가 될 수으며 몇 개의 무작위 링크 이상으로 필요하지않다.

따라서 높은 클러스터링 계수를 가진 네트워크는 몇 개의 무작위 링크만 추가하면 작은 세계 특성을 가질 수 있습니다. Small-World 모델은 클러스터링과 작은 세계 특성 간의 상호작용에 대한 통찰을 제공해 실세계 네트워크에서 관찰되는 높은 클러스터링을 설명할 수 있지만 올바른 차수 분포를 제공하지 않을 수 있습니다.