We introduce the concept of a Graph-Informed Neural Network (GINN), a hybrid approach combining deep learning with probabilistic graphical models (PGMs) that acts as a surrogate for physics-based representations of multiscale and multiphysics systems. GINNs address the twin challenges of removing intrinsic computational bottlenecks in physics-based models and generating large data sets for estimating probability distributions of quantities of interest (QoIs) with a high degree of confidence. Both the selection of the complex physics learned by the NN and its supervised learning/prediction are informed by a PGM, which includes the formulation of structured priors for tunable control variables (CVs) to account for their mutual correlations and ensure physically sound CV and QoI distributions. GINNs accelerate the prediction of QoIs essential for simulation-based decision-making where generating sufficient sample data using physics-based models alone is often prohibitively expensive. Using applications grounded in energy storage, we describe the construction of GINNs for a domain-aware Bayesian network that embeds a homogenized model of supercapacitor dynamics and a data-driven Bayesian network for a Langmuir adsorption model. Both examples demonstrate the ability of GINNs to produce kernel density estimates of relevant non-Gaussian, skewed QoIs with tight confidence intervals.