기술 요약: 계층적 다중 스케일 그래프 신경망 (HMH)

1. 문제 제기

실제 세계의 그래프는 종종 인접한 노드가 서로 다른 레이블이나 특성을 갖는 **이질성 (heterophily)**을 나타냅니다. 기존 그래프 신경망 (GNN) 은 이러한 데이터를 처리하는 데 진전을 이루었지만, 특히 차수 불균형 (허브 지배적) 그래프에서는 세 가지 치명적인 병리 현상에 시달립니다.

1. 허브 지배 (Hub Domination): 차수가 높은 "허브" 노드가 있는 그래프에서 기존 메시지 전달 메커니즘은 이러한 허브가 집계 과정을 지배하도록 허용합니다. 이는 저차수 "스포크" 노드 (작은 클러스터) 의 신호를 압도하여 서로 다른 클러스터의 임베딩이 공통된 허브 유발 표현으로 수렴하게 만들고, 결과적으로 결정 경계를 지워버립니다.
2. 과평활화 (Oversmoothing): GNN 의 깊이가 증가함에 따라 노드 임베딩은 정적 분포 (클래스 평균) 로 수렴하는 경향이 있어 특징들이 구별 불가능해집니다. 이는 의미적으로 관련 없는 영역의 신호를 혼합하는 비최적 다항식 필터에 의해 더욱 악화됩니다.
3. 과압축 (Oversquashing): 먼 노드에서의 정보는 그래프 거리에 따라 지수적으로 감소하여 장거리 정보 흐름을 방해하는 병목 현상을 만듭니다.

기존의 스펙트럴 접근법 (예: ChebNet, BernNet) 은 종종 연속 직교성을 가정하는 글로벌 다항식 기저 (체비셰프, 야코비) 에 의존합니다. 그러나 실제 그래프는 이산 스펙트럴 측도를 가지므로 주파수 누출, 표현력 저하, 그리고 국소 구조적 이질성에 대한 적응 실패를 초래합니다. 반면, 공간적 접근법 (예: 부호 메시지 전달) 은 종종 계층 간 부호 상쇄로 고통받거나, 영역 간 신호를 혼합하는 비용이 많이 드는 글로벌 집계 단계를 필요로 합니다.

2. 방법론: 계층적 다중 뷰 HAAR (HMH)

저자들은 앞서 언급한 병리 현상을 완화하면서 거의 선형 시간에 확장 가능한 스펙트럴 그래프 학습 프레임워크인 HMH를 제안합니다. 이 프레임워크는 그래프 신호의 계층적, 다중 해상도 분석을 통해 작동합니다.

2.1. 적응형 이질성 인코더

이 과정은 노드 레이블 없이 특징 및 구조 인식 부호 친밀도를 학습하는 이질성 인식 인코더로 시작합니다.

• 적응형 유사도: 인코더는 학습 가능한 가중치를 가진 특징 친밀도와 공유된 2 홉 이웃을 기반으로 한 구조적 유사도를 결합하여 유사도 점수를 계산합니다.
• 부호화 인접 행렬: 이러한 점수는 연속적인 부호화 인접 행렬 ($A_{adp}$) 로 변환됩니다. 높은 유사도는 양의 가중치 (저역 통과 동작) 를, 낮은 유사도는 음의 가중치 (고역 통과 동작) 를 생성합니다.
• 부호 안정성: 고정된 부호 메시지 전달 (SMP) 이 주기적인 부호 뒤집기 ($S^2 = I$) 로 고통받는 것과 달리, HMH 의 적응형 인접 행렬은 현재 임베딩에 기반하여 매 계층마다 재계산되어 경직된 진동과 부호 상쇄를 방지합니다.

2.2. 계층적 그래프 조밀화

인코더의 노드 점수를 사용하여 HMH 는 재귀적 클러스터링 과정을 통해 소프트 그래프 계층 구조를 구축합니다.

1. 클러스터링: 노드는 인코더 임베딩에 대한 $k$-means++ 를 사용하여 클러스터 (초노드) 로 그룹화됩니다.
2. 소프트 할당: 확률적 할당 행렬 ($A_s$) 이 미세 노드를 거친 클러스터로 매핑하며, 이는 온도 파라미터에 의해 제어됩니다.
3. 집계: 특징과 간선은 다음 계층의 계층 구조를 형성하기 위해 집계됩니다. 이 과정은 임계값에 도달할 때까지 반복되어 트리 구조를 생성합니다.

2.3. 클래스 인식 Haar 기저 및 스펙트럴 필터링

각 계층 수준에서 HMH 는 해당 수준의 특정 클러스터 구조에 맞춘 희소 직교 Haar 기저 ($U^{(\ell)}$) 를 구축합니다.

• 기저 구축: 기저는 저주파 추세를 포착하는 글로벌 스케일링 벡터와 웨이브릿으로 구성됩니다. 웨이브릿은 다음과 같이 나뉩니다.
  • 클러스터 간 웨이브릿: 서로 다른 초노드 간의 대비를 포착합니다.
  • 클러스터 내 웨이브릿: 클러스터 내의 국소적 변동을 포착합니다.
• 대각선 필터링: 그래프 신호는 이 기저에 투영됩니다. 학습 가능한 대각선 이득 행렬 ($\Lambda^{(\ell)}$) 이 적용되어 고주파 (이질성) 채널을 선택적으로 증폭하고 저주파 (동질성) 또는 허브 지배적 신호를 감쇠시킵니다.
• 국소성: Haar 기저는 엄격하게 국소화되어 (지지 영역이 작은 이웃으로 제한됨) 관련 없는 그래프 영역 간의 정보 누출을 방지하여 허브 지배 문제를 직접적으로 해결합니다.

2.4. 스킵 연결된 언풀링

원본 해상도를 복원하기 위해 HMH 는 스킵 연결된 언풀링을 사용합니다. 모든 계층 수준의 출력이 원래 노드로 다시 집계됩니다. 이는 각 노드가 계층의 모든 수준에서 다중 스케일 컨텍스트가 보강된 기본 특징을 유지하도록 보장하여, 과압축과 관련된 지수적 감쇠를 효과적으로 우회합니다.

3. 주요 기여

이 논문은 네 가지 주요 기여를 주장합니다.

1. 레이블 없는 적응형 부호 친밀도: 학습된 특징/구조 유사도에 기반하여 양/음 가중치를 할당하는 메커니즘으로, 고정된 SMP 모델에서 발견되는 부호 상쇄 병리 현상을 방지합니다.
2. 거의 선형 직교 기저 구축: 고유값 분해의 $O(n^3)$ 비용과 조밀한 다항식 기저의 $O(n^2)$ 비용을 피하면서 거의 선형 시간에 다중 스케일, 희소, 직교 스펙트럴 기저 (Haar) 를 구축하는 첫 번째 프레임워크입니다.
3. 병리 현상의 이론적 완화: HMH 가 허브 지배, 과평활화, 과압축을 극복한다는 엄격한 증명과 실증적 증거를 제시합니다. 구체적으로, 국소화된 기저는 에너지를 2 홉 이웃으로 제한하고, 계층적 구조는 통신 경로를 로그적으로 단축시킵니다.
4. 최첨단 성능: 동질성 및 이질성 데이터셋을 포함한 노드 및 그래프 분류 작업에서 최첨단 성능을 입증했습니다. 여기에는 OGBN-ArXiv 와 같은 대규모 벤치마크가 포함됩니다.

4. 실험 결과

저자들은 다양한 데이터셋 세트를 사용하여 HMH 를 평가했습니다.

• 노드 분류: HMH 는 표준 동질성 벤치마크 (Cora, Citeseer) 와 까다로운 이질성 데이터셋 (Chameleon, Squirrel, Texas, Roman-empire, Amazon-ratings 등) 에서 테스트되었습니다.

  • 성능: HMH 는 최첨단 스펙트럴 베이스라인 (예: ChebNetII, BernNet, UniFilter) 대비 노드 분류 작업에서 최대 3% 개선을 달성했습니다.
  • 허브 분석: 차수 계층화 평가 (스포크 vs 허브) 에서 HMH 는 성능 격차를 크게 줄였습니다. 예를 들어, Penn94 데이터셋에서 베이스라인이 일반적으로 허브 지배로 고통받는 반면, HMH 는 "스포크"(저차수) 정확도를 10.8% 향상시켰습니다.
  • 깊이 안정성: 깊이에 따라 급격히 저하되는 (과평활화) GCN 과 달리, HMH 는 깊이에 따라 안정적으로 유지되었으며 심지어 개선되었습니다 (Penn94 에서 32~64 계층에서 정점).
  • 과압축: Tree-NeighborsMatch 벤치마크에서 HMH 는 깊이 10 에서 98% 이상의 정확도를 유지한 반면, 베이스라인은 깊이 8 에서 무작위 추측 (50%) 으로 떨어졌습니다.

• 그래프 분류: TU 데이터셋 (MUTAG, PROTEINS 등) 에서 평가되었습니다.

  • 성능: HMH 는 그래프 분류 데이터셋에서 7% 포인트 개선을 달성했으며, 특히 MUTAG 에서 **94.5%**에 도달했습니다.
  • 확장성: 이 프레임워크는 거의 선형 확장성을 입증했습니다. REDDIT-12K 데이터셋에서 HMH 는 고유값 분해 기반 베이스라인보다 에포크당 8.1 배 빠르며, 메모리는 3.9 배 적게 사용했습니다.

5. 중요성 및 주장

이 논문은 HMH 를 이질성 환경에서 현재 스펙트럴 및 공간 GNN 의 근본적인 한계를 해결하는 솔루션으로 위치시킵니다.

• 이론적 중요성: 저자들은 국소화된 직교 Haar 기저를 사용하여 신호 에너지를 엄격하게 제한함으로써, 작은 클러스터가 고차수 노드에 의해 잠식되는 "허브 에일리어싱" 현상을 방지한다고 주장합니다. 계층적 구조는 유효 경로 길이를 로그적으로 단축함으로써 과압축의 부재를 이론적으로 보장한다고 주장합니다.
• 실용적 중요성: 이 프레임워크는 비용이 많이 드는 스펙트럴 방법에 대한 확장 가능한 대안을 제공하여 대규모 그래프 (예: 약 17 만 노드가 있는 OGBN-ArXiv) 에 대한 고성능 이질성 학습을 가능하게 합니다.
• 겸손함: 저자들은 현재 한계를 인정하며, 공식화가 정적 그래프를 가정하고 있으며, 동적 또는 다중 관계 그래프로의 확장은 향후 연구 방향이라고 언급합니다. 그들은 실제 세계 배포에 중요한 요소인 선형 확장성을 유지하면서 개선을 달성했다고 강조합니다.