ㅁ 그래프 신경망 최적화

1. Positional Encoding on Graphs

ㅇ 정의:
그래프의 노드에 절대적 또는 상대적 위치 정보를 부여하여 GNN이 구조적 위치를 학습할 수 있도록 하는 기법. 주로 그래프 라플라시안 고유벡터, 랜덤 워크 기반 임베딩 등을 활용.

ㅇ 특징:
– 노드 간 구조적 구분이 어려운 GNN의 한계를 보완.
– Transformer 구조와 결합 시 성능 향상.
– 라플라시안 고유벡터 기반 방법은 계산 비용이 큼.
– 위치 정보가 없는 순수 메시지 패싱 GNN 대비 장거리 의존성 학습 가능.

ㅇ 적합한 경우:
– 노드의 절대적 위치나 위상 정보가 중요한 그래프.
– 대규모 그래프에서 장거리 관계를 학습해야 하는 경우.
– 그래프 분류, 링크 예측 등에서 구조적 패턴이 중요한 경우.

ㅇ 시험 함정:
– Positional Encoding이 항상 성능을 향상시키는 것은 아님.
– 라플라시안 기반과 랜덤 워크 기반의 차이를 혼동하기 쉬움.
– Transformer의 Positional Encoding과 동일하게 취급하면 오답.

ㅇ 시험 대비 “패턴 보기” 예시:
O: “그래프 라플라시안 고유벡터는 그래프의 절대적 위치 정보를 제공한다.”
X: “Positional Encoding은 모든 그래프에서 성능을 무조건 향상시킨다.”
O: “랜덤 워크 기반 Positional Encoding은 노드 간의 확률적 거리를 반영한다.”
X: “Positional Encoding은 Transformer에서만 사용된다.”

ㅁ 추가 학습 내용

학습 정리

1. 그래프 라플라시안(Laplacian)
– 정의: L = D – A (D는 차수 행렬, A는 인접 행렬)
– 정규화 라플라시안: L_norm = I – D^(-1/2) A D^(-1/2)
– 고유벡터 계산: 라플라시안 행렬의 고유분해를 통해 고유값과 고유벡터를 구함
– Positional Encoding 활용: 고유벡터(특히 하위 고유벡터)를 노드의 위치 정보로 사용

2. Random Walk Positional Encoding
– 전이확률행렬: P = D^(-1) A
– 스펙트럼 특성: P의 고유분해를 통해 그래프의 전이 특성과 구조를 반영한 인코딩 가능

3. 최신 GNN 모델 사례
– SignNet: 라플라시안 고유벡터의 부호 불변성 문제를 해결하여 위치 인코딩 적용
– Graphormer: 그래프 Transformer 구조에서 거리 및 위치 정보를 통합하여 성능 향상

4. 절대적 위치 인코딩 vs 상대적 위치 인코딩
– 절대적: 고유벡터나 좌표 기반으로 각 노드의 절대 위치를 표현
장점: 전역 구조 반영 가능
단점: 그래프 크기 변화나 노드 순서 변화에 민감
– 상대적: 노드 간 거리, 연결 관계 등 상대적 정보로 인코딩
장점: 구조적 불변성 유지
단점: 전역 위치 정보 부족

5. Positional Encoding의 영향
– 과적합: 불필요하게 세밀한 위치 정보는 모델의 일반화 성능 저하 가능
– 계산 복잡도: 고유벡터 계산은 O(N^3) 복잡도를 가짐, 대규모 그래프에서 부담

6. 대규모 그래프에서의 효율적 계산 방법
– 근사 고유벡터 계산: Lanczos, Power iteration 등 반복법 사용
– 샘플링 기반 방법: 그래프 일부만 사용해 근사 위치 인코딩 계산
– 희소 행렬 연산 최적화로 메모리와 계산량 절감