정규화된 보정 GNN 전파(Normalized Corrected GNN Propagation)의 스펙트럼 이론

우리는 extit{정규화된 보정 GNN 전파 (normalized corrected GNN propagation)}를 위한 스펙트럼 이론 (spectral theory)을 개발합니다. 연구 대상은 차수-정상 성분 (degree-stationary component)이 제거된 대칭 정규화 인접 행렬 (symmetric normalized adjacency)이며, 이는 표준 GCN 스타일 모델에서 사용되는 정규화와 일치하면서 오버스무딩 (oversmoothing)과 가장 직접적으로 연결된 정상 방향 (stationary direction)을 격리합니다. 핵심적인 이론적 질문은 이 보정된 정규화 연산자 (corrected normalized operator)가 많은 전파 레이어 (propagation layers)를 거친 후에도 클래스 판별 신호 (class-discriminative signal)를 보존하는지 여부입니다. 우리의 주요 결과는 명시적인 그래프-신호 (graph-signal) 및 특징-SNR (feature-SNR) 조건 하에서, 임의의 고정된 $B>4$에 대해 밀집된 폴리로그(polylogarithmic) 영역 $p \ge C\log^B n/n$ 내에서 $k=O(\log n)$ 전파 단계 이후 이진 문맥적 확률 블록 모델 (binary Contextual Stochastic Block Model)에 대한 고확률 정확 복구 정리 (high-probability exact-recovery theorem)입니다. 또한 우리는 대부분의 노드가 클래스 중심 (class centers)으로 수축함을 보여주는 다중 클래스 부분 복구 정리 (multi-class partial recovery theorem)를 확립합니다. 이론이 예측하는 깊이 (depth), 그래프 신호 (graph signal), 그리고 특징 노이즈 (feature noise)에 대한 의존성을 경험적으로 확인하기 위해 합성 및 실제 노드 분류 (node-classification) 실험이 포함되었습니다.