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.

该论文提出了一种新的自适应 Krylov 子空间方法，通过优化多项式基，在图谱上实现了对不同异质度的图进行自适应滤波，并利用扩展的 AdaptKry 捕捉图的复杂特征并提供对其内在复杂性的见解。

优化多项式图滤波器：一种新的自适应克莱洛夫子空间方法

Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace  Approach

Polynomial graph filters have been widely used as guiding principles in the
design of Graph Neural Networks (GNNs). Recently, the adaptive learning of the
polynomial graph filters has demonstrated promising performance for modeling
graph signals on both homophilic and heterophilic graphs, owning to their
flexibility and expressiveness. In this work, we conduct a novel preliminary
study to explore the potential and limitations of polynomial graph filter
learning approaches, revealing a severe overfitting issue. To improve the
effectiveness of polynomial graph filters, we propose Auto-Polynomial, a novel
and general automated polynomial graph filter learning framework that
efficiently learns better filters capable of adapting to various complex graph
signals. Comprehensive experiments and ablation studies demonstrate significant
and consistent performance improvements on both homophilic and heterophilic
graphs across multiple learning settings considering various labeling ratios,
which unleashes the potential of polynomial filter learning.

本文提出了一种新的自动多项式图滤波器学习框架 ——Auto-Polynomial，能够更高效地学习适应各种复杂图信号的滤波器，从而解决了多项式图滤波器学习中的过拟合问题，并在多个学习设置下，考虑各种标记比率，显著提高了同构和异构图的性能。