그래프 분석 (Graph Analysis)
1. 개요
그래프 분석은 노드(정점)와 엣지(간선)로 구성된 네트워크 데이터의 구조와 패턴을 분석하는 기술. 소셜 네트워크, 지식 그래프, 분자 구조, 추천 시스템 등 관계 데이터가 존재하는 모든 영역에서 활용됨.
정의
그래프 G = (V, E)
V: 정점(노드) 집합
E: 간선(엣지) 집합, E ⊆ V × V
유형:
- 방향/무방향 그래프
- 가중/비가중 그래프
- 이분 그래프 (Bipartite)
- 이종 그래프 (Heterogeneous)
그래프 표현
| 표현 |
설명 |
공간 복잡도 |
| 인접 행렬 |
A[i,j] = 1 if (i,j) ∈ E |
O(V²) |
| 인접 리스트 |
각 노드의 이웃 목록 |
O(V+E) |
| 엣지 리스트 |
(source, target, weight) |
O(E) |
2. 핵심 개념
2.1 노드 중심성 (Centrality)
| 지표 |
정의 |
해석 |
| Degree |
연결된 엣지 수 |
직접 연결 |
| Betweenness |
최단 경로 통과 빈도 |
중개자 역할 |
| Closeness |
평균 거리의 역수 |
접근성 |
| Eigenvector |
중요 노드와 연결 |
영향력 |
| PageRank |
방문 확률 |
웹 페이지 중요도 |
PageRank:
PR(v) = (1-d)/N + d × Σᵤ∈in(v) PR(u)/out(u)
d: 감쇠 계수 (보통 0.85)
N: 전체 노드 수
2.2 커뮤니티 탐지
목적: 밀집 연결된 노드 그룹 식별
모듈성 (Modularity):
Q = (1/2m) Σᵢⱼ [Aᵢⱼ - kᵢkⱼ/2m] δ(cᵢ, cⱼ)
m: 전체 엣지 수
kᵢ: 노드 i의 차수
cᵢ: 노드 i의 커뮤니티
| 알고리즘 |
방법 |
| Louvain |
모듈성 최적화 |
| Label Propagation |
레이블 전파 |
| Girvan-Newman |
엣지 제거 |
| Spectral |
라플라시안 고유벡터 |
2.3 그래프 특성
| 특성 |
정의 |
| Diameter |
최대 최단 경로 |
| Clustering Coefficient |
삼각형 비율 |
| Density |
실제 엣지 / 가능한 엣지 |
| Connected Components |
연결된 부분그래프 |
| Transitivity |
전역 군집 계수 |
3. 주요 알고리즘/기법
3.1 그래프 임베딩
전통적 방법
| 방법 |
설명 |
| Spectral Embedding |
라플라시안 고유벡터 |
| MDS |
거리 보존 |
| Isomap |
측지 거리 |
랜덤 워크 기반
DeepWalk:
1. 각 노드에서 랜덤 워크 수행
2. 워크 시퀀스를 Word2Vec 학습
3. Skip-gram으로 노드 임베딩
특징: 구조적 유사성 포착
Node2Vec:
편향된 랜덤 워크 (p, q 파라미터)
p: 이전 노드 복귀 확률 제어
q: BFS vs DFS 균형
p↓: 지역 탐색 (커뮤니티)
q↓: 전역 탐색 (구조적 역할)
3.2 그래프 신경망 (GNN)
GCN (Graph Convolutional Network)
H⁽ˡ⁺¹⁾ = σ(D̃⁻½ Ã D̃⁻½ H⁽ˡ⁾ W⁽ˡ⁾)
à = A + I (자기 연결)
D̃: Ã의 차수 행렬
H: 노드 특성 행렬
W: 학습 가능 가중치
GraphSAGE
집계 + 업데이트:
hᵥ⁽ˡ⁺¹⁾ = σ(W⁽ˡ⁾ · CONCAT(hᵥ⁽ˡ⁾, AGG({hᵤ⁽ˡ⁾: u ∈ N(v)})))
집계 함수: Mean, LSTM, Pooling
장점: 귀납적 학습, 샘플링 기반
GAT (Graph Attention Network)
어텐션 가중치:
αᵢⱼ = softmax(LeakyReLU(aᵀ[Whᵢ || Whⱼ]))
업데이트:
hᵢ' = σ(Σⱼ∈N(i) αᵢⱼ Whⱼ)
Multi-head attention 사용
| GNN 변형 |
특징 |
| GIN |
구분력 최대화 |
| R-GCN |
관계형 그래프 |
| HAN |
이종 그래프 |
| Graph Transformer |
Transformer 적용 |
3.3 지식 그래프 임베딩
지식 그래프: (head, relation, tail) 트리플
목적: 엔티티와 관계를 벡터 공간에 임베딩
| 모델 |
점수 함수 |
| TransE |
||h + r - t|| |
| RotatE |
||h ∘ r - t|| |
| ComplEx |
Re(⟨h, r, t̄⟩) |
| ConvE |
Conv 기반 |
3.4 그래프 태스크
| 태스크 |
설명 |
| 노드 분류 |
노드 레이블 예측 |
| 링크 예측 |
엣지 존재 여부 예측 |
| 그래프 분류 |
그래프 전체 레이블 |
| 노드 클러스터링 |
커뮤니티 탐지 |
4. 실무 적용 사례
4.1 소셜 네트워크 분석
사용자 노드, 팔로우/친구 엣지
분석:
- 인플루언서 식별 (중심성)
- 커뮤니티 탐지
- 봇 탐지
- 정보 확산 모델링
4.2 추천 시스템
User-Item 이분 그래프:
- 유저-유저 유사도 (협업 필터링)
- 아이템-아이템 유사도
- GNN 기반 추천 (LightGCN, PinSage)
4.3 사기 탐지
거래 그래프:
- 계정 간 자금 이동
- 이상 패턴 탐지
- 공모 사기 네트워크 식별
4.4 약물 발견
분자 그래프:
- 원자 = 노드
- 결합 = 엣지
GNN으로 분자 특성 예측:
- 용해도, 독성, 활성
4.5 지식 그래프 QA
질문 → 엔티티/관계 추출 → 그래프 쿼리 → 답변
예: "서울의 인구는?"
엔티티: 서울
관계: 인구
5. 참고 논문/저널
핵심 논문
| 논문 |
저자 |
출처 |
기여 |
| "DeepWalk: Online Learning of Social Representations" |
Perozzi et al. |
KDD 2014 |
DeepWalk |
| "node2vec: Scalable Feature Learning for Networks" |
Grover & Leskovec |
KDD 2016 |
Node2Vec |
| "Semi-Supervised Classification with GCN" |
Kipf & Welling |
ICLR 2017 |
GCN |
| "Inductive Representation Learning on Large Graphs" |
Hamilton et al. |
NeurIPS 2017 |
GraphSAGE |
| "Graph Attention Networks" |
Veličković et al. |
ICLR 2018 |
GAT |
| "How Powerful are Graph Neural Networks?" |
Xu et al. |
ICLR 2019 |
GIN |
| "Translating Embeddings for Modeling Multi-relational Data" |
Bordes et al. |
NeurIPS 2013 |
TransE |
주요 컨퍼런스
| 컨퍼런스 |
분야 |
| KDD, WWW, WSDM |
그래프 마이닝 |
| NeurIPS, ICML, ICLR |
GNN |
| CIKM, ICDM |
데이터 마이닝 |
| LoG (Learning on Graphs) |
그래프 학습 전문 |
벤치마크 데이터셋
| 데이터셋 |
도메인 |
태스크 |
| Cora, Citeseer, Pubmed |
인용 네트워크 |
노드 분류 |
| OGB (Open Graph Benchmark) |
다양 |
표준 벤치마크 |
| FB15k, WN18 |
지식 그래프 |
링크 예측 |
| QM9, ZINC |
분자 |
그래프 회귀 |
6. 구현 도구
| 도구 |
용도 |
| NetworkX |
Python 그래프 분석 |
| PyTorch Geometric |
GNN 라이브러리 |
| DGL |
Deep Graph Library |
| graph-tool |
고성능 분석 |
| Neo4j |
그래프 데이터베이스 |
| igraph |
고속 그래프 알고리즘 |
| Stellargraph |
GNN (TF/Keras) |
PyTorch Geometric 예시
import torch
from torch_geometric.nn import GCNConv
class GCN(torch.nn.Module):
def __init__(self, in_channels, hidden_channels, out_channels):
super().__init__()
self.conv1 = GCNConv(in_channels, hidden_channels)
self.conv2 = GCNConv(hidden_channels, out_channels)
def forward(self, x, edge_index):
x = self.conv1(x, edge_index).relu()
x = F.dropout(x, training=self.training)
x = self.conv2(x, edge_index)
return F.log_softmax(x, dim=1)