グラフニューラルネットワーク（GNN）のグラフ分類における成功は、Weisfeiler-Lehman (1-WL) アルゴリズムと密接に関連しています。1-WL と GNN は、中心ノードに隣接するノードの特徴を反復的に集約することで、中心ノードを中心にした根付き部分木の表現を得ます。これらの根付き部分木の表現は、その後、単一の表現にプーリングされて全体のグラフを表します。しかし、根付き部分木は非木構造のグラフを表現する上で限られた表現力を有しています。この問題に対処するために、我々はネストされたグラフニューラルネットワーク（NGNN）を提案します。NGNN では、根付き部分木ではなく根付き部分グラフを使用してグラフを表現します。これにより、多くの同一の部分グラフ（而非樹形的部分木）を持つ2つのグラフが類似した表現を持つ傾向があります。重要なのは、各ノードの表現がその周囲の部分グラフよりも部分木をエンコードすることです。これを達成するために、NGNN は各ノードを中心とした局所的な部分グラフを抽出し、ベースとなる GNN を各部分グラフに適用して部分グラフの表現を学習します。その後、これらの部分グラフの表現をプーリングして全体のグラフ表現を得ます。我々は厳密な理論解析を行い、NGNN が 1-WL よりも厳密に強力であることを示しました。特に、r-正則グラフ（r-regular graphs）の大半を区別できることが証明されました。一方で 1-WL は常に失敗します。さらに、他のより強力な GNN とは異なり、NGNN は標準的な GNN よりも定数倍高い時間計算量しか導入しません。NGNN はプラグアンドプレイ型フレームワークであり、さまざまなベースとなる GNN と組み合わせることができます。我々は異なるベースとなる GNN を使用していくつかのベンチマークデータセットで NGNN をテストしました。結果として NGNN は一貫してそれらの性能を向上させ、すべてのデータセットにおいて非常に競争力のある性能を示しました。