Graph Neural Networks With High-Order Polynomial Spectral Filters

Area of Science:

• Graph Neural Networks
• Machine Learning
• Spectral Graph Theory

Background:

• Graph Neural Networks (GNNs) utilize polynomial spectral filters for graph convolutions.
• High-order polynomial approximations in GNNs can detect more structural information but lead to node representation indistinguishability and performance degradation due to overfitting.
• Existing methods struggle with information processing in high-order neighborhoods, limiting GNN scalability.

Purpose of the Study:

• To theoretically identify and address the overfitting issue in polynomial coefficients of GNN spectral filters.
• To propose a novel flexible spectral-domain graph filter that improves GNN performance and receptive field size.
• To reduce memory demand and adverse impacts on message transmission in GNNs with large receptive fields.

Main Methods:

• Restricting polynomial coefficients through dimensionality reduction and sequential assignment of a forgetting factor.
• Transforming coefficient optimization into hyperparameter tuning.
• Developing a flexible spectral-domain graph filter for GNNs.

Main Results:

• The proposed filter significantly reduces memory requirements and mitigates negative impacts on message transmission for large receptive fields.
• GNN performance is substantially improved in large receptive fields, with a notable multiplication of their effective range.
• The superiority of high-order approximation is validated across diverse datasets, particularly in strongly hyperbolic datasets.

Conclusions:

• The novel spectral-domain graph filter effectively overcomes the limitations of traditional GNN filters in high-order neighborhoods.
• The proposed method enhances GNN capabilities, enabling better performance and expanded receptive fields, especially for complex graph structures.
• This work offers a significant advancement in GNN efficiency and effectiveness for large-scale graph analysis.