ㅁ 그래프 신경망 최적화

ㅇ 정의:
그래프 구조 데이터를 효율적으로 학습하기 위해 모델 구조, 학습 전략, 노드/엣지 표현 방식을 개선하는 기법들의 집합.

ㅇ 특징:
– 그래프 데이터의 불규칙성과 희소성을 고려한 연산 최적화 필요.
– 메모리 사용량과 연산 복잡도 절감이 주요 목표.
– 샘플링, 집계, 위치 인코딩 등 다양한 접근 방식 존재.

ㅇ 적합한 경우:
– 대규모 그래프 데이터셋에서 효율적인 학습이 필요할 때.
– 노드/엣지 속성 정보와 구조 정보를 동시에 활용해야 할 때.

ㅇ 시험 함정:
– 각 기법의 핵심 차이를 혼동.
– ‘그래프 임베딩’과 ‘그래프 신경망 최적화’를 동일시하는 오류.

ㅇ 시험 대비 “패턴 보기” 예시:
O: “그래프 신경망 최적화 기법은 연산 효율과 표현력 향상을 동시에 추구한다.”
X: “그래프 신경망 최적화는 항상 노드 수를 줄이는 것을 의미한다.”

================================

1. GraphSAGE

ㅇ 정의:
대규모 그래프에서 이웃 노드 샘플링을 통해 효율적으로 노드 임베딩을 학습하는 방법.

ㅇ 특징:
– 이웃 전체가 아닌 일부를 샘플링하여 메모리/연산 절감.
– Aggregator 함수(Mean, LSTM, Pooling 등)를 사용.
– inductive 학습 지원.

ㅇ 적합한 경우:
– 새로운 노드가 추가되는 동적 그래프.
– 전체 이웃 정보를 모두 불러오기 어려운 대규모 그래프.

ㅇ 시험 함정:
– transductive와 inductive 개념 혼동.
– Aggregator 종류에 따른 성능 차이를 간과.

ㅇ 시험 대비 “패턴 보기” 예시:
O: “GraphSAGE는 샘플링 기반 Aggregator를 사용하여 대규모 그래프를 처리한다.”
X: “GraphSAGE는 항상 모든 이웃을 사용하여 학습한다.”

================================

2. GIN (Graph Isomorphism Network)

ㅇ 정의:
그래프 동형성 판별 능력을 최대화하기 위해 설계된 GNN 구조로, Weisfeiler-Lehman 테스트와 동등한 표현력을 가짐.

ㅇ 특징:
– 단순한 MLP 기반 Aggregation.
– 이웃 특성과 자기 노드 특성을 합한 후 MLP 적용.
– 표현력 극대화.

ㅇ 적합한 경우:
– 구조적 차이를 잘 구분해야 하는 분류 문제.
– 그래프 동형성 검증.

ㅇ 시험 함정:
– GIN이 항상 GAT보다 성능이 높다고 일반화.
– WL 테스트와의 관계를 모호하게 기억.

ㅇ 시험 대비 “패턴 보기” 예시:
O: “GIN은 WL 테스트와 동등한 구별 능력을 가진다.”
X: “GIN은 WL 테스트보다 항상 더 강력하다.”

================================

3. Graph Attention Networks (GAT)

ㅇ 정의:
노드 간 중요도를 학습하기 위해 Attention 메커니즘을 적용한 GNN.

ㅇ 특징:
– 각 이웃 노드의 가중치를 학습.
– self-attention 기반.
– 이웃별로 다른 정보 중요도 반영 가능.

ㅇ 적합한 경우:
– 이웃 노드의 중요도가 균등하지 않은 경우.
– 복잡한 관계망에서 핵심 노드 식별.

ㅇ 시험 함정:
– Attention이 항상 성능 향상을 보장한다고 착각.
– GAT의 가중치가 고정된다고 오해.

ㅇ 시험 대비 “패턴 보기” 예시:
O: “GAT는 self-attention을 통해 이웃별 가중치를 학습한다.”
X: “GAT는 모든 이웃에 동일한 가중치를 부여한다.”

================================

4. Positional Encoding on Graphs

ㅇ 정의:
그래프 내 노드의 위치 정보를 임베딩에 반영하는 기법.

ㅇ 특징:
– 그래프 구조만으로는 절대적 위치 정보 부족.
– Laplacian eigenvectors, random walk distance 등 활용.
– Transformer 기반 GNN에서 중요.

ㅇ 적합한 경우:
– 위치/거리 기반 패턴이 중요한 그래프.
– 순서 없는 구조에서 위치 정보 보강 필요.

ㅇ 시험 함정:
– Positional Encoding이 시계열 전용이라고 오해.
– Laplacian 기반과 Random walk 기반 혼동.

ㅇ 시험 대비 “패턴 보기” 예시:
O: “그래프 Positional Encoding은 Laplacian eigenvectors를 활용할 수 있다.”
X: “그래프 Positional Encoding은 노드 순서가 있는 경우에만 적용 가능하다.”

ㅁ 추가 학습 내용

GraphSAGE Aggregator별 장단점과 적용 사례
– Mean Aggregator: 구현이 간단하고 연산 속도가 빠르지만 이웃 노드 특성의 세부 정보를 잃을 수 있음. 대규모 그래프나 빠른 추론이 필요한 경우 적합.
– LSTM Aggregator: 이웃 노드 순서에 민감하며 복잡한 패턴 학습 가능. 그러나 순서 의존성이 불필요한 경우 성능 저하 가능.
– Pooling Aggregator: 이웃 특성 중 극값을 강조하여 중요한 특징을 부각. 그러나 평균적 경향은 반영이 약해질 수 있음.

GIN(Graph Isomorphism Network)
– 높은 표현력을 가지며, 그래프 구조를 구분하는 능력이 강함.
– 매개변수 ε은 자기 자신의 특성을 이웃 정보와 결합할 때 자기 정보의 반영 비율을 조절하는 역할.

GAT(Graph Attention Network)
– Multi-head attention은 여러 개의 독립적인 attention을 병렬로 적용하여 안정성을 높이고 다양한 표현을 학습 가능.
– 각 head의 결과를 결합함으로써 과적합을 방지하고 일반화 성능 향상.

Positional Encoding
– Laplacian eigenvector 계산은 계산 복잡도가 높아 대규모 그래프에서는 비효율적.
– 근사 기법(예: 랜덤 워크 기반, 스펙트럼 근사)을 사용하여 계산량을 줄임.

시간 복잡도 및 메모리 사용량 비교
– 각 기법별로 노드 수, 엣지 수에 따른 연산량과 메모리 요구량을 표로 정리하여 비교.

벤치마크 데이터셋 성능 비교
– Cora, PubMed, Reddit 등에서의 정확도, F1-score, 학습 시간, 메모리 사용량 비교 결과 숙지.

Inductive vs Transductive 학습
– Inductive: 학습 시 보지 않은 새로운 노드나 그래프에 대해 일반화 가능 (예: GraphSAGE).
– Transductive: 학습 시 사용한 노드 집합에 대해서만 예측 가능 (예: 기본 GCN).
– 각 기법이 지원하는 학습 방식 명확히 구분.