2021/06/07 by Juan Cerviño, Cervino, Juan, Luana Ruiz +3 · 3 citations
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning and ELM #Signal Processing (eess.SP) #Stochastic Gradient Optimization Techniques #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2106.03693
openalex publication_date 2021/06/07 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Graph neural networks (GNNs) use graph convolutions to exploit network invariances and learn meaningful feature representations from network data. However, on large-scale graphs convolutions incur in high computational cost, leading to scalability limitations. Leveraging the graphon -- the limit object of a graph -- in this paper we consider the problem of learning a graphon neural network (WNN) -- the limit object of a GNN -- by training GNNs on graphs sampled from the graphon. Under smoothness conditions, we show that: (i) the expected distance between the learning steps on the GNN and on the WNN decreases asymptotically with the size of the graph, and (ii) when training on a sequence of growing graphs, gradient descent follows the learning direction of the WNN. Inspired by these results, we propose a novel algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training. This algorithm is further benchmarked on a decentralized control problem, where it retains comparable performance to its large-scale counterpart at a reduced computational cost.