Pyramid Graph Neural Network: A Graph Sampling and Filtering Approach for Multi-scale Disentangled Representations

Spectral methods for graph neural networks (GNNs) have achieved great success. Despite their success, many works have shown that existing approaches are mainly focused on low-frequency information which may not be pertinent to the task at hand. Recent efforts have been made to design new graph filters for wider frequency profiles, but it remains an open problem how to learn multi-scale disentangled node embeddings in the graph Fourier domain. In this paper, we propose a graph (signal) sampling and filtering framework, entitled Pyramid Graph Neural Network (PyGNN), which follows the Downsampling-Filtering-Upsampling-Decoding scheme. To be specific, we develop an ω-bandlimited downsampling approach to split input graph into subgraphs for the reduction of high-frequency components, then perform spectral graph filters on subgraphs to achieve node embeddings with different frequency bands, and propose a Laplacian smoothing-based upsampling approach to extrapolate the node embedding on subgraphs to the full set of vertices on the original graph. In the end, we add frequency-aware gated units to decode node embeddings of different frequencies for downstream tasks. Results on both homophilic and heterophilic graph datasets show its superiority over state-of-the-art methods.