그래프 신경망 (GNN)의 구조적 보존과 논리적 표현력

그래프 신경망 (GNNs)과 논리적 형식주의 (logical formalisms) 사이의 가교는 집계 (aggregation), 결합 (combination), 활성화 함수 (activation functions)의 유형과 같은 구조적 선택을 고정함으로써 구축되어 왔습니다. 이러한 선택은 논리식 (logical formulae)이 동등한 GNN으로 번역될 수 있고, 반대로 GNN이 동등한 논리식으로 번역될 수 있음을 보여줌으로써, 논리적 형식주의와 긴밀한 대응 관계를 얻을 수 있는 제한된 GNN 클래스를 정의합니다. 본 논문에서는 구조적 속성인 임베딩 (embeddings, extensions), 단사 준동형 (injective homomorphisms), 그리고 준동형 (homomorphisms) 하에서 보존되는 GNN 분류기 클래스의 논리적 표현력 (logical expressiveness)을 확립함으로써 의미론적 관점을 취합니다. 우리는 이러한 각 속성에 대해, 해당 GNN 클래스를 특징짓는 등급 양상 논리 (graded modal logic)의 파편 (fragment)이 존재함을 보여줍니다. 특히, 임베딩, 단사 준동형, 그리고 준동형 하에서의 보존은 각각 존재 양상 논리 (existential graded modal logic), 그 존재-긍정 파편 (existential-positive fragment), 그리고 존재-긍정 양상 논리 (existential-positive modal logic)에 대응합니다. 이러한 결과는 특정 구조적 선택과 무관하게 광범위한 GNN 클래스의 표현력을 특징짓지만, 우리는 또한 이러한 각 클래스가 동일한 표현력을 가진 GNN 구조를 허용함을 보여줍니다. 기술적으로, 우리의 접근 방식은 제한된 높이를 가진 트리 (trees of bounded height)에 대한 새로운 준순서 (well-quasi-order) 결과를 사용하여, 언래블링 불변 (unravelling-invariant) 클래스의 유한한 표현을 산출합니다.