Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks

Abstract

Recently, neural network based approaches have achieved significant improvement for solving large, complex, graph-structured problems. However, their bottlenecks still need to be addressed, and the advantages of multi-scale information and deep architectures have not been sufficiently exploited. In this paper, we theoretically analyze how existing Graph Convolutional Networks (GCNs) have limited expressive power due to the constraint of the activation functions and their architectures. We generalize spectral graph convolution and deep GCN in block Krylov subspace forms and devise two architectures, both with the potential to be scaled deeper but each making use of the multi-scale information in different ways. We further show that the equivalence of these two architectures can be established under certain conditions. On several node classification tasks, with or without the help of validation, the two new architectures achieve better performance compared to many state-of-the-art methods.

arXiv commentAccepted and to be published by NeurIPS 2019

References in corpus (9)

• Semi-Supervised Classification with Graph Convolutional Networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Geometric deep learning: going beyond Euclidean data
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Graph Partition Neural Networks for Semi-Supervised Classification
• Improved Analyses of the Randomized Power Method and Block Lanczos Method