연구진은 그래프 신경망(GNN)과 논리 형식주의 간의 연결고리를 구조적 보존성을 통해 확립했어요. 임베딩, 주입 준동형사상, 준동형사상과 같은 구조적 속성을 유지하는 GNN 분류기의 논리적 표현력을 분석했죠. 각 속성에 따라 GNN의 표현력을 특징짓는 등급 모달 논리 조각이 존재하며, 이는 특정 아키텍처 선택에 독립적이에요.
임베딩, 주입 준동형사상, 준동형사상에 대한 구조적 보존성은 각각 존재 등급 모달 논리, 긍정적 존재 등급 모달 논리, 존재적 긍정적 모달 논리를 나타내요. 연구는 GNN의 광범위한 클래스의 표현력을 특정 아키텍처 선택에 독립적으로 특징짓고, 각 클래스에 동일한 표현력을 갖는 GNN 아키텍처가 존재함을 보여줘요.
연구팀은 새로운 잘-순서 관계 결과와 함께 유한한 표현을 사용하여, 풀림 불변 클래스를 분석했어요.