Limitless stability for Graph Convolutional Networks

  • 2023-01-30 13:38:49
  • Christian Koke
  • 0


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.


Quick Read (beta)

loading the full paper ...