그래프 신경망을 위한 절단된 위치 인코딩 이해하기

위치 인코딩(PEs)은 그래프 신경망(GNNs)의 성능을 이론적 및 경험적으로 향상시킵니다. 가장 인기 있는 PE 계열 중 두 가지—스펙트럴(예: 라플라시안 고유 공간, 유효 저항)과 워크 기반(인접 행렬의 다항식)—는 1-WL 테스트와 3-WL 테스트 사이에서 표현력 측면에서 이론적으로 동등합니다. 그러나 이러한 등가성은 GNN이 PE의 '완전한' 버전을 사용할 때를 가정하며, 이는 $O(n^3)$ 시간 및 공간 복잡도를 요구합니다. 대신, 실무자들은 첫 $k$개의 고유 공간이나 인접 행렬의 거듭제곱과 같은 절단된 변형을 흔히 사용합니다. 하지만 이러한 절단된 PE의 이론적 속성은 알려져 있지 않습니다. 본 연구에서는 이 절단된 PE에 대한 연구를 시작합니다. 이론적으로, 우리는 절단 조건 하에서 여러 PE 계열이 표현력 측면에서 근본적으로 다르다는 것을 보여줍니다. 그 결과로, 우리는 절단된 스펙트럴 PE가 더 이상 1-WL 테스트보다 강력하지 않음을 보여줍니다. 또한, 우리는 유사하게 관련된 절단된 PE 간의 표현력 차이를 강조하기 위해 $k$-하모닉 거리라는 스펙트럴 PE 계열을 연구합니다. 마지막으로, 실제 데이터셋에서 여러 절단된 PE를 혼합하는 것이 단일 계열보다 선호됨을 실험적으로 보여줍니다.