  Graph Neural Networks (GNNs), particularly Graph Convolutional Neural
Networks (GCNNs), have emerged as pivotal instruments in machine learning and
signal processing for processing graph-structured data. This paper proposes an
analysis framework to investigate the sensitivity of GCNNs to probabilistic
graph perturbations, directly impacting the graph shift operator (GSO). Our
study establishes tight expected GSO error bounds, which are explicitly linked
to the error model parameters, and reveals a linear relationship between GSO
perturbations and the resulting output differences at each layer of GCNNs. This
linearity demonstrates that a single-layer GCNN maintains stability under graph
edge perturbations, provided that the GSO errors remain bounded, regardless of
the perturbation scale. For multilayer GCNNs, the dependency of system's output
difference on GSO perturbations is shown to be a recursion of linearity.
Finally, we exemplify the framework with the Graph Isomorphism Network (GIN)
and Simple Graph Convolution Network (SGCN). Experiments validate our
theoretical derivations and the effectiveness of our approach.
