그래프 신경망(GNN)의 그래프 분류 성공은 와이스페일러-레만(1-WL) 알고리즘과 밀접한 관련이 있습니다. 1-WL과 GNN은 주변 노드 특성을 중심 노드로 반복적으로 집계하여, 중심 노드 주변의 루트 트리를 인코딩하는 노드 표현을 얻습니다. 이러한 루트 트리 표현들은 전체 그래프를 나타내기 위해 단일 표현으로 풀링됩니다. 그러나, 루트 트리는 비트리(non-tree) 그래프를 표현하는 데 한계가 있습니다. 이를 해결하기 위해 우리는 중첩 그래프 신경망(Nested Graph Neural Networks, NGNNs)을 제안합니다.NGNN은 루트 트리 대신 루트 서브그래프(rooted subgraphs)로 그래프를 표현하여, 많은 동일한 서브그래프(서브트리가 아닌)를 공유하는 두 그래프가 유사한 표현을 가지도록 합니다. 핵심은 각 노드 표현이 그 주변의 서브그래프보다는 서브트리를 인코딩하도록 하는 것입니다. 이를 달성하기 위해 NGNN은 각 노드 주변의 로컬 서브그래프를 추출하고, 기본 GNN을 각 서브그래프에 적용하여 서브그래프 표현을 학습합니다. 전체 그래프 표현은 이러한 서브그래프 표현들을 풀링하여 얻어집니다.우리는 엄격한 이론적 분석을 제공하여 NGNN이 1-WL보다 엄밀히 더 강력하다는 것을 보여주었습니다. 특히, NGNN이 거의 모든 r-정규 그래프(r-regular graphs)를 구별할 수 있다는 것을 증명하였는데, 이는 1-WL이 항상 실패하는 경우입니다. 또한, 다른 더 강력한 GNN들과 달리 NGNN은 표준 GNN들보다 시간 복잡도가 상수 배수만큼만 증가합니다. NGNN은 다양한 기본 GNN들과 결합할 수 있는 플러그 앤 플레이(plug-and-play) 프레임워크입니다. 우리는 여러 벤치마크 데이터셋에서 다른 기본 GNN들과 함께 NGNN을 테스트하였습니다. 결과적으로 NGNN은 그들의 성능을 일관되게 개선하며 모든 데이터셋에서 매우 경쟁력 있는 성능을 보였습니다.