  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.
