Abstract
Graph Neural Networks (GNNs) have become a topic of intense research recentlydue to their powerful capability in high-dimensional classification andregression tasks for graph-structured data. However, as GNNs typically definethe graph convolution by the orthonormal basis for the graph Laplacian, theysuffer from high computational cost when the graph size is large. This paperintroduces the Haar basis, a sparse and localized orthonormal system for graph,constructed from a coarse-grained chain on the graph. The graph convolutionunder Haar basis --- the 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 the graphsignals and the filters can be achieved. We conduct preliminary experiments onGNNs equipped with Haar convolution, which can obtain state-of-the-art resultsfor a variety of geometric deep learning tasks.