기술 요약: 단순 스펙트럼 그래프에서 Weisfeiler–Leman 은 불완전하므로 이를 표준화하라

문제 제기

그래프 신경망 (GNN) 은 그래프 구조 데이터 학습에 널리 사용되지만, 그 표현력은 종종 Weisfeiler–Leman (WL) 계층에 의해 제한받습니다. $k$-차원 WL 테스트 ($k$-WL) 가 모든 비동형 그래프를 구별할 수 없다는 것은 알려진 사실입니다. 그러나 단순 스펙트럼(인접 행렬이 서로 다른 고유값을 가짐) 을 가진 그래프라는 특정 클래스는 3 차 시간 복잡도 내에서 동형성 테스트가 가능합니다. 이러한 이론적 처리 가능성에도 불구하고, 많은 GNN 의 표현력을 상한으로 하는 WL 계층이 모든 단순 스펙트럼 그래프를 구별할 수 있는지 여부는 여전히 열린 질문이었습니다.

또한, 표현력을 향상시키기 위해 GNN 에 일반적으로 통합되는 스펙트럼 위치 인코딩 (예: 라플라시안 고유벡터) 은 본질적인 모호성으로 인해 고통받습니다. 단순 스펙트럼의 경우 부호 모호성 (sign ambiguity) 이, 반복된 고유값의 경우 기저 모호성 (basis ambiguity) 이 발생하기 때문입니다. 이러한 모호성을 해결하는 기존 방법들 (SignNet, MAP, OAP 등) 은 단순 스펙트럼 그래프에서 명백히 불완전하여, 특정 비동형 쌍을 구별하지 못합니다. 이러한 불완전성은 스펙트럼 GNN 이 이 클래스의 그래프에서 보편적 근사 (universal approximation) 를 달성하는 능력을 제한합니다.

방법론

1. 단순 스펙트럼에 대한 WL 불완전성 증명

저자들은 먼저 전체 WL 계층이 단순 스펙트럼 그래프에서 불완전함을 입증합니다.

• 구성: 그들은 $k$-WL 로 구별할 수 없는 비동형 그래프 쌍을 생성하는 Cai–Fürer–Immerman (CFI) 구성을 활용합니다.
• 인코딩: 표준 CFI 그래프는 단순 스펙트럼을 갖지 않으므로, 저자들은 새로운 정수 인코딩 메커니즘을 도입합니다. 그들은 CFI 인접 패턴을 정수 성분으로 구성된 직교 행렬 $\tilde{X}$로 매핑합니다.
• 다중 그래프 형성: 이 직교 행렬과 서로 다른 정수 고유값의 대각 행렬을 사용하여, 단순 스펙트럼을 가진 한 쌍의 대칭 다중 그래프 ($A_{G,0}$ 및 $A_{G,1}$) 를 구성합니다.
• 결과: 그들은 구성된 이러한 단순 스펙트럼 다중 그래프가 $k$-WL 테스트로 구별되지 않음을 증명하여, WL 계층의 어떤 수준도 이 클래스에 대한 동형성 문제를 해결할 수 없음을 보여줍니다. 이는 문제가 3 차 시간 내에 해결 가능함에도 불구하고 그렇습니다.

2. PRiSM: 완전한 표준화

기존 스펙트럼 방법의 한계를 극복하기 위해, 저자들은 단순 스펙트럼 그래프의 고유분해에 대한 명백히 완전한 표준화 절차인 PRiSM(Partition, Refine, Solve, Match) 을 제안합니다.

• 입력: 고유벡터의 열 단위 정규 직교 행렬 $U$.
• 모호성 군: 이 절차는 모호성 군 $S_n \times \{-1, 1\}^k$(치환 및 부호 반전) 을 처리합니다.
• 네 단계:
  1. 분할 (Partition): 고유벡터 성분의 절대값인 부호 불변 시그니처를 기반으로 정점을 그룹화합니다.
  2. 정제 (Refine): 분할에 WL 색상 정제 절차의 스펙트럼 변형을 적용합니다. 이는 고유벡터 성분의 요소별 곱 ($U_v \odot U_u$) 으로 정의된 엣지 특징의 다중 집합을 사용하여 정점 클래스를 반복적으로 정제하여 분할이 안정화될 때까지 진행합니다.
  3. 해결 (Solve): 안정된 분할은 $\mathbb{Z}_2$ 필드 위의 선형 방정식 시스템을 정의합니다. 이 시스템은 각 분할 클래스에 음수가 아닌 성분이 적어도 한 행을 포함하도록 강제합니다. 이 시스템을 풀면 고유벡터에 대한 고유한 표준 부호 (그래프 자동형사상까지) 를 결정합니다.
  4. 일치 (Match): 부호가 고정되면, 행을 사전식 순서로 정렬하여 치환 모호성을 해결하고 고유한 표준 행렬을 생성합니다.
• 확장: 반복된 고유값 (비단순 스펙트럼) 을 가진 그래프의 경우, PRiSM 은 휴리스틱하게 확장됩니다. 이는 기본 절차를 단순 스펙트럼 블록 ($m=1$) 에 적용하고, QR 분해 및 피벗 선택을 사용하여 고차 고유공간 ($m > 1$) 을 해결합니다.

3. 이론적 보장

• 완전성: PRiSM 은 유효한 표준화임이 증명되었습니다. 즉, 동형 그래프에 대해서는 동일한 출력을, 비동형 단순 스펙트럼 그래프에 대해서는 서로 다른 출력을 생성합니다.
• 보편적 근사: PRiSM 을 보편적 집합 네트워크 (예: DeepSets 또는 Transformer) 와 결합함으로써, 결과 모델은 단순 스펙트럼 그래프에서 임의의 동형 불변 함수에 대해 보편적 근사를 달성합니다. 이는 이 클래스에 대한 스펙트럼 GNN 의 완전성 달성에 대한 열린 문제를 해결합니다.

주요 결과

이론적 발견

• 정리 1: 모든 자연수 $k$에 대해, $k$-WL 알고리즘으로 구별되지 않는 $\Theta(k)$개의 노드를 가진 비동형 단순 스펙트럼 다중 그래프가 존재합니다. 이는 PPGN, $k$-GNN, Graph Transformer 를 포함한 모든 $k$-WL 정렬 GNN 계열이 단순 스펙트럼 그래프에서 불완전함을 의미합니다.
• 정리 2: PRiSM 은 단순 스펙트럼 고유분해에 대한 유효한 표준화를 제공합니다.
• 정리 3: PRiSM 과 보편적 집합 네트워크로 구성된 모델은 단순 스펙트럼 그래프에서 보편적 근사를 달성합니다.

실험적 성능

저자들은 세 가지 벤치마크에서 PRiSM 을 평가했습니다:

1. BREC 표현력 벤치마크: PRiSM 은 비동형 그래프 쌍을 구별하는 데 경쟁 표준화 방법 (MAP, OAP) 보다 우수했습니다. 특히 Regular 및 Extension 카테고리에서 두드러졌습니다. MAP/OAP 가 360 쌍 중 199 쌍을 올바르게 구별한 반면, PRiSM 은 360 쌍 중 212 쌍을 올바르게 구별했습니다.
2. 분자 특성 예측 (ZINC, OGB-Mol): PRiSM 은 GatedGCN 과 PNA 백본을 모두 사용하여 분자 회귀 (ZINC) 및 분류 (MOLTOX21, MOLPCBA) 작업에서 최첨단 성능을 달성하거나 최상위 기록과 동률을 이뤘습니다.
3. Transformer 백본 (OGB, Alchemy): Graph Transformer 의 위치 인코딩으로 사용될 때, PRiSM 은 네 가지 데이터셋 (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY) 전반에 걸쳐 모든 베이스라인 (LPE, MAP, OAP) 을 능가했습니다. 저자들은 PRiSM 이 부호 수정된 고유벡터에 더해 결정론적 정점 순서를 제공하기 때문이라고 설명하며, 이는 Transformer 어텐션 메커니즘에 중요하다고 강조했습니다.

중요성과 주장

이 논문은 GNN 표현력과 스펙트럼 방법에 대한 이론적 이해의 근본적인 격차를 해소했다고 주장합니다:

1. WL 의 불완전성: WL 계층이 그 힘을 증가시킴에도 불구하고, 동형성이 이론적으로 쉬운 클래스인 모든 단순 스펙트럼 그래프를 구별할 수 없음을 명백히 증명합니다.
2. 첫 번째 완전한 표준화: PRiSM 은 이 클래스에서 불완전한 이전 방법들 (MAP 및 OAP 등) 의 한계를 극복하는, 단순 스펙트럼 고유분해에 대한 명백히 완전한 부호 표준화의 첫 번째 사례로 제시됩니다.
3. 보편적 근사: 이 연구는 완전한 표준화 (PRiSM 과 같은) 와 짝을 이룰 경우 스펙트럼 GNN 이 단순 스펙트럼 그래프에서 보편적 근사를 달성할 수 있음을 입증하여, 표준화된 라플라시안 위치 인코딩의 사용을 정당화합니다.
4. 실용적 유용성: 실험적으로, 스펙트럼 모호성을 완전히 해결하는 것이 다운스트림 작업에서 실질적인 개선으로 이어지며, 기존 부호 불변 및 표준화 접근법보다 우수함을 보여줍니다.

저자들은 한계를 지적했는데, 특히 완전성 보장은 단순 스펙트럼 그래프 (또는 증명에서 구성된 다중 그래프) 에만 엄격하게 적용되며, 표준화 절차는 불연속적이라는 점입니다. 그들은 완전한 부호 표준화에 대해 이 불연속성이 수학적으로 피할 수 없는 것이라고 주장합니다. 또한, 다중 엣지가 없는 단순 조합 그래프로의 불완전성 증명 확장은 향후 과제로 남겨둡니다.