그래프 분석 개요¶

그래프 분석(Graph Analytics)은 노드(정점)와 엣지(간선)로 구성된 네트워크 데이터의 구조와 패턴을 분석하는 분야다. 소셜 네트워크, 지식 그래프, 추천 시스템, 사기 탐지 등에 활용됨.

핵심 개념¶

그래프 표현¶

\[G = (V, E)\]

요소	설명
$V$	노드 집합 (Vertices)
$E$	엣지 집합 (Edges)
$A$	인접 행렬 (Adjacency Matrix)
Directed/Undirected	방향성 여부
Weighted	엣지 가중치

그래프 유형¶

유형	특징	예시
Homogeneous	단일 노드/엣지 유형	친구 관계
Heterogeneous	다중 노드/엣지 유형	지식 그래프
Bipartite	두 그룹 간 연결	사용자-아이템
Temporal	시간에 따른 변화	거래 네트워크

알고리즘 분류 체계¶

Graph Analytics
├── Graph Metrics
│   ├── Centrality (Degree, Betweenness, PageRank)
│   ├── Clustering Coefficient
│   └── Graph Density
├── Community Detection
│   ├── Modularity Optimization (Louvain)
│   ├── Label Propagation
│   ├── Spectral Clustering
│   └── Hierarchical Clustering
├── Link Prediction
│   ├── Heuristic (Common Neighbors, Adamic-Adar)
│   └── Embedding-based
├── Node Embedding
│   ├── DeepWalk
│   ├── Node2Vec
│   ├── LINE
│   └── SDNE
├── Graph Neural Networks
│   ├── GCN (Graph Convolutional Network)
│   ├── GraphSAGE
│   ├── GAT (Graph Attention Network)
│   └── GIN (Graph Isomorphism Network)
├── Knowledge Graphs
│   ├── TransE, TransR
│   ├── DistMult, ComplEx
│   └── RotatE
└── Shortest Path / Flow
    ├── Dijkstra, Bellman-Ford
    └── Max Flow

그래프 지표¶

중심성 (Centrality)¶

지표	의미	수식
Degree	연결 수	$C_D(v) = \frac{deg(v)}{N-1}$
Betweenness	최단경로 통과 빈도	$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
Closeness	평균 거리의 역수	$C_C(v) = \frac{N-1}{\sum_{u} d(v, u)}$
PageRank	중요도 재귀 계산	$PR(v) = \frac{1-d}{N} + d \sum_{u \in In(v)} \frac{PR(u)}{

import networkx as nx

G = nx.karate_club_graph()

# 중심성 계산
degree_centrality = nx.degree_centrality(G)
betweenness = nx.betweenness_centrality(G)
closeness = nx.closeness_centrality(G)
pagerank = nx.pagerank(G, alpha=0.85)

# 상위 노드
top_pagerank = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)[:5]

커뮤니티 탐지¶

Louvain Algorithm¶

모듈러리티 최대화:

\[Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)\]

import community as community_louvain

partition = community_louvain.best_partition(G)
modularity = community_louvain.modularity(partition, G)
print(f"Modularity: {modularity:.4f}")
print(f"Number of communities: {len(set(partition.values()))}")

Label Propagation¶

from networkx.algorithms.community import label_propagation_communities

communities = list(label_propagation_communities(G))
print(f"Number of communities: {len(communities)}")

노드 임베딩¶

Node2Vec¶

랜덤 워크 + Skip-gram:

\[\max_f \sum_{u \in V} \log P(N_S(u) | f(u))\]

하이퍼파라미터: - $p$: Return parameter (작을수록 BFS-like) - $q$: In-out parameter (작을수록 DFS-like)

from node2vec import Node2Vec

# Node2Vec 모델
node2vec = Node2Vec(
    G, 
    dimensions=64,
    walk_length=30,
    num_walks=200,
    p=1,  # Return parameter
    q=1,  # In-out parameter
    workers=4
)

# 학습
model = node2vec.fit(window=10, min_count=1, batch_words=4)

# 노드 임베딩 얻기
embedding = model.wv['node_1']

# 유사 노드
similar_nodes = model.wv.most_similar('node_1', topn=10)

참고 논문: - Grover, A. & Leskovec, J. (2016). "node2vec: Scalable Feature Learning for Networks". KDD.

Graph Neural Networks¶

GCN (Graph Convolutional Network)¶

이웃 정보 집계:

\[H^{(l+1)} = \sigma\left(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)}\right)\]

여기서 $\tilde{A} = A + I$ (자기 루프 추가)

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.datasets import Planetoid

# 데이터 로드
dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

class GCN(torch.nn.Module):
    def __init__(self, num_features, num_classes, hidden_dim=64):
        super().__init__()
        self.conv1 = GCNConv(num_features, hidden_dim)
        self.conv2 = GCNConv(hidden_dim, num_classes)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=0.5, training=self.training)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

model = GCN(dataset.num_features, dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

# 학습
model.train()
for epoch in range(200):
    optimizer.zero_grad()
    out = model(data.x, data.edge_index)
    loss = F.nll_loss(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()

참고 논문: - Kipf, T.N. & Welling, M. (2017). "Semi-Supervised Classification with Graph Convolutional Networks". ICLR.

GraphSAGE¶

샘플링 + 집계 (유도적 학습):

\[h_v^{(l)} = \sigma\left(W^{(l)} \cdot AGGREGATE\left(\{h_u^{(l-1)} : u \in N(v)\}\right)\right)\]

from torch_geometric.nn import SAGEConv

class GraphSAGE(torch.nn.Module):
    def __init__(self, num_features, num_classes, hidden_dim=64):
        super().__init__()
        self.conv1 = SAGEConv(num_features, hidden_dim)
        self.conv2 = SAGEConv(hidden_dim, num_classes)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

GAT (Graph Attention Network)¶

어텐션 메커니즘으로 이웃 가중치 학습:

\[\alpha_{ij} = \frac{\exp(LeakyReLU(a^T[Wh_i \| Wh_j]))}{\sum_{k \in N(i)} \exp(LeakyReLU(a^T[Wh_i \| Wh_k]))}\]

from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, num_features, num_classes, hidden_dim=8, heads=8):
        super().__init__()
        self.conv1 = GATConv(num_features, hidden_dim, heads=heads, dropout=0.6)
        self.conv2 = GATConv(hidden_dim * heads, num_classes, heads=1, concat=False, dropout=0.6)

    def forward(self, x, edge_index):
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv1(x, edge_index)
        x = F.elu(x)
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

참고 논문: - Hamilton, W.L. et al. (2017). "Inductive Representation Learning on Large Graphs". NeurIPS. - Velickovic, P. et al. (2018). "Graph Attention Networks". ICLR.

지식 그래프¶

트리플 임베딩¶

$(h, r, t)$: head, relation, tail

TransE: $$\|h + r - t\|$$

from pykeen.pipeline import pipeline

result = pipeline(
    model='TransE',
    dataset='FB15k-237',
    training_kwargs=dict(num_epochs=100),
    evaluation_kwargs=dict(batch_size=256),
)

# 링크 예측
result.save_to_directory('transe_fb15k237')

참고 문헌¶

교과서¶

Hamilton, W.L. (2020). "Graph Representation Learning". Morgan & Claypool.
Newman, M.E.J. (2018). "Networks" (2nd ed). Oxford.

핵심 논문¶

Kipf, T.N. & Welling, M. (2017). "GCN". ICLR.
Grover, A. & Leskovec, J. (2016). "node2vec". KDD.
Velickovic, P. et al. (2018). "GAT". ICLR.

라이브러리¶

NetworkX: https://networkx.org/
PyTorch Geometric: https://pytorch-geometric.readthedocs.io/
DGL: https://www.dgl.ai/
PyKEEN: https://pykeen.readthedocs.io/

요소	설명
\(V\)	노드 집합 (Vertices)
\(E\)	엣지 집합 (Edges)
\(A\)	인접 행렬 (Adjacency Matrix)
Directed/Undirected	방향성 여부
Weighted	엣지 가중치

지표	의미	수식
Degree	연결 수	\(C_D(v) = \frac{deg(v)}{N-1}\)
Betweenness	최단경로 통과 빈도	\(C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}\)
Closeness	평균 거리의 역수	\(C_C(v) = \frac{N-1}{\sum_{u} d(v, u)}\)
PageRank	중요도 재귀 계산	$PR(v) = \frac{1-d}{N} + d \sum_{u \in In(v)} \frac{PR(u)}{