Convergence and Stability of Graph Convolutional Networks on Large Random Graphs

We study properties of Graph Convolutional Networks (GCNs) by analyzing their\nbehavior on standard models of random graphs, where nodes are represented by\nrandom latent variables and edges are drawn according to a similarity kernel.\nThis allows us to overcome the difficulties of dealing with discrete notions\nsuch as isomorphisms on very large graphs, by considering instead more natural\ngeometric aspects. We first study the convergence of GCNs to their continuous\ncounterpart as the number of nodes grows. Our results are fully non-asymptotic\nand are valid for relatively sparse graphs with an average degree that grows\nlogarithmically with the number of nodes. We then analyze the stability of GCNs\nto small deformations of the random graph model. In contrast to previous\nstudies of stability in discrete settings, our continuous setup allows us to\nprovide more intuitive deformation-based metrics for understanding stability,\nwhich have proven useful for explaining the success of convolutional\nrepresentations on Euclidean domains.\n