Spectral Graph Neural Network: Polynomial Approximation and Optimization

Add to your list(s) Download to your calendar using vCal

• Keke Huang, National University of Singapore
• Wednesday 18 October 2023, 17:30-18:30
• Lecture Theatre 2, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Pietro Lio.

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.

This talk is part of the Foundation AI series.

This talk is included in these lists:

• Lecture Theatre 2, Computer Laboratory, William Gates Building

Note that ex-directory lists are not shown.