Department of Educational Technology, Zhejiang Normal University, Jinhua, China; School of Mathematics and Statistics, The University of New South Wales, Sydney, Australia.
Department of Physics, Princeton University, NJ, USA.
Neural Netw. 2020 Aug;128:188-198. doi: 10.1016/j.neunet.2020.04.028. Epub 2020 May 4.
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 a Haar basis, which is a sparse and localized orthonormal system for a coarse-grained chain on the 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 the graph, by which one then achieves a fast evaluation of Haar convolution between graph data and filters. We conduct experiments on GNNs equipped with Haar convolution, which demonstrates state-of-the-art results on graph-based regression and node classification tasks.
图神经网络 (GNNs) 由于在图结构数据的高维分类和回归任务中具有强大的能力，最近成为研究的热点。然而，由于 GNNs 通常通过图拉普拉斯的正交基来定义图卷积，因此当图的大小较大时，它们的计算成本很高。本文引入了 Haar 基，它是图上粗粒度链的稀疏且局部化的正交系统。在 Haar 基下的图卷积，称为 Haar 卷积，可以相应地为 GNNs 定义。Haar 基的稀疏性和局部性允许在图上进行快速 Haar 变换 (FHT)，从而实现图数据和滤波器之间的 Haar 卷积的快速评估。我们在配备 Haar 卷积的 GNNs 上进行实验，结果表明在基于图的回归和节点分类任务中取得了最先进的结果。
