Abstract
This work establishes rigorous, novel and widely applicable stabilityguarantees and transferability bounds for graph convolutional networks --without reference to any underlying limit object or statistical distribution.Crucially, utilized graph-shift operators (GSOs) are not necessarily assumed tobe normal, allowing for the treatment of networks on both directed- and for thefirst time also undirected graphs. Stability to node-level perturbations isrelated to an 'adequate (spectral) covering' property of the filters in eachlayer. Stability to edge-level perturbations is related to Lipschitz constantsand newly introduced semi-norms of filters. Results on stability to topologicalperturbations are obtained through recently developed mathematical-physicsbased tools. As an important and novel example, it is showcased that graphconvolutional networks are stable under graph-coarse-graining procedures(replacing strongly-connected sub-graphs by single nodes) precisely if the GSOis the graph Laplacian and filters are regular at infinity. These newtheoretical results are supported by corresponding numerical investigations.