2026
Minimax Sample Complexity of Graph Neural Networks: Lower Bounds and Structural Effects
ICLR 2026poster
Graph Neural Networks (GNNs) achieve strong empirical performance across domains, yet their fundamental statistical behavior remains poorly understood. This paper develops a minimax analysis of ReLU message-passing GNNs with explicit architectural assumptions, in both inductive (graph-level) and tr…