ㅁ 최신 모델

1. GraphSAGE

ㅇ 정의:
– Graph Sample and Aggregate의 약자로, 이웃 노드의 정보를 샘플링하고 집계하여 노드 임베딩을 생성하는 그래프 신경망 모델.

ㅇ 특징:
– 대규모 그래프 처리에 효율적.
– 이웃 샘플링으로 메모리 사용량 절감.
– Aggregator로 mean, LSTM, max-pooling 등을 사용 가능.

ㅇ 적합한 경우:
– 노드 수가 매우 많아 전체 이웃 정보를 모두 사용할 수 없는 경우.
– 온라인 학습 또는 스트리밍 그래프 처리.

ㅇ 시험 함정:
– 모든 이웃을 사용하는 GCN과 혼동.
– Aggregator 종류를 고정된 것으로 오해.

ㅇ 시험 대비 “패턴 보기” 예시:
– O: GraphSAGE는 이웃 노드를 샘플링하여 임베딩을 생성한다.
– X: GraphSAGE는 항상 모든 이웃의 정보를 사용한다.

2. GIN

ㅇ 정의:
– Graph Isomorphism Network의 약자로, 그래프 동형사상 판별 능력이 강한 GNN 모델.

ㅇ 특징:
– Weisfeiler-Lehman 그래프 동형사상 테스트와 동일한 구분 능력.
– 단순한 합(sum) Aggregator 사용.

ㅇ 적합한 경우:
– 그래프 구조 차이를 민감하게 구분해야 하는 경우.
– 화합물 구조 판별, 분자 그래프 분석.

ㅇ 시험 함정:
– 평균(mean) 또는 최대(max) 집계로도 동일한 구분 능력을 가진다고 착각.
– GIN이 항상 GCN보다 성능이 높다고 일반화.

ㅇ 시험 대비 “패턴 보기” 예시:
– O: GIN은 sum Aggregator를 사용하여 높은 구분 능력을 가진다.
– X: GIN은 mean Aggregator를 사용한다.

3. GAT

ㅇ 정의:
– Graph Attention Network의 약자로, 이웃 노드별로 주의(attention) 가중치를 학습하여 정보를 집계하는 모델.

ㅇ 특징:
– Self-attention 메커니즘 적용.
– 이웃 노드별 중요도를 차등 반영.

ㅇ 적합한 경우:
– 이웃 노드의 중요도가 균등하지 않은 경우.
– 소셜 네트워크, 추천 시스템.

ㅇ 시험 함정:
– Attention이 항상 성능을 향상시킨다고 오해.
– GAT가 이웃 수에 관계없이 동일한 계산량을 가진다고 착각.

ㅇ 시험 대비 “패턴 보기” 예시:
– O: GAT는 이웃 노드별로 attention 가중치를 학습한다.
– X: GAT는 모든 이웃의 정보를 동일하게 반영한다.

4. Positional Encoding on Graphs

ㅇ 정의:
– 그래프 구조 내에서 노드의 위치 정보를 인코딩하여 모델에 제공하는 기법.

ㅇ 특징:
– Laplacian eigenvectors, random walk 기반 위치 정보 활용.
– Transformer 기반 그래프 모델에서 성능 향상.

ㅇ 적합한 경우:
– 그래프의 전역 구조를 반영해야 하는 경우.
– 노드 간 상대적 위치가 중요한 문제.

ㅇ 시험 함정:
– Positional Encoding이 항상 좌표 정보라는 오해.
– 모든 그래프 모델이 위치 정보를 필요로 한다고 착각.

ㅇ 시험 대비 “패턴 보기” 예시:
– O: Laplacian eigenvectors는 그래프 positional encoding에 활용될 수 있다.
– X: Positional Encoding은 물리적 좌표 정보만을 의미한다.

ㅁ 추가 학습 내용

시험 대비를 위해 다음 내용을 정리한다.

1. 각 모델의 수식적 정의와 학습 과정
– GraphSAGE: 이웃 노드 샘플링 기반의 aggregation 수식. 샘플링 후 평균, LSTM, Pooling 등의 방법으로 이웃 정보를 집계.
– GIN(Graph Isomorphism Network): 업데이트 수식 h_v^(k) = MLP((1 + ε) * h_v^(k-1) + Σ_{u∈N(v)} h_u^(k-1)), ε은 학습 가능 매개변수.
– GAT(Graph Attention Network): attention coefficient α_{ij} = softmax_j(LeakyReLU(a^T [W h_i || W h_j])) 계산 후 가중합으로 업데이트.

2. 시간 복잡도와 메모리 요구사항
– GraphSAGE: 샘플링으로 인해 대규모 그래프에서 메모리 사용량과 계산량을 줄임.
– GIN: 모든 이웃을 활용하므로 밀집 그래프에서는 계산량이 커질 수 있음.
– GAT: 모든 이웃 쌍에 대해 attention 계산 필요, 이웃 수가 많으면 시간·메모리 부담 증가.

3. 실제 데이터셋 성능 비교
– Cora, PubMed: 노드 수와 특성이 작아 GCN, GAT, GIN 모두 비교적 높은 정확도.
– Reddit: 대규모 데이터셋으로 GraphSAGE의 샘플링 장점이 부각됨.

4. Positional Encoding
– Laplacian eigenvectors: 그래프 라플라시안의 고유벡터를 사용하여 노드 위치 정보 부여.
– Random walk 기반: DeepWalk, Node2Vec는 랜덤 워크로 생성된 시퀀스를 임베딩하여 위치 정보 획득.
– Transformer 결합 시 positional bias: 노드 간 거리나 위치 정보를 attention score 계산에 반영.

5. 각 모델이 풀 수 있는 대표 그래프 문제 유형
– 노드 분류: 각 노드의 속성을 예측 (예: 논문 주제 분류).
– 링크 예측: 두 노드 간 연결 가능성 예측 (예: 친구 추천).
– 그래프 분류: 그래프 전체의 속성을 예측 (예: 화합물의 독성 여부).