Asymmetric Learning for Spectral Graph Neural Networks

Fangbing Liu, Qing Wang

Introduction

Spectral Graph Neural Networks (GNNs) leverage the frequency domain of graphs to capture intricate structural patterns. Despite their theoretical advantages, these models are often difficult to optimize. This paper identifies a structural imbalance in parameter updates as a primary cause of training instability and proposes Asymmetric Learning, a dynamic preconditioning strategy that smooths the loss landscape and significantly improves performance, particularly on heterophilic graphs.

The Optimization Challenge: Parameter Imbalance

Spectral GNNs typically involve two distinct sets of parameters with very different roles and scales:

  1. $Θ$ (Graph Convolution Parameters): These define the spectral filter shape and are usually low-dimensional (e.g., < 20).
  2. $W$ (Feature Transformation Parameters): These handle high-dimensional node features and can contain thousands of parameters.

The authors demonstrate that these parameter groups evolve at vastly different rates. This disparity leads to a "stretched" loss landscape characterized by a high block condition number in the Hessian matrix. In such environments, standard optimizers like Adam or SGD struggle with narrow, steep valleys, often converging to suboptimal local minima. This issue is particularly acute in heterophilic graphs, where connected nodes often belong to different classes, requiring more complex filtering.

Visualizing the Loss Landscape

The impact of this imbalance is visible in the curvature of the loss function. Heterophilic datasets like Texas exhibit much more challenging optimization surfaces compared to homophilic datasets like Cora. Asymmetric Learning aims to mitigate these steep gradients to allow for smoother convergence.

Loss landscapes for Texas and Cora datasets, illustrating the 'stretched' surfaces that Asymmetric Learning aims to smooth.

Proposed Method: Asymmetric Learning

To address this, the researchers introduce a dynamic preconditioning framework designed to "re-condition" gradients during training:

  • Gradient-Parameter Norm Ratio (GPNR): A metric used to monitor the relative update speeds of $Θ$ and $W$. The authors found that $Θ$ typically updates much faster, causing the imbalance.
  • Asymmetric Preconditioner ($R^t$): A "wrapper" for existing optimizers that scales gradients based on an exponential moving average of parameter norms. This ensures that both parameter groups evolve at a compatible pace, effectively "rounding out" the loss landscape.
  • Theoretical Foundation: The authors provide mathematical proof that this scaling reduces the block condition number of the Hessian, facilitating more stable and efficient optimization.

Experimental Evaluation

The method was tested across 18 benchmark datasets, ranging from small-scale heterophilic graphs (e.g., Texas, Wisconsin) to large-scale homophilic ones (e.g., Cora, Citeseer).

Key Results

  • Heterophilic Performance: The most dramatic improvements were seen on heterophilic graphs. For instance, on the Texas dataset, ChebNet's accuracy increased from 36.76% to 50.81% (+14.05%).
  • Broad Applicability: Across six small heterophilic datasets, the average accuracy gain was 3.08%.
  • Robustness: The method proved effective across various scales and was relatively insensitive to hyperparameter tuning, making it a practical addition to GNN training pipelines.

Conclusion

Asymmetric Learning provides a simple yet powerful solution to the optimization hurdles faced by spectral GNNs. By acknowledging and correcting the inherent imbalance between filter weights and feature transforms, it unlocks the full potential of spectral methods, especially in the challenging domain of heterophilic graph learning.

Summary updated

Abstract

Optimizing spectral graph neural networks (GNNs) remains a critical challenge in the field, yet the underlying processes are not well understood. In this paper, we investigate the inherent differences between graph convolution parameters and feature transformation parameters in spectral GNNs and their impact on the optimization landscape. Our analysis reveals that these differences contribute to a poorly conditioned problem, resulting in suboptimal performance. To address this issue, we introduce the concept of the block condition number of the Hessian matrix, which characterizes the difficulty of poorly conditioned problems in spectral GNN optimization. We then propose an asymmetric learning approach, dynamically preconditioning gradients during training to alleviate poorly conditioned problems. Theoretically, we demonstrate that asymmetric learning can reduce block condition numbers, facilitating easier optimization. Extensive experiments on eighteen benchmark datasets show that asymmetric learning consistently improves the performance of spectral GNNs for both heterophilic and homophilic graphs. This improvement is especially notable for heterophilic graphs, where the optimization process is generally more complex than for homophilic graphs. Code is available at https://github.com/Mia-321/asym-opt.git.
BibTeX
@inproceedings{liu2025asymmetric,
  author = {Fangbing Liu and Qing Wang},
  title = {{Asymmetric Learning for Spectral Graph Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i18.34069},
}
Figure