Graph convolutional neural networks (GCNNs) are nonlinear processing tools to learn representations from network data. A key property of GCNNs is their stability to graph perturbations. Current analysis considers deterministic perturbations but fails to provide relevant insights when topological changes are random. This paper investigates the stability of GCNNs to stochastic graph perturbations induced by link losses. In particular, it proves the expected output difference between the GCNN over random perturbed graphs and the GCNN over the nominal graph is upper bounded by a factor that is linear in the link loss probability. We perform the stability analysis in the graph spectral domain such that the result holds uniformly for any graph. This result also shows the role of the nonlinearity and the architecture width and depth, and allows identifying handle to improve the GCNN robustness. Numerical simulations on source localization and robot swarm control corroborate our theoretical findings.

Stochastic graph neural networks (SGNNs) are information processing architectures that can learn representations from data over random graphs. SGNNs are trained with respect to the expected performance, but this training comes with no guarantee about the deviation of particular output realizations around the optimal mean. To overcome this issue, we propose a learning strategy for SGNNs based on a variance constrained optimization problem, balancing the expected performance and the stochastic deviation. To handle the variance constraint in the stochastic optimization problem, training is undertaken in the dual domain. We propose an alternating primal-dual learning algorithm that updates the primal variable (SGNN parameters) with gradient descent and the dual variable with gradient ascent. We show the stochastic deviation is explicitly controlled through Chebyshev inequality and analyze the optimality loss induced by the primal-dual learning. Through numerical simulations, we observe a strong performance in expectation with a controllable deviation corroborating the theoretical findings.