Fast Haar Transforms for Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) have become a topic of intense research recently due to their powerful capability in high-dimensional classification and regression tasks for graph-structured data. However, as GNNs typically define the graph convolution by the orthonormal basis for the graph Laplacian, they suffer from high computational cost when the graph size is large. This paper introduces Haar basis which is a sparse and localized orthonormal system for a coarse-grained chain on graph. The graph convolution under Haar basis, called Haar convolution, can be defined accordingly for GNNs. The sparsity and locality of the Haar basis allow Fast Haar Transforms (FHTs) on graph, by which a fast evaluation of Haar convolution between graph data and filters can be achieved. We conduct experiments on GNNs equipped with Haar convolution, which demonstrates state-of-the-art results on graph-based regression and node classification tasks.

arXiv comment24 pages, 5 figures, 3 tables

References in corpus (21)

• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Geometric deep learning: going beyond Euclidean data
• Fast and Accurate Modeling of Molecular Atomization Energies with Machine Learning
• ANI-1: An extensible neural network potential with DFT accuracy at force field computational cost
• Graph Embedding Techniques, Applications, and Performance: A Survey
• A Review of Relational Machine Learning for Knowledge Graphs
• Quantum-Chemical Insights from Deep Tensor Neural Networks
• Graph Neural Networks: A Review of Methods and Applications
• Deep Convolutional Networks on Graph-Structured Data
• Simplifying Graph Convolutional Networks
• Convolutional Networks on Graphs for Learning Molecular Fingerprints
• Massively Multitask Networks for Drug Discovery
• Attention-based Graph Neural Network for Semi-supervised Learning
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Deep Learning on Graphs: A Survey
• Accelerated filtering on graphs using Lanczos method
• Nearly Optimal Sparse Fourier Transform
• A tree-based kernel for graphs with continuous attributes
• PAN: Path Integral Based Convolution for Deep Graph Neural Networks