연구진은 Weisfeiler-Leman (WL) 테스트가 단순 스펙트럼 그래프를 완벽하게 구별할 수 없음을 증명했어요. WL 계층은 널리 사용되는 그래프 신경망(GNN)의 구별력을 상한으로 제한하기 때문에, 이 불완전성은 모든 GNN에 적용돼요.
연구진은 단순 스펙트럼 그래프의 완전한 표현력을 달성하는 첫 번째 정규화 방법인 PRiSM을 소개했어요. PRiSM은 기존 정규화 방법이 부족했던 완전성 보장을 제공해요.
DeepSets 또는 Transformer와 결합된 PRiSM은 단순 스펙트럼 그래프에서 범용 근사 성능을 달성하며, 정규화된 Laplacian 위치 인코딩 사용을 정당화해요. 실험적으로 그래프 회귀, 분류, 표현력 측면에서 기존 방법보다 우수한 성능을 보여요.