On the Trade-Off between Stability and Representational Capacity in
  Graph Neural Networks
Zhan Gao Amanda Prorok Elvin Isufi
Analyzing the stability of graph neural networks (GNNs) under topological
perturbations is key to understanding their transferability and the role of
each architecture component. However, stability has been investigated only for
particular architectures, questioning whether it holds for a broader spectrum
of GNNs or only for a few instances. To answer this question, we study the
stability of EdgeNet: a general GNN framework that unifies more than twenty
solutions including the convolutional and attention-based classes, as well as
graph isomorphism networks and hybrid architectures. We prove that all GNNs
within the EdgeNet framework are stable to topological perturbations. By
studying the effect of different EdgeNet categories on the stability, we show
that GNNs with fewer degrees of freedom in their parameter space, linked to a
lower representational capacity, are more stable. The key factor yielding this
trade-off is the eigenvector misalignment between the EdgeNet parameter
matrices and the graph shift operator. For example, graph convolutional neural
networks that assign a single scalar per signal shift (hence, with a perfect
alignment) are more stable than the more involved node or edge-varying
counterparts. Extensive numerical results corroborate our theoretical findings
and highlight the role of different architecture components in the trade-off.