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.
Introduction
Spectral Graph Neural Networks (GNNs) have emerged as a powerful paradigm for processing graph-structured data. However, they often suffer from an "optimization tax" that hinders their full potential. Recent research from the Australian National University identifies a fundamental mismatch between the two primary parameter groups in these models: the graph convolution parameters ($\Theta$), which handle structural filtering, and the feature transformation parameters ($W$), which project node features into a latent space.
The Optimization Challenge: Distorted Landscapes
In a typical spectral GNN, the number of parameters in $\Theta$ is often orders of magnitude smaller than those in $W$. Despite their small number, $\Theta$ parameters can exert a disproportionate influence on the loss function. This disparity leads to a "stretched" or poorly conditioned loss landscape, where standard gradient descent steps may be too aggressive for one group while being too slow for the other.
As illustrated in Figure 1, this distortion is particularly acute in heterophilic graphs (e.g., Texas), where connected nodes often belong to different classes. In contrast, homophilic graphs (e.g., Cora) exhibit a more regular, "spherical" landscape that is easier for standard optimizers to navigate.
Quantifying Difficulty: The Block Condition Number
To formally address this issue, the researchers introduced the block condition number of the Hessian matrix. By analyzing the curvature of the loss function relative to each parameter block ($H_{\Theta,\Theta}$ and $H_{W,W}$), they defined a metric $\alpha$ representing the ratio of their maximum eigenvalues.
Figure 2 demonstrates that $\alpha$ is significantly higher for heterophilic datasets like Texas and Chameleon compared to homophilic ones like Cora. This high ratio confirms that the optimization problem is inherently more difficult for heterophilic graphs due to the extreme sensitivity gap between parameter groups.
Proposed Solution: Asymmetric Learning
The authors propose Asymmetric Learning, a dynamic preconditioning technique designed to "whiten" the optimization landscape. Instead of a uniform learning rate, the method applies an asymmetric preconditioner that scales gradients based on the Gradient-Parameter Norm Ratio (GPNR). This ratio measures how fast a parameter group is updating relative to its current magnitude. By dynamically dampening or boosting updates, Asymmetric Learning balances the scales between $\Theta$ and $W$, effectively reducing the block condition number and smoothing the path to convergence.
Experimental Results
The method was evaluated across 18 benchmark datasets, including both small and large-scale heterophilic and homophilic graphs. Key findings include:
- Significant Performance Boosts: Spectral GNNs like ChebNet saw dramatic improvements, such as a +14.05% accuracy increase on the Texas dataset.
- Robustness: The approach proved insensitive to its internal smoothing hyperparameters, making it a reliable "plug-and-play" addition to existing architectures.
- Synergy with Orthogonal Bases: The method performs exceptionally well when paired with GNNs using orthogonal polynomial bases (e.g., JacobiConv), which naturally reduce interference between filter orders.
Conclusion
Asymmetric Learning provides a theoretically grounded solution to the long-standing optimization challenges in spectral GNNs. By addressing the sensitivity disparity between structural and feature parameters, it unlocks significant performance gains, particularly for complex heterophilic graph data.
Code Availability: https://github.com/Mia-321/asym-opt.git
Summary updated