WidthWall: Hypergraph Neural Networks를 위한 엄격한 표현력 계층 구조

Hypergraphs (하이퍼그래프)는 과학적, 사회적, 생물학적 시스템에서 고차 상호작용 (higher-order interactions)을 모델링하기 위한 자연스러운 프레임워크를 제공합니다. Hypergraph neural networks (HGNNs, 하이퍼그래프 신경망)는 이러한 데이터로부터 학습하는 것을 목표로 하지만, 이러한 모델들이 어떤 고차 구조를 표현할 수 있는지는 여전히 불분명합니다. 본 연구에서는 하이퍼그래프의 표현력 (expressivity)이 아키텍처가 어떤 작은 패턴을 탐지하고 셀 수 있는지에 의해 결정됨을 보여줍니다. 우리는 이를 하이퍼그래프 내에서 구조적 모티프 (structural motif)가 얼마나 자주 나타나는지를 측정하는 준동형 밀도 (homomorphism densities)를 통해 공식화합니다. 고전적인 준동형 개수 완비성 (homomorphism-count completeness)과 불변량 근사 (invariant approximation)를 결합하여, 우리는 준동형 밀도가 모든 연속적인 하이퍼그래프 불변량 (hypergraph invariants)을 생성하며, 이를 hypertree width (하이퍼트리 너비)로 인덱싱된 엄격한 계층 구조로 조직함을 보여줍니다. 이는 Width Wall (너비 장벽)을 생성합니다: 즉, 어떠한 은닉 차원 (hidden dimension), 학습 절차 (training procedure) 또는 고정된 깊이의 HGNN도 더 넓은 패턴을 요구하는 불변량을 표현할 수 없는 근본적인 아키텍처적 한계입니다. 우리의 프레임워크는 15가지 HGNN 아키텍처에 대한 통합된 특성화를 제공하고, clique expansion (클리크 확장)에 의해 손실되는 정보를 정확하게 식별하며, 유계 너비 메시지 전달 (bounded-width message passing)을 넘어 표현력을 확장하는 밀도 인식 모델 (density-aware models)의 동기를 부여합니다. 우리는 실제 하이퍼그래프의 APPLICATION NODE CLASSIFICATION SUITE (애플리케이션 노드 분류 스위트)에서 이 발견을 실험적으로 검증하였으며, 여기서 Width Wall은 그래프 축소 베이스라인 (graph-reduction baselines)이 실패하는 시점과 밀도 특징 (density features)이 도움이 되는 시점을 예측합니다.