How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing

谱图神经网络（GNN），又称为图滤波器，已经在异质图中得到了越来越广泛的应用。最优图滤波器依赖于拉普拉斯特征分解用于傅里叶变换。为了避免计算量过大，已经提出了许多多项式滤波器。然而，在大多数这些滤波器中，多项式是预定义的，在不同的图中保持不变，无法适应异质性的不同程度。针对这一问题，我们通过深入的理论分析揭示了期望多项式基的谱性质与异质性程度之间的内在关联。随后，我们开发了一种新颖的自适应异质性基础，其中基向量相互形成反映图的异质性程度的角度。我们将这种异质性基础与同质性基础相结合，构建了一个通用的多项式基础UniBasis，它设计了基于多项式滤波器的图神经网络UniFilter。它优化了GNN中的卷积和传播，从而有效地限制了过度平滑和减轻了过度压缩。我们在各种真实世界和合成数据集上进行了广泛的实验，这些数据集具有不同程度的异质性，支持UniFilter的优越性。这些结果不仅证明了UniBasis的通用性，还突显了它在图形解释方面的熟练程度。

论文旨在解决图神经网络中多样性图的谱滤波器问题，即预定义的多项式滤波器无法适应不同图的异质性程度的问题。

论文提出了一种新的自适应异质性基础，通过理论分析将谱多项式基础的特性与异质性程度相联系，并将其与同质性基础相结合构建出一种通用的多项式基础UniBasis，从而设计出一种新的谱滤波器UniFilter，用于优化图神经网络中的卷积和传播，有效限制了过度平滑和过度压缩。

论文通过广泛的实验验证了UniFilter的优越性，并展示了UniBasis的通用性和解释性，实验使用了多种不同的真实和合成数据集，证明了UniFilter在不同异质性程度下的表现。论文没有开源代码。

最近在这个领域中，一些相关的研究包括：《Semi-supervised Classification with Graph Convolutional Networks》、《Graph Attention Networks》、《Adaptive Graph Convolutional Networks》等。