INVESTIGATING EXPRESSIVE POWER CAPABILITIES OF GRAPH NEURAL NETWORKS

Abstract

The Capstone project investigates the expressive power of Graph Neural Networks (GNNs) from the perspective of graph filtering, specifically focusing on group of spectral GNNs that use polynomial approximations to model graph filters to learn from graph data. These models rely on graph signal processing (GSP) techniques, which are generalizations of classical signal processing over graphs. However, polynomial filters cannot fully capture the whole frequency range. Therefore, to address this problem, autoregressive moving average (ARMA) graph filters have been studied, which are based on rational function. However, they either have larger memory requirements or higher computational complexity depending on a specific model. Thus, a novel periodic ARMA GNN (pARMA-GNN) network is proposed, which is inspired by periodic ARMA graph filters. The main advantage of the proposed model is reduced memory requirements compared to other rational function based GNNs. Experiments on node classification in semi-supervised setting and graph classification have been conducted. Results show better performance of the proposed model compared to other baseline models in heterophilic datasets, while providing compet itive results in homophilic datasets. As a part of ablation study, the experiment on impact of each component of the proposed model has been done.