ProgNet: Program-Grounded Evidence Composition for Interpretable Graph Classification

We present ProgNet, a graph learning framework for interpretable graph classification that treats explanatory structures as first-class, reusable components of the prediction mechanism. Departing from existing methods that generate isolated, instance-specific explanations, ProgNet introduces a paradigm where reasoning is grounded in a shared vocabulary of reusable structural programs. Specifically, ProgNet represents each graph using a shared vocabulary of human-interpretable programs written in a graph pattern description language, grounding predictions in explicit structural evidence rather than latent embeddings alone. The vocabulary is constructed to promote both coverage and diversity, yielding compact and reusable structural primitives that generalize across instances. Classification is performed via an inherently decomposable evidence composition network that scores and aggregates program-level evidence, resulting in predictions whose logits admit additive, signed attributions. Extensive experiments on eight graph classification benchmarks demonstrate that ProgNet achieves competitive predictive accuracy while providing more faithful explanations.