Convergence and Stability of Graph Convolutional Networks on Large Random Graphs
We study properties of Graph Convolutional Networks (GCNs) by analyzing their behavior on standard models of random graphs, where nodes are represented by random latent variables and edges are drawn according to a similarity kernel. This allows us to overcome the difficulties of dealing with discrete notions such as isomorphisms on very large graphs, by considering instead more natural geometric aspects. We first study the convergence of GCNs to their continuous counterpart as the number of nodes grows. Our results are fully non-asymptotic and are valid for relatively sparse graphs with an average degree that grows logarithmically with the number of nodes. We then analyze the stability of GCNs to small deformations of the random graph model. In contrast to previous studies of stability in discrete settings, our continuous setup allows us to provide more intuitive deformation-based metrics for understanding stability, which have proven useful for explaining the success of convolutional representations on Euclidean domains.
Code (1)
Tasks
validMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs
We study the convergence of message passing graph neural networks on random graph models to their continuous counterpart as the number of nodes tends to infinity. Until now, this convergence was only known for architectu…
Estimating the stability number of a random graph using convolutional neural networks
Graph combinatorial optimization problems are widely applicable and notoriously difficult to compute; for example, consider the traveling salesman or facility location problems. In this paper, we explore the feasibility …
Combinatorial OptimizationDeep LearningStability of Graph Convolutional Neural Networks to Stochastic Perturbations
Graph convolutional neural networks (GCNNs) are nonlinear processing tools to learn representations from network data. A key property of GCNNs is their stability to graph perturbations. Current analysis considers determi…
An Energy Efficient Distributed Gossip Algorithm for Wireless Sensor Networks based on a Randomized Markovian Duty-Cycling
This paper proposes a novel asynchronous consensus algorithm which is based on a continuous update rule and an energy efficient event triggered duty (wake-sleep) cycle based on a discrete Markov chain model. The system m…
Sinusoidal Initialization, Time for a New Start
Initialization plays a critical role in Deep Neural Network training, directly influencing convergence, stability, and generalization. Common approaches such as Glorot and He initializations rely on randomness, which can…