기술 요약: RADE – 무작위 에지 추가-삭제(Random Add-Drop Edge) 정규화 기법

문제 정의

그래프 신경망(GNN), 특히 메시 전달 신경망(MPNN)은 두 가지 뚜렷한 문제에 직면해 있습니다: **과적합(Overfitting)**과 **과도한 압축(Over-squashing)**입니다.

• 과적합: 모델이 일반화에 실패하는 광범위한 머신러닝 문제. 기존의 GNN 정규화 기법들은 주로 에지 삭제(예: DropEdge)와 같은 확률적 그래프 증강에 의존합니다. 그러나 이러한 방법들은 모델이 변형된 그래프로 학습하고 추론 시에는 원래의 고정된 그래프를 사용하는 **학습-추론 불일치(train-inference misalignment)**를 유발하여, 잠재적으로 분포 변화(distribution shifts)를 일으킬 수 있습니다.
• 과도한 압축: 레이어 수가 증가함에 따라 먼 거리에 있는 노드의 정보가 고정된 크기의 임베딩으로 압축되어야 하는 구조적 한계로, 장거리 의존성(long-range dependencies) 포착을 방해합니다. 기존 솔루션들은 일반적으로 연결성을 개선하기 위해 결정론적인 리와이어링(rewiring)이나 지름길 에지(shortcut edges)를 추가합니다. 이러한 방법들은 정보 흐름에는 효과적이지만, 학습 과정에서 과적합을 방지하는 정규화 기능은 내재되어 있지 않습니다.

기존 연구들은 이러한 문제들을 각각 독립적으로 다루어 왔습니다. 즉, 확률적 증강은 정규화는 수행하지만 장거리 통신을 개선하지 못하며, 리와이어링 방식은 연결성은 개선하지만 정규화 특성이 부족합니다.

방법론

저자들은 과적합과 과도한 압축을 동시에 해결하기 위해 기존 에지를 삭제하고 비에지(non-edges)를 추가하는 작업을 결합한 확률적 그래프 증강 프레임워크인 **RADE (Random Add-Drop Edge)**를 제안합니다. RADE는 두 가지 핵심 구성 요소로 설계되었습니다.

1. 섭동 메커니즘 (Perturbation Mechanism)

각 학습 에포크마다 RADE는 입력 그래프 $G$로부터 섭동된 인접 행렬 $A'$를 샘플링합니다:

• 에지 삭제 (Edge Deletion): 기존 에지는 확률 $p$로 삭제됩니다.
• 에지 추가 (Edge Addition): 비에지는 확률 $q$로 추가됩니다.
  이는 DropEdge(여기서 $q=0$)를 일반화한 것이며, 순수 무작위 에지 추가(여기서 $p=0$)도 가능하게 합니다.

2. 집계-교정 메커니ận (Aggregation-Correction Mechanism)

학습-추론 불일치를 방지하기 위해, RADE는 메시 집계를 위한 명시적인 교정 규칙을 도입합니다. 저자들은 학습 목적에 따라 두 가지 변형을 제안합니다:

• RADE-OF (Overfitting only): 원래 입력 그래프의 추론 시 집계와 **기댓값 보존(expectation-preserving)**이 이루어지도록 하여 과적합을 타겟팅합니다.

  • 메커니즘: 기존 에지 상의 메시는 기대 기여도에 맞게 재스케일링됩니다. 새로 추가된 에지 상의 메시는 전체 기대 기여도가 0이 되도록 중심화(가중 평균을 뺌)됩니다.
  • 결과: 무작위 섭동은 추론 규칙을 변화시키지 않으면서 순수하게 분산 기반의 정규화 역할을 수행합니다.

• RADE-OFS (Overfitting and Over-squashing): 두 문제를 모두 타겟팅합니다.

  • 메커니즘: 삭제 효과를 교정(기존 에지 재스케일링)하면서도, 추가된 에지의 기대 기여도는 유지합니다.
  • 추론 정렬: 추론 시의 집계는 추가된 에지의 결정론적인 기대 기여도를 포함하도록 수정됩니다.
  • 결과: 학습은 확률성에 의해 정규화되는 동시에, 추론 시에는 밀집된 그래프 구조의 이점을 얻어 장거리 통신을 위한 추가적인 경로를 생성합니다.

3. 적응형 비율 선택 (Adaptive Rate Selection - GradNorm)

$p$와 $q$에 대한 데이터셋별 하이퍼파라미터 튜닝을 피하기 위해, RADE는 **미니 배치 그래디언트 노름 균형 알고리즘(mini-batch gradient-norm balancing algorithm)**을 채택합니다.

• 이 알고리즘은 분산 기반 정규화 효과를 암묵적인 목적 함수로 취급합니다.
• 정규화 프록시의 그래디언트 노름을 지도 학습 손실(supervised loss)의 그래디언트 노름과 일치시키도록 학습 중에 $p$와 $q$를 동적으로 조정합니다.
• 패널티 항을 통해 그래프의 밀도에 상대적인 추가율을 정규화함으로써 과도한 그래프 밀집화를 방지합니다.
• 이를 통해 RADE는 실제 적용 시 효과적으로 하이퍼파라미터가 필요 없는(hyperparameter-free) 상태가 됩니다.

주요 기여

1. 통합 프레임워크: RADE는 단일 확률적 증강 프레임워크 내에서 무작위 에지 삭제와 추가를 모두 사용하여 과적합과 과도한 압축을 동시에 해결하는 최초의 방법입니다.
2. 이론적 정렬: 논문은 **기댓값 보존 집계(expectation-preserving aggregation)**에 대한 원칙적인 유도를 제공하여, 확률적 학습이 추론 규칙과 일치하도록 보장함으로써 분포 변화를 제거합니다.
3. 원시 요소의 비교환성 (Non-Interchangeability of Primitives): 저자들은 에지 삭제와 에지 추가가 서로 교환 불가능한 정규화 효과를 유도한다는 점을 이론적, 경험적으로 입증했습니다. 두 연산은 서로 다른 노드별 통계량(기존 에지 vs 비에지)에 작용하며, 이를 결합했을 때 단독 사용 시보다 우수한 성능을 냅니다.
4. 적응형 정규화: GradNorm 기반의 규칙을 도입하여 삭제 및 추가 비율을 적응적으로 튜닝함으로써 수동적인 하이퍼파라미터 탐색의 필요성을 없앴습니다.

실험 결과

저자들은 다양한 노드 및 그래프 분류 벤치마크에서 GCN, GIN, GAT 백본을 사용하여 RADE-OF와 RADE-OFS를 평가했습니다.

• 노드 분류: RADE-OF는 대부분의 데이터셋에서 경쟁력 있는 정규화 기법들(Dropout, DropEdge, DropNode, DropMessage)보다 일관되게 우수한 성능을 보였습니다. RADE-OFS는 중간 정도의 과도한 압축이 발생하는 데이터셋(예: PubMed)에서 대등하거나 약간 더 나은 성능을 보였습니다.
• 그래프 분류: RADE-OFS는 특히 과도한 압축 문제를 겪거나 장거리 상호작용이 필요한 데이터셋(예: peptides-func, MUTAG)에서 가장 유의미한 이득을 보였습니다. 이 작업들에서 모든 베이스라인을 능가했습니다.
• 절제 연구 (Ablation Studies):
  • 기댓값 보존 교정(EPC) 또는 적응형 비율 선택(GradNorm)을 제거하면 성능이 크게 저하되었으며, 이는 두 요소 모두의 필요성을 확인시켜 줍니다.
  • RADE를 "Drop-only"와 "Add-only" 변형으로 분해했을 때, 결합된 접근 방식이 단일 구성 변형보다 일관되게 우수한 성능을 보여 두 연산의 상호 보완적인 성격을 검증했습니다.
  • 적응형 비율 선택 방식이 고정된 미세 조정 비율보다 모든 데이터셋에서 우수한 성능을 보였습니다.

의의 및 주장

본 논문은 RADE가 정규화와 연결성 강화 사이의 간극을 메우는 단순하고 효과적인 증강 프레임워크라고 주장합니다.

• 과적합 측에 대하여: RADE-OF는 학습과 추론을 일치시켜 표준적인 확률적 증강의 문제점들을 피하는 견고하고 하이퍼파라미터가 필요 없는 정규화 도구 역할을 합니다.
• 과도한 압축 측에 대하여: RADE-OFS는 추론 시 추가된 에지의 이점을 유지함으로써 과도한 압축을 효과적으로 완화하며, 장거리 정보 흐름이 필요한 작업에 특히 적합합니다.
• 실용성: 그래디언트 노름 균형 규칙을 사용함으로써, RADE는 번거로운 데이터셋별 섭동 비율 튜닝을 제거하여 기존 GNN 학습 파이프라인에 바로 적용 가능한 실용적인 도구가 됩니다.

저자들은 무작위 에지 삭제와 추가를 결합하고, 이를 기댓값 보존 교정과 적응형 비율로 제어하는 것이 GNN의 가장 지속적인 두 가지 과제에 대한 통합된 솔루션을 제공한다고 결론짓습니다.