Abstract

Graph Neural Networks (GNNs), functioning as spectral graph filters, have found extensive applications in practical scenarios. However, deriving optimal graph filters through eigendecomposition of the Laplacian matrix is computationally prohibitive. To address this challenge, polynomial graph filters have been proposed as an approximation method. These filters leverage diverse polynomial bases for training, yet a unified exploration of these filters for optimization is lacking in existing studies.

In this presentation, we systematically examine existing polynomial filters within a unified framework. Specifically, we investigate polynomial graph filters of identical degrees within the Krylov subspace of the same order, thus providing equivalent theoretical expressive power. Subsequently, we delve into the asymptotic convergence behavior of polynomials within this unified Krylov subspace. Our analysis reveals the limited adaptability of these polynomials in graphs with varying degrees of heterophily. Inspired by these insights, we introduce a novel adaptive Krylov subspace approach. This method optimizes polynomial bases with control over the graph spectrum, allowing adaptation to diverse graphs with different heterophily degrees. Based on this approach, we propose AdaptKry, an optimized polynomial graph filter that uses the adaptive Krylov basis. Moreover, considering the complex nature of graphs, we extend AdaptKry by incorporating multiple adaptive Krylov bases without additional training costs. This extended version captures the intricate characteristics of graphs, providing valuable insights into their complexity.

Keke Huang is a Research Fellow at the National University of Singapore. He received his Ph.D. degree from Nanyang Technological University in Singapore. His research primarily focuses on graph algorithm design and analysis, approximation algorithms in social networks, and graph neural networks.