The Polynomial Counting Capabilities of Message Passing Neural Networks

기술적 요약: 메시지 전달 신경망의 다항식 카운팅 능력

문제 제기
최근 연구에 따르면 메시지 전달 신경망 (MPNN) 은 첫 번째 논리식 (first-order logic) 의 카운팅을 포함하는 부분식 (FOC2) 이나 선형 정수 산술 확장으로 종종 특징지어지는, 임계값까지 카운팅하거나 선형 산술 제약을 만족하는 논리적 속성을 표현할 수 있음이 입증되었습니다. 그러나 다항식 커널과 같은 고급 그래프 분류 기법과 관련된 **다항식 카운팅 제약 (비선형 산술)**에 관한 MPNN 의 표현력에 대한 이해에는 여전히 간극이 존재합니다. 본 논문은 **평균 집계 (mean aggregation)**를 사용하는 MPNN 이 **페아노 모달 논리 (PML)**로 정의된 속성을 인식할 수 있는 조건을 조사합니다. PML 은 선형 제약뿐만 아니라 다항식 제약 (예: $x_1^2 \cdot x_2 \leq x_3$) 을 허용함으로써 등급 모달 논리 (Graded Modal Logic) 를 확장합니다.

방법론
저자들은 MPNN 의 표현 능력을 분석하기 위해 PML 의 부분식들과 비교하는 형식적 프레임워크를 사용합니다.

• 모델 정의: 이 연구는 로컬 (이웃) 및 글로벌 (전체 그래프) 정보 모두에 대해 평균 집계를 사용하는 MPNN($M_{mean}$) 에 초점을 맞춥니다. 저자들은 또한 추가적인 합 (sum) 또는 최대 (max) 집계를 허용하는 변형 ($M_{mean, x}$) 을 고려합니다.
• 논리 정의: 그들은 PML 을 정의하는데, 여기서 모달 식 $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$은 특정 이웃 (모달리티 $\pi \in \{id, E_{in}, E_{out}, \top\}$으로 정의됨) 내에서 부분식 $\phi_i$를 만족하는 노드를 카운트하고, 해당 카운트가 페아노 산술 제약 $\psi$를 만족하는지 확인합니다.
• 인식 프레임워크: MPNN 이 특정 그래프 클래스에서 식 $\phi$를 "인식"한다고 함은, 그래프가 $\phi$를 만족할 때 집중 노드 $v$에 대한 네트워크의 출력 상태가 0 이 아닌 (구체적으로 $\geq c(|V|)$) 경우이고, 그렇지 않으면 0 인 경우를 말합니다. 여기서 확신도 $c(|V|)$는 그래프 크기에 의존할 수 있습니다.
• 구축 전략: 증명들은 계층별로 특정 MPNN 아키텍처를 구축하는 것을 포함합니다. 이러한 구축은 집계된 값에 대해 산술 연산 (곱셈, 덧셈, 비교) 을 수행하기 위해 "가젯"(ReLU 뉴런의 조합) 을 활용합니다. 다루어지는 주요 기술적 과제는 다양한 차수의 다항식 항을 평가할 때 평균 집계에 의해 도입된 분모 (예: $1/|V|$ 또는 $1/|neigh(v)|$) 를 처리하는 것입니다.

주요 기여 및 결과
본 논문은 평균 MPNN 이 다항식 카운팅 속성을 포착할 수 있게 하는 입력 그래프에 대한 특정 구조적 가정을 식별합니다. 결과는 모달리티의 깊이 (얕음 vs 중첩) 와 사용된 모달리티의 유형 (글로벌 vs 로컬) 에 따라 분류됩니다.

1. 글로벌 모달리티 (얕은 깊이):

   • 동질적 제약: 글로벌 모달리티 ($\top$) 와 동질적 페아노 항 (상수 항 없음, 모든 단항식의 차수 동일) 만을 사용하는 식의 경우, 평균 MPNN 은 추가적인 그래프 가정 없이 논리를 인식할 수 있습니다 (Lemma 1).
   • 일반 다항식 제약: 임의의 글로벌 다항식 제약 (비동질적 항과 상수 포함) 을 인식하기 위해서는 입력 그래프에 표시된 노드(고유한 색상을 가진 노드) 가 포함되어야 합니다. 이 가정 하에 평균 MPNN 은 분모를 $|V|^k$로 정렬하고 논리를 인식할 수 있습니다 (Theorem 1).

2. 로컬 모달리티 (얕은 깊이):

   • 정규성 요구 사항: 로컬 모달리티 ($E_{in}, E_{out}$) 만을 사용하는 식의 경우, 평균 MPNN 은 입력 그래프가 정규적(모든 노드가 동일한 인/아웃 차수를 가짐) 이고 집중 노드가 강하게 표시된(표시되어 있고 자기 루프를 가짐) 경우를 요구합니다. 이를 통해 네트워크는 로컬 이웃 크기를 정규화할 수 있습니다 (Theorem 2).
   • 정규성 완화: MPNN 이 평균 외에 합 또는 최대 집계를 사용할 수 있다면 정규성 가정을 철회할 수 있습니다. 이 경우 네트워크는 집중 노드가 강하게 표시된 모든 그래프에서 로컬 다항식 제약을 인식할 수 있습니다 (Theorem 3).

3. 혼합 모달리티 (얕은 깊이):

   • 글로벌 및 로컬 모달리티를 결합할 때, 이전 섹션의 결과를 결합할 수 있습니다. 평균 MPNN 은 정규적이고 강하게 표시된 그래프에서 이러한 식을 인식합니다 (Theorem 4).
   • 합/최대 집계를 추가하면 정규성 가정을 다시 제거할 수 있습니다 (Theorem 5).

4. 중첩 모달리티 (임의의 깊이):

   • 글로벌 중첩: 글로벌 모달리티를 중첩하는 것은 깊이 1 을 넘어서는 표현력을 증가시키지 않으며, 평탄화될 수 있습니다 (Proposition 1).
   • 로컬 중첩: 중첩된 로컬 모달리티를 가진 식의 경우, 논문은 $(T \circlearrowleft_\phi)^p_\bullet$라고 불리는 그래프 클래스를 도입합니다. 이는 집중 노드가 표시되어 있고, 그래프 구조가 특정 거리의 노드에 대해 고유한 흔적 (trace) 을 보장하여 이웃 카운트의 모호성을 피하는 "트리와 유사한" 구조입니다.
   • 결과: 평균 MPNN 은 이러한 트리와 유사하고 정규적이며 강하게 표시된 그래프에서 중첩된 로컬 PML 을 인식할 수 있습니다 (Theorem 6). 합/최대 집계가 허용된다면 정규성 제약이 제거되어 일반적인 트리와 유사하고 강하게 표시된 그래프에서 인식이 가능해집니다 (Theorem 7).

의의 및 주장
본 논문은 MPNN 이 선형 산술을 넘어 다항식 카운팅으로 일반화되기 위해 필요한 최소 조건을 식별한다고 주장합니다.

• 이론적 일반화: 결과는 평균 집계를 가진 MPNN 이 특정 구조적 속성 (표시된 노드, 정규성, 또는 트리와 유사성) 을 만족하는 입력 데이터가 제공된다면 다항식 커널에 의존하는 그래프 분류 (예: 다항식 커널을 가진 SVM) 에 사용된 기법을 일반화할 수 있음을 시사합니다.
• 집계의 역할: 이 연구는 평균 집계가 엄격한 구조적 가정 하에 다항식 카운팅에 충분하지만, 합 또는 최대 집계의 포함은 이러한 요구 사항 (특히 그래프 정규성 필요성 제거) 을 크게 완화함을 강조합니다.
• 한계: 저자들은 명시적으로 이러한 구조적 가정 (표시된 노드, 정규성, 또는 트리와 유사한 구조) 없이서는 평균 MPNN 이 모든 다항식 제약을 표현할 수 없다고 명시합니다. 예를 들어, Lemma 2 는 평균 MPNN 이 간단한 다항식 제약을 만족하는 특정 비정규 그래프들을 구별할 수 없음을 보여줍니다.

본 논문은 MPNN 이 다항식 카운팅 능력을 보유하고 있지만, 이를 실현하려면 특정 아키텍처 선택 (합/최대 추가) 이나 특정 데이터 전처리/구조적 가정 (노드 표시, 정규성 또는 트리와 유사한 구조 보장) 이 필요하다고 결론지었습니다. 향후 연구로는 현재 사용된 PML 프레임워크에서 다루지 않는 모달리티의 임의의 부울 조합과 서로 다른 거리에서의 카운트 비교를 탐구할 것을 제안합니다.