SpectralMLP: Message-Passing-Free Dual-Frequency Spectral Filtering on Hypergraphs

기술 요약: SpectralMLP

문제 정의
현재의 하이퍼그래프 신경망(HGNN)은 노드 표현을 풍부하게 하기 위해 로컬 메시 전달(local message passing), 글로벌 어텐션(global attention), 또는 스펙트럴 투영(spectral projection)과 같은 집계(aggregation) 메커니즘에 주로 의존합니다. 이러한 접근 방식은 심각한 실질적 한계에 직면해 있습니다. 로컬 메시 전달은 오버스쿼싱(over-squashing)과 노이즈 민감도 문제를 겪으며, 글로벌 어텐션은 $O(N^2)$의 복잡도를 가져 확장성이 제한되고, 정확한 스펙트럴 방법론은 $O(N^3)$의 고유값 분해(eigendecomposition)를 요구하여 대규모 그래프에서는 실행 불가능합니다. 또한, 기존의 스펙트럴 방법들은 "스펙트럴 퇴화(spectral degeneration)" 현상을 해결하지 못하는 경우가 많습니다. 이는 라플라시안 고유값들이 매우 밀집되어 나타나는 현상(예: $\lambda_{max} - \lambda_{min} < 10^{-4}$)으로, 이로 인해 표준 필터가 상수 응답으로 붕괴되어 주파수 식별 능력을 상실하게 됩니다. 아울러, 단일 스펙트럴 응답은 동종성(homophilic) 그래프에 유익한 저주파 신호와 이종성(heterophilic) 또는 다중 클래스 작업에 필요한 고주파 신호를 동시에 포착할 수 없습니다.

방법론
저자들은 학습 가능한 야코비 다항식 기저(Jacobi polynomial bases)를 사용하여 집계를 **이중 주파수 스펙트럴 필터링(dual-frequency spectral filtering)**으로 대체하는 메시 전달이 없는 프레임워크인 SpectralMLP를 제안합니다. 이 프레임워크는 세 가지 주요 구성 요소로 이루어져 있습니다:

1. MLP 백본(Backbone): MLP는 그래프 연산 없이 입력 특징을 은닉 표현으로 변환하며, 비교를 위한 공정한 베이스라인 역할을 합니다.
2. 적응형 이중 주파수 스펙트럴 필터(ADF-SF): 이것이 핵심 혁신입니다. ADF-SF는 단일 필터 대신, 독립적으로 매개변수화된 두 개의 브랜치로 은닉 표현을 분해합니다:
   • 저주파 브랜치(Low-frequency branch): 학습 가능한 야코비 다항식 기저와 매개변수 $(\alpha_l, \beta_l)$ 및 계수 $\theta_{low}$에 의해 제어됩니다.
   • 고주파 브랜치(High-frequency branch): 별도의 학습 가능한 야코비 기저와 매개변수 $(\alpha_h, \beta_h)$ 및 계수 $\theta_{high}$에 의해 제어됩니다.
   • 적응형 게이팅(Adaptive Gating): 학습된 게이트($g = \sigma(W_g[h_{low}; h_{high}] + b_g)$)가 노드별로 이 브랜치들을 동적으로 융합하여, 모델이 동종성 및 이종성 신호 사이의 균형을 적응적으로 맞출 수 있도록 합니다.
   • 잔차 연결(Residual Connection): 필터링된 출력은 학습 가능한 스케일 $\beta_{res}$를 통해 원래 신호와 결합되어 안정성과 신호 보존을 보장합니다.
3. 구현 세부 사항: 이 방법은 3항 재귀 관계(three-term recurrence relations)를 사용하여 희소 정규화 라플라시안(clique expansion을 통해 도출됨)에서 직접 작동합니다. 이를 통해 고유값 분해를 완전히 배제하며, 레이어당 복잡도를 $O(K \cdot \text{nnz} \cdot H)$로 낮춥니다 (여기서 $K$는 다항식 차수, $\text{nnz}$는 라플라시안의 비제로 원소 수).

학습 목적 함수는 크로스 엔트로피 손실(cross-entropy loss)과 함께, 샘플링을 통해 효율적으로 계산되는 동일 하이퍼엣지 내 노드 간의 유클리드 거리를 페널티화하는 구조 인식 평활화 정규화 항(structure-aware smoothness regularizer)을 결합합니다.

주요 기여

• 메시 전달이 없는 프레임워크: SpectralMLP는 학습 가능한 집계 연산자 없이도 스펙트럴 필터링만으로 하이퍼그래프 노드 분류에 충분하다는 것을 입증했습니다.
• 학습 가능한 야코비 기저: 본 논문은 하이퍼그래프에 학습 가능한 야코비 다항식 필터링을 최초로 적용했습니다. 매개변수 $(\alpha, \beta)$를 학습 가능하게 만듦으로써, 모델은 각 데이터셋의 특정 스펙트럴 분포에 맞춰 다항식 기저를 적응시키며, 필터당 단 두 개의 매개변수만을 추가합니다.
• 이중 주파수 아키텍처: 이 프레임워크는 저주파 및 고주파 처리를 분리함으로써 하이퍼그래프의 다양한 스펙트럴 특성을 명시적으로 다룹니다. 이 설계는 모델이 동종성과 이종성을 모두 처리할 수 있게 하며, 결정적으로 표준 필터가 실패하는 스펙트럴 퇴화 문제를 완화합니다.
• 계산 효율성: 이 방법은 고유값 분해와 이웃 확장을 제거하고, 오직 희소 행렬-벡터 곱(sparse matrix-vector products)에만 의존합니다.

실험 결과
저자들은 10개의 하이퍼그래프 노드 분류 데이터셋(101개에서 41,302개의 노드 범위)에 대해 메시 전달 HGNN, 트랜스포머 기반 모델, MLP 기반 방법 등 9개의 베이스라인과 함께 SpectralMLP를 평가했습니다.

• 성능: SpectralMLP는 10개 데이터셋 중 7개에서 1위 또는 2위를 차지했습니다.
  • 스펙트럴 퇴화: 심각한 스펙트럴 퇴화($\lambda_{max} - \lambda_{min} < 10^{-4}$) 특성을 가진 Congress 데이터셋에서, SpectralMLP는 **95.88%**의 정확도를 달 기록하며 MLP 베이스라인(70.47%)과 다른 최첨단 방법들을 크게 압도했습니다. 이는 균일 설정(uniform settings) 하에서 MLP 베이스라인 대비 **+27.9%**의 성능 향상을 의미합니다.
  • 다중 클래스 작업: ModelNet40(40개 클래스)에서 SpectralMLP는 **98.08%**를 달성하여 모든 베이스라인을 넘어섰습니다.
  • 강건성: 이중 주파수 모드는 견고한 "제로 구성(zero-configuration)" 기본값 역할을 수행했으며, 모든 데이터셋에서 가장 우수한 단일 브랜치 변형의 성능 대비 1% 이내의 차이를 보였습니다.
• 매개변수 효율성: SpectralMLP는 MLP 백본 대비 중간값으로 약 **2.4%**의 매개변수만을 추가했습니다. 총 매개변수 수는 대부분의 메시 전달 베이스라인(예: AllSet, HyperGT, SheafHyperGCN)보다 적었으며, 이는 스펙트럴 필터링이 학습 가능한 집계의 효율적인 대안임을 확인시켜 줍니다.

의의 및 주장
본 논문은 SpectralMLP가 필터링이 표현력 측면에서 집계와 이론적으로 동일함을 증명함으로써 하이퍼그래프 학습의 새로운 패러다임을 구축한다고 주장합니다. 저자들은 집계를 우회함으로써 오버스쿼싱, $O(N^2)$ 어텐션 비용, $O(N^3)$ 고유값 분해를 피할 수 있다고 설명합니다. 이중 주파수 설계는 표준 스펙트럴 필터의 "일률적인(one-size-fits-all)" 한계에 대한 해결책으로 제시되며, 모델이 다양한 작업에 대해 최적의 주파수 균형을 자동으로 발견할 수 있게 합니다. 특히 Congress 데이터셋의 결과는 기존 스펙트럴 방법들이 퇴화하는 시나리오에서 이 방법이 성능을 회복하는 능력을 강조합니다.

한계 및 향후 과제
저자들은 현재의 MLP 백본이 성능의 상한선을 설정하고 있음을 언급하며, 고용량 잔차 연결(high-capacity residual connections)이나 어텐션이 강화된 MLP를 사용하면 결과를 더욱 개선할 수 있을 것이라고 제안합니다. 향-후 연구 방향으로는 하이퍼그래디언트 최적화(hypergradient optimization)를 통한 적응형 다항식 차수($K$) 개발과, clique expansion 대신 하이퍼그래프 인시던스 구조(incidence structure)에서 직접 작동하는 스펙트럴 필터를 설계하는 것이 포함됩니다.