  We propose a novel class of deep stochastic predictors for classifying metric
data on graphs within the PAC-Bayes risk certification paradigm. Classifiers
are realized as linearly parametrized deep assignment flows with random initial
conditions. Building on the recent PAC-Bayes literature and data-dependent
priors, this approach enables (i) to use risk bounds as training objectives for
learning posterior distributions on the hypothesis space and (ii) to compute
tight out-of-sample risk certificates of randomized classifiers more
efficiently than related work. Comparison with empirical test set errors
illustrates the performance and practicality of this self-certifying
classification method.
