When Does A Spectral Graph Neural Network Fail in Node Classification?
This work addresses the problem of unreliable GNN performance for researchers and practitioners in graph learning, offering theoretical insights and a practical improvement strategy, though it is incremental as it builds on existing spectral GNN frameworks.
The paper investigates when spectral Graph Neural Networks (GNNs) fail in node classification by analyzing prediction error using graph indicators like homophily degree and response efficiency, finding that filters with low response efficiency on label differences are prone to failure, and proposes a data-driven filter bank strategy that shows consistent experimental results.
Spectral Graph Neural Networks (GNNs) with various graph filters have received extensive affirmation due to their promising performance in graph learning problems. However, it is known that GNNs do not always perform well. Although graph filters provide theoretical foundations for model explanations, it is unclear when a spectral GNN will fail. In this paper, focusing on node classification problems, we conduct a theoretical analysis of spectral GNNs performance by investigating their prediction error. With the aid of graph indicators including homophily degree and response efficiency we proposed, we establish a comprehensive understanding of complex relationships between graph structure, node labels, and graph filters. We indicate that graph filters with low response efficiency on label difference are prone to fail. To enhance GNNs performance, we provide a provably better strategy for filter design from our theoretical analysis - using data-driven filter banks, and propose simple models for empirical validation. Experimental results show consistency with our theoretical results and support our strategy.