Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace
  Approach
Keke Huang Wencai Cao Hoang Ta Xiaokui Xiao Pietro Liò
Graph Neural Networks (GNNs), known as spectral graph filters, find a wide
range of applications in web networks. To bypass eigendecomposition, polynomial
graph filters are proposed to approximate graph filters by leveraging various
polynomial bases for filter training. However, no existing studies have
explored the diverse polynomial graph filters from a unified perspective for
optimization.
  In this paper, we first unify polynomial graph filters, as well as the
optimal filters of identical degrees into the Krylov subspace of the same
order, thus providing equivalent expressive power theoretically. Next, we
investigate the asymptotic convergence property of polynomials from the unified
Krylov subspace perspective, revealing their limited adaptability in graphs
with varying heterophily degrees. Inspired by those facts, we design a novel
adaptive Krylov subspace approach to optimize polynomial bases with provable
controllability over the graph spectrum so as to adapt various heterophily
graphs. Subsequently, we propose AdaptKry, an optimized polynomial graph filter
utilizing bases from the adaptive Krylov subspaces. Meanwhile, in light of the
diverse spectral properties of complex graphs, we extend AdaptKry by leveraging
multiple adaptive Krylov bases without incurring extra training costs. As a
consequence, extended AdaptKry is able to capture the intricate characteristics
of graphs and provide insights into their inherent complexity. We conduct
extensive experiments across a series of real-world datasets. The experimental
results demonstrate the superior filtering capability of AdaptKry, as well as
the optimized efficacy of the adaptive Krylov basis.