zkMPNN: Query-Local Zero-Knowledge Proofs of Complete Message-Passing Inference

Message passing neural networks (MPNNs) are a powerful class of deep learning models for graph-structured data. To our knowledge, no existing approaches to verifiable machine learning establish both the correctness of the computation and the completeness of the required neighbors and intermediate states for a prediction. This paper formalizes this requirement as complete GNN verification and proposes zkMPNN, a modular framework for complete, query-local graph neural network (GNN) inference over committed models and graphs using zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs). Our evaluation demonstrates end-to-end proving for all 48 selected cases across four GNN families on node-classification and link-prediction tasks. Compressed proofs are 14.2–18.4 KiB and verify in 3.2–11.1 s with the public parameters and verifier key available. Controlled synthetic experiments show that proving costs depend jointly on query dependencies and authentication-circuit shape, rather than total graph size alone.